齐齐哈尔大学操作系统课程综合实践题目：存储管理——动态分区分配/回收算法的模拟班级：0姓名：0学号：0指导教师：02011年 12 月综合实践评分表在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。
存储管理---动态分区分配/回收算法的模拟摘要：主存的分配和回收的实现是与住存储器的管理方式有关的。
解决多进程如何共享主存空间的问题。
当进程运行完时将进程所占的主存空间归还给系统。
可变分区存储管理方式，分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行。
关键字：内存分配，空闲分区表，进程申请队列一、【实践目的】：1、熟悉主存分配与回收2、理解在不同的存储管理方式，如何实现主存空间的分配与回收3、掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过程。
二、【实践内容和要求】：主存的分配和回收的实现是与住存储器的管理方式有关的。
所谓分配，就是解决多进程如何共享主存空间的问题。
所谓回收，就是当进程运行完时将进程所占的主存空间归还给系统。
实验要求使用可变分区存储管理方式，分区分配中所用的数据就够采用空闲分区说明表和空闲分区链表来进行，分区分配中所用的算法采用首次适应算法、循环首次适应算法、最佳适应算法、三种算法来实现主存的分配与回收。
同时要求设计一个实用友好的可视化用户界面，并显示分配与回收过程。
仿真实现动态可变分区存储管理模拟系统。
内存调度策略可采用首次适应算法、循环首次适应算法和最佳适应法等，并对各种算法进行性能比较。
为了实现分区分配，系统中必须配置相应的数据结构，用来描述空闲区和已分配区的情况，为分配提供依据。
常用的数据结构有两种形式：空闲分区表和空闲分区链。
为把一个新作业装入内存，须按照一定的算法，从空闲分区表或空闲分区链中选出一个分区分配给该作业。
三、【实践原理】操作系统是最重要的计算机系统软件，同时也是最活跃的学科之一。
计算机系统由硬件和软件两部分组成。
操作系统是配置在计算机硬件上的第一层软件，是对硬件的首次扩充。
本次课程设计的主要目的是在学习操作系统理论知识的基础上，对操作系统整体的一个模拟。
也是对本学期所学知识的一个总体的检测，使理论知识应用到实际的编程中，根据理论的算法来实现具体的编程操作。
同时通过本次课程设计加深对操作系统理论知识各个部分管理功能的感性认识，进一步分析和理解各个部分之间的联系和功能，最后达到对完整系统的理解。
同时，可以提高运用操作系统知识和解决实际问题的能力；并且锻炼自己的编程能力、创新能力以及开发软件的能力；还能提高自己的调查研究、查阅文献、资料以及编写软件设计文档的能力并提高分析问题的能力。
实验中为有效地对内存进行管理，实验中应设计一些数据结构，能有效地进行分配和回收，具体分析如下：1．设计一个空闲分区表，空闲分区表通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲分区低端的空间。
2．设计一个内存分区表，可用链表管理，用以表示当前以内存使用情况。
3．设计一个进程申请队列以及进程完成后的释放顺序，实现主存的分配和回收。
4．要求每次分配和回收后把空闲分区的变化情况以及各进程的申请、释放情况以及各进程的申请、释放情况以图形方式显示、打印出来。
循环首次适应算法的alloc()函数与首次适应算法的alloc()函数区别在于从哪里开始找是否有满足作业要求的空闲区，它是从上次找到的空闲区的下一个空闲分区开始找，只需要改变for循环的条件即可。
for(i=s;i<N;i++)最佳适应算法：该算法总是把满足要求、又是最小的空闲区分配给作业。
检查空闲区说明表是否有满足作业要求的空闲区，也分为三种情况：大于，等于，小于。
若检查到有“等于”的情况，就可以直接分配，若没有，则继续检查是否有“大于”的情况：if(freeblock[i].state==1&&freeblock[i].size==applyarea){freeblock[i].state=0;tag=1;return freeblock[i].startaddress;}检查“大于”的情况：先把所有大于所要求的空闲区放入数组,for(i=0;i<N;i++){if(freeblock[i].state==1&&freeblock[i].size>applyarea)a[j++]=i;}再从数组中挑出最小的那个：果数组中的元素大于一个，则需要一个个比较过去，然后取出最小的那个分配给作业：if(j>1){h=a[0];min=freeblock[h];for(k=1;k<j;k++){h=a[k];if(freeblock[h].size<min.size){mid.size=freeblock[h].size;mid.state=freeblock[h].state;mid.startaddress=freeblock[h].startaddress;freeblock[h].size=min.size;freeblock[h].state=min.state;freeblock[h].startaddress=min.startaddress;min.size=mid.size;min.state=mid.state;min.startaddress=mid.startaddress;}}min.startaddress=min.startaddress+applyarea;min.size=min.size-applyarea;tag=1;return min.startaddress-applyarea;}如果数组中只有一个元素，则直接分配给作业：if(j==1){h=a[0];min=freeblock[h];min.startaddress=min.startaddress+applyarea;min.size=min.size-applyarea;tag=1;return min.startaddress-applyarea;}如果没有满足条件的空闲区，分配不成功，返回-1if(tag==0)return -1;四、【实践环境】（使用的软件）Microsoft Visual C++ 6.0五、【实践设计分析】：内存分配：①动态输入构造空闲区表，并显打印示构造好的空闲分区表。
②键盘接收内存申请。
③根据申请，实施内存分配，并返回分配所得内存首址。
④分配完后，调整空闲分区表（即扣除分配部分），并显示调整后的空闲分区表。
⑤若分配失败，返回分配失败信息。
内存回收：①显示当前的空闲分区表和内存分区表。
②从键盘接收回收分区的首址与大小，按内存回收的四种情况进行内存回收。
③显示回收后已调整好的的空闲分区表六、【实践过程和步骤】：●数据结构设计①空闲分区表的设计，该空闲分区表记录内存中未使用的各个分区，记录内容有未使用分区的大小、首地址，用链表就行管理；相关代码如下：Typedef struct free{Int size; //分区大小Int address;//首地址free *next;}；②内存分区表设计，用以表示当前内存的使用情况，记录内容已使用分区的大小、首地址，用链表进行管理，相关数据结构如下：Typedef struct map{Int size; //分区大小Int address;//首地址map *next;}；③进程申请队列的设计，用作进程到达的缓冲队列，记录各进程的相关信息，如进程的所需内存的大小、进程名，相关数据结构如下：Typedef struct pro{Int size; //分区大小sring name;pro *next;};●内存分配当有进程进行内存申请时，我们利用首次适应算法从空闲分区链表、找出一块做够大的空间进行分配并对空闲分区和内存分区的相关结点进行处理，若未找到则返回错误信息，相关示意图如下：图一：内存分配示意图●内存回收内存的回收存在以下几种情况：①上邻空闲区：合并两分区，删除正回收的节点，改变上邻分区大小为两分区之和②下邻空闲区：合并两分区，删除下邻分区节点，改变正回收节点大小为两分区之和，改变正回收节点的首址。
③上、下邻空闲区：合并三分区，删除下邻分区和正在回收节点，改变上分区节点大小为三分区之和，改变上分区收节点的首址④不邻接，则建立一新表项。
相关的示意图如下：图二：内存回收示意图相关代码1.采用最优分配算法分配作业空间，主要代码如下：void allocate(char J,float xk)//采用最优分配算法分配xk大小的空间{int i,k,l;float ad;k=-1;for(i=0;i<m;i++) //寻找空间大于xk的最小空闲区登记项kif(free_table[i].length>=xk && free_table[i].flag==1)if(k==-1 || free_table[i].length<free_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;i<n;i++){while(used_table[i].flag=='0'&&i<n) //寻找空表目 {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;}//主存分配函数结束2.作业的回收bool reclaim(char J)//回收作业名为J的作业所占主存空间{int i,k,j, s,t;float S,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(i<m&&(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);}//主存归还函数结束/*动态分区的分配与回收演示程序*/#include <iostream.h>#include <stdio.h>#define N 5int start;//存放首址struct freearea /*定义一个空闲区说明表结构，并初始化变量*/ {int ID;/*分区号*/int startaddress;/*空闲区始址*/int size;/*空闲区大小*/int state;/*空闲区状态:0为空表目，1为可用空闲块*/}freeblock[N]={{1,20,20,1},{2,80,50,1},{3,150,30,1},{4,300,30,1},{5,5 00,10,1}};/*定义为作业分配主存空间的函数alloc(),给首次适应算法调用*/int alloc(int applyarea){int i,tag=0; /*applyarea为作业申请量,tag为检查是否有满足作业需要的空闲区的标志*/for(i=0;i<N;i++) /*检查空闲区说明表是否有满足作业要求的空闲区*/if(freeblock[i].state==1&&freeblock[i].size>applyarea){freeblock[i].startaddress=freeblock[i].startaddress+applyarea;freeblock[i].size=freeblock[i].size-applyarea;tag=1; /*有满足条件的空闲区时，tag置1*/return freeblock[i].startaddress-applyarea; /*返回为作业分配的主存地址*/}elseif(freeblock[i].state==1&&freeblock[i].size==applyarea){freeblock[i].state=0;tag=1; /*有满足条件的空闲区时，tag置1*/return freeblock[i].startaddress; /*返回为作业分配的主存地址*/}if(tag==0)return -1; /*没有满足条件的空闲区，分配不成功，返回-1*/ }/*定义为作业分配主存空间的函数alloc2(),给循环首次适应算法调用*/int alloc2(int applyarea,int s) /*applyarea为作业申请量*/{int i,tag=0; /*tag为检查是否有满足作业需要的空闲区的标志*/for(i=s;i<N;i++)/*检查空闲区说明表是否有满足作业要求的空闲区,从上次找到的空闲去的下一个空闲分区开始找*/if(freeblock[i].state==1&&freeblock[i].size>applyarea){freeblock[i].startaddress=freeblock[i].startaddress+applyarea;freeblock[i].size=freeblock[i].size-applyarea;tag=1; /*有满足条件的空闲区时，tag置1*/start=freeblock[i].startaddress-applyarea;return i;}elseif(freeblock[i].state==1&&freeblock[i].size==applyarea) {freeblock[i].state=0;tag=1; /*有满足条件的空闲区时，tag置1*/start=freeblock[i].startaddress; /*返回为作业分配的主存地址*/return i;}if(tag==0)return -1; /*没有满足条件的空闲区，分配不成功，返回-1*/}/*定义为作业分配主存空间的函数alloc3(),给最佳适应算法调用*/int alloc3(int applyarea) /*applyarea为作业申请量*/{int i,k,h,flag,tag=0,j=0; /*tag为检查是否有满足作业需要的空闲区的标志*/int a[N];struct freearea min;struct freearea mid;for(i=0;i<N;i++) /*检查空闲区说明表是否有满足作业要求的空闲区*/{if(freeblock[i].state==1&&freeblock[i].size==applyarea)//大小刚好相等{freeblock[i].state=0;tag=1; /*有满足条件的空闲区时，tag置1*/return freeblock[i].startaddress; /*返回为作业分配的主存地址*/}}for(i=0;i<N;i++)//把所有大于所要求的空闲区放入数组,挑出最小的那个{if(freeblock[i].state==1&&freeblock[i].size>applyarea)a[j++]=i;}if(j>1){h=a[0];min=freeblock[h];//min.startaddress=freeblock[h].startaddress;//min.size=freeblock[h].size;//min.state=freeblock[h].statfor(k=1;k<j;k++){h=a[k];if(freeblock[h].size<min.size){mid.size=freeblock[h].size;mid.state=freeblock[h].state;mid.startaddress=freeblock[h].startaddress;freeblock[h].size=min.size;freeblock[h].state=min.state;freeblock[h].startaddress=min.startaddress;min.size=mid.size;min.state=mid.state;min.startaddress=mid.startaddress;}}min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea;tag=1; /*有满足条件的空闲区时，tag置1*/ return min.startaddress-applyarea;}else if(j==1){h=a[0];min=freeblock[h];min.startaddress=min.startaddress+applyarea; min.size=min.size-applyarea;tag=1; /*有满足条件的空闲区时，tag置1*/ return min.startaddress-applyarea;}if(tag==0)return -1; /*没有满足条件的空闲区，分配不成功，返回-1*/ }/*定义主存回收函数：setfree()tag1代表释放区的高地址是否邻接一个空闲区，tag2代表释放区的高低地址是否都邻接一个空闲区，tag3代表释放区的低地址是否邻接一个空闲区*/void setfree(){int s,l,tag1=0,tag2=0,tag3=0,i,j;printf("请输入释放区的起始地址:");scanf("%d",&s); /*输入释放区的开始地址*/printf("请输入释放区的大小:");scanf("%d",&l); /*输入释放区的大小*/printf("************回收内存后空闲区表的状态如下**********\n");for(i=0;i<N;i++){if(freeblock[i].startaddress==s+l&&freeblock[i].state==1) {l=l+freeblock[i].size;tag1=1; /*有与释放区高地址邻接的空闲区，tag1置1*/for(j=0;j<N;j++)if(freeblock[j].startaddress+freeblock[j].size==s&&freeblock[j].state ==1){freeblock[i].state=0;freeblock[j].size=freeblock[j].size+l;tag2=1;/*有与释放区上下都邻接的空闲区，tag2置1*/break;}if(tag2==0) /*无与释放区高低地址邻接的空闲区*/{freeblock[i].startaddress=s;freeblock[i].size=l;break;}}}if(tag1==0) /*无与释放区高地址邻接的空闲区，并检查是否低地址有邻接空闲区*/{for(i=0;i<N;i++)if(freeblock[i].startaddress+freeblock[i].size==s&&freeblock[i].s tate==1){freeblock[i].size=freeblock[i].size+l;tag3=1; /*有与释放区低地址邻接的空闲区*/break;}if(tag3==0) /*无与释放区低地址邻接的空闲区*/for(j=0;j<N;j++)if(freeblock[j].state==0)/*找一个空表目，将释放区放入表中*/{freeblock[j].startaddress=s;freeblock[j].size=l;freeblock[j].state=1;break;}}}/*定义对空闲区表中的空闲区调整的函数adjust(),使空闲区按始地址从小到大排列，空表目放在最后面*/void adjust(){int i,j;struct freearea middata;for(i=0;i<N;i++) /*将空闲区按始地址顺序在表中排列*/ for(j=0;j<N;j++)if(freeblock[j].startaddress>freeblock[j+1].startaddress) {middata.startaddress=freeblock[j].startaddress;middata.size=freeblock[j].size;middata.state=freeblock[j].state;freeblock[j].startaddress=freeblock[j+1].startaddress;freeblock[j].size=freeblock[j+1].size;freeblock[j].state=freeblock[j+1].state;freeblock[j+1].startaddress=middata.startaddress;freeblock[j+1].size=middata.size;freeblock[j+1].state=middata.state;}for(i=0;i<N;i++) /*将空表目放在表后面*/for(j=0;j<N;j++)if(freeblock[j].state==0&&freeblock[j+1].state==1){middata.startaddress=freeblock[j].startaddress;middata.size=freeblock[j].size;middata.state=freeblock[j].state;freeblock[j].startaddress=freeblock[j+1].startaddress;freeblock[j].size=freeblock[j+1].size;freeblock[j].state=freeblock[j+1].state;freeblock[j+1].startaddress=middata.startaddress;freeblock[j+1].size=middata.size;freeblock[j+1].state=middata.state;}}/*定义打印空闲区说明表函数：print()*/void print(){int i;printf("|---------------------------------------------------------------|\n");printf(" | ID start size state|\n");printf("|---------------------------------------------------------------|\n");for(i=0;i<N;i++){printf(" | %3d %3d %3d %3d |\n",freeblock[i].ID,freeblock[i].startaddress,freeblock[i].size,freeblock[i].state);printf("|---------------------------------------------------------------|\n");}}//首次void First_fit(){int applyarea,start;{printf("请输入作业的申请量:");scanf("%d",&applyarea);/*输入作业的申请量*/start=alloc(applyarea);/*调用alloc()函数为作业分配空间，start为返回的始地址*/if(start==-1) /*alloc()分配不成功时，返回-1*/printf("作业申请量过大，空闲区表中的存储空间无法满足，分配失败\n");else{adjust();printf("申请作业的起始地址为:%d\n",start);printf("作业的申请量为:%d\n",applyarea);printf("内存分配成功\n");}}}//循环首次void Next_fit(){int applyarea,i=0;printf("请输入作业的申请量:");scanf("%d",&applyarea);/*输入作业的申请量*/if(i==N-1){i=alloc2(applyarea,i);if(i==-1)i=0;}else if(i<N-1)i=alloc2(applyarea,i);//start=alloc2(applyarea,start);/*调用alloc2()函数为作业分配空间，start为返回的始地址*/if(i==-1) /*alloc2()分配不成功时，返回-1*/printf("作业申请量过大，空闲区表中的存储空间无法满足，分配失败\n");else{adjust();printf("申请作业的起始地址为:%d\n",start);printf("作业的申请量为:%d\n",applyarea);printf("内存分配成功\n");}}//最佳void Best_fit(){int applyarea,start;printf("请输入作业的申请量:");scanf("%d",&applyarea);/*输入作业的申请量*/start=alloc3(applyarea);/*调用alloc()函数为作业分配空间，start为返回的始地址*/if(start==-1) /*alloc()分配不成功时，返回-1*/printf("作业申请量过大，空闲区表中的存储空间无法满足，分配失败\n");else{adjust();printf("申请作业的起始地址为:%d\n",start);printf("作业的申请量为:%d\n",applyarea);printf("内存分配成功\n");}}/*主函数*/void main(){loop:int ch;//算法选择标记cout<<" 动态分区分配方式的模拟 \n";cout<<"*********************************************************\ n";cout<<"** 1)首次适应算法 2)循环首次适应算法 3)最佳适应算法**\n";cout<<"*********************************************************\n"; cout<<"请选择分配算法：";cin>>ch;int choice; //操作选择标记while(1)cout<<"*************************************************\n"; cout<<"** 1: 分配内存 2: 回收内存 **\n"; cout<<"** 3: 查看空闲分区表 0: 退出 **\n"; cout<<"*************************************************\n"; cout<<"请输入您的操作：";cin>>choice;if(choice==1) // 分配内存{int ch;if(ch==1){First_fit();}if(ch==2){Next_fit();}else{Best_fit();}}else if(choice==2) // 回收内存{setfree();adjust();print();}else if(choice==3) print();//显示空闲分区表else if(choice==0) goto loop; //退出else //输入操作有误{cout<<"输入有误，请重试！"<<endl;continue;}}●程序流程图图三：程序流程图七、【测试数据和实践结果分析】：假设初始状态下，可用的内存空间为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图4：运行结果示意图实践结果分析：由测试数据知，首先进程1、2、3到达缓冲队列依次申请各自所需内存，对应着上图1，之后进程3、1依次释放，对应图2，从实验结果看，实验结果的正确性得到验证。