操作系统试验四报告-主存空间分配和回收含源码

实验题目主存空间的分配和回收 一、实验目的一、实验目的 熟悉主存的分配与回收。 理解在不同的存储管理方式下， 如何实现主存空间的分配与回 收。掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现过 程。 二、实验内容和要求二、实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的。 所谓分配， 就是解决多道作 业或多进程如何共享主存空间的问题。 所谓回收， 就是当作业运行完成时将作业或进程所占 的主存空间归还给系统。 可变分区管理是指在处理作业过程中建立分区， 使分区大小正好适合作业的需求， 并且 分区个数是可以调整的。 当要装入一个作业时， 根据作业需要的主存量查看是否有足够的空 闲空间， 若有， 则按需要量分割一个分区分配给该作业； 若无， 则作业不能装入， 作业等待。 随着作业的装入、完成， 主存空间被分成许多大大小小的分区，有的分区被作业占用， 而有 的分区是空闲的。 实验要求使用可变分区存储管理方式， 分区分配中所用的数据结构采用空闲分区表和空 闲分区链来进行，分区分配中所用的算法采用首次适应算法、 最佳适应算法、最差适应算法 三种算法来实现主存的分配与回收。 同时，要求设计一个实用友好的用户界面， 并显示分配 与回收的过程。同时要求设计一个实用友好的用户界面,并显示分配与回收的过程。 三、实验主要仪器设备和材料三、实验主要仪器设备和材料 实验环境 硬件环境：IBM-PC 或兼容机 软件环境：VC++ 6.0 四、实验原理及设计分析四、实验原理及设计分析 某系统采用可变分区存储管理， 在系统运行当然开始， 假设初始状态下，可用的内存空 间为 640KB，存储器区被分为操作系统分区（40KB）和可给用户的空间区（600KB） 。 （作业 1 申请 130KB、 作业 2 申请 60KB、作业 3 申请 100KB 、 作业 2 释放 60KB 、 作业 4 申请 200KB、 作业 3 释放 100KB、 作业 1 释放 130KB 、 作业 5 申请 140KB 、 作业 6 申请 60KB 、作业 7 申请 50KB） 当作业 1 进入内存后，分给作业1（130KB） ，随着作业1、2、3 的进入，分别分配60KB、 100KB，经过一段时间的运行后，作业2 运行完毕，释放所占内存。此时，作业4 进入系统， 要求分配 200KB 内存。作业 3、1 运行完毕，释放所占内存。此时又有作业5 申请 140KB， 作业 6 申请 60KB，作业 7 申请 50KB。为它们进行主存分配和回收。 1、采用可变分区存储管理，使用空闲分区链实现主存分配和回收。 空闲分区链： 使用链指针把所有的空闲分区链成一条链， 为了实现对空闲分区的分配和链接， 在每个分区的起始部分设置状态位、 分区的大小和链接各个分区的前向指针， 由状态位指示 该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面的分区；分 区中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位就由“0”置为 “1” 。 设置一个内存空闲分区链，内存空间分区通过空闲分区链来管理，在进行内存分配时， 系统优先使用空闲低端的空间。 设计一个空闲分区说明链， 设计一个某时刻主存空间占用情况表， 作为主存当前使用基 1 础。初始化空间区和已分配区说明链的值， 设计作业申请队列以及作业完成后释放顺序， 实 现主存的分配和回收。 要求每次分配和回收后显示出空闲内存分区链的情况。 把空闲区说明 链的变化情况以及各作业的申请、释放情况显示打印出来。 2.采用可变分区存储管理， 分别采用首次适应算法、 最佳适应算法和最坏适应算法实现 主存分配和回收。 3、主存空间分配 （1）首次适应算法 在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配 存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到第一个能 满足要求的空闲区，从中划出与请求的大小相等的存储空间分配给作业，余下的空闲 区仍留在空闲区链中。 （2）最佳适应算法 在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配 存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满 足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小，从中划出与请求的 大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中 （3）最坏适应算法 在该算法中，把主存中所有空闲区按其起始地址递增的次序排列。在为作业分配 存储空间时，从上次找到的空闲分区的下一个空闲分区开始查找，直到找到一个能满 足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大，从中划出与请求的 大小相等的存储空间分配给作业，余下的空闲区仍留在空闲区链中。 4、主存空间回收 当一个作业执行完成撤离时， 作业所占的分区应该归还给系统。 归还的分区如果与其 它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明链中，此时，相邻空闲区的 合并问题，要求考虑四种情况： （1）释放区下邻空闲区（低地址邻接） （2）释放区上邻空闲区（高地址邻接） （3）释放区上下都与空闲区邻接 （4）释放区上下邻都与空闲区不邻接 五、程序流程图五、程序流程图 main 函数里的流程图 2 选择算法 a a=1，首次适应算法a=2，最佳适应算法 初始化 first 和 end 整理分区序号 显示空闲分区链 a=3，最坏适应算法 选择操作 i i=1，分配空间函数 ai=0，退出程序 结束 i=2，回收空间函数 分配空间里的流程图 3 分配空间函数 a=1a=2a=3 输入申请内存大 小 初始化 q，使它指向空 闲块中长度小的一块 初始化 q，使它指向空 闲块中长度大的一块 按顺序找空闲块输入申请内存 大小 输入申请内存 大小 p-data.lengthrequest Y p 的状态为已分配 Y N p-data.length=request 剩下 p-data.length-=request N 分配不成功 返回到整理分区序号 回收空间里的流程图 4 回收空间函数 回收 p， p 的前一个为 first N Y p 的后一 个是 end Y N p 的后一 个状态空 Y p 的后一 个是 end N 将 p 的 状 态 改 为空闲 p 的前一p 的前一 个状态空Y 与后面空闲 块相连 N 将 p 的状态改 为空闲 个状态空 Y N N Y p 的后一 个状态空 p 的后一 个状态空 p 的后一 个状态空 p 的后一 个状态空 Y 与前面空 闲块相连 N p 的状态 改为空闲 p 的状态 改为空闲 与前面空 闲块相连 与后面空闲 块相连 返回到整理分区序号 六、相关数据结构及关键函数说明六、相关数据结构及关键函数说明 本程序采用了一个 struct free_table 数据结构，里面包含分区序号（num） 、起始地址 （address） 、 分区长度 （length） 和分区状态 （state） 。 还用了线性表的双性链表存储结构 （struct Node） ，里面包含前区指针（ prior）和后继指针（ next） 。一开始定义一条（含有first