페이지 교체 알고리즘

나의 답변

FIFO, 최적 페이지 교체, LRU, LFU, MFU가 있다.

개념

FIFO 페이지 교체

가장 간단한 페이지 교체 알고리즘으로 FIFO(first-in first-out)의 흐름을 가진다. 즉, 먼저 물리 메모리에 들어온 페이지 순서대로 페이지 교체 시점에 먼저 나가게 된다는 것이다.

• 장점
  • 이해하기도 쉽고, 프로그램하기도 쉽다.
• 단점
  • 오래된 페이지가 항상 불필요하지 않은 정보를 포함하지 않을 수 있다(초기 변수 등)
  • 처음부터 활발하게 사용되는 페이지를 교체해서 페이지 부재율을 높이는 부작용을 초래할 수 있다.
  • Belady의 모순: 페이지를 저장할 수 있는 페이지 프레임의 갯수를 늘려도 되려 페이지 부재가 더 많이 발생하는 모순이 존재한다.

최적 페이지 교체(Optimal Page Replacement)

Belady의 모순을 확인한 이후 최적 교체 알고리즘에 대한 탐구가 진행되었고, 모든 알고리즘보다 낮은 페이지 부재율을 보이며 Belady의 모순이 발생하지 않는다. 이 알고리즘의 핵심은 앞으로 가장 오랫동안 사용되지 않을 페이지를 찾아 교체하는 것이다. 주로 비교 연구 목적을 위해 사용한다.

• 장점
  • 알고리즘 중 가장 낮은 페이지 부재율을 보장한다.
• 단점
  • 구현의 어려움이 있다. 모든 프로세스의 메모리 참조의 계획을 미리 파악할 방법이 없기 때문이다.

LRU 페이지 교체(LRU Page Replacement)

LRU: Least-Recently-Used최적 알고리즘의 근사 알고리즘으로, 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.

• 특징
  • 대체적으로 FIFO 알고리즘보다 우수하고, OPT알고리즘보다는 그렇지 못한 모습을 보인다.

LFU 페이지 교체(LFU Page Replacement)

LFU: Least Frequently Used참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많아질 거라는 가정에서 만들어진 알고리즘이다.

• 특징
  • 어떤 프로세스가 특정 페이지를 집중적으로 사용하다, 다른 기능을 사용하게되면 더 이상 사용하지 않아도 계속 메모리에 머물게 되어 초기 가정에 어긋나는 시점이 발생할 수 있다
  • 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

MFU 페이지 교체(MFU Page Replacement)

MFU: Most Frequently Used참조 회수가 가장 작은 페이지가 최근에 메모리에 올라왔고, 앞으로 계속 사용될 것이라는 가정에 기반한다.

• 특징
  • 최적(OPT) 페이지 교체를 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.