Transcript Paging (continued) & Caching

Paging (continued) &
Caching
CS-3013 Operating Systems
A-term 2008
(Slides include materials from Modern Operating Systems, 3rd ed., by Andrew Tanenbaum and from
Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne)
CS-3013 A-term 2008
Paging (continued) &
Caching
1
Review – Paging
• Partition virtual memory into small fixed size
units called pages
• Typically 512-8192 bytes
• Translate every memory address on-the-fly
from virtual to physical address
• Allow process to execute, even if not all
pages are in physical memory
CS-3013 A-term 2008
Paging (continued) &
Caching
2
Definition — Page Fault
• Trap when process attempts to reference a
location in virtual memory whose virtual
address cannot be translated
• I.e., valid bit in PTE set to false
• I.e., reference violates protection bits in PTE
• OS takes appropriate action, restarts process
at point of fault
CS-3013 A-term 2008
Paging (continued) &
Caching
3
PTE Structure
1 1 1
2
V R M
prot
20
page frame number
• Valid bit gives state of this PTE
– says whether or not a 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-3013 A-term 2008
Paging (continued) &
Caching
4
Paging – Advantages
• Easy to allocate physical memory
• pick any free frame
• No external fragmentation
• All frames are equal
• Minimal internal fragmentation
• Bounded by page/frame size
• Easy to swap out pages (called pageout)
• Size is usually a multiple of disk blocks
• PTEs may contain info that help reduce disk traffic
• Processes can run with not all pages swapped in
CS-3013 A-term 2008
Paging (continued) &
Caching
5
Definitions & Recurring Themes
• Temporal Locality – locations referenced recently
tend to be referenced again soon
• Spatial Locality – locations near recent references
tend to be referenced soon
• 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-3013 A-term 2008
Paging (continued) &
Caching
6
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-3013 A-term 2008
Paging (continued) &
Caching
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-3013 A-term 2008
Paging (continued) &
Caching
8
Paging Tricks
• Shared Virtual Memory
• Pages of two or more processes point to same page
frames
• E.g. shared libraries
• Copy-on-write
• Processes share virtual memory
• Writable pages marked read-only
• On page fault, make separate writable copies
CS-3013 A-term 2008
Paging (continued) &
Caching
9
Definition — Backing Storage
• A place on external storage medium where
copies of virtual pages are kept
• Usually a hard disk (locally or on a server)
• Place from which contents of pages are read
after page faults
• Place where contents of pages are written if
page frames need to be re-allocated
CS-3013 A-term 2008
Paging (continued) &
Caching
10
Backing Storage
• Executable code and constants:–
• The loadable image file produced by compiler
• Working memory (stack, heap, static data)
• Special swapping file (or partition) on disk
• Persistent application data
• Application data files on local or server disks
CS-3013 A-term 2008
Paging (continued) &
Caching
11
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-3013 A-term 2008
Paging (continued) &
Caching
12
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 very well in practice
CS-3013 A-term 2008
Paging (continued) &
Caching
13
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-3013 A-term 2008
Paging (continued) &
Caching
14
Virtual Memory Organization
0xFFFFFFFF
stack
(dynamically allocated)
SP
Virtual
address space
heap
(dynamically allocated)
static data
0x00000000
CS-3013 A-term 2008
program code
(text)
Paging (continued) &
Caching
PC
15
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-3013 A-term 2008
program code
& constants
Paging (continued) &
Caching
PC
16
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
Map to writable
swap file
Map to writable
swap file
SP (T3)
guard page (never mapped)
heap
static data
PC (T2)
Mapped to read-only
executable file
CS-3013 A-term 2008
program code
& constants
Paging (continued) &
Caching
PC (T3)
17
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-3013 A-term 2008
Paging (continued) &
Caching
18
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-3013 A-term 2008
Paging (continued) &
Caching
19
Reading Assignment
• Tanenbaum
– §§ 3.1-3.2 (previous topic – Memory
Management)
– § 3.3 (this topic on Paging)
CS-3013 A-term 2008
Paging (continued) &
Caching
20
Related topic – Caching
CS-3013 A-term 2008
Paging (continued) &
Caching
21
Definition — Cache
• A small subset of active items held in fast
storage while most of the items are in much
larger, slower storage
– Virtual Memory
• Very large, mostly stored on (slow) disk
• Small working set in (fast) RAM during execution
– Page tables
• Very large, mostly stored in (slow) RAM
• Small working set stored in (fast) TLB registers
CS-3013 A-term 2008
Paging (continued) &
Caching
22
Caching is Ubiquitous in Computing
• Transaction processing
• Keep records of today’s departures in RAM while records of
future flights are on disk
• Program execution
• Keep the bytes near the current program counter in on-chip
memory while rest of program is in RAM
• File management
• Keep disk maps of open files in RAM while retaining maps of
all files on disk
• Game design
• Keep nearby environment in cache of each character
• …
CS-3013 A-term 2008
Paging (continued) &
Caching
23
Caching issues
• When to put something in the cache
• What to throw out to create cache space for new
items
• How to keep cached item and stored item in sync
after one or the other is updated
• How to keep multiple caches in sync across
processors or machines
• Size of cache needed to be effective
• Size of cache items for efficiency
• …
CS-3013 A-term 2008
Paging (continued) &
Caching
24
Caching issues
• When to put something in the cache
• What to throw out to create cache space for new
items
• How to keep cached item and stored item in sync
after one or the other is updated
• How to keep multiple caches in sync across
processors or machines
• Size of cache needed to be effective
• Size of cache items for efficiency
• …
CS-3013 A-term 2008
Paging (continued) &
Caching
25
Questions?
CS-3013 A-term 2008
Paging (continued) &
Caching
26