通过代码实例了解页面置换算法原理

页面置换算法：本质是为了让有限内存能满足无线进程。

先说明一下处理缺页错误的过程：

分页硬件在通过页表转换地址时会注意到无效位被设置，从而陷入操作系统，这种陷阱是因为操作系统未能将所需要的页面调入内存引起的。

处理缺页错误：

1、检查这个进程的内部表，确定该引用是否为有效的内存访问（可以理解为这个内存能被当前进程使用），如果无效那么直接终止进程；如果有效但是尚未调入页面，就将该页面调入内存。

2、然后从空闲帧链表上找到一个空闲帧。

3、调度磁盘将进程所需要的内存读入页帧中，

4、磁盘读取完成，修改页表，使空闲帧对应到该页号上。并且修改页表有效-无效位 为有效。

注意页表中的一些标志位：

修改位：如果有效为位1，表明被修改，那么替换页面时需要将内存写入磁盘中；如果为0，表明未被修改，那么使用页面替换算法直接释放

保护位：可以标记为只读，写。

有效-无效位：i：表示逻辑页号不对应物理页帧，为V表示有对应的物理页帧

页面替换算法：

FIFO:算法

操作系统总时替换出在内存中停留时间最久的页面，可以用一个指针来指向这个位置（开销很小，可以使用一个队列来实现，每次缺页时移出末尾的页面，再队列头添加新的页面，未发生缺页错误就不需要对队列进行操作）

LRU算法：操作系统总时替换在内存中最久没有使用的页面：我么可以使用链表来实现这个算法，表头表示的是最近被使用的页面，表尾表示最久没被使用的页面，每一次不管是否发生缺页，都需要对这个链表进行从新增删改查，来保证每一次的链表都是我们需要的（开销太大）

近似LRU算法：我们在页表中添加一个引用位clock，当clock为1时，不能移出，当clock为0时，表明可以移除

procedure t: {
  指针p：指向当前的页面
  p = 0;//指向初始位置
  boolean ：标志位clock
  进程包含的所有页面组成的循环链表：linklist//当进程在运行时，链表存在，进程结束时，链表也消失
  while(进程运行){

    if(p.clock == 1){
      p.clock = 0;
      p++;//指针指向下一个
    }
    if(p.clock == 0){
      删除p指向的页面并且在p处添加新的页面；
      p.clock = 1;
      p++;
    }
  }
}

近似LRU增强算法：将修改位和引用位合起来作为是否替换条件：当（修改位，引用位） = （0，0）时表明可以替换

procedure t: {
  指针p：指向当前的页面
  p = 0;//指向初始位置
  boolean ：标志位clock
  boolean : 修改位m
  进程包含的所有页面组成的循环链表：linklist//当进程在运行时，链表存在，进程结束时，链表也消失
  while(进程运行){

    if(p.(clock,m) == (0,0)){

      删除p指向的页面并且在p处添加新的页面；
      p.(clock,m) = (1,0);
      p++;
    }
    if(p.(clock,m) == (0,1)){

      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,0)){

      p.(clock,m) = (0,0);
      p++;
    }
    if(p.(clock,m) == (1,1)){

      p.(clock,m) = (0,1);
      p++;
    }
    if(修改页面){
      p.(clock,m) = (1,1);
      p++
    }
    if(读页面){
      p.(clock,m) = (1,0);
      p++;
    }
  }
}

页面缓冲算法：操作做系统保留一个空闲帧池。

当发生缺页错误时，所需要的页面就读取空闲帧，并且将替换的牺牲帧放入缓冲池，在调页空闲时期将缓冲池中的牺牲帧中的内容写入（如果页表上的修改位为1）磁盘中（减少了操作系统的调页时直接访问磁盘的过程，提高了调页效率）.

第二种方法：将牺牲帧中的内容写入磁盘，但是不释放帧中的内容，因为进程有可能调用之前的页，这样就将缓冲池中的帧直接写入内存，减少了（从磁盘读取数据的操作）。

以上均为局部页面置换算法，都是在单个进程内部进行的页面替换操作，但是操作系统在运行过程中不同的进程可以并行并发执行，这样对页面的替换就不会仅仅局限于单个进程中

下面我们学习全局置换算法：我们规定一个工作集和一个常驻集。工作集表明当前程序需要访问的Δ个页面，常驻集表明操作系统正在使用的页面。

工作集：WS(Δ，t) = {}　　工作集不断移动，操作系统替换出不在工作集中的页面

