페이지 교체 알고리즘
메인메모리의 공간은 한정적이기때문에, 새로운 페이지를 적재하기 위해서는 희생될 페이지를 선정해야한다.
이때 어떤 알고리즘을 사용하는지에 따라 성능이 달라진다. 성능이 좋다는 것은 페이지 부재율이 낮다는 것을 의미한다.
OPT(Optimal)
가장 오랫동안 사용되지 않을 페이지를 교체하는 방식으로 최적 방식
- 가장 낮은 페이지 부재율
- 실제로 구현 불가능
FIFO(First-In-First-Out)
가장 먼저 올려진 페이지를 교체하는 방식.
- 이해하기 쉽고, 구현이 쉬움
- Belady 모순 발생 가능(프레임 수가 많아져도 부재율이 높아지는 상황있음)
- Queue 자료구조로 구현
LRU(Least-Recently-Used)
가장 오랫동안 사용되지 않은 페이지를 교체하는 방식
- 최적에 가까운 방식
- Linked List 자료구조로 구현, O(1)로 빠른 연산 가능
LFU(Least-Frequently-Used)
가장 적게 참조된 페이지를 교체하는 방식.
- 참조횟수 정보 필요
- LRU보다 낮은 성능
- Heap 자료구조로 구현, O(logN)로 빠른 연산 가능
MFU(Most-Frequently-Used)
가장 많이 참조된 페이지를 교체하는 방식.
- 참조횟수 정보가 필요
- LRU보다 낮은 성능
- Heap 자료구조로 구현, O(logN)로 빠른 연산 가능
Clock Algorithm
LRU의 근사 알고리즘으로, Second chance algorithm 또는 NRU(Not recently used)라고도 불림.
부재가 발생했을 때 희생 페이지를 선정한다. 이를 위해 Page table 상에서 포인터를 한 칸씩 옮기면서 reference bit을 검사한다. 값이 1이면 0으로 바꾸고, 0이면 그 페이지를 희생 페이지로 선정한다.
한 바퀴를 돌더라도 희생 페이지를 찾지 못할 수 있다. 그런 경우에는 한 바퀴 더 돌아 희생될 페이지를 찾는다.
2바퀴째에는 무조건 찾을 수 있다는 게 보장이 된다.
-
Paging system에 적용할 수 있는 방식
LRU, LFU, MFU와 같은 방식은 paging system에 적용하기 어렵다. 이들은 이론적으로 운영체제가 자료구조를 관리해야하며 발생하는 페이지 참조들을 운영체제가 항상 알아야한다. 하지만 존재하는 페이지를 참조할 때는 운영체제가 관여하지 않기 때문에 적용하기 어려운 것이다.
-
성능 개선을 위해, modified bit을 사용해 변경되지 않은 페이지를 우선적으로 선정
