《2022年操作系统实验五》由会员分享，可在线阅读，更多相关《2022年操作系统实验五（13页珍藏版）》请在金锄头文库上搜索。
1、实验五存储分配 实验目的 1 了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及实现过程的理解。2通过对页面、页表、地址转换和页面转换过程的模拟，加深对请求调页系统的原理和实现过程的理解。实验内容和步骤 1用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc()和回收过程 free()。其中，空闲分区通过空闲分区链管理；在进行内存分配时，系统优先使用空闲区低端的空间。2假设初始状态下，可用的内在空间为640KB，并有下列的请求序列：作业 1申请 130KB 作业 2申请 60KB 作业 3申请 100KB 作业 2释放 60KB 作
2、业 4申请 200KB 作业 3释放 100KB 作业 1释放 130KB 作业 5申请 140KB 作业 6申请 60KB 作业 7申请 50KB 作业 6释放 60KB 请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。3假设每个页面中可存放10 条指令，分配给一个作业的内存块数为4 4用 C 语言模拟一作业的执行过程。该作业共有320 条指令，即它的地址空间为 32页，目前它的所有页都还未调入内存。在模拟过程中，如果访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数
3、，并将相应页调入内存。如果4 个内存块中均已装入该作业，则需进行页面转换。最后显示其物理地址，并转下一条指令。在所有320 条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。5置换算法：请分别考虑OPT、FIFO 和 LRU 算法。6作业中指令的访问次序按下述原则生成：50%的指令是顺序执行的25%的指令是均匀分布在前地址部分25%的指令是均匀分布在后地址部分具体的实施办法：在0,319 之间随机选取一条起始指令，其序号为m 顺序执行下一条指令，即序号为m+1的指令通过随机数，跳转到前地址部分 0,m-1 中的某条指令处，其序号为 m1 ；名师资料总结 - - -精品资料欢迎下载 -
4、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 13 页 - - - - - - - - - 顺序执行下一条指令，即序号为m1+1的指令通过随机数，跳转到后地址部分m1+2,319中的某条指令处，其序号为 m2; 顺序执行下一条指令，即序号为m2+1的指令重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行 320条指令。代码 1：#include #include #define Free 0 /空闲状态#define Busy 1 / 已用状态#define OK 1 / 完成#define
5、 ERROR 0 / 出错#define MAX_length 640 / 最大内存空间为640KB typedef int Status; typedef struct freearea/定义一个空闲区说明表结构 int ID; / 分区号long size; /分区大小long address; /分区地址int state; / 状态ElemType; /- 线性表的双向链表存储结构- typedef struct DuLNode /double linked list ElemType data; struct DuLNode *prior; /前趋指针struct DuLNode *
6、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=(DuLin
7、kList)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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 13 页
8、- - - - - - - - - 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分配成功
9、！ 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-d
10、ata.ID=ID; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 13 页 - - - - - - - - - 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-d
11、ata.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
12、=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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
13、- - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 13 页 - - - - - - - - - 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-pri
14、or; 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
15、-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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 13 页 - - - - - - - - - p-next-next-prior=p; p-next=p-next-next; break; p=p-ne
16、xt; 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; cout next; /- 主 函 数- void main() int ch;/
17、 算法选择标记cout 动态分区分配方式的模拟/n; cout*/n; cout* 1) 首次适应算法2)最佳适应算法*/n; cout*/n; coutch; Initblock(); / 开创空间表int choice; / 操作选择标记while(1) cout*/n; cout* 1: 分配内存2: 回收内存*/n; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 13 页 - - - - - - - - - cout* 3: 查看分配0: 退 出 */n; co
18、ut*/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 4 typedef struct BLOCK/ 声明一种新类型物理块类型 int p
19、agenum;/页号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 ( );/
20、显示void suijishu( );/ 产生 320 条随机数 ,显示并存储到temp320 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 13 页 - - - - - - - - - void pagestring( );/ 显示调用的页面队列void OPT( );/OPT算法void LRU( );/ LRU算法void FIFO( );/FIFO算法void init( ) for(int i=0;iBsize;i+) blocki.pagenum=-1; b
21、locki.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; f
22、or(int i=0; iblockpos.accessed) pos = i;/找到应予置换页面，返回BLOCK 中位置 return pos; void display( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 13 页 - - - - - - - - - for(int i=0; iBsize; i+) if(blocki.pagenum != -1) printf( %02d,blocki.pagenum); coutpc; cout*按照要求产生的3
23、20 个随机数： *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(
24、 ) 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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 13 页 - - - - - - - - -
25、blockspace.pagenum = curpage; display( ); n=n+1; else for(int k=0;kBsize;k+) for(int j=i;j320;j+) if(blockk.pagenum!= tempj/10) blockk.accessed = 1000; / 将来不会用，设置为一个很大数else blockk.accessed = j; break; position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; cout 缺页次数 :nendl; cout
26、缺页率 :(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) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 13 页 - - - - - - - - - s
27、pace = findSpace( ); if(space != -1) blockspace.pagenum = curpage; display( ); n=n+1; else position = findReplace( ); blockposition.pagenum = curpage; display( ); n+; else blockexist.accessed = -1;/ 恢复存在的并刚访问过的BLOCK 中页面 accessed为-1 for(int j=0; j4; j+) blockj.accessed+; cout 缺页次数 :nendl; cout 缺页率 :(
28、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; else 名师资料总结 - - -精品资料欢迎下载 - -
29、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 13 页 - - - - - - - - - position = 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 selec
30、t; cout 请输入第一条指令号(0320) ：; suijishu( ); 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:c
31、out先进先出置换算法FIFO:endl; cout*endl; FIFO( ); break; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 13 页 - - - - - - - - - default: ; while(select!=4); 问题讨论 1采用首次适应算法和最佳适应算法，对内存的分配和回收速度有什么不同的影响？首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“ 请求” 的空闲块的一部分分配给用户。可利用空间表本身既不按节点
32、的初始地址有序，也不按节点的大小有序。用户释放内存， 回收时只是将空闲块插入在链表的表头即可，此算法比较节省时间。最佳适应算法将可利用空间表中一个大小不小于“ 请求 ” 且最接近 “ 请求 ” 的空闲块的一部分分配给用户。分配与回收都需要对可利用空间表从头至尾查询一遍。为了避免每次分配都要查询整个链表，通常要求节点从大到小排序，由此只需找到第一个足够大的空闲块即可予以分配。 但回收时， 必须把回收的空闲块放置在符合大小顺序关系的链表位置。在分配时容易产生太小而无法利用的内存碎片，同时这种做法也保留了那些很大的内存块以备响应将来发生的内存量较大的用户“ 请求 ” ，从而使整个链表逐渐趋向于节点大
33、小差别甚远的状态。这种分配算法适合请求分配内存大小范围较广的系统，此算法比较费时间。2如何解决因碎片而造成内存分配速度降低的问题？在装入作业时， 根据需要及时地将空闲存储区拼在一起成一个大分区，以消除碎片， 满足作业对空间的要求。3如果增加分配给作业的内存块数，将会对作业运行过程中的缺页率产生什么影响？增加作业的内存块数，可以降低缺页率，对于不同的算法，增加物理块数都能降低缺页率，只是效果有所不同。4为什么一般情况下，LRU 具有比 FIFO 更好的性能？答：FIFO 置换算法设计简单，容易理解。但它的效率并不是总能达到令人满意的效果。这种算法只有在顺序访问地址空间时才能达到理想效果，但根据程
34、序的局部性原理，那些常被访问的页面，往往要在主存中停留得最久，FIFO 算法却将会将其换出页面，留下的只是一些新调入的指令，这将导致内存频繁换页。而 LRU 则选择在最近一段时间里最久没有使用过的页面予以置换，LRU 算法是与每个页面最后使用的时间有关的。当必须置换一个页面时，LRU 算法选择过去一段时间里最久未被使用的页面。这种算法以“最近的过去”作为“最近的将来”的近似，较好地利用了程序的局部性原理。一般情况下，能取得较好的效果，是经常采用的页面置换算法。3名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 13 页 - - - - - - - - -
