[운영체제] 16. Paging

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

Paging

 

Segmentation의 경우 가변 크기로 메모리를 할당하였고, 이로 인해 external fragmentation이 발생한다고 했다.

Paging은 프로세스의 가상주소공간을 고정 크기로 나눠 메모리를 할당한다.

가상공간에서 나누어진 고정 크기 단위를 page라 하며, 이 page를 실제 메모리에 할당할땐 frame이라 한다.

또한 프로세스마다 va를 pa로 바꾸는 page table이 필요하다.

 

Paging의 장점은 1. Flexiblity - 각 주소 공간에 대한 abstraction을 지원하고, 2. Simplicity - free-space mangement가 쉽다는 것이다. va의 pages와 pa의 frame이 같고, external fragmentation이 없기 때문이다.

 

128 byte의 physical memory에 16 bytes의 page frame이 있다고 하자.

그리고 여기에 16bytes page를 가지는 64 bytes의 virtual address space가 있다.

 

va는 VPN과 offset으로 이루어져 있다. VPN은 virtual address space / page size로, 즉 page number를 말한다.

offset은 va size에서 VPN bit를 제외한, page와 같은 크기를 가지게 된다.

 

이때 address translation의 경우, va의 VPN이 Physical Frame Number(PFN)로 변환되어지며 offset은 그대로 들고간다.

 

Page Table은 va를 pa로 mapping하는 자료구조다. Page table로 mapping하는 과정은 아래와 같이 진행된다.

 

- Where are page tables stored?

page table은 register에 저장할 수 없다. 32bit 주소공간에서 page 크기가 4KB(2^12)라 한다면 VPN은 2^32 / 2^12 = 2^20, 약 100만개다. 그리고 page table의 크기가 4byte라 하면, 각 프로세스의 PTE마다 4MB가 필요하게 된다.

따라서 page table은 커널 메모리에 저장하게 된다. 

PTE의 flag에는 valid bit, protection bit를 비롯한 여러 bit가 있다.

Page sharing의 경우 parent's pages를 가리키는 page table를 만든다. fork()한 프로세스가 부모 페이지를 변경하면, copy를 생성하고 새로운 페이지에 Write한다. Protect bit가 RE로 set되어있으면, modification이 MMU에 의해 금지된다.

 

Paging의 단점은 아래와 같다.

1. Internal fragmentation : 내부 단편화 - code, heap, stack이 page size보다 작으면, 남은 메모리 공간은 낭비되게 된다. 

2. performance degradation : Paging은 모든 메모리 접근에서 메모리 내 page table로부터 PTE를 fetch하고, 메모리의 데이터에 접근하는 형태로, 메모리 접근이 두번 발생해서 퍼포먼스가 안좋다. 

3. Huge page tables : 위에서 설명했듯이, page table의 크기가 매우 커진다. 만약 page size를 키운다면, VPN은 조금 줄어들겠지만 Internal fragmentation이 더 심화될 것이다.