Advanced Page Tables

Paging : Linear Tables

 

 

We usually have one page table for every process in the system.

 

- Assume that 32-bit address space with 4KB pages and 4-byte page-table entry.

 

 

entry size가 4Byte 이므로 Page table 에 들어갈 entry 총 갯수는 다음과 같다.

 

Page table의 entry 총 갯수 = 2^12 / 2^2 = 2^10 = 1024 개 이다.

 

page table total size = 2^32 / 2^12 * 4 Byte = 4 MByte 이다.

 

즉, Page table 이 너무 커서 memory 소비가 큰 문제점이 있다.

 

 

Paging : Smaller Tables

 

 

Page tables are too big and thus consume to much memory.

 

=> Assume that 32-bit address space with 16KB pages and 4-byte page-table entry.

 

 

여기서 entry size가 4 Byte 이므로 Page 에 들어갈 entry 갯수는 다음과 같다.

 

Page entry 갯수 = 2^14 / 2^2 = 2^12 = 4096 개

 

Page table total size = 2^32 / 2^14 * 4 Byte = 2^20 Byte = 1 MB

 

page를 크게하면 internal fragmentation 이 일어난다.

 

 

 

 

Most of the page table is unused, full of invalid entries.

 

 

Hybrid Aprroach : Paging and Segments

 

 

Page table for each segment

 

- the base register for each of these segments contains the physical address of a linear page table for that segment.

 

- The bound register : indicate the end of the page table.

 

ex ) Each process has three page tables associated with it.

 

 

 

TLB miss on Hybrid Approach

 

The hardware gets physical address from page table.

 

- The hardware uses the segment bits(SN) to determine which base and bounds pair to use.

 

- The hardware then takes the physical address there in and combines it wichi the VPN

   as follows to form the address of the page table entry(PTE).

 

(1) SN = (VirtualAddress & SEG_MASK) >> SN_SHIFT

 

     32-bit Virtual address 임을 고려할 때 Segment Number를 얻기 위해서 

     SEG_MASK = 1100 0000 0000 0000 0000 0000 0000 0000  이 되야 하고

     SN_SHIFT = 30 만큼을 오른쪽으로 shift 하여 Segment Number 를 얻을 수 있다.

 

(2) VPN = (VirtualAddress & VPN_MASK) >> VPN_SHIFT

 

    VPN_MASK = 0011 1111 1111 1111 1111 0000 0000 0000  이 되야 하고

    VPN_SHIFT = 12 만큼을 오른쪽으로 shift 하여 Virtual Page Number 를 얻을 수 있다. 

   

(3) AddressOfPTE = Base[SN] + (VPN * sizeof(PTE))

 

    Page table entry의 size만큼을 Virtual Page number를 곱하여 해당 위치로 내려간 후에 

    Base[SN] 으로 Segment Number에 해당하는 Base 값을 더해준다.

 

 

Hybrid Approach is not without problems.

 

- If we have a large bur sparsely-used heap, we can still end up with a lot of page table waste.

 

- Causing external fragmentation to arise again.

 

 

Multi-level Page Tables

 

 

Turn the linear page table into something like a tree.

 

- Chop up the page table into page-sized units.

 

- If an entire page of page-table entries is invalid, don't allocate that page of the page table at all.

 

- To track whether a page of the page table is valid, use a new structure, called page directory.

 

 

Linear Page Table은 PFN 202, 203 에 대해 사용하지 않아 메모리 효율이 떨어지는 반면에

Multi-level Page Table 은 필요한 PFN 에 대해서 할당하고 그 외에는 할당하지 않는다.

 

즉, Worst case가 아니라면 (모든 PFN이 적어도 하나씩은 valid 한 경우) ?

=> Multi-level Page Table 이 Memory 효율이 좋다.

 

반면에 Linear Page Table 은 access를 한번하는 반면에 

Multi-level Page Table 은 access를 Page Directory 쪽으로 한번하고 그 후에 한번 더 access를 하여

총 2번을 access 한다.

 

즉, 시간적인 면에서는 떨어진다. 

 

 

Multi-level Page Tables

 

 

Page Directory

 

- The page directory contains one entry per page of the page table.

 

- It consists of a number of page directory entries(PDE).

 

- PED has a valid bit and page frame number(PFN).

 

Advantage

 

- Only allocates page-table space in proportion to the amount of address space you are using.

 

