페이지 교체 알고리즘
정의
페이지 부재(page fault) 발생 시 새로운 페이지를 할당해야 하는데, 이 때 현재 할당되어있는 페이지 중 어떤 것을 교체할 지 결정하는 방법
1) FIFO (First-In First-Out)
메모리에 가장 먼저 올라온 페이지를 교체하는 알고리즘
- FIFO 큐를 이용하여 구현한다.
단점: 오래전에 적재되었지만 반복적으로 사용되는 페이지가 교체될 수 있다.
2) OPT (Optimal Page Replacement)
앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘
최적 알고리즘은 수행하기 전에 선행되어야 할 전제조건이 있다.
프로세스가 앞으로 사용할 페이지를 미리 알아야 한다이 전제 조건이 실제로는 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘이다. 때문에 이 알고리즘은 실제 구현 목적보다 다른 알고리즘과 비교 연구 목적을 위해 주로 사용된다.
3) LRU (Least-Recently-Used)
최근에 사용하지 않은 페이지를 가장 먼저 내보내는 알고리즘
-
최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어를 기반으로 함. (실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다)
-
참조시간 또는 List를 이용하여 구현한다.
-참조시간이용 시 : 페이지가 참조될 때마다 그때의 시간을 기록하여 참조시간이 가장 오래된 페이지를 교체한다.
-List이용 시 : 페이지가 참조되면 List의 선두로 옮겨 List의 가장 끝에 있는 페이지를 교체한다.
단점: 높은 오버헤드
4) LFU (Least Frequently Used)
참조된 횟수가 가장 적은 페이지를 교체하는 알고리즘
- 페이지가 참조될 떄마다 참조 횟수를 증가시켜 참조 횟수가 가장 적은 페이지를 교체한다.
단점
- 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높다.
- 초기에 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체 가능성이 낮다.
- 높은 오버헤드
출처
https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/Page%20Replacement%20Algorithm.md
https://3catpapa.tistory.com/111
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
