#13 페이징 (Paging)

프로세스를 16바이트씩 잘라서 아무데나 흩뿌린다고? — 페이징

지난 글에서 세그멘테이션이 외부 단편화라는 숙제를 남겼다고 했잖아. 그 숙제를 푸는 방법이 페이징이라고 했던 것까지 기억해? 아이디어는 단순해 — 세그먼트처럼 가변 크기로 나누지 말고, 아예 처음부터 똑같은 크기로 잘라버리자는 거야.

---

페이징이 뭐야

Paging은 프로세스의 가상 주소 공간을 고정 크기(fixed-size)로 잘라서 메모리에 할당하는 방식이야. 이 고정 크기 단위를 가상 주소 공간에서는 page라고 부르고, 이 page가 실제 메모리에 할당되는 자리를 page frame이라고 불러. 정리하면, 가상 쪽에서는 page, 물리 쪽에서는 frame — 이름만 다르지 크기는 완전히 똑같아.

---

페이징의 장점

유연성(Flexibility)

주소 공간을 추상화하는 데 훨씬 유연해. 세그멘테이션은 Code, Heap, Stack이 각각 어떻게 자랄지 미리 가정하고 설계해야 했는데, 페이징은 힙이랑 스택이 얼마나 커질지 미리 고민할 필요가 없어. 그냥 필요한 만큼 page를 더 배정하면 끝이야.

 

단순함(Simplicity)

여유 공간 관리가 쉬워져. page랑 page frame이 항상 같은 크기니까, 빈 프레임 목록만 관리하면 할당이 훨씬 단순해져. 세그멘테이션처럼 "20KB짜리 연속 공간이 있나?" 같은 복잡한 고민을 할 필요가 없어.

---

작은 예시로 감 잡기

128바이트짜리 물리 메모리를 16바이트짜리 page frame 8개로 나누고, 64바이트짜리 주소 공간을 16바이트짜리 page 4개로 나눈다고 해보자.

4개 page가 순서대로 배치되는 게 아니라 물리 메모리 여기저기에 완전히 흩어져서 자리 잡는 게 보이지? 이걸 표로 정리하면 이래.

Virtual Page	Page Frame
0	3
1	7
2	5
3	2

이 표가 바로 Page Table이야. 가상 주소 공간의 각 page가 실제 메모리 어디에 있는지 기록해두는 자료구조지. 프로세스마다 하나씩 따로 갖고 있고(per-process structure), OS가 관리하는 메모리 영역에 저장돼.

 

 

 

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

Q. Paging이 왜 나오게 됐고, 개념을 설명해 주세요.

세그멘테이션은 세그먼트 크기가 프로세스마다 제각각이라 물리 메모리에 자잘한 빈 공간이 흩어지는 외부 단편화 문제가 있었습니다. 페이징은 이 문제를 풀려고 가상 주소 공간을 고정 크기의 page 단위로 잘라서, 물리 메모리의 같은 크기 단위인 page frame에 할당하는 방식입니다. 크기가 항상 똑같기 때문에 빈 프레임 목록만 관리하면 되고, 이 덕분에 외부 단편화가 사라집니다.

---

가상 주소는 어떻게 물리 주소가 될까

가상 주소는 두 부분으로 나뉘어. VPN(Virtual Page Number)은 어느 page인지 가리키고, offset은 그 page 안에서 몇 번째 바이트인지 가리켜. 64바이트 주소 공간에 16바이트짜리 page라면, 전체 6비트 중 상위 2비트가 VPN(4개 page를 구분), 나머지 하위 4비트가 offset(page 안 16바이트를 구분)이 돼.

가상 주소 21을 예로 들어보자. 21을 2진수로 쓰면 010101이야.

자 정리해보자.

1. VPN(01, 10진수 1)으로 Page Table을 찾아가서 PFN(7)을 얻어
2. PFN에 offset(5)을 그대로 이어붙이면 물리 주소가 나와
3. 7번 frame은 16바이트 단위니까 7×16=112, 여기에 offset 5를 더하면 117이 돼

