基于王道计算机考研 操作系统。

笔记目录

第一章-计算机系统概述
第二章-进程与线程
第三章-内存管理
第四章-文件系统
第五章-输入/输出管理

第三章 内存管理

3.1 内存管理概念

3.1.1 内存管理的基本原理和要求

内存管理是操作系统设计中最重要和最复杂的内容之一。操作系统对内存的划分和动态分配，就是内存管理的概念。

内存管理的主要功能有：

1. 内存空间的分配和回收。
2. 地址转换。将逻辑地址转换成相应的物理地址。
3. 内存空间扩充。利用虚拟存储技术逻辑上扩充内存。
4. 内存共享。允许多个进程访问内存的同一部分。
5. 存储保护。保证各个进程在各自的存储空间内运行。

程序的链接与装入

将用户的源程序变为可在内存中执行的程序，通常要经过：

1. 编译。将用户程序源代码编译成若干目标模块。
2. 链接。由链接程序将编译后形成的模块和所需的库函数链接在一起，形成一个完整的装入模块。
3. 装入。由装入程序将装入模块装入内存运行。

• 绝对装入

绝对装入方式只适用于单道程序环境。编译时，如果知道程序将放到内存的哪个位置，则编译程序将产生绝对地址的目标代码。装入程序按装入模块的地址将程序和数据装入内存。

程序中使用的绝对地址，可以在编译或汇编时给出，也可以由程序员赋予。通常情况下采用的是符号地址，编译或汇编时再转换为绝对地址。

• 可重定位装入

经过编译、链接后的装入模块的始址通常从0开始，程序中的地址都是相对于始址的。此时应采用可重定位装入方式。根据内存的当前情况将装入模块装入合适的内存位置。

装入时对目标程序相对地址的修改过程称为重定位，又因为地址转换通常是进程装入时一次完成的，又称为静态重定位。一个作业装入内存后就无法再内存中移动，也不能再申请内存空间。

• 动态运行时装入

动态运行时装入也称为动态重定位。程序要想再内存中发生移动，就要采取动态的装入方式。装入程序将模块装入内存后，不会立即将相对地址转为绝对地址，而是将地址转换延迟到程序真正要执行时才执行。这需要一个重定位寄存器用于存放装入模块的起始位置。

动态重定位的优点：可以将程序分配到不连续的存储区；程序运行前只需装入部分代码即可投入运行，然后根据需要动态申请分配内存；便于程序段的共享。

根据链接时间不同，有三种链接方式：

• 静态链接

在程序运行之前，将各目标模块和所需库函数链接成一个完整的装入模块，以后不再拆开。

需要解决两个问题：第一是修改相对地址，所有目标模块都是从0开始的相对地址，链接后需要修改。第二是变换外部调用符号，将每个模块的外部调用符号也变为相对地址。

• 装入时动态链接

将源程序编译后得到的目标模块，在装入内存时一边装入一边链接。优点是便于修改和更新，便于实现对目标模块的共享。

• 运行时动态链接

在程序执行时需要某种模块才对它进行链接。优点是可以加快程序的装入过程，还可以节省内存空间。

逻辑地址和物理地址

编译后，每个目标模块都从0开始编址，称为目标模块的相对地址或逻辑地址。链接程序按顺序依次按各个模块的相对地址构成逻辑地址空间或虚拟地址空间。

进程在运行时看到的都是逻辑地址，用户和程序员只需要知道逻辑地址，而内存管理的具体机制是透明的。

物理地址空间是指内存中物理单元的集合，是地址转换的最终地址。进程在运行时执行指令和访问数据，最后都要通过物理地址从主存中获取。将逻辑地址转为物理地址，这个过程称为地址重定位。

操作系统通过内存管理部件(MMU)将逻辑地址转为物理地址，逻辑地址通过页表映射到物理内存，而页表由操作系统维护并被处理器引用。

进程的内存映像

一个进程的内存映像一般有几个要素：

1. 代码段。代码段是只读的，可以被多个进程共享。
2. 数据段。程序运行时的加工处理对象，比如全局变量和静态变量。
3. PCB。存放在系统区。
4. 堆。用来存放动态分配的变量，通过调用malloc函数动态向高地址分配空间。
5. 栈。用来实现函数调用。从用户空间最大地址向低地址方向增长。

代码段和数据段在调入内存时就指定了大小，而堆和栈可以在运行时动态地扩展和收缩。

内存保护

确认每个进程都有一个单独的内存空间。保护操作系统不受用户进程影响，同时用户进程不受其他用户进程的影响。

