操作系统原理学习笔记（二十）-连续分配存储管理方式

操作系统原理学习笔记目录

单一连续分配

• 单道程序环境下，存储器分为系统区与用户区。
• 系统区提供给OS，放在内存低址部分。
• 用户区内存仅有一道用户程序。
• 早期单用户单任务OS中，为了节省硬件成本，且出错解决成本低，不配置存储器保护机构。

固定分区分配

• 多道程序系统中，将用户空间分为N个固定空间，每个空间仅可运行一道程序。
• 划分分区方法：
  • 分区大小相等。
  • 分区大小不等。
• 内存分配：
  • 根据分区大小排队，并建立分区使用表。
    • 使用表中包括分区起始地址，大小，状态。
  • 用户程序装入时，根据用户程序大小检索分区使用表，并分配。

动态分区分配

• 动态分区分配中的数据结构
  • 空闲分区表：
    • 记录每个空间分区的情况，包括分区号，分区大小，分区始址等数据项。
  • 空闲分区链：
    • 实现空闲分区的分配与链接，将所有空闲分区链接成一个双向链。
    • 前向链接指针，后向链接指针，状态位，分区大小。
• 动态分区匹配算法
  • 将作业装入内存的算法。
  • 有四种传统分配算法，都属于顺序式搜索算法。
  • 还有三种索引式搜索算法。
  • 七种算法在后续篇幅中介绍
• 分区分配操作
  • 分配内存：
    1. 根据分配算法找到大小合适分区。
    2. 设请求分区大小为u，空闲分区大小为m，不可切割的最小分区为s。
    3. m-u≤s，将整块m分配，否则，切割u，将u中m大小分配给m。
  • 回收内存（四种情况）：
    • 回收区前有空闲分区，合并两个分区即可。
    • 回收区后有空闲分区，以回收区首地址为新地址，合并两个分区。
    • 回收区前后均有空闲分区，以前分区地址作为新地址，合并三个分区。
    • 回收区前后无空闲分区，将回收区插入到空闲链中适当位置。

基于顺序搜索的动态分区分配算法

• 首次适应算法(First Fit, FF)
  • 空闲分区链以地址递增次序链接，分配内存时，从链首顺序查找，直到找到大小合适的分区，若无，则表示分配失败。
  • 优先利用内存中低址空间，为高址保留大空间，可方便大作业分配空间。
  • 但低址部分会不断被划分，产生多个空闲小分区，称为碎片。还增加了不少查找开销。
• 循环首次适应算法(Next Fit, NF)
  • 在FF算法的基础上改进，每次从上次分配地址中查找。
  • 使空闲分区分配均匀，减少查找开销。
  • 但缺乏大的空闲分区。
• 最佳适应算法(Best Fit, BF)
  • 按分区容量从小到大形成空闲分区链。
  • 但每次分割下来的空间都是最小的，产生很多难以利用的空间。
• 最坏适应算法(Worst Fit, WF)
  • 与BF算法相反，从大到小排空闲分区链。
  • 缺乏大的空闲分区。
  • 但切割产生产生的空间是最大的，不容易产生碎片，提高查找效率。
  • 对中，小型作业有利。

基于索引搜索的动态分区分配算法

• 快速适应算法(Quick Fit)/分类搜索法
  • 按空闲分区大小分类。
  • 搜索步骤：
    • 根据进程长度找到可容纳它的最小空闲分区链。
    • 从链表中取出第一块进行分配。
  • 不对任何分区分割，因此能保留大分区，且不产生碎片，查找效率高。
  • 但合并分区时算法复杂，开销大，且分配空间时以进程为单位，会产生浪费。
  • 是一种以空间换时间的做法
• 伙伴系统(Buddy System)
  • 无论是已分配分区还是空闲分区，大小均为2^k。
  • 若系统可利用空间为2^m字，则初始内存区为2^m。经过不断划分，会形成若干个不连续的空闲分区。
  • 步骤：
    1. 若为长度为n的进程分配空间，则查找一个i，使2ⁱ<n<2ⁱ⁺¹。
    2. 在分区大小为2ⁱ的空闲分区链中寻找，找到则分配。
    3. 没找到，则在2ⁱ⁺¹的空闲分区链中寻找，若找到，则均分切割后，分配，并将切割剩余的空闲分区加入2ⁱ表中。若没找到，继续此步骤
  • 一次分配可能需要多长分割，一次回收亦然。
• 哈希算法：
  • 利用哈希快速查找的优点，以及空闲分区在可利用空闲区表中的分布规律，建立哈希函数。
    构建一张以空闲分区大小为关键字的哈希表。
  • 表中每个项目记录一个对应的空闲分区链表表头。
  • 空闲分区分配时，根据所需空闲分区大小， 通过哈希函数计算，得到哈希表位置，从中得到相应空闲分区链表。

动态可重定位分区分配

• 紧凑/拼接-利用碎片的方法
  • 将内存中所有作业移动，使其相邻接，则碎片就能邻接在一起，形成大空间。
  • 但每次“紧凑”后，都需要对程序与数据进行重定位，大大影响系统效率。
    • 重定位是指将地址修改到新的位置。
• 动态重定位
  • 新增一个重定位寄存器，存放程序/数据在内存中的起始地址。
  • 程序运行时，访问的地址是相对地址与寄存器起始地址的和。
  • 进行“紧凑”时，只需要将新起始地址代替原来的起始地址即可。
• 动态重定位分区分配算法
  • 是在动态分区分配算法基础上，使用重定位功能的算法。
  • 即，如果动态分区分配算法没有找到合适空间，则将剩余空闲空间进行“紧凑”，如果“紧凑”出来的空间足够，则分配。