『Operating System』 Memory Management

存储层次

需求与目标, 存储管理的功能

需求

计算机使用角度:
1. 整个空间都能够使用.
2. 不希望任何因素阻碍程序的正常运行.
计算机平台角度 - 尽可能同时为多个程序提供服务.

分析:

计算机中至少同时存在两个程序: 一个用户程序和一个服务程序.

每个程序具有的地址空间应当是相互独立的.

每个程序使用的空间应当得到保护.

目标

地址独立: 程序发出的地址与物理地址无关.
地址保护: 未经允许, 一个程序不能访问另一个程序的存储空间.

存储管理的功能

存储分配与回收: 是存储管理的主要内容. 主要讨论其算法与相应的数据结构.
地址变换: 可执行文件生成中的链接技术, 程序加载时的重定位技术, 进程运行时硬件与软件的地址变换技术与机构.
存储共享与保护: 代码与数据共享, 对地址空间的访问权限(读, 写, 执行).
存储器扩充: 存储器的逻辑组织与物理组织.
- 由应用程序控制: 覆盖.
- 由操作系统控制: 交换(整个地址空间), 请求调入与预调入(部分进程空间).

基本概念

地址空间: 源程序经过编译后得到的目标程序, 存在于它所限定的地址范围内, 这个范围称为地址空间. 这是逻辑地址的集合.
存储空间: 存储空间是指主存中一系列存储信息的物理单元的集合, 这些单元的编号称为物理地址或绝对地址. 这是物理地址的集合.

单道程序的内存管理 - 静态地址翻译

静态地址翻译: 即程序运行前就计算出所有物理地址. 这一做法显然是满足存储管理目标的.

优点是显然的: 简单, 适用于单用户单任务的操作系统. 程序在运行过程中无需进行任何的地址翻译, 运行速度快.

缺点也很显然: 无法加载比物理内存大的程序, 存在资源浪费(小程序造成空间浪费, 不区分常用与非常用数据, I/O时间长会导致计算资源浪费).

多道程序的内存管理 - 分区

空间分配: 分区式分配

把内存分为一些大小相等或不等的分区, 每个应用程序占用一个或几个分区. 操作系统占用其中一个分区.
适用于多道程序系统和分时系统, 支持多个程序并发, 但难以进行内存分区的共享.

碎片: 内存中无法被利用的存储空间.

内碎片: 给作业分配的存储空间中未被利用的部分. 即被分配了但事实上没有被利用.

外碎片: 系统中无法利用的小的空闲分区. 如分区与分区之间狭小的空间. 外碎片是导致内存系统性能下降的主要原因, 可以使用紧凑技术消除外碎片.

固定式分区 - 程序适应分区

当系统初始化时, 把存储空间划分为若干个任意大小的区域, 然后把这些区域分配给每一个用户作业.

分区大小相等: 只适用于多个相同的程序并发执行.
分区大小不等: 多个小分区, 适量的中等分区, 少量的大分区. 根据程序的大小, 分配当前空闲且大小适当的分区.

这一做法的优点是易于实现, 开销小; 而缺点是内碎片造成浪费, 分区总数固定, 限制了并发执行的程序数目.

实现方式有: 单队列, 多队列.

可变式分区 - 分区适应程序

分区的边界可以移动(即大小可变).

这一做法的优点是没有内碎片; 而缺点是外碎片造成浪费.

闲置空间管理

位图表示法: 给每一个分配单元赋予一个二进制位(bit), 用于标识此单元是否闲置.

空间成本固定: 不依赖于内存中的程序数量.
时间成本低: 操作简单, 仅需直接修改对应二进制位即可.
容错能力差: 某一分配单元为 1 , 不能肯定是确实为 1 , 还是因干扰而变成了 1 .

链表表示法: 将闲置的单元使用空闲链表连接起来, 将被分配的单元用占用链表连接起来.

空间成本: 取决于程序的数量.
时间成本: 链表的扫描速率较慢.
有一定的容错能力: 因为链表有空闲链表和占用链表两支, 可以互相验证.

