가상 메모리 — 페이징, 페이지 폴트, 그리고 스래싱

RAM이 4GB인데 프로세스 10개가 각각 1GB씩 요구하면 어떻게 될까? 프로세스 A가 프로세스 B의 메모리를 건드리지 못하게 하려면?

가상 메모리는 이 두 가지 문제를 동시에 해결하는 구조입니다. 각 프로세스에게 독립적인 주소 공간을 제공하면서, 물리 메모리보다 큰 공간을 사용할 수 있게 만들어요.

가상 메모리가 왜 필요한가

물리 메모리(RAM)는 용량이 한정되어 있습니다. 4GB짜리 RAM에서 프로세스 10개가 각각 1GB씩 요구하면? 당연히 안 되죠. 그렇다고 프로세스마다 "너는 여기서부터 여기까지만 써" 하고 물리 주소를 직접 할당하면, 프로세스끼리 메모리를 침범하는 문제가 생기고 멀티프로그래밍 자체가 어려워집니다.

가상 메모리는 이 문제를 해결하기 위해 각 프로세스에게 독립적인 가상 주소 공간 을 제공합니다. 프로세스 입장에서는 마치 자기 혼자 메모리를 전부 쓰는 것처럼 보이지만, 실제로는 OS가 뒤에서 가상 주소를 물리 주소로 변환해주고, 지금 당장 필요하지 않은 데이터는 디스크(스왑 영역)에 내려놓아요.

핵심 이점을 정리하면 이렇습니다.

• 프로세스 격리: 프로세스 A가 프로세스 B의 메모리를 건드릴 수 없습니다
• 물리 메모리보다 큰 주소 공간 사용: 실제 RAM이 4GB여도 프로세스는 자신만의 4GB(32비트 기준) 주소 공간을 갖습니다
• 메모리 관리 단순화: 프로그래머는 물리 메모리 배치를 신경 쓸 필요가 없어요
• 공유 메모리: 여러 프로세스가 같은 물리 프레임을 공유할 수 있어서 공유 라이브러리 같은 걸 효율적으로 올릴 수 있습니다

페이징 (Paging)

가상 메모리를 구현하는 가장 대표적인 기법이 페이징 입니다.

페이지와 프레임

가상 주소 공간은 페이지(Page) 라는 고정 크기 블록으로 나뉘고, 물리 메모리도 같은 크기의 프레임(Frame) 으로 나뉘어요. 보통 페이지 크기는 4KB입니다. 가상 주소의 페이지를 물리 메모리의 프레임에 매핑하는 방식으로 동작하기 때문에, 연속된 가상 주소가 물리 메모리에서는 흩어져 있을 수 있어요. 그래도 프로세스는 그런 거 모릅니다 — 자기한테는 연속된 주소로 보이니까요.

페이지 테이블 (Page Table)

가상 페이지 번호를 물리 프레임 번호로 바꿔주는 매핑 테이블입니다. 프로세스마다 하나씩 가지고 있어요.

가상 주소는 두 부분으로 쪼개집니다.

예를 들어 32비트 주소 체계에서 페이지 크기가 4KB(2^12)라면, 상위 20비트가 페이지 번호, 하위 12비트가 오프셋이 됩니다.

페이지 테이블 엔트리(PTE)에는 프레임 번호 말고도 여러 비트가 붙어요.

• Valid bit: 이 페이지가 물리 메모리에 올라와 있는지
• Dirty bit: 이 페이지가 수정되었는지 (스왑 아웃할 때 디스크에 다시 써야 하는지 판단)
• Reference bit: 최근에 접근되었는지 (페이지 교체 알고리즘에서 사용)
• Protection bit: 읽기/쓰기/실행 권한

MMU (Memory Management Unit)

주소 변환은 CPU 안의 MMU 라는 하드웨어가 담당합니다. CPU가 가상 주소를 내보내면 MMU가 페이지 테이블을 참조해서 물리 주소로 변환한 뒤, 그 주소로 메모리에 접근해요. 소프트웨어로 하면 매 메모리 접근마다 오버헤드가 생기니까, 하드웨어가 처리하는 겁니다.

TLB (Translation Lookaside Buffer)

문제가 하나 있습니다. 페이지 테이블 자체도 메모리에 있다는 거예요. 그러면 메모리에 한 번 접근하려면 페이지 테이블 조회 1번 + 실제 데이터 접근 1번, 총 2번의 메모리 접근 이 필요합니다. 느리죠.

그래서 등장한 게 TLB 입니다. MMU 안에 있는 아주 작고 빠른 캐시로, 최근에 변환한 페이지 번호 → 프레임 번호 매핑을 저장해둡니다.

동작 흐름:

