Optimal Page Replacement In C

March 25, 2022

Optimal Page Replacement

The process in an operating system occupies some dedicated memory. This memory is further divided into chunks called pages. These pages are brought from secondary memory to the primary memory as the CPU demands them. This method is known as page swapping and is done through an algorithm.

Optimal Page Replacement Program in C

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 look at

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

Read Also – Optimal page replacement in C++