clock置换算法

⑴ 页面置换算法的常见的置换算法

最简单的页面置换算法是先入先出（FIFO）法。这种算法的实质是，总是选择在主存中停留时间最长（即最老）的一页置换，即先进入内存的页，先退出内存。理由是：最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。建立一个FIFO队列，收容所有在内存中的页。被置换页面总是在队列头上进行。当一个页面被放入内存时，就把它插在队尾上。
这种算法只是在按线性顺序访问地址空间 时才是理想的，否则效率不高。因为那些常被访问的页，往往在主存中也停留得最久，结果它们因变“老”而不得不被置换出去。
FIFO的另一个缺点是，它有一种异常现象，即在增加存储块的情况下，反而使缺页中断率增加了。当然，导致这种异常现象的页面走向实际上是很少见的。
FIFO算法和OPT算法之间的主要差别是，FIFO算法利用页面进入内存后的时间长短作为置换依据，而OPT算法的依据是将来使用页面的时间。如果以最近的过去作为不久将来的近似，那么就可以把过去最长一段时间里不曾被使用的页面置换掉。它的实质是，当需要置换一页时，选择在之前一段时间里最久没有使用过的页面予以置换。这种算法就称为最久未使用算法（Least Recently Used，LRU）。
LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。
LRU算法是经常采用的页面置换算法，并被认为是相当好的，但是存在如何实现它的问题。LRU算法需要实际硬件的支持。其问题是怎么确定最后使用时间的顺序，对此有两种可行的办法：
1.计数器。最简单的情况是使每个页表项对应一个使用时间字段，并给CPU增加一个逻辑时钟或计数器。每次存储访问，该时钟都加1。每当访问一个页面时，时钟寄存器的内容就被复制到相应页表项的使用时间字段中。这样我们就可以始终保留着每个页面最后访问的“时间”。在置换页面时，选择该时间值最小的页面。这样做， 不仅要查页表，而且当页表改变时（因CPU调度）要 维护这个页表中的时间，还要考虑到时钟值溢出的问题。
2.栈。用一个栈保留页号。每当访问一个页面时，就把它从栈中取出放在栈顶上。这样一来，栈顶总是放有目前使用最多的页，而栈底放着目前最少使用的页。由于要从栈的中间移走一项，所以要用具有头尾指针的双向链连起来。在最坏的情况下，移走一页并把它放在栈顶上需要改动6个指针。每次修改都要有开销，但需要置换哪个页面却可直接得到，用不着查找，因为尾指针指向栈底，其中有被置换页。
因实现LRU算法必须有大量硬件支持，还需要一定的软件开销。所以实际实现的都是一种简单有效的LRU近似算法。
一种LRU近似算法是最近未使用算法（Not Recently Used，NUR）。它在存储分块表的每一表项中增加一个引用位，操作系统定期地将它们置为0。当某一页被访问时，由硬件将该位置1。过一段时间后，通过检查这些位可以确定哪些页使用过，哪些页自上次置0后还未使用过。就可把该位是0的页淘汰出去，因为在之前最近一段时间里它未被访问过。
4）Clock置换算法（LRU算法的近似实现）
5）最少使用（LFU）置换算法
在采用最少使用置换算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在之前时期使用最少的页面作为淘汰页。由于存储器具有较高的访问速度，例如100 ns，在1 ms时间内可能对某页面连续访 问成千上万次，因此，通常不能直接利用计数器来记录某页被访问的次数，而是采用移位寄存器方式。每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间(例如100 ns)右移一次。这样，在最近一段时间使用最少的页面将是∑Ri最小的页。
LFU置换算法的页面访问图与LRU置换算法的访问图完全相同；或者说，利用这样一套硬件既可实现LRU算法，又可实现LFU算法。应该指出，LFU算法并不能真正反映出页面的使用情况，因为在每一时间间隔内，只是用寄存器的一位来记录页的使用情况，因此，访问一次和访问10 000次是等效的。
6）工作集算法
7）工作集时钟算法
8）老化算法（非常类似LRU的有效算法）
9）NRU(最近未使用）算法
10）第二次机会算法
第二次机会算法的基本思想是与FIFO相同的，但是有所改进，避免把经常使用的页面置换出去。当选择置换页面时，检查它的访问位。如果是 0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的访问位总保持为1，它就从来不会被淘汰出去。
第二次机会算法可视为一个环形队列。用一个指针指示哪一页是下面要淘汰的。当需要一个 存储块时，指针就前进，直至找到访问位是0的页。随着指针的前进，把访问位就清为0。在最坏的情况下，所有的访问位都是1，指针要通过整个队列一周，每个页都给第二次机会。这时就退化成FIFO算法了。

⑵ 页面访问序列怎么求

一般采用以下几种算法
1、最佳置换算法
2、先进先出置换算法
3、最近最久未使用置换算法
4、改进型Clock置换算法
5、页面缓冲置换算法
例如
已知页面大小为100，则可分成第1页：0-100，第2页：100-200.。。。第5页：400-500
根据已知进程访问序列，可知10在第1页内，11在第1页内，以此类推得出页面访问序列：
1,1,2,2,1,4，2,3,3,5,5,4
页面访问的序列串是一个整数序列，需要我们编写函数生成，要求整数的取值范围为0-N-1。页面访问序列串中的每个元素p表示对页面p的一次访问。1.确定虚拟内存的尺寸N，工作集的起始位置p，工作集中包含的页数e，工作集移动率m（每处理m个页面访问则将起始位置p +1），以及一个范围在0和1之间的值t；2.生成m个取值范围在p和p + e间的随机数，并记录到页面访问序列串中； 3.生成一个随机数r，0 ≤ r ≤ 1；4.如果r < t，则为p生成一个新值，否则p = (p + 1) mod N； 5.如果想继续加大页面访问序列串的长度，请返回第2步，否则结束。

⑶ 谁能给个详细的clock置换算法

教材是王道。说白了就是如果访问位是1就置零，继续扫，如果是零就换出。改进的需要考虑修改位

⑷ nru算法----改进型"clock"算法

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。

3）如果第2）步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。
改进型的 CLOCK算法优于简单CLOC算法之处在于替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。

⑸ 进程/作业/页面调度算法

进程已获得除CPU之外的所有必须资源,只等待操作系统利用CPU调度算法将CPU分配给该进程以便执行。

进程等待某一特定事件的出现。如[I/O操作,在该过程中,进程依旧位于内存内,且占有CPU资源。

（1）静态优先数法：
一开始创建的时候就确定他的优先数，并在运行时保持不变。确定优先数时可以让外设的进程优先，或者操作时间长的优先....

（2）动态优先数法：
克服无法修改优先数的问题。CPU占用时间过长优先数下降，进程等待时间过长，优先数提高。

时间片太短切换开销太大不划算，太长又变成了FCFS。

引入多个就绪队列，在时间片轮转基础上改进

最高优先级队列运行一个时间片，次高两个，低优先级四个。当该进程用完所分配时间片仍未执行完时，需要调入下一级队列，下一级队列只有在上一级队列为空时才有机会执行。如果进程执行时有新进程进入上级优先级渣燃返的队列，则会中断该进程并放入原队列的队尾然后执行新进程。

非抢占式的先来先服务（First Come First Severd, FCFS）算法了。

顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。

最短作业优先（Shortest Job First, SJF）调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。

每次进行进程调度时，先计算“响应比优先级”，然后把“响应比优先级”最高的进程投入运行，“响应比优先级”的计算公式：

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。

时间片的长度就是一个很关键的点：

如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；如果设得太长又可能引起对短作业进程的响应时间变长。

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；

动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

（1）非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
（2）抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；

新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，段谈以此类推，直至完成；

当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。

对于短作业可能可以在第一级队列很快被处理完。对于长作如饥业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。

算法思想：每次选择淘汰的页面是最早进入内存的页面。

该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4

算法思想：每次淘汰的页面是最近最久未使用的页面。

实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。

最佳置换算法性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销均平衡的算法。又称CLOCK算法，或最近未用算法（NRU，Not Recently Used）

简单CLOCK算法算法思想：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描）。

除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。

改进型时钟置换算法的算法思想：在其他在条件相同时，应该优先淘汰没有被修改过的页面，从而来避免I/O操作。

⑹ 操作系统CLOCK置换算法的题目，急求解！！

因为一个目录文件最多可以由4个磁盘块组成，读目录和下级目录的时候，在最好的情况下，总能在第一个磁盘块上就能找到所需的下级目录信息，所以ADKQ四个目录读四次就可以了，此后是读文件，理想情况下所需页面可以通过前10个索引直接找到，此时只需再读一次就能读到所需页了，结果最少共用5次

最坏情况下，每个目录都存放在4个磁盘块的最后一个上，因此每个目录都得读四次，一共4*4=16次，而找到文件后，所需页面又得通过2级索引去找，这样一来2级索引表读一次，1级索引表又读一次，页面本身内容再读一次，又需2+1=3次，所以最坏情况就是16+3=19次

⑺ 对于问题小孩这门课所学所识有什么启发

我做了这么多年幼师，一直在想幼儿园的小孩是否全部都是天真快乐呢？是否全部都能友好相处呢？这些问题一直萦绕在我的心中，直到我读了《幼儿园里的“问题小孩”》,我这个疑惑的云朵才被拨开。

对于《幼儿园里的“问题小孩”》这一本书的总体评价，我认为这是一本基于作者理论学养于实践经验的原创之作，站在一个幼师的角度，我认为要以身作则，去在现实中发现书中存在的“问题”小孩，学会更多的专业知识去辅导孩子的心理，引导他们积极向上，懂得生活的美好。

在书中，论述围绕幼儿园课程的课程价值，分析了幼儿园教学内容有别于其他阶段的特质，从课程与教学的视角，澄清了长期以来幼儿园教育设计中诸多群体性、无意识的错误做法。语言浅白通俗又不失学理思考，虽脱胎于日常的授课讲义，又从读者的阅读心理出发设计了灵动的阅读结构，为职前、职后的幼儿园教师提供了有价值的学习与指导。

书中描述的一个很典型的现象就是幼儿的“隐蔽性”说谎，是指幼儿在特定环境下因为某种原因而隐蔽地说谎，这对刚处在萌芽阶段的幼儿有很不利的影响。由于幼儿“心灵的纯洁”，他们在真实的伪装下说谎时，往往会显得很不自然，对他们心灵的摧残也是显而易见的，因此，教导幼儿学会真诚，多和幼儿熟悉，多听他们的心事，也是我读完这本书的一个很大的感悟。

书中描述的幼儿园中存在的问题小孩主要有下面这八个问题：磨蹭、倔强、叛逆、暴力、吹牛、撒谎、孤僻，这些都是一个人成长中起阻碍的消极面，书中主要描写了从行为规范、心理健康、培养个性、解决叛逆等问题入手，以幼儿园和家长的双角度去更好地描述这本书的主题思想，带给普世大众对幼儿园教育中的解决。其中，书中展现的“榜样模范”也是让我记忆尤深的，一个好的集体需要好的带领人，在幼儿中建立榜样模范，可以让幼儿培养良好的习惯，汲取优秀的品质从而培养真诚善良的性格，良好的学习升高习惯，有益于幼儿集体的发展。

总之，幼儿园里的孩子作为稚嫩的花朵，必然需要社会上人们的关怀，作为幼儿园老师和家长，我们要学会用爱去鼓励孩子，去呵护每一个娇嫩的花朵，使他们寻回自信和坚强，让他们能以更好的姿态去迎接生活中的困难，去呵护每一个幼儿园孩子，培养他们优良的品格，成为国家未来的中流砥柱.

⑻ 实现虚拟存储器最常用的算法是哪个

页式虚拟存储器的页面置换算法一般有：
最佳置换算法（OPT），先进先出置换算法（FIFO），最近最久未使用置换算法（LRU），Clock置换算法，最少使用置换算法（拆困LFU），页面缓存算法（PBA）等。
先进先出（FIFO）置换算法是最直观的置换算法，由于它可能是性能最差的算法，故实际应携简用极少。（摘录自汤旅隐念的教材）

⑼ 计算机操作系统中页面置换的三种方式

常见的置换算法有：
1．最佳置换算法（OPT）（理想置换算法）
2．先进先出置换算法（FIFO）：
3．最近最久未使用（LRU）算法
4．Clock置换算法改御（LRU算法的近似实现坦陪）核信岩
5．最少使用（LFU）置换算法
6．工作集算法
7 . 工作集时钟算法
8. 老化算法（非常类似LRU的有效算法）
9. NRU(最近未使用）算法
10. 第二次机会算法

⑽ C++编程，clock置换算法

#include<iostream>
#include<stdlib.h>
#include<time.h>
#define N 20 //虚拟内存尺寸
using namespace std;

int P;
int const blockCount=3 ;//内存中的物理块数
int count = 0;
int block[blockCount];
int const PageCount=15;//总的页面数
int Page[PageCount];
int state[blockCount];//clock置换算法中，内存中的每个页面号对应的状态
int state2[blockCount][2];// 二维数组，第一行第一列为访问位，第一行的第二列为修改位
double lost= 0.0;

void generate_list(int *list,int e,int m,int t)
{
int i,j=0,q=P,r;
srand((unsigned)time(NULL));
while(j<e)
{
for(i=j;i<j+m;i++)
{
if(i==e)
break;
list[i]=(q+rand()%e)%N; //保证在虚拟内存的页号内
}
j=i;
r=rand()%100;
if(r<t)
q=rand()%N;
else
q=(q+1)%N;
}
}

//随机生产是否被修改的情况，prop(0……100),prop/100的概率为被修改
void generate_modify(int *mo,int e,int prop)
{
int i,t;
for(i=0;i<e;i++)
{
t=rand()%100;
if(t>prop)
mo[i]=0;
else
mo[i]=1;
}
}

//检测页号是否在内存中
bool inblock(int num)
{
for(int i=0; i<blockCount;i++)
{
if(block[i] == Page[num])
{
state[i] = 1;
return true;
}
}
return false;
}

//判断页面是否已经被修改
bool change()
{
if((rand()%2+1) == 1 )
{
printf("该页面被修改!\n");
return true;
}
else
return false;
}

//用于改进型clock置换算法，检测页号是否在内存中并把访问位和修改位置1
bool inblock2(int num)
{
for(int i=0;i<blockCount;i++){
if(block[i] == Page[num]){
if(change()){
state2[i][0] = 1;
state2[i][1] = 1;
}
else{
state2[i][0] = 1;
}
return true;
}
}
return false;
}

//用于改进型clock置换算法，判断内存中第几个需要被置换
int whichpage(){

int j;

for(j=0;j<blockCount;j++)
{
if(state2[j][0] == 0&&state2[j][1] == 0)
{
return j;
}
}
for(j=0;j<blockCount;j++ )
{
if(state2[j][0] == 0&&state2[j][1] == 1)
{
return j;
}
state2[j][0] = 0 ;
}
for(j=0;j<blockCount;j++ )
{
state2[j][0] =0 ;
}
return whichpage();
}

//简单Clock置换算法
void CLOCK(int num)
{
int j;

if(inblock(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block [i]);
}
else
if(count == blockCount)
{
//lost++;
for(j=0;j<blockCount; )
{
if(state[j] == 0)
{
break;
}
else{
state[j] = 0;
}
j++;
j = j%3;
}
block[j] = Page[num];
state[j] = 1;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block[i]);
}
}

//改进型clock置换算法
void LCLOCK(int num)
{
int j;

if(inblock2(num))
{
printf("命中!\n");
lost++;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block[i]);
}
else
if(count == blockCount)
{
//lost++;
j = whichpage();
block[j] = Page[num];
state2[j][0] = 1;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block[i]);
}
else{
block[count] = Page[num];
count++;
for(int i=0;i<blockCount;i++)
printf("物理块%d#中内容:%d\n",i,block[i]);
}
}