1. 在CPU中设置一对上、下限寄存器，存放用户进程的上限和下限地址，每当CPU要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。
2. 采用重定位寄存器（也称基地址寄存器）和界地址寄存器（也称限长寄存器）进行越界检查。重定位寄存器放进程的起始物理地址，界地址寄存器存放进程的最大逻辑地址。内存管理部件将逻辑地址和界地址寄存器进行比较，如果没有发生地址越界，则加上重定位寄存器的值后映射成逻辑地址。

内存共享

只读的区域才可以共享。可重入代码也称纯代码，允许多个进程同时访问但不允许被任何进程修改。实际运行时，也可以为每个进程配置局部数据区，将执行中可能改变的部分复制到该数据区，执行时只对私有数据区的内存进行修改，不变动共享的代码。

还可以通过内存映射文件来实现内存共享。

内存分配与回收

操作系统由单道向多道发展时，存储管理从单一连续分配发展为固定分区分配，又发展到动态分区分配。为了更好提高内存的利用率，又从连续分配方式发展到离散分配方式——页式存储管理。

引入分段管理的目的主要在于满足用户在编程和使用的需求。

3.1.2 连续分配管理方式

单一连续分配

在单一连续内存分配中，内存分为系统区和用户区，系统区仅操作系统可用，通常在低地址；用户区仅有一道用户程序，独占整个用户区。

优点：简单，无外部碎片；不需要进行内存保护。

缺点：只能用于单用户、单任务的操作系统；有内部碎片；存储器的利用率极低。

固定分区分配

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小空间的分区，每个分区装入一道作业。有分区空闲时，就可以从外存的后备队列选择合适大小的作业装入分区。

• 分区大小相等。程序太小会浪费，太大又无法装入，缺乏灵活性。
• 分区大小不等。划分为多个较小的分区、适量的中等分区和少量大分区。

为了方便分配和回收，建立一张分区使用表，通常按分区大小排队。分配内存时，检索该表，找到一个满足的分区分配。

存在两个问题：

1. 程序太大而放不进任何一个分区。
2. 程序小于固定分区大小时，也要占用一个完整的分区，存在空间浪费，称为内部碎片。

固定分区方式无外部碎片，但是不能实现多进程共享一个主存区，存储空间利用率低。

动态分区分配

• 基本原理

动态分区分配也称可变分区分配，根据进程的实际需要动态分配内存，而且分区大小正好适合需要。系统中分区的大小可变。

动态分区随着时间推移会产生越来越多的小内存块，称为外部碎片，存在于所有分区的外部。

外部碎片可通过紧凑技术克服，操作系统不时地对进程进行移动和整理。但是需要动态重定位寄存器的支持，而且相对费时。

在动态分区分配中，和固定分区分配类似，设置一张空闲分区链表，可以按始址排序。分配内存时，检索空闲分区链，找到所需分区，按请求大小分配一块空间给装入进程，余下部分仍然留在空间链中。

回收时，根据回收分区的始址，找到链中相应插入点。可能出现四种情况：

1. 回收区和插入点的前一空闲分区相邻。将两个分区合并，并修改前一分区表项的始址和大小。
2. 回收区和插入点的后一空闲分区相邻。将两个分区合并，并修改后一分区表项的始址和大小。
3. 回收区同时和插入点的前后两个分区相邻。将三个分区合并，修改前一分区表项的大小为三者之和，取消后一分区表项。
4. 回收区没有相邻的空闲分区，此时应该为回收区新建一个表项，填写始址和大小，插入空闲分区链。

以上的三种内存分区管理方法都有一个特点，即用户程序在主存中都是连续存放的。

• 基于顺序搜索的分配算法

从空间分区链选择分区时，需要按照一定的分配算法。按检索方式可分为顺序分配算法和索引分配算法。

顺序分配算法依次搜索空闲分区链上的空闲分区，以寻找一个大小满足要求的分区。

1. 首次适应(First Fit)算法。空闲分区按地址递增的次序排列，每次分配内存，顺序查询第一个能满足大小的空闲分区，分配给作业。首次适应算法保留了高地址部分的大空闲分区，有利于大作业的装入。但是它会使低地址部分出现许多小碎片，每次分配查找都要经过这些分区，增加了开销。
2. 邻近适应(Next Fit)算法。也称循环首次适应算法。和首次适应的不同之处在于，分配内存时从上次查找结束的位置继续查找。它让内存高低地址部分的空闲分区以同等概率被分配，划分为小分区，导致内存高地址部分没有大空闲分区可用。通常比首次适应算法更差。
3. 最佳适应(Best Fit)算法。空闲分区按容量递增的次序排列。每次分配，顺序查找到第一个能满足大小的空闲分区。最佳适应能更多地留下大空闲分区，但通常性能较差，每次分配会留下越来越多的很小的外部碎片。（产生最多）
4. 最坏适应(Worst Fit)算法。空闲分区按容量递减的次序排列。每次分配时，顺序查找到第一个能满足大小的空闲分区（最大的空闲分区），分割一部分空间给作业。会导致很快没有大空闲分区可用，性能也很差。

