Virtual Memory & Paging

1. Overview

가상 메모리와 페이징(Virtual Memory & Paging)은 프로그램이 독립적인 연속 주소 공간을 가진 것처럼 실행되도록, 운영체제와 CPU(MMU)가 가상 주소를 물리 메모리에 매핑하는 메모리 가상화 기법입니다.

학습자는 연속적으로 보이는 가상 주소(Virtual Address)가 실제로는 물리 램(Physical RAM)의 여러 프레임에 나뉘어 매핑되는 페이지 테이블(Page Table) 구조를 이해합니다. 이어 RAM이 부족할 때 덜 쓰는 페이지를 스왑(Swap) 공간으로 내보내는 **페이지 교체 알고리즘(LRU)**과, 주소 변환 비용을 줄이는 CPU 내부 하드웨어 캐시인 **TLB(Translation Lookaside Buffer)**를 살펴보며 OOM(Out of Memory)과 쓰레싱(Thrashing)을 진단하는 관점을 익힙니다.

2. Scope & Boundaries

In-Scope

• 주소 변환 기하학 (Address Translation): 가상 주소(Virtual Address), 물리 주소(Physical Address), MMU(Memory Management Unit).
• 페이징과 단편화 (Paging & Fragmentation): 외부/내부 단편화, 페이지(Page, 가상)와 프레임(Frame, 물리) 사이즈(4KB, HugePages 2MB).
• 메모리 환상 장벽 (Isolation & Demand Paging): 페이지 폴트(Page Fault), 스왑 인/아웃(Swap In/Out), 요구 페이징(Demand Paging).
• 페이지 교체와 하드웨어 가속 (Replacement & TLB): 페이지 교체 알고리즘(FIFO, LRU, Clock), TLB(Translation Lookaside Buffer) 미스율.

Out-of-Scope

• 캐시 메모리 일관성 원리: L1/L2 캐시 메모리가 멀티코어 환경에서 쪼개지는 하드웨어 프로토콜(MESI) $\rightarrow$ 02-01-02. CPU Architecture Mechanics 영역.
• 가비지 컬렉션(GC) 알고리즘: 유저 공간(V8 엔진/JVM)에서 힙(Heap) 메모리를 청소하는 마크-앤-스윕 방식 $\rightarrow$ 01-05-02. Memory Management (GC) 영역.

Boundaries

• Virtual Memory vs. File System (03-03-03): 페이징 스왑(Swap)은 RAM이 부족할 때 익명 메모리 페이지를 임시로 스왑 파티션에 내보냈다가 다시 불러오는 메모리 확장 장치입니다. 파일 시스템(VFS)은 사용자가 읽고 관리할 파일을 디렉토리 구조에 영구 보존하는 저장 장치입니다. 스왑 공간은 사용자가 일반 텍스트 파일을 저장하는 영역이 아닙니다.

3. Counterexample

• 빅데이터 연속 할당의 한계 (External Fragmentation Illusion): 커널이 가상 메모리(페이징) 없이 프로세스에게 물리 RAM 공간을 연속적으로만 할당(Contiguous Allocation)한다고 가정해봅니다. 메모리 16GB 중 12GB가 비어 있어도, 프로세스 생성과 종료가 반복되어 최대 연속 빈 공간이 1GB뿐이라면 2GB를 요구하는 프로그램은 실행되지 못할 수 있습니다. 페이징은 4KB 단위의 프레임을 조합해 이런 외부 단편화 문제를 줄입니다.
• 배열 접근 패턴과 쓰레싱 (Thrashing by Poor Locality): 실제 RAM이 1GB뿐인 환경에서 int arr[10000][10000](400MB) 이차원 배열을 열(Column) 방향으로 스캔하면, C 배열의 행(Row) 우선 저장 방식과 맞지 않아 페이지 폴트(Page Fault)가 급증할 수 있습니다. CPU는 유용한 연산보다 Swap In/Swap Out에 시간을 쓰게 되고, 시스템은 쓰레싱(Thrashing)에 빠질 수 있습니다.

4. Prerequisites

• 권한 링과 컨텍스트 (Basic): 페이지 폴트가 터졌을 때 CPU가 유저 권한에서 커널 모드(Ring 0)로 강제 스위칭되어 램을 메꾼다는 OS 트랩 구조를 알아야 합니다. (03-01-02 System Call Interface)
• CPU 캐시 레이어 (Recommended): TLB(하드웨어 주소 번역 캐시)가 무엇인지 이해하기 위해 L1/L2 캐시의 속도차 개념이 필요합니다. (02-01-02 CPU Architecture)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 가상 주소와 MMU (Virtual Memory Illusion)

