페이지 교체 알고리즘
기술노트
🔄 페이지 교체 알고리즘 (FIFO, LRU, LFU 등)
페이지 교체 알고리즘은 운영체제(OS)의 가상 메모리 시스템에서 페이지 부재(Page Fault)가 발생했을 때, 즉 CPU가 참조하려는 페이지가 현재 물리 메모리(RAM)에 없을 때, 물리 메모리에서 어떤 페이지를 스와프 영역(하드 디스크)으로 내보내고 새로운 페이지를 가져올지 결정하는 알고리즘입니다.
이 알고리즘의 목표는 페이지 부재 발생 횟수를 최소화하여 시스템의 성능을 향상시키는 것입니다.
📚 주요 페이지 교체 알고리즘
- FIFO (First-In, First-Out) : 가장 먼저 물리 메모리에 들어온 페이지를 먼저 내보내는 방식입니다. 큐(Queue) 자료구조를 사용합니다.
> * 장점: 구현이 가장 간단합니다. > * 단점: 가장 오래된 페이지가 항상 가장 적게 사용되는 것은 아니므로, 비효율적일 수 있습니다. '벨라디의 변이(Belady's Anomaly)' 현상이 발생할 수 있습니다.
- LRU (Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지를 내보내는 방식입니다. 최근에 사용된 페이지는 미래에도 사용될 가능성이 높다는 '지역성(Locality)' 원리에 기반합니다.
> * 장점: FIFO보다 효율적이며, 실제 시스템에서 많이 사용됩니다. > * 단점: 각 페이지의 사용 시점을 기록해야 하므로 구현이 복잡하고 오버헤드가 발생합니다.
- LFU (Least Frequently Used) : 가장 적게 사용된(참조된) 페이지를 내보내는 방식입니다. 사용 횟수를 카운트하여 관리합니다.
> * 장점: LRU보다 더 정확하게 페이지의 사용 빈도를 반영합니다. > * 단점: 사용 횟수를 계속 기록해야 하므로 구현이 복잡하고 오버헤드가 큽니다. 초기에 많이 사용되고 나중에 사용되지 않는 페이지가 계속 남아있을 수 있습니다.
- OPT (Optimal Replacement) : 가장 먼 미래에 사용될 페이지를 내보내는 방식입니다. 가장 이상적인(최적의) 알고리즘이지만, 미래를 예측해야 하므로 실제 구현은 불가능합니다. 다른 알고리즘의 성능을 평가하는 기준으로 사용됩니다.
💡 정보처리기사 핵심 Point
- 페이지 교체 알고리즘은 가상 메모리 시스템의 성능에 직접적인 영향을 미칩니다.
- 정보처리기사 시험에서는 각 알고리즘의 개념, 동작 방식, 장단점, 그리고 특정 페이지 참조열에 대한 페이지 부재 횟수 계산 문제가 자주 출제됩니다.
- 특히 FIFO, LRU, LFU는 반드시 정확히 이해하고 계산할 수 있어야 합니다.