가상 주소 21이 물리 주소 117로 바뀐 거야. 이게 페이징 주소 변환의 전부야.

여기서 하나 실감 나는 예를 들면, 실행 파일의 code 영역이랑 배열(array) 하나가 있다고 해보자. code는 가상 주소 공간 앞쪽 VPN 0에 있고, 배열은 훨씬 뒤쪽 VPN 39~42에 걸쳐 있다고 해도, 각 page는 완전히 독립적으로 물리 메모리에 자리를 잡아.

code랑 array가 가상 주소 공간에서는 한참 떨어져 있지만, 물리 메모리에는 각자 필요한 만큼만 프레임을 배정받아. 그 사이의 빈 공간은 아예 물리 메모리에 자리를 안 잡으니까, 세그멘테이션 때처럼 낭비될 일이 없어. array 안에서는 PFN 7~10이 우연히 연속으로 배정됐는데, 이것도 어디까지나 우연이고 페이지 테이블이 각 page마다 따로 기록해두기 때문에 실제로 연속일 필요는 없어.

---

Page Table은 얼마나 커질까

여기서 문제가 하나 생겨. Page Table은 세그멘테이션에서 쓰던 세그먼트 테이블이나 base·bound 레지스터보다 필요한 크기가 훨씬 커질 수 있어.

4KB짜리 page를 쓰는 32비트 가상 주소 공간을 예로 들어보자.

• 전체 주소 공간 크기가 32비트이니까 2^32
• page 크기가 4KB니까 2^12
• VPN 비트 수 = 전체 page 개수를 표현하는 데 필요한 비트 = 2^32 / 2^12 = 2^20, 즉 20비트
• offset 비트 수 = 전체 32비트 중 VPN이 쓰고 남은 비트 = 32 − 20 = 12비트

page table entry(PTE) 하나가 4바이트라고 하면, 전체 page table 크기는 2^20개 entry × 4바이트 = 4MB가 돼. 프로세스 하나당 4MB. 이게 프로세스 수만큼 곱해진다고 생각하면 절대 작은 숫자가 아니야. 각 프로세스의 page table은 OS가 관리하는 가상 메모리 영역에 저장돼.

---

Page Table 안에는 뭐가 들어있을까?

Page Table은 가상 주소를 실제 메모리 주소로 매핑할 때 쓰는 자료구조야. 가장 단순한 구현은 1차원 배열이야. VPN으로 이 배열을 인덱싱해서 해당하는 PTE(Page Table Entry)를 조회하는 거지. PTE는 그 page에 대한 온갖 정보를 담고 있는 한 칸이라고 생각하면 돼.

x86 아키텍처의 PTE에는 이런 정보들이 들어있어.

필드	설명
Present	이 page가 지금 실제 메모리에 있는지, 디스크로 밀려났는지 나타내는 비트
R/W (Protection)	page에 쓰기가 허용되는지 결정하는 비트
U/S	User 모드 프로세스가 이 page에 접근할 수 있는지 나타내는 비트
A (Accessed)	최근에 참조된 적이 있는지 (페이지 교체 정책에서 씀)
D (Dirty)	page 내용이 수정된 적이 있는지
PWT, PCD, PAT	이 page에 대해 하드웨어 캐시(메모리 캐시)가 어떻게 동작할지 결정하는 비트
G (Global)	TLB에서 이 page 엔트리를 Context Switch 때도 유지할지 결정하는 비트
나머지	Page Frame Number, 즉 PFN(= Page Base Address)

G 비트는 PWT·PCD·PAT랑 묶어서 "캐싱 관련 비트"로 보기 쉬운데, 엄밀히는 성격이 좀 달라. PWT·PCD·PAT는 이 page의 데이터를 하드웨어 캐시에 어떻게 담을지 결정하는 거고, G는 이 page의 주소 변환 결과를 TLB에서 얼마나 오래 유지할지에 관여해. TLB는 다음다음 글에서 자세히 다룰 거야.

---

