Ⅰ 操作系统题：页面置换算法 OPT FIFO LRU
fifo就是先进先出，可以想象成队列
lru是最久未使用，当或厅需要替换页面的时候，向前面看，最久衫老隐没使用的那个被替换
opt是替换页面的时候，优先替换后面最含清迟出现的。
不懂再问。。
Ⅱ 试说明改进形clock页面置换算法的基本原理
这很简单啊，要打字太多了。不过网上这类算法举例很少，就看你怎么理解了。
改良后的Clock算法
考虑到如果某一调入内存的页没有被修改过，则不必将它拷回到磁盘。于是在改进的Clock增加了弊漏旅一个M位， M=0 表示该页未被修改过。这样我们选择页面换出时，既要最近未访问过的页面，又要未被修改过的页面。其执行过程分一下三步：
第一步：从开始位置循环扫描队列，寻找A=0、M=O的第一类面，找到立搜厅即置换。另外，第一次扫描期租凳间不改变访问位A。
第二步：如果第一步失败，则开始第二轮扫描，寻找A=0且M=1的第二类页面，找到后立即置换，并将所有扫描过的A都置0。
第三步：如果第二步也失败，则返回指针开始位置，然后重复第一步，必要时再重复第二步，此时必能找到淘汰页。
Ⅲ 内存扩充之虚拟存储技术
传统存储管理
特征
时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问（因为程序中存在大量循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元很有可能被访问（因为很多数据在内存中是连续存放的，并且程序的指令也是顺序地在内存中存放的
寄存器
高速缓存
内存
外存（如磁盘、磁带等）
越往上容量越小，访问速度越快，成本越高
越往下容量越大，访问速度越慢，成本越低
高速缓存技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中
快表机构就是将近期常访问的页表项副本放到更高速的cache中
基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
若内存空间不够，由操作系统将内存中暂时用不到的信息换出到外存
因此，在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充
虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的
虚拟内存的实际容量 = min(内存外存容量之和，CPU寻址范围)
虚拟内存有以下三个主要特征
虚拟内存技术，允许一个作业多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上
传统的非连续分配存储管理
基本分页存储管理
基本分段存储管理
基本段页式存储管理
虚拟内存的实现
请求分页存储管理
请求分段存储管理
请求段页式存储管理
主要区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
操作系统要提供请求调页/段功能、页面/段置换功能
请求分页存储管理和基本分页存储管理的主要区别
页表机制
页表项：内存块号、状态位、访问字段、修改位、外存地址，页号时隐含的
内存块号是页面在内存中对应的页框号，如果状态位为0，则内存块号为无
状态位表示是否已被调入内存
访问字段记录最近被访问过几次，或者上次访问时间，由此操作系统能够提供置换算法
修改位记录页面被调入内存后是否被修改过，如果没有，就不需要浪费时间写回外存
外存地址是页面在外存中的存放位置
缺页中断机构
在请求分页系统中，每当要访问的页面不在内存时，便会产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断（内中断）
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存，为修改过的页面不用写回外存
一条指令再执行期间可能产生多次缺页中断（ A to B）
新增的步骤
页面的换入、换出需要磁盘IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率
缺页中断≠页面置换
发生缺页中断会发生调页，只有内存块满了才发生页面置换
最佳置换算法OPT：每次淘汰以后永不使用或最长时间内不再被访问的页面
理想化的算法，很难实现
先进先出算法FIFO：每次淘汰最先进入内存的页面
实现：把调入内存的页面根据调入的先后顺序排成队列，页面置换时换出队头页面，新调入的页面排到队尾
优点：实现简单
缺点1：belady异常，为进程分配的物理块数增大时，缺页次数不减反增的异常现象。只有FIFO会产生belady异常。
缺点2：算法与进程实际运行时的规律不适应，因为先调入的页面有可能最经常被访问，因此算法性能差
最近最久未使用置换算法LRU：淘汰最近最久未使用的页面
实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t
优点：性能最接近OPT
缺点：实现困难、开销大
时钟置换算法CLOCK/NRU
简单NRU：为每一个页表项设置一个访问位，再将内存中的页面都通过连接指针连成一个循环队列，当某页被访问时，访问位为1，只需检查页的访问位。如果为0，就将该页换出，否则将其改为0，暂不换出，继续向后扫描，若第一轮扫描都是1，将这也页面的访问位改为0后，进行第二轮扫描，第二轮扫描中一定会有访问位为0的页面，将其换出。因此最多经过两轮扫描
改进NRU：如果淘汰的页面没有被修改过，就不需要执行IO操作，只有淘汰的页面被修改过时，才需要写回外存。因此，同时考虑最近有无访问和有无修改，在其他条件相同时，优先淘汰没有修改过的页面，避免IO操作
第一轮：找到第一个访问位和修改位都为0的页面进行替换，如果没有找到进行下一轮扫描
第二轮：查找第一个访问位为0，修改位为1的页面进行替换，本轮将所有被扫描过的访问位设置为0，如果没有进行下一轮扫描
第三轮：查找0，0替换否则下一轮
第四轮：查找0，1替换
最多会进行四轮扫描
驻留集：请求分页管理中给进程分配的物理块的集合
在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小
驻留集太小，导致缺页频繁，系统要花大量时间处理缺页，实际用于进程推进的时间很少
驻留集太大，会导致多道程序并发度下降，资源利用率降低
固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况作适当的增加或减少
局部置换：发生缺页时只能选进程自己的物理地址块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程
不存在固定分配全局置换的策略，因为全局置换意味着一个进程拥有的物理块数量必然改变
其他三种组合存在
固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，并且需要进行页面置换，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面
缺点：很难在刚开始就确定应为每个进程分配多少个物理地址块才算合理（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数
可变分配全局置换：刚开始会为进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块中取出一块分给该进程；若无空闲物理块，则选择一个未锁定的页面换出到外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页面可能是系统中任何一个进程的页面，因此这个被选中的进程拥有的物理块会减少，缺页率会增加
只要缺页就给该进程分配新的物理块
可变分配局部置换：刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行页面置换。如果进程在运行过程中频繁缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋于适当程度；反之，如果缺页率太低，就是当减少分配给该进程的内存块数
要根据发生缺页的频率来动态增加或减少进程的物理块
何时调入页面
从何处调入页面
对换区：读写速度更快，采用连续分配方式
文件区：读写速度更慢，采用离散分配方式
抖动/颠簸现象：刚刚换出的页面马上要换入内存，刚刚换入的页面马上要换出外存，这种频繁的页面调度行为称为抖动/颠簸
主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）
为进程分配物理块太少会使进程发生抖动现象，为进程分配的物理块太多会降低系统的并发度降低某些资源的利用率。因此提出了“工作集”的概念
工作集：在某段时间间隔里，进程实际访问页面的集合
驻留集：请求分页存储管理中给进程分配的内存块的集合
驻留集不能小于工作集，否则进程运行过程中将频繁缺页
Ⅳ 页面置换算法的常见的置换算法
最简单的页面置换算法是先入先出（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算法了。
Ⅳ 简单时钟置换算法（NLU）当不发生页面置换也就是命中时，循环队列中的扫描指针跟着命中的页移动不
在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一模旦个页面将其移出内存，以便为即将调入的页面让出空间。而用来选铅码氏择淘汰哪一页的规则叫做页面置换算法。槐散
Ⅵ 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;
}
Ⅶ 操作系统CLOCK置换算法的题目，急求解！！
因为一个目录文件最多可以由4个磁盘块组成，读目录和下级目录的时候，在最好的情况下，总能在第一个磁盘块上就能找到所需的下级目录信息，所以ADKQ四个目录读四次就可以了，此后差颂是读文件，理想情况下所需页面可以通过前10个索引直接找到，此时只需再读一次就虚核郑能读到所需页了，结果最少共用5次
最坏情况下，每个目录都存放在4个磁盘块的最后一个上，因此每个目录都得读四次，一共4*4=16次，而找到文件后，所需页面又得通过2级索引去找，这样一来2级索引表读一次，1级索引表又读一次，氏配页面本身内容再读一次，又需2+1=3次，所以最坏情况就是16+3=19次
Ⅷ 页面置换算法
上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
本文内容
算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此算法依次执行，最后的结果如下
结果图
注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。
算法思想：每次选择 淘汰的页面是最早进入内存的页面。
该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
分配三个内存块的情况：
分配四个内存块的情况：
当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。
算法思想： 每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面纯亏自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。
举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
这里先直接给出答案
结果图
最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均春裤配平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个扒指淘汰页面最多会经过 两轮扫描 ）。
这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。
简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
算法规则 ：将所有可能被置换的页面排成一个循环队列
由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。
假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图
如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。
某一时刻页面状态如下
如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。
某一时刻页面状态如下
第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图
某一时刻页面状态如下
具体的扫描过程和上面相同，这里只给出最后的结果，如下图
所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
(1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
(2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
(3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
(4) 第四优先级淘汰的是 最近访问且修改 的页面。
Ⅸ 12、存储模型2（操作系统笔记）
我们将虚拟存储技术和页式存储管理方案结合起来得到了虚拟页式存储管理系统。具体有两种方式，一是请求调页，二是预先调页。以 cpu 时间和磁盘换取昂贵内存空间，这是操作系统中的资源转换技术。
通常，页表项是硬件设计的。
为什么要锁定页面？
又称页面淘汰算法。最佳算法-->先进先出-->第二次机会-->时钟算法-->最近未使用-->最近最少使用-->最不经常使用-->老化算法-->工作集-->工作集时钟
在先进先出算法的基础上进行该机而来的，此算法按照先进先出算法选择某一页面，检查其访问位 R ，如果为 0 ，则置换该页；如果为 1 ，则给第二次机会，并将访问位置零，并将其从链头取下放到链尾。
在第二次机会算法中当给某个页面第二次机会的时候，将其访问位置零，然后将其挂到链尾，这都是需要开销的，于是我们改进为时钟算法。
选择最后一次访问时间距离当前时间最长的一页并置换，即置换未使用时间最长的一页。
即 Not frequently Used ，选择访问次数最少的页面置换
例子：
要求：
计算应用 FIFO、LRU、OPT 算法时的缺页次数
应用 FIFO、LRU 页面置换算法
应用OPT页面置换算法
例子：系统给某进程分配 m 个页框，初始为空页面访问顺序为
1 2 3 4 1 2 5 1 2 3 4 5 ，采用 FIFO 算法，计算当 m=3 和 m=4 时的缺页中断次数。
结论： m=3 时，缺页中断九次； m=4 时，缺页中断十次。注意： FIFO 页面置换算法会产生异常现象（ Belady 现象），即：当分配给进程的物理页面数增加时，缺页次数反而增加。
缺页越多，系统的性能越差，这称为颠簸（抖动）：虚存中，页面在内存与磁盘之间频繁调度，使得调度页面所需的时间比进程实际运行的时间还多，这样导致系统效率急剧下降，这种现象称为颠簸或抖动。
例子：
分配了一个页框，页面大小为 128 个整数，矩阵 A(128 x 128) 按行存放。
如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次数，这是由 Denning 提出的。