Scribd
Upload
10 views

Notes on Page Replacement Algorithms

Uploaded by

aryan rusia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
10 views

Notes on Page Replacement Algorithms

Uploaded by

aryan rusia
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Page Replacement Algorithms

 A virtual memory system which is a combination of hardware and software


techniques. The memory management software system handles all the
software operations for the efficient utilization of memory space. It decides
(1) which page in main memory required to be removed to make room for a
new page, (2) when a new page is to be transferred from auxiliary memory
to main memory, and (3) where the page is to be placed in main memory.

 When a program starts execution, one or more pages are transferred into
main memory and the page table is set to indicate their position. The
program is executed from main memory until it attempts to reference a
page that is still in auxiliary memory. This condition is called page fault.

 When page fault occurs, the execution of the present program is suspended
until the required page is brought into main memory.

 If main memory is full, it would be necessary to remove a page from a


memory block to make room for the new page. The policy for choosing
pages to remove is determined from the replacement algorithm that is
used. The goal of a replacement policy is to try to remove the page least
likely to be referenced in the immediate future.

 Two of the most common replacement algorithms used are the first-in,
FIFO first-out (FIFO) and the least recently used (LRU).

 The FIFO algorithm selects for replacement the page that has been in
memory the longest time. When a new page must be loaded, the page least
recently brought in is removed.

 The FIFO replacement policy has the advantage of being easy to implement.
It has the disadvantage that under certain circumstances pages are
removed and loaded from memory too frequently.

 The LRU policy is more difficult to implement but has been more attractive
on the assumption that the least recently used page is a better candidate
for removal than the least recently loaded page as in FIFO.
Example Using FIFO: Consider a system with virtual space of 8k, main memory
space of 4k and page is of 1k. Find the number of page faults if the system
makes page referencing during execution of a program as 4, 2, 0, 1, 2, 6, 1, 4, 0,
1, 0, 2, 3, 5, and 7.

No. of pages in virtual address space= 8k/1k =8


No. of blocks main memory space= 4k/1k =4

4 2 0 1 2 6 1 4 0 1 0 2 3 5 7

4 4 4 4 6 6 6 6 5 5
2 2 2 2 4 4 4 4 7
0 0 0 0 2 2 2 2
1 1 1 1 3 3 3

PF PF PF PF NPF PF NPF PF NPF NPF NPF PF PF PF PF

(PF: page fault; NPF: No page fault; Numbers in red colour are least recently
loaded pages which is to be replaced by new page)

Total no. of page accessed= 15

Total no. page faults =10

Page fault/miss ratio = 10/15 = 2/3

Page hit ratio = 1- 2/3= 1/3

Above Example Using LRU:

4 2 0 1 2 6 1 4 0 1 0 2 3 5 7

4 4 4 4 6 6 6 2 2 2 2
2 2 2 2 2 0 0 0 0 7
0 0 0 4 4 4 3 3 3
1 1 1 1 1 1 5 5

PF PF PF PF NPF PF NPF PF PF NPF NPF PF PF PF PF

Numbers in red colour are least recently used pages which is to be replaced by
new page)

Total no. page faults =11

You might also like