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-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)

Optimization of First In First Out Disk Scheduling

Q1. How can we optimize First In First Out Disk Scheduling Algorithm?

Ans.A simple optimization to FIFO algorithm is to attach a reference bit for each page in page table. Each time the page is accessed the page bit is set to 1. When a page fault occurs that respective bit is checked and if it is 1 then set the bit to 0 but jumps over that page and looks for another page but if the bit is 0 the page will be removed.

The idea is that the heavy used page in the table will not get out. But in the extreme case when all pages are in heavy use the algorithm will cycle through all the pages setting their bits to zero before finding the page to remove. If it might not find the page to replace, and the bit was set again while it was looking through the others, in which a case the paging system fails.

Numerical Solved By First In First Out Disk Scheduling

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 First Come First Serve Disk Scheduling Algorithm.

Solu:

  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 Fault = 10

Fair Share Scheduling Algorithm

Q1. Explain Fair Share Scheduling.

Ans. Solaris 9 introduced two new classes of scheduling:

  1. Fixed Priority
  2. Fair Share

Threads in fixed priority class have the same priority range as in time sharing system.

Fair Share Scheduling class uses CPU share instead of priorities to make scheduling decisions. CPU share indicates right to available CPU resources and are allocated to a set of processes (known as project).