페이지 교체 알고리즘

페이지 교체 알고리즘

 FIFO(First In First Out) 알고리즘 

• 시간상 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘 
• 큐로 구현하기에 구현은 간단 성능은 별로 => 앞으로 사용하지 않을 페이지를 내보내는 것이 중요 

FIFO 알고리즘

 

OPT(Optimal) 알고리즘

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체 => 실제로는 미래의 패턴 알기 힘듬 
• 모든 교체 알고리즘 중 페이지 부재 현상이 가장 적게 발생

OPT 알고리즘

 

LRU(Least Recently Used) 알고리즘 

• 가장 오랫동안 사용하지 않은 페이지를 교체
• 최적 알고리즘과 비슷한 효과
• 성능이 좋음 

LRU 알고리즘

 

LFU(Least Frequently Used) 알고리즘 

• 참조횟수가 가장 적은 페이지를 교체 => 사용한 횟수 카운팅 
• 참조횟수가 같은 경우엔 다른 추가 기준 알고리즘을 사용

LFU 알고리즘

 

NUR(Not Used Recently) 알고리즘 

• LRU처럼 가장 최근에 참조되지 않은 페이지를 선택하지만 교체되는 페이지의 참조 시점이 가장 오래되었음을 보장하지 않음
• 알고리즘의 동작 과정
  1. 페이지가 참조될 때 하드웨어에 의해 참조 비트가 1로 자동 세팅
  2. 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 변경 
  3. 참조 비트가 0인 페이지를 방문하면 해당 페이지 교체 
• 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았기 때문에 교체 대상 페이지로 선정 

NUR 알고리즘

 

 

 

참고

https://zangzangs.tistory.com/143

[OS] 페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR)

https://rob-coding.tistory.com/37

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

https://code-lab1.tistory.com/60

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)

https://zu-techlog.tistory.com/134

[운영체제] 페이지 교체 알고리즘 - FIFO, OPT, LRU, NRU, LFU, MFU