Optimal Page Replacement Algorithm in C

/* 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;
}

Hey do u get the vhdl code.if yes then please share with me it’s urgent.