前言

存储器管理

概述

存储管理

存储系统的结构

程序的诞生

空间分类

地址映射

程序链接的方式

静态链接

装入时动态链接

运行时动态链接

程序装入的方式

程序装入的两类三种方法

绝对装入

静态重定位

动态重定位√

关键点

存储器管理：连续分配

单一连续分配

分区管理

固定分区分配

[放置算法（分配算法）]

动态分区分配

常用分区分配算法

[最先适配算法]

[循环最先适配算法]

[最佳适配算法]

[最坏适配算法]

[伙伴系统]

[碎片问题：紧凑/动态重定位]

动态分区分配算法总结

覆盖

基本概念

实例

缺点

交换/对换

基本概念

交换粒度

优缺点

交换与覆盖的比较

存储器管理：离散分配

页式存储管理

基本概念

[分页逻辑地址结构]

[基本页式存储管理]

[地址变换机构]

页式存储中的重定位

⭐重点计算方法：

具有快表的地址变换机构

[快表]

计算页表存储空间

两级和多级页表

[例题]

反置页表

页式存储小结

段式存储管理

基本概念

[评价]

段式地址变换

分配（类似动态分区）

与分页的比较

段页式存储管理

基本思想

地址映射

地址变换

地址变换实例

虚拟存储器

基本概念

局部性原理

虚拟内存

虚拟页式

请求分页

内存分配、置换策略

缺页中断处理

系统颠簸/抖动

工作集

页面替换/置换算法

最佳算法（OPT）

先进先出算法(First in First Out，FIFO)

最近最久未使用算法(LRU, Least Recently Used)

Clock算法

改进Clock算法

其他置换算法

练习题

编辑

虚拟段式

请求分段

地址变换过程

虚拟段页式

分段的共享与保护

总结

前言

进程与并发控制已更新，传送门：电子科技大学操作系统期末复习笔记（二）：进程与并发控制

本复习笔记基于电子科技大学计算机操作系统-教学大纲（2022）中的课程模块部分，分为五大章节，分别是：

CM1：操作系统概念。操作系统基本功能、操作系统发展历史及趋势、操作系统主流架构、常见操作系统特点、操作系统安全机制。
CM2：进程管理。进程概念、线程概念、进程生命周期、进程调度算法、进程同步互斥、进程间通信和死锁。
CM3：内存管理。内存空间的概念、连续分配、离散分配（分页管理、分段管理、段页式管理）、虚拟存储管理和页面置换算法。
CM4：设备管理。I/O 系统结构、缓冲管理、磁盘结构和磁盘调度算法。
CM5：文件管理。文件系统的作用、逻辑结构、物理结构、目录、文件共享和文件系统的一致性。

本节要点在CM3，大致内容如下：

第三章存储器管理（14 学时，多媒体课件结合板书面授）CM3

1、主要内容

操作系统存储管理的需求分析；现代计算机系统的多级存储体系；存储划分技术；分区、动

态分区分配算法；伙伴系统；分页/分段存储管理；段页式存储管理技术。对换技术。虚拟存储器的基本概念，请求分页存储管理，请求分段存储管理，虚拟存储的软件策略：驻留集管理、页面获取、页面放置、页面置换算法、负载控制。

2、应达到的要求

记忆：多级存储体系结构、程序的装入和链接。

理解：存储器管理相关技术、虚拟存储器的基本概念。

应用：重定位与地址转换、分区存储管理、动态分区分配算法、交换技术、分页存储管理、

各种页面置换算法、分段存储管理。

分析：段页式存储管理、虚拟存储管理技术。

本节涉及到4个PPT，分四个大块叙述。

存储器管理

概述

存储管理

定义

主要是指对内存储器的管理
在多道程序环境之中，多个作业需共享内存资源，内存紧张的问题依然突出
存储管理是操作系统的重要组成部分，能否合理有效地利用内存在很大程度上影响着整个计算机的性能。

主要目的

提高资源的利用率，尽量满足多个用户对内存的要求；
方便用户使用内存，不必考虑作业具体放在哪块区域。

