페이지 교체 알고리즘
페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.
프레임: 물리 메모리를 일정한 크기로 나눈 블록
페이지: 가상 메모리를 일정한 크기로 나눈 블록
페이지 교체 알고리즘의 종류
FIFO(first in first out)
가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체한다. 이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나, 페이지가 올라온 순서를 큐(Queue)에 저장하는 방식
OPT(Optimal) - 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
최적 알고리즘은 수행하기 전에 선행되어야 할 전제조건이 있다. 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것이다. 이 전제 조건이 실제 활용에서는 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘. 모든 페이지 교체 알고리즘 중 페이지 교체 수가 적다.
LRU - Least Recently Used : 가장 오랫동안 사용되지 않은 페이지 교체
가장 오래 사용되지 않은 페이지를 교체하는 알고리즘이다.
최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법을 사용한 것이 LRU 알고리즘이다.
최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능하다. 예측 방법으로 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식
LFU - Least Frequently Used : 참조 횟수가 가장 작은 페이지 교체
참조 횟수가 가장 작은 페이지를 교체하는 알고리즘이다. 만약 교체 대상인 페이지가 여러 개 일 경우, LRU 알고 리즘을 따라 가장 오래 사용되지 않은 페이지로 교체
MFU - Most Frequently used : 참조 횟수가 가장 많은 페이지 교체
LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다. 참조 횟수가 적은 페이지가 최 근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단
LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.
구현에 비용이 많이 들고, LRU보다 제대로 구현이 안되기 때문이다.
참고자료
https://velog.io/@hkh1213/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Page-Replacement-Algorithm
https://medium.com/pocs/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-page-replacement-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-650d58ae266b
사람이 여행을 하는 것은 도착하기 위해서가 아니라 여행하기 위해서이다. -괴테
