1. 分页存储的几个基本概念#

2. 基本地址变换机构#

地址变换机构的任务是将逻辑地址转换为内存中的物理地址，这一过程借助页表实现。

NOTE

在页表中，页表项按页号顺序连续存放，因此页号作为索引是隐含的，无须在页表项中显式存储。

为提高地址变换速度，系统设置一个页表寄存器(PTR)，存放页表在内存中的始址 $F$ 和页表长度 $M$。由于寄存器造价昂贵，单CPU系统中通常只设置一个PTR。进程未执行时，其页表始址和长度保存在该进程的PCB中；当进程被调度执行时，操作系统将这些信息装入PTR。

设页面大小为 $L$，逻辑地址 $A$ 到物理地址 $E$ 的变换过程如下。

1. 根据逻辑地址计算页号 $P = \lfloor A/L \rfloor$、页内偏移量 $W = A \% L$。
2. 判断页号是否越界，若页号 $P \ge$ 页表长度 $M$，则产生越界中断；否则，继续执行。
3. 根据页号 $P$ 查找页表，找出对应页表项中的物理块号。页表项地址 $=$ 页表始址 $F +$ 页号 $P \times$ 页表项长度，取出该页表项中的物理块号 $b$。
4. 计算物理地址 $E = b \times L + W$，并据此访问内存（注意，物理地址 $=$ 页面在内存中的始址 $+$ 页内偏移量，页面在内存中的始址 $=$ 块号 $\times$ 块大小)。

上述地址变换过程由MMU硬件自动完成的。例如，若页面大小 $L = 1\text{KB}$，则页号2对应的物理块号 $b = 8$，逻辑地址 $A = 2500$ 的物理地址 $E$ 的计算过程如下：$P = 2500/1\text{K} = 2$，$W = 2500 \% 1\text{K} = 452$，故物理地址 $E = 8 \times 1024 + 452 = 8644$。

若逻辑地址以二进制形式给出，则页号和页内偏移可直接通过截取高位和低位获得，效率更高。正因页面大小固定，逻辑地址可视为一维线性地址，因而仅需一个整数即可确定其位置。

页表项大小不是随意规定的，而是有所约束的。页表项大小如何确定？

页表项需能表示所有可能的物理页框号。以32位地址空间、按字节编址、页面大小为4KB为例，物理内存最多包含 $2^{32}\text{B}/4\text{KB} = 2^{20}$ 个页框，因此需要 $\log_2 2^{20} = 20$ 位来表示页框号。由于内存按字节编址，为保证页表项能够指向所有页面，页表项大小至少为 $\lceil 20/8 \rceil = 3\text{B}$。但出于对齐和扩展考虑（如加入有效位、访问位等），实际系统通常将页表项设为4B。

分页管理面临两个主要挑战：

1. 每次访存都需要进行地址转换，若转换速度不够快，则会显著降低系统性能；
2. 页表本身占用内存空间，若页表过大，则会降低内存利用率。正是这些问题，推动了后续优化技术的发展，如快表(TLB)和多级页表。

3. 具有快表的地址变换机构#

由前述地址变换过程可知，若页表全部存放在内存中，则每次访问内存(无论是取指令还是读/写数据)至少需两次访存：第一次访问页表以获取物理块号，第二次根据形成的物理地址访问目标内容。显然，这种方式会显著降低系统性能。为此，现代地址变换机构增设了一个具有并行查找能力的高速缓冲存储器——快表(TLB)，用于缓存当前活跃的若干页表项，以加速地址变换。相应地，主存中的完整页表常被称为慢表。

在具有快表的分页机制中，地址变换过程如下。

1. CPU给出逻辑地址后，硬件自动提取页号，并将其与快表中所有页号并行比较。
2. 若命中（找到匹配的页号），则直接从快表中取出对应的物理块号，与页内偏移量拼接形成物理地址。此时，仅需一次访存即可。
3. 若未命中（未找到匹配的页号），则需访问内存中的页表，读取相应的页表项以获得其物理块号，再拼接形成物理地址并访问内存，共需两次访存。同时，系统会将该页表项装入快表，以便后续可能的重复访问；若快表已满，则按特定置换算法淘汰一个旧项。

