paging : smaller table

paging

base and bound, segmentation과 구분되는 paging의 장점은 고정된 페이지 크기를 사용하여 메모리 관리가 편리하다는 점이다.

하지만 주소변환정보를 담고 있는 page table과 관련해서 두가지의 문제가 있다.

 

1. 속도의 문제

page table이 물리적 메모리에 위치하고 있기 때문에, 하나의 명령어를 수행하기 위해 여러번 메모리에 접근해야 해서 속도가 느림.

>> 이것은 TLB로 해결할 수 있다.

 

2. 크기의 문제

page table에서 VPN를 인덱스로 PFN를 담고있는 entry를 가져오기 위해서는 페이지 테이블이 연속된 공간을 확보해야 한다.

그런데 page table이 너무 커진다.

그렇다고 page의 크기를 크게 하면, page table entry개수는 줄어들지만 internal fragmentation이 생겨버린다.

(segmentation에서는 임의의 크기를 할당해주므로 external fragmentation이 생긴다.)

>> 대체 어떻게 작은 page table을 만들어낼 수 있을까?

 

우리는 오늘 이러한 이슈를 해결하기 위한 세가지 방법을 살펴볼 것이다.

1. Hybrid Approach 

2. Multi-Level page table

3. Inverted page table

 

 

Hybrid Approach : paging and segments

segmentation과 paging을 섞어서 장점만 취하는 방법이다.

말 그대로, 주소체계를 page로만 나누지 말고 segmentation도 함께 사용하자는 것이다

 

우선 address space를 크게 나눈다. 이 경우 4개로 크게 나누어서 4개의 segment number를 갖게 된다. (00, 01, 10, 11)

4개의 비트로 표현되던 VPN을 잘라서 두자리는 segment number, 나머지 두자리는 각각의 세그먼트에 속한 VPN가 된다. 

각 페이지 테이블은 연속된 공간을 가져야한다.

다시 말해, segment table을 만들고, 그 안에 page table을 만드는 것이다.

그런데 위 그림을 보면 10 segment는 사용하지 않는 것을 볼 수 있는데, 이 경우 굳이 페이지 테이블을 구성할 필요가 없다. 

 

또한 segment table은 mmu안에 레지스터 형식으로 들어가 있다고 볼 수 있다.

기존의 segmentation에서는 segment table이 갖는 정보가 실제 내용, 즉 해당 segment가 시작하는 물리적 주소였다.

하지만 hybrid 방식에서 segment table이 갖는 정보는 page table이 시작하는 주소이다. 

그리고 그 옆에 크기 정보도 들어가는데, 이는 segment의 크기가 아니라 해당 page table entry가 몇개인지를 나타내는 것이다.

 

그리고 너무 당연한 이야기지만 위 과정에서 고려해야하는 segment number, vpn의 비트수는 상황에 따라 다르다.

예를 들어 32비트 머신 + 4개의 세그먼트 + 메모리 페이지의 크기는 4KB(2^12)라고 가정했을 때의 상황은 위 그림과 같아진다.

또한 페이지 테이블의 크기는 위 그림에서 vpn이 나타내는 범주 내에서 다양하게 나올 수 있다.

 

 

Hybrid 방식에서의 주소 변환과정
<VPN, offset> => <PFN, offset>

결국, 주소 변환을 한다는 것은 mmu를 통해 VPN를 PFN로 변환하는 것이다.

그 과정을 한번 살펴보자. (위의 예시에서 VPN은 4자리로 들어오고 segment는 4개이다.)

 

0. 만약 VPN에 맞는 유효한 TLB entry가 있다면 그걸 쓰면 된다. (주소변환을 할 필요가 없음)

 

1. TLB miss일 경우, 4자리로 들어온 VPN에서 제일 위 두자리를 마스킹하여 segment number를 뽑아내고, 다음 두자리를 마스킹하여 VPN을 뽑아낸다.

 

2. 그리고 PTE를 뽑아내기 위해 segment table에서 segment number를 인덱스로 base(해당 page table의 시작주소)를 알아낸다.

 

3. 그렇게 구한 page table에서 아까 뽑아낸 VPN을 인덱스로 PTE address를 구하고, 이 주소로 접근하여 PTE를 가져온다.

 

4. 해당 PTE에 있는 PFN, Protect bits정보를 TLB에 넣고, 명령어를 재실행한다.

 

5. TLB에 VPN에 맞는 유효한 entry가 있으므로 주소 변환이 가능해진다.

 

 

