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
 Allocation of Frames
 Thrashing
 Memory-Mapped Files
 Allocating Kernel Memory
 Other Considerations
 Operating-System Examples

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 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 Essentials – 9 th Edition 9.3 Silberschatz, Galvin and Gagne ©2013
 Background
 Virtual memory is a common technique used in a computer's
operating system (OS). Virtual memory uses both hardware and
software to enable a computer to compensate for physical
memory shortages, temporarily transferring data from random
access memory (RAM) to disk storage.

Operating System Concepts Essentials – 9 th Edition 9.4 Silberschatz, Galvin and Gagne ©2013
 Background

 Virtual memory can be implemented via:

 Demand paging
 Demand segmentation

Operating System Concepts Essentials – 9 th Edition 9.5 Silberschatz, Galvin and Gagne ©2013
 Demand Paging
 With demand-paged virtual memory, pages are loaded only when they are demanded
during program execution. Pages that are never accessed are thus never loaded into
physical memory.

 A demand-paging system is similar to

a paging system with swapping where
processes reside in secondary
memory (usually a disk). When we
want to execute a process, we swap it
into memory

Operating System Concepts Essentials – 9 th Edition 9.6 Silberschatz, Galvin and Gagne ©2013
 Basic Concepts
 A swapper manipulates entire processes, whereas a pager is
concerned with the individual pages of a process. We thus use
“pager,” rather than “swapper,” in connection with demand
paging

Operating System Concepts Essentials – 9 th Edition 9.7 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.8 Silberschatz, Galvin and Gagne ©2013
 Page Table When Some Pages Are Not in Main Memory

Operating System Concepts Essentials – 9 th Edition 9.9 Silberschatz, Galvin and Gagne ©2013
 Page Fault
 If the referred page is not present in the main memory then there will be
a miss and the concept is called Page miss or page fault.

or in other words

 Access to a page marked invalid causes a page fault.

Operating System Concepts Essentials – 9 th Edition 9.10 Silberschatz, Galvin and Gagne ©2013
 Steps in Handling a Page Fault

Operating System Concepts Essentials – 9 th Edition 9.11 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

Operating System Concepts Essentials – 9 th Edition 9.12 Silberschatz, Galvin and Gagne ©2013
 Need For Page Replacement

Operating System Concepts Essentials – 9 th Edition 9.13 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

Operating System Concepts Essentials – 9 th Edition 9.14 Silberschatz, Galvin and Gagne ©2013
 Page Replacement

Operating System Concepts Essentials – 9 th Edition 9.15 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

Operating System Concepts Essentials – 9 th Edition 9.16 Silberschatz, Galvin and Gagne ©2013
 Graph of Page Faults Versus
The Number of Frames

Operating System Concepts Essentials – 9 th Edition 9.17 Silberschatz, Galvin and Gagne ©2013
 First-In-First-Out (FIFO) Algorithm
 This is the simplest page replacement algorithm. In this
algorithm, the OS maintains a queue that keeps track of
all the pages in memory, with the oldest page at the
front and the most recent page at the back.

 When there is a need for page replacement, the FIFO

algorithm, swaps out the page at the front of the
queue, that is the page which has been in the memory
for the longest time.

Operating System Concepts Essentials – 9 th Edition 9.18 Silberschatz, Galvin and Gagne ©2013
 First-In-First-Out (FIFO) Algorithm
 Consider the page reference string of size 12: 1, 2, 3, 4, 5, 1, 3, 1, 6, 3, 2, 3 with frame
size 4 (i.e. maximum 4 pages in a frame).

Total Page
Fault = 9

Operating System Concepts Essentials – 9 th Edition 9.19 Silberschatz, Galvin and Gagne ©2013
 Belady’s Anomaly

• Effect of Increasing Number of Frames- The number of

page faults should either decrease or remain constant
on increasing the number of frames in main memory.

• But sometimes the unusual behavior is observed.

