#16 Paging: Smaller Table

Page Table이 4MB라고? 이걸 어떻게 줄여 — Smaller Table

지난 글에서 TLB가 관리할 수 있는 page 수보다 프로세스가 훨씬 많은 page를 요구하는 상황이 있다고 했잖아. 이럴 때 문제는 TLB만이 아니야 — Page Table 자체가 너무 커져서 메모리를 잡아먹는 문제가 따로 있어. 이걸 줄이는 방법들을 하나씩 보자.

---

문제부터: Page Table이 왜 이렇게 커

TLB가 감당할 수 있는 것보다 훨씬 많은 page를 요구하는 프로세스는 흔해. 이런 프로세스의 Page Table 크기를 실제로 계산해보자.

4KB(2^12) 크기의 page랑 4바이트 크기의 Page Table Entry를 쓰는 32비트 가상 주소 공간이 있다고 하면:

 

Page Table 크기 = (가상 주소 공간 크기 / page 크기) × entry 크기
                = (2^32 / 2^12) × 2^2
                = 2^20 × 4바이트
                = 4MB

프로세스 하나당 4MB짜리 Page Table이 필요하다는 뜻이야. 프로세스가 여러 개 뜨면 이게 그대로 곱해지니까, 순식간에 만만치 않은 메모리를 잡아먹어. 이 크기를 줄이는 방법을 세 가지로 나눠서 볼게.

---

방법 1: Page를 크게 만들기

가장 단순한 접근은 page 크기 자체를 키우는 거야. page가 커지면 필요한 page 개수가 줄고, 그만큼 Page Table도 작아지니까.

같은 32비트 주소 공간에 page 크기만 16KB로 늘려보면 어떻게 될까.

Page table size = (2^32 / 2^14) × 2^2 = 1MByte

4MB에서 1MB로 확 줄었어. 근데 여기엔 대가가 있어. page 하나가 크다는 건, 아주 조금만 필요해도 page 하나를 통째로 내줘야 한다는 뜻이야. 이렇게 남아서 버려지는 공간을 내부 단편화라고 불러 — 예를 들어 10KB짜리 메모리가 할당됐는데 실제로 7KB만 쓴다면, 남는 3KB가 그대로 낭비되는 거야.

page가 커질수록 이 낭비도 같이 커지고, page 개수 자체가 줄어드니까 물리 메모리도 더 성기게, 더 빨리 소모돼. 그러니까 page 크기를 키우는 건 완전한 해결책은 아니야.

---

근데 진짜 문제는 따로 있어

 

1KB짜리 page랑 16KB짜리 가상 주소 공간을 생각해보자. 전체 16개 page 중에서 실제로 code 영역 1개, heap 영역 1개, stack 영역 2개 — 딱 4개뿐이야. (여기서 헷갈리기 쉬운 표현인데, page table이 4개 있는 게 아니라, 하나의 page table 안에서 유효한 항목이 4개라는 뜻이야.) 나머지 12개 자리는 Page Table 안에서 그냥 invalid 상태로 비어있는 거야.

 

문제가 뭐냐면, Linear Page Table은 이 안 쓰는 12개 자리도 똑같이 메모리 공간을 차지하고 있다는 거야. 실제로 쓰는 건 4개뿐인데, 테이블 전체 크기는 16개 자리만큼 미리 잡아둬야 하니까. 이게 바로 앞에서 계산한 4MB 안에 숨어있는 진짜 낭비야 — 실제로 쓰이는 주소는 얼마 안 되는데, 테이블은 전체 주소 공간 크기만큼 미리 통째로 잡혀있는 거지.

---

방법 2: Paging + Segmentation 섞기

이 낭비를 줄이는 또 다른 방법은 Paging이랑 Segmentation을 같이 쓰는 거야. 프로세스마다 Code, Heap, Stack 각각을 위한 Page Table을 따로 두는 거지 — 그러니까 프로세스 하나당 총 3개의 Page Table을 갖게 돼.

