Virtual Memory

and
Demand Paging
 Virtual Memory
⚫ Virtual memory is a mechanism
that creates the illusion of having
a very big main memory.

⚫ It is a technique that allows the

execution of processes that are
not completely in memory. This
technique frees programmers
from the concerns of
memory-storage limitations.

⚫ Need to allow pages to be

swapped in and out.
Virtual memory – benefits:
• Only part of the process needs to be in memory for execution.
• So the user can store larger processes than physical memory.
• Logical address space can therefore be much larger than physical address space.
• More program could be run concurrently
• Increase in CPU utilization and throughput but with no increase in response time or
turnaround time.
• Less I/O needed to load or swap process into memory, so each process would run faster.

Virtual memory can be implemented via:

• Demand paging
• Demand segmentation
 Demand Paging

• Loading the entire program in physical memory at program execution time is not so
good because the user doesn’t need the entire program in memory at a time.
• An alternative strategy is to load pages only as they are needed. This technique is
known as demand paging.

• Demand paging is a method of virtual memory management where the pages are
only loaded when they are demanded by the CPU 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.
 Lazy Swapper

• Demand paging uses a

lazy swapper.

• A lazy swapper never

swaps a page into
memory unless that
page will be needed.

• In Demand paging,
pager is more suitable
than swapper .

Transfer of a paged memory to contiguous disk space.

Bring a page into memory only when it
is needed.

some form of hardware support is

needed to distinguish between the pages
that are in memory and the pages that are
on the disk. The valid -invalid bit
scheme can be used for this purpose.

With each page table entry a

valid–invalid bit is associated (v ⇒
in-memory – memory resident, i ⇒
not-in-memory)
disk

Initially valid–invalid bit is set to i on all

entries
 valid–invalid bit

When this bit is set to “valid,” the associated page is both legal and
in memory. If the bit is set to “invalid,” the page either is not valid
(that is, not in the logical address space of the process) or is valid but
is currently on the disk.

With each page table entry a valid–invalid bit is associated (1 ⇒

Valid, 0 ⇒ Invalid) Initially valid–invalid bit is set to 0 on all
entries.

Page table requires a "resident“ bit showing that page is/isn't in

memory. (1 ⇒ in-memory, 0 ⇒ not-in-memory)

It makes more sense to have two bits – one indicating that the page is
legal (valid) and a second to show that the page is in memory.
 Page Fault
• The page fault occurs when the demanded page is not present in the main memory. In other
words, the page with an invalid bit.
• Page fault can be handled by OS

Handling Page fault: Following sequence of events are use to handle page fault.

1. Load the instruction, and check for the relevant page in the page table.
2. If the bit of the referenced page is invalid, a page fault occurs. A trap occurs that is sent
to the operating system.
3. The system checks for the required page in the secondary memory.
4. Using the frame replacement algorithm, find the frame location. Read the data from disk
to memory.
5. Update the page table entry by making an invalid bit to valid.
6. Restart the instruction.
disk
 Performance of Demand Paging

• Demand paging can significantly affect the performance of a computer system.

• the effective access time is

Effective Access Time (EAT) = (1 - p) x memory access + p x page fault time.

where,
p be the probability of a page fault ; Page Fault Rate 0 ≤ p ≤ 1.0
if p = 0 no page faults
if p = 1, every reference is a fault
Demand Paging Example 1

Memory access time = 200 nanosecond

Avg page fault service time=8 millisec

EAT = (1 – p) x 200 + p (8,000,000)

= 200+7999800P nanosecond
•What happens if there is no free frame?
•Generally, the number of pages of the process is more than the frames available to the process.
Hence, when the process request for a page and no free frame is available the system will replace one
of the pages in the memory with the new one.
•Page replacement – find some page in memory, but not really in use, swap it out.

•Now, which page to select for replacement?

•Whenever a process requests data from a page which is not in the memory then the system uses a
page replacement algorithm to swap out an existing page to make space for the new page.

•Algorithm performance:
•-want an algorithm which will result in minimum number of page faults.
•-Want lowest page-fault rate.
 Page Replacement

Page replacement takes the following approach.

[Link] the location of the desired page on the disk.

[Link] a free frame:
a) If there is a free frame, use it.
b) If there is no free frame, use a page-replacement algorithm to select a victim frame
c) Write the victim frame to the disk; change the page and frame tables accordingly.
[Link] the desired page into the newly freed frame; change the page and frame tables.
[Link] the user process
Page Replacement
 Page replacement algorithm

There are three page replacement algorithms:

•First In First Out (FIFO)

•Least Recently Used First (LRU)

•Optimal Page Replacement

 A FIFO replacement algorithm associates
with each page the time when that page
First In First was brought into memory.