Sometimes, on increasing the number of frames in main
memory, the number of page faults also increase.

Operating System Concepts Essentials – 9 th Edition 9.20 Silberschatz, Galvin and Gagne ©2013
 • Reason Behind Belady’s Anomaly

• An algorithm suffers from Belady’s Anomaly if and only if

it does not follow stack property.

• Algorithms that follow stack property are called as stack

based algorithms.

• Stack based algorithms do not suffer from Belady’s

Anomaly.

Operating System Concepts Essentials – 9 th Edition 9.21 Silberschatz, Galvin and Gagne ©2013
 FIFO Illustrating Belady’s Anomaly

Operating System Concepts Essentials – 9 th Edition 9.22 Silberschatz, Galvin and Gagne ©2013
 First-In-First-Out (FIFO) Algorithm
Case-01: When frame size = 3

Case-02: When frame size = 4

Operating System Concepts Essentials – 9 th Edition 9.23 Silberschatz, Galvin and Gagne ©2013
 Optimal Algorithm
 Optimal Page Replacement algorithm is the best page replacement
algorithm as it gives the least number of page faults. It is also known
as OPT, clairvoyant replacement algorithm, or Belady’s optimal page
replacement policy.

 In this algorithm, pages are replaced which would not be used for the
longest duration of time in the future, i.e., the pages in the memory
which are going to be referred farthest in the future are replaced.

 This algorithm was introduced long back and is difficult to implement

because it requires future knowledge of the program behaviour.
However, it is possible to implement optimal page replacement on the
second run by using the page reference information collected on the
first run.

Operating System Concepts Essentials – 9 th Edition 9.24 Silberschatz, Galvin and Gagne ©2013
 Optimal Algorithm

Total Page Fault

=6

Operating System Concepts Essentials – 9 th Edition 9.25 Silberschatz, Galvin and Gagne ©2013
 Least Recently Used (LRU) Algorithm
 Least Recently Used page replacement algorithm keeps
track of page usage over a short period of time. It
works on the idea that the pages that have been most
heavily used in the past are most likely to be used
heavily in the future too.

 In LRU, whenever page replacement happens, the page

which has not been used for the longest amount of time
is replaced.

Operating System Concepts Essentials – 9 th Edition 9.26 Silberschatz, Galvin and Gagne ©2013
 Least Recently Used (LRU) Algorithm
 Consider the page reference string of size 12: 1, 2, 3, 4, 5, 1, 3, 1, 6, 3, 2, 3 with frame
size 4 (i.e. maximum 4 pages in a frame).

Total Page Fault

=8

Operating System Concepts Essentials – 9 th Edition 9.27 Silberschatz, Galvin and Gagne ©2013
 MRU (most recently used)
 MRU page replacement algorithm is the counterpart to the
LRU algorithm.

 Instead of replacing the least recently used page, MRU

replaces the most recently used page.

 The underlying idea is that the page that has been most
recently used is likely to be accessed again in the near
future.

Operating System Concepts Essentials – 9 th Edition 9.28 Silberschatz, Galvin and Gagne ©2013
 MRU (most recently used)

Operating System Concepts Essentials – 9 th Edition 9.29 Silberschatz, Galvin and Gagne ©2013
 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 Essentials – 9 th Edition 9.30 Silberschatz, Galvin and Gagne ©2013
 LFU (least frequently used)
 LFU replaces the page that has been accessed the least number of
times.
Or

 The LFU page replacement algorithm stands for the Least

Frequently Used. In the LFU page replacement algorithm, the page
with the least visits in a given period of time is removed.

 It replaces the least frequently used pages. If the frequency of

pages remains constant, the page that comes first is replaced first.

Operating System Concepts Essentials – 9 th Edition 9.31 Silberschatz, Galvin and Gagne ©2013
 LFU (least frequently used)

