本文原创作者：源理君头条号：底层软件架构公众号：技术原理君排程程式是操作系统核心的组成部分，它负责选择下一个要执行的程序。所以排程策略就决定了这个操作系统的是非实时还是实时的操作系统。当今操作系统的种类繁多，但程序排程算法可以总结为一下几种。

先来先服务排程算法（FCFS）

短程序优先排程算法（SPF）

高优先权优先排程算法

该算法有两种型别：

非抢占式优先权算法：在这种模式下，系统一旦把处理机分配给了就绪伫列中某个优先级最高的程序，这个程序就会一直执行下去，直到程序结束；或者是主动放弃处理机，系统才会将处理机分配给另一个优先级最高的程序。这种算法可用于某些对实时性要求不高的操作系统中。抢占式优先权排程算法：在这种模式下，系统同样是把处理机分配给优先级最高程序，然后执行。但是如果在执行期间，就绪伫列中出现了优先级更高的程序，系统就会立即停止当前执行的程序，重新将处理机分配给新加入的优先级更高的程序。所以在这种模式下，可以更好的满足实时性的要求，故常用在实时性要求高的系统中。想象下高优先程序由于因资源缺乏而处于受阻状态，一直等到低优先级程序释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的程序反而超过这两个程序而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级程序无法与高优先级程序争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级程序无法获得资源而继续推进。我们把这种现象称之为：优先级翻转。

怎么解决上述问题呢？

有三种方法：

设定优先级上限，给临界区一个高优先级，进入临界区的程序都将获得这个高优先级，如果其他试图进入临界区的程序的优先级都低于这个高优先级，那么优先级反转就不会发生。优先级继承，当一个高优先级程序等待一个低优先级程序持有的资源时，低优先级程序将暂时获得高优先级程序的优先级别，在释放共享资源后，低优先级程序回到原来的优先级别。嵌入式系统VxWorks就是采用这种策略。第三种方法就是临界区禁止中断，通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级：可抢占优先级和中断禁止优先级。前者为一般程序执行时的优先级，后者为运行于临界区的优先级。火星探路者正是由于在临界区中执行的气象任务被中断发生的通讯任务所抢占才导致故障，如果有临界区的禁止中断保护，此一问题也不会发生。

高响应比优先排程算法

时间片轮转

多级反馈伫列排程算法

设定多个就绪伫列，并且每个伫列的优先等级不一样。第一伫列优先级最高，第二伫列优先级次之，以此类推。优先级越高伫列，时间片就最短。当一个新程序进入内存后，首先将它放入第一伫列的末尾，按FCFS原则排队等待排程。当轮到该程序执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，排程程式便将该程序转入第二伫列的末尾，再同样地按FCFS原则等待排程执行；如果它在第二伫列中执行一个时间片后仍未完成，再依次将它放入第三伫列，……，如此下去，当一个长作业(程序)从第一伫列依次降到第n伫列后，在第n 伫列便采取按时间片轮转的方式执行。仅当第一伫列空闲时，排程程式才排程第二伫列中的程序执行；仅当第1～(i-1)伫列均空时，才会排程第i伫列中的程序执行。如果处理机正在第i伫列中为某程序服务时，又有新程序进入优先权较高的伫列(第1～(i-1)中的任何一个伫列)，则此时新程序将抢占正在执行程序的处理机，即由排程程式把正在执行的程序放回到第i伫列的末尾，把处理机分配给新到的高优先权程序。如下图：

参考

总结

觉得不错，记得转发，关注哦！