动态分区管理的主存分配模拟设计最优适应法、最差适应法.doc

武汉理工大学操作系统课程设计说明书学 号： 0120910340918课 程 设 计题 目动态分区管理的主存分配模拟设计-最先适应法、最优适应法学 院计算机科学与技术学院专 业计算机科学与技术专业班 级0909姓 名梁芳平指导教师汪祥莉 2011年1月8日课程设计任务书学生姓名： 梁芳平 专业班级： 0909 指导教师： 汪祥莉 工作单位： 计算机科学与技术学院 题 目: 动态分区管理的主存分配模拟设计-最先适应法、最优适应法初始条件：1预备内容：阅读操作系统的内存管理章节内容，理解动态分区的思想，并体会各分配算法的具体实施方法。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他的其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录1.目的与功能32. 需求分析，数据结构或模块说明32.1需求分析32.2数据结构的定义62.3模块说明63.源程序的主要部分93.1链表输出函数93.2 最先适应法103.3最优适应算法124.运行结果与运行情况分析154.1最先适应法154.2最优适应法164.3进程所需空闲块太大时174.4错误输入的处理185.自我评价与总结185.1设计哪些地方做得比较好或比较出色185.2什么地方做得不太好，以后如何改正185.3从本设计得到的收获（在编写，调试，执行过程中的经验和教训）185.4完成本题其他方法195.5对实验题的评价和改进意见196.参考文献191.目的与功能采用指定算法模拟动态分区管理方式的主存分配。能够处理以下的情形： 随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址Len 分区长度；Process 如果使用，使用的进程号，否则为0 主存分配函数实现寻找空闲区、空闲区表的修改、已分配区表的修改功能；2. 需求分析，数据结构或模块说明2.1需求分析计算机系统由两部分组成：硬件和软件。其中，硬件由中央处理器、存储器、输入输出设备等组成，它构成了系统本身和用户作业赖以生存的物质基础和工作环境。无任何软件的计算机称为裸机，而操作系统则是包在裸机外层的最基础的系统软件，引入操作系统的目的可以从三个方面来进行考虑：为用户提供最好的服务，构建一个用户和计算机和谐之间的和谐交互环境；合理地组织计算机工作流程，管理和分配计算机系统中的硬件及软件资源，使之能为多个用户高效率地共享。因此，操作系统是计算机资源的管理者；给计算机系统的功能扩展提供支撑平台，使之在追加新的服务和功能时更加容易和不影响原有的服务与功能。所以，计算机对操作系统的需求是与其对应的功能的实现和用户简单操作的需要密切相连的。操作系统功能有：进程管理、处理机的调度、存储管理、文件系统的管理和设备的管理，在此次试验我做的是动态分区的存储管理，所以主要讨论的是操作系统的内存功能的实现这一方面。存储器是计算机的重要组成部分,存储空间是操作系统管理的宝贵资源,虽然其容量在不断扩大,但仍然远远不能满足软件发展的需要。对存储资源进行有效的管理,不仅关系到存储器的利用率,而且还对操作系统的性能和效率有很大的影响。操作系统的存储管理的基本功能有：存储分配、地址转换和存储保护、存储共享、存储扩充。存储分配指为选中的多道运行的作业分配主存空间；地址转换是把逻辑地址空间中的用户程序通过静态重定位或动态重定位转换和映射到分给的物理地址空间中,以便用户程序的执行；存储保护指各道程序只能访问自己的存储区域,而不能互相干扰,以免其他程序受到有意或无意的破坏；存储共享指主存中的某些程序和数据可供不同用户进程共享。存储分配有：分区管理，分页管理和段式管理，分区又分为静态分区和动态分区。单道系统中,一旦一个程序能装入主存,它将一直运行直到结束。如果程序长度超出了主存的实际容量,可以通过覆盖和交换的技术获得解决。更多的操作系统支持多个用户进程在主存同时执行,能满足多道程序设计需要的最简单的存储管理技术是分区方式。可变分区的分配算法包括：最先适应、最佳适应、最坏适应等分配算法。(1)、静态分区内存示意图 (2)动态分区内存分配示意图分区存储管理是满足多道程序设计的最简单的一种存储管理方法，它允许多个用户程序同时存在系统内存中，即共享内存空间。分区的原理是把内存分为一些大小相等或不等的分区(partition)，除操作系统占用一个分区外，其余分区用来存放每个进程的程序和数据。特点是适用于多道程序系统和分时系统支持多个程序并发执行难以进行内存分区的共享。问题是可能存在内碎片和外碎片。动态分区相对静态分区来讲又有它独到的一些优点：首先，固定分区不存在内碎片，因为它是在进程创建申请存储成功后给进程分配内存，所以不会产生内碎片，但是可能有外碎片；其次，动态分区是动态的，相对静态分区更具有灵活性，但是从设计方面来说更为复杂。 在动态分区的三种算法中，最先匹配法(first-fit)（如图a）：按分区起始地址的递增次序，从头查找，找到符合要求的第一个分区。该算法的分配和释放的时间性能较好，一旦找到大于或等于所要求内存长度的分区，则结束探索。最佳匹配法(best-fit)：按分区大小的递增次序，查找，找到符合要求的第一个分区。当申请空闲区时，存储管理程序从表头开始查找，当找到一个满足要求的空闲区时，停止查找，此时的空白区必定是最合适的，因为它是最接近于要求的大小。最坏匹配法(worst-fit)：按分区大小的递减次序，从头查找，找到符合要求的第一个分区。（本次课程设计不讨论最坏适应算法）找到最大的空闲分区 。比较最先适应算法和最佳适应算法，可以看出。从搜索速度上看，最先适应算法具有最佳性能。从回收过程来看，最先适应法也是最佳的。它的另一个优点就是尽可能地利用了低地址空间。从而保证高地址有较大的空闲区来放置要求内存过多的进程或作业。最优适应算法每次找到的是最合适该进程的内存块大小，在内存的利用方面，最优适应算法是最佳的，但相对来说，最优适应算法更容易产生外碎片。分配时候应该注意。 （a）.最先适应算法内存分配示意图 （b）.最优适应算法内存分配示意图2.2数据结构的定义链表节点的定义：typedef struct node int start; int length; int state; int program;int end; struct node *next;Node,*pNode;常变量的定义：const int Max=2552.3模块说明创建两个节点p,temp,p=temp=head-next 本次程序设计主要由3个函数模块组成，第一个函数实现打印链表所有节点的功能，void PrintMemoryState(Node *)；函数的形参为pNode节点指针，void表示函数的返回值为空，该函数的主要思想是：用一个do while语句将链表中节点包含的数值打印出来，这些数值包括内存块初始地址start,内存块长度Length，内存块尾地址end，内存块状态state；这些数值都是被刺课程设计要求输出到屏幕用以给用户查看空闲队列的使用情况和进程占用内存的实际情况，具体算法流程图见下图(a)： p-end=p-start+p-length,p=p-next N p=null? Y打印temp中的值，temp=temp-next Ntemp=null? Y 结束 (a).打印链表函数示意图 第二个函数是实现最先适应算法的，函数定义为：void FirstFit(Node *)；函数的形参为pNode节点指针，void表示返回值为空，函数的主要思想为：最先适应算法是在所给的空闲链表中寻找符合进程要求的内存大小的空闲块，3个进程的内存大小需求需要用户自己输入，然后程序进行查找匹配，找到后变将空闲块分配给进程，这里在查找的时候会出现五种情况：(a)如果空闲块的状态state=1；表明这个内存块正在被其他进程使用，申请不成功，则继续往下寻找；(b)如果空闲块长度lengthnext求出节点最大值，判断最大值是否满足要求 Y last=last-next Y ai-lenlast-len N N Nai-len=last-len last-state=1 Y ai-lenlen N修改原空闲块节点，添加新节点。 Y 结束 (b)最先适应法的工作流程图 第三个函数是实现最佳适应算法的，函数定义为：void BestFit(Node *head)。函数形参为pNode节点指针，void表示无返回值；函数的主要思想为：最优适应法是从空闲链表中寻找最符合进程要求的空闲块；何为最符合？就是在所有满足进程所需值的空闲块中找出最小的那个空闲块分配给进程，在查找的时候也会出现下面的五种情况：(a)如果空闲块的状态state=1；表明这个内存块正在被其他进程使用，申请不成功，则继续往下寻找。(b)如果空闲块长度lengthnext求出节点最大值，判断最大值是否满足要求 Y last=last-next Y ai-lenlast-len N N Nai-len=last-len last-state=1 Y ai-lenlen N Y 为其找到最小长度last-lenlast-len是否为最小的 N 结束 Y 3.源程序的主要部分3.1链表输出函数用于输出链表所有内存块的特征值。void PrintMemoryState(Node *head) int state=0; Node *temp=(Node *)malloc(sizeof(Node);Node *p=(Node *)malloc(sizeof(Node); p=temp=head-next;do p-end=p-start+p-length; p=p-next;while(p!=NULL); printf(ttProcessttFaddresstLentEaddresstStaten);do printf(t%8dt%8dt%8dt%8dt%8dn,temp-program,temp-start,temp-length,temp-end,temp-state); temp=temp-next; while(temp!=NULL); printf(t%8dt%8dn,Max,0); return ;3.2 最先适应法最先适应法，先创建一个随机进程p，再逐个遍历内存单元，如果发现该内 存单元是空闲的并且它的大小比进程申请长度大，则对它进行分配。void FirstFit(Node *head)/装入作业,最先适应法 int flag=0;/int sum=0; int lengthtemp;int a10;int k;int c10; Node *last=(Node *)malloc(sizeof(Node); Node *Task=NULL; Node *newFree=NULL;cout请输入进程数:k;cout输入进程编号endl;for(int i=0;ici;cout请分别输入需要分配内存的k个作业内存长度:endl;for(i=0;iai;for(i=0;inext;while(Task!=NULL)if(Task-state=1)Task=Task-next;elsebn=Task-length;Task=Task-next;n+;delete Task;/把各个length装入数组Bsum=b0;for(int j=0;jn;j+)if(sumsum)cout第i+1个作业过长，无法装入 next;while(last!=NULL)if(last-state=1)last=last-next;continue;/首先判断占用情况，如果被占用则查看下一个内存块elseif(last-length=ai)last-state=1;flag=1;last-program=ci;goto B;/等于的话直接装入if(last-lengthai)lengthtemp=last-length;last-length=ai;last-state=1;last-program=ci;newFree=(Node *)malloc(sizeof(Node);newFree-next=last-next;newFree-start=last-start+last-length;newFree-length=lengthtemp-last-length;newFree-state=0;newFree-program=0;last-next=newFree;/成功插入newFree节点flag=1;goto B;if(last-lengthnext;continue;/else结束 /while 结束B:i+; if(flag=0) printf(所有请求进程的所需内存长度太长，不能装载。!n); exit(-1);3.3最优适应算法最优适应算法扫描空闲链表，找出所有满足要求的空闲块，然后比较找出最小长度的空闲块。void BestFit(Node *head)/装入作业,最优适应法 int k; int lengthtemp;int a10;int c10; Node *last=(Node *)malloc(sizeof(Node); Node *newFree=NULL;Node *H=NULL;cout请输入进程数：k;cout请输入进程的编号：endl;for(int i=0;ici;cout请分别输入需要分配内存的k个作业内存长度:endl;for(i=0;iai;for(i=0;inext;Task=last;p=head-next;H=head-next;while(H!=NULL)if(H-state=1)H=H-next;elsebn=H-length;H=H-next;n+;delete H;/把各个length装入数组Bsum=b0;for(int j=0;jn;j+)if(sumsum)cout第i+1作业过长，无法装入 state=1)last=last-next;elseif(ailast-length)last=last-next;else if(ai=last-length)last-state=1;last-program=ci;goto C;else if(ailength)Task=last;if(d=0)p=Task;d+;if(p-lengthTask-length)p=Task;last=last-next;lengthtemp=p-length;p-length=ai;p-state=1;p-program=ci;newFree=(Node *)malloc(sizeof(Node);newFree-next=p-next;newFree-start=p-start+p-length;newFree-length=lengthtemp-p-length;newFree-state=0;newFree-program=0;p-next=newFree;/成功插入newFree节点C: i+;4.运行结果与运行情况分析4.1最先适应法 结果如图(a): (a)最先适应法结果图示说明：choice选择时选1，输入进程数目：3，输入3个进程的编号：1,2,3；输入3个进程所需内存的长度：20、30、80。程序运行结果如上图所示：1号进程申请长度为20的空闲块，则搜索链表发现第一个空闲块30满足要求，则把该空闲快分配给进程1；由于空闲块长度大于进程所需值，则此快一分为二，结果如上图所示，2号和3号进程的分配与1号进程的分配相类似，在此不再赘述。4.2最优适应法结果如图(b): (b)最优适应法结果图示 说明：在choice选择中输入数值2选择最优适应法；输入你要的进程数：2；输入这2个进程所需要的内存长度：20,40；然后程序开始运行；并将对应的结果输出到屏幕上，图如上。在进程1申请内存块时，链表启动搜索，首先找到的是第一个空闲块长度为30满足要求，但这是不是所有满足要求的空闲块中最小的那块呢？是不是最优的？还不能肯定，则继续向下搜索，找到了第二个空闲块长度刚好20，则这就是最优的，搜索结束，将此空闲块分配给1进程，然后对第2个进程进行查找分配，思想是一样的。4.3进程所需空闲块太大时结果如图(c): (c)空闲块过大图示4.4错误输入的处理结果如图(d): (d)错误输入结果示意图5.自我评价与总结5.1设计哪些地方做得比较好或比较出色本次课程设计中，实验代码能够满足课程设计任务书上所给出的要求，如随机出现的进程i申请jKB内存，程序能判断是否能分配，如果能分配，要求输出分配的首地址Faddress，并要求输出内存使用情况和空闲情况。内存情况输出的格式为：Faddress该分区的首地址；Eaddress该分区的尾地址，Len 分区长度；Process 如果使用，使用的进程号，否则为0。这些度能够在程序中得到实现，实验中最主要的还是链表的定义和使用，寻找和分配内存时能够较好地实现最先适应算法和最佳适应算法。5.2什么地方做得不太好，以后如何改正本次课程设计虽然能够较好地完成要求，但是仍然存在一些不足与缺陷，在这次实验中，最优适应算法的对空闲块链表的排序有着不一样的要求，操作系统教材中规定最优适应算法的空闲块链表是按照空闲块从小到大的顺序进行排列的。这样就可以简化在void Bestfit(Node *head)中的算法得复杂性，提高整个程序的执行效率和性能。5.3从本设计得到的收获（在编写，调试，执行过程中的经验和教训） 在编写的过程中，我认识到从空白区中寻找空闲空间是关键。另外采用C+自带的容器可以很大程度上方便程序的编写。在模拟过程中，要充分理解操作系统教程上关于动态分区法、最先适应法、最坏适应法的概念，只有充分理解了它们的工作流程，才能编写出