페이지교체 알고리즘

페이지 히트 & 미스

용어	설명
페이지 히트 (Page Hit)	요청한 페이지가 이미 메모리에 존재하여, 바로 접근 가능한 상태입니다.
페이지 미스 (Page Miss)	요청한 페이지가 메모리에 존재하지 않아, 디스크에서 불러와야 하는 상태입니다. 이 경우 페이지 교체가 필요할 수 있습니다.

 

페이지 교체 알고리즘

 

오프라인 알고리즘 (Optimal / OPT)

• 가장 이상적인 알고리즘(실제 구현 불가)
• 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체
• 이론적 성능 비교 기준으로 사용됨

FIFO (First-In First-Out)

• 가장 먼저 메모리에 들어온 페이지를 먼저 교체
• 구조가 단순하지만, Belady's Anomaly 발생 가능

LRU (Least Recently Used)

• 가장 오래전에 사용된 페이지를 교체
• 과거 접근 기록을 기반으로 함
• 최근 사용된 페이지일수록 중요하다고 가정

NUR (Not Used Recently) / Clock 알고리즘

• 각 페이지에 **사용 비트(U 비트)**를 둠 (1: 최근 사용, 0: 사용되지 않음)
• 시계 방향으로 포인터를 돌며 U 비트가 0인 페이지를 교체
• 교체 시 해당 비트를 1로 설정
• 구현이 LRU보다 효율적이면서 성능은 유사

LFU (Least Frequently Used)

• 참조 횟수가 가장 적은 페이지를 교체
• 오랫동안 적게 사용된 페이지는 더 이상 필요 없다고 가정
• 참조 횟수 누적 관리가 필요하여 구현 복잡도 ↑

요약 비교

알고리즘	기준	장점	단점
OPT	미래 가장 늦게 참조될 페이지	최적의 성능	실제 구현 불가
FIFO	먼저 들어온 순서	구현 쉬움	성능 불안정 (Belady’s anomaly)
LRU	가장 오래 전에 사용된 페이지	성능 좋음	구현 복잡 (시간/공간 비용)
NUR	최근 사용 여부	성능/복잡도 균형	정확도는 LRU보다 낮음
LFU	가장 적게 참조된 페이지	참조 빈도 반영	구현 복잡, 오래된 페이지 유지 가능