가상 메모리의 페이지 표는 “이 페이지가 지금 메모리에 있나, 있다면 어느 프레임인가, 올라온 뒤 바뀌었나”를 페이지마다 적은 표다. 문제는 크기다. 32비트 주소에 4 KB 페이지면 프로세스마다 항목이 백만 개쯤 된다. 그래서 표를 여러 단계로 나눠 필요한 부분만 메모리에 두거나(다단계 페이지 표), 프로세스가 아니라 실제 프레임 기준으로 표를 하나만 두는(역 페이지 표) 방법을 쓴다. 단계가 늘면 주소 하나를 바꾸는 데 메모리를 여러 번 읽어야 한다.
예시로 보기
32비트 주소, 페이지 4 KB, 페이지 표 항목 4바이트라고 하자1.
| 계산 | 값 |
|---|---|
| 프로세스의 페이지 수 | \(2^{32} / 2^{12} = 2^{20}\) (약 100만 개) |
| 한 단계 페이지 표 크기 | \(2^{20} \times 4\) B = 4 MB |
| 4 MB 표를 담는 페이지 수 | 4 MB / 4 KB = 1024장 |
| 그 1024장을 가리키는 루트 표 | 1024 × 4 B = 4 KB (한 페이지) |
프로세스마다 4 MB 표를 늘 주기억장치에 둘 수는 없다. 2단계 구조는 4 KB짜리 루트 표만 늘 메모리에 두고, 4 MB 사용자 페이지 표는 필요한 페이지만 올린다.
정확히 말하면
페이지 표 항목
프로세스마다 페이지 표가 있다. 각 항목에는 그 페이지가 든 프레임 번호와 함께 비트 두 개가 더 있다.
| 칸 | 뜻 |
|---|---|
| P (존재) | 이 페이지가 지금 주기억장치에 있는가 |
| M (변경) | 마지막으로 올라온 뒤 내용이 바뀌었는가. 바뀌었으면 내보낼 때 디스크에 써야 한다 |
| 그 밖의 제어 비트 | 보호, 공유 등 |
| 프레임 번호 | 페이지가 있는 프레임 |
주소 변환은 페이징과 같다. 가상 주소의 페이지 번호로 표를 찾아 프레임 번호를 얻고 오프셋을 붙인다. 프로세스마다 페이지 표의 시작 주소는 레지스터에 둔다. P가 0이면 페이지 부재다.
다단계 페이지 표
페이지 표 자체도 가상 메모리에 저장한다. 프로세스가 실행될 때 페이지 표의 일부만 주기억장치에 있다. 2단계 표에서 32비트 주소는 이렇게 나뉜다.
| 루트 색인 10비트 | 사용자 표 색인 10비트 | 오프셋 12비트 |
- 루트 색인으로 4 KB 루트 표에서 항목을 찾는다. 이것이 사용자 페이지 표의 몇 번째 페이지인지 알려 준다. 그 페이지가 메모리에 없으면 페이지 부재다.
- 그 페이지 안에서 두 번째 색인으로 항목을 찾아 프레임 번호를 얻는다.
- 프레임 번호 뒤에 오프셋을 붙인다.
flowchart LR
VA["가상 주소: 루트 색인, 두 번째 색인, 오프셋"] -->|"루트 색인"| RT["루트 페이지 표 4 KB, 늘 메모리에 있음"]
RT -->|"사용자 페이지 표의 몇 번째 페이지인가"| UP["사용자 페이지 표의 한 페이지 4 KB"]
VA -->|"두 번째 색인"| UP
UP -->|"프레임 번호"| PA["실제 주소: 프레임 번호와 오프셋"]
VA -->|"오프셋은 그대로"| PA
가상 주소의 세 부분이 각각 다른 곳에 쓰인다. 앞 10비트는 루트 표에서, 가운데 10비트는 사용자 페이지 표의 한 페이지에서 쓰이고, 오프셋은 실제 주소까지 그대로 간다2.
예: 가상 주소 0x00403ABC는 루트 색인 1, 두 번째 색인 3, 오프셋 0xABC다.
역 페이지 표
지금까지의 페이지 표는 크기가 가상 주소 공간에 비례한다. 주소가 64비트가 되면 감당할 수 없다. 대안이 역 페이지 표다.
- 실제 메모리의 프레임마다 항목이 하나다. 그래서 프로세스 수와 상관없이 실제 메모리의 일정 비율만 표에 쓴다.
- 가상 주소의 페이지 번호를 해시 함수로 해시값으로 바꾸고, 그 값이 역 페이지 표의 항목을 가리킨다. 해시가 겹치면 사슬로 잇는다.
- 항목에는 페이지 번호, 이 페이지를 가진 프로세스 ID, 제어 비트(유효, 참조 등), 사슬의 다음 항목 번호가 있다.
flowchart TD
P["가상 주소의 페이지 번호"] --> H["해시 함수"]
H --> E["역 페이지 표의 항목"]
E --> Q{"항목의 페이지 번호와 프로세스 ID가 맞나?"}
Q -->|"예"| F["이 항목의 프레임에 페이지가 있다"]
Q -->|"아니오"| N{"사슬에 다음 항목이 있나?"}
N -->|"있다"| E
N -->|"없다"| PF["페이지 부재"]
해시값은 출발점일 뿐이다. 그 칸이 다른 페이지 것이면 사슬을 따라 다음 칸으로 옮겨 가며 같은 비교를 되풀이한다2.
- PowerPC, UltraSPARC, IA-64가 쓴다.
| 다단계 페이지 표 | 역 페이지 표 | |
|---|---|---|
| 크기의 기준 | 가상 주소 공간 (프로세스마다) | 실제 메모리 (시스템 전체에 하나) |
| 찾는 법 | 색인으로 바로 | 해시 후 사슬 따라가기 |
| 공유 페이지 | 여러 표가 같은 프레임을 가리키면 됨 | 프레임당 항목이 하나라 다루기 어렵다1 |
활용
- 리눅스는 3단계(페이지 디렉터리, 페이지 중간 디렉터리, 페이지 표)를 쓰고, 표 하나가 한 페이지 크기다. 페이지 디렉터리는 프로세스마다 하나이고 늘 주기억장치에 있다.
- 표의 단계가 늘면 주소 하나에 메모리를 여러 번 읽어야 한다. 이 비용을 줄이는 것이 TLB다.
연결
확인 문제
C1 가상 메모리의 페이지 표 항목에 프레임 번호 말고 꼭 필요한 비트 두 개와 그 뜻을 쓰라.
답: P(존재) 비트: 페이지가 주기억장치에 있는가. M(변경) 비트: 올라온 뒤 내용이 바뀌었는가.
C2 M 비트가 없으면 운영체제는 무엇을 해야 하는가? 그것이 왜 손해인가?
답: 페이지를 내보낼 때마다 디스크에 다시 써야 한다. 바뀌지 않은 페이지는 디스크에 이미 같은 내용이 있으므로 쓸 필요가 없는데, M 비트가 없으면 구별할 수 없어 쓸데없는 디스크 쓰기가 늘어난다.
C3 64비트 주소, 페이지 4 KB, 항목 8바이트로 한 단계 페이지 표를 만들면 프로세스마다 표 크기는? 이것이 역 페이지 표를 쓰는 이유와 어떻게 이어지는가?
답: 페이지 수 \(2^{64}/2^{12} = 2^{52}\), 표 크기 \(2^{52} \times 8 = 2^{55}\) 바이트 = 32 PB. 가상 주소 공간에 비례하는 표는 64비트에서 감당할 수 없다. 역 페이지 표는 실제 메모리 크기에 비례하므로 주소 공간이 커져도 표 크기가 그대로다.