1、为什么要进行非连续内存分配
非连续内存管理具有以下的优势：使得一个程序的物理地址空间是非连续的，可以更好地利用和管理内存，减少内存碎片，允许共享代码与数据，支持动态加载和和动态链接。但是非连续内存管理的管理本身的开销比较大，需要建立虚拟地址和物理地址之间的转换(可以通过硬件或者软件方案来实现)。
2、两种硬件方案：分段和分页
2.1 分段
程序的虚拟的地址空间是连续的逻辑地址空间，通过分段，将程序中不同的部分进行隔离开来，分别放置到非连续的内存之中。通过一种映射机制建立连续的逻辑地址空间和非连续内存之间的映射关系。
分段的逻辑视图如下图所示。
2.1.1 硬件分段寻址方案
程序访问内存地址需要：一个2维的二元组(s, addr)，其中s表示短号，addr表示段内偏移。
如下所示，OS在硬件分段的过程中主要负责段表的建立工作，且操作系统建立段表之后，段机制才能够正常进行工作。
2.2 分页
和分段一样，分页机制也需要知道一个页号和页内的地址偏移。与分段机制不同的是，分页机制总，段的尺寸是固定的，因为页帧的大小是一定的。在分页机制中，需要划分物理内存值固定大小的帧，大小是2的幂；需要划分逻辑地址空间至相同大小的页，大小是2的幂；需要建立方案，转换逻辑地址为物理地址(pages to frames)。
2.2.1 页帧-frame
物理内存被分割成大小相等的帧，每一帧有 2 S 2^S 2S字节， S S S表示一个页帧的大小。一个内存物理地址是一个二元组，包括帧号f和帧内偏移o，物理地址= 2 S × f + o 2^S×f+o 2S×f+o。
2.2.2 页-page
一个程序的逻辑地址空间被划分为大小相同的页，一个逻辑地址是一个二元组，不包括页号p和页内偏移o，虚拟地址= 2 S × p + o 2^S×p+o 2S×p+o。
2.2.3页寻址机制
通过页的虚拟逻辑地址找到页表中对应的帧号，之后通过帧号的计算得到物理地址。其中，页表是由OS事先建立起来的。
2.2.4页寻址机制的注意事项
页映射到帧；页是连续的虚拟内存；帧是非连续的物理内存；不是所有的也都有对应的帧。
2.3 页表
为了有效地实现分页这种转换机制，需要用到页表。每个运行的程序都会有一个页表，属于程序的运行状态，会动态变化；PTBR为页表基址寄存器。下面介绍一个页表地址转换的实例：
首先逻辑地址中的地址有第4页0偏移量和第3页1023偏移量两个逻辑地址，需要通过页表来找到其分别对应的物理内存空间的地址。首先通过页表找到(4，0)的对应物理地址驻留位为0，表示此逻辑地址没有对应的物理地址；而(3,1023)对应的物理地址驻留位为1，说明其物理地址存在，从页表右侧读出物理地址的页帧号为4，物理地址的偏移量和逻辑地址相同都为1023，即可寻找到物理地址。
2.3.1 分页机制的性能问题
1）访问一个内存单元需要2次内存的访问，一次用于获取页表项，一次用于访问数据。
2) 页表可能非常大，一个64位的机器，若页表每页有1024字节，则一个页表需要的空间大小为： 264/210=254字节大小。
如何处理?
可以通过缓存(caching)来提升访问速度，通过间接(indirection)访问的方式来缓解页表占用空间过大问题。
2.3.1.1 TLB-Translation Look-aside Buffer
在CPU中的内存管理单元MMU中有cache缓冲区叫做TLB，其采用二叉树map来实现，能够实现快速查找的功能，但是其空间比较小，通常把经常访问的页表项放到TLB中去来提升访问速度。当CPU得到逻辑地址的值之后，首先根据逻辑地中的P值在TLB中进行查找，若在TLB中没有查找到，则再到内存中的页表之中进行查找，若物理页表中的驻留位为1，则将对应的页帧号取到TLB中，实现TLB的动态管理，并且在X86操作系统中，这个过程由CPU硬件来完成，不需要OS进行参与。
2.3.1.2 二级，多级列表
通过多级列表的方式来克服页表占据空间过大的问题。分成多级列表之后，逻辑地址也要跟着进行相应的改变，其中的page num需要细化为一级列表的page num，二级列表的page num，etc。一个二级页表的寻址过程如下图所示：
分级列表机制涉及到多次的内存访问，会造成额外的时间开销，但是可以将驻留位为0的页表项后续的空间省出来，从而节省空间的开销，是一种典型的以时间换空间的机制。
2.3.2 反向页表-inverted page table
十分大的页表空间使得前向映射页表变得十分繁琐(如5级页表)，若使页表不与逻辑地址空间建立关系，而是与物理地址空间建立关系，这便是反向页表的思想起源(逻辑地址空间增长速度快于物理地址空间增长速度)。
2.3.2.1 基于页寄存器(page Registers)的方案
基于page Registers的方案如下图所示：其中，页表的key值用来存放对应物理内存的页帧号，而页表的value值用来存放对应逻辑地址的页号，这样做使得由页号来查找页帧号变得不好处理。
2.3.2.2 基于关联内存(associated memory)的方案
2.3.2.2 基于哈希(hash)查找的方案
将上述寄存器或者关联存储器换成哈希表来进行处理，但哈希表存在value值冲突的情况，这时候需要给哈希表传进去一个PID(执行程序的ID号)来缓解哈希表寻找页帧号时候的冲突问题。
