페이지 교체 알고리즘

많은 페이지 교체 알고리즘이 존재하는데 일반적으로는 페이지 부재율 (Page-Fault rate)이 가장 낮은걸 선정합니다.
아래와 같이 다양한 페이지 교체 알고리즘이 있습니다.

각 알고리즘의 장점과 단점을 확인하면 다음과 같습니다.

1. FIFO 페이지 교체 (First-in First-out Page Replacement)

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

ㄴ. 장 점

- 가장 간단한 페이지 교체 알고리즘~~.

ㄷ. 단 점

- 가장 오래된 페이지가 초기화 모듈이라면 성능이 저하될 수 있음

- Belady의 모순(Belady's anomaly)
: 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

2. 최적 페이지 교체 (Optimal Page Replacement, OPT)

ㄱ. "앞으로 가장 오랜 동안 사용되지 않을 페이지를 찾아 교체하라."

ㄴ. 장 점

- 모든 알고리즘보다 낮은 페이지 부재율

- Belady의 모순 발생하지 않음

ㄷ. 단 점

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

3. LRU 페이지 교체 (Least-lecently-used Page Algorithm)

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

4. LRU 근사 페이지 교체 (Least-recently-used Approximation Page Algorithm)

ㄱ. 하드웨어가 지원하지 못할 경우 참조 비트(reference bit)를 이용하여 사용된 페이지와 사용되지 않은 페이지를
구분할 수 있음

5. 계수-기반 페이지 교체 (Counting-Based Page Algorithm)

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

(1). LFU 알고리즘(Least Frequently Used Algorithm)

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

(2). MFU 알고리즘(Most Frequently Used Algorithm)

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

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

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

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

6. 페이지 버퍼링 알고리즘 (Page-Buffering Algorithm)

ㄱ.  여러 개의 자유 프레임을 풀(Pool)에 넣어 가지고 있다가 페이지 교체가 필요할 때
        자유 프레임에 새로운 페이지를 읽어 들이고, 희생될 프레임을 찾은 뒤 그 프레임을 디스크에 기록하고
        자유 프레임 풀(Pool)에 추가한다.

FaithPaC27's Blog