作者：程序员cxuan
原文链接：https://juejin.im/post/5f1a8b295188252e362e38a8
此篇文章带你梳理一下操作系统中都出现过哪些算法
进程和线程在调度时候出现过很多算法，这些算法的设计背景是当一个计算机是多道程序设计系统时，会频繁的有很多进程或者线程来同时竞争 CPU 时间片。 那么如何选择合适的进程/线程运行是一项艺术。当两个或两个以上的进程/线程处于就绪状态时，就会发生这种情况。如果只有一个 CPU 可用，那么必须选择接下来哪个进程/线程可以运行。操作系统中有一个叫做 调度程序(scheduler) 的角色存在，它就是做这件事儿的，调度程序使用的算法叫做 调度算法(scheduling algorithm) 。
针对不同的操作系统环境，也有不同的算法分类，操作系统主要分为下面这几种
下面我们分别来看一下这些操作系统中的算法。
批处理系统广泛应用于商业领域，比如用来处理工资单、存货清单、账目收入、账目支出、利息计算、索赔处理和其他周期性作业。在批处理系统中，一般会选择使用非抢占式算法或者周期性比较长的抢占式算法。这种方法可以减少线程切换因此能够提升性能。
在交互式用户环境中，因为为了用户体验，所以会避免长时间占用进程，所以需要抢占式算法。由于某个进程出现错误也有可能无限期的排斥其他所有进程。为了避免这种情况，抢占式也是必须的。
在实时系统中，抢占式不是必须的，因为进程知道自己可能运行不了很长时间，通常很快的做完自己的工作并挂起。
通常有三个指标来衡量系统工作状态：吞吐量、周转时间和 CPU 利用率
下面我们就来认识一下批处理中的算法。
很像是先到先得。。。它是一种非抢占式的算法。此算法将按照请求顺序为进程分配 CPU。最基本的，会有一个就绪进程的等待队列。当第一个任务从外部进入系统时，将会立即启动并允许运行任意长的时间。它不会因为运行时间太长而中断。当其他作业进入时，它们排到就绪队列尾部。当正在运行的进程阻塞，处于等待队列的第一个进程就开始运行。当一个阻塞的进程重新处于就绪态时，它会像一个新到达的任务，会排在队列的末尾，即排在所有进程最后。
这个算法的强大之处在于易于理解和编程，在这个算法中，一个单链表记录了所有就绪进程。要选取一个进程运行，只要从该队列的头部移走一个进程即可；要添加一个新的作业或者阻塞一个进程，只要把这个作业或进程附加在队列的末尾即可。这是很简单的一种实现。
不过，先来先服务也是有缺点的，那就是没有优先级的关系，试想一下，如果有 100 个 I/O 进程正在排队，第 101 个是一个 CPU 密集型进程，那岂不是需要等 100 个 I/O 进程运行完毕才会等到一个 CPU 密集型进程运行，这在实际情况下根本不可能，所以需要优先级或者抢占式进程的出现来优先选择重要的进程运行。
批处理中的第二种调度算法是 最短作业优先(Shortest Job First)，我们假设运行时间已知。例如，一家保险公司，因为每天要做类似的工作，所以人们可以相当精确地预测处理 1000 个索赔的一批作业需要多长时间。当输入队列中有若干个同等重要的作业被启动时，调度程序应使用最短优先作业算法
如上图 a 所示，这里有 4 个作业 A、B、C、D ，运行时间分别为 8、4、4、4 分钟。若按图中的次序运行，则 A 的周转时间为 8 分钟，B 为 12 分钟，C 为 16 分钟，D 为 20 分钟，平均时间内为 14 分钟。
现在考虑使用最短作业优先算法运行 4 个作业，如上图 b 所示，目前的周转时间分别为 4、8、12、20，平均为 11 分钟，可以证明最短作业优先是最优的。考虑有 4 个作业的情况，其运行时间分别为 a、b、c、d。第一个作业在时间 a 结束，第二个在时间 a + b 结束，以此类推。平均周转时间为 (4a + 3b + 2c + d) / 4 。显然 a 对平均值的影响最大，所以 a 应该是最短优先作业，其次是 b，然后是 c ，最后是 d 它就只能影响自己的周转时间了。
需要注意的是，在所有的进程都可以运行的情况下，最短作业优先的算法才是最优的。
最短作业优先的抢占式版本被称作为 最短剩余时间优先(Shortest Remaining Time Next) 算法。使用这个算法，调度程序总是选择剩余运行时间最短的那个进程运行。当一个新作业到达时，其整个时间同当前进程的剩余时间做比较。如果新的进程比当前运行进程需要更少的时间，当前进程就被挂起，而运行新的进程。这种方式能够使短期作业获得良好的服务。
交互式系统中在个人计算机、服务器和其他系统中都是很常用的，所以有必要来探讨一下交互式调度
一种最古老、最简单、最公平并且最广泛使用的算法就是 轮询算法(round-robin)。每个进程都会被分配一个时间段，称为时间片(quantum)，在这个时间片内允许进程运行。如果进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。轮询算法比较容易实现。调度程序所做的就是维护一个可运行进程的列表，就像下图中的 a，当一个进程用完时间片后就被移到队列的末尾，就像下图的 b。
时间片轮询调度中唯一有意思的一点就是时间片的长度。从一个进程切换到另一个进程需要一定的时间进行管理处理，包括保存寄存器的值和内存映射、更新不同的表格和列表、清除和重新调入内存高速缓存等。这种切换称作 进程间切换(process switch) 和 上下文切换(context switch)。
轮询调度假设了所有的进程是同等重要的。但事实情况可能不是这样。例如，在一所大学中的等级制度，首先是院长，然后是教授、秘书、后勤人员，最后是学生。这种将外部情况考虑在内就实现了优先级调度(priority scheduling)
它的基本思想很明确，每个进程都被赋予一个优先级，优先级高的进程优先运行。
但是也不意味着高优先级的进程能够永远一直运行下去，调度程序会在每个时钟中断期间降低当前运行进程的优先级。如果此操作导致其优先级降低到下一个最高进程的优先级以下，则会发生进程切换。或者，可以为每个进程分配允许运行的最大时间间隔。当时间间隔用完后，下一个高优先级的进程会得到运行的机会。
可以很方便的将一组进程按优先级分成若干类，并且在各个类之间采用优先级调度，而在各类进程的内部采用轮转调度。下面展示了一个四个优先级类的系统
它的调度算法主要描述如下：上面存在优先级为 4 类的可运行进程，首先会按照轮转法为每个进程运行一个时间片，此时不理会较低优先级的进程。若第 4 类进程为空，则按照轮询的方式运行第三类进程。若第 4 类和第 3 类进程都为空，则按照轮转法运行第 2 类进程。如果不对优先级进行调整，则低优先级的进程很容易产生饥饿现象。
对于批处理系统而言，由于最短作业优先常常伴随着最短响应时间，所以如果能够把它用于交互式进程，那将是非常好的。交互式进程通常遵循下列模式：等待命令、执行命令、等待命令、执行命令。。。如果我们把每个命令的执行都看作一个分离的作业，那么我们可以通过首先运行最短的作业来使响应时间最短。这里唯一的问题是如何从当前可运行进程中找出最短的那一个进程。
一种方式是根据进程过去的行为进行推测，并执行估计运行时间最短的那一个。假设每个终端上每条命令的预估运行时间为 T0，现在假设测量到其下一次运行时间为 T1，可以用两个值的加权来改进估计时间，即aT0+ (1- 1)T1。通过选择 a 的值，可以决定是尽快忘掉老的运行时间，还是在一段长时间内始终记住它们。当 a = 1/2 时，可以得到下面这个序列
可以看到，在三轮过后，T0 在新的估计值中所占比重下降至 1/8。
有时把这种通过当前测量值和先前估计值进行加权平均从而得到下一个估计值的技术称作 老化(aging)。这种方法会使用很多预测值基于当前值的情况。
一种完全不同的调度方法是对用户做出明确的性能保证。一种实际而且容易实现的保证是：若用户工作时有 n 个用户登录，则每个用户将获得 CPU 处理能力的 1/n。类似地，在一个有 n 个进程运行的单用户系统中，若所有的进程都等价，则每个进程将获得 1/n 的 CPU 时间。
对用户进行承诺并在随后兑现承诺是一件好事，不过很难实现。但是有一种既可以给出预测结果而又有一种比较简单的实现方式的算法，就是 彩票调度(lottery scheduling)算法。
其基本思想是为进程提供各种系统资源（例如 CPU 时间）的彩票。当做出一个调度决策的时候，就随机抽出一张彩票，拥有彩票的进程将获得该资源。在应用到 CPU 调度时，系统可以每秒持有 50 次抽奖，每个中奖者将获得比如 20 毫秒的 CPU 时间作为奖励。
如果希望进程之间协作的话可以交换它们之间的票据。例如，客户端进程给服务器进程发送了一条消息后阻塞，客户端进程可能会把自己所有的票据都交给服务器，来增加下一次服务器运行的机会。当服务完成后，它会把彩票还给客户端让其有机会再次运行。事实上，如果没有客户机，服务器也根本不需要彩票。
可以把彩票理解为 buff，这个 buff 有 15% 的几率能让你产生 速度之靴 的效果。
到目前为止，我们假设被调度的都是各个进程自身，而不用考虑该进程的拥有者是谁。结果是，如果用户 1 启动了 9 个进程，而用户 2 启动了一个进程，使用轮转或相同优先级调度算法，那么用户 1 将得到 90 % 的 CPU 时间，而用户 2 将之得到 10 % 的 CPU 时间。
为了阻止这种情况的出现，一些系统在调度前会把进程的拥有者考虑在内。在这种模型下，每个用户都会分配一些CPU 时间，而调度程序会选择进程并强制执行。因此如果两个用户每个都会有 50% 的 CPU 时间片保证，那么无论一个用户有多少个进程，都将获得相同的 CPU 份额。
实时系统(real-time) 对于时间有要求的系统。实时系统可以分为两类，硬实时(hard real time) 和 软实时(soft real time) 系统，前者意味着必须要满足绝对的截止时间；后者的含义是虽然不希望偶尔错失截止时间，但是可以容忍。在这两种情形中，实时都是通过把程序划分为一组进程而实现的，其中每个进程的行为是可预测和提前可知的。这些进程一般寿命较短，并且极快的运行完成。在检测到一个外部信号时，调度程序的任务就是按照满足所有截止时间的要求调度进程。
实时系统中的事件可以按照响应方式进一步分类为周期性(以规则的时间间隔发生)事件或 非周期性(发生时间不可预知)事件。一个系统可能要响应多个周期性事件流，根据每个事件处理所需的时间，可能甚至无法处理所有事件。例如，如果有 m 个周期事件，事件 i 以周期 Pi 发生，并需要 Ci 秒 CPU 时间处理一个事件，那么可以处理负载的条件是
只有满足这个条件的实时系统称为可调度的，这意味着它实际上能够被实现。一个不满足此检验标准的进程不能被调度，因为这些进程共同需要的 CPU 时间总和大于 CPU 能提供的时间。
实时系统的调度算法可以是静态的或动态的。前者在系统开始运行之前做出调度决策；后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等信息时，静态调度才能工作，而动态调度不需要这些限制。
到目前为止，我们隐含的假设系统中所有进程属于不同的分组用户并且进程间存在相互竞争 CPU 的情况。通常情况下确实如此，但有时也会发生一个进程会有很多子进程并在其控制下运行的情况。例如，一个数据库管理系统进程会有很多子进程。每一个子进程可能处理不同的请求，或者每个子进程实现不同的功能（如请求分析、磁盘访问等）。主进程完全可能掌握哪一个子进程最重要（或最紧迫），而哪一个最不重要。但是，以上讨论的调度算法中没有一个算法从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择。
解决问题的办法是将 调度机制(scheduling mechanism) 和 调度策略(scheduling policy) 分开，这是长期一贯的原则。这也就意味着调度算法在某种方式下被参数化了，但是参数可以被用户进程填写。让我们首先考虑数据库的例子。假设内核使用优先级调度算法，并提供了一条可供进程设置优先级的系统调用。这样，尽管父进程本身并不参与调度，但它可以控制如何调度子进程的细节。调度机制位于内核，而调度策略由用户进程决定，调度策略和机制分离是一种关键性思路。
操作系统在内存管理上也出现过许多算法，这些算法的目标的最终目的都是为了合理分配内存。
操作系统有两种内存管理方式，一种是位图，一种是 链表。
在使用链表管理内存时，有几种方法的变体
当按照地址顺序在链表中存放进程和空闲区时，有几种算法可以为创建的进程（或者从磁盘中换入的进程）分配内存。我们先假设内存管理器知道应该分配多少内存，最简单的算法是使用 首次适配(first fit)。内存管理器会沿着段列表进行扫描，直到找个一个足够大的空闲区为止。除非空闲区大小和要分配的空间大小一样，否则将空闲区分为两部分，一部分供进程使用；一部分生成新的空闲区。首次适配算法是一种速度很快的算法，因为它会尽可能的搜索链表。
首次适配的一个小的变体是 下次适配(next fit)。它和首次匹配的工作方式相同，只有一个不同之处那就是下次适配在每次找到合适的空闲区时就会记录当时的位置，以便下次寻找空闲区时从上次结束的地方开始搜索，而不是像首次匹配算法那样每次都会从头开始搜索。Bays(1997) 证明了下次适配算法的性能略低于首次匹配算法。
另外一个著名的并且广泛使用的算法是 最佳适配(best fit)。最佳适配会从头到尾寻找整个链表，找出能够容纳进程的最小空闲区。最佳适配算法会试图找出最接近实际需要的空闲区，以最好的匹配请求和可用空闲区，而不是先一次拆分一个以后可能会用到的大的空闲区。比如现在我们需要一个大小为 2 的块，那么首次匹配算法会把这个块分配在位置 5 的空闲区，而最佳适配算法会把该块分配在位置为 18 的空闲区，如下
那么最佳适配算法的性能如何呢？最佳适配会遍历整个链表，所以最佳适配算法的性能要比首次匹配算法差。但是令人想不到的是，最佳适配算法要比首次匹配和下次匹配算法浪费更多的内存，因为它会产生大量无用的小缓冲区，首次匹配算法生成的空闲区会更大一些。
最佳适配的空闲区会分裂出很多非常小的缓冲区，为了避免这一问题，可以考虑使用 最差适配(worst fit) 算法。即总是分配最大的内存区域（所以你现在明白为什么最佳适配算法会分裂出很多小缓冲区了吧），使新分配的空闲区比较大从而可以继续使用。仿真程序表明最差适配算法也不是一个好主意。
如果为进程和空闲区维护各自独立的链表，那么这四个算法的速度都能得到提高。这样，这四种算法的目标都是为了检查空闲区而不是进程。但这种分配速度的提高的一个不可避免的代价是增加复杂度和减慢内存释放速度，因为必须将一个回收的段从进程链表中删除并插入空闲链表区。
如果进程和空闲区使用不同的链表，那么可以按照大小对空闲区链表排序，以便提高最佳适配算法的速度。在使用最佳适配算法搜索由小到大排列的空闲区链表时，只要找到一个合适的空闲区，则这个空闲区就是能容纳这个作业的最小空闲区，因此是最佳匹配。因为空闲区链表以单链表形式组织，所以不需要进一步搜索。空闲区链表按大小排序时，首次适配算法与最佳适配算法一样快，而下次适配算法在这里毫无意义。
另一种分配算法是 快速适配(quick fit) 算法，它为那些常用大小的空闲区维护单独的链表。例如，有一个 n 项的表，该表的第一项是指向大小为 4 KB 的空闲区链表表头指针，第二项是指向大小为 8 KB 的空闲区链表表头指针，第三项是指向大小为 12 KB 的空闲区链表表头指针，以此类推。比如 21 KB 这样的空闲区既可以放在 20 KB 的链表中，也可以放在一个专门存放大小比较特别的空闲区链表中。
快速匹配算法寻找一个指定代销的空闲区也是十分快速的，但它和所有将空闲区按大小排序的方案一样，都有一个共同的缺点，即在一个进程终止或被换出时，寻找它的相邻块并查看是否可以合并的过程都是非常耗时的。如果不进行合并，内存将会很快分裂出大量进程无法利用的小空闲区。
页面置换有非常多的算法，下面一起来认识一下
当发生缺页异常时，操作系统会选择一个页面进行换出从而为新进来的页面腾出空间。如果要换出的页面在内存中已经被修改，那么必须将其写到磁盘中以使磁盘副本保持最新状态。如果页面没有被修改过，并且磁盘中的副本也已经是最新的，那么就不需要进行重写。那么就直接使用调入的页面覆盖需要移除的页面就可以了。
当发生缺页中断时，虽然可以随机的选择一个页面进行置换，但是如果每次都选择一个不常用的页面会提升系统的性能。如果一个经常使用的页面被换出，那么这个页面在短时间内又可能被重复使用，那么就可能会造成额外的性能开销。在关于页面的主题上有很多页面置换算法(page replacement algorithms)，这些已经从理论上和实践上得到了证明。
下面我们就来探讨一下有哪些页面置换算法。
最优的页面置换算法很容易描述，但在实际情况下很难实现。它的工作流程如下：在缺页中断发生时，这些页面之一将在下一条指令（包含该指令的页面）上被引用。其他页面则可能要到 10、100 或者 1000 条指令后才会被访问。每个页面都可以用在该页首次被访问前所要执行的指令数作为标记。
最优化的页面算法表明应该标记最大的页面。如果一个页面在 800 万条指令内不会被使用，另外一个页面在 600 万条指令内不会被使用，则置换前一个页面，从而把需要调入这个页面而发生的缺页中断推迟。计算机也像人类一样，会把不愿意做的事情尽可能的往后拖。
这个算法最大的问题是无法实现。当缺页中断发生时，操作系统无法知道各个页面的下一次将在什么时候被访问。这种算法在实际过程中根本不会使用。
为了能够让操作系统收集页面使用信息，大部分使用虚拟地址的计算机都有两个状态位，R 和 M，来和每个页面进行关联。每当引用页面（读入或写入）时都设置 R，写入（即修改）页面时设置 M，这些位包含在每个页表项中，就像下面所示
因为每次访问时都会更新这些位，因此由硬件来设置它们非常重要。一旦某个位被设置为 1，就会一直保持 1 直到操作系统下次来修改此位。
如果硬件没有这些位，那么可以使用操作系统的缺页中断和时钟中断机制来进行模拟。当启动一个进程时，将其所有的页面都标记为不在内存；一旦访问任何一个页面就会引发一次缺页中断，此时操作系统就可以设置 R 位(在它的内部表中)，修改页表项使其指向正确的页面，并设置为 READ ONLY 模式，然后重新启动引起缺页中断的指令。如果页面随后被修改，就会发生另一个缺页异常。从而允许操作系统设置 M 位并把页面的模式设置为 READ/WRITE。
可以用 R 位和 M 位来构造一个简单的页面置换算法：当启动一个进程时，操作系统将其所有页面的两个位都设置为 0。R 位定期的被清零（在每个时钟中断）。用来将最近未引用的页面和已引用的页面分开。
当出现缺页中断后，操作系统会检查所有的页面，并根据它们的 R 位和 M 位将当前值分为四类：
尽管看起来好像无法实现第一类页面，但是当第三类页面的 R 位被时钟中断清除时，它们就会发生。时钟中断不会清除 M 位，因为需要这个信息才能知道是否写回磁盘中。清除 R 但不清除 M 会导致出现一类页面。
NRU(Not Recently Used) 算法从编号最小的非空类中随机删除一个页面。此算法隐含的思想是，在一个时钟内（约 20 ms）淘汰一个已修改但是没有被访问的页面要比一个大量引用的未修改页面好，NRU 的主要优点是易于理解并且能够有效的实现。
另一种开销较小的方式是使用 FIFO(First-In,First-Out) 算法，这种类型的数据结构也适用在页面置换算法中。由操作系统维护一个所有在当前内存中的页面的链表，最早进入的放在表头，最新进入的页面放在表尾。在发生缺页异常时，会把头部的页移除并且把新的页添加到表尾。
先进先出页面可能是最简单的页面替换算法了。在这种算法中，操作系统会跟踪链表中内存中的所有页。下面我们举个例子看一下（这个算法我刚开始看的时候有点懵逼，后来才看懂，我还是很菜）
我们上面学到的 FIFO 链表页面有个缺陷，那就是出链和入链并不会进行 check 检查，这样就会容易把经常使用的页面置换出去，为了避免这一问题，我们对该算法做一个简单的修改：我们检查最老页面的 R 位，如果是 0 ，那么这个页面就是最老的而且没有被使用，那么这个页面就会被立刻换出。如果 R 位是 1，那么就清除此位，此页面会被放在链表的尾部，修改它的装入时间就像刚放进来的一样。然后继续搜索。
这种算法叫做 第二次机会(second chance)算法，就像下面这样，我们看到页面 A 到 H 保留在链表中，并按到达内存的时间排序。
a）按照先进先出的方法排列的页面；b）在时刻 20 处发生缺页异常中断并且 A 的 R 位已经设置时的页面链表。
假设缺页异常发生在时刻 20 处，这时最老的页面是 A ，它是在 0 时刻到达的。如果 A 的 R 位是 0，那么它将被淘汰出内存，或者把它写回磁盘（如果它已经被修改过），或者只是简单的放弃（如果它是未被修改过）。另一方面，如果它的 R 位已经设置了，则将 A 放到链表的尾部并且重新设置装入时间为当前时刻（20 处），然后清除 R 位。然后从 B 页面开始继续搜索合适的页面。
寻找第二次机会的是在最近的时钟间隔中未被访问过的页面。如果所有的页面都被访问过，该算法就会被简化为单纯的 FIFO 算法。具体来说，假设图 a 中所有页面都设置了 R 位。操作系统将页面依次移到链表末尾，每次都在添加到末尾时清除 R 位。最后，算法又会回到页面 A，此时的 R 位已经被清除，那么页面 A 就会被执行出链处理，因此算法能够正常结束。
即使上面提到的第二次页面置换算法也是一种比较合理的算法，但它经常要在链表中移动页面，既降低了效率，而且这种算法也不是必须的。一种比较好的方式是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面。如下图所示
当缺页错误出现时，算法首先检查表针指向的页面，如果它的 R 位是 0 就淘汰该页面，并把新的页面插入到这个位置，然后把表针向前移动一位；如果 R 位是 1 就清除 R 位并把表针前移一个位置。重复这个过程直到找到了一个 R 位为 0 的页面位置。了解这个算法的工作方式，就明白为什么它被称为 时钟(clokc)算法了。
最近最少使用页面置换算法的一个解释会是下面这样：在前面几条指令中频繁使用的页面和可能在后面的几条指令中被使用。反过来说，已经很久没有使用的页面有可能在未来一段时间内仍不会被使用。这个思想揭示了一个可以实现的算法：在缺页中断时，置换未使用时间最长的页面。这个策略称为 LRU(Least Recently Used) ，最近最少使用页面置换算法。
虽然 LRU 在理论上是可以实现的，但是从长远看来代价比较高。为了完全实现 LRU，会在内存中维护一个所有页面的链表，最频繁使用的页位于表头，最近最少使用的页位于表尾。困难的是在每次内存引用时更新整个链表。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常耗时的操作，即使使用硬件来实现也是一样的费时。
然而，还有其他方法可以通过硬件实现 LRU。让我们首先考虑最简单的方式。这个方法要求硬件有一个 64 位的计数器，它在每条指令执行完成后自动加 1，每个页表必须有一个足够容纳这个计数器值的域。在每次访问内存后，将当前的值保存到被访问页面的页表项中。一旦发生缺页异常，操作系统就检查所有页表项中计数器的值，找到值最小的一个页面，这个页面就是最少使用的页面。
尽管上面的 LRU 算法在原则上是可以实现的，但是很少有机器能够拥有那些特殊的硬件。上面是硬件的实现方式，那么现在考虑要用软件来实现 LRU 。一种可以实现的方案是 NFU(Not Frequently Used，最不常用)算法。它需要一个软件计数器来和每个页面关联，初始化的时候是 0 。在每个时钟中断时，操作系统会浏览内存中的所有页，会将每个页面的 R 位（0 或 1）加到它的计数器上。这个计数器大体上跟踪了各个页面访问的频繁程度。当缺页异常出现时，则置换计数器值最小的页面。
NFU 最主要的问题是它不会忘记任何东西，想一下是不是这样？例如，在一个多次（扫描）的编译器中，在第一遍扫描中频繁使用的页面会在后续的扫描中也有较高的计数。事实上，如果第一次扫描的执行时间恰好是各次扫描中最长的，那么后续遍历的页面的统计次数总会比第一次页面的统计次数小。结果是操作系统将置换有用的页面而不是不再使用的页面。
幸运的是只需要对 NFU 做一个简单的修改就可以让它模拟 LRU，这个修改有两个步骤
修改以后的算法称为 老化(aging) 算法，下图解释了老化算法是如何工作的。
我们假设在第一个时钟周期内页面 0 - 5 的 R 位依次是 1，0，1，0，1，1，（也就是页面 0 是 1，页面 1 是 0，页面 2 是 1 这样类推）。也就是说，在 0 个时钟周期到 1 个时钟周期之间，0，2，4，5 都被引用了，从而把它们的 R 位设置为 1，剩下的设置为 0 。在相关的六个计数器被右移之后 R 位被添加到 左侧 ，就像上图中的 a。剩下的四列显示了接下来的四个时钟周期内的六个计数器变化。
当缺页异常出现时，将置换（就是移除）计数器值最小的页面。如果一个页面在前面 4 个时钟周期内都没有被访问过，那么它的计数器应该会有四个连续的 0 ，因此它的值肯定要比前面 3 个时钟周期内都没有被访问过的页面的计数器小。
这个算法与 LRU 算法有两个重要的区别：看一下上图中的 e，第三列和第五列
它们在两个时钟周期内都没有被访问过，在此之前的时钟周期内都引用了两个页面。根据 LRU 算法，如果需要置换的话，那么应该在这两个页面中选择一个。那么问题来了，我萌应该选择哪个？现在的问题是我们不知道时钟周期 1 到时钟周期 2 内它们中哪个页面是后被访问到的。因为在每个时钟周期内只记录了一位，所以无法区分在一个时钟周期内哪个页面最早被引用，哪个页面是最后被引用的。因此，我们能做的就是置换页面3，因为页面 3 在周期 0 - 1 内都没有被访问过，而页面 5 却被引用过。
LRU 与老化之前的第 2 个区别是，在老化期间，计数器具有有限数量的位（这个例子中是 8 位），这就限制了以往的访问记录。如果两个页面的计数器都是 0 ，那么我们可以随便选择一个进行置换。实际上，有可能其中一个页面的访问次数实在 9 个时钟周期以前，而另外一个页面是在 1000 个时钟周期之前，但是我们却无法看到这些。在实际过程中，如果时钟周期是 20 ms，8 位一般是够用的。所以我们经常拿 20 ms 来举例。
在最单纯的分页系统中，刚启动进程时，在内存中并没有页面。此时如果 CPU 尝试匹配第一条指令，就会得到一个缺页异常，使操作系统装入含有第一条指令的页面。其他的错误比如 全局变量和 堆栈 引起的缺页异常通常会紧接着发生。一段时间以后，进程需要的大部分页面都在内存中了，此时进程开始在较少的缺页异常环境中运行。这个策略称为 请求调页(demand paging)，因为页面是根据需要被调入的，而不是预先调入的。
在一个大的地址空间中系统的读所有的页面，将会造成很多缺页异常，因此会导致没有足够的内存来容纳这些页面。不过幸运的是，大部分进程不是这样工作的，它们都会以局部性方式(locality of reference) 来访问，这意味着在执行的任何阶段，程序只引用其中的一小部分。
一个进程当前正在使用的页面的集合称为它的 工作集(working set)，如果整个工作集都在内存中，那么进程在运行到下一运行阶段（例如，编译器的下一遍扫面）之前，不会产生很多缺页中断。如果内存太小从而无法容纳整个工作集，那么进程的运行过程中会产生大量的缺页中断，会导致运行速度也会变得缓慢。因为通常只需要几纳秒就能执行一条指令，而通常需要十毫秒才能从磁盘上读入一个页面。如果一个程序每 10 ms 只能执行一到两条指令，那么它将需要很长时间才能运行完。如果只是执行几条指令就会产生中断，那么就称作这个程序产生了 颠簸(thrashing)。
在多道程序的系统中，通常会把进程移到磁盘上（即从内存中移走所有的页面），这样可以让其他进程有机会占用 CPU 。有一个问题是，当进程想要再次把之前调回磁盘的页面调回内存怎么办？从技术的角度上来讲，并不需要做什么，此进程会一直产生缺页中断直到它的工作集 被调回内存。然后，每次装入一个进程需要 20、100 甚至 1000 次缺页中断，速度显然太慢了，并且由于 CPU 需要几毫秒时间处理一个缺页中断，因此由相当多的 CPU 时间也被浪费了。
因此，不少分页系统中都会设法跟踪进程的工作集，确保这些工作集在进程运行时被调入内存。这个方法叫做 工作集模式(working set model)。它被设计用来减少缺页中断的次数的。在进程运行前首先装入工作集页面的这一个过程被称为 预先调页(prepaging)，工作集是随着时间来变化的。
根据研究表明，大多数程序并不是均匀的访问地址空间的，而访问往往是集中于一小部分页面。一次内存访问可能会取出一条指令，也可能会取出数据，或者是存储数据。在任一时刻 t，都存在一个集合，它包含所哟欧最近 k 次内存访问所访问过的页面。这个集合 w(k,t) 就是工作集。因为最近 k = 1次访问肯定会访问最近 k > 1 次访问所访问过的页面，所以 w(k,t) 是 k 的单调递减函数。随着 k 的增大，w(k,t) 是不会无限变大的，因为程序不可能访问比所能容纳页面数量上限还多的页面。
事实上大多数应用程序只会任意访问一小部分页面集合，但是这个集合会随着时间而缓慢变化，所以为什么一开始曲线会快速上升而 k 较大时上升缓慢。为了实现工作集模型，操作系统必须跟踪哪些页面在工作集中。一个进程从它开始执行到当前所实际使用的 CPU 时间总数通常称作 当前实际运行时间。进程的工作集可以被称为在过去的 t 秒实际运行时间中它所访问过的页面集合。
下面来简单描述一下工作集的页面置换算法，基本思路就是找出一个不在工作集中的页面并淘汰它。下面是一部分机器页表
因为只有那些在内存中的页面才可以作为候选者被淘汰，所以该算法忽略了那些不在内存中的页面。每个表项至少包含两条信息：上次使用该页面的近似时间和 R（访问）位。空白的矩形表示该算法不需要其他字段，例如页框数量、保护位、修改位。
算法的工作流程如下，假设硬件要设置 R 和 M 位。同样的，在每个时钟周期内，一个周期性的时钟中断会使软件清除 Referenced(引用)位。在每个缺页异常，页表会被扫描以找出一个合适的页面把它置换。
随着每个页表项的处理，都需要检查 R 位。如果 R 位是 1，那么就会将当前时间写入页表项的 上次使用时间域，表示的意思就是缺页异常发生时页面正在被使用。因为页面在当前时钟周期内被访问过，那么它应该出现在工作集中而不是被删除（假设 t 是横跨了多个时钟周期）。
如果 R 位是 0 ，那么在当前的时钟周期内这个页面没有被访问过，应该作为被删除的对象。为了查看是否应该将其删除，会计算其使用期限（当前虚拟时间 - 上次使用时间），采用这个时间和 t 进行对比。如果使用期限大于 t，那么这个页面就不再工作集中，而使用新的页面来替换它。然后继续扫描更新剩下的表项。
然而，如果 R 位是 0 但是使用期限小于等于 t，那么此页应该在工作集中。此时就会把页面临时保存起来，但是会记生存时间最长（即上次使用时间的最小值）的页面。如果扫描完整个页表却没有找到适合被置换的页面，也就意味着所有的页面都在工作集中。在这种情况下，如果找到了一个或者多个 R = 0 的页面，就淘汰生存时间最长的页面。最坏的情况下是，在当前时钟周期内，所有的页面都被访问过了（也就是都有 R = 1），因此就随机选择一个页面淘汰，如果有的话最好选一个未被访问的页面，也就是干净的页面。
当缺页异常发生后，需要扫描整个页表才能确定被淘汰的页面，因此基本工作集算法还是比较浪费时间的。一个对基本工作集算法的提升是基于时钟算法但是却使用工作集的信息，这种算法称为WSClock(工作集时钟)。由于它的实现简单并且具有高性能，因此在实践中被广泛应用。
与时钟算法一样，所需的数据结构是一个以页框为元素的循环列表，就像下面这样
最初的时候，该表是空的。当装入第一个页面后，把它加载到该表中。随着更多的页面的加入，它们形成一个环形结构。每个表项包含来自基本工作集算法的上次使用时间，以及 R 位（已标明）和 M 位（未标明）。
与时钟算法一样，在每个缺页异常时，首先检查指针指向的页面。如果 R 位被是设置为 1，该页面在当前时钟周期内就被使用过，那么该页面就不适合被淘汰。然后把该页面的 R 位置为 0，指针指向下一个页面，并重复该算法。该事件序列化后的状态参见图 b。
现在考虑指针指向的页面 R = 0 时会发生什么，参见图 c，如果页面的使用期限大于 t 并且页面为被访问过，那么这个页面就不会在工作集中，并且在磁盘上会有一个此页面的副本。申请重新调入一个新的页面，并把新的页面放在其中，如图 d 所示。另一方面，如果页面被修改过，就不能重新申请页面，因为这个页面在磁盘上没有有效的副本。为了避免由于调度写磁盘操作引起的进程切换，指针继续向前走，算法继续对下一个页面进行操作。毕竟，有可能存在一个老的，没有被修改过的页面可以立即使用。
原则上来说，所有的页面都有可能因为磁盘I/O 在某个时钟周期内被调度。为了降低磁盘阻塞，需要设置一个限制，即最大只允许写回 n 个页面。一旦达到该限制，就不允许调度新的写操作。
那么就有个问题，指针会绕一圈回到原点的，如果回到原点，它的起始点会发生什么？这里有两种情况：
在第一种情况中，指针仅仅是不停的移动，寻找一个未被修改过的页面。由于已经调度了一个或者多个写操作，最终会有某个写操作完成，它的页面会被标记为未修改。置换遇到的第一个未被修改过的页面，这个页面不一定是第一个被调度写操作的页面，因为硬盘驱动程序为了优化性能可能会把写操作重排序。
对于第二种情况，所有的页面都在工作集中，否则将至少调度了一个写操作。由于缺乏额外的信息，最简单的方法就是置换一个未被修改的页面来使用，扫描中需要记录未被修改的页面的位置，如果不存在未被修改的页面，就选定当前页面并把它写回磁盘。
我们到现在已经研究了各种页面置换算法，现在我们来一个简单的总结，算法的总结归纳如下
总之，最好的算法是老化算法和WSClock算法。他们分别是基于 LRU 和工作集算法。他们都具有良好的性能并且能够被有效的实现。还存在其他一些好的算法，但实际上这两个可能是最重要的。
文件系统在备份的过程中会使用到算法，文件备份分为逻辑转储和物理转储
物理转储的主要优点是简单、极为快速（基本上是以磁盘的速度运行），缺点是全量备份，不能跳过指定目录，也不能增量转储，也不能恢复个人文件的请求。因此句大多数情况下不会使用物理转储，而使用逻辑转储。
逻辑转换(logical dump)从一个或几个指定的目录开始，递归转储自指定日期开始后更改的文件和目录。因此，在逻辑转储中，转储磁盘上有一系列经过仔细识别的目录和文件，这使得根据请求轻松还原特定文件或目录。
既然逻辑转储是最常用的方式，那么下面就让我们研究一下逻辑转储的通用算法。此算法在 UNIX 系统上广为使用，如下图所示
待转储的文件系统，其中方框代表目录，圆圈代表文件。黄色的项目表是自上次转储以来修改过。每个目录和文件都被标上其 inode 号。
此算法会转储位于修改文件或目录路径上的所有目录（也包括未修改的目录），原因有两个。第一是能够在不同电脑的文件系统中恢复转储的文件。通过这种方式，转储和重新存储的程序能够用来在两个电脑之间传输整个文件系统。第二个原因是能够对单个文件进行增量恢复。
逻辑转换算法需要维持一个 inode 为索引的位图(bitmap)，每个 inode 包含了几位。随着算法的进行，位图中的这些位会被设置或清除。算法的执行分成四个阶段。第一阶段从起始目录（本例为根目录）开始检查其中所有的目录项。对每一个修改过的文件，该算法将在位图中标记其 inode。算法还会标记并递归检查每一个目录（不管是否修改过）。
在第一阶段结束时，所有修改过的文件和全部目录都在位图中标记了，如下图所示
理论上来说，第二阶段再次递归遍历目录树，并去掉目录树中任何不包含被修改过的文件或目录的标记。本阶段执行的结果如下
注意，inode 编号为 10、11、14、27、29 和 30 的目录已经被去掉了标记，因为它们所包含的内容没有修改。它们也不会转储。相反，inode 编号为 5 和 6 的目录本身尽管没有被修改过也要被转储，因为在新的机器上恢复当日的修改时需要这些信息。为了提高算法效率，可以将这两阶段的目录树遍历合二为一。
现在已经知道了哪些目录和文件必须被转储了，这就是上图 b 中标记的内容，第三阶段算法将以节点号为序，扫描这些 inode 并转储所有标记为需转储的目录，如下图所示
为了进行恢复，每个被转储的目录都用目录的属性（所有者、时间）作为前缀。
最后，在第四阶段，上图中被标记的文件也被转储，同样，由其文件属性作为前缀。至此，转储结束。
从转储磁盘上还原文件系统非常简单。一开始，需要在磁盘上创建空文件系统。然后恢复最近一次的完整转储。由于磁带上最先出现目录，所以首先恢复目录，给出文件系统的框架(skeleton)，然后恢复文件系统本身。在完整存储之后是第一次增量存储，然后是第二次重复这一过程，以此类推。
尽管逻辑存储十分简单，但是也会有一些棘手的问题。首先，既然空闲块列表并不是一个文件，那么在所有被转储的文件恢复完毕之后，就需要从零开始重新构造。
另外一个问题是关于链接。如果文件链接了两个或者多个目录，而文件只能还原一次，那么并且所有指向该文件的目录都必须还原。
还有一个问题是，UNIX 文件实际上包含了许多 空洞(holes)。打开文件，写几个字节，然后找到文件中偏移了一定距离的地址，又写入更多的字节，这么做是合法的。但两者之间的这些块并不属于文件本身，从而也不应该在其上进行文件转储和恢复。
最后，无论属于哪一个目录，特殊文件，命名管道以及类似的文件都不应该被转储。
在 I/O 的磁盘调度中也出现过很多算法，关于寻址和磁盘臂的转动都会对算法产生影响，下面我们就来一起看下
一般情况下，影响磁盘快读写的时间由下面几个因素决定
这三种时间参数也是磁盘寻道的过程。一般情况下，寻道时间对总时间的影响最大，所以，有效的降低寻道时间能够提高磁盘的读取速度。
如果磁盘驱动程序每次接收一个请求并按照接收顺序完成请求，这种处理方式也就是 先来先服务(First-Come, First-served, FCFS) ，这种方式很难优化寻道时间。因为每次都会按照顺序处理，不管顺序如何，有可能这次读完后需要等待一个磁盘旋转一周才能继续读取，而其他柱面能够马上进行读取，这种情况下每次请求也会排队。
通常情况下，磁盘在进行寻道时，其他进程会产生其他的磁盘请求。磁盘驱动程序会维护一张表，表中会记录着柱面号当作索引，每个柱面未完成的请求会形成链表，链表头存放在表的相应表项中。
一种对先来先服务的算法改良的方案是使用 最短路径优先(SSF) 算法，下面描述了这个算法。
假如我们在对磁道 6 号进行寻址时，同时发生了对 11 , 2 , 4, 14, 8, 15, 3 的请求，如果采用先来先服务的原则，如下图所示
我们可以计算一下磁盘臂所跨越的磁盘数量为 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51，相当于是跨越了 51 次盘面，如果使用最短路径优先，我们来计算一下跨越的盘面
跨越的磁盘数量为 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17 ，相比 51 足足省了两倍的时间。
但是，最短路径优先的算法也不是完美无缺的，这种算法照样存在问题，那就是优先级 问题，
这里有一个原型可以参考就是我们日常生活中的电梯，电梯使用一种电梯算法(elevator algorithm) 来进行调度，从而满足协调效率和公平性这两个相互冲突的目标。电梯一般会保持向一个方向移动，直到在那个方向上没有请求为止，然后改变方向。
电梯算法需要维护一个二进制位，也就是当前的方向位：UP(向上)或者是 DOWN(向下)。当一个请求处理完成后，磁盘或电梯的驱动程序会检查该位，如果此位是 UP 位，磁盘臂或者电梯仓移到下一个更高跌未完成的请求。如果高位没有未完成的请求，则取相反方向。当方向位是 DOWN时，同时存在一个低位的请求，磁盘臂会转向该点。如果不存在的话，那么它只是停止并等待。
我们举个例子来描述一下电梯算法，比如各个柱面得到服务的顺序是 4，7，10，14，9，6，3，1 ，那么它的流程图如下
所以电梯算法需要跨越的盘面数量是 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22
电梯算法通常情况下不如 SSF 算法。
一些磁盘控制器为软件提供了一种检查磁头下方当前扇区号的方法，使用这样的控制器，能够进行另一种优化。如果对一个相同的柱面有两个或者多个请求正等待处理，驱动程序可以发出请求读写下一次要通过磁头的扇区。
这里需要注意一点，当一个柱面有多条磁道时，相继的请求可能针对不同的磁道，这种选择没有代价，因为选择磁头不需要移动磁盘臂也没有旋转延迟。
对于磁盘来说，最影响性能的就是寻道时间和旋转延迟，所以一次只读取一个或两个扇区的效率是非常低的。出于这个原因，许多磁盘控制器总是读出多个扇区并进行高速缓存，即使只请求一个扇区时也是这样。一般情况下读取一个扇区的同时会读取该扇区所在的磁道或者是所有剩余的扇区被读出，读出扇区的数量取决于控制器的高速缓存中有多少可用的空间。
磁盘控制器的高速缓存和操作系统的高速缓存有一些不同，磁盘控制器的高速缓存用于缓存没有实际被请求的块，而操作系统维护的高速缓存由显示地读出的块组成，并且操作系统会认为这些块在近期仍然会频繁使用。
当同一个控制器上有多个驱动器时，操作系统应该为每个驱动器都单独的维护一个未完成的请求表。一旦有某个驱动器闲置时，就应该发出一个寻道请求来将磁盘臂移到下一个被请求的柱面。如果下一个寻道请求到来时恰好没有磁盘臂处于正确的位置，那么驱动程序会在刚刚完成传输的驱动器上发出一个新的寻道命令并等待，等待下一次中断到来时检查哪个驱动器处于闲置状态。
在死锁的处理策略中，其中一点是忽略死锁带来的影响（惊呆了），出现过一个叫做鸵鸟算法的
最简单的解决办法就是使用鸵鸟算法(ostrich algorithm)，把头埋在沙子里，假装问题根本没有发生。每个人看待这个问题的反应都不同。数学家认为死锁是不可接受的，必须通过有效的策略来防止死锁的产生。工程师想要知道问题发生的频次，系统因为其他原因崩溃的次数和死锁带来的严重后果。如果死锁发生的频次很低，而经常会由于硬件故障、编译器错误等其他操作系统问题导致系统崩溃，那么大多数工程师不会修复死锁。
在死锁的检测中出现过一些算法
如果有多种相同的资源存在，就需要采用另一种方法来检测死锁。可以通过构造一个矩阵来检测从 P1 -> Pn 这 n 个进程中的死锁。
现在我们提供一种基于矩阵的算法来检测从 P1 到 Pn 这 n 个进程中的死锁。假设资源类型为 m，E1 代表资源类型1，E2 表示资源类型 2 ，Ei 代表资源类型 i (1 <= i <= m)。E 表示的是 现有资源向量(existing resource vector)，代表每种已存在的资源总数。
现在我们就需要构造两个数组：C 表示的是当前分配矩阵(current allocation matrix) ，R 表示的是 请求矩阵(request matrix)。Ci 表示的是 Pi 持有每一种类型资源的资源数。所以，Cij 表示 Pi 持有资源 j 的数量。Rij 表示 Pi 所需要获得的资源 j 的数量
一般来说，已分配资源 j 的数量加起来再和所有可供使用的资源数相加 = 该类资源的总数。
死锁的检测就是基于向量的比较。每个进程起初都是没有被标记过的，算法会开始对进程做标记，进程被标记后说明进程被执行了，不会进入死锁，当算法结束时，任何没有被标记过的进程都会被判定为死锁进程。
上面我们探讨了两种检测死锁的方式，那么现在你知道怎么检测后，你何时去做死锁检测呢？一般来说，有两个考量标准：
还有死锁避免的算法
银行家算法是 Dijkstra 在 1965 年提出的一种调度算法，它本身是一种死锁的调度算法。它的模型是基于一个城镇中的银行家，银行家向城镇中的客户承诺了一定数量的贷款额度。算法要做的就是判断请求是否会进入一种不安全的状态。如果是，就拒绝请求，如果请求后系统是安全的，就接受该请求。
比如下面的例子，银行家一共为所有城镇居民提供了 15 单位个贷款额度，一个单位表示 1k 美元，如下所示
城镇居民都喜欢做生意，所以就会涉及到贷款，每个人能贷款的最大额度不一样，在某一时刻，A/B/C/D 的贷款金额如下
上面每个人的贷款总额加起来是 13，马上接近 15，银行家只能给 A 和 C 进行放贷，可以拖着 B 和 D、所以，可以让 A 和 C 首先完成，释放贷款额度，以此来满足其他居民的贷款。这是一种安全的状态。
如果每个人的请求导致总额会超过甚至接近 15 ，就会处于一种不安全的状态，如下所示
这样，每个人还能贷款至少 2 个单位的额度，如果其中有一个人发起最大额度的贷款请求，就会使系统处于一种死锁状态。
这里注意一点：不安全状态并不一定引起死锁，由于客户不一定需要其最大的贷款额度，但是银行家不敢抱着这种侥幸心理。
银行家算法就是对每个请求进行检查，检查是否请求会引起不安全状态，如果不会引起，那么就接受该请求；如果会引起，那么就推迟该请求。
类似的，还有多个资源的银行家算法，读者可以自行了解。
京公网安备 11010802035086号