1. 进程调度算法

调度的时机通常是以下的几种，即当以下的事件发生的时候就会进行调度：进程从就绪态转变为运行态，操作系统会在就绪队列中选择一个进程运行；或者是进程从运行态转变为阻塞态；在当前进程进入阻塞状态之后OS必须选择一个进程继续运行，此时就会发生调度；同样的，当当前的进程运行结束的时候OS也会使用调度程序选择一个进程运行；调度的原则就是尽量使CPU的利用率高，系统的吞吐率高；周转时间短；等待时间短；响应时间迅速；

1. 先来先服务算法（FIFO）

• 在了解各个算法之前，先来介绍几个概念，以及相关指标，首先就是吞吐量，我们可以把吞吐量理解为单位时间内CPU执行作业的时间，比如系统每小时完成的作业数量；接着就是周转时间，周转时间 = 完成时间 - 到达时间，最后就是响应时间 = 首次运行的时间 - 到达时间；
• 当计算机系统是多道程序设计的时候，通常就会有多个进程或者是线程同时竞争CPU；只要有两个或者是更多的进程/线程处于就绪状态的时候，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程，在操作系统中完成选择的这一部分称为调度程序，该程序使用的算法称为调度算法；调度算法在不同的系统之中有不同的目标，但是通常来说都是实现更高的吞吐量，更低的周转时间，更快的响应时间以及更好的均衡性，但是它们往往不可以被同时满足，比如说如果是一个实时系统，那么在截止时间之前完后任务将会是很重要的，相比之下此时的响应时间就不是那么的重要的了，但是在交互式系统之中，用户都希望能够获得最快的响应时间，所以说在这种系统之中响应时间才是最重要的；
• 先来先服务算法是一个非抢占式的算法，当操作系统使用该算法进行调度的时候，进程将会按照他们请求CPU的顺序使用CPU，该算法会使用一个队列来维护程序在运行过程中的调度，该队列通常是由链表实现的，该链表上的节点就是一个就绪进程，当一个作业从外部进入系统之后，如果该作业是第一个进入系统的作业，那么他就会立即开始运行，并且会运行它所期望的时间长度，该作业不会因为运行时间太长而被中断，如果在该作业运行的时候有其他的作业也进入了系统，那么这些作业将会被放置于就绪队列的队尾(在很多情况下该队列是由链表实现的)；当真在运行的进程被阻塞时，就绪队列中的第一个进程就会接着运行，当被阻塞的进程变为就绪的时候，他就会被放置在就绪队列的队尾，也就是排在所有进程的后面；该算法适用于批处理系统。
• 该算法的实现是非常简单的，要选取一个进程运行的时候只要从队列的头部移走一个进程即可，要添加一个新的作业或者是阻塞一个进程的时候，只需要把改作业或者是进程添加到队列的末尾即可；不过，该算法的缺点也是非常的明显的，那些耗时非常短的进程可能会被排到耗时非常长的进程之后，此时系统的平均周转时间就会变得很高，影响了系统整体的性能；

2. 最短作业优先算法（SJF）

• 该算法每次都会执行运行时间最短的作业，比如有下图三作业，分别是A, B, C，那么他们的平均周转时间将会是(10+20+120)/3=50秒，但是在相同的情况下，如果采用先进先出算法的话，他们的平均周转时间将会是(100+110+120)/3=110秒(假设A只比B和C稍微的早到了一小会儿，虽说这种假设略显牵强，但是这种情况还是会出现的)，大大的降低了周转时间的大小，该算法可以应用于比较在意平均用户周转时间的场景，需要指出的是，当所有的作业几乎都是同时到达系统的情况下，最短作业优先算法将会是最优的算法，但是在其它的情况下最短作业优先算法将不再是最优的调度算法，而且如果在程序执行的过程中一直有比较短的作业源源不断的到达系统等待被调度，那么那些长作业可能永远也不会得到运行的机会，此时我们说这些长作业会被“饿死”；该调度算法同样适用于批处理系统；

3. 最短完成时间优先算法（STCF）

• SJF是一个非抢占式的调度算法，因此它会出现一些问题，比如在上述的例子中，如果B和C晚于A到达系统，那么SJF仍然会先执行A，然后才会继续执行B和C，在这种情况下，他们的平均周转时间将会是(100+(110-10)+(120-10))/3=103.33，只是非常糟糕的，所以我们可以向SJF添加抢占，称为最短完成时间优先(ShortestTime-to-Completion First，STCF)或者是抢占式最短作业优先(Preemptive Shortest Job First ，PSJF)算法，每当有新工作进入系统的时候，该算法就会在剩余的工作以及新工作中确定谁的剩余工作时间最短，然后调度该工作；该算法同样适用于批处理系统；
  

4. 高响应比优先算法(Highest Response Ratio Next, HRRN)

