实验报告实验二动态分区分配与回收算法一、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。二、实验原理算法思想：1.分区的个数和大小不是固定不变的，而是可变的，随装入的作业动态划分，且不会产生内部碎片。2.外部碎片：若存储块长度为N,在该系统所釆用的调度算法下较长时间内无法选出一道长度不超过该块的进程，则称该块为外部碎片。3.首次适应算法（FF）:FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。4.最佳适应算法（BF）：每次为作业分配内存时，BF总是把能满足要求、乂是最小的空闲分区分配给作业，避免大材小用。为了加速寻找，该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。分区分配中的内存回收有四种情况：(1)回收区与插入点的前一个空闲分区相邻接。(2)回收区与插入点的后一空闲分区相邻接。(3)回收区同时与插入点的前、后两个空闲分区邻接。(4)回收分区既不与前一个分区邻接，也不与后一个分区邻接。另外，最佳适应算法不需要考虑多个进程，而首次适应算法需要考虑多道程序的大小，所以前两个程序只需要输入一个进程的信息，后者因为考虑多个程序的原因，所以需要输入两个进程的信息。三、实验步骤、数据记录及处理1、算法流程抽象数据类型的定义：空闲分区结构体类型和结构体链表typedefstructfreespace{intnum;//分区号intsize;//分区大小intaddress://分区首地址statusstate;//分区状态，FREE和BUSY}；typedefstructnode{freespacedata;node*head;}*Linklist;主程序的流程以及各程序模块之间的层次(调用)关系：主函数中先调用初始化函数，再调用菜单函数引导用户选择操作和相应的算法，用switch多选择结构來判断调用firstAlloc(),bestAlloc(),display()还是recycle()。程序流程图：2、运行结果分析：首次适应算法：分配结朿后的空闲分区大小和起始地址与结果相同。大小起始地址30K150K20K280K112K400K闲闲?|>空空咗恚用态1理濫B-B12K申BBbKBKB卜0K卜50K知4060知10知*llklV.XE-XE-*兀分刘分殳衬大80区区00区12林曲区1分分3分身芳/2080址毗址枠种50地22地4地**半ILL・・•・一-:--*半吐止止吐止吐*瞪终珊如终tfi终如.-堰50止止so止00枠号配止1终终2终4林业八段EOO也O也**咻flr&A*r••厶口：••厶口••厶口*存主址戦址址戯址⑨衬内料地t地地t地1枠收衬始区始始区始区衬回朴起闲起起闲起闲林要档4宀八工67宀八工2.S你种枠A村号号号号号号号林输姑区区区区区区区林4请5枠分分分分分分分林最佳适应算法：分配结束后的空闲分区大小和起始地址与结果相同。大小起始地址30K400K42K470K90K210K**号号号号号号号林XX闲闲闲曲:±|灼占状B:9B皿豔B■■KB2B:KE.OK小00小灿小O6丸1弋4t氐分知分知总枠大区00区30区12杯如逅分3分4分5帕初分10如100如170如枷-*02也4也4也咄*15也也也出也也帖站峻遍益终屮渥止10止00止70林彭终2终4终4杯八復、(O也ol:O也衬-子5九O丸|>2九水不O1也3也4也水:・・-4口・・^口・・厶口*、E止止丈止女止史**也也走也走也走**刘W山观水林始始区始区始区林曲起起闲起闲起闲和**47空2〔工6空**西安工业大学实验报告voiddisplav()cout«******************主内存分配情况****************H«endl;node*p=fiist->next;while(p)cout«H分区号：”；if(p->data.num==0)cout«”空闲区H«HM«”起始地址:H«p->data.address«《”终止地址：H«p->data.address+p->data.size«Mn«H分区大小：H«p->data.size«MKBM«HH«”状态:空闲”《endl;}elsecout«p->data.nuni;cout«””«■'起始地址：”«p->data.address«HH«”终止地址：H«p->data.address+p->data.size«””"分区人小："«p->data.size«HKBH«HH«”状态，；if(p->data.state==FREE)cout...
