内存管理概念
内存管理的基本原理和要求
不可能将全部程序与数据放入主存，因此操作系统必须对内存进行划分和动态分配，这就是内存管理的概念
有效的内存管理可以方便用户使用存储器、提高内存利用率、通过虚拟技术从逻辑上扩充存储器
内存管理的功能有：
- 内存空间的分配与回收：由操作系统完成主存储器空间的分配和管理，使程序员摆脱存储分配的麻烦，提高编程效率
- 地址转换：程序中的逻辑地址与内存中的物理地址不一致，需要存储管理把逻辑地址转换成相应的物理地址
- 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存
- 存储保护：保证各道作业在各自的存储空间内运行，互不干扰
程序装入和链接
将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：
- 编译：由编译程序将用户源代码编译成若干目标模块
- 链接：由链接程序将编译后形成的一组目标模块及所需的库函数链接成一个完整的装入模块（如
.exe文件） - 装入：由装入程序将装入模块装入内存运行
程序的链接有以下三种方式：
- 静态链接：将各目标模块及它们所需的库函数链接成一个完整的可执行程序
- 装入时动态链接：装入内存时，采用边装入边链接的方式
- 运行时动态链接：在程序执行中需要目标模块时才进行链接；其优点是便于修改和更新和实现对目标模块的共享
内存的装入模块在装入内存时，同样有以下三种方式：
绝对装入：
编译程序将产生绝对地址的目标代码，绝对装入程序按照装入模块中的地址装入内存，仅适用于单道程序环境
通常程序员给出符号地址，让编译或汇编程序转换成绝对地址，也可由程序员直接给出绝对地址
可重定位装入，静态重定向：只在装入时进行重定向
在多道程序环境下，多个目标模块的起始地址通常都从 0 开始，程序中的其他地址相对于始址
根据内存的当前情况，装入内存的适当位置，装入时对指令和数据的修改过程（逻辑地址→物理地址）称为重定位
特点：
- 作业装入内存时，必须给它分配要求的全部内存空间，若没有足够的内存，则不能装入该作业
- 作业一旦进入内存，整个运行期间不能在内存中移动和再申请内存空间
动态运行时装入，动态重定位：在执行时才进行重定向，现代操作系统使用
程序在内存中若发生移动，则需要采用动态的装入方式，这种方法需要一个重定位寄存器的支持
特点，这是需要在运行时进行地址转换才能做到的：
- 可以将程序分配到不连续的存储区中
- 在程序运行之前可以只装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存
- 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间
逻辑地址空间与物理地址空间
编译后每个目标模块都从 0 号单元开始编址，这称为该目标模块的相对地址或逻辑地址
链接程序将各个模块链接成一个完整的可执行程序后，就构成统一的从 0 号单元开始编址的逻辑地址空间
用户程序和程序员只需知道逻辑地址；不同进程可以有相同的逻辑地址，因为会映射到主存的不同位置
物理地址是主存储器的地址，进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中存取
内存保护
内存保护是指：
- 保护操作系统不受用户进程的影响
- 保护用户进程不受其他用户进程的影响
内存保护可采取两种方法：
在 CPU 中设置一对上、下限寄存器，每当 CPU 要访问一个地址时，分别和两个寄存器的值相比，判断有无越界
采用重定位寄存器（或基址寄存器）和界地址寄存器（又称限长寄存器）来实现这种保护：
重定位寄存器含最小的物理地址值，界地址寄存器含逻辑地址的最大值，每个逻辑地址值必须小于界地址寄存器
内存管理机构将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址
*覆盖与交换
覆盖
早期的计算机系统中，存储空间放不下一道用户进程的现象也经常发生，可以用覆盖技术来解决
覆盖的基本思想如下：
- 把用户空间分成一个固定区和若干覆盖区
- 将经常活跃的部分放在固定区，其余部分按调用关系分段
- 将即将要访问的段放入对应的覆盖区替换其原有的内容，其他段放在外存中
特点：
- 不需要将一个进程的全部信息装入主存后才能运行，但同时运行程序的代码量大于主存时仍不能运行
- 内存中能够更新的地方只有覆盖区的段，不在覆盖区中的段会常驻内存
- 需要程序员指明固定区和覆盖区，增加了用户编程负担
交换
交换（对换）的基本思想是（中级调度采用的就是交换技术）：
- 换出：把处于等待状态的程序从内存移到辅存，把内存空间腾出来
- 换入：把准备好竞争 CPU 运行的程序从辅存移到内存
有关交换，需要注意以下几个问题：
交换需要备份存储，通常是快速磁盘
为了有效使用 CPU，需要使每个进程的执行时间比交换时间长
若换出进程，则必须确保该进程完全处于空闲状态
交换空间通常作为磁盘的一整块，且独立于文件系统
磁盘有对换区和文件区，文件区采用离散方式，对换区采用连续方式效率高
交换通常在有许多进程运行且内存空间吃紧时开始启动，而在系统负荷降低时就暂停
普通的交换使用不多，但交换策略的某些变体在许多系统中仍发挥作用，如 UNIX 系统
选择题：若一个进程正在 I/O 操作，则不能交换出主存，但 OS 开辟 I/O 缓冲区后进程交换不受限制
选择题：可重入程序通过共享或动态链接来使用同一块存储空间，以减少对程序段的调出/调入，减少了对换数量
交换技术主要在不同进程之间进行，而覆盖则用于同一个程序或进程中
对于主存无法存放用户程序的矛盾，现代操作系统是通过虚拟内存技术来解决的
覆盖技术则已成为历史，而交换技术在现代操作系统中仍具有较强的生命力
连续分配管理方式
连续分配方式是指为一个用户程序分配一个连续的内存空间
连续分配方式主要包括单一连续分配、固定分区分配、动态分区分配：
单一连续分配
内存分为系统区和用户区，系统区在低地址部分，这种方式无须进行内存保护（单任务不需要保护）
优点：简单、无外部碎片，可以采用覆盖技术，不需要额外的技术支持
缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低
固定分区分配
最简单的一种多道程序存储管理方式，将用户内存空间划分为若干固定大小的区域，每个分区只装入一道作业
使用：每当有空闲分区时，便可再从外存的后备作业队列中选择适当大小的作业装入该分区
固定分区分配在划分分区时有两种不同的方法：
- 分区大小相等：用于利用一台计算机去控制多个相同对象的场合，缺乏灵活性
- 分区大小不等：划分为多个较小的分区、适量的中等分区和少量大分区
为便于内存分配，通常将分区按大小排队，并为之建立一张分区说明表，其中各表项包括每个分区的始址、大小及状态
有程序要装入时，检索该表找到合适的分区给予分配并将其状态置为已分配，未找到合适分区时，则拒绝分配
这种分区方式存在几个问题：
- 程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间
- 主存利用率低，程序小于固定分区时也占整个固定分区，这种现象称为内部碎片
- 不能实现多进程共享一个主存区，存储空间利用率低
动态分区分配
又称可变分区分配，在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要
如下图，首先装入三个进程，在某个时刻 CPU 出现空闲，换出进程 2 换入进程 4，中间产生了内存块；CPU 又空闲...
动态分区会导致内存中出现许多小的内存块，随着时间的推移，内存中会产生越来越多的碎片，内存的利用率随之下降
这些小的内存块称为外部碎片，可以通过紧凑 Compaction 技术来解决，即把动态分区移动到一起，但这需要动态重定位寄存器的支持，且相对费时
分配策略：内存中有多个足够大的空闲块，操作系统必须确定分配哪个内存块给进程使用，有以下几种算法：
首次适应 First Fit 算法：空闲分区以地址递增的次序链接，分配内存时顺序查找，分配大小能满足要求的第一个空闲分区
会使内存的低地址部分出现很多小的空闲分区，查找时都要经过这些分区，因此增加了查找的开销
首次适应算法不仅是最简单的，而且通常也是最好和最快的
最佳适应 Best Fit 算法：空闲分区按容量递增的方式形成分区链，分配第一个能满足要求的空闲分区
每次最佳的分配会留下很小的难以利用的内存块，会产生最多的外部碎片，性能很差
最坏适应 Worst Fit，最大适应 Largest Fit 算法：空闲分区以容量递减的次序链接，分配第一个能满足要求的空闲分区
总把最大的连续内存划分开，会很快导致没有可用的大内存块，性能非常差
邻近适应 Next Fit，循环首次适应算法：与首次适应算法相比，分配内存时从上次查找结束的位置开始继续查找
虽然查找链表的次数快了，但不能形成较大的空闲分区，当有程序需要较大的内存时不能满足，通常比首次适应法差
注意：空闲分区可以使用数组或链表来管理；实验表明首次适应 > 最佳适应法 > 最大适应法
注意：在回收操作中，当回收的块与原来的空闲块相邻时，需要将这些块合并；算法开销也是需要考虑的一个因素
非连续分配管理方式
非连续分配允许一个程序分散地装入不相邻的内存分区，但这也需要额外的空间去存储分散区域的索引，使得非连续分配方式的存储密度低于连续存储方式的存储密度
非连续分配管理方式根据分区的大小是否固定，分为分页存储管理方式和分段存储管理方式；在分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分页存储管理方式和请求分页存储管理方式
基本分页存储管理方式
为了内存的使用能尽量避免碎片的产生，引入了分页的思想：
- 把主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位
- 每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间
进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但这种碎片相对于进程来说也是很小的，每个进程平均只产生半个块大小的内部碎片（也称页内碎片）
分页存储的几个基本概念
页面和页面大小：
进程中的块称为页 Page 或页面，内存中的块称为页框 Page Frame 或页帧，外存直接称为块 Block
进程在执行时要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应
页面大小应是 2 的整数幂，同时页面大小应该适中：
页面太小会使进程的页面数过多，这样页表就会过长，占用大量内存
也会增加硬件地址转换的开销，降低页面换入/换出的效率（即频繁换页）
页面过大又会使页内碎片增多，降低内存的利用率
选择题：操作系统的内存分页大小一旦确定，所有的页面就是等长的，无论在哪台电脑装（应该）
地址结构：
地址结构包含两部分：前一部分为页号 P，后一部分为页内偏移量 W
注意：地址结构决定了虚拟内存的寻址空间有多大
页表：
系统为每个进程建立一张页表来实现从页号到物理块号的地址映射，页表总是存放在内存中
页表是由页表项组成的，页表项由页号和物理内存中的块号组成；物理内存块号和页内偏移量共同组成物理地址
基本地址变换机构
地址变换机构的任务是将逻辑地址转换为内存中的物理地址，地址变换是借助于页表实现的
通常设置一个页表寄存器 PTR，存放页表在内存的起始地址 F 和页表长度 M
进程未执行时，页表的始址和长度存放在进程控制块 PCB 中；进程执行时，才将页表始址和长度存入页表寄存器
设页面大小为 L，逻辑地址 A 到物理地址 E 的变换过程如下：
计算页号 P=A / L 和页内偏移量 W = A % L
比较页号 Р 和页表长度 M，若 P ≥ M，则产生越界中断，否则继续执行
页表项地址 = 页表始址 F＋页号 P × 页表项长度，根据表项地址取出物理块号 b
注意：页表长度的值是指一共有多少页，页表项长度是指页地址占多大的存储空间
计算物理地址 E = b × L + W，用得到的物理地址去访问内存
以上整个地址变换过程均是由硬件自动完成
页式管理只需给出一个整数就能确定对应的物理地址（页面大小固定），因此页式管理中地址空间是一维的
以 32 位逻辑地址空间、字节编址单位、一页 4KB 为例，确定页表项的大小：
4KB共需要 12 位表示，剩下的 20 位用于表示页号的范围- 因为以字节作为编址单位，页表项的大小 ≥
，页表项至少是 3B - 为了存储方便和放额外信息，可以页表项可以取大点如
4B，这样一页正好装下1K个页表项
下面讨论分页管理方式存在的两个主要问题：
- 每次访存操作都需要进行地址转换，地址转换过程必须足够快，否则访存速度会降低
- 每个进程引入页表，用于存储映射机制，页表不能太大，否则内存利用率会降低
具有快表的地址变换机构
若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，这种方法比通常执行指令的速度慢了一半
在地址变换机构中增设快表 TLB，存放若干页表项以加速地址变换的过程，而主存中的页表常称为慢表
在具有快表的分页机制中，地址的变换过程如下：
- CPU 给出逻辑地址后，由硬件进行地址转换，将此页号与快表中的所有页号同时进行比较
- 若找到匹配的页号，则直接从快表中取出该页对应的页框号，形成物理地址（一次访存）
- 若未找到匹配的页号，则在内存中读出页表项，将其存入快表，若快表已满按照某算法进行替换
注意：有些处理机设计为快表和慢表同时查找，若在快表中查找成功则终止慢表的查找，题目没写一般不是这种
注意：快表访问成功仍需访问一次内存；快慢表非同时查找时，不管快表访问成不成功访问快表的时间都要消耗
由于基于局部性原理，快表的命中率可达 90% 以上，这样分页带来的速度损失就可降低至 10% 以下
两级页表
引入分页管理后，进程在执行时不需将所有页调入内存页框，只需将保存有映射关系的页表调入内存，但仍需考虑页表大小
一个 40MB 的进程它需要 10 页框来保存页表，但是它实际执行时可能只需要几十个页框就可运行：
- 若要求 10 个页面大小的页表必须全部进入内存，相对于几十个页框来说，降低了内存利用率
- 在大多数情况下，映射所需要的页表项都在页表的同一个页面中，没必要 10 个页表都在内存
- 需要连续的 10 个页框空间来存放页表，系统内可能找不到这么大的连续空间
注意：一般进程需要全部地址映射，单页表就需要 4MB，因为一般程序会用到高位和低位地址，如栈在高位，代码在低位
为了减少页表占用空间，进一步延申页表映射思想，得到了二级页表，对页表也进行地址映射，建立上一级页表，来存储页表的映射关系，以下是二级页表的逻辑地址空间的格式（为查询方便，顶级页表只能有 1 个页面）
例如：页面大小为 4KB，页内偏移地址为 12位，页号部分为 20 位，顶级页表可以放 4KB / 4B = 1024 个表项，占 10 位，因此逻辑地址空间就剩下了 10 位，二级页表的大小正好在一页之内，这样就得到了 10 10 12 的格式
建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项
思考：若采用二级页表，当程序挂起时，最高一级页表必须在内存；运行时仅需要用到的二级页表在内存
基本分段存储管理方式
分段管理方式为考虑了用户和程序员而提出，以满足方便编程、信息保护和共享、动态增长、动态链接等多方面的需要
额外：分段后汇编语句：Load [D] | <A> 把 D 段的 A 加载，这样编程更方便，可读性更高
额外：分页用户不可见，而分段用户可见；段内必须连续导致段太长时找不到连续空间
分段
段式管理方式按照用户进程中的自然段划分逻辑空间，每段从 0 开始编址，并分配一段连续的地址空间，其逻辑地址由段号 S 与段内偏移量 W 两部分组成，最多拥有
在段式系统中，段号和段内偏移量必须由用户显式提供，在高级程序设计语言中，这个工作由编译程序完成
段表
每个进程都有一张段表，用于实现从逻辑段到物理内存区的映射，其中每个段表项对应进程的一段
段表项由段号、段基址、段长组成，每个段表项长度相同，段长位数和逻辑地址中的段长一样，基址位数和内存大小一样
这是进程的段与物理内存的映射关系：
地址变换机构
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址 F 和段表长度 M
从逻辑地址 A 到物理地址 E 之间的地址变换过程如下：
- 从逻辑地址 A 中取出前几位为段号 S，后几位为段内偏移量 W
- 比较段号 S 和段表长度 M，若 S ≥ M，则产生越界中断，否则继续执行
- 段表项地址 = 段表始址 F＋段号 S × 段表项长度
- 从段表项取出段长 C，若段内偏移量 ≥ C，则产生越界中断，否则继续执行
- 从段表项取出该段的始址 b，计算物理地址 E = b + W，用得到的物理地址去访问内存
段的共享与保护
段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的
当一个作业正从共享段中读取数据时，必须防止另一个作业修改此共享段中的数据，因此：
不能修改的代码称为纯代码或可重入代码，这样的代码和不能修改的数据可以共享，而可修改的代码和数据不能共享
分段管理的保护方法主要有两种：
- 存取控制保护：访问内存时查看段表项的保护码检查是否有该操作的权限
- 地址越界保护：校验段号和段内地址偏移，保证不会访问过界
访问内存时要给出段号和段内偏移，因此分段管理的地址空间是二维的
段页式管理方式
段页式存储管理方式是页式存储和分段存储的结合，即有效地提高内存利用率，又反映程序的逻辑结构并有利于段的共享
在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段都有自己的段号，再将每段分成若干大小固定的页
对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位
在段页式系统中，作业的逻辑地址分为三部分：段号、页号、页内偏移量
系统为每个进程建立一张段表，每个分段有一张页表：段表表项中至少包括段号、页表长度和页表始址；页表表项中至少包括页号和块号。系统中有一个段表寄存器，指出作业的段表始址和段表长度
进行地址变换步骤：
- 通过段表查到页表始址
- 通过页表找到页帧号
- 形成物理地址
进行一次访问实际需要三次访问主存，可以使用快表来加快查找速度，其关键字由段号、页号组成，值是页帧号和保护码
访问内存时要给出段号和页号，因此段页式管理的地址空间是二维的
虚拟内存管理
虚拟内存的基本概念
传统存储管理方式的特征
指上一节的存储管理方式，它们具有以下两个共同的特征：
- 一次性：作业必须一次性全部装入内存后，才能开始运行这导致：
- 当作业很大而不能全部被装入内存时，将使该作业无法运行
- 当大量作业要求运行时，内存不足以容纳所有作业，只能使少数作业先运行，导致多道程序度的下降
- 驻留性：作业被装入内存后，不会换出任何内存，直至作业运行结束，即使进程会因等待 I/O 而被阻塞
程序运行中暂时不用的程序或数据占据大量的内存空间，而一些需要运行的作业又无法装入运行，浪费了内存资源
局部性原理
快表、页高速缓存、虚拟内存技术从广义上讲，都属于高速缓存技术，其所依赖的原理是局部性原理
局部性原理适用于程序结构和数据结构，它表现在以下两个方面：
时间局部性：
- 某条指令一旦执行，不久后该指令可能再次执行
- 某数据被访问过，不久后该数据可能再次被访问
将近来使用的指令和数据保存到高速缓冲存储器中，并使用高速缓存的层次结构实现
空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问
使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现
虚拟内存技术就是使用内存对外存进行高速缓存，使得有外存的容量和内存的速度，利用局部性原理实现
虚拟存储器的定义和特征
根据局部性原理得：
- 程序的一部分装入内存，就可启动程序执行
- 程序执行过程中，所访问的信息不在内存时，将其调入内存继续执行
- OS 将暂时不使用的内容换出到外存上，腾出空间放要调入内存的信息
这样，系统似乎给用户提供了一个比实际内存大得多的存储器，称为虚拟存储器（实际上不存在）
这是由系统提供了对用户透明的部分装入、请求调入、置换功能实现的
- 虚拟内存的实际容量 ≤ 内存容量和外存容量之和
- 虚拟内存的最大容量 ≤ 计算机的地址位数能容乃的最大容量
虚拟存储器有以下三个主要特征：
- 多次性：无须在作业运行时一次性地全部装入内存，而允许被分成多次调入内存运行
- 对换性：无须在作业运行时一直常驻内存，而允许在作业的运行过程中，进行换进和换出
- 虚拟性：从逻辑上扩充内存的容量，使用户所看到的内存容量远大于实际的内存容量
虚拟内存技术的实现
虚拟内存的实现需要建立在离散分配的内存管理方式的基础上，否则将作业分多次调入内存时，难以分配连续内存
虚拟内存的实现有以下三种方式：
- 请求分页存储管理
- 请求分段存储管理
- 请求段页式存储管理
不管哪种方式，都需要有一定的硬件支持，一般需要：
- 一定容量的内存和外存
- 页表机制或段表机制，作为主要的数据结构
- 中断机构，当用户程序要访问的部分尚未调入内存时，则产生中断
- 地址变换机构，逻辑地址到物理地址的变换
请求分页管理方式
在基本分页系统基础之上，增加了请求调页功能和页面置换功能，从而支持虚拟存储器功能
在请求分页管理方式中：
- 只需将当前需要的一部分页面装入内存，便可以启动作业运行
- 在作业执行过程中，要访问的页面不在内存中时，通过调页功能将其调入
- 还可通过置换功能将暂时不用的页面换出到外存上，以便腾出内存空间
为了实现请求分页需要：一定容量的内存及外存、页表机制、缺页中断机构、地址变换机构
页表机制
因为没有一次加载进内存，请求分页系统必须解决的两个基本问题：如何发现和处理要访问的页面不在内存中的情况
因此在请求页表项中增加了 4 个字段：
- 状态位 P：指示该页是否已调入内存，供程序访问时参考
- 访问字段 A：记录本页在一段时间内被访问的次数或多长时间未被访问，供置换算法换出页面时参考
- 修改位 M：标识该页在调入内存后是否被修改过
- 外存地址：用于指出该页在外存上的地址，供调入该页时参考，通常和物理块号共用
思考：当程序被挂起时，把页面都调到外存，并修改页表的物理块号，令其为外存地址；这样可以只留最高级页表在内存
缺页中断机构
在请求分页系统中，每当所要访问的页面不在内存中时：
- 产生一个缺页中断，请求操作系统将所缺的页调入内存
- 将缺页的进程阻塞，调页完成后唤醒
- 若没有空闲块，则要淘汰某页，若其修改位为 1，则要将其写回外存，此时有空闲块
- 分配一个空闲块，将要调入的页装入该块，并修改页表中的相应页表项
缺页中断与一般的中断相比，有以下不同的区别:
- 在指令执行期间产生和处理中断信号，属于内部中断
- 一条指令在执行期间，可能产生多次缺页中断
- 执行完中断后会回到引发中断的指令重新执行
地址变换机构
请求分页系统中的地址变换机构，是在分页系统地址变换机构的基础上，为实现虚拟内存又增加了某些功能而形成的
一般来说只需修改快表中的数据，只有要将快表项删除时才需要写回内存中的慢表
- 快表当查询成功时，要修改访问位，写指令要额外修改修改位，最后计算出物理地址，而失败时去慢表查找
- 慢表找到表项后检查状态位，若在内存将表项复制到快表转步骤 1，若在外存产生缺页中断
- 页面调入内存后，需要修改慢表，同时也需要将表项复制到快表中，转步骤 1
页面置换算法
页面对换时，若内存已无空闲空间，就需要使用页面置换算法从内存中调出一页程序或数据到外存
好的页面置换算法应有较低的页面更换频率，应将以后或较长时间内不会再访问的页面先调出
最佳 OPT 置换算法
最佳置换算法：被淘汰页面是永不使用或最长时间内不再被访问的页面，缺页率最低，因无法预知未来该算法无法实现
最佳置换算法用来评价其他算法；下面是例子有 3 个物理块，和页面引用串，每次置换出最晚访问的页面：
先进先出 FIFO 页面置换算法
优先淘汰最早进入内存的页面；该算法与进程实际运行时的规律不适应，进入内存的时间和以后是否访问没有关系
下面是例子，数据和上面的一样，但这里进行了 12 次页面置换：
Belady 异常：产生所分配的物理块数增大而页故障数不减反增的异常现象，只有 FIFO 算法可能出现 Belady 异常
下面是 Belady 的例子，物理块增大了，但缺页次数不减反增：
最近最久未使用 LRU 置换算法
淘汰最近最长时间未访问过的页面，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问
该算法为每个页面设置一个访问字段，记录页面自上次被访问以来所经历的时间，淘汰时选择现有页面中值最大的予以淘汰
LRU 算法是向前看的，最佳置换算法是向后看的；LRU 算法的性能较好，但需要寄存器和栈的硬件支持
LRU 是堆栈类的算法，堆栈类算法不可能出现 Belady 异常
时钟 CLOCK 置换算法
CLOCK 算法给每帧关联一个附加位，称为使用位：
- 当某页首次装入主存或再被访问时，将该帧的使用位设置为 1
- 有一个指针指向用于替换的候选帧集合（看作循环缓冲区），一页被替换时，指针指向下一帧
- 需要替换一页时，从指针位置开始循环查找，找出使用位为 0 的来替换，把跳过的帧的使用位 1 的帧置为 0
因为算法要循环扫描缓冲区，像时钟的指针一样转动，所以称为 CLOCK 算法，又称最近未用 NRU 算法
CLOCK 算法的性能比较接近 LRU 算法，而通过增加使用的位数目，可以使得 CLOCK 算法更加高效
下面使用一个例子来详细说明 CLOCK 算法：
进程依次访问 1, 3, 4, 2, 5 号页面，系统会将这些页面连成一个循环队列，刚开始扫描指针指向第一个被访问的页面，如图 a
进程请求访问 6 号页面，选择一个页面置换出去，在第一轮扫描中，指针扫过的页面的使用位置为 0，如图 b
第二轮扫描中换出首个使用位为 0 的页面，换入 6 号页面并设置访问位为 1，将扫描指针后移，下次从 3 号页开始，如图 c
注意：1 号页面原先占有的是 x 号物理块，则 6 号页面换入内存后也放在 x 号物理块中
改进型 CLOCK 置换算法
改进型 CLOCK 置换算法：在使用位的基础上再增加一个修改位
每帧都处于以下 4 种情况之一：
- 未访问未修改：u = 0, m = 0
- 被访问未修改：u = 1, m = 0
- 未访问被修改：u = 0, m = 1
- 被访问被修改：u = 1, m = 1
算法执行如下操作步骤：
- 从指针的当前位置开始，扫描帧缓冲区选择 u = 0, m = 0 来替换，不做任何修改
- 若第 1 步失败，则重新扫描，选择 u = 0, m = 1 来替换，每个跳过的帧的使用位设置成 0
- 若第 2 步失败，返回第 1 步
改进型 CLOCK 算法首选没访问的页，次选没修改的页，没修改的页被替换时不用写回，这样做会节省时间
优化页面置换算法的原则：尽可能保留曾经使用过的页面，而淘汰未使用的页面，认为可以在总体上减少换页次数
页面分配策略
驻留集大小
进程的驻留集：给一个进程分配的物理页框的集合；操作系统必须决定给特定的进程分配几个页框
需要考虑以下几点：
- 驻留集越小，驻留在主存中的进程数就越多，可以提高处理机的时间利用效率
- 驻留集过少，则尽管有局部性原理，页错误率仍然会相对较高
- 驻留集过多，则由于局部性原理，分配更多的主存空间对该进程的错误率没有明显的影响
页面的分配置换策略有：
- 固定分配：操作系统为进程分配好物理块后，驻留集大小不变
- 可变分配：操作系统为进程分配好物理块后，驻留集大小可变
- 局部置换：只能选进程自己的物理块进行置换
- 全局置换：可以从操作系统拿物理块，也可以抢其他进程的物理块
现代操作系统通常采用三种策略，开始时都为进程分配一定的物理块：
固定分配 + 局部置换：驻留集固定，缺页时只能从自己的物理块进行置换
难以确定驻留集大小：太少会频繁出现缺页中断，太多又会使 CPU 和其他资源利用率下降
可变分配 + 全局置换：驻留集可变，缺页时 OS 会从空闲块中分配一个物理块给该进程，最简单的策略
可以动态的增加物理块，但也会盲目地给进程增加物理块，从而导致系统多道程序的并发能力下降
可变分配 + 局部置换：驻留集可变，缺页时只能从自己的物理块进行置换，但 OS 根据缺页率动态调整驻留集
优点：在保证进程不会过多地调页的同时，也保持了系统的多道程序并发能力
缺点：需要更复杂的实现，也需要更大的开销，但对比频繁地换入/换出所浪费的计算机资源，这种牺牲是值得的
注意：没有固定分配 + 全局置换，因为全局置换就会增加物理块与固定分配矛盾
调入页面的时机
为确定系统将进程运行时所缺的页面调入内存的时机，有以下调页策略：
预调页策略：一次调入多页比多次调入多页时间要短，可以根据局部性原理，一次调入多个相邻页
这样可能会更高效，但若调入页面中大多数都未被访问又是低效的
因此需要采用以预测为基础的预调页策略，但目前预调页的成功率仅约 50%
因此主要用于进程的首次调入，由程序员指出应先调入哪些页，如调入 main 函数
请求调页策略：访问的页面不在内存时，请求 OS 将所需页面调入内存
调入的页一定会被访问，且策略更易于实现，故目前的虚拟存储器中大多采用此策略
缺点：每次只调入一页，调入/调出页面数多时会花费过多的 I/O 开销
预调入就是运行前的调入，请求调页就是运行期间调入；通常两种调页策略会同时使用
从何处调入页面
外存分为离散分配方式的文件区和连续分配方式的对换区，因此对换区的磁盘 I/O 速度比文件区的更快
从何处调入页面存在三种情况：
系统拥有足够的对换区空间：运行前，将进程有关的文件复制到对换区；运行时，从对换区调入所需页面
系统缺少足够的对换区空间：
刚开始进程`有关的文件都从文件区读入，换出时：
- 不会被修改的文件直接覆盖
- 可能被修改的文件换到对换区，需要时再从对换区调入（读比写快）
UNIX 方式：
与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入
换出是都换出到对换区，曾经运行过但又被换出的页面，下次调入时应从对换区调入
进程请求的共享页面若被其他进程调入内存，则无须再从对换区调入
抖动
抖动，颠簸：频繁进行页面调度，如刚换出又要换入，刚换入又要换出，这是由 CPU 的调度算法不合理引起的
进程在颠簸：一个进程在换页上用的时间多于执行时间
频繁发生缺页中断的主要原因：某个进程频繁访问的页面数目高于可用的物理页帧数目
虚拟内存技术可在内存中保留更多的进程以提高系统效率
在稳定状态，几乎主存的所有空间都被进程块占据，处理机和操作系统可以直接访问到尽可能多的进程
如果管理不当，那么处理机的大部分时间都将用于交换块，会大大降低系统效率
工作集
基于局部性原理，可以用最近访问过的页面来确定工作集，最近访问的页面以后很可能会再访问
工作集：在某段时间间隔内，进程要访问的页面集合，工作集 W 可由时间 t 和工作集窗口大小
工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合
例如，某进程对页面的访问次序如下：
假设工作集窗口大小
实际应用中，工作集窗口会设置得很大，即对于局部性好的程序，工作集大小一般会比工作集窗口
若驻留集大小小于工作集大小，则该进程就很有可能频繁缺页，为防止这种抖动现象，驻留集大小要大于工作集大小
工作集模型的原理是：
- 让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块
- 工作集内的页面需要调入驻留集中，工作集外的页面可从驻留集中换出
- 若还有空闲物理块，则可以再调一个进程到内存以增加多道程序数
- 若所有工作集之和超过可用物理块数，则暂停一个进程，将其页面调出并将其物理块分配给其他进程，以防止抖动
📝 个人补充与原笔记精华
TIP
动态分区分配算法评价：综合效果：首次适应算法 (FF) > 最佳适应法 (BF) > 临近适应法 (NF) > 最大适应法 (WF)。
IMPORTANT
缺页中断的本质：缺页中断属于内部异常（Fault），发生在指令执行期间。一条指令可能产生多次缺页中断。
WARNING
Belady 异常：指分配的物理块数增大而缺页次数反而增大的异常现象。只有 FIFO 算法会产生 Belady 异常。