페이지 교체 알고리즘

주기억장치 메모리 공간의 한계를 프로세스 전체가 메모리 내에 올라오지 않더라고 실행이 가능하도록 하는 가상기억장치 기법을 통해 해결한다고 하였다.

​가상기억장치는 주로 페이지 단위로 관리한다.

가상기억장치는 프로그램 전체를 메모리에 적재하지 않는 대신, 초기에 필요한 것들만 미리 메모리에 할당하는 요구 페이징(Demand Paging)이라는 전략을 주로 사용한다.​

요구 페이징 전략을 통해 몇 개의 페이지가 메모리에 할당되고 프로그램을 실행한다고 가정하자. 프로그램 실행 시 필요한 페이지가 요구 페이징 전략을 통해 할당되지 않았을 수도 있다. 즉, 필요로 하는 페이지가 주기억장치에 없는 페이지 부재(Page Fault)가 발생할 수 있다.

​페이지 부재가 발생하게 되면, 원하는 페이지를 보조기억장치에서 가져와서 적재해야 하는데 주기억장치가 꽉 차서 페이지를 적재할 공간이 부족하다면 주기억장치에 존재하는 페이지와 원하는 페이지를 교체해야 한다.

 

이때 주기억장치에 할당된 페이지를 특정 기준 없이 임의대로 교체한다면 비효율적인 상황이 발생할 수도 있을 것이다.

만약 페이지 A를 교체하였는데 바로 다음에 페이지 A를 다시 필요로 하게 된다면 또다시 페이지를 교체해야 하기 때문에 비용이 발생하게 된다.

즉, 이러한 비효율적인 상황을 개선하여 성능을 높이기 위해 어떤 페이지를 선택하여 교체할 것인지를 결정하는 기법이 바로 페이지 교체 알고리즘이다.

​페이지 교체 알고리즘에는 FIFO, OPT, LRU, LFU, NUR, SCR 등이 존재한다. 하나씩 살펴보도록 하자.

 

FIFO(First In First Out)

- 가장 간단한 페이지 교체 알고리즘으로 먼저 들어온 페이지부터 차례대로 교체하는 기법

ㅁ 장점

• 이해하기 쉽고, 프로그래밍 및 설계가 간단

ㅁ 단점

• 오래된 페이지가 무조건 불필요한 페이지가 아닐 수 있기 때문에 오히려 페이지 부재율을 높임
• Belady의 모순 : 페이지를 저장할 수 있는 페이지 프레임의 개수를 늘려도 오히려 페이지 부재가 더 많이 발생하는 모순이 존재

 

OPT(Optimal Page Replacement)

- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법

- Belady가 제안한 것으로, 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘

ㅁ 장점

• 페이지 부재율이 가장 낮은 기법

ㅁ 단점

• 모든 프로세스의 메모리 참조 계획을 미리 파악할 수 없기 때문에 구현이 어려움

 

LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

- 각 페이지마다 계수기(Counter)나 스택(Stack)을 두어 가장 오랫동안 사용하지 않은 페이지 판단

 

LFU(Least Frequently Used)

- 사용 빈도가 가장 적은 페이지를 교체하는 기법

- 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용됨

 

NUR(Not Used Recently)

- LRU와 비슷한 알고리즘으로, 최근에 사용하지 않은 페이지를 교체하는 기법

- LRU에서 가장 오랫동안이라는 특징을 제거하여 시간적인 오버헤드를 줄임

- 최근의 사용 여부를 확인하기 위해 각 페이지마다 참조 비트와 변형 비트를 사용

 

SCR(Second Change Replacement)

- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로 FIFO 기법의 단점을 보완하는 기법