王道操作系统笔记，视频链接：3.1.2.1 连续分配管理方式

知识总览

1. 内存管理的概念：
   • 内存空间的分配与回收：
     • 连续分配管理方式：（本节内容）
       • 单一连续分配
       • 固定分区分配
       • 动态分区分配
     • 非连续分配管理方式
   • 内存空间的扩充
   • 地址转换
   • 存储保护
2. 连续分配：指为用户进程分配的必须是一个连续的内存空间。

单一连续分配

1. 在单一连续分配方式中，内存被分为系统区和用户区。
   • 系统区通常位于内存的低地址部分，用于存放操作系统相关数据；
   • 用户区用于存放用户进程相关数据。
2. 该方式的内存中只能有一道用户程序，用户程序独占整个用户区空间。
   • 也就是说，哪怕该程序只用了一小部分，另一大部分都不会给其他程序用
3. 优点：
   • 实现简单
   • 无外部碎片
     • 后续动态分区部分详细说明
   • 可以采用覆盖技术扩充内存
   • 不一定需要采取内存保护
     • 比如：早期的PC操作系统MS-DOS就没采用内存保护
     • 但是也不一定，有些可能添加了内存保护
4. 缺点：
   • 只能用于单用户、单任务的操作系统中
   • 有内部碎片
     • 分配给某进程的内存区域中，如果有些部分没有用上，就是“内部碎片”
   • 存储器利用效率极低
5. 图示：
   

固定分区分配

1. 20世纪60年代出现了支持多道程序的系统，
   • 为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，
   • 于是将整个用户空间划分为若干个固定大小的分区，
   • 在每个分区中只装入一道作业，
   • 这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
2. 两种分配方式：
   • 分区大小相等
   • 分区大小不等
   • 图示：
     
3. 两种方法优缺点：
   • 分区大小相等：
     • 缺乏灵活性，但是很适合用于用一台计算机控制多个相同对象的场合
     • 比如（优点）：
       • 钢铁厂有n个相同的炼钢炉，
       • 就可把内存分为n个大小相等的区域存放n个炼钢炉控制程序
     • 又比如（缺点）：
       • 小的进程占用空间小，可能会浪费分区
       • 大的进程占用空间较大，分区大小不满足不能使用
         • 可以使用覆盖技术，但是会增加系统开销
   • 分区大小不等：
     • 增加了灵活性，可以满足不同大小的进程需求，根据常在系统中运行的作业大小情况进行划分。
     • 比如：
       • 划分多个小分区、适量中等分区、少量大分区
     • 一般来说可以估计系统当中会出现的大小作页有多少，有多少比例对内存进行划分。
4. 操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收。
   • 每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态（是否已分配）。
   • 示例：（包括大小、起始地址、状态）
     
5. 上述的分区说明表可以用数据结构的**数组（或链表）**即可表示这个表。
   • 当某用户程序要装入内存时，
     • 由操作系统内核程序根据用户程序大小检索该表，
     • 从中找到一个能满足大小的、未分配的分区，将之分配给该程序，
     • 然后修改状态为“已分配”。
   • 优点：实现简单，无外部碎片
   • 缺点：
     • 当用户程序太大时，可能所有的分区都不能满足需求，
       • 此时不得不采用覆盖技术来解决，但这又会降低性能；
     • 会产生内部碎片，内存利用率低。
       • 内部碎片：已经分配给某进程，但该进程没有用到的部分
       • 外部碎片：尚未分配的空闲内存，但因分散成多个不连续小块，无法满足新请求

动态分区分配

1. 动态分区分配又称为可变分区分配。
   • 这种分配方式不会预先划分内存分区，
   • 而是在进程装入内存时，根据进程的大小动态地建立分区，
   • 并使分区的大小正好适合进程的需要。
   • 因此系统分区的大小和数目是可变的。
   • 举例：
     • 假设某计算机内存大小为 64MB，系统区 8MB，用户区共 56 MB
     • 此时来了三个进程，分别占用20、14、18MB，总共占用52MB
     • 所以只会剩下4MB的空闲分区
     • 图示：
       
2. 问题：
   • 操作系统要用什么样的数据结构记录内存的使用情况？
   • 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
   • 如何进行分区的分配与回收操作？
