大厂面试题中爱问的「调度算法」(1)，java 后端技术栈图谱
FCFS 调度算法
顾名思义，先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
这似乎很公平，但是当一个长作业先运行了，那么后面的短作业等待的时间就会很长，不利于短作业。
FCFS 对长作业有利，适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。
最短作业优先调度算法
==============
最短作业优先(Shortest Job First, SJF)调度算法同样也是顾名思义，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。
SJF 调度算法
这显然对长作业不利，很容易造成一种极端现象。
比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。
高响应比优先调度算法
==============
前面的「先来先服务调度算法」和「最短作业优先调度算法」都没有很好的权衡短作业和长作业。
那么，高响应比优先 (Highest Response Ratio Next, HRRN)调度算法主要是权衡了短作业和长作业。
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：
从上面的公式，可以发现：
如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行;
如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会;
时间片轮转调度算法
=============
最古老、最简单、最公平且使用最广的算法就是时间片轮转(Round Robin, RR)调度算法。
RR 调度算法
每个进程被分配一个时间段，称为时间片(Quantum)，即允许该进程在该时间段中运行。
如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程;
如果该进程在时间的结束前阻塞或结束，则 CPU 立即进行切换;
另外，时间片的长度就是一个很关键的点：
如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率;
如果设得太长又可能引起对短作业进程的响应时间变长;
通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。
最高优先级调度算法
=============
前面的「时间的轮转算法」做了个假设，即让所有的进程同等重要，也不偏袒谁，大家的运行时间都一样。
但是，对于多用户计算机系统就有不同的看法了，它们希望调度是有优先级的，即希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级(Highest Priority First，HPF)调度算法。
进程的优先级可以分为，静态优先级或动态优先级：
静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化;
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间(就绪队列的等待时间)增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。
该算法也有两种处理优先级高的方法，非抢占式和抢占式：
非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
但是依然有缺点，可能会导致低优先级的进程永远不会运行。
多级反馈队列调度算法
==============
多级反馈队列(Multilevel Feedback Queue)调度算法是「时间的轮转算法」和「最高优先级算法」的综合和发展。
顾名思义：
「多级」表示有多个队列，每个队列优先级从高到低，同时优先级越高时间片越短。
「反馈」表示如果有新的进程加入优先级高的队列时，立刻停止当前正在运行的进程，转而去运行优先级高的队列;
多级反馈队列
来看看，它是如何工作的：
设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短;
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间还没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成;
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行;
可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。
内存页面置换算法
============
在了解内存页面置换算法前，我们得先谈一下缺页异常(缺页中断)。
当 CPU 访问的页面不在物理内存时，便会产生一个缺页中断，请求操作系统将所缺页调入到物理内存。那它与一般中断的主要区别在于：
缺页中断在指令执行「期间」产生和处理中断信号，而一般中断在一条指令执行「完成」后检查和处理中断信号。
缺页中断返回到该指令的开始重新执行「该指令」，而一般中断返回回到该指令的「下一个指令」执行。
我们来看一下缺页中断的处理流程，如下图：
缺页中断的处理流程
在 CPU 里访问一条 Load M 指令，然后 CPU 回去找 M 所对应的页表项。
如果该页表项的状态位是「有效的」，那 CPU 就可以直接去访问物理内存了，如果状态位是「无效的」，则 CPU 则会发送缺页中断请求。
操作系统收到了缺页中断，则会执行缺页中断处理函数，先会查找该页面在磁盘中的页面的位置。
找到磁盘中对应的页面后，需要把该页面换入到物理内存中，但是在换入前，需要在物理内存中找空闲页，如果找到空闲页，就把页面换入到物理内存中。
页面从磁盘换入到物理内存完成后，则把页表项中的状态位修改为「有效的」。
最后，CPU 重新执行导致缺页异常的指令。
上面所说的过程，第 4 不是能在物理内存找到空闲页的情况，那如果找不到呢?
找不到空闲页的话，就说明此时内存已满了，这时候，就需要「页面置换算法」选择一个物理页，如果该物理页有被修改过(脏页)，则把它换出到磁盘，然后把该被置换出去的页表项的状态改成「无效的」，最后把正在访问的页面装入到这个物理页中。
这里提一下，页表项通常有如下图的字段：
那其中：
状态位：用于表示该页是否有效，也就是说是否在物理内存中，供程序访问时参考。
访问字段：用于记录该页在一段时间被访问的次数，供页面置换算法选择出页面时参考。
修改位：表示该页在调入内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统的开销;如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终是最新的副本。
硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。
这里我整理了虚拟内存的管理整个流程，你可以从下面这张图看到：
虚拟内存的流程
所以，页面置换算法的功能是，当出现缺页异常，需调入新页面而内存已满时，选择被置换的物理页面，也就是说选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。
那其算法目标则是，尽可能减少页面的换入换出的次数，常见的页面置换算法有如下几种：
最佳页面置换算法(OPT)
先进先出置换算法(FIFO)
最近最久未使用的置换算法(LRU)
时钟页面置换算法(Lock)
最不常用置换算法(LFU)
最佳页面置换算法
最佳页面置换算法
============
基本思路是，置换在「未来」最长时间不访问的页面。
所以，该算法实现需要计算内存中每个逻辑页面的「下一次」访问时间，然后比较，选择未来最长时间不访问的页面。
我们举个例子，假设一开始有 3 个空闲的物理页，然后有请求的页面序列，那它的置换过程如下图：
最佳页面置换算法
在这个请求的页面序列中，缺页共发生了 7 次(空闲页换入 3 次 + 最优页面置换 4 次)，页面置换共发生了 4 次。
这很理想，但是实际系统中无法实现，因为程序访问页面时是动态的，我们是无法预知每个页面在「下一次」访问前的等待时间。
所以，最佳页面置换算法作用是为了衡量你的算法的效率，你的算法效率越接近该算法的效率，那么说明你的算法是高效的。
先进先出置换算法
既然我们无法预知页面在下一次访问前所需的等待时间，那我们可以选择在内存驻留时间很长的页面进行中置换，这个就是「先进先出置换」算法的思想。
还是以前面的请求的页面序列作为例子，假设使用先进先出置换算法，则过程如下图：
先进先出置换算法
在这个请求的页面序列中，缺页共发生了 10 次，页面置换共发生了 7 次，跟最佳页面置换算法比较起来，性能明显差了很多。
最近最久未使用的置换算法
================
最近最久未使用(LRU)的置换算法的基本思路是，发生缺页时，选择最长时间没有被访问的页面进行置换，也就是说，该算法假设已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。
这种算法近似最优置换算法，最优置换算法是通过「未来」的使用情况来推测要淘汰的页面，而 LRU 则是通过「历史」的使用情况来推测要淘汰的页面。
还是以前面的请求的页面序列作为例子，假设使用最近最久未使用的置换算法，则过程如下图：
最近最久未使用的置换算法
在这个请求的页面序列中，缺页共发生了 9 次，页面置换共发生了 6 次，跟先进先出置换算法比较起来，性能提高了一些。
虽然 LRU 在理论上是可以实现的，但代价很高。为了完全实现 LRU，需要在内存中维护一个所有页面的链表，最近最多使用的页面在表头，最近最少使用的页面在表尾。
困难的是，在每次访问内存时都必须要更新「整个链表」。在链表中找到一个页面，删除它，然后把它移动到表头是一个非常费时的操作。
所以，LRU 虽然看上去不错，但是由于开销比较大，实际应用中比较少使用。
时钟页面置换算法
============
那有没有一种即能优化置换的次数，也能方便实现的算法呢?
时钟页面置换算法就可以两者兼得，它跟 LRU 近似，又是对 FIFO 的一种改进。
该算法的思路是，把所有的页面都保存在一个类似钟面的「环形链表」中，一个表针指向最老的页面。
当发生缺页中断时，算法首先检查表针指向的页面：
如果它的访问位位是 0 就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置;
如果访问位是 1 就清除访问位，并把表针前移一个位置，重复这个过程直到找到了一个访问位为 0 的页面为止;
我画了一副时钟页面置换算法的工作流程图，你可以在下方看到：
时钟页面置换算法
了解了这个算法的工作方式，就明白为什么它被称为时钟(Clock)算法了。
最不常用算法
==========
最不常用(LFU)算法，这名字听起来很调皮，但是它的意思不是指这个算法不常用，而是当发生缺页中断时，选择「访问次数」最少的那个页面，并将其淘汰。
它的实现方式是，对每个页面设置一个「访问计数器」，每当一个页面被访问时，该页面的访问计数器就累加 1。在发生缺页中断时，淘汰计数器值最小的那个页面。
看起来很简单，每个页面加一个计数器就可以实现了，但是
在操作系统中实现的时候，我们需要考虑效率和硬件成本的。
要增加一个计数器来实现，这个硬件成本是比较高的，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很大，是非常耗时的，效率不高。
但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，比如有些页面在过去时间里访问的频率很高，但是现在已经没有访问了，而当前频繁访问的页面由于没有这些页面访问的次数高，在发生缺页中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不高的页面。
那这个问题的解决的办法还是有的，可以定期减少访问的次数，比如当发生时间中断时，把过去时间访问的页面的访问次数除以 2，也就说，随着时间的流失，以前的高访问次数的页面会慢慢减少，相当于加大了被置换的概率。
磁盘调度算法
==========
我们来看看磁盘的结构，如下图：
磁盘的结构
常见的机械磁盘是上图左边的样子，中间圆的部分是磁盘的盘片，一般会有多个盘片，每个盘面都有自己的磁头。右边的图就是一个盘片的结构，盘片中的每一层分为多个磁道，每个磁道分多个扇区，每个扇区是 512 字节。那么，多个具有相同编号的磁道形成一个圆柱，称之为磁盘的柱面，如上图里中间的样子。
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论