首页 > 搜索 > 简单clock算法实例,clock置换算法

简单clock算法实例,clock置换算法

互联网 2020-10-28 02:11:58
在线算命,八字测算命理

本文主要介绍页面置换算法中的CLOCK置换算法。页面置换算法中的LRU算法最接近理想情况下的OPT算法,但是实现起来比较困难且开销较大,所以很多设计者试图用开销比较小的算法接近LRU算法,CLOCK算法就是其中一种。

1.简单的CLOCK算法是通过给每一个访问的页面关联一个附加位(reference bit),有些地方也叫做使用位(use bit)。他的主要思想是:当某一页装入主存时,将use bit置成1;如果该页之后又被访问到,使用位也还是标记成1。对于页面置换算法,候选的帧集合可以看成是一个循环缓冲区,并且有一个指针和缓冲区相关联。遇到页面替换时,指针指向缓冲区的下一帧。如果这页进入主存后发现没有空余的帧(frame),即所有页面的使用位均为1,那么这时候从指针开始循环一个缓冲区,将之前的使用位都清0,并且留在最初的位置上,换出该桢对应的页。

以下面这个页面置换过程为例,访问的页面依次是:1,2,3,4,1,2,5,1,2,3,4,5。主存有4个空闲的帧,每个页面对应的结构为(页面号,使用位)。

最开始页面号1进入主存,主存里面有空闲的帧,将其使用位记成1,由于主存中之前没有页面1,所以会发生缺页中断。同理随后的页面2,3,4进入主存,将其使用位记成1,发生缺页中断。当之后的页面1,2进入主存时,由于页面1,2已经在主存中,不做处理。当之后的页面5进入主存时,主存内没有空余的帧,这时候随着指针循环移动整个缓冲区,将之前页面的使用位全部清0,即这时候页面1,2,3,4对应的使用位全部为0,指针回到最初的位置,将页面1替换出去,页面5换入主存,同时使用位标记成1。以此类推,可知CLOCK共发生10次缺页中断。

 2.改进型的CLOCK算法

在之前的CLOCK算法上面除了使用位(used bit),还增加了一个修改位(modified bit),有些地方也叫做dirty bit。现在每一页有两个状态,分别是(使用位,修改位),可分为以下四种情况考虑:

(0,0):最近没有使用使用也没有修改,最佳状态!

(0,1):修改过但最近没有使用,将会被写

(1,0):使用过但没有被修改,下一轮将再次被用

(1,1):使用过也修改过,下一轮页面置换最后的选择

以下面这个页面置换过程为例:访问的页面依次是:0,1,3,6,2,4,5,2,5,0,3,1,2,5,4,1,0,其中红色数字表示将要修改的页面,即他们的modified bit将被设置成1,在下图中这些页面用斜体表示,使用位和修改位如下图所示。下面的"Fault ?"表示缺页时查找空闲frame的次数。

页面替换的顺序:

从指针当前的位置开始寻找主存中满足(使用位,修改位)为(0,0)的页面;如果第1步没有找到满足条件的,接着寻找状态为(0,1)页面;如果依然没有找到,指针回到最初的位置,将集合中所有页面的使用位设置成0。重复第1步,并且如果有必要,重复第2步,这样一定可以找到将要替换的页面。

以下面替换的流程为例: 

1.当页面0来时,Frame0空闲,所以换入页面0,修改状态为(1,0),同时发生缺页中断。

2.当访问页面1时,由于页面1,将要被修改,其状态设置为(1,1),同时发生缺页中断。

3.同理对于接下来的页面3,6,将其状态设置为(1,0),,同时发生缺页中断。

4.对于接下来的页面2,按照之前的页面置换算法的顺序,他现在主存中找状态为(0,0)的页面,发现没有....然后执行算法的第二步,找状态为(0,1)的页面,发现还是没有.....这时候把主存里面所有页面的used bit清零,再重复执行算法的第一步,此时由于页面0的状态已经变成(0,0),页面2把页面0替换出主存。同时由于在之前的设计中页面2属于将要被修改(modify)的页面,故将其状态设置为(1,1)。由于经历了两轮查找,所以"Fault ?"对应的查找次数为2*4+1=9。同理可类推访问其他页面的情况。最后可知缺页次数为13次。

 

欢迎指正~ 

参考资料:

http://courses.cs.tamu.edu/bart/cpsc410/Supplements/Slides/page-rep3.pdf

资料更新:

https://github.com/totororz/Examples-of-page-replacement-problems/blob/master/page-rep3.pdf

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多