خوارزميات استبدال الصفحة في أنظمة التشغيل


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون تدرك مجموعة الحقائق Microsoft Paypal
أنظمة التشغيل نظرية

ما هو استبدال الصفحة؟

تستخدم أنظمة التشغيل الحديثة الترحيل لإدارة الذاكرة وهناك حاجة في كثير من الأحيان لاستبدال الصفحة. استبدال الصفحة هو عملية استبدال الصفحة الموجودة حاليًا في الذاكرة بصفحة مطلوبة ولكنها غير موجودة في الذاكرة. يُطلق على هذا الشرط اسم خطأ الصفحة.

هدف خوارزمية استبدال الصفحة هو تقليل عدد أخطاء الصفحة لزيادة الأداء العام. هناك العديد من الخوارزميات لاستبدال الصفحة. نحن نناقش القليل هنا.

First In First Out (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

استبدال الصفحة الأمثل

تقول هذه الخوارزمية أنه إذا عرفنا الصفحة التي سنستخدمها في المستقبل ، فيمكننا تحسين تقنية استبدال الصفحة.
وفقًا لخوارزمية Optimal Page Replacement ، من الأفضل دائمًا استبدال الصفحة التي سيتم استخدامها على الأقل في المستقبل.

مثال

دع السلسلة المرجعية للصفحة تكون {2 ، 3 ، 4 ، 2 ، 1 ، 3 ، 7 ، 5 ، 4 ، 3} وهناك إجمالي 3 فتحات للصفحة. ثم،

خوارزميات استبدال الصفحة في أنظمة التشغيل

الأقل استخدامًا مؤخرًا

تعتمد هذه الخوارزمية على تقنية التخزين المؤقت. تقول الخوارزمية أن تحل محل الصفحة الأقل استخدامًا في الآونة الأخيرة.

مثال

دع السلسلة المرجعية للصفحة تكون {1 ، 2 ، 3 ، 4 ، 1 ، 2 ، 5 ، 1 ، 2 ، 3 ، 4} ويوجد إجمالي 3 فتحات للصفحة. ثم،

خوارزميات استبدال الصفحة في أنظمة التشغيل

تنفيذ First In First Out

كود جافا لخوارزميات استبدال الصفحة في أنظمة التشغيل

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

تحليل التعقيد

تعقيد الوقت

سمح لنا استخدام HashSet بتشغيل الخوارزمية المعطاة في الوقت الخطي. وبالتالي فإن الخوارزمية لها تعقيد زمني خطي على).

تعقيد الفضاء

O (pageSlots) ، لقد ظللنا نحتفظ فقط بعدد pageSlots من الصفحات في قائمة الانتظار. وبالتالي فإن تعقيد المساحة يعتمد على فتحات الصفحة.