操作系统概念_第八章_内存管理

• 概述
  • 基本硬件
    • CPU-高速缓存-内存
    • 基地址-界限地址寄存器
  • 地址绑定
  • 逻辑地址空间和物理地址空间
  • 动态加载
  • 动态链接与共享库
  • 关于动态加载和动态链接
• 交换(略)
• 连续内存分配(略)
  • 内存映射和保护
  • 内存分配
  • 碎片
• 分页
  • 基本方法
    • 实例
    • 题外话
  • 硬件支持
  • （内存）保护
  • 共享页
• 页表结构
  • 层次页表（向前映射表）
  • 哈希页表
  • 反向页表
• 分段
  • 基本方法
  • 硬件
• 实例：Intel Pentium
• 实例：Linux

概述

第五章将CPU调度，CPU调度提高了CPU利用率和系统对用户的响应速度，而这一操作，是将非调度进程保存到内存中实现的，因此需要实现共享内存。

多进程保存到内存和实现共享内存之间有联系吗？上述话来自于课本，但没想明白有什么因果联系…

要管理内存，自然也需要很多策略，算法，本章将从硬件和软件两个层面描述内存的组织方法和管理方法。

---

基本硬件

基本硬件主要解决了访存速度的提高和用户进程的保护问题

CPU-高速缓存-内存

首先要知道的一个前提是，CPU只能从内存和处理器内的寄存器中读取指令或数据，如果数据不在内存或缓存中，那么CPU必须先通过指令将数据从外存中转移到内存中。

为了提高CPU访存速度，通常在CPU-内存之间增加高速缓存，即CPU-高速缓存-内存，这样就保证了CPU访问物理内存的相对速度，提高CPU的利用率。

基地址-界限地址寄存器

除了要保证CPU访存速度外，还需要保证操作系统不被用户进程访问以及一个用户进程不被其他用户进程访问，这种保护可以通过硬件来实现，一个简单的方案就是：使用基地址寄存器保存用户进程合法的最小物理地址，使用界限地址寄存器保存用户进程的地址的范围大小

通过这种方式，CPU硬件对用户进程产生的每一物理地址与寄存器地址进行比较来完成。这种方案允许操作系统修改寄存器的值，而不允许用户进程的修改。过程示意图如下：

因为操作系统在内核模式下，可以无限制的访问任意内存，所以操作系统能够完成将用户进程装入内存，在进程出错时输出进程，以及修改调用进程的参数等操作。

地址绑定

程序以二进制形式存放在硬盘上，进程执行时会装入内存，进程执行时，系统会访问内存中相关的指令和数据。最后，进程终止，相对于的地址空间会被释放。

而在进程装入内存时，指令和数据应该装入内存的哪一块地址，应该如何分配，也就是地址绑定（Address binding）的方式。

虽然计算机的地址空间从0开始，但进程的地址空间是可以放在任意位置，而不必从0开始。

源程序中的地址通常用符号表示（如count）（也就是变量的形式？？），编译器通常将这些符号绑定在可重定位的地址。链接程序 / 加载程序则再将可重定位的地址绑定成绝对地址，每一次绑定都可以看成是一个地址空间到另一个地址空间的映射

地址绑定通常在以下几个阶段发生：

• 编译时(compile time)，如果编译时知道进程将要驻留在内存中的绝对地址，那么就可以生成绝对代码（absolute code），但这种方式一旦开始地址发生变化，就需要重新编译。
• 加载时(load time)，如果编译时不清楚绝对地址，那么编译器就必须生成可重定位代码(relocatable code)，这样地址绑定就会延迟到加载时进行，这样开始地址如果变化，只需要在加载时引入改变值即可
• 执行时(execution time)，如果一个进程在执行时可以从一个内存段移动到另一个内存段，那么绑定就必须发生在执行时。

执行时完成地址绑定是绝大多数通用计算机系统采用的方法。

逻辑地址空间和物理地址空间

逻辑地址(logical address)：CPU生成的地址称为逻辑地址

物理地址(physical address)：加载到内存地址寄存器中的地址称为物理地址。

逻辑地址空间(logical address space)：由程序生成的所有逻辑地址的集合。

物理地址空间(physical address space)：由这些逻辑地址所有相对应的物理地址的集合。

在《操作系统概念》一书中，对逻辑地址和虚拟地址(virtual address)不做区分，两者含义相同。

