最佳置换算法

1、/*最佳置换算法(OPtimalReplacementAlgorithm,ORA)*/*算法描述:所选择的淘汰页，是以后永不使用，或最长时间内不使用的页面*/*writenbyXuZhuozhuo*/C+代码示例：#include#defineMaxSize20#defineNum_Block3usingnamespacestd;intmax(inta,intb,intc)intmax(inta,intb,intc)if(ab)a=b;if(ac)a=c;returna;/返回三者的最大值intmain()/引用字符的数目/引用字符的数目/引用字符串数组/数组模拟“物理块”intnum_ref

2、;intref_arrMaxSize;intphy_blkNum_Block;coutOptimalReplacementAlgorithmsendlendl;docoutPleaseinputthenumberofreferencechars：num_ref;/输入引用字符串的数目while(num_refMaxSize);coutPleaseinputthequeueofreferencechars：endl;for(inti=0;iref_arri;for(intj=0;jNum_Block;j+)/前Num_Block项进物理块phy_blkj=ref_arrj;coutendlDis

3、playthereplacementprocedure：;coutendlendl;for(intp=0;pnum_ref-Num_Block;p+)if(!(phy_blk0=ref_arrNum_Block+p|phy_blk1=ref_arrNum_Block+p|phy_blk2=ref_arrNum_Block+p)寻找phy_blk0在引用字符串中的下一位置k1for(intk1=Num_Block+p+1;k1MaxSize;k1+)if(phy_blk0=ref_arrk1)break;寻找phy_blkl在引用字符串中的下一位置k2for(intk2=Num_Block+p+

4、1;k2MaxSize;k2+)if(phy_blkl=ref_arrk2)break;寻找phy_blk2在引用字符串中的下一位置k3for(intk3=Num_Block+p+l;k3MaxSize;k3+)if(phy_blk2=ref_arrk3)break;intmax_ref=max(kl,k2,k3);返回intmax_ref=max(kl,k2,k3);返回k1,k2,k3中的最大者如果最大者为如果最大者为kl/如果最大者为k2/如果最大者为k3if(max_ref=kl)phy_blk0=ref_arrNum_Block+p;elseif(max_ref=k3)phy_blk

5、2=ref_arrNum_Block+p;elseif(max_ref=k2)phy_blk1=ref_arrNum_Block+p;/输出本次替换后的“物理块”数组内容coutendlp+1.Physicalblockarraycontent:;for(intloop=0;loopNum_Block;loop+)coutphy_blkloop;return0;VC+6.0下的运行结果见下页：（数据源自操作系统课本）頁UVfiflTJDOWSsysteii32c:rniExeOptimalReplacementAlgforithmsPleaseinputthenumberofreference

6、cliars20Pleaseinputthequeueofreferencecliars:76120304236321201701Displaythereplacementprocedure:1.Physicalblockarraycontent:2012J.Physicalblockarraycontent:20133.Physicalblockarraycontent:2034J.Physicalblockarraycontent:20353.Physicalblockarraycontent:2436J.Physicalblockarraycontent:2437J.Physicalblockarraycontent:2438J.Physicalblockarraycontent:203?.Physicalblockarraycontent:20310.Physicalblockarraycontent20311J.Physicalblockarraycontent20112.Physicalblockarraycontent20113.Physicalblockarraycontent201141.Physicalblockarraycontent20115.Physic