페이지 교체 알고리즘
가상 메모리(Virtual Memory) 시스템에서 페이지 부재(Page Fault)가 발생했을 때, 어떤 페이지를 대체할 것인지 결정하는 알고리즘이다.
이 알고리즘은 물리적 메모리(Physical Memory)가 한정되어 있을 때, 효율적으로 페이지를 관리할 수 있게 도와준다.
페이지 교체 알고리즘 Type
여러 상황에 따라 다양한 페이지 교체 알고리즘이 적용될 수 있다.
-
FIFO(First In First Out)
가장 먼저 들어온 페이지를 우선적으로 교체한다.
큐(Queue) 자료구조를 사용하여 가장 먼저 들어온 페이지를 큐의 가장 앞쪽에 두고, 새로운 페이지가 들어오면 가장 뒤쪽에 넣게 된다. -
LRU(Least Recently Used)
가장 오랫동안 사용하지 않은 페이지를 우선적으로 교체하게 된다.
페이지마다 사용한 시간을 기록하고, 대체할 페이지를 결정할 때 가장 오랫동안 사용하지 않은 페이지를 대체하는 방식이다. -
LFU(Least Frequently Used)
가장 적게 사용된 페이지를 우선적으로 교체하는 방식이다.
페이지마다 사용 횟수를 기록하고, 대체할 페이지를 결정할 때 사용 횟수가 가장 적은 페이지를 대체한다. -
Optimal
앞으로 가장 오랫동안 사용하지 않을 페이지를 우선적으로 교체한다.
이 알고리즘은 미래에 어떤 페이지가 사용될지 미리 예측하여 대체할 페이지를 결정하는, 이론적으로는 최적의 페이지 교체 알고리즘이다. 하지만, 실제로는 예측이 어렵기 때문에 사용하기 어렵다고 볼 수 있다.
이 중에서 FIFO와 LRU 알고리즘이 주로 이용된다고 한다.
FIFO 알고리즘 같은 경우에는 구현이 간단하기도 하고, 페이지의 개수가 많을 경우에도 효율적으로 동작하기 때문이다. 하지만, 가장 오래된 페이지가 항상 최근에 사용하지 않은 페이지라는 보장이 없기 때문에 교체 후 오류가 발생할 가능성이 있다.
LRU 알고리즘은 대체할 페이지를 결정하는 데 있어서 더욱 정확한 기준을 제공하기 때문에 오류 발생 가능성이 낮다. 하지만, 페이지의 개수가 많을 경우에는 구현이 복잡해질 수 있다는 단점이 있다.
결론은?
따라서, 페이지 교체 알고리즘을 선택할 때는 시스템의 요구사항에 따라 적절한 알고리즘을 선택해야 한다.(아쉽게도 해당 알고리즘으로 무언갈 구현해본 적은 없지만)
간단한 예로, 페이지의 개수가 적을 때는 FIFO 알고리즘이 효율적일 수 있지만, 페이지의 개수가 많을 경우에는 LRU 알고리즘이 더 효율적이라 생각할 수 있다.
또한, 페이지 교체 알고리즘은 페이지 부재율(Page Fault Rate)과 교체 비용을 고려하여 결정해야 한다. 페이지 부재율이 높을 경우에는 교체 알고리즘의 성능을 더욱 중요하게 생각해서 설정해야 한다.
그렇다보니, 최근에는 페이지 교체 알고리즘을 개선하여 더욱 효율적으로 동작하는 알고리즘이 개발되고 있는 추세라고 한다. LRU 알고리즘을 개선한 Approximate LRU(A-LRU) 알고리즘 같은 경우 LRU 알고리즘의 정확도를 유지하면서 구현이 간단하고 빠른 속도로 동작할 수 있다.
결국, 페이지 교체 알고리즘은 가상 메모리 시스템에서 매우 중요한 역할을 한다고 볼 수 있다. 페이지 교체 알고리즘의 효율성이 곧, 시스템의 성능과 안정성에 곧바로 연결되기 때문에 어떤 상황에서 어떤 알고리즘을 선택하는 것이 좋을지 항상 고민해야 한다고 한다.
