本文转载自微信公众号《飞天小牛》，作者飞天小牛。转载本文请联系飞天小牛公众号。本文很多图片来自我考研时看的网课。B站上应该能找到，你可以去看看王道炎出品的操作系统系列。重点太细了，每个角落都会被覆盖。你可以选择几章来阅读。全文思维导图如下：一、调度的概念当CPU有一堆任务要处理时，由于资源有限，这些东西不可能同时处理。这就需要某种规则来决定这些任务的处理顺序，这就是“调度”研究的问题。除了接下来要说的进程调度之外，还有作业调度和内存调度。回顾进程的三态模型：“运行中”（running）：进程占用CPU，正在运行。“就绪”（ready）：进程准备运行，等待系统分配CPU运行。“阻塞状态”/等待状态（wait）：进程不具备运行的条件，正在等待某个事件的完成。所谓进程调度就是“按照一定的算法，从进程的就绪队列（阻塞）中选择一个进程，将CPU分配给它运行”，从而实现进程的并发执行。这是操作系统中最基本（最低级）的调度，一般的操作系统都必须配置进程调度。进程调度的频率很高，一般是几十毫秒一次。2.非抢占式进程调度算法所谓非抢占式是指当一个进程在运行时，它会一直运行，直到该进程执行完毕或事件发生而被阻塞，才不会把CPU让给其他进程。相应的，抢占式就是当一个进程在运行的时候，可以被中断，把CPU让给其他进程。①FirstComeFirstServeFCFS调度算法（FirstComeFirstServe，FCFS）：按照进程到达的先后顺序进行调度，“先到的进程先被调度”，也就是说等待时间越长，更多优先获得服务。优点：公平，算法实现简单缺点：不利于短流程。长进程后面的短进程需要等待很长时间，短进程的响应时间过长，用户交互体验会变差。②ShortestJobFirstSJF最短作业/进程优先级调度算法（ShortestJobFirst，SJF）：“选择当前到达的运行时间最短的进程进行每次调度”。最短作业优先算法正好与先到先得相反。先来先服务不适用于短期流程，而最短作业优先算法不适用于长期流程。因为如果一直有短进程过来，长进程永远不会被调度，长进程可能会饿死，等待短作业完成。③高响应比优先HRRN高响应比优先算法（HighestResponseRatioNext，HRRN）：只有当前运行的进程主动让出CPU（正常/异常完成，或者主动阻塞），才需要调度。就绪进程的响应率，将CPU分配给响应率最高的进程。响应率=（进程的等待时间+进程需要的运行时间）/进程需要的运行时间3.抢占式进程调度算法抢占是指当一个进程在运行时，可以被中断，将CPU让给其他进程。抢占一般有3种原则，即时间片原则、优先级原则、短作业优先级原则。①最短剩余时间优先SRTN最短剩余时间优先（ShortestRemainingTimeNext，SRTN）算法是“最短作业优先的抢占式版本”。当前进程的。如果新进程需要的时间较少，则挂起当前进程并运行新进程，否则新进程正在等待。”②循环调度算法RR循环调度算法（RoundRobin，RR）也称为时间片调度算法：调度器每次为就绪队列的第一个进程分配CPU时，都使用一个指定的时间间隔，称为时间片，通常为10ms~200ms，”就绪队列中的每个进程依次运行一个时间片。当时间片耗尽时，当前运行的进程被迫让出CPU资源，然后排在就绪队列的尾部，等待下一轮调度。因此，一个进程一般需要进行多次轮换round-robin调度算法对每个进程都是平等对待的，就像大家排队一样，一个接一个，大家先跑一段时间再排队等待运行，需要注意的是时间片的长度一个关键因素是：如果时间片设置的太短，会造成频繁的进程上下文切换，降低CPU效率；如果时间片设置的太长，那么随着就绪队列中进程数的增加，轮流消耗的总时间会更长，即每个进程相应的速度会变慢，即使时间片足够大，进程可以完成所有任务，RR调度算法也会退化为FCFS算法。4.时间最高优先级调度算法HPFRR调度算法对所有进程应用相同的策略。如果用户进程太多，内核服务进程的响应可能会跟不上。在操作系统中，内核进程比用户进程要重要得多，毕竟关系到整个系统的稳定性。最高优先级调度算法（HighestPriorityFirst，HPF）是“从就绪队列中选择优先级最高的进程运行”。如何定义进程的优先级？分为静态优先级或动态优先级：“静态优先级”：当一个进程被创建时，其优先级是预先确定的，在整个进程运行过程中，该进程的优先级不会发生变化。一般来说，内核进程的优先级高于用户进程。“动态优先级”：根据进程的动态变化调整优先级。例如，随着进程运行时间的增加，适当降低其优先级；随着进程在就绪队列中等待时间的增加，其优先级适当提高。另外需要注意的是，最高优先级算法并不是固定的抢占策略或者非抢占，“系统可以预先指定使用哪种策略”：非抢占：当优先级高的进程出现在就绪队列，则运行当前进程后，选择优先级高的进程。抢占式：当就绪队列中出现高优先级进程时，立即强制剥夺当前运行进程的CPU资源，分配给更高优先级的进程运行。
