Optimal Page Replacement Algorithm in C

Optimal Page Replacement using C

The Optimal Page Replacement algorithm is a page replacement strategy used in memory management. It replaces the page that will not be used for the longest time in the future, which helps reduce the number of page faults.

Although it’s mainly used for comparison and teaching purposes (since predicting the future is not possible in real systems), it helps us understand how efficient a page replacement method can be.

In this article, we’ll learn how to implement the Optimal Page Replacement algorithm using the C programming language.

Optimal Page replacement in C

What is the Optimal Page Replacement Algorithm in C ?

  • Optimal Page Replacement Algorithm is a memory management technique used to decide which page to remove from memory when a new page needs to be loaded.
  • It works by looking ahead in the page reference string (the order in which pages will be needed) and replacing the page that won’t be used for the longest time in the future.
  • This approach gives the lowest possible number of page faults, which is why it’s considered optimal.

In C programming, we can implement this algorithm using arrays and loops to simulate how pages are loaded, checked, and replaced based on future references.

Why Choose C?

Here’s why C is a good choice for implementing the Optimal Page Replacement algorithm:

  • Low Level Memory Control: C gives direct access to memory, which helps in understanding how memory management works at a system level.
  • Educational Purposes: Many operating systems and textbooks use C to teach memory management, making it a standard for learning these concepts.
  • Speed and Performance: C is fast and efficient, making it ideal for simulating performance based algorithms.
  • Closer to OS Level Concepts: Since many operating systems are built using C, it makes sense to use the same language to study algorithms related to OS.

Method 1:

Run
#include <stdio.h>
  
// This function checks if current strea item(key) exists in any of the frames or not
int search(int key, int frame_items[], int frame_occupied)
{
    for (int i = 0; i < frame_occupied; i++)
        if (frame_items[i] == key)
            return 1;
    return 0;
}

void printOuterStructure(int max_frames){
    printf("Stream ");
    
    for(int i = 0; i < max_frames; i++)
        printf("Frame%d ", i+1);
}
void printCurrFrames(int item, int frame_items[], int frame_occupied, int max_frames){
    
    // print current reference stream item
    printf("\n%d \t\t", item);
    
    // print frame occupants one by one
    for(int i = 0; i < max_frames; i++){
        if(i < frame_occupied)
            printf("%d \t\t", frame_items[i]);
        else
            printf("- \t\t");
    }
}
// This Function helps in finding frame that will not be used
// for the longest period of time in future in ref_str[0 ... refStrLen - 1]
int predict(int ref_str[], int frame_items[], int refStrLen, int index, int frame_occupied)
{
    // For each current occupant in frame item
    // we try to find the frame item that will not be referenced in 
    // for the longest in future in the upcoming reference string
    int result = -1, farthest = index;
    for (int i = 0; i < frame_occupied; i++) {
        int j;
        for (j = index; j < refStrLen; j++) 
        { 
            if (frame_items[i] == ref_str[j]) 
            { 
                if (j > farthest) {
                    farthest = j;
                    result = i;
                }
                break;
            }
        }
  
        // If we find a page that is never referenced in future,
        // return it immediately as its the best
        if (j == refStrLen)
            return i;
    }
  
    // If none of the frame items appear in reference string
    // in the future then we return 0th index. Otherwise we return result
    return (result == -1) ? 0 : result;
}
  
void optimalPage(int ref_str[], int refStrLen, int frame_items[], int max_frames)
{
    // initially none of the frames are occupied
    int frame_occupied = 0;
    printOuterStructure(max_frames);
    
    // Here we traverse through reference string
    // and check for miss and hit.
    int hits = 0;
    for (int i = 0; i < refStrLen; i++) {
  
        // If found already in the frame items : HIT
        if (search(ref_str[i], frame_items, frame_occupied)) {
            hits++;
            printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
            continue;
        }
  
        // If not found in frame items : MISS
  
        // If frames are empty then current reference string item in frame
        if (frame_occupied < max_frames){
            frame_items[frame_occupied] = ref_str[i];
            frame_occupied++;
            printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
        }
        // else we need to use optmial algorithm to find
        // frame index where we need to do replacement for this
        // incoming reference string item
        else {
            int pos = predict(ref_str, frame_items, refStrLen, i + 1, frame_occupied);
            frame_items[pos] = ref_str[i];
            printCurrFrames(ref_str[i], frame_items, frame_occupied, max_frames);
        }
        
    }
    printf("\n\nHits: %d\n", hits);
    printf("Misses: %d", refStrLen - hits);
}
  
