가상 메모리와 페이징 2

가상 메모리와 페이징에서 본 주소 변환을 빠르고 가볍게 만드는 방법을 이어서 다룬다. 페이징(paging)에서는 프로세스(process)마다 있는 페이지 테이블(page table)이 가상 주소(virtual address)를 같은 크기로 나눈 조각인 페이지(page)의 번호를, 물리 메모리를 같은 크기로 나눈 칸인 프레임(frame)의 번호로 바꿔 준다. 이 표는 메모리에 있어서 매번 읽으면 느리고, 통째로 만들어 두면 크다. 변환 결과를 기억해 두는 방법과 표를 여러 단계로 쪼개는 방법을 본 뒤, 주소 공간(address space)을 크기가 다른 논리 단위로 나누는 방식과 비교한다.

TLB: 변환 결과를 기억하는 캐시

페이지 테이블은 메모리에 있다. 그대로라면 메모리 한 번을 읽으려 해도 페이지 테이블을 한 번 더 읽어야 해서 접근이 두 배로 느려진다. 그래서 CPU는 최근 변환 결과를 담아 두는 작은 하드웨어 캐시(cache)인 TLB(Translation Lookaside Buffer, 변환 색인 버퍼)를 둔다.

다이어그램 로딩…

TLB에서 찾으면 곧바로 변환이 끝나고, 못 찾는 TLB 미스(TLB miss)면 페이지 테이블을 읽어 결과를 TLB에 채운다. x86 같은 많은 CPU는 이 조회를 하드웨어가 직접 한다. 교육용·임베디드 기기에 많이 쓰인 MIPS 계열처럼, TLB 미스가 나면 예외(exception)를 일으켜 커널(kernel) 코드가 대신 처리하게 하는 CPU도 있다. 프로그램은 가까운 주소를 반복해 쓰는 경향인 지역성(locality)이 강하다. 그래서 TLB가 작아도 대부분의 접근이 TLB에서 끝나 적중률(hit ratio)이 높다.

TLB의 내용은 프로세스마다 다르다. 그래서 문맥 교환(context switch)으로 다른 프로세스로 바뀌면 TLB를 비우거나, 항목마다 어느 주소 공간 것인지 표시하는 ASID(Address Space Identifier, 주소 공간 식별자)로 구분해야 한다. TLB를 비우면 전환 직후 한동안 미스가 몰려 느려진다. 프로세스 사이 전환이 비싼 이유 중 하나가 이것이다.

다단계 페이지 테이블

32비트 주소 공간에 4KB 페이지를 쓰면 페이지는 약 100만 개(2의 20제곱)다. 페이지 테이블의 한 칸인 PTE(Page Table Entry, 페이지 테이블 항목) 하나가 4바이트면 페이지 테이블 하나가 4MB이고, 프로세스 100개면 페이지 테이블만 400MB가 된다. 실제로는 대부분의 주소를 쓰지도 않는데 표를 전부 만들어 두는 것은 낭비다.

다단계 페이지 테이블(multi-level page table)은 페이지 테이블 자체를 페이지 크기로 쪼개고, 그 조각들의 위치를 담는 상위 표를 하나 더 둔다. 주소를 변환할 때는 페이지 번호를 앞부분과 뒷부분으로 나눠, 앞부분으로 상위 표에서 하위 조각의 위치를 찾고 뒷부분으로 그 조각 안에서 프레임 번호를 찾는다. 통째로 비어 있는 구간은 하위 조각을 아예 만들지 않으므로 메모리를 크게 아낀다. 대신 TLB 미스가 나면 단계 수만큼 메모리를 더 읽어야 한다. 64비트 x86-64는 보통 4단계 표를 쓰고, 더 넓은 주소 공간이 필요한 CPU를 위해 5단계도 지원한다.

세그멘테이션과의 비교

세그멘테이션(segmentation)은 주소 공간을 코드·힙(heap)·스택(stack)처럼 의미 있는 단위인 세그먼트(segment)로 나누고, 세그먼트마다 시작 위치와 길이를 따로 기록하는 방식이다. 세그먼트는 크기가 제각각이라 논리적으로 자연스럽다. 또 코드 세그먼트는 읽기·실행만, 데이터 세그먼트는 쓰기도 허용하는 것처럼 단위마다 접근 권한을 따로 정하기 쉽다. 하지만 크기가 제각각인 덩어리를 물리 메모리에 연속으로 올려야 하므로, 빈 공간을 합치면 충분한데 연속된 덩어리가 없어 못 쓰는 외부 단편화(external fragmentation)가 다시 생긴다. 페이징은 이 문제가 없는 대신, 마지막 페이지가 꽉 차지 않아 남는 내부 단편화(internal fragmentation)가 조금 생긴다.

기준	페이징	세그멘테이션
나누는 단위	같은 크기의 페이지	크기가 다른 논리 단위
외부 단편화	없음	생김
내부 단편화	마지막 페이지에 조금	거의 없음
변환 정보	페이지 테이블(프레임 번호)	세그먼트 테이블(시작 위치·길이)

주소 공간을 먼저 세그먼트로 나누고 각 세그먼트를 다시 페이지 단위로 나눠 올리는 페이지드 세그멘테이션(paged segmentation)도 있지만, 오늘날 주요 운영체제는 사실상 페이징 중심으로 가상 메모리(virtual memory)를 구현한다.

페이지 테이블을 읽었는데 그 페이지가 물리 메모리에 없어 커널이 끼어드는 페이지 폴트(page fault)의 처리는 요구 페이징과 페이지 교체에서 다룬다.

면접 포인트

• "TLB가 왜 필요한가요?" → 페이지 테이블도 메모리에 있어 접근이 두 배가 되기 때문. 최근 변환 결과를 캐시한다.
• "TLB 미스가 나면?" → 페이지 테이블을 읽어 결과를 TLB에 채운다(x86은 하드웨어, MIPS는 커널). 페이지가 메모리에 없으면 페이지 폴트.
• "문맥 교환과 TLB의 관계는?" → TLB 내용은 프로세스마다 달라 비우거나 ASID로 구분한다. 비우면 전환 직후 미스가 몰린다.
• "페이지 테이블이 너무 크면?" → 다단계 페이지 테이블로 비어 있는 구간의 하위 표를 만들지 않는다. 대신 TLB 미스 때 단계 수만큼 더 읽는다.
• "페이징과 세그멘테이션의 차이는?" → 같은 크기 vs 논리 단위. 페이징은 외부 단편화가 없고 내부 단편화가 조금 생긴다. 세그멘테이션은 그 반대.