Chapter 10: Virtual Memory

Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018
 Chapter 10: Virtual Memory
 Background
 Demand Paging
 Copy-on-Write
 Page Replacement
 Allocation of Frames

Operating System Concepts – 10th Edition 10.2 Silberschatz, Galvin and Gagne ©2018
 Objectives
 Define virtual memory and describe its benefits.
 Illustrate how pages are loaded into memory using demand paging.
 Apply the FIFO, optimal, and LRU page-replacement algorithms.

Operating System Concepts – 10th Edition 10.3 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.4 Silberschatz, Galvin and Gagne ©2018
 Virtual memory
 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

Operating System Concepts – 10th Edition 10.5 Silberschatz, Galvin and Gagne ©2018
 Virtual memory (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 – 10th Edition 10.6 Silberschatz, Galvin and Gagne ©2018
 Virtual Memory That is Larger Than Physical Memory

Operating System Concepts – 10th Edition 10.7 Silberschatz, Galvin and Gagne ©2018
 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/ processes
 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 – 10th Edition 10.8 Silberschatz, Galvin and Gagne ©2018
 Demand Paging

Operating System Concepts – 10th Edition 10.9 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.10 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.11 Silberschatz, Galvin and Gagne ©2018
 Page Table When Some Pages Are Not
in Main Memory

Operating System Concepts – 10th Edition 10.12 Silberschatz, Galvin and Gagne ©2018
 Steps in Handling Page Fault

1. If there is a reference to a page, first reference to that page will trap to

operating system
• Page fault
2. Operating system looks at page table to decide:
• Invalid reference  abort
• Just not in memory
3. Find free frame
4. Swap page into frame via scheduled disk operation
5. Reset tables to indicate page now in memory
Set validation bit = v
6. Restart the instruction that caused the page fault

Operating System Concepts – 10th Edition 10.13 Silberschatz, Galvin and Gagne ©2018
 Steps in Handling a Page Fault (Cont.)

Operating System Concepts – 10th Edition 10.14 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.15 Silberschatz, Galvin and Gagne ©2018
 Free-Frame List

 When a page fault occurs, the operating system must bring the
desired page from secondary storage into main memory.
 Most operating systems maintain a free-frame list -- a pool of free
frames for satisfying such requests.

 Operating system typically allocate free frames using a technique

known as zero-fill-on-demand -- the content of the frames zeroed-
out before being allocated.
 When a system starts up, all available memory is placed on the free-
frame list.

Operating System Concepts – 10th Edition 10.16 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.17 Silberschatz, Galvin and Gagne ©2018
 Before Process 1 Modifies Page C

Operating System Concepts – 10th Edition 10.18 Silberschatz, Galvin and Gagne ©2018
 After Process 1 Modifies Page C

Operating System Concepts – 10th Edition 10.19 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.20 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.21 Silberschatz, Galvin and Gagne ©2018
 Need For Page Replacement

Operating System Concepts – 10th Edition 10.22 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.23 Silberschatz, Galvin and Gagne ©2018
 Page Replacement

Operating System Concepts – 10th Edition 10.24 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.25 Silberschatz, Galvin and Gagne ©2018
 Graph of Page Faults Versus the Number of Frames

Operating System Concepts – 10th Edition 10.26 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.27 Silberschatz, Galvin and Gagne ©2018
 FIFO Illustrating Belady’s Anomaly

Operating System Concepts – 10th Edition 10.28 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.29 Silberschatz, Galvin and Gagne ©2018
 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 – 10th Edition 10.30 Silberschatz, Galvin and Gagne ©2018
 LRU Algorithm (Cont.)
 Counter implementation
• Every page entry has a counter; every time page is referenced
through this entry, copy the clock into the counter
• When a page needs to be changed, look at the counters to find
smallest value
 Search through table needed
 Stack implementation
• Keep a stack of page numbers in a double link form:
• Page referenced:
 move it to the top
• But each update more expensive
• No search for replacement

Operating System Concepts – 10th Edition 10.31 Silberschatz, Galvin and Gagne ©2018
 LRU Algorithm (Cont.)
 LRU and OPT are cases of stack algorithms that don’t have Belady’s
Anomaly
 Use Of A Stack to Record Most Recent Page References

Operating System Concepts – 10th Edition 10.32 Silberschatz, Galvin and Gagne ©2018
 LRU Approximation Algorithms
 LRU needs special hardware and still slow
 Reference bit
• With each page associate a bit, initially = 0
• When page is referenced bit set to 1
• Replace any with reference bit = 0 (if one exists)
 We do not know the order, however

Operating System Concepts – 10th Edition 10.33 Silberschatz, Galvin and Gagne ©2018
 LRU Approximation Algorithms (cont.)

 Second-chance algorithm
• Generally FIFO, plus hardware-provided reference bit
• Clock replacement
• If page to be replaced has
 Reference bit = 0 -> replace it
 reference bit = 1 then:
– set reference bit 0, leave page in memory
– replace next page, subject to same rules

Operating System Concepts – 10th Edition 10.34 Silberschatz, Galvin and Gagne ©2018
 Second-chance Algorithm

Operating System Concepts – 10th Edition 10.35 Silberschatz, Galvin and Gagne ©2018
 Enhanced Second-Chance Algorithm
 Improve algorithm by using reference bit and modify bit (if available)
in concert
 Take ordered pair (reference, modify):
• (0, 0) neither recently used not modified – best page to replace
• (0, 1) not recently used but modified – not quite as good, must
write out before replacement
• (1, 0) recently used but clean – probably will be used again soon
• (1, 1) recently used and modified – probably will be used again
soon and need to write out before replacement

Operating System Concepts – 10th Edition 10.36 Silberschatz, Galvin and Gagne ©2018
 Counting Algorithms
 Keep a counter of the number of references that have been made
to each page
• Not common
 Lease Frequently Used (LFU) Algorithm:
• Replaces page with smallest count
 Most Frequently Used (MFU) Algorithm:
• Based on the argument that the page with the smallest count
was probably just brought in and has yet to be used

Operating System Concepts – 10th Edition 10.37 Silberschatz, Galvin and Gagne ©2018