操作系统– 连续内存分配、非连续内存分配一点一滴铺就人生-

一、连续内存分配

逻辑地址映射到物理地址，当我们给程序分配物理地址空间时，会给予一个程序随机连续的一段物理地址空间。那么就会出现内存碎片的问题！

1、内存碎片的问题

（1）外部碎片

上述白色部分就是外部碎片

定义：在分配单元间的未使用内存

（2）内部碎片

定义：在分配单元中的未使用内存

有了碎片，就降低了内存使用率，这个时候连续内存分配方法就很重要了。

2、连续内存分配算法

（1）首次适配

使用该算法进行内存分配时，按地址排序的空闲块列表，从空闲分区链首开始查找，直至找到一个能满足其大小需求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。

该算法倾向于使用内存中低地址部分的空闲分区，在高地址部分的空闲分区非常少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。缺点在于低址部分不断被划分，留下许多难以利用、非常小的空闲区，而每次查找又都从低址部分开始，这无疑会增加查找的开销。

碎片重分配需要检查，看是否有自由分区能合并于相邻的空闲分区，若有，然后调整空闲块列表

优势：

• 简单
• 易于产生更大空闲块，向着地址空间的结尾

劣势：

• 外部碎片
• 不确定性

（2）最优适配

最优适配算法是从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区的一种计算方法，这种方法能使碎片尽量小。

优势：

• 当大部分分配是小尺寸时，很有效
• 比较简单

劣势：

• 外部碎片
• 重分配慢
• 易产生很多没用的微小碎片

（3）最差适配

为了避免有太多微小的碎片，最差适配算法是从全部空闲区中找出能满足作业要求的、且最大的空闲分区的一种计算方法。

优势：

• 假如分配是中等尺寸效果最好

劣势：

• 重分配慢
• 外部碎片
• 易于分割大的空闲块，以致需要大分区时，无法满足需要。

3、碎片整理方法

（1）压缩式
将程序拷贝到其他连续的地址空间里去，一般在程序停止时，进行拷贝，在内存中拷贝开销也是非常大的，如下图所示

（2）交换式
采用换入换出的方式，将硬盘当作后备
这种内存已经使用满了，压缩式已经不能够使用了，我们只能把其中一个未运行的程序放入硬盘中，腾出空间给需要运行的程序。粒度是以单个程序大小作为单位的，如果大块的程序的换入换出开销也挺大的。当然p4的数据并没有丢失，只是放到了硬盘，需要运行时，又从硬盘调进内存。

选择那个程序换入换出，也是需要一个好的算法来支持的。

4、连续内存分配的缺点

• 分配给一个程序的物理内存是连续的
• 内存利用率低
• 有外碎片和内碎片的问题

二、非连续内存分配

1、非连续分配的优点

• 一个程序的物理地址空间是非连续的
• 更好的内存利用和管理
• 允许共享代码和数据（共享库等）
• 支持动态加载和动态链接

2、分段

从代码来看，有主程序、子程序、共享库形成了代码不同的分段；从数据存储来看，有堆、栈段、共享数据段。

将各个段进行识别分离，这样更有效的进行管理，这就是分段的目的。因为我们需要映射到物理地址空间，可以是不连续的，就需要一种映射的机制。

（1）程序访问物理地址需要：

一个2维的二元组（s，addr）

• s—段号
• addr—段内偏移

（2）两种存储方式：

（3）分段机制访问内存流程图

段表：里面存的是逻辑段号到物理段号的映射，以及段长的限制 段号：决定了看段表中的哪一项 段偏移：段偏移会和段长的限制比较大小，小了，才是合法的，才能允许访问内存。 

因为段的大小不固定，所以不能光凭物理段号加段偏移算出物理地址。

3、分页

（1）程序访问物理地址需要：

一个2维的二元组（p，o）

• p—页号
• o—页内偏移

注：

• 页寄存器定义了DMA缓冲区的起始位置所在物理页的基地址，即页号。页寄存器有点类似于PC中的段基址寄存器
• 帧号原名页帧号，又叫块号、页框号

（2）和分段的区别：

分段的段长是可变的，分页的页的大小是固定的。

（3）逻辑地址和物理地址划分的单位

• 划分物理内存至固定大小的帧，大小是2的幂；eg：…512，4096，8192
• 划分逻辑地址空间至固定大小的页，大小是2的幂；eg：…512，4096，8192

注：页和帧都是大小必须是相同的。

（3）物理地址计算实例

（4）分页机制访问内存流程图

根据页号找到页表项，然后得到帧号，帧号*帧大小+页内偏移就得到了物理地址。

（5）分页机制的特点总结

逻辑地址空间是大于物理地址空间的，所以不可能所有页都有对应的帧，这个需要硬盘虚拟内存技术来解决！

（6）页表转换实例

第一个求逻辑地址为（4，0）的物理地址：
我们可以根据页号4，判断页表项为第一项，其存在位为0，故此页在内存中不存在，所以会报内存异常。
第二个求逻辑地址为（3，1023）的物理地址：
我们可以根据页号3，判断页表项为第二项，其存在位为1，故此页在内存中存在，且帧号为4，所以物理地址为（4，1023）。

注：因为页表可能非常大，所以不能放在cpu或者缓存中，因此页表是处于内存中的。
所以访问一个内存单元需要两次内存访问：

• 一次用于获取页表项中的帧号
• 一次用于从内存中取数据

接下来将从时间和空间提升访问速度。

（7）从时间上提升访问速度：TLB快表

TLB特点：

• TLB使用关联内存实现，具备快速访问性能，但它非常小，只存储最近使用的表项
• 如果TLB命中，帧号可以很快被获取
• 如果TLB未命中，会去查询页表，同时对应的表项被更新至TLB中
  

（8）从空间上提升访问速度：多级页表（了解即可）

如果存在位为0，那么只查询一级页表就够了。加快了速度。

（9）反向页表（了解即可）

我们都知道逻辑地址空间是大于物理地址的，很多查询不存在，我们能不能不建立页表和逻辑地址空间大小相对应，而是让页表与物理地址空间大小相对应？

这个就是反向页表，根据帧号查询页号。