4、调度算法
点击阅读更多查看文章内容
进程调度算法
进程调度算法也称 CPU 调度算法，毕竟进程是由 CPU 调度的。 当 CPU 空闲时，操作系统就选择内存中的某个「就绪状态」的进程，并给其分配 CPU。 什么时候会发生 CPU 调度呢？通常有以下情况：
- 当进程从运行状态转到等待状态；
- 当进程从运行状态转到就绪状态；
- 当进程从等待状态转到就绪状态；
- 当进程从运行状态转到终止状态；
其中发生在 1 和 4 两种情况下的调度称为「非抢占式调度」，2 和 3 两种情况下发生的调度称为「抢占式调度」。
- 非抢占式的意思就是，当进程正在运行时，它就会一直运行，直到该进程完成或发生某个事件而被阻塞时，才会把 CPU 让给其他进程。
- 而抢占式调度，顾名思义就是进程正在运行时，可以被打断，使其把 CPU 让给其他进程。
那抢占的原则一般有三种，分别是时间片原则、优先权原则、短作业优先原则。 你可能会好奇为什么第 3 种情况也会发生 CPU 调度呢？假设有一个进程是处于等待状态的，但是它的优先级比较高，如果该进程等待的事件发生了，它就会转到就绪状态，一旦它转到就绪状态，如果我们的调度算法是以优先级来进行调度的，那么它就会立马抢占正在运行的进程，所以这个时候就会发生 CPU 调度。 那第 2 种状态通常是时间片到的情况，因为时间片到了就会发生中断，于是就会抢占正在运行的进程，从而占用 CPU。 调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真在使用 CPU 的时间和 I/O 时间。
- 先来先服务调度算法
- 最短作业优先调度算法
- 高响应比优先调度算法
- 时间片轮转调度算法
- 最高优先级调度算法
- 多级反馈队列调度算法
内存页面置换算法
在了解内存页面置换算法前，我们得先谈一下缺页异常（缺页中断）。 当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：
- 缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号。
- 缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。
我们来看一下缺页中断的处理流程，如下图：
页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。
那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：
最佳页面置换算法（OPT） ：置换在「未来」最长时间不访问的页面。实际系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间。 所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的
先进先出置换算法（FIFO） ：选择在内存驻留时间很长的页面进行中置换
最近最久未使用的置换算法（LRU） ：选择最长时间没有被访问的页面进行置换，虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。 困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。
时钟页面置换算法（Lock） ：把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。 当发生缺页中断时，算法首先检查表针指向的页面： 如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置； 如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止；
最不常用置换算法（LFU）：当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。它的实现方式是，对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。
磁盘调度算法
常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。
磁盘调度算法的目的很简单，就是为了提高磁盘的访问性能，一般是通过优化磁盘的访问请求顺序来做到的。 寻道的时间是磁盘访问最耗时的部分，如果请求顺序优化的得当，必然可以节省一些不必要的寻道时间，从而提高磁盘的访问性能。 假设有下面一个请求序列，每个数字代表磁道的位置： 98，183，37，122，14，124，65，67 初始磁头当前的位置是在第 53 磁道。 接下来，分别对以上的序列，作为每个调度算法的例子，那常见的磁盘调度算法有：
先来先服务算法
最短寻道时间优先算法：优先选择从当前磁头位置所需寻道时间最短的请求
扫描算法 ：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上的最后的磁道，才调换方向，这就是扫描（Scan）算法。中间部分的磁道会比较占便宜，中间部分相比其他部分响应的频率会比较多，也就是说每个磁道的响应频率存在差异。
循环扫描算法：循环扫描（Circular Scan, CSCAN ）规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接快速移动至最靠边缘的磁道，也就是复位磁头，这个过程是很快的，并且返回中途不处理任何请求，该算法的特点，就是磁道只响应一个方向上的请求。
LOOK 与 C-LOOK 算法：我们前面说到的扫描算法和循环扫描算法，都是磁头移动到磁盘「最始端或最末端」才开始调换方向。 那这其实是可以优化的，优化的思路就是磁头在移动到「最远的请求」位置，然后立即反向移动。
LOOK：针对 SCAN 算法的优化，磁头在移动到「最远的请求」位置，然后立即反向移动
C-LOOK：针 C-SCAN 算法的优化则叫 C-LOOK，它的工作方式，磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。
