Abstract
- Maintains mappings between Memory Page and the Memory Frames. The mappings are stored inside the Main Memory, we can use TLB to reduce the number of memory access since memory access is an expensive operation
Why doesn't one virtual address simply map to one physical address?
Because this would make our page table too large! We would need one entry in the page table to keep track of each individual address. With memory pages, we can have one entry to keep track of 4096 addresses if the page size is
4KB.
Different process different page table
Separate page tables allow us to isolate processes, preventing them from accessing each other’s data, while still providing the flexibility for controlled data sharing when necessary. For example, refer to the virtual memory implementation in Linux.
Page Table Entry
- A mapping of memory page and memory frame in the page table
Page Table Address Translation
- The above diagram assumes the Memory Page and the Memory Frames are
4kb. The TLB is part of MMU that handles the mapping - As you can see, the value in the mapping ignores the last 12 Bit which is known as the page offset. The same memory page number share the same memory frame number
Multi-level Page Table
- For a 32-bit machine with 4kB () pages, we need a total of 1M () PTEs to map all virtual addresses to physical addresses. Each PTE is about 4 bytes, so we need a total of 4MB of memory for the page table
- Each program needs it s own page table, so if we have 100 programs, we need a total of 400MB of main memory to store the pages table. And we can’t place the pages table to swap space. If the page table not in main memory, we have no way to access it to find it
Solution: Add a Second-Level Page Table
To map the full 1M () physical addresses of a 32-bit machine, we can use a two-level page table structure. The first-level page table, with a size of () entries, points to second-level page tables, each also containing () PTEs.
The second-level page tables can be paged out to swap space when not in use, as they can be located through the first-level table, which is always kept in main memory.
This approach significantly reduces the minimum amount of page table data needed in memory for each process. It requires only 4kB for the first-level table and 4kB for one active second-level table (8kB total) to obtain a physical address, a substantial improvement over the 4MB of main memory consumed per application when using a single-level page table.
How does virtual-to-physical address translation work?
- First-Level Page Table Lookup: The first 10 bits of the virtual address are used as an index to locate the corresponding PTE in the first-level page table.
- Page Table Entry (PTE) Retrieval: The retrieved PTE contains the physical address of the second-level page table that holds the final translation.
- Second-Level Page Table Lookup: The next 10 bits of the virtual address are used as an index into this second-level page table.
- Physical Address Retrieval: The PTE in the second-level page table provides the physical address of the desired data.
