操作系统实验三

操作系统实验存储分配收藏实验目的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源代码如下：/*动态分区分配方式的模拟*#include#include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1/完成#define ERROR 0 /出错#define MAX_length 640 /最大内存空间为640KBtypedef int Status;typedef struct freearea/定义一个空闲区说明表结构int ID;/分区号long size;/分区大小long address; /分区地址int state;/状态ElemType;/-线性表的双向链表存储结构-typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next;/后继指针DuLNode,*DuLinkList;DuLinkList block_first; /头结点DuLinkList block_last;/尾结点Status alloc(int);/内存分配Status free(int); /内存回收Status First_fit(int,int);/首次适应算法Status Best_fit(int,int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-data.size=MAX_length;block_last-data.ID=0;block_last-data.state=Free;return OK;/-分配主存-Status alloc(int ch)int ID,request;coutID;coutrequest;if(request0 |request=0)cout分配大小不合适，请重试！endl;return ERROR;if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout分配成功！endl;else cout内存不足，分配失败！endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout分配成功！endl;else cout内存不足，分配失败！data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小恰好合适的空闲块p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;/-最佳适应算法-Status Best_fit(int ID,int request)int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode);temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=block_first-next;DuLNode *q=NULL; /记录最佳插入位置while(p) /初始化最小空间和最佳位置if(p-data.state=Free &(p-data.sizerequest | p-data.size=request) )q=p;ch=p-data.size-request;break;p=p-next;while(p)if(p-data.state=Free & p-data.size=request)/空闲块大小恰好合适p-data.ID=ID;p-data.state=Busy;return OK;break;if(p-data.state=Free & p-data.sizerequest)/空闲块大于分配需求if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p-next;if(q=NULL) return ERROR;/没有找到空闲块else/找到了最佳位置并实现分配temp-prior=q-prior;temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;/-主存回收-Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/与前面的空闲块相连p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior=p-prior;if(p-next-data.state=Free)/与后面的空闲块相连p-data.size+=p-next-data.size;p-next-next-prior=p;p-next=p-next-next;break;p=p-next;return OK;/-显示主存分配情况-void show()cout+n;cout+主存分配情况+n;coutnext;while(p)coutdata.ID=Free) coutFreeendl;else coutdata.IDendl;cout起始地址：data.addressendl;cout分区大小：data.size KBendl;coutdata.state=Free) cout空闲endl;else cout已分配endl;coutnext;/-主函数-void main()int ch;/算法选择标记cout动态分区分配方式的模拟n;cout*n;cout* 1)首次适应算法2)最佳适应算法*n;cout*n;coutch;Initblock(); /开创空间表int choice;/操作选择标记while(1)cout*n;cout*1:分配内存2:回收内存*n;cout*3:查看分配0:退出*n;cout*n;coutchoice;if(choice=1) alloc(ch); /分配内存else if(choice=2)/内存回收int ID;coutID;free(ID);else if(choice=3) show();/显示主存else if(choice=0) break; /退出else /输入操作有误cout输入有误，请重试！endl;continue;二、请求调页存储管理方式的模拟1假设每个页面中可存放10条指令，分配给一个作业的内存块数为42用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面转换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。3置换算法：请分别考虑OPT、FIFO和LRU算法。4作业中指令的访问次序按下述原则生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在后地址部分具体的实施办法：在0,319之间随机选取一条起始指令，其序号为m顺序执行下一条指令，即序号为m+1的指令通过随机数，跳转到前地址部分0,m-1中的某条指令处，其序号为m1；顺序执行下一条指令，即序号为m1+1的指令通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2;顺序执行下一条指令，即序号为m2+1的指令重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。5关键知识在进程运行过程中，若其所要访问的页面不在内存需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据，送磁盘的对换区中。但应将哪个页面调出，所以需要根据一定的算法来确定。在这一过程中，选择换出页面的算法称为页面置换算法。一个好的页面置换算法，应具有较低的页面更换频率。页面置换算法的好坏，将直接影响到系统的性能。以下分别是实验要求的三个页面置换算法的介绍及设计思想。最佳置换算法（Optimal）：最佳置换算法是Blady在理论上提出的一种算法。其所选择的被淘汰页是将来不再被使用，或者是在最远的将来才被访问的页面。采用这种页面置换算法，保证有最少的缺页率。但由于目前还无法预知一个进程在内存的若干个页面中，哪个在最长的时间内不会被访问，因而，现实中该算法是无法实现的。因此在该算法的模拟过程中，页面访问次序必须是给定的，具体实现为：对每一个物理块设置一个整数型的访问标志位，当需要置换物理块中的某一页时，将每一个物理块中的页面号与当前需调入页以后的每一页面号进行比较，若物理块中的页面号与所有的页面号都不同，则该页即为将来不再使用的页，将访问标记设置为1000，表示将来不会用，设置为一个很大数；若找到页号相同的则将其访问次序记入访问标记，比较访问标记，最大的即为最久不会被访问的，将其换出。先进先出法（First In First Out）：该算法总是淘汰最先进入内存的页面，既选择在内存中驻留时间最久的页面予以淘汰。在该算法的模拟过程中，每当某一页面进入内存时（包括页面置换时页面的置入），物理块中各页面访问标记自动加一，置换后，将置换页面所在的物理块中访问标记减一；这样能防止当物理块访问标记出现两个以上相同的值的错误执行，更好地模拟了先进先出法；最近最久未使用（Least Recently Used）：该算法以最近的过去作为不久将来的近似，将过去最长一段时间里不曾被使用的页面置换掉。在该算法的模拟过程中，每当物理块中的页面被访问时，便将其访问标记置为1以后每执行一条指令，便将物理块中各页面的访问标记加一，需置换时访问标记最大的便是将要被置换的。四、源代码#include #include#include#include#define Bsize 4typedef struct BLOCK/声明一种新类型物理块类型int pagenum;/页号int accessed;/访问字段，其值表示多久未被访问BLOCK;int pc;/程序计数器，用来记录指令的序号int n;/缺页计数器，用来记录缺页的次数static int temp320;/用来存储320条随机数BLOCK blockBsize; /定义一大小为4的物理块数组void init( );/程序初始化函数int findExist(int curpage);/查找物理块中是否有该页面int findSpace( );/查找是否有空闲物理块int findReplace( );/查找应予置换的页面void display ( );/显示void suijishu( );/产生320条随机数,显示并存储到temp320void pagestring( );/显示调用的页面队列void OPT( );/OPT算法void LRU( );/ LRU算法void FIFO( );/FIFO算法void init( )for(int i=0;iBsize;i+)blocki.pagenum=-1;blocki.accessed=0;pc=n=0;int findExist(int curpage)for(int i=0; iBsize; i+)if(blocki.pagenum = curpage )return i;/检测到内存中有该页面，返回block中的位置return -1;int findSpace( )for(int i=0; iBsize; i+)if(blocki.pagenum = -1)return i;/找到空闲的block，返回block中的位置return -1;int findReplace( )int pos = 0;for(int i=0; iblockpos.accessed)pos = i;/找到应予置换页面，返回BLOCK中位置return pos;void display( )for(int i=0; iBsize; i+)if(blocki.pagenum != -1)printf( %02d,blocki.pagenum);coutpc;cout*按照要求产生的320个随机数：*endl;for(int i=0;i320;i+)tempi=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,tempi);if(i+1)%10=0) coutendl;void pagestring( )for(int i=0;i320;i+)printf( %02d,tempi/10);if(i+1)%10=0) coutendl;void OPT( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace ( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elsefor(int k=0;kBsize;k+)for(int j=i;j320;j+)if(blockk.pagenum!= tempj/10)blockk.accessed = 1000;/将来不会用，设置为一个很大数elseblockk.accessed = j;break;position = findReplace( );blockposition.pagenum = curpage;display( );n+;cout缺页次数:nendl;cout缺页率:(n/320.0)*100%endl;/-void LRU( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elseposition = findReplace( );blockposition.pagenum = curpage;display( );n+;else blockexist.accessed = -1;/恢复存在的并刚访问过的BLOCK中页面accessed为-1for(int j=0; j4; j+)blockj.accessed+;cout缺页次数:nendl;cout缺页率:(n/320.0)*100%endl;/-void FIFO( )int exist,space,position ;int curpage;for(int i=0;i320;i+)if(i%100=0) getch( );pc=tempi;curpage=pc/10;exist = findExist(curpage);if(exist=-1)space = findSpace( );if(space != -1)blockspace.pagenum = curpage;display( );n=n+1;elseposition = findReplace( );blockposition.pagenum = curpage;display( );n+;blockposition.accessed-;for(int j=0; jBsize; j+)blockj.accessed+;cout缺页次数:nendl;cout缺页率:(n/320.0)*100%endl;void main( )intselect;cout请输入第一条指令号(0320)：;suijishu( );cout*对应的调用页面队列*endl;pagestring( );docout*endl;cout-1:OPT2:LRU3:FIFO4:退出-endl;cout*endl;coutselect;cout*endl;init( );switch(select)case 1:cout最佳置换算法OPT:endl;cout*endl;OPT( );break;case 2:cout最近最久未使用置换算法LRU:endl;cout*endl;LRU( );break;case 3:cout先进先出置换算法FIFO:endl;cout*endl;FIFO( );break;default: ;while(select!=4);问题讨论1采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么不同的影响？答：最佳适应算法（Best Fit）：它从全部