在程序具有良好局部性的前提下，快表命中率通常可达90%以上，因此分页机制带来的性能开销可控制在10%以内。快表的有效性基于著名的局部性原理，这一原理将在3.2节中介绍。

4. 两级页表#

引入分页管理后，进程执行时无须将所有页面调入内存，但仍需将整个页表驻留内存。然而，页表本身可能非常庞大。以32位逻辑地址空间、页面大小为4KB、页表项大小为4B为例：页内偏移占 $\log_2 4\text{K} = 12$ 位，页号占20位，因此每个进程的页表最多包含 $2^{20}$ 个页表项，仅页表就需占用 $2^{20} \times 4\text{B} / 4\text{KB} = 1\text{K}$ 个页。若还要求页表连续存放，则显然不切实际。

解决上述问题的思路是将页表本身也视为可分页的对象，具体体现为两个方面：

1. 对页表采用离散分配，不再要求其连续存放，而是通过一张专门的索引表记录各页表页在内存中的位置，从而消除对连续内存空间的需求；
2. 仅将当前活跃的部分页表项调入内存，其余仍驻留磁盘，按需调入（虚拟内存的思想），从而有效缓解页表占用过多内存的问题。

不难发现，这一方案与最初引入页表以解决进程地址空间离散分配的思路如出一辙：本质上，就是为已离散化的页表再建立一层页表，称为外层页表（或页目录）。仍以上述条件为例：当采用两级分页时，将原页表按页面大小(4KB)进行分页。由于每页可容纳 $4\text{KB}/4\text{B} = 1024$ 个页表项，而总页表项数为 $2^{20}$，故需 $2^{20}/2^{10} = 2^{10} = 1024$ 个页表页，对应外层页表包含1024个表项，恰好占用一页(4KB)。

两级页表是在普通页表结构上再加一层页表。

在页表的每个表项中，存放的是进程某页对应的物理块号。例如，0号页存放在1号物理块中，1号页存放在5号物理块中。在外层页表的每个表项中，存放的是某个页表分页的物理起始地址。例如，0号页表页存放在3号物理块中。

通过外层页表和内层页表的协同作用，可实现从逻辑地址到物理地址的变换。

为方便地址变换，系统增设一个外层页表寄存器（也称页目录基址寄存器），用于存放外层页表的起始地址。地址变换过程如下。

1. 用逻辑地址中的页目录号作为索引，访问外层页表，获取对应内层页表的物理起始地址。
2. 用逻辑地址中的二级页号作为索引，访问该页表，得到目标页面的物理块号。
3. 将物理块号与页内偏移量拼接，形成物理地址，并据此访问内存单元。

在无快表的情况下，此过程需三次访存。

对于更大的地址空间（如64位），两级页表远远不够。例如，若逻辑地址为64位、页面大小为4KB，则页号占52位。若每页仍可存放1024个页表项，则需约6级页表才能覆盖整个地址空间。然而，实际系统通常将虚拟地址限制为48位，从而采用三级或四级页表即可高效管理，既满足应用需求，又避免硬件过度复杂化。建立多级页表的根本目的，是通过按需分配页表页，避免为未使用的地址空间预留大量无用的页表项，进而显著节省内存开销。

1. 分段#

分段系统将用户进程的逻辑地址空间划分为若干大小不等的段。例如，一个进程可包含主程序段、子程序段、栈段和数据段，共划分为5个段。每个段内部从0开始编址，并分配一段连续的地址空间（段内连续，段间不要求连续）。由于地址空间被组织为多个具有明确语义的段，整个进程的逻辑地址结构呈现出二维特性：由段号和段内偏移共同确定一个地址。

分段存储管理的逻辑地址由段号 $S$ 和段内偏移量 $W$ 两部分组成。在图3.12中，段号占16位，段内偏移量也占16位，则一个进程最多可拥有 $2^{16}=65536$ 个段，最大段长为64KB。

