Page Replace Algorithm

Page Replace Algorithm이란?

Virtual memory system에서 페이지 부재(page fault)가 발생했을때 주기억장치(메모리)의 모든 페이지 프레임이 사용중이라면 어느 페이지 프레임을 교체할 지 결정하는 알고리즘

FIFO(First In First Out)

페이지 교체 시, 메모리에 올라온지 가장 오래된 페이지를 내쫓는다.

장 점: 

•  가장 간단한 페이지 교체 알고리즘

 단 점:

• 가장 오래된 페이지가 초기화 모듈이라면 성능이 저하될 수 있음
• Belady의 모순(Belady's anomaly)
  • 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

OPT(Optimal)

앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체한다

 장 점: 

•  모든 알고리즘보다 낮은 페이지 부재율
•  Belady의 모순 발생하지 않음

단 점: 

•  구현이 어려움. (프로세스가 앞으로 메모리를 어떻게 참조할 것인지 미리 알아내기 힘들기 때문)

LRU(Least Recently Used)

페이지 교체 시에 가장 오래 사용되지 않은 페이지를 교체 
최적 페이지 교체 알고리즘에 근사한 알고리즘으로 각 페이지마다 마지막 사용 시간을 유지 (미래시간 대신 과거 시간에 대해 적용한 최적 교체 알고리즘)

구현방식

 

• 카운트 방식 : Counting에서 이 방식을 쓴다.
• 스택 방식 : 그 많은 페이지를 관리하기 위해, doubly-linked-list를 차용한 스택을 쓰기엔 메모리, 연산량이 너무 아깝다

Least-recently-used Approximation

reference bit을 사용

• reference bit: 하드웨어 지원없이 시스템은 LRU에 대한 도움을 제공하기 위해 reference bit의 형태를 지원.

이 방식은 페이지가 변하는 순서는 알 수 없지만 페이지가 교체 되는지 아닌지는 알 수 있는 방식

Counting-Based Page

참조 횟수를 가지고 교체될 페이지를 선정

Least Frequently Used

참조 횟수가 가장 적은 페이지를 교체

Most Frequently Used

참조 횟수가 가장 많은 페이지를 교체

 가장 작은 참조 횟수를 가진 페이지가 가장 최근에 참조됐기 때문에 가장 적게 참조됐고, 앞으로 사용될 것이라는 판단에 근거한 알고리즘이다.

대개 LFU, MFU 알고리즘을 잘 쓰지 않는다.

• 현 시 비용이 많이 들고, 최적(OPT) 페이지 교체 정책에 제대로 근사하지 않기 때문