clock算法和请求分页EAT计算

时钟置换算法（CLOCK）例题：一个作业的物理块数为3，此作业的页面走向为：内存及控制信息输入串指针移动情况及帧替换信息是否缺页？内存访问位指针3内存中没有3，需要找到一个帧放入3，指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移√0←内存访问位指针4内存中没有4，需要找到一个帧放入4，指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移√310←内存访问位指针2内存中没有2，需要找到一个帧放入2，指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移√31410←内存访问位指针6内存中没有6，需要找到一个帧放入6，指针所指的位置的访问位为1，将其变成0，再下移√31←4121内存访问位指针指针所指的位置的访问位仍为1，将其变成0，再下移3041←21内存访问位指针指针所指的位置的访问位仍为1，将其变成0，再下移（回到开头）304021←内存访问位指针指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移30←4020内存访问位指针4内存中有4，于是4所在帧的访问位变为1，指针下移×6140←20内存访问位指针3内存中没有3，需要找到一个帧放入3，指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移√614120←内存访问位指针7内存中没有7，需要找到一个帧放入7，指针所指的位置的访问位为1，将其变成0，再下移√61←41 31内存访问位指针指针所指的位置的访问位仍为1，将其变成0，再下移6041←31内存访问位指针指针所指的位置的访问位仍为1，将其变成0，再下移（回到开头）604031←内存访问位指针指针所指的位置恰好有访问位为0的，于是就淘汰这个帧，指针下移60←4030内存访问位指针4内存中有4，于是4所在帧的访问位变为1，指针下移×7140←30内存访问位指针3内存中有3，于是3所在帧的访问位变为1，指针下移（回到开头）×71 41。

常用的页面调度算法一、引言在计算机科学中，页面调度算法是操作系统中的一种重要机制，用于管理计算机内存中的页面。

页面调度算法的目标是尽可能地提高内存的利用率，减少页面置换的次数，从而提高系统的性能和响应速度。

常用的页面调度算法有先进先出（FIFO）、最近最久未使用（LRU）和时钟（Clock）算法等。

本文将介绍这些常用的页面调度算法，并分析它们的优缺点及适用场景。

二、先进先出（FIFO）算法先进先出算法是最简单的页面调度算法之一。

它的原理是将最早进入内存的页面置换出去，即先进先出。

当内存空间不足时，操作系统将最早进入内存的页面替换出去，腾出空间给新的页面。

这种算法简单易实现，但是它没有考虑页面的使用频率和重要性，可能导致常用的页面被频繁替换，影响系统的性能。

三、最近最久未使用（LRU）算法最近最久未使用算法是一种常用的页面调度算法。

它的原理是根据页面的使用情况来进行页面置换。

当需要替换页面时，操作系统选择最近最久未使用的页面进行置换。

这种算法考虑了页面的使用频率，可以有效地提高内存的利用率。

然而，LRU算法的实现比较复杂，需要维护一个页面访问的时间戳列表，当页面被访问时，需要更新时间戳列表，这会带来额外的开销。

四、时钟（Clock）算法时钟算法是一种简化的页面调度算法，它是基于LRU算法的改进。

时钟算法使用一个循环链表来保存内存中的页面，并维护一个指针指向当前页面。

当需要替换页面时，时钟算法从当前页面开始顺时针扫描链表，找到一个未被访问的页面进行置换。

如果当前页面已被访问，则将访问位清零，并将指针指向下一个页面。

这种算法简化了LRU算法的实现，并且可以在O(1)的时间内完成页面置换操作。

五、比较和总结先进先出算法简单易实现，但没有考虑页面的使用频率和重要性；最近最久未使用算法考虑了页面的使用频率，可以提高内存的利用率，但实现较复杂；时钟算法是一种简化的LRU算法，可以在O(1)的时间内完成页面置换操作。

时钟(CLOCK)置换算法L RU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。

当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。

对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。

当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。

当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。

每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。

由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。

在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。

这样，每一帧都处于以下四种情况之一：1.最近未被访问，也未被修改(u=0, m=0)。

2.最近被访问，但未被修改(u=1, m=0)。

3.最近未被访问，但被修改(u=0, m=1)。

4.最近被访问，被修改(u=1, m=1)。

算法执行如下操作步骤：1.从指针的当前位置开始，扫描帧缓冲区。

在这次扫描过程中，对使用位不做任何修改。

选择遇到的第一个帧(u=0, m=0)用于替换。

2.如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。

选择遇到的第一个这样的帧用于替换。

在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。

四、应用题（每小题8分，共40分）1．在一单道批处理系统中，一组作业的提交时间和运行时间见下表所示。