这两种方法不仅适用于分区式内存管理, 还适用于后文的分页式内存管理.

基于顺序搜索的分配算法

首次适应算法 - First Fit

每个空白内存区域按其在存储空间中地址递增的顺序连接在一起, 在为作业分配存储区域时, 从这个空白内存区域的始端开始查找, 选择第一个足以满足请求的空白内存区域.

优先利用内存低地址部分的空闲分区, 但由于低地址部分不断被划分, 留下了许多难以利用的小空闲块, 而每次查找又都是从低地址部分开始, 增加了查找可用的空闲块的开销.

下次适应算法 - Next Fit

把存储空间中的空白内存区域连接为一个循环链表, 每次为存储请求查找合适分区时, 总是从上一次查找结束的地方开始, 只要找到一个足够大的空白内存区域, 就将它划分后分配出去.

使存储空间的利用更加均衡, 不致使小空闲块集中在存储空间的某一段, 但这会导致缺乏大的空闲块.

最佳适应算法 - Best Fit

为一个作业选择分区时, 总是寻找大小最接近于作业需求的空白内存区域.

往往使得剩下的空闲块非常小, 从而在存储空间中留下许多难以利用的小空闲块.

最坏适应算法 - Worst Fit

为一个作业选择分区时, 总是寻找最大的空白内存区域.

分配内存后剩下的空闲分区也比较大, 可以装下其他作业. 但由于最大的空闲分区总是首先被分配和划分, 因此当有大作业到来时, 其存储空间的申请往往得不到满足.

基于索引搜索的分配算法

基于顺序搜索的动态分区分配算法一般只适用于较小的系统, 若系统的内存分区很多, 空闲分区表(链)可能很大(很长), 检索的速率比较慢. 为提高搜索空闲分区的速率, 大中型系统采用基于索引搜索的动态分区分配算法.

快速适应算法

快速适应算法, 又称分类搜索法, 把空闲分区按容量大小进行分类, 经常用到的长度的空闲块设立单独的空闲块链表. 系统为多个空闲链表设立一张管理索引表.

优点: 查找效率高, 进需要根据程序长度, 寻找能够容纳它的最小空闲块链表, 取下第一块进行分配即可. 该算法不会对任何分区进行分割, 所以能够保留大的分区, 也不产生内碎片.

缺点: 在分区归还给主存时算法复杂. 分配空闲分区时以进程为单位, 一个分区只属于一个进程, 存在一定的浪费. 这是以空间换时间的算法.

伙伴系统

在分配存储块时, 将一个大存储块分裂为两个大小相等的块, 称他们为”伙伴”.

伙伴系统规定: 无论是已分配的分区还是空闲分区, 其大小均为 $2^k(k\in\mathbf{Z}, n\le k\le m)$ , 其中 $2^n$ 为能够分配的最小分区大小, $2^m$ 为整个空间的大小.

利用了计算机二进制寻址的优点, 加速了相邻空闲分区的合并.

可重定位分区分配

定时地或在内存紧张时, 移动某些已经分配内存空间的信息, 将存储空间中所有的空白块合并为一个大的连续块.

可重定位下的程序的链接和装入

程序的链接

静态链接: 用户的一个工程所需的多个程序采用静态链接的方式链接在一起. 当我们希望共享库的函数代码直接链接入程序代码中, 也采用静态链接方式.
动态链接: 用于链接共享库代码. 当程序运行中需要某些目标模块时, 才对它们进行链接, 具有高效且节省内存空间的优点. 但相比于静态链接, 使用动态链接库的程序相对慢.

程序的装入

由于程序的位置可重定位, 因此一般采用动态运行时装入方式, 这种方式需要一个重定位寄存器来支持, 在程序运行过程中进行地址转换.

多重分区分配

多重分区分配是指: 一个作业由相对独立的程序段与数据段组成, 将这些片段分别装入到存储空间中不同的区域内.

关于C语言中的内存空间, 在此文已有详细解说, 本文不再赘述.

多道程序的内存管理 - 分页