综上，首次适应算法的开销小，性能最好，回收分区也不需要对空闲分区重新排序。

• 基于索引搜索的分配算法

系统很大时，空闲分区链可能很长，需要采用索引分配算法。根据其大小对空闲分区分类，对于每类（大小相同）空闲分区，单独设置一个空闲分区链，并设置一张索引表来管理这些空闲分区链。

为进程分配时，在索引表查询得到对应分区链的头指针。

1. 快速适应算法。空闲分区根据进程常用空间的大小进行分类，分配过程分为两步：
   第一步，根据进程的长度，在索引表中找到能容纳它的最小空闲分区链表。
   第二步，从链表中取出第一块进行分配。
   优点是查找效率高，不产生内部碎片。
   缺点是回收分区时，需要有效地合并分区，算法比较复杂，系统开销较大。
2. 伙伴系统。规定所有分区的大小均为2的k次幂。需要分配大小为n的分区时，在大小为$2^i$的空闲分区链中查找。若找到，则分配。否则需要在$2^{i+1}$的分区链中继续查找。若存在$2^{i+1}$的分区，则将其分为两个分区，这两个分区称为一对伙伴，其中一个用于分配，另一个则加入$2^i$的空闲分区链。回收时，也可能需要对伙伴分区进行合并。
3. 哈希算法。根据空闲分区链表的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，每个表项记录一个对应空闲分区链的头指针。分配时，根据所需分区大小，通过哈希计算找到哈希表中的位置。

采用连续分配方式，如果没有超过1GB的连续空间，即使内存空闲空间超过1GB，也无法运行需要1GB空间的任务；若采用非连续分配方式，则作业需要的内存空间可以分散地分配在内存的各个区域，不过也需要额外的空间去存储他们的索引，使得非连续分配方式的存储密度低于连续分配方式。

非连续分配方式根据分区的大小是否固定分为分页存储管理和分段存储管理。在分页存储管理中，又根据运行作业时是否要将所有页面装入内存，分为基本分页存储管理和请求分页存储管理。

3.1.3 基本分页存储管理（重点）

固定分区会产生内部碎片，动态分区会产生外部碎片，这两者对内存的利用率都比较低。

分页的思想：将内存空间分为若干固定大小的分区，称为页框、页帧或物理块。进程的逻辑地址空间也分为与块大小相等的若干区域，称为页或页面。操作系统以页框为单位为各个进程分配内存空间。

分页管理不产生外部碎片，块的大小相对分区要小很多。进程也按块进行划分，进程运行时按块申请主存空间。进程只会在为最后一个不完整的块申请一个主存空间时才产生一个很小的内部碎片（也称页内碎片），这种碎片相对进程来说也是很小的。

分页存储的几个基本概念

• 页面和页面大小

每个页面有一个编号，称为页号，从0开始；内存中的每个页框也有一个编号，称为页框号或物理块号，从0开始。进程需要为每个页面分配内存中的可用页框，产生页号和页框号的一一对应。

为了方便地址转换，页面大小应该是2的整数次幂，页面大小应该适中，页面太小会导致进程页面数过多，页表就会过长，占用大量内存，同时增加地址转换的硬件开销，降低页面换入/换出的效率；页面过大又会使页内碎片增多，降低内存的利用率。

• 地址结构

地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。地址长度为32位，0-11位表示页内地址，12-31位为页号。

如果有K位表示页内偏移量，则说明一个页面的大小是$2^K$个内存单元；

如果有M位表示页号，则说明一个进程最多有$2^M$个页面。

• 页表

为了便于找到进程的每个页面在内存中存放的位置，系统为每个进程建立一张页面映射表，简称页表。每个页面对应一个页表项，由页号和块号组成，记录了页面在内存中对应的物理块号。页表的作用是从页号到物理块号的地址映射。

基本地址变换机构

地址变换机构的任务是将逻辑地址转换为内存中的物理地址。地址变换是借助页表实现的。

