模拟实现一个简单的固定(可变)分区存储管理系统

合肥学院计算机科学与技术系实验报告2009～2010学年第一学期课程操作系统原理实验名称模拟实现一个简单的固定（可变）分区存储管理系统学生姓名朱海燕、汪小白、秦月、程美玲专业班级07计本（1）班指导教师屠菁2009年12月1．实验目的通过本次课程设计，掌握了如何进行内存的分区管理，强化了对首次适应分配算法和分区回收算法的理解。2．实验内容（1）建立相关的数据结构，作业控制块、已分配分区及未分配分区（2）实现一个分区分配算法，如最先适应算法、最优或最坏适应分配算法（3）实现一个分区回收算法（4）给定一个作业/进程，选择一个分配或回收算法，实现分区存储的模拟管理初始化并创建空闲分区表；flag=0显示空闲分区表和已分配分区表i++NYNNYNYY图1.流程图flag=Choiceflag=0；i=0;输入要申请作业名及大小;输入要回收的作业名返回回收区上回收回收区下回收回收删除分配表中该作业；表长度减1空闲空间i长度申请分配空闲区长度减1分配输出分配成功flag=1;申请无效空闲空间i长度=申请作业长度3．实验步骤首先，初始化函数initial（）将分区表初始化并创建空闲分区列表，空闲区第一块的长度是30，以后的每个块长度比前一个的长度长20。frees[0].length=30第二块的长度比第一块长20，第三块比第二块长30，以此类推。frees[i].length=frees[i-1].length+20;下一块空闲区的首地址是上一块空闲区的首地址与上一块空闲区长度的和。frees[i].front=frees[i-1].front+frees[i-1].length;分配区的首地址和长度都初始化为零occupys[i].front=0;occupys[i].length=0;显示函数show（）是显示当前的空闲分区表和当前的已分配表的具体类容，分区的有起始地址、长度以及状态，利用for语句循环输出。有一定的格式，使得输出比较美观好看。assign（）函数是运用首次适应分配算法进行分区，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。这个算法倾向于优先利用内存中低址部分被的空闲分区，从而保留了高址部分的的大空闲区。着给为以后到达的大作业分配大的内存空间创造了条件。它的缺点是低地址部分不断被划分，会留下很多难以利用的、很小的空闲分区，而每次查找又都是从低址部分开始，这样无疑会增加查找可用空闲分区的开销。分配内存，从空闲的分区表中找到所需大小的分区。设请求的分区的大小为job_length，表中每个空闲分区的大小可表示为free[i].length。如果frees[i].length=job_length，即空闲空间I的长度大于等于作业的长度将空闲标志位设置为1，如果不满足这个条件则输出：“对不起，当前没有满足你申请长度的空闲内存，请稍后再试！”。如果frees[i].length=job_length空闲区空间I的长度不大于作业长度，I的值加1判断下一个空闲区空间是否大于作业的长度。把未用的空闲空间的首地址付给已用空间的首地址，已用空间的长度为作业的长度，已用空间数量加1。如果(frees[i].lengthjob_length)，空间的长度大于作业的长度，frees[i].front+=job_length;空闲空间的起始首地址=原空闲区间的起始长度加作业长度frees[i].length-=job_length;空闲区间的长度=原空闲区间的长度-作业的长度。如果空间的长度与作业的长度相等，空闲区向前移一位，空闲区的数量也减一。这样判断所有情况并相应分配之后，内存空间分配成功。第二个操作为：撤消相应作业。在这个操作中，进行了以下步骤：（1）按照系统提示输入将要撤消的作业名；（2）判断该作业是否存在若不存在：输出“没有这个作业名，请重新输入作业名”；若存在：则先分别用flag,start,len保存该作业在分配区表的位置i，内存空间的首地址以及长度。接着根据回收区的首地址，即该作业的首地址，从空闲区表中找到相应的插入点，将其加入空闲表，此时可能出现以下三种情况之一：1.回收区只与插入点前一个空闲分区F1相邻接即（frees[i].front+frees[i].length)==start），此时判断其是否与后一个空闲分区F2相邻接，又分两种情况:若相邻接，则将三个分区合并，修改新的空闲分区的首地址和长度。新的首地址为F1的首地址，长度为三个分区长度之和，相应的代码为：frees[i].length=frees[i].length+frees[i+1].length+len;，并相应的空闲区表。若不相邻接，即合并后的首应将回收区与插入点的前一分区合并，则不须为回收分区分配新的表项，只须修改其前一分区的大小。该大小为F1与当前作业大小之和。frees[i].length+=len;2.回收分区与插入点前一个空闲分区不邻接但与后一空闲分区F2邻接。此时应合并当前作业分区与F2分区，合并后的分区首地址为当前作业首地址start，长度为两个分区长度之和。代码为：frees[i].front=start;frees[i].length+=len;3.回收分区既不与插入点前一空闲分区相邻接，也不与后一空闲分区相邻接。此时只须将该回收分区插入空闲区表即可。此时空闲区的数量加1。将回收区加入空闲区表后还须修改分配区表内容。具体为：修改分配区表中回收区（第一区）之后的各区指针，使其依次前移一位，即occupys[i]=occupys[i+1];同时已分配分区数量减1，即occupy_quantity--;最后输出内存空间回收完毕！即完成了撤消作业并回收相应空间的操作。图2.初始化空闲分区列表图3.内存空间分配图4.内存回收4．实验总结动态分区分配是根据进程的实际需要，动态地为之分配内存空间。程序中采用空闲分区表，用于纪录每个空闲分区的情况。每个空闲分区占一个表目，表目中包括起始地址、长度和状态。采用已分配表，用于存放请求的作业，每个作业占一个表目，包括起始地址、长度和作业名。程序调用initial()函数实现对空闲分区的初始化。将作业装入内存时，运用首次适应分配算法。程序中调用assign()实现，分配内存时，从表首开始查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲表中。若不能找到满足要求的空闲区，则此次内存分配失败，返回。回收内存，即撤销某些作业，调用撤销函数cancel()，根据所撤销作业的首址，从空闲区表中找到相应的插入点，回收内存包括四种情况：（1）回收区与前一空闲分区相邻接，此时将回收区与前一分区合并，并修改前一分区的大小；（2）回收区与后一空闲分区相邻接，此时将回收区与后一分区合并，并修改后一分区的首址和大小；（3）回收区同时与前、后分区相邻接，则将三个分区合并，使用前一分区的首址，大小为三分区大小之和；（4）回收区不与空闲分区相邻，则重新建立一新表项，填写首址和大小，插入表中相应位置。函数show()用于显示空闲区表和已分配表时，运用for循环，依次显示每个空闲区表和已分配表的信息。5．附录#includestdlib.h#includestdio.h#includeiostream.h#includestring.h#includeiomanip.hconstintMAXJOB=5;//定义表最大记录数typedefstructnode{intfront;intlength;chardata[20];}job;//定义job类型的数据类型jobfrees[MAXJOB];//定义空闲区表intfree_quantity;joboccupys[MAXJOB];//定义已分配区表intoccupy_quantity;//初始化并创建空闲分区表函数intinitial(){inti;frees[0].front=0;frees[0].length=30;occupys[0].front=0;occupys[0].length=0;strcpy(frees[0].data,free);for(i=1;iMAXJOB;i++){frees[i].front=frees[i-1].front+frees[i-1].length;frees[i].length=frees[i-1].length+20;strcpy(frees[i].data,free);occupys[i].front=0;occupys[i].length=0;strcpy(occupys[i].data,);}free_quantity=MAXJOB;occupy_quantity=0;return1;}//显示函数voidshow(){inti;printf(----------------------------------------------------------\n);printf(当前空闲分区表如下:\n);printf(起始地址长度状态\n);for(i=0;ifree_quantity;i++){printf(%5d%8d%s\n,frees[i].front,frees[i].length,frees[i].data);}printf(----------------------------------------------------------\n);printf(当前已分配表如下:\n);printf(起始地址长度占用作业名\n);for(i=0;ioccupy_quantity;i++){printf(%5d%6d%s\n,occupys[i].front,occupys[i].length,occupys[i].data);}printf(----------------------------------------------------------\n);}//首次适应分配算法voidassign(){charjob_name[20];intjob_length;inti,j,flag,t;printf(请输入新申请内存空间的作业名和空间大小:);scanf(%s,job_name);scanf(%d,&job_length);flag=0;for(i=0;ifree_quantity;i++){if(frees[i].length=job_length)//如果空闲空间I的长度=作业长度{flag=1;//空闲标志位就置1}}if(flag==0){printf(对不起,当前没有能满足你申请长度的空闲内存,请稍候再试！\n);}else{t=0;i=0;while(t==0)//为空闲区间的时候{if(frees[i].length=job_length){t=1;}i++;//如果空闲空间I的长度不大于作业长度，I加1，判断下一个空间}i--;occupys[occupy_quantity].front=frees[i].front;//把未用的空闲空间的首地址付给已用空间的首地址strcpy(occupys[occupy_quantity].data,job_name);//已用空间的内容为作业名occupys[occupy_quantity].length=job_length;//已用空间的长度为作业的长度occupy_quantity++;//已用空间数量加1if(frees[i].lengthjob_length)//如果空间的长度大于作业的长度，{frees[i].front+=job_length;//空闲空间的起始首地址=原空闲区间的起始长度加作业长度frees[i].length-=jo