Operating System Concepts Essentials – 9 th Edition 9.32 Silberschatz, Galvin and Gagne ©2013
 MFU (most frequently used)
 MFU replaces the page that has been accessed the most. This
algorithm aims to prioritize pages based on their frequency of
usage.

 Advantage: Suitable for scenarios where frequently used pages

are more likely to be relevant in the future.

 Disadvantage: Similar to LFU, MFU might not adapt well to

varying access patterns and can lead to suboptimal
replacements.

Operating System Concepts Essentials – 9 th Edition 9.33 Silberschatz, Galvin and Gagne ©2013
 MFU (most frequently used)
 Consider the page reference string of size 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 with
frame size 3 (i.e. maximum 3 pages in a frame).

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 7 7 2 2 2 0 4 2 2 0 0 2 2 2 0 0 7 7 7

0 0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 0 0

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

M M M M H M M M M H M H M H H M H M M H

HIT = 7
MISS 13

PAGE FAULT = 13

Operating System Concepts Essentials – 9 th Edition 9.34 Silberschatz, Galvin and Gagne ©2013
 Some more Algorithms (Home Task)

1. Second-Chance Algorithm

2. Enhanced Second-Chance Algorithm

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

 When page replacement called for, use the clock scheme but use the four classes replace page in
lowest non-empty class
 Might need to search circular queue several times

Operating System Concepts Essentials – 9 th Edition 9.36 Silberschatz, Galvin and Gagne ©2013
 Thrashing
 When the OS brings one page in, it must throw another out. If
it throws out a page just before it is used, then it will just have
to get that page again almost immediately.

 Too much of this leads to a condition called Thrashing. The

system spends most of its time swapping pages rather than
executing instructions. So, a good page replacement algorithm
is required.

Operating System Concepts Essentials – 9 th Edition 9.37 Silberschatz, Galvin and Gagne ©2013
 Thrashing (Cont.)

Operating System Concepts Essentials – 9 th Edition 9.38 Silberschatz, Galvin and Gagne ©2013
 Thrashing
 In the given diagram, the initial degree of multiprogramming up
to some extent of point(lambda), the CPU utilization is very
high and the system resources are utilized 100%.

 But if we further increase the degree of multiprogramming the

CPU utilization will drastically fall down and the system will
spend more time only on the page replacement and the time
taken to complete the execution of the process will increase.
This situation in the system is called thrashing.

Operating System Concepts Essentials – 9 th Edition 9.39 Silberschatz, Galvin and Gagne ©2013
 Causes of Thrashing
 High Degree of Multiprogramming: If the number of
processes keeps on increasing in the memory then the
number of frames allocated to each process will be decreased.
So, fewer frames will be available for each process.

 Due to this, a page fault will occur more frequently and more
CPU time will be wasted in just swapping in and out of pages
and the utilization will keep on decreasing.

Operating System Concepts Essentials – 9 th Edition 9.40 Silberschatz, Galvin and Gagne ©2013
 Causes of Thrashing
 High Degree of Multiprogramming

For example:
Let free frames = 400
Case 1: Number of processes = 100
Then, each process will get 4 frames.

For example:
Let free frames = 400
Case 2: Number of processes = 400
Then, each process will get 1 frames.

Case 2 is a condition of thrashing, as the number of processes is increased,

frames per process are decreased. Hence CPU time will be consumed just by
swapping pages.

Operating System Concepts Essentials – 9 th Edition 9.41 Silberschatz, Galvin and Gagne ©2013
 Recovery of Thrashing
 Do not allow the system to go into thrashing by instructing the
long-term scheduler not to bring the processes into memory
after the threshold.

 If the system is already thrashing then instruct the mid-term

scheduler to suspend some of the processes so that we can
recover the system from thrashing.

Operating System Concepts Essentials – 9 th Edition 9.42 Silberschatz, Galvin and Gagne ©2013
 End of Chapter 9

Operating System Concepts Essentials – 9 th Edition Silberschatz, Galvin and Gagne ©2013