《实验三存储管理.doc概要11835.pdf》由会员分享，可在线阅读，更多相关《实验三存储管理.doc概要11835.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实 验 报 告 实验名称：存储管理 任课教师：冯霞 学 号：100341328 姓 名：魏然 完成日期：2012-12-5 一、实验目的：深入了解采用可变分区存储管理方式的内存分配回收的实现。二、实验内容：编写程序完成可变分区存储管理方式的内存分配回收。实验具体包括：首先确定内存空间分配表；然后采用最优适应算法完成内存空间的分配和回收；最后编写主函数对所做工作进行测试。可变分区管理方式预先不将内存划分成几个区域，而将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小查询内存内各个空闲区，当从内存空间中找到一个大于或等于该作业大小的内存空闲区时，选
2、择其中一个空闲区，按作业需求量划出一个分区装入该作业。作业执行完后。它所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。实现可变分区的分配和回收，主要考虑的问题由三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用区域；第二，在设计的数据表格基础上设计内存分配算法；第三，在设计的数据表格基础上设计内存回收算法。首先，考虑第一个问题：设计记录内存使用情况的数据表格，用来记录空闲区和作业占用区域。由于可变分区的大小时由作业需要量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能
3、发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录已分分区和空闲区，酒水使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，经该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要时对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“已分分区表”；一张是记录空
4、闲区的“空闲区表”。这两张表的实现方法一般有两种：一种时链表形式，一种时顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论时“已分分区表”还是“空闲分区表”都有空闲栏目。“已分分区表”中除了分区起始地址、长度外，至少还要有一项“标志”，如果时空闲栏目，内容为空，如果为某个作业占用分区的登录项，内容为改作业的作业名；“空闲分区表”中除了分区其实地址、长度外，也有一项“标志”，如果时空闲栏目，内容为空，如果为某个空闲区的登机箱，内容为“未分配”。在世纪系统中，这两个表格的内容可能还要多，实验中仅仅使用上述必须的数据。当要装入一个作业时，从空闲区表中查找标志为“
5、未分配”的空闲区，从中找出一个能容纳该作业的空闲区。如果找到的空闲区正好等于改作业的长度，则把该分区全部分配给作业。这时应该把该空闲区登记栏中的标志改为“空”，同时，在已分配区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长度和作业名。如果找到的空闲区大于作业长度，则把空闲区分两部分，一部分用来装入作业，另外一部过分仍为空闲区，这是只要修改原空闲区的长度，且把新装入的作业登记到已分配区表中。实验中内存分配算法采用“最有适应”算法。最优适应算法是按作业要求挑选一个能满足作业要求的最小空闲区，这样保证可以不去分割一个大的区域，使装入大作业时比较容易得到满足。但是最优适应算法容易
6、出现找到的一个分区可能只比作业所要求的长度略大一点的情况，这时，空闲区分割后剩下的空闲区就很小，这种很小的空闲区往往无法再使用，影响了内存的使用。为了在一定程度上解决这个问题，如果空闲区的大小比作业要求的长度略大一点，不再将空闲区分成已分分区和空闲区两部分，而是将整个空闲区分配给作业。在实现最优适应算法时，可把空闲区按长度以递增的方式登记在空闲区表中。分配时顺序查找空闲表，查找到的第一个空闲区就是满足作业要求的最小分区。这样查找速度快，但是为使空闲区按长度以递增顺序登记在空闲表中，就必须在分配回收时进行空闲区表的调整。空闲区表调整时移动表目的代价要高于查询整张表的代价，所以实验中不采用空闲区有
7、序登记在空闲区表中的方法。可变分区方式下回收内存空间时，应该检查是否有与归还区相邻的空闲区，若有，则应该合并成一个空闲区。一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区又无下邻空闲区。在实现回收时，首先将作业归还的区域在已分配表中找到，将该栏目的状态变为“空”；然后，检查空闲区表中标志为“未分配”栏目，查找是否有相邻空闲区；最后，合并空闲区，修改空闲区表。开始作业 J申请 xk大小的内存空间I=0;k=ii是空闲区表中一栏（i=m）?第i栏空闲区为第一个满足需求的或第 i栏空闲区长度小于第k栏空闲区长度？i=i+1是否找到满足需求的分区 k
8、？主存分配失败结束第k栏长度-作业需求=minsize分配整个分区：第k栏状态为“空”ad=第k栏起始地址 xk=第k栏长度切割空闲区：第k栏长度减去 xk，ad=第k栏起始地址-第k栏长度k=ii=0i=i-1第i栏是已分配区表中一栏且第 i栏状态不为空？第i栏是否已为分配表中的一栏？空闲区表第k栏状态为空？填写已分分区表：第j栏其实地址=ad第j栏长度=xk第j栏状态=作业名 J空闲区表状态未分配空闲区表第k栏长度家 xk已分分区表长度不足，分配失败结束NYYYNNYNNNYYNN图 1 可变分区最优分配算法流程图 开始作业归还空间s=0已分分区表第s栏状态为作业J（s=n）s为已分配区表
9、中一 栏？S=已分分区表第s栏起始地址L=已分分区表第s栏长度已分分区表第s栏状态为空假设下邻空闲区在第j栏j=-1假设上邻空闲区在第k栏k=-1i=0第i栏不是空闲区表中一栏或回收分区上下邻空闲区均找到？第i栏状态为“为配”？第i栏为回收分区的下邻？第i栏为回收分区的上邻？s=s+1未找到作业，回收失败结束i=i+1j=ij=i回收分区有上邻居？回收分区有下邻？回收分区有下邻？和上下邻三项合并：第k栏长度=第k栏长度+第j栏长度+L第j栏状态=“空”t=0t=t+1第t栏是空闲区表中非空栏？和上下邻合并：第k栏长度=第k栏长度+L和下邻合并：第j栏长度=第j栏长度+L第j栏起始地址=S第t栏
10、是空闲区表中一栏？已分分区表第s栏状态为 J：空闲区表长度不足，回收失败归还分区填入空闲区表：第t栏起始地址=S第t栏长度=L第t栏状态=“未分配”结束NYYNNYNNYYNYYYNNNYYNNY图 2 可变分区回收流程图 三、实验结果与结论：图 3 插入 4 个作业 图 4 分配后显示“空闲区表”和“已分分区表 图 5 回收作业 a，并显示内存 图 6 回收全部作业，并显示内存 图 7 退出 四、过程分析与建议：通过本次实验实现了操作系统内存的分配与回收，将内存除操作系统占用区域外的空间看做一个大的空闲区，当作业要求装入内存时，根据作业需要的内存大小查询空闲分区表，找一块合适的区域予以分配。
11、通过实验使我加深了对内存分配与回收的理解，巩固了课本中的理论知识。程序源代码如下：#include stdio.h#include stdlib.h#include conio.h#define n 10/假定系统允许的最大作业数为 n#define m 10/假定系统允许的空闲区表最大为 m#define minisize 100 struct float address;/起始位置 float length;/长度，字节 int flag;/标志，0 为未占用 used_tablen;struct float address;/起始位置 float length;/长度，字节 int fl
12、ag;/1 可以被分配，0 不能被分配 free_tablen;void allocate(char J,float xk)int i;int k=-1;float ad;for(i=0;i=xk&free_tablei.flag=1)/flag=1 表示空闲可用 if(k=-1|free_tablei.lengthfree_tablek.length)/k=-1 表示第一个，现在要找符合条件的最小的 k=i;if(k=-1)printf(无可用空闲区n);return;if(free_tablek.length-xk=minisize)/如果剩余量不大于最小值 free_tablek.fla
13、g=0;/将空闲区的标记设置成空闲 ad=free_tablek.address;/将空闲表中找到的那个最适合的区域的地址计入 ad xk=free_tablek.length;/长度计入 else/如果大于最小值 free_tablek.length=free_tablek.length-xk;/空闲表变成原来长度减作业所占长度 ad=free_tablek.address+free_tablek.length;/地址开始位置从原来位置变为原来位置加作业长度 i=0;/把 i 置为初始值 while(used_tablei.flag!=0&i=n)/如果超过了最大作业长度 printf(无表
14、目填写已分分区，错误n);if(free_tablek.flag=0)/如果前面找到的是整个空闲区 free_tablek.flag=1;/将这个空闲区标识设为 1 else/如果不是整个空闲区 free_tablek.length=free_tablek.length+xk;/就增加空闲区的长度为原长+作业长 return;else/修改整个分区表 used_tablei.address=ad;/将作业表当前位置的地址变为作业地址 used_tablei.length=xk;/将作业表当前位置的长度变为作业长度 used_tablei.flag=J;/标识设置为作业名return;void
15、reclaim(char J)/进行回收作业，作业名为 J int i,k,j,s,t;float S,L;s=0;while(used_tables.flag!=J|used_tables.flag=0)&s=n)printf(找不到作业n);return;used_tables.flag=0;/作业表标记设为 0 S=used_tables.address;/S 记录作业地址 L=used_tables.length;/L 记录作业长度 j=-1;k=-1;i=0;while(im&(j=-1|k=-1)/寻找回收分区的上下邻空闲区，上邻表目 K，下邻表目j if(free_tablei.
16、flag=0)if(free_tablei.address+free_tablei.length=S)k=i;/找上邻区 if(free_tablei.address=S+L)j=i;/找下邻区 i+;if(k!=-1)/找到上邻区为空闲 if(j!=-1)/找到下邻区为空闲 free_tablek.length=free_tablej.length+free_tablek.length+L;/将上，本身，下合并 free_tablej.flag=0;/标识设置为 0 else free_tablek.length=free_tablek.length+L;/只是上邻区为空闲，将上邻区空闲长度
17、+回收作业长 else if(j!=-1)/只找到下邻区为空闲 free_tablej.address=S;/将下邻区的地址改为作业地址 free_tablej.length=free_tablej.length+L;/长度再加上作业长度 else/都没找到 t=0;/在空闲区表中寻找空栏目 while(free_tablet.flag=1&t=m)printf(内存空闲表没有空间，回收空间失败n);used_tables.flag=J;/回收失败，重新将标识还原为作业名 return;free_tablet.address=S;/找到了，就在空闲分区表中记下它的地址 free_tablet.
18、length=L;/记下长度 free_tablet.flag=1;/将该标识设为 1return;void main()int i,a;float xk;char J;char b;free_table0.address=10240;/空闲分区表的开始地址为 102400 free_table0.length=102400;/第一块的长度为 102400 free_table0.flag=1;/第一块标识为 1 for(i=1;im;i+)/将其他标识设为 0 free_tablei.flag=0;for(i=0;in;i+)/将作业表的标识全设为 0，还没有作业 used_tablei.f
19、lag=0;while(1)printf(选择功能项（0-退出，1-分配内存，2-回收内存，3-显示内存）n);printf(选择功能项（0-3）);scanf(%d,&a);switch(a)case 0:exit(0);case 1:/分配内存，转入 allocate printf(输入作业名 J 和作业所需长度 xk:);scanf(%*c%c%f,&J,&xk);allocate(J,xk);break;case 2:/回收内存，转向 reclaim printf(输入要回收分区的作业名);scanf(%*c%c,&J);reclaim(J);break;case 3:/显示内存 pr
20、intf(输出空闲区表：n 起始地址 分区表长 标志n);for(i=0;im;i+)printf(%5.0f%10.0f%6dn,free_tablei.address,free_tablei.length,free_tablei.flag);/输出空闲区每一个地址，长度，标识 printf(按任意键，输出已分分区表n);b=getche();/按任意键 printf(输出已分分区表：n 起始地址 分区长度 标志n);for(i=0;in;i+)if(used_tablei.flag!=0)/已分配出去的 printf(%6.0f%9.0f%6cn,used_tablei.address,used_tablei.length,used_tablei.flag);else/标识为 0 的 printf(%6.0f%9.0f%5cn,used_tablei.address,used_tablei.length,used_tablei.flag);break;default:printf(没有该选项n);