OS - [CH20_Advanced page tables]

page table이 메모리를 너무 많이 잡아 먹는다

프로그램마다 페이지 테이블을 각각 가지는데 

여러개 동시에 작동하면 (프로그램 수*페이지 테이블 사이즈) <- 넘나 큼

페이지 테이블을 디스크로 swap out도 못함-> 페이지 테이블이 RAM에 없어서 접근 불가

  -> page table을 어떻게 작게 할 수 있을까?

 

 

 

쉬운 방법: Large page

페이지 크기를 크게해서 page table 사이즈를 줄인다.

단점 - internal fragmentation 유발 (각각의 페이지에서 메모리 낭비됨)

결론: 문제 해결 불가

 

 

Hybrid Approach: Paging and Segments

접근: 프로세스의 모든 주소 공간의 페이지 테이블을 한 개 두는 것 대신 각 논리적 세그먼트마다 두자.

ex) code, heap, stack이 각각 페이지 테이블을 가짐

 

hybrid에서 여전히 이러한 구조를 MMU에 둔다.

base를 세그먼트 자신을 가리키게 하는 것이 아니라 해당 세그먼트의 page table의 physical address를 가지도록 한다.

bounds register은 페이지 테이블의 끝을 나타낸다. (유효 페이지가 몇 개인지 나타냄)

 

context switch가 일어날 때, 이러한 레지스터들은 새로 작동하는 프로세스의 페이지 테이블 위치를 반영하도록 바꿔야한다.

TLB miss(hardware-managed TLB, 즉, 하드웨어가 TLB miss 핸들링하면)가 일어나면 하드웨어는 어떤 base-bounds 쌍을 사용할 지 결정하기 위해 세그먼트 비트(SN)를 사용한다.

 

PTE의 주소 형성

전에 본 linear page table이랑 다른 점은 단일 페이지 테이블의 base register를 사용하는 것이 아니라 세 세그먼트(code, stack, heap) 중 하나의 base register을 사용함

hybrid scheme에서 가장 중요하게 다른점은 각각의 세그먼트의 bounds register의 존재이다; 각각의 bounds register은 세그먼트 안에 유효한 페이지의 최대값을 가지고 있다.

예를 들어,

code segment가 첫번째 세 페이지들을 가진다면(0,1,2), 코드 세그먼트 페이지 테이블은 이것이 할당된 세개의 entry를 가지고 bounds register은 3으로 설정된다.

 

stack과 heap 사이에 할당되지 않은 페이지들은 페이지 테이블에서 공간을 차지하지 못하게 한다.

ㄴ> 문제가 있음

1. 이것 또한 세그먼테이션을 사용해야 한다. segmentation은 flexible하지 않다.  

만약 크고 드물게 쓰는 heap이 있다면 우리는 페이지 테이블 낭비됨

2. 이러한 hybrid는 external fragmentation을 유발한다.

페이지 크기의 유닛으로 대부분의 메모리를 관리하는 동안 페이지 테이블은 임의의 크기라 될 수 있다.

따라서, 메모리에서 적당한 free space를 찾는 것이 복잡해짐

 

Multi-level Page Tables

Single-level -> page table이 하나

 

segmentation에 의존하지 않지만 같은 문제가 있는 다른 접근 법: 

메모리의 모든 것을 저장하는 것 대신에 페이지 테이블에서 유효하지 않는 영역을 없애는 방법은?

-> multi-level page table

linear page table을 tree처럼 바꾼다

 

The basic idea

1. 페이지 테이블을 페이지 크기로 자른다.

만약 page-table entries의 전체 페이지가 유효하지 않다면 모든 페이지 테이블의 페이지를 할당하지 않는다.

페이지 테이블의 페이지가 유효하다면 page directory라는 구조를 사용한다.

page directory는 페이지 테이블의 페이지가 어디에 있는지, 또는 유효하지 않는 페이지를 포함하는 페이 테이블의 전체 페이지를 말해 줄 때 사용할 수 있다.

 

page directory는 사용하지 않는 페이지 빼고 사용하는 두 개의 페이지만 마크한다. (linear page table은 안 쓰는 공간도 공간 할당 해줌) 즉, 메모리에는 페이지 테이블의 두 개의 페이지만 남는다.

page table에서 어떤 페이지가 page directory로 할당받을지 추적한다.

page directory는 단순한 two-level table로 페이지 테이블의 페이지 당 하나의 항목만 포함한다.

이것은 다수의 page directory entries(PDE)를 포함한다.  PDE는 valid bit와 PFN를 가진다(PEN과 유사)

PDE가 유효하다는 것은 entry가 가리키는 페이지 테이블의 페이지가 하나 이상 유효하다는 것이다.

-> 해당 PTE의 valid bit가 1로 설정됨

만약 PDE가 유효하지 않다면 나머지 PDE는 정의되지 않는다

 

Advantages of Multi-level page table 

1. multi-level page table은 사용하는 주소 공간의 양에 비례하여 페이지 테이블 공간을 할당한다.

-> 크기가 작고 드물게 사용하는 주소 공간을 지원한다

 

