페이지 교체 알고리즘

1) 최적기법(Optimal 또는 Min)

-앞으로 가장 오랫동안 참조되지 않을 페이지를 선택하여 교체

=>미래를 알수 없음으로 현실적으로 불가능

 

2) FIFO기법

-가장 오래된 페이지 교체

시간 기록 후  선택 / 큐사용(교체대상은 항상 큐 맨앞)

부재율 낮추기 위해 프레임을 더 주었을 경우 오히려 부재율이 올라가는 현상도 (fifo모순, belay's anomaly)

 

3) LRU기법

-least recently used로 참조된지 가장 오래된 페이지 교체

시간 기록/ 스택 사용(가장 밑에 있는 페이지 교체) - 스택 꼭대기에는 최근 사용한것 밑에있을수록 오래된것

미래를 알 수 없지만 최근에 자주 참조된 페이지가 앞으로도 참조될 것이라는 판단에 근거

 

4) Second-chance 기법

-적재된 후 한번이라도 더 참조된 페이지를 바로 교체시키지 않고 한번 더 메모리에 머물 수 있는 기회를 주는 것

참조비트 (0:바로교체, 1:한번이상 참조 된 것으로 0으로 바꾸고 큐 맨뒤로) / 큐사용

 

5) Clock기법

-second-chance에 순환큐(포인터를 움직이는 것)

 

6) 개선된 Second-chance 기법

-clock기법+갱신bit

참조 갱신

  0     0  찾고 교체, 다음으로 이동

  0     1  찾고 그놈 교체, 다음으로 이동

그외는 참조비트 0으로 만들면서 반복

3패턴을 반복하면 됨

 

7) NUR 기법

-not used recently 참조비트를 주기적으로 0으로 만들면서 (0,0) (0,1) (1,0) (1,1) 순으로 선택

 

8) LFU 기법

-least frequently used로 가장 참조 적게된 페이지 선택

 

9) MFU 기법

-most frequently used로 가장 참조 많이 된 페이지 선택