Transcript class slides

Virtual Memory
Operating Systems
Fall 2002
OS Fall’02
Paging and Virtual Memory
 Paging makes virtual memory possible
Logical to physical address mapping is
dynamic
Processes can be broken to a number of
pages that need not be mapped into a
contiguous region of the main memory
=> It is not necessary that all of the
process pages be in main memory during
execution
OS Fall’02
How does this work?
 CPU can execute a process as long as
some portion of its address space is
mapped onto the physical memory
E.g., next instruction and data addresses are
mapped
 Once a reference to an unmapped page
is generated (page fault):
Put the process into blocking state
Read the page from disk into the memory
Resume the process
OS Fall’02
Benefits
 More processes may be maintained in the
main memory
Better system utilization
 The process size is not restricted by the
physical memory size: the process
memory is virtual
But what is the limit anyway?
OS Fall’02
Why is this practical?
 Observation: Program branching and data
access patterns are not random
 Principle of locality: program and data
references tend to cluster
=> Only a fraction of the process virtual
address space need to be resident to
allow the process to execute for
sufficiently long
OS Fall’02
Virtual memory implementation
 Efficient run-time address translation
Hardware support, control data structures
 Fetch policy
Demand paging: page is brought into the
memory only when page-fault occurs
Pre-paging: pages are brought in advance
 Page replacement policy
Which page to evict when a page fault
occurs?
OS Fall’02
Thrashing
 A condition when the system is engaged
in moving pages back and forth between
memory and disk most of the time
 Bad page replacement policy may result
in thrashing
 Programs with non-local behavior
OS Fall’02
Address translation
 Virtual address is divided into page
number and offset
Virtual Address
Page Number
Offset
 Process page table maintains mappings
of virtual pages onto physical frames
Each process has its own unique page table
OS Fall’02
Forward-mapped page tables (FMPT)
 Page table entry
P M Other Control Bits
(PTE) structure
Frame Number
P: present bit
M: modified bit
Page Table
 Page table is an array
of the above
Page #
Index is the virtual
page number
Frame #
OS Fall’02
Address Translation using FMPT
Virtual address
Page #
Offset
Frame # Offset
Register
Page Table Ptr
Page Table
Offset
+
P#
Frame #
Program
Paging
OS Fall’02
Main Memory
Page
Frame
Handling large address spaces
 One level FMPT is not suitable for large
virtual address spaces
32 bit addresses, 4K (212) page size, 232 / 212
= 220 entries ~4 bytes each =>
4Mbytes resident page table per process!
What about 64 bit architectures??
 Solutions:
multi-level FMPT
Inverted page tables (IPT)
OS Fall’02
Multilevel FMPT
 Use bits of the virtual address to index a
hierarchy of page tables
 The leaf is a regular PTE
 Only the root is required to stay resident
in main memory
Other portions of the hierarchy are subject to
paging as regular process pages
OS Fall’02
Two-level FMPT
page number
pi
10
page offset
p2
10
d
12
OS Fall’02
Two-level FMPT
OS Fall’02
Inverted page table (IPT)
 A single table with one entry per physical
page
 Each entry contains the virtual address
currently mapped to a physical page (plus
control bits)
 Different processes may reference the
same virtual address values
Address space identifier (ASID) uniquely
identifies the process address space
OS Fall’02
Address translation with IPT
 Virtual address is first indexed into the
hash anchor table (HAT)
 The HAT provides a pointer to a linked list
of potential page table entries
 The list is searched sequentially for the
virtual address (and ASID) match
 If no match is found -> page fault
OS Fall’02
Address translation with IPT
Virtual address
page number
register
offset
frame number
HAT
ASID
ASID
page number
+
hash
Frame#
+
IPT base
HAT base
register
register
OS Fall’02
IPT
Translation Lookaside Buffer (TLB)
 With VM accessing a memory location
involves at least two intermediate
memory accesses
Page table access + memory access
 TLB caches recent virtual to physical
address mappings
ASID or TLB flash is used to enforce
protection
OS Fall’02
TLB internals
 TLB is associative, high speed memory
Each entry is a pair (tag,value)
When presented with an item it is compared
to all keys simultaneously
If found, the value is returned; otherwise, it
is a TLB miss
Expensive: number of typical TLB entries:
64-1024
Do not confuse with memory cache!
OS Fall’02
Address translation with TLB
OS Fall’02
Bits in the PTE: Present (valid)
 Present (valid) bit
Indicates whether the page is assigned to
frame or not
Invalid page can be not a part of any
memory segment
A reference to an invalid page generates
page fault which is handled by the operating
system
OS Fall’02
Bits in PTE: modified, used
 Modified (dirty) bit
Indicates whether the page has been
modified
Unmodified pages need not be written back
to the disk when evicted
 Used bit
Indicates whether the page has been
accessed recently
Used by the page replacement algorithm
OS Fall’02
Bits in PTE
 Access permissions bit
indicates whether the page is read-only or
read-write
 UNIX copy-on-write bit
Set whether more than one process shares a
page
If one of the processes writes into the page,
a separate copy must first be made for all
other processes sharing the page
Useful for optimizing fork()
OS Fall’02
Protection with VM
 Preventing processes from accessing
other process pages
 Simple with FMPT
Load the process page table base address
into a register upon context switch
 ASID with IPT
OS Fall’02
Segmentation with paging
 Segmentation
simplifies protection and sharing, enforce
modularity, but prone to external
fragmentation
 Paging
transparent, eliminates ext. fragmentation,
allows for sophisticated memory management
 Segmentation and paging can be
combined
OS Fall’02
Address translation
Seg #
Page #
Frame #
Offset
Offset
Seg Table Ptr
Segment
Table
Page Table
Offset
P#
S#
+
Program
+
Segmentation
Paging
OS Fall’02
Main Memory
Page
Frame
Page size considerations
 Small page size
better approximates locality
large page tables
inefficient disk transfer
 Large page size
internal fragmentation
 Most modern architectures support a
number of different page sizes
 a configurable system parameter
OS Fall’02
Next: Page replacement
OS Fall’02