最近在看操作系统, 感觉操作系统真的是软件工程界人类智慧的结晶了👏👏, 操作系统俨然是一套方法论, 看操作系统真的是能够开阔眼界, 对你的思考、设计、架构的能力都有很大提升(而不仅仅是搬砖:-)), 甚至感觉这东西应该在进入编程领域初就应该知道的, 是每个软件工程师最基本的技能, 操作系统非常值得反复学习、思考、钻研, 里面有很多设计方法、理念值得借鉴和思考. 无奈操作系统太复杂, 内容太多, 因此这篇文章只是用通俗的语言大致介绍了操作系统里面我感兴趣的主要部分, 包括操作系统概述、进程线程模型、内存管理、分布式系统以及Linux系统的实现.

读之前请注意!

这篇文章是我读《操作系统概念》写的读书笔记, 文章内容包括我从这本书和网上学到的知识. 其中很大概率会有错误、片面、过时的内容, 仅供参考. 建议读者自己去读这本书或者直接阅读相关标准.

最好了解过计算机系统组织结构

正文

本篇文章用通俗的语言大致介绍了操作系统是什么, 主要的作用, 操作系统是如何管理硬件资源的. 具体介绍了它的进程、线程模型、CPU调度算法、进程同步机制、解决死锁的方法, 介绍了操作系统的内存分配、虚拟内存机制, 介绍了应用广泛的分布式系统的结构、设计, 最后介绍了优秀的操作系统实例 Linux 的实现.

操作系统概述

操作系统是管理硬件的程序, 它提供两个功能, 向下管理硬件, 向上提供软件运行环境. 由于所管理的硬件不同, 倾向点不同, 操作系统有很多种, 它们各自实现了自己关注的功能. 如大型机操作系统、个人计算机操作系统、手机操作系统、嵌入式设备操作系统等.

现代计算机系统由CPU,内存,磁盘,输入输出设备等组成, CPU 负责不断取指令、执行指令、输出结果到内存, 内存是CPU可以直接访问的大容量存储器, 程序需装载到内存才能运行; 磁盘用于存储大尺寸的静态文件, 程序执行时由磁盘装载到内存中; 输入输出设备有自己的设备控制器, 通过总线与内存相连, 方便输入输出内容.

操作系统负责管理、协调这些硬件, 并且尽可能地提高效率. 操作系统的基本能力(部分):

  • 多道程序能力 —— 操作系统将多个任务保存在内存中, 实现进程、线程模型, 使CPU(伪)并发执行
  • 进程管理—— 操作系统可以创建、删除、挂起、重启进程, 提供进程调度、同步、通信、死锁处理机制
  • 内存管理 —— 为进程合理分配内存、协调管理各存储器
  • 存储管理 —— 实现文件系统、文件管理
  • 保护和安全 —— 保护资源不被非法访问, 防止系统不受内部外部攻击

操作系统能够对用户提供用户界面、程序执行、系统调用接口、I/O操作、文件系统操作、通信、错误检测、资源分配、统计、保护和安全等功能

进程、线程模型

进程

线程

同步机制

同步的目的是要保证进程或线程间的有序协作. 很多进程/线程是协作进程/线程, 它们需要按照一定次序来执行才能完成任务.

进程/线程并发执行带来的临界区问题:

CPU 会并发执行多个进程, 这意味着CPU执行进程里的代码会随机的“跳来跳去”, 如果这些进程里同时操作共享数据(多个进程进入临界区, 产生竞争条件), 就会因为CPU并发执行的跳转次序不定而可能引起冲突, 理想上是当CPU执行一个进程的临界区代码时, 别的进程不能使用CPU, 且有次序地执行一个个进程. 解决冲突的方式是当CPU执行到一个进程里的操作共享数据的时候, 就避免执行其他进程, 也就是使进程互斥. 实现进程互斥有两种解决方案: 软件层面和硬件层面.

进程互斥是一种特殊的同步, 同步的目的是要保证进程或线程间的有序协作, 包括实现进程互斥

软件——使用算法实现互斥:

1
2
3
4
5
6
7
8
// Peterson Algorithm
while(true) {
flag[i] = true; // flag[i] 表示 i 进程想进入临界区
turn = j;// 最终可以进入临界区的进程
while(flag[j] && turn == j);
// 这里进入临界区
flag[i] = false; // 退出临界区
}