• 该算法会在进行调度的时候先计算各个进程的响应比优先级，把优先级最高的进程投入运行，响应比优先级的计算公式如下所示：
  
  从这个公式可以看出，如果两个进程的等待时间相同的时候，要求服务的时间越短，响应比优先级就越高，也就是说短作业的进程更加容易被选中运行；如果两个进程的要求服务时间相同的时候，等待时间越长，响应比优先级就越高，并且进程的响应比优先级会随着等待时间的增加而增加，也就更容易被选中运行；所以这个算法兼顾了短作业以及长作业；同时也不会使进程等待过长的时间；

5. 时间片轮转调度算法(RR)

• 以上三个算法虽然是用于批处理系统，但是以上三个算法的响应时间都太长了，如今的很多PC机都是供用户使用的个人电脑，那么其中的操作系统就必须非常重视响应时间这一性能指标，这是如果OS的调度程序使用的是以上三个算法的话，用户对响应时间的要求肯定是得不到满意的，如果是FIFO或者是SJF，那么后到来的程序作业可能会必须一直等到前面的进程执行完毕才能开始运行，此时的响应时间就太长了，哪怕是抢占式的SJF也会出现这样的问题，为了解决这个问题，我们可以引入一种叫做时间片轮转的调度算法；
• 时间片轮转算法是一种最古老，最简单同时又是最公平的调度算法；在执行时间片轮转算法的时候，OS会为每一个处于就绪状态的进程分配一个可以使用CPU的时间段，该时间段就被称之为时间片；如果时间片在用完的时候进程还没有执行结束，那么OS会剥夺CPU并分配给另外一个进程；如果进程在时间片用完之前就已经执行完毕了，那么CPU会立即进行切换，从而使其他正在处于就绪态的进程开始执行。时间片轮转调度算法的实现非常简单，调度程序只需要维护一个就绪进程列表，当一个进程使用完它的时间片的时候，如果该进程还没有执行完毕，那么就将该进程移动到队列的末尾；
  
  
• 虽说时间片轮转算法实现起来非常的简单，但是时间片长度的选取是一个亘久不变的话题；我们知道，从一个进程切换到另一个进程的时是需要一定的时间进行事务管理相关的工作的：保存并装入寄存器的值以及内存映像，更新各种表格以及列表等数据结构，清除并重新调入内存高速缓存等；如果我们假设发生进程切换的工作(有时也称为上下文切换)需要1ms，时间片长度为4ms，那么当进程使用完4ms的时间片之后(假设进程在执行一个时间片之后它的工作还没有执行完)，CPU将耗费1ms的时间进行上下文切换，因此CPU会浪费掉20%的执行时间用于管理上下文切换；
• 为了降低管理上下文切换所浪费的时间比率(也就是提高CPU的效率)，我们可以将时间片设置为100ms，这时浪费的时间只占有1%，但是如果在一个非常短的时间间隔内如果同时有50个进程进入了就绪队列，此时如果CPU是空闲的，那么第一个到达的进程将会立即执行，如果每一个进程都充分利用了分配给它们的时间片，那么第二个进程必须得要等100ms的时间之后才能够获取CPU，而最后一个进程要等上足足5s的时间之后才能够执行，假想你打开一个应用或者是点击一个应用的按钮之后过了5s才得到响应，那么你很有可能会恼羞成怒；另一方面，如果我们将时间片的大小设置为大于平均的CPU突发时间，那么通常就不会发生抢占，因为此时在时间片耗费完之前多数进程都会完成一个阻塞操作，从而发生上下文切换，但是这种上下文切换不是因抢占而发生的，而是在逻辑上确实有需要的时候才发生的，所以说这个时候CPU的执行效率将会得到提升；由此我们可以得到如下的结论：时间片设置的太短的话会导致过多的上下文切换，降低了CPU的效率；而将时间片设置的太长的话又会导致对后到达的进程以及短进程的交互请求的响应时间边长。经实践表明，将时间片设置为20~50ms通常是一个比较合理的折中。

6. 优先级调度算法

• 时间片轮转算法做了一个隐含的假设，那就是所有的进程的重要程度都是一样的，即所有的进程的优先级都是一样的，但是事实却并非如此，即使在只有一个用户的PC机上面的众多进程之中，他们的重要程度也不太可能全部都是一样的，比如在屏幕上实时显示视频内容的进程和一个在后台发送电子邮件的守护进程相比，肯定是前者的优先级要高，只有这样才能够满足用户的需求；所以说我们引入了优先级调度算法；当引入优先级调度算法之后，我们就必须防止高优先级的进程永无止境的运行下去，调度程序可以在每一个时钟中断发生的时候适当降低当前进程的优先级，这样可以使当前进程的优先级降低到小于次高优先级的进程的优先级，此时就可以发生上下文切换；另一种做法是为每一个进程分配一个允许运行的最大时间片，当前进程用完这个时间片的时候就必须发生上下文切换从而让次高优先级的进程运行；优先级可以是静态赋予的也可以是动态赋予的；比如说有一个I/O密集型的进程，其多数时间都是用来等待I/O的结束，当该进程需要CPU的时候应当立即将CPU分配给它，以便启动下一个I/O请求，这样就可以在该进程等待I/O的时候执行另一个进程；如果CPU没有被立即分配给I/O密集型的进程，而是让它长时间的等待CPU，那么该进程就会毫无意义的长时间的占用内存等资源。为了使有I/O密集型进程存在的程序能够获得比较好的执行效率，我们可以将进程的优先级设置为1/f，其中f为该进程在上一个时间片之中真正运行的时间与时间片长度的比值，比如该进程被分配了50ms的时间片，但是他只执行了1ms，那么它的优先级就是50(数值越大优先级越高)，此时就可以确保I/O密集型的进程能够获得较高的优先级，从而提高整个程序的执行效率。
• 我们可以把一组进程按优先级分为若干类，并在各类进程之间采用优先级调度，在各类进程内部采用时间片轮转调度算法；这种调度的一种经典实现方式就是多级反馈队列调度算法(MLFQ)，下面我们就来看看这个算法的具体实现原理。

