페이징

8장에서 본 세그먼테이션은 프로그램을 논리적인 단위로 나누었지만, 세그먼트마다 크기가 달라 외부 단편화를 피하지 못했습니다. 시간이 지나면 물리 메모리의 빈 공간이 여기저기 흩어지는 문제가 그대로 남았습니다. 이 문제를 근본적으로 푸는 방법은 메모리를 모두 같은 크기의 작은 블록으로 나누는 것입니다. 블록의 크기가 모두 같으면, 빈 블록이 어디에 있든 아무 블록이나 쓰면 되기 때문입니다. 이 방법이 페이징(paging)이며, 오늘날 거의 모든 범용 운영체제가 메모리를 관리하는 바탕입니다.

가상 메모리가 주는 것

RAM이 8GB인 컴퓨터에서 각각 4GB의 주소 공간을 쓰는 프로그램 다섯 개를 동시에 실행할 수 있을까요? 실행할 수 있는 경우가 많습니다. 프로그램이 주소 공간을 4GB 예약했다고 해서 그 4GB를 모두 동시에 물리 메모리에 올려 두어야 하는 것은 아니기 때문입니다. 실제로 지금 접근하는 부분만 물리 메모리에 있으면 됩니다.

가상 메모리(virtual memory)는 프로세스에게 물리 메모리와 상관없이 자기만의 넓은 주소 공간을 주고, 그 가운데 실제로 쓰는 부분만 물리 메모리에 올리는 방법입니다. 나머지는 필요할 때 준비합니다. 실행 파일이나 매핑한 파일의 내용이라면 파일에서 읽어 오고, 힙이나 스택처럼 파일과 연결되지 않은 익명 메모리라면 처음 쓸 때 0으로 채운 메모리를 주거나, 예전에 스왑으로 내보냈던 내용을 되살립니다. 모든 가상 페이지가 미리 디스크에 저장되어 있는 것은 아닙니다. 프로세스는 자기가 연속된 큰 메모리를 혼자 쓰는 것처럼 동작하고, 그 착각을 만들어 내는 장치가 페이징입니다.

가상 메모리가 주는 것은 다음과 같습니다. 물리 메모리보다 큰 주소 공간을 쓸 수 있습니다. 프로세스마다 주소 공간이 따로 있어 서로의 메모리를 건드리지 못합니다. 반대로 공유 라이브러리처럼 여러 프로세스가 같은 물리 페이지를 함께 쓰게 할 수도 있습니다. 그리고 페이지마다 읽기, 쓰기, 실행 권한을 따로 정할 수 있습니다.

페이지와 프레임

페이징은 가상 주소 공간을 페이지(page)라는 같은 크기의 블록으로, 물리 메모리를 프레임(frame)이라는 같은 크기의 블록으로 나눕니다. 페이지와 프레임의 크기는 같고, 페이지 하나는 프레임 하나에 놓입니다. x86과 대부분의 ARM 시스템은 4KiB(4,096바이트) 페이지를 기본으로 쓰고, x86-64는 2MiB와 1GiB 크기의 큰 페이지도 지원하며, ARM64는 기본 크기를 16KiB나 64KiB로 정할 수도 있습니다. 이 글의 계산은 모두 4KiB 페이지를 씁니다.

프로세스의 페이지들은 물리 메모리의 아무 프레임에나 놓일 수 있고, 서로 이어져 있을 필요가 없습니다. 페이지 0은 프레임 5에, 페이지 1은 프레임 100에, 페이지 2는 프레임 3에 놓여도 됩니다. 그래서 프로세스 전체를 위한 큰 연속 공간을 찾을 필요가 없고, 프레임 하나씩 따로 할당하는 한 외부 단편화가 생기지 않습니다. 다만 큰 페이지처럼 여러 프레임이 연속으로 필요한 할당에는 8장에서 본 단편화 문제가 다시 나타날 수 있습니다.

내부 단편화는 남습니다. 메모리를 페이지 단위로 주므로, 필요한 크기를 페이지 크기로 올림한 만큼 마지막 페이지에 빈 자리가 생깁니다. 72,000바이트가 필요한 영역이라면 페이지 17개(69,632바이트)로는 모자라 18번째 페이지가 필요하고, 그 페이지에서는 2,368바이트만 쓰고 1,728바이트가 남습니다. 연속된 영역 하나에서 생기는 낭비는 한 페이지보다 작지만, 따로 할당한 영역이 여럿이면 영역마다 끝부분이 남으므로 낭비의 합은 한 페이지보다 커질 수 있습니다.

