1. 서론
우리가 사용하는 컴퓨터가 물리적 한계를 뛰어넘어 수많은 작업을 동시에 수행할 수 있는 비결은 가상메모리라는 마법에 있다. 하지만 이 마법이 유지되기 위해서는 끊임없이 밀려드는 데이터 중 무엇을 남기고 무엇을 버릴지 결정하는 정교한 판단 기준이 필요하다. 운영체제의 핵심 기능 중 하나인 페이지 대치 알고리즘은 바로 이 지점에서 시스템의 생존을 책임진다. 잘못된 선택 한 번이 시스템 전체의 속도를 급격히 떨어뜨리는 쓰레싱 현상을 유발할 수 있기에, 효율적인 알고리즘의 선택은 소프트웨어 공학의 영원한 숙제이자 시스템 최적화의 정수로 불린다.
2. 본론
고전적 질서와 효율의 대립: FIFO와 LRU
가상메모리 관리의 가장 원초적인 전략인 FIFO 알고리즘은 메모리에 적재된 지 가장 오래된 페이지를 우선적으로 제거한다. 구현이 매우 쉽고 관리 비용이 적다는 강점이 있지만, 때로는 더 많은 자원을 할당받았음에도 오히려 성능이 저하되는 'Belady의 역설'이라는 모순에 직면한다. 이러한 한계를 극복하고자 고안된 LRU 알고리즘은 과거의 사용 이력을 추적하여 가장 오랫동안 참조되지 않은 데이터를 교체 대상으로 삼는다. 이는 최근에 사용된 데이터가 가까운 미래에 다시 사용될 가능성이 높다는 시간 국소성 원리를 영리하게 이용한 사례로 평가받는다.
...이하 생략...