topic★★★★★난이도 · 약 30분
페이지 교체 알고리즘
가상 메모리에서 페이지 부재(Page Fault) 발생 시 어느 페이지를 교체할지 결정하는 정책.
#OS#가상메모리#실기계산
왜 배우는가
참조 문자열과 프레임 수가 주어지고 페이지 부재 횟수를 손으로 계산하는 문제가 매회 출제된다. 알고리즘별 차이를 시뮬레이터로 확실히 잡아두면 실수할 일이 없다.
가상 메모리 시스템에서 프로세스가 필요로 하는 페이지가 메인 메모리에 없을 때 페이지 부재(Page Fault) 가 발생한다. 이때 메인 메모리가 가득 차 있다면 어떤 페이지를 내보낼지 선택해야 하는데, 그 선택 정책을 페이지 교체 알고리즘이라 한다.
| 알고리즘 | 정책 | 특징 |
|---|---|---|
| OPT | 앞으로 가장 오래 안 쓸 페이지 | 이상적, 실제 구현 불가 (참조 예측 필요) |
| FIFO | 가장 먼저 들어온 페이지 | 단순, 발생 |
| LRU | 가장 오래 사용 안 된 페이지 | 성능 우수, 구현 오버헤드 |
| LFU | 참조 횟수 가장 적은 페이지 | 최근 급등 페이지 불리 |
| NUR | 참조/수정 비트 기반 근사 LRU | 구현 단순, 성능 LRU 근접 |
| SCR | 참조 비트로 2차 기회 제공 | FIFO 개선 |
가 가장 자주 출제된다. 아래 시뮬레이터에서 참조 문자열과 프레임 수를 바꿔가며 페이지 부재 횟수가 어떻게 달라지는지 직접 확인해 보자. 알고리즘을 FIFO로 바꾸고 프레임을 늘려보면 Belady's Anomaly도 재현할 수 있다.
| 시점 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 참조 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 |
| Frame 1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 |
| Frame 2 | — | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 |
| Frame 3 | — | — | 1 | 1 | 1 | 3 | 3 | 3 | 2 | 2 | 2 | 2 | 2 |
| 결과 | MISS | MISS | MISS | MISS | HIT | MISS | HIT | MISS | MISS | MISS | MISS | HIT | HIT |
페이지 부재 (MISS)
9
적중 (HIT)
4
적중률
30.8%
참조 문자열을 바꿔보거나 프레임 수/알고리즘을 전환하며 결과가 어떻게 달라지는지 관찰해 보자.
계산 팁: 시험장에서는 참조열 아래에 프레임 표를 그리고, 각 열마다 MISS/HIT를 적으며 진행. 한 열에 한 번의 판단이므로 실수 여지가 적다.
개념 딥다이브
LRU 시뮬레이터 자유 실험
참조 문자열을 직접 바꿔보며 페이지 부재 패턴의 규칙을 발견해 보자.
인터랙티브 페이지 열기
실기 드릴 3문항
edit실기 드릴 · 단답형
참조 문자열 7 0 1 2 0 3 0 4 2 3 0 3 2를 3프레임으로 LRU로 처리할 때, 총 페이지 부재 횟수는?
edit실기 드릴 · 단답형
FIFO 페이지 교체에서 프레임 수를 늘렸는데 페이지 부재가 오히려 증가하는 역설적 현상을 무엇이라 하는가?
check_circle실기 드릴 · OX
LRU는 과거의 참조 이력만 사용하므로 구현이 완전히 가능하다.