由于页表项连续存放，因此页号可以是隐含的，不占用存储空间。

为了提高地址变换的速度，在系统中设置一个页表寄存器(PTR)，存放页表在内存的始址F和页表长度M。单CPU只设置一个页表寄存器。进程未执行时，F和M存放在本进程的PCB中，当进程被调度执行时，才将F和M装入页表寄存器中。

设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

1. 根据逻辑地址计算出页号$P=A\div L $、页内偏移量$W=A \% L$。
2. 判断页号是否越界，若页号P>=页表长度M，则产生越界中断，否则继续执行。
3. 在页表中查询页号对应的页表项，确定页面存放的物理块号。$P对应的页表项地址=F+P\times 页表项长度$，取出页表项内容b，即物理块号。
4. 计算物理地址$E=b\times L+W$，用物理地址E去访存。
   物理地址=页面始址+页内偏移量；页面始址=块号$\times$块大小（页面大小）。

整个地址变换过程均是由硬件自动完成的。页式管理只要给出一个整数就能确定对应的物理地址，因此页式管理中地址空间是一维的。

以32位地址空间，字节编制，一页4KB为例，总共能划分出$2^{20}$页，需要20位表示页面范围，又因为是字节编址所以需要$\lceil \frac{20}{8} \rceil=3$B。因此页表项的大小应该大于等于3B。

具有快表的地址变换机构

如果页表全部放在内存中，则存取一个数据或一条指令至少要两次访存。第一次是访问页表，确定指令或数据的物理地址；第二次是根据地址存取。

为此在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器：快表(TLB)，也称为相联存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。主存中的页表则称为慢表。

地址的变换过程如下：

1. CPU给出逻辑地址，硬件进行转换，将页号和快表中的页号比较。
2. 若找到匹配的页号，直接从中取出对应的页框号，与页内偏移量拼接形成物理地址，这样只需一次访存。
3. 若未找到，需要访问主存中的页表。读出页表项后将其存入快表，以便后续访问。如果快表已满，则按一定的算法 淘汰一个旧页表项。

一般快表的命中率在90%以上，快表的有效性基于局部性原理。

两级页表

还需要考虑页表过大的问题，因为页表项是连续的。

解决方法有两种：

1. 对于页表所需的内存空间采用离散分配的方式，用一张索引表记录各个页表的存放位置。
2. 只将当前需要的部分页表项调入内存，其余需要时再调入。

实际上可以为离散分配的页表再建立一张页表，称为外层页表或页目录。

页表的每个表项中，存放的是进程某页对应的物理块号；外层页表的每个表项中，存放的是某个页表分页的始址。可以利用外层页表和页表实现进程从逻辑地址到物理地址的转换。

为了实现地址转换，需要增设一个外层页表寄存器（也称页目录基址寄存器），用于存放页目录始址。将逻辑地址的页目录号作为页目录索引，找到页表的始址；再用二级页号作为页表分页的索引，找到对应的页表项；将页表项的物理块号和页内偏移拼接，形成物理地址，访问内存单元，总共进行了3次访存。

对于更大的逻辑地址空间，则需要多级页表，再对外层页表进行分页。多级页表的目的在于建立索引，避免浪费空间去存储无用的页表项。

3.1.4 基本分段存储管理

分页方式是从计算机的角度考虑的，目的是提高内存利用率，提升计算机性能。

分页通过硬件机制实现，对用户完全透明。而分段考虑了用户和程序员，满足方便编程、信息保护和共享、动态增长和动态链接等多方面的需要。

分段

分段系统将用户进程的逻辑地址分为大小不等的段，每段从0开始编址，段内要求连续，段间不要求连续，地址空间是二维的。

分段存储管理的逻辑地址由段号S和段内偏移量W组成。

在页式系统中，逻辑地址的页号和偏移量对用户是透明的，但是在分段系统中，段号和段内偏移量必须是用户显式提供。在高级程序设计语言中，这个工作由编译程序完成。

段表

每个进程都有一张逻辑空间和内存空间映射的段表，每个段对应一个段表项，段表项中记录了该段在内存中的始址和段长。段表用于实现逻辑段到物理内存区的映射。

地址变换机构

为了实现逻辑地址到物理地址的变换，设置一个段表寄存器，用于存放段表始址F和段表长度M。

1. 从逻辑地址取出前几位为段号S，后几位为偏移量W。
2. 判断段号S是否越界，若S>=M，则产生越界中断，否则继续。（段号从0开始，段表长度至少为1，因此相等也是越界）
3. 在段表中查询段号对应的段表项，S对应的段表项地址=F+S$\times$段表项长度。取出段表项中的段长C，若W>C，则产生越界中断，否则继续。
4. 取出段表项中的始址b，计算物理地址E=b+W，用物理地址E去访存。

