මෙහෙයුම් පද්ධතිවල පිටු ප්‍රතිස්ථාපන ඇල්ගොරිතම


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් සංජානන ෆැක්ට්සෙට් මයික්රොසොෆ්ට් පේපෑල්
මෙහෙයුම් පද්ධති න්යාය

පිටු ප්‍රතිස්ථාපනය යනු කුමක්ද?

නවීන මෙහෙයුම් පද්ධති මතක කළමනාකරණය සඳහා පේජින් භාවිතා කරන අතර බොහෝ විට පිටු ප්‍රතිස්ථාපනය කිරීමේ අවශ්‍යතාවයක් පවතී. පිටු ප්‍රතිස්ථාපනය යනු මතකයේ දැනට පවතින පිටුවක් අවශ්‍ය පිටුවක ප්‍රතිස්ථාපනය කිරීමේ ක්‍රියාවලියයි. එවැනි කොන්දේසියක් පේජ් ෆෝල්ට් ලෙස හැඳින්වේ.

පිටු ප්‍රතිස්ථාපන ඇල්ගොරිතමයේ පරමාර්ථය වන්නේ සමස්ත ක්‍රියාකාරිත්වය වැඩි කිරීම සඳහා පිටු දෝෂ ගණන අඩු කිරීමයි. පිටු ප්‍රතිස්ථාපනය සඳහා බොහෝ ඇල්ගොරිතම ඇත. අපි මෙහි කිහිපයක් සාකච්ඡා කරමු.

ෆස්ට් ඉන් ෆස්ට් අවුට් (FIFO)

පළමුව ඇතුලට යන කෙනා පළමුව එළියට එයි පිටු ආදේශන ඇල්ගොරිතම පිටු ප්‍රතිස්ථාපනය සඳහා සරලම ඇල්ගොරිතම වේ. එය සියලු පිටු නිරීක්ෂණය කිරීම සඳහා පෝලිමක් පවත්වා ගනී. අපි සෑම විටම පෝලිමේ අවසානයට නව පිටුවක් එක් කරන්නෙමු. විට පෝලිමේ පිරී ඇති අතර පිටු දෝෂයක් ඇත, අපි පෝලිමේ ඉදිරිපස ඇති පිටුව ඉවත් කර පෝලිම් අවසානයේ නව පිටුවක් එක් කරමු.
මේ ආකාරයට අපි පළමුවැන්න පළමු තාක්ෂණයෙන්, එනම් මතකයට ඇතුල් කළ පිටුව පළමුව මතකයෙන් ඉවත් කරනු ලැබේ.

උදාහරණයක්

පිටු යොමු කිරීමේ දාමය {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1 be විය යුතු අතර පිටු 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 be විය යුතු අතර මුළු පිටු 3 ක් ඇත. ඉන්පසු,

මෙහෙයුම් පද්ධතිවල පිටු ප්‍රතිස්ථාපන ඇල්ගොරිතම

අවම වශයෙන් මෑතකදී භාවිතා කරන ලදි

මෙම ඇල්ගොරිතම හැඹිලි තාක්ෂණය මත පදනම් වේ. ඇල්ගොරිතම පවසන්නේ මෑත කාලයේ අවම වශයෙන් භාවිතා කළ පිටුව ප්‍රතිස්ථාපනය කරන බවයි.

උදාහරණයක්

පිටු යොමු කිරීමේ දාමය {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4 be විය යුතු අතර පිටු 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

හැෂ්සෙට් භාවිතා කිරීමෙන් අපට ලබා දී ඇති ඇල්ගොරිතම රේඛීය වේලාවට ධාවනය කිරීමට ඉඩ ලබා දී ඇත. මේ අනුව ඇල්ගොරිතමයට රේඛීය කාල සංකීර්ණතාවයක් ඇත මත).

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (පිටු ස්ලොට්), අපි පෝලිම්වල පිටු ගණනක් පමණක් තබා ඇත. මේ අනුව අවකාශයේ සංකීර්ණත්වය පිටු ස්ලොට් මත රඳා පවතී.