Page Replacement Algorithms-

 

Before you go through this article, make sure that you have gone through the previous article on Page Replacement Algorithms.

 

We have discussed-

• When a page fault occurs, the required page has to be brought from the secondary memory.
• If all the frames of main memory are already occupied, then a page has to be replaced.
• Page replacement algorithms help to decide which page should be replaced.

 

In this article, we will discuss some important results.

 

Important Results-

 

Result-01: For a Reference String Consisting Of Repeated Sequence Of Page Numbers-

 

For such a reference string,

• Optimal page replacement algorithm replaces the most recently used page to minimize the page faults.
• This is because most recently page will be required after the longest time.
• Thus, Optimal page replacement algorithm acts as Most Recently Used (MRU) page replacement algorithm.

 

In other words,

• MRU page replacement algorithm will behave as Optimal page replacement algorithm.
• MRU page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string consisting of a repeated sequence of page numbers-

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

 

Here,

• Both Optimal and MRU page replacement algorithm replaces the most recently used page.
• Most recently used page will be required after the longest time.
• Hence, both these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 12

 

NOTES-

 

Note-01:

 

• These are the minimum number of page faults that are possible.
• If any other page replacement algorithm is used, it will surely give rise to more number of page faults.
• FIFO and LRU page replacement algorithm give rise to 24 number of page faults.

 

Note-02:

 

• CPU may generate such a reference string when executing loops.
• This is because while executing loops, same set of instructions have to be executed again and again.

 

Note-03:

 

• Principle of locality states that the next reference would be most probably from the most recently used pages.
• Here, the behavior of Optimal page replacement algorithm contradicts with the principle of locality.
• Here, Optimal algorithm replaces the most recently used page to give the optimal performance.
• So, from here we can infer that principle of locality does not hold true in certain scenarios.

 

Result-02: For a Reference String Where First Half String Is a Mirror Image Of Other Half-

 

For such a reference string,

• Optimal page replacement algorithm replaces the least recently used page or firstly arrived page to minimize page faults.
• This is because such a page will be required after the longest time.
• Thus, Optimal page replacement algorithm acts as LRU and FIFO page replacement algorithm.

 

In other words,

• LRU and FIFO page replacement algorithm will behave as Optimal page replacement algorithm.
• LRU and FIFO page replacement algorithm gives the optimal performance.

 

Example-

 

Consider the following reference string where first half string is a mirror image of other half string-

1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1

 

Here,

• Optimal, LRU and FIFO page replacement algorithms replaces the least recently used or firstly arrived page.
• Least recently used or firstly arrived page will be required after the longest time.
• Hence, all these algorithms give the optimal performance.

 

 

Total number of page faults occurred = 14

 

• These are the minimum number of page faults that are possible.
• If any other page replacement algorithm is used, it will surely give rise to more number of page faults.

 

Remember-

 

• Optimal page replacement algorithm always gives the best performance in every scenario.
• This is because it foresees the future and takes the form of an algorithm which gives the best performance in that scenario.

 

Next Article- Segmentation in OS

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Page Fault in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Page Fault in OS.

 

We have discussed-

• A page fault occurs when a page referenced by the CPU is not found in the main memory.
• The required page has to be brought from the secondary memory into the main memory.
• A page has to be replaced if all the frames of main memory are already occupied.

 

Page Replacement-

 

Page replacement is a process of swapping out an existing page from the frame of a main memory and replacing it with the required page.

 

Page replacement is required when-

• All the frames of main memory are already occupied.
• Thus, a page has to be replaced to create a room for the required page.

 

Page Replacement Algorithms-

 

Page replacement algorithms help to decide which page must be swapped out from the main memory to create a room for the incoming page.

 

Various page replacement algorithms are-

 

 

1. FIFO Page Replacement Algorithm
2. LIFO Page Replacement Algorithm
3. LRU Page Replacement Algorithm
4. Optimal Page Replacement Algorithm
5. Random Page Replacement Algorithm

 

A good page replacement algorithm is one that minimizes the number of page faults.

 

FIFO Page Replacement Algorithm-

 