应实现的主要功能

分配和回收
共享
保护
扩充

存储系统的结构

程序的诞生

从源代码 → 可以在内存中运行的程序

编译
由编译程序（Compiler）将用户源代码编译成若个目标模块
链接
由链接程序（Linker）将目标模块，以及所需要的库函数链接在一起，形成一个完整的装入模块
装入
由装入程序（Loader）将装入模块装入内存。

C语言的过程：预处理、编译、汇编、链接、加载

空间分类

名空间：代码里的变量名（个人理解）

用汇编语言或高级语言编写程序时，用符号名来访问某一单元。
程序中由符号名组成的程序空间称为符号名空间，简称名空间。
逻辑空间：汇编时分配的地址（个人理解）

源程序经过编译形成目标程序，每个目标程序都以0为基址顺序进行编址，原来用符号名访问的单元用具体的数据——单元号取代。
这样生成的目标程序占据一定的地址空间，称为逻辑地址空间，简称逻辑空间。
在逻辑空间中每条指令的地址和指令中要访问的操作数地址统称为逻辑地址。
内存空间（物理空间）：加载入内存运行时的实际地址（个人理解）

内存由若干存储单元组成，每个存储单元有一个编号，这种编号可惟一标识一个存储单元，称为内存地址（或物理地址）。
内存地址的集合称为内存地址空间（或物理地址空间），简称内存空间（或物理空间）。
内存空间编号示例：
一维线性空间，编址顺序为0，1，2，3，…… n-1，n的大小由实际组成存储器的存储单元个数决定。比如，64K内存的空间编号为0，1，2，3，……65535。
（64K=2^6*2^10=2^16；空间地址为[0, 2^16-1]=[0, 65535]）
空间的关系

地址映射

将逻辑地址转换为运行时机器直接寻址的物理地址。
当程序装入内存时，操作系统要为该程序分配具体的内存空间。
由于程序的逻辑地址与内存物理地址未必一致，CPU执行指令按物理地址进行的，要进行地址转换。
重定位(relocation)

程序链接的方式

源程序经过编译后，可得到一组目标模块，再利用链接程序将目标模块链接形成装入模块：模块拼接
根据链接时机不同，链接分为三种：
静态链接(Static Linking)
动态链接(Dynamic Linking)
装入时动态链接(Load-time Dynamic Linking)
运行时动态链接(Runtime Dynamic Linking)

静态链接

在(编译)链接阶段(程序运行之前)，将各目标模块及它们所需的库函数，链接成一个完整的装入模块，以后不再拆开。
相对地址的修改
变换外部调用符号

个人理解：提前（静态）装入不需要额外的算力，装入后程序运行稳定

装入时动态链接

目标模块在装入内存时，采用边装入边链接的链接方式，装入后不再链接。
各目标模块分开存放，便于修改和更新。
便于目标模块的共享
静态链接：每个装入模块都含有其目标模块的拷贝，无法实现对目标模块的共享。
装入时动态链接：OS可将一个目标模块链接到多个装入模块上，实现多个应用程序对该模块的共享。
个人理解：装入再装可以同时给多个装，达到共享、便于修改的目的

运行时动态链接

在程序执行中需要该目标模块时，由OS找到该模块，将其装入内存，并把它链接到调用者模块上。
执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上。
加快程序的装入
节省内存空间
共享
个人理解：运行再装可以灵活选自己需要的装入，节约内存，加快运行速度，还能共享模块

程序装入的方式

地址重定位：模块载入位置（可能伴随链接）

程序装入的两类三种方法

绝对装入
编译时完成
可重定位装入
加载时执行，静态地址重定位
运行时执行，动态地址重定位

绝对装入

固定地址重定位，编译时知道进程在内存中的驻留地址，生成绝对代码，即在可执行文件中记录内存地址，装入时直接定位在该内存地址。
程序地址空间和内存地址空间一一对应
如果开始地址发生变化，必须重新编译代码
优点：装入过程简单
缺点：不灵活，不适于多道程序系统