페이지 테이블

어떤 페이지가 어느 프레임에 놓였는지는 페이지 테이블(page table)에 적어 둡니다. 페이지 테이블은 프로세스마다 하나씩 있으며, 페이지 번호를 인덱스로 하여 그 페이지가 놓인 프레임 번호를 찾을 수 있게 되어 있습니다. 3장에서 본 컨텍스트 스위칭 때 x86의 CR3 레지스터에 바꾸어 넣는 것이 바로 이 페이지 테이블의 위치입니다.

가상 주소를 둘로 나누기

가상 주소는 두 부분으로 나뉩니다. 상위 비트는 페이지 번호(page number)로, 페이지 테이블의 인덱스입니다. 하위 비트는 페이지 오프셋(page offset)으로, 페이지 안에서 몇 번째 바이트인지를 나타냅니다. 페이지 크기가 $2^{12}$ = 4,096바이트이므로 오프셋은 하위 12비트이고 0부터 4,095까지입니다. 32비트 주소라면 나머지 상위 20비트가 페이지 번호여서 $2^{20}$ = 1,048,576개의 페이지가 있습니다. x86-64에서 48비트 가상 주소를 쓴다면 페이지 번호는 36비트로, 페이지가 $2^{36}$, 약 687억 개입니다.

페이지 크기가 2의 거듭제곱이기 때문에, 주소를 나누는 계산은 나눗셈 없이 비트 연산으로 끝납니다. 주소를 오른쪽으로 12비트 밀면 페이지 번호가 되고, 하위 12비트만 남기면 오프셋이 됩니다. 하드웨어가 모든 메모리 접근마다 이 계산을 해야 하므로, 이렇게 단순하다는 점이 중요합니다.

페이지 테이블 항목

페이지 테이블의 각 항목(page table entry, PTE)에는 프레임 번호와 함께 여러 제어 비트가 들어 있습니다.

비트의 이름과 배치는 아키텍처마다 다릅니다. 이 글의 모델에서는 유효 비트 하나로 페이지가 물리 메모리에 있는지만 나타내지만, 실제 하드웨어는 주소를 바꿀 때 보호 비트로 권한도 함께 검사합니다.

주소를 바꾸는 과정

가상 주소 8,200을 예로 들어 보겠습니다. 페이지 테이블에서 페이지 2는 프레임 1에 놓여 있다고 합시다.

먼저 주소를 페이지 크기로 나눕니다. 8,200 = 2 × 4,096 + 8이므로 페이지 번호는 2, 오프셋은 8입니다. 페이지 2가 테이블 범위 안에 있는지 확인하고, 2번 항목을 읽어 프레임 1에 놓여 있고 유효하다는 것을 확인합니다. 마지막으로 프레임 1의 시작 주소 1 × 4,096에 같은 오프셋 8을 더해 물리 주소 4,104를 얻습니다. 바뀐 것은 페이지 번호가 프레임 번호로 바뀐 것뿐이고, 오프셋은 그대로 유지됩니다. 페이지와 프레임의 크기가 같으므로, 페이지 안의 위치가 프레임 안의 같은 위치가 되기 때문입니다.

다음 코드는 이 과정을 구현하고, 페이지의 끝과 다음 페이지의 시작, 테이블 밖의 주소까지 함께 변환해 봅니다.

PAGE_SIZE = 4096
OFFSET_BITS = 12                         # 4096 = 2의 12제곱

class PageFault(Exception):
    pass

class InvalidAddress(Exception):
    pass

page_table = [                           # 인덱스가 페이지 번호
    {"frame": 5, "valid": True},
    {"frame": 8, "valid": True},
    {"frame": 1, "valid": True},
    {"frame": None, "valid": False},     # 아직 물리 메모리에 없다
]

