메모리 관리 (페이지, LRU, 가상메모리)
운영체제의 가장 까다로운 책임 중 하나가 한정된 물리 메모리(RAM)를 여러 프로세스가 안전하고 효율적으로 나눠 쓰도록 관리하는 일이다. 메모리가 부족하면 프로그램이 멈추고, 분배가 불공평하면 한 프로세스가 시스템 전체를 마비시킬 수 있으며, 단편화가 누적되면 빈 공간이 충분한데도 큰 메모리를 할당할 수 없는 사태가 벌어진다. 이 모든 문제를 풀어 주는 핵심 메커니즘이 가상 메모리(Virtual Memory)와 페이징(Paging)이며, 그 위에 페이지 교체 알고리즘이 얹어진다. 본 글은 메모리 계층·가상 메모리·페이지 교체 알고리즘을 정보처리기사 시험 범위와 실무 입문 영역에 모두 닿도록 세심하게 정리한다(출처: 위키백과 — Virtual memory). 제가 학교 OS 수업에서 같은 페이지 참조열에 FIFO·LRU·LFU를 모두 시뮬레이션해 본 후 결과가 모두 다르게 떨어지는 모습을 직접 본 후로는 "교체 알고리즘 한 줄의 차이가 페이지 부재율을 결정한다"는 사실을 손끝으로 받아들였다.
가상 메모리와 페이징의 기본 구조
가상 메모리(Virtual Memory)란 보조 기억장치(SSD/HDD)의 일부를 주기억장치(RAM)처럼 활용해 실제 물리 메모리보다 훨씬 큰 가상의 주소 공간을 각 프로세스에 제공하는 기법이다. 모든 프로그램은 자신만의 독립적인 가상 주소 공간을 갖는다고 믿고 동작하며, 운영체제와 MMU(Memory Management Unit)가 가상 주소를 실제 물리 주소로 변환해주는 역할을 수행한다. 여기서 MMU란 CPU 안에 내장된 전용 하드웨어로, 가상 주소를 물리 주소로 매핑하는 페이지 테이블을 빠르게 참조해 주는 변환 가속기를 가리킨다.
가상 메모리의 가장 큰 가치는 두 가지다. 첫째, 물리 메모리보다 큰 프로그램을 실행할 수 있다. 자주 쓰지 않는 페이지는 디스크에 두고 필요할 때만 RAM에 올리는 방식이기 때문이다. 둘째, 프로세스 간 메모리 격리가 자연스럽게 보장된다. 각 프로세스가 자기만의 가상 주소 공간을 가지므로 다른 프로세스의 메모리에 직접 접근할 수 없다.
가상 메모리를 구현하는 두 가지 표준 방식이 페이징과 세그멘테이션이다.
| 비교 항목 | 페이징(Paging) | 세그멘테이션(Segmentation) |
|---|---|---|
| 분할 단위 | 고정 크기(페이지) | 가변 크기(세그먼트) |
| 외부 단편화 | 없음 | 있음 |
| 내부 단편화 | 있음 (마지막 페이지) | 없음 |
| 주소 변환 | 페이지 번호 + 오프셋 | 세그먼트 + 오프셋 |
| 대표 채택 | 거의 모든 현대 OS | 일부 시스템 (혼합형) |
여기서 페이징이란 메모리를 일정한 크기의 페이지 단위로 나누어 관리하는 기법으로, 일반적으로 4KB가 표준 페이지 크기이며, 외부 단편화 문제를 원천적으로 차단한다는 강점을 가진다. 세그멘테이션은 의미 단위(코드·데이터·스택)로 가변 크기 분할을 하지만 외부 단편화가 누적되는 문제가 있다. 현대 운영체제는 거의 예외 없이 페이징을 기반으로 하며, 일부는 세그멘테이션을 위에 얹은 페이지화된 세그멘테이션 형태를 채택한다.
가상 주소 0x12345 (32비트, 4KB 페이지)
┌─────────────┬─────────────┐
│ 페이지 번호 │ 오프셋 │
│ 20비트 │ 12비트 │
└──────┬──────┴─────────────┘
│ (페이지 테이블 조회)
▼
┌─────────────┐
│ 물리 프레임 │
│ 번호 │
└─────────────┘
물리 주소 = 프레임 번호 × 4KB + 오프셋페이지 부재와 페이지 교체 알고리즘
페이지 부재(Page Fault)란 프로세스가 참조하려는 페이지가 주기억장치에 없을 때 발생하는 상황이다. 이때 운영체제는 디스크에서 해당 페이지를 가져와야 하며, 빈 프레임이 없다면 기존에 있는 페이지 중 하나를 선택해 교체해야 한다. 어떤 페이지를 교체할지 결정하는 기준이 바로 페이지 교체 알고리즘이며, 시험에서는 다음 다섯 가지가 매회 출제된다.
| 알고리즘 | 기준 | 특징 |
|---|---|---|
| FIFO | 가장 먼저 적재된 페이지 | 구현 단순, 벨라디 이상 현상 발생 가능 |
| LRU (Least Recently Used) | 가장 오래 전 사용된 페이지 | 시간 지역성에 부합, 실무 가장 널리 채택 |
| LFU (Least Frequently Used) | 사용 빈도가 가장 낮은 페이지 | 초기 자주 쓰인 페이지 빼내기 약함 |
| OPT (Optimal) | 앞으로 가장 오래 안 쓰일 페이지 | 미래를 알아야 해 구현 불가 (이론 기준) |
| NUR (Not Used Recently) | 참조 비트·변형 비트 기반 | LRU 근사, 구현 비용 작음 |
여기서 벨라디 이상 현상(Belady's Anomaly)이란 페이지 프레임 수를 늘려도 페이지 부재율이 오히려 증가하는 비직관적 현상을 가리키며, FIFO에서만 발생한다. 1969년 라슬로 벨라디가 발견한 이 현상이 FIFO의 결정적 약점으로 자주 시험에 출제된다(출처: 위키백과 — Page replacement algorithm).
# LRU 페이지 교체 시뮬레이션
def lru(pages, frames):
cache = []
faults = 0
for p in pages:
if p in cache:
cache.remove(p); cache.append(p) # 가장 최근 사용으로 갱신
else:
faults += 1
if len(cache) >= frames:
cache.pop(0) # 가장 오래 전 사용 제거
cache.append(p)
return faults
print(lru([1,2,3,4,1,2,5,1,2,3,4,5], frames=3)) # 9
print(lru([1,2,3,4,1,2,5,1,2,3,4,5], frames=4)) # 10? 6? 실험으로 확인같은 참조열에 알고리즘 한 줄만 바꾸어 돌려 보면 페이지 부재율이 20~50%까지 달라지는 모습을 직접 볼 수 있다. 솔직히 제 경험상 학교 시뮬레이션에서 LRU가 OPT에 가장 가까운 성능을 내고, FIFO는 의외로 자주 LRU에 뒤지는 모습을 보고 나서야 "시간 지역성"이라는 추상적 단어가 페이지 부재율의 차이로 손에 잡혔다.
워킹셋·스래싱과 메모리 관리의 실전 도전
가상 메모리 운영에서 자주 출제되는 두 핵심 용어가 워킹셋(Working Set)과 스래싱(Thrashing)이다. 워킹셋은 일정 시간 동안 자주 참조되는 페이지의 집합이며, 한 프로세스가 효율적으로 동작하려면 자신의 워킹셋이 RAM에 모두 적재되어 있어야 한다. 워킹셋 크기보다 할당된 프레임이 적으면 페이지 부재가 폭증하기 시작한다.
스래싱은 페이지 부재가 너무 빈번해 CPU가 사용자 작업이 아니라 페이지 스왑 작업에 시간을 거의 모두 쓰는 현상을 가리킨다. CPU 사용률이 떨어지면 운영체제는 그것을 "프로세스가 부족하다"고 오판해 더 많은 프로세스를 적재하고, 그 결과 메모리 압박이 더 커져 페이지 부재가 더 늘어나는 악순환이 벌어진다. 스래싱을 막는 표준 전략은 워킹셋 모델(각 프로세스에 워킹셋 크기만큼 프레임 보장)과 페이지 부재 빈도 제어(부재율이 임계치를 넘으면 새 프로세스 적재 중단)이다.
| 단편화 종류 | 의미 | 해결 |
|---|---|---|
| 내부 단편화 | 할당한 공간 중 사용 안 한 일부 | 페이징의 마지막 페이지 (작은 비용) |
| 외부 단편화 | 빈 공간은 있는데 연속이 아니어서 못 씀 | 압축(compaction)·페이징으로 해결 |
여기서 외부 단편화란 메모리 어딘가에 빈 공간이 충분히 남아 있음에도 그 빈 공간들이 흩어져 있어 한 덩어리로 모이지 못해 큰 할당 요청을 거절하게 되는 상태를 의미하며, 가변 분할 방식의 결정적 약점이다. 페이징은 모든 분할 단위가 같은 크기이므로 외부 단편화가 원천적으로 없다는 점이 가장 큰 강점이고, 그 대가로 마지막 페이지의 남는 공간에서 발생하는 내부 단편화를 일부 감수한다. 솔직히 이건 예상 밖이었는데, 학교에서는 두 단편화의 정의만 외웠다가 실습에서 가변 분할로 빈 공간이 누적되는 모습을 본 후로는 "왜 모든 OS가 페이징을 채택했는가"라는 질문이 단번에 풀렸다. 다음 글에서는 이 메모리 관리 위에서 CPU 시간을 분배하는 CPU 스케줄링 알고리즘을 이어 다룬다.
메타 디스크립션: 가상 메모리와 페이징의 기본 구조, 페이지 교체 알고리즘 5종(FIFO·LRU·LFU·OPT·NUR)의 차이와 벨라디 이상 현상, 그리고 워킹셋·스래싱·단편화의 실전 도전을 코드 예시와 비교표로 세심하게 정리합니다.