实验报告_动态分区分配算法

1、:y.大学实验报告学生： 马江涛 学 号：8000612091专业班级:计算机软件121班实验类型：口验证综合设计创新 实验日期：2014-05-08实验成绩: 【实验要求】1、编程实现首次适应算法和最佳适应算法的动态分区分配的分配过程和回 收过程。其中，空闲分区通过分区链来管理；在进行存分配时，系统优先使用空 闲区低端的空间。2、假设初始状态下，可用存空间为640K，并依次有下列请求序列：1）作业1申请130KB。2）作业2申请60KB。3）作业3申请100KB。4）作业2释放60KB。5）作业4申请200KB。6）作业3释放100KB。7）作业1释放130KB。8）作业5申请140KB。9

2、）作业6申请60KB。10）作业7申请50KB。11）作业6释放60KB。请分别用首次适应算法和最佳适应算法进行存块的分配和回收，要求每次分 配和回收后显示出空闲存分区链的情况【可参考后文的实验提示】。3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果；4、具体要求：（1）对你的程序关键代码处进行注释。（2）给出实验数据，对结果进行分析，说明对相关知识点的理解。【实验目的】了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态 分区存储管理方式及其实现过程的理解。【实验思路】首次适应算法（First-fit）：当要分配存空间时，就查表，在各空闲区中查 找满足大小要求的可

3、用块。只要找到第一个足以满足要球的空闲块就停止查找， 并把它分配出去;如果该空闲空间与所需空间大小一样，则从空闲表中取消该项； 如果还有剩余，则余下的部分仍留在空闲表中，但应修改分区大小和分区始址。最佳适应算法 （Best-fit）：当要分配存空间时，就查找空闲表中满足要求 的空闲块，并使得剩余块是最小的。然后把它分配出去，若大小恰好合适，则直 按分配；若有剩余块，则仍保留该余下的空闲分区，并修改分区大小的起始地址。存回收：将释放作业所在存块的状态改为空闲状态，删除其作业名，设置为 空。并判断该空闲块是否与其他空闲块相连，若释放的存空间与空闲块相连时， 则合并为同一个空闲块，同时修改分区大小及

4、起始地址。【实验结果分析】【实验提示】你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果 的模式。请分析如下这个结果来自于哪一种动态分配算法？实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录存使用情况的数据表格，用来记录空闲区和作业占用的区域； 第二，在设计的数据表格基础上设计存分配算法； 第三，在设计的数据表格基础上设计存回收算法。首先，考虑第一个问题，设计记录存使用情况的数据表格，用来记录空间区 和作业占用的区域。由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定 的，且分区的个数也随存分配和回收变动。总之，所有分区情况随时可能发生变 化，数据表

5、格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表 格应该包括分区在存中的起始地址和长度。由于分配时空闲区有时会变成两个分 区：空闲区和己分分区，回收存分区时，可能会合并空闲分区，这样如果整个存 采用一表格记录己分分区和空闲区，就会使表格操作繁琐。分配存时查找空闲区 进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该 分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见， 存的分配和回收主要是对空闲区的操作。这样为了便于对存空间的分配和回收， 就建立两分区表记录存使用情况，一表格记录作业占用分区的“己分分区表”； 一是记录空闲区的“空闲区表”。这

6、两表的实现方法一般有两种：一种是链表形 式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表 的长度必须提前固定，所以无论是“己分分区表”还是“空闲区表”都必须事先 确定长度。它们的长度必须是系统可能的最大项数。+ 主存分配情况 +分区号：1起始地址：0分区大小：130 KB状 态：已分配 分区号：Free 起始地址：130 分区大小：60 KB 状 态：空闲 分区号：3 起始地址：190 分区大小：100 KB 状 态：已分配 分区号：Free 起始地址：290 分区大小：350 KB 状 态：空闲 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个

7、个个个个个个个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“*请输入您的操作：1请输入作业（分区号）：4请输入需要分配的主存大小（单位:KB）： 200分配成功！ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“*请输入您的操作：3+ 主存分配情况 +分区号：1起始地址：0分区大小：130 KB状 态：已分配 分区号：Free 起始地址：130 分区大小：60 KB 状 态：空 闲 分区号：3 起始地址：190 分区大小：100 KB 状 态：已分配 分区号：4 起始地址：290 分区

