Optimal Page Replacement Algorithm in C

Here you will get program for optimal page replacement algorithm in C.

Optimal page replacement algorithm says that if page fault occurs then that page should be removed that will not be used for maximum time in future.

It is also known as clairvoyant replacement algorithm or Bélády’s optimal page replacement policy.

Also Read: LRU Page Replacement Algorithm in C

Video Tutorial

Below program shows how to implement this algorithm in C.

Program for Optimal Page Replacement Algorithm in C

#include<stdio.h>
 
int main()
{
    int no_of_frames, no_of_pages, frames[10], pages[30], temp[10], flag1, flag2, flag3, i, j, k, pos, max, faults = 0;
    printf("Enter number of frames: ");
    scanf("%d", &no_of_frames);
    
    printf("Enter number of pages: ");
    scanf("%d", &no_of_pages);
    
    printf("Enter page reference string: ");
    
    for(i = 0; i < no_of_pages; ++i){
        scanf("%d", &pages[i]);
    }
    
    for(i = 0; i < no_of_frames; ++i){
        frames[i] = -1;
    }
    
    for(i = 0; i < no_of_pages; ++i){
        flag1 = flag2 = 0;
        
        for(j = 0; j < no_of_frames; ++j){
            if(frames[j] == pages[i]){
                   flag1 = flag2 = 1;
                   break;
               }
        }
        
        if(flag1 == 0){
            for(j = 0; j < no_of_frames; ++j){
                if(frames[j] == -1){
                    faults++;
                    frames[j] = pages[i];
                    flag2 = 1;
                    break;
                }
            }    
        }
        
        if(flag2 == 0){
        	flag3 =0;
        	
            for(j = 0; j < no_of_frames; ++j){
            	temp[j] = -1;
            	
            	for(k = i + 1; k < no_of_pages; ++k){
            		if(frames[j] == pages[k]){
            			temp[j] = k;
            			break;
            		}
            	}
            }
            
            for(j = 0; j < no_of_frames; ++j){
            	if(temp[j] == -1){
            		pos = j;
            		flag3 = 1;
            		break;
            	}
            }
            
            if(flag3 ==0){
            	max = temp[0];
            	pos = 0;
            	
            	for(j = 1; j < no_of_frames; ++j){
            		if(temp[j] > max){
            			max = temp[j];
            			pos = j;
            		}
            	}            	
            }
			
			frames[pos] = pages[i];
			faults++;
        }
        
        printf("\n");
        
        for(j = 0; j < no_of_frames; ++j){
            printf("%d\t", frames[j]);
        }
    }
    
    printf("\n\nTotal Page Faults = %d", faults);
    
    return 0;
}

Output

Enter number of frames: 3
Enter number of pages: 10
Enter page reference string: 2 3 4 2 1 3 7 5 4 3

2 -1 -1
2 3 -1
2 3 4
2 3 4
1 3 4
1 3 4
7 3 4
5 3 4
5 3 4
5 3 4

Comment below if you have doubts or found anything incorrect in above optimal page replacement algorithm in C.