• As the name suggests, this algorithm works on the principle of “First in First out“.
• It replaces the oldest page that has been present in the main memory for the longest time.
• It is implemented by keeping track of all the pages in a queue.

 

LIFO Page Replacement Algorithm-

 

• As the name suggests, this algorithm works on the principle of “Last in First out“.
• It replaces the newest page that arrived at last in the main memory.
• It is implemented by keeping track of all the pages in a stack.

 

NOTE Only frame is used for page replacement during entire procedure after all the frames get occupied.

 

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.

 

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.

 

Random Page Replacement Algorithm-

 

• As the name suggests, this algorithm randomly replaces any page.
• So, this algorithm may behave like any other algorithm like FIFO, LIFO, LRU, Optimal etc.

 

PRACTICE PROBLEMS BASED ON PAGE REPLACEMENT ALGORITHMS-

 

Problem-01:

 

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 the hit ratio and miss ratio.

 

Solution-

 

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 6

 

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%

 

Calculating Miss ratio-

 

Total number of page misses or page faults = 6

 

Thus, Miss ratio

= Total number of page misses / Total number of references

= 6 / 10

= 0.6 or 60%

 

Alternatively,

Miss ratio

= 1 – Hit ratio

= 1 – 0.4

= 0.6 or 60%

 

Problem-02:

 

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.

 

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%

 

Problem-03:

 

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.

 

Solution-

 

Total number of references = 10

 

 

From here,

Total number of page faults occurred = 5

 

In the similar manner as above-

• Hit ratio = 0.5 or 50%
• Miss ratio = 0.5 or 50%

 

To gain better understanding about Page Replacement Algorithms,

Watch this Video Lecture

 

Next Article- Practice Problems On Page Fault

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Page Fault in OS-

 

Before you go through this article, make sure that you have gone through the previous article on Page Fault in OS.

 

We have discussed-

• A page fault occurs when the referenced page is not found in the main memory.
• Page fault handling routine is executed on the occurrence of page fault.
• The time taken to service the page fault is called as page fault service time.

 

Effective Access time-

 

In a multilevel paging scheme using TLB without any possibility of page fault, effective access time is given by-

 

 

In a multilevel paging scheme using TLB with a possibility of page fault, effective access time is given by-

 

 

Also Read- Page Replacement Algorithms

 

PRACTICE PROBLEMS BASED ON PAGE FAULTS IN OS-

 

Problem-01:

 

Let the page fault service time be 10 ms in a computer with average memory access time being 20 ns. If one page fault is generated for every 10⁶ memory accesses, what is the effective access time for the memory?

1. 21 ns
2. 30 ns
3. 23 ns
4. 35 ns

 

Solution-

 

Given-

• Page fault service time = 10 ms
• Average memory access time = 20 ns
• One page fault occurs for every 10⁶ memory accesses

 

Page Fault Rate-

 

It is given that one page fault occurs for every 10⁶ memory accesses.

Thus,

Page fault rate

= 1 / 10⁶

= 10^-6

 

Effective Access Time With Page Fault-

 

It is given that effective memory access time without page fault = 20 ns.

 

Now, substituting values in the above formula, we get-

Effective access time with page fault

= 10^-6 x { 20 ns + 10 ms } + ( 1 – 10^-6 ) x { 20 ns }

= 10^-6 x 10 ms + 20 ns

= 10^-5 ms + 20 ns

= 10 ns + 20 ns

= 30 ns

Thus, Option (B) is correct.

 

Problem-02:

 

Suppose the time to service a page fault is on the average 10 milliseconds, while a memory access takes 1 microsecond. Then, a 99.99% hit ratio results in average memory access time of-

1. 1.9999 milliseconds
2. 1 millisecond
3. 9.999 microseconds
4. 1.9999 microseconds
5. None of these

 

Solution-

 

Given-

• Page fault service time = 10 msec
• Average memory access time = 1 μsec
• Hit ratio = 99.99% = 0.9999

 

Page Fault Rate-

 

Page fault rate

= 1 – Hit ratio

= 1 – 0.9999

= 0.0001

 

Effective Access Time With Page Fault-

 

It is given that effective memory access time without page fault = 1 μsec.

 