3. 操作系统要用什么样的数据结构记录内存的使用情况？
   • 两种常用数据结构：
     • 空闲分区表
       • 每个空闲分区对应一个表项。
       • 表项中包含分区号、分区大小、分区起始地址等信息
       • 表中没有的分区就是已经被分配出去了。
     • 空闲分区链
       • 每个分区的起始部分和末尾部分分别设置前向指针和后向指针。
       • 起始部分处还可记录分区大小等信息
   • 图示：
     
4. 当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配？
   • 把一个新作业装入内存时，须按照一定的动态分区分配算法，
   • 从空闲分区表（或空闲分区链）中选出一个分区分配给该作业。
   • 由于分配算法算法对系统性能有很大的影响，因此人们对它进行了广泛的研究。
   • 下个小节会介绍四种动态分区分配算法，此处不详细展开。
5. 如何进行分区的分配与回收操作？
   • 假设系统采用的数据结构是“空闲分区表”，如何分配？
   • 第一种情况，分区大小比进程需要内存大：
     • 比如1号分区大小为20MB，起始地址为8M，进程为4MB
       • 这里的M和MB都是兆字节的缩写，
       • 至于为什么不用同一个缩写，是因为视频就这样的，
       • 但是它们确实是一样的意思，理论上可以混用
     • 那么将进程放入该分区后，该分区大小变为20-4=16MB，
     • 起始地址变为8+4=12M
   • 第二种情况，分区大小与进程需要内存一样：
     • 比如1号分区大小为4MB，起始地址为60M，进程为4MB
     • 那么将进程放入该分区后，需要把该分区从空闲分区表中删除。
   • 回收情况一，回收区的后面有一个相邻的空闲分区：
     • 比如1号分区大小为10MB，起始地址为32M，进程为4MB（28M到32M）
     • 此时回收了该进程，需要把1号分区大小修改为10+4=14MB，
     • 起始地址修改为32-4=28M
     • 也就是需要将两个空闲分区合二为一
   • 回收情况二，回收区的前面有一个相邻的空闲分区：
     • 与前面的情况一类似，但是回收时因为空闲分区起始地址没有变化，
     • 所以只用修改分区大小即可
   • 回收情况三，回收区的前后各有一个相邻的空闲分区：
     • 比如第一个分区大小20MB，起始8M
     • 第二个分区大小10MB，起始32M
     • 中间的进程被回收了，需要合并三个空闲分区
       • 前后两个加上进程空闲出来的一个
     • 此时合并后起始为8M，大小为32-8+10=34MB
     • 也就是中间全空出来的情况
   • 回收情况四，回收区前后均没有响铃的空闲分区
     • 直接添加一个新的空闲分区即可。
   • 注：
     • 各表项的顺序不一定按照地址递增顺序排列，
     • 具体的排列方式需要依据动态分区分配算法来确定。
   • 一句话总结，有相邻空闲空间，就要合并
6. 关于内外部碎片：
   • 内部碎片，分配给某进程的内存区域中，如果有些部分没有用上。
   • 外部碎片，是指内存中的某些空闲分区由于太小而难以利用。
     • 如果内存中空闲空间的总和本来可以满足某进程的要求，
     • 但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。
     • 但是可以通过**紧凑（拼凑，Compaction）**技术来解决外部碎片。
       • 也就是将各个进程挪位，将碎片组合成一个连续的空闲空间
       • 回忆交换技术，什么是换入/换出？什么是中级调度（内存调度）？
       • 思考动态分区分配应使用哪种装入方式？“紧凑”之后需要做什么处理？
       • 结果就是动态重定位的方式最方便实现紧凑技术，应该使用它
       • 并且需要修改进程起始地址，进程起始地址一般存放在PCB中，
       • 进程上CPU前，会把进程的起始地址放到重定位寄存器（基址寄存器）里

知识回顾与重要考点

1. 连续分配指用户进程分配的必须是一个连续的内存空间
2. 单一连续分配和固定分区分配都不产生外部碎片，只产生内部碎片
3. 动态分区分配会产生外部碎片，无内部碎片
4. “紧凑”技术作为选择题选项考察过，回收内存分区四种情况也选择题考察过
5. 需要对空闲分区表、空闲分区链有印象。