2. page table의 각 부분은 페이지 내에 깔끔하게 맞춰져 메모리 관리가 쉽도록 함

OS는 이것이 할당이나 페이지 테이블 성장이 필요할 때 다음 free page를 잡기 쉽다.

이것은 VPN을 index로 하는 PTE 배열인 단순한 linear page table (non-paged)이다.

이러한 구조로 전체 linear page table은 physical memory에 인접하게 놓여있다.

 

multi-level 구조로 page directory 사용을 통해 level of indirection을 추가한다.

이 indirection은 physical memory의 원하는 곳에 page-table page를 놓을 수 있게한다.

 

A cost to multi-level tables

- TLB miss에서 page table로부터 올바른 translation을 얻으려면 메모리에서 두번 로드해야한다.

   ㄴ한번은 page directory, 한번은 PTE 자신

   ㄴ linear page table에서는 한번 로드하는 것과 달리

-> multi-level table은 time-space trade-off의 작은 예이다 (빨리 접근하려면 공간을 많이 사용함)

- TLB miss는 작은 테이블로 인해 높은 비용에 고통 받는다

- 복잡하다

   ㄴ multi-level table은 메모리를 절약하기 위해 page-table 조회를 복잡하게 한 것

 

A Detailed Multi-Level Example

주소 공간 크기가 16KB이고 64byte page가 있다고 상상보자

그럼 우리는 14bit 가상 주소 공간이 있다. 8bit는 VPN, 6bit는 offset

linear page table은 주소 공간의 작은 부분만 사용하더라도 2^(8)=256 entry를 가진다

이 주소 공간을 two-level page table로 만든다면 일단 페이지 크기의 유닛으로 이것을 쪼갠다

PTE가 4byte라면 페이지 테이블은 1KB(256X4) 크기이다. 

64byte page가 있으니까 1KB를 16개 x 64byte로 나눌 수 있다. 각각의 페이지는 16 PTE를 가질 수 있다.

 

그렇다면 VPN은 어떻게 얻을 수 있는가? page directory과 page table의 page에 이것을 어떻게 index 하는가? 

각각의 VPN으로부터 어떻게 index 하는가

먼저 page directory에 index를 정하는가.

page directory는 페이지 당 하나의 항목을 가진다. (예로는 16개)

그 결과, 우리는 directory에 indexing하려면 VPN 4 bit가 필요하다. VPN의 상위 4bit를 사용한다.

일단 VPN에서 page-directory index를 추출하면 PDE 주소를 찾을 수 있다

PDEAddr=PageDirBase+(PDIndex*sizeof(PDE))

 

page-directory entry는 유효하지 않는 것을 마크한다면 우리는 접근이 유효하지 않다는 것을 알고 예외를 발생한다.

하지만 PDE가 유효하다면 

page directory entry가 가리킨 페이지 테이블의 페이지로부터 PTE를 패치해야한다.

PTE를 찾기 위해서, 남은 VPN bit를 사용한다

 

이 page-table index는 페이지 테이블 자체를 인덱싱하여 PTE 주소를 제공할 수 있다.

PTEAddr = (PDE.PEN << SHIFT) + (PTIndex*sizeof(PTE))

PDE로부터 얻은 PFN는 PTE 주소를 형성하기 위해 페이지 테이블 인덱스와 결합하기 전에 left-shift 해야된다.

 

 

More than two levels

페이지 테이블의 모든 조각을 한 페이지에 맞추기 위해 multi-level table에서 몇 개의 level이 필요할지를 결정하려면

한 페이지 내에 얼마나 많은 PTE를 넣을지 결정해야 한다.

 

페이지 크기가 512byte로 주어지고 PTE 크기가 4byte라고 한다면 

단일 페이지에 128개의 PTE를 저장할 수 있어야 한다. (512/4=128)

그렇다면 VPN index로 최소한 7bit가 필요하다. (2^7=128)

 여러 페이지들에 맞게 페이지 디렉토리도 쪼갠다.

 

Process of address translation using a two-level page table

1. hardward는 TLB를 체크

2. TLB hit이면 페이지 테이블에 접근 없이 물리 주소 얻음

   TLB miss이면 multi-level lookup 수행

 

Inverted page table

-> 공간 절약 

프로세스당 하나의 테이블만 가져서 피지컬 페이지항목들은 가짐

항목은 현재 페이지에서 사용하는 프로세스와 피지컬 페이지의 프로세스 맵의 가상 페이지를 알려줌

 

Swapping the page table to disk

page table이 kernel-owned physical memory에 놓여있다고 가정하다.

페이지 테이블이 kernel virtual memroy에 저장되어 있는데 메모리 압박이 오면 페이지 테이블을 disk로 swap한다.

 

SUMARY

가상 주소 공간을 여러개의 페이지 테이블(multi-level page table)로 나눠서 페이지 테이블의 물리적인 크기를 줄인다.

모든 주소 범위를 사용하는 것이 아닌 일부 페이지 테이블이 필요하다.

 

level1 table: page directory -> 현재 필요한 PTE 주소 가짐

level2 table: 현재 쓰일 PFN만 가진 페이지 테이블을 형성