1. 进程调度算法⚓

1.1 单核 CPU 系统调度算法⚓

以下是单核 CPU 系统中常见的调度算法。

非抢占式的先来先服务（First Come First Serve, FCFS）算法。

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。

FCFS 对长作业有利，不利于短作业。适用于 CPU 繁忙型作业的系统，而不适用于 I/O 繁忙型作业的系统。

最短作业优先（Shortest Job First, SJF）调度算法，它会优先选择运行时间最短的进程来运行，这有助于提高系统的吞吐量。

这显然对长作业不利，很容易造成一种极端现象。

比如，一个长作业在就绪队列等待运行，而这个就绪队列有非常多的短作业，那么就会使得长作业不断的往后推，周转时间变长，致使长作业长期不会被运行。

高响应比优先（Highest Response Ratio Next, HRRN）调度算法，每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行。权衡了短作业和长作业。

如果两个进程的「等待时间」相同时，「要求的服务时间」越短，「响应比」就越高，这样短作业的进程容易被选中运行；
如果两个进程「要求的服务时间」相同时，「等待时间」越长，「响应比」就越高，这就兼顾到了长作业进程，因为进程的响应比可以随时间等待的增加而提高，当其等待时间足够长时，其响应比便可以升到很高，从而获得运行的机会；

Note

一个进程要求服务的时间是不可预估的。所以，高响应比优先调度算法是「理想型」的调度算法，现实中是实现不了的。

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。

每个进程被分配一个时间段，称为时间片（Quantum），即允许该进程在该时间段中运行。

时间片的长度是一个很关键的点：

因此，在时间片轮转调度算法中，选择合适的时间片大小需要综合考虑系统的特点、作业的类型和需求。

一般来说，时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级（Highest Priority First，HPF）调度算法，调度程序能从就绪队列中选择最高优先级的进程进行运行。

进程的优先级可以分为：

静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。

该算法也有两种处理优先级高的方法，非抢占式和抢占式：

但是依然有缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

如何工作：

设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短；
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
priority boost（优先级提升）机制。ChatGPT【基本思想是周期性地提升处于低优先级队列中的进程的优先级。通过优先级提升机制，长时间等待的进程可以在一段时间后获得更高的优先级，这样它们有更大的机会被调度执行，从而减少等待时间并提高响应性。】也可以防止防止一直来新的任务让低优先级的长任务饿死。

可以发现，对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也变更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。