操作系统实验报告 动态分区分配算法的模拟.doc

操作系统课程设计计算机科学与应用系课程设计报告操作系统原理姓名学号指导教师专业计算机科学与技术S日期2014年6月5日成 绩题目动态分区分配算法的模拟指导教师评语目 录1 题目简述22 需求分析22.1设计思想22.2要求22.3任务32.4运行环境32.5开发工具33 概要设计与详细设计33.1系统流程图33.2算法流程图54 编码与实现104.1数据结构和算法设计104.2程序调试与截图175 课程设计总结20参考文献21附录22动态分区分配算法的模拟1 题目简述 动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现可变分区分配时，将涉及到分区分配中所用到的数据结构、分配算法和分区的分配与回收操作。常用的数据结构有空闲分区表和空闲分区链两种，分区分配算法主要有首次适应算法、最佳适应算法、最坏适应算法等。本次试验通过C语言进行编程调试并运行，形象地表现出动态分区分配方式，直观地展示了首次适应算法、最佳适应算法、最坏适应算法对内存的释放和回收方式之间的区别。加深了我对三种算法优缺点的理解，帮助我了解一些数据结构和分配算法，进一步加深我对动态分区存储器管理方式及其实现过程的理解。主要问题在于，如何解决三种算法对内存的释放和回收空间的表示。动态分区分配又称为可变分区分配，这种分配方式并不是事先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区，并使分区的大小正好适适应作业的需要。因此，分区中的大小是可变的，分区的数目也是可变的。2 需求分析2.1设计思想（1）首次适应算法（First_fit）空闲分区链以地址递增的次序连接。在分配内存时，从联手开始顺序查找，直到找到一个大小能满足要求的空闲分区为止；然后再按照作业大小，从该分区划出一块内存空间给请求者，余下的空闲分区仍然留在空闲链中。若从链首直至链尾都找不到一个能满足要求的分区，则此次内存分配失败。（2）最佳适应算法（Best_fit）它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。（4）最坏适应算法（Worst_fit）最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。优点是可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利，同时该算法查找效率很高。（4）内存回收（Free）将释放作业所在内存块若改为空闲状态，删除其作业名，变为空。然后判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并其为同一个空闲链表，同时修改开始地址及分区大小。2.2要求（1）用C+语言实现程序设计；（2）利用结构体进行相关信息处理；（3）画出查询模块的流程图；（4）界面友好（良好的人机互交），程序要有注释。2.3任务（1）掌握为实现多道程序并发执行，操作系统是如何通过作业调度选择作业进入内存；（2）系统如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收，计算进程周转时间；（3）画出所有模块的流程图；（4）编写代码；（5）程序分析与调试。2.4运行环境（1）WINDOWS2000/XP系统（2）Microsoft Visual C+ 6.0编译环境2.5开发工具C+语言本程序采用C语言编写，在Windows下的Visual C+环境下编译，模拟可变分区存储管理方式的内存分配与回收。3 概要设计与详细设计3.1系统流程图3.1.1系统流程图图3.1.1 系统流程图3.2算法流程图3.2.1内存分配流程图图3.2.1 内存分配流程图3.2.2.首次适应算法流程图图3.2.2 首次适应算法流程图3.2.3最佳适应算法流程图图3.2.3 最佳适应算法流程图3.2.4 最坏适应算法流程图图3.2.4 最坏适应算法流程图3.2.5 内存回收流程图图3.2.5 内存回收流程图4 编码与实现4.1数据结构和算法设计相关数据结构定义：空闲分区结构：typedef struct freearea()线性链表结构：typedef struct DuLNode()带头结点内存空间链表结构：Status Initblock() 内存分配：Status alloc()显示主存：void show（） 测试类（主函数类）：class TestForMemManage4.2程序调试与截图1)首界面2)首次适应算法测试数据：为作业申请空闲区800KB。作业1申请资源100kb，作业2申请资源120kb，作业3申请资源130kb，作业4申请资源140kb，释放作业1和作业3，作业5申请资源160kb，这时，按照表从头开始查询，第一个找到满足条件的就停止查找，并分配资源。运行结果如下图所示：3)最佳适应算法测试数据：为作业申请空闲区800KB。作业1申请资源105kb，作业2申请资源115kb，作业3申请资源125kb，作业4申请资源135kb，释放作业2和作业4，作业5申请资源145kb，这时，在每次的分配内存中，总是找到既满足要求又是最小空闲分区，然后分配资源，这样，就避免了“大材小用”的问题。运行结果如下图所示：4) 最坏适应算法测试数据：为作业申请空闲区800KB。作业1申请资源80kb，作业2申请资源100kb，作业3申请资源120kb，作业4申请资源140kb，释放作业1和作业3，作业5申请资源160kb，这时，在扫描整个空闲分区链表时，总是找到既满足要求又是最大空闲分区，然后把它分割给作业。运行结果如下图所示：5 课程设计总结为期五周的课程设计，对于我个人来说是相当有难度的。在设计的过程中，有很多问题不是很清楚，所以做起来就就很困难，刚开始的时候都有点无从下手的感觉。很多时候在遇到问题时，基本知识都了解，但是就不知道怎么才能把它们都整合到一块，也就是说知识都是很零散的，没有一个完整的系统。而且，又由于基础知识不牢固，使得我在这次的课程设计中感到更加力不从心。在设计的过程中，每走一步就会发现，思路想出来很容易，但涉及到实现的时候，总是有点手无足措。对于本次的课程设计，里面还有很多需要改进的地方。一个程序的顺利出炉，少不了反复地调试和修改。在调试的过程中，总是会发生很多错误，但在解决这些错误的时候，开始很模糊的概念就会变得越来越清晰。其实很多错误都是很类似的，只要解决了一个，其余的就会迎刃而解了。“千里之行，始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义，我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础。这次的课程设计，使我树立了正确的设计思想，培养实事求是、严肃认真、高度负责的学习作风，加强操作能力的训练和培养严谨求实的科学作风更尤为重要。在这次设计过程中，充分体现出自己单独设计课程的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补。通过本次实验，我掌握了实现多道程序并发执行，操作系统是如何通过作业调, 选择作业进入内存以及系统是如何为进入内存的作业分配内存空间，实现多道作业同时驻留内存，就绪进程队列中的多个进程是如何以分式方式共享CPU，作业运行完成离开系统时，系统如何进行内存回收。最后，感谢我们的荆立夏老师，老师严谨细致、一丝不苟的作风将会一直是我工作、学习中的榜样；老师循循善诱的教导和不拘一格的教学思路给予我无尽的启迪；这次课程设计的每个实验细节和每个数据，都离不开老师您的细心指导。而您开朗的个性和宽容的态度，帮助我能够很顺利的完成了这次课程设计。祝愿老师您在以后的工作和生活中继续保持健康的身体和愉快的心情，再次感谢！同时，也很感谢对我帮助过的同学们，谢谢你们对我的帮助和支持，让我感受到同学的友谊和温暖。参考文献1 李玲玲. C语言程序设计M. 辽宁大学出版社，2010.12 谭浩强程序设计基础与C语言 沈阳：辽宁大学出版社，2010.13 严蔚敏、吴伟民等数据结构（C语言版）北京：清华大学出版社，20084 汤子瀛、梁红兵等计算机操作系统第三版北京：西安电子科技大学出版社，2009附录源代码#include#include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1 /完成#define ERROR 0 /出错#define MAX_length 800 /最大内存空间为800KBtypedef 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 *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); /最佳适应算法Status Worst_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内存不足，分配失败！endl; return OK; if(ch=3) /选择最坏适应算法 if(Worst_fit(ID,request)=OK) cout分配成功！endl; elsecout内存不足，分配失败！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 Worst_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-requestch)/剩余空间比初值还大 ch=p-data.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