作业提交时间运行时间1 8.0 1.02 8.5 0.53 9.0 0.24 9.1 0.1计算以下二种作业调度算法的平均周转时间T和平均带权周转时间W。

先来先服务调度算法。

（2）短作业优先调度算法。

2．考虑某个系统在某时刻的状态如下表所示。

Allocation Max AvailableＡＢＣＤＡＢＣＤ１５２０P0 ００１２００１２P1 １０００１７５０P2 １３５４２３５６P3 ００１４０６５６使用银行家算法回答下面的问题：（1）求Need矩阵。

（2）系统是否处于安全状态？如安全，请给出一个安全序列。

（3）如果进程P1发来一个请求（0，4，2，0），这个请求能否立刻被满足？如安全，请给出一个安全序列。

(2) 安全，安全序例为：P0，P2，P1，P3……（3分）（3）能立刻被满足，满足的安全序列为：P0，P2，P1，P3……（3分）3．桌子上有一只盘子，每次只能向其中放入一只水果。

爸爸专向盘子中放苹果，妈妈专向盘子中放桔子，儿子专等吃盘子中的桔子，女儿专等吃盘子中的苹果。

只有盘子为空时，爸爸或妈妈就可向盘子中放一只水果；仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

用信号量机制解决该问题。

答:在本题中，应设置三个信号量S、So、Sa，信号量S表示盘子是否为空，其初值为l；信号量So表示盘中是否有桔子，其初值为0；信号量Sa表示盘中是否有苹果，其初值为0。

(2分)father(){ 。

while(1) { 。

P(S); 。

放苹果。

V(Sa); 。

}} 。

mather(){。

while(1) { 。

P(S); 。

放苹果。

V(So);。

}} 。

son(){ 。

while(1) { 。

P(So); 。

从盘中取出桔子; 。

V(S); 。

吃桔子; 。

｝。

} 。

daughter(){ 。

while(1) { 。

实验四页面置换算法一、实验目的本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。

学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。

二、实验要求基本要求：描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。

1）初始化：输入作业可占用的总页框数，初始化置空。

2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用；3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。

4）显示当前分配淘汰序列：显示淘汰的页号序列。

描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。

三、实验内容1)基本原理时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面，如图所示。

当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。

2)算法流程设计主函数流程:STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列STEP2:内存页面初始化。

内存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。

开始时页号均为-1，访问位为0.STEP3：测试数据。

具体算法是依要访问的页面号，调用find()函数查找是否已经存在于内存中。

若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tihuan()函数。

最后，打印当前内存状态。

如此循环直至测试串都访问完毕。

3)主要函数实现a)Makenode(double)函数：用于初始化一个节点。

b)Find（double）函数：依据输入的页号，查询内存中是否已存在此页面。

若存在返回值1，不存在返回值0.c)Tihuan（double）函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指针扫过的页面访问位置0，新加入的页面访问位置1。

页面置换算法之Clock算法1.前言缓冲池是数据库最终的概念，数据库可以将一部分数据页放在内存中形成缓冲池，当需要一个数据页时，首先检查内存中的缓冲池是否有这个页面，如果有则直接命中返回，没有则从磁盘中读取这一页，然后缓存到内存并返回。

但是内存的价值较高，一般来说服务器的内存总是小于磁盘大小的，而且内存不能完全分配给数据库作为缓冲池。

这就意味着数据库基本上无法将所有的数据都缓冲到内存中。

当缓冲池满后，如果还有新的页面要被缓冲到池中，就要设计一种页面置换的算法，将一个旧的页面替换成新的页面。

一般来说我们熟悉的算法有下面几种：下面逐一介绍各种算法。

2. 最佳置换算法如果被替换掉的页是以后再也不会使用的，那么这种算法无疑是最优秀的。

因为不管什么算法，替换掉的页也有可能再次被缓存，替换掉其它的页。

但是这种算法是无法实现的，我们不可能知道哪个页面以后也在不会被使用。

或者我们退一步，将这个算法改成被替换掉的页是以后很长一段时间都不会再次被使用的，那么这种算法无疑也是最优秀的。

但是还是会面对一个无法实现的问题，我们还是不知道哪些页面会在未来多长一段时间内不会被再次访问。

页面无法确认，时间也无法确定。

虽然这种算法无法被实现，但是可以作为一种度量，如果有一种算法其效率最接近OPT，那么这种算法无疑是优秀的算法。

3. 先进先出算法先进先出算法是一种很简单的算法，其基本思想是形成一个队列，最先入队的页面最先被逐出。

