운영체제: 페이지 교체 알고리즘

 페이지 교체 알고리즘에 따라, 효율적으로 페이지를 교체하거나 비효율적으로 페이지가 교체 될 수 있다. 이에 페이지를 교체하는 알고리즘을 알아보고자 한다.

 

FIFO Algorithm

 공간이 부족할 경우 가장 먼저 할당된 페이지를 할당 해제 하는 방식이다. 가장 간단한 방식으로 초기화 과정의 코드는 더 이상 불필요할 것이라는 아이디어로 설계되었다. 하지만 대체로 효율적이지 않다.

 

Figure 1. FIFO page-replacement algorithm.

 그림 1과 같이 FIFO 방식으로 페이지를 관리하게 되면, 페이지 공간이 부족할 경우 가장 먼저 추가된 값 부터 삭제 되는 것을 알 수 있다. FIFO 방식으로 입력되는 값에 대한 page fault 발생 횟수는 15이다. 단순히 삽입된 순서에 따라 page-out을 하게 되므로, 지속적으로 사용하는 페이지에 대해서 빈번하게 page-in/out이 일어나는 비효율적인 경향을 볼 수 있다.

 

Belady's Anomaly

 그림 1의 page frame은 3이므로 빈번한 page fault가 일어난다. 따라서 pae frame의 수가 증가하면 더 많은 페이지를 적재할 수 있어, page fault 수가 줄어들 것이다. 하지만, 특정한 페이지에 대해서는 page frame이 증가하여도 page fault가 증가하는 현상이 발생한다.

 

OPT (MIN)

 Optimal하게 가장 오랫동안 사용되지 않을 페이지를 page-out하는 방식이다.

Figure 2. Optimal page-replacement algorithm.

  그림 2와 같이 7은 초기에 메모리에 할당 후 끝에 다다를때 까지 사용되지 않는다. 이에 7이 victim으로 선택되어 page-out 되는 것을 알 수 있다. FIFO와 달리 OPT의 page fault 횟수는 9회이다. 상대적으로 오버헤드가 작아 효율적으로 보이지만 이 방식은 실제로 구현이 불가능하다. 향후에 어떤 데이터를 사용할지 알 수 없기 때문이다.

 

LRU

 Least Recently Used는 가장 최근에 사용되었다면, 향후에도 사용될 가능성이 크다고 판단하여 최근에 사용되지 않는 페이지를 victim으로 판단하는 방식이다.

 

Figure 3. LRU page-repalcement algorithm.

 그림 3을 보면 7을 page-in 후에 사용되지 않았으므로 victim으로 선정되어 page-out 된다. 그 다음 victim은 최근에 사용된 2, 0과 달리 가장 이전에 사용된 1이 victime이 된다. page fault 횟수는 12회로 OPT 보다는 많지만 FIFO보다는 작은 경향을 보인다. 현재 가장 많이 사용되고 있는 페이지 교체 방식이다.