15. Paging : Smaller Table

Motivation

- TLB가 관리할 수 있는 page보다 더 많은 page를 요구하는 프로세스를 처리하는 경우, page table에 사용되는 메모리 공간을 줄이는 방법

 

Paging : Linear Tables

: 일반적으로 시스템에서 모든 프로세스에 대해 하나의 page table을 가짐

- page table size = (가상 주소 공간의 크기 / page의 크기) x page table entry의 크기

-> 계산해보면 page table이 너무 커서 너무 많은 메모리를 사용하고 있음

 

1. Large Page : Smaller Table

: page의 크기를 늘려서 page table size를 줄이는 방법

- page 자체 활용도가 낮아서(page 자체 크기가 커서) 내부 단편화가 발생

-> 낭비하는 공간이 큼

 

cf) 내부 단편화

: 메모리를 할당할 때 프로세스가 필요한 양보다 더 큰 메모리가 할당되어서 프로세스에서 사용하고 남은 공간을 의미

 

- 더 큰 page size는 더 적은 page 수를 의미하며 이는 메모리가 빨리 소모된다는 것을 의미

 

2. Hybrid Approach : Paging and Segments

: Paging 기법과 Segmentation을 함께 사용하는 방식

- page table 메모리 오버헤드를 줄이기 위해서

• base 레지스터는 실제 주소의 page table을 가리키는데 사용
• bound 레지스터는 해당 page table의 끝을 나타내는데 사용

1) 동작 방식

• 하드웨어는 page table으로부터 실제 주소를 얻을 수 있음
• 하드웨어는 세그먼트 비트(SB)를 사용하여 사용할 base 및 bound 쌍을 결정
• 그런 다음 하드웨어는 실제 주소를 가져와서 VPN과 결합하여 Page Table Entry의 주소를 형성
• TLB miss바 발생해도 segement bit를 사용해서 주소 변환을 진행할 수 있음

- 기존 Paging 기법과 차이점은 bound 레지스터가 page table의 끝을 가지기 때문에 사용하지 않는 page  table의 공간을 유지할 필요가 없어지므로 메모리 낭비를 줄일 수 있음

 

2) Problem

- 사용 빈도가 낮지만 큰 Heap이 있다면, 여전히 너무 많은 Page Table이 낭비될 수 있음

-> 이러한 문제점은 외부 단편화를 다시 발생시킴it

 

3. Multi-level Page Tables

: Page Table에서 사용하지 않는 공간은 메모리에서 제거하는 방법

- 실제 OS에서도 사용되며 아주 효과적임

 

1) 동작방식

• Linear Page Table을 Tree와 같은 무언가로 바꿔줌
• page table을 page 크기의 단위로 자름
• 만약 page table entries가 전체 page에 유효하지 않은 경우(하나라도 유효한 entry가 없다면) -> 해당 page table을 할당하지 않음
• page table의 page가 유효한지 아닌지 추적하기 위해 Page Directory라는 새로운 구조를 사용

- Page Directory : page table의 page가 어디에 있는지, 해당 page table에 유효한 page가 있는지 알려주는 역할

• Page Directory는 page당 하나의 page entry만 가짐 -> page table의 시작 부분, base 레지스터와 같은 역할을 함
• page directory는 다수의 Page Directory Entries(PDE)로 구성되어 있음
• 유효한 Bit과 Page Frame Number를 가짐
• Invalid : page table의 전체 page에 유효한 page가 없는 것을 의미
• Valid : 이 PDE가 가리키는 해당 페이지의 PTE가 적어도 하나는 유효하다는 것을 의미

2) 장점

• Only 사용 중인 주소 공간에 비례해서 Page-table Space만 할당함
• OS가 page table을 할당하거나 확장해야 할 때 다음의 free page를 잡을 수 있음

3) 단점

• TLB miss인 경우, page table에서 올바른 변환 정보를 얻으려면 메모리에서 2개의 load가 필요
• "2개의 load에 접근" 의미 : page table에 접근하기 위해 page directory에도 접근할 때의 1번, page directory에서 유효한 PFN 정보를 가져오기 위해 접근할 때의 2번 -> Time-space Trade-off
• 기존의 방법보다 복잡하므로 Increased Complexity라고도 부름