int main()
{
int a[N];
int mo[N];
int A=10;
int e,m,prop,t,j;
printf("页面走向为：");
generate_list(a, e,m,t);
generate_modify(mo,e,prop);

for(int i = 0;i<PageCount;i++)
{

Page[i] =rand()%9 + 1;
printf("%d ",Page[i]);
}
char ch ;
printf("\n");
printf("\t\t1 Clock置换算法\n");
printf("\t\t2 改进型Clock置换算法\n");
printf("\t\t3 退出!\n\n");
printf("请输入算法序号:\t\n");
while(1){
scanf("%c",&ch);
switch(ch){
case '1':{
lost=0;
count=0;
for(int m=0;m<blockCount;m++)
{
state[m] = 0;
}
for(int j=0;j<blockCount;j++)
{
block[j]=0;
}
for(int i=0;i<PageCount;i++)
{
printf("读入Page[%d]\n",i);
CLOCK(i);
}
printf("页面访问次数: %d\n缺页次数: %0.lf\n",PageCount,PageCount-lost);
printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n请输入算法序号:\t");
}break;
case '2':{
lost = 0;
count = 0;
for(int m = 0; m < blockCount; m++)
{
for(int n = 0; n < 2;n++)
state2[m][n] = 0;
}
for(int j = 0; j < blockCount; j++)
{
block[j] = 0;
}
for(int i = 0; i < PageCount; i++)
{
printf("读入Page[%d]\n",i);
LCLOCK(i);
}
printf("页面访问次数: %d\n缺页次数: %0.lf\n",PageCount,PageCount-lost);
printf("缺页率为:%0.001f\n",(PageCount-lost)/PageCount);
printf("\n请输入算法序号:\t");
}break;
case '3':{
exit(0);
}
}
}
return 0;
}