페이지 교체 알고리즘
IT위키
더 많은 작업
페이지 교체 알고리즘(page replacement algorithm)은 가상 메모리에서 페이지 부재(page fault)가 발생했을 때, 어떤 페이지를 메모리에서 제거하고 새 페이지를 적재할지를 결정하는 전략이다. 제한된 물리 메모리 내에서 효율적인 페이지 관리를 통해 전체 시스템 성능을 유지하는 데 핵심적인 역할을 한다.
프로세스가 참조한 페이지가 현재 메모리에 없을 때 페이지 부재가 발생하고, 이때 빈 공간이 없다면 기존 페이지 중 하나를 제거해야 한다. 어떤 페이지를 제거할지를 결정하는 기준이 바로 페이지 교체 알고리즘이다.
- 페이지 폴트(page fault) 수 최소화
- 현실적 구현 가능성
- 지역성(locality) 반영 여부
- 성능, 구현 난이도, 예측성 등의 균형
- FIFO (페이지 교체 알고리즘)
- 가장 먼저 들어온 페이지를 제거
- 구현 단순하지만 성능 불안정 (Belady의 역설 가능)
- LRU (페이지 교체 알고리즘)
- 가장 오랫동안 사용되지 않은 페이지 제거
- 지역성 가정에 적합, 실제 성능 우수
- LFU (페이지 교체 알고리즘)
- 가장 적게 참조된 페이지 제거
- 장기 캐시 오염(Cache Pollution) 발생 가능
- OPT (최적 페이지 교체)
- 앞으로 가장 오랫동안 사용되지 않을 페이지 제거
- 실제 구현 불가능 (이론적인 최적 기준)
- Clock 알고리즘
- LRU의 근사 알고리즘, 하드웨어적으로 구현 용이
- 각 페이지에 사용 비트(use bit)를 두어 원형 큐 방식으로 관리
- Second-Chance (2차 기회) 알고리즘
- FIFO를 기반으로 사용 비트가 1이면 기회를 한 번 더 줌
| 알고리즘 | 교체 기준 | 장점 | 단점 |
|---|---|---|---|
| FIFO | 가장 먼저 들어온 페이지 | 단순함 | 사용 여부 고려 안 함 |
| LRU | 가장 오랫동안 안 쓰인 페이지 | 지역성 반영 | 구현 복잡 |
| LFU | 사용 횟수 가장 적음 | 자주 쓰는 페이지 유지 | 오래된 정보 유지될 수 있음 |
| OPT | 미래 사용 정보 기반 | 페이지 폴트 최소화 | 실현 불가 |
| NUR | 참조 비트·변형 비트 두 비트로 최근 사용 여부 판단 | LRU 보다 구현이 쉬움 | 근사치 |
- 각 페이지에 참조 비트와 변형(수정) 비트 2개를 두고 (0,0) → (0,1) → (1,0) → (1,1) 순으로 교체하는 것이 NUR 이다
- 스택 알고리즘은 교체 알고리즘 하나의 이름이 아니라, 프레임 수를 늘려도 페이지 부재가 늘지 않는 성질을 가진 알고리즘 부류(LRU, OPT)를 가리킨다. FIFO 는 스택 알고리즘이 아니어서 Belady 의 역설이 생긴다
- LRU 는 마지막으로 쓴 시점이 가장 오래된 페이지를 고른다. "가장 오랫동안 사용되지 않은" 페이지다
- LFU 는 쓴 횟수가 가장 적은 페이지를 고른다. 최근에 한 번 썼더라도 횟수가 적으면 교체된다
- NUR(NRU) 는 LRU 를 참조 비트로 흉내 낸 근사 방식이다
- LUF(Least Used First)라는 페이지 교체 알고리즘은 없다. 사용 횟수가 적은 페이지를 고르는 것은 LFU(Least Frequently Used), 가장 오래 쓰지 않은 페이지를 고르는 것은 LRU(Least Recently Used)다
- Optimal 은 OPT(최적 교체)의 다른 이름이다. FIFO·LRU·LFU·OPT·NUR·Second-Chance·Clock 이 교과서에 나오는 교체 알고리즘이다
- MFU(Most Frequently Used)는 반대로 가장 많이 쓴 페이지를 교체하는 실제 알고리즘이다
- 라운드 로빈(Round-Robin)과 SPN(Shortest Process Next)은 CPU 를 어느 프로세스에 줄지 정하는 프로세스 스케줄링 기법이다. 메모리에서 내보낼 페이지를 고르는 교체 알고리즘이 아니다. 스케줄링의 FCFS 를 FIFO 라고도 부르지만, 페이지 교체의 FIFO 와는 고르는 대상(프로세스와 페이지)이 다르다
Random 교체는 교체할 페이지를 무작위로 고른다. 구현 부담이 없지만 참조 지역성을 반영하지 못해 성능을 예측할 수 없다. 하드웨어 캐시처럼 단순해야 하는 곳에서 쓰이기도 한다.
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2020). Operating System Concepts. Wiley
- Tanenbaum, A. S., & Bos, H. (2014). Modern Operating Systems. Pearson