페이지 교체 알고리즘 — FIFO와 LRU

정의

가상 메모리를 쓰는 시스템은 물리 메모리보다 큰 프로그램을 프레임 단위로 나눠 올린다. 필요한 페이지가 메모리에 없으면 페이지 폴트가 발생하고, 빈 프레임이 없으면 어떤 페이지를 내보내고 새 페이지를 넣을지 정해야 한다. 이 결정 규칙이 페이지 교체 알고리즘이다.

핵심 원리

교체 알고리즘의 성능은 같은 참조열(reference string)을 놓고 페이지 폴트 횟수로 비교한다. 프레임 수가 늘면 폴트가 줄어드는 게 상식적이지만, 뒤에서 보듯 FIFO는 이 상식을 깨는 경우가 있다.

FIFO — 먼저 들어온 페이지가 먼저 나간다

큐에 적재 순서를 그대로 유지하다가 교체가 필요하면 큐의 맨 앞, 즉 가장 오래 머문 페이지를 내보낸다. 구현이 단순하지만 그 페이지가 최근에도 자주 쓰이는지는 전혀 고려하지 않는다.

LRU — 가장 오래 안 쓴 페이지가 나간다

최근 사용 시각을 기준으로 가장 오래전에 참조된 페이지를 내보낸다. 프로그램이 최근 접근한 영역을 다시 찾을 가능성이 높다는 지역성(locality of reference)을 이용한 방식이다. 정확한 LRU는 참조마다 시각을 갱신해야 해 비용이 크고, 실제 운영체제는 참조 비트를 순회하는 Clock(Second-Chance) 같은 근사 알고리즘을 쓴다.

예시로 비교

참조열 1 2 3 1 2 4 1 2 5, 프레임 3개로 두 알고리즘을 돌려본다.

FIFO: 1, 2, 3을 순서대로 적재한 뒤 1, 2는 그대로 히트. 4가 들어오며 가장 먼저 올라온 1을 내보내 [2, 3, 4]가 된다. 이후 1, 2가 다시 폴트로 올라오고 5도 폴트. 총 폴트 7회.
LRU: 1, 2, 3 적재 후 1, 2 히트(참조 시각 갱신). 4가 들어오며 가장 오래 안 쓴 3을 내보내 [1, 2, 4]가 된다. 1, 2는 여전히 최근 참조라 히트를 유지하고 5만 폴트. 총 폴트 5회.

같은 입력이라도 LRU는 지역성을 반영해 FIFO보다 폴트를 덜 낸다.

Belady’s Anomaly

FIFO는 프레임을 늘렸는데 오히려 폴트가 늘어나는 역설이 생길 수 있다. 참조열 1 2 3 4 1 2 5 1 2 3 4 5를 FIFO로 돌리면 프레임 3개일 때 폴트 9회, 프레임 4개일 때 폴트 10회가 나온다. 자원을 늘렸는데 성능이 오히려 나빠지는 이 현상을 Belady’s Anomaly라 부른다. LRU를 포함한 스택 알고리즘(stack algorithm) 계열은 프레임 수를 늘리면 폴트가 발생하는 참조 지점의 집합이 항상 이전 집합을 포함하는 관계를 유지해, 이 anomaly가 구조적으로 생기지 않는다는 성질(스택 속성)이 알려져 있다.

시험에 자주 나오는 포인트

FIFO와 LRU 각각의 교체 기준과 구현 방식(큐 vs 참조 시각)을 구분해서 외운다.
Belady’s Anomaly는 FIFO에서 나타나고 LRU에서는 나타나지 않는다는 점 — 스택 알고리즘 여부와 연결해 기억한다.
참조열과 프레임 수가 주어졌을 때 손으로 페이지 폴트 횟수를 세는 계산 문제가 자주 나온다.
LRU의 근사 구현으로 Clock(Second-Chance) 알고리즘이 언급된다는 점도 알아둔다.
OPT(Optimal, 이후 가장 늦게 쓰일 페이지를 내보내는 이론상 최선)와 비교해 FIFO·LRU가 어디에 위치하는지 묻는 문제도 나온다.