MODULE 4

CHAPTER 1
VIRTUAL MEMORY
 Virtual Memory
◦ Virtual Memory: Basics of Virtual Memory,
Demand Paging, Copy on Write, Page
Replacement Algorithms- Basic Page
Replacement, FIFO Page Replacement, Optimal
Page Replacement, LRU Page replacement,
Thrashing- cause of Thrashing, Working set model,
Page fault frequency.
What is Virtual Memory?

◦ Virtual memory is a memory management technique used

by operating systems to extend the available physical RAM
by using a portion of secondary storage—such as a hard
drive or SSD—as temporary memory.
◦ This allows systems to run larger applications and more
processes than physical memory alone would permit.
◦ In simple terms, virtual memory creates the illusion of
more RAM, enabling smoother multitasking and better
system stability.
Objectives of Virtual Memory

◦ A program doesn’t need to be fully loaded in memory to

run. Only the needed parts are loaded.
◦ Programs can be bigger than the physical memory available
in the system.
◦ Virtual memory creates the illusion of a large memory, even
if the actual memory (RAM) is small.
◦ It uses both RAM and disk storage to manage memory,
loading only parts of programs into RAM as needed.
◦ This allows the system to run more programs at once and
manage memory more efficiently.
The diagram represents Virtual Memory Management in an Operating System. It shows
how virtual memory pages are mapped to physical memory frames and stored in
backing store (disk).

1. Virtual Memory
It is divided into pages such as:
page 0
page 1
…
page v
These pages belong to a process and represent the memory the program thinks it has.
Virtual memory is usually larger than physical RAM.

2. Memory Map (Page Table)

•It keeps track of where each virtual page is located.
•It maps:
•Virtual Page Number → Physical Frame Number
Example:
•Page 0 → Frame 3
•Page 1 → Frame 7
This mapping allows the CPU to find the correct location of data.
3. Physical Memory
•RAM is divided into frames.
•Some frames contain the currently active pages of the process.
Only a few pages are loaded in RAM at a time.

4. Backing Store
The cylinder on the right represents the backing store (secondary storage / disk).
Pages that are not currently in RAM are stored here.
When needed, they are loaded into physical memory.

How It Works
1.A program requests data from virtual memory page.
[Link] page table (memory map) checks where the page is.
[Link] the page is in physical memory, it is accessed immediately.
[Link] not, the OS performs a page fault and loads it from the backing store.
Benefits of Virtual Memory

Allows Large Programs to Run:

Virtual memory allows programs that are larger than the physical RAM to run by
using disk space.

Better Memory Utilization:

Only the required pages are loaded into RAM, so memory is used more efficiently.

Supports Multitasking:
Multiple programs can run at the same time because each process uses virtual
address space.

Process Isolation and Protection:

Each process has its own virtual memory space, preventing one process from
accessing another’s memory.
Heap grows upwards and
the stack grows
downwards and the hole
between these two is the
virtual memory
 Virtual address space
[Link] Growth
The heap grows upward in memory.
It is used for dynamic memory allocation (e.g., malloc, new).
[Link] Growth
The stack grows downward in [Link] grows when function calls are made and stores
local variables.
[Link] Space Between Heap and Stack
A large empty space (hole) exists between the heap and stack.
This space is part of the virtual address space but does not use physical memory initially.
[Link] Memory Used Only When Needed
Physical pages are allocated only when the heap or stack expands into the empty space.
[Link] Address Space
A virtual address space with unused holes is called a sparse address space.

Advantages:
Allows heap and stack to grow dynamically.
Enables dynamic linking of libraries and shared objects during program execution.
Shared Library using virtual memory
Advantages of using shared library

◦ System libraries can be shared by mapping them into

the virtual address space of more than one process.
◦ Processes can also share virtual memory by mapping
the same block of memory to more than one process.
◦ Process pages can be shared during a fork( ) system
call, eliminating the need to copy all of the pages of
the original ( parent ) process.
Virtual memory
is implemented
using DEMAND
PAGING
 Demand Paging
• According to the concept of Virtual Memory, in order to
execute some process, only a part of the process needs to be
present in the main memory which means that only a few
pages will only be present in the main memory at any time.

• However, deciding, which pages need to be kept in the main

memory and which need to be kept in the secondary memory,
is going to be difficult because we cannot say in advance that a
process will require a particular page at particular time.
 Demand Paging
• Therefore, to overcome this problem, there is a concept
called Demand Paging. It suggests keeping all pages of
the frames in the secondary memory until they are
required. In other words, it says that do not load any
page in the main memory until it is required.

• Whenever any page is referred for the first time in the main
memory, then that page will be found in the secondary
memory.
• After that, it may or may not be present in the main memory
depending upon the page replacement algorithm
Basic concepts