7. 多级反馈队列调度算法(MLFQ)

• 如果我们想要获得表现更优异的周转时间，那么我们就会采用SJF或者是STCF，这两个调度算法必须知道一个工作会运行多长时间，但是在实际的情况中，OS通常并不知道一个工作会运行多久，所以说SJF和STCF在很多情况下是不能使用的；同时，由于现代的OS很多都是应用于个人PC上面的，所以我们需要OS提供良好的响应时间表现，此时我们可以采用RR(时间片轮转算法)来解决这一问题，但是RR虽然降低了响应时间，但是它的周转时间却表现的很差，而MLFQ就是用来解决SJF, STCF以及RR的问题的，我们需要在保证拥有良好的响应时间的表现的同时拥有良好的周转时间表现，并且需要在对进程一无所知的情况下实现这些目标；多级反馈队列就是通过从历史中学习来解决这些问题的，比如一个进程会有明显的阶段性行为，因此我们可以通过他们的这一特性进行预测，不过这一种技术可能会导致OS做出比一无所知的时候更糟糕的决定；

• MLFQ中有许多独立的队列，每一个队列有不同的优先级，任何时刻一个工作只能在一个队列中存在；MLFQ总是优先执行较高优先级的工作(也就是在较高级队列中的工作)，同时，每一个队列中会有很多的工作，因此他们的优先级是相同的，此时MLFQ将会对这些工作采用轮转调度算法；因此，MLFQ的关键就在于如何合理地设置队列优先级；MLFQ不会为每一个工作设置固定的优先级，而是根据观察到的工作的具体行为动态地调整每一个工作的的优先级；比如一个工作不断地放弃CPU等待键盘的输入，那么这个工作是一个交互型的工作，此时MLFQ会让它保持较高的优先级，而对于一个长时间占用CPU的工作，MLFQ会降低它的优先级。通过这种方式，MLFQ在进程运行的过程中学习其行为，从而利用工作的历史来预测它未来的行为；

• 至此，我们得到了MLFQ的两条基本的规则：

  • 规则1：如果A的优先级>B的优先级，那么运行A而不运行B；
  • 规则2：如果A的优先级=B的优先级，那么轮转运行A和B；

• 在这里我们展示一些队列的静态快照，此时A和B会优先被执行：
  

如何改变优先级

我们必须决定在一个工作的生命周期中MLFQ应该如何改变他们的优先级；要做到这一点，我们必须获得工作负载相关的信息，在计算机实际运行的过程中，既有频繁放弃CPU，且运行时间很短的交互性工作；也有需要很多CPU时间，但是响应时间要求却不高的长时间计算密集型工作，MLFQ必须想办法对这些工作的优先级进行合理的调整，在这里我们可以得到另外三个规则；

• 规则3：工作进入系统时，放在最高优先级(最上层队列)；
• 规则4a：工作完整个时间片后，降低其优先级；
• 规则4b：如果工作在其时间片以内主动释放CPU，则优先级不变；

实例1. 单个长工作

首先，我们来看一个单个长工作的例子，下图展示了一个拥有3各队列的调度程序；随着时间的推移，该工作的运行情况如下图所示：

从这个例子中可以看出，该工作首先就最高优先级(Q2)，执行一个10ms的时间片后，调度程序将工作的优先级减1，进入队列Q1；在Q1又执行一个时间片之后，最后进入系统的最低优先级并一直停留在那里；

实例2. 外加一个短工作

在这个例子中，有两个工作，A(用黑色表示)是一个长时间运行的CPU密集型工作，B(用灰色表示)是一个运行时间很短的交互型工作，假设A执行一段时间后B到达，对于B来说MLFQ会近似于SJF吗？下图展示了这种场景的结果；A在最低优先级队列执行(长时间运行的CPU密集型作业都是这样的)，随后B到达并被加入到最高优先级队列，由于它的运行时间很短，只有20ms，所以在经过两个时间片之后B就执行完毕了，然后A接着执行。

