Optimal Page-Replacement policy

Optimal Page-Replacement:

1. This algorithm is a result of discovery by Belady’s Anomaly. 2. This technique replace the page that won’t be in use for longest time. 3. When a page replacement is needed, it looks ahead in the input queue for the page frame which will be referenced only after a long time. 4. The page with the longest reference is swapped. 5. Optimal Page Replacement technique reduces the page faults to the minimum.

Advantages:  It has the lowest page fault rate.  It never suffers from Belady’s Anomaly.

Disadvantages:  This technique is difficult to implement because it needs future knowledge.

Contributor's Info

Created:
0Comment
First In First Out

First In First Out (FIFO):
1. FIFO stands for First In First Out.
2. It is simplest page replacement technique.
3. In this technique, the oldest page is chosen as a victim for replacement.
4. A queue is used to main the pages in the memory.
5. The page present at the head position is removed and the new page is inserted at the tail position.
Advantages:
 It is easy to understand & execute.
Disadvantages:
 However, performance wise it’s not good.
 It suffers from Belady’s Anomaly which says that the page fault increases with the reduction in page frames.

Contributor's Info

Created:
0Comment
Page Replacement Algorithms

There are some page replacement algorithms. The main goal of a page replacement algorithm is to minimize the page fault rate. When number of frames are fixed that is known as static allocation and when number of frames are not fixed that is known as dynamic allocation. There are some static page replacement algorithms as described below.

 

FIFO(First Come First Out) replacement:

This algorithm replaces a page that has longest time or oldest page, when a page fault occurs and there is no available free frame. This algorithm can be implemented using queue or time stamp of pages.

 

Example1:

Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Find the number of page faults using FIFO page replacement algorithm with 3 page frames.

 

1

1

1

4

4

4

5

   

5

5

hit

 

2

2

2

1

1

1

hit

 

3

3

 
   

3

3

3

2

2

 

hit

1

4

 

 

Total number of page faults = 9

 

Example2:

Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Find the number of page faults using FIFO page replacement algorithm with 4 page frames.

 

1

1

1

1

hit

 

5

5

5

5

4

4

 

2

2

2

 

hit

2

1

1

1

1

5

   

3

3

   

3

3

2

2

2

2

     

4

   

4

4

4

3

3

3

 

Total number of page faults = 10

 

Belady’s Anomaly

This is the phenomenon occurs when number of page frames increasing, the number of page faults also increase. Belady’s anomaly occurs in FIFO, Random, and Second chance page replacement algorithms.

Above two examples 1 and example 2 shows this phenomenon in FIFO page replacement algorithm.

 

Optimal Page Replacement

This algorithm replace the page in the memory that will not be used for the longest period of time. This algorithm gives less number of page faults compared to any other algorithms. However, optimal algorithm is not possible to implement in practice.

 

Example:

Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Find the number of page faults using FIFO page replacement algorithm with 3 page frames.

 

1

1

1

1

hit

 

1

hit

 

3

3

 
 

2

2

2

 

hit

2

 

hit

2

4

 
   

3

4

   

5

   

5

5

hit

 

Total number of page faults = 7

 

LRU Page Replacement

LRU(least recently used) page replacement algorithm replaces page that has not been used for the longest period of time. This algorithm can be implemented using stack or counter.

 

Example:

Consider the following reference string:
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Find the number of page faults using FIFO page replacement algorithm with 3 page frames.

 

1

1

1

4

4

4

5

   

3

3

3

 

2

2

2

1

1

1

hit

 

1

4

4

   

3

3

3

2

2

 

hit

2

2

5

 

Total number of page faults = 10

 

Contributor's Info

Created:
0Comment