操作系统存储器的分配与回收算法实现.doc
《操作系统存储器的分配与回收算法实现.doc》由会员分享，可在线阅读，更多相关《操作系统存储器的分配与回收算法实现.doc（20页珍藏版）》请在冰点文库上搜索。
操作系统实验报告
操作系统实验报告
存储器的分配与回收算法实现
姓名：
学号：
09070009
班级：
09计算机1
一、实验名称及要求
1、实验名称：
存储器的分配与回收算法实现
2、实验要求：
学生应正确地设计有关的数据结构与各个功能模块，画出程序的流程图，编写程序，程序执行结果应正确。
3、实验方式：
学生通过实验室的微机上机，实际调试程序。
。
4、实验环境：
Windows操作系统环境下的个人微机
Ｃ或Ｃ＋＋程序设计语言
二、实验内容
1本实验是模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。
2采用最先适应法、最佳适应法、最坏适应法分配主存空间。
3当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。
若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。
4当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。
5运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。
三、实验程序
#include
#include
#include
typedefstructFreeLink{//定义自由链
structFreeLink*prior;
charname;
intstart;
intsize;
boolflag;
structFreeLink*next;
}*ptr,*head;
headtop;
ptrp;
voidprint（）{//将内存分配情况打印到屏幕上
p=top;
cout<<"************************内存分配情况表************************"< cout<<"区号\t\t"<<"起始位置\t"<<"区间长度\t"<<"区间状态\t"< do{
cout<name<<"\t\t"<start<<"\t\t"<size<<"\t\t";
if（p->flag==false）{cout<<"空闲"< else{cout<<"已占用"< p=p->next;
}
while（p!
=NULL）;
}
voidclear（）{//结束操作时清空“内存”以备其他操作
do{
p=top;
top=top->next;
free（p）;
}
while（top!
=NULL）;
}
voidasc（ptr&p）{//最佳适应法的内存分配函数
intmin;
ptrop;
FreeLink*fl=（FreeLink*）malloc（sizeof（FreeLink））;
cout<<"请输入要分配内存的进程名"< cin>>fl->name;
cout<<"请输入要分配内存的大小"< cin>>fl->size;
min=256;
fl->flag=true;
do{
if（p->flag==false&&p->size<=min&&p->size>=fl->size）{
min=p->size;
op=p;
}
p=p->next;
}
while（p!
=NULL）;
if（op->size>fl->size）{
fl->start=op->start;
op->start=fl->start+fl->size;
op->size=op->size-fl->size;
fl->next=op;
fl->prior=op->prior;
op->prior->next=fl;
op->prior=fl;
gotoflag1;
}
if（op->size==fl->size）{
op->flag=fl->flag;
op->name=fl->name;
free（fl）;
gotoflag1;
}
cout<<"内存过小，分配失败！
"<flag1:
cout<<"分配成功！
"<flag2:
;
}
voiddec（ptr&p）{//最坏适应法的内存分配函数
intmax;
ptrop;
FreeLink*fl=（FreeLink*）malloc（sizeof（FreeLink））;
cout<<"请输入要分配内存的进程名"< cin>>fl->name;
cout<<"请输入要分配内存的大小"< cin>>fl->size;
max=fl->size;
fl->flag=true;
do{
if（p->flag==false&&p->size>=max）{
max=p->size;
op=p;
}
p=p->next;
}
while（p!
=NULL）;
if（op->size>fl->size）{
fl->start=op->start;
op->start=fl->start+fl->size;
op->size=op->size-fl->size;
fl->next=op;
fl->prior=op->prior;
op->prior->next=fl;
op->prior=fl;
gotoflag3;
}
if（op->size==fl->size）{
op->flag=fl->flag;
op->name=fl->name;
free（fl）;
gotoflag3;
}
cout<<"内存过小，分配失败！
"<flag3:
cout<<"分配成功！
"<flag4:
;
}
voidsplice（ptr&p）{//若被操作的内存有相邻空闲区则将空闲区拼接合并
intx;
if（p->prior->flag==false&&p->next->flag==false）x=1;
if（（p->prior->flag==false&&p->next->flag==true）||（p->prior->flag==false&&p->next==NULL））x=2;
if（（p->prior->flag==true&&p->next->flag==false）||（p->prior==NULL&&p->next->flag==false））x=3;
if（（p->prior->flag==true&&p->next->flag==true）||（p->prior==NULL&&p->next->flag==true）||（p->prior->flag==true&&p->next==NULL））x=4;
switch（x）{
case1:
p->next->prior=p->prior;
p->prior->next=p->next;
p->prior->size=p->prior->size+p->size+p->next->size;
p->prior->next=p->next->next;
if（p->next->next!
=NULL）p->next->next->prior=p->next->prior;
free（p->next）;
free（p）;
break;
case2:
if（p->next==NULL）{
p->prior->next=p->next;
}else{
p->next->prior=p->prior;
p->prior->next=p->next;
}
p->prior->size=p->prior->size+p->size;
free（p）;
break;
case3:
if（p->prior==NULL）{
top=p->next;
p->next->prior=NULL;
p->next->start=p->start;
p->next->size=p->next->size+p->size;
}else{
p->next->prior=p->prior;
p->prior->next=p->next;
p->next->start=p->start;
p->next->size=p->next->size+p->size;
}
free（p）;
break;
case4:
p->name='@';
p->flag=false;
break;
}
}
voidallocate（ptr&p）{//最先适应法的内存分配函数
FreeLink*fl=（FreeLink*）malloc（sizeof（FreeLink））;
cout<<"请输入要分配内存的进程名"< cin>>fl->name;
cout<<"请输入要分配内存的大小"< cin>>fl->size;
fl->flag=true;
do{
if（p->flag==false&&p->size>fl->size）{
fl->start=p->start;
p->start=fl->start+fl->size;
p->size=p->size-fl->size;
fl->next=p;
fl->prior=p->prior;
p->prior->next=fl;
p->prior=fl;
gotoa;
}
if（p->flag==false&&p->size==fl->size）{
p->flag=fl->flag;
p->name=fl->name;
free（fl）;
gotoa;
}
p=p->next;
}
while（p!
=NULL）;
cout<<"内存过小，分配失败！
"<a:
cout<<"分配成功！
"<b:
;
}
voidrecover（ptr&p）{//内存回收函数
charn='';
cout<<"请输入要回收的内存对应的进程名";
cin>>n;
do{
if（p->flag==true&&p->name==n）{
splice（p）;
gotoc;
}
p=p->next;
}
while（p!
=NULL）;
cout<<"内存并未分配给对应进程，回收失败！
"<c:
cout<<"内存回收成功！
"<d:
;
}
intffa（）{//最先适应法
charchoice='';
print（）;
ptrpcb=（FreeLink*）malloc（sizeof（FreeLink））;
pcb->next=top;
pcb->prior=top->prior;
top->prior=pcb;
pcb->start=top->start;
cout<<"请输入要为系统分配的内存块名"< cin>>pcb->name;
cout<<"请输入要分配内存的大小"<e:
cout<<"超过内存最大容量请重新输入要分配内存的大小"<f:
cin>>pcb->size;
if（pcb->size>256）gotoe;
top->size=top->size-pcb->size;
top=pcb;
top->flag=true;
top->next->start+=top->size;
print（）;
while（true）{
do{
p=top->next;
cout<<"请从下列选项中进行选择"< cout<<"1.分配内存"< cout<<"2.回收内存"< cout<<"3.结束操作"< cout<<"请输入你的选择";
cin>>choice;
}
while（choice!
='1'&&choice!
='2'&&choice!
='3'）;
switch（choice）{
case'1':
allocate（p）;print（）;break;
case'2':
recover（p）;print（）;break;
case'3':
clear（）;return0;break;
}
}
}
intbfa（）{//最佳适应法
charchoice='';
print（）;
ptrpcb=（FreeLink*）malloc（sizeof（FreeLink））;
pcb->next=top;
pcb->prior=top->prior;
top->prior=pcb;
pcb->start=top->start;
cout<<"请输入要为系统分配的内存块名"< cin>>pcb->name;
cout<<"请输入要分配内存的大小"<g:
cout<<"超过内存最大容量请重新输入要分配内存的大小"<h:
cin>>pcb->size;
if（pcb->size>256）gotog;
top->size=top->size-pcb->size;
top=pcb;
top->flag=true;
top->next->start+=top->size;
print（）;
while（true）{
do{
p=top->next;
cout<<"请从下列选项中进行选择"< cout<<"1.分配内存"< cout<<"2.回收内存"< cout<<"3.结束操作"< cout<<"请输入你的选择";
cin>>choice;
}
while（choice!
='1'&&choice!
='2'&&choice!
='3'）;
switch（choice）{
case'1':
asc（p）;print（）;break;
case'2':
recover（p）;print（）;break;
case'3':
clear（）;return0;break;
}
}
}
intwfa（）{//最坏适应法
charchoice='';
print（）;
ptrpcb=（FreeLink*）malloc（sizeof（FreeLink））;
pcb->next=top;
pcb->prior=top->prior;
top->prior=pcb;
pcb->start=top->start;
cout<<"请输入要为系统分配的内存块名"< cin>>pcb->name;
cout<<"请输入要分配内存的大小"<i:
cout<<"超过内存最大容量请重新输入要分配内存的大小"<j:
cin>>pcb->size;
if（pcb->size>256）gotoi;
top->size=top->size-pcb->size;
top=pcb;
top->flag=true;
top->next->start+=top->size;
print（）;
while（true）{
do{
p=top->next;
cout<<"请从下列选项中进行选择"< cout<<"1.分配内存"< cout<<"2.回收内存"< cout<<"3.结束操作"< cout<<"请输入你的选择";
cin>>choice;
}
while（choice!
='1'&&choice!
='2'&&choice!
='3'）;
switch（choice）{
case'1':
dec（p）;print（）;break;
case'2':
recover（p）;print（）;break;
case'3':
clear（）;return0;break;
}
}
}
intmain（）{//主函数
charchoice='';
ptrfree=（FreeLink*）malloc（sizeof（FreeLink））;
top=free;
top->name='@';
top->start=0;
top->size=256;
top->flag=false;
top->prior=NULL;
top->next=NULL;
cout<<"***************Memoryallocationandrecoveryalgorithm***************"< cout<<"************************存储器的分配与回收算法************************"< while（true）{
do{
cout<<"请从下列选项中进行选择"< cout<<"1.最先适应算法"< cout<<"2.最优适应算法"< cout<<"3.最坏适应算法"< cout<<"4.退出"< cout<<"请输入你的选择";
cin>>choice;
}
while（choice!
='1'&&choice!
='2'&&choice!
='3'&&choice!
='4'）;
switch（choice）{
case'1':
ffa（）;break;
case'2':
bfa（）;break;
case'3':
wfa（）;break;
case'4':
return0;break;
}
}
}
四、实验结果
最先适应法
最佳适应法
最坏适应法
五．实验总结
知道了存储器的分配与回收算法实现方法，采用最先适应法、最佳适应法、最坏适应法分配主存空间。
当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。
若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。
当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。
最后感谢李老师的指导。
19
升级会员 