// Driver Function
int main()
{
    // int ref_str[] = {9, 0, 5, 1, 0, 3, 0, 4, 1, 3, 0, 3, 1, 3};
    int ref_str[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};
    int refStrLen = sizeof(ref_str) / sizeof(ref_str[0]);
    int max_frames = 3;
    int frame_items[max_frames];
    
    optimalPage(ref_str, refStrLen, frame_items, max_frames);
    return 0;
}

Output

Stream Frame1 Frame2 Frame3 
7 	7 	- 	- 		
0 	7 	0 	- 		
1 	7 	0 	1 		
2 	2 	0 	1 		
0 	2 	0 	1 		
3 	2 	0 	3 		
0 	2 	0 	3 		
4 	2 	4 	3 		
2 	2 	4 	3 		
3 	2 	4 	3 		
0 	2 	0 	3 		
3 	2 	0 	3 		
2 	2 	0 	3 		
1 	2 	0 	1 		
2 	2 	0 	1 		
0 	2 	0 	1 		
1 	2 	0 	1 		
7 	7 	0 	1 		
0 	7 	0 	1 		
1 	7 	0 	1 		

Hits: 11
Misses: 9

Method 2

Below is another method that you can check out….

Run

#include <stdio.h> 
 int main()
{
    int flag1, flag2, flag3, i, j, k, position, max, faults = 0;
    int num_frames = 3;
    
    int frames[num_frames];
    int temp[num_frames];
    
    int inputStream[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};

    int num_pages = sizeof(inputStream) / sizeof(inputStream[0]);

    for(i = 0; i < num_frames; i++){
        frames[i] = -1;
    }

    for(i = 0; i < num_pages; i++){
        
        flag1 = flag2 = 0;

        for(j = 0; j < num_frames; j++){
            if(frames[j] == inputStream[i]){
                   flag1 = flag2 = 1;
                   break;
               }
        }

        if(flag1 == 0){
            for(j = 0; j < num_frames; j++){
                if(frames[j] == -1){
                    faults++;
                    frames[j] = inputStream[i];
                    flag2 = 1;
                    break;
                }
            }    
        }

        if(flag2 == 0){
            flag3 =0;

            for(j = 0; j < num_frames; j++){
                temp[j] = -1;

                for(k = i + 1; k < num_pages; k++){
                    if(frames[j] == inputStream[k]){
                        temp[j] = k;
                        break;
                    }
                }
            }

            for(j = 0; j < num_frames; j++){
                if(temp[j] == -1){
                    position = j;
                    flag3 = 1;
                    break;
                }
            }

            if(flag3 ==0){
                max = temp[0];
                position = 0;

                for(j = 1; j < num_frames; j++){ if(temp[j] > max){
                        max = temp[j];
                        position = j;
                    }
                }               
            }

            frames[position] = inputStream[i];
            faults++;
        }

        printf("\n");
        

        for(j = 0; j < num_frames; j++){
            printf("%d\t", frames[j]);
        }
    }

    printf("\n\nTotal Page Faults = %d", faults);
    printf("\nTotal Hits = %d", num_pages-faults);

    return 0;
}

Output

7	-1	-1	
7	0	-1	
7	0	1	
2	0	1	
2	0	1	
2	0	3	
2	0	3	
2	4	3	
2	4	3	
2	4	3	
2	0	3	
2	0	3	
2	0	3	
2	0	1	
2	0	1	
2	0	1	
2	0	1	
7	0	1	
7	0	1	
7	0	1	

Total Page Faults = 9
Total Hits = 11

FAQ's

It’s a page replacement method that replaces the page not needed for the longest time in the future, minimizing page faults.

Because it gives the lowest possible number of page faults : but it’s mostly theoretical since we can’t always predict the future in real systems.

Not usually. It’s used for comparison and bench marking, since real OS can’t predict future page requests.

  • C is close to hardware-level memory operations.
  • It’s commonly used in OS development.
  • Helps understand memory management clearly.