动态分区分配存储管理系统

1、精选优质文档-倾情为你奉上专心-专注-专业操作系统原理操作系统原理课程设计报告题目：题目：动态分区分配存储管理系统动态分区分配存储管理系统所在学院： 班 级： 学 号： 姓 名： 指导教师： 2014 年 3 月 18精选优质文档-倾情为你奉上专心-专注-专业目目 录录444556精选优质文档-倾情为你奉上专心-专注-专业1 1 引言引言操作系统是最重要的系统软件，同时也是最活跃的学科之一。我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能

2、满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。2 2 需求分析需求分析动态分区分配是根据进程的实际需要，动态地为之分配内存空间。在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。常用的数据结构有动态分区表和动态分区链。在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算

3、法） ，在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。3 3 概要设计概要设计本程序采用机构化模块化的设计方法，共分为两大模块。1最佳适应算法实现它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。2.最坏算法实现最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链

4、，查找时只要看第一个分区能否满足作业要求。4 4 详细设计详细设计4.1 问题描述和分析系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大精选优质文档-倾情为你奉上专心-专注-专业小大于请求分区大小，则从该分区中按改请求的大小划分出一块内存空间大小划分出一块内存空间分配出去，余下的部分仍留在空闲链表中。然后，将分配区的首址返回给调用者。当进程运行完毕师范内存时，系统根据回收区的首址，从空闲区中找到相应的插入点，此时可能出现以下四种情况之一：该空闲区的上下两相邻分区都是空闲区：将三个空闲区合并为一个空闲区。新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。空闲

5、区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。 该空闲区的上相邻区是空闲区：将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。合并后，修改上空闲区对应的可用表的表目项或自由链指针。 该空闲区的下相邻区是空闲区：将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。合并区的长度为释放区与下空闲区之和。同理，合并后修改可用表或自由链中相应的表目项或链指针。两相邻区都不是空闲区：释放区作为一个新空闲可用区插入可用表或自由链。4.2 程序流程图内存分配流程图，如图 4-1 所示。精选优质文档-倾情为你奉上专心-专

6、注-专业从头开始查表检索完否？分区大小所需大小分区大小-所需大小=不可再分割大小从该分区中划出所需大小的新分区将该分区分配给请求者修改有关数据结构返回继续检索下一个表项将该分区从链中移出返回YYYNNN内存回收流程图，如图 4-2 所示。开始判断空闲区上下内存情况上为空下为空上下都为空上下都不为空将上面的空闲区合并，并回收将下面的空闲区合并，并回收将上下的空闲区合并，并回收直接将其回收结束4.3 数据结构体分析进程属性结构体精选优质文档-倾情为你奉上专心-专注-专业typedef struct readyque char name10; int size;readyque,*readyqueu

7、e;空闲链表结构体typedef struct idlyspace int from; int size; idlyspace * next;idlyspace,*idly;已分配链表结构体typedef struct busyspace int from; readyque r; busyspace * next;busyspace,*busy 4.4 主要程序代码分析#include#include#includeusing namespace std;typedef struct readyque/进程的属性结构体 char name10; int size;readyque,*read

8、yqueue;typedef struct idlyspace/空闲表结构体精选优质文档-倾情为你奉上专心-专注-专业int from; int size; idlyspace * next;idlyspace,*idly,*idly1;typedef struct busyspace/已分配链表结构体int from; readyque r; busyspace * next;busyspace,*busy;static idly Is;static idly Is2;static busy Bs;int bestfit();int worstfit();int recover();void