在编译、加载、执行时都会产生虚拟地址和物理地址，但编译和加载时会产生相同的虚拟地址和物理地址，而在执行时，根据绑定方案，则会产生不同的虚拟地址和物理地址。

理所当然的，执行时的虚拟地址空间和物理地址空间也是不同的。

内存管理单元：当虚拟地址和物理地址不同时，需要通过一个映射关系来完成两者的转换，完成这个操作的设备称为内存管理单元(memory-management unit，MMU)。

为了完成这种映射，有很多种方式，一个简单的基于基地址寄存器的推广的方式是：所有用户进程生成的地址都要经过基地址寄存器，经过加操作后，生成物理地址。

这里将基地址寄存器称为重定位寄存器(relocation register)，其他的映射方案将在 8.3-8.7 节讨论

动态加载

之前讨论的进程都是完整的放入内存中的，但进程大小受限于物理内存大小的限制，一个解决方案是采用动态加载(dynamic loading)，这样一个子程序只有在执行时才加载，在这之前均会以重定位的形式存储在外存上。

当主程序执行时，当一个子程序调用另一个子程序时，先检查该子程序是否已加载，如果没有加载则动态加载。

动态加载的使用不到的子程序绝对不会被加载，节省了内存空间。

动态链接与共享库

操作系统或者用户本身会写一些库，用于复用，而链接(linking)就是将用户自己的程序和这些库链接起来，这样程序就能够通过这些库来实现自己想要的功能（类似于编程中的import）。

静态链接和动态链接中静态和动态的概念有些类似于是否使用动态加载：

• 静态链接(static linking)：指在加载时将库与用户程序直接合并为一个二进制可执行程序。
• 动态链接(dynamic linking)：用户的程序中只保存一个存根(stub) / 引用，在使用到库的时候，通过这个引用来查找系统中相应的库装入内存。

两者各有优点，具体可以看一下百科中对静态链接和动态链接的比对

静态链接一个明显的缺点就是每一个进程都需要一份库的备份，占用硬盘空间，而动态链接则很明显没有这个缺点

关于动态加载和动态链接

动态加载不需要操作系统提供特殊的支持，主要通过程序员来完成，而动态链接则需要操作系统进行判断，如检查进程是否已经加载，或者是否允许用户进程访问相关内存地址。

交换(略)

连续内存分配(略)

内存映射和保护

内存分配

• 可变分区
• 不可变分区

动态存储空间：

• 首次适应
• 最佳适应
• 最差使用

碎片

• 紧缩

分页

分页是另一种内存管理方案，它允许进程的物理地址空间是非连续的。

该方案将页面作为内存空间的最小分配单位，一个程序的一个页面可以存放在任意一个物理页面里。

基本方法

该方案将:

• 物理内存分为固定大小的块，称为帧(frame)
• 将逻辑内存也分为同样大小的块，称为页(page)

外存此时也分为同样大小的各个块。

执行进程时，进程以页面为单位加载到可用的帧中(可以不连续)，CPU在生成地址时，生成相应的页号(p)和页偏移(d)。

同时，每个进程都拥有了一个页表，页号是页表的索引，页表能够通过索引找到每页所在的物理内存的基地址，而基地址与页偏移的组合代表了真正的物理地址。

可以简单理解成页表就是一个页号到物理内存基地址的映射函数。

页 / 帧大小是由硬件决定的，为了方便查找，一般都定位2的幂。其大小从512B~16MB不等。其地址映射与cache地址映射比较类似，如逻辑地址空间大小为 2m $2^m$，页大小为 2n $2^n$，那么CPU给出的逻辑地址的高 m−n $m-n$ 位为页号p，低 n $n$位为页偏移d：

采用分页技术不会产生外部碎片，每个帧都可以分配给需要它的进程，但是分页有内部碎片。如果进程要求的内存不是页的整数倍，那么最后一个帧就可能用不完。

可以比较容易的想到如果页比较小的话，内部碎片产生的可能性以及产生的大小就会更小，但页表的每一项也同样是一种开销，这种开销随着页的增大而减小，另外在IO传输的时候页更大也意味着传输速度更快(详情见12章)。

当系统执行进程时，将检查进程占用内存的大小（按页/帧），如果内存中能够分配出足够的页/帧，那么就可以分配。

下面通过两个实例说明地址如何映射以及内部碎片的产生。

实例

如上图，页大小为4B，物理内存为32B(8页)，当进程占用了16B时（左表），对应中间的页表，能够换算出逻辑地址真实的物理地址：