1. CPU가 가상 주소 발생
2. TLB에서 해당 페이지 번호 검색 (TLB Hit → 바로 물리 주소 획득, 빠름)
3. TLB에 없으면 (TLB Miss) → 페이지 테이블에서 조회 후 TLB에 캐싱
4. 물리 주소로 메모리 접근

TLB 적중률이 보통 95% 이상이기 때문에 대부분의 메모리 접근은 추가 오버헤드 없이 처리됩니다. 엔트리 수는 보통 64~1024개 정도로 작지만, 지역성(locality) 덕분에 적중률이 높게 유지돼요.

참고로 컨텍스트 스위칭이 일어나면 TLB를 비워야(flush) 합니다. 프로세스마다 페이지 테이블이 다르니까요. 이 비용을 줄이기 위해 ASID(Address Space ID) 같은 걸 쓰기도 해요.

페이지 폴트 (Page Fault) 처리 과정

프로세스가 접근하려는 페이지가 물리 메모리에 없을 때 발생합니다. 페이지 테이블의 valid bit가 0인 상태예요.

처리 흐름:

1. CPU가 가상 주소로 메모리 접근 시도
2. MMU가 페이지 테이블 조회 → valid bit가 0 → 페이지 폴트 트랩 발생
3. OS 커널로 제어권 전환
4. 유효한 접근인지 확인 (주소 범위 밖이면 segfault)
5. 디스크(스왑 영역)에서 해당 페이지를 찾습니다
6. 비어 있는 프레임을 찾습니다 — 없으면 페이지 교체 알고리즘 가동
7. 디스크에서 페이지를 물리 프레임에 로드 (I/O 발생, 느림)
8. 페이지 테이블 업데이트 (프레임 번호 기록, valid bit → 1)
9. 트랩을 발생시킨 명령어부터 다시 실행

핵심은 7번 단계가 디스크 I/O 라는 점입니다. 메모리 접근은 나노초 단위인데, 디스크 I/O는 밀리초 단위니까 수만 배 느려요. 그래서 페이지 폴트 빈도를 최소화하는 게 성능에 직결됩니다.

페이지 교체 알고리즘

물리 메모리가 꽉 찼을 때, 어떤 페이지를 내쫓고 새 페이지를 올릴지 결정하는 알고리즘입니다. 목표는 페이지 폴트율을 최소화하는 거예요.

OPT (Optimal)

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 이론적으로 최적이지만 미래를 알 수 없으니 실제로는 구현이 불가능해요. 다른 알고리즘의 성능을 비교할 때 기준선으로 씁니다.

FIFO (First-In, First-Out)

가장 먼저 들어온 페이지를 먼저 내보냅니다. 구현이 가장 단순하지만 성능은 별로예요. 오래 전에 들어왔어도 지금 자주 쓰이는 페이지일 수 있으니까요.

LRU (Least Recently Used)

가장 오랫동안 사용되지 않은 페이지를 교체합니다. "최근에 쓴 건 앞으로도 쓸 가능성이 높다"는 시간적 지역성을 활용한 거예요. OPT에 가장 가까운 성능을 보여주지만, 매 메모리 접근마다 타임스탬프를 기록하거나 스택을 유지해야 해서 구현 비용이 높습니다.

LFU (Least Frequently Used)

사용 빈도가 가장 낮은 페이지를 교체합니다. 자주 쓰이는 페이지를 보호할 수 있지만, 과거에 폭발적으로 사용되었다가 이제는 안 쓰는 페이지가 카운트만 높아서 계속 살아남는 문제가 있어요.

Clock Algorithm (Second-Chance)

FIFO의 개선 버전입니다. 프레임들을 원형 큐로 관리하면서, 교체 대상을 선택할 때 reference bit 를 확인해요.

1. 포인터가 가리키는 페이지의 reference bit를 확인
2. bit가 1이면 → 0으로 바꾸고 다음으로 넘어감 (한 번 더 기회를 줌)
3. bit가 0이면 → 이 페이지를 교체

LRU에 근접한 성능을 내면서도 구현이 훨씬 간단해서, 실제 OS에서 많이 쓰입니다. Linux의 페이지 교체도 Clock 기반 변형을 사용해요.

Belady's Anomaly

상식적으로 프레임 수를 늘리면 페이지 폴트가 줄어야 합니다. 그런데 FIFO 알고리즘에서는 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 현상 이 나타날 수 있어요. 이걸 Belady's Anomaly라고 부릅니다.

왜 이런 일이 벌어질까요? FIFO는 페이지의 "사용 빈도"를 전혀 고려하지 않고 순서만 보기 때문입니다. 프레임 수가 바뀌면 교체 순서가 달라지면서, 운 나쁘게 자주 쓰는 페이지가 더 빨리 밀려나는 경우가 생겨요.

