페이지 교체 알고리즘
페이지 교체 알고리즘
페이지 교체 알고리즘은 가상 메모리 시스템에서 페이지 폴트(Page Fault)가 발생하고, 물리 메모리(RAM)에 빈 프레임이 없을 때, 어떤 페이지를 디스크로 내보내고(Swap Out) 새로운 페이지를 가져올지(Swap In) 결정하는 전략입니다. 목표는 페이지 폴트 발생률을 최소화하여 시스템 성능을 최적화하는 것입니다.
🔄 페이지 교체 알고리즘의 필요성
- 페이지 폴트 (Page Fault) : CPU가 접근하려는 페이지가 현재 물리 메모리에 없는 경우 발생합니다. 페이지 폴트가 발생하면 디스크 I/O가 발생하며, 이는 매우 느린 작업이므로 시스템 성능에 큰 영향을 미칩니다.
- 프레임 부족 : 물리 메모리의 프레임이 모두 사용 중일 때, 새로운 페이지를 로드하려면 기존 페이지 중 하나를 디스크로 내보내야 합니다. 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘의 역할입니다.
- 목표 : 미래에 가장 오랫동안 사용되지 않을 페이지를 예측하여 교체함으로써, 페이지 폴트 발생률을 최소화하는 것입니다.
⚙️ 주요 페이지 교체 알고리즘
- FIFO (First-In, First-Out)
> * '방식': 물리 메모리에 가장 먼저 들어온 페이지를 가장 먼저 교체합니다. > * '장점': 구현이 간단합니다. > * '단점': Belady의 모순(Belady's Anomaly) 발생 가능. 페이지 프레임 수를 늘려도 페이지 폴트 수가 오히려 증가하는 현상입니다. 또한, 자주 사용되는 페이지가 일찍 들어왔다는 이유로 교체될 수 있어 비효율적입니다.
- LRU (Least Recently Used)
> * '방식': 가장 오랫동안 사용되지 않은(참조되지 않은) 페이지를 교체합니다. '시간 지역성(Temporal Locality)'을 활용합니다. > * '장점': FIFO보다 효율적이며, Belady의 모순이 발생하지 않습니다. > * '단점': 구현이 복잡하고 오버헤드가 큽니다. 각 페이지의 사용 시간을 기록하거나, 연결 리스트로 관리해야 하므로 추가적인 하드웨어 지원이 필요할 수 있습니다.
- LFU (Least Frequently Used)
> * '방식': 참조 횟수가 가장 적은(가장 적게 사용된) 페이지를 교체합니다. > * '장점': 자주 사용되는 페이지는 계속 메모리에 유지됩니다. > * '단점': 구현이 복잡하고 오버헤드가 큽니다. 한 번 많이 사용되고 더 이상 사용되지 않는 페이지가 메모리에 오래 남아있을 수 있습니다.
- OPT (Optimal Page Replacement)
> * '방식': 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. (미래를 예측) > * '장점': 이론적으로 가장 낮은 페이지 폴트율을 보장하는 최적의 알고리즘입니다. > * '단점': 미래를 예측해야 하므로 실제 시스템에서는 구현 불가능합니다. 다른 알고리즘의 성능을 평가하는 기준(benchmark)으로 사용됩니다.
💡 개발자 핵심 Point
- 페이지 교체 알고리즘은 가상 메모리 시스템의 성능에 직접적인 영향을 미칩니다.
- LRU의 근사 알고리즘 : LRU는 이론적으로 효율적이지만 구현 비용이 높아, 실제 운영체제에서는 LRU의 아이디어를 근사하여 구현한 알고리즘들을 사용합니다. (e.g., Clock Algorithm, Second Chance Algorithm)
- 작업 세트 (Working Set) : 프로세스가 일정 시간 동안 집중적으로 참조하는 페이지들의 집합. 운영체제는 각 프로세스의 작업 세트를 물리 메모리에 유지하려고 노력하여 스래싱(Thrashing)을 방지합니다.
- 개발자는 직접 페이지 교체 알고리즘을 구현할 일은 거의 없지만, 어떤 알고리즘이 어떤 상황에 유리하고 불리한지 이해하는 것은 메모리 관련 성능 문제를 진단하고 해결하는 데 도움이 됩니다.