分段和分页的对比

两者都是非连续分配方式，都要通过地址映射机构实现地址变换。但是概念上两者完全不同。

1. 页是信息的物理单位，分页的目的是提高内存利用率，完全是系统的行为，对用户不可见。段是信息的逻辑单位，分段的目的是更好地满足用户需求，用户按照逻辑关系将程序划分为若干段，对用户可见。
2. 页的大小固定，且由系统决定。段的长度不固定，具体取决于用户编写的程序。
3. 分页管理的地址空间是一维的。而分段管理不能通过一个整数便确定对应的物理地址，需要显示给出段号和段内偏移，因此分段管理的地址空间是二维的。

段的共享和保护

在分页中虽然也能共享，但是远不如分段方便。共享代码如果占N个页面，则每个进程都要建立N个页表项，指向被共享的N个页框。

分段中，不管该段有多大，都只需为该段设置一个段表项。只需在每个进程的段表设置一个段表项，指向被共享的同一个物理段。

不能被任何进程修改的共享代码称为可重入代码或纯代码，不属于临界资源。为了防止被修改，在每个进程中都必须配置局部数据区，将可能改变的部分复制到数据区。

分段的保护方法有两种：存取控制保护和地址越界保护。地址越界保护将段表寄存器中的段表长度和段号比较，将段长和逻辑地址的段内偏移进行比较，如果出错（后者比前者大）就会产生越界中断。而分页管理只需要判断页号，页内偏移不会越界。

3.1.5 段页式存储管理

分页有效提高内存利用率，分段能反映程序的逻辑结构并有利于段的共享和保护，将两者结合得到段页式存储管理。（段式管理会产生外部碎片）

地址空间仙贝分成若干逻辑段，每段都有自己的段号，然后将每段分成若干固定大小的页。对内存空间的管理和分页存储管理一样，分为若干和页面大小相同的存储块，对内存的分配以存储块为单位。

逻辑地址分为段号、页号和页内偏移量三部分。

实现地址变换：每个进程建立一张段表，每个段表项至少包含段号、页表长度和页表始址；每个段有一张页表，每个页表至少包含页号和块号。此外还有一个段表寄存器，指出进程的段表始址和段表长度。

在段页式存储管理中，每个进程的段表只有一个，而页表可能有多个。

3.2 虚拟内存管理

3.2.1 虚拟内存的基本概念

传统存储管理方式的特征

3.1讨论的内存管理策略都有以下共同特征：

1. 一次性。作业必须一次性全部装入内存后才可以开始运行，这会导致大作业无法装入内存而无法运行，同时会导致大量作业要求运行时内存不足，导致多道程序的并发度下降。
2. 驻留性。作业被装入内存后，任何部分都不会换出，直到运行结束。运行中的进程会因等待I/O而被阻塞，可能处于长期等待。

局部性原理

快表、页高速缓存以及虚拟内存都属于高速缓存技术，依赖局部性原理。

局部性原理的介绍参见计算机组成原理。（时间局部性、空间局部性）

虚拟存储器的定义和特征

程序装入时，仅需将当前运行需要的少数页面（或段）装入内存，其余部分暂留在外存。

所访问信息如果不在内存，由操作系统负责将所需信息调入内存，这个过程就是请求调页/段功能。当内存空间不够时，由操作系统将内存中暂时用不到的信息换出外存，这个过程就是页面/段置换功能。

这样，系统就像是为用户提供了一个比实际容量大得多存储器，称为虚拟存储器。

系统提供的部分装入、请求调入、置换功能均对用户透明。虚拟存储器有以下三大特征：

1. 多次性。作业允许被分成多次调入内存，需要时再调入需要的部分。多次性是虚拟存储器最重要的特征。
2. 对换性。作业无需常驻内存，而是允许将暂不使用的程序和数据调至外存的对换区，需要时再调入。正是由于对换性，才使得虚拟存储器得以正常运行。
3. 虚拟性。从逻辑上扩充了内存容量。这是虚拟存储器表现出来的最重要特征，也是最重要目标。

虚拟内存技术的实现

虚拟内存的实现有三种方式：

1. 请求分页存储管理。
2. 请求分段存储管理。
3. 请求段页式存储管理。

不管哪种方式都需要硬件支持，一般需要：

