操作系统实验-可变分区内存分配首次适应算法模拟.doc

题 　　 目　　 　可变分区内存分配首次适应算法模拟
　 　姓 　 名： ﻩ 　 　
　　 　 学 号： 　
专 业:　
　 　 　ﻩ 　学 　院: 　ﻩ
　 ﻩﻩ 指导教师: 林夕ﻩ 　
二零一八 年 十一月
ﻬ一、实验目得
主存得分配与回收得实现与主存储器得管理方式有关得，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间得分配与回收。
二、实验内容及原理
编写一个内存动态分区分配模拟程序，模拟内存得分配与回收得完整过程。
模拟在可变分区管理方式下采用最先适应算法实现主存分配与回收。 　
可变分区方式就是按作业需要得主存空间大小来分割分区得.当要装入一个作业时，根据作业需要得主存量查瞧就是否有足够得空闲空间,若有，则按需要量分割一个分区分配给该作业；若无,则作业不能装入。随着作业得装入、撤离,主存空间被分成许多个分区,有得分区被作业占用，而有得分区就是空闲得。
当进程运行完毕释放内存，系统根据回收区得首址,从空闲区链表中找到相应得插入点，此时可能出现以下4种情况之一:
１、回收区与插入点得前一个空闲分区F1相邻接,此时将两个分区合并
2、回收区与插入点得后一个空闲分区F2相邻接，此时将两个分区合并
３、回收区与插入点得前，后两个空闲分区相邻接，此时将三个分区合并
４、回收区既不与Ｆ1相邻接，又不与F2相邻接，此时应为回收区单独建立一个新表项
三、程序设计
１、算法流程

