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

1 计算机 学院 计算机科学与技术 专业 班学号 姓名 教师评定 实验题目 主存空间的分配和回收 一 实验目的一 实验目的 熟悉主存的分配与回收 理解在不同的存储管理方式下 如何实现主存空间的分配与 回收 掌握动态分区分配方式中的数据结构和分配算法及动态分区存储管理方式及其实现 过程 二 实验内容和要求二 实验内容和要求 主存的分配和回收的实现是与主存储器的管理方式有关的 所谓分配 就是解决多道 作业或多进程如何共享主存空间的问题 所谓回收 就是当作业运行完成时将作业或进程 所占的主存空间归还给系统 可变分区管理是指在处理作业过程中建立分区 使分区大小正好适合作业的需求 并 且分区个数是可以调整的 当要装入一个作业时 根据作业需要的主存量查看是否有足够 的空闲空间 若有 则按需要量分割一个分区分配给该作业 若无 则作业不能装入 作 业等待 随着作业的装入 完成 主存空间被分成许多大大小小的分区 有的分区被作业 占用 而有的分区是空闲的 实验要求使用可变分区存储管理方式 分区分配中所用的数据结构采用空闲分区表和 空闲分区链来进行 分区分配中所用的算法采用首次适应算法 最佳适应算法 最差适应 算法三种算法来实现主存的分配与回收 同时 要求设计一个实用友好的用户界面 并显 示分配与回收的过程 同时要求设计一个实用友好的用户界面 并显示分配与回收的过程 三 实验主要仪器设备和材料三 实验主要仪器设备和材料 实验环境 硬件环境 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 申请 2 140KB 作业 6 申请 60KB 作业 7 申请 50KB 为它们进行主存分配和回收 1 采用可变分区存储管理 使用空闲分区链实现主存分配和回收 空闲分区链 使用链指针把所有的空闲分区链成一条链 为了实现对空闲分区的分配和链 接 在每个分区的起始部分设置状态位 分区的大小和链接各个分区的前向指针 由状态 位指示该分区是否分配出去了 同时 在分区尾部还设置有一后向指针 用来链接后面的 分区 分区中间部分是用来存放作业的空闲内存空间 当该分区分配出去后 状态位就由 0 置为 1 设置一个内存空闲分区链 内存空间分区通过空闲分区链来管理 在进行内存分配时 系统优先使用空闲低端的空间 设计一个空闲分区说明链 设计一个某时刻主存空间占用情况表 作为主存当前使用 基础 初始化空间区和已分配区说明链的值 设计作业申请队列以及作业完成后释放顺序 实现主存的分配和回收 要求每次分配和回收后显示出空闲内存分区链的情况 把空闲区 说明链的变化情况以及各作业的申请 释放情况显示打印出来 2 采用可变分区存储管理 分别采用首次适应算法 最佳适应算法和最坏适应算法实 现主存分配和回收 3 主存空间分配 1 首次适应算法 在该算法中 把主存中所有空闲区按其起始地址递增的次序排列 在为作业分配 存储空间时 从上次找到的空闲分区的下一个空闲分区开始查找 直到找到第一个能 满足要求的空闲区 从中划出与请求的大小相等的存储空间分配给作业 余下的空闲 区仍留在空闲区链中 2 最佳适应算法 在该算法中 把主存中所有空闲区按其起始地址递增的次序排列 在为作业分配 存储空间时 从上次找到的空闲分区的下一个空闲分区开始查找 直到找到一个能满 足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都小 从中划出与请求的 大小相等的存储空间分配给作业 余下的空闲区仍留在空闲区链中 3 最坏适应算法 在该算法中 把主存中所有空闲区按其起始地址递增的次序排列 在为作业分配 存储空间时 从上次找到的空闲分区的下一个空闲分区开始查找 直到找到一个能满 足要求的空闲区且该空闲区的大小比其他满足要求的空闲区都大 从中划出与请求的 大小相等的存储空间分配给作业 余下的空闲区仍留在空闲区链中 4 主存空间回收 当一个作业执行完成撤离时 作业所占的分区应该归还给系统 归还的分区如果与 其它空闲区相邻 则应合成一个较大的空闲区 登记在空闲区说明链中 此时 相邻空闲 区的合并问题 要求考虑四种情况 1 释放区下邻空闲区 低地址邻接 2 释放区上邻空闲区 高地址邻接 3 释放区上下都与空闲区邻接 4 释放区上下邻都与空闲区不邻接 五 程序流程图五 程序流程图 main 函数里的流程图 3 初始化 first 和 end 整理分区序号 显示空闲分区链 选择算法 a a 1 首次适应算法a 2 最佳适应算法a 3 最坏适应算法 选择操作 i i 1 分配空间函数 ai 0 退出程序i 2 回收空间函 数 结束 分配空间里的流程图 4 p data length request 分配不成功 分配空间函数 a 1a 2a 3 输入申请内存大 小 按顺序找空闲块 初始化 q 使它指向空 闲块中长度小的一块 输入申请内存 大小 初始化 q 使它指向空 闲块中长度大的一块 p data length request p 的状态为已分配 剩下 p data length request 输入申请内存 大小 Y Y N N 返回到整理分区序号 回收空间里的流程图 5 p 的状态 改为空闲 回收 p p 的前一个为 first p 的后一 个是 end p 的后一 个状态空 与后面空闲 块相连 将 p 的 状态改为 空闲 将 p 的状态改 为空闲 回收空间函数 p 的后一 个是 end Y N Y N YN p 的前一 个状态空 p 的前一 个状态空 p 的后一 个状态空 p 的后一 个状态空 p 的后一 个状态空 p 的后一 个状态空 Y Y Y N N N 与前面空 闲块相连 p 的状态 改为空闲 与前面空 闲块相连 与后面空闲 块相连 Y N 返回到整理分区序号 六 相关数据结构及关键函数说明六 相关数据结构及关键函数说明 本程序采用了一个 struct free table 数据结构 里面包含分区序号 num 起始地址 address 分区长度 length 和分区状态 state 还用了线性表的双性链表存储结构 struct Node 里面包含前区指针 prior 和后继指针 next 一开始定义一条 含有 first 和 end 的链 用开始指针和尾指针开创空间链表 然后分别按三种算法进行分配和 6 回收 在该程序中关键函数有 sort allocation recovery 和 First fit Best fit Worst fit 其中 sort 函数是用来整理分区序号的 如在删序号 3 时 她与前面序号 2 相连在一起了 然后序号 2 中的长度总满足申请的内存大小 就会在序号 2 中分配 然后序号在 2 的基础上加 1 一直加 加到与原本序号 3 的下一个序号也就是 4 相等 这时 sort 就开始有明显的工作了 allocation 是分配空间的 也是过渡到三 个算法中的 当三个算法中满足或者不满足分配请求 都会又返回值给 allocation recovery 是用来回收内存的 里面包含了四种情况相连结果 即释放区上与空闲区邻接 释放区下与空闲区邻接 释放区上下都与空闲区邻接 释放区上下都与空闲区不邻接这四 种情况的结果 七 源代码七 源代码 include include define OK 1 完成 define ERROR 0 出错 typedef int Status typedef struct free table 定义一个空闲区说明表结构 int num 分区序号 long address 起始地址 long length 分区大小 int state 分区状态 ElemType typedef struct Node 线性表的双向链表存储结构 ElemType data struct Node prior 前趋指针 struct Node next 后继指针 Node LinkList LinkList first 头结点 LinkList end 尾结点 int flag 记录要删除的分区序号 Status Initblock 开创带头结点的内存空间链表 first LinkList malloc sizeof Node end LinkList malloc sizeof Node first prior NULL first next end 7 end prior first end next NULL end data num 1 end data address 40 end data length 600 end data state 0 return OK void sort 分区序号重新排序 Node p first next q q p next for p NULL p p next for q p next q q q next if p data num q data num q data num 1 显示主存分配情况 void show int flag 0 用来记录分区序号 Node p first p data num 0 p data address 0 p data length 40 p data state 1 sort printf n t t 主存空间分配情况 n printf n n printf 分区序号 t 起始地址 t 分区大小 t 分区状态 n n while p printf d t t d t t d p data num p data address p data length if p data state 0 printf t t 空闲 n n else printf t t 已分配 n n p p next 8 printf n n 首次适应算法 Status First fit int request 为申请作业开辟新空间且初始化 Node p first next LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p if p data state 0 return OK break else if p data state 0 temp next p temp data address p data address temp data num p data num p prior next temp p prior temp p data address temp data address temp data length p data length request p data num 1 return OK break p p next return ERROR 最佳适应算法 Status Best fit int request int ch 记录最小剩余空间 Node p first 9 Node q NULL 记录最佳插入位置 LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p 初始化最小空间和最佳位置 if p data state 0 ch p data length request else if q data length p data length q p ch p data length request p p next if q NULL return ERROR 没有找到空闲块 else if q data length request q data state 1 return OK else temp prior q prior temp next q temp data address q data address temp data num q data num q prior next temp q prior temp q data address request q data length ch q data num 1 return OK return OK 10 最差适应算法 Status Worst fit int request int ch 记录最大剩余空间 Node p first next Node q NULL 记录最佳插入位置 LinkList temp LinkList malloc sizeof Node temp data length request temp data state 1 p data num 1 while p 初始化最大空间和最佳位置 if p data state 0 ch p data length request else if q data length data length q p ch p data length request p p next if q NULL return ERROR 没有找到空闲块 else if q data length request q data length 1 return OK else temp prior q prior temp next q temp data address q data address temp data num q data num q prior next temp q prior temp q data address request q data length ch 11 q data num 1 return OK return OK 分配主存 Status allocation int a int request 申请内存大小 printf 请输入申请分配的主存大小 单位 KB scanf d if requestnext if q p 12 if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 q next q next next q next next prior q q data state 0 q data num flag if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 return OK Status deal2 Node p 处理回收空间 Node q first for q NULL q q next if q p if q prior data state 0 q prior next q next q next prior q prior q p prior q data state 0 q data num flag 1 if q prior data state 0 if q prior data state 0 q prior next q next q next prior q prior q q prior q data state 0 q data num flag 1 if q prior data state 0 return OK 主存回收 Status recovery int flag Node p first for p NULL p p next if p data num flag if p prior first if p next end 当前 P 指向的下一个不是最后一个时 if p next data state 0 与后面的空闲块相连 p data length p next data length 14 p next next prior p p next p next next p data state 0 p data num flag else p data state 0 if p next end 当前 P 指向的下一个是最后一个时 p data state 0 结束 if p prior block first 的情况 else if p prior first if p next end deal1 p else deal2 p 结束 if p prior block first 的情况 结束 if p data num flag 的情况 printf t 回收成功 return OK 主函数 void main int i 操作选择标记 int a 算法选择标记 printf n printf t t 用以下三种方法实现主存空间的分配 n printf t 1 首次适应算法 t 2 最佳适应算法 t 3 最差适应算法 n printf n printf n printf 请输入所使用的内存分配算法 scanf d while a3 printf 输入错误 请重新输入所使用的内存分配算法 n 15 scanf d switch a case 1 printf n t 使用首次适应算法 n break case 2 printf n t 使用最佳适应算法 n break case 3 printf n t 使用最坏适应算法 n break Initblock 开创空间表 while 1 show printf t1 分配内存 t2 回收内存 t0 退出 n printf 请输入您的操作 scanf d if i 1 allocation a 分配内存 else if i 2 内存回收 printf 请输入您要释放的分区号 scanf d recovery flag else if i 0 printf n 退出程序 n break 退出 else 输入操作有误 printf 输入有误 请重试 continue 八 执行结果和结果分析八 执行结果和结果分析 16 初始化首次适应算法 当作业 1 2 3 顺利分配内存空间后 回收序号 2 里面的内存 17 分配作业 4 回收序号 3 里面的内存 与上邻序号 2 相连了 18 回收序号 1 里的内存 与下邻序号 2 相连了 继续分配 会发现总是按顺序查找满足要求的第一个空闲块 一旦发现就