LRU Approximation Page Replacement Algorithm

Q1. Explain LRU Approximation Page Replacement Algorithm.

Ans. Few computer systems provide sufficient hardware support for true LRU page replacement. Many systems provide some help, however, in the form of a reference bit. The reference bit for a page is set by the hardware whenever that page is referenced (either a read or a write to any byte in the page). Reference bits are associated with each entry in the page table.

Initially, all bits are cleared (to 0) by the operating system. S a user process executes, the bit associated with each page referenced is set (to 1) by the hardware. After some time, we can determine which pages have been used and which have not been used by examining the reference bits, although we do not know the orders of use. This information is the basis for many page replacement algorithms that approximate LRU replacement.

Numerical To Calculate Physical Address

Q1. Consider the following segment table:

Segment Base Length Logical Address
0 219 600 430
1 2300 14 10
2 90 100 2500
3 1327 580 3400
4 1952 96 4112

Calculate the Physical Address.

Solu:

Step 1:

Check logical address, it must be less than length.

Formula:

Physical Address = Logical Address + Base Address

So, for segment 0

Length is less than logical address,

that is,        600 > 430.

Therefore,

Physical Address = 430 + 219

= 649

For segment 1

Length is less than logical address,

That is,       14>10.

Therefore,

Physical Address = 10 + 2300

= 2310

For segment 2

Length is not less than logical address,

that is         100 ≥ 2500.

Therefore,

no physical address.

For segment 3

Length is not less than logical address,

that is, 580 ≥ 3400.

Therefore,

no physical address.

For segment 4

Length is not less than logical address,

that is, 96 ≥ 4112.

Therefore,

no physical address.

Numerical-II Solved For Belady’s Anomaly Problem

Q2. The reference string is:

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

Solve it with 3 frames and 4 frames while using FIFO technique.

Solu: Using 3 frames

1 2 3 4 1 2 5 1 2 3 4 5
Frame1 1 1 1 4 4 4 5 5 5 5 5 5
Frame2 2 2 2 1 1 1 1 1 3 3 3
Frame3 3 3 3 2 2 2 2 2 4 4
Faults + + + + + + + +

Page Fault = 9

Using 4 frames

1 2 3 4 1 2 5 1 2 3 4 5
Frame1 1 1 1 1 1 1 5 5 5 5 4 4
Frame2 2 2 2 2 2 2 1 1 1 1 5
Frame3 3 3 3 3 3 2 2 2 2
Frame4 4 4 4 4 4 4 3 3 3
Faults + + + + + + + + + +

Page Fault = 10

(Problem of Belady’s Ananmoly)

 

Numerical For Belady’s Anomaly Problem

Q1. If the reference string is

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

then solve by First In First Out Disk Scheduling Algorithm using physical memory of three frames and four frames.

Q2. The reference string is:

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

Solve it with 3 frames and 4 frames while using FIFO technique.

 

Numerical Solved by Least Recently Used Page Replacement Algorithm

Q1. If the reference string is

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

we have taken the physical memory of three frames, then solve by Least Recently Used Page Replacement Algorithm.

Ans.

7 0 1 2 0 3 0 4 2 3 0 3
Frame1 7 7 7 2 2 2 2 4 4 4 0 0
Frame2 0 0 0 0 0 0 0 0 3 3 3
Frame3 1 1 1 3 3 3 2 2 2 2
Faults + + + + + + + + +

Page Fault = 9 (better than FIFO)

Least Recently Used Page Replacement Algorithm

Q1. Explain Least Recently Used Page Replacement Algorithm.

Ans. This kind of technique includes the removal of those pages which has not been used for a longest period of time also known as Look Backward Technique. It requires a hardware support to make it worthwhile.

Optimal Page Replacement Algorithm

Q1. Explain Optimal Page Replacement Algorithm.

Ans.It is the best page replacement algorithm which is easy to describe but impossible to implement. At the moment when a page fault occurs, some set of pages is in memory. One of these pages will be referenced onto the very next instruction. Other pages may not be referenced until 10, 100, or perhaps 1000instructions occur. Each pages can be labelled with the number of instructions which will be executed before that page is first referenced.

The optimal page replacement algorithm,also known as Look Forward Technique, simply says that the page with the highest labels should be removed. If one page will not be used for 100 instructions and another page will not be used for 50 instructions, removing the former pushes the page fault that will fetch it back as far as possible into the future.

Numerical-I Solved For Belady’s Anomaly Problem

Q1. If the reference string is

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

then solve by First In First Out Disk Scheduling Algorithm using physical memory of three frames and four frames.

The below figure shows how with 3 frames the number of page faults are 9 while we get 10 page faults with 4 frames.

7 0 1 2 0 3 0 4 2 3 0 3
Frame1 7 7 7 2 2 2 2 4 4 4 0 0
Frame2 0 0 0 0 3 3 3 2 2 2 2
Frame3 1 1 1 1 0 0 0 3 3 3
Faults + + + + + + + + + + +

Page faults = 9 (3 frames)

0 1 2 3 0 1 4 0 1 2 3 4
Frame1 0 0 0 0 0 0 4 4 4 4 3 3
Frame2 1 1 1 1 1 1 0 0 0 0 4
Frame3 2 2 2 2 2 2 1 1 1 1
Frame4 3 3 3 3 3 3 2 2 2
Faults + + + + + + + + + +

Page faults = 4 (4 frames)