Chapter 9: Virtual Memory
Operating System Concepts Essentials – 9 th Edition Silberschatz, Galvin and Gagne ©2013
Chapter 9: Virtual Memory
Background
Demand Paging
Copy-on-Write
Page Replacement
Operating System Concepts Essentials – 9 th 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 examine the relationship between shared memory and memory-mapped
files
Operating System Concepts Essentials – 9 th Edition 9.3 Silberschatz, Galvin and Gagne ©2013
Background
Code needs to be in memory to execute, but entire program rarely used
Error code, unusual routines, large data structures
Entire program code not needed at same time
Consider ability to execute partially-loaded program
Program no longer constrained by limits of physical memory
Each program takes less memory while running -> more programs run at
the same time
Increased CPU utilization and throughput with no increase in response
time or turnaround time
Less I/O needed to load or swap programs into memory -> each user
program runs faster
Operating System Concepts Essentials – 9 th Edition 9.4 Silberschatz, Galvin and Gagne ©2013
Background
Virtual memory – separation of user logical memory from physical memory
Only part of the program needs to be in memory for execution
Logical address space can therefore be much larger than physical address space
Allows address spaces to be shared by several processes
Allows for more efficient process creation
More programs running concurrently
Less I/O needed to load or swap processes
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 Essentials – 9 th Edition 9.5 Silberschatz, Galvin and Gagne ©2013
Virtual Memory That is
Larger Than Physical Memory
Operating System Concepts Essentials – 9 th Edition 9.6 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 Essentials – 9 th Edition 9.7 Silberschatz, Galvin and Gagne ©2013
Shared Library Using Virtual Memory
Operating System Concepts Essentials – 9 th Edition 9.8 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 Essentials – 9 th Edition 9.9 Silberschatz, Galvin and Gagne ©2013
Basic Concepts
With swapping, pager guesses which pages will be used before swapping out again
Instead of swapping in a whole process, 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 Essentials – 9 th Edition 9.10 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:
Frame # valid-invalid bit
v
v
v
v
i
….
i
i
page table
During MMU address translation, if valid–invalid bit in page table entry
is i page fault
Operating System Concepts Essentials – 9 th Edition 9.11 Silberschatz, Galvin and Gagne ©2013
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts Essentials – 9 th Edition 9.12 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 Essentials – 9 th Edition 9.13 Silberschatz, Galvin and Gagne ©2013
Steps in Handling a Page Fault
Operating System Concepts Essentials – 9 th Edition 9.14 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
Hardware support needed for demand paging
Page table with valid / invalid bit
Secondary memory (swap device with swap space)
Instruction restart
Operating System Concepts Essentials – 9 th Edition 9.15 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 Essentials – 9 th Edition 9.16 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 Essentials – 9 th Edition 9.17 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
Operating System Concepts Essentials – 9 th Edition 9.18 Silberschatz, Galvin and Gagne ©2013
Page Replacement
Operating System Concepts Essentials – 9 th Edition 9.19 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 Essentials – 9 th Edition 9.20 Silberschatz, Galvin and Gagne ©2013
Graph of Page Faults Versus
The Number of Frames
Operating System Concepts Essentials – 9 th Edition 9.21 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 Essentials – 9 th Edition 9.22 Silberschatz, Galvin and Gagne ©2013
FIFO Illustrating Belady’s Anomaly
Operating System Concepts Essentials – 9 th Edition 9.23 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 Essentials – 9 th Edition 9.24 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 Essentials – 9 th Edition 9.25 Silberschatz, Galvin and Gagne ©2013
End of Chapter 9
Operating System Concepts Essentials – 9 th Edition Silberschatz, Galvin and Gagne ©2013
