OS Menu9>
- OS Home
- Introduction
- CPU Scheduling
- What is Process?
- Process Lifecyle
- Process Control Block
- Process Scheduling
- Context Switching
- CPU Scheduling
- FCFS Scheduling
- SJF (non-preemptive)
- SJF (Preemptive - SRTF)
- Round Robin
- Priority Scheduling
- Convoy Effect
- Scheduler Vs Dispatcher
- Preemptive Vs non
- Preemptive scheduling
- Non preemptive scheduling
- Process Synchronization
- Deadlock
- Popular Algorithms
- Memory Management
- Memory Management Introduction
- Partition Allocation Method
- First Fit
- First Fit (Intro)
- First Fit in C
- First Fit in C++
- First Fit in Python
- First Fit in Java
- Best Fit
- Best Fit (Intro)
- Best Fit in C
- Best Fit in C++
- Best Fit in Java
- Worst Fit
- Worst Fit (Intro)
- Worst Fit in C++
- Worst Fit in C
- Worst Fit in Java
- Worst Fit in Python
- Next Fit
- First fit best fit worst fit (Example)
- Memory Management 2
- Memory Management 3
- Page Replacement Algorithms
- LRU (Intro)
- LRU in C++
- LRU in Java
- LRU in Python
- FIFO
- Optimal Page Replacement algorithm
- Optimal Page Replacement (Intro)
- Optimal Page Replacement Algo in C
- Optimal Page Replacement Algo in C++
- Optimal Page Replacement Algo in Java
- Optimal Page Replacement Algo in Python
- Thrashing
- Belady’s Anomaly
- Static vs Dynamic Loading
- Static vs Dynamic Linking
- Swapping
- Translational Look Aside Buffer
- Process Address Space
- Difference between Segmentation and Paging
- File System
- Off-campus Drive Updates
- Get Hiring Updates
- Contact us
PREPINSTA PRIME
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.

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:
#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
Time Complexity:
O(n² × f) in the worst case
(because for each of n
references, predict()
may scan up to n
steps for each of f
frames)
Space Complexity:
O(n + f)
(n
for reference string, f
for frames)
Also Checkout:
Operating Systems Course
Method 2
Below is another method that you can check out….
#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
Time Complexity: O(n² × f)
Space Complexity: O(f)
n
= number of pagesf
= number of frames
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.
Login/Signup to comment