- The OS can grab the next free page when it needs to allocate or grow a page table.

 

Disadvantage

 

- Multi-level table is a small example of a time-space trade off.

 

- Complexity.

 

 

 

Single level paging

 

 

 

 

 

Single level paging 

 

- 256 page table entries : 2^8 entries

 

- Page table size : 256 * 4 byte = 1 KB

 

- page 개수는 page size가 64 byte이므로 2^10 / 2^6 = 2^4 = 16 개 이다.

 

 

 

Two level Paging

 

 

Page directory index

 

- A page table consists of 16 pages.

 

- 16 entries for page directory : one entry per page of the page table.

 

- 16 * 4 byte = 64 byte is required for page directory.  => it can fit in a page.

 

- 4 bits for page directory index.

 

- If the page-directory entry is invalid, raise an exception.

 

 

 

More than Two Levels

 

 

In some cases, a deeper tree is required.

 

Consider the following address space.

 

 

Number of pages in a page table.

 

- 2^21 page table entries.

 

- PTE 갯수 = page size / 4 = 2^9 / 4 = 2^7 = 128 

 

-  21 bit 중에 7 bit 을 PTE 에 대해서 사용하고 있으므로 나머지 14 bit 에 대해서

    Number of page directory entries : 2^14 가 된다.

 

 

 

More than Two Level : Page Directory

 

 

Two level page table 에 대해서 생각을 해보자.

 

Page Directory 가 valid한 page table (valid한 PFN를 point 하는) 을 point 하는 그림을 상상할 수 있다.

 

그렇다면 Three level page table 에서 Page Directory 가 Page table로 교체가 되면서 교체가 된 page table 을 또 다시 point 하도록 하면 어떨까? 라는 동일한 방법이 적용이 된다.

 

The number of pages in a page directory : 2^14 / 2^7 = 2^7 (128)

 

Three level page table 에서 만들어진 page directory 의 entry 갯수가 128 개다.

 

그렇다는 이야기는? Page directory 가 point 하고 있는 page table(two level 에서는 directory 였던) 의 entry 갯수 또한 2^7 = 128 개라는 소리다.

 

즉 2^7 개의 page Directory의 entry 가 2^7 개의 page table 의 entry 를 point 하고 거기서 또 2^7 개의 page table 의 page entry 를 point 하여 최종적으로 valid 한 PFN 를 point 하는 3번의 access 과정이 일어난다.

 

굉장한 Memory 효율을 얻을 것 같다. (Worst case가 아닌 이상?)

 

하지만 access가 늘은 만큼 시간적인 면에서 떨어질 것이다.

 

 

 

 

Multi-level Page Table Control Flow

 

VPN = (VirtualAddress & VPN_MAKS) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if(Success == true){
    if(CanAccess(TlbEntry.ProtectBits) == true){
        offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | OFFSET
        Register = AccessMemory(PhysAddr)
    } else RaiseException(PROTECTION_FAULT)
else{
    PDIndex = (VPN & PD_MASK) >> PD_SHIFT
    PDEAddr = PDBR + (PDIndex * sizeof(PDE))
    PDE = Accessmemory(PDEAddr)
    if(PDE.Valid == false) 
        RaiseException(SEGMENTATION_FAULT)
    else{
        PTIndex = (VPN & PT_MASK) >> PT_SHIFT
        PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))
        PTE = AccessMemory(PTEAddr)
        if(PTE.Valid == false)
            RaiseException(SEGMENTATION_FAULT)
        else if(CanAccess(PTE.ProtectBits) == false)
            RaiseException(PROTECTION_FAULT)
        else{
            TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
            RetryInstruction()
        }
    }
}

 

 

Exercise ) 

 

64 bits logical address, 32 KB page, 4 Byte page table entry 가 존재한다.

 

How many bits for page offset?

=> 32 KB = 2^5 * 2^10 Byte = 2^15 byte

     따라서 15 bits 이고     010 1101 0100 0011 와 같이 표기할 수 있겠다.

 

How many page table entries in each page?

=> 2^15 / 2^2 = 2^13, 따라서 2^13 개 존재한다.

 

 

Inverted Page Tables

 

 

Keeping a single page table that has an entry for each physical page of the system.

 

The entry tells us which process is using this page, and which virtual page of that process maps to this physical page.

 

 

Inverted Page Tables