内存管理的基本原理

内存管理的功能

内存管理的功能：

• 空间的分配和回收
• 地址转换：逻辑地址和物理地址。
• 内存扩充：逻辑上扩充内存，例如采用虚拟存储技术或者覆盖技术。
• 内存共享：多个进程访问同一块数据区域。
• 内存保护：各作业在各自存储空间内运行，互不干扰。

链接和装入的三种方式

重定位的概念：重定位指的是装入过程中对目标程序的指令和数据地址的修改过程。

程序的链接和装入：创建进程之前，要将程序和数据都装入内存。一般要经过编译、链接、装入三个步骤来完成。

• 链接的三种方式：
  • 静态链接：程序运行之前，将各个目标模块链接为完整装配模块。
  • 装入时动态链接：装入内存时，边装入边链接。方便修改和更新，方便共享。
  • 运行时动态链接：执行中需要用到的时候才链接。能加快装入过程和节省内存。
• 装入的三种方式：
  • 绝对装入：只适合单道程序。编译的时候就编译为内存绝对地址。
  • 静态重定位：地址变换在进程装入时一次完成。必须一次性分配需要的全部内存空间，否则就无法装入。而且装入后不能在内存中移动。
  • 动态重定位：程序如果需要在内存中移动，就要用到动态重定位的装入方式。
    • 描述：装入后不立刻修改地址，而是等到执行时才修改地址。
    • 硬件：需要重定位寄存器的支持。
    • 优点：程序可以分配到不连续的存储；可以只装入部分代码；可以根据需要动态分配内存；可以方便程序共享

操作系统通过内存管理部件MMU来完成逻辑地址转换为物理地址。

进程的内存映像

进程的内存映像的要素：

• 代码段：只读，可共享。
• 数据段：运行时加工处理的对象。包括全局变量，静态变量。
• PCB：放到系统区。
• 堆：存放动态分配结果。malloc可以向高地址分配空间。
• 栈：实现函数调用。

下图是一个进程再内存中的映像，从低到高大致可以分为：

• 未使用区
• 代码段（只读）
• 数据段（可以读和写）
• 堆：向高处扩展
• 共享映射文件：存放共享函数库的代码，如c里面的printf。
• 用户栈：向低处扩展
• 内核区

内存保护

• 概念：保护进程的存储空间不受其他进程影响。
• 两种方法：
  • 方法1：设置上下限寄存器。
    • 描述：存储这个作业的上限地址和下限地址。每次访问一个地址，需要CPU判断这个地址是否越界。
  • 方法2：重定位寄存器（基地址寄存器） + 界地址寄存器
    • 重定位：用来加的。偏移量，如果没有越界，那么加上这个偏移量就是物理地址。
    • 界地址：用来比的。边界值，如果小于表示越界。
    • 加载这两个寄存器必须试用特权指令。

内存共享

• 概念：某一块内存区域可以被多个进程共享使用。
• 可重入代码：不是所有的区域都可以被共享，只有只读的存储区域才可以被进程共享。其中，纯代码，即允许多个进程同时访问但不允许被任何进程修改的代码。

覆盖与交换

覆盖和交换技术都是用来扩充内存的方法。

覆盖：（已经成为历史）

• 描述：将用户空间分为一个固定区和若干覆盖区。我们将经常访问的部分放在固定区。将要访问的段放到覆盖区，其他段放到外存，需要调用前系统再将其调入覆盖区。
• 特点：打破了一个进程的所有信息必须都装入主存才能运行的限制。
• 缺点：同时运行程序的代码量大于主存的话还是不能运行。内存中只能更新覆盖区。
• 范围：同一个进程。

交换：

• 描述：将处于等待的进程换出到外存。
• 案例：中级调度就是交换技术。
• 要求：
  • 进程执行时间要大于交换时间，不然就没意义了。
  • 交换空间独立于文件系统，磁盘分为交换区和文件区
    • （文件区是离散分配，交换区是连续分配）
• 适用范围：不同进程之间。

连续分配管理

• 概念：为一个用户进程分配连续的空间。
• 分类：
  • 单一连续分配
  • 固定分区分配
  • 动态分区分配

