Operating Systems တွင်စာမျက်နှာအစားထိုး Algorithms


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ သိမှ အချက်အလက် Microsoft က PayPal က
လည်ပတ်မှုစနစ်များ သဘောတရား

စာမျက်နှာအစားထိုးဆိုတာဘာလဲ။

မျက်မှောက်ခေတ်လည်ပတ်သည့်စနစ်များသည်မှတ်ဥာဏ်စီမံခန့်ခွဲမှုအတွက် paging ကိုအသုံးပြုသည်။ စာမျက်နှာကိုအစားထိုးခြင်းဆိုသည်မှာမှတ်ဉာဏ်ထဲတွင်လက်ရှိရှိနေသောစာမျက်နှာကိုလိုအပ်သော်လည်းမှတ်ဉာဏ်တွင်မရှိသောစာမျက်နှာတစ်ခုအားအစားထိုးခြင်းလုပ်ငန်းစဉ်ဖြစ်သည်။ ထိုသို့သောအခြေအနေကို Page Fault ဟုခေါ်သည်။

Page Replacement Algorithm ၏ရည်မှန်းချက်မှာ Page Faults အရေအတွက်ကိုလျှော့ချရန်ဖြစ်ပြီးစွမ်းဆောင်ရည်ကိုမြှင့်တင်ရန်ဖြစ်သည်။ စာမျက်နှာကိုအစားထိုးဘို့များစွာသော algorithms ရှိပါတယ်။ ကျနော်တို့ဒီမှာအနည်းငယ်ဆွေးနွေးနေကြသည်။

ပထမ ဦး ဆုံးအထဲကပထမ (FIFO)

ပထမ ဦး ဆုံးအထဲကပထမ ဦး ဆုံး စာမျက်နှာအစားထိုး Algorithm စာမျက်နှာကိုအစားထိုးဘို့အရိုးရှင်းဆုံး algorithm ကိုဖြစ်ပါတယ်။ စာမျက်နှာများအားလုံးကိုခြေရာခံရန်တန်းစီထားသည်။ ကျနော်တို့တန်းစီ၏အဆုံးသို့စာမျက်နှာအသစ်တစ်ခုကိုထည့်ပါ။ ဘယ်အချိန်မှာ ဆံပင်ကြိုး ပြည့်နေတယ်၊ ​​Page Fault လည်းရှိတယ်၊ တန်းစီရဲ့ရှေ့ဖက်မှာရှိနေတဲ့စာမျက်နှာကိုဖယ်ထုတ်လိုက်ပြီး၊ တန်းရဲ့အဆုံးမှာစာမျက်နှာအသစ်တစ်ခုထပ်ထည့်လိုက်တယ်။
ဤနည်းအားဖြင့်ကျွန်ုပ်တို့သည်ပထမ ဦး ဆုံးထုတ်နည်းစနစ်ကိုထိန်းသိမ်းသည်။ ဆိုလိုသည်မှာပထမဆုံးမှတ်ဉာဏ်ထဲထည့်လိုက်သောစာမျက်နှာကိုပထမဆုံးမှတ်ဉာဏ်မှဖယ်ရှားလိမ့်မည်။

နမူနာ

စာမျက်နှာအညွှန်းစာသား {1, 0, 1, 2, 5, 7, 3, 4, 3, 4, 1} နှင့်စုစုပေါင်း 4 စာမျက်နှာ slot နှစ်ခုရှိပါတယ်ကြပါစို့။ ထို့နောက်

Operating Systems တွင်စာမျက်နှာအစားထိုး Algorithms

Belady ရဲ့ Anomaly

Belady သည်အချို့သောစာမျက်နှာရည်ညွှန်းညှို့ညှပ်မှုများအတွက်စာမျက်နှာပိတ်ခြင်းကိုတိုးမြှင့်ခြင်းကြောင့်စာမျက်နှာအမှားများပိုများလာနိုင်သည်ကိုသက်သေပြခဲ့သည်။

နမူနာ
စာမျက်နှာကိုးကားထားသော string ကို {3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4} စာမျက်နှာ ၃ ခုနှင့်စာမျက်နှာ ၄ ​​ခုပါသော slot များထည့်သွင်းစဉ်းစားပါ။
စာမျက်နှာ ၃ မျက်နှာရှိစာမျက်နှာပြFaနာများ = ၃
စာမျက်နှာ ၃ မျက်နှာရှိစာမျက်နှာပြFaနာများ = ၃

အကောင်းဆုံးစာမျက်နှာအစားထိုး

ဒီ algorithm ကဆိုလျှင်ကျွန်ုပ်တို့သည်အနာဂတ်၌မည်သည့်စာမျက်နှာကိုအသုံးပြုမည်ကိုကျွန်ုပ်တို့သိပါကကျွန်ုပ်တို့သည်စာမျက်နှာကိုအစားထိုးခြင်းနည်းစနစ်ကိုအကောင်းဆုံးဖြစ်စေနိုင်သည်ဟုဆိုသည်။
Optimal Page Replacement algorithm အရအနာဂတ်တွင်အနည်းဆုံးအသုံးပြုမည့်စာမျက်နှာကိုအစားထိုးရန်အမြဲတမ်းအကောင်းဆုံးဖြစ်သည်။

နမူနာ

စာမျက်နှာအညွှန်းစာသား {2, 3, 4, 2, 1, 3, 7, 5, 4, 3} နှင့်စုစုပေါင်းစာမျက်နှာ 3 slot နှစ်ခုရှိပါတယ်ကြပါစို့။ ထို့နောက်

Operating Systems တွင်စာမျက်နှာအစားထိုး Algorithms

အနည်းဆုံးအသုံးပြုထားသော

ဒီ algorithm ကို cache technique ကိုအပေါ်အခြေခံသည်။ အဆိုပါ algorithm ကိုကမကြာသေးမီကာလများတွင်အနည်းဆုံးအသုံးပြုခဲ့သည့်စာမျက်နှာကိုအစားထိုးကပြောပါတယ်။

နမူနာ

စာမျက်နှာအညွှန်းစာသား {1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4} နှင့်စုစုပေါင်း 3 စာမျက်နှာ slot နှစ်ခုရှိပါတယ်ကြပါစို့။ ထို့နောက်

Operating Systems တွင်စာမျက်နှာအစားထိုး Algorithms

ပထမ ဦး ဆုံးအထဲကပထမ ဦး ဆုံးအကောင်အထည်ဖော်မှု

Operating Systems တွင် Page အစားထိုး Algorithms များအတွက် Java code

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

Operating Systems ရှိစာမျက်နှာအစားထိုး Algorithms များအတွက် 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

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

HashSet ကိုအသုံးပြုခြင်းအားဖြင့်ပေးထားသော algorithm ကို linear အချိန်တွင်အသုံးပြုရန်ခွင့်ပြုထားသည်။ ထို့ကြောင့် algorithm ကို linear အချိန်ရှုပ်ထွေးရှိပါတယ် အို (N).

အာကာသရှုပ်ထွေးမှု

အို (စာမျက်နှာနံပါတ်များ), ကျနော်တို့တန်းစီထဲမှာသာ pageSlots စာမျက်နှာအရေအတွက်ကိုစောင့်ရှောက်ခဲ့ကြပြီ။ ထို့ကြောင့်ရှုပ်ထွေးမှုသည် pageSlots ပေါ်တွင်မူတည်သည်။