09. 운영체제 - Memory Virtualization(4)

Paging

Linear Table

보통 각 프로세스마다 하나의 page table을 가진다.

앞선 게시글에서 언급했던 것 처럼 32bit address space의 4KB 페이지, 4byte의 PTE 에서 페이지테이블의 사이즈는 4MB이다.

이 경우 Page table의 사이즈가 너무 크고 메모리를 너무 많이 잡아먹는다. 

Smaller Table

32bit address space를 16KB 의 페이지로 나누면, PTE의 개수가 2^16개로 줄어드므로 page table의 사이즈가 1MB로 줄어들지만, 페이지의 크기가 커지면 internal fragmentation이 더 많이 발생한다. 

Hybrid Approach

page table의 메모리 오버헤드를 줄이기 위해 paging과 segmentation 기법을 함께 사용하는 방식이다.

세그먼트를 가리키기 위해 base 레지스터를 사용하는 대신 그 세그먼트의 page table의 physical address를 가리키도록한다.

bound 레지스터는 page table의 끝을 가리키기 위해 사용한다.

예를 들어 각 프로세스는 세개의 page table을 가지고, 프로세스가 실행되면 각 세그먼트의 base register들은 해당 세그먼트의 page table의 physical 주소를 담는다.

하지만 hybrid 방식도 여전히 external fragmentation 문제를 갖고있다. 만약 사이즈가 크지만 대부분 사용되지 않는 heap 세그먼트가 있다면 우리는 page table을 낭비하는 것이 된다.

Multi-level Page Table

Page table을 linear array로 하는 대신 Page table 자체에도 paging기법을 적용하여 트리와 같은 형태로 저장하는 방법이다.

page table을 page 와 같은 사이즈의 단위로 쪼갠다.

만약 page table에서 valid한 페이지가 없다면 page table을 위해 아무런 메모리도 할당할 필요가 없다.

페이지 테이블의 페이지가 valid한지 확인하기 위해 page directory 라는 새로운 자료구조를 사용한다.

페이지 디렉토리의 entry (PDE)는 페이지 테이블의 페이지를 가리킨다.

PDE는 valid bit과 PFN으로 이루어져있다.

해당 PDE가 valid할 경우 대응되는 PFN의 페이지로 가면 해당하는 페이지 테이블을 찾을 수 있다.

위 그림의 경우 페이지 디렉토리의 1번과 2번 entry는 invalid하다. 즉 해당하는 페이지 테이블에 들어가야하는 페이지가 아무것도 없는 것이므로 페이지테이블을 위한 공간이 할당될 필요가 없다. 따라서 Multi-level Page Table의 경우에는 실제로도 할당되지 않았다.

하지만 왼쪽의 Linear Page Table 방법에서는 모든 페이지테이블을 위한 공간을 모두 할당해주어야하기 때문에 공간의 낭비가 발생한다.

장단점

• 장점 : Page table을 위한 공간을 실제 사용하는 address space 만큼만 할당해줄 수 있다. (Internal fragmentation 감소)
• 단점 : Space 측면에서는 장점이 있지만 translation time이 늘어나므로 space와 time 사이에 트레이드오프가 존재한다.

Multi-level page table 방식은 페이지 디렉토리를 이용해 Indirection을 구현한다. 그리고 우리는 indirection의 레벨을 조절할 수 있다.

Example

• Address space : 16KB
• Page 사이즈 : 64byte
• Virtual address : 14bit

인 상황을 생각해보자.

페이지가 64byte이므로 Offset으로는 6bit가 필요하다. 그리고 나머지 8bit가 VPN으로 쓰인다.

그리고 VPN의 앞의 4bit를 페이지 디렉토리 인덱스로 사용하면 페이지 디렉토리에는 총 16개의 entry가 생긴다.

page directory index를 통해 페이지 디렉토리에 접근하여 페이지 테이블을 가져온다.

만약 접근한 PDE가 invalid하다면 exception을 발생시키고, valid하다면 page table index를 통해 페이지 테이블에서 알맞은 페이지를 갖고온다.

 

Deeper Multi-level Page Table

페이지 디렉토리를 중첩으로 두어 더 깊은 트리를 구성할 수 있다.

• Page 사이즈 : 512byte
• Virtual address : 30bit
• Offset : 9bit
• VPN : 21bit

인 상황을 생각해보자.

512byte짜리 페이지에 4byte 짜리 entry가 들어가면 한 페이지 당 총 128개의 PTE/PDE가 들어갈 수 있다.

페이지 디렉토리가 2^14개의 entry로 이루어진다면 PDE하나에는 총 128개의 페이지가 들어간다. 그러면 128개 중 하나의 페이지테이블만 존재하더라도 PDE가 할당되어야한다.

이를 해결하기 위해 트리의 레벨을 늘린다.

페이지 디렉토리 하나의 인덱스로 사용되던 14bit를 7개씩 나누어 두개의 페이지 디렉토리를 사용한다.

그리고 첫번째 페이지 디렉토리에 접근하여 entry를 가져오면 그 다음에는 페이지 테이블로 가는 대신 두번째 페이지디렉토리에 접근하게된다. 

3 level page table은 위와 같이 이루어진다. 

CR3 레지스터는 가장 상위의 페이지 디렉토리의 베이스 주소를 담고있는 레지스터이다.