페이지 교체 알고리즘(Page Replacement Algorithm)에 대해 설명하세요
Keyword
page out, FIFO, 최적, LRU, LFU, MFU
Script
페이지 교체 알고리즘은, 필요한 페이지를 물리 메모리에 적재해야할때, 만약 물리 메모리가 가득 차 있는 상태라면, 특정 페이지를 page out 해야하는데, 어떤 페이지를 page out할지 결정하는 알고리즘입니다.
대표적인 페이지 교체 알고리즘으로는 FIFO 페이지 교체, 최적 페이지 교체, LRU 페이지 교체, LFU 페이지 교체, MFU 페이지 교체 등이 있습니다.
Additional
페이지 교체 알고리즘이 필요한 이유
만약 추가적으로 필요한 페이지를 물리 메모리에 적재해야 하는 경우, 물리 메모리가 모두 사용중인 상태일 경우에는 페이지 교체가 이루어져야 한다. 이때, 어떤 페이지를 page out 할지를 결정해야하는데, page fault가 최소가 되도록 페이지 교체를 수행하는 것이 좋다.
페이지 교체 알고리즘은 이 과정을 효율적으로 하기 위해 고안되었고, 페이지 교체 알고리즘을 잘 설계할수록 메모리 효율성과 성능이 높아진다.
FIFO(first-in first-out) 페이지 교체
가장 간단하고 직관적인 페이지 교체 방법이다. 먼저 물리 메모리에 들어온 순으로 페이지 교체가 이루어진다.
이해하기 쉽고 구현도 쉽지만, 단순히 먼저 들어온 페이지가 더 이상 사용되지 않는다는 것을 의미하는 것이 아니기 때문에, 오히려 활발하게 사용되는 페이지를 교체해서 page fault를 높힐 수도 있다.
그리고 FIFO 페이지 교체 알고리즘에서는 Belady의 모순이 발생하는 현상이 있다.
일반적으로 페이지 frame의 수를 늘리면, 메모리에 적재될 수 있는 페이지의 수가 늘어나기 때문에, page fault 발생 확률이 감소한다. 그런데, FIFO 페이지 교체 알고리즘에서는 단순히 오래된 페이지를 교체하기 때문에, 산술적으로 오히려 더 많은 Page fault가 발생하게 된다.
즉, 성능 개선을 위해 frame의 수를 늘렸지만, 반대로 page fault가 더 자주 발생하여 성능이 악화되는 일이 일어난다. 그래서 적절한 페이지 교체 알고리즘과 page frame의 수를 조절하는 것이 중요하다.
최적 페이지 교체(Optimal Page Replacement)
최적 페이지 교체는 가장 이상적인 페이지 교체 알고리즘이다. 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식인데, 가능만 하다면 가장 낮은 page fault rate을 보일 수 있다.
하지만 모든 프로세스의 메모리 참조 계획을 미리 파악하여, 가장 오랫동안 사용되지 않을 페이지를 선정하는 것은 구현의 어려움이 있고, 사실상 불가능하다.
LRU 페이지 교체(LRU Page Replacement)
LRU: Least-Recently-Used
최적 페이지 교체를 근사한 알고리즘으로, LRU 페이지 교체 알고리즘이 있다. 가장 오랫동안 사용되지 않을 페이지를 찾는 것이 아니라, 결과적으로 가장 오랫동안 사용되지 않은 페이지를 찾는 것이다.
아무래도, 참조 지역성(locality of reference)을 고려하여 페이지 교체를 수행할 확률이 높아져, Page fault rate이 낮아질 수 있다.
하지만, 페이지의 사용 여부를 추적하기 위해 추가적인 데이터 구조와 연산을 필요로 한다는 점에서, 알고리즘 구현의 복잡도가 높아지고, 메모리 사용량이 높아질 수 있다.
실제로 가장 많이 사용되는 페이지 교체 알고리즘으로, 간단하면서도 효율적인 알고리즘이다.
LFU 페이지 교체(LFU Page Replacement)
LFU: Least Frequently Used
참조 횟수가 가장 적은 페이지를 교체하는 방법이다. 활발하게 사용되는 페이지는 참조 횟수가 많을 것이라 가정하고 설계된 알고리즘이다.
이 알고리즘은 적게 사용한 페이지를 우선적으로 제거하기 때문에, page fault rate이 높은 페이지를 우선적으로 메모리에 유지할 수 있다는 장점이 있다. 하지만, 어떤 프로세스가 특정 페이지를 집중적으로 사용하다가, 다른 기능을 사용하게 될 경우에는, 이전에 많이 사용했지만 지금은 사용하지 않는 페이지가 계속해서 메모리에 남아있게 될 수 있다. 이는 초기 가정인 '활발하게 사용되는 페이지는 참조 횟수가 많다'에 어긋나게 되고, 의도한 성능 개선이 이루어지지 않을 수 있다.
MFU 페이지 교체(MFU Page Replacement)
MFU: Most Frequently Used
MFU 페이지 교체 알고리즘은 LFU 페이교체 알고리즘과 반대의 가정에서 출발한다. 가장 적게 사용된 페이지일수록, 최근에 메모리에 올라왔을 것이고, 앞으로도 계속 사용될 것이라는 가정이 기반이 된다.
추가적인 페이지 교체 알고리즘
대부분의 운영체제에서는 기본적으로 LRU 페이지 교체 알고리즘을 사용한다. 그런데, 단순히 LRU 뿐 아니라, 이를 변형한 알고리즘을 사용한다.
또, 대부분의 운영체제에서 페이지 교체 알고리즘을 사용자가 선택할 수 있다.
변형된 알고리즘으로는 윈도우에서는 Clock 알고리즘, 리눅스는 Second Chance 알고리즘, 맥에서는 LRU Approximation 알고리즘 등을 사용한다.
Reference
