프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 ‘페이지를 올릴 빈 프레임이 없을 경우’ 교체할 희생 프레임을 찾는 알고리즘 => 페이지 교체 알고리즘
FIFO(first in first out)
이해가 쉽고 구현이 간단하지만, 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있다.
- 가장 간단한 알고리즘
- 메모리에 올라온 지 가장 오래된 페이지를 교체
- 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식 등을 사용
최적(Optimal) 페이지 교체
모든 알고리즘 중 가장 페이지 교체 수가 적지만, 실제로 구현이 불가능하기 때문에 다른 알고리즘과 비교 연구 목적으로 주로 사용된다.
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
- 선행되어야 할 전제조건 : 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것
=> 구현이 불가능한 알고리즘
LRU(least-recently-used)
최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다.
미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용하는 것
-> 따라서 많은 운영체제가 채택하는 알고리즘이며, 좋은 알고리즘이라고 평가 받고있다.
- 가장 오래 사용되지 않은 페이지를 교체하는 알고리즘
- 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘
계수-기반(Counting-Based) 페이지 교체
: 페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅하는 방법
LFU(least-frequently-used)
- 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘
- 만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체
- LFU 알고리즘은 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 앞으로 사용하지 않아도 초기에 사용된 참조횟수가 높아 메모리에 계속 남아있기 때문에 성능이 저하될 우려가 있다.
MFU(most-frequently-used)
- LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
- 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단
=> LFU와 MFU는 구현에 상당한 비용이 들고, 최적 페이지 교체 정책을 (LRU 만큼) 제대로 유사하게 구현해내지 못하기 때문에 실제 사용에 잘 쓰이지 않는다.
참고
링크텍스트