각 세그먼트의 base 레지스터는 그 세그먼트의 Page Table이 물리 메모리 어디 있는지를 가리키고, bound 레지스터는 그 Page Table이 어디서 끝나는지를 나타내. 세그먼트가 실제로 쓰는 만큼만 Table을 만드니까, 안 쓰는 칸을 통째로 갖고 있을 필요가 없어져.

가상 주소는 이제 세그먼트 번호(SN) + VPN + offset으로 나뉘고, 변환 공식은 이렇게 돼.

SN  = (VirtualAddress & SEG_MASK) >> SN_SHIFT
VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT
AddressOfPTE = Base[SN] + (VPN × sizeof(PTE))

TLB miss가 나도 문제없어. 하드웨어가 세그먼트 비트로 어느 base·bound 쌍을 쓸지 바로 알 수 있으니까, 그대로 주소 변환을 진행하면 돼.

기존 방식이랑 다른 점은, bound 레지스터가 그 세그먼트 Table의 끝을 알려주기 때문에 안 쓰는 칸까지 미리 만들어둘 필요가 없다는 거야. 이 덕분에 메모리 낭비가 줄어.

 

근데 이것도 완전한 해법은 아니야. 만약 크긴 한데 듬성듬성 쓰는 Heap이 있다면, 그 세그먼트의 Table 자체는 여전히 크고 그 안에 낭비되는 칸도 많아. 게다가 세그먼트마다 크기가 다른 Table을 물리 메모리에 흩어서 배치하다 보니, 이번엔 외부 단편화 문제가 다시 고개를 들어. 세그멘테이션에서 이미 한 번 봤던 그 문제가 그대로 돌아온 셈이야.

---

방법 3: Multi-level Page Table

이번엔 안 쓰는 공간을 아예 메모리에서 통째로 빼버리는 방법이야. 실제 OS들이 쓰는 방식이고, 꽤 효과적이야.

아이디어는 이래. 선형(linear) Page Table을 page 크기 단위로 잘게 잘라. 그리고 어떤 조각(chunk) 안에 유효한 entry가 하나도 없다면, 그 조각 자체를 아예 할당하지 않아. 어떤 조각이 할당됐고 어떤 조각이 비어있는지는 Page Directory라는 새 구조가 추적해.Linear 방식이랑 Multi-level 방식을 나란히 보면:

Page Directory는 조각(page)마다 하나씩, Page Directory Entry(PDE)로 구성돼. PDE는 valid bit이랑 PFN을 갖고 있어.

• Invalid: 이 조각 안에 유효한 entry가 단 하나도 없다는 뜻 → 이 조각 자체가 물리 메모리에 할당 안 됨
• Valid: 이 조각 안에 유효한 entry가 적어도 하나는 있다는 뜻 → PFN이 그 조각의 실제 위치를 가리켜

숫자로 감을 잡아보자. 선형 Table이 16개 entry(4개씩 4조각)로 이뤄져 있고, 그중 실제로 유효한 건 6개뿐이라고 해보자 — 첫 조각에 3개, 마지막 조각에 2개, 나머지 두 조각은 완전히 비어있어. 선형 방식이면 이 16칸을 전부 물리 메모리에 올려둬야 해. 근데 멀티레벨 방식이면, 비어있는 두 조각은 Page Directory에서 그냥 invalid로 표시하고 아예 할당을 안 해버려. 결과적으로 실제 물리 메모리에 올라가는 건 유효한 entry가 있는 딱 2개 조각뿐이야. 4개 조각이 필요했던 걸 2개로 줄인 거지.

---

장점과 단점

👍 장점

• 실제로 쓰이는 주소 공간 크기에 딱 비례해서 Page Table 공간만 할당해 — 안 쓰는 부분은 아예 존재하지 않아
• Page Table을 새로 할당하거나 늘려야 할 때, OS는 그냥 다음 빈 page 하나를 가져다 쓰면 돼. Page Table도 이제 page 크기 단위 조각이니까, 일반적인 free page 관리 방식을 그대로 재사용할 수 있는 거지

