- 가장 오래 사용하지 않은 페이지를 교체하는 알고리즘(현재 채택)
- 참조 횟수가 가장 적은 페이지를 교체하는 알고리즘
- LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간규모에서의 참조성향을 고려할 수 있다.
- 단점
- 초기에 한 페이지를 집중적으로 참조하다가 나중에는 참조하지 않을 경우 문제가 될 수 있다. (앞으로 사용하지 않는 페이지의 참조 횟수가 높아 메모리에 계속 남아있기 때문)
- 가장 최근에 불러온 페이지가 교체될 수 있으며, 구현 더 복잡함, 오버헤드
- 가정: 가장 오랫동안 사용하지 않았던 데이터라면 앞으로도 사용할 확률이 적을 것이다.
- 시간 지역성(temporal locality)을 고려한 알고리즘
- 시간 지역성: 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질
- 사용된 시간을 알수있는 부분을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거(페이지마다 카운터 필요)
- 큐로 구현가능. 사용한 데이터를 큐에서 제거하여 맨 위로다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제
- 단점
- 프로세스가 주기억장치에 접근할때마다 참조된 페이지 시간을 기록해야 하므로 오버헤드 발생
- 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요
- 카운터 : 각 페이지별로 존재하는 논리적인 시계(Logical Clock)로, 해당 페이지가 사용될때마다 0으로 클리어 시킨 후 시간을 증가시켜 시간이 가장 오래된 페이지를 교체
- 가정: 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이다. (참조 횟수가 적은 페이지가 최근에 참조된 것으로 보고 앞으로 사용될 가능성이 높다고 판단)
- 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘
- 메모리에 가장 먼저 올라온 페이지를 먼저 내보냄.
- 구현이 쉽고 빠르다
- 최근에 사용하지 않은 페이지 교체 (LRU를 근사한 알고리즘)
- 적은 오버헤드로 적절한 성능, 동일 그룹 내에서 선택 무작위
- 각 페이지마다 두개의 비트 참조 비트(Reference Bit)와 변형 비트(Modified Bit, Birty Bit)가 사용됨
- 참조 비트: 페이지가 참조되지 않았을 때 0, 호출되었을 때 1 (모든 참조비트를 주기적으로 0으로 변경)
- 변형 비트: 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
- 우선순위: 참조비트 > 변형비트
- 단점
- 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못함
- FIFO 알고리즘에 우선순위를 고려한 알고리즘
- 2차 기회 페이지 교체를 원형 큐를 이용하여 구현한 것
- 교체가 필요한 경우, 큐에서의 삭제 및 삽입 대신 포인터 이동으로 간단히 구현할 수 있다.
- 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
- 가장 이상적이나, 프로세스가 앞으로 사용할 페이지를 미리 알아야 함 -> 불가능
- 프로세스마다 페이지 프레임에 적재된 페이지들의 집합
- 페이지 집합의 크기가 크면? -> 메모리에 적재할 수 있는 프로세스의 수 작다 (시스템처리량감소), 페이지 부재 확률은 낮아짐
- 페이지 집합의 크기가 작으면? -> 메모리에 적재할 수 있는 프로세스의 수 크다 (시스템처리량증대), 페이지 부재 확률은 높아짐 (성능저하)
페이지 교체 시 다양한 페이지 교체 알고리즘을 활용한 victim page의 선정 기준
- 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
- 실제로는 더 효율적이다. 자기 프로세스 페이지에서만 교체를 하면, 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적
- 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
- 다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음 (다양한 프로세스의 페이지가 메모리에 존재함)