• 分页是系统视角的内存管理方案(系统为了充分利用内存，不产生外碎片，不需要连续地址空间而采取的方案)
• 分段是用户视角的内存管理方案(比如我们看到的pc、虚拟机栈、堆等，他们之间无先后次序可言)
• 实际的OS中是二者相结合，系统和用户看到各自想看到的东西。

1、内存管理背景

• 基本硬件

  • 程序必须被装入内存才能执行
  • cpu可以直接访问的存储器只有主存和寄存器
  • cpu内置寄存器通常可以在一个(或少于一个)的cpu时钟周期内完成访问
  • 完成主存访问可能需要多个cpu时钟周期
  • 为了协调这种速度差异，再主存和cpu之间增加了高速缓存
    (cache)
  • 内存保护，即确保操作系统内核不被用户进程访问以及进程之间不相互干扰，这种保护可以通过硬件来实现。一个可能的方案是保证每个进程有独立的内存空间，即确定用户进程可以访问的合法地址范围，并确保用户只能访问其合法地址。可以通过两个寄存器来实现，即基址寄存器(base)和界限寄存器(limit)。cpu在执行指令时，需要进行地址合法性验证(总结来说，即cpu硬件将用户模式所产生的每一个地址，和寄存器的地址进行比较，合法的地址应该base<= user_add<base+limit，否则进入操作系统内核，作为寻址错误处理)。

• 地址绑定

  • 指令和数据需要绑定到内存地址，通常有三个不同阶段进行绑定
    • 编译时期(如果在编译时就知道进程在内存中的驻留地址，可以生成绝对代码，如果开始位置改变了，则需要重新编译代码。)
    • 加载时期(存储位置在编译时期未知，则必须生成可重定位代码，这样地址绑定就延迟到加载时期进行)
    • 执行时期(如果进程执行时可以在内存移动，则地址绑定可以延迟到运行时，这种方案需要特定硬件对地址映射的支持，如基址寄存器和界限寄存器，目前绝大多数OS采用这种方式)

• 逻辑地址和物理地址

  • 通常称CPU产生的地址为逻辑地址，是进程内的相对地址(也称虚拟地址、相对地址、程序地址)。
  • 而内存单元所看到的地址称为物理地址，如所有的内存需要按字或者字节统一编址，这个编号就是物理地址，也叫绝对地址、实地址。
  • 编译和加载时期的地址绑定生成相同的逻辑地址和物理地址，此时重定位是静态的；但执行时的地址绑定导致不同的逻辑地址和物理地址，此时的重定位称为动态重定位。由程序所生成的所有逻辑地址的集合称为逻辑地址空间，与这些逻辑地址所对应的所有物理地址的集合称为物理地址空间。
  • 逻辑地址空间绑定到物理地址空间至关重要，是正确进行内存管理的中心。
  • 执行时期，从虚拟地址到物理地址的映射是由一个硬件设备来完成的，该硬件称为内存管理单元(MMU)，它是CPU用来管理内存的控制路线。一个简单的例子就是，在逻辑地址和物理地址之间用MMU进行处理(即将逻辑地址加上对应的重定位地址，这里的重定位地址类似于基址寄存器的值)。

• 迄今为止，我们讨论的是一个进程的所有数据和代码都在内存中的情况。为了更好的内存空间使用率，可以使用动态加载。

• 我们可以这样认为，动态加载是按需要去外存加载数据或者代码到内存(所以它可以由程序员自己完成)，动态链接是按需要去别的进程的内存空间加载(所以它需要OS支持)。

• 动态加载

  • 只有程序被使用时才会加载到内存，它不需要操作系统的特别支持，而是通过程序设计来实现。OS可以通过提供子程序库来实现动态加载，如Windows的动态链接库(dll)。比如对各种库文件的链接被推迟到执行时期。这一技术通常用于系统库。它可减少磁盘空间和内存空间，且需要动态加载技术的支持。具体来说，程序代码中，每个库程序的引用都有一个存根(即一小段代码)，用来定位适当的内存驻留库程序，当执行存根时，首先检查所需子程序是否在内存，如不在，就将程序调入内存，并将子程序的地址来替换自己，再开始执行子程序。

