운영체제의 메모리 관리 7 - Page Replacement

6편에서 TLB 동작 흐름을 따라가면서, 페이지 폴트가 발생했을 때 운영체제가 디스크에서 페이지를 읽어 메모리에 적재한다고 했습니다. 그런데 메모리에 빈 프레임이 없다면 어떻게 될까요? 기존에 올라와 있는 페이지 중 하나를 디스크로 내보내 자리를 만들어야 합니다(스와핑). 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘Page Replacement Algorithm입니다.

만약 교체를 위해 디스크로 내보낸 페이지가 곧바로 사용되어야 한다면 또 디스크 I/O를 발생시켜 가져와야하고, 이 빈도가 높아진다면 5편에서 언급했던 쓰래싱Thrashing 현상이 발생합니다. 따라서 좋은 교체 알고리즘은 앞으로 참조될 가능성이 낮은 페이지를 골라낼 필요가 있습니다.

하지만 페이지 참조는 프로세스의 동작에 따라 동적으로 결정될 것이고, 앞으로 어떤 페이지가 필요할지 정확하게 알 수는 없습니다. 따라서 이 문제를 해결하기 위해 다양한 페이지 교체 알고리즘이 등장했습니다.

OPT

가장 이상적인 알고리즘은 최적 알고리즘OPT, Optimal입니다. 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 삼는 방식입니다. 이론적으로 페이지 폴트 횟수를 최소화할 수 있지만, 미래의 참조 순서를 미리 알아야 한다는 전제가 있습니다. 실제 시스템에서는 구현이 불가능하고, 다른 알고리즘의 성능을 비교하는 기준선으로만 활용합니다.

FIFO

FIFOFirst-In-First-Out는 메모리에 가장 오래 머문 페이지를 내보내는 방식입니다. 구현이 단순하고 직관적이지만, 오래 있었다고 해서 앞으로 쓰일 가능성이 낮은 것은 아닙니다. 자주 참조되는 페이지라도 메모리에 먼저 올라왔다는 이유로 쫓겨날 수 있습니다.

더 나아가 Belady의 이상 현상이 발생하기도 합니다. 프레임 수를 늘리면 페이지 폴트가 줄어야 할 것 같지만, FIFO에서는 오히려 늘어나는 경우가 있습니다. FIFO가 지역성 원칙을 전혀 고려하지 않기 때문에 발생하는 현상입니다.

LRU

LRULeast Recently Used는 가장 오랫동안 참조되지 않은 페이지를 교체하는 알고리즘입니다. FIFO가 메모리에 언제 올라왔는지를 기준으로 한다면, LRU는 마지막으로 참조된 시점을 기준으로 합니다.

LRU가 잘 동작하는 근거는 5편에서 다룬 지역성 원칙입니다. 프로세스의 메모리 참조는 군집을 이루는 경향이 있기 때문에, 최근에 참조된 페이지는 가까운 미래에도 다시 참조될 가능성이 높습니다. 반대로 오랫동안 참조되지 않은 페이지는 앞으로도 쓰일 가능성이 낮습니다. LRU는 이 원칙을 교체 판단에 사용한 것입니다.

LRU의 구현

LRU를 정확하게 구현하려면 모든 페이지 참조를 추적해야 합니다. 대표적인 방법은 두 가지입니다.

1. 카운터 방식

각 PTE에 타임스탬프 필드를 추가하고, 페이지가 참조될 때마다 현재 시각을 기록합니다. 교체할 때는 타임스탬프가 가장 오래된 페이지를 고릅니다. 정확하지만 매 메모리 참조마다 타임스탬프를 기록하고, 교체 시점에 전체 페이지를 탐색해야 한다는 부담이 있습니다.

2. 스택 방식

참조된 페이지를 스택의 맨 위로 올립니다. 가장 최근에 참조된 페이지는 항상 위에, 가장 오래된 페이지는 항상 아래에 위치합니다. 교체 대상은 스택의 맨 아래 페이지입니다. 카운터 방식처럼 전체 탐색이 필요 없지만, 참조마다 스택을 재구성하는 비용이 발생합니다.

두 방식 모두 구현 비용이 높은데, 그 이유는 OS가 메모리 참조 하나하나를 직접 볼 수 없다는 데 있습니다.

프로세스가 실행되는 동안 명령어 fetch, 변수 읽기, 데이터 쓰기 등 메모리 참조가 초당 수백만 번 일어납니다. 이 참조들은 CPU와 MMU가 직접 처리하며, OS는 페이지 폴트처럼 예외가 발생할 때만 개입합니다. 소프트웨어만으로 LRU를 구현하려면 이 모든 참조를 트랩으로 가로채 타임스탬프를 기록하거나 스택을 갱신해야 하는데, 그 오버헤드가 너무 커서 실용적이지 않습니다.

그래서 실제 시스템에서는 순수 LRU 대신 이를 근사하는 방식이 쓰입니다.

Clock 알고리즘

Clock 알고리즘은 LRU를 현실적으로 근사하는 대표적인 방법입니다. 각 페이지에 참조 비트Reference Bit를 두고, 해당 페이지가 참조될 때마다 하드웨어가 이 비트를 1로 세웁니다.

교체가 필요해지면 운영체제는 시계 방향으로 프레임을 순회합니다. 참조 비트가 1인 페이지는 아직 최근에 사용된 것으로 보고 비트를 0으로 초기화한 뒤 넘어갑니다. 참조 비트가 0인 페이지를 만나면 그 페이지를 내보냅니다. 다음 교체 때는 이전에 멈춘 위치부터 다시 순회합니다. 이 순환 구조가 시계 바늘처럼 돌아간다고 하여 Clock 알고리즘이라는 이름이 붙었습니다.

완전한 LRU처럼 정확한 참조 시점을 추적하지는 않지만, 최근에 한 번이라도 참조된 페이지는 보호된다는 점에서 합리적인 근사가 됩니다. 구현 비용도 낮아 많은 운영체제에서 실제로 채택하는 방식입니다.

이것으로 가상 메모리의 소프트웨어 측면까지 살펴봤습니다. MMU와 TLB가 주소 변환을 담당하고, 운영체제는 페이지 테이블을 유지하며 폴트가 날 때마다 교체 알고리즘으로 어떤 페이지를 내보낼지 결정합니다. 하드웨어와 소프트웨어가 역할을 나눠 가상 메모리 전체가 돌아가는 구조입니다.