存储器管理

存储器的层次结构

现代计算机的存储器并非一块均匀的内存芯片，而是一个精心设计的层次体系。最顶层是 CPU 寄存器，速度最快但容量极小，直接与 CPU 交互。中间层是主存储器，包含高速缓存 Cache、内存和磁盘缓存三个子层次，CPU 可以直接访问。最底层是辅助存储器，如硬盘和 SSD，速度最慢但容量最大。

操作系统主要管辖 CPU 寄存器层和主存储器层的分配与调度，辅助存储器层则归设备管理负责。寄存器和主存储器统称为可执行存储器。

程序的装入与链接

用户写好源代码后，程序并不能直接跑起来。它需要经历编译、链接、装入三个阶段。编译器把源程序翻译成若干目标模块，链接器把这些模块和所需的库函数合并成一个完整的装入模块，最后由装入程序把它加载到内存中。

这个过程中有一个关键概念：地址绑定。源代码里的地址通常是文字符号，编译器将它们绑定到可重定位的相对地址，链接器或装入程序再把相对地址绑定到绝对地址。CPU 生成的地址叫逻辑地址，也叫相对地址；内存单元实际看到的地址叫物理地址，也叫绝对地址。

内存保护则完全由硬件实现。系统设置基地址寄存器和界限寄存器，分别保存最小合法物理地址和合法范围大小。只要物理地址落在 [基地址, 基地址 + 界限地址) 的范围内就是合法的。加载这两个寄存器必须使用特权指令，只有操作系统内核才有权限，用户程序无法修改。

程序的装入

装入方式有三种。绝对装入是最简单的，适用于早期单道程序环境，程序只能装入内存中预先指定的位置。可重定位装入在装入时一次性完成逻辑地址到物理地址的变换，之后不再改变，可以装入内存的任何位置，适用于多道程序环境。动态运行时装入则更加灵活，装入后不立即做地址变换，推迟到程序真正执行时才进行，所有地址仍保持相对地址形式，需要重定位寄存器的支持。

程序的链接

链接也有三种方式。静态链接在运行前就把所有目标模块和库函数链接成一个完整的装入模块，以后不再拆开，需要解决修改相对地址和变换外部调用符号两个问题。装入时动态链接采用边装入边链接的方式，由外部模块调用事件触发目标模块的装入，便于修改和更新，也便于实现模块共享。运行时动态链接把链接推迟到程序执行时，加快装入速度并节省内存空间。

交换

多道程序环境下，内存空间有限，不可能让所有进程同时驻留。交换技术的思路很直接：把内存中暂时不能运行的进程调出到硬盘的交换区，腾出空间给需要运行的进程。

交换区和文件区的设计目标截然不同：

对比项	文件区	交换区
磁盘占比	大部分区域	小部分区域
访问频率	较低	较高（换入换出频繁）
主要目标	提高存储空间利用率	提高换入换出速度
次要目标	提高访问速度	提高空间利用率
分配方式	离散分配	连续分配
碎片问题	—	很少考虑

进程的换出分两步：先选择合适的进程，再执行换出。换入时则找出处于就绪态但已被换出的进程，优先选择换到磁盘上时间最久的那个。如果内存不够，需要先把某些进程换出再换入。

连续分配存储管理方式

最简单的内存分配方式是为每个进程分配一块连续的内存空间。它经历了从单一连续分配到动态分区分配的演进。

单一连续分配是早期单用户单任务操作系统采用的方式。内存分为系统区和用户区，用户区仅由一道用户程序独占。这种方式没有外部碎片，但有内部碎片，而且不需要内存保护。

固定分区分配把内存划分为若干固定大小的分区，每个分区装入一道程序。分区可以大小相等，也可以大小不等。系统维护一张固定分区使用表，记录每个分区的起始地址、大小及状态。缺点是程序超出最大分区就无法装入，而且会产生内部碎片。

动态分区分配

动态分区分配根据进程的实际需要动态划分内存分区，也叫可变分区分配。系统用空闲分区表或空闲分区链来记录空闲区域。

分配算法分为两大类。基于顺序搜索的算法包括首次适应算法（从头找第一个够大的块）、循环首次适应算法（从上次位置继续找）、最佳适应算法（找最小的够大块）和最坏适应算法（找最大块）。基于索引搜索的算法包括快速适应算法（按大小分类维护链表）、伙伴系统（按 2 的幂组织成二叉树）和哈希算法（用哈希函数直接定位）。

首次适应算法在实际中表现通常最好。空闲分区按地址递增排列，从头找到第一个够大的就分配。低地址碎片虽然逐渐累积，但大作业在高地址仍有大块可用。循环首次适应算法从上次分配位置继续往下找，查找更快，但大空闲分区消耗快。最佳适应算法按容量递增排列，找最小的够大块，每次浪费最少，却会产生大量极小碎片。最坏适应算法按容量递减排列，找最大块分配，剩余碎片相对大，但大块消耗快。

分配时如果空闲分区剩余空间不超过预设的阈值，即 m.size - u.size ≤ size，就把整个分区分配给进程，否则划出所需大小，剩余部分仍作为空闲分区保留。回收时如果释放的分区与相邻空闲分区相邻，则合并更新。

动态重定位分区分配

