[운영체제] 18. Paging - smaller table

Reference - Operating Systems: Three Easy Pieces

 

 

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

Operating Systems: Three Easy Pieces

 

 

Hybrid Approach

 

우리는 매 process마다 page table을 사용하고 있다.

32bit 주소 공간에서 4KB의 pages와 4byte의 PTE를 쓴다고 가정하자. 이때 page table의 크기는 4MB다.

100개의 활성 프로세스가 있으면, 오로지 Page Table을 위해 400MB의 메모리 할당이 필요하다.

페이지 크기를 키우면, page table 크기가 1MB지만, internal fragmentation을 야기한다.

 

Single page table의 경우 대부분이 사용되지 않고, invalid entries로 꽉 차있는 문제가 있다.

따라서 Hybrid approach로, segmentation과 paging을 결합하여 접근해보자.

 

page 크기가 4KB, 32bit 가상 주소를 갖는 시스템이라 가정하자.

젤 앞의 2 bit는 segment를 구분하는데 쓴다. 또한 각각의 segment에 대해 base, bound register가 존재한다.

이때 기존 segmentation 기법과 달리 base는segment의 page table의 pa를, bound는 page table의 끝을 나타낸다고 정의한다. 프로세스를 실행하면 page table의 주소를 레지스터에 저장하고, context switch가 발생하면 레지스터의 값을 새로 실행할 프로세스 정보로 바꿔준다. TLB Miss가 발생하면 segment bit를 통해 주소변환을 진행한다.

 

이러한 방법은 segment 당 bound가 있어서 기존 paging의 문제였던 사용하지 않는 공간 낭비를 줄일 수 있다.

하지만 이 방법은 external fragmentation이 발생하게 된다. 또한 free space management도 paging에 비해 복잡해진다.

 

Multi-level Page Table

multi level page table을 통해 사용하지 않는 공간을 메모리에서 제거할 수 있다.

이 방법은, page table을 page 단위로 자른 뒤 유효한 entry가 하나도 없으면 해당 page table은 유지하지 않는 것이다.

이를 위해 page directory 개념을 도입한다. page directory는 page table의 page가 어디에 있는지, page table에 유효한 page가 있는지를 알려준다. 과정은 아래와 같이 진행된다.

 

PDE에서 실제로 사용중인 page에만 접근할 수 있도록 하여 메모리 낭비를 방지한다. 위처럼 두 단계로 page table을 나누는걸 two level page table이라 한다. 

 

이 방법의 장점은 page table의 메모리 공간을 줄여준다. 또한 page-table의 page들을 어디든 정할 수 있어 메모리 관리가 쉬워진다. 단점은 TLB miss가 발생하면 두번의 load가 필요하며, complexity가 더 늘어난다.

 

Inverted Page Table

 

Page table의 크기를 줄이기 위해 많은 page table이 필요할까?

프로세스들의 유효한 PTE는 physical memory의 page frame 수와 동일하다.

따라서 하나의 page table의 entry들이 각 physical page를 가리키게 한다.

vpn이 hash function을 통해 변환돼서 PTE에 삽입되고, PTE의 index가 PFN이 되는 것이다. (= hashed VPN = PFN)

이 방법의 장점은 프로세스별 page table이 필요없어서, 메모리 공간을 줄여준다. 메모리 공간의 크기는 physical memory의 크기에 비례할 것이다. 또한 TLB miss를 처리할 때 메모리 load가 덜 필요하다.

단점은 Hash collision이 worst-case에 긴 access time을 유발할 수 있고, page sharing이 쉽지 않으며, swapping을 지원하지 못한다. hash collision의 경우 메모리 공간을 늘릴수록 collision은 줄어드는 tradeoff 관계다.

모든 PTE에 PFN을 추가하면, PTE가 physical pages보다 커지고 PFN이 PTE location을 추론할 수 없지만, page sharing 문제를 해결할 수 있다.