Peterson 算法适用于2个进程间的互斥, i 代表本进程, j 代表另一个; 在一个进程里这样写, 在另一个进程里把 j 和 i 对换即可实现互斥——当2个进程并发执行时, 就像之前说的, CPU执行进程里的代码会随机的“跳来跳去”. 对 i 进程, 当 j 进程想进入临界区(flag[j] = true;)并且 turn == j时, i 进程无限循环, 相当于等待, 而 j 进程由于turn == j不等于 i 因此不满足 j 进程的循环而进入临界区; 当 j 退出临界区, flag[j] = false;, 不满足 i 进程的flag[j] && turn == j的循环条件, 因此进入临界区, 实现了互斥.

硬件——使用硬件指令:

在一个进程进入临界区前通过一些硬件指令或者原子操作(不可分割步骤的操作)防止这个进程被中断, 即屏蔽中断, 阻止CPU切换.

以上软硬件层面的方法都各有缺点, 比如软件层面比较复杂, 需要考虑操作系统底层的特点, 对编程人员要求较高; 硬件层面限制了CPU并发能力, 不适用多处理器等. 它们都有CPU忙等待, 浪费了CPU时钟周期的缺点.

临界区问题会导致进程优先级反转, 但这也是理所当然的事情.

什么是进程优先级反转?

限制CPU在一个进程上执行, 就不能被更高优先级进程抢占, 称为进程优先级反转

信号量——经典的进程同步机制

信号量是将上述软硬件层面方法的优缺点结合的对于同步问题的解决方案 .

信号量是一个特殊变量, 可以在进程间传递, 因此进程可以直接使用.

1
2
3
4
5
// 信号量是一个结构体, 包含一个当前资源的整型数量以及一个存储等待进程的队列
struct Semaphore {
int count;
queueType queue;
}

信号量有3种操作:

  • 初始化——初始化资源数目, 通常为1

  • P操作——表示本进程想要要进入临界区, 原子操作

    1
    2
    3
    4
    5
    6
    7
    P(S) {
    S.count --; // 减少资源计数
    if(S.count < 0) { // 没有可用的资源
    // 放到等待队列并设置改进程为等待状态
    // CPU调度程序重新调度另一个进程来执行
    }
    }
  • V操作——表示本进程要出临界区, 释放资源, 原子操作

    1
    2
    3
    4
    5
    6
    V(S) {
    S.count ++;
    if(S.count <= 0) { // 等待队列不为空
    // 取等待队列的一个进程, 唤醒进程到就绪态
    }
    }

使用方法:

1
2
3
4
Semaphore S = new Semaphore();
S.P(S);
// 临界区
S.V(S);

信号量是怎么解决同步问题的?

假设, 有3个进程都有相同的临界区, 且被CPU并发执行, 资源数count初始为1. 当P1想进入临界区, 调用了P操作, count为0, 然后判断不小于0, 因此P1进入临界区, P1在临界区执行的时候, 可能在此时CPU跳到P2, 执行P2的P操作, count变为-1小于0, 加入到这个信号量的等待队列, 如果再跳到P3, count为-2小于0同样加入等待队列. 知道P1退出临界区, 执行V操作, count+1为-1小于等于0, 说明等待队列里有进程, 于是取进程P2并唤醒执行, P2因此进入临界区, P2退出临界区后同样取等待队列的P3, P3就进入了临界区. 实现了进程互斥、有序执行的同步机制.

不仅如此, 因为信号量允许CPU在执行进程的临界区时跳转, 避免了一个进程不断循环的忙等待, CPU忙等待仅发生在P、V原子操作的时候, 因为这2个操作是不可分割(中断)的.

不过, 信号量同样有问题, 由于它存在等待队列, 因此如果开发人员使用不当就很容易导致 一个等待进程 等待 另一个等待进程 的死锁情况以及饥饿(starvation)问题, 并且这些问题很难检测.

管程——高级语言层面、基于类的同步解决方案

信号量对编程人员要求较高, 管程则是一种高级的同步机制, 体现在了高级语言层面上的一种抽象操作. 管程就像一个类, 有共享数据以及对共享数据的各种操作:

1
2
3
4
5
6
7
8
monitor name {
// 共享变量声明
integer i;
condition c;
// 对共享数据的操作
procedure insert();
procedure remove();
}

管程将共享数据封装了起来, 提供对共享数据操作的借口供进程调用, 换句话说, 进程只能通过管程中的操作来访问管程中的共享数据.

