Optimal Page Replacement Algorithm in C with Output of Program

Optimal Page Replacement Algorithm in C with Output of Program

by

The processes in an operating system occupy dedicated memory and the memory is divided into smaller parts called pages. On demand of the CPU, these pages are brought from secondary memory to primary memory and this is done using an algorithm which is discussed elaborately in this article.

In operating systems, when new pages are referred and it’s not stored/present in the memory of the system, in such a condition , page fault occurs and the operating system itself replaces the newly required page with some already existing pages. And we have different page replacement algorithms to decide which page to replace with.

The ultimate goal of all the algorithms is to reduce the number of page faults as much as possible.
Optimal page replacement algorithm says that if page fault occurs then that page should be removed from the system and it should not be used in future.

Optimal Page Replacement Algorithm Program 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

OPR – Optimal Page Replacement Algorithm in C

The concept of “Optimal Page Replacement Algorithm Program in C” here is pretty easy to understand :

If the referred page is not found , then search for a page that is never referenced in the future. If such a page exists , then replace the present page with this new page. And if we don’t find any such page , search for a page that is referenced in the farthest future and replace the original page with this new page.

Hope this article was useful to you.

Leave a Comment