通过这个例子，我们就可以体会到这个算法的一个重要的目标：如果不知道一个工作是短工作还是长工作，就都先将其假设为短工作，并赋予最高的优先级；真正的短工作会很快就结束运行，而长工作会慢慢地被移动到低优先级的队列中，通过这种方式，MLFQ近似于SJF；

实例3. 加上I/O

现在我们来看一个有I/O的例子，在上述的规则4b中，如果有一个工作在自己的时间片用完之前主动的放弃了CPU，那么它的优先级将会保持不变，假设一个交互型的工作有大量的I/O操作，那么它会在时间片用完之前主动放弃CPU，在这种情况下，我们并不希望它的优先级会被降低，并保持它的优先级不变，此时如果处于Q2的工作是一个交互型工作，那么MLFQ就实现了它的目标：让交互型工作快速运行(保持较高的优先级)；下图展示了这一过程；

当前MLFQ的一些问题

首先，该算法存在饥饿问题，如果系统有过多的交互型工作，那么他们就会不断地占用CPU，可能会导致长作业永远无法得到CPU；其次，可能会出现一些每运行99%的时间片就主动放弃CPU的作业出现，该作业几乎可以独占CPU；

解决方案1：提升优先级

一个简单并且可行的方法就是周期性的提升所有工作的优先级：将所有的工作扔到优先级最高的队列；于是我们便有了一个新的规则：规则5：经过一段时间S，就将系统中的所有工作重新加入到最高优先级的队列；新规则一下解决了两个问题。首先，进程不会饿死：在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享CPU，从而最终获得执行。其次，如果一个CPU密集型工作变成了交互型，当它优先级提升时，调度程序会正确对待它；我们来看一个例子。在这种场景下，我们展示长工作与两个交互型短工作竞争CPU时的行为。以下两张图中，左边没有优先级提升，长工作在两个短工作到达后被饿死。右边每50ms就有一次优先级提升（这里只是举例，这个值可能过小），因此至少保证长工作会有一些进展，每过50ms就被提升到最高优先级，从而定期获得执行；当然，添加时间段S带来了一个新的问题，S的值很难设置，如果S设置得太高，长工作会饥饿；如果设置得太低，交互型工作又得不到合适的CPU时间比例；

解决方式2：更好的计时方式

现在还有一个问题要解决，怎么确保每运行99%的时间片就主动放弃CPU的作业不会几乎独占CPU？其实我们更改一下规则4就可以了，这里的解决方案，是为MLFQ的每层队列提供更完善的CPU计时方式（accounting）。调度程序应该记录一个进程在某一层中消耗的总时间，而不是在调度时重新计时。只要进程用完了自己的配额，就将它降到低一优先级的队列中去。不论它是一次用完的，还是拆成很多次用完。因此，我们重写规则4a和4b；规则4：一旦工作用完了其在某一层中的时间配额（无论中间主动放弃了多少次CPU），就降低其优先级（移入低一级队列）；下图对比了规则4修改前后的情况：

没有新的规则4的保护时，进程可以在每个时间片结束前发起一次I/O操作，从而垄断CPU时间。有了这样的保护后，不论进程的I/O行为如何，都会慢慢地降低优先级，因而无法获得不合理的CPU时间比例；关于MLFQ调度算法还有一些问题。其中一个大问题是如何配置一个调度程序，例如，配置多少队列？每一层队列的时间片配置多大？为了避免饥饿问题以及进程行为改变，应该多久提升一次进程的优先级？这些问题都没有显而易见的答案，因此只有利用对工作负载的经验，以及后续对调度程序的调优，才会得到令人满意的方案；例如，大多数的MLFQ变体都会支持不同的队列可变的时间片长度；高优先级队列通常只有较短的时间片（比如10ms或者更少），因而这一层的交互工作可以更快地切换。相反，低优先级队列中更多的是CPU密集型工作，配置更长的时间片会取得更好的效果。下图展示了一个例子，两个长工作在高优先级队列执行10ms，中间队列执行20ms，最后在最低优先级队列执行40ms；

Solaris的MLFQ实现（时分调度类TS）很容易配置。它提供了一组表来决定进程在其生命周期中如何调整优先级，每层的时间片多大，以及多久提升一个工作的优先级。管理员可以通过这些表，让调度程序的行为方式不同。该表默认有60层队列，时间片长度从20ms（最高优先级），到几百ms（最低优先级），每一秒左右提升一次进程的优先级；除此之外的其他一些MLFQ调度程序没用表，甚至没用本文中讲到的规则，有些采用数学公式来调整优先级。例如，FreeBSD调度程序（4.3版本），会基于当前进程使用了多少CPU，通过公式计算某个工作的当前优先级。
最后，许多调度程序有一些我们没有提到的特征。例如，有些调度程序将最高优先级队列留给操作系统使用，因此通常的用户工作是无法得到系统的最高优先级的。有些系统允许用户给出优先级设置的建议（advice），比如通过命令行工具nice，可以稍微地增加或降低工作的优先级，从而增加或降低它在某个时刻运行的机会。

