[OS] Paging : Smaller Tables

지금까지 살펴본 것을 다시 복기 해보자.

각 프로세스 마다 page table이 하나씩 존재하는데, page table이 크기가 너무 커서 메모리에 존재

그 page table에 매번 접근 하자니 memory에 두번 access 하는 것이 되어 overhead 가 커지게 되는 문제가 생겼다.

이를 해결하기 위해 TLB를 만들어 cache 처럼 사용하자는 아이디어를 지금까지 살펴 보았다.

 

32-bit address space 를 가정해보자.

4KB 크기의 page와 4 byte page table entry 라고 했을 때 아래 그림과 같다.

 

 

 

 

 

 

 

 

 

 

먼저 4KB = 2^12이므로 offset에 해당하는 bit 수가 12개 이고 나머지 20 bit에 해당하는 부분이 VPN을 나타내게 된다.

즉 page table entry 수가 2^20개가 되고 한 entry 크기가 4바이트라고 했으므로

따라서 page table size는 2^32/2^12 * 4byte = 4MB가 되게 된다.

 

사이즈가 너무 크다,, 너무 많은 메모리를 사용하게 되므로 효율적이지 못하다.

 

그렇다면 page 크기를 늘려서 entry 수를 조금 줄여보는 방법은 어떨까?

 

한 페이지 크기를 16KB라고 해보자. 그럼 2^14에 해당하는 크기 이므로 offset bit이 14 bit이 되고, 32 bit address space 이므로 나머지 18bit이 VPN을 의미하게 된다.

 

ㄱ럼 아래 그림처럼 표현되고 page table size는 1 MB로 줄어들게 된다.

하지만 이렇게 되면 문제가 또 있다.

페이지 크기가 크게 되면 page 내부의 internal fragmentation이 발생하게 되며 memory 낭비가 심해지게 된다.

 

 

그럼 이제 추가적인 상황을 더 생각해보자.

 

아래 그림은 16KB address space를 나타낸 것이고 14bit으로 표현 가능한 것이다. 이때 page 개수는 16개 이므로 4bit 가 VPN에 해당, 나머지 10bit 가 page offset을 의미한다.

위 그림을 보다시피 page table의 1/4 정도만 사용하고 나머지는 낭비 중임을 알 수 있다.

Virtual Address Space가 있는데 빈 공간이 너무 많은데 이를 전부 Page Table을 만든다고 생각해보자.

그렇다면 Page Table도 쓸모 없이 크게 만들게 된다.

 

그럼 사용하는 부분으로만 page table을 만들어서 작게 만들어 보자.

 

1. hybrid approach : paging and segments

segement와 paging을 결합하여 이용해보는 방법이 있을 수 있다.

 

아래 그림을 보자. 32bit virtual address space  이고 4KB page 크기 이므로 offset에 해당하는 bit는 12개 이다.

이떄 segment를 3개 활용해야 하므로 segment value에 해당하는 2 bit을 사용하고, 나머지 18 bit을 VPN value로 사용한다.

segment table을 만들어 code, heap, stack영역으로 segment를 나눈다. 그리고  base address, bound address 도 함께 저장하여 준다.

그리고 각 segement 별로 각각의 page table을 만드는 것이다. (segment 개수 = page table 개수)

base 에 해당하는 것이 해당 세그먼트에 해당하는 page table의 주소인 것이다.

 

 

이 경우는 무슨 문제가 있을까

heap 같은 경우는 여전히 중간에 비는 경우가 많다.  여전히 page table waste 는 많이 생길 수 밖에 없다.

 

그럼,,!

page table을 다시 page로 잘라서 paging 해보자.

->multi level page table