[정처기 실기] 페이지 교체 (LRU)
정보처리기사 실기 — 페이지 교체 (LRU)
0. 한눈에 보기
| 항목 | 내용 |
|---|---|
| 출제 포인트 | 페이지 참조 순서 + 프레임 수 → 페이지 부재(Page Fault) 횟수 계산 |
| 핵심 알고리즘 | LRU (Least Recently Used) — 가장 오래 사용되지 않은 페이지를 교체 |
| 자주 틀리는 점 | 프레임이 아직 비어 있을 때도 부재로 세는지, 히트인데 교체하는지 |
한 줄 요약: 메모리에 없으면 부재(O). 프레임이 꽉 찼으면 가장 오래 전에 쓴 페이지를 보낸다.
1. 문제
다음 페이지 참조 순서를 참고하여, 할당된 프레임 수가 3개일 때 LRU 알고리즘의 페이지 부재 횟수를 구하시오.
페이지 참조 순서
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
| 조건 | 값 |
|---|---|
| 알고리즘 | LRU |
| 프레임 수 | 3 |
| 구하는 것 | 페이지 부재 횟수 |
정답: 12회
2. 핵심 개념
2.1 용어 정리
| 용어 | 영어 | 의미 |
|---|---|---|
| 페이지 | Page | 프로세스를 나눈 고정 크기 블록 |
| 프레임 | Frame | 물리 메모리에 페이지를 올려두는 칸 |
| 페이지 참조 | Page Reference | CPU가 요청한 페이지 번호 |
| 페이지 히트 | Page Hit | 요청한 페이지가 이미 프레임에 있음 |
| 페이지 부재 | Page Fault | 요청한 페이지가 프레임에 없음 (디스크에서 가져와야 함) |
2.2 LRU (Least Recently Used)
- 프레임이 가득 찬 상태에서 새 페이지가 들어오면
- 가장 오래 전에 참조된(사용된) 페이지를 교체한다.
- 최근에 쓴 페이지일수록 오래 남아 있을 가능성이 높다고 보는 방식.
2.3 부재 판정 규칙 (시험용)
| 상황 | 부재 여부 |
|---|---|
| 빈 프레임에 처음 적재 | 부재(O) — 처음 들어오는 것도 부재로 센다 |
| 이미 프레임에 있는 페이지 재참조 | 히트(X) |
| 프레임이 꽉 찼는데 새 페이지 필요 | 부재(O) + LRU 페이지 교체 |
정처기 실기에서는 처음 적재도 페이지 부재로 계산하는 경우가 많다.
3. 풀이 방법 (4단계)
Step 1 — 표 준비
가로: 참조 순서 / 세로: 프레임 3칸 / 마지막 열: 부재 여부
Step 2 — 한 칸씩 진행
- 참조한 페이지가 프레임에 있는지 확인
- 히트 → 프레임 내용 유지, 최근 사용 시각 갱신
- 부재 → 빈 칸 있으면 적재 / 없으면 LRU 페이지 제거 후 그 칸에 새 페이지 적재
표를 쓸 때는 제거된 페이지가 있던 칸에 새 페이지를 넣으면 단계별로 따라가기 쉽다.
Step 3 — LRU 판별
프레임에 있는 페이지마다 마지막으로 참조된 순서를 기억한다.
예) 14번 직전 프레임 {0, 3, 2} 에서
0 → 11번째 참조
3 → 12번째 참조
2 → 13번째 참조
→ 가장 오래된 0을 교체
Step 4 — 부재 횟수 합산
표에서 부재(O) 개수를 센다.
4. LRU 단계별 풀이
O= 페이지 부재 /X= 페이지 히트 /-= 빈 프레임
| # | 참조 | 프레임1 | 프레임2 | 프레임3 | 부재 | 교체(LRU) |
|---|---|---|---|---|---|---|
| 1 | 7 | 7 | - | - | O | |
| 2 | 0 | 7 | 0 | - | O | |
| 3 | 1 | 7 | 0 | 1 | O | |
| 4 | 2 | 2 | 0 | 1 | O | 7 제거 |
| 5 | 0 | 2 | 0 | 1 | X | |
| 6 | 3 | 2 | 0 | 3 | O | 1 제거 |
| 7 | 0 | 2 | 0 | 3 | X | |
| 8 | 4 | 4 | 0 | 3 | O | 2 제거 |
| 9 | 2 | 4 | 0 | 2 | O | 3 제거 |
| 10 | 3 | 4 | 3 | 2 | O | 0 제거 |
| 11 | 0 | 0 | 3 | 2 | O | 4 제거 |
| 12 | 3 | 0 | 3 | 2 | X | |
| 13 | 2 | 0 | 3 | 2 | X | |
| 14 | 1 | 1 | 3 | 2 | O | 0 제거 |
| 15 | 2 | 1 | 3 | 2 | X | |
| 16 | 0 | 1 | 0 | 2 | O | 3 제거 |
| 17 | 1 | 1 | 0 | 2 | X | |
| 18 | 7 | 1 | 0 | 7 | O | 2 제거 |
| 19 | 0 | 1 | 0 | 7 | X | |
| 20 | 1 | 1 | 0 | 7 | X |
페이지 부재 횟수: 1, 2, 3, 4, 6, 8, 9, 10, 11, 14, 16, 18 → 12회
5. 핵심 구간 해설
5.1 4~6번 — 첫 교체 구간
7 → 0 → 1 → 2(부재, 7 제거) → 0(히트) → 3(부재, 1 제거)
- 4번에서 프레임이
{7,0,1}로 가득 참 - LRU는 7 (1번째에 마지막 사용) →
2적재 - 5번
0은 이미 있으므로 히트 - 6번
3은 없음 → LRU 1 (3번째 참조 이후 미사용) 제거
5.2 8~11번 — 연속 부재 구간 (주의)
4(부재) → 2(부재) → 3(부재) → 0(부재)
이 구간은 참조가 겹치지 않아 연속 4회 부재가 발생한다.
| # | 상황 | LRU 제거 | 결과 |
|---|---|---|---|
| 8 | 4 진입 | 2 (4번째 참조 이후 미사용) | 4 | 0 | 3 |
| 9 | 2 재진입 | 3 (6번째 참조 이후 미사용) | 4 | 0 | 2 |
| 10 | 3 재진입 | 0 (7번째 참조 이후 미사용) | 4 | 3 | 2 |
| 11 | 0 재진입 | 4 (8번째 참조 이후 미사용) | 0 | 3 | 2 |
10번을 히트로 착각하기 쉽다. 9번 직후
4 \| 0 \| 2이므로3은 없고 부재다.
5.3 14~18번 — 마무리 구간
1(부재) → 2(히트) → 0(부재) → 1(히트) → 7(부재)
- 14번:
0 \| 3 \| 2상태에서1요청 → LRU 0 (11번째 참조 이후 미사용) 제거 →1 \| 3 \| 2 - 15번:
2히트 →1 \| 3 \| 2유지 - 16번:
0요청 → 프레임에 없음 → LRU 3 (12번째 참조 이후 미사용) 제거 →1 \| 0 \| 2 - 17번:
1히트 →1 \| 0 \| 2유지 - 18번:
7요청 → LRU 2 (15번째 참조 이후 미사용) 제거 →1 \| 0 \| 7
6. 시험에서 자주 틀리는 포인트
| 실수 | 올바른 처리 |
|---|---|
| 빈 프레임 적재를 히트로 봄 | 처음 들어오는 것도 부재(O) |
| 히트인데 페이지 교체 | 이미 있으면 교체 없음, 최근 사용만 갱신 |
| 10번을 히트로 착각 | 9번 직후 4 | 0 | 2 → 3은 부재 |
| LRU를 “먼저 들어온 순”으로 봄 | 그건 FIFO. LRU는 가장 오래 전에 참조된 페이지 |
| 교체 후 칸을 섞어 적음 | 제거된 페이지 자리에 새 페이지를 넣어 일관되게 추적 |
7. 다른 알고리즘과 비교 (참고)
같은 조건(프레임 3, 동일 참조 순서)에서 알고리즘만 바꾸면 부재 횟수가 달라진다.
| 알고리즘 | 교체 기준 | 특징 |
|---|---|---|
| FIFO | 가장 먼저 들어온 페이지 | 구현 단순, Belady 현상 가능 |
| LRU | 가장 오래 사용 안 한 페이지 | 지역성 반영, 이 문제 정답 12 |
| OPT | 앞으로 가장 오래 안 쓸 페이지 | 이론상 최적, 실제 불가 |
시험 문제마다 알고리즘 이름을 정확히 확인한 뒤 풀 것.
8. 빠른 풀이 템플릿
[준비] 참조 순서 적기 / 프레임 N칸 / 부재 카운터 = 0
각 참조마다:
1) 프레임에 있나? → YES: 히트, 최근 사용 갱신
2) 없나? → 부재 +1
- 빈 칸 있음 → 그냥 적재
- 꽉 참 → LRU 페이지 제거 후 적재
마지막에 부재 합계 확인
</think>
StrReplace