[운영체제]LRU, LFU - 가상 메모리 관리3

운영체제 - 한빛아카데미

운영체제에 대해 공부한 내용에 대해 정리해보았습니다.

KOREATECH 김덕수 교수님의 자료와 한밭대학교 임경태 교수님의 강의를 참고하였습니다.

---

LRU(Least Recently Used) Algorighm - Fixed Allocation

 

• 가장 오랫동안 참조되지 않은 page를 교체 → page참조 시 마다 시간을 기록해야 함(overhead)
• Locality에 기반을 둔 교체 기법
• Min Algorithm에 근접한 성능을 보인다
• 실제로 가장 많이 사용

 

위의 그림은 x가 가장 마지막에 참조되었다고 가정했을 때 x를 교체한다는 내용이다.

 

LFU(Least Frequently Used) Algorithm

• 가장 참조 횟수가 적은 Page를 교체한다.
• Tie-breaking 일 때(동점일때)는 LRU를 적용한다.
• Page 참조 시 마다, 참조 횟수를 누적시켜야한다. → Time Locality
• 시간을 매번 기록하는 LRU보다 참조될때마다 변수에 ++;만 해주면 되기 때문에 LFU의 overhead가 더 적다.

 

단점

• 최근 적재된 참조될 가능성이 높은 Page가 교체 될 가능성이 있다.
• 참조 횟수 누적 overhead