8、大小：200 KB状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空闲 *个 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1:分配存 2:回收存 1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：2请输入您要释放的分区号：3“*1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：3+ 主存分配

9、情况 +分区号：1起始地址：0分区大小：130 KB状 态：已分配 分区号：Free 起始地址：130 分区大小：160 KB 状 态：空 闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空 闲*3:查看分配 0:退 出 *1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：1请输入作业（分区号）：5请输入需要分配的主存大小（单位:KB）： 140分配成功！*1:分配存 2:回收存 * 3:查

10、看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：3+ 主存 分 配情 况 +分区号：5分区号：6 起始地址：140 分区大小：60 KB 状 态：已分配 分区号：7 起始地址：200 分区号：7 起始地址：200“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：2请输入您要释放的分区号：1*1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：3+

11、主存分配情况 +分区号：Free起始地址：0分区大小：290 KB状 态：空闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空 闲 起始地址：0分区大小：140 KB状 态：已分配 分区号：Free 起始地址：140 分区大小：150 KB 状 态：空闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空 闲 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1:分配存 2

12、:回收存 *3:查看分配 0:退 出 *“*请输入您的操作：1请输入作业（分区号）：6请输入需要分配的主存大小（单位:KB）： 60分配成功！*1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：3+ 主存分配情况 +分区号：5起始地址：0分区大小：140 KB状 态：已分配分区号：Free 起始地址：200 分区大小：90 KB 状 态：空闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空

13、闲 *个*个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：1请输入作业（分区号）：7请输入需要分配的主存大小（单位:KB）： 50分配成功！ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“*请输入您的操作：3+ 主存分配情况 +分区号：5起始地址：0分区大小：140 KB状 态：已分配 分区号：6 起始地址：140 分区大小：60 KB 状 态：已分配分区大小：50 KB状 态：

14、已分配 分区号：Free 起始地址：250 分区大小：40 KB 状 态：空闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空 闲 *个*个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：2请输入您要释放的分区号：6“ 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个*1:分配存 2:回收存 *3:查看分配 0:退 出 *“*请输入您的操作：3+

15、主存分配情况 +分区号：5起始地址：0分区大小：140 KB状 态：已分配 分区号：Free 起始地址：140 分区大小：60 KB 状 态：空 闲 分区大小：50 KB状 态：已分配 分区号：Free 起始地址：250 分区大小：40 KB 状 态：空闲 分区号：4 起始地址：290 分区大小：200 KB 状 态：已分配 分区号：Free 起始地址：490 分区大小：150 KB 状 态：空 闲口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口口 *个*个*1:分配存 2:回收存 *3:查看分配0:退 出 *口口口口口口口口口口口口口口口口口口口口口口口

16、口口口口口口口口口口口口口口口口口口口口口 个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个请输入您的操作：0Press any key to continue【首次适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。. BT:DOOJMENTi： AND SETTrNG5ADMINI5TRATOfiLiBaanHAMJT =1人需夏芬配的主存大小 13S2；巨枚内存： :B. 中入您的操作=1 孺斐猫器咨冬小单位= KB1：分配声T73=查看分酉己去：回枚内If?0： R IIIS;:制到:或泌要蠢的仁狂大小燮 己成耘I:ic

17、it：1WM；竺闱清输入您的操作:分配内存 有看分配具体分配情况如下:项八A 三区缨 二III分相分状号J1八恐I4r2心-口皂父心 Z地大X地大X地大 3始满一国始区 一7妨区 弁喙状分*状2介IU主任分配情况已分配己分配己分配2.作业2释放60KB。-Jnl 吊|1：已；催己竺I和g L:UULU1ti I b nnu hkl ILHLS5UM1PUSI H/kTD心皂面L试会六MJT*动赢分区分配SVebugL动态分.区戮0人您爰葺J.1X心 r地天 r荷区 *分状号廿安心 羸5 分起分状口立?心 A州 K 君区 分5分状声T7分酥319H106 HB己分配3.作业4申请200KB。1-

