페이지 교체 알고리즘 - FIFO, LRU, LFU, MFU, NUR, OPT(오프라인 알고리즘)

 

스와핑이 일어날 때 페이지 교체 알고리즘에 의해 페이지가 교체되게 된다.

 

FIFO (First In First Out) 

• 방법 : 메모리에 가장 먼저 올라온 페이지를 먼저 내보냄.
• 특징
  • 구현이 간단하고 직관적
  • 성능이 좋지 않을 수 있음. Belady의 역설(FIFO anomaly)이 발생할 수 있음.
    즉, 페이지 프레임 수가 늘어날 수록 페이지 부재가 증가할 수 있음

 

 

LRU (Least Recently Used)

• 방법 : 가장 오랫동안 사용하지 않은 페이지를 교체
• 특징
  • "가장 오랫동안 사용하지 않았다면 앞으로도 사용할 확률이 적을 것이다"라고 가정.
  • 자주 사용되는 페이지를 유지하므로 성능이 FIFO보다 상대적으로 좋음.
  • 프로세스가 주기억 장치에 접근할 때 참조된 페이지 시간을 기록해야 한함.
    -> 막대한 오버헤드가 발생할 수 있다.
    -> 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요하다.

 

 

LFU (Least Frequently Used)

• 방법 : 사용 빈도가 가장 낮은 페이지를 교체
• 특징
  • 자주 사용되지 않는 페이지를 제거하여 효율성을 높임. 장기적 시간 규모에서의 참조성향 고려.
  • 초기화 시점부터의 빈도를 기준으로 하기 때문에, 새로운 페이지가 불리.
  • 오래 전에 사용되었지만 최근에는 사용되지 않는 페이지가 남아 있을 수 있어 성능에 문제가 발생할 수 있음. 
  • 때문에 특정 상황에서만 효율적...

 

 

MFU (Most Frequently Used)

• 방법 : 사용 빈도가 가장 높은 페이지를 교체
• 특징
  • "가장 많이 사용된 페이지는 앞으로는 사용되지 않을 것이다" 라고 가정.
  • 오래된 페이지를 제거할 수 있음.
  • 실제로 자주 사용되는 페이지를 제거할 위험이 있어 성능이 저하될 수 있음.
  • LFU와 마찬가지로, 특정 상황에서만 효율적...

 

NUR / NRU (Not Recently Used) / Clock

먼저 0과 1을 가진 비트를 둠. 1은 최근에 참조되었고 0은 참조되지 않음을 의미. 만약 한 바퀴 도는 동안 사용되지 않으면 0이 됨.

• 방법 : 최근에 사용되지 않은 페이지를 교체. 
• 특징
  • 두 개의 비트(참조 비트/수정 비트)를 사용하여 페이지의 사용 상태를 추적.
  • 구현이 비교적 간단하며, 효과적인 경우가 많습니다.
  • 참조 비트와 수정 비트를 주기적으로 초기화해야 함.
  • LRU보다는 덜 정밀한 편...

 

 

오프라인 알고리즘 (OPT, Optiomal)

 

• 방법 : 현재 메모리에 있는 페이지 중에서 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
• 특징
  • "미래의 페이지 참조를 완벽히 예측할 수 있다"고 가정.
  • 페이지 부재를 최소화하는 가장 효율적인 알고리즘. 메모리 관리의 효율성 극대화.
  • 실제 시스템에서는 미래를 예측할 수 없어 구현할 수 없는 이론적인 알고리즘임.
  • 다른 페이지 교체 알고리즘의 성능을 평가하는 기준으로 사용됨.

 

 

 

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

 

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR