操作系统第三章-内存管理
[[toc]]
内存管理和进程管理是操作系统的核心内容，需要重点复习。
通过分页管理方式在物理内存大小的基础上提高内存的利用率，再进一步引入请求分页管理方式，实现虚拟内存， 使内存脱离物理大小的限制，从而提高处理器的利用率。
内存管理概念
- 为什么要进行内存管理？
在单道系统阶段，一个系统在一个时间段内只执行一个程序，内存的分配极其简单，即只分配给当前运行的进程。 引入多道程序后，进程之间共享的不仅仅是处理机，还有主存储器，然而，共享主存会形成一些特殊挑战，若不对 内存进行管理，则容易导致内存数据的混乱，以至于影响进程的并发执行。因此，为了更好地支持多道程序并发执行， 必须进行内存管理。
- 页式管理中每个表项大小的下限如何决定？
页表项的作用是找到该页在内存中的位置。
- 多级页表解决了什么问题？又带来了什么问题？
多级页表解决了当前逻辑地址空间过大时，页表的长度会大大增加的问题。而采用多级页表时，一次访盘需要多次访问内存甚至磁盘，会增加一次访存的时间。
内存管理的主要功能：
内存空间的分配与回收
地址转换
- 把逻辑地址转换为相应的物理地址
内存空间的扩充
- 主要是覆盖和交换技术
内存共享
内存保护
- 设置一对上下限寄存器
- 采用重定位寄存器和界地址寄存器
程序运行的基本原理
将用户源程序变为可在内存中执行的文件，通常需要以下步骤：
- 编译：由编译程序将用户源代码编译成若干目标模块，每个模块具有各自的逻辑地址空间。
- 链接：由链接程序将上述目标模块，以及所需库函数链接，形成具有完整的逻辑控制地址的装入模块。
- 装入：由装入程序将装入模块装入内存。
程序的链接
- 静态链接
在程序运行之前，先将各自目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。
- 装入时动态链接
将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的方式。其优点是便于修改和更新，便于实现对目标模块的共享。
- 运行时动态链接
对某些目标模块的链接，是在程序执行过程中需要该目标模块时才进行的。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到 装入模块上。其优点是能加快程序的装入过程，还可节省大量的内存空间。
内存的装入模块
- 绝对装入
绝对装入只适用于单道程序环境。程序中的逻辑地址与实际内存地址完全相同。
- 可重定位装入
在多道程序环境下，多个目标模块的起始地址通常都从0开始，程序中的其他地址都是相对与起始地址的。在装入时对目标程序中的指令和数据地址 的修改过程称为重定位，又因为地址变换通常是在进程装入时一次完成的，故又称静态重定位。当一个作业装入内存时，必须给它分配要求的全部内存空间， 若没有足够的内存，则无法装入，此外，作业一旦进入内存，整个运行期间就不能在内存中移动，也不能再申请内存空间。
- 动态运行时装入
也称动态重定位，装入程序把装入模块装入内存后，并不立即把装入模块中的相对地址转化为绝对地址，而是把这种地址转换推迟到程序真正要执行 时才进行。因此，装入内存后的所有地址均为相对地址，这种方式需要一个重定位寄存器的支持。
动态重定位的优点：可以将程序分配到不连续的存储区，便于程序的共享。
对重定位存储管理方式，应在整个系统中设置一个重定位寄存器。
逻辑地址与物理地址
编译完成后，每个目标模块都从0号单元开始编址，这称为该目标模块的相对地址（或逻辑地址）。 链接程序顺序依次按各个模块的相对地址构成一个统一的从0号单元开始编址的逻辑地址空间（或虚拟地址空间）。
进程在运行时，看到和使用的都是逻辑地址。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的。 不同进程可以有相同的逻辑地址。
物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从内存中存取。
当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。
逻辑地址通过页表映射到物理内存，页表由操作系统维护并被处理器引用。具体转换过程我们后面再讲。
进程地内存映像
- 代码段：即程序的二进制代码
- 数据段：即程序运行时加工处理的对象，包括全局变量和静态变量
- 进程控制快（PCB）：存放在系统区。操作系统通过PCB来控制和管理进程
- 堆：用来存放动态分配的变量
- 栈：用来实现函数调用，从用户空间的最大地址往低地址方向增长
内存保护
确保每个进程都有一个单独的内存空间。内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。
多进程在主存中彼此互不干扰的环境下允运行，操作系统是通过内存保护来实现的。
在CPU中设置一对上，下限寄存器，存放用户作业在主存中的下限和上限地址，每当CPU要访问一个地址时，分别和两个寄存器的值对比，判断有无越界
采用重定位寄存器（又称基地址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护。重定位寄存器含最小的物理地址值，界地址寄存器 含逻辑地址的最大值。内存管理机构动态地将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再 送交内存单元。
物理地址 = 逻辑地址 + 重定位寄存器中的值
内存共享
并不是所有进程内存空间都适合共享，只有那些只读的区域才可以共享。
内存分配与回收
在操作系统由单道向多道发展时，存储管理方式便由单一连续分配发展为固定分区分配，为了更好地适应不同大小的程序要求，又从 固定分区分配发展到动态分区分配。为了更好地提高内存的利用率，进而从连续分配方式发展到离散分配方式---页式存储管理，引入分段存储管理的 目的，主要是为了满足用户在编程和使用方面的要求。
覆盖与交换
覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法。
覆盖和交换的提出是为了解决主存空间不足的问题，但不是在物理上扩充主存，只是将暂时不用的部分换出主存，以节省空间，从而在逻辑上扩充主存。
覆盖：
由于程序运行时并非任何时候都要访问程序及数据的各个部分，因此可以把用户空间分成一个固定区和若干覆盖区。将经常活跃的部分放在固定区，其余部分 按调用关系分段。首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统再将其调入覆盖区，替换覆盖区中原有的段。
覆盖技术打破了必须将一个进程的全部信息装入主存后才能运行的限制，此外，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存。 覆盖技术对用户和程序员不透明
交换：
把处于等待状态（或在CPU调度原则下被剥夺运行权利）的程序从内存移到辅存，把内存空间腾出来，这一过程称为换出；把准备好竞争CPU运行的程序从 辅存移到内存，这一过程称为换入。
交换技术主要在不同进程（或作业）之间进行，而覆盖则用于同一个程序或进程中。对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的， 覆盖技术则已成为历史。
连续分配管理方式
| 分配方式 | 单一连续分配 | 固定分区分配 | 动态分区分配 |
|---|---|---|---|
| 说明 | 分为系统区和用户区 系统区仅供操作系统使用，通常在低地址部分 |
最简单的一种多道存储管理方式 | 又称可变分区分配，它是在进程装入内存时， 根据进程的实际需要，动态地为之分配内存， 系统中的分区的大小和数目是可变的 |
| 碎片 | 内部碎片 | 内部碎片 | 外部碎片 |
| 作业道数 | 1 | <= N(用户空间划为N块) | 不确定 |
| 硬件 | 界地址寄存器，越界检查机构 | 下界地址寄存器，越界检查机构 基地址寄存器，长度寄存器，动态地址转换机构 |
下界地址寄存器，越界检查机构 基地址寄存器，长度寄存器，动态地址转换机构 |
| 解决空间不足 | 覆盖 | 覆盖/交换 | 交换 |
外部碎片
动态分区开始时是很好的，但随着时间的推移，内存中会产生越来越多小的内存块，内存的利用率也随之下降。这些小的内存快称为外部碎片， 它存在与所有分区的外部，克服外部碎片可以通过紧凑技术来解决。
动态分区分配算法
| 算法 | 说明 | 特点 |
|---|---|---|
| 首次适应算法 | 空闲区以地址递增的次序链接 | 实现方法简单 查找速度快，平均性能最好 碎片多出现在低地址空间 |
| 邻近适应算法 | 又称循环首次适应算法 分配内存从上次查找结束的位置开始继续查找 |
平均性能比首次适应算法差 碎片多出现于高地址空间 |
| 最佳适应算法 | 空闲区按容量递增的次序形成空闲分区链 | 开销大，会产生最多的外部碎片 |
| 最坏适应算法 | 空闲区以容量递减的次序链接 | 使系统缺少大的连续空闲地址空间 |
上面的算法都是找到第一个满足要求的空闲区间，并且用户程序在主存中都是连续存放的。
动态分区是在系统运行过程中在作业装入时动态建立的。
非连续分配方式根据分区的大小是否固定，分为分页存储管理和分段存储管理。在分页存储管理中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分页存储管理和请求分页存储管理。
3.1.4 基本分页存储管理
固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低，这就引入了分页的思想：
把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块 作为单位逐个申请主存中的块空间。
页式管理中地址空间是一维的。
分页管理不会产生外部碎片
操作系统采用分页存储管理方式，要求每个进程拥有一张页表，且进程的页表驻留在内存中。
基本概念
进程中的块称为页（页面），内存中的块称为页框（页帧），外存也以同样单位进行划分，直接称为块。进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。
为了方便地址转换，页面大小应是2的整数幂。同时页面大小应该适中，页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；
页面过大又会使页面内碎片增多，降低内存的利用率。
页式管理中页面大小一旦确定，所有页面就是等长的（一般取2的整数幂），以便易于系统管理。
地址结构：
其中0-11位为页内地址，即每页大小为4KB;12-31位为页号，即最多允许\(2^{20}\)页。
地址结构决定了虚拟内存的寻址空间有多大。
为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立了一张页表，它记录页面在内存中对应的物理块号，页表一般存放在内存中。
页表的作用是实现从页号到物理块号的地址映射。
页表是由页表项组成的。
页表项：
| 页号 | 主存物理块号 |
|---|
页表项与地址都由两部分构成，而且第一部分都是页号，但页表项的第二部分是物理内存中的块号，而地址的第二部分是页内偏移，页表项的第二部分与地址的第二部分共同组成物理地址。
第n个页表项的物理地址 = 页表首地址 + n
* 一个页表项所占地址的个数。
硬件支持：页表寄存器（PTR）,存放页表在内存的始址和页表长度。
基本地址变换机构
设页面大小为L，逻辑地址A到物理地址E的变换过程如下：（假设下面都是十进制数）
- 计算页号
P(P = A/L)和页内偏移量W(W = A % L) - 比较页号P和页表长度M，若\(P \geq M\)，则产生越界中断，否则继续执行。
- 页表中页号P对应的页表项地址 = 页表始址F + 页号P x
页表项长度，取出该页表项内容
b，即为物理块号。 - 计算
E = b * L + W,用得到的物理地址E去访问内存。
notes:
页表长度是指一共有多少页，页表项长度是指页地址占多大的存储空间。
以上整个地址变换过程均是由硬件自动完成的。例如：
若页面大小L为1KB，页号2对应的物理块为b=8，计算逻辑地址A=2500的物理过程如下：
P = 2500/1K = 2， W = 2500 % 1K = 452
查找得到页号2对应的物理块号为8，E = 8 * 1024 + 452 = 8644
页表项的作用是找到该页在内存中的位置。以32位逻辑地址空间，字节编址单位，一页4KB为例，地址空间一共有
\[ 2^{32}/{4KB} = 1M \]
因此需要 \[ log_2{1M} = 20 \]
位才能保证表示范围能容纳所有页面，又因为以字节作为编址单位，即页表项的大小 \[ \geq \lceil 20/8 \rceil = 3B \]
所以页表项的大小应该大于等于 3B， 为了方便存储可以取成4B。
具有快表的地址变换机构
若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存；第一次是访问页表，确定所存取的数据或指令的物理地址；第二次是根据该地址存取数据或指令。显然，这种方法比通常执行指令的速度慢了一半。
为此，在地址变换机构中增设一个具有并行查找功能的高速缓冲存储器----快表，又称相联存储器（TLB），用来存放当前访问的若干页表项，以加速地址变换的过程。
在具有快表的分页机制中，地址的变换过程如下：
- CPU给出逻辑地址后，由硬件进行地址转换，将页号送入高速缓存寄存器，并将此页号与快表中的所有页号进行比较。
- 若找到匹配的页号，说明所要访问的页表项在快表汇中，则直接从中取出该页对应的页框号，与页内偏移量拼接形成物理地址。 这样，存取数据仅一次访存便可实现。
- 若未找到匹配的页号，则需要访问主存中的页表，读出页表项后，应同时将其存入快表，以便后面可能的再次访问。若快表已满， 则须按特定的算法淘汰一个旧页表项。
快表基于局部性原理。
两级页表
顶级页表最多只能有1个页面。
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序查找页表项。
例：
已知系统为32位实地址，采用48位虚拟地址，页面大小为4KB，页表项大小为8B，假设系统使用纯页式存储，则采用（）级页表，页内偏移（）位。
页式管理的地址结构：
| 页号P | 页内偏移量W |
|---|
页面大小为4KB，因此页内偏移为12位，因此虚页号为48 - 12 = 36位，采用多级页表时，最高级页表项不能超出一页大小；每页能容纳的页表项数为 4KB/8B = 512 = \(2^9\),36/9 = 4，因此应采用4级页表，最高级页表项正好占据一页空间。
3.1.5 基本分段存储管理
分页管理方式是从计算机的角度去考虑设计的，目的是提高内存的利用率，提升计算机的性能。分页通过硬件机制实现， 对用户完全透明。分段管理方式的提出则考虑了用户和程序员。
目的：
- 方便编程
- 信息保护和共享
- 动态增长
- 动态链接
段式管理方式按照用户进程中的自然段划分逻辑空间。
段内要求连续，段间不要求连续，因此地址空间是二维的
逻辑地址由段号S和段内偏移量W两部分组成。
系统为每个进程都建立一张逻辑空间与主存空间映射的段表，每个段表项对应进程的一个段，段表项记录该段在内存中的始址和长度。
配置段表后，执行中的进程可通过查找段表，找到每段所对应的内存区。可见，段表用于实现从逻辑段到物理内存区的映射。
地址变换机构
硬件支持：段表寄存器，用于存放段表始址和段表长度M
- 从逻辑地址A中取出前几位为段号S，后几位为段内偏移量W，需要注意是十进制还是二进制
- 比较段号S和段表长度M，若 \(S \geq M\),则产生越界中断，否则继续执行。
- 段表中段号S对应的段表项地址 = 段表始址F + 段号S x 段表项长度，取出该段表项的前几位得到段长C，若段内偏移量 \(\geq C\),则产生越界中断，否则继续执行。
- 取出段表项中该段的始址b，计算 E = b + W,用得到的物理地址E去访问内存。
段的共享与保护
在分段系统中，段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的。
不能修改的代码和数据可以共享，而可修改的代码和数据不能共享。
不能修改的代码称为纯代码或可重入代码（不属于临界资源）
分段管理的保护：
- 存取控制保护
- 地址越界保护
因为每段的长度是不固定的，因此段号和段内偏移量一定要显式给出。所以分段管理的地址空间是二维的。
分页式存储管理与分段式存储管理方式对比
| 分页存储管理 | 分段式存储管理 |
|---|---|
| 是从计算机的角度考虑设计的 以提高内存的利用率，提升计算机的性能为目标 |
考虑用户关于方便编程，信息保护和共享，动态增长及动态链接等多方面的需要 |
| 分页通过硬件机制实现，逻辑地址的页号和页内偏移量对用户是透明的 | 段号和段内偏移量由用户显式给出，在高级程序中这个工作由编译程序完成 |
| 逻辑地址是一维结构 | 逻辑结构是二维结构 |
| 产出内部碎片 | 产生外部碎片 |
| 页表大小一致 | 段长大小不等 |
段页式管理
在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，然后将每段分成若干大小固定的页。
用分段方法来分配和管理用户地址空间，用分页方法来管理物理存储空间。
段页式系统的逻辑地址结构
notes:
在一个进程中，段表只有一个，而页表可能有多个。
在进行地址变换时，首先通过段表查找到页表始址，然后通过页表找到页帧号，最后形成物理地址。
在段页式中，CPU每次从内存中取出一次数据需要3次访问内存。
- 先从内存查找段表
- 再访问内存查找相应的页表
- 最后拼成物理地址后访存
段页式管理的地址空间是二维的。
3.2 虚拟内存管理
虚拟存储器的定义与特征
基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时， 由操作系统将所需要的部分调入内存。另一方面，操作系统将内存中暂时不用的内容换出到外存。这样，系统好像为用户提供了一个比实际内存大得多的存储器。
局部性原理：
时间局部性: 程序中的某条指令一旦执行，不久后该指令可能再次执行；某数据被访问过，不久后该数据可能再次被访问。
空间局部性： 一旦程序访问了某个存储单元，在不久后，其附近的存储单元也被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围内， 因为指令通常是顺序存放，顺序执行的，数据也一般以向量，数组，表等形式簇聚存储的。
三个主要特征：
多次性，是指无须在作业运行一次性地全部装入内存，而允许被分成多次调入内存运行。
对换性，是指无须在作业运行时一直常驻内存，在进程运行期间，允许将那些暂不使用的程序和数据从内存调至外存的兑换区，待需要时再调回内存。
虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量大于实际的内存容量。
三种实现方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
虚拟存储器的容量取决于地址空间的大小而不是由实际的内存容量决定！！！
不管使用哪种方式，都需要一定的硬件支持，一般需要以下几个方面：
- 一定容量的内存与外存
- 页表机制（或段表机制），作为主要的数据结构
- 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断
- 地址变换机构，逻辑地址到物理地址的变换
缺页中断机构：
产生缺页中断的目的是要将位于外存上的代码或数据装入内存，此时应将缺页的进程阻塞（调页完成唤醒），如果内存中有空闲块，则分配一个块， 将要调入的页装入该块，并修改页表中相应页表项，若此时内存中没有空闲块，则需要淘汰某页。
缺页中断作为中断，同样要经历诸如保护CPU环境，分析中断原因，转入缺页中断处理程序，恢复CPU环境等几个步骤。但与一般的中断相比，
它有以下两个明显的区别：
- 在指令执行期间而非一条指令执行完成后产生和处理中断信号，属于内部异常
- 一条指令在执行期间，可能产生多次缺页中断
请求分页管理方式
请求分页系统建立在基本分页系统基础上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。
在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动作业运行。在作业执行过程中，当所要访问的页面不在内存时，再通过调页功能将其调入， 同时还可通过置换功能将暂时不用的页面换成到外存上，以便腾出内存空间。
若进程访问的页面不在主存中，且主存中没有可用的空闲帧时，系统正确处理顺序为：
缺页中断--> 决定淘汰页--> 页面调出--> 页面调入
需要的硬件支持：
页表机制
页表项：
| 页号 | 物理块号 | 状态位P | 访问字段A | 修改位M | 外存地址 |
|---|
- 状态位P：用于指示该页是否已调入内存，供程序访问时参考
- 访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供置换算法换成页面时参考
- 修改位M：标识该页在调入内存后是否被修改过，以确定页面置换时是否写回外存
- 外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考
缺页中断机构
在请求分页系统中，当所要访问的页面状态位P无效时，便产生一个缺页中断，此时硬件陷入内核，操作系统将所缺的页调入内存，并更新页表，中断后返回产出中断 的那条指令继续执行。
地址变换机构
- 先根据逻辑地址高位的页号检索快表
- 若找到要访问的页，，便修改页表项中的访问位（写指令还须重置修改位），然后利用页表项中给出的物理块号和页内地址形成物理地址
- 若未找到该页的页表项，则到内存中查找页表，再对比页表项中的状态位P，看该页是否已调入内存，若页面已调入，则修改页表项中的访问位和 快表，并根据页表项中的物理块号和逻辑地址低位的页内地址形成物理地址。若快表已满，则需采用某种算法替换。若页面未调入，则产生缺页中断，请求 从外存把该页调入内存。
页框分配
驻留集大小
对于分页式的虚拟内存，在进程准备执行时，不需要也不可能把一个进程的所有页都读入主存，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。 给一个进程分配的物理页框的集合就是这个进程的驻留集。
- 分配给一个进程的页框越少，驻留在内存中的进程就越多，从而可提高
CPU的利用率 - 若一个进程的主存中的页面过少，则尽管有局部性原理，缺页率仍相对较高
- 若内配的页框过多，则由于局部性原理，对该进程的缺页率没有太明显的影响
内存分配策略
- 固定分配局部置换，为每个进程分配规定的一些页框，在进程生命周期中保持不变
- 可变分配全局置换
- 可变分配局部置换
页面置换算法
假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1
以下是4种常见页面置换算法的执行结果：
最佳置换算法（OPT）
置换原则：
选择的被淘汰页面是以后永不使用的，或者是在最长时间内不再被访问的页面。
- 最佳置换算法可以保证获得最低的缺页率
- 最佳置换算法可以用来评价其他算法
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 2 | 2 | 7 | |||||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 4 | 0 | 0 | 0 | ||||||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 3 | 1 | 1 | |||||||||||||
| 缺页否 | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) |
只看当前页面后面的即可，选择最晚出现的页面进行置换
缺页中断次数：9
页面置换的次数：6(前面3次不是页面置换)
先进先出（FIFO）页面置换算法--Belady
置换原则：
优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面
- FIFO
算法可能会产生当所分配的物理块数增大而页故障数不减反增的
Belady异常。
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 2 | 4 | 4 | 4 | 0 | 0 | 0 | 7 | 7 | 7 | |||||
| 物理块2 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | 1 | 1 | 0 | 0 | ||||||
| 物理块3 | 1 | 1 | 1 | 0 | 0 | 0 | 3 | 3 | 3 | 2 | 2 | 2 | 1 | |||||||
| 缺页否 | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | $ | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(surd\) | \(\surd\) | \(\surd\) | \(\surd\) |
只看当前页面之前填写过的页面即可，选择最早进入内存的页面进行置换。
缺页中断次数：15
页面置换次数：12
最近最久未使用（LRU）置换算法
置换原则：
选择最近最长时间未访问的页面予以淘汰
| 访问页面 | 7 | 0 | 1 | 2 | 0 | 3 | 0 | 4 | 2 | 3 | 0 | 3 | 2 | 1 | 2 | 0 | 1 | 7 | 0 | 1 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 物理块1 | 7 | 7 | 7 | 2 | 2 | 4 | 4 | 4 | 0 | 1 | 1 | 1 | ||||||||
| 物理块2 | 0 | 0 | 0 | 0 | 0 | 0 | 3 | 3 | 3 | 0 | 0 | |||||||||
| 物理块3 | 1 | 1 | 3 | 3 | 2 | 2 | 2 | 2 | 2 | 7 | ||||||||||
| 缺页否 | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) | \(\surd\) |
从当前页面往前看，不管有没有填写过，选择最晚出现的置换即可。
缺页中断次数：12
页面置换次数：9
LRU算法的性能较好，但需要寄存器和栈的硬件支持。
导致LRU算法实现起来耗费高的原因是：
LRU算法需要对所有页最近一次被访问的时间进行记录，查找时间最久的进行替换，这涉及到排序。
时钟(CLOCK)置换算法
系统为每一帧关联一个附加位，称为使用位
置换原则：
- 将候选帧集合视为一个循环缓冲区
- 当需要替换一页时，从当前指针位置开始查找首个使用位为0的帧。查找过程重复以下操作直至找到为止：
- 若帧的使用位为0，则将该帧中的页被替换，其使用位被置为1，并将指针指向缓冲区中的下一帧
- 若帧的使用位为1，操作系统就将该位置为0.并查找缓冲区的下一帧。
最好画一个圆分区进行模拟
改进型CLOCK置换算法
在使用位的基础上再增加一个修改位
置换原则：
- 从指针的当前位置开始，扫描帧缓冲区，选择遇到的第一个帧(使用位 = 0， 修改位 = 0)用于替换
- 如果1步失败，则重新扫描，选择遇到的第一个(使用位 = 0，修改位 = 1)帧用于替换，在这个扫描过程中，对每个跳过的帧，把它的使用位设置为0
- 如果第2步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0，重复第1步，并且如果有需要，重复第2步，这样就可以找到替换的帧
抖动和工作集
抖动
在进程的页面置换过程中，刚刚换出的页面马上又要换入主存，刚刚换入的页面马上又要换出主存，这种频繁的页面调度行为称为抖动或颠簸
引起系统抖动的原因是对换的信息量过大，内存容量不足，置换算法选择不当，所以解决方法就是降低交换页面的数量，加大内存容量，改变置换选择算法， 但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量，或者降低进程数量。而增加交换区容量并不能解决物理内存不足的问题
所有的页面调度策略都不可能完全避免抖动
产生抖动的主要原因：页面置换算法不合理
工作集（驻留集）
工作集是指在某段时间间隔内，进程要访问的页面集合。
一般来说，工作集W可由时间t和工作集窗口大小
\(\triangle\) 来确定
假设工作集窗口大小 \(\triangle\) 为5，则在\(t_1\)时刻，进程的工作集为{2,3,5},在\(t_2\)时刻，进程的工作集为{1,2,3,4}
正确的选择工作集的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。