操作系统课程设计-主存空间的分配与回收.doc

《操作系统课程设计-主存空间的分配与回收.doc》由会员分享，可在线阅读，更多相关《操作系统课程设计-主存空间的分配与回收.doc（40页珍藏版）》请在三一文库上搜索。

1、学校代码：学 号： 200920205003课程设计题 目：主存空间的分配与回收学生姓名： 学 院： 系 别： 专 业： 班 级： 指导教师： 2011年12月30日内蒙古工业大学课程设计任务书（三）学院（系）：信息学院计算机系 课程名称：操作系统课程设计 指导教师（签名）： 专业班级： 软件工程 0902班 学生姓名： 学号： 一、课程设计题目主存空间的分配与回收二、课程设计的目的通过该课程设计使学生理解在不同的存储管理方式下，如何实现主存空间的分配与回收。使学生初步具有研究、设计、编制和调试操作系统模块的能力。 三、课程设计的主要内容和要求（包括原始数据、技术参数、设计要求、工作量要求等）

2、 原始数据：空闲区说明表结构体。 技术参数：Windows XP系统，VC+6.0开发工具。设计要求： 1 设计基于空闲区说明表的可变分区分配与回收算法；2 或设计基于空闲区链表的可变分区分配与回收算法；3 画出以上算法流程图；4 编程实现算法功能；5编写课程设计说明书。 工作量要求：完成以上设计要求中的所有算法功能。四、工作进度安排 周一：布置、讲解题目，收集资料；周二：系统分析，算法设计；周三：编制、调试程序；周四：测试系统，形成设计结论，编写课设报告；周五：系统及材料验收，课设答辩。五、主要参考文献1 张尧学编计算机操作系统教程（第三版）习题解答与实验指导北京:清华大学出版社，20062

3、 汤子瀛主编计算机操作系统（第三版）西安:西安电子科技大学出版社，2001 3 张坤等编操作系统实验教程北京:清华大学出版社，2008审核批准意见系（教研室）主任（签字） 摘要在内存初始化完成以后，内存中就常驻有内核映象（内核代码和数据）。以后，随着用户程序的执行和结束，就需要不断地分配和释放物理页面。内核应该为分配一组连续的页面而建立一种稳定、高效的分配策略。为此，必须解决一个比较重要的内存管理问题，即外碎片问题。频繁地请求和释放不同大小的一组连续页面，必然导致在已分配的内存块中分散许多小块的空闲页面。由此带来的问题是，即使这些小块的空闲页面加起来足以满足所请求的页面，但是要分配一个大块的连

4、续页面可能就根本无法满足。Linux采用著名的伙伴（Buddy）系统算法来解决外碎片问题。但是请注意，在Linux中，CPU不能按物理地址来访问存储空间，而必须使用虚拟地址；因此，对于内存页面的管理，通常是先在虚存空间中分配一个虚存区间，然后才根据需要为此区间分配相应的物理页面并建立起映射，也就是说，虚存区间的分配在前，而物理页面的分配在后，但是为了承接上一节的内容，我们先介绍内存的分配和回收，然后再介绍用户进程虚存区间的建立。分配效率、碎片问题是操作系统中内存分配的两大问题。一个好的分配器应该能够快速地满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。基于数据结构中的伙伴系统的分配与回

5、收思想给出了一个有效的算法。关键字：操作系统 内存分配 首次适应算法 磁盘存储管理目录第一章 课程设计简介11.1 课程设计的目的11.2 课程设计内容2第二章 需求分析32.1 硬件需求32.2 软件需求32.3 设计需求3第三章 概要设计43.1算法设计思想43.2 数据结构的设计5第四章 详细设计64.1 菜单模块64.2 分配方法模块84.2.1首次适应算法分配概念84.2.2 数据流程图84.2.3 核心代码84.3 内存释放模块94.3.1概念94.3.2 释放区与上下临界区的关系94.3.3 数据流程图104.3.4 核心代码11第五章 程序运行问题及解决办法结果135.1 程序