근데 이 방식, 너무 느려

 

가상 주소를 물리 주소로 바꾸는 과정을 정리하면 이래.

1. 가상 주소에서 VPN과 offset을 뽑아내고, VPN으로 해당 프로세스의 Page Table에서 PTE를 가져와
2. PTE에서 PFN을 뽑아내
3. PFN이랑 offset을 합쳐서 물리 주소를 얻어

문제는 이 과정 자체가 컴퓨터 성능을 깎아먹는다는 거야. 원하는 PTE 위치를 찾으려면 Page Table의 시작 위치가 필요한데, 결국 메모리에 있는 데이터 하나를 읽으려면 그 전에 Page Table을 읽는 메모리 접근이 한 번 더 필요해. 모든 메모리 참조마다 이 추가 참조가 따라붙는 거야.

 

 

 

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

Q. Paging을 이용한 주소 변환 과정을 Page table, PTE, PFN 개념을 언급해서 설명해 주세요.

가상 주소는 VPN과 offset으로 나뉩니다. VPN으로 해당 프로세스의 Page Table을 인덱싱해서 그 page에 대한 정보인 PTE를 가져오고, PTE 안에 들어있는 PFN(Page Frame Number)을 꺼냅니다. 이 PFN에 원래 가상 주소의 offset을 그대로 이어붙이면 물리 주소가 완성됩니다. 다만 이 과정에서 Page Table 자체도 메모리에 있기 때문에, 모든 메모리 접근마다 실제 데이터를 읽기 전에 Page Table을 읽는 메모리 접근이 한 번 더 발생한다는 게 단점입니다.

Q. Paging의 장점과 단점을 설명해 주세요.

장점은 고정 크기 단위로 메모리를 관리해서 세그멘테이션의 외부 단편화 문제가 사라지고, 힙·스택 크기를 미리 고민할 필요 없이 유연하게 주소 공간을 쓸 수 있다는 겁니다. 단점은 두 가지인데, 하나는 Page Table 자체가 커질 수 있다는 것(예: 32비트 주소 공간에 4KB page라면 프로세스당 4MB), 다른 하나는 모든 메모리 접근마다 Page Table을 조회하는 추가 메모리 참조가 필요해서 성능이 떨어진다는 겁니다.

Q. Paging을 배열과 연관지어 설명해 주세요. << 실제 받은 질문

페이징은 논리 메모리를 고정 크기의 페이지로 나누고, 이를 물리 메모리의 프레임에 매핑하는 방식인데, 이 매핑 정보를 저장하는 페이지 테이블 자체가 배열 구조로 되어 있습니다.

배열이 인덱스로 원소에 O(1)로 접근하듯이, 페이지 테이블도 페이지 번호를 인덱스로 사용해서 해당하는 프레임 번호를 O(1)에 조회합니다. 그리고 주소 변환 방식도 배열의 base address + index와 동일하게, 프레임 번호 + 오프셋으로 물리 주소를 계산합니다.

이게 가능한 이유는 페이지 크기가 고정되어 있기 때문인데, 배열의 원소 크기가 균일해서 인덱스 계산이 단순한 것과 같은 원리입니다.

---

정리하면, 페이징은 세그멘테이션의 외부 단편화 문제를 고정 크기라는 단순한 아이디어로 해결하고 유연성까지 챙겼어. 근데 그 대가로 두 가지 새 문제가 생겼어. 메모리 접근이 잦아져서 성능이 떨어지는 것, 그리고 그 접근 하나하나가 다 추가 메모리 낭비로 이어진다는 것. 이 두 문제를 보완하려고 나온 게 바로 TLB(Translation Lookaside Buffer)야.

 

페이징은 "크기를 고정해버리면 관리가 단순해진다"는 트레이드오프고, 그 대가로 얻은 성능 문제(매번 추가 메모리 참조)는 결국 캐싱이라는 익숙한 해법으로 풀게 돼. 다음 글에서 TLB가 어떻게 이 추가 메모리 참조를 없애주는지 이어서 보자.