Page Table
A page table helps us to do Address Translation, mapping virtual addresses to physical addresses (these are then used to access main memory data).
Each virtual memory reference can cause two physical memory accesses
- One to fetch the page table entry
- One to fetch the data
In SE350, we introduce the simplest forms of paging, and then show more and more complex ones.
1 page table or multiple?
In most systems, there is one page table per process.
See Virtual Address
Simple Page Table
We start off with the most basic Paging, where we translate a virtual address into a physical address by looking at the page number and figuring out the frame number.
Disadvantages
In this implementation, the page table resides in RAM. Page tables will eat all your RAM! (e.g. 4MB of page tables per process for 4GB RAM)
Why isn't secondary memory included in this diagram?
You’ll see it later for the TLB, but it should also be here??
Two-Level Hierarchical Page Table
Therefore, the idea is to put some of the page tables in virtual memory too! We thus have a two-level hierarchical page table.
Below is a diagram of how we actually do address translation:
Inverted Page Table
Page table size is proportional to the virtual address space.
Alternative:
- Inverted page table: use a hash table.
Page Table + Translation-Lookaside Buffer
What do you do when a system is too slow? We can add caches! That is what we do using a Translation-Lookaside Buffer.
This diagram explains the underlying mechanisms.
Segmentation/Paging System
- Paging is transparent to the programmer
- Segmentation (Memory) is visible to the programmer
- Elements:
- 1 process
- 1 segment table per process
- 1 page table per segment
So we can combine both the segment number and the page number in the Virtual Address.
This is how we do address translation
Multi-Level Page Table Example
Given 8-bit virtual address space, main memory of 64B, page size of 4B, and page table entry size of 1B. Find the size of VPN, PPN, PO. How many levels of multi-level page table are needed?
- page size vs page table size???
The PO is determined by the page size.
- → PO = 2bits
Since the virtual address is 8 bits, we have that
- virtual address size = VPN + PO → VPN = 8 - 2 = 6 bits
How do we find the PPN? We know that the main memory is 64B. We do main memory size / page size to determine how many pages in memory we can fit:
- pages → PPN = 4 bits to index into page
To figure out how many Multi-Level Page Table we need, we look that the page-table entry size, which is 1B:
- page table size / page table entry size = 4B / 1B = 4 = entries in page table→ 2 bits to index into entry
- Since our VPN is 6 bits, then 6/2 = 3 entries