操作系统实验动态分区分配算法Word格式文档下载.docx
《操作系统实验动态分区分配算法Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《操作系统实验动态分区分配算法Word格式文档下载.docx（14页珍藏版）》请在冰点文库上搜索。
作业１
作业3
空闲区
作业2
为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表,格式如下:
起址
长度
状 态
第一栏
１4Ｋ
１2K
未分 配
第二栏
32Ｋ
96 K
Ｍ
其中,起址——指出一个空闲区的主存起始地址。
长度——指出从起始地址开始的一个连续空闲的长度。
状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。
（2）当有一个新作业要求装入主存时,必须查空闲区说明表，从中找出一个足够大的空闲区。
有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：
一部分分给作业占用；
另一部分又成为一个较小的空闲区。
为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域,以利于大型作业的装入。
为此,在空闲区说明表中,把每个空闲区按其地址顺序登记,即每个后继的空闲区其起始地址总是比前者大。
（3） 采用最先适应算法（顺序分配算法）分配主存空间。
按照作业的需要量,查空闲区说明表,顺序查看登记栏,找到第一个能满足要求的空闲区。
当空闲区大于需要量时，一部分用来装入作业,另一部分仍为空闲区登记在空闲区说明表中。
由于本实验是模拟主存的分配,所以把主存区分配给作业后并不实际启动装入程序装入作业,而用输出“分配情况”来代替。
（４）当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻,则应合成一个较大的空闲区，登记在空闲区说明表中。
（5）请按最先适应算法设计主存分配和回收的程序。
假设初始时主存中没有作业,现按下面序列进行内存的申请与释放：
作业1申请300K,作业2申请１00Ｋ，作业1释放30０Ｋ,作业３申请150K,
作业４申请3０K,作业5申请40Ｋ,作业6申请６0K,作业４释放30Ｋ。
请你为它们进行主存分配和回收,把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。
四、实验报告
1.画出算法流程图。
2.源代码
＃ｄefinｅ_CRＴ_SEＣＵＲE＿NＯ＿WARNINGＳ1
#incluｄe＜ｓtdｉo．ｈ＞
#ｉnclude＜string.h＞
＃ｉnclude<
sｔdｌib．h＞
#incluｄe<
math．ｈ>
＃deｆｉneＮ 10000
iｎｔn1;
／/空闲分区的个数
ｉntn2;
/／作业区的个数
structｋongxian
{
ﻩintsｔarｔ;
／／起址
ﻩinｔend;
//结束
intlength;
//长度
}ｋｏnｇxｉan[Ｎ];
sｔrｕｃtzuｏye
ﻩiｎt stａrt;
//起址
ﻩiｎt eｎd;
/／结束
ﻩintｌengtｈ;
／／长度
}zuoye[N]；
ｉnt ｃmp1（conｓｔvoid*a,ｃｏnsｔvoid ＊b）
ｒetｕrn（*（sｔruｃt ｋonｇｘian*）a）．ｓtaｒｔ-（*（stｒｕctkoｎgxian*）ｂ）．ｓtａrt;
}
intcｍp２（ｃoｎstｖoid＊ａ,ｃonstvｏｉd＊b）
ﻩreturn（＊（ｓtｒuctzuｏｙｅ*）a）.ｓtaｒｔ-（*（sｔrｕctｚｕoye*）b）.staｒt;
ｖoid ｉｎｉt（）
ｎ１= 1;
/／初始时只有一个空闲区
ﻩｎ2=0；
//初始没有作业
koｎgxｉaｎ[0］.ｓtａrｔ=０；
koｎgxian［0].ｅnd =511;
kongxｉan［0].lｅngｔh = 512;
voｉｄprint１（） /／打印空闲分区
inti;
ﻩfor（i = 0;
ｉ<
n１;
i++）
ﻩpriｎｔf（＂空闲分区IＤ：
％d起止:
%d结束：
％ｄ长度：
％d＼ｎ"
i，kongｘiａｎ[i]．ｓtaｒt，kongｘｉan[i］.eｎd, kongxｉａn[i]．ｌengｔh）;
｝
voｉdprint２（）//打印作业分区
ﻩiｎti;
ﻩｆor（i＝0;
i＜n2;
ﻩﻩprinｔf（"
作业分区ＩD：
%d起止：
％d结束:
%ｄ 长度:
%ｄ\n＂，i, zuoye［i]．starｔ,zuoye[i］.enｄ,zｕoｙe[ｉ].ｌｅｎgtｈ）;
intｍａｉn（）
int i, j,t,leｎ, flａg,id;
ｉnｔｆronｔ， ｍiddle,behｉnd；
int t1, ｔ２;
iｎit（）;
priｎｔ1（）;
ﻩpriｎtｆ（"
输入1装入新作业，输入0回收作业，输入-1结束\n"
）；
wｈile（scaｎf（＂％d"
&
t）!
=EOF）
{
ﻩﻩｉf（ｔ== 1）//装入新作业
ﻩ{
ﻩpriｎtf（＂请输入作业的占用空间的长度"
）;
ﻩﻩｓcanf（＂%ｄ＂，＆len）；
ﻩﻩfｌaｇ=0;
ﻩfｏｒ （ｉ=0；
i<
ﻩﻩﻩ{
ﻩﻩﻩif （koｎgxian[i].ｌengｔh>
=len）//首次适应算法
ﻩﻩﻩ{
ﻩﻩflaｇ ＝1;
ﻩﻩbｒeak;
ﻩﻩ}
ﻩ}
if（!
flag）
ﻩﻩ{
ﻩｐrintｆ（"
内存分配失败＼n＂）；
ﻩelｓｅ
ﻩ{
ﻩﻩﻩ／/将该作业加入作业区里
ﻩﻩﻩzuoyｅ[n2］.start=kongxian[i]．start;
ﻩﻩzuoｙe[ｎ2].enｄ =zｕｏyｅ[n２].start+ｌeｎ;
ﻩﻩzuoye[ｎ2］.lengｔh =len;
ﻩｎ2++;
／/作业数加1
ﻩﻩif（kongxｉaｎ[i].lengtｈ==ｌeｎ）//该分区全部用于分配,删除该空闲分区
ﻩﻩﻩ{
ﻩﻩfor（ｊ ＝ i;
j<
n1-1;
j＋+）
ﻩﻩﻩﻩ{
ﻩkonｇxiaｎ[j].ｓtart=ｋongxian[j +１］.staｒt;
ﻩﻩﻩkongｘiａn[j].end= kongxian[j+ 1].end;
ﻩﻩﻩﻩﻩﻩkongxiaｎ[j]．length =koｎｇxian[j+ 1]．lengｔh;
ﻩﻩ}
ﻩﻩｎ1-－；
ﻩ}
ﻩﻩelｓe//该空闲分区部分用于分配，剩余的留在空闲分区中
ﻩﻩﻩﻩ｛
ﻩﻩﻩkongｘiaｎ［i].starｔ +=len;
ﻩﻩﻩkｏnｇxｉan[ｉ］.lengtｈ-＝len;
ﻩ}
ﻩ}
ﻩ}
elseif（t＝＝0）
ﻩｐrintf（"
输入要回收的作业ID "
ﻩｓcａnｆ（"
％d＂,&
id）;
ﻩfｒonｔ=miｄdle=ｂeｈｉｎd =0;
ﻩfｏr（ｉ = ０;
i<
n1;
i++）
ﻩﻩ{
ﻩﻩﻩﻩif（ｋongxian[ｉ].ｓtart>
ｚuoye[iｄ]．end）
ﻩﻩbreak;
ﻩﻩﻩﻩiｆ（kｏｎgｘian[i].enｄ ==zuoye[id].ｓtａrｔ）//待回收的作业上面有空闲分区
ﻩ｛
ﻩﻩﻩﻩfrｏnｔ =１；
ﻩﻩt1=i;
ﻩ}
ﻩif （kｏngxｉan[i].stａrt ==zuoｙe[id].end） //待回收的作业下面有空闲分区
ﻩ{
ﻩﻩbｅhind=1；
ﻩﻩﻩﻩt2= i;
ﻩ}
ﻩﻩ}
ﻩﻩif（!
ｆrｏnt&
＆！
behｉｎd）//待回收的作业上下均没有空闲分区
ﻩ{
ﻩﻩﻩﻩkongxiａn［ｎ1].starｔ =ｚｕoye[id]．stａrt;
ﻩﻩｋonｇｘiaｎ[ｎ1］.ｅnd＝ zuｏyｅ[ｉd].end;
ﻩﻩﻩkｏngｘiａn［ｎ1].ｌｅngｔh=zuｏｙe[ｉｄ].ｌeｎgth;
ﻩﻩﻩn１＋+;
//空闲分区增加一个
ﻩﻩﻩqsoｒt（ｋongxｉan，n1,ｓｉｚeof（strｕcｔ kｏngxian）, ｃｍp1）;
／／插入空闲分区后排序
ﻩｆor（ｊ= id；
ｊ＜n2－1;
j＋+）//在作业分区中删除该作业
ﻩﻩ｛
ﻩﻩﻩｚuoｙe[ｊ].sｔarｔ= zuoye[ｊ ＋ 1].staｒt;
ﻩﻩﻩﻩzｕoｙｅ[ｊ].eｎd= zuoye［j＋1].ｅｎd；
zｕoye[ｊ].lｅngth＝ｚuｏye［j + １].leｎｇth；
ﻩﻩﻩﻩ}
ﻩﻩﻩn2--;
ﻩﻩ｝
ﻩif （frｏnt&
＆behind） //待回收的作业上下均有空闲分区
ﻩmｉdｄlｅ＝1;
ｉf（front&
&
!
middle）/／合并待回收的作业和上面的空闲分区
ﻩ｛
ﻩﻩﻩkongxian[ｔ1].eｎd +=ｚｕoye[id].length;
ﻩﻩkongxｉａn[t１].length＋=ｚuoｙe[id].length；
ﻩﻩfor（j=iｄ;
n2－１;
j++）／/在作业分区中删除该作业
ﻩ｛
ﻩﻩﻩzｕｏye[j].start=zuoyｅ［j+1].starｔ;
zuoye［ｊ].eｎd＝ｚuoye［j +1].end;
ﻩﻩﻩzuｏye[j].leｎgｔh=zｕoye[j ＋ 1].ｌeｎgｔh;
ﻩﻩ}
ﻩﻩﻩn2--;
ﻩﻩ}
ﻩﻩif（middｌｅ） /／合并待回收的作业和上下的空闲分区
ﻩ{
ﻩﻩkoｎgxian[t1]．enｄ = kｏnｇxian［ｔ2]．eｎd;
ﻩﻩkongxiaｎ[t1]．lengtｈ+=（zuoye[id].length＋ｋｏngxiａn[t2］．lengｔｈ）;
ﻩﻩﻩﻩ//删除空闲分区t２
ﻩﻩﻩfor （ｊ=t2;
ｊ<
n１-1;
j++）
｛
ﻩkongxian[ｊ］.staｒt= kongxian［ｊ＋１］.staｒｔ;
ﻩﻩﻩkongxｉan[ｊ].enｄ=kｏnｇｘian[j ＋1].eｎd；
ﻩｋｏngxian[j].length=kongｘian[j＋1］．lｅngth;
n1-－;
ﻩﻩfor（j=ｉd;
ｎ2－ 1；
j++） //在作业分区中删除该作业
ﻩﻩzuoｙｅ[j］.start=ｚｕoye[j+ 1].sｔart;
ﻩﻩﻩﻩzｕoyｅ[j].ｅｎd=zｕｏyｅ[j＋1].eｎd;
ﻩﻩﻩzｕｏｙe[j].ｌｅngｔh＝ zuｏye[j + 1].length；
ﻩﻩﻩn２－－;
ﻩﻩﻩ}
ﻩﻩif（behiｎd&
ｍiｄdle）/／合并待回收的作业和下面的分区
ﻩﻩkoｎgxian[t2].starｔ-=zｕｏｙe[id].leｎgtｈ;
ﻩkonｇｘian[ｔ２]．lｅnｇth+＝zuoye［ｉd].length；
ﻩｆor （j=id；
n2-1;
ｊ++） ／/在作业分区中删除该作业
ﻩﻩﻩ{
ﻩﻩﻩzuoye[j］．staｒt =zｕoye[ｊ+ 1]．sｔart；
ﻩzuoｙe[j].eｎｄ=zuoye[ｊ+1]．enｄ;
ﻩzuoye[j]．lｅnｇth=zuｏｙe[j＋１].ｌenｇth;
｝
ﻩﻩﻩn２--;
ﻩ｝
ﻩ}
ﻩelse
ﻩ｛
ﻩﻩpｒinｔf（"
操作结束＼n＂）；
ﻩbrｅaｋ;
｝
prｉnt１（）;
print2（）;
｝
ﻩreturｎ ０；
3. 程序运行时的初值和运行结果。
初始：
装入实验要求作业一：
装入作业二：
作业１释放30０ｋ：
作业三申请150ｋ
作业4申请3０k:
作业5申请４0ｋ:
作业6申请60ｋ：
作业4释放３0k:
5.如果在要申请一个10０K的作业空间,能否满足？
可以满足!
五、实验小结
通过本次实验,我对操作系统中首次适应的内存分配方法有了深刻的理解,对理论学习有了很好的促进作用，本次的实验难度比实验一难一些，也对考验了我的编程能力，重要的还是要理解算法。
升级会员 