进程与线程：08 一个实际的 schedule 函数
一、CPU调度概述
在上一讲我们讲过了cpu的调度是吧。那么cpu调度就是要从就绪队列中选择一个进程，让他来执行是吧，切换过去我们也讲了。调度是cpu调度主要考虑的一个主题，就是折中。
上一课我们也说了，cpu的调度往往是一个很深刻的话题。在不同的场合下，可能会导致这个调度算法有很多深刻的内容需要研究。比如说如果是实时系统，那么放在导弹上、卫星上，就必须要做实时调度，对应的算法是一套体系；而如果是一个手持设备、嵌入式系统，调度的时候就要考虑节能问题，这又是另一套方法。
我们这个课程里主要讲的是一个普通机器，比如我们的pc机。在pc机上，既有前台任务，又有后台任务；既有io约束性的任务，又有cpu约束型的任务。既要考虑周转时间，又要考虑响应时间。这个时候，一个实际的操作系统应该怎么做调度，应该考虑哪些内容，怎么进行折中，这些是上一课探讨的内容。上节课我们还提到，这一课要看一个实际的函数，接下来我们就深入研究这个实际的调度函数。
二、Linux 0.1调度函数Schedule解析
我们要看的就是Linux 0.1的调度函数schedule，在Linux 0.1源码中就有，大家可以去找来看一看。该函数代码核心目标是要找到一个next进程，最后执行switch to next，这和前面的内容正好衔接。这个函数加上前面的switch to，就构成了整个操作系统中核心的多进程切换机制，堪称操作系统的发动机。
在Linux 0.1中，将pcb做成一个数组。在schedule函数中，先把p设成数组的最后一个地址，然后从后往前遍历数组（i从nr_task即数组末尾开始递减） 。每次遍历做这样一件事：如果进程状态state等于task running（在Linux 0.1上，task running表示就绪状态），并且它的count大于c（初始c等于-1），就将c赋值为该进程的count，nex赋值为i。循环结束后，最终得到的next进程就是counter最大的进程，这本质上是一种优先级调度方法，count就是优先级。找到最大counter的进程后，如果c不等于零，就跳出循环，执行switch to切换到该进程执行。
三、Counter的双重作用及修改机制
整个算法的核心基于优先级调度，但counter本身还有另一重身份——时间片。这个算法巧妙地用一个count变量，既实现了基于优先级的调度，又实现了时间片轮转调度，操作和维护都非常简单。接下来重点看counter的修改机制。
-
时间片耗尽时的处理：当所有就绪态进程的
counter都减为零（即时间片都用完）时，会执行特定操作。对于所有进程，将当前counter右移一位（相当于除以二），如果原counter为零（即进程初始状态），则维持为零；对于阻塞态进程，counter右移一位后再加上初值。这样一来，当阻塞态进程转为就绪态时，其counter值会比一直处于就绪态且刚耗尽时间片的进程更大。因为io操作会使进程进入阻塞态，所以执行过io的进程再次就绪后，优先级会提高，能获得更多执行时间，这种设计照顾到了io约束性进程，而io约束性正是前台进程的特征之一。 -
时钟中断时的处理：在时钟中断中，每次都会对当前进程的
counter进行减一操作。当counter减为零时，就触发调度，这是典型的时间片轮转机制体现。
四、算法综合效果分析
-
优先级动态调整：
counter作为优先级，实现了动态调整。io操作时间越长的进程，在阻塞队列中待的时间越久，经历时间片耗尽并重新计算counter的次数就越多，其counter值会不断增大，优先级也就越高。这使得io约束性进程（前台进程）的优先级高于只执行cpu的后台进程，并且io时间越长，优先级提升越明显 。
-
响应时间保证：虽然
counter在不断变化，但通过对counter除以二（右移一位）的操作，保证了响应时间有界。假设进程初始counter值为p，经过一系列计算可以得出，最长时间片不会超过2p，每个进程最大时间片为12p，最终周转时间最多为2n×p（n为进程数量） 。这种设计既实现了灵活的调度，又确保了系统响应的稳定性。 -
多种调度算法融合：该算法综合了时间片轮转、优先级调度和近似最短作业优先（
sgf）算法的特点。基于时间片轮转保证了响应时间；通过io时间影响优先级，照顾了io约束性的前台进程；后台cpu约束性进程按时间片轮转，在不断轮转过程中，短作业会比长作业先完成，近似体现了sgf的特点。
五、总结与启示
Linux 0.1的schedule函数用短短几句代码，仅靠一个变量counter，就综合考虑了大多数任务的需求，折中了多种调度目标。如果将来需要编写操作系统中的进程调度函数，一定要借鉴这种思路：既要折中多个任务的特点，又要设计精巧的变量和简洁的程序实现方式。