随机淘汰算法

《操作系统》课程设计报告书-1-页式虚拟存储管理缺页中断的随机淘汰算法虚拟页号物理块号状态位辅存地址访问字段修改位各字段说明如下：状态位：用于指示该页是否已调入内存，供程序访问时参考。访问字段：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供替换页面时参考。修改位：表示该页面在调入内存后是否被修改过。由于内存中的每一页都在外存上保留有副本，因此，若未被修改，在替换该页时就不需要再将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入页面时参考。在模拟系统的实现中，只需要用到虚拟页号，物理块号和中断位。页表可用一个结构体的数组实现。请求分页的具体实现过程如图1图1请求分页流程图《操作系统》课程设计报告书-2-开始请求页面序列结束？内存块已满？利用替换算法，选择内存块中应该被替换的页面进行替换，修改页表选择将要调入页面放入未被占用的内存块中,修改页表NYN结束Y页面在内存中？NY2算法分析在进程运行过程中，若其所要访问的页面不在内存，这时候会产生一个缺页中断，并需要把它们调入内存，但内存已无空闲已空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区。但应将哪个页面调出，必须根据一定的算法来确定。通常，把选择换出页面的算法称为页面替换算法。虚拟内存性能的好坏很大程度上由替换算法的好坏，替换算法的好坏，也将直接影响系统的性能，一个好的页面置换算法，应具有较低的页面更换频率。常见置换算法有随机淘汰算法（RandomGlongram）、轮转法（RoundRobin）和先进先出(FIFO)、最近最久未使用页面置换算法和理想型淘汰算法OPT（OptimalReplacementAlgorithm）。本次所设计的模拟系统根据题目要求利用随机淘汰算法，先进先出算法和理想型淘汰算法进行页面替换，详细算法原理如下：随机淘汰算法：在系统设计人员无法确定哪些页被访问的概率较低时，明智《操作系统》课程设计报告书-3-的作法是随机地选择某个用户的页并将其换出。随机淘汰算法实现简单，但是缺页率高。先进先出算法：总是选择在内存驻留时间最长的一页将其淘汰，因为最早调入内存的页，不再被使用的可能性比近期调入内存的大。该算法实现简单，只需要把一个进程调入内存的页面，按先后次序连结成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如有全局变量、常用函数，例程等的页面，FIFO算法并不能保证这些页面不被淘汰。假定系统为某进程分配了三个可用物理块，并考虑有以下的页面号引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1进程运行时，先将7，0，1三个页面装入内存，且采用FIFO替换算法。当有请求页面2时，内存中页面7，0，1三个页号可知道7先进入内存，所以替换页面1；当请求页面0时，可知，0在内存中，不需要替换；当请求页面号3时内存中0，1，2三个页面0先进入内存，替换0号页。如此进行下去，可得出利用FIFO替换算法，以上请求页面号序列共进行了12次页面替换，比理想型算法要多出一倍。使用FIFO替换算法效率低的原因是：基于处理器按线性顺序访问地址空间这一假设。事实上，许多时候，处理器不是按线性顺序访问地址空间的。例如，执行循环结构的程序段。使用FIFO算法时，在未给进程或作业分配足够它所需要的页面数时，有时会出现分配的页面数增，缺页次数反而增加的现象（Belady现象）。例如针对请求序列：123412512345，若分配3个可用内存块，使用FIFO算法，一共会缺页9次，缺页率：75%；而如果分配4个可用内存块，则一共会缺页10次，缺页率：83.3%。理想型淘汰算法基本思想：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。采用理想型替换算法，通常可保证获得最低的缺页率。但是由于人们目前无法预知一个进程在内存的若干个页面中，哪个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但是在模拟设计中，由于是事先给定一个页面序列，即知道各个时刻以前和以后的页面出现情况，所以可实现该算法。在实际系统中，虽无法实现理想型淘汰算法，但是可用它来评价其他替换算法。用上面的例子，先将7，0，1三个页面装入内存。以后当进程要访问页面2时，将会产生缺页中断。此时OS根据最佳替换算法，将选择页面7予以淘汰，这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面1则要在第18次页面访问时才需要调入。下次访问页面0时，因它已经在内存而不必产生缺页中断。当进程访问页面3时，又将引起页面1被淘汰；因为，它在现有的1，2，0三个页面中，将是最后被访问的。如此继续，这个作业序列将会产生6次页面置换。理想型淘汰算法的具体工作流程如图2：图2《操作系统》课程设计报告书-4-开始选择在内存块i中的页面ji=memorySize？选择使得OPT[i]最大的i，就是应该被替换占用的内存块NY结束i=0；Page=当前请求页面序列号t=page+1t=inputSize？j=in[t]？OPT[i]=t；i++；YNt++；NOPT[i]=inputSize；i++；Y3数据结构模拟设计时，页表用数组模拟。数组的数据类型为结构体，结构体有三个成员：intpageNum表示页面号；intmemoryNum表示页面所对应的内存块号；intisInmemory是存在状态位标志，表示页面是否在内存，0表示不在内存，1表示在内存。程序中设定虚拟页面号共10个，所以页表大小为10，即10个元素的数组pageTable。在每一个算法函数中都要初始化页表，否则，后面的算法会受前面算法结果的影响。structpage{intpageNum;intmemoryNum;intisInmemory;};pagepageTable[10];《操作系统》课程设计报告书-5-初始化页表：for(inti=0;i10;i++){pageTable[i].pageNum=i;pageTable[i].memoryNum=-1;//初始化时，内存块号为-1，即没在内存块中。pageTable[i].isInmemory=0;//初始化时，各页面均不在内存}页面请求序列：int*in=newint[inputSize]。模拟内存：int*memory=newint[memorySize]，在程序中模拟内存存放页面号。4各模块函数功能说明intMain（）函数提示并接受用户输入等待调入页面数inputSize，可用物理块数memorySize，并随机生成inputSize个请求页面，或提示用户自己输入页面序列。然后调用FIFO()、random()和OPT()函数实现按不同替换算法调入页面进内存。voidFIFO()函数实现先进先出的替换算法调入页面。voidrandom()函数实现随机替换算法调入页面。voidOPT()函数实现理想型替换算法。intgetOPTPage(intpage)用于获取最优替换页面所在的内存块。该函数的算法实现流程图如图2。三源程序的主要部分1main函数intmain(){for(inti=0;i10;i++)//初始化页表{pageTable[i].pageNum=i;pageTable[i].memoryNum=-1;pageTable[i].isInmemory=0;}cout输入待调入页面数endl;cininputSize;cout输入可使用的物理块数：endl;cinmemorySize;《操作系统》课程设计报告书-6-inttemp;srand((unsigned)time(NULL));cout随机生成页面请求序列(0-9)endl;for(i=0;iinputSize;i++){temp=rand()%10;couttemp;in[i]=temp;}coutendl;random();return0;}四使用说明运行程序替换算法.exe，根据提示输入等待调入页面数和可使用的物理块数，程序会提示是否随机生成并显示一个页面请求序列，如果是，则随机生成序列，否则，要求自行输入序列。然后显示利用各算法处理请求页面的结果：如果页面在内存则显示“‘页面号’isinmemory”，若不在内存则显示“‘页面号’notinmemory！takeplaceof‘被替换的页面号’”。处理完各页面后，统计并显示缺页次数和缺页率。五运行结果与运行情况分析待调入页面数：25可用物理块数：3随机生成页面请求序列，如图3：0394016015095276888252530图3《操作系统》课程设计报告书-7-3随机替换算法运行结果，如图5：图5结果分析，如表3（×表示缺页，并在下方填被替换的页面号，√表示不缺页）：表3《操作系统》课程设计报告书-8-0394016015095276888252530000444400000000666665555533301661119997777777777099999995555222888222233×××××××√√×××√××××√√××√√××0301469159028627通过表可以看出，利用随机替换算法，请求序列共缺页19次，替换序列依次是：0301469159028627缺页率为76%，运行结果与分析结果一致。附录#includeiostream#includetime.husingnamespacestd;intinputSize;intmemorySize;int*in;//请求序列int*memory;//模拟内存voidrandom();intgetOPTPage(intinPage);structpage{intpageNum;intmemoryNum;intisInmemory;};pagepageTable[10];//假设虚拟页面数10个，页表长度10intmain(){for(inti=0;i10;i++)//初始化页表{pageTable[i].pageNum=i;pageTable[i].memoryNum=-1;pageTable[i].isInmemory=0;}cout输入待调入页面数endl;《操作系统》课程设计报告书-9-cininputSize;cout输入可使用的物理块数endl;cinmemorySize;in=newint[inputSize];memory=newint[memorySize];inttemp;intselect;srand((unsigned)time(NULL));cout随机生成请求序列？(1是)endl;cinselect;if(select==1){cout随机生成页面请求序列(0-9)endl;for(i=0;iinputSize;i++){temp=rand()%10;couttemp;in[i]=temp;}}else{cout输入inputSize个页面号(0-9)endl;for(i=0;iinputSize;i++){cintemp;in[i]=temp;}}coutendl;random();delete[]in;delete[]memory;return0;}voidrandom()//随机替换算法实现函数{for(inti=0;i10;i++)//初始化页表《操作系统》课程设计报告书-10-{pageTable[i].pageNum=i;pageTable[i].memoryNum=-1;pageTable[i].isInmemory=0;}srand((unsi