페이지 교체 전략
지금부터 설명하는 페이지 교체 전략은 Fixed allocation 즉 paging system에서 사용될 수 있는 기법들이다.
Opt Algorithm
page fault를 최소로 만드는 알고리즘으로 최적의 솔루션이라고 불린다. 이 기법은 가장 오랫동안 참조되지 않을 페이지와 교체하는 방식으로 실현불가능한 방법이다. 다른 교체 기법들의 성능 평가도구로 사용된다.
Random Algorithm
무작위로 교체할 page를 고르는 방식이다. 이 방식은 일단 비용이 매우 저렴하다. 따라서 페이지 기법들의 평가기준이 된다. 만약 이 알고리즘보다 성능이 별로라면 굳이 쓸필요 없는 교체기법인 것이다.
FIFO(first in first out) Algorithm
가장 오래된 page를 교체하는 방식으로 적재된 시간을 기억하고 있어야한다. 이 기법은 locality에 대한 고려가 없기 때문에 자주 사용되는 page가 교체될 가능성이 있다. 따라서 FIFO Anomaly라는 현상이 발생하는데 page frame을 더 많이 할당해줘도 page fault가 증가하는 현상이다.
LRU(least recently used) Algorithm
가장 오랫동안 참조되지 않은 page를 교체하는 것이다. page가 참조될 때 마다 시간을 기록해야한다. 이 방법은 locality를 고려했기 때문에 좋은 성능을 보여준다. 그리고 실제로 가장 많이 사용된다.
하지만 이도 loop실행에 필요한 크기보다 작은 수의 page frame이 할당된 경우에는 급격하게 page fault가 증가한다. 따라서 이는 allocation 기법 즉 프로세스에 얼마나 메모리를 할당할지에서 해결해야하는 문제이다.
LFU(least frequently used) Algorithm
가장 참조 횟수가 적은 page를 교체한다. page를 참조할 때 마다 횟수를 누적해서 저장한다. 하지만 최근에 적재된 page가 교체될 가능성이 있다.
NUR(not used recently) Algorithm
LRU보다 적은 Overhead로 비슷한 성능을 달성하려는 목적이있다. bit vector를 사용하는데 참조비트와 갱신비트를 가지고 교체페이지를 결정한다.
갱신과 참조가 되지 않을 수록 교체될 확률이 높아진다.
순서
- (r, u) = 0, 0
- (r, u) = 0, 1
- (r, u) = 1, 0
- (r, u) = 1, 1
Clock Algorithm
마치 시침이 움직이듯이 동작하는 알고리즘 이다. page frame을 순차적으로 가리키는 포인터가 교체될 page frame을 결정한다.
결정에는 참조 비트를 사용한다. 하지만 주기적인 초기화는 일어나지 않고 시침이 지나가면서 참조비트가 0이면 교체할 페이지로 선택하고 1이면 0으로 교체하고 넘어간다.
Second Chance Algorithm
clock algorithm과 유사하지만 update bit도 함께 고려한다. 참조비트와 업데이트비트를 순서대로 나타냈을 때 (0,0)은 교체될 페이지가 된다. (0,1)은 (0,0)으로 바꾼뒤 write-back list에 추가해준다. (1,0)은 (0,0)으로 바꿔주고 (1,1)은 (0,1)로 바꿔준다.
기존의 clock algorithm보다 더 많은 경우의 수를 고려해서 기회를 준다.