静态重定位

目标程序装入内存时，由装入程序对目标程序中的指令和数据的地址进行修改，即把程序的逻辑地址都改成物理内存地址。
当用户程序被装入内存时，一次性实现逻辑地址到物理地址的转换，以后不再转换。
优点
易实现，无需硬件支持
缺点
程序重定位后就不能移动，因而不能重新分配内存，不利于内存的有效利用。
程序在存储空间中只能连续分配，不能分布在内存的不同区域。
难于共享

动态重定位√

程序装入内存时，不修改逻辑地址，在访问物理内存之前，再实时地将逻辑地址转换成物理地址。
优点
程序不必连续存放在内存中，可分散存储，可移动；
便于共享；
有利于紧缩、碎片问题的解决。
缺点
需要硬件支持，实现存储管理的算法比较复杂。
主流方式

关键点

绝对装入和静态重定位

符号解析 + 地址重定位：紧耦合
动态重定位

符号解析→地址重定位：松耦合
链接和装载动作的交织

存储器管理：连续分配

存储器管理分为三大方式：连续分配、离散分配、虚拟存储器。

单一连续分配

基本思想

整个内存空间分成系统区和用户区，系统区给操作系统使用，用户区给用户使用。
用户区分配给一个进程
适用场合

最简单，适用于单用户、单任务OS
优点

易于管理
缺点

对内存空间需求少的程序，造成内存浪费；
程序全部装入，很少使用的程序部分也占用内存。

分区管理

基本原理

把内存分为一些大小相等或不等的分区；
每个应用进程占用一个分区，操作系统占用一个分区。
特点

适用于多道程序系统和分时系统
问题

内部碎片：占用分区之内未被利用的空间
外部碎片：占用分区之间难以利用的空闲分区
难以进行内存分区的共享。

固定分区分配

把内存分为大小相等或不等的分区(partition)
分区的划分一般由系统管理员或操作系统决定，一旦划定，在整个执行过程中不变
特点
适用于多道程序系统和分时系统
支持多个程序并发执行
问题
难以进行内存分区的共享
碎片

等大小分区和不等大小分区

[放置算法（分配算法）]

当一个进程装入或换入主存中时，如果存储器中有多个足够大的空闲分区，放置算法确定分配哪个自由块。

等大小分区
只要有一个可用分区，进程就可以装入该分区
如果所有分区都被占满了，须换出一个进程
一个程序可能太大而不能放到一个分区中
不等大小分区
方法1：每个分区一个调度队列，将每个进程指定到适应它的最小分区。
内部碎片最小
缺点：一段时间没有大尺寸程序到来，小程序排队，大空间闲置。
方法2：所有进程一个队列。
当需要把一个进程装入主存时，选择可以保存该进程的最小的可用分区。
如果所有分区都已被占据，须进行交换。
优点：
比单一连续分配方法，内存利用率提高了
可以支持多道程序
实现简单
缺点：
分区的数目在系统生成时确定，限制了系统中活跃进程的数目
小作业的内部碎片可能比较大
作业须预先能够估计要占用的内存空间

动态分区分配

在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小。

优点
没有内部碎片
缺点
外部碎片
分区分配算法
寻找空闲分区，需大等于程序的要求。
若大于要求，则将该分区进行分割，分别标记为“占用”和 “空闲”。
分区释放算法
将相邻的空闲分区合并成一个空闲分区。
优点
实现了主存共享，有助于多道程序设计；
主存利用率比固定分区高；
实现存储保护的措施比较简单。
缺点
外部碎片→ 主存利用率低；
一个作业执行前必须全部装入主存。

常用分区分配算法

最先适配算法
循环最先适配算法
最佳适配算法
最坏适配算法

[最先适配算法]

算法思想
按分区地址排序，从头查找，找到符合要求的第一个分区。
算法实质
尽可能利用存储区低地址空闲区，尽量在高地址部分保存较大空闲区，以便一旦有分配大空闲区要求时，容易得到满足。
空闲区按地址顺序组织