LRU나 OPT 같은 스택 알고리즘(stack algorithm) 에서는 이 현상이 발생하지 않습니다. 스택 알고리즘은 n개 프레임에서 메모리에 있는 페이지 집합이, n+1개 프레임에서의 집합에 항상 포함되는 성질을 갖기 때문이에요.

핵심만 정리하면 "FIFO의 단점은 Belady의 모순이다"로 이걸 언급하면 됩니다.

스래싱 (Thrashing)

현상

프로세스가 실제 작업보다 페이지 교체에 더 많은 시간을 쓰는 상태 입니다. 이런 일이 일어나는 흐름을 볼게요.

1. 멀티프로그래밍 정도(동시 실행 프로세스 수)를 높입니다
2. 프로세스마다 할당되는 프레임이 줄어듭니다
3. 페이지 폴트가 급증합니다
4. 디스크 I/O 대기가 늘어나면서 CPU 이용률이 떨어집니다
5. OS는 CPU 이용률이 낮으니까 프로세스를 더 올립니다
6. 악순환. 시스템이 거의 멈춥니다

해결: Working Set Model

Peter Denning이 제안한 모델입니다. 프로세스가 특정 시간 윈도우(Δ) 동안 참조하는 페이지들의 집합을 워킹 셋(Working Set) 이라 부릅니다. 각 프로세스에게 워킹 셋 크기만큼의 프레임을 보장해주면, 페이지 폴트를 크게 줄일 수 있어요.

모든 프로세스의 워킹 셋 합이 물리 메모리를 초과하면? 그때는 일부 프로세스를 통째로 스왑 아웃시켜서 나머지 프로세스가 충분한 프레임을 확보하게 합니다.

해결: PFF (Page Fault Frequency)

좀 더 직관적인 방법입니다. 프로세스의 페이지 폴트 비율을 모니터링하다가,

• 폴트율이 상한선을 넘으면 → 프레임을 더 할당
• 폴트율이 하한선 아래면 → 프레임을 회수

이렇게 동적으로 조절해요. 더 이상 줄 프레임이 없는데 폴트율이 높으면, 해당 프로세스를 suspend합니다.

세그멘테이션 vs 페이징

현대 OS 대부분은 페이징 을 주로 사용합니다. 세그멘테이션은 x86의 레거시 기능으로 남아 있고, x86-64에서는 사실상 평탄 세그먼트(flat segment) 모델을 쓰면서 세그멘테이션을 무력화시켰어요.

다만 개념적으로 세그멘테이션은 여전히 쓰입니다. 프로세스 메모리를 코드/데이터/힙/스택으로 나누는 것 자체가 세그멘테이션적 사고방식이고, 보호와 공유의 단위로 활용돼요. 실제로는 세그멘테이션 + 페이징 을 결합해서 쓰는 시스템도 있었습니다(Intel IA-32).

주의할 점

TLB 플러시의 숨겨진 비용

컨텍스트 스위칭이 일어나면 TLB를 비워야(flush) 합니다. 프로세스마다 페이지 테이블이 다르니까요. 전환 직후 모든 메모리 접근에서 TLB 미스가 발생하고, 이 비용이 컨텍스트 스위칭의 간접 비용 중 가장 큽니다. ASID(Address Space ID)로 완화할 수 있지만, 모든 아키텍처가 지원하는 건 아니에요.

페이지 폴트와 디스크 I/O

페이지 폴트의 핵심 비용은 디스크 I/O 입니다. 메모리 접근이 나노초 단위인데, 디스크 I/O는 밀리초 단위 — 수만 배 차이예요. SSD가 보편화되면서 줄어들었지만, 여전히 페이지 폴트 빈도가 성능에 직결됩니다.

FIFO의 Belady's Anomaly

FIFO 알고리즘에서는 프레임 수를 늘렸는데 오히려 페이지 폴트가 증가하는 현상이 나타날 수 있습니다. 사용 빈도를 고려하지 않고 순서만 보기 때문이에요. LRU나 OPT 같은 스택 알고리즘에서는 발생하지 않습니다.

Demand Paging

프로세스 시작 시 모든 페이지를 메모리에 올리지 않고, 실제로 접근할 때 그때서야 올리는 전략 입니다. 처음 접근하면 반드시 페이지 폴트가 발생하지만, 쓰지도 않을 페이지를 미리 올리느라 메모리를 낭비하는 것보다 낫죠.

반대 개념으로 Pre-paging 이 있습니다. 곧 사용될 것 같은 페이지를 미리 올려두는 건데, 예측이 틀리면 오히려 메모리만 낭비해요. 실제로는 demand paging이 기본이고, 프로세스 시작 시 초기 working set 정도만 pre-page하는 절충안을 씁니다.

