Ratingપરેટિંગ સિસ્ટમ્સમાં પૃષ્ઠ બદલો એલ્ગોરિધમ્સ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન કોગ્નિઝન્ટ ફેક્ટસેટ માઈક્રોસોફ્ટ પેપાલ
ઓપેરેટીંગ સીસ્ટમ થિયરી

પેજ રિપ્લેસમેન્ટ શું છે?

આધુનિક operatingપરેટિંગ સિસ્ટમ્સ મેમરી મેનેજમેન્ટ માટે પેજિંગનો ઉપયોગ કરે છે અને ઘણી વખત પૃષ્ઠની ફેરબદલની જરૂર પડે છે. પેજ રિપ્લેસમેન્ટ એ પૃષ્ઠને બદલવાની પ્રક્રિયા છે જે વર્તમાનમાં મેમરીમાં હાજર હોય તેવા પૃષ્ઠ સાથે મેમરીમાં હાજર છે પરંતુ તે મેમરીમાં હાજર નથી. આવી સ્થિતિને પેજ ફોલ્ટ તરીકે ઓળખવામાં આવે છે.

પેજ રિપ્લેસમેન્ટ અલ્ગોરિધમનો ધ્યેય પેજ ફોલ્ટની સંખ્યાને ઘટાડવાનું છે જેથી એકંદર કામગીરીમાં વધારો થાય. પૃષ્ઠ બદલવા માટે ઘણાં અલ્ગોરિધમ્સ છે. અમે અહીં થોડીક ચર્ચા કરી રહ્યા છીએ.

ફર્સ્ટ ઇન ફર્સ્ટ આઉટ (FIFO)

જે પહેલા જશે પહેલા આવશે પૃષ્ઠ બદલો એલ્ગોરિધમ પૃષ્ઠ રિપ્લેસમેન્ટ માટે સૌથી સરળ અલ્ગોરિધમનો છે. તે બધા પૃષ્ઠોને ટ્ર trackક રાખવા માટે એક કતાર જાળવે છે. અમે હંમેશા કતારના અંતમાં એક નવું પૃષ્ઠ ઉમેરીએ છીએ. જ્યારે કતાર ભરેલું છે અને ત્યાં પેજ ફોલ્ટ છે, અમે કતારના આગળના ભાગમાં હાજર પૃષ્ઠને દૂર કરીએ છીએ અને કતારના અંતમાં એક નવું પૃષ્ઠ ઉમેરીશું.
આ રીતે આપણે પ્રથમ ઇન ફર્સ્ટ આઉટ તકનીકને જાળવીએ છીએ, એટલે કે, જે પૃષ્ઠ પ્રથમ મેમરીમાં દાખલ કરવામાં આવે છે તે પહેલા મેમરીમાંથી દૂર કરવામાં આવશે.

ઉદાહરણ

પૃષ્ઠ સંદર્ભ શબ્દમાળાને {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1 be થવા દો અને કુલ 4 પૃષ્ઠ સ્લોટ છે. પછી,

Ratingપરેટિંગ સિસ્ટમ્સમાં પૃષ્ઠ બદલો એલ્ગોરિધમ્સ

બેલાડીની વિસંગતતા

બેલેડીએ સાબિત કર્યું કે કેટલાક પૃષ્ઠ સંદર્ભ શબ્દમાળાઓ માટે તે શક્ય છે કે પૃષ્ઠ સ્લોટ્સમાં વધારો થવાથી પૃષ્ઠની ખામી વધુ હોઈ શકે છે.

ઉદાહરણ
પૃષ્ઠ સંદર્ભ શબ્દમાળા Consider 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4 Consider ને 3 પૃષ્ઠ સ્લોટ્સ અને 4 પૃષ્ઠ સ્લોટ્સ સાથે ધ્યાનમાં લો.
3 પૃષ્ઠ સ્લોટ્સ સાથે પૃષ્ઠ ખામી = 3
4 પૃષ્ઠ સ્લોટ્સ સાથે પૃષ્ઠ ખામી = 4

શ્રેષ્ઠ પૃષ્ઠ બદલો

આ અલ્ગોરિધમનો કહે છે કે જો આપણે જાણતા હોઈએ કે આપણે ભવિષ્યમાં કયા પૃષ્ઠનો ઉપયોગ કરીશું તો આપણે પૃષ્ઠ રિપ્લેસમેન્ટ તકનીકને optimપ્ટિમાઇઝ કરી શકીશું.
Pageપ્ટિમલ પેજ રિપ્લેસમેન્ટ અલ્ગોરિધમ મુજબ, ભવિષ્યમાં ઓછામાં ઓછો ઉપયોગ થનાર પૃષ્ઠને બદલવું હંમેશાં શ્રેષ્ઠ છે.

ઉદાહરણ

પૃષ્ઠ સંદર્ભ શબ્દમાળાને {2, 3, 4, 2, 1, 3, 7, 5, 4, 3 be થવા દો અને કુલ 3 પૃષ્ઠ સ્લોટ છે. પછી,

Ratingપરેટિંગ સિસ્ટમ્સમાં પૃષ્ઠ બદલો એલ્ગોરિધમ્સ

ઓછામાં ઓછું તાજેતરમાં વપરાયેલ

આ અલ્ગોરિધમનો કેશીંગ તકનીક પર આધારિત છે. અલ્ગોરિધમનો કહે છે કે તાજેતરના સમયમાં જે પૃષ્ઠનો ઓછામાં ઓછો ઉપયોગ થાય છે તે પૃષ્ઠને બદલો.

ઉદાહરણ

પૃષ્ઠ સંદર્ભ શબ્દમાળાને {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4 be થવા દો અને કુલ 3 પૃષ્ઠ સ્લોટ છે. પછી,

Ratingપરેટિંગ સિસ્ટમ્સમાં પૃષ્ઠ બદલો એલ્ગોરિધમ્સ

ફર્સ્ટ ઇન ફર્સ્ટ આઉટનું અમલીકરણ

Ratingપરેટિંગ સિસ્ટમ્સમાં પેજ રિપ્લેસમેન્ટ અલ્ગોરિધમ્સ માટેનો જાવા કોડ

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

Ratingપરેટિંગ સિસ્ટમ્સમાં પેજ રિપ્લેસમેન્ટ એલ્ગોરિધમ્સ માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમયની જટિલતા

હેશસેટનો ઉપયોગ કરવાથી આપેલ આપેલ અલ્ગોરિધમનોને રેખીય સમયમાં ચલાવવાની મંજૂરી આપવામાં આવી છે. આમ અલ્ગોરિધમમાં રેખીય સમયની જટિલતા છે ઓ (એન).

અવકાશ જટિલતા

ઓ (પેજ સ્લોટ્સ), અમે કતારમાં ફક્ત પૃષ્ઠસ્લોટ્સ પૃષ્ઠો જ રાખીએ છીએ. આમ જગ્યા જટિલતા પેજ સ્લોટ્સ પર આધારિત છે.