操作系统基础:内存管理
内存
CPU是高速设备，磁盘是一种低速设备，为了使数据读写不拖累CPU的计算速度，二者通过内存进行交互，内存速度高，但存储空间小于外存，用于存放CPU处理的数据。
首先要搞明白革命对象，存储器涵盖的种类是十分广泛的，有些存储器概念太久不接触也会混淆。
外存
外存就是最常见的存储器件，例如电脑硬盘等，用于大量存放数据，掉电也可以保存数据，只是相对内存而命名。
内存
内存就是暂存硬盘数据的存储器，硬件上是一种内存条的东西，硬盘的IO读写速度不能满足CPU要求，因此内存应运而生，一旦掉电，内存数据就会被清空。内存也称主存，一般是属于DRAM。
cache
cache是比内存更加高速的缓存，对CPU而言，内存的速度仍然是欠缺的，因此高速的读写需要cache的帮助，cache存在于内存和CPU之间，也因为其对速度的追求，其大小一般很小，几十k到几十M。现代CPU一般采取多级缓存架构，越靠近CPU，容量越小，速度越快。cache一般使用的是SRAM。
RAM与ROM与Flash
RAM是随机读取存储器，可以对存储器进行任意读写，但是掉电数据也会丢失；RAM被分成静态随机读取存储器（SRAM）和动态随机读取存储器（DRAM）；SRAM使用触发器进行信息存储，因此它的性能很快，读写效率很高，因为触发器的原因集成度却很低，而且功耗很大，这也是限制它容量大小的原因，所以它被用于cache；而DRAM是使用电容进行信息存储，电容的集成度可以被做得很高，功耗也很小，因此几G、十几G的内存是可以被使用的。
ROM是只读存储器，ROM一般只用于读取数据，ROM的数据修改是一项复杂的工作，包括紫外、电子擦写等，数据一旦写入就永久不变（或者很难改变），存放系统固件、操作系统启动程序等。只要是需要不变数据的地方，可能就存在ROM。
Flash是一项后来居上的技术，综合了RAM和ROM的优点。Flash通过存储芯片用于存储数据，掉电能够保存。读写速度、可靠性、稳定性、成本方面都有一定的优势。小到单片机几M内存，大到固态硬盘（SSD），都采用了Flash存储技术。
总结
现在很习惯的误导性说法将RAM=内存，ROM=外存，实际上是扭曲了ROM的实际价值。现在的硬盘是支持随机读写的，因此从客观来说就不符合ROM的特点，ROM是存在于各种电子设备、嵌入式系统存放系统信息的存储器，掉电也不会丢失数据。
编址
为了使CPU区分不同位置的数据，内存的空间也是需要编址：
大部分计算机采用“按字节编号”，每个存储单元可以存放一字节（8位二进制）的数据。
有的计算机采取“按字编址”，字的大小和计算机定义的字长有关，例如字长为16位的计算机每个存储单元可以存放16位二进制。
内存与指令
高级程序语言会被编译器编译成汇编语言，最后翻译成机器码（目标模块）。目标模块经过链接，会形成比较完整的可执行程序，装入内存中给CPU执行。内存中分为指令段和数据段，指令会告诉CPU从哪里的寄存器（数据段）读取数据，运算后写数据到哪里，这就是一个基本的程序运行流程。
程序编译形成的可执行文件（.exe、.o等）是一种指令的集合（经过链接阶段形成装入模块（完整的指令和逻辑地址）），其告诉编译器从什么地址读取和写入数据，但是这里的地址使用的是逻辑地址（相对的地址），并不是真正的物理地址，如何将程序的逻辑地址映射到CPU能够认识的物理地址，是内存管理中重要的一部分。
逻辑地址到物理地址的三种映射策略
1. 绝对装入
绝对装入是指在编译时，程序就应该知道将在放入的内存地址是什么，因此编译器会把程序对应的逻辑地址修改成物理地址，这样装入内存后就能够被CPU正确执行。
特点：这是一种早期程序方法，需要保证这个内存地址不会被占用、分配给其他进程，灵活性差，这在现代计算机系统是不现实的要求。
2. 可重定位装入（静态重定位）
编译、链接后可执行文件的地址都是从0开始的，在装入阶段（可执行文件->内存），会对地址进行重定位，也即将逻辑地址进行调整，使其成为真正的物理地址，能够被CPU执行；
特点：
要求装入该可执行文件的内存必须是连续的，而且应该一次性装入全部可执行文件的指令，如果没有足够的内存，就不能装入这个作业。
作业一旦进入内存，在运行期间就不能移动，也不能申请内存空间。
3. 动态运行时装入（动态重定位）
与静态重定位不同，装入模块（可执行文件）装入内存后，不会立刻将逻辑地址转换成物理地址，只有程序真正执行时才会进行转换。这种方式需要重定位寄存器的支持，重定位寄存器存放装入模块存放的起始地址，CPU会将指令指向的数据地址和重定位寄存器地址进行求和，得到真实的数据物理地址。
特点：
装入程序时可以装入到不连续的存储地址中；
程序只需要装入部分代码就可以投入运行；
在运行阶段也可以动态申请分配内存，灵活性高、易于共享。
链接的三种方式
源代码经过编译形成一系列目标模块，这些模块是一系列的机器码，存储这指令和数据给CPU执行；但是目标模块应该是有序的，因此需要经过链接才能真正形成装入模块，也即平时运行的可执行文件。
和装入相似，链接也有三种方式：
静态链接：程序运行前就将各个目标模块以及他们的库函数连接成一个完整的可执行文件，之后不再拆分；
装入时动态链接：先将某几个目标模块装入内存，一边装入一边链接其他目标模块。
运行时动态链接：先装入某几个目标模块运行，运行时确定需要的目标模块才对他进行连接，没有使用到的模块不进行装入。
内存管理任务
操作系统作为内存管理的统筹者，完成的工作包括：
内存的分配和回收；根据新建进程、进程销毁及时为其分配、回收内存资源；
内存扩展；例如一款游戏几十到上百G，而我们的计算机内存往往只有十几G，因此需要某种虚拟技术从逻辑上对内存空间进行扩展。
地址重定位：也就是我们刚刚描述的逻辑地址和实际物理地址映射的问题。
内存保护：内存具有共享性和隔离性，一个进程一般难以直接访问操作系统内核、其他进程的内存。一般有两种方式进行这样的限制：其一是通过设定上下限寄存器由于限定某个进程能够访问物理地址的上下限；其二是通过重定位寄存器（基址寄存器）和界地址寄存器判断访问地址是否越界。
内存扩展
为了解决程序大小大于内存大小的问题，人们一直尝试在操作系统引入不同的方法加以解决。
覆盖技术
覆盖技术的基本思想是将程序分成多个段，常用的段常驻内存，其他的段需要时才调入内存，内存也被划分成一个“固定区”和若干个“覆盖区”，程序的常驻内存的段就放置在固定区中，调入后不再调出，直到程序结束；不常用的段需要时调入覆盖区，不需要时及时调出。
一个模块通常会调用各种子模块，但是CPU的调用逻辑是串行的，因此依次调用子模块时，各种子模块可以共享一个内存区间，等待一个执行完了另一个调入，这种覆盖技术就节省了大量的内存空间。
特点：覆盖的结构是由程序员定义的，定义后操作系统才能完成覆盖，因此增加了编程上的负担，只在早期操作系统上使用。
交换技术
交换技术是指内存紧张时，系统会将内存中某些进程暂时换出外存，外存中某些已经具备运行条件的进程换入内存，进程在内存和磁盘间动态调度。交换技术需要考虑以下几个问题：
1. 换出的进程应该存放在外存的什么位置？
具有对换功能的操作系统通常把磁盘分为文件区和对换区，文件区主要存放文件，追求的是空间存储利用率，因此一般采用离散分配的方式；对换区空间一般只占磁盘空间的小部分，追求内存的换入换出速度，因此一般采取连续分配方式，I/O读写速度一般快于文件区。
2. 什么时候应该交换？
在内存紧张的时候，例如许多进程发生缺页，缺页率高居不下就可以考虑换出，等待缺页率明显下降就停止交换。
3. 应该换出什么样的进程？
可优先换出阻塞的、优先级低的进程，有的操作系统为了防止优先级低的进程在系统很快被换出，还会考虑进程的驻留时间（太短的不会立马被换出。
内存空间的分配和回收
介绍内存空间如何分配给进程以及回收；内存的分配被划分成连续分配模式和非连续分配模式，连续分配的意思是为进程分配的内存必须是一块连续的内存空间；非连续分配的意思是为用户进程分配的可以是一些分散的内存空间。
连续分配管理的三种方式
单一连续分配、固定分区分配、动态分区分配。
两种碎片术语
内部碎片：指的是系统分配给进程内存区域，如果有些部分没有被用上，就是称为内部碎片；
外部碎片：指的是每个进程都需要一片连续的内存空间，如果某些空闲分区太小，对每个程序而言都无法利用，这就称为外部碎片）
单一连续分配
内存被分为系统区和用户区。系统区一般是低址部分，用于存放操作系统的相关数据；用户区用于存放用户进程相关的数据。内存的用户区只有一道用户程序（一个进程），其独占用户区的资源；
优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，无需内存保护（进程单一不可能影响其他进程，系统区可以通过重启重新初始化。
缺点：只能用于单用户、单任务的操作系统，无法实现程序并发运行；有内部碎片、存储器利用率极低。
固定分区分配
20世纪60年代出现了支持多道程序运行的操作系统，为了能在内存装入多道程序，而这些程序又不会互相干扰，于是将内存空间划分成若干个分区，每个分区只会装入一个作业，形成了可运行多道程序的简单的内存管理方式。
固定分区又分为分区大小相等、分区大小不等的划分方法。
分区大小相等：缺乏灵活性，适用于一台计算机控制若干台相同设备的情况，例如一台计算机同时控制多台打印机控制程序等。而一般情况下，过小的程序导致产生内部碎片。过大的程序无法装入内存，或者通过内存扩充才能被内存装入，带来额外的系统开销。
分区大小不等：增加了灵活性，将内存划分成小分区、中等分区、大分区以满足作业大小需求。
固定分区需要一种数据结构来说明各个分区的情况，这种数据结构被称为分区说明表，每个表包含了分区的编号、大小、起始地址、状态（是否分配、使用）。当程序需要装入内存时，操作系统根据用户程序的大小检索该表，找到一个能满足大小、未分配的分区将其分配给该程序，然后修改状态为已分配。
固定分区优点：实现简单，无外部碎片；
缺点：程序过大时所有分区仍然可能不满足需求，需要考虑内存扩充但提高系统开销。程序过小时可能产生内部碎片，利用率低。
动态分区分配（可变分区分配）
动态分区分配不会预先在内存中划定分区，而是会在程序装入时动态建立分区，使得分区大小正好时候进程需要，因此内存分区的数目、大小是可变的。
动态分区策略需要考虑的问题：
1. 系统用什么数据结构记录内存的使用情况？
一般使用空闲分区表或者空闲分区链表结构；空闲分区表和固定分区的分区说明表类似，每个表项都记录了分区编号、大小、起始地址、状态等情况；空闲分区链是一种双向链表结构，每个结点存储了分区的各种信息、前向指针、后向指针。
2. 当很多分区可以满足需求时，应该选择什么样的分区进行分配？
按照动态分区分配算法进行分配，不同的算法性能效率不一样，详见后文动态分区分配；
3. 如何对分区进行分配和回收？
分配：遍历空闲分区表或者分区链根据某种算法选择分区，如果分区大于作业大小，就修改空闲分区表的大小、起始地址，将其中一部分空间分配给用户程序。如果分区大小刚好和作业大小相当，就删除这个表项或者空闲分区链结点，代表已被分配。
回收：假如回收进程有相邻的空闲空间，该进程占用的空间会并入相邻空闲空间，修改其分区大小、起始位置等，成为更大的一块空闲空间；假如回收进程邻近没有空闲分区，就增加表项或者结点。
动态分区特点：没有内部碎片，但会存在外部碎片；但外部碎片问题能够被解决：例如用于内存被连续的分配给多个进程，而也不断的有空闲的小空间释放，最后导致大进程无法装入内存，但是此时空闲内存之和是大于进程的；这是可以通过紧凑技术处理，在装入时采取动态重定位的方式进行装入，对进程起始地址进行修改，使得空闲空间集中在一起，解决外部碎片问题。
动态分区分配算法
1. 首次适应算法
每次从低址开始查找，找到第一个满足大小的空闲分区；实现：空闲分区表、空闲分区链按地址递增排序，顺序查找满足大小要求的空闲分区。（注意查找的分区只要大于等于进程需要的内存即可，这里是动态分配，大内存的改小即可。
2. 最佳适应算法
为了保证大进程享有大片内存空间，小内存被优先使用，因此空闲分区表、空闲分区链需要按照内存大小递增进行排序，每次使用时顺序查找，找到第一个能满足大小要求的分区。
值得注意的是，每次进程装入后会产生冗余的小内存，需要重新排序将小内存排在表前面，最佳适应算法的明显缺点是会带来大量的外部碎片。
3. 最坏（大）适应算法
为了解决最佳适应算法存在大量外部碎片问题，每次分配内存时优先使用大的内存，分配后剩余的空间一般不会太小，避免过多的外部碎片。因此按照容量递减的顺序进行排列。
这种算法的缺点也很明显，也即大进程到来时，可能就找不到适合的连续分区进行使用了。
4. 邻近适应算法
最佳、最大适应算法都是根据分区大小进行排序的，每次分配完都需要重新对其进行排序，带来的算法开销很大。首次适应算法按照地址查找，每次都要从低址开始查找，也带来了额外的开销。
因此，邻近适应算法采取的数据结构是一种空闲分区链（或者特殊的空闲分区表）。这种链表是双向循环链表数据结构，初始分配时从低址开始搜索适合大小的分区，修改其分区大小，下次搜索时不会回到低址，而是会在当前位置继续向后搜索。
带来的缺点也是明显的，这样低地址的空间就不会优先被使用，一般而言低地址可能使用的是小分区，高地址剩下的是大分区，因此采用邻近适应算法时，也有可能导致没有足够大的内存给大进程使用。
综合而言，从分配效果和科学性上说，首次适应算法是比较好的方法。
非连续分配管理方式
铺垫了那么多，终于进入到现代内存管理的核心部分了，也是我想记录这篇文章的初衷。
分页存储
内存空间会被分为一个个大小相等的分区（如4KB），这些分区被称为页帧（另称页框、内存块、物理块、物理页面），每个页帧都有一个编号，即页帧号（块号），页帧号从0开始。
进程的逻辑地址也会被分为与页帧大小相等的一个个部分，每个部分被称为一个页（或页面），每个页面也有编号（称为页号），从0开始。
注意不要混用两方面的术语，一个来自内存，一个来自进程。
页表
如何知道进程的页被存放到哪个页帧呢？这就需要一种重要的数据结构进行记录，这个结构被称为页表。页表一般存在于进程控制块PCB中，一个进程对应一个页表，进程的每个页对应页表的一个页表项，页表由页号和块号组成，记录了进程页面和内存块之间的映射关系。
页表的一些重要问题：
1. 页表使用几个字节的数据用于存放页帧号呢？
这关系到内存中能被划分成多少个页帧，例如4GB内存:每个页帧为4KB，说明一共会有
页表本身也是需要放到内存中的，从工程应用来说，3B的确足够编号存放所有的页帧，但装入内存，4KB的页帧无法完整装入整个页表（1个页表项3字节，4KB页帧无法装满整数个页表项），如果页表过大需要第二个页帧，那么第一个页帧就会产生4096%3=1B的内存碎片。因此每次查找页帧号时，从页表起始地址开始需要加上这些内存碎片产生的偏移量，才能找到对应的页帧号，为了避免这个问题很多时候会选择使用4字节（32位）存放页帧号数据。
此外，进程页号是连续的（进程大小已知、页单位大小已知，页号也就找到了，因此不需要考虑页号的存储问题，在物理上页表也只是记录了页帧号，没有页号，实际上获取某个页对应的页帧起始地址，需要用页帧号乘上页帧大小即可。
2. 如何实现地址转换（逻辑to物理）？
这并不困难，首先通过进程逻辑地址（如11KB）以及页的单位（4KB） 大小，就可以获知整数页号（11/4=2），页偏移量（11%4=3），通过查询页表就可以知道页号对应的页帧号，页帧内部也是连续存储，因此页偏移量也是页帧的偏移量，因此就可以获知实际的物理地址。
从计算机计算角度，页帧单位大小一般是4KB（或者其他2的n次方），因此将逻辑地址表示成二进制，实际上除以4KB，也就是右移操作，也即页的偏移量就是取逻辑地址的低几位（4KB=2的12次方，就是低12位），剩下的部分就是页号。这种方法让计算机很高效地就获取到页号和页偏移量。
基本地址变换机构
详细描述了地址变换的细节：系统内通常会设置一个页表接触器（PTR），存放页表在内存中的起始地址F和页表长度M；当进程未执行时，页表的起始地址和长度会放置在PCB中，当进程被调度时，操作系统内核会将它们加载到页表寄存器中。
根据进程的逻辑地址计算出页号、页偏移量，得到页号需要和页表寄存器中的页表长度进行对比，如果页号大于等于页表长度，说明发生越界错误，会触发中断（内中断）。否则继续执行：根据页号在页表中查询页号对应的页帧号（内存块号），从逻辑上来说，应该是找到存放着页帧号的地址（页表项地址），页表项地址=页表起始地址+页号*页表项长度（页表存放页帧号的字节大小）。得到页帧号，物理地址=页帧号*页帧大小+偏移量，这里一样是二进制的计算，对计算机而言十分快速。
具有快表的地址变换机构
快表：另称联想寄存器（translation lookaside buffer，TLB），是一种访问速度比内存快很多的高速缓存（cache），用于存放最近访问页表项的副本，可以加快地址变换的速度。与此对应，内存中的页表常被称为慢表。
这样，通过逻辑地址获取页号、页偏移量时，会首先查询快表是否有对应的页表项，如果命中则无需访问内存，而直接获取到内存块号，进一步得到物理地址；如果不存在则访问内存，并且复制页表项存入快表，这样下次就可以快速访问了。
在不引入快表的情况下，地址的转换需要经过两次访存（查页表+访问物理地址），而引入快表只需要进行一次访存。高速缓存能够大大提高数据的访问速度，涉及到局部性原理：时间的局部性体现在某一时刻某条指令被执行，短时间内再次被执行的可能性很高，例如主程序正在循环某项操作；空间局部性体现在一个内存位置被访问，其邻近位置的内存也很大可能被访问，因此将提前将其放入缓存，往往有利于性能的提升。、
两级页表
单级页表存在两个问题：
页表存储问题：在上述的讨论中，4GB内存可能存在
个页帧，页表每个页帧号占用3字节或者4字节，那么存储整个页表就需要几MB（单个进程、用户态、内核态都要）的空间。页表是顺序存储的，因此需要占用连续的很多个页帧。也就是说：分页存储的页表，还是存在着连续存储的问题。 进程在地址转换时很少用完整个页表，整个页表常驻内存也没有必要。
页表的存储
解决这些问题的思路和解决连续存储问题是一致的，就是继续分页存储。将一个页表打散成若干个小页表，例如约定每个小页表的大小为4KB，每个页表项占用4字节（前文已经讨论，未含标记位），那么每个小页表能够存放1024个页表项（实际上页表项一般会有标记位，存放数量不会是1024）。这些小页表项可以分散存储在内存的各个位置，为了记录小页表们的顺序和对应的位置，我们新增了一个页目录表（另称顶级页表、外层页表）来记录小页表们的存储位置。
地址转换
两级页表的地址转换还是和单级是类似的，假设我们一共有1024个小页表，也即顶级页表有1024个顶级页表项，那么逻辑地址（虚拟地址）就应该至少使用30位表达，前10位指示了内存块号存放着的二级页表，访问内存块得到二级页表，中间十位是二级页表对应的内存块号，访问内存块号，计算起始地址（内存块号×4096），最后十位是偏移量，加上起始地址就是对应的物理地址。
页表调入问题
为了解决第二个问题，需要在页表引入一个标志位，来说明该页面是否已经调入内存。更加详细的问题将在后面的虚拟内存一节进行讨论。
多级页表的细节
当小页表数目大于1024个时（因为我们设定页帧是4KB），顶级页表也需要进行离散存储，这又要再套一层顶级页表，成为三级页表结构。我们基于RiscV的xv6系统就使用了这样的三级页表结构。
页表的分级是由逻辑地址和编址方法决定的，在纯分页方法中，假设逻辑地址有40位，系统按字节编址，应该使用多少级页表：
按习惯假设页帧大小为4KB（
），按字节编址，也即标识页偏移量的为逻辑地址后12位。 假设内存为4GB（如Xv6内存，4GB=
，4G内存和32位系统很多时候是绑定的），那么一共有 个页帧，需要4B（32位，24位不方便查找）空间存储页帧号，页帧大小为4KB，因此上一级单个页表最多有1024个页表项，占用逻辑地址10位； 再上一级最多能表示多少个页表呢？答案是1024个页表，需要占用10位逻辑地址，每个页表索引仍然占据4B空间。我们一直没有强调这样的问题，所以导致有这样的疑问，为什么索引1024个页表还需要4B的空间？这里我们要对前面说法进行一个说明：上级页表查询下级页表，仍然是通过地址来进行查询的，而不是编号。通过地址查询，地址=基址+索引地址（内存块号×4）B（按字节编址），因此，绝不能因为
认为10位或者12位编号就能够索引1024个页表。 剩下8位逻辑地址，毫无疑问需要再增加一级页表，故需要三级页表结构。
其次，在不使用快表的前提下，n级页表储存就要经历n+1次访存，其中n次访问页表，最后一次访问计算出的物理地址。
分段存储
非连续存储处理分页存储以外，另一种方法是分段存储，分段存储将进程按功能段分割成段，每个段可以离散装入内存，分割的段名称、功能由程序员确定，因此分段存储对程序员是透明的，而分页存储是不透明的，分页存储是系统内核行为，使用者无需获知；分段存储对于程序共享、保护有着更好的效果。
其他用到再补，鸽掉~。
段页存储
分页存储：内存空间利用率高、不会产生外部碎片，会产生少量页内碎片，但不利于按照逻辑模块实现信息共享、保护；
分段存储：共享、保护容易实现，但会产生外部碎片（同动态分区，需要紧凑技术解决，增加系统开销），段长过大不利于分配连续空间。
段页存储：先分段，再分页（查找先查段表、再查页表），逻辑地址构成：段号、页号、页偏移量，其中程序员需要指明段号、段内地址（同分段存储），内核会自动将段内地址转换成页号、页偏移量。
其他，也鸽掉~。
虚拟内存
连续分配（单一连续、固定分区、动态分区分配）、非内存连续分配（分页、分段、段页）都属于传统存储管理，存在这样的问题：
一次性：作业必须一次性装入才能开始运行，因此大内存作业无法运行，或者并发的作业不能全部运行。
驻留性：一旦作业装入，一直驻留在内存中（无论是否被使用），直至作业结束。
之前介绍的覆盖、交换技术进化出了虚拟内存:
基于局部性原理，程序装入时将程序很快用到的也装入内存，用不到的暂时留在外存；
程序执行时，访问信息的不在内存时，由操作系统负责调入内存，然后继续执行程序；
内存空间不够，操作系统负责将用不到的内存交换到外存，这样使用到的内存就像比实际内存大的多，因此称为虚拟内存。
允许一个作业多次调入内存，从连续分配方式上实现是困难的，因此仍需要基于离散分配的管理方式。
根据系统内存非连续分配方式，虚拟内存的实现分为请求分页存储管理、请求分段存储管理、请求段页式存储管理，以请求分页存储管理为例，当访问的信息不存在时，操作系统要提供请求调页功能，将所需信息从外存调入内存，当内存不足时，操作系统要提供页面置换功能，将不需要的内存换出外存。
请求调页
为了实现虚拟内存的功能，需要在传统的页表进行加工，基本分页存储只记录了对应的内存块号，虚拟内存需要在其基础上增加状态位（是否存在内存）、访问字段（最近访问几次、上次访问时间等，与页面置换算法有关）、脏位（是否被修改，只有被修改才需要重新换出外存，否则直接删除副本即可）、外存地址（页面在外存存放位置）。
缺页中断
在虚拟内存中，通过页号、页偏移量找到对应的内存块，首先会检查该内存块是否已经存在与内存，如果不存在，则会引发缺页中断，此时进程会进入阻塞状态，内核会将对应的页读入内存，如果此时内存没有空闲的页，就会使用页面置换算法决定换出哪一个页面，首先会判断这个页面是否发生修改，如果发生修改，则还需要将修改更新到外存（否则直接换入覆盖），最后换入需要的页面，进程进入就绪状态。
缺页中断属于内中断，内中断分为陷入、故障、终止，缺页中断属于故障范畴，一次程序允许可能涉及多个页面，因此可能触发多次缺页中断。
页面置换
页面的置换是内存和磁盘IO之间的操作，因此会导致大的开销，理想的页面置换算法应该追求更少的缺页率。
最佳置换算法（Optimal，OPT）
最佳置换算法要求预先知道程序会访问的页面，因此每次换出的页面是永不使用，或者最长时间不会使用的页面。从下图理解:
假设有三个内存块，如果遇到即将访问的页面早就存在三个内存块，则不会发生缺页中断，所以也不会发生页面置换。如果遇到页面不存在内存，就会触发缺页中断，需要换出的页面就是之后最晚出现的一个。缺页中断不一定会引发页面置换（只决定是否调入，无空闲内存才置换）。
最佳置换算法是一种理想算法，无法在工程中实现，因为操作系统不总是在运行前就知道所有即将访问的页面顺序。
先进先出置换算法（FIFO）
思想比较简单：通过队列结构实现，每次淘汰的页面是最早进入内存的页面，换出时直接选择队头元素即可。队列的长度就是内存块的数量。
内存数量和缺页率紧密相关，甚至会出现内存块数量大，缺页率升高的异常，被称为Belady异常（因为淘汰的总是最早的页面，无论它被使用的概率）。五个算法中只有FIFO会出现这样的现象，而且首先被换出的也很有可能被需要，虽然其实现十分简单，但其算法性能较差。
最近最久未使用置换算法（least recently used，LRU）
每次换出的页面是最近最久没有被使用的。这就需要使用我们之前提到的访问字段，用于记录该页面自从上次被访问经历的时间t，每次换出，就会换出t值最大的页面。
该算法是性能较好，最接近OPT算法的一种，但是每个页面都需要进行计时、查找时需要进行遍历和比较，需要专门的硬件支持，实现比较困难，算法开销很大。
时钟置换算法（Clock）
Clock算法另称最近未用算法（NRU，Not Recently Used），为了平衡性能和开销问题，人们提出了该算法。
简单Clock算法实现：将内存中的页面使用循环链表链接，需要使用访问字段，每个被访问的页面的访问字段都被置为1，每次换出将字段为0的进行换出。例如：假设现在内存页面依次为1，3，2，4，7；每个页面都被置为1，那么第一次扫描会将这些页面重新置0，所以首选会将1换出；接下来访问3，5，4；就会导致3，4重新变成1，其换出优先级就下降了。也就是说最多两轮遍历，就可以确定换出哪个页面。
改进型时钟置换算法（改进型Clock）
改进型的时钟置换算法：改进型时钟算法除了考虑访问字段，还需要考虑修改字段，其淘汰优先级是：（访问位、修改位）
- （0，0）最近没有被访问，且没有被修改的；
- （0，1）最近没有被访问，但被修改过的；
- （1，0）最近访问过，但没有被修改；
- （1，1）访问过，且修改过的。
为什么没有被修改的换出优先级最高：因为这样就不用重新写入外存，减少了换出的IO操作，提高了算法性能，这就是改进的地方。具体流程：在第一轮扫描，会查找（0，0）的页面，如果没有就会进入第二轮扫描，查找（0，1）页面，如果没有，就会将所有的访问字段置为1，进入第三轮扫描，查找（1，0），如果没有，就说明原本所有页面都是（1，1），就进入第四轮扫描查找（0，1）字段，决定换出的页面。也即：改进型算法最多需要经过4轮扫描才能确定换出字段。
页面分配、置换策略
驻留集：请求分页存储中系统给进程分配的内存块集合。在虚拟技术中，驻留集大小一般小于进程的总大小。若驻留集太小，会导致缺页频繁，系统要消耗大量资源处理缺页中断，页面置换，推进进程的时间很少；如果驻留集太大，多道程序的并发性下降，资源利用率降低。
驻留集的分配策略分为两种：
固定分配：系统为进程分配固定数目的物理块，且运行期间不再改变；
可变分配：系统为每个进程分配一定数目的物理块，且运行期间可以根据情况适当增加或者减少。
页面置换也分为两种策略：
局部置换：发生缺页时只选择自己进程的物理块进行置换；
全局置换：只要是空闲的物理块，就置换到外存，再分配给缺页的进程。
两个方面的策略构成了四种可能，但是如果采用固定分配，是不可能实现全局置换的，因为把自身的进程物理块交给了别的进程，说明不可能是固定分配策略，所以我们讨论的只剩下以下三种情况：
固定分配局部置换：系统为进程分配固定数量的物理块，进程运行发生缺页，将在该进程选择一页换出，再调入需要的页面。缺点是很难开始时确定分配多少个内存块是比较合适的。
可变分配全局置换：系统开始时分配一定数量的物理块，当发生缺页，如果系统存在空闲物理块就会将其分配给该进程，如果不存在空闲物理块就会从非锁定（一些进程页面被禁止换出外存称为锁定）页面换出，再分配给该进程；因此某个进程缺页都会获得新的物理块，而有可能因此导致其他进程减少物理块，导致缺页率提高。
可变分配局部置换：刚开始为进程分配一定数量的物理块，当发生缺页只允许在自身进程选出一个页面换出，如果缺页频繁，系统会为该进程多分配物理块，直至缺页率趋势适当；反之如果一个进程缺页率很低，就会适当减少分配的物理块。这种策略比较合理。
调入页面时机策略
请求调页策略：这是我们一直采用的策略（运行时调入），只要系统发生缺页时，才会主动调入页面，每次调用一页，提高内存利用率，但涉及IO操作开销较大；
预调页策略：根据局部性原理（空间），相邻页面被调用的可能性比较大，因此预先调用的效果可能是高效的，如果没有被使用，这种操作则是冗余的，目前系统的预测成功也在50%左右，该策略主要用于进程的首次调入（运行前调入），由程序员告知系统应该先调入哪部分；
调入页面位置策略
外存磁盘分区一般分为对换区和文件区，对换区容量小但调入调出速度较快（因为连续存储），文件区容量大但是IO操作较慢（非连续存储，一切为了利用率）：
如果对换区空间足够，调入、调出可以在对换区、内存之间执行，首先从文件区拷贝到对换区，再与内存进行交互；
如果对换区空间不充足，那么凡是不会被修改的文件都会从文件区直接读入内存，也无需被换出而是直接覆盖；一旦文件修改，那么会重新读出到交换区，那么下次调入就是交换区调入了。
UNIX方式：运行前有关进程数据都会放在文件区，第一次使用时都需要从文件区调入，然后从交换区调出；再次使用就从交换区调入。
抖动（颠簸）现象
刚刚换出的页面很快又被调入，换入的页面很快又被换出，这种频繁调度页面的行为就称为抖动或者颠簸现象；产生该现象的主要原因是频繁访问页面的数量大于系统分配的物理块数目。为了探索如何分配合适的物理块数目，有人提出了工作集概念，配合驻留集一起讨论：
工作集：某段时间间隔内，进程实际访问页面的集合。
通过窗口尺寸确定，例如窗口尺寸为5，我们只关心最近时刻进程访问的5个页面，统计其工作集；工作集有可能小于窗口尺寸，例如过去访问了1，3，4，1，5，因为1是重复访问，那么工作集为4，如果经过一段时间，这种现象重复出现（工作集最大就是4），说明进程有良好的局部性，因为分配4个以上的内存块（驻留集设置为4）就可以使该进程工作良好。
一般驻留集不能小于工作集，否则会出现频繁缺页。
内存映射文件
操作系统向上层用户提供系统调用功能，实现两个目的：
方便用户访问文件数据。
方便多个进程共享数据。
方便访问
传统的文件访问流程可能涉及四个系统调用：通过open打开文件，执行seek使得系统定位（系统指针指向）开始读写操作的文件位置，read指定从磁盘读取多少数据进入内存（读入内核缓冲区，拷贝到用户空间），write操作修改文件（用户空间更新到内核缓冲区，写出外存）；
对大文件而言，read、write涉及拷贝读写操作，比较麻烦，内存映射文件提供了一种更加简单的方式：它只涉及两个系统调用，通过open打开文件，然后通过mmap将文件映射到内存的某个虚拟地址空间，mmap会向用户返回文件在内存的起始地址指针，接下来读写文件，就像对内存操作一样，通过指针+偏移量可以读写数据；但注意，开始时建立的只是映射关系，文件没有真正存在内存，但是这时读写文件相当于发生了缺页情况，操作系统内核会自动帮我们把文件读入内存，修改完毕后也会自动写回磁盘。
方便共享
对于第二个问题，由于使用的内存映射，因此多个进程无需经历open——读写——close再open——读写——close，在一个进程open，使用内存映射，另一个进程采取同样的操作，同一个文件在两个进程都有了独立的虚拟地址，但是其页表指向的最后是同一个物理空间，所有一个进程修改了文件，能够立马反映到另一个进程上，实现数据共享。