基本思想: 将逻辑地址连续的程序分散存放到若干不连续的物理内存中, 并保证程序的正确执行, 则既可以充分利用内存空间, 又可以减少内存块移动带来的开销.

纯分页系统

在分页存储管理方式中, 如果不具备页面交换功能, 则必须将作业的所有页面一次性装入到主存的物理页框中; 若当前空闲物理页框数不足, 则该作业必须等待.

基本概念

页面: 把作业的地址空间划分为一些大小相等的片段, 这些片段就是页面, 或称虚页, 或简称页.
页框: 把主存的存储空间划分为与页面大小相同的片段, 这些片段就是页框, 或称实页, 存储块.

对于一个逻辑地址 $A$ , 页面大小为 $L$ , 则(虚)页号 $P$ , 和页内偏移 $d$ 为:

\[P = \left\lfloor\frac{A}{L}\right\rfloor,\quad d = A - P\]

数据结构

进程页面表: 每一个进程有一个页表, 描述该进程占用的物理页面及逻辑排列顺序.
物理页框表: 整个系统有一个物理页框表(位图, 链表), 描述物理内存空间的分配使用情况.
请求表: 整个系统有一个请求表, 描述系统内各个进程页表的位置与大小, 用作地址转换, 也可以结合到各进程的控制块中.

页面大小

页面大小是由硬件决定的, 通常是 $2^n(n\in\mathbf{Z})$ 的大小. 对于这样的页面大小, 若逻辑地址宽度为 $m$ (即逻辑地址空间大小为 $2^m$ ), 则逻辑地址的高 $m-n$ 位表示页号(页表索引), 低 $n$ 位表示页内偏移.

现代操作系统中, 常用页面大小是 4KB.

若页面较小:

减少了页内碎片和总的内存碎片, 有利于提高内存利用率.

每个进程的页面数增多, 使页表长度增加, 增加了内存开销.

页面换进换出速度将降低.

若页面较大:

每个进程页面数减少, 页表长度减少, 占用内存较小.

页面换进换出速度将提高.

增大了页内碎片, 不利于提高内存利用率.

假设进程平均占用 $s$ 个字节, 页面大小是 $p$ 个字节, 一个页表项约占 $e$ 字节. 则分页的开销为: $\displaystyle\frac{s\times e}{p}+\frac{p}{2}$

由均值不等式可得:

\[\frac{s\times e}{p}+\frac{p}{2}\ge2\sqrt{\frac{s\times e}{2}}=\sqrt{2se}\]

当且仅当 $\displaystyle\frac{se}{p}=\frac{p}{2}$ 时等号成立, 此时页面大小 $p$ 为 $\sqrt{2se}$ .

可重入代码

可重入代码又称纯代码, 是一种允许多个进程同时访问的代码. 不允许任何进程对其进行修改.

一级页表

一级页表下的地址转换

一级页表的问题

若逻辑地址空间很大, 则划分的页就比较多, 页表将占用很大的连续空间. 比如, 对于48位的逻辑地址空间的分页系统, 若规定页面大小为4KB, 则页表需要由2³⁶页组成. 若一个页表项占8B, 则页表就需要占用512GB的空间, 这显然是不可接受的.

解决此问题的方法有:

动态调入页表
多级页表

两级页表

将页表进一步分页, 离散地将各个页表页面存放在不同的物理块中, 同时建立一张页目录用以记录页表页面对应的物理块号.

正在运行的进程, 必须将页目录调入内存, 而动态调入内部页表.

二级页表下的地址转换

页目录的自映射

以地址空间为4GB, 页面大小为4KB的常见情况为例:

若页表的基地址为 PTBase, 该基地址需要4MB对齐, 因此:

PTBase & 0x3fffff == 0

页目录的基地址 PDBase:

PDBase == PTBase + (PTBase >> 10)

自映射页目录项 PDE_SelfMapping:

PDE_SelfMapping == PDBase + (PTBase >> 20)

多级页表

确定虚地址的最小位数

某些系统中提供了64位的字长, 但是实际上不是64位页式存储系统.

