• We were talking about page replacement algorithms in which we had discussed “FIFO algorithm”. In this post I am continuing on the same topic by discussing another page replacement algorithm called Optimal algorithm.
  • An optimal page-replacement algorithm has the lowest page-fault rate among all algorithms. It is also called MIN algorithm.
  • Optimal or MIN algorithm replaces the page that will not be used for the longest period of time. In other words, it will replace the page whose next reference is far away in the page reference string.
  • Optimal page replacement is infeasible because the virtual memory handler does not have knowledge of the future reference. It is just used to evaluate the performance with other algorithms for comparison.

Optimal Algorithm

  • In our example the first three page reference will generate page fault and they will be loaded in memory.
  • The next reference is of page 2. It will replace page 7 because page 7 will not be used until reference 18.
  • Optimal algorithm is much better than FIFO algorithm because it had 15 page faults while optimal has only 9 page faults.
  • Total No. of page fault in optimal is 9

Let’s see one more example to work. Consider the following page reference string and find out total number of page fault using optimal algorithm. Total Free frames are 3.

Page Reference String :  1, 2, 3, 4, 2, 1, 5, 6, 2,1,2, 3, 7, 6, 3, 2, 1, 2, 3, 5.

  • We have total three frames available and initially all three frames are blank.
  • The first page reference comes for page 1 and since it is not available in the memory, reference to page 1 will result in page fault so we need to bring page 1 into the memory and for that we need to allocate free memory are. Since we have total three free frames available, one of the free frame will be allocated to page 1.

Optimal Algorithm

  • Next page references are for page 2 and page 3 respectively and due to absence of that pages in the memory they will generate page faults and we will allocate both free frames to page 2 and page 3 respectively.
  • After the page 3, next reference is for page 4 in the page reference string but now we don’t have any free frames so operating system has to take decision for swapping using page replacement algorithm. According to our optimal algorithm the page that has the reference far away in the reference string will be selected for the replacement so if we look future references of all thee pages that are available in memory i.e. page 1, 2 and 3 we come to know that reference for page three is the far away that the references of page 1 and 2 so page 3 will be selected for replacement assuming that it will be required in future but not now. So page 3 will be replaced by page 4.
  • Next two references for page 2 and 1 are all ready available in the memory so no page fault will be generated so no replacement is required.
  • Note that the next reference is for page 5 and since it is not available in the memory again page fault will be generated. Looking to the page reference string for future references of pages 1, 2 and 4 respectively, we came to know that there is no future reference for page 4 in the page reference string so we are assuming that it is far away than the other pages present in the memory as in practical environment new requests keep arriving constantly so here page 4 will be the victim page for the replacement and it will be replaced by page 5.
  • After that next reference is for page 6 and it will be replaced by page 5 due to page fault. Since page 2 and 1 are already available in the memory, next three references for the page 2,1 and 2 no page fault will be generated.
  • Similarly all the page reference will be checked and where necessary, page replacement will be done after looking to their future reference depending on how far the reference for particular page is.
  • Notice the 16th page reference in the page reference string for page 2. At this point we have page 3, 7 and 6 in the memory and the absence of page 2 will result in new page fault. For the selection of victim page, we can notice that future references for page 6 and 7 could not be found in the page reference string so we can assume that their references might be far war and we since we have two such pages we can select either page 6 or page 7 but normally FIFO policy can be useful to break the tie.
  • The complete calculation of page faults are given on the above picture please refer to it. You can allocated free frames either from top or bottom. It does not affect the result.
  • Total page fault for above page reference string is 11.