Paging with Smaller Tables

Page Table 은 굉장히 크기가 큽니다. 동작중인 프로세스를 전부 저장해야 하기때문에 그 부담이 더 크죠.

 

그렇다고 이렇게 Page Size를 늘이면 Page Table의 크기는 줄어들지만 Internel Fragmentation이 매우 심각해집니다.

 

그렇다면 이것을 어떻게 해결할 수 있을까요?

 

일단 Hybrid Approach를 해 봅시다.

 

일단 Page Table의 대부분은 비어 있습니다. 모든 프로그램이 Address Space를 전부 채워서 사용하는것은 아니죠.

 

이 성질을 활용하여 segmentation과 paging을 합칠 겁니다.

전체 Address가 PageTable을 가지는게 아니라, cod heap stack 즉 logical Segment 하나당 PageTable을 가지는 것입니다.

 

그러면 각 세그먼트에는 두 가지 register가 필요하겠죠?

• Base는 segment를 physical memory로 포인트 합니다.
• Bound는 Limit은 Page Table이 끝나는 지점을 Point 합니다.

이럴 경우 Virtual Address는

VA of Hybrid Approach

다음과 같이 됩니다.

 

Segment Table로 Seg를 사용해 들어가서 Bound와 Base를 찾고 Base에 Page Table 주소가 있으니, 여기서 VPN을 사용하여 Paging처럼 Memory에 Access하는 것입니다.

 

다만 이럴 경우 Externel Fragmentation과 Free space management라는 Segmentation의 문제가 똑같이 일어나게 됩니다.

 

그럼 어떤 방법을 사용해야 할까요?

 

Multi-level Page Tables라는 기술이 있습니다. Page Table을 Tree같은 것으로 조각내는 것이죠.

 

이렇게 될 경우 장단점이 존재하는데,

 

• Advantage
  • Memory를 아낄 수 있습니다.
    • Page Table을 여러개로 나누어 Allocate될 부분을 줄일 수 있습니다.
  • Memory를 Manage하기 쉽습니다.
    • 페이지 테이블을 저장할때 페이지 테이블이 연속적으로 저장되었어야하는데 이제 페이지테이블을 나누어 저장할 수 있습니다.
    • 이를 level of Indirection이라고 합니다.
• Disadvantage
  • Time-Space trade off : TLB miss가 나면 두번 이상 memory에 접근해야 합니다.
  • Complexity : 구현이 어렵습니다.

그런데 요즘 메모리가 커지고 있어서, 사실 많은 Page Table을 쓰지 않는 방식도 고려되고 있습니다.

 

그러니까 Physical Memory 의 사이즈 전체를 Inverted Page Table로 만들고, 그곳에서 찾은 PTE가 그냥 Physical Memory로 흘러가는 것이죠. 

 

• Advantage
  • Inverted Page Table은 Memory를 효율적으로 사용합니다. Process별 PageTable을 전부 저장할 이유가 없습니다.
  • TLB miss가 일어났을때 Memory Reference가 적습니다.
• Disadvantage
  • Hash collision 문제가 일어납니다.
    • 이로 인해서 Worst -Access Time이 될 수도 있습니다.
    • Entry의 숫자를 늘립니다. 즉 메모리 스페이스를 늘려야 합니다.
  • Page를 Share할 수 없습니다.
  • Swapping이 지원되지 않습니다.

여기서 Hash collision은 PFN을 Inverted PageTable에 더해줌으로써 해결할 수 있습니다.

그러면 PTE로 Physical Memory를 바로 알 수는 없지만, Sharing Problem역시 해결할 수 있습니다.