8. 将调度的机制和策略分离

• 在以上算法的讨论过程中，我们假设系统中所有的进程都是分别属于不同的用户并且相互竞争CPU的，在通常的情况下确实是这样，但是在某一些工作场景中会出现一个父进程会有许多的子进程在父进程的控制下运行。例如在一个数据库系统之中可能会存在许多的子进程，每一个子进程处理不同的请求，或者是每一个子进程进行不同的工作。父进程完全可能掌握哪一个子进程的工作才是最重要的，但是在以上讨论的算法之中没有一个算法可以从用户进程接收有关的调度决策信息，这就导致了调度程序很少能够做出最优的选择；
• 解决该问题的一个行之有效的方法就是将调度机制(机制决定了系统要提供那些功能)与调度策略(策略决定了系统将会怎么执行那些机制)分离。也就是将调度算法以某种形式进行参数化，而参数可以由用户进程进行填写，这样一个父进程本身虽然并不参与调度，但是它可以控制如何调度子进程的细节，比如决定让哪一个子进程优先执行。在这里调度机制位于OS的内核，而调度策略则由用户进程决定。将策略与机制进行分离的思想在OS的各种实现中是非常常见的。

9. 比例份额调度

1. 概算法的目标数是确保每一个工作都有一定比例的CPU执行时间而不是得到好的周转时间和响应时间，可以使用彩票抽奖的例子理解该调度方式。假设现在有两个进程，分别是A和B，分配给进程A的彩票是25张，分配给B的彩票有25张，这么分配的目的是使A占用75%的CPU时间，使进程B占有25%的CPU时间；

2. 具体来说就是随机的进行彩票的抽取，对于100个彩票的话单次抽取的结果就是0~99之间的一个数字，哪一个进程持有数字编号对应的彩票就使哪一个进程使用CPU。如果抽取彩票得到了一下的彩票序列，那么A和B的运行情况如下所示：
   
   
   可以看到B运行了20个时间片之中的4个，占有20%，并不是所期望的25%。但是这两个进程运行的事件越长，最终得到的CPU时间比例就会越接近期望的数值。同时各个进程执行完毕的时间会更加的接近。

3. 该机制还允许拥有彩票的用户自行对自己的工作进行彩票的再分配，比如用户A和用户B各自拥有100张彩票，用户A有两个工作A1，A2，它可以给A1和A2分别分配50张彩票，也可以假设用户B有一个工作B1，那么B1就可以拥有用户B的所有彩票；一个进程也可以临时将自己的彩票转让给另一个进程。该机制在客户端/服务器交互的场景之中很有用，客户端向服务器发送消息，请求服务器完成所需的工作，为了加速服务器的执行，客户端可以将自己的彩票分配一部分给服务器，使服务器得到更多的CPU执行时间，在服务器之中完成之后会将这部分彩票归还给客户端。进程也可以提升或者是降低自己所持有的彩票数，但是这种机制的意义不大，因为进程之间是互不信任的。

4. 彩票机制的实现是很简单的，只需要一个运行的不错的随机数生成器和一个记录系统中所有进程信息的数据结构，以及彩票的总数；假定以上的数据结构采用的是链表，并且各个进程都拥有一定数量的彩票，那么所得出的链表如下图所示：
   
   在做决策之前，首先会从总数400之中选取一个随机数，假定选择了300，然后就可以遍历链表根据计数器找到需要调度的进程：
   
   每个进程的彩票值会增加到计数器counter上，直到值超过300，此时到达的进程就是我们所需的进程。可以按照彩票的数量进行递减排序，最终得到的结果仍然是正确的，但是能够以最小的迭代次数找到所需的节点。

5. 对于该调度机制来说如何为进程分配彩票依然没有最佳的答案，同时使用“彩票”和计数器的方式最终得出的结果是不确定的。采用步长调度算法可以得到确定的比例份额结果。系统中的每一个进程都有自己的步长，和彩票数值是反比的关系。比如以上的A, B, C三个进程的彩票数分别是100,50和250，通过一个大数分别除以它们的票数来得到相应的步长，比如10000，得到的步长分别是100,200和40。每次进程运行后就会让进程的计数器增加它的步长，得到行程值以记录进程的工作进展。当需要进行调度的时候，选择目前拥有最小行程值的进程，并且在运行之后对该进程的行程值增加一个步长，以下是伪代码描述：
   
   在刚开始的时候三个进程的行程值都是0，假设选择A执行，在A执行一个时间片之后，它的行程值会增加一个步长，变为100，之后运行B，并更新行程值为200，最后是C，更新行程值为40。此时算法选择行程值最小的进程C继续运行，并更新行程值，以此类推。步长调度算法在执行一个周期之后会是每一个进程最终都运行准确的时间份额；

6. 彩票调度算法不需要全局状态，但是步长调度算法需要设置步长的全局数据，如果有一个新的进程加入进来，对于它的行程值的设置就会是一个棘手的问题，如果设置成0的话，在一段时间内该进程可能会独占CPU，所以说步长调度算法在实现之上是更加复杂的。彩票调度只需要将新进程的彩票数更新至全局的总票数就可以了，因此其可以更加合理地加入新的进程。

