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


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना जानकार FactSet माइक्रोसॉफ्ट पेपैल
ऑपरेटिंग सिस्टम सिद्धांत

पेज रिप्लेसमेंट क्या है?

आधुनिक ऑपरेटिंग सिस्टम मेमोरी प्रबंधन के लिए पेजिंग का उपयोग करते हैं और कई बार पृष्ठ प्रतिस्थापन की आवश्यकता होती है। पृष्ठ प्रतिस्थापन एक पृष्ठ को बदलने की प्रक्रिया है जो वर्तमान में स्मृति में उस पृष्ठ के साथ मौजूद है जिसकी आवश्यकता है लेकिन स्मृति में मौजूद नहीं है। ऐसी स्थिति को पेज फॉल्ट कहा जाता है।

पृष्ठ प्रतिस्थापन एल्गोरिदम का लक्ष्य पृष्ठ दोषों की संख्या को कम करना है ताकि समग्र प्रदर्शन में वृद्धि हो सके। पृष्ठ प्रतिस्थापन के लिए कई एल्गोरिदम हैं। हम यहां कुछ चर्चा कर रहे हैं।

फर्स्ट इन फर्स्ट आउट (FIFO)

पेहले आये पेहलॆ गये पृष्ठ प्रतिस्थापन एल्गोरिथम पृष्ठ प्रतिस्थापन के लिए सबसे सरल एल्गोरिथ्म है। यह सभी पृष्ठों का ट्रैक रखने के लिए एक कतार बनाए रखता है। हम हमेशा एक कतार के अंत में एक नया पृष्ठ जोड़ते हैं। जब पंक्ति पूर्ण है और पृष्ठ दोष है, हम कतार के सामने मौजूद पृष्ठ को हटाते हैं और कतार के अंत में एक नया पृष्ठ जोड़ते हैं।
इस तरीके से हम पहले को पहले आउट-टेक तकनीक में बनाए रखते हैं, अर्थात्, जो पेज पहले मेमोरी में डाला जाता है, उसे पहले मेमोरी से हटा दिया जाएगा।

उदाहरण

पृष्ठ संदर्भ स्ट्रिंग {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1} हो और कुल 4 पृष्ठ स्लॉट हों। फिर,

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

बेलिडा की विसंगति

बेल्दी ने साबित किया कि कुछ पृष्ठ संदर्भ स्ट्रिंग के लिए संभव है कि पृष्ठ स्लॉट बढ़ने से पृष्ठ दोष अधिक हो सकते हैं।

उदाहरण
पेज संदर्भ स्ट्रिंग {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4} पर विचार करें 3 पेज स्लॉट और 4 पेज स्लॉट के साथ।
3 पेज स्लॉट = 3 के साथ पृष्ठ दोष
4 पेज स्लॉट = 4 के साथ पृष्ठ दोष

इष्टतम पृष्ठ प्रतिस्थापन

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

उदाहरण

पृष्ठ संदर्भ स्ट्रिंग {2, 3, 4, 2, 1, 3, 7, 5, 4, 3} हो और कुल 3 पृष्ठ स्लॉट हों। फिर,

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

कम से कम हाल ही में प्रयुक्त

यह एल्गोरिथ्म कैशिंग तकनीक पर आधारित है। एल्गोरिदम कहता है कि उस पृष्ठ को प्रतिस्थापित करें जिसका उपयोग हाल के दिनों में कम से कम किया गया है।

उदाहरण

पृष्ठ संदर्भ स्ट्रिंग {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4} हो और कुल 3 पृष्ठ स्लॉट हों। फिर,

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

फर्स्ट इन फर्स्ट आउट का क्रियान्वयन

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

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

class FirstInFirstOutPageReplacement {
    private static int pageFaults(int[] pageString, int pageSlots) {
        int faults = 0;

        // Set to store the elements present in queue, used to check if a page is present or not
        HashSet<Integer> set = new HashSet<>();
        // Queue to maintain the order of insertion
        Queue<Integer> queue = new LinkedList<>();

        // traverse the page string
        for (int i = 0; i < pageString.length; i++) {
            // if there are some empty slots
            if (queue.size() < pageSlots) {
                if (!set.contains(pageString[i])) {
                    // and the current page is missing
                    // add the page to set
                    set.add(pageString[i]);
                    // add the page to queue
                    queue.add(pageString[i]);
                    // it is a page fault, increment faults
                    faults++;
                }
            } else {
                // there are no empty slots and if current page is absent
                if (!set.contains(pageString[i])) {
                    // remove the first page in queue
                    int removedPage = queue.poll();
                    // remove the page from set
                    set.remove(removedPage);

                    // add the new page to set
                    set.add(pageString[i]);
                    // add the new page to queue
                    queue.add(pageString[i]);

                    // it is page fault, increment faults
                    faults++;
                }
            }
        }

        // return total number of page faults
        return faults;
    }

    public static void main(String[] args) {
        // Example
        int pageString[] = new int[] {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
        int pageSlots = 4;
        System.out.println(pageFaults(pageString, pageSlots));
    }
}
Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4
8

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

#include <bits/stdc++.h> 
using namespace std; 

int pageFaults(int *pageString, int pageSlots, int n) {
    int faults = 0;
    
    // Set to store the elements present in queue, used to check if a page is present or not
    unordered_set<int> set;
    // Queue to maintain the order of insertion
    queue<int> q;
    
    // traverse the page string
    for (int i = 0; i < n; i++) {
        // if there are some empty slots
        if (q.size() < pageSlots) {
            if (set.find(pageString[i]) == set.end()) {
                // and the current page is missing
                // add the page to set
                set.insert(pageString[i]);
                // add the page to queue
                q.push(pageString[i]);
                // it is a page fault, increment faults
                faults++;
            }
        } else {
            // there are no empty slots and if current page is absent
            if (set.find(pageString[i]) == set.end()) {
                // remove the first page in queue
                int removedPage = q.front();
                q.pop();
                // remove the page from set
                set.erase(removedPage);
                
                // add the new page to set
                set.insert(pageString[i]);
                // add the new page to queue
                q.push(pageString[i]);
                
                // it is page fault, increment faults
                faults++;
            }
        }
    }
    
    return faults;
}

int main() {
    // Example
    int pageString[] = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1};
    int pageSlots = 4;
    cout<<pageFaults(pageString, pageSlots, sizeof(pageString) / sizeof(pageString[0]))<<endl;
    
    return 0;
}
Page String = {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1}
Page Slots = 4
8

जटिलता विश्लेषण

समय की जटिलता

हैशसेट का उपयोग करके हमें दिए गए एल्गोरिदम को रैखिक समय में चलाने की अनुमति दी गई है। इस प्रकार एल्गोरिथ्म में रैखिक समय जटिलता है पर).

अंतरिक्ष जटिलता

O (पेजस्लैट्स), हम कतार में केवल पृष्ठों की संख्या रखते हैं। इस प्रकार अंतरिक्ष जटिलता पृष्ठस्थलों पर निर्भर है।