举例: 64位系统中, 如果采用三级页表机制, 页面大小为4KB.

由于64位系统中字长为8B, 且页目录也占用一页. 因此, 页目录中有512项, 也就是说, 每级页表都需要9位. 因此三级页表管理下, 总共需要3×9+12=39位. 并不需要64位.

自映射

考虑上述39位三级页式存储系统, 地址空间为512GB. 若页表基地址为 PTBase, 则有:

页目录基地址为 PDBase:

PDBase == PTBase + (PTBase >> 9) + (PTBase >> 18)

自映射页目录项 PDE_SelfMapping:

PDE_SelfMapping == PDBase + (PTBase >> 27)

页表快速访问

页表机制的问题:

页表机制带来的严重问题就是内存访问效率严重下降. 由一个虚地址访问到实地址, N 级页表机制将需要 N+1 次内存访问, 其中前 N 次是访问页表.

MMU

为提高地址转换效率, CPU内部增加了一个硬件单元MMU(Memory Management Unit, 存储管理单元), 其内部包含:

页表Cache: TLB, 用于存放虚地址与相应的实地址.
TLB控制单元: TLB内容填充, 刷新, 覆盖, 以及越界检查.
页表查找单元: 若TLB未命中, 自动查找多级页表, 将找到的实地址送TLB控制单元.(可用软件实现)

MMU的工作过程:

MMU得到虚地址后先在TLB中内查找, 若没有找到匹配的PTE(Page Table Entry, 页表项), 则到页表中查询, 并将页表项存入TLB.
根据PTE中对访问权限的限定, 检查当前访存指令是否符合权限, 若不符合则抛出异常.
检查该地址是否已映射到物理地址, 若尚未映射到内存则引发缺页异常.
若符合权限且已映射到内存, 则组合出物理地址, 完成MMU的工作.

其中, TLB即为快表, 又称联想存储器. 它其实是一种特殊的Cache, 内容是页表中的一部分或全部内容.

通常, TLB 中条目数并不多, 在 64 到 1024 之间.

CPU也产生逻辑地址的页号, 首先在TLB中寻找, 若命中就找出其对应的物理块; 若未命中, 再到页表中找其对应的物理块, 将其复制到TLB, 若TLB已满, 则按某种算法淘汰某些页.

有的 TLB 允许有些条目固定下来. 通常内核代码的条目固定下来.

TLB还有一些特性:

有的TLB在每个TLB条目中还保存着ASID(Address Space Identifier, 地址空间标识码). ASID可用来唯一标识进程, 并为进程提供地址空间保护. 当TLB试图解析虚拟页号时, 它确保当前运行进程的ASID与虚拟页相关的ASID匹配. 若不匹配, 则引发TLB失效.
除了提供地址空间保护外, ASID允许TLB同时保存多个进程的条目. 如果TLB不支持独立的ASID, 每次切换进程时, TLB需要被刷新或清除, 以确保下一进程不使用错误的地址转换.

哈希页表

考虑地址由页内偏移 $d$ 和的虚页号 $p$ 组成. 可以使用哈希函数 $h(\cdot)$ 进行虚页号转换. $h(p)$ 作为地址去访问哈希地址表, 从中找到实页号, 与页内偏移 $d$ 拼接形成物理地址.

反置页表

一般意义上, 每个进程都有其对应的页表. 该进程使用的每一个页都在页表中有一项. 这种方法的缺点之一, 是每一个页表可能有很多项. 这些表可能需要耗费大量的物理内存, 却仅用来跟踪物理内存是如何使用的. 为解决这个问题, 可以使用反置页表.

反置页表不是依据进程的逻辑页号来组织的, 而是依据该进程在内存中的物理页号来组织的, 其表项的内容是逻辑页号及其隶属进程的标识符. 反置页表的大小仅与物理内存大小有关.

64bit-PowerPC, UltraSparc 等处理器用的就是反置页表.

利用反置页表进行地址变换的方法:

