페이지 교체 알고리즘

• 프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재 발생
• 페이지 부재가 발생 시 스왑 영역에서 페이지를 메모리로 가져옴
• 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑 영역으로 보내야 함 → 스왑 영역으로 보낼 페이지를 결정하는 알고리즘

종류

FIFO (First-In-First-Out)

• 가장 간단한 페이지 교체 알고리즘으로, 가장 먼저 메모리에 들어온 페이지 교체
• 페이지 교체 순서는 페이지가 메모리에 도착한 순서대로 결정
• 교체되는 페이지가 최근에 사용된 페이지일지라도 교체될 수 있다는 단점

LRU (Least Recently Used)

• 가장 오랫동안 사용되지 않은 페이지를 교체
• 페이지가 사용될 때마다 해당 페이지의 사용 시간을 업데이트하고, 교체할 때 가장 오랫동안 사용되지 않은 페이지 선택
• 최적의 성능을 제공하지만 구현이 복잡하고 메모리 사용량이 크다는 단점

LFU (Least Frequently Used)

• 가장 적게 사용된 페이지를 교체
• 페이지가 사용될 때마다 해당 페이지의 사용 횟수를 업데이트하고, 교체할 때 사용 횟수가 가장 적은 페이지 선택
• 일부 상황에서 LRU보다 성능이 좋을 수 있으나, 사용 횟수를 추적하는데 추가적인 오버헤드 발생 가능

Optimal

• 최적 페이지 교체 알고리즘으로, 교체할 페이지 중 미래에 사용되지 않을 페이지 교체
• 이론적으로 최고의 성능을 제공하지만 미래의 페이지 접근을 예측해야 하므로 구현 어려움

Clock

• FIFO의 개선된 버전으로, 참조 비트(Reference Bit)를 사용하여 페이지 평가
• 페이지를 참조할 때마다 참조 비트를 설정하고, 교체할 때 참조 비트가 설정되지 않은 페이지 선택
• 비교적 간단하면서도 효율적인 알고리즘

references
👉 https://cocoon1787.tistory.com/860