Question

Consider the following string of page references:

5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.

showing the frame allocation for:

a. Optimal

b. LRU (least recently used)

c. FIFO (first-in-first-out)

d. List the total number of page faults for each policy. Count page faults only after all frames

have been initialized.

Answer 1

Note: If required page is not present in RAM then its page fault. If yes then its page hit.

a. Optimal Replacement : In this algorithm, pages are replaced which would not be used for the longest duration of time in the future.

string of page references:

5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.

Let number of page frame be = 3

Initially all slots are empty, so when 5, 7, 8 came they are allocated to the empty slots

5

5

miss page fault=1

7

7

5

miss page fault=2

8

8

7

5

miss page fault=3

9 // check which page will not be used in near future={5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.} i.e either you can replace 5 or 8 because it will not be used in near future

8

7

9

miss page fault=4

7

8

7

9

hit

3 //check which page will not be used in near future={5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.} ie. use can ureplace only 8 as 7 and 9 will be used in future

3

7

9

miss page fault = 5

7

3

7

9

hit

4 ////check which page will not be used in near future={5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.} ie. 9 and 3 will be used in immediate future so replace 7

3

4

9

miss page fault = 6

9

3

4

9

hit

3

3

4

9

hit

7 ////check which page will not be used in near future={5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.} ie. 9 and 3 will be used in immediate future so replace 4

3

7

9

miss page fault= 7

3

3

7

9

hit

9

3

7

9

hit

Total number of page fault (Optimal) = 7

b. LRU (least recently used) : In this algorithm page will be replaced which is least recently used.

string of page references:

5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.

Let number of page frame be = 3

Initially all slots are empty, so when 5, 7, 8 came they are allocated to the empty slots

5

5

miss page fault=1

7

7

5

miss page fault=2

8

8

7

5

miss page fault=3

9 // check which page was least recently used before={5, 7, 8} i.e 5 was least recently used and 8 most recently used so replace 5

8

7

9

miss page fault=4

7

8

7

9

hit

3 /check which page was least recently used before={5, 7, 8,9,7} i.e 8 was least recently used and 9 most recently used so replace 8

3

7

9

miss page fault = 5

7

3

7

9

hit

4 //check which page was least recently used before={5, 7, 8,9,7,3,7} i.e 9 was least recently used and 7 most recently used so replace 9

3

7

4

miss page fault = 6

9 //check which page was least recently used before={5, 7, 8,9,7,3,7,4} i.e 3 was least recently used and 4 most recently used so replace 3

9

7

4

miss page fault = 7

3 //check which page was least recently used before={5, 7, 8,9,7,3,7,4,9} i.e 7 was least recently used and 9 most recently used so replace 7

9

3

4

miss page fault = 8

7 //check which page was least recently used before={5, 7, 8,9,7,3,7,4,9,3} i.e 4 was least recently used and 3 most recently used so replace 4

9

3

7

miss page fault= 9

3

3

7

9

hit

9

3

7

9

hit

Total number of page fault (LRU) = 9

C. FIFO (first-in-first-out) : In this algorithm, the operating system keeps track of all pages in the memory in a queue, the oldest page is in the front of the queue. When a page needs to be replaced, page in the front of the queue is selected.

string of page references:

5, 7, 8,9, 7, 3, 7, 4, 9, 3, 7, 3, 9.

Let number of page frame be 4

Initially all slots are empty, so when 5, 7, 8,9 came they are allocated to the empty slots

5

5

miss page fault=1

7

7

5

miss page fault=2

8

8

7

5

miss page fault=3

9

9

8

7

5

miss page fault=4

7 // it is already in memory so —> page hit

9

8

7

5

hit

3

9

8

7

3

miss page fault=5  

7 // it is already in memory so —> page hit

9

8

7

3

hit

4

9

8

4

3

miss page fault=6

9 // it is already in memory so —> page hit

9

8

4

3

hit

3 // it is already in memory so —> page hit

9

8

4

3

hit

7

9

7

4

3

miss page fault=7

3 // it is already in memory so —> page hit

9

8

4

3

hit

9 // it is already in memory so —> page hit

9

8

4

3

hit

Total number of page fault (FIFO) = 7