• 动态链接

  • 与动态加载不同，动态链接则需要OS的帮助，因为内存中进程是彼此保护的，只有OS才可能检查所需子程序是否在其他进程的内存空间。

2、 连续内存分配

• 内存通常分为两部分，一部分用于驻留操作系统，一部分用于保存用户进程。OS既可位于内存低端，也可位于内存高端。这主要是由中断向量的位置来决定的，由于中断向量通常保存在内存低端，因此OS通常也驻留在内存低端(我的理解是一般中断就是中断用户进程，切换到OS的内核模式，进行一些只能由内核模式才能运行的命令，或者进行进程切换的工作，所以都在内存低端便于寻址，节省耗费)。

• 连续内存分配是内存管理的一种常见方法，即为一个用户进程分配一个连续的内存空间。他是早期的内存分配方式，适用于内存较少的系统。分为三类：

  • 单一连续分配(适用于单用户、单任务)
  • 固定分区分配(内存分成大小相同的块)
  • 可变分区分配
    • 不同大小的分区(Hole)在整个内存中，当一个进程到来的时候，他将从一个足够容纳他的分区中分配内存，如c中的malloc()。此时OS包含以下信息：a)已分配的分区；b)空闲分区。具体实现的数据结构可以是线性表或者链表。
    • 它是动态存储分配问题的一种情况
      • 其存储分配算法常用的有三种:
        • 1)首次适应(First-fit)；
        • 2)最佳适应(Best-fit)；
        • 3)最差适应(Worst fit，即搜索整个列表，寻找最大的分区进行分配，对应到数据结构上，如链表实现，则是在对空闲分区搜索时，按从大到小排序)。
      • 其内存回收存在四种情况：即回收内存块的前后是否存在空闲块(有则合并)。
      • 随着进程频繁的装入和移出内存，空闲内存空间可能被分割成小的片段。
        • 1、当整个可用内存空间可以用来满足一个请求，但它不是连续的。所以无法分配，就出现了外碎片问题。Ff和Bf都存在这个问题。最坏的情况下，每两个进程之间都有空闲块被浪费。解决外碎片问题一种是可以用内存移动(最简单的做法就是把使用过的移动到一端，空闲的移动到另一端，这样的开销很大，可以有改进，尽量让移动内容小)，另一种是允许物理地址为非连续，也就是分页和分段。
        • 2、在固定分区分配模式下，给进程分配的内存比进程申请的内存大一点，这两者的差值是其他进程无法利用的，这就是内碎片问题。
        • 3、无论是外碎片还是内碎片，都会导致内存利用率低下。
        • 4、外碎片指的是还没有被分配出去(不属于任何进程)，内碎片是已经被分配了，但是分配的那部分没有完全被利用。

  3、 分页内存管理

• 非连续的内存管理方案有多种，即分页、分段和段页式。现在绝大多数操作系统使用分页内存管理方案。

