페이지 교체 알고리즘 - FIFO/LRU/OPT
📄페이지 교체 알고리즘
페이징 기법을 사용하여 메모리를 관리하는 과정에서 페이지가 메인메모리(주기억장치)에 적재되지 않은 경우 페이지 프레임에서 교체할 페이지를 선택하는 알고리즘을 뜻함
FIFO
- 가장 먼저 들어온 페이지와 교체하는 알고리즘
해당 사진을 설명한다면, 참조열에 있는 페이지들이 순차적으로 페이지 프레임에 적재가 되는 과정을 표로 작성하는 것입니다. 부재여부란, 적재되는 페이지가 페이지 프레임에 존재한다면 H(Hit), 존재하지 않다면 F(Fault)입니다.
표를 채우면 위와 같은 상태가 될 것입니다. 위에서 말씀 드린 것처럼 FIFO 방식은 가장 먼저 들어온 페이지와 교체하는 알고리즘이므로 최근에 참조가 되었음에도 불구하고 페이지 교체가 발생한다는 것을 알 수 있습니다. 추가로 FIFO를 알고 싶으신 분들은 벨러디의 모순 혹은 FIFO 변칙 현상을 검색하시면 새로운 개념을 이해하실 수 있습니다.
LRU
- 가장 오래전에 참조된 페이지와 교체하는 알고리즘
똑같은 참조열을 바탕으로 LRU에 대해서 설명하도록 하겠습니다.
FIFO와 다른 점은 가장 오래전에 들어온 페이지와 교체하는 것이 아닌, 가장 오래전에 참조한 페이지와 교체한다는 것입니다. 이해를 돕기 위해 추가적인 설명을 하면, 3을 참조하려는 상태에서 페이지 프레임에는 [0, 1, 2]가 담겨있고 가장 오래전에 참조된 페이지는 1번 페이지이고, 가장 최근에 참조된 페이지는 0이므로 FIFO와 다르게 3번 페이지와 1번 페이지와 교체됨을 알 수 있습니다.
OPT
- 가장 오랫동안 참조되지 않을 페이지와 교체하는 알고리즘
- 가장 효율적이지만 실행 불가능한 알고리즘
해당 표를 채우면,
이렇게 채워질 수 있습니다. 추가적인 설명을 하면, 가장 오랫동안 참조되지 않을 페이지와 교체한다는 말은 알고리즘을 실행하기에 앞서 참조열을 모두 알고 있어서 가장 나중에 나오는 페이지와 교체하여 부재율을 조금이나마 줄이는 방법입니다. 만약, 페이지 프레임에 있는 페이지를 교체해야 하는 경우에 미래에 사용되지 않을 페이지가 두 개라고 가정하였을 때, FIFO나 LRU 등과 같이 문제에서 우선 순위가 같은 경우 다른 알고리즘을 사용하여 페이지를 교체하도록 지정할 수 있습니다.