管程生来具有进程互斥特性——管程确保一次只有一个进程能在管程内活动, 也就是编译器帮你实现好了. 如果需要解决一些特定同步问题也可以自定义额外的同步机制, 通过条件变量的 wait 和 signal 操作来阻塞、唤醒一个进程.

操作系统实例的解决方案

  • Windows XP: 内核线程采用自旋锁, 内核外线程利用调度对象采取互斥、信号量、时间、定时器等多种同步机制;
  • Linux: 原子操作、自旋锁、读写锁、信号量、屏障等等.

死锁

考虑这种情况, 某个进程P1占用资源R1, 并且申请的资源R2被另一个进程P2占用, 那么P1进入等待状态, 如果P2进程申请被P1占用的资源R1, 那么P2也要进入等待状态, 两个进程相互等待, P1和P2将产生死锁.

死锁的产生源于操作系统进程、线程模型和调度的特性, 这个“ 事故 ”是偶然发生的. 死锁产生有4个必要条件, 缺一不可:

  • 互斥——资源一次只能被一个进程使用
  • 占有并等待——一个进程占有至少一个资源, 并且等待另一个被占有的资源
  • 非抢占——资源一旦分配给进程只能等进程释放该资源, 不能中途抢占
  • 循环等待——P0等待P1, P1等待P2….Pn-1等待Pn, Pn等待P0, 形成等待环

可以利用上图的资源分配图来分析死锁.

解决死锁

  • 设计规则预防/避免死锁——死锁预防、死锁避免
  • 死锁发生时检测并恢复

死锁预防

死锁的产生需要4个条件缺一不可, 只要不满足其中一个条件即可, 然而前三个条件是由于操作系统的特性和各种机制引起的副作用, 且资源的种类、用途不同, 很难否定前三个条件, 因此可以从第四个条件下手.

要使得一组进程之间不发生循环等待, 结合操作系统特性(前三个条件), 可以采用资源有序分配法:

将系统所有资源编号, 进程在申请资源时, 只能按照递增的顺序申请, 即只能申请编号比自己已经申请过资源编号大的资源, 否则等待.

为什么这种方法可以避免死锁? 考虑一组进程, 它们申请的资源都按照资源有序分配法分配, 任一时刻, 这组进程里都存在一个进程拥有编号最大的那个资源, 那么这个进程就可以继续申请所有编号比自己还大的资源, 于是这个进程可以得到所有申请的资源, 使用后释放. n 个进程变为 n - 1 个进程. 接下来的进程同是如此, 所有进程就可以有序被分配资源而不会发生死锁.

死锁避免

操作系统事先可以得到进程申请资源和使用资源的额外信息, 通过这些信息去判断此次是给进程资源还是让进程等待, 从而避免可能发生的死锁.

操作系统会根据信息尝试寻找一个安全序列, 如果找到, 系统就处于安全状态. 安全序列是一组进程的执行顺序<p2,p1,p3...>, 如果按照这个顺序执行, 执行到每个进程时, 这个进程需要的资源量不超过系统当前剩余资源量与这个进程顺序之前的进程资源占有量之和. 在这种情况下, 如果进程 Pi 所需要的资源超过系统当前剩余量, 即使不能立即可用, Pi 可以等待前面的进程完成时释放资源, 仍可以得到想要的资源. 如果找不到这样一个安全序列, 则系统处于不安全状态, 不安全状态会导致死锁.

如何寻找一个安全序列? 抽象考虑以上情况, 这种问题与银行贷款问题相似, 都属于资源分配问题. 因此可以采用银行家算法.

采用银行家算法有几个条件需要满足: 1. 进程数固定、资源数固定; 2. 已知每个进程的资源最大需求量; 3. 进程申请数不能超过系统可用资源数; 4. 进程等待时间是有限的(不能饥饿); 5. 进程使用一定时间后归还资源.

银行家算法使用多个一维或多维数组记录了系统分配资源的状态:

  • Available —— 系统可用资源(剩余 + 已占用)
  • Max —— 每个进程需要的所有资源
  • Allocation —— 某时每个进程占有的资源
  • Need —— 每个进程还需要的资源
  • Request —— 某个进程当前请求的资源

采用这些变量实时记录系统分配资源的状态, 每次进程请求时, 判断 Request 是否小于 Available, 小于则分配, 大于则等待.

死锁发生时检测并恢复

