Chapter 9: Virtual Memory
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013
Chapter 9: Virtual Memory
Background
Demand Paging
Copy-on-Write
Page Replacement
Allocation of Frames
Thrashing
Memory-Mapped Files
Allocating Kernel Memory
Other Considerations
Operating-System Examples
Operating System Concepts – 9th Edition 9.2 Silberschatz, Galvin and Gagne ©2013
Objectives
To describe the benefits of a virtual memory system
To explain the concepts of demand paging, page-replacement
algorithms, and allocation of page frames
To discuss the principle of the working-set model
To examine the relationship between shared memory and
memory-mapped files
To explore how kernel memory is managed
Operating System Concepts – 9th Edition 9.3 Silberschatz, Galvin and Gagne ©2013
Background (Cont.)
Virtual address space – logical view of how process is stored
in memory
Usually start at address 0, contiguous addresses until end of
space
Meanwhile, physical memory organized in page frames
MMU must map logical to physical
Virtual memory can be implemented via:
Demand paging
Demand segmentation
Operating System Concepts – 9th Edition 9.4 Silberschatz, Galvin and Gagne ©2013
Virtual Memory That is Larger Than Physical Memory
Operating System Concepts – 9th Edition 9.5 Silberschatz, Galvin and Gagne ©2013
Virtual-address Space
Usually design logical address space for
stack to start at Max logical address and
grow “down” while heap grows “up”
Maximizes address space use
Unused address space between
the two is hole
No physical memory needed
until heap or stack grows to a
given new page
Enables sparse address spaces with
holes left for growth, dynamically linked
libraries, etc
System libraries shared via mapping into
virtual address space
Shared memory by mapping pages read-
write into virtual address space
Pages can be shared during fork(),
speeding process creation
Operating System Concepts – 9th Edition 9.6 Silberschatz, Galvin and Gagne ©2013
Shared Library Using Virtual Memory
Operating System Concepts – 9th Edition 9.7 Silberschatz, Galvin and Gagne ©2013
Demand Paging
Could bring entire process into memory
at load time
Or bring a page into memory only when
it is needed
Less I/O needed, no unnecessary
I/O
Less memory needed
Faster response
More users
Similar to paging system with swapping
(diagram on right)
Page is needed reference to it
invalid reference abort
not-in-memory bring to memory
Lazy swapper – never swaps a page
into memory unless page will be needed
Swapper that deals with pages is a
pager
Operating System Concepts – 9th Edition 9.8 Silberschatz, Galvin and Gagne ©2013
Basic Concepts
With swapping, pager guesses which pages will be used before
swapping out again
Instead, pager brings in only those pages into memory
How to determine that set of pages?
Need new MMU functionality to implement demand paging
If pages needed are already memory resident
No difference from non demand-paging
If page needed and not memory resident
Need to detect and load the page into memory from storage
Without changing program behavior
Without programmer needing to change code
Operating System Concepts – 9th Edition 9.9 Silberschatz, Galvin and Gagne ©2013
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated
(v in-memory – memory resident, i not-in-memory)
Initially valid–invalid bit is set to i on all entries
Example of a page table snapshot:
During MMU address translation, if valid–invalid bit in page table
entry is i page fault
Operating System Concepts – 9th Edition 9.10 Silberschatz, Galvin and Gagne ©2013
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts – 9th Edition 9.11 Silberschatz, Galvin and Gagne ©2013
Page Fault
If there is a reference to a page, first reference to that page will
trap to operating system:
page fault
1. Operating system looks at another table to decide:
Invalid reference abort
Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault
Operating System Concepts – 9th Edition 9.12 Silberschatz, Galvin and Gagne ©2013
Steps in Handling a Page Fault
Operating System Concepts – 9th Edition 9.13 Silberschatz, Galvin and Gagne ©2013
Aspects of Demand Paging
Extreme case – start process with no pages in memory
OS sets instruction pointer to first instruction of process, non-
memory-resident -> page fault
And for every other process pages on first access
Pure demand paging
Actually, a given instruction could access multiple pages -> multiple
page faults
Consider fetch and decode of instruction which adds 2 numbers
from memory and stores result back to memory
Pain decreased because of locality of reference
Hardware support needed for demand paging
Page table with valid / invalid bit
Secondary memory (swap device with swap space)
Instruction restart
Operating System Concepts – 9th Edition 9.14 Silberschatz, Galvin and Gagne ©2013
Instruction Restart
Consider an instruction that could access several different locations
block move
auto increment/decrement location
Restart the whole operation?
What if source and destination overlap?
Operating System Concepts – 9th Edition 9.15 Silberschatz, Galvin and Gagne ©2013
Demand Paging Example
Memory access time = 200 nanoseconds
Average page-fault service time = 8 milliseconds
EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p x 200 + p x 8,000,000
= 200 + p x 7,999,800
If one access out of 1,000 causes a page fault, then
EAT = 8.2 microseconds.
This is a slowdown by a factor of 40!!
If want performance degradation < 10 percent
220 > 200 + 7,999,800 x p
20 > 7,999,800 x p
p < .0000025
< one page fault in every 400,000 memory accesses
Operating System Concepts – 9th Edition 9.16 Silberschatz, Galvin and Gagne ©2013
Copy-on-Write
Copy-on-Write (COW) allows both parent and child processes to initially
share the same pages in memory
If either process modifies a shared page, only then is the page copied
COW allows more efficient process creation as only modified pages are
copied
In general, free pages are allocated from a pool of zero-fill-on-demand
pages
Pool should always have free frames for fast demand page execution
Don’t want to have to free a frame as well as other processing on
page fault
Why zero-out a page before allocating it?
vfork() variation on fork() system call has parent suspend and child
using copy-on-write address space of parent
Designed to have child call exec()
Very efficient
Operating System Concepts – 9th Edition 9.17 Silberschatz, Galvin and Gagne ©2013
Before Process 1 Modifies Page C
Operating System Concepts – 9th Edition 9.18 Silberschatz, Galvin and Gagne ©2013
After Process 1 Modifies Page C
Operating System Concepts – 9th Edition 9.19 Silberschatz, Galvin and Gagne ©2013
What Happens if There is no Free Frame?
Used up by process pages
Also in demand from the kernel, I/O buffers, etc
How much to allocate to each?
Page replacement – find some page in memory, but not really in
use, page it out
Algorithm – terminate? swap out? replace the page?
Performance – want an algorithm which will result in minimum
number of page faults
Same page may be brought into memory several times
Operating System Concepts – 9th Edition 9.20 Silberschatz, Galvin and Gagne ©2013
Page Replacement
Prevent over-allocation of memory by modifying page-
fault service routine to include page replacement
Use modify (dirty) bit to reduce overhead of page
transfers – only modified pages are written to disk
Page replacement completes separation between logical
memory and physical memory – large virtual memory can
be provided on a smaller physical memory
Operating System Concepts – 9th Edition 9.21 Silberschatz, Galvin and Gagne ©2013
Need For Page Replacement
Operating System Concepts – 9th Edition 9.22 Silberschatz, Galvin and Gagne ©2013
Basic Page Replacement
1. Find the location of the desired page on disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page replacement algorithm to
select a victim frame
- Write victim frame to disk if dirty
3. Bring the desired page into the (newly) free frame; update the page
and frame tables
4. Continue the process by restarting the instruction that caused the trap
Note now potentially 2 page transfers for page fault – increasing EAT
Operating System Concepts – 9th Edition 9.23 Silberschatz, Galvin and Gagne ©2013
Page Replacement
Operating System Concepts – 9th Edition 9.24 Silberschatz, Galvin and Gagne ©2013
Page and Frame Replacement Algorithms
Frame-allocation algorithm determines
How many frames to give each process
Which frames to replace
Page-replacement algorithm
Want lowest page-fault rate on both first access and re-access
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string
String is just page numbers, not full addresses
Repeated access to the same page does not cause a page fault
Results depend on number of frames available
In all our examples, the reference string of referenced page
numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
Operating System Concepts – 9th Edition 9.25 Silberschatz, Galvin and Gagne ©2013
Graph of Page Faults Versus The Number of Frames
Operating System Concepts – 9th Edition 9.26 Silberschatz, Galvin and Gagne ©2013
First-In-First-Out (FIFO) Algorithm
Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
3 frames (3 pages can be in memory at a time per process)
15 page faults
Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
Adding more frames can cause more page faults!
Belady’s Anomaly
How to track ages of pages?
Just use a FIFO queue
Operating System Concepts – 9th Edition 9.27 Silberschatz, Galvin and Gagne ©2013
FIFO Illustrating Belady’s Anomaly
Operating System Concepts – 9th Edition 9.28 Silberschatz, Galvin and Gagne ©2013
Optimal Algorithm
Replace page that will not be used for longest period of time
9 is optimal for the example
How do you know this?
Can’t read the future
Used for measuring how well your algorithm performs
Operating System Concepts – 9th Edition 9.29 Silberschatz, Galvin and Gagne ©2013
Least Recently Used (LRU) Algorithm
Use past knowledge rather than future
Replace page that has not been used in the most amount of time
Associate time of last use with each page
12 faults – better than FIFO but worse than OPT
Generally good algorithm and frequently used
But how to implement?
Operating System Concepts – 9th Edition 9.30 Silberschatz, Galvin and Gagne ©2013
Thrashing
If a process does not have “enough” pages, the page-fault rate is
very high
Page fault to get page
Replace existing frame
But quickly need replaced frame back
This leads to:
Low CPU utilization
Operating system thinking that it needs to increase the
degree of multiprogramming
Another process added to the system
Thrashing a process is busy swapping pages in and out
Operating System Concepts – 9th Edition 9.31 Silberschatz, Galvin and Gagne ©2013
Thrashing (Cont.)
Operating System Concepts – 9th Edition 9.32 Silberschatz, Galvin and Gagne ©2013
Demand Paging and Thrashing
Why does demand paging work?
Locality model
Process migrates from one locality to another
Localities may overlap
Why does thrashing occur?
size of locality > total memory size
Limit effects by using local or priority page replacement
Operating System Concepts – 9th Edition 9.33 Silberschatz, Galvin and Gagne ©2013
End of Chapter 9
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013
