内存分配,首次适应算法

实 验 报 告 一、 实验名称：内存分配与回收二、 实验内容：用首次适应算法实现存储空间的分配,回收作业所占用的存储空间。三、 实验目的：一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定可靠的存储器，而且能够合理的分配和使用这些主存空间。当用户提出申请主存空间的要求时，存储管理能够按照一定的策略分析主存的使用情况，找出足够的空间分配给申请者；当作业运行完毕，存储管理要回收作业占用的主存空间。本实验实现在可变分区存储管理方式下，采用最先适应算法对主存空间进行分配和回收，以加深了解操作系统的存储管理功能。四、 实验过程：a) 基本思想空闲分区链以地址递增的次序连接。在分配内存时，从链首开始顺序查找，直至找到一个大小能够满足要求的空闲分区为止；然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败。b)主要数据结构typedef struct FreeLink /空闲链 struct FreeLink *prior; char name; int start; int size; bool flag; struct FreeLink *next;* ptr,*head;head top;ptr p;c)内存分配算法 当有进程要求分配主存时，依据首次适应算法从链头开始，延链查找一个足以容纳该进程的空闲区。若这个分区比较大，则一分为二，一部分分配给进程，另一部分作为空闲区仍留在链中的当前位置，修改它的上一个空闲区的前向指针值为再加上分配给进程的分区大小，下一个空闲区的后向指针值为再加上分配给进程的分区大小，使链保持完整。若这个分区的大小正好等于进程的大小，该分区全部分配给进程，并将该空闲区从链中摘除（即修改下一个空闲区的后向指针=该空闲区后向指针，上一个空闲区的前向指针=该空闲区的前向指针）。再在已分配区表中找一个空表目，登记刚刚分配的内存始址、长度和进程号。d)内存的回收当进程运行完成，释放内存时，通过输入进程号，来回收进程占用的分区。在回收时，释放区与空闲区相邻接的情况要考虑4种情况： 释放区下邻空闲区释放区上邻空闲区释放区与上下空闲区均相邻释放区与上下空闲区均不相邻e)程序流程图空闲链的首次适应算法分配流程图开始申请xkb内存由链头找到第一个空闲区分区大小xkb？大于分区大小=分区大小-xkb，修改下一个空闲区的后向指针内容为（后向指针）+xkb;修改上一个空闲区的前向指针为（前向指针）+xkb将该空闲区从链中摘除：修改下一个空闲区的后向地址=该空闲区后向地址，修改上一个空闲区的前向指针为该空闲区的前向指针等于小于延链查找下一个空闲区到链尾了？作业等待返回是否登记已分配表返回分配给进程的内存首地址 空闲链的首次适应算法回收流程图 开始输入完成进程的标号在分配区表中查找释放区p下邻分区空闲区前一个空闲区的后向指针指向p的后一个分区，p的后一个分区的前向指针指向p的前一个分区，且p的前一个分区大小更改为加上p的大小，释放p释放区p上邻分区空前一个分区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个分区，且p的后一个分区大小更改为加上p的大小释放区p上下均邻空闲区前一个空闲区的后向指针指向p的后一个空闲分区，p的后一个空闲分区的前向指针指向p的前一个空闲分区，且p的前一个空闲分区大小更改为加上p的大小再加上p的后一个空闲分区的大小，合并后的这个空闲区的后向指针指向p的下下个分区，如果p的下下个分区不为空，则其前向指针指向合并后的这个空闲区，释放p和p的下一个分区释放区p上下均不邻空闲区将p放在链首，并修改其状态位为空闲f）截屏 五、 源代码#include #include #include using namespace std;typedef struct FreeLink/定义空闲链struct FreeLink *prior;char name;int start;int size;bool flag;struct FreeLink *next;* ptr,*head;head top;ptr p;void print()/将内存分配情况打印到屏幕上p=top;cout*内存分配情况表*endl;cout区号tt起始位置t区间长度t区间状态tendl;docoutnamettstartttsizeflag=false)/flag为false，表明该分区空闲cout空闲endl;elsecout已占用next;while(p!=NULL);void clear()/结束操作时清空“内存”以备其他操作dop=top;top=top-next;free(p);while(top!=NULL);coutprior-flag=false&p-next-flag=false)x=1; /释放区与上下空闲区均相邻if(p-prior-flag=false&p-next-flag=true)|(p-prior-flag=false&p-next=NULL)x=2;/释放区下邻空闲区if(p-prior-flag=true&p-next-flag=false)|(p-prior=NULL&p-next-flag=false)x=3;/释放区上邻空闲区if(p-prior-flag=true&p-next-flag=true)|(p-prior=NULL&p-next-flag=true)|(p-prior-flag=true&p-next=NULL)x=4;/释放区与上下空闲区均不相邻 switch(x)case 1:p-next-prior=p-prior; p-prior-next=p-next; p-prior-size=p-prior-size+p-size+p-next-size; p-prior-next=p-next-next; if(p-next-next!=NULL) p-next-next-prior=p-next-prior; free(p-next);/释放 free(p); break; case 2:if(p-next=NULL)/p为最后一个分区 p-prior-next=p-next; else p-next-prior=p-prior; p-prior-next=p-next; p-prior-size=p-prior-size+p-size; free(p); break;case 3:if(p-prior=NULL)/p为第一个分区 top=p-next; p-next-prior=NULL; p-next-start=p-start; p-next-size=p-next-size+p-size; else p-next-prior=p-prior; p-prior-next=p-next;p-next-start=p-start; p-next-size=p-next-size+p-size; free(p); break;case 4:p-name=*;/将释放区移至链首并标记为未被占用 p-flag=false; break;void allocate(ptr &p)/最先适应法的内存分配函数FreeLink *fl=(FreeLink *)malloc(sizeof(FreeLink);coutfl-name;coutfl-size;fl-flag=true;doif(p-flag=false&p-sizefl-size) fl-start=p-start; p-start=fl-start+fl-size; p-size=p-size-fl-size; fl-next=p; fl-prior=p-prior; p-prior-next=fl; p-prior=fl; goto a;if(p-flag=false&p-size=fl-size) p-flag=fl-flag; p-name=fl-name; free(fl); goto a;p=p-next;while(p!=NULL);cout内存过小，分配失败！endl;goto b;a: cout分配成功！endl;b: ;/啥也不做void huishou(ptr &p)/内存回收函数char n = ;coutn;do if(p-flag=true&p-name=n)hebing(p); goto c; p=p-next;while(p!=NULL);cout内存未能分配给该进程，回收失败！endl;goto d;c: cout内存回收成功！next=top;pcb-prior=top-prior; top-prior=pcb;pcb-start=top-start;coutpcb-name;cout请输入要分配内存的大小：;goto f;e:coutpcb-size;if(pcb-size256)goto e;top-size=top-size-pcb-size;top=pcb;top-flag=true;top-next-start+=top-size;print();while(true)dop=top-next;cout请从下列选项中进行选择：endl;cout1.分配内存endl;cout2.回收内存endl;cout3.结束操作endl;coutchoice;while(choice!=1&choice!=2&choice!=3);switch(choice)case 1:allocate(p);print();break;case 2:huishou(p);print();break;case 3:clear();return 0;break;int main()/主函数 ptr free=(FreeLink *)malloc(sizeof(FreeLink); top=free; top-name=*; top-start=0; top-size=256;top-flag=false; top-prior=NULL; top-next=NULL;co