这类方案采用消极方法, 检测到发生了死锁再恢复.

死锁检测时机

  • 当进程申请不到资源而等待时 —— 频率高、代价大
  • 定时监测
  • 系统资源利用率下降到固定阈值

死锁检测算法

分别维护一个资源分配表(哪个进程占用哪个资源)和一个进程等待表(哪个进程等待哪个资源), 从进程等待表找出一个进程, 找到它等待的资源, 在资源分配表查哪个进程占用了这个资源, 再在等待表查这个进程有没有等待, 有的话等待哪个资源…就这样在两个表之间来回查找, 如果回到原点说明有环存在, 即发生死锁.

死锁解除

  • 撤销所有进程——代价大
  • 进程回退再启动(基于系统日志) ,再启动很小几率会再次导致死锁, 别忘了, 死锁是偶然情况 —— 代价大
  • 按某规则逐一撤销进程
  • 按某规则逐一剥脱已占有资源

内存分配

内存是计算机运行的中心, 程序需要装载到内存中才能运行. 多个进程被分配到内存中的指定地址空间, 由CPU来从内存中提取指令并执行, 执行进程所产生的数据会保存在进程相应地址空间. 进程在内存中的地址空间是独立的, 由基地址和界限地址确定, 访问不合法的地址会导致寻址错误. 程序在执行时生成的地址称为逻辑地址, 需要经过操作系统的地址映射为内存中的物理地址, 这一过程被称为地址重定位. 地址重定位由内存管理单元MMU硬件来完成.

地址重定位有多种映射方案, 每种方案的设计可以从如下几个方面考虑 :

  • 硬件支持 —— 重定位发生频率非常高, 需专门的硬件配合共同设计;
  • 性能
  • 碎片—— 内存空间被分成块时, 进程所占用的地址空间小于分配的块所产生的剩余空间, 这些剩余不连续导致
  • 共享 —— 相同的程序和数据可以共享同一块内存节省空间
  • 保护 —— 进程有些程序和数据不能被其他进程访问
  • 交换 —— 方便交换(交换是内存的帮手, 内存装不下或者等待的进程可以交换到备用存储上, 用时再交换回去)

连续内存分配

这个连续是指进程在内存中的地址空间连续.

即把内存分割成大小相同或不同的块, 每个块容纳一个进程. 那么如何分割块以使碎片最小化? 来看一种经典的(Linux 内核采用的)内存分配方案——伙伴系统

伙伴系统首先将内存看作2的n次幂大小的一个块, 进程申请 S 大小的空间时就找到合适的块开始对半划分, 直到划分的块满足当前划分比 S 大、再次划分就比 S 小的情况, 把划分的块分给进程, 进程使用后释放空间会与周围空闲块合并, 用于下次划分.

连续内存分配外碎片问题较严重, 内存利用率低.

分页存储

分页和下面的分段都是非连续存储方案, 也就是说, 进程的地址空间在内存中被分割存储.

分页是把进程地址空间分割成大小相同的块, 称为页, 与此同时, 内存也被分割为与页相同大小的块, 称为帧, 这样一来就能 “无缝对接”. 分页提高了内存利用率.

逻辑地址空间与物理地址空间的映射采用一个页表的数据结构, CPU 生成的逻辑地址包含页号和页偏移, 页表记录了每个页号对应的帧地址, 加上偏移地址构成了物理地址.

使用上述结构的页表, 不适合在大内存系统中, 会导致页表很大, 且无法连续存储, 因此现代操作系统将页表实现为多级页表、哈希页表、反向页表以及高速缓存的快表等解决这些问题

  • 多级页表 —— 之前逻辑地址只包含帧号和偏移, 多级页表使每个进程有多个页表, 通过一个页目录来索引页表, 最后再索引帧号和偏移. 每个进程指有一个页目录, 页表可存到其他地方. 多级页表没有实现更小内存, 实现了分散存储
  • 哈希页表 —— 将页号映射成哈希表号, 利用哈希表查找与页号对应的表项, 从表项里查到帧号, 实现分散存储.
  • 反向页表 —— 从物理内存角度来考虑, 物理内存是固定的, 只要建立物理内存与逻辑内存的映射关系即可, 因此反向页表只维护一张页表, 这个页表记录了哪个物理内存的帧页对应哪个进程的哪个页号, 节省了空间. 此外, 反向页表的查找可以采用哈希表, 查找更快.
  • 快表 —— 快表是在 CPU 中, 属于高速缓存, 缓存当前进程的部分页表项, 这样就不用一次一次查页表了

