이 글은 건국대학교 2024년 1학기 운영체제 수업과 『Operating Systems: Three Easy Pieces』 를 참고하여 작성되었습니다.

『Operating Systems: Three Easy Pieces』
18장. Paging: Introduction

Space Management

segmentation

이전 게시물에서 다룬 segmentation 방법은 각 segment(코드, 힙, 스택)들 각각이 불연속적이고 가변적인 물리 메모리 영역을 할당받습니다. 가변적이라는 특성 때문에 비어있는 공간을 합쳐 보면 크지만 곳곳에 흩어져 있어 external fragmentation 문제가 발생합니다. 이 문제는 memory compaction (빈 공간을 한쪽으로 모으기 위해 할당된 메모리를 이동시키는 작업)을 통해 해결할 수 있지만, 이는 오버헤드가 너무 크기 때문에 수행하기 어렵습니다.

paging

segmentation의 문제점을 해결하기 위해 도입된 방식으로 paging 기법이 있습니다. 이 방법은 물리 메모리 영역을 page frame이라는 고정된 크기 단위로 잘게 자르고, 필요할 때마다 페이지 단위만큼 할당해주는 방식입니다. 이 방식을 사용하면 스택과 힙 영역의 메모리가 어느 방향으로 자라나는지 고려하지 않아도 되어 segmentation 방식처럼 grow positive 변수를 갖고 있지 않아도 됩니다. 또한 빈 공간이 흩어져 있더라도 이를 나눠서 할당해줄 수 있기 때문에 메모리가 낭비되는 일(external fragmentation)을 막을 수 있습니다.

Address Translation

위의 그림에서 알 수 있듯이, 가상 주소 공간에서는 메모리가 연속적으로 위치해 있는 것 같은 환상을 주지만, 실제 물리 메모리에서는 page frame 단위 각각이 불연속적으로 흩어져 있는 것을 알 수 있습니다.

실제 메모리에 접근하기 위해서는 가상 주소 공간에서의 주소를 실제 물리 주소로 바꿔야 하는데, paging 기법에서는 이를 위해 page table을 사용합니다. page table에는 '가상 주소에서는 a번째 위치에 있는 page가, 물리 주소에서는 b번째 위치에 있습니다.' 라는 정보를 제공합니다.

가상주소 (a)	물리주소 (b)
VP 0	PF 3
VP 1	PF 7
VP 2	PF 5
VP 3	PF 0

위 표는 VP이 커지는 순서대로 정렬되어 있으므로 linear page table 입니다. 다양한 구조의 page table에 대해서는 이후에 다룰 예정입니다.

가상 주소는 어떻게 구성되어 있을까?

가상 주소는 VPN과 offset으로 구성되어 있습니다. VPN은 virtual page number로 몇번째 페이지인지, 페이지의 순서를 의미합니다. offset은 하나의 페이지 내에서 어느 위치에 존재하는지를 의미합니다.

6-bit address space with 16byte page 라고 가정하면,

• 하나의 주소를 6개의 bit로 표현하는데,
• 페이지 하나의 크기가 16byte이므로, offset이 4bit를 차지하게 됩니다.
• offset을 할당하고 남은 2bit에 VPN이 할당됩니다.

아래 그림에서 알 수 있듯이, 가상 주소가 물리 주소로 변환될 때 offset 값은 그대로 유지되고, page table에 매핑되어있는 값에 따라 VPN만 PFN으로 변환됩니다.

Page Table

1. 크기와 저장 위치

page table 의 크기는 어느정도 일까??

32-bit address space with 4KB pages 라고 가정하면,

• offset은 4KB를 표현해야 하므로 12bit를 할당받아야 합니다.
  4KB = $2^1$$^2$ byte
• VPN은 32bit 중 offset을 할당하고 남은 20bit를 사용하여 표현됩니다.
• address translation에서는 VPN만 필요하므로 PTE (page table entry) 에서 VPN을 할당하고 남은 12bit에는 page에 대한 여러 정보들이 저장됩니다.
• 32-bit는 $2^3$$^2$개의 수를 표현할 수 있으므로, 4GB 메모리 영역을 표현할 수 있습니다. 이는 한 프로세스 당 4GB의 가상 주소 공간을 가질 수 있다는 것을 의미합니다.
  $2^3$$^2$byte = $2^2$$^2$KB = $2^1$$^2$MB = $2^2$GB
• 하나의 프로세스가 4GB 가상 주소 공간을 가질 수 있고, 페이지 하나의 크기가 4KB이므로, page table은 $2^2$$^0$개의 페이지에 대한 정보를 가지고 있어야 합니다.
  4GB / 4KB = $2^2$$^0$
• PTE 하나의 크기가 32bits 이므로 총 page table의 크기는 4MB 입니다.
  32bits * $2^2$$^0$ = $2^2$$^5$bits = 4MB

page table 은 어디에 저장될까?

32-bit address space with 4KB pages 컴퓨터에서는 page table 1개가 4MB 입니다. 현재는 64-bit 주소 공간과 4KB 크기의 페이지를 사용하지만, 32bit도 꽤 현실적인 예시입니다. 여기서 4MB에 달하는 테이블을 모두 CPU에 모두 저장하기엔 불가능하므로, page table은 메모리에 저장되어 OS가 관리합니다.

2. 저장되는 정보

page table entry 에는 어떤 정보가 저장되어 있을까?

하나의 page table entry는 아래와 같은 구조를 갖고 있습니다. 아래 구조느 x86-32 컴퓨터의 PTE 구조 예시입니다.

• valid bit : 해당 항목이 유효한 변환 정보를 갖고 있는지 여부를 나타낸다.
• protection bit : 해당 항목이 읽기, 쓰기, 실행, 사용자/커널 모드 접근 권한 중 어떤 권한을 가지고 있는지를 나타낸다.
• present bit : 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지(스왑 아웃 되었는지)를 가리킨다.
• dirty bit : 페이지가 갱신되었는지 여부를 판별한다. write가 발생 여부
• reference bit : 자주 읽는 페이지인지 나타낸다.

3. 속도

page table 을 사용하면 속도가 많이 느려지지 않을까?

CPU는 메모리에 저장되는 page table을 사용하기 위해, page table의 시작 주소를 가리키는 PTBR (page table base register)를 갖습니다. 각각의 page와 매핑되어 있는 PTE에 접근하기 위해선 PTBR + VPN * sizeof(PTE) 주소로 접근하면 됩니다.

이 코드는 가상 주소를 통해 물리 메모리 주소를 알아내고, 이에 접근하는 일련의 과정을 슈도 코드로 나타낸 것입니다. 코드를 보며 실제 메모리에 접근하는 과정을 알아봅시다!
1. 가상 주소에서 VPN 알아내기
2. PRBR에 접근하여 PTE의 물리 주소 알아내기
- 페이징 기법에서만 추가로 발생하는 메모리 접근 (이것 때문에 속도가 느려짐)
3. PTE에서 알게된 페이지 정보를 바탕으로 예외처리 하기 & PTE에서 PFN도 알아내기
4. 가상 주소에서 offset 구하기
5. PFN과 offset을 통해 실제 물리 주소 구하기
6. 실제 물리 주소로 메모리에 접근하기