[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)

페이지 교체 알고리즘 (Page Replacement Algorithm)

이전 포스팅으로 요구 페이징(Demand Paging)에 대해 알아보았다. 필요한 페이지가 메모리에 없을 때 page-falut가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.

 

페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다. 

 

+요구 페이징에 대한 내용은 다음을 참고하자.

[운영체제] 가상메모리(Virtual Memory)와 요구 페이징(Demand Paging), Valid-Invalid Bit, 페이지 부재(Page Faul

FIFO(First In First Out) 알고리즘

FIFO 알고리즘

• FIFO 알고리즘은 이름 그대로 가장 먼저 메모리에 올라온 페이지를 가장 먼저 내보내는 알고리즘이다.
• 구현이 간단하지만 성능은 좋지 않은 편이다.
• 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있다.
• Belady`s Anomaly 현상이 발생할 수 있다.

Belady`s Anomaly

Belady`s Anomaly란 프레임의 개수가 많아져도 page-fault가 줄어들지 않고 늘어나는 현상을 말한다.

직관적으로 생각해보면 프레임의 개수가 많아지면 page-fault가 줄어들어야 할텐데, FIFO 알고리즘을 사용하면 그렇지 않을 수 있다.

OPT(Optimal) 알고리즘

Opt 알고리즘

• OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다.
• 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적다.
• Belady`s Anomaly 현상이 발생하지 않는다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야한다.
• 실제로 구현하기 거의 불가능한 알고리즘이다.
• 실제로 사용하기 보다는 연구 목적을 위해 사용된다.

LRU(Least Recently Used) 알고리즘

LRU 알고리즘

• LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.
• 최적 알고리즘과 비슷한 효과를 낼 수 있다.
• 성능이 좋은 편이다.
• 많은 운영체제가 채택하는 알고리즘이다.

LFU(Least Frequently Used) 알고리즘

LFU 알고리즘

• LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.
• 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.

MFU(Most Frequently User) 알고리즘

MFU 알고리즘

• MFU 알고리즘은 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.

---

참고 

1. 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

2. https://doh-an.tistory.com/28