OS——基本存储管理(1)

基本存储管理

终于也是跨过了处理机管理，来到内存管理的内容了。目前基本存储管理这一章还差分页、分段以及段页三种管理方式没有学，之所以在学之前来写这一篇文章，主要是觉得这一章的内容过于零碎了，不易成逻辑又很容易忘掉，所以写这一篇来串一下已学的内容，在复习的基础上为学接下来的做一些铺垫。

大致框架

在第一节基本就把存储管理的大致框架说明了，首先是一些基本概念，之后是存储管理的基本功能。基本功能几乎是整个第六章的内容，内存的分配与回收功能是最主要的，已经学的分区以及后面的分页，分段等等都是说这个的。接着是地址重定位，这在第一节已经说清楚了，之后是内存的共享和保护，这里课本上涉及不多，但是在看课时也略微学到一些。最后是内存的扩充，这一章主要介绍了覆盖和交换技术，至于虚拟内存技术要留在下一章讲了。

那么，大概了解框架后，我们就正式开始。

存储系统基本概念

物理地址&逻辑地址

• 物理地址：就是数据在内存中实际存放的位置，是一个绝对地址。
• 逻辑地址：程序员编的一个相对地址。

举个例子：一段程序在内存中的存放位置是100-149，这是它的物理地址。那么程序员在编写时，可以将逻辑地址设为0-50。

那么问题就来了，我们写的时候直接用物理地址写，然后再装入内存不就好了，为什么要再使用一个逻辑地址？原因是在多道程序环境中，程序员无法知道程序被装入内存的哪个区域执行。在单道程序环境下，是可以使用物理地址的。

程序修行学

这里用一张图说明一个程序从编写到装入内存需要经历的事，我们假设编辑的是一个C程序：

• 经程序员编写后，形成最初的.c文件
• .c文件经过编译，将高级语言翻译为机器语言，形成目标模块.o文件
  • 目标模块中的指令使用的地址是逻辑地址
• 若干目标模块经过链接，形成装入模块.exe，在链接的过程中将目标模块中分散的逻辑地址合并为完整的逻辑地址
• 最后装入模块经过地址重定位后转换为物理地址，最后装入内存

在这个过程中我们需要研究的重点是：

• 怎样完成逻辑地址到物理地址的转换——地址重定位
• 怎么完成程序的装入
• 几种链接方式

地址重定位

我们知道逻辑地址是一个相对地址，和其加载到内存中的物理地址是不对应的，所以程序想顺利执行就得把逻辑地址转换成物理地址，这个过程就称之为地址重定位。

我们根据地址重定位的时机不同，分为静态地址重定位与动态地址重定位。

静态地址重定位

重定位时机：程序被装入内存的过程中，程序运行前

物理地址 = 装入内存的起始地址 + 逻辑地址

图解：

优点：不需要硬件支持（动态需要重定位寄存器）

缺点：

• 程序只能装入内存的一片连续区域上，不能离散装
• 一旦装进去，就不能移动

😶‍🌫️分割线———-

动态地址重定位

重定位时机：程序运行过程中。即程序在装入内存中先不地址转换，等到执行时，再转换。（也就是装入的是逻辑地址）

使用重定位寄存器存放装入模块存放的起始位置

物理地址 = 重定位寄存器的值 + 逻辑地址

优点

• 支持程序执行过程在内存中移动，只需修改重定位寄存器的值（起始地址的值）
• 支持程序在内存中离散存储，也是修改重定位寄存器的值

缺点：需要硬件支持。

现代OS基本采用的是动态地址重定位。

程序的装入方式

根据地址重定位的方式不同，其装入内存的方式也不同，我们分为3类，其和地址重定位的方式是一一对应的。

绝对装入

装入模块使用物理地址直接装进去，无需地址重定位。

这是在单道程序设计阶段实现的，用户提前知道物理地址，因此无需转换。

静态重定位装入（可重定位装入）

即使用静态地址重定位的装入方法，不再赘述。

动态重定位（动态运行时装入）

即使用动态地址重定位的装入方式，装入内存的是逻辑地址，直到运行时利用重定位寄存器转换为物理地址。

链接

看完最核心的两步之后，我们折返回来看看链接。链接的目的形成完整的逻辑地址，我们根据链接的时机，也可以分为三种链接方式：

• 静态链接：在程序运行前，将若干目标函数以及他们所需要的库函数链接为一个完整的可执行文件（装入模块），之后不再拆开。
• 装入时动态链接：将目标模块装入内存时，边装入边链接
• 运行时动态链接：在程序执行过程中，需要该目标模块时，才对其链接。
  • 有若干模块，需要谁链接谁
  • 便于修改和更新
  • 便于实现对目标模块的共享

分区存储管理（内存的分配&回收）

在上面的地址重定位是内存管理的基本功能之一，现在我们再来讲讲内存管理的另一个基本功能——内存的分配和回收。

其按照分配的方式可分为连续分配存储管理和非连续分配存储管理。

• 连续分配存储管理：为一个程序分配一个连续的空间，其中这一节要说的单一连续分配、固定分区分配、动态分区分配都是连续分配
• 非连续分配存储管理：大概就是分配的空间是不连续的，这块的学习还在后面。

在正式开始之前，我们先明确两个概念——内碎片和外碎片

• 内碎片：某进程用不完其分到的分组
  • 例：给一个10MB的进程分配了12MB的内存，就有2MB为内碎片
