内存管理与虚拟内存

本节导读

大纲的「内存管理」分两块：内存管理基础（逻辑地址空间与物理地址空间、地址变换、内存共享、内存保护、内存分配与回收，连续分配、页式、段式、段页式管理）和虚拟内存管理（基本概念、请求页式管理、页框分配与回收、页置换算法、内存映射文件、虚拟存储器性能的影响因素及改进方式）。其中「页框分配与回收」，常见资料称 2025 年版新增（2022 年版写的是「页框分配」）。

页表、快表和地址变换的计算在第 16 节已经讲过，这一节侧重操作系统怎样分配、回收和置换内存。计算题主要是两类：动态分区按某种算法分配，以及给一串页面访问序列算缺页次数。

内存管理基础

程序里用的是逻辑地址，内存单元的真实地址是物理地址，把逻辑地址转换成物理地址叫地址变换（重定位）。动态重定位在程序执行时才变换，靠重定位寄存器（基址寄存器）完成：物理地址 = 基址 + 逻辑地址。

内存保护常用一对寄存器：界地址寄存器存放进程的长度（逻辑地址的上限），重定位寄存器存放起始物理地址。每次访存先把逻辑地址和界地址比较，小于它才加上基址，否则产生越界中断。内存共享靠多个进程的页表项（或段表项）指向同一块物理内存实现，共享的代码必须是可重入的纯代码，运行中不被修改。

连续分配管理方式

方式	做法	碎片
单一连续分配	内存分系统区和用户区，用户区只装一道程序	用户区没用完的部分浪费
固定分区分配	事先把用户区分成若干固定大小的分区，每个分区装一道作业	分区内没用完的部分是内部碎片
动态分区分配	作业装入时按需要的大小划出分区	分区之间留下的小空闲块是外部碎片，可用紧凑技术合并

动态分区有四种常用的分配算法：

• 首次适应：空闲分区按地址递增排列，从头找第一个够大的；
• 邻近适应（循环首次适应）：从上次分配结束的位置开始往后找第一个够大的；
• 最优适应：空闲分区按容量递增排列，找能满足要求的最小分区；
• 最坏适应：空闲分区按容量递减排列，找最大的分区。

回收分区时，要和相邻的空闲分区合并：上邻空闲、下邻空闲、上下都空闲各合并成一块，上下都不空闲就新建一个空闲分区表项。

页式、段式与段页式管理

比较项	分页	分段
划分依据	页的大小由系统决定，与程序结构无关	段的长度由程序的逻辑结构决定
逻辑地址空间	一维，给出一个地址即可	二维，要给出段号和段内地址
碎片	只有每个进程最后一页的内部碎片	段与段之间有外部碎片
共享与保护	一页里可能混有不同模块，不太方便	按逻辑模块共享和保护，比较方便

段页式先分段、段内再分页，内存按页框分配，兼顾了分段的逻辑性和分页的利用率，代价是一次访存要查段表、页表两次。

请求页式管理

虚拟内存利用程序的局部性，只把当前要用的页面装入内存，其余留在外存，需要时再调入、内存满了就换出，让用户感觉到的内存比实际大得多。

请求页表在页表项里增加：状态位（是否在内存）、访问字段（最近是否被访问）、修改位（调入后是否被改过，改过的换出时要写回外存）、外存地址。访问的页不在内存时产生缺页中断：缺页中断在一条指令执行期间产生并立即处理，处理完后重新执行这条指令。

若内存访问时间为 $t_{m}$tm​、缺页率为 $p$p、缺页处理时间为 $t_{f}$tf​，有效访问时间约为 $(1-p) \times t_{m} + p \times t_{f}$(1−p)×tm​+p×tf​。缺页处理要读写磁盘，是毫秒级的，所以缺页率哪怕只有万分之几，也会把平均访存时间拉长好几倍。

内存映射文件：把磁盘文件的一部分映射到进程的虚拟地址空间，进程像读写内存一样读写文件，由请求分页按需调入；多个进程映射同一个文件，就能共享这块数据。

页框分配与回收

分配给一个进程的页框集合叫驻留集。分配与置换策略有三种组合：固定分配局部置换（页框数不变，只在自己的页框里换）、可变分配全局置换（缺页时从系统空闲页框中再分给它一个，不够时可以换出任何进程的页）、可变分配局部置换（只换自己的页，但系统根据缺页率增减它的页框数）。固定分配不能与全局置换搭配，因为从别的进程那里换来页框，页框数就变了。

调入时机有预调页（运行前或按局部性提前调入）和请求调页（缺页时才调入）；页面可以从对换区（读写快）或文件区调入。进程结束或页面被换出时，页框回收到空闲页框链表（或位示图）中，供以后分配。

页置换算法

算法	换出哪一页	特点
最优置换 OPT	以后最长时间不再访问的页	缺页最少，但要预知未来，只用来做比较
先进先出 FIFO	最早调入内存的页	实现简单，与访问规律不符，会出现 Belady 异常
最近最久未使用 LRU	最近一段时间最久没被访问的页	性能接近 OPT，要记录每页最近的访问时间，需硬件支持，开销大
时钟 CLOCK	指针循环扫描，访问位为 1 的清 0 跳过，换出第一个访问位为 0 的页	用一个访问位近似 LRU，开销小