개념
한정된 공간에 데이터를 캐싱할 때, 새로 캐싱해야 하는 데이터가 생겨 기존의 데이터 중 일부를 해제해야 하는 상황에서, 어떤 데이터를 해제할 것인지 결정하는 알고리즘.
다음과 같은 경우에 사용된다.
- 캐시 메모리에서 해제할 데이터를 고를 때
- OS가 가상 메모리 기법으로 보조 저장장치로 이동시킬 페이지를 고를 때
유명한 알고리즘들
- Optimal (OPT) : 앞으로 가장 오랫동안 사용되지 않을 (것으로 보이는) 페이지를 교체
- FIFO (First In First Out) : 가장 오래 적재되어 있던 페이지를 교체
- LRU (Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지를 교체
- LFU (Least Frequently Used) : 사용된 빈도가 가장 적은 페이지를 교체
- NUR (Not Used Recently) : 최근에 사용되지 않은 페이지 중 하나를 교체
Optimal (OPT)
앞으로 가장 오랫동안 사용되지 않을 (것으로 보이는) 페이지를 교체
안타깝게도 비교 연구 목적으로 존재하는 이상적인 개념일 뿐, 실제로 프로세스가 앞으로 사용되지 않을 페이지를 미리 아는 것은 불가능하다.
FIFO (First In First Out)
가장 오래 적재되어 있던 페이지를 교체
들어온 시간을 저장해두거나, 큐 구조를 사용해 페이지를 관리한다.
LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체
가장 오랫동안 사용되지 않은 페이지가 앞으로도 사용될 확률이 적을 것이라는 가정에 입각한 알고리즘.
큐로 비교적 간단하게 구현이 가능하다. 사용한 페이지를 큐에서 꺼내서 맨 위로 올리고, 프레임이 모자랄 경우 맨 아래에 있는 페이지를 제거하고 맨 위에 새 페이지를 넣으면 된다. (근데 임의 위치에 있는 걸 꺼내려면 링크드 리스트를 써야 하는 거 아닌가? 큐에선 어쨌든 꺼낸 뒤에 뒤에 있는 놈들을 한 칸씩 당기는 작업이 필요할텐데)
비교적 간단하고 효과적인 알고리즘이라 자주 쓰이지만, 단점도 있다. 우선 사용된 순서를 기록하는 자료구조 또는 페이지가 마지막으로 참조된 시간을 기록해야 하므로 막대한 오버헤드가 발생한다.
LFU (Least Frequently Used)
사용된 빈도가 가장 적은 페이지를 교체
LRU와 달리 보다 장기적인 차원에서 참조 성향을 고려할 수 있다. 그러나 구현이 LRU보다 복잡하고, 가장 최근에 로드된 페이지일 수록 참조 횟수가 쌓이기 힘드니 빈번하게 교체되는 일이 생길 수도 있다. 막대한 오버헤드는 여전하다.
NUR (Not Used Recently)
최근에 사용되지 않은 페이지 중 하나를 교체
LRU를 근사한 알고리즘으로, 효율과 오버헤드 모두 적절한 수준이다.
다만 LRU와 달리 교체되는 페이지가 가장 예전에 참조된 페이지임을 보장하지는 않는다.
구현은 복잡하니 생략