计算机操作系统内存管理系统可变分区存储管理方式的内存分配回收

1 课程设计课程设计 2 可变分区存储管理方式的内存分配回收可变分区存储管理方式的内存分配回收 一 课程设计目的一 课程设计目的 深入了解采用可变分区存储管理方式的内存分配回收的实现 二 预备知识二 预备知识 存储管理中可变分区的管理方式 三 小组成员三 小组成员 四 课程设计内容四 课程设计内容 编写程序完成可变分区存储管理方式的内存分配回收 具体包括 确定内存空间分配表 采用最优适应算法完成内存空间的分配和回收 编写主函数对所做工作进行测试 五 设计思路 五 设计思路 整体思路 整体思路 可变分区管理方式将内存除操作系统占用区域外的空间看做一个大的空闲 区 当作业要求装入内存时 根据作业需要内存空间的大小 查询内存中的各个 空闲区 当从内存空间中找到一个大于或等于该作业大小的内存空闲区时 选 择其中一个空闲区 按作业需求量划出一个分区装人该作业 作业执行完后 其所占的内存分区被收回 成为一个空闲区 如果该空闲区的相邻分区也是空 闲区 则需要将相邻空闲区合并成一个空闲区 设计所才用的算法 设计所才用的算法 采用最优适应算法 每次为作业分配内存时 总是把既能满足要求 又是最 小的空闲分区分配给作业 但最优适应算法容易出现找到的一个分区可能只比 作业所需求的长度略大一点的情行 这时 空闲区分割后剩下的空闲区就很小 以致很难再使用 降低了内存的使用率 为解决此问题 设定一个限值 minsize 如果空闲区的大小减去作业需求长度得到的值小于等于 minsize 不再 将空闲区分成己分分区和空闲区两部分 而是将整个空闲区都分配给作业 2 内存分配与回收所使用的结构体 内存分配与回收所使用的结构体 为便于对内存的分配和回收 建立两张表记录内存的使用情况 一张为记录 作业占用分区的 内存分配表 内容包括分区起始地址 长度 作业名 标志 为 0 时作为标志位表示空栏目 一张为记录空闲区的 空闲分区表 内容 包括分区起始地址 长度 标志 0 表空栏目 1 表未分配 两张表都采用顺 序表形式 关于分配留下的内存小碎片问题 关于分配留下的内存小碎片问题 当要装入一个作业时 从 空闲分区表 中查找标志为 1 未分配 且 满足作业所需内存大小的最小空闲区 若空闲区的大小与作业所需大小的差值 小于或等于 minsize 把该分区全部分配给作业 并把该空闲区的标志改为 0 空栏目 同时 在已分配区表中找到一个标志为 0 的栏目登记新装人作 业所占用分区的起始地址 长度和作业名 若空闲区的大小与作业所需大小的 差值大于 minsize 则把空闲区分成两部分 一部分用来装入作业 另外一部分 仍为空闲区 这时只要修改原空闲区的长度 且把新装人的作业登记到已分配 区表中 内存的回收 内存的回收 在可变分区方式下回收内存空间时 先检查是否有与归还区相邻的空闲区 上邻空闲区 下邻空闲区 若有 则将它们合件成一个空闲区 程序实现时 首先将要释放的作业在 内存分配表 中的记录项的标志改为 0 空栏目 然后检查 空闲区表 中标志为 1 未分配 的栏目 查找是否有相邻的空 闲区 若有 将之合并 并修改空闲区的起始地址和长度 六 数据结构六 数据结构 1 已分配表的定义 struct float address 已分分区起始地址 float length 已分分区长度 单位为字节 int flag 已分配区表登记栏标志 0 表示空栏目 实验中 3 只支持一个字符的作业名 used table n 已分配区表 2 空闲分区表的定义 struct float address 空闲区起始地址 float length 空闲区长度 单位为字节 int flag 空闲区表登记栏标志 用 0 表示空栏目 用 1 表示未分配 free table m 空闲区表 3 全局变量 float minsize 5 define n 10 假定系统允许的最大作业数量为 n define m 10 假定系统允许的空闲区表最大为 m 七 核心算法 七 核心算法 最优分配算法实现的动态分区最优分配算法实现的动态分区 int distribute int process name float need length int i k 1 k 用于定位在空闲表中选择的未分配栏 float ads len int count 0 i 0 核心的查找条件 找到最优空闲区核心的查找条件 找到最优空闲区 while i m 1 循环找到最佳的空闲分区循环找到最佳的空闲分区 if free table i flag 1 if count 1 free table i length free table k length k i i i 1 if k 1 if free table k length need length minsize 整个分配 free table k flag 0 ads free table k address len free table k length else 切割空闲区 ads free table k address len need length free table k address need length free table k length need length i 0 循环寻找内存分配表中标志为空栏目的项 while used table i flag 0 i i 1 if i n 1 找到 在已分配区表中登记一个表项 used table i address ads used table i length len used table i flag process name count1 else 已分配区表长度不足 if free table k flag 0 将已做的整个分配撤销 5 free table k flag 1 free table k address ads free table k length len else 将已做的切割分配撤销 free table k address ads free table k length len cout 内存分配区已满 分配失败 n return 0 else cout 无法为该作业找到合适分区 n return 0 return process name 八 程序流程图 八 程序流程图 作业分配流程图 6 7 内存回收流程图 九 程序说明 九 程序说明 本程序采用 Visual C 编写 模拟可变分区存储管理方式的内存分配与回 8 收 假定系统允许的最大作业数量为 n 10 允许的空闲区表最大项数为 m 10 判断是否划分空闲区的最小限值为 minsize 5 初始化用户可占用内存 区的首地址为 1000 大小为 1024B 定义两个结构体及其对象 free table m 和 used table n 实现内存的分配回收及分配表和空闲表的登记 用最优分配算法实 现动态分配时 调用 int distribute int process name float need length 内存分配函 数 设定循环条件查找最佳空闲分区 定义 int k 以记录最佳空闲区的首地址 根据找到的空闲区大小和作业大小判断是整个分配给作业还是切割空闲区后再 分配给作业 并在 内存分配表 和 空闲分区表 中作登记 调用 int recycle int process name 函数实现内存的回收 顺序循环 内存分配表 找到要 回收的作业 将标志位设为 0 定义 float recycle address recycle length 用 recycle address 记下回收作业的首地址 recycle length 记下回收作业长度 查 找空闲表 如果 free table i address free table i length recycle address 说 明有上邻接空闲区 这时上邻接区的起始地址不变 长度 recycle address 如果 recycle address recycle length free table i address 说明有下邻接 这 时下邻接空闲区的起始地址改为回收作业的起始地址 recycle address 长度 recycle length 如果 同时有上下邻接空闲区 则上邻接的起始地址不变 长度 recycle address 下邻接的长度 下邻接标志设为 0 否则 要回收的内存没 有邻接空闲区 在空闲区中找到一个标志为 0 的空栏目登记回收的内存 十 内存分配回收实现截图 十 内存分配回收实现截图 1 后台代码的截图 1 假定系统内存分配表允许的最大作业项为 10 当分配超过 10 时 提示 内存分配区已满 分配失败 9 2 回收作业所占内存时 当输入的作业名不存在 回收失败 提示 该作业 不存在 10 3 当要释放某个作业时 将已分配表中此作业的标志置为 0 并在空闲区 做相应登记 4 分配的作业大小 21B 与找到的最优空闲区大小 25B 差值小于 5B 所以将 整块空闲区直接分配给作业 11 5 分配的作业大小 14B 与找到的最优空闲区大小 20B 差值大于 5B 所以将 整块空闲区分割成两部分 然后修改空闲表 12 6 要回收的内存在空闲表中有上邻 将其合并 7 空闲区有两个长度分别为 20B 和 18B 的未分配烂 现为作业 6 分配 14B 的 内存 用最佳分配算法找到空闲区 13 2 制作界面的实现截图 14 十 源程序 十 源程序 include include 全局变量全局变量 float minsize 5 int count1 0 int count2 0 define m 10 假定系统允许的空闲区表最大为假定系统允许的空闲区表最大为 m define n 10 假定系统允许的最大作业数量为假定系统允许的最大作业数量为 n 已分配表的定义已分配表的定义 struct float address 已分分区起始地址已分分区起始地址 float length 已分分区长度 单位为字节已分分区长度 单位为字节 int flag 已分配区表登记栏标志 已分配区表登记栏标志 0 表示空栏目表示空栏目 used table n 已分配区表对象名已分配区表对象名 空闲区表的定义 空闲区表的定义 15 struct float address 空闲区起始地址空闲区起始地址 float length 空闲区长度 单位为字节空闲区长度 单位为字节 int flag 空闲区表登记栏标志 用空闲区表登记栏标志 用 0 表示空栏目 用表示空栏目 用 1 表示表示 未分配未分配 free table m 空闲区表对象名空闲区表对象名 函数声明函数声明 void initialize void int distribute int float int recycle int void show 初始化两个表初始化两个表 void initialize void int a for a 0 a n 1 a used table a flag 0 已分配表的表项全部置为空表项已分配表的表项全部置为空表项 free table 0 address 1000 free table 0 length 1024 free table 0 flag 1 空闲区表的表项全部为未分配空闲区表的表项全部为未分配 最优分配算法实现的动态分区最优分配算法实现的动态分区 int distribute int process name float need length int i k 1 k 用于定位在空闲表中选择的未分配栏用于定位在空闲表中选择的未分配栏 float ads len int count 0 i 0 while i m 1 循环找到最佳的空闲分区循环找到最佳的空闲分区 if free table i flag 1 if count 1 free table i length free table k length 16 k i i i 1 if k 1 if free table k length need length minsize 整整 个分配个分配 free table k flag 0 ads free table k address len free table k length else 切割空闲区切割空闲区 ads free table k address len need length free table k address need length free table k length need length i 0 循环寻找内存分配表中标志为空栏目的项循环寻找内存分配表中标志为空栏目的项 while used table i flag 0 i i 1 if i n 1 找到 在已分配区表中登记一个表项找到 在已分配区表中登记一个表项 used table i address ads used table i length len used table i flag process name count1 else 已分配区表长度不足已分配区表长度不足 if free table k flag 0 将已做的整个分配撤销将已做的整个分配撤销 free table k flag 1 free table k address ads free table k length len 17 else 将已做的切割分配撤销将已做的切割分配撤销 free table k address ads free table k length len cout 内存分配区已满 分配失败 内存分配区已满 分配失败 n return 0 else cout 无法为该作业找到合适分区 无法为该作业找到合适分区 n return 0 return process name int recycle int process name int y 0 float recycle address recycle length int i j k j 栏是下邻空闲区 栏是下邻空闲区 k 栏是上栏空闲区栏是上栏空闲区 int x 在内存分配表中找到要回收的作业在内存分配表中找到要回收的作业 while y n 1 if y n 1 找到作业后 将该栏的标志置为找到作业后 将该栏的标志置为 0 recycle address used table y address recycle length used table y length used table y flag 0 count2 else 未能找到作业 回收失败未能找到作业 回收失败 cout m k 1 判断是否有上邻接判断是否有上邻接 if recycle address recycle length free table i addr ess j i 判断是否有下邻接判断是否有下邻接 i i 1 合并空闲区合并空闲区 if k 1 回收区有上邻接回收区有上邻接 if j 1 回收区也有下邻接 和上下领接合并回收区也有下邻接 和上下领接合并 free table k length free table j length recycle leng th free table j flag 0 将第将第 j 栏的标记置为栏的标记置为 0 else 不存在下邻接 和上邻接合并不存在下邻接 和上邻接合并 free table k length recycle length else if j 1 只有下邻接 和下邻接合并只有下邻接 和下邻接合并 free table j length recycle length free table j address recycle address else 上下邻接都没有上下邻接都没有 x 0 while free table x flag 0 x x 1 在空闲区表中查找一个状态为在空闲区表中查找一个状态为 0 的栏目的栏目 if x m 1 找到后 在空闲分区中登记回收的内存找到后 在空闲分区中登记回收的内存 free table x address recycle address 19 free table x length recycle length free table x flag 1 else 空闲表已满 执行回收失败空闲表已满 执行回收失败 used table y flag process name cout 空闲区已满 回收失败 空闲区已满 回收失败 n return 0 return process name void show 程序执行时输出模拟的内存分配回收表程序执行时输出模拟的内存分配回收表 cout n cout 空空 闲闲 区区 n cout n for int i 0 i count2 i cout 地址 地址 free table i address 作业长作业长 度 度 free table i length 状状 态 态 free table i flag endl cout n cout 已已 分分 配配 区区 n cout n for int j 0 j count1 j cout 地址 地址 used table j address 作业长作业长 度 度 used table j length 作业名 作业名 used table j flag endl void main 主函数调用各功能函数对所有工作进行测试主函数调用各功能函数对所有工作进行测试 int choice 用来选择将要进行的操作用来选择将要进行的操作 int job name float need memory bool exitFlag false 20 cout 动态分区分配方式的模拟动态分区分配方式的模拟 n cout n cout 请选择操作类型 请选择操作类型 n initialize 开创空闲区和已分配区两个表开创空闲区和已分配区两个表 while exitFlag cout n cout 1 分配内存分配内存 2 回收内存回收内存 n cout 3 查看分配查看分配 0 退退 出出 n cout n cout choice switch choice case 0 exitFlag true 退出操作退出操作 break case 1 cout job name need memory distribute job name need memory 分配内分配内 存存 break case 2 int ID cout ID recycle ID 回收内存回收内存 break case 3 show break 十一 心得体会 十一 心得体会 21 每一次的实践 都会有很大的收获 决定做这个题目的时候 就针对此题 要解决的几个问题反复思考 重新翻开教科书把相关内容特别是算法原理认真 细致的看了一遍 设想会遇到的问题 在内存动态分配程序设计中 最优适应 算法比首次要难一些 要加上对分配后该分区是否能最好地利用的判断 再一 个问题是回收时候的合并 对地址的修改不是很有把握 着手写程序后 半天 才理清回收的内存和上下邻合并的条件与关系 写此处的代码时 逻