单一连续分配

• 描述：此方式下内存分为用户区和系统区。系统区通常在低地址，用户区中只能有一道程序。
• 优点：简单、无外部碎片、无须内存保护
• 缺点：只能单用户和单任务；有内部碎片；存储器利用率低

固定分区分配

固定分区分配是最简单的多到程序存储器管理方式。

• 描述：将用户空间分为若干固定大小的区域，每个分区装一个进程。如果有空闲分区，就从外存的后备队列选择一个作业装入这个分区。
• 分区的划分：
  • 分区大小相等：缺乏灵活性。
  • 分区大小不等：需要建立分区使用表，按照大小排队。如下图所示。
• 缺点：
  • 如果程序太大，可能无法放入任何一个分区。需要采用覆盖技术。
  • 如果程序小于固定分区大小，又必须占用一个完整内存分区，就会浪费空间，产生所谓的内存内部碎片。存储空间利用率低。

动态分区分配（可变分区分配）

• 描述：根据进程的需要按需分配内存，并且使得分区大小适合进程的需要。可见分区的大小和数目是可以改变的。
• 缺点：随着时间推移，产生越来越多小的内存分块无法被使用，这就是外部碎片。解决办法是操作系统定时对内存进行整理，通过紧凑技术来实现。
• 硬件：需要动态重定位寄存器的支持。
• 动态分配算法：内存中有多个足够大的空闲块时，操作系统该如何选取。
  • 首次适应算法First Fit：
    • 描述：空闲分区按照地址递增顺序链接，找到满足要求的第一个空闲空间。
    • 特点：简单，快速。会增加绕过小分区的开销。
  • 邻近适应算法Next Fit（循环首次适应）：
    • 描述：从上次查找结束的位置开始查找。
    • 特点：通常在尾部有碎片，比首次适应算法差。
  • 最佳适应算法Best Fit：
    • 描述：空闲分区按照容量递增连接。查找满足要求且最小的空间。
    • 特点：性能很差，产生最多外部碎片。局部最优解不等于全局最优解。
  • 最坏适应算法Worst Fit：
    • 描述：查找满足要求且最大的空间。
    • 特点：性能很差，导致没有大内存可以用。
• 内存回收的四种情况：回收后相邻则合并
  • 回收区域的后面有一个空闲分区：合并求和。
  • 回收区域前面有一个空闲分区：合并求和。
  • 回收区域的前后都有空闲分区：合并分区，总空闲个数-1.
  • 回收区域前后都没有空闲分区：插入一个表项，总空闲个数+1

非连续分配

连续分配无法解决一个程序过大时无法装入内存的问题，例如固定分区分配会产生内部碎片，动态分区分配会产生外部碎片，于是就引入了非连续分配。

我们可以根据分区的大小是否固定，将非连续分配分为，其中分页存储管理可以分为：基本分页、请求分页：

• 分页存储管理
• 分段存储管理

基本分页存储

分页的基本概念

• 分页思想：将内存划分为多个大小相等且固定的块，作为主存的基本单位。
  • 形式上，有点像固定分区分配。不会产生外部碎片。
  • 尽管会产生内部碎片，但是这种碎片相对进程来说是很小的。
• 分页存储中的基本概念：
  • 页面和页面大小：
    • 页：进程中的块（逻辑）
    • 页框/页帧：内存中的块（物理）
    • 块：外存中的块。
  • 页面的大小应该是2的整数幂，应该适中。太小会导致页面数太多，占用大量内存；太大会导致页内碎片变多。
  • 地址结构：20位页号 + 12位偏移
    • 12位偏移量：说明每个页大小4KB。
    • 20位页号：最多允许1M个页面。
  • 页表：每个进程都有一张页表。负责从逻辑地址->物理地址映射。页表一般存放到内存中。

注意：页表项和地址结构的区别！

地址结构 = 页号 + 页内偏移
页表项 = 页号 + 块号（就是个映射关系）

基本的地址变换机构