• Why to Learn: 프로그램 A와 프로그램 B가 같은 0x04000 주소를 사용해도 서로의 메모리를 침범하지 않도록 격리되는 가상 주소 공간 구조를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 가상 주소(Virtual Address, 논리 주소), 물리 주소(Physical Address), MMU(Memory Management Unit).
  • Skills: 주소 변환(Address Translation) 메커니즘, 독립된 주소 공간(Isolated Space) 검증.
  • Tools: 리눅스 /proc/[pid]/maps 메모리 공간 레이아웃.
  • Trade-offs: 프로세스마다 독립적인 가상 주소 공간을 제공하면 메모리 충돌과 권한 침범을 줄일 수 있습니다. 대신 CPU가 메모리에 접근할 때마다 MMU가 가상 주소를 물리 주소로 변환해야 하므로 주소 변환 오버헤드가 발생합니다.
• How to Learn:
  • 1단계: 사용자 앱이 메모리 0x5000 번지에 "Hello"를 쓰려고 할 때, CPU(MMU)가 프로세스별 매핑 정보를 참고해 실제 RAM 0x25000 같은 물리 주소로 변환하는 과정을 살핍니다.
  • 2단계: 프로세스 2번이 같은 0x5000 주소를 사용해도, MMU가 프로세스 2번의 매핑 정보를 기준으로 다른 물리 주소에 연결해 두 프로그램이 서로의 메모리를 읽지 못하는 이유를 확인합니다.
• Implement: 파이썬 딕셔너리로 Physical_RAM 100칸짜리 배열을 만들고, MMU_Table 클래스를 통해 프로세스 A의 주소 0번은 RAM 50번으로, 프로세스 B의 주소 0번은 RAM 80번으로 변환되도록 구성합니다. 같은 가상 주소가 프로세스마다 다른 물리 주소로 매핑되는 디버그 로그를 출력합니다.

Recommended

Core Topic 02: 페이지 단위 매핑과 테이블 구조 (Paging & Tables)

• Why to Learn: 메모리를 연속된 큰 덩어리로만 할당하면 외부 단편화 때문에 충분한 총량의 RAM이 있어도 큰 연속 공간을 확보하지 못할 수 있습니다. 4KB 페이지 단위 매핑이 이 문제를 어떻게 줄이는지 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 페이지(Page, 가상), 프레임(Frame, 물리), 외부 단편화(External Fragmentation), 내부 단편화(Internal Fragmentation).
  • Skills: 다단계 페이지 테이블(Multi-level Page Table), HugePages(2MB 대용량 매핑 튜닝).
  • Tools: htop의 VIRT(가상)와 RES(물리) 메모리 차이 관측.
  • Trade-offs: 메모리를 4KB 페이지 단위로 나누면 외부 단편화를 크게 줄일 수 있습니다. 대신 각 페이지의 매핑 정보를 저장하는 페이지 테이블 자체가 커져 커널 메모리 오버헤드가 발생하므로 다단계 테이블이 필요합니다.
• How to Learn:
  • 1단계: 가상 주소 공간을 4KB 크기의 페이지로 나누고, 실제 RAM도 같은 크기의 프레임으로 나눕니다. 가상 1번 페이지가 RAM 5번 프레임에, 가상 2번 페이지가 RAM 99번 프레임에 연결될 수 있음을 테이블로 표현합니다.
  • 2단계: 64비트 OS에서는 가상 주소 공간이 매우 크므로 전체 테이블을 한 번에 만들면 낭비가 큽니다. 사용하지 않는 주소 대역에는 테이블을 만들지 않는 2단계, 3단계 다단계 페이지 테이블 구조를 살핍니다.
• Implement: 32비트 환경을 모사합니다. 4KB 페이지 단위에서 입력된 가상 주소 0x00012345를 받아 상위 비트 0x00012를 가상 페이지 넘버(VPN)로, 하위 오프셋 0x345를 페이지 내부 위치로 분리합니다. 테이블을 거쳐 물리 프레임 넘버(PFN) 0x000A1로 바꾼 뒤 최종 물리 주소 0x000A1345를 계산하는 비트 마스킹(Shift) 연산기를 작성합니다.

Practical

Core Topic 03: 요구 페이징과 페이지 폴트 (Demand Paging & Faults)

• Why to Learn: 큰 프로그램을 실행할 때 필요한 모든 데이터를 처음부터 RAM에 올리지 않고, 실제 접근 시점에 필요한 페이지만 가져오는 요구 페이징의 최적화를 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 요구 페이징(Demand Paging), 페이지 폴트(Page Fault - Minor/Major), 스왑 영역(Swap Space).
  • Skills: 카피 온 라이트(Copy-on-Write, COW), 유효-무효 비트(Valid-Invalid Bit).
  • Tools: 리눅스 sar -B (페이지 폴트 프로파일링).
  • Trade-offs: 실제 접근(Touch)하는 4KB 페이지 단위로만 데이터를 올리면 초기 로딩과 메모리 사용량을 줄일 수 있습니다. 대신 실행 중 아직 올라오지 않은 페이지를 접근할 때마다 Page Fault가 발생해 커널 처리와 I/O 지연이 생길 수 있습니다.
