Question

Answer the following questions based on the Memory Management tasks of an Operating System.
	5

Consider the following sequence of page references:

5, 6, 7, 6, 8, 7, 9, 5, 9, 6, 8, 9

Assuming that all frames are initially empty, indicate the contents of memory after each reference, and how many page faults are found for each of the following page replacement algorithms:

1. First In First Out (FIFO):                                   [2 .5 M]                                              

Reference String	5	6	7	6	8	7	9	5	9	6	8	9
Frame 1
Frame 2
Frame 3
Frame 4
Page Fault

       Total Page Faults:

2. Least Recently Used (LRU):                               [2.5 M]

Reference String	5	6	7	6	8	7	9	5	9	6	8	9
Frame 1
Frame 2
Frame 3
Frame 4
Page Fault

Total Page Faults:

Answer 1

First In First Out (FIFO) :
This is one of the  simplest page replacement algorithm. 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 and is removed when a page needs to be replaced with a new page .

Reference String 5 6 7 6 8 7 9 5 9 6 8 9 1 Frame 1 5 5 5 5 5 5 9 9 9 9 9 9 2 Frame 2 6 6 6 6 6 6 5 5 5 5 5 3 Frame 3 7 7 7 7 6 6 6 4 Frame 4 8 8 8 8 8 8 8 8 5 Page Fault 1 1 1 0 1 0 1 1 0 1 0 0 6

Total Page Faults = all the page fault with the value 1 , so here there are 7  1's . Total Page fault = 7

Explanation, : (Lets call rs = reference string)

1. First 3 rs (5,6,7) goes in Frame (1,2,3). - 3 page faults

2. 4th rs 6 is already present in Frame 2  - 0 page fault

3. 5th rs 8 goes in Frame 4 - 1 page fault
4. 6th rs 7 is is already present in Frame 3  - 0 page fault

Now 9 comes and none of the frames are empty , so operating system will try to replace the oldest rs with 9. Here that is 5 available in Frame 1.

5. So 7th rs 9 replaces 5 in frame 1 - 1 page fault
6. Next , 8th rs 5 replaces 6(oldest frame) in Frame 2 - 1 page fault
7. 9th rs 9 is already present in Frame 1  - 0 page fault
8. Next , 10th rs 6 replaces 7(oldest frame) in Frame 3 - 1 page fault
9. Next , both 11th and 12th rs (8,9) are already available in the frames(4,1) - 0 page faults

-----------------------------------------

Least Recently Used(LRU) :
In LRU algorithm least recently used page will be replaced with the new one.

Reference String 5 6 7 6 8 7 9 5 9 6 8 9 1 Frame 1 5 5 5 5 5 5 9 9 9 9 9 9 2 Frame 2 6 6 6 6 6 6 5 5 5 5 5 3 Frame 3 7 7 7 7 7 7 7 7 8 8 4 Frame 4 8 8 8 8 8 6 6 6 5 Page Fault 1 1 1 0 1 0 1 1 0 1 1 0 6

Total Page Faults = all the page fault with the value 1 , so here there are 8  1's . Total Page fault = 8

1. First 3 rs (5,6,7) goes in Frame (1,2,3). - 3 page faults

2. 4th rs 6 is already present in Frame 2  - 0 page fault

3. 5th rs 8 goes in Frame 4 - 1 page fault
4. 6th rs 7 is already present in Frame 3  - 0 page fault

Now 9 comes and none of the frames are empty , so operating system will try to replace the least recently used rs with 9. Here that is 5 available in Frame 1.

5. So 7th rs 9 replaces 5 in frame 1 - 1 page fault
6. Next , 8th rs 5 replaces 6(least recently used) in Frame 2 - 1 page fault
7. 9th rs 9 is already present in Frame 1  - 0 page fault
8. Next , 10th rs 6 replaces 8(least recently used) in Frame 4 - 1 page fault ( rs 7 used once more after rs 8 came , so 8 is least recently used)

9. Next, 11th rs 8 replaces 7(least recently used) in Frame 3 - 1 page fault
10. Next , 12th rs 9 is already present in Frame 1  - 0 page fault

I hope this answers your question.

Please give thumbs up if it helps.