1. 一定容量的内存和外存。
2. 页表/段表机制，作为主要的数据结构。
3. 中断机构，当用户访问的部分未调入内存时，产生中断。
4. 地址变换机构。

3.2.2 请求分页管理方式

页表机制

在请求分页系统中，操作系统需要知道每个页面是否已经调入内存。若未调入，还需要知道该页在外存中的存放地址。操作系统还要通过一些指标决定换出哪个页面，对于要换出的页面，还需要知道是否被修改过，决定是否写回外存。

为此在请求页表项增加了四个字段:

1. 状态位P：标志该页是否已调入内存。
2. 访问字段A：记录本页在一段时间内被访问的次数，或本页最近已经有多长时间未被访问。
3. 修改位M：标记该页在调入内存后是否被修改过，以决定换出时是否写回外存。
4. 外存地址：记录该页在外存的存放地址，通常是物理块号，供调入该页时参考。

缺页中断机构

当访问的页面不在内存时，产生一个缺页中断请求缺页中断处理程序。此时缺页的进程阻塞，调页完成后唤醒，放回就绪队列。

若内存中有空闲页框，则为进程分配一个页框，将页面装入，并修改页表中的对应项。若没有空闲页框，则由页面置换算法选择一个页面淘汰，若该页面在内存中被修改过，还要写回外存。

缺页中断与一般的中断有两个区别：

• 在指令执行期间而非指令执行结束后产生和处理中断，属于内部异常中的故障。
• 一条指令在执行期间，可能产生多次缺页中断。

地址变换机构

变换过程如下：

1. 先检索快表，若命中，取出对应物理块号，并修改页表项中的访问位。如果是写指令，还要将修改位置为1。
2. 快表未命中，从页表查找，若找到，则取出物理块号，写入快表。如果快表已满则用某种算法替换。
3. 页表中未找到，则需要进行缺页中断处理，将该页从外存换入内存，页面调入内存后，由操作系统更新页表和快表，并获得物理块号。
4. 利用得到的物理块号和页内地址拼接成物理地址，然后访存。

3.2.3 页框分配

驻留集大小

给一个进程分配的页框的集合称为这个进程的驻留集。

1. 驻留集越小，驻留在内存中的进程就越多，可以提高并发度，但是分配给进程的页框太少，会导致缺页率太高，CPU花费大量时间来处理缺页。
2. 驻留集越大，当分配给进程的页框超过某个数目后，再为进程增加页框对缺页率的改善是不明显的，反而只是浪费内存空间，降低并发度。

内存分配策略

在请求分页系统中，可以采取固定和可变分配策略。进行置换时，也可以采用全局和局部置换。

• 固定分配局部置换

为每个进程分配固定数目的物理块，在运行期间都不改变。局部置换指进程中如果缺页，只能从分配在该进程在内存中的一页换出，保证分配给这个进程的内存空间不变。

实现这种策略时，难以确定要分配的物理块数目，太少会频繁出现缺页，太多会降低CPU和其他资源利用率。

• 可变分配全局置换

先为每个进程分配一定数目的物理块，运行期间视情况增加或减少。全局置换指进程中如果缺页，系统从空闲物理块队列取出一块分配给该进程。

这种方法更加灵活，可以动态增加进程的物理块，但是会盲目地增加，从而导致并发能力下降。

• 可变分配局部置换

先为每个进程分配一定数目的物理块，运行期间视情况增加或减少。如果缺页，只能从分配在该进程在内存中的一页换出。

如果进程在运行中频繁发生中断，则系统再为进程分配若干物理块，直到缺页率趋于适当程度；如果缺页率特别低，则适当减少分配给该进程的物理块，但是不能引起缺页率的明显增加。

这种方法保证进程不会过多调页的同时也保持了并发能力，虽然需要更复杂的实现，也需要更大的开销，但是对比频繁换入换出的开销，是值得的。

物理块调入算法

采用固定分配策略时，可采用下面的算法：

1. 平均分配算法，将系统所有可分配的物理块平均分配给各进程。
2. 按比例分配算法，根据进程的大小按比例分配物理块。
3. 优先权分配算法，为重要和紧迫的进程分配较多的物理块。

通常采取的办法时将所有可分配的物理块分成两部分，一部分按比例分配给各个进程；一部分根据优先权分配。

调入页面的时机

