主存空间的分配与回收1.doc

第 12 页 共 28 页华东交通大学理工学院课程设计报告存档资料 成绩： 华东交通大学理工学院课 程 设 计 报 告 书所属课程名称 计算机操作系统 题 目 主存空间的分配与回收 分 院 电 信 分 院 专业班级 计算机科学与技术 学号 学生姓名 指导教师 2012 年 6 月 21 日 第3页 共27页目录第1章 课程设计内容及要求. 第2章 需求分析 .?第3章 概要设计.?第4章 调试分析.?第5章 用户使用说明.第6章 课程设计心得.第7章 参考文献.? 第一章课程设计内容及要求： 主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机的性能。通过本次实验可以帮助理解主存空间的分配与回收的几种算法：掌握最先适应分配算法；掌握最优适应分配算法；掌握最坏适应分配算法。 编程序实现下述在不同的存储管理方式下的主存空间的分配与回收，其中原始数据设为空闲区说明表结构体(1).设计基于空闲区说明表的可变分区分配与回收算法；(2).或设计基于空闲区链表的可变分区的分配与回收； 第二章需求分析： 硬件需求本系统适用于现用的各种类型的计算机，内存容量建议为128MB以上，不必配备外部附加设备 软件需求ubuntu开发工具，vi编译器。 设计需求 内存的分配与回收是内存管理的主要功能之一。无论采取哪一种管理和控制方式，能否把外存中的数据和程序调入内存，取决于内否在内存中为他们安排合适的位置。因此，存储管理模块要为每一个并发执行的进程分配内存空间。另外，当进程执行结束之后，存储管理模块又要及时回收该进程所占用的内存资源，以便给其他进程分配空间。但由于作业大大小不一，所以系统为作业分配内存大小不一，在释放时造成系统资源的浪费。因此，采取首次适应算法，以及那少内存的浪费。 第三章概要设计：算法设计思想初始化系统的内存分区说明表；输入当前作业或进程的使用内存情况，检索系统内的内存分区说明表，判断是否可分配，也就是查看是否有足够的空闲空间，若有，则按需求量分割一部分给作业；若无；则作业等待。随着作业的装入、完成，主存空间被分割成许多大大小小的分区。有的分区被作业占用，有的分区空闲。使用内存的分配和回收算法进行，完成所有作业或进程的内存使用请求，作业完成后回收其所占用的内存给系统；并可输出查看内存的当前使用状况。例如，某时刻主存空间占用情况如图3-1所示。(1) 为了说明哪些分区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，如表3-1所示。操作系统(10KB)作业1(10KB)作业4(25KB)空闲区1(20KB)作业2(45KB)空闲区2(146KB)起始地址长度状态45K20KB未分配110K146KB未分配空表目空表目空表目010K20K45K65K110K256K3-1主存空间占用情况 表3-1 空闲区说明表其中，起始地址指出各空闲区的主存起始地址，长度指出空闲区大小。状态有： 未分配：该栏目是记录的有效空闲区。 空表目：没有登记信息。由于分区个数不定，所以空闲区说明表中应有足够的空表目项。否则造成溢出，无法登记。同样，再设一个已分配区表，记录作业或进程的主存占用情况。(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需求量，这时应将空闲区一分为二。一个分给作业；另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片，尽可能分配低地址部分的空闲区，将较大空闲区留在高地址端，以利于大作业的装入。为此在空闲区表中，按空闲区首地址从低到高进行登记。为了便于快速查找，要不断地对表格进行紧缩，即让“空表目”项留在表的后部。(3) 当一个作业执行完成时，作业所占用的分区应归还给系统。在归还时要考虑相邻空闲区合并的问题。作业的释放区与空闲区的邻接分以下4种情况考虑：A释放区下邻(低地址邻接)空闲区；B释放区上邻(高地址邻接)空闲区；C释放区上下都与空闲区邻接；D释放区与空闲区不邻接。数据结构的设计 区说明表的设计 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; 说明：设置空闲区为结构体类型，并且为其初始化，构成空闲区表的分区已分配区说明表设计 struct fullareaint address; /*分配作业的首地址*/int sizes; /*分配作业的大小*/fullblockN;说明：设置已分配区说明表为结构体类型，构成已分配区表的分区 第四章 调试分析： 分配方法模块 首次适应算法分配概念 首次适应算法要求可用表或自由链按起始地址递增的次序排列。该算法的最大特点是一旦找到大于或等于所要求内存长度的分区，则结束探索。然后该算法从所找到分区中画出所要求的内存长度分配给用户，把余下的部分进行合并（如果有相邻空闲区存在）后留在可用表中，但要修改其相应的表项。 数据流程图开始申请XK主存J=0J=J+1J为空闲区说明表的最后一个表目？查看第J个表目的登记项NN状态为“未分配”吗?Y小于等于长度=XK?大于作业等待Y置状态为“空表目”长度=长度XK始址=始址XK返回将空表目向后移登记已分配区表和空闲区表，输出系统中各数据结构的值。返回分配给作业的主存始址。 内存释放模块概念当一个作业执行完成时，作业所占用的分区应归还给系统。由于每个作业或进程所用的内存长度不一样而出现大量分散，较小的空闲区。这样造成内存大量的浪费。解决这个办法之一就是在空闲区回收时，把不连续的空闲区集中起来。 释放区与上下临界区的关系A释放区下邻(低地址邻接)空闲区：将释放区与下空闲区合并，将其释放区的首地址作为合并区的首地址，合并区的长度为释放区与下空闲区长度之和。B释放区上邻(高地址邻接)空闲区：将释放区与下空闲区合并，将其上临区的首地址作为合并区的首地址，合并区的长度为释放区与下空闲区长度之和。C释放区上下都与空闲区邻接：释放区作为一个新的可用区插入可用表。D释放区与空闲区不邻接：将三个空闲区合并为一个空闲区，新空闲区的首地址为上空闲区的首地址，大小为三个空闲区之和。合并后，取消可用表下空闲区，修改上空闲区的对应项。数据流程开始图S=释放区始址L=释放区长度查空闲区说明表有与释放区的高地址邻接(上邻)的空闲区吗？YN有与释放区下邻的空闲区吗？L=L上邻空闲区长度Y有与释放区下邻的空闲区吗？在空闲区说明表中找一空表目登记：始址=S长度=L状态=未分配YN把上邻空闲区登记栏中的状态置为“空表目”，且将空表目向后调整。把上邻空闲区登记栏中的始址改为S，长度改为LN按地址顺序调整和紧缩空闲区说明表上空闲区首地址为总地址，大小为两个大小之和上空闲区首地址为总地址，大小为两个大小之和把下邻空闲区登记栏中的长度改为：长度=长度L返回N有等待装入的作业吗？Y唤醒等待的作业并返回图3-3 首次适应算法回收框图 第 12 页 共 28 页 华东交通大学理工学院课程设计报告第五章用户使用说明： 从程序的运行过程来看内存分配与回收的各项功能和分配后的结果显示，回收的结果显示，作业载入的过程和显示结果。运行结果截图：（1）在vi编辑器中填写的代码（2） 分配与回收的主界面（3） 作业载入和申请（4） 分配中（5） 分配完成（6） 输入作业大小（7） 退出界面程序代码：#include#include#include#include#include#include#define N 6struct 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;struct fullareaint address;int sizes;fullblockN;void menu()printf(n*n);printf(* *n);printf(* 1 模拟的主存空间的分配与回收 1 *n);printf(* *n);printf(* *n);printf(* 1.载入作业 2.回收内存 *n);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=freeblocki.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.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+)for(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( | | |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,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=1&freeblocki.size=a) freeblocki.state=0;fullblockj.address=freeblocki.startaddress;fullblockj.sizes=a;tag=1;/*有满足条件的空闲区时,tag置1*/return freeblocki.startaddress;/*返回为作业分配的主存地址*/break;if(tag=0)return -1;void setfree() int s,l,i,j,k; /*tagl代表释放区的高地址是否邻接一个空闲区,tag2代表释放区的高低地址是否都邻接一个空闲区,tag3代表释放区的低地址是否邻接一个空闲区*/ printf(nn请输入需要释作业的首地址:); scanf(%d,&s); /*输入释放区的开始地址*/ printf(n输入作业的大小:); scanf( %d,&l);/*输入释放区的大小*/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+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.size=freeblockj.size+l;return;elseif(freeblockj.state=0)freeblockj.size=l;freeblockj.startaddress=s;freeblockj.state=1;return;void main()int i,b,a,d=0,c=1;int start;char t;while(c)system(clear);menu();printf(请选择操作编号:);scanf(%d,&b);switch(b)case 1:system(clear);printf(n系统原有内存空闲区分表和已分配表区如下:nn);order();order1();show();printf(n请输入作业申请量:);scanf(%d,&a);order();start=alloc(a,d);d+;if(start=-1)system(clear);printf(n1 内存中没有符合的空闲区可供分配!等待释放内存中n);sleep(10);system(clear);show();setfree();break;system(clear);printf(n1 系统采用最佳适应算法正在为作业分配内存中nn);sleep(10);system(clear);printf(n1 系统为作业分配内存成功!:nn);order();order1();sleep(5);system(clear);break;case 2:system(clear);order();show();setfree();system(clear);order1();for(i=0;iN;i+)if(fullblocki.address=0)d=i;break;printf(n1 系统正在回收为作业分配的内存中nn);sleep(10);system(clear);printf(n1 系统回收内存成功!:nn);order();sleep(5);system(clear);break;case 3:system(clear);t=getchar();printf(n);order();show();printf(n1 按回车键返回主菜单nn);if(t=getchar()=n)break;case 0:if(b=0)c=0;break;default: system(clear);printf(n输入有误,请重新选择!n);sleep(5);system(clear); 第六章课程设计心得： 虽然我们做过很多次课程设计了，但是感觉自己还有好多需要学习的地方，接到题目要求时，设计大体的框架，考虑好所使用的数据结构，然后用高级编程语言分模块的把架子的思路编写出来，调试，运行，再看看是不是符合题目的要求，上网找些资料，看看想想是不是要提高要求，才可以满足实际的需要，最后把收集的