第五讲_物理内存管理 : 连续内存分配

计算机系统中除了处理能力之外, 还有存储能力. 存储能力就是我们有一系列的基本的存储介质, 我们要在这些介质当中存我们的代码和数据.

对于计算机系统当中, 它的体系结构当中就约定了我哪些地方可以存数据, 然后在存数据的这些地方, 既包括 CPU 寄存器, 也包括内存和外存这几种不同的介质, 它的容量速度价格都是不一样的.

计算机体系结构和内存层次

计算机体系结构

为了组织一个合理的系统, 我们把计算机系统当中的存储组织成了一个层次结构, 针对这种层次结构下的存储单元, 操作系统需要对它进行管理, 操作系统当中的存储管理实际上就是用来管理这些存储介质的.

最基本的管理要求就是我一个进程需要使用存储单元的时候, 操作系统分一块给它, 等它不用的时候还给操作系统, 这是最基本的分配和释放的管理要求.

针对这种内存管理的要求, 我们来看看系统结构当中, 有哪些因素对它有影响.

这个图实际上在前面计算机系统结构的时候已经说过了, 计算机系统包括 CPU, 内存和 I/O 设备. 我们在上一节说到过 CPU 在加电的时候我们关心各个寄存器的初始状态. 那么现在讲存储的时候, 我们会更多关注与存储相关的内容.

比如在 CPU 里面, 寄存器可以存数据, 但是寄存器的容量是非常小的, 通常是 32 位或者 64 位的寄存器, 能存的数据也就几十个字节, 或者几百个字节这种.

然后我们说内存是能存更多数据的地方, 计算机系统中内存最小的访问单位是字节, 也就是 8 bit, 而通常我们所说的计算机系统是 32 位的总线, 那所谓 32 位总线也就相当于我一次读写可以从内存当中读或者写 32 位, 也就是 4 字节, 这样我们读写的速度就会快了. 针对这种特点, 再由于一次读写 32 位的有地址对齐这种事情, 你在访问的时候就不能从任意的地方开始一个 4 字节,有可能这个读写就会被分成两次.

还有一个就是你在 CPU 里面会看到高速缓存, 高速缓存就是在你进行读写指令或者指令执行过程中, 访问数据都需要从内存里读数据, 这个时候如果说我有大量数据要读写, 而且我会重复利用的话, 我在 CPU 里加上高速缓存, 那这样的话它的读写速度会更快, 整个读写效率会提高.

这几个部分对我们存储管理有至关重要的影响, 所以大家在实际做操作系统的存储管理实现的时候, 你必须很准确地了解对应的 CPU 的结构, 呢么对于我们操作系统课来讲, 我们讲的是 X86 的系统, 这底下是 X86 的手册, 你可以查最详细的内容.

(手册链接)

内存层次

接下来我们更详细地来看存储的层次结构

刚才已经说了, 在 CPU 里面有两级缓存 (L1 L2 缓存). 如果你在读写数据或者指令的时候, 在缓存里面已经有相应的内容, 事先已经读过, 那这个时候我就可以直接从缓存里拿到内容, 这时候速度是最快的.

如果在这个时候缓存不命中, 也就是缓存里面没有的话, 你就得去上内存里面去读.

我们在写程序的时候, 你是感觉不到 L1 L2 cache 的存在的, 实际上这一部分完全是由硬件在做控制, 你写的程序不能显示地使用到它们.

而内存的访问需要操作系统的控制, 如果说你在内存里访问的时候仍然找不到, 这个时候还有可能是到外存里面去, 把它找到读进来, 你再进行访问, 这时候就要操作系统的控制.

那在这个体系结构当中, 我们可以看到从 CPU 内部一直到硬盘的外部, 这几个速度差别非常大, 具体差到什么程度, 我们这里有一张表.

最快的和你 CPU 的主频是一样的, 那就是几个纳秒我就能访问到, 最慢的是几个毫秒, 这两者之间, 毫秒 微秒 纳秒, 差距将近百万倍的数量级, 所以在这套体系当中, 要想把它协调成一个有机的整体, 实际上对于存储管理来讲, 挑战性还是很大的.

操作系统的内存管理

对于操作系统来说, 我们存储管理最后想达到什么效果, 在这里给大家一个描述.

首先我们看到系统当中的存储, 内存是以字节为单位进行访问, 每一个字节都有自己的一个地址, 这个地址是物理地址.

然后我如果数据存到外存里了, 比如像磁盘是外存, 磁盘的访问有扇区编号, 每一个扇区是 512 字节最小单位.

这是你能够读写存储的最基本的内容, 而我们写程序的时候希望看到的情况是什么, 是我有若干个进程, 每一个进程都有共同的一部分地址空间, 是操作系统的内核, 而每一个应用程序自己又是不一样的, 它们各自有各自的内容. 我希望在各自写这些内容的时候, 它们的地址是可以重叠的, 相互之间是不干扰的, 这是我们希望见到的状态.

把下面这种内存的状态, 转换成我们上面逻辑的理想状态, 我们在中间加了一层存储管理单元. 存储管理单元就把逻辑地址空间, 转变成物理地址空间.

这时候我实际操作系统的代码存在内存里面, 而进程的地址空间随着它们运行的转换, 有些是在内存里面, 有些是在外存里面. 这个转换的过程, 由中间的存储管理单元来完成.

---

存储管理要达到的效果是抽象, 把线性的物理地址编号, 转变成抽象的逻辑地址空间.

然后我需要在里面对地址空间进行保护, 每一个进程只能访问自己的空间, 尽管在内存里它们是相邻存放的

