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

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

单一连续分配

  • 单道程序环境下,存储器分为系统区与用户区。
  • 系统区提供给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)
    • 无论是已分配分区还是空闲分区,大小均为2k
    • 若系统可利用空间为2m字,则初始内存区为2m。经过不断划分,会形成若干个不连续的空闲分区。
    • 步骤:
      1. 若为长度为n的进程分配空间,则查找一个i,使2i<n<2i+1
      2. 在分区大小为2i的空闲分区链中寻找,找到则分配。
      3. 没找到,则在2i+1的空闲分区链中寻找,若找到,则均分切割后,分配,并将切割剩余的空闲分区加入2i表中。若没找到,继续此步骤
    • 一次分配可能需要多长分割,一次回收亦然。
  • 哈希算法:
    • 利用哈希快速查找的优点,以及空闲分区在可利用空闲区表中的分布规律,建立哈希函数。
      构建一张以空闲分区大小为关键字的哈希表。
    • 表中每个项目记录一个对应的空闲分区链表表头。
    • 空闲分区分配时,根据所需空闲分区大小, 通过哈希函数计算,得到哈希表位置,从中得到相应空闲分区链表。

动态可重定位分区分配

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

You may also like...

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注