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

南昌大学实验报告学生姓名：马江涛学号：8000612091专业班级：计算机软件121班实验类型：□验证□综合□设计□创新实验日期：2014-05-08实验成绩：【实验要求】1、编程实现首次适应算法和最正确适应算法的动态分区分配的分配过程和回收过程。其中，空闲分区通过分区链来管理；在进行内存分配时，系统优先使用空闲区低端的空间。2、假设初始状态下，可用内存空间为640K，并依次有以下请求序列：作业1申请130KB。作业2申请60KB。作业3申请100KB。作业2释放60KB。作业4申请200KB。作业3释放100KB。作业1释放130KB。作业5申请140KB。作业6申请60KB。作业7申请50KB。作业6释放60KB。请分别用首次适应算法和最正确适应算法进行内存块的分配和回收，要求每次分配和回收后显示出空闲内存分区链的情况【可参考后文的实验提示】。3、上机时认真的进行测试，输入不同的资源分配请求，写出实验结果；4、具体要求：〔1〕对你的程序关键代码处进行注释。〔2〕给出实验数据，对结果进行分析，说明对相关知识点的理解。【实验目的】了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。【实验思路】首次适应算法〔First-fit〕：当要分配内存空间时，就查表，在各空闲区中查找满足大小要求的可用块。只要找到第一个足以满足要球的空闲块就停止查找，并把它分配出去；如果该空闲空间与所需空间大小一样，那么从空闲表中取消该项；如果还有剩余，那么余下的局部仍留在空闲表中，但应修改分区大小和分区始址。最正确适应算法〔Best-fit〕：当要分配内存空间时，就查找空闲表中满足要求的空闲块，并使得剩余块是最小的。然后把它分配出去，假设大小恰好适宜，那么直按分配；假设有剩余块，那么仍保存该余下的空闲分区，并修改分区大小的起始地址。内存回收：将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。并判断该空闲块是否与其他空闲块相连，假设释放的内存空间与空闲块相连时，那么合并为同一个空闲块，同时修改分区大小及起始地址。【实验结果分析】【实验提示】你的动态分区的分配与回收，程序运行结果要可视化。可参考如下运行结果的模式。请分析如下这个结果来自于哪一种动态分配算法？？实现可变分区的分配和回收，主要考虑的问题有三个：第一，设计记录内存使用情况的数据表格，用来记录空闲区和作业占用的区域；第二，在设计的数据表格根底上设计内存分配算法；第三，在设计的数据表格根底上设计内存回收算法。首先，考虑第一个问题，设计记录内存使用情况的数据表格，用来记录空间区和作业占用的区域。由于可变分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随内存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在内存中的起始地址和长度。由于分配时空闲区有时会变成两个分区：空闲区和已分分区，回收内存分区时，可能会合并空闲分区，这样如果整个内存采用一张表格记录己分分区和空闲区，就会使表格操作繁琐。分配内存时查找空闲区进行分配，然后填写己分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，内存的分配和回收主要是对空闲区的操作。这样为了便于对内存空间的分配和回收，就建立两张分区表记录内存使用情况，一张表格记录作业占用分区的“己分分区表〞；一张是记录空闲区的“空闲区表〞。这两张表的实现方法一般有两种：一种是链表形式，一种是顺序表形式。在实验中，采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分分区表〞还是“空闲区表〞都必须事先确定长度。它们的长度必须是系统可能的最大项数。++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：1起始地址：0分区大小：130KB状态：已分配——————————————分区号：Free起始地址：130分区大小：60KB状态：空闲——————————————分区号：3起始地址：190分区大小：100KB状态：已分配——————————————分区号：Free起始地址：290分区大小：350KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：1请输入作业(分区号)：4请输入需要分配的主存大小(单位:KB)：200分配成功！**********************************************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分区大小：130KB状态：已分配——————————————分区号：Free起始地址：130分区大小：160KB状态：空闲——————————————分区号：4起始地址：290分区大小：200KB状态：已分配——————————————分区号：Free起始地址：490分区大小：150KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：2请输入您要释放的分区号：1**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：3++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：Free起始地址：0分区大小：290KB状态：空闲——————————————分区号：4起始地址：290分区大小：200KB状态：已分配——————————————分区号：Free起始地址：490分区大小：150KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：1请输入作业(分区号)：5请输入需要分配的主存大小(单位:KB)：140分配成功！**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：3++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：5起始地址：0分区大小：140KB状态：已分配——————————————分区号：Free起始地址：140分区大小：150KB状态：空闲——————————————分区号：4起始地址：290分区大小：200KB状态：已分配——————————————分区号：Free起始地址：490分区大小：150KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：1请输入作业(分区号)：6请输入需要分配的主存大小(单位:KB)：60分配成功！**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：3++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：5起始地址：0分区大小：140KB状态：已分配——————————————分区号：6起始地址：140分区大小：60KB状态：已分配——————————————分区号：Free起始地址：200分区大小：90KB状态：空闲——————————————分区号：4起始地址：290分区大小：200KB状态：已分配——————————————分区号：Free起始地址：490分区大小：150KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：1请输入作业(分区号)：7请输入需要分配的主存大小(单位:KB)：50分配成功！**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：3++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：5起始地址：0分区大小：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++++++++++++++++++++++++++++++++++++++++++主存分配情况++++++++++++++++++++++++++++++++++++++++++分区号：5起始地址：0分区大小：140KB状态：已分配——————————————分区号：Free起始地址：140分区大小：60KB状态：空闲——————————————分区号：7起始地址：200分区大小：50KB状态：已分配——————————————分区号：Free起始地址：250分区大小：40KB状态：空闲——————————————分区号：4起始地址：290分区大小：200KB状态：已分配——————————————分区号：Free起始地址：490分区大小：150KB状态：空闲——————————————**********************************************1:分配内存2:回收内存****3:查看分配0:退出**********************************************请输入您的操作：0Pressanykeytocontinue【首次适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。具体分配情况如下：2.作业2释放60KB。3.作业4申请200KB。4.作业3释放100KB。5.作业1释放130KB。6.作业5申请140KB。作业6申请60KB。作业7申请50KB。7.作业6释放60KB。【最正确适应算法】1.作业1申请130KB。作业2申请60KB。作业3申请100KB。2.作业2释放60KB。作业4申请200KB。3.作业3释放100KB。4.作业1释放130KB。5.作业5申请140KB。作业6申请60KB。作业7申请50KB。6.作业6释放60KB。【代码实现】//***************************************************************//********动态分区分配方式的模拟*********//********制马江涛*********//********学号：8000612091*********//********班级：计算机软件121班*********//***************************************************************#include<iostream.h>#include<stdlib.h>#defineFree0//空闲状态#defineBusy1//已用状态#defineOK1//完成#defineERROR0//出错#defineMAX_length640//最大内存空间为640KBtypedefintStatus;typedefstructfreearea//定义一个空闲区说明表结构{ intID;//分区号 longsize;//分区大小 longaddress;//分区地址 intstate;//状态}ElemType;//----------线性表的双向链表存储结构------------typedefstructDuLNode//doublelinkedlist{ ElemTypedata; structDuLNode*prior;//前趋指针 structDuLNode*next;//后继指针}DuLNode,*DuLinkList;DuLinkListblock_first;//头结点DuLinkListblock_last;//尾结点Statusalloc(int);//内存分配Statusfree(int);//内存回收StatusFirst_fit(int,int);//首次适应算法StatusBest_fit(int,int);//最正确适应算法voidshow();//查看分配StatusInitblock();//开创空间表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; block_last->data.ID=0; block_last->data.state=Free; returnOK;}//-----------------------分配主存-------------------------Statusalloc(intch){ intID,request; cout<<"请输入作业(分区号)："; cin>>ID; cout<<"请输入需要分配的主存大小(单位:KB)："; cin>>request; if(request<0||request==0) { cout<<"分配大小不适宜，请重试！"<<endl; returnERROR; } if(ch==2)//选择最正确适应算法 { if(Best_fit(ID,request)==OK)cout<<"分配成功！"<<endl; elsecout<<"内存缺乏，分配失败！"<<endl; returnOK; } else//默认首次适应算法 { if(First_fit(ID,request)==OK)cout<<"分配成功！"<<endl; elsecout<<"内存缺乏，分配失败！"<<endl; returnOK; }}//------------------首次适应算法-----------------------StatusFirst_fit(intID,intrequest)//传入作业名及申请量{ //为申请作业开辟新空间且初始化 DuLinkListtemp=(DuLinkList)malloc(sizeof(DuLNode)); temp->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.size>request) {//有空闲块能满足需求且有剩余" temp->prior=p->prior; temp->next=p; 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.size=request; temp->data.state=Busy; DuLNode*p=block_first->next; DuLNode*q=NULL;//记录最正确插入位置 while(p)//初始化最小空间和最正确位置 { if(p->data.state==Free&& (p->data.size>request||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; returnOK; break; } if(p->data.state==Free&&p->data.size>request) {//空闲块大于分配需求 if(p->data.size-request<ch)//剩余空间比初值还小 { ch=p->data.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; 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->next->prior=p; p->next=p->next->next; } break; } p=p->next; } returnOK;}//---------------显示主存分配情况------------------voidshow(){ cout<<"+++++++++++++++++++++++++++++++++++++++\n"; cout<<"+++主存分配情况+++\n"; cout<<"+++++++++++++++++++++++++++++++++++++++\n"; DuLNode*p=block_first->next; while(p) { cout<<"分区号："; if(p->data.ID==Free)cout<<"Free"<<endl; elsecout<<p->data.ID<<endl; cout<<"起始地址："<<p->data.address<<endl; cout<<"分区大小："<<p->data.size<<"KB"<<endl; cout<<"状态："; if(p->da