其他
大厂面试爱问的「调度算法」,20 张图一举拿下
The following article is from 小林coding Author 小林coding
进程调度算法
当进程从运行状态转到等待状态; 当进程从运行状态转到就绪状态; 当进程从等待状态转到就绪状态; 当进程从运行状态转到终止状态;
先来先服务调度算法 最短作业优先调度算法 高响应比优先调度算法 时间片轮转调度算法 最高优先级调度算法 多级反馈队列调度算法
先来先服务调度算法
最短作业优先调度算法
高响应比优先调度算法
如果两个进程的「等待时间」相同时,「要求的服务时间」越短,「响应比」就越高,这样短作业的进程容易被选中运行; 如果两个进程「要求的服务时间」相同时,「等待时间」越长,「响应比」就越高,这就兼顾到了长作业进程,因为进程的响应比可以随时间等待的增加而提高,当其等待时间足够长时,其响应比便可以升到很高,从而获得运行的机会;
时间片轮转调度算法
如果时间片用完,进程还在运行,那么将会把此进程从 CPU 释放出来,并把 CPU 分配另外一个进程; 如果该进程在时间片结束前阻塞或结束,则 CPU 立即进行切换;
如果时间片设得太短会导致过多的进程上下文切换,降低了 CPU 效率; 如果设得太长又可能引起对短作业进程的响应时间变长;
最高优先级调度算法
静态优先级:创建进程时候,就已经确定了优先级了,然后整个运行时间优先级都不会变化; 动态优先级:根据进程的动态变化调整优先级,比如如果进程运行时间增加,则降低其优先级,如果进程等待时间(就绪队列的等待时间)增加,则升高其优先级,也就是随着时间的推移增加等待进程的优先级。
非抢占式:当就绪队列中出现优先级高的进程,运行完当前进程,再选择优先级高的进程。 抢占式:当就绪队列中出现优先级高的进程,当前进程挂起,调度优先级高的进程运行。
多级反馈队列调度算法
「多级」表示有多个队列,每个队列优先级从高到低,同时优先级越高时间片越短。 「反馈」表示如果有新的进程加入优先级高的队列时,立刻停止当前正在运行的进程,转而去运行优先级高的队列;
设置了多个队列,赋予每个队列不同的优先级,每个队列优先级从高到低,同时优先级越高时间片越短; 新的进程会被放入到第一级队列的末尾,按先来先服务的原则排队等待被调度,如果在第一级队列规定的时间片没运行完成,则将其转入到第二级队列的末尾,以此类推,直至完成; 当较高优先级的队列为空,才调度较低优先级的队列中的进程运行。如果进程运行时,有新进程进入较高优先级的队列,则停止当前运行的进程并将其移入到原队列末尾,接着让较高优先级的进程运行;
内存页面置换算法
缺页中断在指令执行「期间」产生和处理中断信号,而一般中断在一条指令执行「完成」后检查和处理中断信号。 缺页中断返回到该指令的开始重新执行「该指令」,而一般中断返回回到该指令的「下一个指令」执行。
在 CPU 里访问一条 Load M 指令,然后 CPU 会去找 M 所对应的页表项。 如果该页表项的状态位是「有效的」,那 CPU 就可以直接去访问物理内存了,如果状态位是「无效的」,则 CPU 则会发送缺页中断请求。 操作系统收到了缺页中断,则会执行缺页中断处理函数,先会查找该页面在磁盘中的页面的位置。 找到磁盘中对应的页面后,需要把该页面换入到物理内存中,但是在换入前,需要在物理内存中找空闲页,如果找到空闲页,就把页面换入到物理内存中。 页面从磁盘换入到物理内存完成后,则把页表项中的状态位修改为「有效的」。 最后,CPU 重新执行导致缺页异常的指令。
状态位:用于表示该页是否有效,也就是说是否在物理内存中,供程序访问时参考。 访问字段:用于记录该页在一段时间被访问的次数,供页面置换算法选择出页面时参考。 修改位:表示该页在调入内存后是否有被修改过,由于内存中的每一页都在磁盘上保留一份副本,因此,如果没有修改,在置换该页时就不需要将该页写回到磁盘上,以减少系统的开销;如果已经被修改,则将该页重写到磁盘上,以保证磁盘中所保留的始终是最新的副本。 硬盘地址:用于指出该页在硬盘上的地址,通常是物理块号,供调入该页时使用。
最佳页面置换算法(OPT) 先进先出置换算法(FIFO) 最近最久未使用的置换算法(LRU) 时钟页面置换算法(Lock) 最不常用置换算法(LFU)
最佳页面置换算法
先进先出置换算法
最近最久未使用的置换算法
时钟页面置换算法
如果它的访问位位是 0 就淘汰该页面,并把新的页面插入这个位置,然后把表针前移一个位置; 如果访问位是 1 就清除访问位,并把表针前移一个位置,重复这个过程直到找到了一个访问位为 0 的页面为止;
最不常用算法
先来先服务算法 最短寻道时间优先算法 扫描算法算法 循环扫描算法 LOOK 与 C-LOOK 算法
先来先服务
最短寻道时间优先
扫描算法
循环扫描算法
LOOK 与 C-LOOK算法
推荐阅读:
每日打卡赢积分兑换书籍入口
👇🏻👇🏻👇🏻