1. 预调页策略。根据局部性原理，一次调入若干个相邻的页面会比一次调入一页更高效。但是如果提前调入的页面大多数都未被访问，则又是低效的。因此可以预测不久之后可能要被访问的页面，预先调入内存。不过预测成功率不高（约50%），这种策略主要用于进程的首次调入，由程序员指出应该调入哪些页。
2. 请求调页策略。进程需要的页面不在内存，就提出请求，由系统将其调入内存。这种策略调入的页必定被访问，而且比较容易实现。目前的虚拟存储器大多采用此策略。缺点是每次只调入一页，增加了磁盘I/O开销。

预调入实际上就是运行前的调入，请求调页实际上就是运行期间的调入。

从何处调入页面

请求分页的外存分为存放对换页面的对换区（交换区）和存放文件的文件区。

对换区采用连续分配方式，文件区采用离散分配方式，因此对换区的磁盘I/O更快。发生缺页请求时，系统从何处调入缺页分为三种情况：

1. 系统拥有足够的对换区空间。可以全部从对换区调入所需页面，提高调页速度。在运行前需要将与进程有关的文件从文件区复制到对换区。
2. 系统缺少足够的对换区空间。不会被修改的文件都直接从文件区调入；当换出这些页面时，由于它们不会被修改而不必再换出。可能被修改的部分，将它们换出时必须放在对换区，需要时再从对换区调入。
3. UNIX方式。与进程有关的文件都存放在文件区，未运行过的页面都从文件区调入。曾经运行过但是被换出的页面，由于是存放在对换区，下次调入应从对换区调入。进程请求的共享页面如果被其他进程调入内存。则不需要从对换区调入。

如何调入页面

进程访问的页面不在内存中时，向CPU发出缺页中断，中断响应后转入缺页中断处理程序。

通过查询页表得到该页的物理块，如果内存未满，则启动磁盘I/O，将缺页调入内存，修改页表。

如果内存已满，则先按某种置换算法从内存中选出一页准备换出；若该页未被修改过，则不需要写回磁盘；如果修改过，必须写回磁盘，然后将缺页调入内存，修改页表，置存在位为1。

3.2.4 页面置换算法

最佳（OPT）置换算法

最佳置换算法选择淘汰的页面是以后永不使用的页面，或是最长时间不再被访问的页面，以保证获得最低的缺页率。然而，人们无法预测哪个页面是未来最长时间不再被访问的，该算法无法实现。

先进先出（FIFO）置换算法

FIFO选择淘汰的页面是最早进入内存的页面。该算法实现简单，根据调入的先后顺序排成一个队列，需要换出时选择队头即可。但是该算法没有利用局部性原理，因此性能较差。

FIFO还会产生位进程分配的物理块增多，缺页次数不减反增的现象，称为Belady异常。只有FIFO算法可能出现Belady异常，LRU和OPT算法永远不会出现Belady异常。

最近最久未使用（LRU）置换算法

LRU算法选择淘汰的页面是最近最长时间未使用的页面，为每个页面设置一个访问字段，用来记录页面自上次访问以来经历的时间，淘汰值最大的页面。

LRU算法的性能较好，但是需要寄存器和栈的硬件支持，LRU是类堆栈类的算法，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

时钟（CLOCK）置换算法

LRU算法的性能接近OPT算法，但是实现起来的开销大。CLOCK算法的变体的开销比较小，性能接近LRU。

• 简单的CLOCK置换算法

为每个页面设置一个访问位，当页面首次装入或被访问时，访问位被置为1。算法将内存中的页面链接成一个循环队列，并有一个替换指针与之相关联。

某一页被替换时，该指针指向被替换页面的下一页。选择淘汰一页时，只需要检查页面的访问位，如果为0，就选择该页换出，如果为1，就置为0，暂不换出，给予第二次驻留内存的机会，继续依次检查，如果所有访问位都为1，则返回到队首去再次循环检查。

由于该算法是循环检查各个页面的使用情况，所以称为CLOCK算法。但是该算法只有一位访问位，而置换时将未使用的页面换出，所以也称为最近未用(NRU)算法。

• 改进型CLOCK置换算法

将一个页面换出时，如果该页已经被修改过，则需要将该页写回磁盘。该页未被修改则不必写回磁盘。

在改进型CLOCK算法中，除了考虑页面使用情况外，还增加了置换代价修改位。选择页面换出时，优先考虑未使用过也未修改过的页面。

设访问位A，修改位M，可以组合成4种类型的页面：

1. 1类A=0,M=0：最近未被访问，且未被修改，是最佳的淘汰页。
2. 2类A=0,M=1：最近未被访问，但已被修改，是次佳的淘汰页。
3. 3类A=1,M=0：最近已被访问，但未被修改，可能再被访问。
4. 4类A=1,M=1：最近已被访问，且已被修改，可能再被访问。