动态工作集页面替换算法：如下图，我们规定一个阈值windows size = 2，我们使用两次缺页中断的差值（表明两次中断之间有多少次没有中断）和阈值比较，如果比阈值大，那么将不再当前工作集的页面换出，并且重置工作集的大小，如果比阈值小，那么将缺的页换入工作集并且重置工作集的大小。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python实现mean-shift聚类算法

    本文实例为大家分享了python实现mean-shift聚类算法的具体代码,供大家参考,具体内容如下 1.新建MeanShift.py文件 import numpy as np # 定义 预先设定 的阈值 STOP_THRESHOLD = 1e-4 CLUSTER_THRESHOLD = 1e-1 # 定义度量函数 def distance(a, b): return np.linalg.norm(np.array(a) - np.array(b)) # 定义高斯核函数 def gaussian

  • redis 数据删除策略和逐出算法的问题小结

    数据存储和有效期 在 redis 工作流程中,过期的数据并不需要马上就要执行删除操作.因为这些删不删除只是一种状态表示,可以异步的去处理,在不忙的时候去把这些不紧急的删除操作做了,从而保证 redis 的高效 数据的存储 在redis中数据的存储不仅仅需要保存数据本身还要保存数据的生命周期,也就是过期时间.在redis 中 数据的存储结构如下图: 获取有效期 Redis是一种内存级数据库,所有数据均存放在内存中,内存中的数据可以通过TTL指令获取其状态 删除策略 在内存占用与CPU占用之间寻找一

  • 详细分析JAVA加解密算法

    加解密算法分析 日常开发中,无论你是使用什么语言,都应该遇到过使用加解密的使用场景,比如接口数据需要加密传给前端保证数据传输的安全:HTTPS使用证书的方式首先进行非对称加密,将客户端的私匙传递给服务端,然后双方后面的通信都使用该私匙进行对称加密传输:使用MD5进行文件一致性校验,等等很多的场景都使用到了加解密技术. 很多时候我们对于什么时候要使用什么样的加解密方式是很懵的.因为可用的加解密方案实在是太多,大家对加解密技术的类型可能不是很清楚,今天这篇文章就来梳理一下目前主流的加解密技术,本篇文

  • 如何基于js及java分析并封装排序算法

    前言 本次来分享一下排序的api底层的逻辑,这次用js模拟,java的逻辑也是差不多. 先看封装好的api例子: js的sort排序 java的compareTo排序 自己模拟的代码(JS) function compareTo(a,b){ return a-b;//a-b为从下到大 b-a为从大到小 } Object.prototype.newSort = function(Func){ const flag = Func(1,0); const $this = this; // 注意:上面f

  • 详解vue3.0 diff算法的使用(超详细)

    前言:随之vue3.0beta版本的发布,vue3.0正式版本相信不久就会与我们相遇.尤玉溪在直播中也说了vue3.0的新特性typescript强烈支持,proxy响应式原理,重新虚拟dom,优化diff算法性能提升等等.小编在这里仔细研究了vue3.0beta版本diff算法的源码,并希望把其中的细节和奥妙和大家一起分享. 首先我们来思考一些大中厂面试中,很容易问到的问题: 1 什么时候用到diff算法,diff算法作用域在哪里? 2 diff算法是怎么运作的,到底有什么作用? 3 在v-f

  • Python实现ElGamal加密算法的示例代码

    在密码学中,ElGamal加密算法是一个基于迪菲-赫尔曼密钥交换的非对称加密算法.它在1985年由塔希尔·盖莫尔提出.GnuPG和PGP等很多密码学系统中都应用到了ElGamal算法. ElGamal加密算法可以定义在任何循环群G上.它的安全性取决于G上的离散对数难题. 使用Python实现ElGamal加密算法,完成加密解密过程,明文使用的是125位数字(1000比特). 代码如下: import random from math import pow a = random.randint(2

  • 经典实例讲解C#递归算法

    一 .递归算法简介 在数学与计算机科学中,递归是指在函数的定义中使用函数自身的方法. 递归算法是一种直接或者间接地调用自身算法的过程.在计算机编写程序中,递归算法对解决一大类问题是十分有效的,它往往使算法的描述简洁而且易于理解. 递归算法解决问题的特点: (1) 递归就是在过程或函数里调用自身. (2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口. (3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低.所以一般不提倡用递归算法设计程序. (4) 在递归调用的过程当中

  • SHA:安全散列算法简析 附实例

    前言 体能状态先于精神状态,习惯先于决心,聚焦先于喜好. SHA算法简介 1.1 概述 SHA (Secure Hash Algorithm,译作安全散列算法) 是美国国家安全局 (NSA) 设计,美国国家标准与技术研究院(NIST) 发布的一系列密码散列函数.正式名称为 SHA 的家族第一个成员发布于 1993年.然而人们给它取了一个非正式的名称 SHA-0 以避免与它的后继者混淆.两年之后, SHA-1,第一个 SHA 的后继者发布了. 另外还有四种变体,曾经发布以提升输出的范围和变更一些细

  • 通过代码实例了解页面置换算法原理

    页面置换算法:本质是为了让有限内存能满足无线进程. 先说明一下处理缺页错误的过程: 分页硬件在通过页表转换地址时会注意到无效位被设置,从而陷入操作系统,这种陷阱是因为操作系统未能将所需要的页面调入内存引起的. 处理缺页错误: 1.检查这个进程的内部表,确定该引用是否为有效的内存访问(可以理解为这个内存能被当前进程使用),如果无效那么直接终止进程:如果有效但是尚未调入页面,就将该页面调入内存. 2.然后从空闲帧链表上找到一个空闲帧. 3.调度磁盘将进程所需要的内存读入页帧中, 4.磁盘读取完成,修

  • java实现页面置换算法

    本文实例为大家分享了java实现页面置换算法的具体代码,供大家参考,具体内容如下 原理就不说了,直接上代码 FIFO import java.util.ArrayList; import java.util.List; import utils.ListUtils; /** * * * @author cnkeysky * */ public class FIFO { public void run() { String[] inputStr = {"1", "2"

  • C语言实现页面置换算法

    C语言实现页面置换算法

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时

  • 利用C语言实现页面置换算法的详细过程

    目录 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 题目: 代码 总结 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择

  • Linux页面置换算法的C语言实现

    Linux页面置换算法的C语言实现 编写算法,实现页面置换算法FIFO.LRU.OPT:针对内存地址引用串,进行页面置换算法进行页面置换. 其中,算法所需的各种参数由输入产生(手工输入或者随机数产生):输出内存驻留的页面集合,缺页次数以及缺页率. #include <stdio.h> //#include <conio.h> #include <stdlib.h> #include <time.h>//随机数 #define Myprintf printf(

  • C语言实现页面置换算法(FIFO、LRU)

    C语言实现页面置换算法(FIFO、LRU)

    目录 1.实现效果 2.实现源代码  1.实现效果 2.实现源代码  #include<iostream> #include<process.h> #include<stdlib.h> #include<ctime> #include<conio.h> #include<stdio.h> #include<string.h> using namespace std; #define Myprintf printf(&quo

  • 通过代码实例解析PHP session工作原理

    这里的介绍主要是基于php语言,其他的语言操作可能会有差别,但基本的原理不变. 1.在php中如何操作session: session_start(); //使用该函数打开session功能 $_SESSION //使用预定义全局变量操作数据 使用unset($_SESSION['key']) //销毁一个session的值 简单地操作,一切都是由服务器实现:由于处理在后台,一切看起来也很安全.但是session采用什么样机制,又是怎样被实现,并且如何来保持会话的状态的呢? 2.session实

  • C语言实现页面置换 先进先出算法（FIFO）

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 一.设计目的 加深对请求页式存储管理实现原理的理解,掌握页面置换算法中的先进先出算法. 二.设计内容 设计一个程序,有一个虚拟存储区和内存工作区,实现下述三种算法中的任意两种,计算访问命中率(命中率=1-页面失效次数/页地址流长度).附加要求:能够显示页面置换过程. 该系统页地址流长度为320,页面失效次数为每次访问相应指令时,该指令对应的页不在内存的次数.    程序首先用srand()和rand()函数分别进行初

  • Python实现的插入排序算法原理与用法实例分析

    Python实现的插入排序算法原理与用法实例分析

    本文实例讲述了Python实现的插入排序算法原理与用法.分享给大家供大家参考,具体如下: 插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的.个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2).是稳定的排序方法 插入算法把要排序的数组分成两部分:第一部分包含了这个数组的所有元素,但将最后一个元素除外(让数组多一个空间才有插入的位置),而第二部分就只包含这一个元素(即待插入元素).在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分中. 插

  • Java算法之数组冒泡排序代码实例讲解

    冒泡排序是数组查找算法中最为简单的算法 冒泡排序原理: 假设一个数组长度为k(最高索引k-1),遍历前k - 1个(最高索引k-2)元素,若数组中的元素a[i]都与相邻的下一个元素a[i+1]进行比较,若a[i] > a[i+1] ,则这两个元素交换位置.以此类推,若a[i+1] > a[i+2],则交换位置-直至a[k-2]与a[k-1]比较完毕后,第0轮迭代结束.此时,a[k-1]为数组元素中的最大值. 第1轮迭代,再对数组a的前k-1个元素重复进行以上操作. - 第k-2轮迭代,对数组a

随机推荐