Linux 任务调度

前言

1-3：任务调度策略

4-5：任务调度过程

1 任务调度概述

Linux的任务调度分为非实时性调度和实时性调度。非实时调度称为SCHED_NORMAL，而实时调度又分为SCHED_FIFO和SCHED_RR两种。非实时性调度时非常适合于个人PC的，即适合于交互式比较强的地方。但是对于嵌入式设备来说，有时是非常强调实时性的。所以有实时性调度策略。标志位实时性调度的进程总是优先于非实时性进程执行。

首先明确一下概念，这是非常重要的，否则下面的叙述无法展开。

（1）任务调度对象

任务调度只相对于TASK_RUNNING状态的任务，即runqueue中的队列。

（2）抢占的概念

抢占是指任务在没有阻塞的情况发生时，被强制剥夺cpu的使用权。

 

2 非实时调度SCHED_NORMAL

非实时调度，可以概括为依据优先级和时间片的抢占式调度策略。根据抢占的概念，上一句话可以理解为抢占的发生或是由优先级引起或是由时间片引起。下面会详细解释。总的来说linux内核根据动态优先级来调度，任务运行的时间片由静态优先级决定。

2.1时间片

2.1.1 时间片概念

时间片是指：任务一次连续占用CPU的最大时间跨度。该时间跨度是内核根据任务的静态优先级nice计算出来的。当然时间片并不是都是一次用完的。有可能因为高优先级任务的抢占导致当前低优先级任务退出执行，那么剩下的时间片是保留的。

2.1.2 时间片的计算时机

当所有任务的时间片用完后，则重新计算时间片。关于时间片的值，下面会详述。

2.2 静态优先级nice

Nice是task struct中的一个值，之所以称为静态，是因为用户指定后其是不变的。Nice的取值范围是-20到19。其中-20代表最高优先级。

Nice的作用有两个：用于计算时间片、做为动态优先级的基数

（1）用于计算时间

时间片的计算其实就来源于nice值，这是一个静态值，由用户指定。Nice为0，则时间片为100ms，nice为19，则时间片为5ms，nice为-20，则时间片为800ms.也就是说，任务每次分配的时间片是固定的。

（2）作为动态优先级的基数

任务调度时使用的优先级是动态优先级，而不是静态优先级nice。任务调度时的优先级并不是一直不变的。内核会根据任务的表现确定一个动态优先级。这个动态优先级才是系统调度的真正参考优先级。

但是动态优先级的初始值就是nice的值。并且，动态优先级的值的范围是（nice-5，nice+5）。当然最小值和最大值都不能超过nice的取值范围。

 

2.3 动态优先级的计算

详见书。

2.4 非实时调度的抢占

2.4.1 基于优先级的抢占

当一个进程进入TASK_RUNNING状态，内核会检查它的优先级是否高于当前正在执行的进程。如何是这样，调度程序会被唤醒，抢占当前正在执行的进程。

2.4.2 基于时间片的抢占

当一个进程的时间片变为0时，它会被抢占。调度程序被唤醒以选择新的进程。因为高优先级任务也是根据nice值分配得到有限的时间片的。有可能高优先级的时间片用完的时候，它还需要时间片来运行，可是根据时间片机制，此时它会被低优先级抢占。只有所有在runqueue中的任务使用完时间片时，才会重新计算时间片并调度。

其实，这个问题本来无可厚非的。因为这本来就是linux的非实时调度策略。只是我做嵌入式，对实时性思考的比较多，才有了这个想法。后面会发现，实时调度和非实时调度最本质的区别就是这个时间片机制。

 

3 实时调度

3.1 两种实时调度策略

Linux提供了两种实时调度策略:SCHED_FIFO和SCHED_RR。

3.2 SCHED_FIFO

SCHED_FIFO实现了一种简单的先入先出的调度算法，它不使用时间片的概念。一旦一个SCHED_FIFO级的进程处于可执行状态，就会一直执行，直到它自己受阻或显示的释放处理器为止。只有当更高优先级的SCHED_FIFO或SCHED_RR任务才能抢占SCHED_FIFO任务。

所以，SCHED_FIFO任务被抢占只有一种可能性：有优先级更高的任务。下面分析两种调度行为。

(1)两个SCHED_FIFO任务，优先级一高一低

高优先级任务先运行，直到自己受阻或显示释放，低优先级才能占有处理器。

(2)两个SCHED_FIFO任务，优先级相同

最先运行的任务会一直运行，直到自己受阻或显示释放，同优先级的另一任务才有机会占有处理器。

题外话：其实我现在使用的vxworks就是使用的这种调度算法。

3.3 SCHED_RR

SCHED_RR和SCHED_FIFO大致一样，只有一点不同。这点不同表现在如下调度行为。

假设：两个SCHED_RR任务，优先级相同

每个SCHED_RR任务被分配一个时间片。当一个任务在占用CPU时时间片用完后，会被另一任务抢占。也就是对同一优先级的SCHED_RR任务执行轮流调度算法。

 

4 调度过程全分析

调度过程因性质不同而不同。

4.1 自愿放弃CPU占用

其全过程就是调度时机了。没有表达调度需求的必要性。在自愿调度时机必然发生。

4.2 抢占

调度分两个步骤：

(1)    表达调度的需求

(2)    在系统调度时机实现调度。

在调度时机，内核检查有无调度需求，如果有的话，才进行调度。

4.2.1 表达调度需求

内核提供了一个need_resched标志来表明是否需要重新执行一次调度。

当进程耗尽它的时间片时，scheduler_tick（）会设置这个标志；

当一个优先级高的进程进入可执行状态的时候，try_to_wake_up（）会设置这个标志；

4.2.2 调度时机

看第5章“调度时机”

5 调度时机

调度时机概括为两种：自愿调度和强制调度。所谓自愿和强制是针对于当前运行的任务而言的。必须理解这个概念。

5.1 自愿的调度

自愿的调度是可以发生在用户空间和内核空间。

（1）自身受阻，需要隐式执行调度程序

比如等待IO

（2）进程显示的调用调度程序

直接执行schedule()；

或通过系统调用nanosleep。注意，开始运行nanosleep会导致一次调度，当系统调用nanosleep结束时，仍然会引起调度。这两个调度，前一个是自愿调度，因为其自身就是当前执行的任务；而后一个事强制调度，因为当前占用CPU的任务不是自身。

 

5.2 强制执行调度（抢占时机）

注意，2.4内核只包括下面4.2.1所说的用户空间强制调度，其并没有内核空间的强制调度机制。但是2.6内核包括两者。所以说2.4内核是“内核不可抢占的”，而2.6内核是“内核可抢占的”。

5.2.1 用户空间强制调度

（1）每次从系统调用返回前夕

Sleep族也属于系统调用

（2）从中断返回用户空间

注意“返回用户空间”的含义（摘录自内核源代码情景分析）：这意味着只有在用户空间（当CPU在用户空间运行时）发生的中断或异常才会引起调度。

时钟中断也算的吧，不然任务时间片用完的时候，虽然会置need_sched，但是，调度时机在哪呢？

5.2.2 内核空间强制调度

摘自《linux内核设计与实现》

(1)当中断处理程序正在执行，且返回内核空间之前

该中断必然是当任务在内核空间执行时发生的。

(2)当内核代码再一次具有可抢占性的时候

进程的thread_info的preempt_count计数值为0

 

书上的剩余两种其实应归类于自愿调度。