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 |