• f(0) = 5*4+0 = 20
• f(5) = 6*4+1 = 25
• f(10) = 1*4 + 2 = 6
• f(15) = 2*4 + 3 = 11
  …

注意地址都是从0开始的。
这是另一种动态重定位，分页类似于一组重定位地址寄存器，实现地址的换算。

另外现在假设页大小为2048B，而一个进程需要72776B的内存，这样就会需要35页加上1086B的额外空间，而1086B必须分配一整个页，这个页剩下的部分就产生了内部碎片。（大小为2048-1086=962B）

在最坏的情况，可能只会有1B需要单独分配页，那么这个页剩下的空间均为内部碎片。

题外话

一般右键一个包含了很多文件的文件夹查看属性时会看到空间属性有两个：大小和占用空间，占用空间会比大小大，这是因为硬盘也是采用这种分页的方式为每个文件分配空间，这样每个文件也都有可能产生内部碎片（硬盘空间意义上的内部碎片）

硬件支持

每个操作系统都有自己的办法来保存页表，绝大多数进程为每个进程分配一个页表。页表的指针与其他寄存器的值（如指令计数器）一起存入进程控制块PCB中，当调度程序启动进程时，它必须首先装入用户寄存器，并根据所保存的页表来定义正确的硬件页表值。

页表的硬件实现有多种方法。

方法一：
最简单的方法是将页表作为一组专用寄存器实现。寄存器使用高速逻辑电路，能够有效进行页表的转换。

方法二：
第一条方法只适合于小页表（如256个条目），当页表很大时，就需要将页表存入内存中，并将页表基寄存器（page-table base register）指向各个页表。但这种情况下访问一个字节就需要访问两次内存（一次用于页表条目，一次用于实际字节），会导致访存速度减半，这是无法忍受的。

因此如果采用方法二，需要增加一个小且快速的硬件缓冲，称为转换表缓冲区（translation look-side buffer，TLB），类似于高速缓冲cache，当查表时，会先和缓冲区的所有值进行比对，如果找到则直接使用，如果找不到才会到内存中去找。

TLB的使用方式：TLB只包含页表中的一小部分条目，当CPU产生逻辑地址后，将页号交给TLB，如果找到页号，那么也就得到了帧号，并可以直接访问字节所在的物理地址。

由于缓冲区速度很快，通常增加的时间开销不超过10%。

如果页码不在TLB中（称为TLB失效），那么就需要重新访问内存中的页表（两次访存），同时需要通过一定的替换策略来让内存中的页表替换到缓冲区中。

有的TLB在每个TLB条目中还保存地址空间标识码（address-space identifier，ASID）。它有以下作用：

• ASID可用来唯一标识进程，并为进程提供地址空间保护。当TLB试图解析虚拟页号时，它确保当前运行进程的ASID与虚拟页相关的ASID相匹配。如果不匹配，那么就作为TLB失效。
• 除了提供地址空间保护外，ASID 允许TLB同时包含多个进程的条目。如果TLB不支持独立的ASID，每次选择一个页表时（例如，上下文切换时），TLB就必须被冲刷（flushed）或删除，以确保下一个进程不会使用错误的地址转换。

替换策略也就是各类算法，详情可以看一下这篇博客
另外注意，有的TLB允许一些条目固定（通常是内核代码等），永远不会被替换。

另外与Catch类似的，TLB也有命中率和有效访问内存时间的计算。

假如查找TLB需要20ns，访问内存需要100ns，如果访问位于TLB中的页号，那么采用内存映射访问需要120ns。如果不能在TLB中找到（20ns），那么必须先访问位于内存中的页表得到帧号（100ns），并进而访问内存中所需字节（100ns），这总共需要220ns。

假设命中率为80%：
有效内存访问时间 =0.80∗120+0.2∗220=140（ns）
对于这种情况，现在内存访问速度要慢40%

如果命中率为98%，那么
有效内存访问时间 =0.98∗120+0.02∗220=122(ns)
由于提高了命中率(Hit ratio)，内存访问时间只慢了22%

（内存）保护

在分页环境下，内存保护是通过与每个帧相关联的保护位来实现的，这些保护位一般保存在页表中。

可以用一个位(bit)来定义一个页的只读的还是可写的。

每次地址引用都要通过页表查找正确的帧，而在查找过程中(计算物理地址的过程中)，可以通过检查保护位来验证有没有对只读页进行写操作。

这种方式可以很容易的被扩展，以提供更细致的保护。

另外在页表中的每一个条目都关联了另一个位来表示该页是否有效：

