정보처리산업기사, 가상기억장치에서는 모든 프로그램이 동시에 메모리에 올라갈 수 없기 때문에, 운영체제는 필요한 페이지만 메모리에 적재하고 불필요한 페이지를 교체한다. 이때 어떤 페이지를 내보낼지를 결정하는 규칙이 바로 페이지 교체 알고리즘(Page Replacement Algorithm) 이다.
이번 학습에서는 실기 시험에 자주 등장하는 OPT, FIFO, LRU, LFU, NUR, SCR(Clock) 알고리즘을 정리하고, 각 방식의 원리와 비교표를 함께 살펴본다.
정보처리산업기사 1개월 단기 과정 스케줄을 확인하고 싶은분들은 아래글을 이용바랍니다.
1. 페이지 교체의 기본 개념
1) 페이지 부재(Page Fault)
프로세스 실행 중 필요한 페이지가 메모리에 없을 때 발생하는 인터럽트.
운영체제는 디스크에서 해당 페이지를 읽어와야 하며,
이때 기존 페이지 중 하나를 교체해야 한다.
2) 페이지 교체 절차
- CPU가 참조하려는 페이지가 메모리에 있는지 확인
- 없으면 페이지 폴트 발생
- 교체 대상 페이지 선택 (교체 알고리즘 적용)
- 새 페이지 적재 및 페이지 테이블 갱신
- CPU 재실행 (재개)
2. 대표 알고리즘 비교
| 알고리즘 | 원리 | 특징 / 장단점 |
|---|---|---|
| OPT (Optimal) | 앞으로 가장 오랫동안 사용되지 않을 페이지 교체 | 이론적으로 최소 페이지 폴트, 현실 구현 불가 |
| FIFO (First In First Out) | 가장 먼저 들어온 페이지 교체 | 단순, 구현 쉬움, Belady’s Anomaly 발생 가능 |
| LRU (Least Recently Used) | 가장 오랫동안 사용되지 않은 페이지 교체 | 실제 환경에 근접, 구현 복잡 |
| LFU (Least Frequently Used) | 참조 횟수가 가장 적은 페이지 교체 | 빈도 기반, 오래된 데이터 유지 문제 발생 가능 |
| NUR (Not Used Recently) | 최근 참조/변경 비트 조합(2비트)으로 판단 | LRU 근사, 하드웨어 지원 필요 |
| SCR (Second Chance / Clock) | FIFO + 참조비트(Reference Bit) 활용 | 구현 효율 높고 실 OS에서 자주 사용 |
3. OPT (Optimal) 알고리즘
개념
- 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식
- 이론적으로 가장 적은 페이지 폴트를 보장하지만, “앞으로”의 참조 순서를 알아야 하므로 실제 구현은 불가능하다.
예시
프레임 수: 3
참조열: 7, 0, 1, 2, 0, 3, 0, 4
| 순서 | 참조 | 프레임 상태 | 교체 | 폴트 |
|---|---|---|---|---|
| 1 | 7 | 7 | ● | |
| 2 | 0 | 7, 0 | ● | |
| 3 | 1 | 7, 0, 1 | ● | |
| 4 | 2 | 0, 1, 2 | 7 → 교체 | ● |
| 5 | 0 | 0, 1, 2 | ||
| 6 | 3 | 1, 2, 3 | 0 → 교체 | ● |
| 7 | 0 | 2, 3, 0 | ● | |
| 8 | 4 | 3, 0, 4 | 2 → 교체 | ● |
페이지 폴트 횟수 = 6회
4. FIFO (First In First Out)
개념
- 가장 먼저 메모리에 들어온 페이지를 가장 먼저 내보냄
- 큐(Queue) 구조로 구현
- 간단하지만 Belady’s Anomaly (프레임 수를 늘려도 폴트가 줄지 않음) 발생 가능
예시
프레임 수: 3
참조열: 7, 0, 1, 2, 0, 3, 0, 4
| 순서 | 참조 | 프레임 상태 | 교체 | 폴트 |
|---|---|---|---|---|
| 1 | 7 | 7 | ● | |
| 2 | 0 | 7, 0 | ● | |
| 3 | 1 | 7, 0, 1 | ● | |
| 4 | 2 | 0, 1, 2 | 7 → 교체 | ● |
| 5 | 0 | 0, 1, 2 | ||
| 6 | 3 | 1, 2, 3 | 0 → 교체 | ● |
| 7 | 0 | 2, 3, 0 | 1 → 교체 | ● |
| 8 | 4 | 3, 0, 4 | 2 → 교체 | ● |
페이지 폴트 횟수 = 7회
5. LRU (Least Recently Used)
개념
- 가장 오랫동안 사용되지 않은 페이지를 교체
- 과거 접근 이력을 기반으로 판단 (Stack 구조나 Counter 이용)
- 실제 시스템에서 널리 사용됨
예시
| 순서 | 참조 | 프레임 상태 | 교체 | 폴트 |
|---|---|---|---|---|
| 1 | 7 | 7 | ● | |
| 2 | 0 | 7, 0 | ● | |
| 3 | 1 | 7, 0, 1 | ● | |
| 4 | 2 | 0, 1, 2 | 7 → 교체 | ● |
| 5 | 0 | 1, 2, 0 | ||
| 6 | 3 | 2, 0, 3 | 1 → 교체 | ● |
| 7 | 0 | 2, 3, 0 | ||
| 8 | 4 | 3, 0, 4 | 2 → 교체 | ● |
페이지 폴트 횟수 = 6회
LRU < FIFO < OPT 순으로 효율이 증가한다.
6. LFU (Least Frequently Used)
개념
- 참조 횟수가 가장 적은 페이지를 교체
- LRU가 “최근성” 기준이라면 LFU는 “사용 빈도” 기준
- 장시간 유지된 오래된 데이터가 남아있을 수 있음
| 장점 | 단점 |
|---|---|
| 참조 빈도 기반, 특정 패턴에 효율적 | 초기 참조 후 사용되지 않아도 유지됨 (Old Frequency Problem) |
변형 기법:
Aging Algorithm
7. NUR (Not Used Recently)
개념
- 최근에 사용되지 않은 페이지를 교체
- 하드웨어의 참조비트(Reference Bit) 와 변경비트(Modified Bit) 를 이용
- 2비트를 조합해 4단계 분류:
| 참조비트 (R) | 변경비트 (M) | 우선순위 | 설명 |
|---|---|---|---|
| 0 | 0 | 1 | 최근 사용·수정 X (가장 먼저 교체) |
| 0 | 1 | 2 | 최근 사용 X, 수정 O |
| 1 | 0 | 3 | 최근 사용 O, 수정 X |
| 1 | 1 | 4 | 최근 사용·수정 O |
- R비트는 접근 시 1로, 일정 주기마다 0으로 초기화한다.
- LRU의 근사 알고리즘으로 하드웨어 친화적이다.
8. SCR (Second Chance / Clock Algorithm)
개념
- FIFO에 참조비트(Reference Bit) 를 추가한 형태
- 시계 바늘처럼 페이지를 원형 큐로 관리
동작 원리
- FIFO 순서로 페이지를 스캔
- 교체 대상 페이지의 R비트가 1이면 0으로 바꾸고 “두 번째 기회” 부여
- R비트가 0인 페이지를 교체
장점
- LRU보다 구현 간단
- 실제 OS에서 매우 자주 사용 (Linux의 Clock 알고리즘)
9. 비교 요약
| 알고리즘 | 기준 | 특징 | 효율성 |
|---|---|---|---|
| OPT | 미래 참조 | 이론적 최적, 실제 구현 불가 | ★★★★★ |
| LRU | 최근성 | 현실적 효율, 구현 복잡 | ★★★★☆ |
| LFU | 빈도 | 특정 패턴 유리, 오래된 데이터 잔존 | ★★★☆☆ |
| FIFO | 도착 순서 | 단순, Belady 현상 발생 | ★★☆☆☆ |
| NUR | 참조/변경 비트 | LRU 근사, 하드웨어 지원 필요 | ★★★★☆ |
| SCR (Clock) | 참조 비트 순환 | 실 OS 사용, 효율적 구현 | ★★★★☆ |
10. Belady’s Anomaly (벨라디의 이상현상)
- FIFO 알고리즘에서 프레임 수를 늘려도 페이지 폴트가 줄지 않는 현상
- 예: 참조열 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 → 3프레임: 9회 / 4프레임: 10회 (오히려 증가)
결론
페이지 교체 알고리즘은
가상기억장치의 효율과 시스템 성능을 결정하는 핵심 요소다.
- OPT: 이론적 기준
- FIFO: 단순 구현
- LRU / NUR / SCR: 실제 OS 사용
- LFU: 빈도 기반 보조 알고리즘
시험에서는
- 페이지 폴트 횟수 계산
- FIFO vs LRU 비교
- Belady’s Anomaly 설명 이 세 가지가 빈출된다.
다음 학습 – 디스크 스케줄링 알고리즘
다음 학습에서는 디스크 스케줄링(Disk Scheduling) 을 다룬다. CPU 스케줄링과 유사한 원리를 적용하여, 디스크 탐색 거리를 최소화하는 FCFS, SSTF, SCAN, CSCAN 알고리즘을 비교한다.