18、：. T ： i.pnCIJMBNTS AMD SET imGSlEIMirNITRTEIRA,卓画 试技六MJT%动舂分区分配甘秘|、口帖1311口动醒分*查看/古配f*：甚 出 *村*t利*t 利*皱*喋*t 时*t 陇*时村村 * M 女 * 利请顼入您的操作.I露父盲眷新牌荐上小博粒我职200分配成功I*tt 村忧 *t*t *t*t *t*t M*村*t 扯*喋*t*t 喋*tKXK 村 *t*t * JtH*1： J?配内存2；回收内存*心 *查看分配A： -R 出 XX XX XX XX XX XX H XHX * XXX * X JCX * X*CX X XKXK XX XX

19、XX XX XX H 请输入您的操作=3 + 1- + T + + + + + -t + -t+ + + + + + + + + T -HI- + 1- + 1- + 1- + 1-+ + +主存分配情况+ + + + + + + + + + + + + + + 1- -m- + 1- + 1- +I- + 1-+ + + ! 1 :0 :136 KD :已令配写N八.恐 :y始区 III分起分状号p2n 14-11八态 4r 八-号J1八.态 X地大一* 区一区地大 2艮一区始区Z始EZ傍 分杞分状一八S分状一分超分状一分起分状:Free:13B:GB 1:空闹s 19B=1Q6=已分配2I

20、0己命配:Frees 4典s 15M NB=m rn4.作业3释放100KB。主存今配节况: 一130 KB己分酉己4900 KB已分3己会区牛Fret 差始堆正& 40 会区天小e 150 KB请输入您的操作=3果郭3曜建勇榆兄号，:*K地大 者区+ + + - + + + i- + i-+-r + -t+ + + + 1- + 1-b-b-t5140 KB 己分配406# KB已分酒己分以斗7起始地山L 209NJI1小舟* 匕始L1号扯尖 z-IHil 分票状7.作业6释放60KB。|n| xC：1DOCUMENTS ftND SETriNCADMINISTRATORl真面业六MJT 匕

21、动;分区导配算Dcbug.+i况-+ +己+ I + +孑+uz + + VE+ .3+B己0 /X4 nl5 0 i E+Z地大+区始也I+分起分状Z地人 区始区 分起分状己KR翎9 4，720业号址尘土XI旃大区始区分普状KB闲02540空BE 淆 0 0/T= 42920已KB闹0 04915空02X弛大 区始区 分起分状-S-* 态区地大区始区分起彖区弛大 区始区 分起分状【最佳适应算法.作业1申请130KB。作业2申请60KB。作业3申请100KB。m C DOCUMENTS AND SETTING5ADMINI5TRATOH面、试会六MJT，动态分区务配算菽1Dehug，惑+日2心

22、+Z弛大+区始区+分起分状E己K牌0 /T3己0 1 ZL I 口| K口_显主 区弛大 区始区分起分状己KB牌0 J7 1360已区弛大 区始区 分起分状1X1弛大 区始区 分起分状:190:100 KE:E分配;Free:290:359 KB:空闲*1：分配内存2：回收内存 *.作业2释放60KB。作业4申请200KB。.作业3释放100KB。-Inlxi+旦品S+区地大+区始区+分起分状KE闲 e8 0 0F 3 6 F .|_|F 1 1 .5分起分状区地大 区始区 分起分就O品 S弛大始区分起分状m C DOCUMENTS AND 5ETTING5ADMINISTRATDR建面试装六

23、田T动态分区分配宜湿Debug国志分.请输入您的操作=3+ + + + +-t+fr+t+主存分配清况a显来区弛大区始区分起分状R-KB闲290空旦显4心区地大区始区分起分状E n_jK 10 0429如己口_品来 区地大 区始区分起分我KE闲eB 0 0F 9 5 FtF 4 1 .5JDlxl42902丽KE 己分配:Free；490:150 KB，空闲痢 1：分配内存2：回收内存 好d4.作业1释放130KB。JOOIJCXJCJtXjtJCICJIJCXXJOOCICJIJCKXJCXitXIOtJCX， 林 1：分配内存2：回收内存* 3：杏看分a： iH. ti*请输入您的操作;.

24、作业5申请140KB。作业6申请60KB。作业7申请50KB。07 !_； DULUMLn I 5 ftND SEI I lNL.iADMIN15 I试登六MJTL动忘分区分配尊:桔.1吊。口动主存分配情况X地大 区始区 分躬茶750 KB己分配KE闭 -Cs B 0FV1118空 一I:来 一 E地大 Ll 分起甚s17始房分票状490第尘心 区始区 分打分状140 KB己分噌己A地大E始区 分超蒸M-631Q空6.作业6释放60KB。MXMM MMXMMMXMXMM MM MKMMMXXMMKM MM M X M*1：分配内存2：回收内存 *m u,DULUMtnibftnD bt 11