用进程标识符和虚页号遍历反置页表.
若检索完整个页表, 均未找到与之匹配的页表项, 则表明此页尚未调入内存. 对于具有请求调页功能的存储器系统而言, 将产生调页中断, 否则将引发地址异常.
若检索到与之匹配的项, 则表项的序号就是物理块号, 将此块号与页内偏移拼接, 即可得到物理地址.

反置页表的问题

可能需要遍历整张表来寻找匹配项.

可以引入哈希页表来限制页表条目或加入 TLB 来改善.
难以共享内存.

页保护与页共享

页保护 - 页式存储系统提供了两种方式:

地址越界保护
在页表中设置保护位

页共享 - 带来一些问题:

若共享数据和不共享数据被划分到同一页中, 则会导致不共享数据也被共享, 影响保密性.

多道程序的内存管理 - 分段

最好的数据共享方式.

方便编程:

通常一个作业由多个程序段和数据段组成, 用户一般按逻辑关系对作业分段, 并能根据名字来访问程序段和数据段.

信息共享:

共享是以信息的逻辑单位为基础的. 页是存储信息的物理单位, 段是存储信息的逻辑单位.
页式管理中地址空间是一维的, 主程序, 子程序都顺序排列, 共享公用子程序比较困难, 一个共享过程可能需要几十个页面. 而段式管理中地址空间是二维的, 根据段号与偏移量来访问物理内存.

信息保护:

页式管理中, 一个页面可能装有两个不同的子程序段的指令代码, 不能通过页面共享来实现共享一个逻辑上完整的子程序或数据块.
段式管理中, 可以以信息的逻辑单位进行保护.

动态增长:

实际应用中, 某些段(数据段)会不断增长, 前面的存储管理方法难以实现.

动态链接:

动态链接在程序运行时才把主程序和要用到的目标程序(程序段)链接起来.

段式管理下的地址变换

其中段表其实也存在于内存中, 因此通过虚地址访问实地址需要两次访存.

分段管理的优缺点

优点: 易于实现段共享(仅需在段表中使其映射到同一物理位置即可), 易于实现段保护.
缺点:
- 地址变换增加了系统开销, 段表的存储增加了存储开销.
- 为满足分段的动态增长和减少外碎片, 需要采用拼接手段.
- 在辅存中管理不定长度的分段困难较多.
- 分段的最大尺寸收到主存可用空间的限制.

多道程序的内存管理 - 分段&分页

分段方法来分配和管理虚拟内存, 分页方法来分配和管理物理内存.

实现原理

先将用户程序分为若干个段, 再把段内分为若干个页.
地质结构由段号, 段内页号和页内偏移三部分组成.
系统中设段表和页表, 均存放于内存中. 从虚地址访问实地址需要三次访存. 为提高速度, 可以采用高速缓冲寄存器.
每个进程设一张段表, 每个段设一张页表.
段表中含段号, 页表基地址和页表长度; 页表中含页号和块号.

段页式管理下的地址变换

虚拟存储

覆盖与交换 - 突破物理内存限制

覆盖 (节约, 时间上扩展)
- 重用内存
- 突破内存占用空间一致性
交换 (借用, 空间上扩展)
- 外部存储
- 页面调度
- 突破内存占用时间一致性

覆盖

覆盖管理, 就是将一个大程序划分为一系列覆盖, 每一个覆盖是一个相对独立的程序单位.

称一组覆盖为覆盖段, 是指这些覆盖在程序执行过程中不要求同时装入内存. 一个覆盖段被分配到同一个存储区.

覆盖管理要求程序员编程时划分程序模块和确定程序模块之间的覆盖关系, 增加了编程的复杂度.

交换

交换管理, 广义地说, 就是将暂时不用的某个(或某些)程序以及其数据的部分或全部从内存移到外存中去, 以便腾出必要的存储空间; 接着把指定程序与数据从外存读取到相应的内存块中, 并将控制权交给它.

这种做法的优点是增加了并发运行的程序数目, 并且给用户提供了适当的响应时间; 编写程序时不影响程序结构; 缺点是换入与换出的控制增加了开销, 程序整个地址空间都被传送, 没有考虑执行过程中地址访问的统计特性.

