페이지 교체 알고리즘은 페이지 부재가 났는데 빈 프레임이 없을 때, 프레임에 있는 페이지 가운데 무엇을 내보낼지 정하는 규칙입니다. 내보낸 페이지를 곧 다시 쓰면 부재가 또 나므로, 고르는 규칙에 따라 같은 일을 해도 부재 횟수가 크게 달라집니다.
가상 메모리: 페이징과 세그먼테이션에서는 표에 없는 페이지를 빈 프레임에 올렸습니다. 프레임이 모두 차 있으면 하나를 비워야 합니다. 이 레슨은 프레임 셋에 참조열 1 2 3 2 1 2 4 1 4 5 3 4가 차례로 오는 경우를 셉니다. 참조열은 프로그램이 쓰는 페이지 번호를 차례대로 적은 것입니다. 아래 그림은 같은 참조열을 FIFO·OPT·LRU가 나란히 받아 서로 다른 페이지를 내보내는 모습과, 한 순간에 LFU·NUR이 고르는 페이지를 보입니다.
1페이지 부재와 교체
쓰려는 페이지가 프레임에 있으면 적중(hit)이고, 없으면 페이지 부재(page fault)입니다.
- 빈 프레임에 처음 들어오는 것도 부재로 셉니다. 프레임 셋이 비어 있으면 1·2·3은 모두 부재입니다.
- 적중이면 프레임도 부재 수도 그대로입니다(4~6번째의 2·1·2).
- 빈 프레임이 없는데 부재가 나면 프레임의 페이지 하나를 내보내고, 그 칸에 새 페이지를 넣습니다. 무엇을 내보낼지가 알고리즘마다 다릅니다.
2FIFO·OPT·LRU — 무엇을 보고 내보내나
- FIFO(First In First Out): 프레임에 가장 먼저 들어온 페이지를 내보냅니다.
- OPT(Optimal Replacement): 앞으로 가장 오랫동안 쓰이지 않을 페이지를 내보냅니다. 다시 쓰이지 않는 페이지가 있으면 그것이 먼저입니다.
- LRU(Least Recently Used): 가장 오래전에 쓴 페이지를 내보냅니다.
| 가르는 기준 | FIFO | OPT | LRU |
|---|---|---|---|
| 보는 것 | 들어온 때 | 앞으로 쓸 때 | 마지막으로 쓴 때 |
| 7번째 참조 4에서 내보내는 것 | 1 | 2 | 3 |
| 이 참조열의 부재 | 8번 | 5번 | 6번 |
7번째 참조 4가 올 때 프레임에는 1·2·3이 있습니다. 1은 가장 먼저 들어왔고, 2는 뒤에서 다시 쓰이지 않으며, 3은 3번째 뒤로 쓰지 않았습니다. FIFO는 바로 다음 8번째에 1을 다시 불러옵니다. 들어온 차례만 보고 자주 쓰는 페이지를 내보냈기 때문입니다.
OPT는 부재가 가장 적지만, 앞으로 올 참조를 미리 알아야 해서 실제로는 쓸 수 없습니다. 다른 알고리즘을 견주는 기준이 됩니다. LRU는 최근에 쓴 페이지를 곧 다시 쓰는 쏠림에 기대어 OPT에 다가갑니다.
3LFU와 NUR — 횟수와 비트로 고르기
LFU(Least Frequently Used)는 프레임에 들어온 뒤 참조 횟수가 가장 적은 페이지를 내보냅니다. 횟수가 같을 때의 규칙은 자료마다 달라, 문제에 적힌 규칙을 따릅니다. 이 참조열을 LFU로 세면 부재 7번입니다.
NUR(Not Used Recently)은 페이지마다 둔 두 비트로 고릅니다. 참조 비트는 페이지를 쓰면 1이 되고, 운영체제가 일정 시간마다 0으로 돌립니다. 변형 비트는 페이지 내용을 고치면 1이 됩니다. 최근에 쓰지 않은 페이지(참조 비트 0)를 먼저 내보내고, 그 안에서는 고치지 않은 페이지(변형 비트 0)가 먼저입니다.
| 내보내는 차례 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| 참조 비트·변형 비트 | 0 · 0 | 0 · 1 | 1 · 0 | 1 · 1 |
10번째 참조 5가 올 때 LRU와 LFU의 프레임은 둘 다 1·2·4입니다. 참조 비트는 6번째 뒤에 0으로 돌렸고, 2와 4는 내용을 고쳤다고 둡니다.
| 페이지 | 마지막으로 쓴 때 | 참조 횟수 | 참조 비트·변형 비트 |
|---|---|---|---|
| 1 | 8번째 | 3 | 1 · 0 |
| 2 | 6번째 | 3 | 0 · 1 |
| 4 | 9번째 | 2 | 1 · 1 |
LRU는 가장 오래전에 쓴 2를, LFU는 횟수가 가장 적은 4를 내보냅니다. NUR은 참조 비트가 0인 2를 내보냅니다. 1은 고치지 않았지만 최근에 썼으므로 2보다 뒤입니다.
예제
프레임 셋에 참조열 1 2 3 2 1 2 4 1 4 5 3 4를 FIFO와 LRU로 셉니다. 프레임은 칸 자리 차례로 적고, 새 페이지는 내보낸 페이지의 칸에 들어갑니다.
| 순서 | 참조 | FIFO 프레임 | FIFO | LRU 프레임 | LRU |
|---|---|---|---|---|---|
| 1 | 1 | 1 | 부재 | 1 | 부재 |
| 2 | 2 | 1 2 | 부재 | 1 2 | 부재 |
| 3 | 3 | 1 2 3 | 부재 | 1 2 3 | 부재 |
| 4 | 2 | 1 2 3 | 적중 | 1 2 3 | 적중 |
| 5 | 1 | 1 2 3 | 적중 | 1 2 3 | 적중 |
| 6 | 2 | 1 2 3 | 적중 | 1 2 3 | 적중 |
| 7 | 4 | 4 2 3 | 부재(1 나감) | 1 2 4 | 부재(3 나감) |
| 8 | 1 | 4 1 3 | 부재(2 나감) | 1 2 4 | 적중 |
| 9 | 4 | 4 1 3 | 적중 | 1 2 4 | 적중 |
| 10 | 5 | 4 1 5 | 부재(3 나감) | 1 5 4 | 부재(2 나감) |
| 11 | 3 | 3 1 5 | 부재(4 나감) | 3 5 4 | 부재(1 나감) |
| 12 | 4 | 3 4 5 | 부재(1 나감) | 3 5 4 | 적중 |
FIFO는 부재 8번, LRU는 부재 6번입니다. OPT로 세면 7번째에 2를, 10번째에 1을 내보내 부재 5번입니다.
시험 포인트
- 필기: 빈 프레임에 처음 들어오는 것도 부재로 셉니다. FIFO는 가장 먼저 들어온, OPT는 앞으로 가장 오래 쓰이지 않을, LRU는 가장 오래전에 쓴, LFU는 참조 횟수가 가장 적은 페이지를 내보냅니다. NUR은 참조 비트·변형 비트가 0·0, 0·1, 1·0, 1·1인 차례로 내보냅니다. OPT는 부재가 가장 적지만 앞날을 알아야 해 실제로는 쓰지 못합니다. 참조열과 프레임 수를 주고 부재 횟수를 묻습니다.
- 실기: 계산 — 부재 횟수를 숫자로 씁니다. 이름은 FIFO(First In First Out), OPT(Optimal Replacement), LRU(Least Recently Used), LFU(Least Frequently Used), NUR(Not Used Recently)로 씁니다.
확인 문제
1. 프레임 넷이 차 있고 다음 참조로 새 페이지가 들어옵니다. 페이지마다 들어온 때·마지막으로 쓴 때·참조 횟수가 아래와 같을 때, LRU(Least Recently Used)로 내보내는 페이지를 고르세요.
| 페이지 | 들어온 때 | 마지막으로 쓴 때 | 참조 횟수 |
|---|---|---|---|
| 5 | 1번째 | 10번째 | 3 |
| 6 | 4번째 | 7번째 | 2 |
| 7 | 9번째 | 9번째 | 1 |
| 8 | 8번째 | 11번째 | 2 |
- ① 5
- ② 6
- ③ 7
- ④ 8
정답
②입니다. 마지막으로 쓴 때가 가장 이른 페이지는 7번째에 쓴 6입니다.
- ① 가장 먼저 들어온 페이지를 골랐습니다. FIFO로 내보낼 때의 답입니다. 5는 10번째에 다시 썼습니다.
- ③ 참조 횟수가 가장 적은 페이지를 골랐습니다. LFU로 내보낼 때의 답입니다.
- ④ 가장 최근에 쓴 페이지를 골랐습니다. LRU는 가장 오래전에 쓴 페이지를 내보냅니다.
2. 다음 (가)~(라)의 교체 알고리즘 이름을 약어와 원어로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 프레임에 머문 시간이 가장 긴 페이지를 내보냅니다. 그 페이지를 방금 썼어도 따지지 않습니다.
- (나) 남은 참조열을 끝까지 내다보고, 다음 쓰임이 가장 먼 페이지를 내보냅니다.
- (다) 페이지마다 마지막으로 쓴 시각을 적어 두고, 그 시각이 가장 이른 페이지를 내보냅니다.
- (라) 페이지마다 몇 번 쓰였는지 세어 두고, 그 수가 가장 작은 페이지를 내보냅니다.
정답
받는 답: (가) FIFO(First In First Out) · (나) OPT(Optimal Replacement) · (다) LRU(Least Recently Used) · (라) LFU(Least Frequently Used)
(가)의 실마리는 '들어온 차례만 본다', (나)는 '앞으로 올 참조를 본다', (다)는 '마지막으로 쓴 시각', (라)는 '쓰인 횟수'입니다.
- 틀리는 꼴 LRU — (가)에: 마지막으로 쓴 때를 봅니다. 방금 쓴 페이지라면 LRU는 내보내지 않습니다.
- 틀리는 꼴 LFU — (다)에: 쓰인 횟수를 봅니다. (다)는 횟수가 아니라 시각을 봅니다.
- 틀리는 꼴 LRU — (라)에: 횟수가 아니라 마지막으로 쓴 때를 봅니다. 이름의 Recently(최근)와 Frequently(자주)로 가릅니다.
3. 페이지마다 참조 비트와 변형 비트를 두고, 두 비트만 보고 내보낼 페이지를 고르는 알고리즘이 있습니다. 이 알고리즘의 이름을 약어와 원어로 쓰고, 아래 표에서 가장 먼저 내보내는 페이지를 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
| 페이지 | 참조 비트 | 변형 비트 |
|---|---|---|
| A | 1 | 1 |
| B | 1 | 0 |
| C | 0 | 1 |
| D | 1 | 0 |
정답
받는 답: NUR(Not Used Recently) · C
참조 비트가 0인 페이지는 C뿐이라 C가 먼저입니다. 참조 비트를 먼저 보고, 변형 비트는 그다음에 봅니다.
- 틀리는 꼴 B: 고치지 않은(변형 비트 0) 페이지를 먼저 골랐습니다. B는 최근에 써서(참조 비트 1) 참조 비트가 0인 C보다 뒤입니다.
- 틀리는 꼴 LRU: 마지막으로 쓴 시각을 보는 알고리즘입니다. 두 비트로 고르는 것은 NUR입니다.
4. 같은 참조열 1 2 3 2 1 2 4 1 4 5 3 4를 프레임 셋이 아니라 넷으로 셉니다. FIFO와 LRU의 부재 횟수를 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
정답
받는 답: FIFO 5번 · LRU 6번
프레임이 넷이면 1·2·3·4가 모두 들어가, 7번째까지 부재는 4번입니다. 10번째 5에서 처음으로 하나를 내보냅니다. FIFO는 가장 먼저 들어온 1을 내보내고, 1은 다시 쓰이지 않아 남은 11·12번째가 적중입니다. LRU는 가장 오래전(3번째)에 쓴 3을 내보내는데, 3을 바로 11번째에 다시 써서 부재가 한 번 더 납니다.
- 틀리는 꼴 FIFO 8번 · LRU 6번: 프레임 셋일 때의 답을 옮겼습니다.
- 틀리는 꼴 FIFO 6번 · LRU 5번: LRU가 늘 FIFO보다 부재가 적다고 봤습니다. 어느 쪽이 적은지는 참조열과 프레임 수에 따라 바뀌고, 늘 가장 적은 것은 OPT뿐입니다.
더 보기: 프레임이 모자라 부재가 끝없이 이어지는 상황은 지역성·워킹 셋·스래싱에서 봅니다.