内存中的每页肯定都是这4种之一。算法执行过程：

1. 从当前指针开始，循环扫描队列，寻找1类页面，将遇到的第一个1类页面淘汰。第一次扫描不改变A。
2. 第一步失败进行第二轮扫描，寻找2类页面。在扫描期间，将所有扫描过的页面的访问位A都置为0。
3. 若第二步也失败，将指针回到开始的位置，将所有帧的访问位复0。重复第一步，若有必要，重复第二步，此时一定能找到被淘汰的页。

改良型的CLOCK算法相比简单CLOCK算法，可以减少磁盘I/O的操作次数，但是为了找到一个可置换的页，增加了几轮扫描，算法本身的开销增加了。

页面置换算法都有一个原则：尽可能保留访问过的页面，淘汰未访问过的页面。简单CLOCK只考虑页是否访问过；改进CLOCK在这基础上还考虑了优先替换未修改过的页面。如果全部页面都使用过，还是优先替换未修改的页面。

3.2.5 抖动和工作集

抖动

刚刚换出的页面马上又换入内存，刚刚换入的页面马上又换出内存，频繁的页面调度行为称为抖动或颠簸。

造成这种原因的根本是分配给每个进程的物理块太少，不能满足进程正常运行的基本要求。

抖动是进程运行时出现的严重问题，由于抖动的发生与系统分配的物理块的多少（驻留集）有关，又提出了进程工作集的概念。

工作集

工作集是指在某段时间间隔内，进程要访问的页面集合。工作集W可由时间t和工作集窗口尺寸$\Delta$来确定。

假设工作集窗口尺寸$\Delta$为5，则在$t_1$时刻，进程的工作集为{2,3,5}，$t_2$时刻，进程的工作集为{1,2,3,4}。实际应用中，工作集窗口会设置的很大，局部性好的程序的工作集大小一般会比工作集窗口$\Delta$小很多。

工作集反映了进程在接下来的一段时间内很有可能会频繁访问的页面集合，因此驻留集大小不能小于工作集，否则进程在运行过程中会频繁缺页。

3.2.6 内存映射文件

内存映射文件是操作系统向应用程序提供的一个系统调用，和虚拟内存相似，在磁盘文件和进程的虚拟地址空间之间建立映射关系。

进程通过系统调用，将一个文件映射到其虚拟地址空间的某个区域，之后用访存的方式读写文件。这种功能将一个文件当做内存中的一个大字符数组访问，而不通过I/O操作访问。磁盘文件的读写由操作系统完成，对进程是透明的。映射进程的页面时，不会实际读入文件的内容，只有访问页面时才会每次一页地读入。进程退出或关闭文件映射时，所有被改动的页面才写回磁盘文件。

进程可通过共享内存来通信，共享内存是通过映射相同文件到通信进程的虚拟地址空间来实现的。多个进程映射到同一个文件时，各进程的虚拟地址空间都是相互独立的，但是操作系统将这些虚拟地址空间映射到相同的物理内存（通过页表实现）。

内存映射文件带来的好处：

1. 使程序员的编程更简单，已建立映射的文件只要访存就可以读写。
2. 方便多个进程共享同一个磁盘文件。

3.2.7 虚拟存储器性能影响因素

缺页率是影响虚拟存储器性能的主要因素，缺页率又受到页面大小、分配给进程的物理块数、页面置换算法以及编程方法的影响。

根据局部性原理，页面较大缺页率低，页面较小缺页率高。页面较小时，减少了内存碎片，有利于提高内存利用率；但是也会导致页表过长，占用了大量内存。页面较大，虽然可以减少页表长度，但是会使页内碎片增大。

进程分配的物理块数越多，缺页率就越低。当物理块超过某个数目后，对缺页率的改善就不明显了，只要保证活跃页面在内存中，保持缺页率在一个很低的范围即可。

好的页面置换算法可以使进程在运行过程中有较低的缺页率，选择LRU、CLOCK等置换算法。

写回磁盘的频率。换出已修改的页面时必须写回磁盘，换一次写一次开销很大。所以要建立一个已修改换出页面的链表，页面到达一定值再一起写回，可以减少I/O开销。如果有进程在这批数据还未写回就再次访问，则可以不用从外存调入，直接在链表上获取，减少开销。

编写程序的局部化程度越高，执行时的缺页率就越低，如果是按行存储，就要尽量采用相同的访问方式，避免按列访问造成缺页率过高。

3.2.8 地址翻译