《操作系统实验五(13页).doc》由会员分享，可在线阅读，更多相关《操作系统实验五(13页).doc（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-实验五 存储分配实验目的1 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及实现过程的理解。2 通过对页面、页表、地址转换和页面转换过程的模拟，加深对请求调页系统的原理和实现过程的理解。实验内容和步骤1 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc()和回收过程free()。其中，空闲分区通过空闲分区链管理；在进行内存分配时，系统优先使用空闲区低端的空间。2 假设初始状态下，可用的内在空间为640KB，并有下列的请求序列：作业1申请130KB作业2申请60KB作业3申请100KB作业2释放60KB作业4申请200KB作业3释放
2、100KB作业1释放130KB作业5申请140KB作业6申请60KB作业7申请50KB作业6释放60KB请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。3 假设每个页面中可存放10条指令，分配给一个作业的内存块数为44 用C语言模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面转换。最后显
3、示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。5 置换算法：请分别考虑OPT、FIFO和LRU算法。6 作业中指令的访问次序按下述原则生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在后地址部分具体的实施办法：在0,319之间随机选取一条起始指令，其序号为m顺序执行下一条指令，即序号为m+1的指令通过随机数，跳转到前地址部分0,m-1中的某条指令处，其序号为m1；顺序执行下一条指令，即序号为m1+1的指令通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为m2;顺序执行下一条指令，即序号
4、为m2+1的指令重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。代码1：#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; /状态
5、ElemType; /- 线性表的双向链表存储结构 -typedef struct DuLNode /double linked list ElemType 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
6、 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
7、_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;els
8、e 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;brea
9、k;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
10、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-
11、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/找到了最佳位置并实现
12、分配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-pr
13、ior-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) coutFreeen
14、dl;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*
15、 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;代码2：#include #include#include#include#define Bsize 4typedef
16、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( );/查找应予置换
17、的页面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 = c
18、urpage )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+) i
19、f(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;i3
20、20;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
21、(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 c
22、urpage;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
23、 = -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(sp
24、ace != -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( ) int select;cout请输入第一条指令号(0320)：;suijishu(
25、);cout*对应的调用页面队列*endl;pagestring( );do cout*endl;cout-1:OPT 2:LRU 3:FIFO 4:退出-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; d
26、efault: ; while(select!=4); 问题讨论1采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么不同的影响？首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。可利用空间表本身既不按节点的初始地址有序，也不按节点的大小有序。用户释放内存，回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。最佳适应算法将可利用空间表中一个大小不小于“请求”且最接近“请求”的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到
27、第一个足够大的空闲块即可予以分配。但回收时，必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户“请求”，从而使整个链表逐渐趋向于节点大小差别甚远的状态。这种分配算法适合请求分配内存大小范围较广的系统，此算法比较费时间。2如何解决因碎片而造成内存分配速度降低的问题？在装入作业时，根据需要及时地将空闲存储区拼在一起成一个大分区，以消除碎片，满足作业对空间的要求。3如果增加分配给作业的内存块数，将会对作业运行过程中的缺页率产生什么影响？增加作业的内存块数，可以降低缺页率，对于不同的算法，
28、增加物理块数都能降低缺页率，只是效果有所不同。4为什么一般情况下，LRU具有比FIFO更好的性能？答：FIFO置换算法设计简单，容易理解。 但它的效率并不是总能达到令人满意的效果。 这种算法只有在顺序访问地址空间时才能达到理想效果， 但根据程序的局部性原理，那些常被访问的页面， 往往要在主存中停留得最久，FIFO算法却将会将其换出页面，留下的只是一些新调入的指令，这将导致内存频繁换页。而LRU则选择在最近一段时间里最久没有使用过的页面予以置换，LRU算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU算法选择过去一段时间里最久未被使用的页面。这种算法以“最近的过去”作为“最近的将来”的近似，较好地利用了程序的局部性原理。一般情况下，能取得较好的效果，是经常采用的页面置换算法。3-第 13 页-