操作系统中的页面替换算法

2021年1月15日09:59:30 发表评论 125 次浏览

本文概述

什么是页面替换?

现代操作系统使用分页进行内存管理, 很多时候需要页面替换。页面替换是将内存中当前存在的页面替换为需要但内存中不存在的页面的过程。这种情况称为"页面错误"。

页面替换算法的目标是减少页面错误的数量, 以提高整体性能。有许多用于页面替换的算法。我们在这里讨论一些。

先进先出(FIFO)

先进先出

页面替换算法

是最简单的页面替换算法。它维护一个队列以跟踪所有页面。我们总是在队列末尾添加一个新页面。当。。。的时候

队列

已满并且有页面错误, 我们删除队列前面的页面, 并在队列末尾添加一个新页面。

通过这种方式, 我们将保持先进先出技术, 也就是说, 首先从内存中删除首先插入内存的页面。

例子

令页面引用字符串为{1、0、1、2、5、7、3、4、3、4、1}, 总共有4个页面槽。然后,

操作系统中的页面替换算法

贝拉迪的异常

Belady证明某些页面引用字符串可能会增加页面槽位, 从而导致更多的页面错误。

例子

考虑具有3个页面插槽和4个页面插槽的页面参考字符串{3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 1, 0, 4}。

具有3个页面插槽的页面错误= 3

具有4个页面插槽的页面错误= 4

最佳页面替换

该算法表示, 如果我们知道将来要使用哪个页面, 则可以优化页面替换技术。

根据最佳页面替换算法, 始终最好替换将来将最少使用的页面。

例子

假设页面参考字符串为{2, 3, 4, 2, 1, 3, 7, 5, 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。

推荐文章:

  • JavaScript中的页面重定向
  • 数字系统的优势
  • 在DBMS中分发数据库系统
  • 数字数字系统的转换
  • 平衡表达与替换
  • 更换后最小的回文
  • 每次替换字符后检查回文查询
一盏木

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: