《存储管理——动态分区分配回收算法的模拟.doc》由会员分享,可在线阅读,更多相关《存储管理——动态分区分配回收算法的模拟.doc(25页珍藏版)》请在金锄头文库上搜索。
1、齐齐哈尔大学操作系统课程综合实践题目:存储管理动态分区分配/回收算法的模拟班级: 0姓名: 0 学号:0 指导教师:0 2011年 12 月综合实践评分表班级0姓名0指导教师0题目: 存储管理-动态分区分配/回收算法的模拟 评分标准评分标准分数权重评分的依据得分AC选题10选题符合大纲要求,题目较新颖,工作量大选题基本符合大纲要求,工作量适中工作态度10态度端正,能主动认真完成各个环节的工作,不迟到早退,出勤好。能够完成各环节基本工作,出勤较好。存储结构、算法描述20能正确选择存储结构,定义准确,算法流程图或类C语言描述的算法准确无误能正确选择存储结构,算法流程图或类C语言描述的算法基本准确独
2、立解决问题的能力10具有独立分析、解决问题能力,有一定的创造性,能够独立完成软件的设计与调试工作,程序结构清晰,逻辑严谨,功能完善。有一定的分析、解决问题能力。能够在老师指导下完成软件的设计与调试工作,程序功能较完善。答辨问题回答20能准确回答老师提出的问题能基本准确回答老师提出的问题程序运行情况10程序运行正确、界面清晰,测试数据设计合理。程序运行正确、界面较清晰,能给出合适的测试数据。综合实践报告20格式规范,层次清晰,设计思想明确,解决问题方法合理,体会深刻。格式较规范,设计思想基本明确,解决问题方法较合理。总分指导教师(签字):注:介于A和C之间为B级,低于C为D级和E级。按各项指标打
3、分后,总分在90100为优,8089为良,7079为中,6069为及格,60分以下为不及格。存储管理-动态分区分配/回收算法的模拟摘要:主存的分配和回收的实现是与住存储器的管理方式有关的。解决多进程如何共享主存空间的问题。当进程运行完时将进程所占的主存空间归还给系统。可变分区存储管理方式,分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行。关键字:内存分配,空闲分区表,进程申请队列一、【实践目的】:1、熟悉主存分配与回收2、理解在不同的存储管理方式,如何实现主存空间的分配与回收3、掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、【实践内容和要求】:
4、主存的分配和回收的实现是与住存储器的管理方式有关的。所谓分配,就是解决多进程如何共享主存空间的问题。所谓回收,就是当进程运行完时将进程所占的主存空间归还给系统。实验要求使用可变分区存储管理方式,分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行,分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法、三种算法来实现主存的分配与回收。同时要求设计一个实用友好的可视化用户界面,并显示分配与回收过程。仿真实现动态可变分区存储管理模拟系统。内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等,并对各种算法进行性能比较。为了实现分区分配,系统中必须配置相应的数据结构,
5、用来描述空闲区和已分配区的情况,为分配提供依据。常用的数据结构有两种形式:空闲分区表和空闲分区链。为把一个新作业装入内存,须按照一定的算法,从空闲分区表或空闲分区链中选出一个分区分配给该作业。三、【实践原理】操作系统是最重要的计算机系统软件,同时也是最活跃的学科之一。计算机系统由硬件和软件两部分组成。操作系统是配置在计算机硬件上的第一层软件,是对硬件的首次扩充。本次课程设计的主要目的是在学习操作系统理论知识的基础上,对操作系统整体的一个模拟。也是对本学期所学知识的一个总体的检测,使理论知识应用到实际的编程中,根据理论的算法来实现具体的编程操作。同时通过本次课程设计加深对操作系统理论知识各个部分
6、管理功能的感性认识,进一步分析和理解各个部分之间的联系和功能,最后达到对完整系统的理解。同时,可以提高运用操作系统知识和解决实际问题的能力;并且锻炼自己的编程能力、创新能力以及开发软件的能力;还能提高自己的调查研究、查阅文献、资料以及编写软件设计文档的能力并提高分析问题的能力。实验中为有效地对内存进行管理,实验中应设计一些数据结构,能有效地进行分配和回收,具体分析如下:1 设计一个空闲分区表,空闲分区表通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲分区低端的空间。2 设计一个内存分区表,可用链表管理,用以表示当前以内存使用情况。3 设计一个进程申请队列以及进程完成后的释放顺序,实现
7、主存的分配和回收。4 要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。 循环首次适应算法的alloc()函数与首次适应算法的alloc()函数区别在于从哪里开始找是否有满足作业要求的空闲区,它是从上次找到的空闲区的下一个空闲分区开始找,只需要改变for循环的条件即可。for(i=s;iN;i+) 最佳适应算法:该算法总是把满足要求、又是最小的空闲区分配给作业。检查空闲区说明表是否有满足作业要求的空闲区,也分为三种情况:大于,等于,小于。若检查到有“等于”的情况,就可以直接分配,若没有,则继续检查是否有“大于”的情况:if(f
8、reeblocki.state=1&freeblocki.size=applyarea) freeblocki.state=0; tag=1; return freeblocki.startaddress; 检查“大于”的情况:先把所有大于所要求的空闲区放入数组,for(i=0;iapplyarea)aj+=i;再从数组中挑出最小的那个:果数组中的元素大于一个,则需要一个个比较过去,然后取出最小的那个分配给作业:if(j1) h=a0; min=freeblockh; for(k=1;kj;k+) h=ak; if(freeblockh.sizemin.size) mid.size=freeb
9、lockh.size; mid.state=freeblockh.state; mid.startaddress=freeblockh.startaddress; freeblockh.size=min.size; freeblockh.state=min.state; freeblockh.startaddress=min.startaddress; min.size=mid.size; min.state=mid.state; min.startaddress=mid.startaddress; min.startaddress=min.startaddress+applyarea; mi
10、n.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果数组中只有一个元素,则直接分配给作业:if(j=1) h=a0; min=freeblockh; min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea; tag=1; return min.startaddress-applyarea; 如果没有满足条件的空闲区,分配不成功,返回-1if(tag=0)return -1;四、【实践环境】(使用的软件)Microso
11、ft Visual C+ 6.0五、【实践设计分析】: 内存分配:动态输入构造空闲区表,并显打印示构造好的空闲分区表。键盘接收内存申请。根据申请,实施内存分配,并返回分配所得内存首址。分配完后,调整空闲分区表(即扣除分配部分),并显示调整后的空闲分区表。若分配失败,返回分配失败信息。内存回收:显示当前的空闲分区表和内存分区表。从键盘接收回收分区的首址与大小,按内存回收的四种情况进行内存回收。显示回收后已调整好的的空闲分区表六、【实践过程和步骤】: 数据结构设计1 空闲分区表的设计,该空闲分区表记录内存中未使用的各个分区,记录内容有未使用分区的大小、首地址,用链表就行管理;相关代码如下: Typ
12、edef struct free Int size; /分区大小 Int address;/首地址 free *next;; 内存分区表设计,用以表示当前内存的使用情况,记录内容已使用分区的大小、首地址,用链表进行管理,相关数据结构如下: Typedef struct map Int size; /分区大小 Int address;/首地址 map *next;; 进程申请队列的设计,用作进程到达的缓冲队列,记录各进程的相关信息,如进程的所需内存的大小、进程名,相关数据结构如下: Typedef struct pro Int size; /分区大小 sring name; pro *next;l 内存分配当有进程进行内存申请时,我们利用首次适应算法从空闲分区链表、找出一块做够大的空间进行分配并对空闲分区和内存分区的相关结点进行处理,若未找到则返回错误信息,相关示意图如下: 图一:内存分配示意图l 内存回收内存的回收存在以下几种情况: 上邻空闲区:合并两分区,删除正回收的节点,改变上邻分区大小为两分区之和 下邻空闲区:合并两分区,删除下邻分区节点,改变正回收节点大小