虚拟存储器

局部性原理

局部性原理是指程序在执行过程中一个较短的时期内, 所执行的指令地址和指令的操作数地址, 分别局限在一定区域内. 还可以表现为:

时间局部性: 即一条指令的一次执行和下一次执行, 一个数据的一次访问和下一次访问都集中在一个较短的时期内.
空间局部性: 即当前指令和相邻的几条指令, 当前访问的数据和相邻的数据都集中在一个较小的区域内.

程序局部性:

程序在执行时, 大部分是顺序执行指令, 少部分是转移和过程调用指令.

过程调用的嵌套深度一般不超过 5, 因此执行的范围不超过这组嵌套的过程.

程序中存在相当多的循环结构, 它们由少量指令组成, 而被多次执行.

程序中存在相当多对一定数据结构的操作, 如数组操作, 往往局限在小的空间范围内.

虚拟存储技术

既要 “覆盖”, 又要 “交换”.

虚拟存储为每一个进程都提供了一个大的, 一致的, 连续可用的和私有的地址空间, 它提供了3个能力:

给所有进程提供一致的地址空间, 每一个进程都认为自己是在独占使用单机系统的存储资源;
保护每一个进程的地址空间不被其他进程破坏, 隔离了进程的地址访问;
根据缓存原理, 虚拟存储中将内存看作磁盘的高速缓存, 在内存和磁盘之间根据需要传输数据, 高效地利用了内存.

基本原理:

按需装载: 在程序装入时, 不必将其全部读入到内存, 而只需要将当前需要执行的部分页面或段读入到内存, 就可以让程序开始执行.
缺页调入: 在程序执行过程中, 如果需要执行的指令或访问的数据尚未在内存中, 处理器将引发缺页中断, 通知操作系统将相应的页面或段调入到内存, 然后继续执行程序.
不用调出: 操作系统将内存中暂时不用的页面或段调出保存在外存中, 从而腾出空间存放将要装入的程序以及将要调入的页面或段(请求调入和置换), 只需程序的一部分在内存中就可以执行, 对于动态链接库也可以请求调入.

虚拟存储技术具有4个显著特征: 离散性, 分时复用, 对换性, 虚拟性.

离散性: 物理内存分配的离散性, 虚拟地址空间使用的离散性.
分时复用: 作业被分成多次调入内存, 正是由于分时复用, 虚拟存储器才具备了逻辑上扩大内存的功能. 分时复用的特性是虚拟存储器的最重要特征, 其他任何的存储器均不具备这个特征.
对换性: 允许在作业运行过程中进行换进换出, 这提高了内存的利用率.
虚拟性: 允许程序从逻辑角度访问存储器, 而不需要考虑物理内存中可用的空间数量.
- 范围大, 但占用的容量不超过内存与外存中交换区之和.

虚拟性以分时复用和对换性为基础, 分时复用和对换性以离散性为基础.

虚拟存储的最大容量由计算机的地址结构决定, 如 32 位机器的虚拟存储最大容量为 4GB.

请求分页(段)系统

在分页(段)系统的基础上, 增加了 请求调页(段) 功能, 页(段)置换 功能.

它允许只装入若干页(段)的用户程序和数据, 便可启动运行, 以后在硬件支持下通过调页(段)功能和置换页(段)功能, 陆续将要运行的页(段)调入内存, 同时将暂不使用的页(段)置换到外存, 置换时以页(段)为单位.

需提供相应的软硬件支持:

硬件: 页(段)表机制, 缺页(段)中断机构和地址变换机构.
软件: 请求调页(段), 页(段)置换.

调入

三个问题:

什么程序和数据调入主存?

OS 的内核部分

正在运行的进程相关的程序与数据

什么时候调入主存?

OS 在系统启动时调入

进程的调入取决于调入策略: 预调页, 按需调页

怎样调入主存?

缺页中断

调入的时机

预调页

当进程开始时, 所有页面都在磁盘上, 每一个页面都需要缺页中断调入内存. 预调页可以同时将所有需要的页一起调入内存, 从而防止了大量的缺页中断.

