가상 메모리 시스템에서 물리 메모리가 가득 찼을 때, 어떤 페이지를 교체할지 결정하는 것은 중요한 문제이다.
기본적인 FIFO와 참조 지역성을 활용한 LRU 알고리즘을 비교 정리했다.
FIFO vs LRU: 교체 기준 비교
참조 스트림 1, 2, 3, 4, 1, 2 (프레임 3개) 상황을 가정하여 동작 방식을 비교했다.
- FIFO (First-In, First-Out): 먼저 들어온 페이지를 먼저 교체한다.
실제 사용 빈도와 상관없이 입장 순서만을 따른다.
구현은 쉬우나, 메모리를 늘려도 성능이 떨어지는 ‘Belady의 모순’이 발생할 수 있다.
- LRU (Least Recently Used): 가장 오랫동안 사용되지 않은 페이지를 교체한다.
최근에 사용된 데이터가 다시 사용될 확률이 높다는 참조 지역성 원리를 활용한다.
과거의 기록을 바탕으로 결정하는 합리적인 방식이다.
자원 관리 분석
실무적인 성능은 LRU가 우수하지만, 각 페이지의 사용 시점을 기록해야 하므로 하드웨어 지원이 필요하고 오버헤드가 발생한다.
반면 FIFO는 큐 하나로 구현할 수 있을 만큼 단순하다.
운영체제는 미래를 완벽히 예측할 수 없기에 과거 데이터를 토대로 최선의 선택을 내린다.
한정된 자원을 효율적으로 관리하기 위한 이러한 고민들이 시스템의 안정성을 지탱하는 것 같다.