• 外碎片：内存中某些空闲分区因太小而难以利用
  • 例：一个内存经分配后空闲分区先后为：1MB,1MB,2MB,1MB，此时如果来一个5MB的进程，是无法满足的。

在如下的讲解中我们都会分析这种方式是否有内碎片或外碎片。下面就来正式看一下这节要说的三种连续分配方式：

单一连续分配

内存被分为系统区和用户区。

• 系统区位于低地址：存放操作系统相关数据
• 用户区：存放用户进程相关数据

单一连续分配即一个进程占一个用户区，显然这种情况只使用于单道程序环境下。

有内碎片：很显然啦，那么大一个用户区就一个进程，存储器利用很低

无外碎片：大概是因为全是内碎片？

固定分区分配

可能是大佬们觉得单一分配太低效辣，然后多道程序环境一出，就想着一片内存给多个进程，咋办呢？于是就把用户区分区了，每个分区装一个程序，分区一旦划好，不能重分。而且分区大小和数量都是固定的，这也就是叫固定分区的原因了。

划分方式：根据划定的分区大小是否相等，分为分区大小相等&分区大小不等。

分区大小相等

看图

这种方式就有点缺乏灵活性，比如来一个12MB的大程序，就没有它的容身之地，来一些很小的程序，一个程序占一个分区，就会产生大量内碎片。

但不会产生外碎片，为什么？因为是固定分区，一个分区就一个进程，外碎片大概是要动态分区才会产生。

虽然这种方式很呆，但不可否认的是，其适用于一台计算机控制多个相同对象的场合。

分区大小不等

看图

就一定程序上解决了分区大小相等的问题，系统可以根据程序的大小选择适合的分区，减少了内碎片的数量（但是也有）。而且较大的分区也有机会找到一个大分区运行。

分区说明表

既然一个用户区被划了好几块，就得用一个数据结构管管它——分区说明表。

功能是来记录每个分区的大小，起始地址和状态等信息。

固定分区分配的优缺点

优点

• 相对单一分配，无疑是增加了内存利用率

缺点

• 分区一开始就确定了，限制了系统并发进程数目。（就很像打仗时就带这么多兵，万一对方比预想的很强就直接gg）
• 还是存在很多内碎片，浪费内存空间。

动态分区存储管理

分区不是固定划分好的，而是根据进程实际需要动态划分（可以让分区大小正好适合进程需要），果然是大佬们看不下去静态分区有那么多内碎片了。

采用的数据结构

• 分区说明表：和静态的相同，描述内存中分区的情况。
• 空闲分区表/链：记录每个空闲分区的情况，包括起始地址，分区大小等。

分区的分配&回收

分配

• 来进程->按照一定算法查空闲分区->查到就塞进去->空闲分区被分为两部分：装入进程的部分以及一个新的空闲分区->修改数据结构
• 没查到就分配失败

回收：进程运行完时内存需回收分区，我们需要考虑回收分区是否与空闲分区相邻

• 不相邻：为该回收区建立一个空闲分区表/链，添加其首地址与大小
• 相邻：回收分区与相邻的空闲分区合并为一个大的空闲分区，并根据情况不同修改其大小与首地址

动态分区分配算法

• 首次适应算法
  • 空闲分区以地址由低到高排列
  • 来一个进程就从头开始找，找到第一个就用，然后修改空闲分区表/链
  • 缺点
    • 低地址部分不断被划分，出现了很多难以利用的小分区
    • 每次都从低地址开始找，然后每次都会遍历一遍上一条出现的很小的分区，就会增加寻找的开销
• 循环首次适应算法
  • 目的：为了解决首次适应算法每次查找可能会经过很多小分区的问题
  • 思路：从上次找到的空闲分区的下一个分区开始寻找
  • 设置一个起始检索指针，指向下一次开始检索的位置
• 最佳适应算法
  • 空闲分区按分区大小递增的顺序排列，保证分配给进程的一定是最小且可以满足的。
  • 优点：避免大材小用，大的分组可以保留下来给大作业
  • 缺点：留下很多小的外碎片
• 最坏适应算法
  • 思路：为了解决最佳适应算法留下很多难以利用的小碎片的问题，在每次分配时优先使用最大的空闲区，这样分配后剩余的空间就不会太小，方便后续使用。
  • 空闲分区按大小递减的顺序排列
  • 缺点：会导致大空间被很快的用完，之后再来大作业就没地方放了。

总体来看：（这一点是我想写的一点）

我们最先设计了首次适应算法，这种算法的缺陷是每次都要从头查找，都需要检索一遍低地址的小分区。我们为了解决这个问题设计了循环首次适应算法，从上次分配的空闲分区的下一个分区开始查找。即循环首次适应不会查找已分配分区之前的分区。那如果来了一个更小的分区，这个分区恰好在之前的小分组可以满足，此时我们希望直接用上面的小分区，这时我们希望算法是首次适应算法。实际上，首次适应算法也隐含了一点最佳适应算法的优点。

而此时我们如果继续使用循环首次适应的算法，那么这个小分区就会占用下面的分区，可能会导致高地址部分的大分区被使用，导致如果来了一个大分组，导致其没有大分区可用，所以，循环首次适应算法也隐含了一点最大适应算法的缺点。

四种算法中，首次适应算法的效果反而更好。