페이지 교체 알고리즘

페이지 교체 알고리즘

앞써 설명한 바와 같이 

가상 메모리 시스템에서는 MMU를 통해 가상 주소를 실제 주소로 바꾸어주어 동작하게 한다. 

이로 인해 프로그램의 전체 크기만큼 메모리가 필요하지 않고, 실제 동작하는데 필요한 최소한의 메모리만으로도 프로그램을 동작시키게 해주는 것이다. 이 때 MMU가 관리하는 메모리를 페이지단위로 관리한다고 했다. 

메모리를 효율적으로 사용하기 위해서는 페이지가 계속 사용된다면 메모리에 놔두어야 하고, 그렇지 않으면 메모리에서 내리는 동작을 취해야 한다.

이러한 것을 페이지 교체 알고리즘을 통해서 처리한다. 

페이지 교체 알고리즘에 대해서 알아보면

1) FIFO 페이지 교체(First In First Out Page Replacement)

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

3) LRU 페이지 교체(Least-Recently-Used Page Algorithm)

4) LRU 근사 페이지 교체(Least-Recently-Used approximation page algorithm)

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

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

각각의 알고리즘에 대해서 설명해보겠다.

1) FIFO 페이지 교체(First In First Out Page Replacement)

개념 : 

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

장점 : 

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

단점 :

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

* Belady의 모순(Belady's Abnomaly)

: 프로세스에게 프레임을 더 주었는데 오히려 페이지 부재율이 더 증가하는 현상

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

개념 : 

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

장점 : 

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

* Belady의 모순 발생하지 않음

단점 :

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

3) LRU 페이지 교체(Least-Recently-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)에 추가한다.