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

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

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

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

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

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

6、一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数。+主存分配情况+分区号：1起始地址：0分区大小：130KB状态：已分配分区号：Free起始地址：130分区大小：60KB状态：空闲分区号:3起始地址:190分区大小:100KB状态:已分配分区号:Free起始地址:290分区大小:350KB状态:空闲*1:分配内存2:回收内存*3:查看分配0:退出*请输入您的操作：1请输入作业（分区号）：4请输入需要分配的主存大小（单位:KB）:200分

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

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

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

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

11、大小:140KB状态:已分配分区号:6起始地址:140分区大小:60KB状态:已分配分区号：7起始地址：200分区大小：50KB状态：已分配分区号：Free起始地址：250分区大小：40KB状态：空闲分区号：4起始地址：290分区大小：200KB状态：已分配分区号：Free起始地址：490分区大小：150KB状态：空闲*1:分配内存2:回收内存*3:查看分配0:退出*请输入您的操作：2请输入您要释放的分区号：6*1:分配内存2:回收内存*3:查看分配0:退出*请输入您的操作：3+分区号：起始地址：分区大小：状态：主存分配情况+50140KB已分配+分区号：Free起始地址：140分区大小：60

12、KB状态：空闲分区号：7起始地址：200分区大小：50KB状态：已分配分区号：Free起始地址：250分区大小：40KB状态：空闲分区号：4起始地址：290分区大小：200KB状态：已分配分区号：Free起始地址：490分区大小：150KB状态：空闲*1:分配内存2:回收内存*3:查看分配0:退出*请输入您的操作：0Pressanykeytocontinue【首次适应算法】作业1申请130KB作业2申请60KB作业3申请100KBCcC;DOCUMENTSAND5ETTINOSADMINISTRATORS.ftliiC4；rxriJTHhlX常配谆试_Drbu(A动宸:动态分区分配方式的模拟K

13、XXKKXXIMKXXKKKXKKKXKKKXKKKXKIMXXKKKXK宀1、首次适应算法财最佳适竝算法FKiMKIMXKiMKXKKHiMKKHiMXKXXKXXKXXXKXXXKXXX请选择分配萍法：i*丄=分配內住*3:査有分配2=回收:內存*氐退tuwwsxn.1入入入成1JM1：分配內存:査看片配2：回收山存0=退m範入您的扌眾作=1命入隹业I弁区号.2幕入需妥外配自勺主存大小甲位亡应功！:KB6S存配内耸分査存出内收-20鹤OiMS单笹：1(D:100口具体分配情况如下:CiXDOCUMENTSANDSETTINCSADMINISTRATOR而试雅六MJTl,动喜分区分配算法De

14、bug动岩分.请输入您的揀作：3+“号址尘沁+才地大“+“国始区二芥起龍+十况一十邑+_IL+*f4+KB配=分心起IX始地IX大3：奎;2130己0K幷1区始地区大S：31910己00分1区区夫S：X;Fr2925空ee&0JBpuDRB酉K西M怀KT-孑-e夕一004Z-000请输入您的操作:2.作业2释放60KB的分区号匚2MM+XX1:W*3:1-1-1-1-主存分配情況*=*=一丨口丨対薯驿蛊0=昙收內當HXXXHXXXHXXXHXXXHXXXHXXXHXXXXXXXXXXXXXXXXXXX二土;入您1=分配内存吐回妆内存:査看分配氐退出算料図鬓梵覽鬓買覽買覽覽梵買買賞梵買覽覽梵買疋

15、寰鬓鬓買疋賢買買覽呉買鬓覽費買覽買贺覽；Kjt1K售状13诃KB已分配区戮B闲K030F165SA*蠱1MMKB己分配3.作业4申请200KBe1打1功專井区分配弊袪D亡buql动奁:*2：回收内存氐退m请输入您的操作：+*-+*主存+分配情况,120KB=已分配分聲伏IXK03016父心Z地大区始区BSK西M0勺21910己区饌分翠伏KB即艺地大区始区廿起疔状B司K蘇0095VK4154.作业3释放100KBC-AIMlIMIHAIMI1HIIIIIMKHAInilMIHIHAIIHiIIJS|x讣配fl；AIr*hllO=*Free2ldldKB已分配惠捡也览4*-*1:3；誦悅鶴魁驛偏G

16、專区=3ZiWIfKZEE*1=分配内耘*3=査看分酉己I诘输入您的操作3主行耸配情況2：叵1收内T7毗退由2：叵1收內TTH=退由分E叮止包；:力、B30KBjfe；己分配“,Free130160KB亩闲49015M空l(B闹5.作业1释放130KB邛LixDOCUMENTSAND5ETTING5ADMINI5TRATOR面试鑿六阿JT动喜分区分配算法Debug动臺分.-la|x|*“分配内存姑回收内存*3：香看分配农退由林脣獸驟輟腐区号;1ww2：回收内存*0：fi.tl|林请输入您的操作；3+主存分配情况+；Free；0290KB=空闲区S分起分状4290200KB己分配Is区地大区始区

17、分起分状Free490150KB空闲l-H-HiH-H-H-H-H-H-H-H-H-H-H-H-H-H-H-H-WHiH-H-WH-H-H-WH-H-H-WH-H-HiH-H-H-H-H-H-H-H-Hf6.作业5申请140KB作业6申请60KB作业7申请50KBSC;DOCUMENTSANDSETTINGSADMINISTRATORilftliHAMJTSh分区归Bd耳(SDubucA莒霓尘心“Z地大-E侵芥起分状主存务配情况140KB己分配614&0KB己分配T7址-e襄茯20050KD已分配介起分状Free2540KB空闹蓋務4290200KB已分配分起分状Free490ICQ(D空闹7

18、.作业6释放60KBB己K酉00韦.42920己一号址小态一蠱一分起分状B闲一ee0K一FF2540空-一食一分起分状己B酉0/T.72050己O迅*一蠱一分起分状B一eK一re400一F:空一食一分起分状KB闲0095P.匸41.3【最佳适应算法】1.作业1申请130KB作业2申请60KB作业3申请100KBi：CA”Ur)nlIMFNTSAND5ETTINC5ftDMINI5TRftTOR面试雅育HJT动壽分区井配诗袪Dubu动态分“FFF+配+分+十况+情十存十主+口耳+区地大+区始区+KB配+0分+1013已KB闲ee00r95vr-F2話也弋区妲区分起分状si区地大区始区分起分状3K

19、B配00/-1910已21360已区饌分起分状B配作业2释放60KB作业4申请200KBcaC:DOCUMENTSANDSETTINGSADMINISTRATOR面试崟天MJT动壽分区分配豈圍。曲如动誉乐FFT+区地大+区始区+分起分状0130KB己分配H区地大区始区分起分状Free1306QKB空闲口Ipr-K心区地大区始区分起分状3190100KB己分配小太心E哋大区区妞分樹分状42902QQKB己分配口小态区地大区始区分起分状Free490150KB空闲作业3释放100KBcaClXDOCUMENTSAND5ETTING5ADMINI5TRATOR面试鑿六MJT动誉分区分配宜袪辺皀bug

20、动”况+情+配+分卄存+主+区地大+区始区卄分起分状KB配0八刀13已号址K心区地大区始区分起分状ee0-Inlxl口僅小态区地大区始区分起分状:4；290:200KB：已分配口丐1-心也弋区螂区分起分状Free490150KB空闲*1=分配内存2：回收内存*创4.作业1释放130KB429Q200KB己分配Free0290KB空闲+主存分配情况+请输入您的操作:3冥貝貝貝弹貝貝貝区貝貝貝区咸貝貝区貝貝貝KICK貝貝貝|(貝|(貝ADMINISTRATOR面试鑿六MJTl动态分医分RS-DebiigXbt分请愉入您的揀作4-4-+4-4-+4-4-4-+4-4-4-十半4-4-4-60KB76

21、QSOKE己配3AA地大殆区介聲状Free110介区:4脸殆地1；290好应夭42onKR伏A:己分酉C養*X地大分起龍B2K酉Mm分5MI4巳分区号：Free起始地址；biiB6.作业6释放60KB-JnlCIL;DULUMENTSANDSETTINGSXADMINiSIRAI山牍桌面试整人MJT动态;W区分配算桜D电bu(j动BWK60空+“区地大+尽始区”分起分状己B酉K分00765-匚口！心X地大区始区分起分状KB闲HH00FF111H空口！X地大E始区分起分状KB配00为42920已2=回收内冇已；Frcc:630:10KB=空闲心X地大区始区分起分状区籐分起分状*=分配内冇代码实现

22、】/*/*动态分区分配方式的模拟/*制作者：马江涛*/*学号：8000612091*/*班级：计算机软件121班*/*#include#include#defineFree0/空闲状态#defineBusy1/已用状态#defineOK1/完成#defineERROR0/出错#defineMAX_length640/最大内存空间为640KBtypedefintStatus;typedefstructfreearea/定义一个空闲区说明表结构intID;/分区号longsize;/分区大小longaddress;/分区地址intstate;/状态ElemType;/线性表的双向链表存储结构typ

23、edefstructDuLNode/doublelinkedlistElemTypedata;structDuLNode*prior;/前趋指针structDuLNode*next;/后继指针DuLNode,*DuLinkList;DuLinkListblock_first;/头结点DuLinkListblock_last;/尾结点Statusalloc(int);/内存分配Statusfree(int);/内存回收StatusFirst_fit(int,int);/首次适应算法StatusBest_fit(int,int);/最佳适应算法voidshow();/查看分配StatusInitb

24、lock();/开创空间表StatusInitblock()/开创带头结点的内存空间链表block_first=(DuLinkList)malloc(sizeof(DuLNode);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;bloc

25、k_last-data.ID=0;block_last-data.state=Free;returnOK;/分配主存Statusalloc(intch)intID,request;coutID;coutrequest;if(request0|request=0)cout分配大小不合适，请重试！endl;returnERROR;if(ch=2)/选择最佳适应算法endl;endl;if(Best_fit(ID,request)=OK)cout分配成功！elsecout内存不足，分配失败！endl;returnOK;else/默认首次适应算法if(First_fit(ID,request)=OK)

26、cout分配成功！elsecout内存不足，分配失败！data.ID=ID;temp-data.size=request;temp-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;returnOK;break;if(p-data.state=Free&p-data.sizerequest)/有空闲块能满足需求且有剩余temp-prior=p-prior;temp-next=p

27、;temp-data.address=p-data.address;p-prior-next=temp;p-prior=temp;p-data.address=temp-data.address+temp-data.size;p-data.size-=request;returnOK;break;p=p-next;returnERROR;/最佳适应算法StatusBest_fit(intID,intrequest)intch;/记录最小剩余空间DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode);temp-data.ID=ID;temp-data.

28、size=request;temp-data.state=Busy;DuLNode*p=block_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;r

29、eturnOK;break;if(p-data.state=Free&p-data.sizerequest)/空闲块大于分配需求if(p-data.size-requestdata.size-request;/更新剩余最小值q=p;/更新最佳位置指向p=p-next;if(q=NULL)returnERROR;/没有找到空闲块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;

30、q-data.size=ch;returnOK;/主存回收Statusfree(intID)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=p-prior;if(p-next-data.state=Free)/与后面的空闲块相连p-data.size+=p-next-data.size;p-next-ne