• How to Learn:
  • 1단계: 실행 파일을 클릭하면 커널은 페이지 테이블에 주소 정보를 준비하지만, 아직 실제 물리 RAM을 할당하지 않은 상태(Valid Bit=0)로 시작할 수 있습니다. CPU가 첫 코드를 읽으려는 순간 해당 페이지가 없으면 Page Fault가 발생합니다.
  • 2단계: 커널은 필요한 4KB 페이지를 디스크에서 RAM의 빈 프레임으로 가져오고, 페이지 테이블을 업데이트(Valid Bit=1)한 뒤 원래 명령을 다시 실행(Resume)합니다.
• Implement: 모방 루프 스크립트를 작성합니다. 배열 인덱스 Mem[index] 접근 시 해당 인덱스가 Loaded_Pages 셋(Set)에 없으면 Raise PageFault를 발생시키고, 예외 처리기에서 Disk_Read(100ms 지연)을 시뮬레이션한 뒤 셋에 추가해 재시도하는 Lazy-Loading 시퀀스를 구현합니다.

Advanced

Core Topic 04: 쓰레싱과 TLB, 페이지 교체 (Thrashing & TLB Hardware)

• Why to Learn: RAM이 부족해 스왑을 사용해야 하는 상황에서 잘못된 페이지 교체가 쓰레싱(Thrashing)을 유발하는 이유와, TLB 캐시 미스가 성능에 미치는 영향을 이해하기 위해서입니다.
• What to Learn:
  • Concepts: 쓰레싱(Thrashing), 워킹 셋(Working Set), 페이지 교체 알고리즘(LRU, Clock/Second Chance), TLB(Translation Lookaside Buffer).
  • Skills: 스왑 파티션(Swap Partition) 최적화, 메모리 로컬리티(Spatial/Temporal Locality) 활용 코딩.
  • Tools: 리눅스 vmstat, sysctl vm.swappiness.
  • Trade-offs: 가장 오래 쓰지 않은 페이지(LRU)를 골라 스왑 아웃(Swap-out)하면 RAM 공간을 확보할 수 있습니다. 하지만 모든 페이지의 최근 접근 시간을 정확히 추적하려면 비용이 크므로, 실제 OS는 Clock 알고리즘처럼 더 가벼운 근사 방식을 사용합니다.
• How to Learn:
  • 1단계: 페이징의 재앙(Thrashing): RAM이 가득 찬 상태에서 여러 프로그램이 서로 다른 페이지를 계속 요구하면, 커널이 방금 내보낸 페이지를 곧바로 다시 불러오는 과정이 반복될 수 있습니다. 이때 디스크 I/O는 높고 CPU의 실제 연산은 줄어듭니다.
  • 2단계: 주소 번역의 한계(TLB): 가상 주소를 물리 주소로 번역할 때 페이지 테이블 접근이 반복되면 비용이 커집니다. TLB는 최근 주소 변환 결과를 저장해 이 비용을 줄이는 하드웨어 캐시입니다.
• Implement: 3칸짜리 물리 프레임(RAM)과 가상 페이지 요청 스트림 [1, 2, 3, 1, 4, 1, 5, 2]를 입력받는 LRU 교체 시뮬레이터를 구현합니다. 가장 오래 사용하지 않은 페이지를 스왑아웃하며 페이지 폴트 카운트를 집계하고, 지역성(Locality)이 낮은 랜덤 접근에서 폴트율이 높아지는 모습을 출력합니다.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Computer Organization (Memory) — Structural context.
• [P1] CS2023 - OS/Operating System Principles (Virtual Memory) — Core requirements.

Secondary

• [Operating Systems: Three Easy Pieces] Remzi — The virtualization of memory.
• [Modern Operating Systems] Andrew S. Tanenbaum — Paging systems analysis.

Industry

• [Intel: IA-32/Intel 64 Paging Structures] — Hardware implementation reference.
• [ARM: Identity Mapping and Memory Management] — Embedded VMP standard.

9. Final Checklist

Primary

• '가상 주소'가 MMU를 거쳐 '물리 주소'로 변환되는 하드웨어 경로를 3단계(Directory, Table, Offset)로 설명 가능한가? (P1)
• '페이지 폴트' 발생 시 운영체제가 커널 모드에서 수행하는 처리 절차를 설명할 수 있는가? (P1)

Secondary

• '단일 페이지 테이블' 구조가 64비트 환경에서 왜 현실적으로 비효율적인지 메모리 사용량 근거를 제시할 수 있는가?
• LRU 알고리즘이 왜 이론적으로 좋지만 실제 구현에서는 비용이 큰지 제약 사항을 설명할 수 있는가?

Industry

• 대용량 DB 서버 튜닝 시, 'Huge Pages' 설정이 페이지 테이블의 깊이를 어떻게 줄이고 주소 변환 물리 오버헤드를 낮추는지 제안할 수 있는 가? (SFIA)
• 리눅스 환경에서 OOM Killer가 작동하는 트리거 조건과 프로세스 선정 기준을 기술할 수 있는가?