下载掌阅APP，畅读海量书库
立即打开
进程可以有一个或多个线程，它们都需要由内核分配CPU来执行任务，可是CPU总共就这么几个，系统应该如何调度呢？本节来详细讲解一下CPU任务调度的原理。无论是进程还是线程，在系统内核里统一称为任务（Task），任务是采用task_struct结构进行描述的。从CPU角度来看，所有的进程与线程都是待执行的任务，如图1-9所示。
图1-9 进程、线程任务
每一个任务都应该有一个ID，作为这个任务的唯一标识，后面介绍的任务挂起、唤醒等调度都是通过这个ID来进行管理的。
在Linux操作系统里有两种进程：一种称为实时进程，另一种称为普通进程。实时进程需要尽快执行并返回结果。通俗地讲，实时进程就好比公司的VIP客户，每次提的需求都特别着急，那公司给的优先级就会比较高。普通进程对执行时效的要求没那么高，只要能完成就行，大部分进程其实都是这种。
实时进程的调度策略通常有3种：SCHED_FIFO、SCHED_RR与SCHED_DEADLINE。SCHED_FIFO是早期的调度策略，按照FIFO的原则进行任务调度，即只有前面的任务结束了后面任务才会被执行。被调度器调度运行后的进程，其运行时长不受限制，只有运行结束或者主动挂起才会退出CPU的运行。SCHED_RR是轮流调度策略，每个任务都有时间片，也就是任务执行的配额，当前进程的时间片用完后会交给其他线程执行，同时会把当前线程重新加入调度队列的尾部。与SCHED_FIFO不同，在SCHED_RR下，高优先级任务可以抢占低优先级任务的执行顺序。SCHED_DEADLINE是一种新的策略，它会给每个任务设置一个到期时间。任务在到期时间到期之前必须完成运行。当需要进行任务调度的时候，DL调度器总是选择离到期时间最近的任务来调度执行。
普通进程也有3种调度策略：SCHED_NORMAL、SCHED_BATCH与SCHED_IDLE。普通的任务都没有那么紧急，所以通常按照公平、公正的流程来进行调度。SCHED_NORMAL是普通进程调度策略，采用CFS调度器来进行调度。SCHED_BATCH是管理后台进程的调度策略，也是采用CFS调度器进行调度的。后台进程任务可以默默执行，不影响需要交互的进程，可以降低它的优先级。SCHED_IDLE是特别空闲的时候才会执行的进程调度策略，就是在没有任何任务执行的时候才会运行空闲线程。
Linux实现了一种完全公平的普通任务的调度策略CFS（Completely Fair Scheduling）。CFS是通过计算进程消耗的CPU时间（标准化以后的虚拟CPU时间）来确定谁来运行，从而达到调度的公平性。CFS通过引入vruntime（虚拟运行时间）的概念来表示进程运行时间与期望运行时间的比率。vruntime越小，说明期望没有满足，需要优先调度，vruntime越大，说明已经基本满足要求了，可以晚点调度。
提示
vruntime=实际运行时间×1024/进程权重时间
在上述公式中，实际运行时间就是当前任务已经完成的时间，进程权重时间就是根据进程设置的权重比换算出来的权重时间。普通进程是通过权重值来调整优先级的，优先级的大小范围是-20～19，数值越小优先级越大，意味着权重值越大。CFS就是通过prio_to_weight数组来设置权重值获取权重时间的。权重值对应的权重时间如代码清单1-2所示。
代码清单1-2 权重值对应的权重时间
如果把一个进入任务的优先级设置成0，那么vruntime的计算公式就变成：
vruntime=实际运行时间×1024/1024
vruntime相当于实际运行时间。在算法实现上，CFS采用了红黑树来存储调度的任务节点，红黑树的结构如图1-10所示。树的左边节点的vruntime值小于右边节点的vruntime值。在任务调度的时候，取下最左边的节点来运行就可以了。
图1-10 CFS红黑树结构
例如在图1-10中，CFS会调度vruntime为11的节点优先运行，之后会调度vruntime为18的节点。
接下来详细地讲解一下任务的整体调度策略。CPU的任务队列结构如图1-11所示。
图1-11 CPU任务队列结构
每个CPU都有自己的任务运行队列（runqueue）。任务调度就是将需要执行的任务加入runqueue中。runqueue中所有任务的状态都是TASK__RUNNING。同时在runqueue的前面设计了3种任务队列：dl_rq、rt_rq、cfs_rq。dl_rq是SCHED_DEADLINE调度策略的任务队列，rt_rq是实时任务的调度队列，cfs_rq是普通任务的公平调度队列。Linux内核为每个具体的任务队列设置了不同的调度类（Scheduling Class）。CPU调度顺序的详细信息如表1-5所示。
表1-5 CPU调度顺序
每次任务调度的时候，Linux都会从Deadline开始调度，按照调度器优先级（Deadline>Realtime > Fair）运行任务调度器，完成对应的任务调度。也就是先从dl_rq中选择任务去执行，如果dl_rq没有任务，才会从rt_rq里选择任务执行，所以实时任务总是会比普通任务先得到执行。