优点
分配简单，合并相邻空闲区也比较容易
缺点
查找总是从表首开始，前面空闲区被分割的很小时，满足分配要求的可能性较小，查找次数较多。
解决方法
对最先适配法稍加改进 → 循环最先适配法。

[循环最先适配算法]

算法思想
按分区先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区
特点
算法的分配和释放的时间性能较好，使空闲分区分布得更均匀，但较大的空闲分区不易保留。
空闲区按顺序组织

[最佳适配算法]

算法思想
在所有大等于要求分配长度的空闲区中挑选一个最小的分区，即对该分区所要求分配的大小来说，是最合适的。
算法实现
空闲区从小到大顺序组织

优点
较大的空闲分区可以被保留
缺点
空闲区按大小而不是按地址顺序排列，因此释放时，要在整个链表上搜索地址相邻的空闲区，合并后，插入到合适的位置。

[最坏适配算法]

算法思想
分区时取所有空闲区中最大的一块，必要时拆分形成2个块，一个选用，一个形成新空闲块。
算法实现
空闲区按由大到小排序

优点
分配时，只需查找一次，就可成功，分配算法很快。
缺点
最后剩余分区会越来越小，无法运行大程序

[伙伴系统]

按照页面组织为块（2的k次幂个页面）
申请时对半拆分，直到能够容纳申请量，空闲的放入新队列
释放回收时合并：尺寸相同
速度快，但利用率不高

[碎片问题：紧凑/动态重定位]

碎片问题
经过一段时间分配、回收后，内存中存在很多很小的空闲块。
每一个都很小，不足以满足分配要求；
但其总和满足分配要求→存储资源浪费。
解决方法
紧凑技术
在内存移动程序，将所有小的空闲区合并为大空闲区域
系统开销大
离散分配方式

动态分区分配算法总结

覆盖

基本概念

一个程序的几个代码段或数据段，按照时间先后占用公共的内存空间
将程序的必要部分代码和数据常驻内存；
可选部分在独立模块中，平时存放在外存中（覆盖文件），需要时才装入到内存；
不存在调用关系的模块不必同时装入到内存，可相互覆盖。

实例

注：不存在调用关系的模块才可以相互覆盖！

覆盖不需要OS提供特殊的支持，但程序员必须适当地设计和编写覆盖结构。

缺点

编程时必须划分程序模块和确定程序模块之间的覆盖关系 → 增加编程复杂度。
从外存装入覆盖文件，以时间换空间。

交换/对换

基本概念

多个程序并发执行：

将暂时不能执行的程序换出到外存中，从而获得空闲内存空间来装入新程序；

或读入保存在外存中而目前到达就绪状态的进程到内存中。

交换粒度

整体交换
也称为进程交换，交换是以整个进程为单位
部分交换
也称为页面交换、分段交换，是分页、分段交换的基础，目的是为了支持虚拟存储系统
对换空间的管理
对换区一般采用连续分配
对换区比普通文件区侧重于对换速度

优缺点

优点
增加并发程序数量，并给用户提供适当的响应时间；
编写程序时不影响程序结构
缺点
换入和换出的控制增加处理机开销
时间换空间

交换与覆盖的比较

覆盖技术主要用在早期的操作系统中；

交换技术被广泛用于分时系统中，导致了虚存技术的出现；

覆盖发生在无调用关系程序段之间；

交换技术对程序段之间的逻辑关系无要求；

交换发生在进程或作业之间；

覆盖发生在同一进程或作业内。

存储器管理：离散分配

连续分配一次性分配所有，不灵活

碎片问题：紧凑方式消耗系统开销

离散分配分页、分段、段页

页式存储管理

基本概念

用户空间划分：用户程序按逻辑页划分成大小相等的部分，称为页（虚页）从0开始编制页号，页内地址相对于0编址。

逻辑空间划分由系统自动完成的，对用户透明。一般页大小为2的整数次幂，因此，地址的高位部分为页号，低位部分为页内地址。

[分页逻辑地址结构]

