在程序运行过程中，如果程序尝试访问的页面不在内存中，则会发出缺页中断，中断处理程序首先保留CPU环境，然后转移到缺页中断处理程序。 检索页表，获取该页存储在外部的物理块后，如果内存不足，将缺少的页调用到内存中，修改页表。
如果内存已满，请根据某种替换算法从内存中选择一页进行更换； 如果页面未更改，则不需要将页面写回磁盘。 但是，如果页面改变，则将其写入磁盘，然后将缺少的页面调入内存，更改页面表中相应的表项，将存在的位设置为“1”，并将该页面表项设置为快速表
最佳置换(OPT)算法通过采用最佳的替换算法，可以将页面不足率降至最低，因为选择的已废弃页面将不再使用，并且可能在最长的时间内不再访问。 但是，由于无法预测哪个页面在今后最长时间内将不再访问，因此该算法无法实现；
先进先出（FIFO）算法选择并丢弃最先访问内存的页面，即最长时间驻留在内存中的页面。
根据最近最久未使用（LRU）算法页读入内存后的使用情况决定，选择最近最旧的页进行废弃； 该算法为各页面提供访问字段，记录上次访问页面后经过的时间t。 如果需要丢弃页，则选择并丢弃现有页中t值最大的页，即最早的未使用的页。
CLCOK算法又称为最近未使用算法（NUR）页设置访问位，当某个页面被访问时，它用链接指针将内存中的所有页面链接到循环队列中，其访问位置为1。 淘汰时，检查其访问位，如果为0则更换； 如果为1，则恢复为0。 按FIFO算法检查下一页，进入队列的最后一页时，如果访问位仍为1，则再次返回队列开头检查第一页。
1假设系统为某进程分配了四个物理块，页面使用走向为：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1，分别采用OPT算法，FIFO算法，LRU算法，给出页面的置换过程，以及各自发生了几次页面置换？
OPT:4次； FIFO:6次LRU:4次
2打开“Microsoft Visual C++ 6.0”，输入相关代码，根据代码注释把空缺的FIFO算法补充完毕，对程序行进编译运行。给出你所填写的FIFO算法代码：
bc[p%blockCount]=pc[i]； p；3根据提示输入上述相关数据，分别记录OPT算法、FIFO算法、LRU算法以及CLOCK算法运行结果：
(1) OPT算法：
)2) FIFO算法
)3) LRU算法
(4)时钟算法
————————————————————————————————————————————————————————————3 3354————————————————————————
附加源代码：
# includeiostreamusingnamespacestd； voidprint(intBC[]，int blockCount ) ) for ) intI=0； iblockCount； I ) {coutbc[i] '； }coutendl； }inttravel(intBC ()，int blockCount，int x ) {int index=-1； int i； for(I=0； iblockCount； I ) if(BC[I]==x ) {index=i； 黑； } }返回索引； }voidFIFO(intPC )、int bc[] )、int pageCount、int blockCount )、{cout'0:FIFO替换算法' endl； int i； 页面计数=块计数(if ) {cout页面缺失次数为'0endl； cout '缺失率为'0endl； }else{int noPage=0； int p=0； for(I=0； ipageCount； I ) {cout (引用页： ) PC[I]endl； if(travel(BC，blockCount，PC[I]==-1 ) ) {bc[i]=pc[i]； }else{bc[p%blockCount]=pc[i]； p； //页面不在内存中，丢弃第一个进入的页面。 }noPage； cout '物理块时为： '； 打印(BC，blockCount )； }coutendl； }cout '的缺页次数为' noPageendl； cout '缺失率为' (float ) noPage/pageCountendl； }intfoundmaxnum(inta[]，int n ) {int
k,j;k=a[0];j=0;for(int i=0; i<n;i++){if(a[i]>=k){k=a[i];j=i;}}return j;} void LRU(int pc[],int bc[], int pageCount, int blockCount) {cout<<"1:LRU 置换算法"<<endl; if(pageCount<=blockCount){cout<<"缺页次数为："<<0<<endl; cout<<"缺页率为："<<0<<endl;} else{int noPage=0;int i, j, m;int*bc1=new int[blockCount]; for(i=0;i<blockCount;i++){bc1[i]=0;}for(i=0; i<pageCount;i++){ cout<<"引用页:"<<pc[i]<<endl;if(Travel(bc,blockCount,pc[i])==-1){//页面不在内存if(i<blockCount) {//欲调页bc[i]=pc[i];for(int p=0; p<=i; p++){bc1[p]++;}}else{for(j=0;j<blockCount;j++){ bc1[j]++;}int k=FoundMaxNum(bc1,blockCount);bc[k]=pc[i];bc1[k]=1;}noPage++;cout<<"物理块情况:"; Print(bc,blockCount);}else { //页面在内存if(i<blockCount){for(j=0; j<=i; j++){bc1[j]++;}for(m=0; m<i;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}else{for(j=0;j<blockCount;j++){bc1[j]++;}for(m=0;m<blockCount;m++){if(bc[m]==pc[i]){break;}}bc1[m]=1;bc[m]=pc[i];}}cout<<endl; }cout<<"缺页次数为:"<<noPage<<endl;cout<<"缺页率为:"<<(float)noPage/pageCount<<endl; delete bc1;} }void Optiomal(int pc[],int bc[],int pageCount,int blockCount){cout<<"2:最佳置换算法"<<endl; if(pageCount<=blockCount){cout<<"缺页次数为："<<0<<endl;cout<<"缺页率为："<<0<<endl;}else{int noPage=0;int i,j, k;for(i=0; i<pageCount;i++){cout<<"引用页:"<<pc[i]<<endl;if(Travel(bc,blockCount,pc[i]) ==-1){if(i<blockCount){bc[i]=pc[i];}else{int max=0;int blockIndex;;for(j=0;j<blockCount; j++){for(k=i;k<pageCount; k++){if(bc[i]=pc[k]){break;}}if(k>=max){ max=k;blockIndex=j;}}bc[blockIndex]=pc[i];} noPage++;cout<<"物理块情况:"; Print(bc, blockCount);}cout<<endl;}cout<<"缺页次数为："<<noPage<<endl;cout<<"缺页率为："<<(float)noPage/pageCount<<endl;}}void NRU(int pc[], int bc[], int pageCount,int blockCount){cout<<"3: Clock置换算法"<<endl ;if(pageCount<=blockCount){cout<<"缺页次数为"<<0<<endl;cout<<"缺页率为"<<0<<endl;}else{int noPage=0; int i,j; int *bc1=new int[blockCount]; for(i=0;i<blockCount;i++){ bc1[i]=0; } int replace=0; for(i=0;i<pageCount;i++){cout<<"引用页:"<<pc[i]<<endl;int index=Travel(bc, blockCount, pc[i]);if(index ==-1) {for(j=0;j<blockCount;j++){if(bc1[replace]==1){bc1[replace]=0;replace =(replace+1)%blockCount;}else{break;}}bc[replace]=pc[i];bc1[replace]=1;replace=(replace+1)% blockCount; noPage++;cout<<"物理块情况:"; Print(bc,blockCount); cout<<"标志位情况:"; Print(bc1,blockCount);}else{bc1[index]=1;replace=(index+1)% blockCount; cout<<"物理块情况:";Print(bc,blockCount);cout<<"标志位情况:";Print(bc1,blockCount);}cout<<endl; }cout<<"缺页次数为："<<noPage<<endl;cout<<"缺页率为："<<(float)noPage/pageCount<<endl;delete bc1;}} int main(){int pageCount,blockCount,i;cout<<"输入页面数"<<endl;cin>>pageCount;int *pc=new int[pageCount]; cout<<"输入页面走向"<<endl; for(i=0;i<pageCount;i++){cin>>pc[i];}cout<<"输入物理块数"<<endl; cin>>blockCount; cout<<"0:FIFO置换算法"<<endl; cout<<"1:LRU置换算法"<<endl; cout<<"2:最佳置换算法"<<endl;cout<<"3: Clock置换算法"<<endl;cout<<"按数字选择类别:"<<endl;int n;while(cin>>n){if(n==0){int *bc=new int[blockCount];FIFO(pc,bc,pageCount,blockCount);delete bc;}else if(n==1){int *bc=new int[blockCount];LRU(pc,bc,pageCount,blockCount);delete bc;}else if(n==2){ int *bc=new int[blockCount]; Optiomal(pc,bc,pageCount,blockCount); delete bc;}else if(n==3){ int *bc=new int[blockCount]; for(i=0; i<blockCount;i++){bc[i]=-1; }NRU(pc,bc,pageCount,blockCount); delete bc;}else break;}delete pc; return 0;}其实做人最重要的是自信，到哪儿都一样。————《叶问4》