◦ The general concept behind demand paging, is to load

a page in memory only when it is needed.
◦ As a result, while a process is executing some pages
will be in memory and some will be in secondary
storage.
◦ Thus, we need some form of hardware support to
distinguish between the two.
◦ The valid invalid bits scheme can be used for this
purpose.
 Valid-Invalid Bit
◦ With each page table entry a valid–invalid bit is associated
(v  in-memory, 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 address translation, if valid–invalid bit in page table entry

is I  page fault
Page Table When Some Pages Are Not in Main Memory

The page-table entry for a page

that is brought into memory
is set as usual, but the page-table
entry for a page that is not
currently in memory is simply
marked invalid. This situation is
depicted in figure.
(Notice that marking a page
invalid will have no effect if the
process never attempts to access
that page.)
Page Fault
◦ But what happens if the process tries to access a page
that was not brought into memory?
◦ Access to a page marked invalid causes a page fault.
◦ The paging hardware, in translating the address through the
page table, will notice that the invalid bit is set, causing a
trap to the operating system.
◦ This trap is the result of the operating system’s failure to
bring the desired page into memory
Steps in Handling a Page Fault
Procedure for handling page faults.
1. We check an internal table (usually kept with the process control
block) for this process to determine whether the reference was a valid
or an invalid memory access.

2. If the reference was invalid, we terminate the process.

If it was valid but we have not yet brought in that page, we now page it in.

3. Find a free frame and schedule a secondary storage operation to read the
desired page into the newly allocated frame.

5. When the storage read is complete, we modify the internal table kept
with the process and the page table to indicate that the page is now in
memory.

6. We restart the instruction that was interrupted by the trap. The process
can now access the page as though it had always been in memory
Copy-on-Write
◦ Copy-on-Write(CoW) is mainly a resource management technique that
allows the parent and child process to share the same pages of the memory
initially.
◦ If any process either parent or child modifies the shared page, only then the
page is copied. The main use of this technique is in the implementation of the
fork system call in which it shares the virtual memory/pages of the Operating
system.
◦ Recall in the UNIX(OS), the fork() system call is used to create a duplicate
process of the parent process which is known as the child process.
➢The CoW technique is used by several Operating systems like Linux, Solaris,
and Windows XP.
➢The CoW technique is an efficient process creation technique as only the
pages that are modified are copied.
◦ Free pages in this technique are allocated from a pool of zeroed-out pages.
 CoW technique

The main intention behind the CoW technique is that whenever a

parent process creates a child process both parent and child process
initially will share the same pages in the memory.

•These shared pages between parent and child process will be marked
as copy-on-write which means that if the parent or child process will
attempt to modify the shared pages then a copy of these pages will be
created and the modifications will be done only on the copy of pages
by that process and it will not affect other processes.
Before Process 1 Modifies Page C
After Process 1 Modifies Page C

When the Copy-on-write(CoW) technique is used, only those

pages that are modified by either process are copied; all the
unmodified pages can be easily shared by the parent and child
process.
CoW Technique
◦ Whenever it is determined that a page is going to be duplicated using
the copy-on-write technique, then it is important to note the location
from where the free pages will be allocated.

◦ There is a pool of free pages for such requests; provided by many

operating systems.

◦ And these free pages are allocated typically when the stack/heap for a
process must expand or when there are copy-on-write pages to manage.

◦ These pages are typically allocated using the technique that is known
as Zero-fill-on-demand. And the Zero-fill-on-demand pages are
zeroed-out before being allocated and thus erasing the previous content.
 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
Need For Page Replacement

If no frame is free, we find one that is

not currently being used and free it.
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 the victim frame to secondary storage (if necessary);
change the page and frame tables accordingly

[Link] the desired page into the (newly) free frame; update the
page and frame tables

[Link] the process from where the page fault occurred.

Basic Page Replacement

Use modify (dirty) bit to reduce overhead of page transfers

– only modified pages are written to disk
 Basic page replacement
◦ With page replacement an enormous virtual
memory can be provided on a smaller physical
memory
◦ If a page that has been modified is to be replaced,
its contents are copied to the disk.
◦ A later reference to that page will cause a page
fault.
◦ At that time, the page will be brought back into
memory, replacing some other page in the process.
 Basic Page Replacement

◦ Two major problems must be solved to implement demand

paging
◦ Frame allocation algorithm:- Decide frames for process
◦ Page-replacement algorithm:- decide frames which are to
be replaced.
◦ How to select a page replacement algorithm?
◦ One having the lowest page-fault rate.
◦ Evaluate algorithm by running it on a particular string of
memory references (reference string) and computing the
number of page faults on that string
◦ The number of frames available should be determined
Page replacement algorithms

[Link](First in First out)

[Link]
[Link](Least Recently Used)
First In First Out(FIFO)

◦ Associates with each page the time when that page

was brought into memory
◦ When a page must be replaced, the oldest page is
replaced
◦ FIFO queue is maintained to hold all pages in
memory
◦ The one at the head of queue is replaced and the
page brought into memory is inserted at the tail of
queue
First In First Out(FIFO) –
Problem 1
◦ A system uses 3 page frames for storing process
pages in main memory. It uses the First in First out
(FIFO) page replacement policy. Assume that all
the page frames are initially empty. What is the
total number of page faults that will occur while
processing the page reference string given below-
4 , 7, 6, 1, 7, 6, 1, 2, 7, 2

◦ Also calculate Hit and Miss Ratio.

Problem 1
Solution:

From here,
Total number of page faults occurred = 6
FIFO Problem 1
Solution:
◦ Calculating Hit ratio-

Total number of page hits

= Total number of references – Total number of page misses or page faults
= 10 – 6
=4
Thus, Hit ratio
= Total number of page hits / Total number of references
= 4 / 10
= 0.4 or 40%

Miss ratio = 1 – Hit ratio

= 1 – 0.4
= 0.6 or 60%
First In First Out(FIFO) –
Problem 2
First In First Out(FIFO) – Problem 2 -
Solution

Total Page Fault = 9

Total Page References = 12

Hit Ratio: 3/12= 25%

Miss Ratio: 9/12= 75%

 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
 Belady’s anomaly
The rate of page faults varies directly with the number of frames
allocated to the individual process.
The increase in the number of frames considerably decreases the
number of page faults.
However, sometimes reverse action occurs when the increased
number of frames results in increased page faults. This exception is
known as the Belady’s Anomaly. The occurrence of this exception
depends on the page replacement algorithm, which governs
the demand paging process.

The page replacement algorithms in which Belady’s

Anomaly occurs the most includes:
[Link] In First Out (FIFO)
[Link] Chance Algorithm
[Link] Page Replacement Algorithm
Consider the reference string is-
0, 1, 2, 3, 0, 1, 4, 0, 1, 2, 3, 4

Now, observe the following two cases-

Case-01: When frame size = 3

Number of page faults = 9

 Number of page faults = 10

From here, we can observe-

At stage-07 and stage-08 in case-02, main memory does not contain the set
of pages that are present in the corresponding stages in case-01.
Thus, FIFO page replacement algorithm does not follow the stack property.
Hence, it suffers from Belady’s Anomaly.
As a proof, number of page faults increase when the number of frames is
increased from 3 to 4.
Optimal Page Replacement Algorithm-

◦ This algorithm replaces the page that will not be referred by

the CPU in future for the longest time.
◦ It is practically impossible to implement this algorithm.
◦ This is because the pages that will not be used in future for
the longest time can not be predicted.
◦ However, it is the best known algorithm and gives the least
number of page faults.
◦ Hence, it is used as a performance measure criterion for
other algorithms.
Optimal Page Replacement Algorithm-
Problem 1
◦ A system uses 3 page frames for storing process pages in
main memory. It uses the Optimal page replacement policy.
Assume that all the page frames are initially empty. What is
the total number of page faults that will occur while
processing the page reference string given below-
4 , 7, 6, 1, 7, 6, 1, 2, 7, 2
◦ Also calculate the hit ratio and miss ratio.
 Optimal Page Replacement Algorithm- Problem 1
Solution
Total number of references = 10

From here,
Total number of page faults occurred = 5
•Hit ratio = 0.5 or 50%
•Miss ratio = 0.5 or 50%
Optimal Page Replacement Algorithm-
Problem 2
◦ A system uses 4 page frames for storing process pages in
main memory. It uses the Optimal page replacement policy.
Assume that all the page frames are initially empty. What is
the total number of page faults that will occur while
processing the page reference string given below-

◦ Also calculate the hit ratio and miss ratio.

Optimal Page Replacement Algorithm-
Problem 2
Solution:

Total Page Fault = 6

Total Page References = 12

Hit Ratio: 6/12= 50%

Miss Ratio: 6/12= 50%

LRU Page Replacement Algorithm-

•As the name suggests, this algorithm works

on the principle of “Least Recently Used”.
•It replaces the page that has not been
referred by the CPU for the longest time.
Least Recently Used Page Replacement Algorithm–
Problem 1

A system uses 3 page frames for storing process pages in

main memory. It uses the Least Recently Used (LRU) page
replacement policy. Assume that all the page frames are
initially empty. What is the total number of page faults that
will occur while processing the page reference string given
below-
4 , 7, 6, 1, 7, 6, 1, 2, 7, 2
◦ Also calculate the hit ratio and miss ratio
LRU - Problem 1
Solution:

Total number of references = 10

From here,
Total number of page faults occurred = 6
In the similar manner as above-
•Hit ratio = 0.4 or 40%
•Miss ratio = 0.6 or 60%
 Least Recently Used Page Replacement Algorithm–
Problem 2
A system uses 4 page frames for storing process pages in main
memory. It uses the Least Recently Used (LRU) page replacement
policy. Assume that all the page frames are initially empty. What is
the total number of page faults that will occur while processing
the page reference string given below-

◦ Also calculate the hit ratio and miss ratio

LRU - Problem 2
Solution:

Total Page Fault = 8

Total Page References = 12

Hit Ratio: 4/12= 33.33 %

Miss Ratio: 8/12=66..67 %

Thrashing
◦ If the number of frames allocated to a low-priority process falls below
the minimum number required by the computer architecture, we must
suspend, that process's execution. We should then page out its
remaining pages, freeing all its allocated frames
◦ If the process does not have the number of frames it needs to support
pages in active use, it will quickly page-fault. At this point, it must
replace some page.
◦ However, since all its pages are in active use, it must replace a page that
will be needed again right away. Consequently, it quickly faults again,
and again, and again, replacing pages that it must bring back in
immediately.
◦ This high paging activity is called thrashing. A process is thrashing
if it is spending more time paging than executing.
Causes of Thrashing
Thrashing in Operating System affects the performance of execution.
◦ Initially, when the CPU utilization is low, then the process scheduling
mechanism loads many processes into the Memory simultaneously so
that the Degree of Multiprogramming can be increased.
◦ In this situation, we have more processes than the available number of
frames in Memory. Allocation of the limited amount of frames to each
process.
◦ When any higher priority Process arrives in Memory and if the frame is not
freely available at that time, then the other process that occupied the frame
which resides in the frame will move to secondary storage, and this free
frame is now allocated to a newly arrived higher priority process.
◦ In other words, we can say that as the Memory fills up, the process starts to
spend a lot of time for the required pages to be swapped in; again, CPU
utilization becomes low because most of the processes are waiting for pages.
Thrashing
◦ As the degree of multiprogramming increases to
increase the CPU Utilization, it causes Thrashing
after some time
 Techniques to handle Thrashing
◦ A locality is a set of pages that are actively used
together. The locality model states that as a process
executes, it moves from one locality to another. Thus,
a program is generally composed of several different
localities which may overlap.
◦ For example, when a function is called, it defines a
new locality where memory references are made to the
function call instructions, local and global variables,
etc. Similarly, when the function is exited, the process
leaves this locality.
Techniques to handle Thrashing
1. Working set model:
This model is based on the above-stated concept of the Locality Model.
◦ The basic principle states that if we allocate enough frames to a process
to accommodate its current locality, it will only fault whenever it
moves to some new locality. But if the allocated frames are lesser than
the size of the current locality, the process is bound to thrash.
◦ According to this model, based on parameter A, the working set is defined
as the set of pages in the most recent 'A' page references. Hence, all the
actively used pages would always end up being a part of the working set.
◦ The accuracy of the working set is dependent on the value of
parameter A.
◦ If A is too large, then working sets may overlap. On the other hand, for
smaller values of A, the locality might not be covered entirely.
 Techniques to handle Thrashing
◦ If D is the total demand for frames and WSSi is the working set size for
process i,
D = ⅀ WSSi
Now, if 'm' is the number of frames available in the memory, there are two
possibilities:
• D>m, i.e., total demand exceeds the number of frames, then thrashing will
occur as some processes would not get enough frames.
• D<=m, then there would be no thrashing.
◦ If there are enough extra frames, then some more processes can be loaded
into the memory. On the other hand, if the summation of working set sizes
exceeds the frames' availability, some of the processes have to be suspended
(swapped out of memory).
◦ This technique prevents thrashing along with ensuring the highest degree of
multiprogramming possible. Thus, it optimizes CPU utilization.
 Techniques to handle Thrashing

2. Page fault frequency

Techniques to handle Thrashing
◦ If the page fault rate is too high, it indicates that the process has too
few frames allocated to it. On the contrary, a low page fault rate
indicates that the process has too many frames.
◦ Upper and lower limits can be established on the desired page fault
rate, as shown in the diagram.
◦ If the page fault rate falls below the lower limit, frames can be
removed from the process. Similarly, if the page faults rate exceeds
the upper limit, more frames can be allocated to the process.
◦ In other words, the graphical state of the system should be kept limited
to the rectangular region formed in the given diagram.
◦ If the page fault rate is high with no free frames, some of the processes
can be suspended and allocated to them can be reallocated to other
processes. The suspended processes can restart later.