10. 多处理器调度

1. 现在的计算机系统往往是多处理器的，多处理器机器对调度算法的要求会更高，同时实现也会更加的复杂，因为多处理器所需要做的工作是是更高的，和单处理器的差别也很大；

2. 多处理器和单处理器之间最大的区别就是对硬件缓存的使用，以及多处理器之间共享数据的方式。对于多处理器的细节在CSAPP的笔记之中已经详细的介绍了，在这里不在赘述。如果系统之中有多个处理器共享同一块内存的话会出现缓存一致性的问题：
   
   比如一个运行在CPU1上的程序从内存地址A读取数据，由于该数据不在CPU1的缓存之中，所以系统直接访问内存得到值D并放入到缓存之中，并且将其修改为D1。由于将修改写回内存会带来额外的开销，一般情况下会延迟对数据的写回。如果此时操作系统中断了运行在CPU1上的程序，并将其转移到CPU2上重新读取数据，但是CPU2还不知道数据已经在缓存之中了，所以说它会重新读取地址A处的数据，得到旧的值D，而不是已经更新了的D1，这就是缓存一致性问题。

3. 硬件提供了这个问题的基本解决方案，硬件会监视对内存的访问，从而保证可以获取正确的数据，并保证共享内存的唯一性。在基于总线的系统中，一种方式是使用总线窥探。每个缓存都通过监听连接所有缓存和内存的总线，从而察觉到对内存的访问。如果CPU发现了它自己放在缓存中的数据在内存中被更新了，就会作废本地副本（从缓存中移除）或者是更新缓存中的数据。回写缓存会让事情变得更复杂。

4. 但是将修改写回内存是会被延迟的，CPU2并不会立即觉察到数据D已经被修改了，除非不延迟对内存的同步，直接将数据写回到内存；

5. 跨CPU的访问，尤其是写入操作，如果对象是共享数据的话，需要使用互斥原语（比如使用锁），才能够保证程序的正确性，当然也可以使用无锁的数据结构，但是比较的复杂。。如果没有锁，仅仅依赖硬件的一致性协议仍然是不安全的；

6. 当一个进程在一个CPU上运行的时候，会在CPU的缓存中维护许多的状态，下次该进程在相同的CPU上运行时会由于缓存中的数据而运行的更快。但是如果进程一直在不同的CPU之间来回切换运行，会由于需要重新加载数据而运行的更慢。这种现象叫做缓存亲和度，所以多处理器调度应该使一个进程尽量保持在一个CPU上运行。

7. 最基本的算法是将所有需要调度的工作放入一个单独的队列中，称作单队列多处理器调度（Single Queue Multiprocessor Scheduling，SQMS），这种方式的优点是实现简单，并且不需要很大的修改就可以将原有的策略应用于多个CPU。但是该算法缺乏可扩展性。在SQMS访问单个队列的时候锁确保得到正确的结果。不过随着CPU数量的增加，锁着对锁的争用增加，会需要更多的时间用在锁的开销上，更少的时间完成真正的操作。该算法还有一个问题就是缓存的亲和度是比较差的，比如有以下的5个工作和4个处理器，调度队列将如下所示：
   
   假设每个进程运行一个时间片，那么一段时间之后得到的CPU可能的调度序列如下所示：
   
   可以看到每一个工作在不同的CPU之间转移，缓存亲和度非常的低。为了解决以上的问题，SQMS必须引入一些亲和度机制，保持一些进程的亲和度的时候可能会牺牲其他工作的亲和度：
   
   可以看到除了E在不断地迁移之外其它的进程都有比较好的缓存亲和度。

8. 多队列调度（MQMS）可以解决SQMS在扩展性以及缓存亲和度上的缺陷。它的思想就是维护多个相互独立的对列，每一个队列可以使用不同的调度规则，比如轮转等各种各样的调度算法。当一个进程进入OS之后可以随机的将其分配到一个队列或者是将其分配到一个进程数量比较少的队列。假设有两个处理器，有四个进程，那么就可以得到一下的可能的队列：
   
   队列可以选择任何的调度算法，比如是RR算法：
   
   MQMS具有很好的可扩展性，队列的数量可以随着CPU数量的增加而增加，因此锁和缓存争用的开销可以被很好的中和，又由于所有的工作保持在固定的CPU之上，所以可以很好地利用缓存中的数据，虽说会带来负载不均衡的问题。如果想要解决负载均衡的问题的话，可以使进程在不同的队列之间不断地切换，系统可以采用工作窃取的方法决定何时对哪一个队列中的进程进行迁移，刚方法会使进程数比较少的进程不定期的查看其它队列中的进程数是不是显著的比自己的要多，如果是的话就从其它的队列之中将进程迁移至自己的队列之中。不过需要找到一个合适的检查时间，如果时间太短的话会带来较大的开销，但是检查时间相隔的太长的话有可能会带来严重的负载不均衡。

