Prob. How many page faults will occur with a reference string 0,1,7,2,3,2,7,1,0,3?
There are four frames which are initially empty.
Use
- OPTIMAL Page replacement algorithm
Sol.
OPTIMAL Page replacement algorithm:
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
Above table is an example of page frame, which is empty initially. And first page is 0.
So 0 will get added here, but there will be a page fault.
What is a page fault?
The page which is requested by the program is not present in the RAM, that means there is a page fault.
0 was not present in the page frame so there was a page fault.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | |||||||||
| F |
The next page is 1 and there is space for two more pages.So 0 will remain there and 1 will get added there.And again there will be a page fault.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | ||||||||
| 1 | |||||||||
| F | F |
The next page is 7, which is not in the page frame, but there is place for one more page, so 0 and 1 will remain there and 7 will get added. And there will be a page fault.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | |||||||
| 1 | 1 | ||||||||
| 7 | |||||||||
| F | F | F |
The next page is 2, which is not in the page frame, but there is place for one more page, so 0, 1 and 7 will remain there and 2 will get added. And there will be a page fault.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | 0 | ||||||
| 1 | 1 | 1 | |||||||
| 7 | 7 | ||||||||
| 2 | |||||||||
| F | F | F | F |
I have given red color when there is a page fault, and black color for rest of the pages, and green color for page hits.
Now the page frame is full, and the next page is 3 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 3 there.
Now see in the table below,
In future pages 2 will come first, than 7 and than 1 and than 0.
So 0 will get removed because it very far to enter in page frame, and 3 will get added there. And there will be a page fault because 3 was not present in the page frame. And 1, 7, and 2 will remain there.
The next page is 2, which is already present in the page frame. This is known as page hit.
What is page hit ?
The page which is requested by the program is already present in the RAM/page frame is known as page hit.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | 0 | 3 | 3 | ||||
| 1 | 1 | 1 | 1 | 1 | |||||
| 7 | 7 | 7 | 7 | ||||||
| 2 | 2 | 2 | |||||||
| F | F | F | F | F | H |
The next page is 7, which is already present in the page frame. This is known as page hit.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | 0 | 3 | 3 | 3 | |||
| 1 | 1 | 1 | 1 | 1 | 1 | ||||
| 7 | 7 | 7 | 7 | 7 | |||||
| 2 | 2 | 2 | 2 | ||||||
| F | F | F | F | F | H | H |
The next page is 1, which is already present in the page frame. This is known as page hit.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | ||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||
| 7 | 7 | 7 | 7 | 7 | 7 | ||||
| 2 | 2 | 2 | 2 | 2 | |||||
| F | F | F | F | F | H | H | H |
The page frame is full, and the next page is 0 which is not there in the page frame. So we need to remove one page from the page frame, so we can add 0 there.
Now see in the table below,
In future pages 3 will come first, and 1, 7 ,2 is not about to come.
So we will use FIFO to remove a page from pages 1, 7, 2. According to FIFO page 1 will get removed, and 0 will get added there. And there will be a page fault because 0 was not present in the page frame. And 7, and 2 will remain there.
The next page is 3, which is already present in the page frame. This is known as page hit.
Now see in the table below,
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
| 0 | 0 | 0 | 0 | 3 | 3 | 3 | 3 | 3 | 3 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | |
| 7 | 7 | 7 | 7 | 7 | 7 | 7 | 7 | ||
| 2 | 2 | 2 | 2 | 2 | 2 | 2 | |||
| F | F | F | F | F | H | H | H | F | H |
Total pages present in the pages = 10.
| 0 | 1 | 7 | 2 | 3 | 2 | 7 | 1 | 0 | 3 |
Total page faults = 06.
| F | F | F | F | F | F |
Total page hits = 04
| H | H | H | H |
SEE ALSO:
FIFO page replacement, LRU page replacement, OPTIMAL page replacement.