与此同时, 我们还要方便共享, 比如说我们这里大家可以看到的, 操作系统的内核的代码, 是各个进程都是一样的, 或者说绝大多数部分是一样的. 这种一致, 如果你每个进程地址空间是相互保护的, 不能访问, 这段你就得存多份, 这个效率是很低的, 我们希望能够很好地把保护和共享统一起来. 这个目标实际上是有一些矛盾的.

与此同时我们还希望它实现更好的虚拟化, 这说的是我们每个进程的地址空间编号都是一样的, 但是实际上每个进程都有一段自己的用户地址空间, 这个用户地址空间映射到物理地址空间上, 实际上存的位置是不一样的, 但是给每个进程看到的都是一个区域一致的一个地址空间. 甚至于说我们在逻辑地址空间里, 看到的可以存数据的地方, 它的大小是大于你的物理内存的总量的.

操作系统的内存管理方式

我们看到实际上想要实现存储管理的抽象, 保护, 共享和虚拟化这几个目标还是很有难度的.

具体说起来, 我们在操作系统里会采取如下的办法.

• 重定位 (relocation)

第一个办法就是重定位, 实际上在最早的计算机系统当中, 它是直接使用总线上的物理地址来写你的程序, 我想要读写某个内存单元, 它在什么位置, 我们在程序里见到的就是它的物理地址, 但是这种做法实际上有很大局限, 你写程序只能在指定类型的机器上运行.

我们第一个可以让它做灵活, 实际上相当于我可以整块地搬, 就是我们这里说的重定位. 如果说我们现在看到地址访问的时候, 说每一个地址是用一个段地址加一个偏移来表示, 实际上就是从重定位这个地方来的.

有了重定位之后, 我通过改变我段寄存器的地址, 我这个程序就能运行了, 这是第一种做法, 为了实现它我在操作系统和程序里面都需要有相应的支持, 这些支持以后会说.

• 分段 (segmentation)

接下来的问题是说我们在这里重定位的时候, 我一个进程分的存储空间, 是一个连续的空间, 我不可以把两个交错起来. 实际上这是一个很大的限制, 我们希望它能够不连续.

实际上我们在写程序的时候, 它的逻辑结构并不是一个必须连成一片的区域, 而是说我们把程序分成数据, 代码, 堆栈这三个相对独立的部分, 它不会说我从堆栈里面直接去访问代码段里的内容, 也很少有我从代码段里直接去访问数据段的内容. 依据这种情况, 我至少可以把代码数据和堆栈分成三块, 每一块我要的空间就会变少了, 这就是我们这里的分段.

分段实际上, 你每一段的内容是要连续的, 这个要求还是比较高的.

• 分页 (paging)

接下来我们说分页, 分页实际上就是把内存分成最基本的单位. 就好比我要盖一栋楼, 盖一栋楼需要各种各样的建筑材料, 但是我们用到的最基本的, 就是一块一块的砖头, 你可以把它加在一起, 之后变成你需要的各种各样的形状.

我们也希望是从最小的单位, 一页, 来构建你所需要的内存区域. 当然你说我们最小的单位, 那就用一个字节不就挺好的吗, 但是实际上这个时候你一个字节的话, 你在访问的时候, 它开销就粒度太细, 以至于管理的时候难度很高, 所以我们在这要选一个合适的大小, 这一块最基本的单位是一个连续区域, 这就是我们这里的页, 基于这个来构造你所需要存储空间的内容.

• 虚拟存储 (Virtual memory)
  • 目前多数系统 (如 Linux) 采用按需页式虚拟存储

在这个基础上, 我们希望把数据存到硬盘上, 而硬盘外存上的数据和内存上的数据, 它们俩之间的倒换是由操作系统内部来实现, 这个时候就希望看到的是程序是一个逻辑的地址空间, 甚至于这个逻辑的地址空间是大于物理内存的空间, 那这就是我们的虚拟存储了.

---

在我们实际的操作系统里, 基本上就是这样几种方式来管理内存, 当然我们说的所有这些管理办法, 它对硬件的依赖程度都是非常高的. 比如说 MMU, 存储管理单元里的结构是什么样的, 然后我们 CPU 能够识别的页表是什么样的, 这些都直接影响到你存储管理方式的实现.

地址空间和地址生成

地址空间的定义

• 物理地址空间 -- 硬件支持的地址空间
  • 起始地址 0, 直到 MAXsys

我们在机器总线上看到的地址是我们这里所说的物理地址, 所有的物理地址空间所构成的空间, 叫作物理地址空间, 它是由硬件支持的.

通常情况下, 我们说机器里有多少位地址总线, 指的就是这里的物理地址总线的条数, 比如说 32 位的, 通常情况下就是 32 条地址线, 在我们这里它的编号是从 0 到 4g 减去 1, 那这是从 0 开始一直到它最大编号.

这个编号在存储单元的角度来讲是唯一的, 但是这种唯一, 实际上对于我们写程序来讲, 是不太好用的, 因为我到底用哪个地址, 在程序写成之前, 或者运行之前, 我可能是不知道的.

• 逻辑地址空间 -- 在 CPU 运行的进程看到的地址
  • 起始地址 0, 直到 MAXprog

那么这样一来, 我们在这里用到第二个地址, 是逻辑地址, 逻辑地址是 CPU 运行的时候, 里面的进程看到的地址空间.

