操作系统实验――分区式存储管理算法.

《操作系统实验――分区式存储管理算法.》由会员分享，可在线阅读，更多相关《操作系统实验――分区式存储管理算法.（20页珍藏版）》请在装配图网上搜索。

1、河南农业大学操作系统实验报告实验题目： 可变分区内存分配与回收学院：理学院班级：10信安三班学 号 ： 1008105072姓名：高凯强一、课程设计目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。通过这次实验，加深对内存管理的认识，进一步掌握内存的分配、回收算法的思想。二、课程设计内容用 C 语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程 alloc(和回收过程 free(。其中，空闲分区通过空闲分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。假设初始状态下，可用的内存空间为 640KB，其中操作系统占用 6

2、4KB ，并有下列的请求序列：作业 1 申请 130KB作业 2 申请 60KB作业 3 申请 100KB作业 2 释放 60KB作业 4 申请 200KB作业 3 释放 100KB作业 1 释放 130KB作业 5 申请 140KB作业 6 申请 60KB作业 7 申请 50KB作业 6 释放 60KB请分别采用首次适应算法和最佳适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况。三、设计思路：整体思路：可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲区。当作业要求装入内存时，根据作业需要内存空间的大小 查询内存中的各个空闲区，当从内存空间中找到一

3、个大于或等于该作业大小的内存空闲区时，选择其中一个空闲区，按作业需求量划出一个分区装人该作业，作业执行完后，其所占的内存分区被收回，成为一个空闲区。如果该空闲区的相邻分区也是空闲区，则需要将相邻空闲区合并成一个空闲区。设计所才用的算法：采用最优适应算法，每次为作业分配内存时，总是把既能满足要求、又是最小的空闲分区分配给作业。 但最优适应算法容易出现找到的一个分区可能只比作业所需求的长度略大一点的情行，这时，空闲区分割后剩下的空闲区就很小以致很难再使用，降低了内存的使用率。为解决此问题，设定一个限值 minsize，如果空闲区的大小减去作业需求长度得到的值小于等于 minsize，不再将空闲区分

4、成己分分区和空闲区两部分，而是将整个空闲区都分配给作业。内存分配与回收所使用的结构体：为便于对内存的分配和回收，建立两张表记录内存的使用情况。一张为记录作业占用分区的“内存分配表”，内容包括分区起始地址、长度、作业名 / 标志（为 0 时作为标志位表示空栏目）；一张为记录空闲区的“空闲分区表”，内容包括分区起始地址、长度、标志（ 0 表空栏目， 1 表未分配）。两张表都采用顺序表形式。关于分配留下的内存小碎片问题：当要装入一个作业时，从“空闲分区表”中查找标志为“ 1”（未分配）且满足作业所需内存大小的最小空闲区，若空闲区的大小与作业所需大小的差值小于或等于minsize ，把该分区全部分配给

5、作业，并把该空闲区的标志改为“ 0”（空栏目）。同时，在已分配区表中找到一个标志为“ 0”的栏目登记新装人作业所占用分区的起始地址，长度和作业名。若空闲区的大小与作业所需大小的差值大于 minsize 。则把空闲区分成两部分，一部分用来装入作业，另外一部分仍为空闲区。这时只要修改原空闲区的长度，且把新装人的作业登记到已分配区表中。内存的回收：在可变分区方式下回收内存空间时，先检查是否有与归还区相邻的空闲区（上邻空闲区，下邻空闲区）。若有，则将它们合件成一个空闲区。程序实现时，首先将要释放的作业在“内存分配表”中的记录项的标志改为“ 0”（空栏目），然后检查“空闲区表”中标志为 1（未分配）的栏

6、目，查找是否有相邻的空闲区，若有，将之合并，并修改空闲区的起始地址和长度。四、程序流程图：作业分配流程图：内存回收流程图：九、程序说明：本程序采用 Visual C+ 编写，模拟可变分区存储管理方式的内存分配与回收。假定系统允许的最大作业数量为n=10，允许的空闲区表最大项数为m=10，判断是否划分空闲区的最小限值为minsize=5。初始化用户可占用内存区的首地址为1000，大小为640Kb。定义两个结构体及其对象free_tablem和 used_tablen实现内存的分配回收及分配表和空闲表的登记。用最优分配算法实现动态分配时，调用int distribute(intprocess_na

7、me, float need_length内存分配函数，设定循环条件查找最佳空闲分区，定义 int k 以记录最佳空闲区的首地址，根据找到的空闲区大小和作业大小判断是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”和“空闲分区表”中作登记。调用int recycle(int process_name函数实现内存的回收。顺序循环“内存分配表”找到要回收的作业，将标志位设为“0”，定义float recycle_address,recycle_length;用recycle_address记下回收作业的首地址，recycle_length记下回收作业长度。查找空闲表，如果(free_

8、tablei.address+free_tablei.length=recycle_address，说明有上邻接空闲区，这时上邻接区的起始地址不变，长度+ recycle_address； 如果(recycle_address+recycle_length=free_tablei.address，说明有下邻接，这时下邻接空闲区的起始地址改为回收作业的起始地址recycle_address，长度 +recycle_length。如果同时有上下邻接空闲区，则上邻接的起始地址不变，长度+recycle_address+下邻接的长度，下邻接标志设为“0” 否则，要回收的内存没有邻接空闲区，在空闲区中找

9、到一个标志为“0”的空栏目登记回收的内存。十、源程序：#include#includeusing namespace std;/ 全局变量float minsize=5;int count1=0;int count2=0;#define m 10 /假定系统允许的空闲区表最大为m#define n 10 /假定系统允许的最大作业数量为n/ 分区表项的定义typedef structfloat address; /分区表项起始地址float length; /分区表项长度，单位为字节int flag; /分区表项登记栏标志，0 表示空栏目，用1 表示未分配 Table;Table used_ta

10、ble100;/已分配表的定义：Table free_table100;/空闲区表的定义：/ 函数声明void initialize(void;char alloc(char, float;char free(char;void sort(Table;void show(;/ 初始化两个表void initialize(voidint a;for(a=0; a=n-1; a+used_tablea.flag=0; /free_table0.address=1000;free_table0.length=640;已分配表的表项全部置为空表项free_table0.flag=1; / 空闲区表的表

11、项全部为未分配/ 最优分配算法实现的动态分区char alloc(char process_name, float need_lengthint i, k=-1; /k用于定位在空闲表中选择的未分配栏float ads, len;int count=0;i=0;while(i=m-1 /循环找到最佳的空闲分区if(free_tablei.flag=1 & need_length =free_tablei.lengthcount+;if(count=1|free_tablei.length free_tablek.lengthk=i;i=i+1;if(k!=-1if(free_tablek.le

12、ngth-need_length=minsize /free_tablek.flag=0;ads=free_tablek.address;len=free_tablek.length;else整个分配 /切割空闲区ads=free_tablek.address;len=need_length;free_tablek.address+=need_length;free_tablek.length-=need_length;i=0;/ 循环寻找内存分配表中标志为空栏目的项while(used_tablei.flag!=0i=i+1;if(i=n-1 /找到，在已分配区表中登记一个表项used_ta

13、blei.address=ads;used_tablei.length=len;used_tablei.flag=(int(process_name-0;count1+;else /已分配区表长度不足if(free_tablek.flag = 0 /free_tablek.flag=1;free_tablek.address=ads;free_tablek.length=len;将已做的整个分配撤销else /将已做的切割分配撤销free_tablek.address=ads;free_tablek.length+=len;cout 内存分配区已满，分配失败！n;return 0;elseco

14、ut 无法为该作业找到合适分区！n;return 0;return process_name;char free(char process_nameint y=0;float recycle_address, recycle_length;int i, j, k; /j栏是下邻空闲区，k 栏是上栏空闲区int x;/ 在内存分配表中找到要回收的作业while(y=n-1&used_tabley.flag!=(int(process_name-0 y=y+1;if(y=n-1 /找到作业后，将该栏的标志置为0recycle_address=used_tabley.address;recycle_

15、length=used_tabley.length;used_tabley.flag=0;count2+;else /未能找到作业，回收失败cout=m|(k!=-1&j!=-1 /修改空闲分区表if(free_tablei.flag=1if(free_tablei.address+free_tablei.length=recycle_addressk=i; /判断是否有上邻接if(recycle_address+recycle_length=free_tablei.addressj=i; /判断是否有下邻接i=i+1;/ 合并空闲区if(k!=-1 /回收区有上邻接if(j!=-1 /回收区

16、也有下邻接，和上下领接合并free_tablek.length+=free_tablej.length+recycle_length;free_tablej.flag=0; /将第j 栏的标记置为 0else /不存在下邻接，和上邻接合并free_tablek.length+=recycle_length;else if(j!=-1 /只有下邻接，和下邻接合并free_tablej.length+=recycle_length;free_tablej.address=recycle_address;else /上下邻接都没有x=0;while(free_tablex.flag!=0x=x+1;

17、 /在空闲区表中查找一个状态为 0的栏目if(x / 找到后，在空闲分区中登记回收的内存free_tablex.address=recycle_address;free_tablex.length=recycle_length;free_tablex.flag=1;else / 空闲表已满，执行回收失败used_tabley.flag=(int(process_name;cout空闲区已满，回收失败！n;return 0;return process_name;void sort(Table arrayint i,j,k,t;for(i=0;ik=i;for(j=i+1;j找到数组中地址最小且

18、不为0 的那一项的序号赋值于kif(arrayj.addressk=j;t=arrayk.address;arrayk.address=arrayi.address;arrayi.address =t;t=arrayk.length;arrayk.length=arrayi.length;arrayi.length=t;t=arrayk.flag;arrayk.flag=arrayi.flag;arrayi.flag=t;/ 将最小项与第一项元素交换void show( /程序执行时输出模拟的内存分配回收表coutnt*n;coutt*空 闲 区 *n;coutt*n;sort(free_ta

19、ble;for(int i=0;i=count2;i+if(free_tablei.flag!=0coutt地址： 作业长度： 状 态： elsecontinue;coutnt*n;coutt*已 分 配 区 *n;cout57coutt地址： 作业长度： 作业名： (charused_tablej.flag48&(used_tablej.flag=57coutt地址： 作业长度：作业名：elsecontinue;void main( /主函数调用各功能函数对所有工作进行测试int choice; /用来选择将要进行的操作char job_name;float need_memory;bool

20、 exitFlag=false;coutt动态分区分配方式的模拟;initialize(; /开创空闲区和已分配区两个表while(!exitFlagcoutnn;couttn;coutt 请选择操作类型 n;coutt n;coutt 1:分配内存 2:回收内存 n;coutt 3:查看分配 0:退 出 n;coutt n;coutchoice;switch(choicecase 0:exitFlag=true; /退出操作break;case 1:coutjob_nameneed_memory;alloc(job_name, need_memory; /break;case 2:char

21、ID;分配内存coutID;free(ID; /break;case 3:show(;break;回收内存11、实验结果截图：（ 1）申请 系统作业 x（64KB）、作业 1（ 130KB）、作业 2（60KB）、作业 3（ 100KB）（ 2）释放作业 2（ 60KB）（ 3）申请作业 4（ 200KB）（ 4）释放作业 3（ 100KB）、作业 1（ 130KB）（ 5）申请 作业 5（ 140KB）、作业 6（ 60KB）、作业 7（ 50KB）（ 6）释放作业 6（ 60KB）十二、心得体会：每一次的实践，都会有很大的收获。决定做这个题目的时候，就针对此题要解决的几个问题反复思考，重新

22、翻开教科书把相关内容特别是算法原理认真细致的看了一遍，设想会遇到的问题。在内存动态分配程序设计中，最优适应算法比首次要难一些，要加上对分配后该分区是否能最好地利用的判断。再一个问题是回收时候的合并，对地址的修改不是很有把握。着手写程序后，半天才理清回收的内存和上下邻合并的条件与关系，写此处的代码时，逻辑上比较混乱，反复错误反复修改了很多次才调试正确，这也是花了最多时间才得以正确实现的部分。之前大多用的 c 语言，对结构体，对象等知识淡忘了很多，这一次的实践让我找回了很多学过的知识点，也弥补了很多的不足之处。逻辑思维也得到了锻炼，写代码也不再像初学的时候那么繁琐，自己都能感觉到那一点点的进步，顿

23、时也觉得充实起来。还有一个难点就是为作业找到最佳空闲区，此处是参照了一些资料后，理清了条件，然后用一个 while （）两个 if （）语句循环嵌套就实现了此功能。实践中也发现自身很多的不足，比如上理论课时认为已经理解了的算法原理在用代码实践时，发现还是有模糊和思考不周的地方。实践中最困难的是以前没有做过界面，所以虽然程序在大家的努力下还算顺利地完成了，功能测试也通过了，可是界面的制作却成了比较大的难题。好在之前在面向对象课程实验和程序设计课程设计中都用到过 MFC ，于是确定了用 C+ 来制作界面。但是因为以前界面程序编写较少，所以界面的编写遇到了许多困难，特别是实现内存分配表和空闲分区表的

24、输出遇到了很大的挫折，最后在查阅资料、认真思考的基础上实现内存分配表和空闲分区表的输出，并最终作出了内存管理子系统。在添加控件和消息映射的时候，问题不是很大，但是在对相应控件添加代码和给类添加成员函数的时候，要将源代码对应的部分添加进去，且要注意修包含的头文件。这些地方一直频繁出错，或在功能得不到实现，大家一起边找资料边学习新的知识，通过很多次的尝试，终于做出了界面，虽然不太好看，而且功能也很简单，但这也是也经过大家很大努力才完成的。学习着，收获着，并快乐着，这真是小组成员们共同的感触。对于自身不足的地方，大家也有了比较清晰的认识，对未来的发展，也有了个参照，将遇到的困难一个个跨过，并最终完成此次课程设计，真的感觉很有收获很有成就感。同时也培养了团队合作精神，几次的讨论，大大提升了我们合作的默契度，体会到合作的重要性。动手能力也得到了提高，当然，我们的设计还有很多的不足之处，有些问题没能很好解决，但通过不断学习和实践，我们一定会做的更好。