操作系统实验五

实验五存储分配[实验目的]1．了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及实现过程的理解。2．通过对页面、页表、地址转换和页面转换过程的模拟，加深对请求调页系统的原理和实现过程的理解。[实验内容和步骤]1．用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链管理；在进行内存分配时，系统优先使用空闲区低端的空间。2．假设初始状态下，可用的内在空间为640KB，并有下列的请求序列：作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200KB作业3释放100KB作业1释放130KB作业5申请140KB作业6申请60KB作业7申请50KB作业6释放60KB请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。3．假设每个页面中可存放10条指令，分配给一个作业的内存块数为44．用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面转换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。5．置换算法：请分别考虑OPT、FIFO和LRU算法。6．作业中指令的访问次序按下述原则生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在后地址部分具体的实施办法：①在[0,319]之间随机选取一条起始指令，其序号为m②顺序执行下一条指令，即序号为m+1的指令③通过随机数，跳转到前地址部分[0,m-1]中的某条指令处，其序号为m1；④顺序执行下一条指令，即序号为m1+1的指令⑤通过随机数，跳转到后地址部分［m1+2,319］中的某条指令处，其序号为m2;⑥顺序执行下一条指令，即序号为m2+1的指令⑦重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。代码1：#include#include#defineFree0agenum=-1;block[i].accessed=0;pc=n=0;}}intfindExist(intcurpage){for(inti=0;iBsize;i++){if(block[i].pagenum==curpage)returni;agenum==-1)returni;ccessedblock[pos].accessed)pos=i;agenum!=-1){printf(%02d,block[i].pagenum);}}coutendl;}voidsuijishu(){intflag=0;cinpc;cout******按照要求产生的320个随机数：*******endl;for(inti=0;i320;i++){temp[i]=pc;if(flag%2==0)pc=++pc%320;if(flag==1)pc=rand()%(pc-1);if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));flag=++flag%4;printf(%03d,temp[i]);if((i+1)%10==0)coutendl;}}voidpagestring(){for(inti=0;i320;i++){printf(%02d,temp[i]/10);if((i+1)%10==0)coutendl;}}voidOPT(){intexist,space,position;intcurpage;for(inti=0;i320;i++){if(i%100==0)getch();pc=temp[i];curpage=pc/10;exist=findExist(curpage);if(exist==-1){space=findSpace();if(space!=-1){block[space].pagenum=curpage;display();n=n+1;}else{for(intk=0;kBsize;k++){for(intj=i;j320;j++){if(block[k].pagenum!=temp[j]/10){block[k].accessed=1000;}ccessed=j;break;}}}position=findReplace();block[position].pagenum=curpage;display();n++;}}}cout缺页次数:nendl;cout缺页率:(n/*100%endl;}agenum=curpage;display();n=n+1;}else{position=findReplace();block[position].pagenum=curpage;display();n++;}}elseblock[exist].accessed=-1;ccessed++;}}cout缺页次数:nendl;cout缺页率:(n/*100%endl;}agenum=curpage;display();n=n+1;}else{position=findReplace();block[position].pagenum=curpage;display();n++;block[position].accessed--;}}for(intj=0;jBsize;j++)block[j].accessed++;}cout缺页次数:nendl;cout缺页率:(n/*100%endl;}voidmain(){intselect;cout请输入第一条指令号(0~320)：;suijishu();cout*****对应的调用页面队列*******endl;pagestring();do{cout****************************************endl;cout------1:OPT2:LRU3:FIFO4:退出-----endl;cout****************************************endl;cout请选择一种页面置换算法:;cinselect;cout****************************************endl;init();switch(select){case1:cout最佳置换算法OPT:endl;cout*****************endl;OPT();break;case2:cout最近最久未使用置换算法LRU:endl;cout**************************endl;LRU();break;case3:cout先进先出置换算法FIFO:endl;cout*********************endl;FIFO();break;default:;}}while(select!=4);}[问题讨论]1．采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么不同的影响首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户“请求”，从而使整个链表逐渐趋向于节点大小差别甚远的状态。这种分配算法适合请求分配内存大小范围较广的系统，此算法比较费时间。2．如何解决因碎片而造成内存分配速度降低的问题在装入作业时，根据需要及时地将空闲存储区拼在一起成一个大分区，以消除碎片，满足作业对空间的要求。3．如果增加分配给作业的内存块数，将会对作业运行过程中的缺页率产生什么影响增加作业的内存块数，可以降低缺页率，对于不同的算法，增加物理块数都能降低缺页率，只是效果有所不同。4．为什么一般情况下，LRU具有比FIFO更好的性能答：FIFO置换算法设计简单，容易理解。但它的效率并不是总能达到令人满意的效果。这种算法只有在顺序访问地址空间时才能达到理想效果，但根据程序的局部性原理，那些常被访问的页面，往往要在主存中停留得最久，FIFO算法却将会将其换出页面，留下的只是一些新调入的指令，这将导致内存频繁换页。而LRU则选择在最近一段时间里最久没有使用过的页面予以置换，LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。这种算法以“最近的过去”作为“最近的将来”的近似，较好地利用了程序的局部性原理。一般情况下，能取得较好的效果，是经常采用的页面置换算法。3．