• 作用：将逻辑地址 --> 物理地址
• 页表寄存器：存放页表起始地址F + 页表长度M（进程被调度的时候从PCB获取）
• 算法步骤：页面大小是L
  • 计算页号P=A/L，页内偏移量W=A%L
  • 如果P >= M，越界终端。
  • P对应的页表地址 = 页表起始地址F + 页号P × 页表项长度，取出这个页表项的内容b，这个b就是物理块号。
  • 物理地址E = b × L + W

举个例子：A = 2500逻辑地址，L=1KB，物理块号=8

P = 2500 / 1KB = 2
W = 2500 % 1024 = 452
E = 8 x 1KB + 452 = 8644

分页访存的问题：

1. 每次访存需要先访问页表，然后访问内存。需要逻辑地址到物理地址的转换，这个转换的速度必须足够快，否则会降低访存速度。
2. 每个进程都有一个页表，页表不能太大，否则会影响内存利用率。

引入快表的地址变换机构

引入快表主要是解决页表访问速度的问题

• 快表：具有并行查找能力的高速缓冲存储器，也叫TLB。
• 算法步骤：
  • 逻辑地址-->页号-->遍历TLB查找是否有这个页号
  • 如果有：直接取出页框号，拼接加上页内偏移量形成物理地址。
  • 如果没有：访问主存的页表，读出页表项后存入快表，将信息存入快表。如果快表满了，会使用淘汰策略淘汰一个旧的页表项

两级页表

引入二级页表主要是解决页表大小的问题。

1. 页表必须连续存放，页表很大时候需要占用很大的页框。
2. 根据局部性原理，没必要让整个页表都常驻内存。

两级页表的原理、逻辑地址结构

假设32位地址，页表项4B，页面大小4KB，页内地址12位。
那么进程最多有2的20次方个页面，每个页面最多存放4KB/4B = 1024个页表项。

分组思想，将1M个页表以1024分组，形成1024组页表，每一组内部有1024个页表。

• 我们为这1024组页表建立一个目录页表，也叫页目录表，只需要1024个位置即可。

这样的话，逻辑地址 = 10位一级页号 + 10位二级页号 + 12位的页内偏移量

如何实现地址转换

1. 将逻辑地址拆分为三个部分。
2. 从PCB读出页目录表的起始位置，查询二级页表的位置。
3. 根据二级页表查表，加上偏移量，找到最终的内存块号。

解决局部性原理问题

页目录项设置一个标志位，表示是否在内存中。如果想访问的不在就发生缺页中断（内中断）。

注意事项

1. 各级页表大小不能超过一个页面。如果一共有40位，最终要建立三级页表。
   
2. 代价：次数更多的访存。

基本分段存储

• 分页和分段：分页更多是从计算机角度区考虑设计，目的是来提高内存的利用率，对用户是完全透明的。分段的提出则考虑了用户和程序员。
• 分段后的地址：段号 + 段内偏移。分段中，段号和段内偏移需要用户自己提供，这个工作在高级语言中由编译器完成。
• 段表：逻辑空间和内存之间的映射表。段表的内容为段号、段长、本段的起始地址。
• 分段的算法步骤：
  1. 逻辑地址中拆分出段号S和段内偏移量W。
  2. 如果S>=W就会产生越界中断。
  3. 段表项地址= 段表起始地址F + 段号S x 段表项长度
  4. 取出段表项的段长C，如果W>=C，越界中断。
  5. 物理地址E = 段表项中该段的基础地址b + W

段式管理因为每个段的大小都是不固定的，无法直接通过一个逻辑地址算出物理地址。所以必须显式给出（段号，段内偏移量），因此分段管理的空间是二维的。

段页式管理

• 描述：系统给每个进程建立一张段表，每个段自己有一张页表。
• 逻辑地址： 段号 + 页号 + 页内偏移量
• 段表项内容：段号 + 页表长度 + 页表起始地址
• 页表项内容：页号 + 块号
• 段表寄存器：给出作业的段表起始地址和段表长度。
• 地址变换算法：三次访存。地址也是二维的。
  1. 从段表查到页表起始地址。
  2. 从页表查找页帧号，形成物理地址。