分页、分段

连续分配要求进程占用一整段连续物理内存，容易受到外部碎片和连续空间不足的限制。分页和分段都允许进程的逻辑地址空间与物理内存分离，只是划分方式不同：

方式	划分依据	主要目标
分页	按固定大小划分	提高内存利用率，避免外部碎片
分段	按逻辑模块划分	方便共享、保护，符合程序员视角
段页式	先按逻辑模块分段，再把段分页	结合分段和分页的优点

透明性

分页的页号、页内偏移通常由硬件从一维逻辑地址中自动拆出，对所有程序员透明；分段的段名、段号、段内地址更贴近程序逻辑，因此在程序员可见。
但无论分页还是分段，最终装入到哪个物理页框或哪段物理内存，仍然对进程透明。

# 基本分页

分页存储把进程的逻辑地址空间划分为大小相等的页，把物理内存划分为同样大小的页框。页可以离散地装入不同页框中。

概念	含义
页 / 页面	进程逻辑地址空间的固定大小块
页框 / 页帧 / 内存块	物理内存中的固定大小块
页号	页面编号，从 0 开始
页内偏移量	页面内部的位置
页表	记录页号到页框号映射的数据结构

分页不产生外部碎片，但可能产生内部碎片：一页未必刚好用满。

进程看到的是连续的逻辑地址空间，但各页在物理内存中可以离散存放。只要页表维护正确，程序按逻辑地址连续访问即可，不需要知道页框位置。

逻辑地址结构

分页系统中，逻辑地址由页号和页内偏移量组成：

$$
\text{逻辑地址} = \text{页号} + \text{页内偏移量}
$$

若页面大小为 $2^d$ Byte，且按字节编址，则页内偏移量占 $d$ 位。其余高位为页号。

Example

页面大小为 4KB，即 $2^{12}$ Byte，则页内偏移量占 12 位。若逻辑地址共 32 位，则页号占 $32-12=20$ 位。

## 页表

页表记录每个逻辑页实际放在哪个物理页框中。最基本的页表项至少要保存页框号。

字段	作用
页框号	指出该页实际位于哪个物理页框
有效位 / 状态位	后续请求分页中用于表示页面是否已在主存
访问位	后续页面置换中记录是否被访问过
修改位	表示页面调入主存后是否被写过
保护位	控制读、写、执行权限

在基本分页中，页表项连续存放，因此页号可以是隐含的。若页表起始地址为 $F$，页表项长度为 $l$，则页号 $P$ 对应的页表项地址为：

$$
F + P \times l
$$

页表项大小通常不只按刚好能表示页框号取最小值，还要考虑对齐和查询方便。例如理论上 20 bit 能表示页框号，但实际可能用 4B 保存一个页表项。

基本地址变换机构

基本地址变换机构通过页表把逻辑地址转换为物理地址。

通常设置页表寄存器 PTR，保存当前进程页表的始址和页表长度。进程未运行时，这些信息保存在 PCB 中；进程被调度运行时，内核把它们装入页表寄存器。

一次基本分页地址转换：

从逻辑地址中得到页号 $P$ 和页内偏移量 $W$。
检查页号是否越界。若 $P \ge M$，其中 $M$ 为页表长度，则产生越界异常。
计算页表项地址：$F + P \times l$。
访问内存中的页表项，取出页框号 $b$。
拼接页框号和页内偏移量，得到物理地址。
访问目标物理地址。

若没有 TLB，访问一个逻辑地址通常需要两次访存：第一次访问页表，第二次访问目标内存单元。

Example

页面大小 $L=1KB$，逻辑地址 $A=9C4H$，页号 2 对应页框号 $b=8$。求物理地址

$$
9C 4H \implies 10|01~~1100~~0100B \implies 0010~~00|01~~1100~0100B \implies 21C4H
$$

## TLB

TLB 又称快表，是页表项的高速缓存。它保存最近访问过的页表项副本，用来加速地址转换。

TLB 和普通 Cache 都利用局部性原理，但缓存对象不同。

对象	缓存的内容
TLB	页表项副本
普通 Cache	主存数据块或指令块

TLB 解决“查页表太慢”的问题，Cache 解决“访问主存太慢”的问题。

TLB 命中

