第 3 章 内存管理
内存管理概念
内存管理的主要功能：
内存空间的分配与回收。由操作系统负责内存空间的分配和管理，记录内存的空闲空间、内存的分配情况，并回收已结束进程所占用的内存空间。
地址转换。由于程序的逻辑地址与内存中的物理地址不可能一致，因此存储管理必须提供地址变换功能，将逻辑地址转换成相应的物理地址。
内存空间的扩充。利用虚拟存储技术从逻辑上扩充内存。
内存共享。指允许多个进程访问内存的同一部分。例如，多个合作进程可能需要访问同一 块数据，因此必须支持对内存共享区域进行受控访问。
存储保护。保证各个进程在各自的存储空间内运行，互不干扰。
存储器的层次结构
存储器的多层结构
可执行存储器
寄存器和主存储器称为可执行存储器
主存储器与寄存器
主存储器
简称内存或主存，是计算机系统中的主要部件，用于保存进程运行时的程序和数据
寄存器
高速缓存和磁盘缓存
高速缓存
介于寄存器和存储器之间（cache）
磁盘缓存
介于磁盘 I/O 与主存之间
程序的装入和链接
（1）编译，有编译程序对用户源程序进行编译，形成若干目标模块
（2）链接，由链接程序将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块。
（3）装入，由装入程序将装入模块装入内存
装入方式：
绝对装入方式
将物理地址装入该进程的内存起始位置，也就是装入到内存中事先指定的位置，适合单道程序环境
可重定位装入方式
根据内存的具体情况将装入模块装入到内存的适当位置，逻辑地址与实际装入内存后的物理地址不同。允许装入到内存中任何允许的位置
必须执行时分配其要求的全部内存空间，运行期间不能再移动
重定位：把在装入时对目标程序中指令和数据地址的修改过程称为重定位。
静态重定位：装入之后不在改变
动态运行时的装入方式
动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才运行。所以装入内存后的所有地址都是逻辑地址。可以将程序分配到不连续的存储区。
源程序经过编译后，可得到一组目标模块。链接程序的功能就是把这组目标模块以及它们所需要的库函数装配成一个完整的装入模块。在进行链接时，根据链接的时间不同，分以下三种情况：
静态链接方式
在程序运行之前，先将各模块以及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。事先链接方式
装入时动态链接
指将用户源程序编译后所得到的一组目标模块，在装入内存时，采用边装入边链接的链接方式。即在装入一个目标模块时，若发生一个外部模块调用时间，将引起装入程序去找出相应的外部目标模块，并将它装入内存
运行时动态链接
将对某些模块的链接推迟到程序执行时才进行，当执行过程总发现一个被调用的模块尚未装入内存时，立即由 OS 去找到该模块，并将之装入内存，将其链接到调用者模块上，凡事未被使用的模块都不会被装入到内存和被链接到装入模块上。
编译后，每个目标模块都从 0 号单元开始编址，这称为该目标模块的相对地址(或逻辑地址)。 当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相 对地址构成统 一的从 0 号单元开始编址的逻辑地址空间(或虚拟地址空间)。
物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指 令和访问数据，最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称地址重定位。
操作系统通过*内存管理部件(MMU)*将进程使用的逻辑地址转换为物理地址
进程中的内存映像
代码段:即程序的二进制代码，代码段是只读的，可以被多个进程共享。
数据段:即程序运行时加工处理的对象，包括全局变量和静态变量。
进程控制块(PCB):存放在系统区。操作系统通过 PCB 来控制和管理进程。
堆:用来存放动态分配的变量。通过调用 malloc 函数动态地向高地址分配空间。
栈:用来实现函数调用。从用户空间的最大地址往低地址方向增长
内存保护
根据一个地址判断是否越界，内存保护可采取两种方法：
在 CPU 中设置一对上、下限寄存器，存放用户进程在主存中的下限和上限地址，每当 CPU 要访问一个地址时，分别和两个寄存器的值相比，判断有无越界。
采用**重定位寄存器 (也称基地址寄存器)和界地址寄存器 (也称限长寄存器)**进行越界捡查。重定位寄存器中存放的是进程的起始物理地址（装入方式采用动态重定位装入），界地址寄存器中存放的是进程的最大逻辑地址。内存管理部件将逻辑地址与界地址寄存器进行比较，若未发生地址越界，则加上重定位寄存器的值后映射成物理地址，再送交内存单元。
实现内存保护需要重定位寄存器和界地址寄存器，因此要注意两者的区别。重定位寄存器是用来加的，逻辑地址加上重定位寄存器中的值就能得到物理地址;界地址寄存器是用来比的，通过比较界地址寄存器中的值与逻辑地址的值来判断是否越界。
连续分配存储管理方式
- 单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区，系统区仅供操作系统使用，通常在低 地址部分;用户区内存中仅有一道用户程序，即用户程序独占整个用户区。不存在外部碎片
- 固定分区分配
将用户空间划分成若干个固定大小的区域，在每个分区装入一道作业。
划分分区的方法：
分区大小相等
分区大小不等。
内存的分配： 建立分区使用表管理分区
问题：程序太大而放不进任何一个分区;当程序小于固定分区大小时， 也要占用一个完整的内存分区，这样分区内部就存在空间浪费，这种现象称为内部碎片；
- 动态分区分配
又称为可变分区分配，它是根据进程的实际需要，动态地为之分配内存空间。内存中会产生越来越多的小内存块，内存的利用率也随之下降。这些小内存块被称为外部碎片，外部碎片可通过紧凑技术来克服，即操作系统不时地对进程进行移动和整理。但是，这需要动态重定位寄存器的支持，且相对费时。紧凑过程实际上类似于 Windows 系统中的磁盘碎片整理程序，只不过后者是对外存空间的紧凑。 
（1）基于顺序搜索的动态分区分配算法
为了实现动态分区分配，通常是将系统中的空闲分区链接成一个链。所谓顺序搜索，是指一次搜索空闲分区链上的空闲分区，去寻找一个其大小满足要求的分区。
首次适应（First Fit）算法
FF 要求空闲分区链以地址递增的次序链接，再分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区。优先利用内存中低地址部分，保留高地址的大空闲区，缺点就是低址部分不断被划分，会留下许多难以利用的、很小的空闲分区，称为碎片。而每次又是头开始查找。
循环首次适应（NF）算法（邻近适应算法）
在 FF 算法上改进，不是每次都是从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。
优点：能使内存中的空闲分区分布更加均匀，从而减少了查找空闲分区时的开销，
缺点：会缺乏大的空闲分区
最佳适应（BF）算法
空闲分区按容量递增的次序排列。所谓“最佳”是指，每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。要求所有空闲分区按其容量以从小到大的顺序形成-空闲分区链。会存在碎片问题。
最坏适应算法（WF）
与最佳适应相反，总是挑选一个最大的空闲区，从中分割一部分存储空间给作业使用，以至于存储器中缺乏大的空闲分区，故把它称为是最坏适应算法。
要求按容量的从大到小的顺序排列。
优点：可使剩下的空闲区不至于太小，产生碎片的可能性最小，对中、小作业有利。
（2）基于索引搜索的动态分区分配算法
索引分配算法的思想是，根据其大小对空闲分区分类，对于每类 (大小相同)空闲分区，单独设立一个空闲分区链，并设置一张索引表来管理这些空闲分区链。 当为进程分配空间时，在索引表中查找所需空间大小对应的表项，并从中得到对应的空闲分区链的头指针，从而获得一个空闲分区 。索引分配算法有以下三种：
快速适应算法
又称为分类搜索算法，将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，内存中设立一个管理索引表，其中的每一个索引项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。空闲分区的分类是按照进程常用的空间大小进行划分的。分配时，不会对分区进行分割。不会产生碎片
缺点：为了有效合并分区，在分区归还主存时的算法复杂，系统开销大。
伙伴系统
哈希算法
利用哈希快速查找的优点，以及空闲分区在可利用空闲区标中的分布规律，建立哈希函数，构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。
当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
动态可重定位分区分配
紧凑
将原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”
问题：紧凑后的用户程序在内存中的位置发生了变化，必须对移动了的程序或数据进行重定位。
动态重定位
重定位寄存器，用来存放程序在内存中的起始地址，真正访问的地址是相对地址与重定位寄存器中的地址想加而形成的。
动态重定位分区分配算法
与动态分区分配算法基本相同，只是增加紧凑功能。
对换技术
内存紧张时，换出某些进程以腾出内存空间，再换入某些进程
磁盘分为文件区和对换区，换出的进程放在对换区
- 多道程序环境下的对换技术：
对换的引入
兑换：指把内存中暂时不能运行的进程或者暂时不用的程序和数据换出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需的程序和数据换入内存。改善内存利用率的有效措施，它可以直接提高处理机的利用率和系统的吞吐量。
对换的类型
（1）整体对换
（2）页面（分段）对换
- 对换空间的管理
兑换空间管理的主要目标
磁盘空间分为：文件区和对换区
1）对文件区的管理和目标
2）对对换区空间的管理的主要目标
对换区空闲盘块管理中的数据结构
对换空间的分配与回收
- 覆盖技术
一个固定区
存放最活跃的程序段
固定区中的程序段在运行过程中不会调入调出
若干覆盖区
不可能同时被访问程序段可共享一个覆盖区
覆盖区中的程序段在运行过程中会根据需要调入调出
必须由程序猿声明覆盖结构，OS 完成自动覆盖
缺点：对用户不透明，增加了用户编程负担
- 覆盖与对换的区别
覆盖是在同一个程序或进程中
交换是在不同进程（或作业）之间的
分页存储管理方式
对内存进行离散分配
分页存储管理的基本方法
页面和物理块
（1）页面
将进程的逻辑地址空间分成若干个页，并为各页加以编号，内存的物理地址空间分成若干块，在进程分配内存时，以块为单位，将进程中的若干页分别装入到多个可以不相邻的物理块中
页内碎片：由于进程的最后一页经常装不满一块，而形成了不可利用的碎片，称为页内碎片。
内存： 页框 = 页帧 = 内存块 = 物理块= 物理页面
进程：页 、页面
进程的页面与内存的页框具有一一对应的关系
（2）页面大小
页面的大小应适当选择，太小，可以减少内存碎片，提高内存利用率，但会导致进程的页表过长，占用大量内存。太大，可以减少页表的长度，提高页面换入换出的速度，但会使页内碎片增大。通常为 2 的幂。
地址结构
页号 P 位移量 W（页内地址）
页表
一进程对应一张页表，进程的每个页面对应一个页表项，每个页表项：页号+ 块号，记录着进程页面和实际存放的内存块之间的映射关系。
页号与物理块号的映射表
页表项至少占多少字节？
页号 = 逻辑地址 / 页面大小
页内偏移量 = 逻辑地址 % 页面大小
物理地址 = 页面在内存中的起始地址 + 页内偏移量
- 地址变化机构
将用户地址空间中的逻辑地址转为内存空间中的物理地址
页内地址和物理地址是一一对应的，无需转换，所以地址变换机构的任务实际上只是将逻辑地址中页号变换为内存中的物理块号，可以借助页表来实现。
基本的地址变换机构
页表寄存器：存放页表再内存的起始地址和页表的长度
逻辑地址 -> 物理地址：将逻辑地址中的页号取出，将页号与页表寄存器中的页表长度进行比较，检测是否越界，将页号*页表项长度 + 页表起始地址 = 该页表项在页表中的位置，读出页表项的数据，取物理块号，再拼接上页内地址，得到物理地址。
页表长度指的是这个页表总共有几个页表项，即共有几个页。
页表项长度指的是每个页表项占多大的存储空间
页面大小指的是一个页面占多大的存储空间
页式管理中地址是一维的，也就是说只用告诉 CPU 一个逻辑地址就可以得到物理地址
具有快表的地址变换机构
由于页表是存放在内存中的，这使得 CPU 在每存取一次数据，都要访问两次内存。第一次，将逻辑地址转为物理地址。第二次，从第一次得到的地址中获取所需数据（或写入数据）。快表（TLB）就是为了解决这个问题，快表位于 CPU 中，用以存放当前访问的那些页表项（最近访问页表项的副本）
有效访问时间：从进程发出指定逻辑地址的访问请求，经过地址变化，到在内存中找到对应的物理地址单元并取出数据，所需要花费的总时间。
分段存储管理方式
分段存储管理方式的引入
方便编程
信息共享
信息保护
动态增长
动态链接
分段系统的基本原理
分段
作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。
段表
地址变化机构
段表放在内存中，每访问一个数据，都须访问两次内存
分页和分段的主要区别
（1）页是信息的物理单位。
（2）页的大小固定且由系统决定。
（3）分页的用户程序地址空间是一维的。
段页式存储管理方式
结合分页系统和分段系统的优点
基本原理
将用户程序进行分段，再把每个段分成若干页，并为每个段赋予一个段名。
地址结构 段号 段内页号 页内地址
地址变换过程
从逻辑地址 A 中取出前几位为段号 S，后几位为段内偏移量
判断段号是否越界，若段号 S ≥ 段表长度 M，则产生越界中断，否则继续执行。
在段表中查询段号对应的段表项，段号 S 对应的段表项地址= 段表始址 F +段号 Sx 段 表项长度。取出段表项中该段的段长 C，若 W ≥ C，则产生越界中断，否则继续执行。
取出段表项中该段的始址 b，计算物理地址 E = b +W，用物理地址 E 去访存。
虚拟存储区概述
从逻辑上实现对内存容量的扩充
常规存储管理方式的特征和局部性原理
常规存储器管理方式的特征
（1）一次性，指作业必须一次性地全部装入内存后方能开始运行。
（2）驻留性，装入之后，一直停留在内存中，任何部分都不会被换出，直到作业运行结束
局部性原理
在很短时间内，程序的执行仅限于某个部分。
（1）程序顺序执行，除开少数转移和过程调用指令
（2）过程调用
（3）程序中存在许多的循环结构
（4）对数数组的处理
（1）时间局部性：程序中的某条指令被执行，则不久以后该指令可能再次执行。（循环结构）
（2）空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问到（程序的顺序执行、向量、数组、表等）
虚拟存储器的基本工作情况
由局部性原理可知，程序在执行的时候，没有必要全部装入内存，而是仅将那些当前需要运行的少数页面或段先装入内存便可执行，其余部分停留在盘上。如果访问的页或段不再内存中，便发出缺页中断，如果内存已满，通过页面置换算法，换入换出一些页面。
虚拟存储器的定义和特征
虚拟存储器的定义
用户感觉到的内存容量比实际内存容量大得多
指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。
虚拟存储器的特征
（1）多次性。一个作业无需全部装入内存，而是分为多次调入，只将当前运行需要的那部分程序和数据装入内存即可开始运行。
（2）对换性。一个作业中的程序和数据无需一直常驻内存，允许在作业运行过程中进行对换。
（3）虚拟性。从逻辑上进行扩充内存容量，使用户看到的内存容量远大于实际内存容量。
虚拟存储器的实现方法
虚拟内存的实现需要建立在离散分配的内存管理方式的基础上
分页请求系统
在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页式虚拟系统。
请求分段系统
请求段页式系统
硬件支持：
一定容量的内存和外存。
请求页表机制
缺页中断机构
地址变换机构
逻辑地址到物理地址的变换
请求分页存储管理方式
- 页表机制
| 页号 | 物理块号 | 状态位 P | 访问字段 A | 修改位 M | 外存地址 |
|---|
- 状态位P。标记该页是否已调入内存，供程序访问时参考。
- 访问字段A。记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访 问，供置换算法换出页面时参考。
- 修改位M。标记该页在调入内存后是否被修改过，以决定换出时是否写回外存。
- 外存地址。记录该页在外存的存放地址，通常是物理块号，供调入该页时参考。
- 缺页中断机构
在请求分页系统中，每当要访问的页面不在内存时，便产生一个缺页中断，请求操作系统的缺页中断处理程序处理。此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列。若内存中有空闲页框，则为进程分配一个页框，将所缺页面从外存装入该页框，并修改页表中的相应表项，若内存中没有空闲页框，则由页面置换算法选择一个页面淘汰，若该页在内存期间被修改过，则还要将其写回外存。未被修改过的页面不用写回外存。
缺页中断与一般的中断相比较，主要区别：
- 在指令执行期间而非一条指令执行完后产生和处理中断，属于内部异常
- 一条指令在执行期间，可能产生多次缺页中断
- 地址变化机构
1️⃣ 先检索快表，若命中，则从相应表项中取出该页的物理块号，并修改页表项中的访问位， 以供置换算法换出页面时参考。对于写指令，还需要将修改位置为1。
2️⃣ 若快表未命中，则要到页表中查找，若找到，则从相应表项中取出物理块号，并将该页表 项写入快表，若快表已满，则需采用某种算法替换。
3️⃣ 若在页表中未找到，则需要进行缺页中断处理，请求系统将该页从外存换入内存，页面被调入内存后，由操作系统负责更新页表和快表，并获得物理块号。
4️⃣ 利用得到的物理块号和页内地址拼接形成物理地址，用该地址去访存。
请求分页中的内存分配
- 驻留集大小
对于分页式的虚拟内存，在进程准备执行时，不需要也不可能将一个进程的所有页都读入主 存。因此，操作系统必须决定读取多少页，即决定给特定的进程分配几个页框。给一个进程分配的页框的集合就是这个进程的驻留集。
需要考虑以下两点:
驻留集越小，驻留在内存中的进程就越多，可以提高多道程序的并发度，但分配给每个 进程的页框太少，会导致缺页率较高，CPU 需耗费大量时间来处理缺页。
驻留集越大，当分配给进程的页框超过某个数目时，再进程增加页框对缺页率的改善 是不明显的，反而只能是浪费内存空间，还会导致多道程序并发度的下降。
内存分配策略
（1）固定分配局部置换
固定分配：为每个进程分配一组固定数目的物理块，在进程运行期间不再改变
局部置换：如果进程在运行过程中发现缺页，则只能从分配给该进程的 n 个页面中选出一页换出，然后再调入一页，以保证分配给该进程的内存空间不变。
（2）可变分配全局置换
可变分配：指先为每个进程分配一定数目的物理块，在运行期间，可根据情况适当的增加或减少。
全局置换：如果发现缺页，从空闲物理块中选出一块分配给该进程。
（3）可变分配局部置换
不存在固定分配全局置换：因为固定分配一定的物理块，缺页后调入一页将原有驻留集中的所有页都替换了，导致只存在一页在内存中，会发生频繁的缺页。
物理块分配算法
（1）平均分配算法。将系统中所有可供分配的物理块平均分配给各个进程
（2）按比例分配算法。根据进程的大小按比例分配物理块。
（3）考虑优先权的分配算法。
何时调入页面
（1）预调页策略
（2）请求调页策略
从何处调入页面
请求分页系统中的外存分为两部分:用于存放文件的文件区和用于存放对换页面的对换区， 也称交换区。对换区采用连续分配方式，而文件区采用离散分配方式，因此对换区的磁盘1/O速度比文件区的更快。这样，当发生缺页请求时，系统从何处将缺页调入内存就分为三种情况:
1）系统拥有足够的对换区空间。可以全部从对换区调入所需页面，以提高调页速度。为此， 在进程运行前，需将与该进程有关的文件从文件区复制到对换区。
2）系统缺少足够的对换区空间。凡是不会被修改的文件都直接从文件区调入;当换出这些 页面时，由 于它们不会被修改而不必再换出。但对于那些可能被修改的部分，在将它们 换出时必须放在对换区，以后需要时再从对换区调入(因为读比写的速度快)。
3）UNIX方式。与进程有关的文件都放在文件区，因此未运行过的页面都应从文件区调入。曾经运行过但又被换出的页面，由于是放在对换区，因此在下次调入时应从对换区调入。进程请求的共享页面若被其他进程调入内存，则不需要再从对换区调入。
外存：用于存放文件的文件区和用于存放对换页面的对换区
页面调入过程
缺页率 = 访问页面失败的次数 / 访问页面总次数
缺页率受到以下几个因素的影响： （1）页面大小。 （2）进程所分配的物理块的数目。 （3）页面置换算法。 （4）程序固有特性。
页面置换算法
抖动：即刚被换出的页又要被访问，需要将它重新调入，此时又需要再选一页调出；而此刚被调出的页很快又被访问，又需将它调入，如此频繁地更换页面，以致一个进程在运行中大部分时间都花费在页面置换工作上，称为该进程的抖动。
最佳置换算法和先进先出置换算法
最佳置换算法（OPT）
其所选择的被淘汰的页面将是以后永不使用的，或许是在最长（未来）时间内不再被访问的页面。
发生缺页中断不一定发生页面置换
先进先出页面置换算法（FIFO）
总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。 队列
Belady 异常： 物理块数增加 缺页次数不减反增 （只有 FIFO 才会出现）
最近最久未使用（LRU）和最少使用（LFU）置换算法
LRU 置换算法
选出最近最久未使用的页面予以淘汰
LRU 置换算法的硬件支持
1）寄存器 2）栈
最少使用置换算法
选择在最近时期使用最少的页面作为淘汰页。需要继续访问该页的次数（采用移位寄存器）
Clock 置换算法
简单的 Clock 置换算法（最近未使用算法 NRU）
需为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。
实现：当某页被访问时，其访问位被置 1。置换算法在选择一页淘汰时，只需要检查页的访问位。如果是 0，就选择该页换出；若为 1，则重新将它置 0，不换出，再按照 FIFO 算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为 1，再返回队首检查第一个页面。
改进型 Clock 置换算法
考虑置换代价、访问代价
4 中类型的页面（A 访问位，M 修改为）：
1 类（A=0，M=0）:表示未访问过，未被修改过，最佳淘汰页
2 类（A=0，M=1）：表示该页未被访问，但已被修改，不是很好的淘汰页
3 类（A=1，M=0）：已被访问，未被修改，可能再次访问。
4 类（A=1，M=1）:已被访问且已被修改，可能再次访问。
算法执行过程：
（1）从当前位置扫描循环队列，找到 A=0，M=0 淘汰。不改变访问位
（2）第一步失败，找到 A=0 M=1 的页面淘汰，并将所有扫描过的页面的访问位都置 0
（3）第二步失败，重复第一步，寻找 A=0 M=0 的页面，如果失败再执行第二步，此时一定能找到 A=0 M=1 的页面
页面缓冲算法（PBA）
影响页面换进换出效率的因素
（1）页面置换算法 （2）写回磁盘的频率 （3）读入内存的频率
页面缓冲算法 PBA
（1）空闲页面链表
该链表是一个空闲物理块链表，是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程，以降低该进程的缺页率。
（2）修改页面链表
已修改的页面形成的链表。为了减少已修改页面换出的次数
访问内存的有效时间
（1）被访问的页在内存中，对应的页表项在快表中 有效时间 = 查找快表的时间 + 实际访问物理地址的时间 （2）被访问页在内存中，不在快表中 需要访问两次内存，一次访问页表，一次读取数据，还需要更新快表 有效时间 = 查找快表时间 + 查找页表时间 + 修改快表时间 + 访问实际物理地址时间
（3）被访问页不在内存中 产生缺页中断， 有效访问时间 = 查找快表时间 + 查找页表时间 + 处理缺页中断时间 + 更新快表时间 + 更新页表时间 + 访问实际物理地址时间
若有快表的命中率和缺页率
“抖动”与工作集
多道程序度与“抖动”
多道程序度与处理机的利用率
产生抖动的原因
根本原因：同时在系统中的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。
工作集
工作集的基本概念
进程发生缺页率的时间间隔与进程所获的物理块数有关。
工作集的定义
所谓工作集，是指在某段时间间隔 t 里，进程实际所要访问页面的集合。
“抖动”的预防方法
采取局部置换策略
只允许在分配给自己的内存空间内进行置换，不允许从其他进程去获得新的物理块。
把工作集算法融入到处理机调度中
利用“L=S”准测调节缺页率
选择暂停的进程