实际应用中, 可以为每一个进程维护一个当前工作集中的页列表, 如果进程在暂停之后需要恢复, 则根据这个列表, 使用预调页的方式将工作集中的页面一次性调入内存.

按需调页

当且仅当需要某页面时, 才将该页面调入内存.

按需调页系统类似于使用交换技术的分页系统.

按需调页需要使用备份存储, 保存不在内存中的页面.

缺页中断

现场保护: 陷入内核态, 保存必要信息.
页面定位: 查找发生缺页中断的虚页. 这个虚页的信息通常保存在硬件寄存器中, 若没有的话, 操作系统需要检索程序计数器, 取出并分析指令, 找出缺页中断的虚拟页面.
权限检查: 检查虚地址的有效性及安全保护位. 若发生保护错误, 则杀进程.
页面调入(1): 查找一个空闲页框, 若没有空闲页框则需要通过页面置换算法找出一个换出的页框.
旧页面写回: 若找到的页框中内容被修改了, 则需要将修改的内容保存到磁盘(此时将页框置为忙状态, 防止页框被其他进程抢占).
页面调入(2): 操作系统将保存在磁盘上的页面复制到空的页框中.
更新页表: 当磁盘的页面内容全部装入页框后, 像操作系统发出中断信号. 操作系统更新页表项, 将页框恢复为正常状态.
恢复进程: 恢复现场, 让程序重新执行引发缺页中断的指令.

需要注意的是: 旧页面写回和页面调入 (2) 均涉及磁盘操作, 这时将引发磁盘读写调用, 发生上下文切换. 在等待磁盘读写的过程中, 处理器将服务其他进程.

置换

最优置换(OPT)

预知未来是无法实现的.

OPT算法置换掉未来最久不用的页面. 这个算法通常用于比较研究, 衡量其他页面置换算法的效果.

先进先出(FIFO)

操作系统记录每一个页面被调入内存的时间, 当必须置换出某一个页面时, 选择最早进入页框的页面进行置换.

这种算法的性能较差. 较早调入的页面往往是经常被访问的页面, 这些页面在FIFO算法中反复被调入和调出. 并且存在Belady现象.

Belady现象

Belady现象: 在使用FIFO算法时, 页框越多, 缺页率反而提高的现象.

这里在页面置换中提 FIFO 的 Belady 现象, 并不是说只有在页面置换中才会有这样的现象. 在使用 FIFO 作为缓存算法时, 也会遇到增加缓存容量, 命中率反而下降的现象.

改进FIFO - Second Chance

基本思想是: 若被淘汰的数据之前被访问过, 则给其第二次机会.

每一个页面增加一个访问标识位, 用于标识此页面放入页框后是否被再次访问过.
假设A是队列头部页面, 此时需要将队列中某一页面置换到外存. 若A在进入队列后没有被访问过, 则A被淘汰; 否则将A移到队列尾部, 并将访问标识位清除. 以此方法选择出一个被置换的页面.

改进Second Chance - CLOCK

CLOCK算法又称最近未使用算法. 使用环形队列, 避免将数据在FIFO队列中移动:

需要置换出某一页面时, 若当前指针指向C. 若C有访问标识, 则清除C的访问标识, 并将指针指向C的下一页面; 若C没有访问标识, 则将新页面放入C的位置, 并置访问标识位, 将指针指向下一页面.

FIFO类算法对比

命中率: CLOCK = Second Chance > FIFO
复杂度: Second Chance > CLOCK > FIFO
代价: Second Chance > CLOCK > FIFO

FIFO 类算法的命中率相比其他算法要低, 实际应用中很少使用此类算法.

最近最少使用(LRU)

LRU算法是根据数据的历史访问记录来进行淘汰数据的算法. 这是局部性原理的合理近似, 是性能接近最优的算法.

设置一个特殊的栈, 保存当前内存中的各个页面的页面号.
当内存中的某页面被访问时, 就将其从栈中移出, 压入栈顶. 栈底始终是最近最少使用的页面.

