[OS] Paging: Introduction

Minseok Kim·2023년 12월 7일

OS

목록 보기

3/4

Concept of Paging

Paging은 한 프로세스의 address space를 고정된 사이즈로 고정된 사이즈의 유닛(페이지)으로 쪼개게 된다.
Segmentation: 가변 크기 분할(code, stack, heap, etc). 외부 단편화 문제
paging: 고정 크기 분할
page: address space의 쪼개진 한 영역
page frame: physical memory의 쪼개진 한 영역
프로세스마다 매핑 정보를 page table 담고 있다.

Advantage Of Paging

페이징의 장점
Flexibility: 세그먼테이션에서는 힙과 스택이 어느 방향으로 자라는지 신경을 써야했지만 페이징은 이러한 단점을 보완한다.
Simplicity: free space의 관리가 쉬워진다.

가상 주소와 물리 주소를 16바이트의 고정된 크기로 분할하였다.
각각의 페이지는 물리 메모리에서 연속적으로 존재하지 않고 임의의 페이지 프레임에 매핑이 될 수 있다.

address space에서 페이지 번호는 VPN(virtual page number)으로 표기한다.

page 0 of the address space = VPN0
page 1 of the address space = VPN1

physical memory에서 페이지 프레임의 번호는 PFN(page frame number)으로 표기한다.

page frame 0 of physical memory = PFN0
page frame 1 of physical memory = PFN1

Address Translation

virtual address를 physical address로 변환해 주는 과정을 보자.

paging에서 virtual address를 VPN과 Offset으로 나눈다.
VPN: virtual page number
Offset: offset within the page

64바이트의 address space를 4개의 페이지로 나눴을 때, virtual address 21의 VPN과 offset은 다음과 같다.

VPN: 1 <-> PFN: 7이라고 할 때 Address Translation은 다음과 같다.

이러한 매핑 정보는 페이지 테이블 안에 기록이 되어있다.
Address Translation은 빠른 속도를 위해 하드웨어(MMU)가 담당한다. MMU 하드웨어는 해당되는 페이지 테이블의 내용을 읽어서 VPN을 PFN으로 바꿔준다. offset은 그대로 유지된다.

Where Are Page Tables Stored?

page table: virtual address를 physical address로 매핑하기 위한 정보를 담고있는 자료구조
보통 배열로 구성하게 된다.

페이지 테이블은 매핑 정보를 담고있다. 각각의 정보는 페이지 테이블 엔트리에 기록이 된다. 위에서는 4개의 페이지 테이블 엔트리가 필요하다.

페이지 테이블은 하나의 배열로 생각할 수 있고 배열의 인덱스와 VPN 번호가 일치하니 VPN 번호는 페이지 테이블 엔트리 안에 넣지 않아도 된다.
만약 PTE크기가 4바이트라면, 페이지 테이블의 사이즈는 16바이트가 될 것이다.

32-bit address space에서 페이지가 4KB의 크기로 나뉜다고 생각해보자. 4KB=4096=2^12이므로 offset은 12비트가 될 것이며, VPN은 20비트가 될 것이다.
PTE가 4바이트이면 페이지 테이블의 사이즈는 4MB(2^20 * 4바이트)가 된다. 즉 한 프로세스당 4MB의 큰 메모리 공간을 차지해야한다. 각각의 프로세스는 자신만의 address space를 가지고 있으니 자신만의 페이지 테이블을 가지고 있어야 하며 프로세스의 개수가 늘어나면 페이지 테이블이 차지하는 물리 메모리의 공간도 상당히 늘어날 것이다.

So, Where are page tables stored?
address translation은 하드웨어가 진행을 하지만 전체적인 페이지 테이블의 크기가 커서 프로세서 안에 담을 수 없으므로 페이지 테이블은 물리 메모리 안에 저장을 하게된다.

Common Flags Of Page Table Entry

페이지 테이블 엔트리에는 PFN뿐만 아니라 다양한 비트들도 포함하고 있다.
Valid Bit: VPN과 PFN이 매핑이 되어 있으면 1, 그렇지 아니하면 0으로 세팅
Protection Bit: 해당 페이지가 읽기 전용인지, 쓸 수도 있는지, 아니면 실행도 가능한지 알려주는 비트
Present Bit: 현재 페이지 프레임이 실제 메모리에 있는지 아니면 디스크로 swapped out 되어있는지 알려주는 비트
Dirty Bit: 해당 페이지가 물리 메모리로 올라온 후 수정이 되었는지 알려주는 비트
Reference Bit(Accessed Bit): 해당 페이지가 접근되었는지(누가 읽거나 실행 했는지) 알려주는 비트

Paging: Too Slow

MMU가 가상 주소를 물리 주소를 변환하기 위해 다음과 같은 과정이 필요하다.
1. 물리 주소에 있는 페이지 테이블의 위치를 알아야한다.
2. 가상 주소에서 VPN을 추출한다. VPN을 페이지 테이블 배열의 인덱스로 사용해서 해당하는 위치로 찾아간다.
3. PTE를 꺼내서 PFN정보를 추출한다. (프로세서 외부에서 진행되므로, 이 단계에서 성능 저하가 크다)
4. VPN을 PFN으로 변환한다.

page table의 위치는 process 구조체(PCB)안에 저장이 되어있다. 해당 프로세스가 컨텍스트 스위칭 되어 실행이 될 떄, 페이지 테이블의 위치가 mmu에 있는 CR3 레지스터로 복사가 된다. mmu는 CR3를 통해 현재 수행하고 있는 프로세스의 페이지 테이블 시작주소를 알게된다.

pseudo code