P3L2 Memory Management - Page Table Size Flashcards
In a 32-bit architecture, how many different addresses into physical memory can you have?
Since the address can have 32 bits, you can have up to 2^32 different addresses.
In a 32-bit architecture, with page size 4K, calculate the number of VPNs.
i.e how many entries would you need in the page table?
- 2^32 different addresses.
- Divide by blocks of 4K, 4k is 2^12
- So ..2^32/2^12 —-> 2^20 entries
In a 64-bit architecture, with page size 4K, where each page table entry is 64 bits (8 bytes), calculate the total size of the page table
- 2^64 different addresses.
- Divide by blocks of 4K (2*2*2^10), 4k is 2^12
- So ..2^64/2^12 —-> 2^52 entries
- Multiply by size of entry —> 8* 2^52 bytes —> 2^55 or 2^5 PB,
- That’s 32 PB !!
In a 32-bit architecture, with page size 4K, where each page table entry is 32 bits (4 bytes), calculate the total size of the page table
- 2^32 different addresses.
- Divide by blocks of 4K, 4k is 2^12
- So ..2^32/2^12 —-> 2^20 entries
- Multiply by size of entry —> 4* 2^20 bytes —> 2 ^22 or 4MB
Review for quick calculations:
Kb is 2^____
Mb is 2^____
Gb is 2^_____
Tera byte is 2^____
Peta byte is 2^____
KB - 2^10
MB - 2^20
GB - 2^30
TB - 2^40
PB - 2^50
Describe Hierarchical page tables. How do they use less memory?
The outer level is referred to as a page table directory. Its elements are not pointers to individual page frames, but rather pointers to page tables themselves.
The inner level has proper page tables that actually to point to page frames in physical memory. Their entries have the page frame number and all the protection bits for the physical addresses that are represented by the corresponding virtual addresses.
The internal page tables exist only for those virtual memory regions that are actually valid. Any holes in the virtual memory space will result in lack of internal page tables.
![](https://s3.amazonaws.com/brainscape-prod/system/cm/283/256/244/a_image_thumb.png?1564386982)
Hierarchical page table
If a process requests more memory to be allocated to it via malloc the OS will check and potentially create another ________________ for the process, adding a new entry in the _______________________.
If a process requests more memory to be allocated to it via malloc the OS will check and potentially create another page table for the process, adding a new entry in the page table directory.
Virtual address with 2 layer hierarchical page table
- The first portion indexes into the __________________ to get the page table
- The second portion indexes into the _____________ to get the PFN.
- The last part of the logical address is still the ___________, which is used to actually index into the physical page frame.
Virtual address with 2 layer page table
- The first portion indexes into the page table directory to get the page table
- The second portion indexes into the page table to get the PFN.
- The last part of the logical address is still the offset, which is used to actually index into the physical page frame.
What is the advantage of adding more levels to a hierarchical page table?
As we add more levels, the internal page tables/directories end up covering smaller regions of the virtual address space.
As a result, it is more likely that the virtual address space will have gaps that will match that granularity, and we will be able to reduce the size of the page table as a result.
What is the disadvantage of adding more levels to the hierarchical page table?
More memory accesses required for translation, since we will have to access more page table components before actually accessing the physical memory. Therefore, the translation latency will be increased.
Multi-level page table quiz
A process with 12 bit architecture has an address space where only the first 2Kb and the last 1Kb is used.
- Given 6 bits for the page number, how many entries are there in the single level page table?
- Given 2 bits for the directory table and 4 bits for the inner page table, and considering the sparse usage:
- How many inner page tables are needed?
- How many inner page table entries are needed?
- 2^6 –> 64 entries
- Given 2 bits for the directory table and 4 bits for the inner page table, and considering the sparse usage:
- 3 inner tables
- 3 * 2^4 —> 3*16 = 48 total entries
In a four-level page table, we will need to perform _____ memory accesses:
- Need to perform ______ accesses to navigate through the page table entries, and ____ access to reach the physical memory.
In a four-level page table, we will need to perform __5___ memory accesses.
- Need to perform ___4___ accesses to navigate through the page table entries, and __1__ access to reach the physical memory.
In most architectures, the MMU integrates a hardware _______ to store address translations.
This cache is called the_________________________________
If we have a TLB miss, we still need to perform the multi-level page ____________.
Even a small number of addresses cached in TLB can result in a ______ TLB hit rate because we usually have ___________ and ________ locality in memory references.
In most architectures, the MMU integrates a hardware cache to store address translations and by-pass multi-level page table navigation.
This cache is called the translation lookaside buffer (TLB).
If we have a TLB miss, we still need to perform the multi-level page navigation /lookups
Even a small number of addresses cached in TLB can result in a high TLB hit rate because we usually have a high temporal and spatial locality in memory references.
True or False?
- On modern x86 platforms, a 64-entry data TLB and 128-entry instruction TLB per core is enough to reduce multi-level page lookup latency.
- A 2nd level TLB shared accross cores can be even smaller.
- TRUE: On modern x86 platforms, there is a 64-entry data TLB and 128-entry instruction TLB per core,
- FALSE: as well as a shared 512-entry shared second-level TLB.
True or False?
The type of address translation that is possible on a particular platform is determined by the operaing system’s segmentation algorithm.
FALSE: The type of address translation that is possible on a particular platform is determined by the hardware.
- Intel x86_32 platforms support segmentation and paging.
- Linux supports up to 8K segments per process and another 8K global segments.
- Intel x86_64 platforms support segmentation for backward compatibility, but the default mode is to use just paging.