메모리 페이지 교체 알고리즘
요약
메모리 관리를 위한 필수 개념, 페이지 교체 알고리즘을 파헤쳐봅니다. 페이지와 페이지 부재의 개념부터 FIFO, LRU, LFU 알고리즘의 동작 방식과 차이점을 명확히 이해하고, 정보처리기사 실기 대비 문제로 실력을 점검하세요.
페이지 교체 알고리즘 정리
| 알고리즘 | 교체 대상 | 기반 원리 |
|---|---|---|
| FIFO | 가장 먼저 메모리에 들어온 페이지 | 선입선출 |
| LRU | 가장 오랫동안 사용되지 않은 페이지 | 시간 지역성 |
| LFU | 참조 횟수가 가장 적은 페이지 | 참조 빈도 |
페이지 교체 알고리즘은 가상 메모리 시스템에서 물리 메모리(RAM)의 프레임이 부족할 때, 어떤 페이지를 보조기억장치로 내보낼지 결정하는 알고리즘입니다.
페이지 교체가 필요한 이유
페이지 교체 알고리즘은 가상 메모리 위에서 동작합니다. 문제를 풀 때 필요한 용어만 짧게 정리하면 다음과 같습니다.
| 용어 | 뜻 |
|---|---|
| 페이지 | 프로그램이 보는 메모리 공간(논리 주소 공간)을 일정한 크기로 나눈 블록 |
| 프레임(페이지 프레임) | RAM을 페이지와 같은 크기로 나눈 자리. "페이지 프레임이 3개"는 페이지를 담을 자리가 3칸이라는 뜻 |
| 참조 | 프로그램이 어떤 페이지를 사용하는 것. 문제에 주어지는 페이지 순서가 참조 순서 |
| 페이지 부재 | 참조한 페이지가 RAM(프레임)에 없어 보조기억장치에서 가져와야 하는 상황 |
페이지 부재가 났는데 빈 프레임이 없으면, RAM에 있는 페이지 하나를 보조기억장치로 내보내고(swap-out) 그 자리에 필요한 페이지를 가져옵니다(swap-in). 이때 "어떤 페이지를 내보낼 것인가?"를 결정하는 규칙이 바로 페이지 교체 알고리즘입니다.
페이지 테이블로 주소를 바꾸는 과정과 페이지 부재가 처리되는 순서는 가상 메모리 글에서 그림과 함께 자세히 다룹니다.
주요 페이지 교체 알고리즘
페이지 교체 알고리즘의 목표는 페이지 부재 횟수를 최소화하여 시스템 성능을 높이는 것입니다. FIFO, LRU, LFU가 대표적인 알고리즘입니다.
FIFO (First-In, First-Out)
가장 간단한 알고리즘으로, RAM에 가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식입니다. 마치 줄을 서서 먼저 온 사람이 먼저 나가는 것과 같습니다.
- 장점: 구현이 매우 간단합니다.
- 단점: 자주 사용되는 페이지임에도 불구하고 먼저 들어왔다는 이유만으로 교체될 수 있어 비효율적일 수 있습니다. (이를 Belady의 모순(Belady's Anomaly) 이라고도 합니다. 프레임 수를 늘렸는데도 페이지 부재가 더 많이 발생하는 현상)
LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다. "최근에 사용된 페이지는 가까운 미래에도 다시 사용될 것이다"라는 시간 지역성(Temporal Locality) 아이디어를 기반으로 합니다.
- 장점: FIFO에 비해 페이지 부재율이 낮고, 일반적으로 좋은 성능을 보입니다.
- 단점: 각 페이지의 최근 사용 시간을 기록하고 유지해야 하므로, 운영체제의 부담이 크고 구현이 복잡합니다.
LFU (Least Frequently Used)
참조 횟수가 가장 적은 페이지를 교체하는 알고리즘입니다. "과거에 많이 사용된 페이지는 앞으로도 많이 사용될 것이다"라는 가정에 기반합니다.
- 장점: LRU가 잡아내지 못하는 장기적인 참조 패턴을 고려할 수 있습니다.
- 단점:
- 참조 횟수를 계산하기 위한 오버헤드가 큽니다.
- 초기에 많이 사용되었지만 더 이상 사용되지 않는 페이지가 계속 메모리에 남아있을 수 있습니다.
- 참조 횟수가 동일한 페이지가 여러 개일 경우, 어떤 것을 교체할지 결정하기 위한 추가적인 규칙(e.g., FIFO)이 필요합니다.
댓글