페이지 교체 알고리즘

페이지 교체

페이지 부재 발생 시 어떤 페이지를 교체할 것인지 여러 개의 알고리즘이 있음

 

FIFO 알고리즘

• First in First out인 알고리즘이며 말그대로 선입선출로 페이지 교체를 한다.
• 페이지 프레임이 증가하면 오히려 더 많은 부재가 발생(벨레이디의 모순)

LRU 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 교체한다.
• 일반 lru는 하드웨어 오버헤드가 매우 큰 문제를 가지고 있어, 참조비트를 사용한 lru 근사를 사용한다.
• 가장 많이 사용되는 알고리즘

OPT 알고리즘

• 가장 오랫동안 사용되지 않을 페이지를 교체한다.
• 실질적으로 구현 불가능.. 미래를 모르니

LFU 알고리즘

• 가장 빈도가 적은 페이지를 교체한다.
• 구현 비용이 비싸며, 구현하기가 어려워 잘 사용하지 않음