通常情况下, 对应着我们可执行文件里的那一段区域, 加载程序的时候, 你的程序加载到内存当中, 它变成进程, 这个时候在你的可执行文件里的 0 到它最大值, 这个地方在相应地址空间里有一段区域, 这段区域就是我们进程的逻辑地址空间. 逻辑地址转换成物理地址, 就是我们后面会说到的方法

那么这时候我们这里访问到一条指令, 这条指令在执行的过程中, 它会访问相应的内存单元, 这些内存单元的地址从哪里来, 就是从这里逻辑地址来, 然后转换到物理地址, 最后在总线上访问相应的存储单元.

逻辑地址生成

我们这里有个小例子, 一个程序, 它有一个保留字, prog 到 end, 这是它的开始和结束标志, 然后中间我调用了一个函数, 这个函数就是一个地址. 我们通常在写函数的时候, 里面不会写 "0x 多少多少" 来作为函数的名字, 这个很不容易记, 我们会用一个符号表示.

用符号之后, 不同的函数之间, 这些符号之间, 它们就没有一个先后顺序的关系, 那你放到内存里面, 可以放到内存的任何一个位置, 这是我们在写程序源代码的时候, 你所希望看到的状态.

---

然后这个源代码我们就会进行一次编译, 源代码的这些语句, CPU 是没办法直接认识的. 我们为了让 CPU 认识这些语句, 必须转化一下. 我们转换的第一步就是把代码转化成机器能认识的汇编码, 然后后面仍然用的是符号名字, 这还只是汇编的源代码.

---

那我们编译之后得到汇编码, 汇编之后我们会再对它进行一次汇编, 汇编之后实际上就变成了二进制代码了, 这时候就是实实在在的机器能够认识的指令了, 这个时候里面的符号就不能再是我们前面讲的这些字符串了, 而是地址空间的某一个位置. 比如这个地方就是 75, 那 75, 就是在你当前位置跳到 75, 这个地方用到的就是编号.

---

在这里面我可能会用到别的符号, 别的地址, 比如我有一个模块调用, 从模块 A 调用模块 B 里的一个函数, 在这个调用过程中, 在你做汇编的时候, 你并不知道另一个模块的位置, 这时我需要再有一个链接的过程, 把多个模块和你用到的函数库放在一起, 排成一个线性的序列.

排了之后我就知道, 你跳转的另一个符号的位置在哪. 比如说我们在这里面你自己会移动, 模块之间也会有, 那这个时候我会告诉你这个地方蹦完之后, 我放的位置往后挪了, 前面是放的函数库, 所以我起头的位置往后挪了 100, 那我这变成了 175, 这个 175 实际上就是从 0 开始, 我只是在这一个文件内的.

---

如果说我的程序这个时候去运行, 那么运行的时候放到什么地方, 不一定正好放到 0 的位置, 那这个时候我在加载的时候, 还会再有一个重定位. 这个重定位就是说我原先的 0, 这是 175, 现在我加载进来之后, 我把它放到 1000 的位置. 那这 1000 从 1000 到 1175, 这个时候我的跳转, 我原来蹦到 175 的位置就是错的, 我要统一把这个位置平移一遍, 变成 1175. 这是你在加载时候的, 由操作系统提供的, 重定位这个功能要做的事情, 有了这个之后, 我们的程序在跑的时候, 它就变成实实在在的地址了, 这是逻辑地址.

地址生成时机和限制

我们在获取这个逻辑地址的时候, 可以在直接加载的时候做到, 但是实际上地址生成机会有这样几种情况.

• 编译时
  • 假设起始地址已知
  • 如果起始地址改变, 必须重新编译

第一个是编译, 假定我知道我最后要放的位置, 我在编译的时候就可以把这个地址写死, 如果是这种情况, 你的起始地址发生变化, 你就必须重新编译了.

这种情况现在在什么地方出现, 比如我们用到的手机, 如果你的手机是功能手机不是智能手机的话, 这个时候里面的程序通常情况下是写死的, 不允许你买了手机之后往里面装地址本或者说再装软件之类的.

• 加载时
  • 如编译时起始位置未知, 编译器需要生成可以重定位的代码 (relocatable code)
  • 加载时, 生成绝对地址

还有一种情况运行你加载到不同地方, 比如我们现在的智能手机, 那你就可以在买到这个手机之后, 再往里面加自己的程序, 这个时候写程序的人就没法知道程序会加载到系统的什么地方去.

如果是这种情况, 我在加载的时候就必须做重定位, 也就是说我根据我装到内存位置里的不同, 我要把里面那些符号的名字或者跳转的地址把它重新捋一遍. 通常情况下, 在我们的可执行文件里面, 它前面有一个重定位表, 那这个重定位项目表里面包含内容就是你在这个程序里面, 到底哪些地方需要去改的, 加载的时候把这个都改成绝对地址, 那你的程序就可以跑了, 这是我们刚才见的情况.

• 执行时
  • 执行时代码可移动
  • 需地址转换 (映射) 硬件支持

还有一种情况, 是执行时生成, 这个相当于我们在前面用的, 一直就是相对地址, 那么到执行的时候, 执行到这条指令的时候, 执行到这条指令的时候, 我才可以去知道它确切访问的是什么地方.

这种情况出现在我们使用虚拟存储的系统里面, 也就是说我执行一条指令, 这条指令访问的位置, 访问到那里之后, 有可能你当时把这一块区域, 放到内存的某一个位置, 这个时候它有一个映射, 映射过去之后你找到相应的位置, 那这个时候只是在执行这条指令的时候, 才会做这种映射.

