페이지 교체 알고리즘

요구 페이징 기법은 프로세스의 현재 실행에 필요한 페이지만 메모리에 두고, 나머지 부분은 보조기억장치에 둔다.

그리고 프로세스는 진행 상태에 따라 해당 시점에 필요한 특정 페이지를 요구한다.

메모리에 요구된 페이지가 존재할 때는 상관 없지만, 존재하지 않을 때는 보조기억장치에서 페이지를 찾아 메모리의 프레임에 로딩한다.

하지만 이 때에도 메모리에 빈 프레임이 없을 수 있다. 이 경우에, 메모리상의 어떤 페이지를 탈락시키고 보조기억장치의 새로운 페이지를 해당 빈 프레임에 올릴지를 결정하는 알고리즘이 페이지 교체 알고리즘이다.

FIFO (First In First Out)

---

메모리에 올라온 지 가장 오래된 페이지를 교체한다.

각 페이지가 올라온 시간을 페이지에 기록하거나, 각 페이지가 올라온 순서를 큐에 저장하는 방식 등을 사용한다.

최적(Optimal) 페이지 교체

---

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다.

이 알고리즘은, 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다.

실제 활용에서는 알 수 없기 때문에, 구현 불가능하다.

실제 구현 목적보다는 다른 알고리즘과의 비교 연구 목적으로 사용된다.

가장 효율적이다.

LRU (Least-Recently-Used)

---

가장 오랜기간(시간)동안 사용되지 않은 페이지를 교체한다.

많은 운영체제가 채택하는 알고리즘이다.

계수 기반(Counting-Based) 페이지 교체

---

페이지 참조시마다 페이지가 현재까지 참조된 횟수를 카운팅하는 방법이다.

LFU (Least-Frequently-Used)

참조 횟수가 가장 적은 페이지를 교체하는 알고리즘이다.

교체 대상인 페이지가 여러개인 경우, LRU 알고리즘을 따라 가장 오래 사용되지 않은 페이지를 교체한다.

초기에 한 페이지를 집중적으로 참조하다가 이후 참조하지 않는 경우 문제가 된다.

앞으로 참조되지 않아도 초기에 참조된 횟수가 높아 메모리에 계속 남아있기 때문이다.

MFU (Most-Frequently-Used)

참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에, 앞으로도 사용될 가능성이 높다는 판단이다.

LFU와 MFU는 실제 사용에 잘 쓰이지 않는다.

• 구현에 상당한 비용이 든다.

• 최적 페이지 교체 정책을 LRU만큼 제대로 유사하게 구현해내지 못한다.

Global, Local 교체

---

Global : 메모리상의 모든 프로세스 페이지에 대해 교체를 하는 방식.

Local : 메모리상의 자신 프로세스의 페이지에서만 교체를 하는 방식.

Global 방식이 Local 방식보다 더 효율적이다.

참조
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