页内地址：长度由页大小决定；

页号：除去页内地址所占的高位部分。

例：逻辑地址为32位，页大小为4KB，则逻辑地址的低12位（2^12=4KB），为页内地址w，而高20位为页号p，地址结构如下：

[基本页式存储管理]

内存空间划分
按页的大小划分为大小相等的区域，称为内存块（物理页面，页框、实页）→ frame
从0开始编号
内存分配
以页为单位进行分配
内部碎片 → 最后一页的页内碎片
外部碎片？
逻辑上相邻的页，物理上不一定相邻；反之亦然。
[地址变换机构]

页表 page table
逻辑页号→物理块号的映射。
基本地址变换机构
每个进程拥有一个页表，其信息（如长度、始址）放在PCB中，执行时将其首地址装入页表寄存器。
页表在内存，属于进程的现场信息(内核)。

⭐描述：将逻辑地址的页号取出和页表始址搭配找到页表中对应的块号，将块号取出和页内地址拼接成物理地址，如此循环，直到取出的逻辑地址页号大于页表长度，越界中断。

页式存储中的重定位

例题：

一个系统，内存容量共256KB，页框大小为1KB，共256块，编号为0～255。第0～4块为操作系统所使用；现有2个用户作业，作业1和作业2，其逻辑地址空间分别占2KB和2.5KB；进入系统后，按块的大小划分分别占2页和3页。

⭐重点计算方法：

计算页号：逻辑地址/页框大小；
页号 → 物理块号
页内偏移：逻辑地址%页框大小。
物理地址：物理块号*页框大小+页内偏移

具有快表的地址变换机构

页表访存：二次访页表操作数据

[快表]

局部性：Locallity
高速缓冲存储器，存放当前作业的最常用的页号和与之相应的物理块号。
快表或联想存储器
Translation Lookaside Buffer （后备/后援缓冲）
Associative Mapping（unordered）

⭐描述：查找过的就放在快表里，拿到逻辑地址先找快表里，没有的话就输入快表再查页表，随后拼接页内地址即可

练习：

有一页式系统，其页表存放在主存中：对主存的一次存取需要1.5μs，问实现一次页面访问的存取时间是多少? 如果系统有快表，平均命中率为85%，当页表项在快表中时，其查找时间忽略，问此时的平均存取时间是多少?

无快表主存存取访问时间：1.5*2=3μs

增加快表后的存取访问时间： 0.85*1.5+(1-0.85)*2*1.5=1.725μs

计算页表存储空间

页表也在内存，也需要按页存储

例子：

32位系统；页面大小：4K；页表项（页号记录）：4B；问：一个进程的页表需要多少存储空间？

64位系统；页表项：8B；问：当页面大小为4K和1M时，一个进程的页表需要多少存储空间？

4K：264/4K * 8B=255B=32P
1M：264/1M * 8B=247B=128T

两级和多级页表

两级页表

逻辑地址结构：
32位地址空间；页面大小4K；页表项4B
如何计算每一层的位数？每页表项数宽度

二级页表查找过程

注意：页号是用来索引页表的，页表里存储的都是内存块号。

计算：

64位系统；页面大小：4KB；页表项：8B；计算：2级页表存储空间；3级页表存储空间；至少设置几级页表才合理？（一级页表在一页内存储）

2级页表: 每页页表项记录数量：4K/8B=2^9个第2级页表项数量：2^64B/4K=2^52 第2级页表项所需页面数量：2^52/2^9=2^43个第1级页表项数量：2^43 第1级页表项所需页面数量：2^43/2^9=2^34个页表空间：(2^43+2^34) * 4K=(2^13+2^4) * 4T=32832T≈32.8P
3级页表: 每页页表项记录数量：4K/8B=2^9个第3级页表项数量：2^64B/4K=2^52 第3级页表项所需页面数量：2^52/2^9=2^43个第2级页表项数量：2^43 第2级页表项所需页面数量：2^43/2^9=2^34个第1级页表项数量：2^34 第1级页表项所需页面数量：2^34/2^9=2^25个页表空间：(2^43+2^34+2^25) * 4K=(2^23+2^14+2^5) * 4G=...
几级页表: 每页页表项数量：2^9 每9位切一刀 1次访存→7次访存 ⌈(64−12)/9⌉⇒⌈(位数−页内偏移)/每级别页号位数⌉⇒⌈log_2页面总数/log_2页内表项数⌉