这样做就有一个好处, 我这个程序在执行的过程当中, 我就可以把它所在的位置, 在物理存储的位置, 我可以挪动, 而如果说是前面两种的话, 你不但需要你在地址空间是连续的, 同时在这里面, 它运行起来之后你是不能再动它的.

比如在这里面我加载的时候做了重定位, 我已经写了绝对地址了, 由于你存储空间不够, 或者说别的程序的存储空间不够, 你把它的位置往后面挪了一段, 你这么一挪完之后, 你那些位置就不对了, 所以从灵活性的角度来讲, 我们在执行时候生成这个地址是最好的, 而前面几种它有一个好处是简单, 所以在这里, 不同系统这几种做法, 我们现在都是有采用的.

地址生成过程

下面我们通过一个例子, 来看一下地址的生成过程

CPU

• ALU : 需要逻辑地址的内存内容

比如说在这里面, CPU 当前正在执行一条指令, 这条指令是 mov 指令, 这条指令在执行的时候里面有地址, 这个地址在 CPU 里先看到了

• MMU : 进行逻辑地址和物理地址的转换

然后这个时候我的 MMU 它依据这边的页表, 来把你这边见到的地址翻译成物理地址

• CPU 控制逻辑 : 给总线发送物理地址请求

翻成物理地址之后, CPU 里面有一个控制器, 这个控制器负责把你得到的物理地址和相关总线控制信号送到总线上

内存

• 发送物理地址的内容给 CPU (读)

• 或者接受 CPU 数据到物理地址 (写)

这个时候存储单元, 存储芯片会识别总线上地址和控制信号, 依据你控制信号到底是读还是写, 总线上有一组相应的时序逻辑的交互

如果是写, 那就会把这边 CPU 送来的数据写到内存中指定的存储单元上; 如果是读, 那就从指定的内存单元当中读出数据, 放到数据总线上, 然后 CPU 拿回去

这是它的一个交互过程

操作系统

• 建立逻辑地址 LA 和物理地址 PA 的映射

在这个交互过程中, CPU 能干什么呢, CPU 能干的是, 地址转换过程它的影响, 实际上在每一次访问的时候, 它是不依赖于软件的, 是由硬件来完成这个转换的, 但这个转换的表, 我们是可以通过操作系统来建立这两者之间的关系, 这是我们后面会说到的页表的功能

地址检查

接下来我们讨论在地址生成过程中的地址检查

这里是一个图示

说明我们 CPU 在执行指令的时候, 它的地址处理过程, 生成过程

这是一条 movl 指令, movl 指令在 CPU 执行过程中, 它会产生逻辑地址, 这个逻辑地址比如我访问的是数据段的数据, 那好, 这时候数据段, 它有一个段基址和段的长度.

如果说你从数据段去访问的偏移量超过这个长度, 这个时候的这个访问应该是非法的, 对于这种情况, 在每次访问的时候, 它都会去检查你的段的长度和偏移量是不是有效的范围.

如果不是, 那么这个时候就去上面这一条, 告诉你内存访问异常, 这条指令执行失败, 然后进行相应的错误处理, 这个由操作系统来做; 另一种情况是说, 这里检查完的结果, 你访问的偏移量是合法的, 这个时候它会和段基址加在一起, 得到你的物理地址. 比如说这里的 500, 1000 加在一起就是 1500. 从这里访问到你对应进程的物理地址空间里面去.

在这个过程中, 操作系统可以通过指令来设置相应的长度和段基址, 我们可以通过软件方法来影响到我这里做相应检查, 有了这个检查之后我们就有了从符号一直到你的逻辑地址, 逻辑地址在执行过程中转换成物理地址, 并且在这个过程中有相应的检查机制, 这是我们在这里说到的地址的生成和检查.

连续内存分配

在分配内存空间的时候, 在没有其他技术支持的情况下, 分配给一个进程的地址空间必须是连续的. 为了提高利用效率, 那我希望分的位置有适度的选择, 这些动态分配算法实际上就是你在去选择的做法.

而选择完之后, 你用的每一个进程可能用的时间长短不一样, 有的进程先结束, 有的进程后结束, 这个时候有可能先结束的会留出一些空间, 后面一个在分配的时候又再去找, 这个过程的执行, 就会在中间留下一些碎片, 这些碎片对于我们后续的分配是会有影响的.

我们就从如何去找你要用的空闲分区, 和如何来处理不能利用的这些小的空闲分区的两个角度来看连续内存分配算法.

连续内存分配和内存碎片

• 连续内存分配

  • 给进程分配一块不小于指定大小的连续的物理内存区域

• 内存碎片

  • 空闲内存不能被利用

每一个进程的地址空间里面, 可能存的是代码数据堆栈这些内容, 那在这些中间, 我们就会有一些区域没办法利用了, 对于这些没法利用的区域, 我们就称之为碎片.

这些碎片是没办法利用的, 没办法利用这个是相对而言的, 如果你要的是小块, 其中这小块还是可以利用的, 但是有一些你是无论如何也用不起来的. 这些碎片, 我们把它分成两种情况.

• 外部碎片
  • 分配单元之间的未被使用内存

一个叫外碎片, 外碎片是两块之间的这一块, 实际上它也是一个小的空闲块, 只是由于它过小, 而其它进程申请的区域的大小都大于它, 而导致这块没法利用.

• 内部碎片
  • 分配单元内部的未被使用内存
  • 取决于分配单元大小是否要取整

另一种情况时内碎片, 内碎片是分配给进程的区域内部的, 一些没办法利用的区域.

