페이지 교체 알고리즘

가상 메모리 페이징 기법 사용시 필요한 페이지를 메인 메모리의 페이지와 교체하는 방법

요구 페이징(Demand Paging)

• 프로그램 실행 시작 시에 프로그램 전체를 물리 메모리에 적재하는 대신, 초기에 필요한 페이지만 적재하는 전략

페이지 교체

• 페이지 부재(Page Fault): 프로세스 동작 중, 필요한 페이지가 물리 메모리에 없는 상황
• 페이지 부재가 발생하면 원하는 페이지를 하드디스크에서 가져오게 됨
• 물리 메모리가 모두 사용중이라서 원하는 페이지를 물리 메모리에 적재하지 못한다면, 페이지 교체가 일어나게 됨

페이지 교체 알고리즘

1. FIFO (First-In, First-Out)

• 가장 오래전에 메모리에 적재된 페이지부터 교체(메모리 올라온 시간)
• 장점: 구현이 매우 간단
• 단점: 자주 사용되는 페이지라도 메모리에 오래 머물렀다면 제거되어 비효율적

2. OPT (Optimal Page Replacement)

• 가장 오랫동안 사용되지 않을 페이지를 교체(미래 사용 횟수 예측)
• 장점: 이론상으로는 최적의 성능을 보장
• 단점: 미래의 페이지 사용 패턴을 예측해야 하므로 실제 시스템에서 구현 어려움

3. LRU (Least Recently Used)

• 원리: 사용된지 가장 오래된 페이지를 교체(마지막 사용 시간)
• 장점: 실질적 구현이 가능하면서, 성능이 가장 좋음
• 단점: 각 페이지의 사용 시점을 추적하고 정렬하는 데 오버헤드 발생

4. LFU (Least Frequently Used)

• 원리: 가장 적게 사용된 페이지를 교체합니다(사용 빈도)
• 단점: 사용 빈도를 추적하는 데 비용이 발생, 초기에 자주 사용되다가 이후 사용되지 않는 페이지 있을 수 있음

5. NRU (Not Recently Used)

• 원리: 최근에 사용되지 않은 페이지를 대상으로 교체(참조된 페이지에 표시, 주기적으로 초기화)

쓰레싱(Threshing)

• 시스템의 페이지 부재율이 높아 실제 유용한 작업보다 페이지 교체 작업에 더 많은 시간을 소비하는 상태
• 해결 전략
  • Working Set 알고리즘: 프로세스의 작업을 구성하는 자주 참조되는 페이지들을 묶어 메모리에 동시에 올리는 알고리즘
  • Page Fault Frequency 알고리즘: Page Fault 퍼센트의 상한과 하한을 두고, 상한을 넘으면 페이지에게 지급하는 프레임 개수를 늘리고, 하한을 넘으면 지급 프레임 개수를 줄이는 알고리즘