多级页表令总空间增加，但通过按需装载，节省了内存空间。

评价：物理空间小，逻辑空间大。

页表大小∝逻辑空间大小

物理内存变化速度<<逻辑空间

[例题]

某24位存储系统采用页式管理，页表分为两级，存储在主存中。每个页面1KB，每个页表项占4B，某进程的页表内容如下图所示（图中数字全部为10进制）。请计算逻辑地址526245（十进制）对应的物理地址。

解答：

每个进程的总页面数为224B/1KB=214个，每个页面可存储页表项1KB/4B=256=28个，存储二级页表所需要的页面数为：214/28=26个<28个，则一级页表可以在一个页面内存储完成。

526245对应的二进制表示（斜线表示上述逻辑切分）：10/00 0000 01/11 1010 0101

按照上述划分方法得到：一级页号为2，二级页号1，页内地址0x03A5。

一级页表第2项查找到二级页表的物理块号：678

在678物理块的第1项找到物理块号889（0x0379），形成物理地址块号

与页内地址0x03A5拼接，形成完整的地址：

1101 1110 01/11 1010 0101→0xDE7A5（十进制：911269）

反置页表

物理块→逻辑块
也称为页寄存器（Page Register）
每个内存块关联：
使用位(Residence bit): 本页是否被占用
使用者(Occupier): 占用此块的页号
进程号
优点：存储开销小；页表大小与逻辑空间无关；全系统一张表
缺点：反向关联信息（页框号→页号），如何正向查询？

哈希算法：

哈希运算：h(PID, 页号)→页框号

查询过程计算h(p, i)，并作为索引访问反置页表；

获取反置页表项；

如果匹配(pid, 页号)，命中；

否则，不命中。

页式存储小结

优点：
解决了碎片问题
便于管理
缺点：
页表的开销大
共享不便，保护不便：语义边界不清晰

段式存储管理

每个段可有其逻辑意义及功能，使得便于：编写程序、分段共享、分段保护、动态链接、动态增长。

基本概念

用户空间划分

按程序自身逻辑关系划分为若干段，如代码段、数据段。
可针对不同类型段采取不同的保护
以段为单位共享，包括通过动态链接进行代码共享
每个程序段都有一个段名，且有一个段号
段号从0开始，段内从0开始编址
段内地址是连续的

内存空间划分

内存空间被动态划分为若干个长度不等的区域，这些区域被称为物理段：(起始地址，长度)
内存分配

以段为单位分配内存，每一个段在内存中占据连续空间
各段之间可以不连续存放
进程段表

段号，段的首址和长度之间的关系。
每一个程序设置一个段表，放在内存，属于进程的现场信息

段号

基址

长度

0

40K

30K

1

80K

20K

2

120K

15K

3

150K

10K

[评价]

优点

分段对程序员是可见的，是一种方便的组织程序和数据的手段，便于模块化程序设计
便于保护和共享
缺点

进程全部装入内存

段式地址变换

分段系统共享editor

分配（类似动态分区）

系统段表
系统内所有占用段
空闲段表
记录空闲段起始地址和长度，可以结合到系统段表中
内存分配算法
首先适配；最佳适配；最坏适配

与分页的比较

分页是出于系统管理的需要，分段是出于用户应用的需要。
一条指令或一个操作数可能会跨越两个页的分界处，而不会跨越两个段的分界处。
页大小是系统固定的，而段大小则通常不固定。
逻辑地址表示：分页是一维的：引用时是统一的地址；分段是二维的，与程序逻辑一致：引用时段名+偏移；
通常段比页大，因而段表比页表短，查找快，提高访问速度。
段式管理碎片问题比页式管理严重
与动态分区不同：一个程序可以占据多个段，段不要求连续。