什么情况下会出现内碎片呢, 如果说我分配的时候, 并不是说我可以准确地分配你所指定的大小, 比如说你想分配 510 字节, 但是实际上我们在分配的时候, 只能一 512 字节这种 2 的整数幂为单位的大小, 那剩下的几个字节你就没办法利用了, 像这样的我们叫作内碎片. 图中的 P1 和 P3 上边所剩下的这段就是这种情况.

那我们在分配的时候, 希望尽可能减少这种碎片的出现, 从而使得我在利用的时候, 比如说图中空白区域这种情况, 我要分配一个六块的, 那么这两块在这里头是没办法利用的, 如果它两个是在一起的, 这事就成了.

连续分配内存 : 动态分区分配

• 动态分区分配
  • 当程序被加载执行时, 分配一个进程指定大小可变的分区 (块、内存块)
  • 分区的地址是连续的

动态分区分配实际上是说, 我在分配的时候, 我可以指定大小, 并且这个大小是用户指定的时候可以改变的. 那我们分配出来的结果称之为一个分区, 也可能叫内存块, 也可能叫块. 分配出来的地址是连续的,

对于这边是一个例子. 第一个进程, 分配, 第二个进程接着来. 刚开始的时候我可以顺序分配, 这比较容易, 在使用过程中, 某些进程就会结束, 结束掉就会还回来.

对于这种情况, 现在我想要再分配的话, 我就必须知道我哪些内存区域已经分配给了进程, 哪些内存区域还是空闲的.

• 操作系统需要维护的数据结构
  • 所有进程的已分配分区
  • 空闲分区 (Empty-blocks)

实际上在这时候, 我们操作系统就要维护这样两个数据结构.

一个是已分配的分区, 我们就需要知道哪些是已经分配出去的, 分配给了谁; 第二个是空闲分区, 我需要知道空闲分区的位置和大小.

对于我不同的找法, 这两个数据结构的组织形式是会有一些变化的, 在不同组织形式下, 你在找分区或者说把分区释放的时候, 放回到分区列表里的时候, 它的开销是会不一样的, 这是我们在这需要考虑的问题.

• 动态分区分配策略
  • 最先匹配 (First-fit)
  • 最佳匹配 (Best-fit)
  • 最差匹配 (Worst-fit)

对于找分区的不同, 我们在这有这样几种动态分区的分配策略, 大家通常想要是说我要分配一块区域, 我给你指定大小, 这个时候你去分你去找, 你可能会碰到一个我就找一个, 这就是我们这里的第一种情况, 最先匹配.

你找着哪一个, 碰到哪一个就是那个.

我也可以是说找最佳的, 叫最佳匹配. 它的意思是, 我把所有这些空闲空间全部看一遍, 看看这里面, 哪一个比我大, 但是又是大的最少的那个. 如果说你的这些空闲分区, 是按照地址顺序排的, 那么就把整个全部找一遍, 遍历一波; 如果是从小到大排的, 找到第一个就行了. 这是你空闲分区排序办法的不同, 我找的时候开销是不一样的.

还有一种是最差匹配, 我去找, 每次用的时候我用的是最大的, 用最大就相当于是, 按照由大到小排序, 我的第一个肯定就是它了.

这是几种基本分区的分配策略, 下面我们具体来看.

最先分配 (First Fit Allocation) 策略

第一种, 最先匹配策略. 在这里它的思路很简单, 你要分配多少字节, 我就从空闲分区列表里去找第一个比它大的. 比如说在这里头我是按照地址顺序排的, 这个时候我在这去找, 我这个黄颜色是我空闲的.

我这给了个例子, 我想找一个 400 字节的, 我上来看, 这个地方是 1K, OK 它就是比我想要的大, 那就是它了.

分配完了之后, 一块被你申请的进程所占用, 我把它放到已分配分区的列表去, 并且注明它是哪一个进程占用的, 然后这个时候还剩一点, 剩下的一点我又把它描述成另外一个小个的空闲分区, 接着把它放到空闲分区列表里头.

如果我是按照地址顺序排的话, 就是这样.

• 原理 & 实现
  • 空闲分区列表按地址顺序排序
  • 分配过程时, 搜索一个合适的分区
  • 释放分区时, 检查是否可以与邻近的空闲分区合并

现在我们看它实现的办法是什么. 我的空闲分区按照地址顺序排序, 然后分配的时候从前往后找; 找第一个所谓的合适, 就是大于我指定大小的就可以了; 释放的时候我在还回来的时候我放回去, 并且看它前后是否有临近的空闲空间, 这个时候我把它合并到一起, 这个时候找和合并的开销都是比较小的.

• 优点
  • 简单
  • 在高地址空间有大块的空闲分区

但是它在这里头, 因为我们每一次都是从头找, 这样的话你都在前面能找到的时候, 它就不会往后面找, 所以这样一来, 它的另外一个好处就是在高地址区域里面, 会留下一些比较大块的分区. 你在后面申请大块的时候, 我是能找到的, 如果我大块都切成了小块, 那这你就找不到了, 这是它的优点.

• 缺点
  • 外部碎片
  • 分配大块时较慢

它的缺点就是说, 我会有外碎片, 我每一次切的时候, 如果大小不合适我都会切成俩, 这个时候就会留下一个小的空闲分区, 如果这个小的空闲分区多到一定程度, 这时候你在后面往下分配大块的时候, 它就得从前往后找, 也就相当于前面很长一段你找不到, 由于你找不到你就只能往后找, 那这个时候往后找的这个过程, 开销就会越来越大, 也就相当于越往后你在前面搜索的时间就会越长.

最佳匹配 (Best Fit Allocation) 策略

