Chapter 10: Virtual Memory
Background
Demand Paging
Process Creation
Page Replacement
Allocation of Frames
Thrashing
Operating System Concepts 10.1 Silberschatz, Galvin and Gagne 2002
Background
Operating System Concepts 10.2 Silberschatz, Galvin and Gagne 2002
Implementation of Virtual Memory:
Demand Paging
Bring a page into memory only when it is needed.
Less I/O needed
Less memory needed
Faster response
More users
Page is needed reference to it
invalid reference abort
not-in-memory bring to memory
Uses Lazy swapper
Operating System Concepts 10.3 Silberschatz, Galvin and Gagne 2002
Transfer of a Paged Memory to Contiguous Disk Space
Operating System Concepts 10.4 Silberschatz, Galvin and Gagne 2002
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated
(1 in-memory, 0 not-in-memory)
Initially valid–invalid but is set to 0 on all entries.
Example of a page table snapshot.
During address translation, if valid–invalid bit in page table entry is 0 page
fault.
Frame # valid-invalid bit
1
1
1
1
0
0
0
page table
Operating System Concepts 10.5 Silberschatz, Galvin and Gagne 2002
Page Table When Some Pages Are Not in Main Memory
Operating System Concepts 10.6 Silberschatz, Galvin and Gagne 2002
Page Fault
If there is ever a reference to a page, first reference will
trap to
OS page fault
1. OS looks at internal table in PCB to decide:
Invalid reference abort.
Valid but Just not in memory.
3. Get empty frame.- check free frame list
4. Swap page into frame.
5. Reset tables, internal table in PCB and page table validation
bit = 1.
6. Restart instruction:
Operating System Concepts 10.7 Silberschatz, Galvin and Gagne 2002
Steps in Handling a Page Fault
Operating System Concepts 10.8 Silberschatz, Galvin and Gagne 2002
What happens if there is no free frame?
Page replacement – find some page in memory, but not
really in use, swap it out.
selection of page by applying algorithm
To increase the 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 10.9 Silberschatz, Galvin and Gagne 2002
Pure Demand Paging
Start executing process with no pages in memory.
When OS starts executing process, process immediately
faults for a page.
Never bring a page into memory until it is required.
Operating System Concepts 10.10 Silberschatz, Galvin and Gagne 2002
Performance of Demand Paging
How it affects the performance of Computer System?
Lets calculated the effective access time for a demand paged
memory
If no page faults,
memory access time=effective access time
Page Fault Rate 0 p 1.0
if p = 0 no page faults
if p = 1, every reference is a fault
Effective Access Time (EAT)
EAT = (1 – p) x memory access
+ p (page fault overhead)
Operating System Concepts 10.11 Silberschatz, Galvin and Gagne 2002
Performance of Demand Paging
Effective Access Time (EAT)
EAT = (1 – p) x memory access
+ p * (page fault overhead)
page fault overhead = [swap page out ]+ swap page in
+ restart overhead
Operating System Concepts 10.12 Silberschatz, Galvin and Gagne 2002
Demand Paging Example
Operating System Concepts 10.13 Silberschatz, Galvin and Gagne 2002
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.
3. Read the desired page into the (newly) free frame.
Update the page and frame tables.
4. Restart the process.
Operating System Concepts
Page Replacement
Operating System Concepts 10.15 Silberschatz, Galvin and Gagne 2002
Basic Page Replacement
Algorithms
There are certain basic algorithms that are used for the
selection of a page to replace, they include
First-in-First-Out (FIFO)
Optimal
Least recently used (LRU)
Aim is to get lowest page-fault rate.
10.16 Silberschatz, Galvin and Gagne 2002
Examples
An example of the implementation of these policies will
use a page address stream formed by executing the
program is
2 3 2 1 5 2 4 5 3 2 5 2
Which means that the first page referenced is 2,
the second page referenced is 3,
And so on.
10.17 Silberschatz, Galvin and Gagne 2002
First-in, first-out (FIFO)
10.18 Silberschatz, Galvin and Gagne 2002
FIFO Example
The FIFO policy results in six page faults.
10.19 Silberschatz, Galvin and Gagne 2002
Optimal policy
10.20 Silberschatz, Galvin and Gagne 2002
Optimal Policy
Example
The optimal policy produces three page faults after the frame
allocation has been filled.
10.21 Silberschatz, Galvin and Gagne 2002
Least Recently Used (LRU)
10.22 Silberschatz, Galvin and Gagne 2002
LRU Example
The LRU policy does nearly as well as the optimal policy.
In this example, there are four page faults
10.23 Silberschatz, Galvin and Gagne 2002
Page Replacement Algorithms
Evaluate algorithm by running it on a particular string of
memory references (reference string) and computing the
number of page faults on that string.
In all our examples, the reference string is
70120304230321201701
Frame size - 3
Operating System Concepts 10.24 Silberschatz, Galvin and Gagne 2002
FIFO Page Replacement
Operating System Concepts 10.25 Silberschatz, Galvin and Gagne 2002
Optimal Page Replacement
Operating System Concepts 10.26 Silberschatz, Galvin and Gagne 2002
LRU Page Replacement
Operating System Concepts 10.27 Silberschatz, Galvin and Gagne 2002
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.
Free pages are allocated from a pool of Zero Fill on
Demand pages.
Zero Fill on Demand pages have to be zeroed-out pages
before allocating it
Operating System Concepts 10.28 Silberschatz, Galvin and Gagne 2002
Before Process 1 Modifies Page C
Operating System Concepts 10.29 Silberschatz, Galvin and Gagne 2002
After Process 1 Modifies Page C
Operating System Concepts 10.30 Silberschatz, Galvin and Gagne 2002
Graph of Page Faults Versus The Number of Frames
Operating System Concepts 10.31 Silberschatz, Galvin and Gagne 2002
FIFO Illustrating Belady’s Anamoly
Operating System Concepts 10.32 Silberschatz, Galvin and Gagne 2002
Page Fault ratio = (total miss/total possible cases)
Hit ratio= (total hit/ total possible cases)
Belady’s anamoly:
The hit ratio is decreasing in place of increasing
although we have increased the frame size.
This unusual behavior is only observed sometimes.
It doesn't mean that every time the frame size is
increased the page faults will increase.
Operating System Concepts 10.33 Silberschatz, Galvin and Gagne 2002
Allocation of Frames
Operating System Concepts 10.34 Silberschatz, Galvin and Gagne 2002
Thrashing
Operating System Concepts 10.35 Silberschatz, Galvin and Gagne 2002
Thrashing
Operating System Concepts 10.36 Silberschatz, Galvin and Gagne 2002