ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम के लिए C++ प्रोग्राम

पेज नंबर और पेज साइज़ दिए गए हैं; कार्य ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम का उपयोग करके मेमोरी ब्लॉक को पेज में आवंटित करते समय हिट्स और मिस की संख्या ढूंढना है।

ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम क्या है?

ऑप्टिमल पेज रिप्लेसमेंट एल्गोरिदम एक पेज रिप्लेसमेंट एल्गोरिदम है। एक पेज रिप्लेसमेंट एल्गोरिदम एक ऐसा एल्गोरिदम है जो तय करता है कि किस मेमोरी पेज को रिप्लेस किया जाए। ऑप्टिमल पेज रिप्लेसमेंट में हम उस पेज को रिप्लेस करते हैं जो निकट भविष्य में रेफर नहीं किया जाता है, हालांकि इसे व्यावहारिक रूप से लागू नहीं किया जा सकता, लेकिन यह सबसे ऑप्टिमल है और इसमें न्यूनतम मिस होते हैं।

आइए एक उदाहरण का उपयोग करके और इसे आरेखीय रूप से समझाते हैं।

यहां 1, 2 और 3 आवंटित करने के बाद अब मेमोरी भर गई है, इसलिए 4 डालने के लिए हम 1, 2 और 3 से उस पेज को देखेंगे जो निकट भविष्य में फिर से रेफर नहीं किया जाता है, इसलिए पेज 3 निकट भविष्य में नहीं है तो हम उस पेज को नए पेज 4 से रिप्लेस करते हैं, और इसी तरह हम अंत तक चरणों को दोहराएंगे।

उदाहरण

इनपुट: page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 }    fn=3
आउटपुट: Hits = 3    Misses = 10

इनपुट: page[] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2 }    fn = 4
आउटपुट: Hits = 7    Misses= 6

उपरोक्त समस्या को हल करने के लिए हम जिस दृष्टिकोण का उपयोग कर रहे हैं -

• पेजों का इनपुट एक ऐरे के रूप में लें।
• देखें कि आवंटित पेज निकट भविष्य में मौजूद है या नहीं, यदि नहीं तो उस पेज को मेमोरी में नए पेज से रिप्लेस करें,
• यदि पेज पहले से मौजूद है तो हिट बढ़ाएं, अन्यथा मिस बढ़ाएं।
• ऐरे के अंतिम तत्व तक पहुंचने तक दोहराएं।
• हिट्स और मिस की संख्या प्रिंट करें।

एल्गोरिदम

शुरुआत
चरण 1 → फंक्शन int predict(int page[], vector& fr, int pn, int index) में
   res = -1, farthest = index घोषित और प्रारंभ करें
   लूप i = 0 और i < fr.size() और i++ के लिए
      लूप j = index और j < pn और j++ के लिए
         यदि fr[i] == page[j] तो,
            यदि j > farthest
               farthest = j सेट करें
               res = i सेट करें
            ब्रेक
         यदि j == pn तो,
            i वापस करें
         यदि (res == -1) ? 0 : res वापस करें

चरण 2 → फंक्शन bool search(int key, vector& fr) में
   लूप i = 0 और i < fr.size() और i++ के लिए
      यदि fr[i] == key तो,
        true वापस करें
      false वापस करें

चरण 3 → फंक्शन void opr(int page[], int pn, int fn) में
   vector fr घोषित करें
   hit = 0 सेट करें
   लूप i = 0 और i < pn और i++ के लिए
      यदि search(page[i], fr) तो,
        hit को 1 से बढ़ाएं
        जारी रखें
      यदि fr.size() < fn तो,
        fr.push_back(page[i])
      अन्यथा
        j = predict(page, fr, pn, i + 1) सेट करें
        fr[j] = page[i] सेट करें
      हिट्स की संख्या प्रिंट करें
      मिस की संख्या प्रिंट करें

चरण 4 → फंक्शन int main() में
   page[] = { 1, 7, 8, 3, 0, 2, 0, 3, 5, 4, 0, 6, 1 } घोषित और असाइन करें
   pn = sizeof(page) / sizeof(page[0]) सेट करें
   fn = 3 सेट करें
   opr(page, pn, fn)
रोकें

उदाहरण

#include 
using namespace std;

int predict(int page[], vector& fr, int pn, int index) {
    // उन पेजों के इंडेक्स स्टोर करें जो भविष्य में हाल ही में उपयोग होने वाले हैं
    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;
            }
        }
        // उन पेजों को वापस करें जो भविष्य में कभी रेफर नहीं किए जाते
        if (j == pn)
            return i;
    }
    // यदि सभी फ्रेम भविष्य में नहीं थे, तो उनमें से किसी को भी वापस करें, हम 0 वापस करते हैं। अन्यथा हम res वापस करते हैं।
    return (res == -1) ? 0 : res;
}

bool search(int key, vector& 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 fr;
    int hit = 0;
    for (int i = 0; i < pn; i++) {
        // फ्रेम में पेज मिला: HIT
        if (search(page[i], fr)) {
            hit++;
            continue;
        }
        // यदि पेज फ्रेम में नहीं मिला: MISS
        // जांचें कि क्या फ्रेम में जगह उपलब्ध है।
        if (fr.size() < fn)
            fr.push_back(page[i]);
        // रिप्लेस किए जाने वाले पेज को ढूंढें।
        else {
            int j = predict(page, fr, pn, i + 1);
            fr[j] = page[i];
        }
    }
    cout << "Hits = " << hit << endl;
    cout << "Misses = " << pn - hit << endl;
}

// मुख्य फंक्शन
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