2. 页面置换算法

当CPU想要访问的页面不在物理内存中的时候就会发生缺页中断，请求操作系统将所缺少的页面从磁盘中读取到物理内存：

以上的步骤中会将在磁盘里面找到的页面数据放置于物理内存的空闲页中；但是如果此时找不到一个空闲页，那么就需要在物理内存中替换出一个物理页面，以容纳此时所需要的页面；此时就要用到页面置换算法选择一个要置换出的页面，如果这个将要被置换出物理页面在被使用的时候数据发生了修改，那么这就是一个脏页，需要把它换出到磁盘，然后把被置换出的页表项的状态置为无效的，最后把现在需要的页面装入到这个物理页中；

所以就需要一种算法可以在出现缺页异常并且没有空闲的物理页的时候合理地选取一个页面置换出去；算法的目标是尽可能的减少整体的页面置换的次数，常见的页面置换算法分别是最佳页面置换(OPT)，先进先出页面置换(FIFO)，最近最久未使用算法(LRU)，时钟置换算法(Lock)，最不常用置换算法(LFU)；

最佳页面置换算法： 最佳页面置换算法的原则就是置换掉在将来最长时间不会被访问的页面；所以该算法需要知道所有的页面在未来的访问序列，然后通过比较选出最长时间内没有被访问的页面；比如在以下的例子中页面的置换顺序将会如图所示：

在以上的例子中一共发生了7次缺页，页面置换发生了4次，其实这就是最佳的置换策略，但是因为程序访问页面的顺序是随机的，根本无法准确的预测，所以无法实现，最佳置换策略仅仅是作为其它算法的衡量标准；在仅考虑实现的思想的情况下，效率越接近于该算法的方式就越高效；

先进先出置换算法： 可以选择将在内存中驻留的时间最长的页面置换出去，这就是先进先出的思想，还是上图中的例子，置换情况将会如下所示：

缺页发生了10次，页面置换发生了7次，可以看出置换的效率是很低的，而且它还可能会置换出重要的页面，这些页面在今后可能会被频繁的访问；同时该算法还存在Belady异常，也就是在缓存的容量变大的时候缓存的命中率不仅没有变大，反而变小了；

最近最久未使用算法： 如果一个程序在过去访问了一个页，那么在不久的将来该程序可能会再次访问这一个页面，越近被访问过的页面，再次被访问的可能性就会越大，这一切都是基于局部性原理，也就是说程序在最近访问到的内存在不久的未来很可能被再次访问；最近最久未使用算法的思想就是基于局部性原理的；该算法会选择一个在最长时间没有被访问的页面进行置换；也就是假设该页面在将来也不大可能会被访问；还是用以上的例子说明该算法的执行流程：

一共发生了9次缺页，页面置换发生了6次，性能要高一些，但是该算法实现的代价很高；如果想要完全实现LRU的话，就需要在内存中维护一个包含所有页面信息的链表；最近最多使用的页面放置于链表的头部，最近最少使用的页面放置于链表的尾部；问题就是在每次进行内存访问的时候都需要更新整个链表；在链表中找到访问的页面并删除，然后将它移动至表头，这是一个非常耗时的操作，所以LRU在思想上虽说看起来不错，但是在实际的实现中所需的开销还是比较大的，在实际情况中可能并不是我们想象中的那样应用的非常广泛；很多情况下会使用类似于LRU的算法，比如时钟算法；

工作负载的示例： 以下的例子中展示了更加复杂的工作负载；第一个工作负载是没有局部性的；

时钟置换算法： 时钟置换算法就是一种既能够优化置换的次数，又能够方便实现的算法，想要实现该算法的话就需要硬件添加一个使用位，对应于每一个页面，每一个页的使用位可以存储在进程的页表中，也可以存储在某一个数组中。每当页面被使用的时候硬件就会将使用位置为1；但是硬件不会将使用位的值设置为0，这是由操作系统完成的；时钟算法会将所有的页面都保存在一个环形链表中，一个表指针指向一个最老的页面，当发生缺页中断的时候会首先检查表指针指向的页面；如果该页面的引用位的值是0的话就淘汰该页面，并把新的页面插入到这个位置，然后将表指针前移一个位置；但是如果访问位是1的话就清除访问位，将访问位的值设置为0，并把表指针向前移动一个位置；所以重复以上的步骤最终找到的引用位为0的那一个页面就是一个比较老的页面，它就是算法的目标页面，将它置换出去就可以了：