Hybrid approach에서도 여전히 존재하는 문제

1. still segmentation, not flexible

힙 공간을 크게 할당했는데 allocation을 별도로 안하는 경우! 너무 아깝지만 해결 방법이 없다..

 

2. external fragmentation이 여전히 존재한다.

direct indexing을 위해 연속된 공간이 필요하지만 페이지테이블의 크기는 가변적이기 때문에 external fragmentation이 여전히 존재하게된다. (base and bound, segmentation을 사용할때의 어쩔수 없는 한계..)

 

 

Multi-Level paging

multi level paging은 page table을 물리 메모리에 넣을때에도 paging의 장점을 살려서 넣어보자는 발상에서 시작한다.

page table을 page크기로 잘라서, page단위로 메모리에 넣는 방법을 통해 구현된다.

이 과정에 대한 논리적 구조를 살펴보자.

page table을 page크기로 자르고, 이 각각의 page table의 시작주소를 page directory에 둔다.

여기서 page directory란 page table을 위한 page table이다.

 

그런데 위 그림의 page directory를 보면 세번째 entry는 유효하지 않은 것을 볼 수있다. 이말은 즉, 세번째 entry를 위한 페이지 테이블은 없어도 된다는 이야기이다.

이렇게 위의 그림에서 multi level paging을 이용하면, 크기가 일정한 3개의 페이지 테이블만 있으면 된다.

 

그러면 위의 구조를 물리적인 공간에서는 어떻게 구현하는지 살펴보자.

일반 paging에서 PTBR(page table base register)를 사용했던 것과 달리, multi level paging의 mmu에서는 PDBR(page directory base register)라는 것을 사용한다.

 

이때 page directory도 page 크기에 맞게 준비되고, PDBR은 page directory가 물리 메모리의 어떤 페이지에 들어가는지를 알려준다.

 

만약 4비트의 vpn이고 page directory entry도 4개라면, hybrid 방식과 비슷하게 vpn을 2비트/ 2비트로 나눠서 page directory index/ page table index로 사용할 수 있을 것이다.

hybrid approach(segmentation+paging)와 multi level paging의 아이디어 차이!

1. hybrid approach = address space를 segment로 잘라보자! (그렇게 잘라서 segment table로 관리)

2. multi level paging = address space는 건드리지 말고, page table을 page크기로 잘라보자! (그렇게 잘라서 page directory로 관리)

 

그럼 이번에는 Multi-Level paging을 기존의 page table과 비교해보자.

왼쪽의 linear page table을 보면 중간에 정보가 없어도 indexing을 위해서 자리를 차지하고 있어야 해서 공간의 낭비가 큰것을 볼 수 있다.

이것을 오른쪽 그림처럼 multi level page tables로 개선하면 저 중간에 있는 불필요한 공간들은 실제 물리메모리에 할당하지 않고, 필요한 페이지테이블만 page frame크기에 맞추어 물리메모리에 둘 수 있다.

 

 

Multi-Level paging의 단점

1. 기존 paging의 단점이 주소변환을 위해 메모리 page table에 한번 더 접근해야 한다는 것인데, multi level paging에서는 page directory에 접근하는 과정이 추가되면서 메모리에 총 3번 접근해야 하는 일이 생긴다.

 

2. complexity : page table을 찾기 더 복잡해진다.

 

하지만 이러한 단점에도 불구하고 multi level paging을 사용하는 것은 TLB의 역할에 기대를 거는 것이라고 볼 수 있다.

 

 

더 큰 machine에서의 Multi-Level paging

더 큰 공간을 가지는 machine을 사용하면 page directory가 더욱 커진다.

그렇게 되면 또 내부에 낭비하는 공간이 많아지므로 이걸 또 잘라서 page directory를 위한 page directory를 만들 수 있다.

3 Level page table

32bit machine에서는 2 Level로 가능했지만, 64bit machine에서는 그것으로는 부족하기 때문에 실제로 Intel칩의 경우 4 Level page table을 사용하고 있다.

그리고 이러한 복잡성때문에 고안하게 된 다른 접근방식도 있다.

 

 

Inverted page tables

위에서 살펴봤듯이 VPN > PFN으로 변환하는 것은 virtual address space가 너무 커서 어렵고 복잡하다.

그래서 이걸 거꾸로 접근해서 PFN에서 VPN를 역으로 찾아보자는 아이디어로 나온 방식이 바로 Inverted page tables이다.

( O(1)으로 검색할 수 있는 해시 테이블을 사용 )