페이징과 스왑

메모리 가상화의 핵심은 결국 페이징이야. 세그멘테이션이 가변 크기로 나눠서 외부 단편화를 만들었다면, 페이징은 주소 공간을 **고정 크기 단위(페이지, 보통 4KB)**로 잘라서 이 문제를 깔끔하게 없앤 거지.

물리 메모리도 같은 크기의 **프레임(frame)**으로 나누고, 각 가상 페이지가 어떤 물리 프레임에 매핑되는지를 **페이지 테이블(page table)**에 기록해. 프로세스마다 자기만의 페이지 테이블을 가지고, 가상 주소를 **VPN(Virtual Page Number)**과 오프셋으로 쪼갠 다음, VPN으로 페이지 테이블을 룩업해서 **PFN(Physical Frame Number)**을 얻고, PFN + 오프셋 = 물리 주소. 이게 전부야.

페이지 테이블의 각 항목(PTE)에는 PFN 말고도 Valid 비트(매핑이 유효한지), Protection 비트(읽기/쓰기/실행 권한), Present 비트(물리 메모리에 있는지 디스크로 갔는지), Dirty 비트(수정됐는지), Reference 비트(최근 접근됐는지) 같은 메타데이터가 들어가. 사용하지 않는 페이지에 접근하면 trap이 발생해서 OS가 프로세스를 죽이는데, 이게 우리가 자주 보는 segfault야. 그리고 성능 면에서 봤을 때, 메모리 접근 한 번을 하려면 페이지 테이블 먼저 읽어야 하니까 실질적으로 두 배의 메모리 접근이 필요해. 공간 면에서도, 32비트 주소 공간에 4KB 페이지면 페이지 테이블 항목이 약 100만 개, 하나가 4바이트면 테이블 하나가 4MB야. 프로세스 100개면 400MB가 테이블에만 날아가지.

성능 문제를 해결하는 게 **TLB(Translation Lookaside Buffer)**야. CPU 안에 있는 주소 변환 캐시인데, 최근에 쓴 VPN → PFN 매핑을 저장해둬. TLB에서 찾으면(히트) 추가 메모리 접근 없이 바로 물리 주소를 얻어. 실제 워크로드에서 TLB 히트율은 99% 이상이라 페이징 오버헤드가 거의 사라지지. 배열을 순회하면서 같은 페이지의 원소들에 접근하면 첫 원소만 미스고 나머지는 전부 히트 — 공간적 지역성 덕분이야. 같은 배열을 다시 순회하면 100% 히트 — 시간적 지역성이고. TLB 미스 처리는 두 가지 방식이 있는데, 하드웨어 관리 TLB(x86 같은 CISC)는 하드웨어가 직접 페이지 테이블을 걸어가서(page table walk) PTE를 찾아. 소프트웨어 관리 TLB(MIPS 같은 RISC)는 trap을 발생시켜서 OS가 처리하는데, OS가 원하는 아무 형태의 페이지 테이블을 쓸 수 있다는 유연성이 있지. 컨텍스트 스위치 때 TLB를 비우면(flush) 전환 직후에 미스가 폭발하니까, **ASID(Address Space IDentifier)**를 써서 여러 프로세스의 매핑이 TLB에 공존하게 하는 게 현대적 해법이야. TLB가 꽉 차면 LRU나 랜덤 정책으로 항목을 교체하고, 전체 크기는 32~128개 항목 정도로 작지만 히트율은 매우 높아.

공간 문제는 **다단계 페이지 테이블(multi-level page table)**로 해결해. 이게 현대 OS의 표준이야. 핵심 아이디어는 페이지 테이블 자체를 페이지 단위로 나누고, 사용하지 않는 범위의 페이지 테이블 페이지는 아예 할당을 안 하는 거야. **페이지 디렉토리(page directory)**가 추가돼서, VPN의 상위 비트로 **페이지 디렉토리 인덱스(PDI)**를 계산하고, 하위 비트로 **페이지 테이블 인덱스(PTI)**를 계산해. 해당 범위의 주소가 전부 invalid이면 페이지 디렉토리 항목(PDE)을 invalid로 마크하고 페이지 테이블 페이지 자체를 할당하지 않아. 사용하는 주소 공간에 비례하는 크기만 차지하니까 빈 공간이 많은 주소 공간에서 메모리를 엄청 아끼지. 대신 TLB 미스 시 메모리 접근이 늘어나는 시간-공간 트레이드오프가 있어 — 2단계면 3번, 3단계면 4번. x86-64는 4단계 페이지 테이블(PML4)을 쓰고, 최신 리눅스 커널은 5단계까지 확장됐어. 다른 접근으로 **역 페이지 테이블(inverted page table)**이 있는데, 가상 페이지 대신 물리 프레임마다 항목을 두는 발상의 전환이야. 테이블이 물리 메모리 크기에 비례해서 작아지지만 검색에 해시 테이블이 필요하고, PowerPC 같은 일부 아키텍처에서 썼지.