13 thoughts on “Optimal Page Replacement Algorithm in C”

    1. /* Optimal Page Replacement Algorithm */

      /*

      STEPS
      —–

      1. READ THE NUMBER OF PAGES, REFERENCE STRING, CACHE SIZE
      2. LET CACHE SIZE BE n. ADD FIRST n ELEMENTS FROM REFERENCE STRING TO CACHE DIRECTLY. PRINT CACHE AND INCREMENT PAGE FAULTS.
      3. FOR THE ELEMEMTS LEFT DO THE FOLLOWING..
      3.1 THERE MAY BE 2 CASES. EITHER THE ELEMENT IN THE REFERENCE STRING MAY BE IN THE CACHE ALREADY. OR IT IS NOT PRESENT
      3.2 IF THE ELEMENT IS NOT IN THE CACHE DO THE FOLLOWING(USES THE FUNCTION ISPRESENT() TO CHECK IF THE ELEMENT IS PRESENT OR NOT)
      3.2.1 FOR ALL THE ELEMENTS IN THE CACHE FIND RESPECTIVE LENGTH FROM CURRENT INDEX IN THE REFERENCE STRING (USING FINDLENGTH() FUNCTION)
      3.2.2 FIND THE MAXIMUM OF THE LENGTHS (USING FINDMAX() FUNCTION )
      3.2.3 REPLACE THAT INDEX OF CACHE WITH THE ELEMENT OF REFERENCE STRING
      3.2.4 INCREMENT PAGE FAULT
      3.3 ELSE DO NOTHING
      4. PRINT PAGE FAULTS

      */
      #include
      #include

      void printCache(int cache[], int n) { // FUNCTION TO PRINT CACHE – AN ARRAY

      int i;

      for (i = 0; i < n; i++)
      printf("%d ",cache[i]);

      printf("\n");
      }

      int isPresent(int cache[], int n, int key) { // FUNCTION TO CHECK WHETHER key IS PRESENT IN THE CACHE OR NOT

      int i = 0;

      for (i = 0; i < n; i++) {

      if(key == cache[i])
      return i; // RETURN THE INDEX OF THE KEY IF FOUND
      }

      return -1; // ELSE RETURN -1
      }

      int findLength(int ref_str[], int start, int end, int key) { // FUNCTION TO FIND THE LENGTH OF ELEMENT W.R.T TO THE REFERENCE STRING

      int i = start;

      for (i = start; i < end; i++) {

      if(key == ref_str[i]) // IF FOUND THAT ELEMT IN THE REF STRING
      return (i – start); // RETRURN ITS LENGTH – NOT INDEX
      }

      return -1; // ELSE RETURN -4

      }

      int findMaxLength(int victim_index[], int n) { // FIND MAXIMUM ELEMENT OF THE ARRAY VICTIM_INDEX[]

      int i = 0;
      int max = victim_index[0];
      for (i = 0; i max)
      max = victim_index[i];
      }

      return max;
      }
      int main()
      {
      int no_of_pages, cache_size, cache[50], i, ref_str[50], j;
      int page_fault = 0;

      printf(“\n Enter the number of pages : “); // READINF NUMBER OF PAGES
      scanf(“%d”,&no_of_pages);

      printf(“\n Enter the reference string : “); // READING REF STRING
      for(i = 0; i = no_of_pages) { // IF CACHE IS BIGGER THAN THE PAGES

      printCache(ref_str, no_of_pages);
      printf(“\n Page Faults = %d”, page_fault);

      return 0;
      }

      for(i = 0; i < cache_size; i++) { // TILL THE SIZE OF CACHE
      page_fault++;
      cache[i] = ref_str[i];
      printCache(cache, i+1);
      }

      int victim_index[50];
      int max_victim_index = 0;
      int check = 0;
      int temp = 0;

      for(j = i; j < no_of_pages; j++) { // FOR INDEXES AFTER THE CACHE SIZE

      check = isPresent(cache, cache_size, ref_str[j]); // CHECKING IF THE ELEMENT IS ALREADY IN THE CACHE

      if(check == -1) { // IF NO THERE

      for(i = 0; i < cache_size; i++) { // FIND LENGTHS OF EACH ELEMENT IN CACHE W.R.T TO THE REF STR

      victim_index[i] = findLength(ref_str, j, no_of_pages, ref_str[j]);
      }

      max_victim_index = findMaxLength(victim_index, cache_size); // FIND MAX LENGTH

      cache[max_victim_index] = ref_str[j]; // SET THE MAX INDEX AS REF_STR[J]

      page_fault++; // INCREMENT PAGE FAULT

      }else{

      }

      printCache(cache, cache_size); // PRINT CACHE
      }

      printf("\n Page Faults = %d\n",page_fault); // PRINT PAGE FAULT

      return 0;
      }

  1. it will print wrong output for this
    Enter number of frames: 3
    Enter number of pages: 20
    Enter page reference string: 1 2 3 4 2 5 3 4 2 6 7 8 7 9 7 8 2 5 4 9

  2. what if 2 or more pages will not be used at all that is they will not occur in sequence again …..so which of them will be replaced

  3. Lab report 10: please give answer

    Write a program to perform FCFS disk scheduling algorithm.

    Do the above coding in your computer using C programming and submit a lab report describing your code.

    Note:
    – Variables should be similar to your name. For example, if your name is R, your used variables will be r1, r2, r3,………

Leave a Comment

Your email address will not be published. Required fields are marked *