连续分配运行一段时间后，内存中会产生大量分散的小空闲分区，无法满足大作业的需求。紧凑操作把所有作业移动使它们相邻，把分散的小分区拼接成一个大分区。每次紧凑后都需要对移动后的程序和数据进行重定位。

为了提高效率，系统增设重定位寄存器，存放程序在内存中的起始地址，访问时由硬件自动完成地址变换。当分配算法找不到足够大的空闲分区时，先紧凑再重定位，然后重新执行分配。

分页存储管理

连续分配要求程序装入连续内存空间，这在内存紧张时效率很低。分页存储管理把进程的地址空间分为若干大小相同的页，把内存空间分成同样大小的块，页和块都加以编号。进程最后一页经常装不满一块，产生页内碎片。页面大小应是 2 的幂，通常为 1KB 到 8KB。

页表是分页系统的核心数据结构，实现页号到物理块号的映射。系统设置一个页表寄存器 PTR，存放页表在内存中的起始地址和页表长度。进程未执行时这些信息存在 PCB 中，被调度时才装入 PTR。

地址变换的过程是：CPU 生成逻辑地址（页号 P + 页内地址 W），先将 P 与 PTR 中的页表长度比较，越界则产生中断；然后以 P 为索引查页表，取出物理块号；最后把物理块号和 W 拼接形成物理地址。每次存取需要两次内存访问——一次查页表、一次取数据——效率较低。

快表

快表 TLB 是专门的高速缓冲寄存器，存放当前访问最频繁的少数页表项，通常 16 到 512 个。它利用了局部性原理：如果一个页面刚被访问过，它很可能很快再次被访问。

引入快表后，CPU 先查 TLB。命中则直接取出物理块号，只需一次访存。未命中则按基本流程查内存中的页表，同时把该页表项更新到 TLB。TLB 满时按 FIFO 或 LRU 等算法换出某个项。

有效访问时间的计算公式为：

$$EAT = \alpha \times \varepsilon + (1 - \alpha) \times (\varepsilon + m) + m$$

其中 α 是快表命中率，ε 是 TLB 访问时间，m 是内存访问时间。命中时只花 TLB 的时间，未命中时多花一次页表访问时间，最后取数据还需要一次内存访问。

两级页表与多级页表

现代计算机地址空间很大，页表本身也很大，全部驻留内存不现实。两级页表把逻辑地址分为外层页号、外层页内地址和页内地址三级。外层页表常驻内存，第二级页表可按需调入。

以此类推可扩展为三级、四级等。64 位计算机实际将地址位数缩减到 48 位，采用三级页表：每级 9 位，每张页表恰好 4KB，可按需调入内存。

反置页表则是另一种思路。传统页表每个进程一张，条目数等于虚拟页数，随地址空间增大而膨胀。反置页表整个系统只有一张，条目数等于物理块数，与虚拟地址空间大小无关。每个表项记录进程 ID 和虚拟页号，对应一个物理块号。缺点是查找需要遍历整张表，通常结合哈希加速检索。

分段存储管理

分段存储管理从另一个角度组织内存。用户按程序的自然逻辑结构把地址空间划分为若干段，每个段有自己的名称和长度。逻辑地址由段号 S 和段内地址 W 组成，W 必须小于段长，否则越界。

段表实现逻辑段到物理内存区的映射，每个段表项包含段基址和段长。地址变换分五步：先将段号 S 与段表寄存器中的段表长度比较，若 S ≥ 段表长度则越界中断；然后以 S 为索引查段表，取出段基址和段长；再将段内地址 W 与段长比较，若 W ≥ 段长则越界中断；最后物理地址 = 段基址 + W。两层越界检查是分段地址变换的特征——分页只检查页号，分段要同时检查段号和段内偏移。

分段的好处是多方面的。段是信息共享的基本单位，不同进程可以共享同一段代码。以段为单位设置存取权限，保护更直观。运行时按需链接段，无需一次性装入全部代码。段还可以根据需要动态增长。

分页与分段的区别

页是信息的物理单位，大小固定，由系统决定。段是信息的逻辑单位，大小不固定，由程序的逻辑结构决定。分页的用户程序地址空间是一维的，只需给出一个地址就能定位；分段是二维的，必须同时给出段号和段内地址。

信息共享在两种方式下的表现也不同。分页系统中共享的代码可能分散在多个页面中，需要为每个页面设置页表项指向同一物理块，页表项较多。分段系统中共享的代码属于同一段，只需一个段表项指向共享段即可。可重入代码允许多个进程同时访问，只读不写，是共享的典型应用。

段页式存储管理

段页式存储管理结合了分段和分页的优点。先将用户程序分为若干段，再把每个段分为若干页。逻辑地址结构为段号 S、段内页号 P、页内地址 W。每个进程一张段表，每个段一张页表。段表项存放段长和该段页表在内存中的起始地址，页表项存放物理块号。

地址变换时用 S 查段表得到页表起始地址，用 P 查页表得到物理块号，最后拼接 W 形成物理地址。每次访问需要三次访存——段表、页表、数据——但可以通过快表加速。快表中存放段号加段内页号到物理块号的映射，命中时一次访存即可。

这种方式兼具分段的逻辑清晰和分页的内存利用率高。