def translate(addr):
    page, offset = addr >> OFFSET_BITS, addr & (PAGE_SIZE - 1)
    if page >= len(page_table):
        raise InvalidAddress(f"페이지 {page}: 테이블 범위 밖")
    entry = page_table[page]
    if not entry["valid"]:
        raise PageFault(f"페이지 {page}: 메모리에 없음")
    return entry["frame"] * PAGE_SIZE + offset   # 프레임의 시작에 같은 오프셋을 더한다

for addr in (8200, 0x2FFF, 0x3000, 0x4000):
    page, offset = divmod(addr, PAGE_SIZE)
    try:
        result = f"물리 {translate(addr)}"
    except (PageFault, InvalidAddress) as error:
        result = f"{type(error).__name__} ({error})"
    print(f"논리 {addr} = 페이지 {page}, 오프셋 {offset} -> {result}")

논리 8200 = 페이지 2, 오프셋 8 -> 물리 4104
논리 12287 = 페이지 2, 오프셋 4095 -> 물리 8191
논리 12288 = 페이지 3, 오프셋 0 -> PageFault (페이지 3: 메모리에 없음)
논리 16384 = 페이지 4, 오프셋 0 -> InvalidAddress (페이지 4: 테이블 범위 밖)

0x2FFF(12,287)는 페이지 2의 마지막 바이트이므로 프레임 1의 마지막 바이트인 8,191이 됩니다. 바로 다음 주소 0x3000(12,288)은 오프셋이 0으로 돌아가고 페이지 번호가 3으로 바뀝니다. 가상 주소로는 1만큼 차이 나지만, 페이지 3은 프레임 1의 바로 다음에 있지 않으므로 물리 주소 8,192가 되는 것이 아닙니다. 가상 주소에서 이웃한 페이지가 물리 메모리에서도 이웃해 있다고 기대해서는 안 됩니다. 이 모델에서 페이지 3은 유효하지 않으므로 페이지 폴트가 나고, 페이지 4는 테이블 범위를 벗어나므로 유효한지 보기 전에 거절됩니다. 실제 시스템에서 페이지 폴트는 오류가 아니라 커널이 페이지를 준비하는 계기인데, 이 과정은 9장 3편에서 다룹니다. 이 모델은 권한 검사와 TLB를 생략했고, 예외를 던지는 것은 커널의 폴트 처리를 흉내 낸 것일 뿐입니다.

페이지 크기 고르기

페이지 크기를 어떻게 정할지에는 맞바꿈이 있습니다. 작은 페이지는 내부 단편화가 적고, 필요한 부분만 정확히 올릴 수 있으며, 권한을 세밀하게 나눌 수 있습니다. 대신 같은 크기의 메모리를 매핑하는 데 페이지 테이블 항목이 더 많이 필요합니다. 4KiB 페이지로 1GiB를 매핑하려면 항목이 262,144개 필요하지만, 2MiB 페이지로는 512개면 됩니다.

항목 수는 다음 글에서 볼 TLB와도 이어집니다. TLB는 최근의 변환 결과를 담아 두는 작은 캐시인데, 칸 수가 정해져 있으므로 페이지가 클수록 같은 칸 수로 더 넓은 메모리를 덮을 수 있습니다. 그래서 큰 메모리를 쓰는 데이터베이스나 가상 머신은 큰 페이지로 변환 비용을 줄이기도 합니다. 반면 큰 페이지는 내부 단편화가 크고, 일부만 쓰는 데이터에도 큰 페이지 전체를 물리 메모리에 올려야 합니다.

Linux의 투명한 큰 페이지(transparent huge pages, THP)는 프로그램이 따로 요청하지 않아도 조건이 맞으면 커널이 큰 페이지로 매핑해 주는 기능입니다. 최근 커널은 2MiB뿐 아니라 그보다 작은 여러 크기의 큰 페이지도 쓸 수 있습니다. 하지만 큰 페이지를 만들려고 메모리를 정리하는 비용이 작업에 따라 지연을 만들기도 하므로, 데이터베이스들은 THP를 끄고 미리 확보해 두는 명시적인 큰 페이지(HugePages)를 권하는 경우가 많습니다. 어느 쪽이 나은지는 작업과 운영체제 설정을 확인해 정해야 합니다.

