c++动态分区分配算法模拟操作系统课程设计.docx
- 文档编号:8921777
- 上传时间:2023-05-16
- 格式:DOCX
- 页数:18
- 大小:121.40KB
c++动态分区分配算法模拟操作系统课程设计.docx
《c++动态分区分配算法模拟操作系统课程设计.docx》由会员分享,可在线阅读,更多相关《c++动态分区分配算法模拟操作系统课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
c++动态分区分配算法模拟操作系统课程设计
课程设计
课程设计名称:
操作系统课程设计
专业班级:
学生姓名:
学号:
指导教师:
课程设计时间:
6月13日-——6月17日
计算机科学专业课程设计任务书
学生姓名
马飞扬
专业班级
学号
题目
动态分区分配方式的模拟1
课题性质
其它
课题来源
自拟课题
指导教师
同组姓名
主要内容
1)用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。
2)假设初始状态如下,可用的内存空间为640KB,并有下列的请求序列;
作业1申请130KB;作业2申请60KB;作业3申请100KB;作业2释放60KB;作业4申请200KB;作业3释放100KB;作业1释放130KB;作业5申请140KB;作业6申请60KB;作业7申请50KB;作业6释放60KB
请采用首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。
任务要求
了解动态分区分配中使用的数据结构和分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解。
参考文献
任满杰等《操作系统原理实用教程》电子工业出版社2006
汤子瀛《计算机操作系统》(修订版)西安电子科技大学出版社2001
张尧学史美林《计算机操作系统教程》实验指导清华大学出版社2000
罗宇等《操作系统课程设计》机械工业出版社2005
审查意见
指导教师签字:
教研室主任签字:
年月日
说明:
本表由指导教师填写,由教研室主任审核后下达给选题学生,装订在设计(论文)首页
1:
需求分析
(1)用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
其中,空闲分区通过空闲分区链表来管理,在进行内存分配时,系统优先使用空闲区低端的空间。
(2)假设初始状态下,可用的内存空间为640KB,并有下列的请求序列:
作业1申请130KB;作业2申请60KB;作业3申请100KB;作业2释放60KB;作业4申请200KB;作业3释放100KB;作业1释放130KB;作业5申请140KB;作业6申请60KB;作业7申请50KB;作业6释放60KB。
采用首次适应算法进行内存块的分配和回收,同时显示内存块分配和回收后空闲内存分区链的情况。
2:
概要设计
(1)数据结构:
作业队列数据结构,用于存储待处理作业;阻塞作业队列数据结构,用于存储阻塞的作业。
已分配内存块的双向链表,记录当前系统已分配的各个内存块;未分配内存块的双向链表,记录系统中剩余的各个内存块;系统内存分配总情况的结点对象,记录系统中阻塞的作业总数,已分配的内存块数,剩余的内存块数。
(2)主函数:
对作业队列、阻塞队列、已分配内存块链表、未分配内存块链表、系统总内存分配情况结点对象进行初始化,调用分配函数或回收函数,循环处理11个作业步。
(3)分配函数alloc():
首次适应算法检索未分配的内存块链表,若找到合适的内存块,则加以判断,空闲内存块大小减去作业去请求内存块大小小于系统额定的最小碎片值,把空闲块全部分配,否则进行分割分配,最后显示分配的内存信息。
(4)回收函数free():
首次适应算法检索已分配的内存块链表,找到要释放的内存块后,在已分配链表中删除该结点,并把该结点挂到未分配内存块链表的结尾处,然后进行两次调整,把未分配的内存块链表调整为首地址从小到大的排列顺序,并且物理上相邻的空闲内存块要进行合并,以方便下次进行分配。
调度分配函数,循环处理阻塞作业队列,最后显示回收后的内存情况。
(5)调度图如下:
Free()
主函数
Alloc()
3:
运行环境
硬件:
计算机
软件:
windowsXPvc++6.0
4:
开发工具和编程语言
开发工具:
vc++6.0
编程语言:
C语言
5:
详细设计
(1):
数据结构模块
structjob//作业结点
{
intnum;//作业编号
intstate;//0表示释放,1表示申请
intlength;//作业要求处理大小
};
structyifenpei//已分配内存块结点
{
intnum;//占有内存区域的作业编号
intfirstadd;//内存区域的首地址
intlength;//内存区域的大小
structyifenpei*forward;
structyifenpei*next;
};
structweifenpei//未分配内存块结点
{
intfirstadd;//空闲区域的首地址
intlength;//空闲区域的大小
structweifenpei*forward;
structweifenpei*next;
};
structtotal//内存分配状况记录结点
{
inttotalyifen;//已分配的总内存块数
inttotalweifen;//未分配的总内存块数
inttotalzuse;//阻塞的作业个数
};
structjobjobarray[11];//作业处理队列
structyifenpei*headyifen=(structyifenpei*)malloc(len2);//已分配的内存块所构成的双向链表的头指针
structweifenpei*headweifen=(structweifenpei*)malloc(len3);//未分配的内存块所构成的双向链表的头指针
structjobzuse[11];//阻塞作业队列
structtotaltotalnow;
2:
主函数模块
voidmain()
{
jobarray[0].num=1;jobarray[0].state=1;jobarray[0].length=130;/*初始化请求序列,共11个作业步*/
jobarray[1].num=2;jobarray[1].state=1;jobarray[1].length=60;
jobarray[2].num=3;jobarray[2].state=1;jobarray[2].length=100;
jobarray[3].num=2;jobarray[3].state=0;jobarray[3].length=60;
jobarray[4].num=4;jobarray[4].state=1;jobarray[4].length=200;
jobarray[5].num=3;jobarray[5].state=0;jobarray[5].length=100;
jobarray[6].num=1;jobarray[6].state=0;jobarray[6].length=130;
jobarray[7].num=5;jobarray[7].state=1;jobarray[7].length=140;
jobarray[8].num=6;jobarray[8].state=1;jobarray[8].length=60;
jobarray[9].num=7;jobarray[9].state=1;jobarray[9].length=50;
jobarray[10].num=6;jobarray[10].state=0;jobarray[10].length=60;
totalnow.totalyifen=0;totalnow.totalweifen=1;totalnow.totalzuse=0;//初始化系统内存分配状况
structweifenpei*weifen=(structweifenpei*)malloc(len3);
weifen->firstadd=1;weifen->forward=headweifen;weifen->length=640;weifen->next=NULL;
headweifen->forward=NULL;headweifen->next=weifen;//初始化未分配的内存块双向链表
headyifen->next=NULL;headyifen->forward=NULL;//初始化已分配的内存块双向链表
for(intm=0;m<11;m++)//初始化阻塞作业队列
{
zuse[m].num=0;zuse[m].state=0;
zuse[m].length=0;
}
for(inti=0;i<11;i++)//循环处理11个作业步
{
if(jobarray[i].state==1)
{
alloc(jobarray[i],jobarray[i].num);//调用分配函数
}
else
{
free(jobarray[i],jobarray[i].num);//调用释放函数
}
}
printf("全部作业已处理完成!
");
}
3:
分配函数模块
voidalloc(structjobjobnow,inti)
{
intj=1;
structweifenpei*weifennow1=NULL;structweifenpei*weifennow2=NULL;
structyifenpei*yifennow2=NULL;structyifenpei*yifennow1=NULL;
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
while(yifennow2!
=NULL)
{
yifennow1=yifennow2;
yifennow2=yifennow2->next;
}
yifennow2=(structyifenpei*)malloc(len2);
while(weifennow2!
=NULL)//首次适应算法检索合适的内存块
{
if(weifennow2->length>=jobnow.length)
{
if((weifennow2->length-jobnow.length)<=erding)//内存碎片小于额定值全部分配
{
weifennow1->next=weifennow2->next;
yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;
yifennow2->length=weifennow2->length;yifennow2->forward=yifennow1;
yifennow1->next=yifennow2;yifennow2->next=NULL;
totalnow.totalyifen++;totalnow.totalweifen--;
}
else//否则进行分割分配诶
{
yifennow2->num=i;yifennow2->firstadd=weifennow2->firstadd;
yifennow2->length=jobnow.length;yifennow2->next=NULL;
yifennow2->forward=yifennow1;yifennow1->next=yifennow2;
weifennow2->length=weifennow2->length-jobnow.length;
weifennow2->firstadd=weifennow2->firstadd+jobnow.length;
totalnow.totalyifen++;
}
j=0;
break;
}
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
if(j)//未找到合适内存块则把作业放入阻塞队列
{
for(inty=0;y<11;y++)
{
if(zuse[y].num==0)
{
zuse[y].num=jobnow.num;zuse[y].length=jobnow.length;
zuse[y].state=jobnow.state;
totalnow.totalzuse++;
break;
}
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
printf("当前阻塞作业个数为:
%d\n",totalnow.totalzuse);//显示分配后的信息
printf("当前已分配%d个存储块:
\n",totalnow.totalyifen);
while(yifennow2!
=NULL)
{
printf("作业号:
%d首地址:
%d大小:
%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
printf("当前还有%d个空闲存储块:
\n",totalnow.totalweifen);
while(weifennow2!
=NULL)
{
printf("首地址:
%d大小:
%d\n",weifennow2->firstadd,weifennow2->length,"\n");
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
printf("\n");
}
4:
回收函数模块
voidfree(structjobjobnow,inti)
{
intj=1;
structweifenpei*weifennow1=NULL;structweifenpei*weifennow2=NULL;
structyifenpei*yifennow2=NULL;structyifenpei*yifennow1=NULL;
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
while(weifennow2!
=NULL)
{
weifennow1=weifennow2;
weifennow2=weifennow2->next;
}
while(yifennow2!
=NULL)//首次适应算法检索已分配链表
{
if((yifennow2->num==jobnow.num)&&(yifennow2->length==jobnow.length))//找到后直接释放到未分配的内存块的表尾
{
yifennow1->next=yifennow2->next;yifennow2->next->forward=yifennow1;
weifennow2=(structweifenpei*)malloc(len3);
weifennow2->forward=weifennow1;weifennow2->next=NULL;
weifennow1->next=weifennow2;
weifennow2->firstadd=yifennow2->firstadd;
weifennow2->length=yifennow2->length;
totalnow.totalyifen--;totalnow.totalweifen++;
j=0;
break;
}
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
if(j==1)//未找到则作业队列有问题
{
printf("参数错误!
");
}
else//将放到未分配的链表尾部的结点移动到合适的位置
{
structweifenpei*weifennow3=headweifen;structweifenpei*weifennow4=headweifen->next;
while(weifennow4!
=weifennow2)
{
if(weifennow4->next==weifennow2)
{
if((weifennow2->firstadd+weifennow2->length)
{
weifennow4->next=weifennow2->next;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4;weifennow4->forward=weifennow2;
break;
}
if((weifennow2->firstadd+weifennow2->length)==weifennow4->firstadd)
{
weifennow2->length+=weifennow4->length;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
totalnow.totalweifen--;
break;
}
}
else
{
if((weifennow2->firstadd+weifennow2->length)
{
weifennow2->forward->next=NULL;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4;weifennow4->forward=weifennow2;
break;
}
if((weifennow2->firstadd+weifennow2->length)==weifennow4->firstadd)
{
weifennow2->forward->next=NULL;
weifennow2->length+=weifennow4->length;
weifennow3->next=weifennow2;weifennow2->forward=weifennow3;
weifennow2->next=weifennow4->next;weifennow4->next->forward=weifennow2;
totalnow.totalweifen--;
break;
}
}
weifennow3=weifennow4;weifennow4=weifennow4->next;
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
while(weifennow2!
=NULL)//对未分配的内存块的双向链表进行合并紧凑操作,使得物理上相邻的内存块放到一个记录中
{
if((weifennow1!
=headweifen)&&((weifennow1->firstadd+weifennow1->length)==weifennow2->firstadd))
{
weifennow2->length+=weifennow1->length;
weifennow2->firstadd=weifennow1->firstadd;
weifennow2->forward=weifennow1->forward;
weifennow1->forward->next=weifennow2;
totalnow.totalweifen--;
}
weifennow1=weifennow2;
weifennow2=weifennow2->next;
}
if(totalnow.totalzuse!
=0)//释放内存后再循环处理阻塞队列中的阻塞作业,若仍无合适内存块则继续阻塞
{
for(intx=0;x<11;x++)
{
if(zuse[x].num!
=0)
{
totalnow.totalzuse--;
zuse[x].num=0;zuse[x].state=0;
zuse[x].length=0;
alloc(zuse[x],zuse[x].num);
}
if(totalnow.totalzuse==0)
{
break;
}
}
}
weifennow1=headweifen;weifennow2=headweifen->next;
yifennow1=headyifen;yifennow2=headyifen->next;
printf("当前阻塞作业个数为:
%d\n",totalnow.totalzuse);//显示释放内存以及处理完阻塞作业后的内存分配情况
printf("当前已分配%d个存储块:
\n",totalnow.totalyifen);
while(yifennow2!
=NULL)
{
printf("作业号:
%d首地址:
%d大小:
%d\n",yifennow2->num,yifennow2->firstadd,yifennow2->length);
yifennow1=yifennow2;yifennow2=yifennow2->next;
}
printf("当前还有%d个空闲存储块:
\n",totalnow.totalweifen);
while(weifennow2!
=NULL)
{
printf("首地址:
%d大小:
%d\n",weifennow2->firstadd,weifennow2->length);
weifennow1=weifennow2;weifennow2=weifennow2->next;
}
printf("\n");
}
6:
调试分析
(1)设计数据结构时考虑到有两种可供选择,一种是用一个数据结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- c+ 动态 分区 分配 算法 模拟 操作系统 课程设计