我们用示意图来模拟一下FIFO算法：我们的内存假设只能保存4个页面，此时的访问请求按照时间顺序是1->2->3->4->5，那么按照时间顺序，当访问到4号页面时队列正好填满，当要访问5号页面时，会将最先入队的1号页面逐出。

这种算法实现起来很简单，但是从实现上来看，性能和OPT算法差距最大。

因为被替换出去的页面很有可能是最常使用的页面，因此这个算法很少见出现在数据库缓冲池管理中的。

FIFO算法会出现一个叫做Belay异常的现象，就这个现象我们解释如下。

第5章虚拟存储器-填空题1.在请求调页系统中,地址变换过程可能会因为( )、( )和( )等原因而产生中断2.虚拟存储器的基本特征是( )和( ),因而决定了实现虚拟存储器的关键技术是( )和( )3.实现虚拟存储器,除了需要有一定容量的内存和相当容量的外存外,还需要有( )、( )和( )的硬件支持4.为实现请求分页管理;应在纯分页的页表基础上增加( )、( )、( )和( )等数据项。

5.在请求调页系统中要采用多种置换算法,其中OPT是( )置换算法,LRU是( )置换算法,NUR是( )置換算法,而LFU则是( )置换算法,PBA是( )算法。

6. VAX/VMS操作系统采用页面缓冲算法:它采用( )算法选择淘汰页,如果淘汰页未被修改,则将它所在的物理块插到( )链表中,否则便将其插入( )链表中,它的主要优点是可以大大减少( )次数7.在请求调页系统中,调页的策略有( )和( )两种方式。

8.在请求调页系统中,反复进行页面换进和换出的现象称为( ),它产生的原因主要是( )9.分页系统的内存保护通常有( )和( )两种措施。

10.分段系统中的越界检查是通过( )中存放的( )和逻地址中的( )的比较,以表项中的( )和逻辑地址中的( )的比较来实现的11.为实现段的共享,系统中应设置一张( ),每个被共享的段占其中的一个表项其中应包含了被共享段的段名、( )、( )和( )等数据项:另外,还在该表项中记录了共享该段的( )的情况12.在分段系统中常用的存储保护措施有( )、( )、( )三种方式13.在采用环保护机制时,一个程序可以访问驻留在( )环中的数据:可以调用駐留在( )环中的服务14. Intel x86 /Pentium系列CPU可采用( )和( )两种工作模式15. Intel x86 Pentium的分段机制,每个进程用于地址映射的段表也叫做( )，另外当进程运行在特权级别为0的核心态下时,它必须使用( )来进行地址映射16. Intel x86/Pentium的分页机制,采用( )级分页模式,其外层页表也叫做( )三、综合应用题1.请求分页管理系统中,假设某进程的页表内容如下表所示。

考研计算机学科专业基础综合-51(总分150,考试时间90分钟)一、单项选择题1. 6个元素以6、5、4、3、2、1的顺序进栈，下列不合法的出栈序列是______。

A. 5、4、3、6、1、2B. 4、5、3、1、2、6C. 3、4、6、5、2、1D. 2、3、4、1、5、62. 用链表方式存储的队列(有头尾指针非循环)，在进行删除运算时______。

A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改3. 一棵二叉树的前序遍历序列为1234567，它的中序遍历序列可能是______。

A. 3124567B. 1234567C. 4135627D. 21536474. 如图所示的二叉树是______。

A. 二叉判定树B. 二叉排序树C. 二叉平衡树D. .堆5. 含有20个结点的平衡二叉树的最大深度为______。

A. 4B. 5C. 6D. 76. 一个有n个顶点和n条边的无向图一定是______。

A. 连通的B. 不连通的C. 无环的D. 有环的7. 已知有向图G=(V，A)，其中V={a，b，c，d，e}，A={＜a，b＞，＜a，c＞，＜d，c＞，＜d，e＞，＜b，e＞，＜c，e＞}，对该图进行拓扑排序，下面序列中不是拓扑排序的是______。

A. a，d，c，b，eB. d，a，b，c，eC. a，b，d，c，eD. a，b，c，d，e8. 散列表的地址范围为0-17，散列函数为H(k)=kmod17。

采用线性探测法处理冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中。

元素59存放在散列表中的地址是______。

A. 8B. 9C. 10D. 119. 排序趟数与序列的原始状态有关的排序方法是______。

A. 插入排序B. 选择排序C. 冒泡排序D. 快速排序10. 对关键字序列{23，17，72，60，25，8，68，71，52}进行堆排序，输出两个最小关键字后的剩余堆是______。