动态分区存储管理系统分解.docx
《动态分区存储管理系统分解.docx》由会员分享，可在线阅读，更多相关《动态分区存储管理系统分解.docx（20页珍藏版）》请在冰点文库上搜索。
动态分区存储管理系统分解
操作系统原理
课程设计报告
题目：
动态分区分配存储管理系统
所在学院：
计算机科学与技术学院
班级：
11级计算机科学与技术（非师）
学号：
20111202052
姓名：
吴创连
指导教师：
黄侠剑
2014年3月18
目录
1引言1
2需求分析1
3概要设计1
4详细设计1
4.1问题描述和分析1
4.2程序流程图2
4.3数据结构体分析3
4.4主要程序代码分析4
5调试与操作说明11
5.1初始界面11
5.2模拟内存分配12
5.3回收内存界面12
5.4最佳适应算法的实现13
5.5最坏适应算法的实现13
6总结与体会13
1引言
操作系统是最重要的系统软件，同时也是最活跃的学科之一。
我们通过操作系统可以理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。
存储器是计算机系统的重要组成部分，近年来，存储器容量虽然一直在不断扩大，但仍不能满足现代软件发展的需要，因此，存储器仍然是一种宝贵而又紧俏的资源。
如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且还对系统性能有重大影响。
而动态分区分配属于连续分配的一种方式，它至今仍在内存分配方式中占有一席之地。
2需求分析
动态分区分配是根据进程的实际需要，动态地为之分配内存空间。
在实现动态分区分配时，将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配和回收操作这样三个问题。
常用的数据结构有动态分区表和动态分区链。
在对数据结构有一定掌握程度的情况下设计合理的数据结构来描述存储空间，实现分区存储管理的内存分配功能，应该选择最合适的适应算法（最佳适应算法，最坏适应算法），在动态分区存储管理方式中主要实现内存分配和内存回收算法，在这些存储管理中间必然会有碎片的产生，当碎片产生时，进行碎片的拼接等相关的内容。
3概要设计
本程序采用机构化模块化的设计方法，共分为两大模块。
1．最佳适应算法实现
它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。
为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。
2.最坏算法实现
最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。
该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。
4详细设计
4.1问题描述和分析
系统应利用某种分配算法，从空闲分区链表中找到所需大小的分区，如果空闲分区大小大于请求分区大小，则从该分区中按改请求的大小划分出一块内存空间大小划分出一块内存空间分配出去，余下的部分仍留在空闲链表中。
然后，将分配区的首址返回给调用者。
当进程运行完毕师范内存时，系统根据回收区的首址，从空闲区中找到相应的插入点，此时可能出现以下四种情况之一：
⑴该空闲区的上下两相邻分区都是空闲区：
将三个空闲区合并为一个空闲区。
新空闲区的起始地址为上空闲区的起始地址，大小为三个空闲区之和。
空闲区合并后，取消可用表或自由链中下空闲区的表目项或链指针，修改上空闲区的对应项。
⑵该空闲区的上相邻区是空闲区：
将释放区与上空闲区合并为一个空闲区，其起始地址为上空闲区的起始地址，大小为上空闲区与释放区之和。
合并后，修改上空闲区对应的可用表的表目项或自由链指针。
⑶该空闲区的下相邻区是空闲区：
将释放区与下空闲区合并，并将释放区的起始地址作为合并区的起始地址。
合并区的长度为释放区与下空闲区之和。
同理，合并后修改可用表或自由链中相应的表目项或链指针。
⑷两相邻区都不是空闲区：
释放区作为一个新空闲可用区插入可用表或自由链。
4.2程序流程图
内存分配流程图，如图4-1所示。
内存回收流程图，如图4-2所示。
4.3数据结构体分析
⑴进程属性结构体
typedefstructreadyque
{
charname[10];
intsize;
}readyque,*readyqueue;
⑵空闲链表结构体
typedefstructidlyspace
{
intfrom;
intsize;
idlyspace*next;
}idlyspace,*idly;
⑶已分配链表结构体
typedefstructbusyspace
{
intfrom;
readyquer;
busyspace*next;
}busyspace,*busy
4.4主要程序代码分析
#include
#include
#include
usingnamespacestd;
typedefstructreadyque//进程的属性结构体
{
charname[10];
intsize;
}readyque,*readyqueue;
typedefstructidlyspace//空闲表结构体
{
intfrom;
intsize;
idlyspace*next;
}idlyspace,*idly;
typedefstructbusyspace//已分配链表结构体
{
intfrom;
readyquer;
busyspace*next;
}busyspace,*busy;
staticidlyIs;
staticidlyIs2;
staticbusyBs;
intbestfit（）;
intworstfit（）;
intrecover（）;
voidIsprint（）;
voidBsprint（）;
intmain（）
{
Is=（idly）malloc（sizeof（idlyspace））;
Is->from=0;
Is->size=100;
Is->next=NULL;
Is2=Is;
Bs=（busy）malloc（sizeof（busyspace））;
Bs->next=NULL;
intt,t1;
l1:
printf（"|********欢迎来到动态分区存储管理系统***************|\n"）;
printf（"|请选择要执行的算法:
|\n"）;
printf（"|1.最佳适应算法|\n"）;
printf（"|2.最差适应算法|\n"）;
printf（"|***************************************************|\n"）;
printf（"请输入您的选择:
"）;
scanf（"%d",&t）;
system（"cls"）;//
inti;
while（i!
=0）
{
printf（"|**************************************************|\n"）;
printf（"|操作菜单如下：
|\n"）;
printf（"|1.分配空间2.回收空间|\n"）;
printf（"|3.返回上级4.退出|\n"）;
printf（"|**************************************************|\n"）;
scanf（"%d",&i）;
system（"cls"）;
switch（i）
{
case1:
switch（t）
{
case1:
t1=bestfit（）;
break;
case2:
t1=worstfit（）;
break;
default:
printf（"选择算法错误\n"）;
return1;
}
if（t1）
printf（"分配空间成功\n"）;
else
printf（"分配空间失败\n"）;
Bsprint（）;
Isprint（）;
break;
case2:
t1=recover（）;
if（t1）
printf（"回收成功\n"）;
else
printf（"回收失败\n"）;
Bsprint（）;
Isprint（）;
break;
case3:
gotol1;
case4:
exit（0）;
default:
printf（"输入错误，重新输入\n"）;
}
}
return0;
}
intbestfit（）//最佳适应算法
{
intt=0;
readyqueD;
printf（"请输入进程名:
\n"）;
scanf（"%s",D.name）;
printf（"输入进程申请空间大小:
\n"）;
scanf（"%d",&D.size）;
idlyl=Is;
idlymin=NULL;
intmt=100;
busyb=Bs;
while（l）//在空闲链中寻找第一个大于所输入的进程大小的空闲块
{
if（D.size<=l->size）
{
if（D.size{
mt=l->size;
min=l;
t=1;
mt=mt-D.size;
}
}
l=l->next;
}
if（mt!
=100）//找到第一个满足要求的空闲块
{
busyj;
j=（busy）malloc（sizeof（busyspace））;//申请分配用于存放进程的内存空间
j->from=min->from;//将第一个满足要求的空闲块（min）的首地址赋给j
for（inti=0;i<10;i++）//将所申请的进程名赋给j
{
j->r.name[i]=D.name[i];
}
j->r.size=D.size;//将所申请的内存大小赋给j
while（b->next）//按从小到大的顺序查找新进程在已分配区中的位置
{
if（b->next->fromfrom）
b=b->next;
else
break;
}
j->next=b->next;
b->next=j;//将所输入的进程插入进程链
min->from=min->from+D.size;//改变该空闲块的起始地址
min->size=min->size-D.size;//改变该空闲块的剩余大小
}
returnt;
}
intworstfit（）//最坏适应算法
{
intt=0;
readyqueD;
printf（"请输入进程名:
\n"）;
scanf（"%s",D.name）;
printf（"输入进程申请空间大小:
\n"）;
scanf（"%d",&D.size）;//输入进程申请的空间大小
idlyl=Is;//l指向空闲链表ls头
idlymin=NULL;
intmt=0;
busyb=Bs;//b指向已分配链表Bs头
//找到空闲分区中大小满足进程的请求且尺寸最大的结点
while（l）
{
if（D.size<=l->size）//判断进程所申请的大小是否小于空闲区的各结点大小
{
if（l->size>mt）
{
mt=l->size;
min=l;//min指向空闲区中尺寸最大的结点
t=1;
}
}
l=l->next;//l指向空闲链表下一个结点
}
if（mt!
=0）//判断是否找到了空闲区的满足结点
{
busyj;
j=（busy）malloc（sizeof（busyspace））;
j->from=min->from;
for（inti=0;i<10;i++）
{
j->r.name[i]=D.name[i];
}
j->r.size=D.size;
while（b->next）//寻找插入到已分配链表中的位置
{
if（b->next->fromfrom）
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;
}
returnt;
}
intrecover（）
{
readyqueD;
printf（"请输入想要回收的进程名\n"）;
scanf（"%s",D.name）;
busyb=Bs;
idlyl=Is;
while（b->next）//查找输入的进程名是否在已分配链表中
{
boolyo=1;
for（inti=0;i<10;i++）
{
if（b->next->r.name[i]==D.name[i]）
yo=yo*1;
else
yo=0;
}
//如果在已分配链表中则释放该结点所占空间
if（yo）
{
intt=b->next->from;
intts=b->next->r.size;
while（l）
{
if（l->from>t+ts）//所回收进程与空闲结点上下都不邻接
{
idlytl;
tl=（idly）malloc（sizeof（idlyspace））;
tl->from=t;
tl->size=ts;
tl->next=l;
Is=tl;
break;
}
if（l->from==t+ts）//所回收进程与空闲结点下邻接
{
l->from=t;
l->size=l->size+ts;
busytb=b->next;
b->next=b->next->next;
free（tb）;
return1;
}
if（l->from+l->size{
idlytl;
tl=（idly）malloc（sizeof（idlyspace））;
tl->from=t;
tl->size=ts;
tl->next=l->next;
l->next=tl;
break;
}
elseif（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;
idlytm=l->next;
l->next=l->next->next;
free（tm）;
}
break;
}
l=l->next;
}
//从已分配链表中释放所回收进程
busytb=b->next;
b->next=b->next->next;
free（tb）;
return1;
}
b=b->next;
}
printf（"没找到这个进程\n"）;
return0;
}
voidIsprint（）//输出空闲表中进程的属性值
{
idlyt=Is;
printf（"---------************空闲分区表***********---------\n"）;
printf（"进程名\t\t起始地址\t大小\n"）;
while（t）
{
printf（"%s\t\t%4d\t\t%4d\n",0,t->from,t->size）;
t=t->next;
}
}
voidBsprint（）//输出已分配表中进程的属性值
{
busyt=Bs->next;
printf（"-----------**********已分配分区表*********---------\n"）;
printf（"进程名\t\t起始地址\t大小\n"）;
while（t）
{
printf（"%s\t\t%4d\t\t%4d\n",t->r.name,t->from,t->r.size）;
t=t->next;
}
}
5调试与操作说明
5.1初始界面
程序初始界面，有两个块选择，选择要执行的算法，调试以最佳算法为例，如图5-1和5-2所示。
图5-1
图5-2
5.2模拟内存分配
给进程1分配内存10，如图5-3所示。
图5-3
5.3回收内存界面
回收进程1所占内存，如图5-4所示。
图5-4
5.4最佳适应算法的实现
如图5-5所示。
图5-5
5.5最坏适应算法的实现
如图5-6所示。
图5-4
6总结与体会
本次做的课题是动态分区分配算法实现，此次课程设计成功实现了内存分配和内存回收，内存分配中包含了两种算法，分别是最佳适应算法和最坏适应算法。
经编码调试，表明该程序模块是有效可行的。
在开始做的时候发现根本不知道该从什么地方下手，接着便开始上网查找，但是网络上的东西很多都是没有用的，于是自己开始去图书馆找资料，看了很多有关动态分区分配算法方面的知识以后，才对这两个算法有了新的理解，于是在掌握了这些基础知识之上，对课题进行分析，然后便一步步按照要求编写程序。
此次的课程设计，学到了很多知识。
因此首先要感谢周老师，为我提供了实践的机会，我才有这样一个学习知识的机会。
其次，在本次课程设计的过程中，我要感谢我的同学，正是由于他们的帮助和支持，我才能比较顺利的完成这次课程设计任务。
在此，我表示由衷地感谢。
升级会员 