페이지 교체 알고리즘이란?
운영체제는 주기억장치의 용량을 초과하는 프로그램을 실행할 때, 프로그램의 일부만 주기억장치에 적재하여 사용하는데, 이를 가상 메모리 기법이라고 한다. 페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 때(페이지 부재), 어떤 페이지 프레임을 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.
페이지 교체 알고리즘 종류
-
OPT - Optimal : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
-
FIFO - First In First Out
-
LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
-
LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
-
MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
-
NUR - Not Used Recently : 최근에 사용하지 않은 페이지 교체
📝 OPT(Optimal) - 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
가장 이상적인 페이지 교체 알고리즘은 프로세스가 앞으로 사용할 페이지를 미리 예측할 수 있는 경우를 가정한다.
그러나 이는 실제로 불가능하므로, 주로 비교 연구 목적으로만 사용된다. 이 알고리즘은 미래에 사용될 페이지를 정확히 알 수 있다면 어떤 페이지를 교체할지 결정하는 데 있어 최적의 성능을 제공한다.
실제 운영체제에서는 이와 유사한 성능을 목표로 다양한 페이지 교체 알고리즘이 개발되고 있다.
📝 FIFO(First in First out) - 가장 먼저 들어온 페이지를 교체
FIFO 알고리즘은 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 방식이다. 이 알고리즘은 구현이 간단하고, 초기화 코드와 같은 경우에는 적절한 방법이 될 수 있다.
FIFO 알고리즘을 구현하기 위해서는 각 페이지가 메모리에 올라온 시간을 저장하거나, 페이지가 올라온 순서를 큐에 저장한다.
직관적으로 생각했을 때, 메모리 프레임의 수가 많아질수록 페이지 결함(page fault)의 횟수가 감소할 것으로 예상할 수 있다.
그러나 FIFO 알고리즘의 경우, Belady's Anomaly라고 불리는 현상이 발생할 수 있다. 이 현상은 메모리 프레임의 수가 증가함에도 불구하고 페이지 결함의 횟수가 오히려 증가하는 현상이다.
Belady's Anomaly는 FIFO 알고리즘의 비효율성을 보여주는 대표적인 사례로, 이를 통해 FIFO 알고리즘의 한계를 이해할 수 있다.
📝 LRU(Least Recently Used) - 가장 오랫동안 사용하지 않은 페이지를 교체
LRU 알고리즘은 가장 오랫동안 사용되지 않은 페이지가 앞으로도 사용될 확률이 낮다는 가정에 기반을 둔다. 이 알고리즘은 시간 지역성(temporal locality) 성질을 고려하는데, 이는 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높다는 성질이다.
LRU 알고리즘은 각 페이지가 마지막으로 사용된 시간을 기록하여 가장 오랫동안 참조되지 않은 페이지를 제거한다. 이를 위해 페이지마다 카운터를 두어 사용된 시간을 저장하거나, 큐를 이용해 구현할 수 있다. 큐를 사용하는 경우, 페이지가 참조될 때마다 해당 페이지를 큐에서 제거하여 맨 위로 올리고, 프레임이 부족할 경우 큐의 맨 아래에 있는 페이지를 삭제한다.
하지만 LRU 알고리즘에는 몇 가지 단점이 있다. 프로세스가 주기억장치에 접근할 때마다 참조된 페이지의 시간을 기록해야 하므로 상당한 오버헤드가 발생할 수 있다. 또한, 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요하여 구현이 복잡해질 수 있다.
📝 LFU(Least Frequently Used) - 참조 횟수가 가장 낮은 페이지를 교체
LFU 알고리즘은 페이지의 참조 횟수를 기반으로 교체할 페이지를 결정한다.
LRU 알고리즘이 직전 참조된 시점만을 반영하는 반면, LFU는 페이지가 얼마나 자주 참조되었는지를 고려하여 장기적인 참조 성향을 반영할 수 있다.
그러나 LFU 알고리즘에도 몇 가지 단점이 있다. 예를 들어, 가장 최근에 불러온 페이지가 아직 참조 횟수가 적어 교체될 수 있다.
또한, LFU는 구현이 더 복잡하며, 참조 횟수를 계속해서 기록하고 업데이트해야 하므로 막대한 오버헤드가 발생할 수 있다.
📝 MFU(Most Frequently used) - 참조 횟수가 가장 많은 페이지 교체
MFU 알고리즘은 LFU 알고리즘과 반대로, 가장 자주 참조된 페이지를 교체하는 방법이다.
MFU 알고리즘은 다음과 같은 가정에 기반을 두고 있다.
가정 : 현재 가장 자주 참조된 페이지는 앞으로는 참조될 가능성이 낮다.
📝 NUR(Not Used Recently)
NUR 알고리즘, 혹은 NRU(Not Recently Used) 알고리즘은 페이지 교체를 위한 간단하고 효율적인 방법 중 하나이다.
이 알고리즘은 간단하면서도 최근 사용 여부를 고려하여 페이지 교체를 효율적으로 수행할 수 있는 방법으로, 특히 하드웨어적으로 참조 비트와 수정 비트를 쉽게 관리할 수 있는 시스템에서 유용하다.
NUR 알고리즘은 구현이 간단하고, 참조 비트와 수정 비트만으로 페이지 교체를 효율적으로 관리하여 성능이 비교적 안정적이라는 장점이 있다.
그러나 비트의 주기적 업데이트와 리셋으로 오버헤드가 발생하며, 단순한 비트 조합만으로 결정하기 때문에 더 정교한 알고리즘(LRU, LFU 등)보다 덜 최적화된 결과를 낼 수 있다.