那么第二种方法是最佳匹配, 也就是说它找到一个比它大并且是最小的空闲分区.

如果说在这里头, 这里的这个例子, 我们想要分配 400 个字节, 那 1K 2K 500 字节这三个比较起来, 500 这个是比它大并且是差距最小的.

那么我们在这里来分配, 分配完的结果是什么样子. 我前两个没动, 第三个这个被切成两块, 留下一个小的 100 字节的空闲分区, 另外一个作为已分配的对它进行相应的标识, 标明它被分配给了哪个进程. 那这个事就算搞定了.

• 原理 & 实现
  • 空闲分区列表按照大小排序
  • 分配时, 查找一个合适的分区
  • 释放时, 查找并且合并临近的空闲分区 (如果找到)

我们看这里面我需要维护的数据结构是什么样子的.

首先第一个空闲分区我怎么来排序. 因为我是找比它大的差距最小的那一个, 我找的时候是从小往大找, 所以我的空闲分区如果是从小往大排序, 我开始是比它小的, 第一个比它大的就是我想要找的. 如果前面比它小的数目比较少, 我很快就能找到.

分配的时候我是从前往后找; 释放的时候, 我就看, 跟它临近的进行合并. 这个时候就有个问题, 临近的话我就是需要去找它地址临近的, 并不是大小临近的, 这样一来按地址排序的, 你合并的时候算法就会复杂一些, 花的时间就会长一些.

• 优点
  • 大部分分配的尺寸较少时, 效果很好
  • 可避免大的空闲分区被拆分
  • 可减小外部碎片的大小
  • 相对简单

这种做法好处是, 我可以把大的块, 如果我分配块的尺度都是比较小的时候, 这个时候它的效果是比较好的. 如果你分配大的, 那这个时候它后边剩下的就少了. 这时候它的好处是避免大的分区被拆分, 因为你找的是比它大差距最小的那个, 然后它可以减少外部碎片的尺寸, 也就是说剩下的那块一定是我能找的这一块里, 剩下的最小的那块. 然后相对来说它比较简单.

• 缺点
  • 外部碎片
  • 释放分区较慢
  • 容易产生很多无用的小碎片

缺点是说你剩的那块边角料是小了, 但剩的越小这块边角料它越没法利用, 所以它有外碎片; 并且释放分区的时候它会比较复杂, 然后剩下的那些小碎片基本上也就没用了, 这是最佳匹配.

最差匹配 (Worst Fit Allocation) 策略

还有一种做法是最差匹配. 它的做法是找最大的, 有可能说我找最大也不满足我的需求, 这是找不到了.

那这里头我找了一个最大的, 比如说在这里的这个例子, 我要分配 400 字节, 那这个时候找哪个呢, 最大的这是 2K. 我把它切成两块. 上面的标记已分配, 剩下的这一块还有 1K 多, 比 1K 那块还大, 它可以被利用的机会就会更多, 这是最差匹配它所带来的的好处.

• 原理 & 实现
  • 空闲分区列表按由大到小排序
  • 分配时, 选最大的分区
  • 释放时, 检查是否可与临近的空闲分区合并, 进行可能的合并, 并调整空闲分区列表顺序

具体做法是这个地方空闲分区排序要怎么排, 这个时候由大到小排, 我每次找的时候只要第一个满足要求, 那就是我要找的.

这时候分配的时候就是找最大的分区, 也是找第一个, 找的速度是最快的.

然后释放的时候, 我要去找它临近的, 由于我排序不是按地址排的, 所以找临近的就需要去顺序找了, 找到临近的然后把它合并到一起, 放回到空闲分区列表, 这个时候我还要去找放的位置, 因为你原来是按大小排序的, 现在你仍然需要按照大小来排序, 要不然下次找的时候就不对了.

• 优点
  • 中等大小的分配较多时, 效果最好
  • 避免出现太多的小碎片

如果说你的中等尺度的分配比较多, 这个时候效果是比较好的, 因为我用掉那块不是很大, 然后剩的那块多的时候还能利用起来, 相当于我剩的小块就比较少了, 剩的那块我还可以找到用处.

实际上这个时候关键是, 剩的那块能给它找什么样的用处.

• 缺点
  • 释放分区较慢
  • 外部碎片
  • 容易破坏大的空闲分区, 因此后续难以分配大的分区

它的缺点是释放过程比较慢, 因为释放之后的合并是要进行搜索的, 它排序跟我这个合并没有关系; 然后也会有外部碎片; 如果说你在这头由于我每次都是最大的, 你在后面想分配大分区的就比较困难了.

---

这是我们在这里说到的几种连续存储分配的做法, 这几种做法的主要出发点就是我那个空闲分区的列表, 它是按什么来排, 然后我们需要去考虑的是, 在分配的时候它的查找开销和在释放的时候它合并的开销和把这个合并完的结果放回到空闲分区列表里的时候, 找合适位置的开销.

碎片整理

碎片整理是说, 我们已经把内存分区分配给了进程, 它们也已经站定了某一个位置, 但是这个时候我正在执行的应用进程, 或者说新创建的进程需要内存空间, 这个时候没有了, 或者说这些都已经剩下小的碎片了.

那我想要内存空间, 这个时候怎么办, 我们可以通过碎片整理, 来获取更大的可用内存空间, 以便满足进程的应用空间需求.

碎片整理 : 紧凑 (compaction)

• 碎片整理
  • 通过调整进程占用的分区位置来减少或避免分区碎片

这种做法有一个图示, 这里面白色部分就是空闲的空间. 这里最大的是剩下三块, 但是我现在要分配一个连续四块的空间, 那就没有了, 这个时候怎么办呢.

