페이지 교체 알고리즘
프로세스 실행 중 invalid 상태의 페이지가 필요하여 Page Fault 트랩이 발생하면 해당 페이지를 메모리에 올려야 한다.
이미 메모리에는 프레임이 적재되어 더 이상 올라갈 공간이 없기 때문에, 특정한 알고리즘에 의하여 선정된 프레임을 swap 영역으로 내리고 사용할 페이지를 메모리에 적재해야 한다.
이러한 알고리즘을 페이지 교체 알고리즘이라 한다.
FIFO(First In First Out)
메모리에 가장 먼저 올라온 페이지를 내보내는 알고리즘이다.
구현이 간단하다.
페이지가 자주 참조 되더라도 고려하지 않고 내보내기 때문에 비효율적일 수 있다.
OPT(Optimal)
가장 이상적인 알고리즘으로 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보내는 알고리즘이다.
구현을 위해서는 앞으로 사용할 페이지를 순서대로 알아야 하는데, 이는 불가능하다.
LRU(Least Recently Used)
가장 오랫동안 사용하지 않은 페이지를 내보내는 알고리즘이다.
이는 시간 지역성 특징을 이용한 것인데, 최근 사용된 페이지는 다시 사용될 확률이 크기 때문이다.
따라서 가장 오랫동안 사용하지 않은 페이지를 내보낸다.
확률에 기반한 알고리즘이므로 효율적인 상황이 연출될 수 있다.
LFU(Least Frequently Used)
페이지가 가장 적게 참조된 페이지를 내보내는 기법이다.
새로 올라온 페이지가 바로 내보내질 수 있기 때문에, 막대한 오버헤드가 발생할 수 있다.
내보진다고 해서 참조횟수를 초기화하지 않게 구현할 수도 있고(Perfect-LFU), 그렇다면 장기적인 관점이 될 수 있으나 최근에 영향을 받지 않을 수 있다.
초기화해서 구현한다면(Incache-LFU) 최근 참조에는 영향을 받을 수 있으나, 오버헤드가 발생할 것이다.
