Translation Lookaside Buffer & Inverted Page Table

Operating System. Page table.

1. G.H.PATEL COLLEGE OF
ENGINEERING & TECH
Prepared By::
Darshit Metaliya (130110107020)
Gujarat technological University

2. TRANSLATION
LOOKASIDE BUFFER
Each virtual memory reference can cause two physical
memory accesses
One to fetch the page table.
One to fetch the data.
To overcome this problem a high-speed cache is set up for
page table entries Called a Translation Lookaside Buffer
(TLB).
Given a virtual address, processor examines the TLB.

3. TRANSLATION
LOOKASIDE BUFFER
If page table entry is present (TLB hit), the frame number is
retrieved and the real address is formed.
If page table entry is not found in the TLB (TLB miss), the
page number is used to index the process page table.
First checks if page is already in main memory .
If not in main memory a page fault is issued,
The TLB is updated to include the new page entry.

4. VIRTUAL-TO-PHYSICAL
LOOKUPS
Programs only know virtual addresses
The page table can be extremely large
Each virtual address must be translated
May involve walking hierarchical page table
Page table stored in memory
So, each program memory access requires several actual memory
accesses
Solution: cache “active” part of page table
Use a translation lookaside buffer (TLB)
TLB is an “associative mapping”; hence, the processor can query in
parallel the TLB entries to determine if there is a match
TLB works like a memory cache and it exploits “principle of locality”

5. TRANSLATION
LOOKASIDE BUFFER
(TLB)
offset
Virtual address
.
.
.
PPage#...
PPage#...
PPage#...
PPage # offset
Physical address
VPage #
TLB
Hit
Miss
Page
table
VPage#
VPage#
VPage#
Note that each TLB entry must
include the virtual page # as
well as the corresponding PTE

6. TLB FUNCTION
If a virtual address is presented to MMU, the hardware checks
TLB by comparing all entries simultaneously (in parallel).
If match is valid, the frame # is taken from TLB without going
through page table.
If a match is not found
MMU detects miss and does a regular page table lookup.
It then evicts one old entry out of TLB and replaces it with the new
one, so that next time that page is found in TLB.

7. Valid bit indicates whether page is in use or not
TRANSLATION LOOKASIDE
BUFFER

8. SOFTWARE TLB MANAGEMENT
1.Risc machines manage TLB in software
2.TLB fault processed by OS instead of by MMU
hardware
3.Results less hardware in MMU and OK
performance
4.Software can figure out which pages to pre-load
into TLB (eg. Load server after client request)
5.Keeps cache of frequently used pages

9. As the size of virtual memory address space grows, additional levels must be
added to multilevel page tables to avoid that the root page table becomes too
large
Assuming 64-bits address space, 4-Kb page size, and a PTE of 4 bytes, each
page table can store 1024 entries, or 10 bits of address space. Thus é52/10ù=
6 levels are required or 6 memory accesses for each address translation
However, size of physical memory is much smaller; hence, the idea of
inverted page table can be exploited
The number of entries in the inverted page table is equal to the number of
physical memory frames
Inverted Page Tables

10. Consider a simple inverted page table
There is one entry per physical memory frame
The table is now shared among the processes, so each PTE must contain the
pair <process ID, virtual page #>
Physical frame # is not stored, since the index in the table corresponds to it
In order to translate a virtual address, the virtual page # and current process ID
are compared against each entry, scanning the array sequentially.
If a match is found, its index (in the inverted page table) is used to obtain a
physical address.
If no match is found, a page fault occurs.
The search can be very inefficient since finding a match may require
searching the entire table. To speed-up the searching, hashed inverted page
tables are used
Inverted Page Tables