《贮存空间的分配与回收》由会员分享，可在线阅读，更多相关《贮存空间的分配与回收（13页珍藏版）》请在金锄头文库上搜索。
1、05k10k14k26k32k128k四、四、 主存储器空间的分配和回收主存储器空间的分配和回收1实验目的实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。主存的分配和回收的实现虽与主存储器的管理方式有关的，通过本实验帮助学生理解在不同的存储管理方式下应怎样实现主存空间的分配和回收。2实验内容实验内容本实验模拟在两
2、种存储管理方式下的主存分配和回收。3 3实验说明实验说明在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。在可变分区管理方式下采用最先适应算法实现主存分配和实现主存回收。可变分区方式是按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。例如：操作系统作业 1作业 3空闲区作业 2空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：起 址长 度状
3、态第一栏14 K12 K未 分 配第二栏32 K96 K未 分 配空 表 目空 表 目其中，起址指出一个空闲区的主存起始地址。长度指出从起始地址开始的一个连续空闲的长度。状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效） ，可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态） 。由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。上述的这张说明表的登记情况是按提示（1）中的例所装入
4、的三个作业占用的主存区域后填写的。(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。为了方便查找还可使表格“紧缩” ，总是让“空表目”栏集中在表格的后部。(3) 采用最先适应算法（顺序分配算法）分配主存空间。按照作业的需要量，查空闲区说明表，顺序查看
5、登记栏，找到第一个能满足要求的空闲区。当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。最先适应分配算法如图 4-1。(4) 当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。例如，在提示（1）中列举的情况下，如果作业 2 撤离，归还所占主存区域时，应与上、下相邻的空闲区一起合成一个大的空闲区登记在空闲区说明表中。归还主存时的回收算法如图 4-2。4 4实验步骤实验步骤本次实
6、验中需要模拟完成采用最先适应算法来分配主存空间以及释放主存空间，因此在实验需要建立一张空闲分区表和一张已分配空间表。采用结构体类型来存放各分区的信息，定义如下： struct Block /空闲链结构体 string name; /作业名 int address; /分区首地址 int size; /分区大小 int state; /分区转态 struct Block *next; /前向指针 struct Block *front; /后向指针 ; struct Used /已分配分区结构体 Block *usedArea; Used *next; ;在实验中同时也设置了子函数用来显示现在的
7、空闲链表结构体和已分配区结构体中的内容以方便使用。其程序代码如下：void Display(Block *p,Used *q) /打印信息的函数 coutusedArea-nameusedArea-addressusedArea-sizenext; coutaddresssizefront; 此次实验中的重点内容便是如何进行内存的分配和回收，通过课本知识的学习，明白了他们的“工作”原理，即是从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。（1）UNIX 空闲分区表
8、数据结构：空闲分区表中的空闲分区要按地址从低到高连续排序，最后一个空闲分区中 m_size 为 0 表示以上表目空白。空闲分区表起始地址为 coremap。流程图如下图：申申从从是是本本m.sizeu.sizem.size-u.sizesize从该分区中划出从该分区中划出u.size继继将将将将返返YNNYNY返返（2）当一个作业运行完毕释放内存时，系统根据释放区的首地址，从空闲区说明表中找到相应的插入点，此时可能出现下列四种情况（如下图所示，其中F1，F2 表示回收区的前、后空闲区）：i 当回收区只与插入点的前一个分区 F1 相领接时，应将回收区与插入点的前一个分区合并，不再为回收区分配新的
9、表目，而只需修改 F1 分区表目的大小m_size 即可。 F1 回收区ii 当回收区只与插入点的后一个分区 F2 相领接时，将把两个空闲区合并，修改F2 分区的表目，把回收区的起址作为新空闲区的起址，大小为两个分区之和。iii 当回收区既不与 F1 领接，又不与 F2 领接时（如 A） ，应为回收区单独建立一项新表目，填写回收区的起址和大小，并根据其起址，插入到空闲区说明表的适当位置。其程序代码如下： void Recycle(string freeName) /回收分区的函数 Used *p=usedHead- next,*r=usedHead;Block *q; while(p!=NUL
10、L) if(p-usedArea- name=freeName)/找到同名的作业 后，再分四种情况讨论F1 回收区F2q=p-usedArea;int flag1=1,flag2=1;Block *p1=freeHead-front;Block *pfront,*pnext;while(p1-addressaddress) if(p1-address+p1-size=q- address)flag1=0;pnext=p1;p1=p1-front; if(q-address+q-size=p1- address)flag2=0;pfront=p1;if(flag1=0)if(flag2=0)pn
11、ext-front =pfront- front;pnext-size=pnext-size + q-size + pfront-size;if(pfront-front!=NULL)pfront -front - next=pnext;r-next =p-next;else pnext -size +=q- size;r-next =p-next ; elseif(flag2 =0)pfront -address -=q-size;pfront -size +=q-size ;r-next =p-next ;elseBlock *temp=freeHead; while(temp-addre
12、ssaddress )temp=temp-front;q-front =temp;q-next =temp-next ;q-next-front =q;temp-next =q;q-state =0;r-next =p-next ; break;r=p;p=p-next ; 流程图如下图：所释放的可用区与 后一可用区合并与后一可用分区 相邻且不为空？将该表目以上的所有表 目上移一格，并插入新 释放的可用区表目 返回将该表目以上的所 有表目下移一格所释放可用 区的 size=0 ?与后一可用区合并与后一可用 去相邻？把所释放的可用区与前一分区合并 回收顺序地检索可用资源表直至找到某表目的 m.a
13、ddraa 或 m.size=0不是第一个表目且与 前一个可用区相邻？回收内存流程图回收内存流程图5 5实验结果实验结果（1） 系统初始时未分给作业分配内存，此时分别向系统中请求分配四个作业系统初始时未分给作业分配内存，此时分别向系统中请求分配四个作业aaa、bbb、ccc、ddd（四个作业满足分配条件）（四个作业满足分配条件）（2） eee 申请资源不能得到满足等待申请资源不能得到满足等待（3）回收）回收 ccc 占用的资源占用的资源（4）显示此时此刻分配和未分配的情况，结果显示）显示此时此刻分配和未分配的情况，结果显示 ccc 占用的资源已经被回收占用的资源已经被回收（5）任务）任务 ff
14、f 可以申请资源可以申请资源（6）找到空闲资源，并为任务）找到空闲资源，并为任务 fff 分配资源分配资源附：实验源程序：#include #include using namespace std; struct Block /空闲链结 构体 string name; /作业名 int address; /分区首地址 int size; /分区大小 int state; /分区转态 struct Block *next; /前向指针 struct Block *front; /后向指针 ; struct Used /已分配 分区结构体 Block *usedArea; Used *next;
15、; Block *freeHead; / 带表头附加节 点的空闲链头指针 Used *usedHead; /带表头附加结 点的已分配分区头指针 bool InitValue() /初始化函数 coutsize=0; freeHead-next=NULL; freeHead-state=1; usedHead=new Used; Block *p=new Block; p-address=0; usedHead-usedArea=p; usedHead-next=NULL; Block *temp=new Block; couttemp-size; temp-address=0; temp-state =0; temp-next=freeHead