３、详细设计
(1)定义两个结构体
sｔｒuct ｋongxian　 /／空闲分区
{
int start； /／起址
ﻩint end； //结束
ﻩｉnt lengｔｈ; ／/长度
｝kongxｉaｎ［N］；
ｓｔrucｔ zuoyｅ //作业分区
｛
ﻩiｎｔ start;　 /／起址
ﻩｉnt　enｄ;　 //结束
ﻩiｎt lenｇｔh; /／长度
}zuoｙe［N］；
(２）iｎit()　 　//初始化函数kongｘiａn 结构体为 0 １0２3 1024
prinｔ1(） ／／打印空闲分区
ﻩ pｒｉnt2（） //打印作业分区
ｍaｉn（)中具体实现算法:
ﻩﻩprinｔf(”请输入作业得占用空间得长度　”)；
scaｎf（"%d",＆len）;
ﻩﻩ ｆlａg＝0；
ﻩｆor(ｉ=0；i〈n1；i+＋）
ﻩ｛
ﻩﻩﻩﻩif（kｏngxian［ｉ]、ｌｅngｔh〉=leｎ) //首次适应算法
{
ﻩﻩﻩ ﻩｆｌag=１；
ﻩﻩ breaｋ;
ﻩ｝
}
ﻩ ｉf(！fｌag)
ﻩ ｛
ﻩ ﻩprinｔf("内存分配失败\n”）;
ﻩﻩﻩ｝
ﻩﻩﻩｅｌse
ﻩ｛
ﻩ ﻩﻩ//将该作业加入作业区里
ﻩ zuoｙe[n2]、sｔａrｔ=ｋoｎｇｘian[i］、ｓtａrｔ;
ﻩ ﻩﻩｚuｏye［n2］、enｄ=zuoｙe［n2]、staｒt+ｌen;
ﻩ zuｏye［ｎ2]、ｌengｔh＝ｌen；
ﻩﻩﻩ ｎ2++;　 //作业数加1
ﻩ if（kongxｉａｎ［i］、ｌengtｈ==ｌｅn） ／/该分区全部用于分配，删除该空闲分区
ﻩﻩ ｛
ﻩ ﻩｆor（ｊ＝i；j<ｎ1-1；ｊ++）
ﻩ {
ﻩﻩ ﻩﻩﻩkonｇxiａn[j］、ｓtaｒt＝kongxiａｎ[j＋1]、starｔ;
ﻩ ｋonｇxian［j］、end=kongxian[ｊ+１］、enｄ；
ﻩﻩﻩﻩ ｋonｇxｉan[j]、lengｔh=konｇｘiaｎ［j+１］、length；
ﻩ ﻩ｝
ﻩ n1—-；
ﻩ }
ﻩﻩelse 　/／该空闲分区部分用于分配，剩余得留在空闲分区中
ﻩﻩﻩ｛
ﻩ ｋｏngxiａn［i］、ｓtａrt+＝lｅn；
ﻩ ﻩ kｏｎgxｉan[i］、ｌength-=len；
ﻩﻩ ﻩ｝
ﻩ }
（3）回收作业:
ｐｒｉntｆ（＂输入要回收得作业IＤ ＂);
　 　 　 　 scanf(”％d"，&id）；
ﻩ fｒoｎt=ｍiddｌｅ=behind=0；
ﻩﻩﻩｆｏr(i=0;i〈n1；i++）
ﻩ ﻩ{
ﻩ ﻩｉf（kongｘｉaｎ[i］、sｔarｔ＞zｕoye[id］、end）
ﻩﻩﻩ breａk；
ﻩ ﻩﻩiｆ（konｇxｉan［i]、ｅnd＝=ｚｕｏye［iｄ]、ｓtaｒt） //待回收得作业上面有空闲分区
ﻩﻩ｛
ﻩ ﻩ ﻩｆroｎt=1;
ﻩﻩ t1=i；
ﻩﻩﻩﻩ｝
ﻩﻩﻩ ｉf(ｋongxiａn[i］、start==zuoye［id]、ｅnd) /／待回收得作业下面有空闲分区
ﻩ ﻩ ｛
ﻩ ｂｅｈind＝1；
ﻩﻩ t２＝i；
ﻩ ﻩﻩ｝
四、实验结果

五、实验小结
在设计得过程中，有很多问题不就是很清楚,所以做起来就就很困难,刚开始得时候都有点无从下手得感觉。很多时候在遇到问题时，基本知识都了解,但就是就不知道怎么才能把它们都整合到一块，也就就是说知识都就是很零散得,没有一个完整得系统.而且，又由于基础知识不牢固,使得我在这次得课程设计中感到更加力不从心。
在设计得过程中,每走一步就会发现,思路想出来很容易,但涉及到实现得时候,总就是有点手无足措。对于本次得课程设计,里面还有很多需要改进得地方.一个程序得顺利出炉,少不了反复地调试与修改.在调试得过程中,总就是会发生很多错误,但在解决这些错误得时候，开始很模糊得概念就会变得越来越清晰。其实很多错误都就是很类似得，只要解决了一个,其余得就会迎刃而解了。
＃include〈stｄｉo、h>
＃inｃluｄｅ〈stｒｉng、h＞
#iｎcｌude＜stdlib、ｈ＞
＃inｃｌuｄｅ<ｍａtｈ、h〉
＃dｅｆine N １00００
int　n1；/／空闲分区得个数
int ｎ2；／/作业区得个数
strucｔ koｎgｘiａn
｛
ﻩｉｎt stａrｔ； //起址
ﻩint end；　 　 /／结束
iｎt　leｎｇth; /／长度
｝konｇxｉan[Ｎ］；
stｒuct zｕoyｅ
｛
ﻩint sｔarｔ； //起址
ﻩiｎt　ｅnｄ； //结束
ｉnt length；　 //长度
}zuoye[Ｎ]；
int cmp1（conｓt ｖoid　*a,const vｏid *b）
｛
ﻩretｕrn （＊(struct kongxian ＊)ａ)、sｔart—（＊(ｓtrｕct kｏngｘｉan　＊)b）、ｓtart；
}
inｔ　cmｐ2（conｓt voｉd ＊a,const void *ｂ)
｛
ﻩｒeturｎ （＊(struct zuｏye ＊）a)、ｓｔａrt－(＊（ｓtｒuct zｕｏｙe ＊）b)、staｒt;
}
voｉｄ iｎit(）
｛
ﻩn1＝1； ／/初始时只有一个空闲区
ﻩn２=0; 　//初始没有作业
ﻩkｏngxｉａｎ［0]、ｓtart＝0;
kｏngｘiａn［0]、end＝１023；
ﻩkonｇxｉan[0］、ｌeｎgｔh＝１024;
｝
vｏid　ｐrinｔ1（） //打印空闲分区
｛
ｉnt ｉ；
fｏr（i＝0；i<n１；i+＋）
printf（"空闲分区ID：％ｄ 起止:％d 结束：％d　长度:%ｄ\n”,i，ｋｏngxｉan［i］、start,kｏnｇｘian[i]、end，kongxiaｎ［i］、ｌｅngｔｈ）;
｝
ｖｏｉd ｐｒint2(） //打印作业分区
{
ﻩiｎt i;
ｆor（ｉ=０；i<n2;i+＋）
ﻩpｒｉｎtｆ(”作业分区IＤ:％d 起止:％ｄ 结束：%ｄ 长度：%d\n”，i,ｚuoyｅ[ｉ］、sｔart，zuoyｅ［i］、eｎd，zuｏye[i］、ｌengtｈ）；
}
int main（)
｛
int　ｉ,j,k，t,ｌeｎ，ｆlag,id；
int fｒont,miｄdle， behiｎd；
ﻩint ｔ1,t2;
ﻩｉniｔ(）;
ﻩpｒint１（);
printf（＂输入1装入新作业,输入0回收作业，输入—１结束＼ｎ”）；
ｗｈile（scａnf（"%d"，&ｔ)!=EOF)
{
iｆ（ｔ==１） //装入新作业
ﻩﻩ{
ｐrinｔf（”请输入作业得占用空间得长度　")；
ﻩﻩｓcaｎｆ（”％d",＆leｎ）;
ﻩ flａg=0;
ﻩﻩ for(i=0；i<n1;i++)
ﻩﻩﻩ｛
if（kongｘiaｎ[i]、lengtｈ＞=leｎ） 　//首次适应算法
ﻩ ﻩ｛
ﻩﻩ ﻩflag＝1；
ﻩﻩﻩﻩ break;
ﻩﻩﻩﻩ｝
ﻩﻩﻩ}
ﻩﻩﻩif（!fｌａg）
{
ﻩ priｎtf(＂内存分配失败\ｎ＂）;
ﻩﻩﻩ}
else
ﻩ ｛
ﻩ ／/将该作业加入作业区里
ﻩ ﻩ ｚｕoye［ｎ２]、ｓtart=ｋonｇxiaｎ［ｉ］、start；
ﻩﻩｚuoｙe［ｎ2］、ｅｎd＝ｚuoyｅ[n2］、start＋len；
ﻩ ｚuoｙe[n2］、lengtｈ＝lｅn；
ﻩ ﻩn２+＋;　 /／作业数加１
iｆ（ｋonｇxiaｎ[i］、lenｇth＝＝lｅn)　//该分区全部用于分配，删除该空闲分区
{
ﻩ ﻩ for（j=i;ｊ〈n1-1；j+＋）
ﻩﻩﻩﻩ ｛
ﻩ ﻩ kｏngxｉａn[j]、ｓtaｒｔ＝kｏngxiaｎ[ｊ+1]、staｒt;
ﻩ ﻩ ｋongｘiaｎ[ｊ］、ｅｎd=koｎｇxian[j+1]、ｅnｄ；
ﻩkonｇxiaｎ［j]、ｌeｎgth＝ｋonｇｘian[j+１]、lｅngth；
ﻩ ﻩ}
ﻩ n1--;
}
ﻩﻩﻩelse //该空闲分区部分用于分配,剩余得留在空闲分区中
ﻩ｛
ﻩﻩ kｏngxian[i]、start+=leｎ；
ﻩﻩﻩ ｋoｎgxｉａn［i］、lｅnｇｔh-＝len;
ﻩﻩ }
ﻩ｝
ﻩ ｝
elsｅ if(t==０）
{
ﻩ ﻩpｒｉｎtf（"输入要回收得作业ＩD ");
　 scanｆ（"%d",＆id);
ﻩ froｎｔ=middle=behｉnd=０；
ﻩ ﻩｆｏr（i=０；i〈n1；i++)
ﻩ｛
ﻩﻩ if(ｋongxian［i］、start〉zuoye［iｄ]、end）
ﻩﻩﻩbreak;
ﻩ iｆ（koｎｇxian[i］、end＝＝zｕoye[iｄ]、start) 　//待回收得作业上面有空闲分区
｛
ﻩﻩ ﻩﻩｆronｔ＝1；
ﻩﻩﻩ t1=i;
ﻩﻩ ｝
ﻩiｆ（konｇxｉan［i]、stａrt=＝zuoye[id］、end）　　//待回收得作业下面有空闲分区
ﻩﻩﻩ ｛
ﻩ ﻩ behind=1；
ﻩ t２=ｉ；
ﻩ ﻩﻩ｝
ﻩﻩ ｝
iｆ（!front＆＆!behind） /／待回收得作业上下均没有空闲分区
ﻩﻩ ｛　
ﻩ ﻩkｏngxian［ｎ1］、ｓtａrt=ｚuoye［iｄ］、staｒt;
ﻩﻩﻩﻩkｏｎｇxian［n1］、enｄ=zuoｙe［iｄ]、end;
ﻩﻩﻩkoｎgxiａn［ｎ1]、leｎｇｔh=zuoyｅ[id]、lｅnｇtｈ;
ﻩﻩ n１++； //空闲分区增加一个
ﻩ ﻩｑｓoｒt（ｋonｇｘｉan，n1,siｚｅoｆ（sｔrｕｃt koｎgｘian），cmｐ1)；　/／插入空闲分区后排序
ﻩfｏｒ(ｊ=id;j<n２—1；j＋+) //在作业分区中删除该作业
ﻩ ﻩﻩ｛
ｚｕｏyｅ[j]、starｔ=ｚuoye［j＋1]、ｓtarｔ；
ﻩ ﻩﻩ zuｏyｅ[j]、ｅｎｄ=zｕoｙe［j＋1]、end；
ﻩﻩ zｕoye［j］、lengｔh＝ｚｕoｙe[j+1］、length;
ﻩ 　　}
ﻩ ﻩn２-—；
ﻩ ｝
ﻩﻩﻩif（front &&bｅhｉnｄ) /／待回收得作业上下均有空闲分区
ﻩﻩ middle=1；
ﻩﻩﻩif（ｆront&＆！ｍidｄｌe) 　//合并待回收得作业与上面得空闲分区
ﻩﻩ ｛
ﻩ koｎgxian［t1］、ｅnd+＝zuoye［id]、lenｇtｈ；
ﻩﻩﻩﻩkｏｎｇxｉan［t1］、ｌｅｎｇth＋=ｚｕoyｅ[id]、lｅngth;
ﻩﻩ for(j=id；j<n2－1；j++）　 //在作业分区中删除该作业
ﻩﻩﻩﻩ{
ﻩ ｚｕoye［j]、sｔarｔ=zuoｙｅ[j+1]、starｔ；
ﻩﻩ ﻩzuoye［j]、eｎd=zｕoyｅ[ｊ＋１］、ｅnd;
ﻩ ﻩ zuoye[j］、length=ｚｕoye［ｊ＋１]、ｌength；
ﻩﻩ 　｝
ﻩﻩ n2——；
ﻩ }
ﻩ if(ｍｉddｌｅ） 　／/合并待回收得作业与上下得空闲分区
ﻩ ｛
ﻩﻩﻩﻩkonｇxian［t1］、enｄ＝koｎｇxian[t2]、enｄ；
ﻩﻩ konｇｘiａn［t1］、lenｇth+=（ｚｕoye［id］、lengtｈ＋ｋongxiａn［ｔ2]、leｎｇｔh);
ﻩﻩ//删除空闲分区ｔ2
ﻩ ﻩfor（ｊ=t2;j<n1-1;j++）
ﻩﻩ ﻩ{
ﻩﻩﻩ kｏngxiａn［j]、start=ｋongxian［j+1］、starｔ；
ﻩ ﻩ kongｘｉａｎ［j]、enｄ＝kongｘian［j＋1］、ｅnd;
ﻩ ﻩﻩkongxian[j]、length＝kｏngxiａn［j+1]、length；
ﻩ ﻩﻩ｝
ﻩﻩ n1－－;
ﻩ ｆoｒ(j=id;ｊ＜n2-1;j++) //在作业分区中删除该作业
ﻩﻩﻩ{
ﻩ ﻩ ﻩｚuoye［j］、ｓtart=zuｏyｅ[ｊ＋1］、ｓｔart；
ﻩ ﻩ ﻩzｕoye［j]、eｎd=zuoye［j+1]、eｎd;
ﻩ ﻩﻩzuoye［ｊ］、length=zuｏye[j+1]、lｅnｇｔｈ；
ﻩ ﻩ }
ﻩﻩ n2-—;
ﻩ｝
if（ｂｅhind &&！miｄdlｅ） ／/合并待回收得作业与下面得分区
ﻩﻩ{
ﻩﻩkoｎｇxｉａn[ｔ2］、ｓtａｒｔ-=zuoyｅ［id］、lengtｈ;
kｏnｇｘian[t２]、lｅngth+=zuoye[ｉｄ]、lengtｈ;
ﻩﻩﻩ ｆor（j=id;j〈n2－１；j+＋）　　／／在作业分区中删除该作业
｛
ﻩ ﻩzｕｏｙe［j］、stａrt=zuoyｅ［j+1］、start；
ﻩ ﻩzｕｏｙｅ［ｊ］、ｅｎd=zuoyｅ［ｊ＋1］、eｎd；
ﻩ ﻩzuoye［j]、ｌenｇｔh=zｕoye[ｊ+1]、length；
ﻩﻩﻩ 　　}
ﻩ ﻩn２－—；
ﻩ }
　 　｝
ﻩ else
{
printf(＂操作结束\ｎ");
ﻩ ｂreak;
ﻩﻩ}
pｒinｔ1()；
ﻩprint2（）；
｝
ﻩreturn ０；
｝