在页式系统中，逻辑地址中的页号与页内偏移量对用户透明；而在分段系统中，段号和段内偏移量必须由用户显式提供——这一工作在高级语言中由编译程序自动完成。

2. 段表#

每个进程都拥有一张段表，用于实现逻辑段到物理内存区的映射。段表中每个段对应一个段表项，记录该段在内存中的基址（起始地址）和段长（长度）。

运行时，系统通过查找段表，即可定位每段在内存中的实际位置。

由于段表项连续存放且长度相同，段号可作为隐含索引，无须额外存储。例如，在某32位分段系统中，段号为16位，段内偏移量为16位（段长字段为16位，对应最大段长64KB），物理地址为32位（可寻址4GB内存）。因此，每个段表项至少需要16（段长）+32（基址）=48位，即6B。若段表首地址为 $M$，则第 $K$ 号段对应的段表项位于地址 $M + K \times 6$ 处。

3. 地址变换机构#

分段系统的地址变换过程如图3.15所示。为实现从逻辑地址到物理地址的变换，系统设置了一个段表寄存器，用于存放段表始址 $F$ 和段表长度 $M$。段式存储管理的地址变换过程如下。

1. 从逻辑地址 $A$ 中分离出段号 $S$ 和段内偏移量 $W$。
2. 判断段号是否越界：若段号 $S \ge$ 段表长度 $M$，则产生段号越界中断，否则继续执行。
3. 根据段号 $S$ 查找段表：段表项地址 $=$ 段表始址 $F +$ 段号 $S \times$ 段表项长度。取出该段表项中该段的段长 $C$，若 $W \ge C$，则产生段内越界中断；否则，继续执行。
4. 取出段表项中该段的基址 $b$，计算物理地址 $E = b + W$，并据此访问内存。

4. 分页和分段的对比#

分页与分段均为非连续分配方式，均需通过地址映射机构实现地址变换。然而，二者在概念上有本质区别，主要体现在以下三个方面：

1. 页是系统管理内存的物理单位，分页的主要目的是提高内存利用率，完全由系统实现，对用户透明；段是用户程序的逻辑单位，分段的主要目的是满足编程、共享、保护等需求，由编译器根据程序结构划分，对用户可见。
2. 页的大小固定，由系统决定。段的长度不固定，取决于程序的逻辑结构。
3. 分页系统的地址空间是一维的，程序员只需提供单一的线性地址；分段系统的地址空间是二维的，程序员在引用地址时，必须同时指定段名（或段号）和段内偏移量。

5. 段的共享与保护#

在分页系统中，虽然也能实现共享，但远不如分段系统方便。若一段共享代码占 $N$ 个页框，则每个共享进程的页表中都需建立 $N$ 个页表项，分别指向这 $N$ 个页框。而在分段系统中，无论该段多大，只需在每个进程的段表中设置一个段表项指向该共享段，因此实现共享极为便捷。

为支持段共享，系统可维护一张共享段表，其中每个共享段对应一个表项，记录其段号、段长、内存起始地址、存在位、外存起始地址以及共享进程计数 count。当某进程不再使用该段时，count 减1；仅当 count=0 时，系统才回收该段所占的内存空间。值得注意的是，同一共享段在不同进程中可以具有不同的段号，各进程通过各自的段号即可访问同一物理段。

不能被修改的代码称为可重入代码（或纯代码），它允许多个进程并发执行。为确保共享代码的完整性，系统通常将此类代码置于只读段中。同时，每个进程需配备私有的局部数据区，专门用于存放执行过程中可能变化的数据，从而有效避免对共享代码段的任何写操作。

与分页管理类似，分段系统的保护机制主要包括两类：

1. 地址越界保护，将逻辑地址中的段号与段表长度比较，若段号 $\ge$ 段表长度，则产生越界中断；将段内偏移与段表项中的段长比较，若偏移 $\ge$ 段长，则同样触发越界中断。
2. 存取控制保护，通过段表项中的访问权限位防止非法访问。