• 分页(Paging)，其内存管理方案允许进程的物理地址空间可能不连续。即只要有可用的物理内存，就可以分配给进程。

  • 基本方法有：
    • 将物理内存分成大小固定的块，也成为帧(frame)，也可以简称为内存块。
    • 帧：又称为页框。
    • 把逻辑地址的内存也分为同样大小的块，称为页。
    • 帧和页的大小是由硬件来决定的，通常为2的幂，根据计算机结构的不同，大小不同。早期为512字节至8K，现在为4K-64K。系统保留所有空闲帧的记录，当运行一个由n个页的进程时，需要找到n个空闲帧来装入程序。系统将建立一张页表，记录页与帧之间的映射关系。进程运行时，通过查找页表，实现逻辑地址和物理地址的转换。
    • 分页在传统中是由硬件来处理的。最新的设计是通过将硬件和操作系统相配合来实现的。采用分页技术不会产生外碎片，因为每个帧都可以分配给进程。但是分页有内碎片(也叫页内碎片)，进程请求的内存可能不是页的整数倍，因此最后一帧中可能存在多余的内存空间。
    • 在分页管理方案中，逻辑地址分为两部分，页号(p)和页偏移(d)。这里的逻辑地址我们又称为线性地址。(linear address)，它有别于分段中的二维地址。
      • 页号，包含每个页在逻辑内存中的基址，用来作为页表的索引。
      • 页偏移，同基址相结合，用来确定送入内存设备的物理内存地址。
    • 利用分页技术将逻辑地址转换为物理地址的过程大概是，以逻辑地址中的页号p为索引，检索页表，得到该页在物理内存中的帧号f，最后将帧号f与页偏移d相结合，形成物理地址。
    • 页表的保存有硬件实现：页表较小时，可放入专用寄存器(直接在Register里存放页表)。页表较大时，需要保存在内存中，并将页表的基址寄存器指向页表，页表限长寄存器表明页表的长度。在这种机制中，每一次数据指令的存取，都需要两次内存访问，一次通过PTBR(PTBR中保存的是页表的地址)访问页表，一次访问数据或指令(过程就是先通过PTBR_Page table base register访问页表，再通过页表找到页和帧之间的对应关系，然后由帧加上PTLR_Page table limited register中的值就可以访问物理地址中的数据了)。这样内存访问的速度减半。在绝大多数情况下，这种延迟是无法忍受的。针对这种问题的标准解决方案是，采用小但专用且快速的缓冲硬件，这种缓冲称为转换表缓冲器(TLB)或者联想寄存器或者快表（我的理解是，其实和缓存一样，就是在PTBR和页表之间加一个缓冲区，把部分页表中的数据放到缓冲区，需要的时候先读缓冲区，缓冲区没有就在去读页表，并更新一下缓冲区，把部分内容换出去，把最新用过的内容换进来）。
    • TLB由键和值两部分组成(实现并行查找)，这种查找方式比较快，但硬件比较昂贵。所以通常TLB的条目数并不多，通常在64-1024之间。
    • TLB一般只包含页表的部分条目，当CPU产生逻辑地址后，其页号提交给TLB,如果在TLB中找到页号，称为TLB命中，直接得到帧号。如果页号不在TLB中，称为TLB失效，则需要访问页表得到帧号。同时将页号和帧号增加到TLB中。页号在TLB中被查找到的百分比称为命中率，这个比率与TLB的大小有关。
    • 为了衡量TLB的性能，引入了有效访问时间(EAT)这一概念，假设查找TLB的时间为a，进行一次内存存取的时间为b，命中率为λ，则有效访问时间为：
      • EAT = λ(a+b) +(1-λ)(a+2b)
  • 分页环境中，内存保护的简单方法是把页号和页表限长寄存器的值相比较。更加细致的方法则是通过与每个帧相关联的保护位来实现。如用一个位来定义一个页是否只读、读写、只执行等。还有一个位通常与页表中的每一个条目相关联，称为有效-无效位。
    • 有效位：相关的页在进程的逻辑地址空间，并且是一个合法的页。
    • 无效位：页不在进程的逻辑地址空间。
    • 通过有效无效位可以捕捉到非法地址，os可以通过对该位的设置来允许或者不允许对该页的访问。
  • 分页的优点是：
    • 可共享公共代码，如果代码是可重入代码(或称为纯代码)，则可以在进程间共享。

4、 页表结构

• 绝大多数现代操作系统支持大逻辑地址空间，即2^32~264，一般一页的大小位4KB，即2^{12个字节。在一个32位的OS中，一个页表最多可以包含2}32/2¹²⁼²20个表项，也就是1MB(2^{10=1024=1KB)。如果一个表项4字节，那么每个进程需要4MB的物理空间来存放这些表项。也就是2}22个字节，也就是1024个连续页面来存储页表本身。1024个连续页面，即2^{10个页面，一页为4KB，2}12个字节，即需要2^22字节，等价于前面的4MB。一个页表，我的理解就是通过逻辑地址里的p1，查阅页表，可以得到p1对应的实际地址的起始位置，再加上逻辑地址中的偏移量d，即可确认最终的物理地址。