LRU 算法的硬件开销很大. 老化算法是 LRU 的简化, 性能接近 LRU:

为每个页面设置一个移位寄存器, 并设置以为访问位 R, 每隔一段时间, 所有的寄存器右移一位, 将 R 的值从左移入.

当需要置换出某页面时, 相应寄存器中值最小的页面被置换.

置换中的更新问题

当一个页面被换出时, 需要保持内存与外存的信息一致性. 必要时进行信息更新:

若换出页面是file backed类型:
- 若未被修改, 则直接丢弃.
- 若已被修改, 则写回原有位置.
若换出页面是anonymous类型:
- 若未被修改:
  - 若是第一次换出, 则写入Swap区.
  - 若非第一次换出, 则直接丢弃.
- 若已被修改:
  - 则写入Swap区.

有关 file backed 与 anonymous:

用户的可执行文件以及共享库都是以文件形式存储在磁盘中的, 其类型为 file backed.

堆和栈在磁盘上没有对应文件, 其类型为 anonymous.

工作集与驻留集

工作集: 当前正在使用的页面集合
驻留集: 虚拟存储系统中, 每个进程驻留在内存的页面集合, 或者进程被分到的物理页框集合.

工作集策略

引入工作集, 是为了根据进程在过去一段时间内访问的页面来调整驻留集.

定义二元函数 $W(\Delta, t)$ , 其中 $t$ 为当前时刻, $\Delta$ 为窗口大小, 函数值表示 $[t - \Delta, t]$ 内访问的页面集合. $W(\Delta, t)$ 是关于 $\Delta$ 不减的函数.

工作集的大小变化: 进程开始执行后, 随着访问新页面的进行, 逐步建立其较稳定的工作集. 当内存访问的局部性区域的位置大致稳定后, 工作集的大小页也大致稳定; 局部性区域的位置改变时, 工作集快速扩张与收缩过渡到下一个大小稳定的状态.

监视每一个进程的工作集, 周期性地从该进程的驻留集中移去那些不在工作集中的页面, 只有当一个进程的工作集在内存中时才可以执行.

通过工作集来调整驻留集, 可以降低缺页率.
通过工作集尺寸来调整驻留集尺寸, 可以提高内存利用率.
优先调度工作集包含于驻留集的进程, 可以提高CPU的利用率.

获取精确工作集的困难:

工作集的过去变化未必能够预示其未来的变化.

记录工作集变化的开销大.

对工作集窗口大小 $\Delta$ 的取值难以优化.

驻留集管理

页框分配:

分配给每一个进程的页框数越少, 同时驻留内存的活跃进程数越多, 进程调度程序能够调度就绪进程的概率就越大, 然而这将导致进程缺页中断的概率变大;
分配给每一个进程的页框数越多, 也并不能显著降低其缺页中断概率.

抖动

随着驻留内存的进程增多, 也就是说进程的并发数增多, 处理器的利用率先上升后下降, 称这种现象为抖动. 每一个进程的常驻集规模缩小, 缺页率不断上升, 频繁调页使得调页的开销增大.

抖动的预防与消除

局部置换策略
引入工作集算法
预留部分页面
挂起若干进程

虚拟存储的其他技术

写时拷贝(Copy On Write)

两个进程共享同一块物理内存, 其中每个页面都被标识为写时复制. 共享的物理内存中每个页面都是只读的. 如果某个进程想要改变其中的某一个页面时, 就会与只读标识冲突, 系统将检测到写时复制标识, 在内存中复制一个对该进程私有的新页面, 进行写操作, 并建立新的虚页面到实页面的映射关系.

内存映射文件(Memory Mapped Files)

基本思想是: 将I/O变为访存, 简化读写操作, 允许共享. 在多数的实现中, 在映射共享页面时, 并不会实际读入页面的内容, 而是在访问页面时, 页面才被每次一页地读入, 磁盘文件则被当作后备存储.

当进程退出或显式地解除文件映射时, 所有被修改的页面会写回文件. 采用内存映射方式, 可以方便地让多个进程共享一个文件.