Copy-on-Write (COW)

fork() 시스템 콜로 자식 프로세스를 만들면, 부모의 주소 공간을 통째로 복사해야 합니다. 그런데 자식이 바로 exec()을 호출해서 새 프로그램을 로드하면? 복사한 메모리가 전부 버려져요. 낭비가 심합니다.

COW는 fork 직후에 부모와 자식이 같은 물리 프레임을 공유 하게 하고, 둘 중 하나가 해당 페이지를 수정(write)하려 할 때 그때서야 복사 합니다. 이러면 실제로 수정되는 페이지만 복사되니까 엄청나게 효율적이에요.

Memory Mapped File

파일을 메모리 주소 공간에 직접 매핑하는 방식입니다. mmap() 시스템 콜을 사용해요. 파일 내용이 가상 메모리에 매핑되어 있으니까, 포인터로 파일 데이터에 접근할 수 있습니다. read()/write() 시스템 콜 없이 메모리 접근만으로 파일 I/O가 가능해져요.

페이지 폴트 메커니즘을 그대로 활용합니다. 매핑만 해두고, 실제로 해당 영역을 읽으려 할 때 페이지 폴트가 발생하면 그때 디스크에서 읽어와요. 여러 프로세스가 같은 파일을 매핑하면 물리 프레임도 공유할 수 있어서, 공유 라이브러리(.so, .dll) 로딩에 핵심적으로 쓰입니다.

메모리 단편화

• 내부 단편화: 할당된 메모리 블록 안에서 실제로 사용하지 않는 공간이 남는 것입니다. 페이징에서 마지막 페이지가 4KB를 다 채우지 못하면 남는 부분이 내부 단편화예요.
• 외부 단편화: 빈 공간이 전체적으로는 충분한데, 조각나 있어서 연속된 큰 블록을 할당할 수 없는 상태입니다. 가변 크기 할당(세그멘테이션, malloc)에서 발생해요. 컴팩션(compaction)으로 해결 가능하지만, 메모리를 재배치해야 하니까 비용이 큽니다.

페이징은 고정 크기 블록을 쓰기 때문에 외부 단편화가 원천적으로 발생하지 않습니다. 이게 페이징의 가장 큰 장점 중 하나예요.

파생 개념

프로세스 메모리 구조

프로세스의 가상 주소 공간은 보통 이렇게 구성됩니다.

힙과 스택이 서로를 향해 자라기 때문에 충돌하면 스택 오버플로우나 메모리 부족이 발생합니다.

캐시 (L1/L2/L3)

CPU와 메인 메모리 사이의 속도 차이를 메우는 계층 구조입니다.

• L1 캐시: CPU 코어 내부. 가장 빠르고(1ns), 가장 작습니다(3264KB). 보통 명령어 캐시(I-cache)와 데이터 캐시(D-cache)로 분리돼요
• L2 캐시: 코어별 또는 코어 쌍별. L1보다 크고(256KB~1MB) 조금 느립니다(~4ns)
• L3 캐시: 모든 코어가 공유. 더 크고(수 MB~수십 MB) 더 느려요(~10ns)

TLB도 캐시의 일종이라고 볼 수 있습니다. 그리고 페이지 테이블을 위한 전용 캐시가 TLB인 것처럼, 데이터/명령어를 위한 캐시가 L1/L2/L3인 셈이에요. 캐시가 잘 작동하는 이유도 결국 지역성(locality) 원리 — 시간적 지역성과 공간적 지역성 — 덕분입니다.

메모리 관리: malloc과 GC

malloc / free (C/C++): 힙 영역에서 메모리를 수동으로 할당하고 해제합니다. 해제를 빼먹으면 메모리 누수, 이미 해제한 걸 다시 쓰면 use-after-free 버그가 발생해요. 내부적으로는 brk/sbrk 시스템 콜이나 mmap으로 OS에 페이지를 요청하고, 유저 레벨에서 free list 등을 관리합니다.

GC (Garbage Collection): Java, Go, Python 등에서 사용합니다. 더 이상 참조되지 않는 객체를 자동으로 회수해요. 편하지만 GC가 도는 동안 애플리케이션이 멈추는 STW(Stop-The-World) 문제가 있고, GC 튜닝 자체가 하나의 분야입니다. 메모리 관리를 런타임에 맡기는 거라 성능에 민감한 시스템에서는 수동 관리를 선호하기도 해요.

이 두 가지가 가상 메모리 위에서 동작한다는 점을 기억하세요. malloc이 메모리를 달라고 하면, 결국 OS가 페이지 단위로 물리 프레임을 할당해주는 겁니다.