👎 단점

• TLB miss가 나면, 올바른 변환 정보를 얻기 위해 메모리에서 2번의 로드가 필요해. 첫 번째는 Page Directory에 접근해서 어느 조각이 유효한지 확인하는 로드, 두 번째는 그 조각(진짜 Page Table) 안에서 PTE를 가져오는 로드야. 이걸 Time-space trade-off라고 불러 — Page Table 크기는 줄었지만(공간 이득), TLB miss가 났을 때 걸리는 시간은 늘어난 거야(시간 손해)
• Linear 방식보다 구조 자체가 복잡해져서(Increased complexity), 구현이랑 관리가 더 까다로워져

 

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. Page Table 크기를 줄이는 방법 중 2가지를 장단점과 함께 설명해 주세요.

첫 번째는 Page 크기를 키우는 방법입니다. Page가 커지면 필요한 page 개수가 줄어서 Page Table 크기도 작아지지만, page 하나를 통째로 할당해야 해서 내부 단편화가 커지고 물리 메모리가 더 빨리 소모될 수 있습니다. 두 번째는 Paging과 Segmentation을 함께 쓰는 하이브리드 방식입니다. 세그먼트마다 별도의 Page Table을 두고 base·bound 레지스터로 필요한 만큼만 할당해서 낭비를 줄이지만, 사용 빈도는 낮은데 크기만 큰 세그먼트가 있으면 여전히 낭비가 생기고 외부 단편화 문제도 다시 나타납니다.

Q. Multi-level Page Table에 대해 Page Directory를 언급해서 설명해 주세요.

Linear Page Table을 page 크기 단위로 잘게 잘라서, 그 조각 안에 유효한 entry가 하나도 없으면 그 조각 자체를 아예 메모리에 할당하지 않는 방식입니다. 어느 조각이 실제로 할당됐는지 추적하기 위해 Page Directory라는 구조를 씁니다. Page Directory는 조각마다 하나씩 PDE(Page Directory Entry)를 가지고 있고, PDE는 valid bit과 PFN으로 구성됩니다. valid면 이 PDE가 가리키는 조각에 최소 하나 이상의 유효한 entry가 있다는 뜻이고, invalid면 이 조각 자체가 할당되지 않았다는 뜻입니다.

Q. Multi-level Page Table의 장점과 단점은 무엇인가요?

장점은 실제로 사용 중인 주소 공간 크기에 비례해서만 Page Table 공간을 할당하기 때문에 메모리를 크게 절약할 수 있고, Page Table 확장도 일반적인 free page 할당으로 처리할 수 있어 단순해진다는 겁니다. 단점은 TLB miss가 났을 때 Page Directory 접근과 실제 PTE 접근, 이렇게 메모리 로드가 두 번 필요해서 시간이 더 걸린다는 겁니다(Time-space trade-off). 구조 자체도 Linear 방식보다 복잡해집니다.

---

지금까지 다룬 세 가지 방법 다 결국 같은 질문에 답하는 거였어. "안 쓰는 주소 공간까지 Page Table이 미리 다 잡아둘 필요가 있을까?" Page를 키우는 방법도, 세그먼트로 쪼개는 방법도 이 낭비를 줄이려는 시도였고, Multi-level Page Table이 가장 근본적으로 "안 쓰는 부분은 아예 안 만든다"는 답을 낸 거야.

Page Table을 줄이는 모든 방법은 결국 시간과 공간을 맞바꾸는 거래야. Page Directory 한 단계를 추가해서 공간은 아꼈지만, 그만큼 TLB miss 때 메모리 접근이 한 번 더 늘었어. 지금까지는 이 Page Table이 항상 메모리에 있다고 가정하고 얘기해왔는데, 다음 글에서 다룰 가상 메모리와 요구 페이징에서는 이 가정 자체가 깨져 — Page Table도, 실제 데이터도 물리 메모리보다 큰 주소 공간을 어떻게 다뤄야 하는지가 그 다음 이야기야.