• 光存放页表就需要连续的1024个页面，显然是不可能的。可以想办法，但是存放页表的大小仍旧不变，只是和前面内存分配一样，可以将空间变得不连续而已。

• 要解决上述页表占用连续空间的问题，可以采用不同的页表结构。

  • 层次页表(低于32位常用的方案)

    • 其思想是将页表划分为更小的部分，如两级页表就是将页表再分页。
    • 例如在32位的逻辑地址空间中，将逻辑地址中的页号再划分，p1(外页表索引),p2(外页表页偏移),d。二级表结构并不能解决需要使用4MB内存来存放页表的问题。只是我们增加了一个页面来存放表目录，使得我们不需要将页表保存在连续的4MB内存块中。
    • 在64位逻辑地址空间中，如果还用2级划分，那么p1=2^42，p2=210，d=2^12，此时，外页表需要1GB的连续页面来表示。是不是太夸张了？所以有了三级、四级页表划分的方案，即将p1进一步划分。实际上呢，对于64位的OS，采用层次结构来表示并不适合。一般用哈希页表。

  • 哈希页表(高于32位的方案)

    • 哈希页表为操作系统分页内存管理方案的页表结构中的一种，是处理超过32位地址空间的一种常用方法，并以虚拟页作为哈希值。

  • 反向页表(也就是用物理内存地址去映射虚拟地址（逻辑地址）。为了让所有进程维护一张页表)

    • 它以帧号为index，页号地址为value，每次访问将value和逻辑地址比对，这样做的原因就是大大节省了内存的开销，全局只需要一张页表。但是当物理内存特别大的时候，这个表也就很大了，访问一个地址可能需要遍历整个表（因为是按照物理地址建立的，所以要挨个访问、判断），那么有什么方法是可以缓减访问速度的压力吗，那就是基于hash表的访问。类比hash表中的直接定位。这里肯定会有hash冲突，处理冲突的过程类似hashTable中，对相同hash值的对象用链表串起来。
    • 反向页表由于无法把一个物理页和多个虚拟页对应起来，所以在进行内存共享时比较困难。一般内存共享是通过多个虚拟页映射到同一物理地址来实现的。

5、 分段和段页式内存管理

• 采用分页内存管理的问题：用户视角的内存和实际物理内存的分离。也就是用户视角的内存和实际物理内存不一样。用户通常愿意将内存看成是一组不同长度的段的集合，段是逻辑上有意义的单位，而且段与段之间没有一定的顺序。
• 分段(segmentation)
  • 支持用户观点的内存观管理机制。
  • 逻辑地址空间是由一组段组成的，每个段都有名称和长度。地址指明了段名称和段内偏移。但实际上是由段编号表示段名称，逻辑地址由一个有序对组成：<段号，偏移>。这称为二维地址。
  • 在编译用户程序时，编译器会自动根据输入程序来构造段。如一个c语言编译器可能会创建如下段：代码、全局变量、堆、栈、标准的库函数等等。
• 段页式原理
  • 先将用户程序分为若干个段，并为每个段赋予一个段号，再把每个段分成若干个页。逻辑地址即为：<段号，页号，页内偏移>。
  • 从用户视角看，程序被划分成了逻辑上有意义的段；从系统视角看，物理内存被划分成了固定大小的帧，结合了两者的优点。它存在页内碎片，但没有外碎片问题。

内存扩充

• 当逻辑地址空间大于物理内存空间时，前面的方法都不能满足请求。这里的内存扩充指的是在内存不变的情况下，提高利用率，常用的方法有紧缩(碎片整理)、覆盖、交换和虚拟内存。
• 覆盖
• 交换