1️⃣ 개념
페이징 기법으로 메모리를 관리하는 운영체제에서
페이지 부재가 발생하여 새로운 페이지를 할당하기 위해, 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법
2️⃣ 종류
FIFO (First-in-First-out)
메모리에 가장 먼저 올라온 페이지를 먼저 내보낸다
- 큐로 구현하며, 메모리 맨 위에는 가장 오래된 페이지가, 맨 아래에는 새로운 페이지가 위치하게 됨
- 메모리가 꽉 차면, 맨 위의 페이지가 나가고 나머지 페이지들은 위쪽으로 이동함
- 메모리에 올라온 시간만 고려하기 때문에, 자주 사용되는 페이지가 나가면 성능이 떨어짐 -> SCR 알고리즘으로 해결
SCR (Second-Chance-Replacement)
FIFO와 마찬가지로 큐를 사용하지만, 특정 페이지에 대한 접근이 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동시킴
즉, 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 줌
- 성능: LRU,LFU,NUR > SCR(2차 기회 알고리즘) > FIFO
- 큐를 유지하는 비용이 많이 들고, 페이지가 성공하면 큐의 중간에 있는 값을 뒤로 이동시키는 작업이 추가된다는 단점이 있음
NUR (Not Used Recently)
= NRU (Not Recently Used)
최근에 사용하지 않은 페이지를 교체함
각 페이지마다 참조 비트와 변형 비트가 사용됨
- 참조 비트는 페이지가 참조되지 않았을 때는 0, 참조되었을 때는 1로 지정하며,
변경 비트는 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정함 - (0, 0)인 페이지가 가장 먼저 교체되며, 없다면 (0,1) -> (1, 0) -> (1, 1) 순서로 교체 대상을 선정함
- 원형 큐로 구현되기 때문에, 대상 페이지를 가리키는 포인터가 큐의 맨 바닥으로 내려가면 다음에는 다시 큐의 처음을 가리킴
LRU (Least-Recently-Used)
가장 오랫동안 사용되지 않은 페이지를 교체함
OPT (Optimal)
앞으로 가장 오랫동안 사용되지 않을 페이지를 교체함
- 프로세스가 앞으로 사용할 페이지를 미리 알아야한다는 조건이 전제되기 때문에, 구현이 불가능한 알고리즘임
- 실제로 사용되진 않고, 연구 목적을 위해 사용됨
MFU (Most-Frequently-Used)
참조 횟수가 가장 많은 페이지를 교체함
가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라고 가정함
LFU (Least-Frequently-Used)
MFU와 반대로, 참조 횟수가 가장 낮은 페이지를 교체함
- 만약 교체 대상인 페이지가 여러 개일 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지를 교체함
- 초기에 한 페이지를 집중적으로 참조하고, 이후에는 해당 페이지를 참조하지 않는 경우 성능이 떨어짐
MFU와 LFU는 구현에 많은 비용이 들지만 최적 페이지 교체 정책을 LRU 만큼 좋은 성능으로 구현해내지 못하기 때문에, 실제로 잘 쓰이지 않음
RANDOM (무작위 페이지 교체 알고리즘)
특별한 로직없이 무작위로 쫒아낼 페이지를 선정함
- 가장 간단하게 구현 가능하지만, 자주 사용되는 페이지가 대상 페이지로 선정되기도 함
- 성능이 안 좋아서 잘 사용되지 않음
참고자료
https://velog.io/@chappi/OS는-할껀데-핵심만-합니다.-17편-페이지-교체-알고리즘FIFO-LRU-LFU-NUR-2차-기회-알고리즘-시계-알고리즘#82-시계-알고리즘clock-algorithm
https://sommda.tistory.com/67
https://devuna.tistory.com/128
🐥👩💻💰