内存分配,首次适应算法

1、实 验 报 告实验名称 ：存分配与回收实验容： 用首次适应算法实现存储空间的分配 , 回收作业所占用的存储空间。三、实验目的：一个好的计算机系统不仅要有足够的存储容量，较高的存取速度和稳定 可靠的存储器， 而且能够合理的分配和使用这些主存空间。 当用户提出申请主存 空间的要求时， 存储管理能够按照一定的策略分析主存的使用情况， 找出足够的 空间分配给申请者； 当作业运行完毕， 存储管理要回收作业占用的主存空间。 本 实验实现在可变分区存储管理方式下， 采用最先适应算法对主存空间进行分配和 回收，以加深了解操作系统的存储管理功能。四、实验过程：a）基本思想空闲分区链以地址递增的次序连接。在分配存

2、时，从链首开始顺序查 找，直至找到一个大小能够满足要求的空闲分区为止；然后再按照作业 大小，从该分区中划出一块存空间分配给请求者，余下的空闲分区仍然 留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区， 则此次存分配失败。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）存分配算法当有进程要求分配主存时， 依据首次适应算法从链头开始， 延

3、链查找一个 足以容纳该进程的空闲区。 若这个分区比较大， 则一分为二，一部分分配给进程， 另一部分作为空闲区仍留在链中的当前位置， 修改它的上一个空闲区的前向指针 值为再加上分配给进程的分区大小， 下一个空闲区的后向指针值为再加上分配给 进程的分区大小， 使链保持完整。 若这个分区的大小正好等于进程的大小， 该分 区全部分配给进程，并将该空闲区从链中摘除（即修改下一个空闲区的后向指针 =该空闲区后向指针，上一个空闲区的前向指针 =该空闲区的前向指针）。再在 已分配区表中找一个空表目，登记刚刚分配的存始址、长度和进程号。d）存的回收当进程运行完成，释放存时，通过输入进程号，来回收进程占用的分区。

4、在 回收时，释放区与空闲区相邻接的情况要考虑 4种情况：。释放区下邻空闲区。释放区上邻空闲区。释放区与上下空闲区均相邻。释放区与上下空闲区均不相邻e）程序流程图空闲链的首次适应算法分配流程图返回分配给进程的内存首地址空闲链的首次适应算法回收流程图开始输入完成进程的标号在分配区表中查找前一个分区的后向指释放区p下邻分区空释放区p上邻分区空前一个空闲区的后向 指针指向p的后一个 分区，p的后一个分区 的前向指针指向p的 前一个分区，且 p的 前一个分区大小更改 为加上p的大小，释 放p针指向p的后一个空 闲分区，p的后一个空 闲分区的前向指针指 向p的前一个分区， 且p的后一个分区大 小更改为加上

5、 p的大 小前一个空闲区的后向指针指向p的后一个空闲分区，p的后一 个空闲分区的前向指针指向 p 的前一个空闲分区，且 p的前 一个空闲分区大小更改为加上释放区p上下均邻空闲区释放区p上下均不邻空闲区p的大小再加上p的后一个空 闲分区的大小，合并后的这个 空闲区的后向指针指向 p的下 下个分区，如果p的下下个分 区不为空，则其前向指针指向 合并后的这个空闲区，释放p和p的下一个分区将p放在链首， 并修改其状态位 为空闲f）截屏M-M苜次适应算法卄*内存分配情侃表卄 区号起始位置区向咯度a256请逋矍为泰迩0蚩於巾存块号小二綸入婁施内存的大小：兰亠.士 士内 分酉己情祈 xxxxxxxtocxx

6、xxxxxtxxxx, 区向咯度10246翱状态it区间状态区号起始位置010请从下列选项中进行选择 一分配内存II:130号程小进大1的的 :存存 择内内 选配配态状用用 间占占闲 区已已|内存分配情苗| 徐要要功 爪入入入成配 青青青Q1030216区号起始位置0104025 2 号: g汪h删存第！进大 1的的 :存存 择内内 选配配态状用用用间占占-41E区已己已宀八工弊因10 配 分 存内列内要要功 下配4入入八成 从分回结配 请1请请请分号区#1040653431 SiSi犀内内态*状用用用用间占占占占闲因已已已已1lr选存： 列內要要功快 下配收克人人人成- 从分回结y迪霧配一一

7、 请；请请请分八区选配配爲弊因10配 分 存 内 八一位 站起分！-矗 状用用用用 间占闲 区已已已已空4 05 .1 ii曹！驻度 情区 强E 豊窪 二血口 二 +:!.I匸 04065顶 谨配配分曲 选存S名，乂 列肉要要小一一 TKiAAAa * 从分回结请2.3.*倩请fe五、源代码#in elude #in elude #in elude using n amespace std;typedef struct FreeLi nk定义空闲链struct FreeL ink *prior;char n ame;int start;int size;bool flag;struct Fre

8、eL ink *n ext;* ptr,*head;head top;ptr p;void prin t()将存分配情况打印到屏幕上p=top;*“ waaH I+/*coutvv区号ttvv 起始位置tvv区间长度tvv区间状态tvvendl;docoutnamettstartttsizeflag=false)/flag为false，表明该分区空闲cout 空闲 endl;elsecout 已占用 next;while(p!=NULL);void clear()/ 结束操作时清空“存”以备其他操作dop=top;top=top-next;free(p);while(top!=NULL);co

9、utprior-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=fa lse)x=3;/ 释放区上邻空闲区if(p-prior-flag=true&p-next-flag=true)|(p-prior=NULL&p-next-flag=tru e)|

10、(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-prio

11、r-next=p-next;elsep-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;elsep-next-prior=p-prior;p-prior-next=p-next; p-next-start=p-start;p-next-size=

12、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-f

13、l-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=

14、n)hebing(p);goto c;p=p-next;while(p!=NULL);endl;cout 存未能分配给该进程，回收失败！ 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

15、+=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; to