オペレーティングシステムのページ置換アルゴリズム


難易度 ミディアム
よく聞かれる Amazon (アマゾン) 認識して ファクトセット マイクロソフト PayPal
オペレーティングシステム 理論

ページ置換とは何ですか?

最新のオペレーティングシステムは、メモリ管理にページングを使用しており、多くの場合、ページ置換が必要です。 ページ置換は、現在メモリに存在するページを、必要であるがメモリには存在しないページに置き換えるプロセスです。 このような状態は、ページフォールトと呼ばれます。

ページ置換アルゴリズムの目標は、ページフォールトの数を減らして、全体的なパフォーマンスを向上させることです。 ページ置換には多くのアルゴリズムがあります。 ここでいくつか議論しています。

先入れ先出し(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}について考えてみます。
3ページスロットのページフォールト= 3
4ページスロットのページフォールト= 4

最適なページ置換

このアルゴリズムは、将来どのページを使用するかがわかっている場合は、ページ置換手法を最適化できることを示しています。
最適なページ置換アルゴリズムによれば、将来最も使用されないページを置換することが常に最適です。

ページ参照文字列を{2、3、4、2、1、3、7、5、4、3}とし、合計3つのページスロットがあります。 次に、

オペレーティングシステムのページ置換アルゴリズム

最近使用されていない

このアルゴリズムは、キャッシュ技術に基づいています。 アルゴリズムは、最近最も使用されていないページを置き換えることを示しています。

ページ参照文字列を{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に依存します。