Substituting values in the above formula, we get-

Effective access time with page fault

= 0.0001 x { 1 μsec + 10 msec } + 0.99999 x 1 μsec

= 0.0001 μsec + 0.001 msec + 0.9999 μsec

= 1 μsec + 0.001 msec

= 1 μsec + 1 μsec

= 2 μsec or 0.002 msec

Thus, Option (E) is correct.

 

Problem-03:

 

If an instruction takes i microseconds and a page fault takes an additional j microseconds, the effective instruction time if on the average a page fault occurs every k instruction is-

1. i + j / k
2. i + j x k
3. (i + j) / k
4. (i + j) x k

 

Solution-

 

Given-

• Page fault service time = j μsec
• Average memory access time = i μsec
• One page fault occurs every k instruction

 

Page Fault Rate-

 

It is given that one page fault occurs every k instruction.

Thus,

Page fault rate

= 1 / k

 

Effective Access Time With Page Fault-

 

It is given that effective memory access time without page fault = i μsec

 

Now, substituting values in the above formula, we get-

Effective access time with page fault

= (1 / k) x { i μsec + j μsec } + ( 1 – 1 / k) x { i μsec }

= j / k μsec + i μsec

= i + j / k μsec

Thus, Option (A) is correct.

 

Problem-04:

 

Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time and two memory accesses. The TLB hit ratio is 90% and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

1. 645 nanoseconds
2. 1050 nanoseconds
3. 1215 nanoseconds
4. 1230 nanoseconds
5. None of these

 

Solution-

 

Given-

• Number of levels of page table = 2
• Main memory access time = 150 ns
• Page fault service time = 8 msec
• Average instruction takes 100 ns of CPU time and 2 memory accesses
• TLB Hit ratio = 90% = 0.9
• Page fault rate = 1 / 10⁴ = 10^-4

 

Assume TLB access time = 0 since it is not given in the question.

Also, TLB access time is much less as compared to the memory access time.

 

Effective Access Time Without Page Fault-

 

Substituting values in the above formula, we get-

Effective memory access time without page fault

= 0.9 x { 0 + 150 ns } + 0.1 x { 0 + (2+1) x 150 ns }

= { 0.9 x 150 ns } + { 0.1 x 450 ns }

= 135 ns + 45 ns

= 180 ns

 

Effective Access Time With Page Fault-

 

Substituting values in the above formula, we get-

Effective access time with page fault

= 10^-4 x { 180 ns + 8 msec } + (1 – 10^-4) x 180 ns

= 8 x 10^-4 msec + 180 ns

= 8 x 10^-7 sec + 180 ns

= 800 ns + 180 ns

= 980 ns

 

Effective Average Instruction Execution Time-

 

Effective Average Instruction Execution Time

= 100 ns + 2 x Effective memory access time with page fault

= 100 ns + 2 x 980 ns

= 100 ns + 1960 ns

= 2060 ns

Thus, Option (E) is correct.

 

Problem-05:

 

A demand paging system takes 100 time units to service a page fault and 300 time units to replace a dirty page. Memory access time is 1 time unit. The probability of a page fault is p. In case of a page fault, the probability of page being dirty is also p. It is observed that the average access time is 3 time units. Then the value of p is-

1. 0.194
2. 0.233
3. 0.514
4. 0.981
5. None of these

 

Solution-

 

Given-

• Page fault service time = 100 time units
• Time taken to replace dirty page = 300 time units
• Average memory access time = 1 time unit
• Page fault rate = p
• Probability of page being dirty = p
• Effective access time = 3 time units

 

Now, According to question-

3 time units = p x { 1 time unit + p x { 300 time units } + (1 – p) x { 100 time units } } + (1 – p) x { 1 time unit }

3 = p x { 1 + 300p + 100 – 100p } + (1 – p)

3 = p x { 101 + 200p } + (1 – p)

3 = 101p + 200p² + 1 – p

3 = 100p + 200p² + 1

200p² + 100p – 2 = 0

On solving this quadratic equation, we get p = 0.019258

Thus, Option (E) is correct.

 

Next Article- Belady’s Anomaly

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.