我们希望通过碎片整理把它压缩到一起, 然后剩的这块就可以满足需求了, 但是我要把正在内存当中的这些进程的位置挪动, 这个事情不可以随便弄的, 原因在于我里面可能有各种各样的地址引用, 这些地址引用要是用的是绝对地址, 那这个时候挪动之后它是没法正确运行的.

• 碎片紧凑
  • 通过移动分配给进程的内存分区, 以合并外部碎片
  • 碎片紧凑的条件
  • 所有的应用程序可动态重定位
  • 需要解决的问题
  • 什么时候移动 ?
  • 开销

所以在这里面要进行碎片紧凑, 它是需要一些条件, 也就是说我所有的这些进程, 都是可以动态重定位的, 只有做到这点之后, 我这里程序才可以去挪动它.

当然这种挪动也是有开销的, 你不可以去搬正在处于运行的状态的.

通常情况下, 处于等待状态的进程, 我会对它进行搬动, 然后再有一个, 并不是说为了一小块区域, 我要把整个内存当中的很多进程都把它挪一遍, 这个开销也是大的. 我在这里头在什么情况下需要考虑到开销, 然后进行紧凑, 关于具体的做法, 在大家需要相应的技术的时候再仔细去看, 我们这就介绍到这种程度.

碎片整理 : 分区对换 (Swapping in/out)

• 通过抢占并回收处于等待状态进程的分区, 以增大可用内存空间

第二种做法是分区对换, 刚才我把内存里的这些分区, 不管怎么挪, 最后的结果它都是在内存里面, 如果这个时候仍然不能用, 你还是没办法.

所以在这里, 内存分区对换, 是指我把这种处于等待状态进程, 它占用地址空间给它抢占了, 然后把这个等待进程占用的数据, 我给存到外存里面去, 在这里就是对换到对换区, 这时候我内存里的空间也就变大了.

我们通过一个图示来看.

在这个图里, 底下是内存和外存的状态, 中间这个实际上是我们在系统里面, 进程在执行过程当中, 我们维护的进程的状态信息, 这个我们后面讨论会说到.

我们看每创建一个进程, 它在内存里要占一块区域, 创建好之后, 它数据结构都弄好, 操作系统维护的数据结构建好, 然后这个时候它可以投入到运行状态.

它在运行的过程中, 可能会有另外一个进程要创建, 它也需要在这里分配相应的存储区域, 然后进到就绪状态, 第一个还在运行, 在这个过程当中我们可以继续进行下去.

由于某种原因, 我 P1 处于等待状态, 这时候 P2 P3 又进内存里来到运行状态, 那么在这种状态下, 如果说我再有一个 P4 进来, 它要的空间不够了, 这个时候怎么办呢, 我们会把处于等待状态的这个搬到外存里面去.

这样空出一块区域来, 我把这个 P4 放到这里, 这时候我们就可以让它更多进程在系统里交替运行, 使得我的可用空间变大.

实际上大家如果注意的话, 在你的 linux 或者 unix 系统里, 它有一个分区, 叫对换分区. 实际上这个对换分区在早期的时候, 它就是一种充分利用内存的做法.

那么在这个图里我们可以看到, 在早期, 甚至在操作系统里面, 只有一个应用进程可以在内存的状态下, 它都可以用对换来实现多进程交替运行. 这里是, 任何时候只有一个进程在内存中运行, 而处于暂停的进程是放在外存里面的. 如果说当前进程主动让出处理器使用权限, 这个时候就把它对换到外存去.

在我们比较早的时候是用的这种方法, 内存很紧张的情况下, 我们在系统里可以实现多进程的交替运行. 当然在这里的交替, 它的开销是非常大的, 原因在于内存和外存之间的速度差的很远.

即使是这样, 由于我们计算机系统的成本非常高, 所以这样做的开销也是可以接受的. 在这里面, 我在对换的时候, 到底把谁对换出来, 这个时候开销有多大, 这个时候在系统里, 你就得经过仔细的权衡, 所以在前面的时候它花很大的精力去解决, 我到底是对换哪一个进程, 这是我们在早期的时候, 计算机系统里的多进程通过对换区的一种实现方式.

伙伴系统

接下来是一个连续内存分配的实例, 伙伴系统

伙伴系统实际上是一种, 连续存储分配的办法, 它在这里比较好地折中了分配和回收过程中, 合并和分配块的位置以及碎片的问题.

伙伴系统 (Buddy System)

• 整个可分配的分区大小 2^u

伙伴系统实际上是把整个你可以分配的分区的大小, 约定为必须是 2 的次方. 这样做之后, 任何一块要分的时候, 只是把它从中间分开. 它不会以其它方式来切, 只是两个小块合在一起变成一个更大的.

• 需要的分区大小为 2^u - 1 < s <= 2^u 时, 把整个块分配给该进程
  • 如 s <= 2^(i - 1) - 1, 将大小为 2^i 的当前空闲分区划分成两个大小为 2^(i - 1) - 1 的空闲分区
  • 重复划分过程, 知道 2^(i - 1) < s <= 2^i, 并把一个分区分配给该进程

如果说你在分配的时候, 你需要一块它的大小, 实际上可用的块, 如果它的大小比你需要大小的 2 倍还大的话, 我就把它切一半然后再跟你做比较. 如果说在这里你比它 1/2 还大, 但是没到当前大小的话, 它就直接把整块给你.