25、ihusadniNI5TRAT0R臭面、试会亢MJT动态分区分配算Sbebug动毒-|D| x;地大X地大 区始区 分起分状X1W大 备分状ZM大 区始区 分杞分状Z地大 区始区 分起分状【代码实现】/+ */*动态分区分配方式的模拟*/*制作者：马江涛*/*学号： 8000612091*/*班级：计算机软件121班*/+/ /个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个#include#include#define Free 0 /空闲状态#define Busy 1 /已用状态#define OK 1/完成#

26、define ERROR 0 /出错#define MAX_length 640 /最大存空间为 640KBtypedef int Status;typedef struct freearea/定义一个空闲区说明表结构int ID;/分区号long size;/分区大小long address; /分区地址int state; /状态ElemType;/线性表的双向链表存储结构typedef struct DuLNode /double linked listElemType data;struct DuLNode *prior; /前趋指针struct DuLNode *next; /后继指

27、针DuLNode,*DuLinkList;DuLinkList block_first; /头结点DuLinkList block_last; /尾结点Status alloc(int);/存分配Status free(int); /存回收Status First_fit(int,int);/首 次适应算法Status Best_fit(int,int); /最佳适应算法void show();/查看分配Status Initblock();/开创空间表Status Initblock()/开创带头结点的存空间链表block_first=(DuLinkList)malloc(sizeof(Du

28、LNode);block_last=(DuLinkList)malloc(sizeof(DuLNode);block_first-prior=NULL;block_first-next=block_last;block_last-prior=block_first;block_last-next=NULL;block_last-data.address=0;block_last-data.size=MAX_length;block_last-data.ID=0;block_last-data.state=Free;return OK;/分配主存Status alloc(int ch)int I

29、D,request;coutID;coutrequest;if(request0 |request=0)cout分配大小不合适，请重试！ endl;return ERROR;if(ch=2) /选择最佳适应算法if(Best_fit(ID,request)=OK) cout分配成功！ endl; else cout存不足，分配失败！ endl;return OK;else /默认首次适应算法if(First_fit(ID,request)=OK) cout分配成功！ endl; else cout存不足，分配失败！ data.ID=ID;temp-data.size=request;temp-

30、data.state=Busy;DuLNode *p=block_first-next;while(p)if(p-data.state=Free & p-data.size=request)/有大小恰好合适的空闲块p-data.state=Busy;p-data.ID=ID;return OK;break;if(p-data.state=Free & p-data.sizerequest)/有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p;temp-data.address=p-data.address;p-prior-next=temp;p-prior=

31、temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;return OK;break;p=p-next;return ERROR;/ 最佳适应算法 Status Best_fit(int ID,int request)int ch; /记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode); temp-data.ID=ID;temp-data.size=request;temp-data.state=Busy;DuLNode *p=bloc

32、k_first-next;DuLNode *q=NULL; /记录最佳插入位置 while(p) /初始化最小空间和最佳位置 if(p-data.state=Free &(p-data.sizerequest | p-data.size=request) q=p;ch=p-data.size-request;break;p=p-next;while(p)if(p-data.state=Free & p-data.size=request)/空闲块大小恰好合适 p-data.ID=ID; p-data.state=Busy; return OK; break;if(p-data.state=Fr

33、ee & p-data.sizerequest) /空闲块大于分配需求if(p-data.size-requestdata.size-request;/更 新剩余最小值 q=p;/更新最佳位置指向p=p-next;if(q=NULL) return ERROR;/没 有找到空闲块 else/找到了最佳位置并实现分配 temp-prior=q-prior; temp-next=q;temp-data.address=q-data.address;q-prior-next=temp;q-prior=temp;q-data.address+=request;q-data.size=ch;return OK;/ 主存回收 Status free(int ID)DuLNode *p=block_first;while(p)if(p-data.ID=ID)p-data.state=Free;p-data.ID=Free;if(p-prior-data.state=Free)/与 前面的空闲块相连 p-prior-data.size+=p-data.size;p-prior-next=p-next;p-next-prior