Demand Paging은 원하는 페이지만 backing store에서 가져옵니다. 다양한 프로그램들이 계속 실행됨에 따라 요구되는 페이지도 늘어나고 결국 메모리도 가득차게 될 것입니다. 이 때 다른 프로그램이 새로 실행되거나 실행중인 프로세스가 다른 페이지를 요구한다면 메모리에 있는 페이지 중 하나를 backing store에 보내고(page out) 새로운 페이지를 메모리에 올려야 합니다(page in). 이것을 페이지 교체(Page Replacement)라고 합니다. 또한 page out되는 페이지가 앞선 포스팅에서 언급했던 victim page입니다.
Victim Page
어떤 페이지를 victim page로 할지 선정해야 합니다. 보통 수정되지 않는 페이지를 고르는 것이 효율적입니다. 수정되지 않는 페이지는 page out 될 때 backing store에 쓰기 연산을 할 필요가 없기 때문입니다. backing store는 읽는 시간도 느린데 거기다가 쓰기 연산까지 한다면 비효율적일 것입니다.
따라서 페이지가 수정되었는지를 확인하기 위해 페이지 테이블에 modified bit를 추가합니다. 페이지가 수정되었다면 1, 그렇지 않다면 0으로 설정합니다.
만약 수정되지 않은 페이지가 여러 개 있어서 선정해야 될 상황이라면 먼저 올라온 페이지를 선택하는 FIFO 방식을 사용하기도 합니다. 이 방식 외에도 다양한 방법이 있다고 합니다. 페이지 교체 알고리즘을 알아보면서 어떤 방법이 있는지 알아보겠습니다.
페이지 교체 알고리즘
Optimal Algorithm(OPT)
가장 먼 미래에 참조되는 페이지를 대체하는 방법입니다. 항상 최적의 결과를 갖습니다. 다만, 미래의 참조를 모두 알아야 해서 실제로 사용하기는 어렵습니다. 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 합니다.
First-In First-Out(FIFO)
가장 간단한 알고리즘입니다. 가장 먼저 page in 한 페이지를 먼저 page out 시킵니다.
모든 페이지가 평등하게 프레임에 상주하고 구현하기 쉽다는 장점이 있습니다. 다만 특정 페이지는 항상 필요할 수 있는데, 그런 때에도 교체시킨다는 단점이 있습니다.
프레임이 늘어나도 page fault가 줄어들지 않는 Belady's Anomaly 현상이 발생할 수 있습니다.
LRU(Least Recently Used) Algorithm
가장 오래 전에 참조된 페이지를 지우는 방법입니다. Optimal에 근접한 방법이고 Belady's Anomaly 현상이 발생하지 않습니다. 하지만 구현이 어렵고 접근되는 빈도를 고려하지 않는다는 단점이 있습니다.
연결 리스트로 LRU를 구현하면 O(1)만에 페이지를 찾고 삽입할 수 있습니다. 제일 최근에 참조된 페이지를 가장 앞으로 옮기는 방식으로 연결 리스트를 구현하면 교체가 일어날 때 가장 뒤에 있는 페이지를 바꿔주면 됩니다.
LFU(Least Frequently Used) Algorithm
참조 횟수가 가장 적은 페이지를 지우는 방법입니다. LRU에 비해 장기적인 시간 규모를 보기 때문에 페이지의 인기도를 더 정확히 반영할 수 있습니다.
힙을 사용하면 최소 빈도를 갖는 페이지를 찾거나 삽입, 삭제하는데 O(logn)의 시간이 걸립니다.
Second Chance Algorithm (Clock Algorithm)
LRU와 LFU 알고리즘은 실제로 사용하는 것은 쉽지 않습니다. 운영체제가 자료구조를 변경하고 유지하는 작업을 수행해야 하는데, 이미 메모리에 페이지가 올라가 있을 때는 CPU가 운영체제에 넘어가지 않습니다. page fault가 발생해야 CPU가 운영체제에 넘어가고 디스크에서 메모리로 페이지를 로드할 때 해당 페이지에 대한 정보를 얻고 갱신할 수 있습니다. 따라서 운영체제가 참조한 지 오래되거나 참조 횟수가 적은 페이지를 정확히 알 수 없습니다.
Second Chance Algorithm은 이에 대한 해결법입니다. LRU의 근사 알고리즘으로 최근에 참조되었는지 여부를 reference bit라는 정보를 이용합니다. 이 bit가 0인 것을 찾을 때까지 시계처럼 한 바퀴씩 포인터를 이동하다가 찾으면 페이지를 교체하는 방식입니다. 만약 bit가 1이면 0으로 바꿔주고 한 바퀴 돌아와서도 0이라면 페이지를 교체합니다. 다시 1로 바뀌어있다면 자주 사용되는 페이지라는 의미입니다.
조금 더 개선된 방식으로 최근 해당 페이지가 변경되었는지 나타내는 modified bit를 추가한 Enhanced Second Chance Algorithm이 있습니다. reference bit가 0이면 modifided bit가 0인지 확인합니다.
