테마
페이지 교체 알고리즘
페이지 부재(page fault)가 일어났는데 빈 페이지 프레임(page frame)이 없으면, 이미 올라와 있는 페이지 하나를 내보내야 한다. 이때 어느 페이지를 내보낼지 정하는 규칙이 페이지 교체 알고리즘(page replacement algorithm)이다. 실기 시험에서는 참조열과 프레임 수를 주고 페이지 부재 횟수를 세게 하는 문제가 가장 많이 나온다. 요구 페이징(demand paging)과 알고리즘 구현 원리는 CS 카테고리의 페이지 교체 문서에서 다룬다.
알고리즘 한눈에
교체 대상을 고르는 기준이 알고리즘마다 다르다. 이름의 영어 풀이가 곧 기준이므로 풀이째 외운다.
| 이름 | 내보내는 페이지 |
|---|---|
| FIFO(First In First Out, 선입선출) | 가장 먼저 들어온 페이지 |
| LRU(Least Recently Used, 최소 최근 사용) | 가장 오랫동안 사용되지 않은 페이지 |
| LFU(Least Frequently Used, 최소 빈도 사용) | 참조 횟수가 가장 적은 페이지 |
| OPT(OPTimal replacement, 최적 교체) | 앞으로 가장 오랫동안 사용되지 않을 페이지 |
| NUR(Not Used Recently, 최근 미사용) | 참조 비트·변형 비트로 보아 최근에 쓰지 않은 페이지 |
| SCR(Second Chance Replacement, 2차 기회 교체) | FIFO 순서로 보되 참조 비트가 1이면 한 번 살려 준다 |
OPT는 미래의 참조를 알아야 하므로 실제로는 구현할 수 없고, 다른 알고리즘을 평가하는 기준으로 쓴다. 벨레이디(Bélády)가 제안해 부재 횟수가 가장 적다. LRU와 OPT가 헷갈리면 LRU는 과거를, OPT는 미래를 본다고 기억한다.
NUR은 페이지마다 참조 비트(reference bit)와 변형 비트(modified bit)를 두고, 참조 비트를 먼저 보아 (참조 0, 변형 0) → (0, 1) → (1, 0) → (1, 1) 순서로 내보낸다. 최근에 쓰지 않았고 디스크에 다시 쓸 필요도 없는 페이지가 가장 싸게 내보낼 수 있기 때문이다. 영어권 자료는 NRU(Not Recently Used, 최근 미사용)라고 쓴다. SCR은 FIFO가 자주 쓰는 페이지까지 내보내는 약점을 줄이려고, 참조 비트가 1인 페이지는 비트를 0으로 바꾸고 큐 뒤로 보내 두 번째 기회를 준다.
부재 횟수 세는 절차
- 프레임은 처음에 모두 비어 있다고 보고, 처음 채워지는 참조도 부재로 센다.
- 참조한 페이지가 이미 프레임에 있으면 적중이다. 부재가 아니다. LRU는 이때 "최근 사용 시각"을, LFU는 "참조 횟수"를 갱신한다.
- 없으면 부재 1회를 세고, 빈 프레임이 없으면 알고리즘 기준으로 한 페이지를 골라 교체한다.
참조열 1 2 3 1 4 5 2 1, 프레임 3개로 해 보자. 앞의 1·2·3은 빈 프레임에 들어가며 부재 3회, 다음 1은 적중이다. 차이는 4가 들어올 때 생긴다. FIFO는 가장 먼저 들어온 1을 내보내지만, LRU는 방금 1을 다시 썼으므로 가장 오래 안 쓴 2를 내보낸다. 끝까지 세면 FIFO와 LRU는 7회, 참조 횟수가 많은 1을 지키는 LFU는 6회, OPT는 5회다.1
벨레이디의 모순
보통은 프레임을 늘리면 부재가 줄어든다. 그런데 FIFO에서는 프레임을 늘렸는데 부재가 오히려 늘어나는 경우가 있다. 이것을 벨레이디의 모순(Bélády's anomaly), 또는 FIFO 이상 현상이라 한다.
참조열 1 2 3 4 1 2 5 1 2 3 4 5 | 프레임 3 | 프레임 4 |
|---|---|---|
| FIFO | 9회 | 10회 |
| LRU | 10회 | 8회 |
| OPT | 7회 | 6회 |
LRU와 OPT는 프레임이 많을 때 올라와 있는 페이지 집합이 프레임이 적을 때의 집합을 항상 포함하는 성질이 있어 이 모순이 생기지 않는다. FIFO는 들어온 순서만 보므로 그 포함 관계가 깨질 수 있다.
시험 포인트
- "가장 오랫동안 사용되지 않은 페이지 교체" → LRU. "앞으로 가장 오래 사용되지 않을 페이지 교체" → OPT. "사용 빈도가 가장 적은 페이지" → LFU.
- "참조 비트와 변형 비트를 사용" → NUR, (0,0)부터 교체. "참조 비트가 1이면 한 번 더 기회" → SCR.
- "프레임을 늘렸는데 부재가 늘었다" → 벨레이디의 모순, FIFO에서 생긴다.
- 부재 횟수에는 처음 빈 프레임을 채울 때의 부재도 포함한다.
참고
LFU에서 참조 횟수가 같은 페이지가 여럿이면 먼저 들어온 페이지를 내보내는 규칙으로 계산했다. 시험 문제는 보통 동률 규칙을 조건으로 준다. 또 참조 횟수는 페이지가 프레임에 올라온 뒤부터 세고, 내보내지면 다시 0부터 센다. ↩︎