操作技巧系统实验二存储管理方案动态分区分配及回收算法.docx
《操作技巧系统实验二存储管理方案动态分区分配及回收算法.docx》由会员分享，可在线阅读，更多相关《操作技巧系统实验二存储管理方案动态分区分配及回收算法.docx（16页珍藏版）》请在冰点文库上搜索。
操作技巧系统实验二存储管理方案动态分区分配及回收算法
实验二存储管理动态分区分配及回收算法
一、实验目的
通过分区管理实验，了解操作系统的基本概念，理解计算机系统的资源如何组织，操作系统如何有效地管理这些系统资源，用户如何通过操作系统与计算机系统打交道。
通过课程设计，我们可以进一步理解在计算机系统上运行的其它各类操作系统，并懂得在操作系统的支持下建立自己的应用系统。
二、实验要求
本实验要求用一种结构化高级语言构造分区描述器，编制动态分区分配算法和回收算法模拟程序，并掌握分配算法的特点，提高编程技巧和对算法的理解和掌握。
三、实验过程
1．准备
（一）主程序
1、定义分区描述器node，包括3个元素：
（1）adr——分区首地址
（2）size——分区大小
（3）next——指向下一个分区的指针
2、定义3个指向node结构的指针变量：
（1）head1——空闲区队列首指针
（2）back1——指向释放区node结构的指针
（3）assign——指向申请的内存分区node结构的指针
3、定义1个整形变量：
free——用户申请存储区的大小（由用户键入）
（二）过程
1、定义check过程，用于检查指定的释放块（由用户键入）的合法性
2、定义assignment1过程，实现FirstFitAlgorithm
3、定义assignment2过程，实现BestFitAlgorithm
4、定义acceptment1过程，实现FirstFitAlgorithm的回收算法
5、定义acceptment2过程，实现BestFitAlgorithm的回收算法
6、定义print过程，打印空闲区队列
（三）执行
程序首先申请一整块空闲区，其首址为0，大小为32767；然后，提示用户使用哪种分配算法，再提示是分配还是回收；分配时要求输入申请区的大小，回收时要求输入释放区的首址和大小。
（四）输出
要求每执行一次，输出一次空闲区队列情况，内容包括：
编号首址终址大小
2.主要流程和源代码
实验二源代码
#include
#include
#include
#defineMAX_SIZE32767
typedefstructnode{
intid;
intadr;
intsize;
structnode*next;
}Node;
Node*head1,*head2,*back1,*back2,*assign;
intrequest;
intcheck（intadd,intsiz,charc）
{
Node*p,*head;
intcheck=1;
if（add<0||siz<0）
check=0;/*地址和大小不能为负*/
if（c=='f'||c=='F'）
head=head1;
else
head=head2;
p=head->next;
while（（p!
=NULL）&&check）
if（（（addadr）&&（add+siz>p->adr））||（（add>=p->adr）&&（addadr+p->size）））
check=0;
else
p=p->next;
if（check==0）
printf（"\t输入释放区地址或大小有错误！
！
！
\n"）;
returncheck;
}
voidinit（）
{
Node*p;
head1=（Node*）malloc（sizeof（Node））;
head2=（Node*）malloc（sizeof（Node））;
p=（Node*）malloc（sizeof（Node））;
head1->next=p;
head2->next=p;
p->size=MAX_SIZE;
p->adr=0;
p->next=NULL;
p->id=0;
}
Node*assignment1（intnum,intreq）
{
Node*before,*after,*ass;
ass=（Node*）malloc（sizeof（Node））;
before=head1;
after=head1->next;
ass->id=num;
ass->size=req;
while（after->size{
before=before->next;
after=after->next;
}
if（after==NULL）
{
ass->adr=-1;}
else
{
if（after->size==req）
{
before->next=after->next;
ass->adr=after->adr;
}
else
{
after->size-=req;
ass->adr=after->adr;
after->adr+=req;
}
}
returnass;
}
voidacceptment1（intaddress,intsiz,intrd）
{
Node*before,*after;
intinsert=0;
back1=（Node*）malloc（sizeof（Node））;
before=head1;
after=head1->next;
back1->adr=address;
back1->size=siz;
back1->id=rd;
back1->next=NULL;
while（!
insert&&after）
{//将要被回收的分区插入空闲区（按首址大小从小到大插入）
if（（after==NULL）||（（back1->adr<=after->adr）&&（back1->adr>=before->adr）））
{
before->next=back1;
back1->next=after;
insert=1;
}
else
{
before=before->next;
after=after->next;
}
}
if（insert）
{
if（back1->adr==before->adr+before->size）
{//和前边分区合并
before->size+=back1->size;
before->next=back1->next;
free（back1）;
}
elseif（after&&back1->adr+back1->size==after->adr）
{//和后边分区合并
back1->size+=after->size;
back1->next=after->next;
back1->id=after->id;
free（after）;
after=back1;
}
printf（"\t首先分配算法回收内存成功！
\n"）;
}
else
printf（"\t首先分配算法回收内存失败！
\n"）;
}
Node*assignment2（intnum,intreq）
{
Node*before,*after,*ass,*q;
ass=（Node*）malloc（sizeof（Node））;
q=（Node*）malloc（sizeof（Node））;
before=head2;
after=head2->next;
ass->id=num;
ass->size=req;
while（after->size{
before=before->next;
after=after->next;
}
if（after==NULL）
{
ass->adr=-1;
}
else
{
if（after->size==req）
{
before->next=after->next;
ass->adr=after->adr;
}
else
{
q=after;
before->next=after->next;
ass->adr=q->adr;
q->size-=req;
q->adr+=req;
before=head2;
after=head2->next;
if（after==NULL）
{
before->next=q;
q->next=NULL;
}
else
{
while（（after->size）<（q->size））
{
before=before->next;
after=after->next;
}
before->next=q;
q->next=after;
}
}
}
return（ass）;
}
voidacceptment2（intaddress,intsiz,intrd）
{
Node*before,*after;
intinsert=0;
back2=（Node*）malloc（sizeof（Node））;
before=head2;
after=head2->next;
back2->adr=address;
back2->size=siz;
back2->id=rd;
back2->next=NULL;
if（head2->next==NULL）
{//空闲队列为空
head2->next=back2;
head2->size=back2->size;
}
else
{//空闲队列不为空
while（after）
{
if（back2->adr==after->adr+after->size）
{//和前边空闲分区合并
before->next=after->next;
after->size+=back2->size;
back2=after;
}
else
{
before=before->next;
after=after->next;
}
}
before=head2;
after=head2->next;
while（after）
{
if（after->adr==back2->adr+back2->size）
{//和后边空闲区合并
before->next=after->next;
back2->size+=after->size;
}
else
{
before=before->next;
after=after->next;
}
}
before=head2;
after=head2->next;
while（!
insert）
{//将被回收的块插入到恰当的位置（按分区大小从小到大）
if（after==NULL||（（after->size>back2->size）&&（before->sizesize）））
{
before->next=back2;
back2->next=after;
insert=1;
break;
}
else
{
before=before->next;
after=after->next;
}
}
}
if（insert）
printf（"\t最佳适应算法回收内存成功！
\n"）;
else
printf（"\t最佳适应算法回收内存失败！
！
\n"）;
}
voidprint（charchoice）//输出空闲区队列信息
{
Node*p;
if（choice=='f'||choice=='F'）
p=head1->next;
else
p=head2->next;
if（p）
{
printf（"\n空闲区队列的情况为：
\n"）;
printf（"\t编号\t首址\t终址\t大小\n"）;
while（p）
{
printf（"\t%d\t%d\t%d\t%d\n",p->id,p->adr,p->adr+p->size-1,p->size）;
p=p->next;
}
}
}
voidmenu（）//菜单及主要过程
{
charchose;
intch,num,r,add,rd;
while
（1）
{
system（"cls"）;
printf（"选择最先适应算法请输入F，选择最佳适应算法请输入B，退出程序请输入E\n\n"）;
printf（"请输入你的选择:
"）;
scanf（"%c",&chose）;
if（chose=='e'||chose=='E'）
exit（0）;
else
{
system（"cls"）;
while
（1）
{
if（chose=='f'||chose=='F'）
printf（"最先适应算法（First-Fit）模拟:
\n"）;
if（chose=='b'||chose=='B'）
printf（"最佳适应算法（Best-Fit）模拟:
\n"）;
printf（"1.分配内存,2.回收内存,3.查看内存,4.返回\n\n"）;
printf（"请输入你的选择:
"）;
scanf（"%d",&ch）;
fflush（stdin）;
switch（ch）
{
case1:
printf（"输入申请的分区大小：
"）;scanf（"%d",&r）;
if（chose=='f'||chose=='F'）
assign=assignment1（num,r）;
else
assign=assignment2（num,r）;
if（assign->adr==-1）
{
printf（"分配内存失败！
\n"）;
}
else
printf（"分配成功！
分配的内存的首址为:
%d\n",assign->adr）;
break;
case2:
printf（"输入释放的内存的首址：
"）;scanf（"%d",&add）;
printf（"输入释放的内存的大小：
"）;scanf（"%d",&r）;
printf（"输入释放的内存的编号：
"）;scanf（"%d",&rd）;
if（check（add,r,chose））
{
if（chose=='f'||chose=='F'）
acceptment1（add,r,rd）;
else
acceptment2（add,r,rd）;
}
break;
case3:
print（chose）;
break;
case4:
menu（）;
break;
}
}
}
}
}
voidmain（）//主函数
{
init（）;
menu（）;
}
四、实验结果
五、实验总结
通过这次课程设计我练习了用C语言写系统软件，对操作系统中可变分区存储管理有了更深刻的了解。
在写程序的时候也遇到了一些困难。
比如在设计数据结构时特别犹豫，总想找一个很合适的。
但是，后来才知道，关键要多尝试，而空想是没有用的。
最后我证实了自己的设计的合理性。
还有为了使程序更健壮，在网上下载了几个代码，进行调试，运行、查看结果。
看懂代码和结果后，这次实验也算是成功的一大半了。
总之这次实验还是让我收获很大，让我在书本上的知识能够运用到实际当中。
这种学以致用的感觉才是最好的。
升级会员 