Out (FIFO) When a page must be replaced, the oldest

page is chosen.
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

1 1
0 0 0
7 7 7 2

Since 0 is already in the memory so no need for page fault.

Now no empty frame is left to insert page 2.
Which page came in first? 7, 0 or 1.
As page 7 came first so it is replaced.
 Note: Do not think that as “0” is used here so it is not the one that came in first (and “1” came first).
Look in the frames and see which out of 1, 0 and 2 was written first in frames.
Example The answer is “0”

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

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

Which page came in first? 1, 0 or 2.

As page 0 came first so it is replaced.
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Which page came in first? 1, 3 or 2.

As page 1 came first so it is replaced.
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Which page came in first? 0, 3 or 2.

As page 2 came first so it is replaced.
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 3

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

On similar lines.

Total No. of page faults = 11

FIFO Illustrating Belady’s Anomaly

Belady’s Anomaly-for some

page-replacement algorithms, the
page-fault rate may increase as the
number of allocated frames increases.

Example:

For the reference string

1,2,3,4,1,2,5,1,2,3,4,5

page fault is 9 with frames 3 and page

fault is 10 with frames 4.
Example 2 :

○ 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)
Example 2 :
○ 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)
 LRU replacement associates with each page the
time of that page's last use.

When a page must be replaced, LRU chooses

the page that has not been used for the longest
LRU period of time

better than FIFO but worse than OPT

Generally good algorithm and frequently used

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

1 1
0 0 0
7 7 7 2

Now no empty frame is left to insert page 2.

Which page is the most recently used page? 7, 0 or 1.
1 (look into the history)
Which page is the next recently used page? 7 or 0
0
Hence the least recently used page is “7”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

1 1
0 0 0
7 7 7 2

Since 0 is already in the memory so no need for page fault.

Example This selection shows the difference
between FIFO and LRU

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

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

Which page is the most recently used page? 1, 0 or 2.

0 (look into the history)
Which page is the next recently used page? 1 or 2
2
Hence the least recently used page is “1”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Since 0 is already in the memory so no need for page fault.

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

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

Which page is the most recently used page? 3, 0 or 2.

0 (look into the history)
Which page is the next recently used page? 3 or 2
3
Hence the least recently used page is “2”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Which page is the most recently used page? 3, 0 or 4.

4 (look into the history)
Which page is the next recently used page? 3 or 0
0
Hence the least recently used page is “3”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Which page is the most recently used page? 2, 0 or 4.

2 (look into the history)
Which page is the next recently used page? 4 or 0
4
Hence the least recently used page is “0”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

On similar lines.
Total Number of page faults = 10
Example 2 :
○ 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)
 • Replace the page that will not be used for the longest
period of time(in future).

Optimal • It has the lowest page-fault rate of all algorithms and

will never suffer from Belady's anomaly-hence known
as OPT or MIN.

• It is difficult to implement, because it requires future

knowledge of the reference string.
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

1 1
0 0 0
7 7 7 2

Now no empty frame is left to insert page 2.

Which page will be again required in near future? 7, 0 or 1.
0 (look in the future page requests) [just look for first occurrence]
Which page will be required next? 7 or 1
1
Hence the page that should be replaced is “7”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

1 1
0 0 0
7 7 7 2

Since 0 is already in the memory so no need for page fault.

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

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

Which page will be again required in near future? 1, 0 or 2.

0 (look in the future page requests) [just look for first occurrence]
Which page will be required next? 2 or 1
2
Hence the page that should be replaced is “1”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Since 0 is already in the memory so no need for page fault.

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

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

Which page will be again required in near future? 3, 0 or 2.

2 (look in the future page requests) [just look for first occurrence]
Which page will be required next? 2 or 1
3
Hence the page that should be replaced is “0”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Since 2 is already in the memory so no need for page fault.

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

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

Since 3 is already in the memory so no need for page fault.

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

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

Which page will be again required in near future? 3, 4 or 2.

3 (look in the future page requests) [just look for first occurrence]
Which page will be required next? 2 or 1
2
Hence the page that should be replaced is “4”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Since 3 is already in the memory so no need for page fault.

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

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

Since 2 is already in the memory so no need for page fault.

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

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

Which page will be again required in near future? 3, 0 or 2.

2 (look in the future page requests) [just look for first occurrence]
Out of 3 and 0 we choose with FIFO
3 came in first
Hence the page that should be replaced is “3”
Example
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2

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

Since 2 is already in the memory so no need for page fault.

Example 2 :
○ 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)
 Consider a program that consists of 8 pages (from 0 to 7) and we have 4
page frames in the physical memory for the pages. The page reference
string is :

•
1 2 3 2 5 6 3 4 6 3 7 3 1 5 3 6 3 4 2 4 3 4 5 1