6、运行出现的问题及解决办法问题135.2运行结果截图13六课程总结与体会心得186.1课程设计心得186.2 总结186.3致谢18七参考文献19源代码20内蒙古工业大学课设第一章 课程设计简介1.1 课程设计的目的通过该课程设计使学生理解在不同的存储管理方式下，以及使学生加深对如何实现主存空间的分配与回收原理的理解。也使学生初步具有研究、设计、编制和调试操作系统模块的能力。1.2 课程设计内容编程序实现下述在不同的存储管理方式下的主存空间的分配与回收，其中原始数据设为空闲区说明表结构体(1).设计基于空闲区说明表的可变分区分配与回收算法；(2).或设计基于空闲区链表的可变分区的分配与回收；35

7、第二章 需求分析2.1 硬件需求本系统适用于现用的各种类型的计算机，内存容量建议为128MB以上，不必配备外部附加设备2.2 软件需求VC+6.0开发工具2.3 设计需求 内存的分配与回收是内存管理的主要功能之一。无论采取哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于内否在内存中为他们安排合适的位置。因此，存储管理模块要为每一个并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。但由于作业大大小不一，所以系统为作业分配内存大小不一，在释放时造成系统资源的浪费。因此，采取首次适应算法，以及那少内存的浪费。第

8、三章 概要设计3.1算法设计思想初始化系统的内存分区说明表；输入当前作业或进程的使用内存情况，检索系统内的内存分区说明表，判断是否可分配，也就是查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。使用内存的分配和回收算法进行，完成所有作业或进程的内存使用请求，作业完成后回收其所占用的内存给系统；并可输出查看内存的当前使用状况。例如，某时刻主存空间占用情况如图3-1所示。(1) 为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如表3-1所示。操作系统(10

9、KB)作业1(10KB)作业4(25KB)空闲区1(20KB)作业2(45KB)空闲区2(146KB)起始地址长度状态45K20KB未分配110K146KB未分配空表目空表目空表目010K20K45K65K110K256K3-1主存空间占用情况 表3-1 空闲区说明表其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。状态有： 未分配：该栏目是记录的有效空闲区。 空表目：没有登记信息。由于分区个数不定，所以空闲区说明表中应有足够的空表目项。否则造成溢出，无法登记。同样，再设一个已分配区表，记录作业或进程的主存占用情况。(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出

10、一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应将空闲区一分为二。一个分给作业；另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。(3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区合并的问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A释放区下邻(低地址邻接)空闲区；B释放区上邻(高地址邻接)空闲区；C释放区上下都与空闲区邻接；D释

11、放区与空闲区不邻接。3.2 数据结构的设计3.2.1 区说明表的设计 struct freearea int startaddress; /*空闲区的起始地址号*/int size; /*空闲区的大小*/int state; /*空闲区状态：0为空表目,1为可用空闲块*/freeblockN=100,100,1,10,10,1,300,50,0,20,35,1,250 ，30,1,600,200,0; 说明：设置空闲区为结构体类型，并且为其初始化，构成空闲区表的分区3.2.2 已分配区说明表设计 struct fullareaint address; /*分配作业的首地址*/int sizes

12、; /*分配作业的大小*/fullblockN;说明：设置已分配区说明表为结构体类型，构成已分配区表的分区 第四章 详细设计4.1 菜单模块 为了操作界面的人性化和美观，为模拟系统开辟一个操作菜单，通过switch() case的方法来实现，其核心代码为int start;char t;while(c)system(cls);muen();printf(请选择操作编号:);scanf(%d,&b);switch(b)case 1:system(cls);printf(n系统原有内存空闲区分表和已分配表区如下:nn);order();order1();show();printf(n请输入作业申请

13、量:);scanf(%d,&a);order();start=alloc(a,d);d+;if(start=-1)system(cls);printf(n1 内存中没有符合的空闲区可供分配!等待释放内存中n);Sleep(1*1000);system(cls);show();setfree();break;system(cls);printf(n1 系统采用最佳适应算法正在为作业分配内存中nn);Sleep(1*1000);system(cls);printf(n1 系统为作业分配内存成功!:nn);order();order1();Sleep(1*1000);system(cls);brea

14、k;case 2:system(cls);order();show();setfree();system(cls);order1();for(i=0;i=XK?大于Y置状态为“空表目”作业等待长度=长度XK始址=始址XK将空表目向后移返回登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的主存始址。 4.2.3 核心代码 int alloc(int a,int b) int i,j,tag=0;j=b;for(i=0;ia) freeblocki.startaddress=freeblocki.startaddress+a;freeblocki.size=freeblocki.

15、size-a;fullblockj.address=freeblocki.startaddress-a;fullblockj.sizes=a;tag=1;return freeblocki.startaddress-a;break;elseif (freeblocki.state=1&freeblocki.size=a) freeblocki.state=0;fullblockj.address=freeblocki.startaddress;fullblockj.sizes=a;tag=1;return freeblocki.startaddress;break;if(tag=0)retur

16、n -1;4.3 内存释放模块4.3.1概念当一个作业执行完成时，作业所占用的分区应归还给系统。由于每个作业或进程所用的内存长度不一样而出现大量分散，较小的空闲区。这样造成内存大量的浪费。解决这个办法之一就是在空闲区回收时，把不连续的空闲区集中起来。4.3.2 释放区与上下临界区的关系A释放区下邻(低地址邻接)空闲区：将释放区与下空闲区合并，将其释放区的首地址作为合并区的首地址，合并区的长度为释放区与下空闲区长度之和。B释放区上邻(高地址邻接)空闲区：将释放区与下空闲区合并，将其上临区的首地址作为合并区的首地址，合并区的长度为释放区与下空闲区长度之和。C释放区上下都与空闲区邻接：释放区作为一个

17、新的可用区插入可用表。D释放区与空闲区不邻接：将三个空闲区合并为一个空闲区，新空闲区的首地址为上空闲区的首地址，大小为三个空闲区之和。合并后，取消可用表下空闲区，修改上空闲区的对应项。4.3.3 数据流程图开始S=释放区始址L=释放区长度查空闲区说明表有与释放区的高地址邻接(上邻)的空闲区吗？YN有与释放区下邻的空闲区吗？L=L上邻空闲区长度Y有与释放区下邻的空闲区吗？在空闲区说明表中找一空表目登记：始址=S长度=L状态=未分配YN把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整。把上邻空闲区登记栏中的始址改为S，长度改为LN按地址顺序调整和紧缩空闲区说明表上空闲区首地址为总地址，

18、大小为两个大小之和上空闲区首地址为总地址，大小为两个大小之和把下邻空闲区登记栏中的长度改为：长度=长度L有等待装入的作业吗？Y唤醒等待的作业并返回N返回图3-3 首次适应算法回收框图4.3.4 核心代码voidsetfree() int s,l,i,j,k; /*tagl代表释放区的高地址是否邻接一个空闲区,tag2代表释放区的高低地址是否都邻接一个空闲区,tag3代表释放区的低地址是否邻接一个空闲区*/ printf(nn请输入需要释作业的首地址:); scanf(%d,&s); /*输入释放区的开始地址*/ printf(n输入作业的大小:); scanf( %d,&l);/*输入释放区的

19、大小*/for(k=0;kN;k+)if(fullblockk.address=s)if(fullblockk.sizes=l)fullblockk.address=0;fullblockk.sizes=0;break;elsefullblockk.sizes=fullblockk.sizes-l;break;if(k=N-1)printf(n输入释放作业开始地址不存在，请重新输入!);setfree();return; for(i=0;iN;i+) if(freeblocki.startaddress+freeblocki.size=s&freeblocki.state=1)for(j=i+

20、1;jN;j+)if(freeblockj.startaddress=s+l& freeblockj.state=1)freeblocki.size=freeblocki.size+l+freeblockj.size;freeblockj.state=0;return;freeblocki.size=freeblocki.size+l;freeblocki.state=1;return;elsefor(j=0;jN;j+)if(freeblockj.startaddress=s+l& freeblockj.state=1)freeblockj.startaddress=s;freeblockj

21、.size=freeblockj.size+l;return;elseif(freeblockj.state=0)freeblockj.size=l;freeblockj.startaddress=s;freeblockj.state=1;return;第五章 程序运行问题及解决办法结果5.1 程序运行出现的问题及解决办法问题（1）程序运行没有按预期完成任务，解决办法是每次在对内存的分配和会和回收之前和之后都要对空闲区按地址进行排序（2）程序不能显示作业状况，解决办法是为作业作一个已分配表用来存储作业记录（3）在进行排序时，采用冒泡法进行排序5.2运行结果截图 （1）主菜单（2）载入作业结结果

22、 （1）（2）（3） 分配结果图（4） 模拟系统回收内存（5） 回收结果显示（1）（2）（6） 多分配结果（7） 多回收结果5.8 退出系统六课程总结与体会心得6.1课程设计心得在这次课程设计中，我们的收获应该说是非常大的。开始的时候我们在网上搜索了一些代码。但是这个代码语法本身有问题。但是由于对JAVA的使用不够熟练，所以我们就用了比较熟悉的c语言。整个过程的代码都是我们自己动脑筋写的，最终代码调试运行成功，但是我们还是面临一个很大的问题就是，源程序使用C编写的，我们如何用图形化界面表示出来呢？我们查阅了相关资料并且动手实践，但仍未解决，最后决定不使用图形用户界面。在这次实践中，我们充分的意

23、识到，编程功底的薄弱，只是粗浅的了解了语言，只是会一些语法，在编程思想上，我们显的很弱。在今后的学习中，一定要扩大自己的知识面，如：多从网上寻找可实现的项目，同学之间组成团队，多学习，自己用代码实现；还有就是要精通一们语言，熟练掌握其数据结构，算法思想，以至于能够熟练运用。应该说这是通过我们小组成员的共同努力和动脑完成的，虽然内容并不是很复杂，但是我们觉得设计的过程相当重要，学到了很多。我觉得课程设计反映的是一个从理论到实际应用的过程，但是更远一点可以联系到以后毕业之后从学校转到踏上社会的一个过程。小组人员的配合相处，以及自身的动脑和努力，都是以后工作中需要的。6.2 总结在这次设计中遇到了很

24、多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定距离的。一切问题必须要靠自己一点一滴的解决，而在解决的过程当中你会发现自己在飞速的提升。程序设计是一个很灵活的东西，它反映了你解决问题的逻辑思维和创新能力，是一个设计的灵魂所在。通过这次课程设计我也发现了自身存在的不足之处，虽然感觉理论上已经掌握，但在运用到实践的过程中仍有意想不到的困惑，经过一番努力才得以解决。总之，通过这次课程设计，我真的在实践中学到的不仅是课本知识的巩固和提高，而且还有在实践中使我着手解决不少程序设计的细节问题。而这些问题是我在从低级的程序员向高级程序设计师过度的过程必须要解决的。而我个人认为

25、，我越早接触，越多接触，越快解决对我本人缩短此过程有重要的意义。6.3致谢首先感谢两位马老师在这次课程设计中给予我们的指导和建议，在他的指导下我们顺利的完成了本次课程设计！其次，要感谢我们同学，在我们互相帮助之下，攻克了在课程设计中遇到的一个个难关！七参考文献1. 教材1 张尧学主编计算机操作系统教程（第三版）北京:清华大学出版社，20062. 主要参考书 1 张尧学编计算机操作系统教程（第三版）习题解答与实验指导北京:清华大学出版社，20062 汤子瀛主编计算机操作系统（第三版）西安:西安电子科技大学出版社，2001 3 张坤等编操作系统实验教程北京:清华大学出版社，20084 张丽芬等编操

26、作系统实验教程北京:清华大学出版社，20065 Andrew S.Tanenbaum. Modern Operating Systems, Second Edition.Englewood Cliffs,N.J,Prentice Hall, 20016 屠祁等编.操作系统基础（第三版）北京:清华大学出版社，20007 冯耀霖等编.操作系统.西安:西安电子科技大学出版社，20018 左万历计算机操作系统教程（第二版）北京：高等教育出版社，2004源代码#include#include #define N 6struct freearea/*定义一个空闲区说明表结构,并初始化变量*/ int st

27、artaddress;/*空闲区始址*/int size;/*空闲区大小*/int state;/*空闲区状态：0为空表目,1为可用空闲块*/freeblockN=100,100,1,10,10,1,300,50,0,20,35,1,250,30,1,600,200,0;struct fullareaint address;int sizes;fullblockN;void muen()printf(n*n);printf(* *n);printf(* 1模拟的主存空间的分配与回收1 *n);printf(* *n);printf(* *n);printf(* 1.载入作业 2.回收内存 *n

28、);printf(* *n);printf(* 3.显示分配回收结果 0.退出 *n);printf(* *n);printf(* *n);printf(* *n);printf(*n);void order()int j,i; struct freearea m; for(i=0;iN;i+)for(j=i; jfreeblockj.startaddress)m.startaddress=freeblockj.startaddress;m.size=freeblockj.size;m.state=freeblockj.state;freeblockj.startaddress=freeblo

29、cki.startaddress;freeblockj.size=freeblocki.size;freeblockj.state=freeblocki.state;freeblocki.startaddress=m.startaddress;freeblocki.size=m.size;freeblocki.state=m.state;for(i=0;iN;i+) for(j=0;jN;j+)if(freeblockj.state=0 & freeblockj+1.state=1)m.startaddress=freeblockj.startaddress;m.size=freeblockj

30、.size;m.state=freeblockj.state;freeblockj.startaddress=freeblockj+1.startaddress;freeblockj.size=freeblockj+1.size;freeblockj.state=freeblockj+1.state;freeblockj+1.startaddress=m.startaddress;freeblockj+1.size=m.size;freeblockj+1.state=m.state;void order1()int j,i; struct fullarea m; for(i=0;iN;i+)f

31、or(j=i; jN; j+)if(fullblocki.addressfullblockj.address)m.address=fullblockj.address;m.sizes=fullblockj.sizes;fullblockj.address=fullblocki.address;fullblockj.sizes=fullblocki.sizes;fullblocki.address=m.address;fullblocki.sizes=m.sizes;void show()int i; printf( |n);printf( | 空闲区说明表 | 已分配区表 |n);printf

32、( | | |n); printf( |startsizestate |start size |n); printf( |n);for(i=0;iN;i+) printf( |%3d%3d%3d |%3d %3d |n,freeblocki.startaddress, freeblocki.size, freeblocki.state,fullblocki.address, fullblocki.sizes);printf( | | |n); printf( |n);int alloc(int a,int b) /*定义为作业分配主存空间的函数alloc(),a为作业申请量*/int i,j,

33、tag=0;/* tag为检查是否有满足作业需要的空闲区的标志,0表示满,1表示未满*/j=b;for(i=0;ia) /*检查空闲区说明表是否有满足作业要求的空闲区*/freeblocki.startaddress=freeblocki.startaddress+a;freeblocki.size=freeblocki.size-a;fullblockj.address=freeblocki.startaddress-a;fullblockj.sizes=a;tag=1;/*有满足条件的空闲区时,tag置1*/return freeblocki.startaddress-a;break;elseif (freeblocki.state=