分页很好解决了外碎片问题, 但会产生帧内的内碎片. 加入进程的最后一个数据只占用了页的一小部分, 那么这个页剩余部分就是内碎片.

分段存储

将进程地址空间分割成相同的块容易引起困惑, 我指的是不太符合逻辑. 因为程序是有逻辑的, 一般都可以分成各个部分/模块/段, 每个段有自己的地址空间, 因此把进程地址空间分为各个段大小的块更为合理. 其他的都与分页差不多——内存的话按照段大小去动态申请, 段与段之间不相邻; 同时像页表一样维护一个段表用于映射.

但这里同样存在内存分配的外碎片问题, 只不过粒度大小不同, 前者是进程级别, 后者是段级别.

段页式存储

顾名思义, 是两种方案的结合, 综合两者优点, 克服缺点.

段页式存储将进程地址空间先按段划分, 每一段再按页划分. 内存空间采用分页式存储方案来划分, 以页为单位进行存储、分配. 这样看起来比较完美了, 但完美的代价是用来映射的数据结构变的复杂. 数据结构由段表和页表组成, 段表记录每一段对应的页表信息, 包括页表起始地址和页表长度; 页表则与分页式相同, 记录了页号与帧号对应关系.

虚拟内存技术

现代操作系统实现了虚拟内存技术, 它是由覆盖技术和交换技术发展而来. 虚拟内存是广义上的内存, 它不仅包括内存还包括其他存储系统如寄存器、高速缓存、内存和磁盘等. 虚拟内存建立在整个存储系统之上, 整个存储系统都可看作是虚拟内存(主要在内存和磁盘上). 虚拟内存由操作系统协调各存储器使用

由此, 进程不必全部加载到内存里才能执行, 虚拟内存技术允许 “ 按需加载 ”, 动态地从磁盘载入需要的进程部分到内存, 且可以在内存空间紧张时调出部分空间. 这样, 操作系统就可以执行比物理内存空间还大的程序——刚开始先执行一部分, 释放内存空间后再执行. 此外, 每个进程所占的空间变小, 内存可以允许更多的进程, CPU 使用率提高. 虚拟页式存储系统允许文件和内存通过共享页而为多个进程锁共享, 这节省了空间, 同时对于一些复制操作会很快; 用户程序不再受限于物理内存限制, 虚拟内存将用户逻辑内存和物理内存分开, 提供了巨大的虚拟内存, 程序员不再担心没有可用的有限物理内存空间.

虚拟页式存储系统

虚拟内存技术 + 分页式存储管理方案构成了现代操作系统的虚拟页式管理系统. 上述过程具体来说就是进程在开始之前不是装入全部页, 而是装入一个甚至0个页面, 然后按需加载页; 当内存已满, 可通过算法利用交换技术置换某个页到磁盘, 以装入新的页. 对于0个页面, 也就是程序试图访问尚未调入内存的页, 系统就会检查页表发现还在磁盘并未调入内存, 于是调入到内存然后重新执行指令, 程序由此可以访问页, 就好像已经在内存里.

要实现按需调页, 虚拟页式存储系统必须解决帧分配问题页置换算法.

虚拟页式存储系统中的主要机制

虚拟地址表示(页表项)

虚拟内存技术的页表项(虚拟地址)记录的也不仅仅有最基本的帧号(多级页表还有页目录偏移), 还包括各种记录页信息的状态位, 如

  • P(有效位) —— 是否进入内存
  • A(访问位) —— 是否被访问过
  • D(修改位) —— 是否被修改过
  • R/W(读写位) —— 只读还是可读写
  • U/S —— 允许用户还是内核访问

方便解决帧分配问题、页置换等各种问题.

页错误

操作系统在进行虚拟地址到物理地址的转换时, 会读取虚拟地址的这些位, 检查是否有出现页错误:

  • 缺页异常——程序要读取页, 系统发现有效位为无效, 也就是页没有进入内存的时候
  • 页访问违反权限——违反读写、用户访问/内核访问权限
  • 错误的访问地址