段页式存储管理

分页优点：提高内存利用率

分段优点：方便用户，易于共享，保护，动态链接

段页式系统：综合优点

基本思想

用户程序按段式划分
内存页式存储管理方案
内存分配：以页为单位进行分配

对用户而言，仍然是二维编址。
对系统而言，则是三维编址

地址映射

地址变换

地址变换实例

练习：

设一个地址空间有8个页，每个页面大小为1024个字节，映射到32块物理页面的主存上。试问：

逻辑地址要用多少位表示？13

物理地址要用多少位表示？15

答：

逻辑地址：8*1024=2^3*2^10=2^13（所以逻辑地址的后13位为“页内地址”，又叫“页内偏移量”，或“页内位移”及有效位）

再算物理地址：32*1024=2^5*2^10=2^15

所以最后的就是逻辑有效位是13；物理有效位是15.

虚拟存储器

允许执行只有部分在内存中的程序

程序不受现有物理内存空间限制，用户只对一个大的虚拟地址空间写程序，简化了编程操作

提高程序执行的并发性、CPU利用率

基本概念

常规存储器的问题

常规存储
一次性，驻留性
覆盖和交换可以减轻这一限制
有时，并不需要将整个程序放入内存中
程序中的异常分支
数组通常分配了比实际所需要更多的内存
程序的某些选项或特点可能很少使用
虚拟存储器的目标

允许执行只有部分在内存中的程序
程序不受现有物理内存空间限制，用户只对一个大的虚拟地址空间写程序，简化了编程操作
提高程序执行的并发性、CPU利用率

局部性原理

程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。
时间局部性（Temporal Locality）
如果程序中的某条指令一旦执行，则不久以后该指令可能再次执行；如果某数据被访问过，则不久以后该数据可能再次被访问。
空间局部性（Spatial Locality）
若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。

虚拟内存

具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
逻辑容量由内存容量和外存容量之和所决定
运行速度接近于内存速度
成本接近于外存
原理
在程序装入时，只需将当前需要执行的部分读入内存，就可让程序开始执行。
在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页或段调入内存，然后继续执行程序。
另一方面，操作系统将内存中暂时不用的页或段调出保存在外存上，腾出空间存放将要调入的页或段。
虚拟内存大于物理内存
实现方法
虚拟页式——请求分页(Demand Page)
虚拟段式——请求段式调度(Demand Segmentation)
虚拟段页式

虚拟页式

在简单页式存储管理的基础上，增加请求调页和页面置换功能。

请求分页

页表：与简单分页相比，增加了如下位：

P：表示该页是否在内存中

A：访问位，是否被访问过

M：修改位，从上次装入到现在是否已经改变

外存地址

地址转换流程

内存分配、置换策略

分配策略：固定分配，可变分配

置换策略：全局置换，局部置换

可组合出以下三种适用的策略：

固定分配局部置换(Fixed Allocation, Local Replacement)
可变分配全局置换(Variable Allocation, Global Replacement)
可变分配局部置换(Variable Allocation, Local Replacement)

缺页中断处理

要访问的页不在内存，则产生缺页中断(page fault)。
操作系统接到此中断信号后，调用缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使作业继续运行下去
如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号
若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存

缺页中断在指令执行期间产生和处理，所缺的页面调入之后，重新执行被中断的指令。

系统颠簸/抖动

页面被频繁地换入换出
缺页率急剧增加，内存有效存取时间加长，系统吞吐量骤减；
系统已基本不能完成什么任务。
原因：CPU利用率太低→调度程序增加多道程序度→新进程启动运行→内存不足→缺页→I/O忙碌，CPU空闲。
防止系统颠簸/抖动
局部置换策略：如果一个进程出现抖动，它不能从另外的进程取帧。
挂起某些进程：优先级低、缺页进程、最大的进程等
利用工作集、缺页频率策略防止抖动

工作集

