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 in C++
What is the Optimal Page Replacement in C++ ?
The Optimal Page Replacement Algorithm is a theoretical page replacement method used in memory management (like virtual memory in operating systems).
The operating system memory is divided into segments. These segments are commonly known as pages. These pages are kept in the main memory and are replaced as per the demands in the operating system. The approach is also known as the page swapping.
Basic Idea of Optimal Page Replacement:
- Whenever a page needs to be replaced, the algorithm looks into the future and selects the page that will not be used for the longest period of time.
- It’s called “optimal” because it gives the minimum possible number of page faults.
Why implement it in C++?
- Speed: C++ is fast, and page replacement simulations involve lots of memory and iteration. You want something efficient.
- Low-Level Control: C++ gives you fine control over arrays, memory, and pointers — very useful in simulating memory management.
- Data Structures: You can easily use vectors, maps, sets, etc., to simulate future page accesses.
- Learning and Practice: For many students and developers, C++ is a standard for understanding operating systems concepts.
- Competitive Programming & Interviews: Questions like “implement Optimal Page Replacement” are common in coding contests, and C++ is popular there.
Programming Code for Optimal Page Replacement in C++
We will look at two different methods –
- Method 1: Uses array to store Frame items
- Method 2: Uses Vector to store frame items
Space and Time Complexity
Space Complexity:
Array Method:
O(f)
(wheref = number of frames
— fixed size array)Vector Method:
O(f)
(vector grows dynamically, but max size =f
)
Time Complexity:
For each reference in the reference string:
search()
→ O(f) timepredict()
→ in worst case O(f × r), where:f = number of frames
r = remaining references (upto n)
Thus, across all n
references:
Total Time → O(n × f × r)
Since f
is usually small constant (like 3–4),
Final Time Complexity ≈ O(n²)
Using Array to store Frame items.
#include <bits/stdc++.h> using namespace std; // 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 cout << "\n" << item << "\t\t"; // print frame occupants one by one for(int i = 0; i < max_frames; i++){ if(i < frame_occupied) cout << frame_items[i] << "\t\t"; else cout << "- \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); } } cout << "\n\nHits: " << hits << "\n"; cout << "Hits: " << refStrLen - hits << "\n"; } // 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
Using Vector to store Frame items.
#include <bits/stdc++.h> using namespace std; // This function checks if current strea item(key) exists in any of the frames or not int search(int key, vector& 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, vector& frame_items, int frame_occupied, int max_frames){ // print current reference stream item cout << "\n" << item << "\t\t"; // print frame occupants one by one for(int i = 0; i < max_frames; i++){ if(i < frame_occupied) cout << frame_items[i] << "\t\t"; else cout << "- \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[], vector& 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 max_frames) { // initially none of the frames are occupied vector frame_items; 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_items.size())) { hits++; printCurrFrames(ref_str[i], frame_items, frame_items.size(), max_frames); continue; } // If not found in frame items : MISS // If frames are empty then current reference string item in frame if (frame_items.size() < max_frames){ frame_items.push_back(ref_str[i]); printCurrFrames(ref_str[i], frame_items, frame_items.size(), 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_items.size()); frame_items[pos] = ref_str[i]; printCurrFrames(ref_str[i], frame_items, frame_items.size(), max_frames); } } cout << "\n\nHits: " << hits << "\n"; cout << "Hits: " << refStrLen - hits << "\n"; } // 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; optimalPage(ref_str, refStrLen, 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
FAQ's
The Optimal Page Replacement Algorithm is mainly used for theoretical bench marking. It provides the best possible performance (least page faults), which helps compare other practical algorithms like LRU, FIFO, etc.
C++ offers faster execution, lower-level memory control, and familiarity with system-level concepts making it ideal for simulating OS algorithms like page replacement.
Yes. Arrays have fixed size and may be slightly faster due to no dynamic memory overhead. Vectors offer flexibility and ease of use, especially when frame size isn’t known at compile time.
Yes, though the nature of the algorithm is to look ahead in the reference string (which is why it’s “optimal”), you can improve performance by using hashing or index maps to reduce look-up times in the predict()
function.
Login/Signup to comment