对于缺页错误, 就像刚才0个页面所说, 系统会在磁盘里找到对应页, 在内存里寻找一块帧, 将页调入到内存然后重新执行指令. 这一过程是开销较大的. 系统给每个进程分配的帧越少, 缺页率就越高, 反之则越低. 这么说并不是系统给每个进程分配的帧越多越好, 分配的帧越多, 内存容下的进程就少, 系统资源利用率就低, 因此, 可以寻找一个平衡点.

哪些因素影响页错误率:

  • 页面置换算法
  • 页面本身大小
  • 程序编制方法
  • 分配个每个进程的帧数量

驻留集(帧分配)

表示系统给每个进程分配的帧数量. 这个量可以是固定的, 在进程创建时确定, 也可以是可变的. 固定的话对于不同类型的进程, 如交互、批处理等可以分配不同数量; 可变是根据进程的缺页率来评估, 缺页率高, 增加帧数、低则减少.

置换

当内存空闲帧数少于一定范围, 再装入页时, 就需要置换将来一段时间不用的页到其他地方, 腾出空间给新进来的页, 这个过程就置换. 由此产生几个问题:

  • 置换范围 —— 选择哪个范围的帧来置换? 是同一个进程里的帧还是全局所有帧? 因此置换范围有两种策略, 局部和全局
  • 置换策略 —— 如何确定哪一个页将来一段时间用不到? 根据页过去的行为来判断.

系统颠簸

如果置换出的页是某个进程经常调用的活跃页, 那么系统就会频繁调入调出这个页, 发生系统颠簸, 性能消耗极大. 系统颠簸的原因主要是采用了全局置换策略, 采用局部置换策略可一定程度上减少颠簸

帧锁定

考虑到系统调入调出页到内存具有一定开销, 对于一些确定要留在内存的页可以锁定帧, 不让系统换出内存. 如一些比较重要的操作, 像操作系统核心代码、关键数据结构、I/O缓冲区等.

清除策略(回收策略)

从进程的驻留集中收回帧. 由于虚拟页式系统工作的最佳状态是当发生缺页异常时, 内存中有大量空闲帧(系统不用去找了), 因此系统可以设定一个阈值, 小于阈值便启动清除策略, 根据页面置换算法来换出一部分页, 如果这些页面被修改过, 那么将修改写回磁盘确保扫的干净.

此外, 考虑这样一种情况, 某进程的一个页从内存中被置换出, 但进程又需要使用这个页, 此时如果来回调入调出, 甚至遭遇这个页已经被修改过, 那么系统开销会增大. 因此引入页缓冲技术, 将置换出去的页缓冲起来, 加入两个表中, 一个存放未被修改的页, 一个存放修改的页, 仍然保留在内存中, 一旦被重新访问就可迅速加入到进程的驻留集中. 长期不访问的、被修改的页将会定期批量写回磁盘.

写时复制

对于一些复制操作, 创建新进程时通常只创建对相同内存空间的引用, 父子进程间共享同一页面, 并不真的复制空间, 遇到写时再复制对应的页.

页面置换算法

上面讨论置换时提出一个问题: 如何确定哪一个页将来一段时间用不到? 我们根据页过去的行为来判断. 这里有几种置换算法:

  • 最佳置换 —— 换掉将来一段时间不用的页. 这个算法是最优理想的算法, 但很难实现, 因为我们不知道哪些页将来用不到, 可以实现近似算法并作为评价其他算法的标准.
  • 先进先出 —— 换掉最先进来的页, 可以用链表队列实现
  • 第二次机会 —— 按照先进先出选择页面, 检查访问位是否访问过, 如果为0则置换, 为1则置0并加入到队列末尾
  • 最近未使用 —— 通过页表项的访问位和修改位检查使用情况, 访问位定期置0, 优先置换0位较多的页
  • 最近最少使用 —— 通过时间戳置换未使用时间最长的页
  • 最不经常使用 —— 记录访问次数, 换出次数最小的页

在比较这些算法的性能时, 可以采用最小页错误率的标准

工作集算法

上面提到发生系统颠簸的原因是置换出了进程频繁调用的活跃页, 因此, 知道进程需要多少帧来放活跃页可有效阻止系统颠簸, 同时降低页错误率.

程序有局部性特性, 程序通常会在一段时间内集中访问一些页面, 在下一段时间又集中访问其他一些页面. 因此可以利用局部性原理, 判断进程最近在调用哪些页面, 置换出没调用的页, 这就是工作集算法

工作集是最近一段时间访问的页的集合, 随着时间段不同而变化, 系统分配大于工作集数量的帧