一个进程在某一段时间内访问页面的集合。（并非越大越好！）
如果页面正在使用，它就落在工作集中；
如果不再使用，它将不出现在相应的工作集中，所以，工作集是程序局部性的近似表示。
工作集：W(t, Δt)，(t-Δt, t] 内访问的页面集合。
虚拟时间t：页面访问点
时间窗口Δt
太小，不能包含整个局部；
太大，是进程执行所碰到的所有页的集合。
避免抖动方法
OS监视每个进程的工作集
新增页面分配内存。
淘汰不在工作集中的页面。
若有足够多的额外内存块，就可装入另一个进程。
如果所有工作集之和超过了可用内存，则OS选择挂起一个进程，把它的页换出，将其内存块分配给其它进程。
工作集的估算不容易：Δ

页面替换/置换算法

最佳算法（OPT）

选择替换下次访问距当前时间最长的那些页。

特点

缺页错误率最低，没有Belady现象；
必须知道页面未来的访问顺序→不可能实现。
仅作为一种标准，用于测试其他算法的性能。

先进先出算法(First in First Out，FIFO)

替换驻留在主存中时间最长的页

注意：驻留时间和访问时间无关

实现：将分配给进程的页帧看作FIFO队列，按循环方式移动页：置换队列的首页，调入的新页加入队尾。

问题：FIFO策略实现简单，但性能相对较差。

Belady异常：有些情况下，缺页率可能会随着所分配帧数的增加而增加。

练习：

页面请求序列：3 2 1 0 3 2 4 3 2 1 0 4 分别计算使用FIFO算法，分配3个Frame和4个Frame时产生page fault的次数。

最近最久未使用算法(LRU, Least Recently Used)

替换主存中上次使用距离当前最远的页（最长时间没有使用的页）

可以理解为向后看最优置换算法：根据局部性原理，这也是最近最不可能访问到的页。

性能接近OPT，但历史不等于未来

实现：
计数器：每个页添加逻辑时钟或计数器，访问页面时加1，定时减1（或寄存器移位）。在淘汰时，选择该值最小的页面。
比较开销
堆栈：页面被访问，该页就从堆栈中提到顶部，底部是目前最少使用的页。

Clock算法

改进Clock算法

增加修改位M

由(A, M)可以组合成四种页面：

(A=0, M=0)：表示该页最近既未被访问，又未被修改，是最佳淘汰页。

(A=0, M=1)：表示该页最近未被访问，但已被修改，若替换要被写回。

(A=1, M=0)：最近已被访问，但未被修改，该页有可能再被访问。

(A=1, M=1)：最近已被访问且被修改，该页可能再被访问。

步骤：

从指针所指示的当前位置开始，扫描循环队列，寻找(A=0, M=0)的第一类页面，将遇到的第一个页面作为淘汰页，如未找到，转第2步；

同样扫描方法，寻找(A=0, M=1)的第二类页面，将遇到的第一个此类页面作为淘汰页。将所有扫描过的页面的访问位A置0。若未找到，转第1步。

其他置换算法

最不经常使用算法LFU(Least Frequently Used)
访问频繁→访问记数大
例外：一个页在进程开始时使用得很多，但以后就不再使用
定期将次数寄存器右移一位，形成指数衰减
关注访问次数，LRU关注上次访问时间
最常使用算法MFU(Most Frequently Used)
最小次数的页可能刚刚调进来，且还没有使用，不换出
页面缓冲算法PBA(Page Buffering Algorithm)
维护一个free page pool
换出页可稍后换出，避免调入时换出写磁盘

练习题

虚拟段式

请求分段

在简单段式存储管理的基础上，增加请求调段和段置换功能。
段表添加若干项：
存在位(present bit)
修改位(modified bit/dirty bit)
访问/使用位(use bit)
存取权限：如读R，写W，执行X
外存地址

动态地址变换和缺段中断：指令和操作数必定不会跨越在段边界上
程序运行时，先把当前需要的一段或者几段装入内存，其它段仅仅在调用时才装入。
地址变换过程