Transcript Paging (Review and continuation)

Paging
(Review and Continuation)
CS-502, Operating Systems
Fall 2009 (EMC)
(Slides include materials from Modern Operating Systems, 3rd ed., by Andrew Tanenbaum and from
Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne)
CS-502 (EMC) Fall 2009
Paging
1
Review
• Virtual Address
• Address space in which the process “thinks”
• Each virtual address is translated “on the fly” to a
physical address
• Fragmentation
• Internal fragmentation – unused within an allocation
• External fragmentation – unused between allocations
CS-502 (EMC) Fall 2009
Paging
2
Paging
CS-502 (EMC) Fall 2009
Paging
3
physical memory
frame 0
frame 1
frame 2
…
…
• Use small fixed size units
in both physical and
Logical Address Space
virtual memory
(virtual memory)
• Provide sufficient MMU
page 0
hardware to allow page
units to be scattered across
page 1
memory
page 2
• Make it possible to leave
MMU
page 3
infrequently used parts of
virtual address space out
page X
of physical memory
• Solve internal & external
fragmentation problems
frame Y
Paging Translation
logical address
virtual page #
offset
physical memory
page
frame 0
page
frame 1
page
frame 2
page
frame 3
page table
physical address
F(PFN)
offset
…
page frame #
page
frame Y
CS-502 (EMC) Fall 2009
Paging
4
Generic PTE Structure
1 1 1
2
V R M
prot
20
page frame number
• Valid bit gives state of this Page Table Entry (PTE)
– says whether or not its virtual address is valid – in memory and VA range
– If not set, page might not be in memory or may not even exist!
• Reference bit says whether the page has been accessed
– it is set by hardware whenever a page has been read or written to
• Modify bit says whether or not the page is dirty
– it is set by hardware during every write to the page
• Protection bits control which operations are allowed
– read, write, execute, etc.
• Page frame number (PFN) determines the physical page
– physical page start address
• Other bits dependent upon machine architecture
CS-502 (EMC) Fall 2009
Paging
5
Steps in Handling a Page Fault
CS-502 (EMC) Fall 2009
Paging
6
Definitions and Observations
• Recurring themes in paging
– Temporal Locality – locations referenced
recently tend to be referenced again soon
– Spatial Locality – locations near recent
references tend to be referenced soon
• Definitions
– Working set: The set of pages that a process
needs to run without frequent page faults
– Thrashing: Excessive page faulting due to
insufficient frames to support working set
CS-502 (EMC) Fall 2009
Paging
7
Paging Issues
• #1 — Page Tables can consume large amounts of space
– If PTE is 4 bytes, and use 4KB pages, and have 32 bit VA space 
4MB for each process’s page table
• Stored in main memory!
– What happens for 64-bit logical address spaces?
• #2 — Performance Impact
– Converting virtual to physical address requires multiple operations
to access memory
•
•
•
•
Read Page Table Entry from memory!
Get page frame number
Construct physical address
Assorted protection and valid checks
– Without fast hardware support, requires multiple memory accesses
and a lot of work per logical address
CS-502 (EMC) Fall 2009
Paging
8
Issue #1: Page Table Size
• Process Virtual Address spaces
– Not usually full – don’t need every PTE
– Processes do exhibit locality – only need a subset of the
PTEs
• Two-level page tables
• I.e., Virtual Addresses have 3 parts
– Master page number – points to secondary page table
– Secondary page number – points to PTE containing
page frame #
– Offset
• Physical Address = offset + startof (PFN)
CS-502 (EMC) Fall 2009
Paging
9
Two-level page tables
12 bits
8 bits
12 bits
virtual address
master page #
secondary page#
offset
physical memory
master
page table
physical address
page frame #
secondary
page table # addr
page
frame 0
page
frame 1
offset
secondary
page table #
page
frame 2
page frame
number
CS-502 (EMC) Fall 2009
n-level page tables
common in 64-bit
systems
Paging
10
…
page
frame 3
page
frame Y
Paging Issues
• Minor issue – internal fragmentation
– Memory allocation in units of pages (also file allocation!)
• #1 — Page Tables can consume large amounts of space
– If PTE is 4 bytes, and use 4KB pages, and have 32 bit VA space ->
4MB for each process’s page table
– What happens for 64-bit logical address spaces?
• #2 — Performance Impact
– Converting virtual to physical address requires multiple operations
to access memory
•
•
•
•
Read Page Table Entry from memory!
Get page frame number
Construct physical address
Assorted protection and valid checks
– Without fast hardware, requires multiple memory accesses and a
lot of work per logical address
CS-502 (EMC) Fall 2009
Paging
11
Solution — Associative Memory
aka Dynamic Address Translation — DAT
aka Translation Lookaside Buffer — TLB
VPN #
•
•
•
PTE
Do fast hardware search of all entries in parallel for VPN
If present, use page frame number from PTE directly
If not,
a) Look up in page table (multiple accesses)
b) Load VPN and PTE into Associative Memory (throwing out
another entry as needed)
CS-502 (EMC) Fall 2009
Paging
12
Translation Lookaside Buffer (TLB)
• Associative memory implementation in hardware
– Translates VPN to PTE (containing PFN)
– Done in single machine cycle
• TLB is hardware assist
– Fully or partially associative – entries searched in
parallel with VPN as index
– Returns page frame number (PFN)
– MMU use PFN and offset to get Physical Address
• Locality makes TLBs work
– Usually have 8–1024 TLB entries
– Sufficient to deliver 99%+ hit rate (in most cases)
• Works well with multi-level page tables
CS-502 (EMC) Fall 2009
Paging
13
MMU with TLB
CS-502 (EMC) Fall 2009
Paging
14
Typical Machine Architecture
Memory
Memory
Memory
I/O device
CS-502 (EMC) Fall 2009
CPU
MMU and TLB
live here
Bridge
Graphics
I/O device
Paging
I/O device
I/O device
15
TLB-related Policies
• OS must ensure that TLB and page tables are consistent
– When OS changes bits (e.g. protection) in PTE, it must invalidate
TLB copy
– Dirty bit and reference bits in TLB must be written back to PTE
• TLB replacement policies
– Random
– Least Recently Used (LRU) – with hardware help
• What happens on context switch?
–
–
–
–
Each process has own page tables (possibly multi-level)
Must invalidate all TLB entries
Then TLB fills up again as new process executes
Expensive context switches just got more expensive!
• Note benefit of Threads sharing same address space
CS-502 (EMC) Fall 2009
Paging
16
Questions?
CS-502 (EMC) Fall 2009
Paging
17
Alternative Page Table format – Hashed
• Common in address spaces > 32 bits.
• The virtual page number is hashed into a
page table.
• Each entry contains a chain of VPN’s with same
hash.
• Search chain for match
• If found, use associated PTE
• Still needs TLB for performance
CS-502 (EMC) Fall 2009
Paging
18
Hashed Page Tables
CS-502 (EMC) Fall 2009
Paging
Advantage:– shorter, denser
page tables
Disadvantage:– TLB faults
trap to software for loading
(implies larger19 TLB)
Alternative Page Table format – Inverted
• One entry for each real page of memory.
• Entry consists of virtual address of page stored at
that real memory location, with information about
the process that owns that page.
• Decreases memory needed to store each page
table, but increases time needed to search the table
when a page reference occurs.
• Use hash table to limit the search to one or a few
page-table entries.
• Still uses TLB to speed up execution
CS-502 (EMC) Fall 2009
Paging
20
Inverted Page Table Architecture
Advantage:– smallest possible
page tables; all processes
share one set of page tables
Disadvantage:– same as hashed
See also Tanenbaum, Fig 3-14
page tables 21
CS-502 (EMC) Fall 2009
Paging
Inverted Page Table Architecture (cont’d)
• Apollo Domain systems
• Common in 64-bit address systems
• Supported by TLB
• Next topic helps to quantify size of TLB
CS-502 (EMC) Fall 2009
Paging
22
Paging – Some Tricks
• Shared Memory
– Part of virtual memory of two or more
processes map to same frames
• Finer grained sharing than segments
• Data sharing with Read/Write
• Shared libraries with eXecute
– Each process has own PTEs – different
privileges
CS-502 (EMC) Fall 2009
Paging
23
Shared Pages (illustration)
CS-502 (EMC) Fall 2009
Paging
24
Paging trick – Copy-on-write (COW)
• During fork()
– Don’t copy individual pages of virtual memory
– Just copy page tables; all pages start out shared
– Set all PTEs to read-only in both processes
• When either process hits a write-protection fault
on a valid page
– Make a copy of that page, set write protect bit in PTE to
allow writing
– Resume faulting process
• Saves a lot of unnecessary copying
– Especially if child process will delete and reload all of
virtual memory with call to exec()
CS-502 (EMC) Fall 2009
Paging
25
Definition — Mapping
• Mapping (a part of) virtual memory to a file =
• Connecting blocks of the file to the virtual
memory pages so that
– Page faults in (that part of) virtual memory
resolve to the blocks of the file
– Dirty pages in (that part of) virtual memory are
written back to the blocks of the file
CS-502 (EMC) Fall 2009
Paging
26
Warning — Memory-mapped Files
• Tempting idea:–
– Instead of standard I/O calls (read(), write(),
etc.) map file starting at virtual address X
– Access to “X + n” refers to file at offset n
– Use paging mechanism to read file blocks into
physical memory on demand …
– … and write them out as needed
• Has been tried many times
• Rarely works well in practice
CS-502 (EMC) Fall 2009
Paging
27
Virtual Memory Organization
0xFFFFFFFF
stack
(dynamically allocated)
SP
Virtual
address space
heap
(dynamically allocated)
static data
0x00000000
CS-502 (EMC) Fall 2009
program code
(text)
Paging
PC
28
Virtual Memory Organization
Map to writable
swap file
Unmapped, may be
dynamically mapped
stack
(dynamically allocated)
SP
guard page (never mapped)
Map to writable
swap file
heap
(dynamically allocated)
Map to writable
swap file
static data
Mapped to read-only
executable file
CS-502 (EMC) Fall 2009
program code
& constants
Paging
PC
29
Virtual Memory Organization (continued)
thread 1 stack
Map to writable
swap file
SP (T1)
guard page
thread 2 stack
SP (T2)
guard page
thread 3 stack
Unmapped, may be
dynamically mapped
SP (T3)
guard page (never mapped)
heap
Map to writable
swap file
Map to writable
swap file
static data
PC (T2)
Mapped to read-only
executable file
CS-502 (EMC) Fall 2009
program code
& constants
Paging
PC (T3)
30
Virtual Memory Organization (continued)
• Each area of process VM is its own segment
(or sequence of segments)
• Executable code & constants – fixed size
• Shared libraries
• Static data – fixed size
• Heap – open-ended
• Stacks – each open-ended
• Other segments as needed
– E.g., symbol tables, loader information, etc.
CS-502 (EMC) Fall 2009
Paging
31
Virtual Memory – a Major OS Abstraction
• Processes execute in virtual memory, not
physical memory
• Virtual memory may be very large
• Much larger than physical memory
• Virtual memory may be organized in
interesting & useful ways
• Open-ended segments
• Virtual memory is where the action is!
• Physical memory is just a cache of virtual memory
CS-502 (EMC) Fall 2009
Paging
32
Reading Assignment
• Tanenbaum
– §§ 3.1-3.2 (previous topic – Memory
Management)
– § 3.3 (this topic on Paging)
CS-502 (EMC) Fall 2009
Paging
33
Questions?
CS-502 (EMC) Fall 2009
Paging
34