如果说它比你 2 倍还大, 那我就把它切半, 切半之后仍然比你 2 倍还大, 那这个时候我继续切半, 一直切到某一个状态, 切到你就比它大了, 而当前状态是比你的 2 倍小, 这个时候我把这块就分给你.

那这个时候我们形成内碎片最大可能是, 你这个大小的 1/2 然后减去 1, 也就是说你正好需要 1/2 的时候, 我就可以把它分半, 你再多一个字节, 我有可能就给了你差不多一倍的大小.

类似于 "折半查找", 这是 Buddy System 它的基本道理.

伙伴系统的实现

• 数据结构
  • 空闲块按大小和起始地址组织成二维数组
  • 初始状态 : 只有一个大小为 2^u 的空闲块

首先我们来看在伴侣系统当中我们需要维护的数据结构, 在这里面我们空闲块维护的是一个二维数组, 这个二维数组第一维是空闲块的大小, 由小到大我排成第一维.

在相同大小这些空闲块里面, 我按照它的地址排序排成第二维, 这是我们这里的空闲块的二维数组.

然后在起头的时候, 整个系统里只有一块空闲块, 这是整个空闲内存区域.

• 分配过程
  • 由小到大在空闲块数组中找最小的可用空闲块
  • 如空闲块过大, 对可用空闲块进行二等分, 直到得到合适的可用空闲块

在分配的时候是什么呢, 分配的时候我是由小到大去找, 去找比我需要的大小更大的空闲块.

如果说我在初始状态下我找到整个一块, 这个时候我就会有第二步, 找到之后我会看, 如果这块过大, 所谓过大就是我需要的大小的二倍比你给出的这块还小, 我就把它切成一半, 变成 2 的 u-1 次幂, 然后比较这个大小跟我需要块的大小.

如果比它 2 倍还大我就继续分, 分完之后变成两个空闲块, 把它放到空闲块列表里面去, 二维数组里头. 然后这个时候一直找, 找到我需要大小是比空闲块的 1/2 大, 但比空闲块的 1/1 小的时候. 这个时候我就把这块分给它. 这是分配的过程.

伙伴系统中的内存分配

我们通过一组例子来看分配流程.

假定我最开始的时候, 它的大小是 1m; 然后这里面我们需要的是 100k, 100k 的话 1m 切成一半 512 256 128, 切到 128 的时候能够满足我的要求.

这个时候切完之后的情况, 切成一半, 再切一半, 然后再切一半, 128, 这个时候它的大小比我需要的 100k 要大, 但是比我需要的 100k 的两倍也就是 200k 要小, 那我就把这块分配给它.

第二个分配请求是 240k. 240k 那我们从这里看, 比它大 256k, 256k 是比它大, 但是比它 2 倍要小, 这个我们应该要分配到这, 分配下来的结果是这样的, 给它分配 256k 的空间.

第三个是给它分配 64k, 64k 我们看比 128 小, 那 128 的 1/2 是 64 正合适, 那这个时候我把它分了, 把 128 分成两半, 搁在那里去了.

再下一个就是说我需要 256, 那 256 我们在这里空闲的只有 512 比它大, 切成 1/2, 这是分配之后的结果.

然后再往下是释放 B, 释放完了之后按照我们原来连续分区的分配, 我有一个合并的问题. B 的这一块回来之后, 它没有办法跟 64k 合并, 因为合完之后的大小不是我们前面说的正好是 2 倍, 也没办法放回到空闲分区的数组里面去, 这个时候我就变成两个空闲分区.

这个时候我就变成两个空闲分区, 然后我再释放 A 那 128k 还回去, 它也没有办法跟别人合并, 它是单独一个.

然后我这个时候申请一个 75k, 75k 仍然可以放到那儿, 这个时候换成 75k 给了它 128k.

这个时候我再看, 这个时候把 C 释放掉. C 释放掉的时候, 这个地方一个 64, 和旁边 64 它俩合起来的时候, 正好是原来 128, 可以把它俩合在一起, 这个时候就变成 128 了. 128 不能和那个 256 合并, 因为不构成 2 的幂, 即使能构成 2 的幂, 它也还会有问题.

然后这个时候我再释放 E, 把这几个最后它们三个就会合在一起. 最后再还回 D 整个过程结束.

在这个过程当中, 我们已经看到了它分配的时候情况, 我找一个比它大的, 最小的空闲块, 然后看看是不是比它 2 倍大. 如果是就切半, 如果不是, OK 那就是它. 这样我们分配的过程就有了.

伙伴系统的实现_续

• 释放过程
  • 把释放的块放入空闲块数组
  • 合并满足条件的空闲块

• 合并条件
  • 大小相同 2^i
  • 地址相邻
  • 起始地址较小的块, 的起始地址必须是 2^(i+1) 的倍数

接下来我们把刚才说的合并的事情再明确一下. 合并的时候我放到空闲块里面, 比如我在这里分配任何一块, 合并的时候需要满足条件.

那满足条件是什么样的呢, 大家看看, 我在这里面, 如果这块还回去, 它可以和哪块合并.

我们在这里第一个条件就是相邻的两块大小必须是一样的, 然后第二个, 当然它必须是相邻的. 如果说你中间隔开了, 那它是合不到一起的, 在这我们也没有移.

相邻的两块, 低的地址必须是 2 的整数次幂, 这个时候我们第三个条件就是低地址的空闲块起始地址必须是块大小的 2 倍的整数倍.

有了这个之后, 我们的伴侣系统就可以在实际系统当中来进行使用了. 目前在我们用到的 linux unix, 都有 buddy system 的实现, 它是用来做内核里的存储分配.