【概述】
连续分配存储方式会形成许多碎片，虽然可通过紧凑的方法将许多碎片拼接成可用的大块空间，但须付出很大的开销
如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存空间，无须再进行紧凑操作
基于上述思想，产生了离散分配存储方式，根据离散分配存储方式在分配地址空间的基本单位的不太，可分为三类：
- 分页存储管理：将用户程序的地址分为若干固定大小的区域（页），再将内存空间划分为同样大小的若干区域，从而将用户程序的任一页放入任一块中
- 分段存储管理：将用户程序的地址空间划分为若干大小不同的段，每段定义成一组相对完整的信息。在分配时，以段为单位，这些段在内存中可以不相邻
- 段页式存储管理：分页与分段两种存储方式相结合的产物
【基本概念】
页面与物理块
分页存储管理将进程的逻辑地址空间划分为若干页，并将各页加以编号，例如：第 0 页，第 1 页等
相应的，也将内存的物理地址空间划分为若干块，也为他们加以编号，例如：0#块，1#块等
需要注意的是，逻辑划分的页大小=物理划分的块大小
在为进程分配内存时，以块为单位，将进程中的若干页分别装入到多个可不相邻的物理块中。
在分页系统中，若页面大小过大，那么会导致进程的最后一页经常装不满一块，从而形成了不可利用的页内碎片；若页面大小过小，那么虽然可以减少页面碎片，提高了利用率，但每个进程的页面数量较多，使得页表过长，反而大量占用内存。
因此，在页面大小应选择适中，且页面大小应为 $2$ 的幂，一般为 1KB~8KB
分页地址的地址结构
分页地址的结构包含两部分内容：前一部分为页号 P，后一部分为位偏移量(页内地址) W。
以下图为例，地址长度为 $32$ 位，$0$ 到 $11$ 位为页内地址，即每页大小为 $2^{12}=4K$，$12$ 到 $31$ 位为页号，即地址空间最多运行有 $2^{20}=1M$ 页
若给定一个逻辑地址空间中的地址为 $A$，页面大小为 $L$，则页号 $P$ 和页内地址 $W$ 可按下式求得：
其中，$INT$ 是整除函数
例如，某系统页面大小为 $1KB$，其逻辑地址为 $2170B$，那么有：
页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程能在内存中找到每个页面所对应的物理块，系统为每个进程创建了一张页面映像表，即页表
在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存中对应的物理块号，进程每次执行时，通过查找该表，即可找到每页在内存中的物理块号，简单来说，页表的作用就是实现从页号到物理块号的地址映射
【分页存储管理】
地址变换机构
作用
地址变换机构用于将用户地址空间中的逻辑地址转为内存空间中的物理地址
由于页内地址与物理地址是一一对应的，因此地址变换机构的任务实际上只是将逻辑地址中的页号转为内存中的物理块号，又因为页表的作用就是实现页号到块号的变换，因此，地址变化任务是借助于页表完成的
基本地址变换结构
系统中设置了一个页表寄存器(PTR)，在其中存放页表在内存的起始地址和页表的长度
在进程未执行时，页表的起始地址和页表长度存放在本进程的 PCB 里，当调度程序调度到某进程时，将这两个数据装入 PTR 中
每执行一条指令时，根据计算分页得到指令的页号与内部偏移量，然后 CPU 高速访问 PTR 找到对应页表位置
最后查找页表数据，得到指令页号实际对应存放的物理块，完成地址映射计算，最终在内存中找到该指令
具快表的地址变换结构
在基本分页机制下，CPU 操作一条指令需访问内存两次，一次访问内存中的页表，以计算指令所在的实际物理地址，一次根据计算出的实际物理地址去进行访问
因此，一次指令需要两次内存访问，虽然分页空间利用率提高，但这使得处理机速度降低了一半
为提高地址变换速度，可在地址变换机构中增设一具有并行查寻能力的高速缓存器，即快表（TLB），以存放当前访问的页表项
在加入快表之后，地址变换过程也有了改变：
在 CPU 给出有效地址后，地址变换机构自动地将页号送入快表，并将此页号与快表中的所有页号进行比较
若有相匹配的页号，表示要访问的页表项在快表中，因此可直接从快表中读出相应的物理块号，并送入物理地址寄存器；若没有相匹配的页表项，则还需访问内存中的页表，找到后将物理号送往物理地址寄存器，同时将该表项送入快表
若快表已满，则 OS 找到一个已被认为不再需要的页表项，进行替换
内存访问有效时间
进程发出逻辑地址的访问请求，经过地址变换，到内存中找到对应的实际物理地址单元并取出数据，所需花费的总时间，称为内存有效访问时间（EAT）
在基本地址变换结构中，设访问一次内存的时间为 $T$，那么 EAT 就等于查找页表对应页表项耗费的时间 T 与将页表的物理块号与页内地址拼接成实际物理地址耗费的时间 $T$ 的和，即：
而在引入了快表的分页存储管理方式中，通过快表查询，可以直接得到逻辑页对应的物理块，减少了一次内存访问，缩短了内存访问有效时间
但由于快表容量有限，因此在快表中查找表项存在命中率，即使用快表并在其中成功找到所需页面表项的比率
设 $\lambda , a, T$ 分别为查找快表所需时间、命中率、访问一次内存所需时间，那么 EAT 的计算公式为：
二级页表与多级页表
概述
由于目前大多数计算机都支持非常大的逻辑地址空间，在这样的环境下，页表就变得非常大，此外，由于页表要求连续，又要占用相当大的内存空间，系统并无法提供大的连续的内存空间来存放页表
为解决上述问题，可再用下述两个方法解决：
- 对页表所需的内存空间，采用离散分配方式
- 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入
对于 $32$ 位的系统，采用两级页表即可，但对于 $64$ 位的系统，两级仍无法解决页表过大的问题，此时，按照二级页表的原理，继续分页下去，可形成多级页表
地址结构
针对难以找到大的连续的内存空间来存放页表的问题，可以将页表进行分页，使每个页面的大小与内存物理块的大小相同，并将他们进行编号，即依次为：0#页，1#页，2#页，…，n#页，然后离散地将各个页面分别存放于不同的物理块中
同样，将离散分配的页表再建立一张页表，称为外层页表，在每个表项下记录了页表页面的物理块号
二级页表的地址结构包含三部分内容：前一部分为外页号 P1，中间一部分为外页内地址(页在外页内的偏移) P2，后一部分为位偏移量(页内地址) W
以下图为例，地址长度为 $32$ 位，$0$ 到 $11$ 位为页内地址，即每页大小为 $2^{12}=4K$，$12$ 到 $21$ 位为外页内地址，即每页最多有 $2^{10}$ 个页表项，$22$ 到 $31$ 位为外页号，即最多允许有 $2^{10}$ 个页表分页
地址变换机构
在地址变换机构中，增设了一个外页表寄存器，用于存放外页表的起始地址，并利用逻辑地址中的外层页号作为外层页表的索引，从中找到指定页表分页的起始地址，再利用 P2 作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号 $P$ 和页内地址 $W$ 即可访问内存的物理地址。
请求调页
上述对页表实行离散分配的方法，虽然解决了对于大页表无需大片连续存储空间的问题，但并未解决用较少的内存空间去放大页表的问题
换言之，只用离散分配空间的方法并未减少页表所占用的内存空间
能够用较少的内存空间存放页表的唯一方法是：仅将当前需要的一批页表项调入内存，以后再根据需要陆续调入
反置页表
在分页系统中，每个进程配置了一张页表，进程逻辑地址空间中的每一页，在页表中都要有一个页表项，这就占用了大量的内存空间
为减少页表占用的内存空间，由此引入了反置页表
反置页表为每一物理块设置了一个页表项，并将他们按物理块的编号排序，其中的内容则是已调入内存的进程标识符与页号
在利用反置页表进行地址变换时，根据进程标识符与页号，去进行检索
若检索到匹配的页表项，说明该页表项中的序号 i 便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送入内存地址寄存器；若未检索到匹配的页表项，说明此页未调入内存
当内存容量很大时，反置页表的页表项还是会很大，利用进程标识符和页号去检索一张大的线性表很费时，此时可利用哈希算法来提高检索速度
【分段存储管理】
段
分段存储管理方式的目的，主要是为了满足用户在编程和使用上多方面的要求，一方面，通常的程序都可以分成若干段，如：主程序段、子程序段、数据段、栈段等，每个段大多是一个相对独立的逻辑单位；另一方面，实现和满足信息共享、信息保护、动态链接、信息动态增长等需要，都是以段为基本单位的
在分段存储管理中，作业的地址空间被划分为若干段，每个段定义了一组逻辑信息，其具有如下特点：
- 每个段都有自己的名字，为实现简单，通常用一个段号来代替段名
- 每个段都从 $0$ 开始编址，并采用一段连续的地址空间
- 段的长度由相应的逻辑信息组的长度决定，因此各段的长度并不相等
- 整个作业的地址空间由于被分成多个段，因此呈现出二维特性，即每个段既包含了一部分地址空间，又标识了逻辑关系
- 编译程序自动地根据源程序的情况进行分段
分段地址的地址由段号 $S$ 和段内地址 $W$ 两部分构成，以下图为例：一个作业最多有 $2^{16}=64K$ 个段，每个段的最大长度为 $2^{16}=64KB$
段表
在分段存储管理系统中，为每个分段分配一个连续的分区，进程中的各个段，可以离散地装入内存中不同的分区
为保证程序正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置
为此，类似于分页系统，在分段系统中，需为每个进程建立一张段映射表（段表），用于实现从逻辑段到物理内存区的映射，每个段在表中占有一个表项，其中记录了该段在内存中的起始位置与段的长度
地址变换机构
为实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表起始地址和段表长度
在进程地址变换时，系统将逻辑地址中的段号 $S$ 与段表长度 $TL$ 进行比较： 若 $S>TL$，说明访问越界，产生越界中断；若 $S<=TL$，说明未产生越界情况，进行以下操作：
- 根据段表起始地址和该段段号，计算该段对应段表项位置，从中读出该段在内存中起始地址
- 检查段内地址 $W$ 是否超过该段的段长 $SL$：
- 若 $W>SL$：访问越界，产生越界中断信号
- 若 $W<=SL$： 未产生越界情况，将该段的基址 $W$ 与段内地址相加，得到要访问的物理地址
与分页系统相似，当段表放入内存时，每要访问一个数据，都要访问内存两次，这成倍的降低了计算机的速率
而解决的方法也与分页系统相似，即增设一个联想存储器，用于保存最近常用的段表项
分页与分段的区别
不难看出，分页与分段有许多相似之处，但在概念上，两者完全不同，主要表现在以下方面：
- 需求：分页是出于系统管理的需要，是信息的物理划分单位；分段是出于用户应用的需要，是逻辑单位，常包含一组意义相对完整的信息
- 大小：页的大小由系统固定，段的大小则不固定
- 碎片：分页存在内碎片，分段存在外碎片
- 逻辑地址：分页是一维的，各模块在链接时必须组织成同一个地址空间；分段是二维的，各个模块在链接时可以每个段组织成一个地址空间
- 其他：通常段比页大，因此段表比页表短，可以缩短查找时间，提高访问速度；分段可针对不同类型采取不同的保护，还可以按段为单位来进行共享
信息共享
分段系统的突出优点主要有两点，一是易于实现段的共享，而是易于实现信息保护
段的共享，是指若干进程共享一个或多个分段，由于在分段系统中，是以段为基本单位的，因此，实现共享只需在每个进程的段表中为共享程序设置一个段表项
信息保护，主要是代码的保护，这与其逻辑意义有关，因此成段的进行保护要远胜于分页的机械式划分
【段页式存储管理】
基本原理
分页系统是以页面为内存分配的基本单位，能有效地提高内存利用率；分段系统以段为内存分配的基本单位，能更好地满足用户多方面的需要
如果对两种存储管理方式各取所长，那么就形成了一种新的存储器管理方式——段页式存储管理，其既有分段系统的便于实现、易于保护、分段可共享、可动态链接的优点外，还能像分页系统那样很好地解决内存的外碎片问题
段页式系统的基本原理是分页与分段的结合，其先将用户程序分为若干段，再将每段分为若干页，地址结构由段号 $S$、段内页号 $P$、页内地址 $W$ 三部分构成
在段页式系统中，为实现逻辑地址到物理地址的变换，系统中需要同时配置段表和页表
段表的内容与分段系统中的段表略有不同，其不再是内存的起始地址与段长，而是页表的起始地址和页表长度
地址变换过程
在段页式系统中，为实现地址变换，须配置一个段表寄存器，其中存放段表起始地址与段长
在进行地址变换时，首先将段号 $S$ 与段长 $TL$ 进行比较：若 $S>TL$：说明访问越界，产生越界中断；若 $S<=TL$：说明未越界，进行下述操作：
- 利用段表起始地址、段号，求出该段所对应的段表项在段表中的位置，得到该段的页表起始地址
- 利用逻辑地址中的段内页号 $P$ 获得对应页的页表项位置，从中读出该页所在的物理块号 $b$
- 利用物理块号 $b$ 与页内地址构成物理地址
在段页式系统中，为获取一条指令或数据，需要访问内存三次：
- 访问内存中的段表，获取页表起始地址
- 访问内存中的页表，获取该页所在的物理块号，并将块号与页内地址一起组成物理地址
- 访问从第二次访问中所得的地址，取出指令或数据
显然这拖慢了执行速度，为此，在地址变化机构中增设了一个高速缓存寄存器
