精华内容
下载资源
问答
  • 时钟置换算法
    万次阅读
    2018-08-19 15:15:57

    系统为进程分配内存,进程是部分装入的。当需要的程序没有在内存中,就产生缺页异常,在进程缺页率正常情况下,系统会根据记录型的数据结构来选择工作集中的某个页淘汰掉,换成调入页。选择淘汰哪个页的算法通常称为页置换算法。

    时钟置换算法就是一种页置换算法。

    页置换算法选择被淘汰的页有几个原则

    • 尽量未被修改(不用再存回磁盘)
    • 最近未被访问(程序局部性原理)
      依赖这两种考虑,操作系统维持这样一个数据结构-环形队列

    环形队列的节点:

    修改位访问位页框号

    0表示最近未被访问和修改,1相反。
    时钟置换算法会多遍扫描环形队列。
    1.第一遍:优先寻找修改位和访问位都为0
    2.第二遍:若第一遍未寻找到,则继续扫描,扫描过的节点置访问位为0,
    并寻找放低标准寻找未访问的修改过的页。
    3.若找到,结束;未找到,重复1,2

    更多相关内容
  • 算法又称为第二次机会算法;大致有两种思路: 思路1: 王道讲解的: 思路2: 清华大学陈渝讲解的: 刚开始接触时,觉得有一个是错误的,但不知道是哪个错误,其次清华大学这个也不太理解。尤其是讲到例子:...

    此算法又称为第二次机会算法;大致有两种思路:

    思路1:

    王道讲解的:

    思路2:

    清华大学陈渝讲解的:

    刚开始接触时,觉得有一个是错误的,但不知道是哪个错误,其次清华大学这个也不太理解。尤其是讲到例子:当页面e进入时,为什么a(11)变成了a(00),b(11)变为了b(00).经过多次听讲终于明白了(参考自操作系统(RISC-V) - 清华大学 - 学堂在线爆肝上传!清华大佬终于把困扰我大学四年的【计算机操作系统】讲的如此通俗易懂_哔哩哔哩_bilibili):

    它是从指针开始的位置开始扫描,

    只要遇到(0,0) 则直接进行置换,并伴随的指针的后移;

    只要遇到(0,1)变为(0,0),指针后移;

    只要遇到(1,0)变为(0,0),指针后移;

    只要遇到(1,1)变为(0,1),,指针后移;

    指针一直循环扫描。

    所以当e页面进入时,第一轮为:a(01) b(01) c(00) d(00) 第二轮 a(00) b(00),页面c为00,所以调出页面c,调入页面e(10),且指针下移,指向页面d。

     使用此种思路和王道思路发现最后殊途同归,结果一致,但本人认为还是清华的思路更为简洁,清楚。

    展开全文
  • 背景:在内存不足的情况下,操作系统会将内存中暂时不需要使用的信息换出到外存,页面置换算法就是用于选择到底将哪个页面换出到外存的算法。 注意:页面置换算法的好坏是可以通过缺页率来体现的,一个好的页面置换...

    来源:https://www.bilibili.com/video/BV1YE411D7nH

    背景:在内存不足的情况下,操作系统会将内存中暂时不需要使用的信息换出到外存,页面置换算法就是用于选择到底将哪个页面换出到外存的算法。

    在这里插入图片描述

    注意:页面置换算法的好坏是可以通过缺页率来体现的,一个好的页面置换算法往往拥有较小的缺页率


    1. 最佳置换算法(Optimal,OPT)

    思想:每次选择淘汰的页面将是以后永远不再使用或在最长时间内不再使用的页面,以保证最低的缺页率。

    例子:假如系统为操作系统分配了三个内存块,并且采用以下的页面号引用串(会依次访问这些页面):7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0

    访问页面7012030423032120
    内存块177722222
    内存块20000400
    内存块3113331
    是否缺页YYYYYYYY

    解释:首先进程一共有三个内存块,因此7 、0、 1依次进入内存块。当2想要进入内存块的时候,发现已满(里面是7,0,),这时候从前往后找,0和1下一次会被使用的位置,在7下一次使用的位置之前。这说明7就是最长时间不会被使用的页面,因此将7的内存块换出到外存,2进入到内存块1。后面依次类推。在整个过程中:缺页中断发生了8次**,页面置换发生了5次(前3次都发生了缺页,但是没用进行置换)。因此可以知道:**缺页时未必发生页面置换,若还有可用的内存块时,就不会进行置换

    总结:最佳置换算法可以保证最低的缺页率,但是实际上不能被实现。因为只有在进程执行过程中才能知道接下来会访问哪个页面,而操作系统并不能提前预知页面的访问顺序

    先进先出置换算法(FIFO)

    思想:每次选择淘汰的页面是最早进入内存的页面(FIFO队列的最大长度取决于系统为进程分配了多少个内存块)

    例子:假设系统为某进程分配了三个内存块,并以下面的页面号为引用串:3,2,1,0,3,2,4,3,2,1,0

    访问页面32103243210
    内存块1333000444
    内存块222233311
    内存块31112220
    是否缺页YYYYYYYYY

    解释:当访问1号页面的时候,这时候队列的形式是3->2->1;当要访问0号页面的时候,内存已满,则将最先进入队列的3置换到外存,这时候队列的形式为2->1>0,后面的情形可以依次类推

    注意

    • FIFO算法实现简单,但是与进程实际运行的规律相违背,因为先进入内存的页面也可能会被经常访问。

    • FIFO算法会出现Belady(贝拉迪)异常

      **Belady异常**是指:当为进程分配的物理块数增大的时候,缺页的次数不增反减(在上面的例子中,如果将内存块改为4个,其他不变,那么缺页的次数将达到10次)

    最近最少使用置换算法(Least Recently Used,LRU)

    思想:淘汰最近最少使用的页面

    实现方法:在每个页面的页表项中,用访问字段记录该页面自从上一次被访问以来经历的时间t,如果需要淘汰一个页面的话,就在页表中选择t值最大的页面。格式如下:

    页号内存块号状态位(0表示未进入内存,1表示在内存)访问字段修改位外存地址

    例子:假设系统为某进程分配了四个内存块,并以下面的页面号为引用串:1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7

    访问页面18178272183821317
    内存块1111111
    内存块288887
    内存块37733
    内存块4222
    是否缺页YYYYYY

    解释:首先肯定是1 8 7 2将内存填满,在下一次访问到3的时候,这时候内存中没有,所以要进行置换操作,在访问3前面,7是最远一次访问的,因此t比较大,所以要置换7。下一次要访问7时,也是这样子进行置换的。

    总结:LRU的实现需要硬件支持,其性能最接近最佳页面置换算法,但是该算法实现困难,开销大

    时钟置换算法(CLOCK)

    简介:是一种性能和开销相对均衡的算法。也被称为最近未使用算法(Not Recenty Use,NRE)。

    思想:简单的CLOCK算法为页面设置一个访问位,再将内存中的页面通过链接指针链接成一个循环队列。当某页被访问的时候,其访问位置设置为1。当淘汰一个页面的时候,只需要检查页的访问位如果是0,就选择将该页换出(之前没被访问过);如果是1,则将其置换为0,暂时不换出(上次访问过,可能还会继续访问)。然后接着检查下一个页面,如果第一轮扫描结束后,所以的页面的访问位都是1,则会将这些页面全部置0,再进行第二次扫描(第二轮扫描中肯定有为0的页面)。因此,简单的CLOCK算法选择淘汰一个页面最多经过两轮扫描

    页号内存块号状态位访问位(1表示最近访问过,0表示没有)修改位外存地址

    例子:假设系统为某进程分配了五个内存块,并以下面的页面号为引用串:1,3,4,2,5,6,3,4,7

    首先五个内存块中分别放入了页面1,3,4,2,5,这时候循环队列如下,访问位都设置为1了:

    在这里插入图片描述

    想要放入6的时候,这时候内存满了,因此需要淘汰,经过一轮的遍历后,会将这五个页面的标志位修改位0,再从队头1的位置放入6,此时循环队列如下:

    在这里插入图片描述

    下一次访问3,则将3号页置为1,再下一次访问4再将4号页置为1,此时循环队列为:
    在这里插入图片描述

    最后访问7,只是7不在内存中,则遍历队列,先将3号页置为0,再将4号页置为0,遍历到2号页的时候,发现2号页的访问位为0,则将2号页换出,此时循环队列如下:

    在这里插入图片描述

    改进型的时钟置换算法

    ​ 简单的时钟置换算法仅考虑了一个页面是否被访问过。事实上,如果淘汰的页面是一些没有被修改过的页面,那么就不用执行I/O操作。只有被淘汰的页面被修改过时,才需要写回外存。


    思想:除了考虑一个页面最近是否被访问之外,操作系统还应考虑页面是否被修改过。在其它条件相同下,优先淘汰没有被修改过的页面,避免I/O操作。其中,修改位为0表示没有被修改过,修改位为1表示被修改过。


    算法规则: 假设用(访问位,修改位)的形式记录各个页面的状态。如(1,1)表示一个页面最近被访问过并修改过。

    首先还是将可能被置换的页面排成一个循环队列。

    第一轮:从当前位置开始扫描到第一个(0,0)的帧用于替换本轮扫描不修改任何标志位第一优先级:找一个既没有被标记也没有被修改过的页面

    第二轮:若第一轮扫描失败,则重新扫描,查找第一个(0, 1)的帧用于替换本轮将所有扫描的帧访问位设置为0第二优先级:找一个没有被标记但是被修改过的页面

    第三轮:若第二轮扫描失败,则重新扫描,查找第一个(1,0)的帧用于替换。本轮扫描不修改任何标志位第三优先级:找一个最近被访问过但是未被修改过的页面

    第四轮:若第三轮扫描失败,则重新扫描,查找第一个(1,1)的帧用于替换【第四优先级:找一个最近被访问过同样也被修改过的页面

    注:由于第二轮扫描的时候将访问位设置为0了,因此经过第三轮、第四轮扫描一定有一个帧被选中。因此改进的CLOCK置换算法选择一个淘汰页面最多会进行四次扫描

    展开全文
  • 页面置换算法 知识总览 最佳置换算法(OPT) 每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面,这样可以保证最低的缺页率。 跟开了上帝视角似的 是最优的情况(实际不可能达到,是无法实现...

    页面置换算法

    知识总览

    在这里插入图片描述

    最佳置换算法(OPT)

    每次选择淘汰的页面将是以后永不使用,或者在最长时间内不再被访问的页面, 这样可以保证最低的缺页率。
    跟开了上帝视角似的
    是最优的情况(实际不可能达到,是无法实现的

    在这里插入图片描述

    先进先出置换算法(FIFO)

    淘汰最先进入内存的页面。
    有Belady异常:当为进程分配的物理块增大时,可能出现缺页次数增多的反常现象。(也只有它会有这种异常)
    算法性能差。
    在这里插入图片描述

    最近最久未使用置换算法(LRU)

    每次淘汰的页面是最近最久未使用的页面
    需要专门的硬件支持算法性能好,但实现困难,开销大。
    它是最接近最佳置换算法的算法!
    在这里插入图片描述

    时钟置换算法(CLOCK)

    一种开销和性能较均衡的算法,也成为最近未用算法。
    换出最近没有被访问的(访问位为0)。若都被访问过,则转到谁谁访问位置为0再转。
    也就是说,当且仅当某个位置访问位为0且被转到,就被置换出去。
    在这里插入图片描述

    改进型的时钟置换算法

    考虑了修改页面的情况。
    在这里插入图片描述

    总结

    在这里插入图片描述

    展开全文
  • 一、页面置换算法 请求分页 存储管理与 基本分页 存储管理的主要区别: ①、在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存【操作系统要提供请求调页功能,将缺失页面从外存...
  • 页面置换算法 根据中国大学MOOC计算机操作系统(电子科技大学)而写. 如果自己要设计页面置换,要根据什么原则来设计?我们首先想到的是存储器的局部性原理(时间局部性、空间局部性) Page removed should be the ...
  • 简单时钟置换: 装入页面:当前页面置为一,指针下跳。 命中页面:命中页面置为一,指针不动。 寻找页面:扫过的页面将一置零,遇到第一个零,装入页面,指针下跳。 改进型时钟替换算法: 1:找(0,0) 2:找(0,1...
  • 文章目录前言知识总览最佳置换算法(OPT)先进先出置换算法(FIFO)最近最久未使用置换算法(LRU)时钟置换算法(CLOCK)改进型的时钟置换算法知识回顾与重要考点 前言 此篇文章是我在B站学习时所做的笔记,大部分图片...
  • 时钟置换算法---CLOCK5.改造型时钟置换算法 0.思维导图 1.最佳置换算法—OPT 2.先进先出置换算法—FIFO 3.最近最久未使用置换算法—LRU 4.时钟置换算法—CLOCK 5.改造型时钟置换算法 只需一轮: 需要...
  • 整个过程,都是使用数组来实现每个算法,模拟队列,模拟堆栈的功能,实现每一个置换算法。 页面置换算法 最佳置换算法(OPT):选择永不使用或是在最长时间内不再被访问(即距现在最长时间才会被访问)的页面淘汰出...
  • 操作系统时钟(CLOCK)置换算法

    万次阅读 多人点赞 2020-01-14 20:08:44
    时钟(CLOCK)置换算法流程 注意:红色为访问位,蓝色为内存数据 箭头处开始 第一步: 第一个页面走向为3,此时内存中没有数据,且访问位为0,于是将3放入内存,并修改访问位为1,指针下移,得到如下图 ...
  • 时钟页面置换算法

    千次阅读 2019-10-08 22:07:02
    Clock页面置换算法,LRU的近似,对FIFO的一种改进; 基本思路: 需要用到页表项当中的访问位,当一个页面被装入内存时,把该位初始化为0,然后如果这个页面被访问(读/写),则把该位置为1; 把各个页面组织成环形...
  • Clock页面置换算法; 6)动态给出页面调用序列并进行调度; 7)输出置换结.C++编程要?考试用 哪位大侠 帮帮 快点 谢谢了这很简单啊,要打字太多了。不过网上这类算法举例很少,就看你怎么理解了。改良后的Clock算法 ...
  • 时钟(CLOCK)置换算法

    万次阅读 多人点赞 2018-12-28 21:44:19
    用于选择淘汰页面的算法称为页面置换算法置换算法的好坏,将直接影响到请求分页系统的性能。 FIFO置换算法和LRU置换算法的思想都比较容易理解,页面置换的推导也是简单的。但是CLOCK置换算法比较难从书上获取准确...
  • 进程页面的时钟(CLOCK)置换算法

    千次阅读 2020-04-26 23:27:12
    时钟置换算法运作过程如下: 假设 此时使用位情况:0-1,1-1; 指针位置:0(初始化假设) 开始,0块使用位为1,不可置换,但是这次把它的使用位变为0,以免一直是1发生死循环。又假设指针顺时针转动,...
  • 工作集时钟页面置换算法

    千次阅读 2019-06-22 08:44:49
    工作集时钟页面置换算法是在工作集和时钟算法的基础上改进的,所以先看看什么是时钟算法: Clock置换算法 LRU算法的性能接近于OPT,但是实现起来比较困难,且开销大;FIFO算法实现简单,但性能差。所以操作系统的...
  • CLOCK置换算法: 是一种LRU的近似算法,是一种性能和开销较均衡的算法。由于LRU算法需要较多的硬件支持,采用CLOCK置换算法只需相对较少的硬件支持。又称为最近未用算法(NRU) 简单的CLOCK置换算法 1.实现方法:...
  • 请问时钟置换算法中的访问位和修改位。 访问位是有页面访问就置为1吗?后面指针的每次访问就替换一次访问位的值吗? 修改位中的修改是什么原因引起的呢?
  • 理解算法才能实现算法,要不然就和我一样无从下手,抓破头皮也没用!!!LRU算法:http://flychao88.iteye.com/blog/1977653import java.util.*;import java.io.*;public class Main{public static void main(String...
  • 4. 时钟置换算法—CLOCK 5. 改造型时钟置换算法 6. 知识回顾与重要考点 0. 知识总览 1. 最佳置换算法(OPT) 2. 先进先出置换算法—FIFO 3. 最近最久未使用置换算法—LRU 4. 时钟置换算法—CLOCK 5. 改造...
  • 如题,我在想一个页面被修改了肯定也被访问了吧 那么u=0,m=1的页面是怎么回事?求指点
  • [操作系统] 页面置换算法(一)

    千次阅读 2017-12-02 17:44:58
    页面置换算法(一) 最优页面置换算法 最近未使用页面置换算法 先进先出置换算法 第二次机会页面置换算法 时钟页面置换算法 最近最少使用页面置换算法 LRU
  • 指针一开始在第0页,每进来一个页指针就向下移动1次且该页标星,内存中已有的页若能满足所需要的,则为内存中对应页重新标星,若内存页满了却不能满足需求,则指针将所指页所标星号清除,并且向下移动1次(循环),...
  • 一个页面置换算法性能比较程序,包括了最佳置换,先进先出,LRU,随机置换,简单时钟和改进时钟六个算法。使用了队列,链表,循环链表等数据结构。随机产生请求页号,计算六种算法的缺页率。
  • 页面置换算法-CLOCK置换算法及其改进版算法

    万次阅读 多人点赞 2018-12-29 13:31:51
    本文主要介绍页面置换算法中的CLOCK置换算法。页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。 1...
  • 功能:置换算法是指当出现缺页异常时,需要调入新页面而内存已满时,置换算法选择被置换的物理页面。 设计目标: 尽可能减少页面的调入调出次数; 把未来不再访问或短期内不访问的页面调出。 页面锁定: 了解...
  • 例如、最优页面置换算法、先进先出算法、最近最久未使用算法、时钟页面置换算法、二次机会法等。 目录 一、最优页面置换算法 二、先进先出算法(FIFO) 三、最近最久未使用方法(LRU) 四、时钟页面置换算法。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,971
精华内容 1,988
关键字:

时钟置换算法

友情链接: tupian.rar