操作系统页面置换算法

操作系统课程设计报告院（系）：信息与数学学院专业：信息与计算科学姓名:张三班级：＿信计11402学号:122914题目：页面置换算法指导教师:孙庆生2017年5月27日一、课程设计目的《Linux操作系统课程设计》是在学完《操作系统》课程之后的实践教学环节，是复习和检验所学课程的重要手段。通过实验环节，加深学生对操作系统基本原理和工作过程的理解，提高学生独立分析问题、解决问题的能力，增强学生的动手能力。二、课程设计的任务和要求由于具体的操作系统相当复杂，不可能对所有管理系统进行详细地分析。因此，选择了操作系统中最重要的管理之一存储器管理，作为本设计的任务。页面置换算法是虚拟存储管理实现的关键，要求在充分理解内存页面调度机制的基础上，模拟实现OPT、FIFO、LRU几种经典页面置换算法，比较各种置换算法的效率及优缺点，从而了解虚拟存储实现的过程。具体任务如下：1)分析设计内容，给出解决方案①要说明设计实现的原理；②采用的数据结构：定义为进程分配的物理块；定义进程运行所需访问的页面号；定义页的结构；2）模拟三种页面置换算法；3）比较各种算法的优劣。4）对程序的每一部分要有详细的设计分析说明。5）源代码格式要规范。6）设计合适的测试用例，对得到的运行结果要有分析。任务要求：Linux平台下实现（Windows+VMware+Ubuntu）三、课程的详细设计1）系统设计在进程运行过程中，若其所要访问的页面不在内存而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面换出，或将那些在较长时间内不会再访问的页面调出。2）主程序流程图主流程图3）先进先出(FIFO)页面置换算法算法的基本思想：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单只需把一个进程已调入内存的页面，按先后次序存入一个时间数组，并将其中时间值最大的页面进行淘汰，并替换入新的页面就可以实现。算法流程图：输入页面序列输入物理块数调用各种置换算法，OPT，LRU，FIFO页面置换算法计算缺页次数和缺页率结束开始FIFO置换算法4）最佳页面置换置换算法（OPT）算法的基本思想：其所选择的被淘汰页面，将是永不使用的，或者是在最长时间内不再被访问的页面。可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法也是无法实现的。但是可利用该算法去评价其它算法。算法流程图：入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择最先进入的页面作为淘汰页计算缺页率，并输出数据结束输出当前页,i++将页面放到空闲的物理块处i页面长度YYYNNNOPT页面置换算法5）最近最久未使用页面置换算法LRU算法的基本思想：当需要淘汰某一页时，选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。该算法的主要出发点是，如果某页被访问了，则它可能马上还被访问。或者反过来说，如果某页很长时间未被访问，则它在最近一段时间不会被访问。算法流程图：入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择以后最长时间内（未来）不在被访问的页面作为淘汰页计算缺页率，并输出数据结束输出当前页,i++将页面放到空闲的物理块处i页面长度YYYNNNLRU页面置换算法四、源程序代码#includestdio.h#includemalloc.h#defineN20#definenum3/*进程分配物理块数目*/intA[N]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};typedefstructpage/*页表映像*/{intaddress;/*页面地址*/structpage*next;}page;structpage*head,*run,*rear;voidinitial()/*进程分配物理块*/入口初始化数据i指向下一个页面页面是否存在物理块是否有空闲选择最近最久未使用的页面作为淘汰页计算缺页率，并输出数据结束输出当前页,i++将页面放到空闲的物理块处i页面长度YYYNNN{inti=1;page*p,*q;head=(page*)malloc(sizeof(page));p=head;for(i=1;i=num;i++){q=(page*)malloc(sizeof(page));p-next=q;q-address=-1;q-next=NULL;p=q;}rear=p;}voidprint(){page*p=head-next;while(p){if(p-address!=-1)/*避免输出-1*/printf(%d\t,p-address);p=p-next;}printf(\n);}intsearch(intn)/*判断链表中是否有n*/{page*p;inti=0;p=head;while(p-next){if(p-next-address==n){printf(Getitatthepage%d\n,i+1);run=p;return1;}p=p-next;i++;}return0;}voidchangeOPT(intn,intposition){inti;inttotal=0;intflag=1;/*默认链表填满*/intdistance[num];/*用于存放距离*/intMAX;intorder=0;page*p,*q;p=head-next;q=head-next;for(i=0;inum;i++)/*初始化距离*/{distance[i]=100;}i=0;while(p)/*判断链表中是否填满*/{if(p-address==-1){flag=0;break;}p=p-next;i++;}if(!flag)/*链表没有填满的情况*/{p-address=n;printf(Changethepage%d\n,i+1);}else/*链表已经填满的情况*/{while(q)/*计算距离*/{for(i=position+1;iN;i++){if(q-address==A[i]){distance[total]=i-position;break;}}total++;q=q-next;}MAX=distance[0];for(i=0;inum;i++)/*计算最大距离*/{if(distance[i]MAX){MAX=distance[i];order=i;/*记录待替换的页面的位置*/}}printf(Changethepage%d\n,order+1);i=0;p=head-next;while(p)/*页面替换*/{if(i==order){p-address=n;}i++;p=p-next;}}}voidchangeFIFO(intn,intposition){inti=0;intflag=1;//默认队列已满page*p,*delect;p=head-next;while(p){if(p-address==-1)//队列未满{flag=0;p-address=n;printf(Changethepage%d\n,i+1);break;}p=p-next;i++;}if(flag)//队列已满{delect=head-next;delect-address=n;head-next=delect-next;printf(Delectfromthehead,andaddnewtotheend.\n);rear-next=delect;rear=delect;rear-next=NULL;}}voidchangeLRU(intn,intposition){inti;inttotal=0;intflag=1;/*默认为已满*/intdistance[num];intMAX;intorder=0;page*p,*q;p=head-next;q=head-next;for(i=0;inum;i++){distance[i]=100;}i=0;while(p)/*判断链表是否已满*/{if(p-address==-1){flag=0;break;}p=p-next;i++;}if(!flag)/*链表没有满的情况*/{p-address=n;printf(Changethepage%d\n,i+1);}else/*链表已满的情况*/{while(q){for(i=position-1;i=0;i--)/*向前计算距离*/{if(q-address==A[i]){distance[total]=position-i;break;}}total++;q=q-next;}MAX=distance[0];for(i=0;inum;i++)/*计算最远距离*/{if(distance[i]MAX){MAX=distance[i];order=i;}}printf(Changethepage%d\n,order+1);i=0;p=head-next;while(p)/*页面替换*/{if(i==order){p-address=n;}i++;p=p-next;}}}floatOPT(){inti;intlose=0;floatlosef;floatpercent;for(i=0;iN;i++){if(search(A[i])==0){lose++;changeOPT(A[i],i);}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}floatLRU(){inti;intlose=0;floatlosef;floatpercent;for(i=0;iN;i++){if(search(A[i])==0){lose++;changeLRU(A[i],i);}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}floatFIFO(){inti;intlose=0;floatlosef;floatpercent;page*p;for(i=0;iN;i++){if(search(A[i])==0){lose++;changeFIFO(A[i],i);}else{p=run-next;run-next=p-next;rear-next=p;rear=p;rear-next=NULL;printf(Moveittoendofqueue.\n);}print();}losef=(float)lose;percent=1-(losef/N);returnpercent;}voidmain()/*主函数部分*/{floatpercent;intchoice;printf(Selectthearithmetic:\n(1)OPT\n(2)LRU\n(3)FIFO\nyourchoiceis:);scanf(%d,&choice);/*选择页面置换算法*/initial();/*创建进程*/if(choice==1)/*采用OPT算法置换*/{percent=OPT();/*计算OPT时的缺页率*/printf(ThepercentofOPTis%f\n,percent);}elseif(choice==2)/*采用LRU算法置换*/{percent=LRU();/*计算LRU时的缺页率*/printf(ThepercentofLRUis%f\n,percent);}elseif(choice==3)/*采用FIFO算法置换*/{percent=FIFO();/*