페이지 교체 알고리즘

 

 

운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라고 한다.

메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재), 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

 

 

 

 

페이지 교체 알고리즘 종류

1. OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체

 

- 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 전제조건이 필요

- 이 전제 조건이 실제 활용에서는 알 수 있는 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘

- 따라서 이는 실제 구현 목적보다 다른 알고리즘과 비교 연구 목적을 위해 주로 사용

 

 

 

 

2. FIFO - First In First Out : 가장 오래된 페이지를 먼저 교체

- 이해가 쉽고, 구현이 간단하다는 장점이 존재

- 그러나 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있음

 

 

 

 

 

3. LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체

 

- 최적 알고리즘(OPT)은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘

 

 

 

 

 

4. LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체

 

- 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체

 

 

 

 

 

5. MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체

 

- LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘

- LFU와 MFU는 실제 사용에 잘 쓰이지 않음

(구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 LRU 만큼 제대로 유사하게 구현해내지 못하기 때문)

 

 

 

 

 

6. NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체

 

- LRU에서 나타나는 오버헤드를 줄일 수 있음

- 최근 사용 여부를 확인하기 위해 각 페이지마다 두 개의 비트 사용 

  ▷ 참조비트(Reference Bit) : 페이지가 호출되지 않았을 때 0, 호출되었을 때 1

  ▷ 변형비트(Modified Bit) : 페이지 내용이 변경되지 않았을 때 0, 변경 되었을 때 1