# 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

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. Can u tell me the vhdl code for this optimal page replacement algoritm? It’s very urgent.