पृष्ठ संख्या और पृष्ठ आकार दिया गया; कार्य हिट और मिस की संख्या का पता लगाना है जब हम इष्टतम पेज रिप्लेसमेंट एल्गोरिथम का उपयोग करके किसी पृष्ठ को मेमोरी ब्लॉक आवंटित करते हैं।
इष्टतम पृष्ठ प्रतिस्थापन एल्गोरिथम क्या है?
इष्टतम पृष्ठ प्रतिस्थापन एल्गोरिथ्म एक पृष्ठ प्रतिस्थापन एल्गोरिथ्म है। पेज रिप्लेसमेंट एल्गोरिथम एक एल्गोरिथम है जो यह तय करता है कि किस मेमोरी पेज को बदला जाना है। इष्टतम पृष्ठ प्रतिस्थापन में हम उस पृष्ठ को प्रतिस्थापित करते हैं जिसे निकट भविष्य में संदर्भित नहीं किया जाता है, हालांकि इसे व्यावहारिक रूप से कार्यान्वित नहीं किया जा सकता है, लेकिन यह सबसे इष्टतम है और इसमें न्यूनतम चूक है, और यह सबसे इष्टतम है।
आइए एक उदाहरण का उपयोग करके और इसे आरेखीय रूप से समझाकर समझते हैं।
यहाँ 1, 2 और 3 को आवंटित करने के बाद अब मेमोरी भर गई है, इसलिए 4 डालने के लिए हम उस पृष्ठ की तलाश करेंगे जो 1, 2 और 3 से निकट भविष्य में फिर से संदर्भित नहीं है, इसलिए पृष्ठ 3 निकट भविष्य में नहीं है इसलिए हम उसे बदल देते हैं नया पेज 4 वाला पेज, और इसी तरह हम अंत तक चरणों को दोहराते रहेंगे।
उदाहरण
Input: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
fn=3
Output: Hits = 3
Misses = 10
Input: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }
fn = 4
Output: Hits = 7
Misses= 6 उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग कर रहे हैं -
- पृष्ठों के इनपुट को एक सरणी के रूप में लें।
- आवंटित पृष्ठ देखें निकट भविष्य में मौजूद है, यदि नहीं, तो उस पृष्ठ को स्मृति में नए पृष्ठ से बदलें,
- अगर पेज पहले से ही इंक्रीमेंट हिट है, तो इंक्रीमेंट मिस हो जाएगा।
- जब तक हम सरणी के अंतिम तत्व तक नहीं पहुंच जाते तब तक दोहराएं।
- हिट और मिस की संख्या प्रिंट करें।
एल्गोरिदम
Start
Step 1-> In function int predict(int page[], vector<int>& fr, int pn, int index)
Declare and initialize res = -1, farthest = index
Loop For i = 0 and i < fr.size() and i++
Loop For j = index and j < pn and j++
If fr[i] == page[j] then,
If j > farthest
Set farthest = j
End If
Set res = i
break
If j == pn then,
Return i
Return (res == -1) ? 0 : res
Step 2-> In function bool search(int key, vector<int>& fr)
Loop For i = 0 and i < fr.size() and i++
If fr[i] == key then,
Return true
Return false
Step 3-> In function void opr(int page[], int pn, int fn)
Declare vector<int> fr
Set hit = 0
Loop For i = 0 and i < pn and i++
If search(page[i], fr) then,
Increment hit by 1
continue
If fr.size() < fn then,
fr.push_back(page[i])
Else
Set j = predict(page, fr, pn, i + 1)
Set fr[j] = page[i]
Print the number of hits
Print the number of misses
Step 4-> In function int main()
Declare and assign page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }
Set pn = sizeof(page) / sizeof(page[0])
Set fn = 3
opr(page, pn, fn)
Stop उदाहरण
#include <bits/stdc++.h>
using namespace std;
int predict(int page[], vector<int>& fr, int pn, int index) {
// Store the index of pages which are going
// to be used recently in future
int res = -1, farthest = index;
for (int i = 0; i < fr.size(); i++) {
int j;
for (j = index; j < pn; j++) {
if (fr[i] == page[j]) {
if (j > farthest) {
farthest = j;
res = i;
}
break;
}
}
// Return the page which are
// are never referenced in future,
if (j == pn)
return i;
}
// If all of the frames were not in future,
// return any of them, we return 0. Otherwise
// we return res.
return (res == -1) ? 0 : res;
}
bool search(int key, vector<int>& fr) {
for (int i = 0; i < fr.size(); i++)
if (fr[i] == key)
return true;
return false;
}
void opr(int page[], int pn, int fn) {
vector<int> fr;
int hit = 0;
for (int i = 0; i < pn; i++) {
// Page found in a frame : HIT
if (search(page[i], fr)) {
hit++;
continue;
}
//If a page not found in a frame : MISS
// check if there is space available in frames.
if (fr.size() < fn)
fr.push_back(page[i]);
// Find the page to be replaced.
else {
int j = predict(page, fr, pn, i + 1);
fr[j] = page[i];
}
}
cout << "Hits = " << hit << endl;
cout << "Misses = " << pn - hit << endl;
}
// main Function
int main() {
int page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 };
int pn = sizeof(page) / sizeof(page[0]);
int fn = 3;
opr(page, pn, fn);
return 0;
} आउटपुट
Hits = 3 Misses = 10