주소 변환은 모든 메모리 접근마다 일어납니다. 명령어 하나를 실행하는 데도 명령어를 가져오고 데이터를 읽고 쓰는 여러 번의 메모리 접근이 필요하므로, 변환 자체가 빨라야 합니다. 그런데 페이지 테이블은 메모리에 있으니, 변환하려고 페이지 테이블을 읽는 것도 메모리 접근입니다. 이 문제를 푸는 방법이 다음 글의 주제입니다.

더 깊이: 페이지 크기를 4KiB로 못 박은 코드

x86-64의 기본 페이지는 4KiB이지만, 모든 시스템의 페이지가 4KiB인 것은 아닙니다. Android의 페이지 크기 안내에 따르면 Android 15부터 AOSP는 페이지 크기를 16KiB로 설정한 기기를 지원합니다. Google이 처음 시험한 결과로는 이런 기기가 평균적으로 메모리를 조금 더 쓰는 대신, 메모리가 부족할 때의 앱 시작 시간이 평균 3.16% 줄고 시스템 부팅 시간이 평균 8% 빨라졌습니다. 앞에서 본 페이지 크기의 맞바꿈이 실제 기기에서 나타난 예입니다.

문제는 페이지 크기를 4KiB로 가정하고 짠 코드입니다. 같은 안내서는 C와 C++ 코드에서 PAGE_SIZE 상수나 4096이라는 숫자에 기대는 부분을 없애고, 실행할 때 getpagesize()나 sysconf(_SC_PAGESIZE)로 값을 얻으라고 권합니다. 또 공유 라이브러리의 ELF 세그먼트를 16KiB 단위로 정렬해 링크해야 이런 기기에서 실행되므로, NDK로 만든 네이티브 라이브러리를 직접 또는 SDK를 통해 쓰는 앱은 다시 빌드해야 합니다. Java나 Kotlin 코드로만 이루어진 앱은 이미 16KiB 기기를 지원합니다.

정리

• 가상 메모리는 프로세스에 자기만의 넓은 주소 공간을 주고 실제로 쓰는 부분만 물리 메모리에 올립니다. 나머지는 파일에서 읽거나, 0으로 채우거나, 스왑에서 되살려 필요할 때 준비합니다.
• 페이징은 가상 주소 공간을 페이지로, 물리 메모리를 같은 크기의 프레임으로 나누고, 페이지를 아무 프레임에나 놓습니다. 외부 단편화가 사라지는 대신 마지막 페이지의 내부 단편화가 남습니다.
• 가상 주소는 페이지 번호와 오프셋으로 나뉘며, 페이지 테이블에서 페이지 번호로 프레임 번호를 찾고 같은 오프셋을 더해 물리 주소를 만듭니다. 가상 주소에서 이웃한 페이지가 물리 메모리에서 이웃한다는 보장은 없습니다.
• 페이지 테이블 항목에는 프레임 번호와 함께 유효, 보호, 참조, 변경, 캐시 속성 비트가 들어 있습니다.
• 작은 페이지는 단편화가 적고 세밀하지만 항목이 많아지고, 큰 페이지는 변환 비용을 줄이지만 단편화가 큽니다.

연습 문제

1. 세 주소 변환하기

본문의 페이지 테이블을 그대로 써서 가상 주소 0x1FFF, 0x2000, 0x4000을 변환하세요. 각 주소의 페이지 번호와 오프셋도 함께 적으세요.

2. 영역마다 생기는 끝부분 낭비

따로 할당한 두 영역의 크기가 각각 4,097바이트와 1바이트입니다. 4KiB 페이지로 각 영역을 매핑할 때 필요한 페이지 수와 끝부분 낭비의 합을 구하세요. 두 영역을 하나로 합쳐 4,098바이트로 계산하면 어떻게 다를까요?

3. 1GiB를 매핑하는 항목 수

1GiB의 메모리를 4KiB 페이지로 매핑할 때와 2MiB 페이지로 매핑할 때 필요한 페이지 테이블 항목 수를 각각 구하세요. TLB에 항목을 1,536개 담을 수 있다면, 각 경우에 TLB로 한꺼번에 덮을 수 있는 메모리는 얼마인가요?

다음 글 TLB와 페이지 테이블 최적화에서는 변환 결과를 담아 두는 TLB와, 거대한 페이지 테이블을 여러 단계로 나누어 메모리를 아끼는 방법을 살펴봅니다.