9、 Isprint();void Bsprint();idly Sort1(idly l);idly Sort(idly l);int main()Is=(idly)malloc(sizeof(idlyspace); Is-from=0; Is-size=100; Is-next=NULL; Is2=Is; Bs=(busy)malloc(sizeof(busyspace); Bs-next=NULL;精选优质文档-倾情为你奉上专心-专注-专业 int t,t1;l1: printf(|*欢迎来到动态分区存储管理系统*|n); printf(|请选择要执行的算法: |n); printf(| 1

10、.最佳适应算法 |n); printf(| 2.最差适应算法 |n); printf(|*|n); printf(请输入您的选择:); scanf(%d,&t);system(cls);/ int i; while(i!=0)printf(|*|n); printf(| 操作菜单如下： |n); printf(| 1.分配空间 2.回收空间 |n); printf(| 3.返回上级 4.退出 |n); printf(|*|n); scanf(%d,&i);switch(i)case 1:switch(t)case 1:t1=bestfit(); break; case 2: t

11、1=worstfit(); break; default:精选优质文档-倾情为你奉上专心-专注-专业 printf(选择算法错误n); return 1;if(t1)printf(分配空间成功n);else printf(分配空间失败n);Bsprint();Isprint();break;case 2:t1=recover();if(t1)printf(回收成功n);else printf(回收失败n);Bsprint();Isprint();break;case 3:goto l1;case 4:exit(0);default: printf(输入错误，重新输入n); return 0;i

12、nt bestfit()/最佳适应算法精选优质文档-倾情为你奉上专心-专注-专业int t=0;readyque D;printf(请输入进程名:n);scanf(%s,D.name);printf(输入进程申请空间大小:n);scanf(%d,&D.size);idly l=Is;idly min=NULL;int mt=100;busy b=Bs;Sort(l);while(l)/在空闲链中寻找第一个大于所输入的进程大小的空闲块if(D.sizesize)if(D.sizesize;min=l;t=1;mt=mt-D.size;l=l-next;if(mt!=100)/找到第一个满

13、足要求的空闲块busy j;j=(busy)malloc(sizeof(busyspace);/申请分配用于存放进程的内存空间j-from=min-from;/将第一个满足要求的空闲块（min）的首地址赋给 jfor(int i=0;i=D.namei;j-r.size=D.size;/将所申请的内存大小赋给 jwhile(b-next)/按从小到大的顺序查找新进程在已分配区中的位置if(b-next-fromfrom)b=b-next;elsebreak;j-next=b-next;b-next=j;/将所输入的进程插入进程链min-from=min-from+D.size;/

14、改变该空闲块的起始地址min-size=min-size-D.size;/改变该空闲块的剩余大小return t;int worstfit()/最坏适应算法int t=0;readyque D; printf(请输入进程名:n); scanf(%s,D.name); printf(输入进程申请空间大小:n); scanf(%d,&D.size);/输入进程申请的空间大小 idly l=Is;/l 指向空闲链表 ls 头 idly min=NULL; int mt=0; busy b=Bs;/b 指向已分配链表 Bs 头 /找到空闲分区中大小满足进程的请求且尺寸最大的结点精选优质文档-倾

15、情为你奉上专心-专注-专业while(l)if(D.sizesize)/判断进程所申请的大小是否小于空闲区的各结点大小if(l-sizemt)mt=l-size;min=l;/min 指向空闲区中尺寸最大的结点t=1;l=l-next;/l 指向空闲链表下一个结点if(mt!=0)/判断是否找到了空闲区的满足结点busy j; j=(busy)malloc(sizeof(busyspace); j-from=min-from;for(int i=0;i=D.namei;j-r.size=D.size;while(b-next)/寻找插入到已分配链表中的位置if(b-next-fr

16、omfrom)b=b-next; else break; /把此进程结点 j 插入到已分配链表中精选优质文档-倾情为你奉上专心-专注-专业j-next=b-next; b-next=j; /修改空闲链表的相应结点的参数 min-from=min-from+D.size; min-size=min-size-D.size;return t;int recover()readyque D; printf(请输入想要回收的进程名n); scanf(%s,D.name); busy b=Bs; idly l=Is;while(b-next) /查找输入的进程名是否在已分配链表中int yo=1;for

17、(int i=0;i=D.namei)yo=yo*1; else yo=0; /如果在已分配链表中则释放该结点所占空间if(yo)int t=b-next-from;int ts=b-next-r.size;精选优质文档-倾情为你奉上专心-专注-专业while(l)if(l-fromt+ts)/所回收进程与空闲结点上下都不邻接idly tl; tl=(idly)malloc(sizeof(idlyspace); tl-from=t; tl-size=ts; tl-next=l; Is=tl;break;if(l-from=t+ts)/所回收进程与空闲结点下邻接l-fro

18、m=t; l-size=l-size+ts;busy tb=b-next;b-next=b-next-next;free(tb);return 1;if(l-from+l-sizefrom=t; tl-size=ts; tl-next=l-next; l-next=tl;break;精选优质文档-倾情为你奉上专心-专注-专业else if(l-from+l-size=t)/所回收进程与空闲结点上邻接l-size=l-size+ts;if(l-from+l-size=l-next-from)/所回收进程与空闲结点上下都邻接l-size=l-size+l-next-size; idly tm=l-

19、next; l-next=l-next-next;free(tm);break;l=l-next; /从已分配链表中释放所回收进程busy tb=b-next; b-next=b-next-next; free(tb); return 1;b=b-next; printf(没找到这个进程n);Sort1(l);return 0;idly Sort(idly l)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/精选优质文档-倾情为你奉上专心-专注-专业idly p,q;int temp;for(p=l;p!=NULL;p=p-next)for(q=p-next;q!=NULL;

20、q=q-next)if(p-sizeq-size)temp=q-size;q-size=p-size;p-size=temp;return l;idly Sort1(idly l)/*递增排序函数：入口参数：链表的头指针，此为链表中的排序函数*/idly p,q;int temp;for(p=l;p!=NULL;p=p-next)for(q=p-next;q!=NULL;q=q-next)if(p-sizesize)temp=q-size;q-size=p-size;p-size=temp;return l;void Isprint()/输出空闲表中进程的属性值idly t=Is;printf(-*空闲分区表*-n); printf(进程名tt 起始地址t 大小n);精选优质文档-倾情为你奉上专心-专注-专业 while(t)printf(%stt%4dtt