물리 메모리가 부족하면 **스와핑(swapping)**이 등장해. 자주 안 쓰는 페이지를 디스크의 스왑 공간으로 내보내고(swap out), 필요할 때 다시 불러오는(swap in) 거야. 이렇게 하면 물리 메모리보다 큰 주소 공간을 지원할 수 있지. PTE의 Present 비트가 0인 페이지에 접근하면 하드웨어가 **페이지 폴트(page fault)**를 발생시키고, OS의 페이지 폴트 핸들러가 PTE에 저장된 디스크 주소를 읽어서 해당 페이지를 물리 메모리로 가져와. 이 동안 프로세스는 blocked 상태로 가고 OS가 다른 프로세스를 돌려. 핵심은 프로세스가 페이지 폴트가 발생했다는 걸 전혀 모른다는 거야. TLB 미스는 빠르지만 페이지 폴트는 디스크 I/O라 밀리초 단위로 느리다는 차이를 확실히 구분해야 해. 재미있는 건 코드 페이지는 이미 실행 파일로 디스크에 있으니까 스왑 아웃할 때 그냥 버리면 돼 — 다시 필요하면 실행 파일에서 읽으면 되거든. 수정된 데이터 페이지만 스왑 공간에 써야 하지. OS는 빈 메모리가 low watermark 이하로 떨어지면 백그라운드 스레드(kswapd)가 페이지를 내보내기 시작해서 high watermark까지 확보해둬. 여러 페이지를 모아서 한꺼번에 디스크에 쓰면(clustering) 순차 쓰기가 되니까 효율적이고.

어떤 페이지를 내보낼지 결정하는 게 페이지 교체 정책이야. 이론적 최적은 OPT — 앞으로 가장 오래 안 쓸 페이지를 내보내는 건데, 미래를 알아야 하니까 현실에서는 구현 불가능하고 벤치마크 비교용으로만 써. FIFO는 가장 먼저 온 페이지를 내보내는데, 단순하지만 자주 쓰는 페이지와 오래된 페이지는 관계가 없잖아. 심지어 메모리를 늘렸는데 오히려 폴트가 늘어나는 Belady의 역설이 생길 수도 있어. 랜덤은 FIFO보다 나을 수도 있는데, 적어도 pathological case는 없으니까. 실전에서 가장 많이 쓰는 건 LRU(Least Recently Used) — 가장 오래 전에 쓴 페이지를 내보내는 거야. "과거의 행동이 미래를 예측한다"는 가정이고, 시간적 지역성을 활용해서 대부분의 워크로드에서 OPT에 가까운 성능을 보여줘. 근데 완벽한 LRU는 매 접근마다 타임스탬프를 기록해야 해서 비싸. 그래서 실제로는 클럭 알고리즘으로 근사해. 페이지가 원형 리스트에 있고 시계 바늘이 돌면서 reference 비트를 확인하는데, 1이면 0으로 바꾸고 넘어가고(한 번 더 기회), 0이면 내보내는 거야. 더티 페이지는 디스크에 써야 하니까 비싸고, 클린 페이지는 그냥 버리면 되니까 클린을 먼저 내보내는 게 유리하지. 단, 루핑 워크로드(메모리보다 큰 데이터를 순차 순회)에서는 LRU도 FIFO도 전부 최악이야 — 항상 방금 내보낸 걸 다시 불러와야 하거든.

실제 시스템 사례를 보면 재밌어. VAX/VMS는 512바이트라는 작은 페이지를 쓰면서 세그멘테이션+페이징 하이브리드를 택했고, 교체 정책은 세그멘트된 FIFO + 두 번째 기회 리스트야. 교체 대상 페이지를 바로 버리지 않고 글로벌 클린/더티 리스트에 넣어서 다시 필요하면 디스크 접근 없이 꺼내오는 영리한 방식이지. demand zeroing(접근할 때 0으로 채우기)이나 copy-on-write(COW) 같은 lazy 전략도 중요한데, 특히 COW는 fork() 때 부모의 페이지를 복사하지 않고 공유하다가 쓰기가 발생할 때만 복사하는 거라 fork()+exec() 패턴에서 엄청난 성능 향상을 가져와. 리눅스는 4~5단계 페이지 테이블에 huge pages(2MB, 1GB)를 조합하고, 커널 메모리는 커널 논리 주소(물리 매핑, kmalloc)와 커널 가상 주소(vmalloc)로 나눠. 페이지 캐시의 교체 정책으로는 2Q 알고리즘을 쓰는데, 처음 접근한 페이지는 비활성 리스트에, 두 번 이상 접근한 페이지는 활성 리스트에 넣어서 한 번만 접근한 페이지가 자주 쓰는 페이지를 밀어내는 걸 방지해. 메모리가 정말 부족하면 kswapd가 비활성 리스트에서 회수하고, 그래도 안 되면 OOM killer가 메모리를 가장 많이 쓰는 프로세스를 죽여.

---

정리

5장 읽고 기억할 거 세 가지:

1. 페이징 + TLB + 다단계 페이지 테이블이 현대 메모리 가상화의 표준 조합이야. TLB 히트율 99% 이상이면 페이징 오버헤드가 사라지고, 다단계 구조로 사용하지 않는 주소 범위의 테이블을 할당하지 않아서 메모리도 절약해
2. 페이지 폴트는 디스크 I/O라서 밀리초 단위로 느려. 그래서 페이지 교체 정책이 중요하고, LRU의 근사인 클럭 알고리즘이 실전 표준이야. kswapd가 백그라운드에서 미리 빈 프레임을 확보해둬
3. **COW(Copy-on-Write)**가 fork()의 성능을 극적으로 개선하고, 리눅스의 2Q 알고리즘이 파일 스캔 같은 워크로드에서 캐시 오염을 방지해. 이론만으로는 감이 안 잡히는 부분을 실제 시스템 사례가 채워줘