华南操作系统大作业.docx
《华南操作系统大作业.docx》由会员分享，可在线阅读，更多相关《华南操作系统大作业.docx（31页珍藏版）》请在冰点文库上搜索。
华南操作系统大作业
“计算机操作系统”
动态内存分区分配方式模拟
学生姓名
专业名称
学号
目录
1题目要求1
2设计思想1
3数据定义2
4处理流程3
5源程序6
6运行结果15
7设计体会22
动态内存分区分配方式模拟
1题目要求
假设初始态下，可用内存空间为640K，并有下列请求序列，请分别用首次适应算法和最佳适应算法为作业分配和回收内存块，并显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。
作业1申请130K
作业2申请60K
作业3申请100k
作业2释放60K
作业4申请200K
作业3释放100K
作业1释放130K
作业5申请140K
作业6申请60K
作业7申请50K
作业6释放60K
2设计思想
根据题目要求，要用首次适应算法和最佳适应算法分别实现内存的动态分区，因此先介绍一下这两种算法的基本思想：
首次适应算法中，空闲分区链是按地址递增的次序链接的，当要分配内存空间时，就查表，在各空闲分区中查找满足大小要求的可用块，只要找到第一个足以满足要求的空间就停止查找，并把它分配出去，如果该空闲空间与所需空间大小一样，则将该分区的状态改为1，即已被分配，若还有剩余，则将剩余空间重新划为一个空闲分区，有新的起始地址，状态为0。
最佳适应算法的空闲链是按照空闲块的大小为序、按增量方式排列的，即小块在前，大块在后，它在满足需要的前提下，尽量分配最小的空闲块，这样每次查找分配时第一次找到的能满足要求的必然的最佳的，若空闲空间大小与要分配的大小相差不多时，可直接将其状态改为1即可，若有剩余，则将剩余空闲空间重新划分为一个空闲区，并根据空闲区的大小对链表进行重新排序。
首次适应算法的回收过程相对简单，因为分区链是按照地址顺序链接的，因此释放内存时只需要判断要释放的分区前后是否也为空闲区，然后根据情况看是要跟前边或后边或前后都合并为一个大的空闲区，如果前后分区都已分配，则直接将该分区状态改为0即可。
最佳适应算法回收时，因为它的分区链是按照空间大小排列的，因此不仅要看要释放分区前后是否为空闲，还要判断其地址是否前后相接，若地址不相接，则即使要释放分区前后均为空闲区，也不能进行合并，而且每次释放后要根据释放空间的大小对链表进行重新排序。
3数据定义
动态分区常用的数据结构有空闲分区表和空闲分区链，用来记录内存的使用情况，此题中我采用的是空闲分区链的结构，用链指针将所有的分区链接成一条链，每个分区的结构如下所示：
structmemory
{
structmemory*former;//前向指针
intaddress;//分区起始地址
intnum;//作业号
intsize;//分配内存大小
intstate;//状态字
structmemory*next;//后向指针
};
前向指针和后向指针分别用于与当前分区的前后分区相链接，address用于说明当前分区的起始地址，状态字为0时表示当前分区空闲，为1时表示已分配，num为分配的作业号，size表示分配的内存大小。
4处理流程
分配算法
详细流程图见图5.1.1，其中各个条件分别为：
P1:
ptr->next==NULL
P2:
ptr->size>=assign->size
P3:
current!
=NULL
P4:
current->size>=assign->size&¤t->state==0
P5:
ptr->size>=assign->size
P6:
（ptr->next）->next!
=NULL&&is_optimist==true
回收算法
详细流程图见图5.1.2
若为首先适应算法回收，则各条件分别为：
P1:
current!
=NULL
P2:
current->state==1&¤t->num==i
P3:
current==NULL
P4:
current->next==NULL
P5:
previous->state==0
P6:
（current->next）->next==NULL
P7:
previous->state==0&&（current->next）->state==0
P8:
（current->next）->state==0
P9:
is_optimist=true
若为最佳适应算法，则各条件分别为：
P1:
current!
=NULL
P2:
current->state==1&¤t->num==i
P3:
current==NULL
P4:
current->next==NULL
P5:
previous->state==0&&（（previous->address+previous->size）==current->addr
ess）
P6:
（current->next）->next==NULL
P7:
previous->state==0&&（current->next）->state==0&&（（previous->address+pr
evious->size）==current->address）&&（（current->size+current->address）==（current->next）->address）
P8:
（current->next）->state==0&&（（current->size+current->address）==（current->next）->address）
5源程序
程序如下所示：
#include
#include
usingnamespacestd;
structmemory
{
structmemory*former;//前向指针
intaddress;//地址
intnum;//作业号
intsize;//分配内存大小
intstate;//状态0表示空闲1表示已分配
structmemory*next;//后向指针
};
typedefstructmemoryMEMORY;
MEMORY*mem;
constintsize_min=10;//内存允许的最小空闲块的大小
boolis_optimist;//判断是否是最佳适应算法
voidinit（）;//初始化内存块
voidexec（）;//执行相应算法
voidF_F（int）;//依次初始化每个作业,并根据相应算法对作业分配内存
voidalloc（MEMORY*,MEMORY*）;//分配内存算法（包括两种不同算法）
voidfree（MEMORY*,int）;//首次适应算法回收内存
voidfree_optimist（MEMORY*,int）;//最佳适应算法回收内存
voidsort（MEMORY*）;//对内存链进行排序
voidinsert（MEMORY*,MEMORY*）;//按空间大小将作业顺序插入到内存链
voidprint（MEMORY*）;//打印内存链
voidmain（）
{//主函数
inti=0;
while
（1）
{//选择算法
cout<<（"华南理工大学“计算机操作系统”课程设计大作业\n"）;
cout<<（"题目：
动态内存分区分配方式模拟\n"）;
cout<<（"学生姓名：
冯桥新\n学生学号：
200804692013001\n"）;
cout<<（"\n请输入一个数字（1,2,0）"）;;
cout<<（"\n1--首次适应算法"）;
cout<<"\n2--最佳适应算法"<cout<<"0--中止程序"<cin>>i;
if（i==1）
{//首次适应算法
cout<<（"\n以下为首次适应算法:
\n"）;
is_optimist=false;
init（）;exec（）;
}
if（i==2）
{//最佳适应算法
cout<<"\n以下为最佳适应算法:
\n";
is_optimist=true;
init（）;exec（）;
}
elseif（i==0）
{exit
（1）;}
}
}
voidinit（）
{//初始化内存容量
mem=newMEMORY;
mem->size=640;
mem->former=0;
mem->next=0;
}
voidexec（）
{//执行算法
while
（1）
{//选择申请或释放内存操作
cout<<"**************************"<cout<<"申请内存请输入作业号（1-7）"<cout<<"释放内存请输入数字8"<cout<<"中止程序请输入数字0"<cout<<"**************************"<intk;cin>>k;
//根据k值选择相应的操作
if（k>=1&&k<=7）F_F（k）;
if（k==8）
{intm;
cout<<"请输入要释放的作业号：
";
cin>>m;//选择相应的回收算法
if（is_optimist==false）free（mem,m）;
elsefree_optimist（mem,m）;
}
elseif（k==0）
{break;}//回滚到选择算法的步骤
}
}
voidF_F（inti）
{//依次初始化每个作业,并根据相应算法对作业分配内存
intwork[]={0,130,60,100,200,140,60,50};//作业序列，i从1开始（与作业号对应），因此从第一个开始存放作业值，第0个值为0，不是作业
MEMORY*running;
running=（MEMORY*）malloc（sizeof（MEMORY））;
if（running!
=NULL）
{running->former=NULL;
running->address=0;
running->num=i;//i从1开始循环
running->size=work[i];//指定作业大小
running->state=0;//作业未分配
running->next=NULL;
//根据相应算法为作业分配内存，详见alloc函数
alloc（mem,running）;print（mem）;cout<}
else
cout<<"没有足够的内存空间"<}
voidfree（MEMORY*ptr,inti）
{//首次适应算法作业处理完后释放内存空间
MEMORY*previous,*current;
previous=ptr;current=previous->next;
while（current!
=NULL）
{//循环直到找到需要释放的作业位置
if（current->state==1&¤t->num==i）
{break;}
previous=current;
current=current->next;
}
if（current==NULL）
{cout<<"内存中没有任何作业！
！
！
"<elseif（current->next==NULL）
{//当前作业为内存中最后一个作业
if（previous->state==0）
{//与前一个相邻空闲区合并
previous->size=previous->size+current->size;
previous->next=NULL;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
else
{//将状态改为0，即为空闲区
current->state=0;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
}
elseif（（current->next）->next==NULL）//p6
{//当前作业为倒数第二个作业（此种情况还是要单列出来讨论的否则会出现错误）
if（previous->state==0&&（current->next）->state==0）//p7
{//释放的地址空间前后均为空闲区
previous->size=previous->size+current->size+（current->next）->size;
previous->next=NULL;//与下边else（其他情况的不同之处）
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
elseif（previous->state==0）//p5
{//释放的地址空间前面有空闲块则把它和前面的合并
previous->size=previous->size+current->size;
（current->next）->former=previous;
previous->next=current->next;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
elseif（（current->next）->state==0）//p8
{//释放的地址空间后面有空闲块则把它和后面的空闲块合并
current->size=current->size+（current->next）->size;
current->state=0;
current->next=NULL;//与下边else（其他情况的不同之处）
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
else
{//释放的地址空间前后都没有空闲块时直接把它的状态改为0
current->state=0;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
}
else
{//其他情况下（当前作业在链表中间）
if（previous->state==0&&（current->next）->state==0）//p7
{//所释放空间前后均为空闲区
previous->size=previous->size+current->size+（current->next）->size;
（（current->next）->next）->former=previous;
previous->next=（current->next）->next;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
elseif（previous->state==0）//p5
{//释放的地址空间前面有空闲块则把它和前面的合并
previous->size=previous->size+current->size;
（current->next）->former=previous;
previous->next=current->next;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
elseif（（current->next）->state==0）//p8
{//释放的地址空间后面有空闲块则把它和后面的空闲块合并
current->size=current->size+（current->next）->size;
current->state=0;
（（current->next）->next）->former=current;
current->next=（current->next）->next;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
else
{//处理完的作业前后都没有空闲块时直接把它的状态改为0
current->state=0;
cout<<"作业"<<（current->num）<<"释放"<<（current->size）<<"k的空间"<print（mem）;
}
}
}
voidalloc（MEMORY*ptr,MEMORY*assign）
{//根据算法分配内存（is_optimist状态）
if（ptr->next==NULL）
{//内存没有作业运行
if（ptr->size>=assign->size）
{//内存空间大于作业所需空间，为内存分配空间
ptr->size=ptr->size-assign->size;
assign->state=1;
ptr->next=assign;
assign->former=ptr;
cout<<"作业"<<（assign->num）<<"申请"<<（assign->size）<<""<<"k的内存空间"<}
else
{
cout<<"没有足够的内存空间为作业"<<（assign->num）<<"分配"<deleteassign;
}
}
else
{//内存中如果已经分配了空间
MEMORY*previous,*current;
previous=ptr;//previous为链表中的第一个元素
current=previous->next;
while（current!
=NULL）
{//当前区间不为空（最后一个区间的next为空），即没有循环到最后
//如果当前内存空间大于作业所需空间并且内存没有被分配
//则结束循环，当前current位置即为要插入的位置
if（current->size>=assign->size&¤t->state==0）
{
break;
}
previous=current;//previous后移
current=current->next;
}
if（current==NULL）
{//空闲链中没有为作业分配所需的空间，即释放的空闲区间小于要分配的作业空间
//不够用，则在所有作业后边另外再申请空闲区，如作业4
if（ptr->size>=assign->size）
{//内存中还有足够没分配的空闲空间为此作业分配
//此时ptr指向内存上未分配空闲空间的起始地址
assign->address=640-（ptr->size）;
ptr->size=ptr->size-assign->size;
assign->state=1;
assign->former=previous;
previous->next=assign;
cout<<"作业"<<（assign->num）<<"申请"<<（assign->size）<<""<<"k的内存空间"<}
else
{
cout<<"没有足够的内存空间为作业"<<（assign->num）<<"分配"<}
}
else
{//释放的空闲链中有可为此作业分配的空间
if（（current->size-assign->size）<=size_min）
{//空闲链所具备的空间与作业所需空间大小差不多时
//直接把整个空闲块的空间分配给作业否则从空闲块中
current->num=assign->num;//划出与作业等同的空间
current->state=1;
deleteassign;
cout<<"作业"<<（current->num）<<"申请"<<（current->size）<<""<<"k的内存间"<}
else
{//从空闲块中划分一块与作业大小等同的空间
current->size=current->size-assign->size;
assign->state=1;
assign->address=current->address+current->size;
if（current->next==NULL）
{//此要分配的空间是空闲链的最后一个元素
assign->former=current;
current->next=assign;
}
else
{
assign->next=current->next;
（current->next）->former=assign;
assign->former=current;
current->next=assign;
}
cout<<"作业"<<（assign->num）<<"申请"<<（assign->size）<<""<<"k的内存空间"<}
}
}
//最佳适应算法要对空闲块排序
if（（ptr->next）->next!
=NULL&&is_optimist==true）
sort（ptr）;//排序由空闲块从小到大
}
voidsort（MEMORY*ptr）
{//排序函数
MEMORY*temp=newMEMORY;
temp->next=0;
temp->former=0;
while（ptr->next）
{
if（（ptr->
升级会员 