然后发现，操作系统的知识点考察还是比较多的，大厂就是大厂就爱问基础知识。其中，关于操作系统的「调度算法」考察也算比较频繁。
所以，我这边总结了操作系统的三大调度机制，分别是「进程调度/页面置换/磁盘调度算法」，供大家复习，希望大家在秋招能斩获自己心意的offer。
进程调度算法
进程调度算法也称CPU调度算法，毕竟进程是由CPU调度的。
当CPU空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配CPU。
什么时候会发生CPU调度呢？通常有以下情况：
其中发生在1和4两种情况下的调度称为「非抢占式调度」，2和3两种情况下发生的调度称为「抢占式调度」。
非抢占式的意思就是，当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把CPU让给其他进程。
你可能会好奇为什么第3种情况也会发生CPU调度呢？假设有一个进程是处于等待状态的，但是它的优先级比较高，如果该进程等待的事件发生了，它就会转到就绪状态。
一旦它转到就绪状态，如果我们的调度算法是以优先级来进行调度的，那么它就会立马抢占正在运行的进程，所以这个时候就会发生CPU调度。
接下来，说说常见的调度算法：
先来先服务调度算法
最简单的一个调度算法，就是非抢占式的先来先服务（FirstComeFirstSeverd,FCFS）算法了。
FCFS调度算法
顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
FCFS对长作业有利，适用于CPU繁忙型作业的系统，而不适用于I/O繁忙型作业的系统。
最短作业优先调度算法
SJF调度算法
这显然对长作业不利，很容易造成一种极端现象。
高响应比优先调度算法
前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。
那么，高响应比优先（HighestResponseRatioNext,HRRN）调度算法主要是权衡了短作业和长作业。
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：
从上面的公式，可以发现：
RR调度算法
最高优先级调度算法
但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（HighestPriorityFirst，HPF）调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
但是依然有缺点，可能会导致低优先级的进程永远不会运行。
多级反馈队列调度算法
顾名思义：
多级反馈队列
来看看，它是如何工作的：
内存页面置换算法
在了解内存页面置换算法前，我们得先谈一下缺页异常（缺页中断）。
当CPU访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：
我们来看一下缺页中断的处理流程，如下图：
缺页中断的处理流程
上面所说的过程，第4步是能在物理内存找到空闲页的情况，那如果找不到呢？
找不到空闲页的话，就说明此时内存已满了，这时候，就需要「页面置换算法」选择一个物理页，如果该物理页有被修改过（脏页），则把它换出到磁盘，然后把该被置换出去的页表项的状态改成「无效的」，最后把正在访问的页面装入到这个物理页中。
这里提一下，页表项通常有如下图的字段：
那其中：
这里我整理了虚拟内存的管理整个流程，你可以从下面这张图看到：
虚拟内存的流程
所以，页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。
那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：
最佳页面置换算法
我们举个例子，假设一开始有3个空闲的物理页，然后有请求的页面序列，那它的置换过程如下图：
在这个请求的页面序列中，缺页共发生了7次（空闲页换入3次+最优页面置换4次），页面置换共发生了4次。
所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。
先进先出置换算法
还是以前面的请求的页面序列作为例子，假设使用先进先出置换算法，则过程如下图：
在这个请求的页面序列中，缺页共发生了10次，页面置换共发生了7次，跟最佳页面置换算法比较起来，性能明显差了很多。
最近最久未使用的置换算法
这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而LRU则是通过「历史」的使用情况来推测要淘汰的页面。
还是以前面的请求的页面序列作为例子，假设使用最近最久未使用的置换算法，则过程如下图：
在这个请求的页面序列中，缺页共发生了9次，页面置换共发生了6次，跟先进先出置换算法比较起来，性能提高了一些。
虽然LRU在理论上是可以实现的，但代价很高。为了完全实现LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。
困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。
所以，LRU虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。
时钟页面置换算法
那有没有一种即能优化置换的次数，也能方便实现的算法呢？
时钟页面置换算法就可以两者兼得，它跟LRU近似，又是对FIFO的一种改进。
该算法的思路是，把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面：
我画了一副时钟页面置换算法的工作流程图，你可以在下方看到：
了解了这个算法的工作方式，就明白为什么它被称为时钟（Clock）算法了。
最不常用算法
最不常用（LFU）算法，这名字听起来很调皮，但是它的意思不是指这个算法不常用，而是当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。
它的实现方式是，对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加1。在发生缺页中断时，淘汰计数器值最小的那个页面。
看起来很简单，每个页面加一个计数器就可以实现了，但是在操作系统中实现的时候，我们需要考虑效率和硬件成本的。
要增加一个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。
磁盘调度算法
我们来看看磁盘的结构，如下图：
磁盘的结构
常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是512字节。
那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。
磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。
假设有下面一个请求序列，每个数字代表磁道的位置：
98，183，37，122，14，124，65，67
初始磁头当前的位置是在第53磁道。
接下来，分别对以上的序列，作为每个调度算法的例子，那常见的磁盘调度算法有：
先来先服务
先来先服务（First-Come，First-Served，FCFS），顾名思义，先到来的请求，先被服务。
那按照这个序列的话：
那么，磁盘的写入顺序是从左到右，如下图：
那么，那么根据距离磁头（53位置）最近的请求的算法，具体的请求则会是下列从左到右的顺序：
65，67，37，14，98，122，124，183
磁头移动的总距离是236磁道，相比先来先服务性能提高了不少。
但这个算法可能存在某些请求的饥饿，因为本次例子我们是静态的序列，看不出问题，假设是一个动态的请求，如果后续来的请求都是小于183磁道的，那么183磁道可能永远不会被响应，于是就产生了饥饿现象，这里产生饥饿的原因是磁头在一小块区域来回移动。
扫描算法
为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。
这种算法也叫做电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向。
还是以这个序列为例子，磁头的初始位置是53：
那么，假设扫描调度先朝磁道号减少的方向移动，具体请求则会是下列从左到右的顺序：
37，14，0，65，67，98，122，124，183
磁头先响应左边的请求，直到到达最左端（0磁道）后，才开始反向移动，响应右边的请求。
扫描调度算法性能较好，不会产生饥饿现象，但是存在这样的问题，中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。
循环扫描算法
扫描算法使得每个磁道响应的频率存在差异，那么要优化这个问题的话，可以总是按相同的方向进行扫描，使得每个磁道的响应频率基本一致。
循环扫描（CircularScan,CSCAN）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
那么，假设循环扫描调度算先朝磁道增加的方向移动，具体请求会是下列从左到右的顺序：
65，67，98，122，124，183，199，0，14，37
磁头先响应了右边的请求，直到碰到了最右端的磁道199，就立即回到磁盘的开始处（磁道0），但这个返回的途中是不响应任何请求的，直到到达最开始的磁道后，才继续顺序响应右边的请求。
循环扫描算法相比于扫描算法，对于各个位置磁道响应频率相对比较平均。
LOOK与C-LOOK算法
我们前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。
那这其实是可以优化的，优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动。
那针对SCAN算法的优化则叫LOOK算法，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。
LOOK算法
而针C-SCAN算法的优化则叫C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。