TLB 命中时，可以直接从 TLB 得到页框号，再与页内偏移量形成物理地址。此时不需要访问内存中的页表。

若只统计主存访问次数，TLB 命中后只需访问一次主存，即访问目标内存单元。

TLB 未命中

TLB 未命中时，需要访问内存中的页表，找到页表项后将其复制到 TLB，再形成物理地址并访问目标内存单元。

若 TLB 已满，需要按替换算法淘汰旧的 TLB 项。

平均访问时间

设访问 TLB 时间为 $t_l$，访问主存时间为 $t_m$，TLB 命中率为 $h$。

先查 TLB，未命中再查页表：

$$
T = h(t_l + t_m) + (1-h)(t_l + 2t_m)
$$

若系统支持 TLB 和页表同时查找，则未命中路径可能少等待一部分 TLB 时间，公式要按题目给定模型处理。

多级页表

单级页表的问题是页表可能很大，并且要求页表项连续存放。

以 32 位逻辑地址、页面大小 4KB、页表项 4B 为例：

页内偏移量占 12 位。
页号占 20 位。
进程最多有 $2^{20}$ 个页表项。
单级页表最大占 $2^{20} \times 4B = 4MB$。

4MB 页表本身需要 1024 个连续页框才能存放。

多级页表把页表再分页，用外层页表记录下一级页表的位置。

两级页表常见地址结构：

$$
\text{逻辑地址} = \text{一级页号} + \text{二级页号} + \text{页内偏移量}
$$

地址转换过程：

用一级页号查页目录表，找到二级页表位置。
用二级页号查二级页表，找到目标页框号。
用页框号和页内偏移量形成物理地址。
访问目标内存单元。

多级页表减少了“整张页表必须连续常驻”的压力，但如果没有 TLB，地址转换需要更多次访存。

分段

分段按程序的逻辑模块划分地址空间。例如主程序、子函数、共享库、全局数据都可以成为不同段。

分段系统的逻辑地址是二维的：

$$
\text{逻辑地址} = \text{段号} + \text{段内地址}
$$

程序员在分段系统中看到的地址更接近逻辑模块。源程序中的段名会被编译器转换为段号。

程序需要按段组织代码、数据和共享库；但每段实际放在哪里，由段表中的基址决定，程序只使用段号和段内地址。

段表与分段地址转换

每个进程有一张段表。段表项至少包含段长和段基址。

字段	作用
段长	检查段内地址是否越界
基址	该段在物理内存中的起始地址
保护信息	控制该段是否可读、可写、可执行

分段地址转换：

从逻辑地址中得到段号 $S$ 和段内地址 $W$。
检查段号是否越界。若 $S$ 大于等于段表长度，则越界。
查段表，取出段长 $C$ 和段基址 $b$。
检查段内地址是否越界。若 $W \ge C$，则越界。
计算物理地址：

$$
E = b + W
$$

分段系统也可以引入类似 TLB 的快表来缓存段表项。

与分页对比

对比项	分页	分段
划分方式	固定大小	按逻辑模块，长度可变
地址结构	一维地址，硬件自动拆页号和偏移	二维地址，段号 + 段内地址
碎片	无外部碎片，有少量内部碎片	有外部碎片
用户可见性	页的划分通常对程序员透明	段的划分通常对程序员可见
物理装入位置	对进程透明，由页表完成页号到页框号的映射	对进程透明，由段表完成段号到基址的映射
共享与保护	单位是页，不一定贴合逻辑模块	单位是段，更贴合逻辑模块

分页主要解决内存利用率问题；分段主要服务程序逻辑结构、共享和保护。

段页式

段页式先把进程按逻辑模块分段，再把每个段分页。逻辑地址由三部分组成：

$$
\text{逻辑地址} = \text{段号} + \text{页号} + \text{页内偏移量}
$$

对用户而言，程序按段组织，分页依然透明。

段页式地址转换：

用段号查段表。
检查段号是否越界。
从段表项中得到该段页表的位置和页表长度。
用页号查该段对应的页表。
检查页号是否越界。
得到页框号，和页内偏移量形成物理地址。
访问目标内存单元。

段页式结合了分段的逻辑结构和分页的离散装入能力，但地址转换过程更复杂。若不引入快表，访问一个逻辑地址可能需要3次访存：先查段表、再查页表、最后访问目标单元。