本文转载自微信公众号《小林编码》，作者小林编码。转载本文请联系小林编码公众号。原文地址：https://mp.weixin.qq.com/s/JWj6_BF9Xc84kQcyx6Nf_g前言最近一直在各大技术群偷偷潜伏，因为秋招快到了，看了很多大厂面试分享由我的朋友。然后发现操作系统的知识点考的还是很多，大厂就是喜欢问基础知识的大厂。其中，对操作系统“调度算法”的考察也比较频繁。因此，我总结了操作系统的三大调度机制，分别是“进程调度/页面替换/磁盘调度算法”，供大家回顾。希望你能在秋招中拿到属于自己的offer。字面上的进程调度算法进程调度算法也叫CPU调度算法，毕竟进程是由CPU调度的。当CPU空闲时，操作系统会在内存中选择一个处于“就绪状态”的进程，将CPU分配给它。什么时候会发生CPU调度？通常有以下几种情况：当进程从运行状态变为等待状态时；当进程从运行状态变为就绪状态时；当进程从等待状态变为就绪状态时；终止状态；发生在1和4两种情况下的调度称为“非抢占式调度”，发生在2和3两种情况下的调度称为“抢占式调度”。非抢占是指当一个进程在运行时，它会一直运行，直到该进程执行完毕或者有事件发生而被阻塞，不会把CPU让给其他进程。而抢占式调度，顾名思义，就是当一个进程正在运行的时候，可以中断它，让它把CPU让给其他进程。抢占一般有3个原则，即时间片原则、优先级原则、短作业优先原则。你可能会疑惑为什么CPU调度也会出现在第三种情况？假设一个进程处于等待状态，但是它的优先级比较高。如果进程正在等待的事件发生，它就会进入就绪状态，一旦进入就绪状态，如果我们的调度算法是按优先级调度的，那么它会立即抢占正在运行的进程，所以会发生CPU调度此时。第二种状态一般是时间片up的时候，因为时间片up的时候会发生中断，所以会抢占正在运行的进程，占用cpu。调度算法影响等待时间（进程在就绪队列中等待调度的时间总和），但不能影响进程实际使用CPU和I/O时间的时间。下面说一下常见的调度算法：先来先服务调度算法最短作业优先级调度算法高响应比优先级调度算法时间片轮询调度算法最高优先级调度算法多级反馈队列调度算法first-先来先服务调度算法最简单的一种调度算法是非抢占式先来先服务（FirstComeFirstSeverd，FCFS）算法。顾名思义，FCFS调度算法是先到先得。每次从就绪队列中选择最先进入队列的进程，然后运行，直到进程退出或阻塞，再继续从队列中选择第一个进程运行。这看起来很公平，但是当一个longjob先运行时，后面的shortjob的等待时间会很长，不利于shortjobs。FCFS适用于长时间作业，适用于CPU密集型作业而非I/O密集型作业的系统。最短作业优先调度算法最短作业优先（SJF）调度算法也顾名思义，会优先让运行时间最短的进程运行，有助于提高系统的吞吐量。SJF调度算法显然不适合长作业，容易造成极端现象。例如，如果一个长作业在就绪队列中等待运行，而就绪队列中有很多短作业，则长作业会不断被推回，周转时间会变长，这样长作业就会不能长时间运行。高响应比优先级调度算法前面的“先来先服务调度算法”和“最短作业优先调度算法”并没有很好地平衡短作业和长作业。然后，HighestResponseRatioNext(HRRN)调度算法主要权衡短作业和长作业。每次调度进程时，先计算“响应比优先级”，然后将“响应比优先级”最高的进程投入运行。“响应率优先级”的计算公式：从上面的公式可以发现：当两个进程的“等待时间”相同时，“需要服务时间”越短，“响应率”越高，使得作业短的进程容易被选中运行；如果两个进程的“所需服务时间”相同，则“等待时间”越长，“响应率”越高，这考虑到了长作业进程，因为进程的响应率可以随着等待时间的增加。当等待时间足够长时，响应率可以为在RR调度算法中，给每个进程分配一个时间段，称为时间片（Quantum），让进程在这个时间段内运行。如果时间片用完，进程还在运行，则释放该进程的CPU，将CPU分配给另一个进程；如果进程在时间片结束前被阻塞或终止，CPU会立即切换；另外，时间片的长度是一个重点：如果时间片设置得太短，会导致进程上下文切换过多，降低CPU效率；如果设置得太长，可能会导致短作业流程的响应时间变长；通常，将时间片设置为20ms~50ms通常是一个合理的折衷值。最高优先级调度算法前面的“时间片轮转算法”，假设所有进程都同等重要，谁也不偏袒谁，每个人的运行时间都是一样的。但是，对于多用户计算机系统有不同的看法。他们希望调度是有优先级的，即希望调度器能从就绪队列中选择优先级最高的进程运行，这称为最高优先级（HighestPriorityFirst，HPF）调度算法。进程的优先级可以分为静态优先级和动态优先级：静态优先级：当进程被创建时，优先级就已经确定了，之后在整个运行时间内，优先级不会改变；动态优先级：根据进程动态改变和调整优先级，比如进程运行时间增加，它的优先级就会降低，如果进程等待时间（就绪队列的等待时间）增加，它的优先级就会增加，即等待进程的优先级会随时间增加。该算法还有两种处理高优先级的方法，非抢占式和抢占式：非抢占式：当一个高优先级进程出现在就绪队列中时，当前进程结束运行，然后选择高优先级进程.抢占式：当就绪队列中出现高优先级进程时，挂起当前进程，调度高优先级进程运行。但是还是有缺点，可能会导致低优先级的进程永远运行不起来。多级反馈队列调度算法多级反馈队列（MultilevelFeedbackQueue）调度算法是“时间片循环算法”和“最高优先级算法”的综合和发展。顾名思义：“多级”就是有多个队列，每个队列都有一个从高到低的优先级，优先级越高，时间片越短。“反馈”是指如果有新进程加入高优先级队列，立即停止当前运行的进程，切换到高优先级队列；让我们来看看多级反馈队列，看看它是如何工作的：设置有多个队列，每个队列被赋予不同的优先级。每个队列的优先级从高到低。同时，优先级越高，时间片越短；新进程会被放在一级队列的末尾，按先来先服务的原则排队等待调度。如果一级队列规定的时间片没有完成，则转移到二级队列的尾部，以此类推，直到完成；当优先级较高的队列为空时，调度优先级较低的队列中的进程运行。如果在进程运行的过程中有新的进程进入了更高优先级的队列，则停止当前正在运行的进程并将其移至原队列的尾部，然后让更高优先级的进程运行；可以发现，对于短作业，有可能第一级队列被快速处理。对于长作业，如果一级队列无法处理，可以移到下一级队列等待执行。虽然等待时间变长，但运行时间也会变长，所以该算法同时考虑了长作业和短作业，并有更好的响应时间。内存页面置换算法在了解内存页面置换算法之前，我们不得不先说一下缺页异常（pagefaultinterrupts）。当CPU访问的页面不在物理内存中时，就会产生缺页中断，请求操作系统将丢失的页面加载到物理内存中。它与一般中断的主要区别在于缺页中断在指令执行“期间”产生并处理中断信号，而一般中断在指令“完成”后检查并处理中断信号。缺页中断返回到指令的开头重新执行“本条指令”，而普通中断则返回到指令的“下一条指令”处执行。我们先看一下缺页中断的处理流程，如下图所示：缺页中断的处理流程是在CPU中访问一条LoadM指令，然后CPU会找到对应的页表项M、如果页表项的状态位为“有效”，则CPU可以直接访问物理内存。如果状态位为“无效”，CPU将发送缺页中断请求。当操作系统收到缺页中断时，会执行缺页中断处理函数，首先找到该页在磁盘中的页位置。在磁盘中找到对应的页后，需要将该页交换到物理内存中，但是在交换之前，需要在物理内存中找到一个空闲页，如果找到空闲页，则将该页交换到物理内存中物理内存。页从磁盘交换到物理内存后，页表项中的状态位变为“有效”。最后，CPU重新执行导致页面错误的指令。在上面提到的过程中，第四步是在物理内存中找到一个空闲页面。如果找不到怎么办？如果没有找到空闲页，说明此时内存已满。这时候就需要通过“页面替换算法”选择一个物理页，如果物理页被修改过（脏页），则将其换出到磁盘，然后页表项的状态被替换将变为“无效”，最后将被访问的页面加载到这个物理页面中。这里提一下，页表项通常有如下图所示的字段：其中：状态位：用来表示页是否有效，即是否在物理内存中，供程序访问时参考。访问字段：用于记录一段时间内该页面被访问的次数，供页面替换算法选择页面时参考。修改位：表示页面加载到内存后是否被修改过。由于内存中的每个页面都在磁盘上保留了一份副本，如果没有被修改过，就没有必要将替换的页面写回磁盘，减少系统开销；如果修改过，则将页面重写到磁盘，保证磁盘上始终保留最新的副本。硬盘地址：用来指出页面在硬盘上的地址，通常是物理块号，供加载页面时使用。这里我梳理了虚拟内存管理的整个过程，大家可以从下图看出：transferred且内存已满，选择要替换的物理页，也就是选择一个物理页换出到磁盘，然后将需要访问的页换入该物理页。该算法的目标是尽可能减少页面换入和换出的数量。常见的页面置换算法如下：最优页面置换算法（OPT）先进先出置换算法（FIFO）最近未使用置换算法（LRU）时钟页面置换算法（Lock）最不常用置换算法（LFU）最佳页面替换算法最佳页面替换算法的基本思想是替换“未来”最长时间内不会被访问的页面。因此，算法的实现需要计算内存中每个逻辑页的“下一次”访问时间，然后将它们进行比较，选出未来最长时间不会被访问的页。举个例子，假设一开始有3个空闲物理页，然后有一个请求的页序列，那么它的替换过程如下：最优页替换算法在这个请求的页序列中，共有7页故障发生次数（免费页面更换3次+最佳页面更换4次），页面更换共发生4次。这是理想的，但在实际系统中无法实现，因为程序是动态访问页面的，我们无法预知每个页面在“下一次”访问之前的等待时间。所以，最优页面置换算法的作用就是衡量你算法的效率。你的算法效率越接近算法的效率，你的算法就越高效。先进先出替换算法由于我们无法预知下一次访问前页面等待的时间，我们可以选择替换内存停留时间长的页面。这就是“先进先出替换”算法的思想。仍然以前面请求的页面序列为例，假设采用先进先出的替换算法，其过程如下：先进先出替换算法在本次请求的页面序列中，一共有发生了10次页面错误，总共发生了7次页面替换，与最好的页面替换算法相比，性能明显差了很多。最近未使用的替换算法最近最少使用（LRU）替换算法的基本思想是，当发生页面错误时，选择最长时间未被访问的页面进行替换，也就是说，该算法假定它已经很长时间没有被使用过的页面很可能在未来很长一段时间内保持未被使用。该算法类似于最优替换算法。最优替换算法使用“未来”用法来推断要淘汰的页面，而LRU使用“历史”用法来推断要淘汰的页面。仍然以上次请求的页序为例，假设使用最近一次未使用的替换算法，流程如下图所示：未使用过的替换算法最近一次请求的页面序列中一共有9次页面错误，页面一共发生了6次排列。与先进先出排列算法相比，性能有所提高。虽然LRU在理论上是可行的，但它很昂贵。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近使用的页面在链表的头部，最近最少使用的页面在链表的尾部。困难在于每次访问内存时都必须更新“整个链表”。在链表中查找一个页面，将其删除，并移到头部是一个非常耗时的操作。因此，LRU虽然看起来不错，但由于开销比较大，在实际应用中很少使用。时钟页面置换算法有没有一种算法可以优化置换次数，便于实现？时钟页面替换算法可以做到这两点。它类似于LRU，是对FIFO的改进。算法的思想是将所有页面保存在一个类似于钟面的“环形链表”中，一个指针指向最旧的页面。当出现页错误时，算法首先检查指针指向的页：如果其访问位为0，则淘汰该页，并在该位置插入新的页，然后指针向前移动一个位置；如果accessbit为1就清除accessbit，并将指针向前移动一个位置，重复这个过程，直到找到accessbit为0的页；我画了一个时钟页面替换算法的工作流程图，你可以在下面看到它：LeastFrequentlyUsedAlgorithmLeastFrequentlyUsed(LFU)算法，名字听着调皮，但并不是说这个算法不常用，而是说当出现页面错误时，选择访问次数最少的页面，敲出来。它是通过为每个页面设置一个“访问计数器”来实现的，每访问一个页面，该页面的访问计数器就加1。当发生页面错误时，淘汰计数器值最小的页面。看似很简单，在每个页面加一个计数器就可以实现，但是在操作系统中实现时，需要考虑效率和硬件成本。要加一个计数器来实现，硬件成本比较高。另外，如果要找这个计数器访问次数最少的是哪个页面，就找链表本身。如果链表很长，非常耗时且效率低下。但是还有一个问题。LFU算法只考虑了频率问题，没有考虑时间问题。比如有些页面过去经常被访问过，现在不再访问了，当前经常访问的页面没有这些页面。访问量高，发生页面错误时，可能不小心损坏了刚开始被频繁访问的页面，但访问量不高。那么这个问题还是有解决办法的。您可以定期减少访问次数。例如，当出现时间中断时，将过去访问过的页面的访问量除以2。也就是说，随着时间的推移，之前访问量高的页面会逐渐减少，相当于以增加被替换的可能性。磁盘调度算法先看一下磁盘的结构，如下图所示：磁盘的结构常见的机械磁盘如上图左侧所示。中间的圆圈是圆盘的圆盘。一般有多个磁盘。自带磁头。右图是磁盘的结构。磁盘中的每一层分为多个磁道，每个磁道又分为多个扇区，每个扇区为512字节。然后，多个编号相同的磁道组成一个柱面，称为磁盘的柱面，如上图中间所示。磁盘调度算法的目的很简单，就是提高磁盘访问性能，一般通过优化磁盘访问请求的顺序来实现。寻道时间是磁盘访问中最耗时的部分。如果适当优化请求顺序，可以节省不必要的寻道时间，从而提高磁盘访问性能。假设有如下请求序列，每个数字代表磁道的位置：98,183,37,122,14,124,65,67初始磁头的当前位置是第53个磁道。下面分别针对上面的序列，作为各个调度算法的例子，常见的磁盘调度算法有：先来先服务算法最短寻道时间优先算法扫描算法循环扫描算法LOOK和C-LOOK算法first-comeFirst-Come,First-Served,FCFS（先来先服务，FCFS），顾名思义，先来的请求先服务。按照这个顺序：98、183、37、122、14、124、65、67，那么，磁盘的写入顺序就是从左到右，如下图：先来先服务算法已经移动一共640个如果看这个算法，比较简单粗暴，但是如果大量进程竞争使用磁盘，请求访问的磁道可能会比较分散，先到先得的表现-serve算法会很差，因为寻道者寻求使用磁盘。路途时间太长。Theshortestseektimefirst最短寻道时间优先（ShortestSeekFirst，SSF）算法的工作原理是从当前磁头位置优先选择寻道时间最短的请求，或者以这个序列为例：98,183,37,122,14,124,65,67那么根据最靠近磁头（位置53）的request的算法，具体的request会从左到右依次为：65,67,37,14,98,122,124,183最短寻道时间优先磁头移动的总距离为236磁道，相比先来先服务的性能有很大提高。但是这个算法可能会饿死一些请求，因为在这个例子中我们是一个静态序列，我们看不出问题，假设是一个动态请求，如果后续请求少于183个tracks，那么183个tracks可能会持续forever不会被响应，所以发生饥饿。这里饥饿的原因是磁头在一个小区域内来回移动。扫描算法最短寻道时间优先算法之所以会造成饥饿，是因为磁头可能会在小范围内来回移动。为了防止这个问题，可以规定磁头朝一个方向移动，访问所有未完成的请求，直到磁头到达该方向的最后一个磁道后才改变方向。这就是扫描算法。这个算法也叫电梯算法，比如电梯一直往一个方向移动，直到那个方向没有请求，然后改变方向。仍以此序列为例，磁头的初始位置为53：98、183、37、122、14、124、65、67。那么，假设扫描时间表先向磁道数递减的方向移动，具体请求如下顺序从左到右：37、14、0、65、67、98、122、124、183扫描算法磁头先响应左边的请求，不开始向相反方向移动，直到到达最左端（轨道0）。正确的要求。scan调度算法性能较好，不会造成饥饿，但是存在这样一个问题，中间部分的tracks会比较便宜，中间部分的响应频率会比其他部分多，即也就是说，每个轨道的响应频率都有差异。循环扫描算法扫描算法使得每个轨道的响应频率不同，所以要优化这个问题，可以一直往同一个方向扫描，这样每个轨道的响应频率基本一致。循环扫描（CSCAN）规定只有当磁头向特定方向移动时，才处理磁道访问请求，返回时直接移动到最边缘磁道，即重置磁头。这个过程非常快，并且在返回期间不处理任何请求。该算法的特点是轨道只响应一个方向的请求。仍然以这个序列为例，磁头的初始位置为53：98、183、37、122、14、124、65、67。那么，假设循环扫描调度向增加磁道的方向移动首先，具体请求如下：顺序从左到右：65、67、98、122、124、183、199、0、14、37循环扫描算法磁头先响应右边的请求，直到碰到最右边的track199，然后立即返回到磁盘上的track开始处（track0），但是在返回的途中，不响应任何请求，直到到达第一个track，才继续响应on上的请求正确的顺序。与扫描算法相比，圆形扫描算法具有相对平均的每个位置的轨迹响应频率。LOOK和C-LOOK算法前面我们提到的扫描算法和循环扫描算法都是在磁头移动到磁盘的“首端或末尾”时开始改变方向的。那么这个其实是可以优化的。优化的思路是，头部正在移动到“最远请求”的位置，然后立即向相反的方向移动。SCAN算法的优化称为LOOK算法。它的工作方式是，磁头仅在每个方向上移动到请求的最远位置，然后立即向相反方向移动，而不会移动到磁盘的最开头或结尾。在反向移动时响应请求。LOOK算法和C-SCAN算法的优化称为C-LOOK。它的工作方式是磁头在每个方向上只移动到最远的请求位置，然后立即向相反的方向移动，而不移动到磁盘的最远位置。在开始或结束时，反向移动时请求不会被响应。C-LOOK算法