• 有效位表示相关的页在进程的逻辑地址空间中，是合法（有效）的。
• 无效位表示不在。

通过有效-无效位能够捕捉到非法地址，并且操作系统可以通过对该位的设置来控制是否允许都某页进行访问。详情看P254

共享页

分页的一个优点是可以共享公共代码，如下图：

如果代码是可重用代码（reentrant code，或称为纯代码），则可以共享。

可重入代码是不能自我修改的代码，它不会在执行期间改变，因此两个或更多的进程可以在相同的时间执行相同的代码。

页表结构

现代计算机系统支持大逻辑地址空间（2^32~2^64）,所以如何管理和组织页表，就需要一些额外的技术方法。

层次页表（向前映射表）

一个方法是适用n级分页算法，对页表再分页。
对页大小为4KB的32位系统来说，一个逻辑地址被分为20位的页码和12位的页偏移。建立2级分页后，该逻辑地址被分为两个十位的页码和12位的偏移。

其中p1是访问外部页表的索引，p2是访问外部页表的页偏移，由于这种地址转换由外向内，因此该方案称为向前映射表（forward-mapped page table）

但对于64位的操作系统，二级分页体系就不再使用，因为外部页表可能需要42位。这样就可以继续分级，得到三级分页，甚至四级分页。

因此对于64位系统，多级分页算法通常并不合适。

一个有效转换逻辑地址的内存访问的极限的层级是7级分页。(如64位ULtraSPARC体系结构)

哈希页表

哈希页表(hashed page table)比较适合处理超过32位的地址空间，其中哈希值为其虚拟页码。

哈希页表的每一条目都包含一个链表，每个链表有多个元素（这些元素的哈希值相同，所以查找和添加的时候要处理碰撞），每一个元素有三个域（属性）：

• 虚拟页码
• 所映射的帧号
• 指向下一个元素的指针

其工作模式如上图所示：

• 将虚拟页号和转换到哈希表中，并和相对应的链表中的每一个元素的第一个域（虚拟页码）比较。
  
  • 如果匹配，第二个域（帧号）就被用来形成物理地址
  • 如果不匹配，则通过第三个域（指针）找到下一个元素，直到找到匹配的元素。

群集页表比较适合64位的地址空间，其相关部分查阅课本P258

反向页表

之前提到的所有使用的页表，都是能通过页表找到所有的地址，这样就存在页表臃肿，这种问题在内存空闲的时候尤为突出。

因此一个方案就是使用反向页表（inverted page table），真正使用的帧才在反向页表中有一个条目。整个系统只有一张页表，对每个物理内存帧只有一个条目，条目包含对应逻辑内存页的地址，及进程号等。

主要的问题是内存共享有点麻烦。详情看一下P260.

分段

分页将用户视角的内存和实际物理内存分离，这在有些情况下（如少量页表仍需查表）可能是一个问题，这个时候可以采用分段的方式来解决。

基本方法

通过分段（segmentation）这一种内存管理方案，内存被看成由不同长度的段的集合，这种方式符合用户编写程序适合的视角。

通过分段方式，每一个单独段中，地址都是连续的。每个段都有名称，地址则指定了段名称和段内偏移。用户通过段名称和偏移量，可以指定一个地址。

回顾一下，在分页中，用户只指定一个地址，这个地址通过硬件分为页码和偏移，这一部分是用户无法看见的。

为了方便定义，段名通过段号来映射，即逻辑地址通过以下的有序对组成：
<segment-number , offset>

如一个C编译器，其在编译时会创建如下段：
代码
全局变量
堆（内存从堆中分配？）
每个线程采用的栈
标准的C库函数

硬件

从用户视角，现在可以方便的制定内存区域了，但实际上物理内存地址仍然是一维连续的序列。因此便要定义一个通过二维地址到一维地址的映射。

这个映射是通过段表（segment table）来实现的。段表的每个条目都有段基地址和段界限

• 段基地址：包含该段在内存中的开始地址
• 段界限：指定该段的长度

分段式管理同样是离散的视角，并通过从用户的视角考虑，让地址的表示更加清晰，但这种方式仍然无法避免内存碎片，所以可以通过在段内分页的方式优化分段
通过更改段表的结构，让每个进程的段表记录：子页表位置，页表的项数，偏移量等（可能不准确）

实例：Intel Pentium

Intel Pentium即采用段页式管理的方式。

实例：Linux

Linux采用适合32位和64位体系结构的三级分页方案