操作系統中的頁面替換算法


難度級別
經常問 亞馬遜 認識到 事實集 Microsoft微軟 貝寶
操作系統 理論

什麼是頁面替換?

現代操作系統使用分頁進行內存管理,並且很多時候需要頁面替換。 頁面替換是將內存中當前存在的頁面替換為需要但內存中不存在的頁面的過程。 這種情況稱為“頁面錯誤”。

頁面替換算法的目標是減少頁面錯誤的數量,從而提高整體性能。 有許多用於頁面替換的算法。 我們在這裡討論一些。

先進先出(FIFO)

先進先出 頁面替換算法 是最簡單的頁面替換算法。 它維護一個隊列以跟踪所有頁面。 我們總是將新頁面添加到隊列的末尾。 當。。。的時候 隊列 已滿,並且存在頁面錯誤,我們刪除隊列前面的頁面,並在隊列末尾添加一個新頁面。
通過這種方式,我們將保持先進先出技術,也就是說,首先從內存中刪除首先插入到內存中的頁面。

令頁面引用字符串為{1、0、1、2、5、7、3、4、3、4、1},總共有4個頁面槽。 然後,

操作系統中的頁面替換算法

貝拉迪的異常

貝拉迪(Belady)證明,某些頁面參考字符串可能會增加頁面插槽,從而導致更多的頁面錯誤。


考慮具有3個頁面插槽和2個頁面插槽的頁面參考字符串{1,0,3,2,4,3,2,1,0,4,3,4,XNUMX}。
具有3個頁面插槽的頁面錯誤= 3
具有4個頁面插槽的頁面錯誤= 4

最佳頁面替換

該算法表示,如果我們知道將來要使用哪個頁面,則可以優化頁面替換技術。
根據最佳頁面替換算法,始終最好替換將來將最少使用的頁面。

令頁面參考字符串為{2,3,4,2,1,3,7,5,4,3,3},共有XNUMX個頁面槽。 然後,

操作系統中的頁面替換算法

最近最少使用

該算法基於緩存技術。 算法說替換最近最少使用的頁面。

令頁面引用字符串為{1、2、3、4、1、2、5、1、2、3、4},總共有3個頁面槽。 然後,

操作系統中的頁面替換算法

先進先出的實施

操作系統中用於頁面替換算法的Java代碼

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頁數。 因此,空間複雜度取決於pageSlots。