지난 포스팅에 이어, 이번 포스팅에서는 페이지 교체(Page Replacement)에 대해 알아보겠습니다.
1. 페이지 교체
비어있는 페이지가 없는 경우에 어떤 페이지를 쫓아낸 후, 해당 메모리에 페이지를 올려야 합니다. 이를 페이지 교체라고 하며, 운영체제가 관리합니다. 어떤 페이지를 빼앗아올지 결정해야 하는데, 이때 사용하는 알고리즘을 Replacement Algorithm이라고 합니다.
지난 포스팅에서 언급했던 Effective Access Time을 보시면 page fault가 일어났을 때 오버헤드가 큰 것을 볼 수 있었습니다.
그래서 이 알고리즘은 가능하면 Page Fault가 일어나는 것이 아닌, 메모리에서 직접 처리할 수 있도록 하는 것이 목표입니다.
아래는 페이지 교체의 과정을 도식화한 것입니다.
Victim 페이지가 결정되면 해당 페이지를 디스크(backstore)로 쫓아냅니다. 만약 디스크에서 메모리에 올린 다음 내용이 변경(Write)되었다면 메모리에서 쫓아낼 때 변경된 내용을 Backing store에 써주고, 변경한 내용이 없다면 메모리에서 쫓아냅니다.
Victim 페이지가 선정되어 쫓겨나면, 쫓겨난 페이지에 대한 테이블 엔트리는 Invalid로 바꾸어줍니다. 그리고 새로운 페이지를 메모리에 올리고 새롭게 올라온 페이지에 대해서는 Page Table Entry에 Frame 번호를 적고, Bit를 Valid로 변경합니다.
2. 페이지 교체 알고리즘
(1) Optimal Algorithm
알고리즘 중에 가장 좋은 알고리즘으로, Page Fault를 가장 적게 하는 알고리즘입니다. 하지만 실제 시스템에서는 사용될 수 없습니다. 대신 실제 시스템에서 사용하는 다른 알고리즘에 대한 기준을 제공합니다. 예를 들어 어떤 알고리즘이 Optimal algorithm과 비슷한 성능이라면 더 좋은 알고리즘을 만들 수 없는 식의 비교가 가능합니다.
Optimal algorithm에 대해 살펴보겠습니다. Optical Algorithm은 가장 먼 미래에 참조되는 Page를 교체합니다. 미래를 다 안다고 가정하기 때문에 실제 시스템에서 사용이 불가능합니다.
그림에서 7, 0, 1 순으로 페이지가 올라왔습니다. 2번 페이지가 올라와야하는데 가장 먼 미래에 사용되는 페이지는 7번입니다. 그래서 7번 페이지가 쫓겨나고 그 자리에 2번 페이지가 올라옵니다. 이렇게 가장 먼 미래에 참조되는 페이지를 쫓아내어 Page Fault를 적게 합니다.
어떤 알고리즘도 Optimal algorithm보다 적게 Page fault를 낼 수는 없습니다.
(2) FIFO (First In First Out)
실제 시스템에서 사용 가능한 알고리즘입니다. 미래를 모르기 때문에 과거를 참고하여 알고리즘을 구성합니다.
FIFO 알고리즘은 이름 그대로 먼저 들어온 페이지를 쫓아내는 방식입니다. 이 알고리즘은 특이한 성질이 있는데, 메모리의 크기(Frame의 수)를 늘려주면 오히려 성능이 더 안좋아지는 현상이 발생할 수도 있습니다. 이를 FIFO Anomaly(Belady's Anomaly)라고 부릅니다.
Page frame이 3개 일때보다 4개 일 때 Page fault가 더 많이 발생한 것을 볼 수 있습니다.
교재에서의 참고 예시 그래프는 위와 같습니다. frame의 크기와 page fault가 꼭 비례하지는 않는 것을 볼 수 있습니다.
(3) LRU(Least Recently Used)
가장 오래 전에 참조된 페이지를 쫓아내는 알고리즘입니다. 단어 그대로 가장 최근에 덜 사용된 페이지를 쫓아내는 것입니다. 메모리 관리에서 자주 사용되는 방법입니다.
들어온 시점이 아닌 사용된 시점을 기준으로 하기 때문에 가장 먼저 들어왔지만 들어와서 재사용이 되었다면 쫓아내지 않습니다.
(4) LFU(Least Frequently Used)
가장 덜 빈번하게 참조된 페이지를 쫓아내는 방법입니다.
참조 횟수가 제일 적은 페이지를 메모리에서 쫓아내며, 과거에 참조 횟수가 많았던 Page는 미래에도 참조될 가능성이 높아 쫓아내지 않습니다. 참조 횟수가 적은 페이지가 여러 개가 있을 때 성능을 좀 더 향상하고 싶다면 동률인 Page 중에서 마지막 참조 시점이 더 오래된 페이지를 쫓아냅니다.
참조 시점의 최근성을 반영하지 못하고 LRU에 비해 구현이 복잡하다는 단점이 있습니다. 하지만 LRU에 비해 장기적인 시간 규모를 보기 때문에 Page의 인기도를 좀 더 정확히 반영합니다. LRU와 LFU에 대한 비교를 살펴보겠습니다.
LRU와 LFU의 비교
Page frame 은 4개가 있고, 우측 그림은 시간 순으로 페이지가 참조되는 것을 나타낸 것입니다. 그림을 보면 시간 순으로 페이지 1이 4번, 페이지 2가 2번, 페이지 3이 2번, 다시 페이지 2가 1번, 페이지 4가 1번으로 참조되는 것을 볼 수 있습니다.
그리고 현재 시간에 와있고 Reference String을 보니 현재 시간에 페이지 5가 들어가야합니다. 그래서 하나의 페이지를 쫓아내야 하는데 LRU 알고리즘은 페이지 1을 쫓아내고, LFU는 페이지 4를 쫓아냅니다.
LRU 알고리즘은 이전 기록을 생각하지 않기 때문에, 가장 오래전에 참조되기는 했지만 과거에 많은 참조가 있었다는 것을 고려하지 않는 문제가 있습니다.
LFU알고리즘은 페이지 4를 쫓아냈지만, 참조 횟수가 1번이라도 여러 번의 참조가 시작되는 상황이라면 문제가 생길 수 있습니다.
LRU와 LFU 알고리즘의 구현
LRU 알고리즘은 메모리 안에 있는 Page들을 참조 시간에 따라 줄을 세웁니다. 맨 위에 있는 페이지가 가장 오래전에 참조된 페이지이고, 아래로 갈수록 가장 최근에 참조된 페이지입니다.
Linked List로 Page 참조 시간을 관리합니다. 그래서 만약 어떤 페이지가 메모리에 올라오거나 메모리 안에서 다시 참조가 되면 그 페이지는 다시 맨 아래로 가게 됩니다. 쫓아낼 때는 맨 위의 페이지를 쫓아냅니다.
List 형태로 구현하여 시간 복잡도가 O(1)이 됩니다.
LFU 알고리즘은 참조 횟수가 가장 적은 Page가 맨 위에 있고, 밑으로 갈수록 참조 횟수가 많습니다.
쫓아낼 때에는 LRU처럼 맨 위의 Page를 내쫓습니다.
LFU알고리즘은 Heap 자료 구조로 구현됩니다. LRU 알고리즘은 시간 순서가 중요하기 때문에, 한 번만 참조되어도 제일 아래로 내려올 수 있지만, LFU알고리즘은 참조 횟수가 1이 늘어났다고 해서 맨 아래로 내려가는 것이 아닌 한 단계씩 비교하며 내려가야 합니다. 그래서 시간 복잡도는 list로 구현하면 O(N)이지만 Heap으로 구현하면 O(logn) 구현이 가능합니다.
그래서 LFU 알고리즘은 자식이 두 개씩 있는 완전 이진 트리의 형태입니다.
맨 위는 참조 횟수가 가장 적은 페이지를 놓고, 밑으로 갈수록 참조 횟수가 많은 페이지를 놓습니다. 참조 횟수가 1 늘어나면 직계 자식들과 비교해 밑으로 내려갑니다.
쫓아낼 때에는 Root에 있는 Page를 쫓아내고 Heap를 재구성합니다.
다음 포스팅에서는 지금까지 살펴본 Replacement Algorithm이 가상 메모리 시스템외에도 cache memory, buffer caching, Web caching 등 다양한 곳에서도 사용이 되는데 그것에 대해 살펴보겠습니다.
참고자료
[KOCW 이화여대 반효경 교수님 - Virtual Memory1]
https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f
반효경 [운영체제] 22. Virtual Memory 1
설명이 없습니다.
core.ewha.ac.kr
[ Operating System Concepts - Abraham Silberschatz ]
https://www.yes24.com/Product/Goods/89496122
운영체제 - 예스24
운영체제
www.yes24.com