由于一个被修改的页面在发生置换的时候需要置换到磁盘，所以可以对时钟算法进行改动，使得它可以尽可能的替换出没有被修改过的页面；比如在硬件中添加一个修改位，每次进行修改操作的时候都会设置修改位，可以在每一次的选择中找到一个既比较老的，又是没有被修改的页面；如果实在是找不到的话再去寻找一个比价老的但是被修改了的页面；当然也可以实现为其它的方式；操作系统在将页面写入到磁盘的时候并不是简单的一次写出一个，而是对需要进行写出的页面尽心收集，以聚集或者是分组的方式将收集到的页面写入到磁盘；因为对于磁盘驱动器的性质来说执行单次大的写操作，比许多小的写操作要更加的有效；同时在内存被超额请求的时候系统会不断地进行换页，也即是常说的抖动现象，操作系统可能会在抖动发生的时候决定先不运行一部分的进程，而仅仅是运行那些最活跃的进程，试图减少进程的工作集，从而将部分页面放置于内存中防止出现抖动的现象；

最不常用算法： 最不常用算法是选择访问次数最少的那一个页面，并将其淘汰；它的实现方式就是为每一个页面设置一个访问计数器，每当一个页面被访问的时候就将访问计数器的值加一；虽说看起来很简单，但是最终的硬件成本是很高的；而且如果保存页面的链表很长的话，寻找一个访问计数最小的页面最终的耗时也很大；同时该算法也只是考虑了使用的次数，并没有考虑时间的效应，比如一个页面在很久之前被访问了很多次，但是在最近的执行中该页面一直没有被访问；而一个新到来的页面可能在之后会被频繁的访问，但是此时它的访问计数器中的值却是很小的；解决方式就是可以定期地减少访问计数器中的值；比如当中断发生的时候把访问计数器中的值除以2，也就是说随着程序的运行，以前的高访问次数的页面会慢慢的变少，相当于加大了它本身被置换的概率；

3. 磁盘调度算法

磁盘的结构如下图所示：

磁盘调度算法的目的很简单，就是为了提高磁盘访问的性能，一般是通过优化磁盘的访问请求顺序来做到的；寻道时间是磁盘访问过程中最耗时的部分，如果将磁盘请求的顺序优化的得当的话就会节省出不必要的寻道时间，从而提高磁盘的访问性能；假设存在以下的请求序列，每一个数字代表的是磁道的位置：98，183，37，122，14，124，65，67，并假设当前读写磁头的位置位于第53磁道，以下将会展示使用不同的算法处理以上的序列会产生的效果：

先来先服务算法： 使用这个算法的话将会得到以下的磁盘访问顺序：

该算法一共移动了640个磁道的位置，是非常的简单粗暴的，在大量的进程竞争地使用磁盘并且访问磁盘的序列是很分散的，那么该算法最终的效果将会非常的差，因为寻道所需的时间过长；

最短寻道优先算法： 该算法会优先选择从当前磁头位置所需寻道时间最短的请求，那么对于以上的例子来说将会得到以下的访问序列：65，67，37，14，98，122，124，183

磁头总的移动距离是236个磁道，相比较于先来先服务算法来说性能提升了不少；但是该算法会导致某些请求的饥饿，以上的例子是静态的，但是在实际的情况中会是动态的，如果后续的请求都是小于183的话，那么183磁道永远都不会得到响应，于是就发生了饥饿的现象，产生饥饿的原因就是磁头在一小块的区域内来回的移动，而没有照顾到之外的数据；

扫描算法： 扫描算法就是规定磁头在一个方向上移动，访问所有的未完成的请求，直到磁头到达该方向上的最后一个磁道，才调转方向；该算法也被称作电梯算法，因为二者的思想是差不多的；还是以同样的序列作为例子：98，183，37，122，14，124，65，67，假设此时磁头的位置是第53磁道，那么如果扫描算法先朝着磁道号减少的方向移动的话，最终将会是以下的序列：37，14， 0 ，65，67，98，122，124，183：

磁头会首先达到最左端，才开始反向移动，响应右边的请求；扫描算法的效率是比较高的，但是中间部分的磁道被响应的频率明显更大，也就是说每一个磁道的响应频率会存在差异；

循环扫描算法： 扫描算法会使得磁道的响应频率不一致，循环扫描算法就是解决该问题的，它的思想就是只有在磁头朝着某一个特定的方向移动的时候才会处理磁道访问的请求，在返回的时候直接将磁头的位置快速的移动至最靠边缘的磁道，也就是直接复位磁头，该过程是很快的，在复位的过程中不会处理任何的请求，该算法的特点就是只会响应一个方向上的请求，还是以上的序列，假设磁头的位置是53号磁道，并假设磁头是朝着磁道号增加的方向移动的，那么最终得到的访问序列如下所示：65，67，98，122，124，183， 199 ， 0 ，14，37

当磁头到达最右端的磁道之后，直接将磁头的位置移动至磁盘的开始处，然后继续响应后续的请求；该算法会使得各个位置磁道的响应频率相对比较平均；

LOOK 与 C-LOOK 算法： 提到的两个扫描算法在移动到最开始的位置或者是最末尾的位置之后才会开始调转方向；这是可以优化的，LOOK 与 C-LOOK 算法就是分别优化扫描算法与循环扫描算法；使得磁头在移动到最远的请求的位置的时候就立即返回，而不是移动到磁盘的开始处或末尾处；