Transcript inverted page table

Operating Systems
COMP 4850/CISG 5550
Page Tables
TLBs
Inverted Page Tables
Dr. James Money
Paging
Page Tables
• In the simplest cases, mapping of virtual
addresses happens as we have described
• The virtual address is split into lower and
higher order bits
• The higher order bits are grouped into a
page number
• Splits might be of 3 or 5 bits instead of 4
Page Tables
• The virtual page number is used as an
index into the page table
• From the entry in the page table, the page
frame number is found
• The page frame number is attached to the
high order bits to determine the physical
address
Page Tables
• The main purpose of the page table is to
map virtual addresses to physical
addresses
• Mathematically the page table is a
function that takes a virtual page number
and returns a physical frame number
Page Tables
• There are two major issues to address
– The page table can grow to be extremely
large
– The mapping of addresses must be fast
Page Tables
• The reason for large page tables is b/c most
•
•
•
computers have at least 32 bits and many now
have 64
With a 4KB page size, a 32 bit address space
has 1 million pages
With a 64 bit address space, there are more
than one can imagine
Typically each process has its own page table
with it’s own virtual address space
Page Tables
• The second point is needed b/c we do the
virtual-to-physical mapping must be done
with every memory reference
• Many times there are 1,2, or memory
references per instruction
• If an instruction takes 4 nsec, the lookup
must not exceed 1 nsec
Page Tables
• The simplest design is to have the table as
an array of fast hardware registers with an
entry for each virtual page
• This requires no memory references
during mapping
• This problem is this can be
expensive($$!!) and slow with a context
switch
Page Tables
• The other end is to have the entire page
table in memory
• There is a single register that points to
start of the table
• Easy for a context switch
• Needs memory references to read page
table
Multilevel Page Tables
• Many computers use a multilevel page
system to alleviate the problem
• The basic idea is a two level tree with the
top level being reference to leaf nodes
with an array of page entries
• We partition the 32 bit virtual address into
a PT1 field, a PT2 field, and the Offset
field
Multilevel Page Tables
Multilevel Page Tables
• The idea is to not keep all the leaf page
tables in memory when they are not
needed
• A page fault occurs when the top level
entry has the Present bit is clear
• Either this is an illegal address or we need
to allocate more pages to the process
• We can extend this scheme to three or
four levels
Multilevel Page Tables
• For example, consider referencing the
virtual address 0x00403004
• This corresponds to PT1=1, PT2=2, and
Offset=4
• The MMU uses PT1 as an index into the
top level table and PT2 as the index into
the appropriate second level table
Page Table Entries
• We consider now the structure of a single
entry for a page table
• This is highly machine dependent, but
roughly the same from machine to
machine
• A common size for an entry is 32 bits
Page Table Entries
• The field contains
– Page frame number
– Present/absent bit
– Protection – what kind of access is permitted
– Modified/Referenced – keeps track of writes
and read to a page frame
– Caching disabled
Page Table Entries
Page Table Entries
• Note the disk address to hold the page is
not in memory or part of the page table
• This is b/c the OS handles this information
internally in its software tables
• The page table only has to hold
information on virtual -> physical
mappings for processes
TLBs
• Most paging systems keep page tables in
memory due to their large size
• In register to register instructions, there is
no paging hit
• Since the rate of the memory access is the
limiting factor, making two references
reduces performance by 2/3
TLBs
• The solution is based on the fact there are
a large number of close by memory
references
• This results in a little number of page
references
• The rest are used rarely
TLBs
• The solution is to equip a device to handle
the mapping without going through the
page table
• This device is called the Translation
Lookaside Buffer (TLB) or associate
memory
• This is kept inside the MMU and has a
small number of entries(8-64)
TLBs
TLBs
• How does this work?
• The MMU first looks in the TLB by
comparing all entries simultaneously
• If an entry is found and the protection is
appropriate, then the entry is used
without going to the page table
• If there is a protection problem, then a
protection fault is issued
TLBs
• If the entry is not in the TLB, the MMU
does a normal page lookup
• It replaces an entry in the TLB with the
page lookup just issued
• If that page is used again, then it will read
the page frame from the TLB
Software TLB Management
• So far the management of the TLB has
been done by the MMU itself
• This was true in the past
• Many modern RISC CPUs do this
management in software
• On these systems, a TLB fault is issued for
handling the TLB miss
Software TLB Management
• The OS needs to find the page table entry,
evict the least used one, and load the new
TLB entry
• This has to be done fast since there are
many TLB misses to a page fault
• If the TLB size is large(64), then there is
no problem b/c the misses are far in
between
Inverted Page Tables
• With 32 bit computers, with 4KB page
size, a full table might require 4MB
• This can be a problem on 64 bit address
systems
• We now need 252 entries
• If each entry is 8 bytes, we need to use
30 million gigabytes
Inverted Page Tables
• We need a different solution
• One solution is called an inverted page
table
• In this design, there is one entry per page
frame in real memory rather than one
entry per virtual page
• In the same scenario with 256MB of RAM,
we need only 65536 entries
Inverted Page Tables
• Each entry keeps track of which
(process,virtual page) belongs to the
frame
• Now the virtual to physical mapping is
hard to perform
• When a process references virtual page p,
it must search the inverted page table for
an entry of the form (n,p)
Inverted Page Tables
• The way around this again it to use the
TLB
• When the TLB holds the heavily used
pages, then this work happens as fast as
regular page tables
• However, on a miss, the search must be
done in software
Inverted Page Tables
• One way to do this search is to use a hash
table with chaining
• If the hash table has as many entries as
frames, then the chains will only have one
entry each
• Once the entry is found, the entry is put in
the TLB
Inverted Page Tables