动态分区存储管理实验报告

数学计算机科学学院实验报告专业名称软件开发已应用实验室学苑楼2#202实验课程计算机操作系统实验名称动态分区存储管理姓名____杨剑_______学号___0915266______同组人员_____无________实验日期____2011/5/23___一、【实验目的】：1、熟悉主存分配与回收2、理解在不同的存储管理方式，如何实现主存空间的分配与回收3、掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。二、【实验内容和要求】：主存的分配和回收的实现是与住存储器的管理方式有关的。所谓分配，就是解决多进程如何共享主存空间的问题。所谓回收，就是当进程运行完时将进程所占的主存空间归还给系统。实验要求使用可变分区存储管理方式，分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法、三种算法来实现主存的分配与回收。同时要求设计一个实用友好的可视化用户界面，并显示分配与回收过程。三、【实验原理】实验中为有效地对内存进行管理，实验中应设计一些数据结构，能有效地进行分配和回收，具体分析如下：1、设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。2、设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况。3、设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。4、要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。四、【实验环境】（使用的软件）MicrosoftVisualC++6.0五、【实验设计分析】：内存分配：①动态输入构造空闲区表，并显打印示构造好的空闲分区表。②键盘接收内存申请。③根据申请，实施内存分配，并返回分配所得内存首址。④分配完后，调整空闲分区表（即扣除分配部分），并显示调整后的空闲分区表。⑤若分配失败，返回分配失败信息。内存回收：①显示当前的空闲分区表和内存分区表。②从键盘接收回收分区的首址与大小，按内存回收的四种情况进行内存回收。③显示回收后已调整好的的空闲分区表六、【实验过程和步骤】：●数据结构设计①空闲分区表的设计，该空闲分区表记录内存中未使用的各个分区，记录内容有未使用分区的大小、首地址，用链表就行管理；相关代码如下：Typedefstructfree{Intsize;//分区大小Intaddress;//首地址free*next;}；②内存分区表设计，用以表示当前内存的使用情况，记录内容已使用分区的大小、首地址，用链表进行管理，相关数据结构如下：Typedefstructmap{Intsize;//分区大小Intaddress;//首地址map*next;}；③进程申请队列的设计，用作进程到达的缓冲队列，记录各进程的相关信息，如进程的所需内存的大小、进程名，相关数据结构如下：Typedefstructpro{Intsize;//分区大小sringname;pro*next;};●内存分配当有进程进行内存申请时，我们利用首次适应算法从空闲分区链表、找出一块做够大的空间进行分配并对空闲分区和内存分区的相关结点进行处理，若未找到则返回错误信息，相关示意图如下：●内存回收内存的回收存在以下几种情况：①上邻空闲区：合并两分区，删除正回收的节点，改变上邻分区大小为两分区之和②下邻空闲区：合并两分区，删除下邻分区节点，改变正回收节点大小为两分区之和，改变正回收节点的首址。③上、下邻空闲区：合并三分区，删除下邻分区和正在回收节点，改变上分区节点大小为三分区之和，改变上分区收节点的首址④不邻接，则建立一新表项。相关的示意图如下：①②③相关代码1．采用最优分配算法分配作业空间，主要代码如下：voidallocate(charJ,floatxk)//采用最优分配算法分配xk大小的空间{inti,k,l;floatad;k=-1;for(i=0;im;i++)//寻找空间大于xk的最小空闲区登记项kif(free_table[i].length=xk&&free_table[i].flag==1)if(k==-1||free_table[i].lengthfree_table[k].length)k=i;回回收收区区空闲区空闲区回回收收区区空闲区回回收收区区空闲区if(k==-1)//未找到可用空闲区,返回{AfxMessageBox(“有效空间不足！”);return;}//找到可用空闲区,开始分配:若空闲区大小与要求分配的空间差小于minisize大小,则空闲区全部分配;若空闲区大小与要求分配的空间差大于minisize大小,则从空闲区划出一部分分配if(free_table[k].length-xk=minisize){free_table[k].flag=0;ad=free_table[k].address;xk=free_table[k].length;}else{free_table[k].length=free_table[k].length-xk;ad=free_table[k].address+free_table[k].length;}//修改已分配区表l=0;for(i=0;in;i++){while(used_table[i].flag=='0'&&in)//寻找空表目{if(i=n)//无表目填写已分分区{AfxMessageBox(无表目填写已分分区错误!);//修正空闲区表if(free_table[k].flag==0)//前面找到的是整个空闲区free_table[k].flag=1;else//前面找到的是某个空闲区的一部分{free_table[k].length=free_table[k].length+xk;return;}}else//修改已分配区表{used_table[i].address=ad;used_table[i].length=xk;used_table[i].flag=J;}l=1;}if(l==1)break;}return;}//主存分配函数结束3．作业的回收boolreclaim(charJ)//回收作业名为J的作业所占主存空间{inti,k,j,s,t;floatS,L;//寻找已分配区表中对应登记项s=0;while((used_table[s].flag!=J||used_table[s].flag=='0')&&s=n){if(s=n)//在已分配区表中找不到名字为J的作业{AfxMessageBox(找不到该作业);return(false);}s++;}//修改已分配区表if(used_table[s].flag==J){used_table[s].flag='0';//取得归还分区的起始地址S和长度LS=used_table[s].address;L=used_table[s].length;j=-1;k=-1;i=0;//寻找回收分区的上下邻空闲区,上邻表目k,下邻表目Jwhile(im&&(j==-1||k==-1)){if(free_table[i].flag==1){if(free_table[i].address+free_table[i].length==S)k=i;//找到上邻if(free_table[i].address==S+L)j=i;//找到下邻}i++;}if(k!=-1)if(j!=-1)//上邻空闲区,下邻空闲区,三项合并{free_table[k].length=free_table[j].length+free_table[k].length+L;free_table[j].flag=0;}else//上邻空闲区,下邻非空闲区,与上邻合并free_table[k].length=free_table[k].length+L;elseif(j!=-1)//上邻非空闲区,下邻为空闲区,与下邻合并{free_table[j].address=S;free_table[j].length=free_table[j].length+L;}else//上下邻均为非空闲区,回收区域直接填入{//在空闲区表中寻找空栏目t=0;while(free_table[t].flag==1&&t=m){if(t=m)//空闲区表满,回收空间失败,将已分配区表复原{AfxMessageBox(主存空闲表没有空间,回收空间失!);used_table[s].flag=J;return(false);}t++;}free_table[t].address=S;free_table[t].length=L;free_table[t].flag=1;}}return(true);}//主存归还函数结束●程序流程图七、【测试数据和实验结果分析】：假设初始状态下，可用的内存空间为400KB，并有下列的请求序列：（1）进程1申请130KB（2）进程2申请60KB（3）进程3申请100KB（4）进程2释放60KB（5）进程4申请200KB（6）进程3释放100KB（7）进程1释放130KB（8）进程5申请140KB（9）进程6申请60KB（10）进程7申请50KB（11）进程6释放60KB从头开始查表检索完否？m.sizeu.size?m.size-u.size=size?从该分区中划出u.size大小的分区将该分区分配，并修改相关结构返回返回继续检索下一个表项将该分区从链中移出YYYNNN●实验结果分析：由测试数据知，首先进程1、2、3到达缓冲队列依次申请各自所需内存，对应着上图1，之后进程3、1依次释放，对应图2，从实验结果看，实验结果的正确性得到验证。八、【实验心得】：本实验极大的帮助我们理解了动态分区作业存储管理的实现过程。在对作业采用最优适应算法的同时，还外加代码弥补了最优适应算法会产生极小的零碎空闲区的弊端。在作业存储时，当前作业的起始地址=原空闲区起始地址+原空闲区偏移地址-当前作业的偏移地址；由此可知当前作业在空闲区内是从空闲区的高地址开始分配。在对作业回收时，作业临区的回收采用if、else语句及其嵌套语句，清楚合理的实现了4中情况下的作业回收。