Linux进程调度时机概念分析

Linux在众多进程中是怎么进行调度的，这个牵涉到Linux进程调度时机的概念，由Linux内核中Schedule（）的函数来决定是否要进行进程的切换，如果要切换的话，切换到哪个进程等等。

Linux进程调度时机主要有：

1、进程状态转换的时刻：进程终止、进程睡眠；

2、当前进程的时间片用完时（current->counter=0）；

3、设备驱动程序

4、进程从中断、异常及系统调用返回到用户态时；

时机1，进程要调用sleep（）或exit（）等函数进行状态转换，这些函数会主动调用调度程序进行进程调度；

时机2，由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机4是一样的。

时机3，当设备驱动程序执行长而重复的任务时，直接调用调度程序。在每次反复循环中，驱动程序都检查need_resched的值，如果必要，则调用调度程序schedule()主动放弃CPU。

时机4，如前所述，不管是从中断、异常还是系统调用返回，最终都调用ret_from_sys_call（），由这个函数进行调度标志的检测，如果必要，则调用调用调度程序。那么，为什么从系统调用返回时要调用调度程序呢？这当然是从效率考虑。从系统调用返回意味着要离开内核态而返回到用户态，而状态的转换要花费一定的时间，因此，在返回到用户态前，系统把在内核态该处理的事全部做完。

对于直接执行调度程序的时机，我们不讨论，因为后面我们将会描述调度程序的工作过程。前面我们讨论了时钟中断，知道了时钟中断的重要作用，下面我们就简单看一下每个时钟中断发生时内核要做的工作，首先对这个最频繁的调度时机有一个大体了解，然后再详细讨论调度程序的具体工作过程。

每个时钟中断（timer interrupt）发生时，由三个函数协同工作，共同完成进程的选择和切换，它们是：schedule（）、do_timer（）及ret_form_sys_call（）。我们先来解释一下这三个函数：

schedule（）：进程调度函数，由它来完成进程的选择（调度）；

do_timer（）：暂且称之为时钟函数，该函数在时钟中断服务程序中被调用，是时钟中断服务程序的主要组成部分，该函数被调用的频率就是时钟中断的频率即每秒钟100次（简称100赫兹或100Hz）；

ret_from_sys_call（）：系统调用返回函数。当一个系统调用或中断完成时，该函数被调用，用于处理一些收尾工作，例如信号处理、核心任务等等。

这三个函数是如何协调工作的呢？

前面我们看到，时钟中断是一个中断服务程序，它的主要组成部分就是时钟函数do_timer（），由这个函数完成系统时间的更新、进程时间片的更新等工作，更新后的进程时间片counter作为调度的主要依据。

在时钟中断返回时，要调用函数ret_from_sys_call（），前面我们已经讨论过这个函数，在这个函数中有如下几行：

cmpl $0, _need_resched

jne reschedule

……

restore_all:

RESTORE_ALL

reschedule:

call SYMBOL_NAME(schedule)

jmp ret_from_sys_call

这几行的意思很明显：检测 need_resched 标志，如果此标志为非0，那么就转到reschedule处调用调度程序schedule（）进行进程的选择。调度程序schedule（）会根据具体的标准在运行队列中选择下一个应该运行的进程。当从调度程序返回时，如果发现又有调度标志被设置，则又调用调度程序，直到调度标志为0，这时，从调度程序返回时由RESTORE_ALL恢复被选定进程的环境，返回到被选定进程的用户空间，使之得到运行。

以上就是时钟中断这个最频繁的调度时机。讨论这个的主要目的使读者对时机4有个大致的了解。

另外，TIF_NEED_RESCHED的设置时机 :

设置这个标志的函数主要有两个: resched_task(),set_tsk_need_resched().主要是resched_task,而resched_task的调用者 check_preempt_curr更是通过:try_to_wake_up/wake_up_new_task/pull_task /__migrate_task 这些被广泛使用的函数, 从而分布在内核中大量的检查点有机会抢占进程.

最后要说明的是，系统调用返回函数ret_from_sys_call（）是从系统调用、异常及中断返回函数通常要调用的函数，但并不是非得调用，对于那些要经常被响应的和要被尽快处理的中断请求信号，为了减少系统开销，处理完成后并不调用 ret_from_sys_call（）（因为很显然的，从这些中断处理程序返回到的用户空间肯定是那个被中断的进程，无需重新选择），并且，它们作的工作要尽可能少，因为响应的频率太高了。

Linux进程调度和其他的UNIX进程调度不同，尤其是在“nice level”优先级的处理上，与优先权调度（priority高的进程最先运行）不同，Linux用的是时间片轮转调度（Round Robing），但同时又保证了高优先级的进程运行的既快、时间又长（both sooner and longer）。而标准的UNIX调度程序都用到了多级进程队列。大多数的实现都用到了二级优先队列：一个标准队列和一个实时（“real time”）队列。一般情况下，如果实时队列中的进程未被阻塞，它们都要在标准队列中的进程之前被执行，并且，每个队列中，“nice level”高的进程先被执行。

总体上，Linux 调度序程在交互性方面表现很出色，当然了，这是以牺牲一部分“吞吐量”为代价的。

Linux schedule框架(调度的时刻)

1.1、中心是rq(runqueue)

rq其实是runnable queue，即本cpu上所有可运行进程的队列集合。每个cpu每种类型的rq(cfs/rt)只有一个，一个rq包含多个runnable的task，但是rq当前正在运行的进程(current running task)只有一个。

既然rq是中心，那么以下几点就是关键路径：

1、什么时候task入rq？

2、什么时候task出rq？

3、rq怎么样从多个可运行的进程(runnable tasks)中选取一个进程作为当前的运行进程(current running task)？

我们下面就逐一解答这些疑问，理解了这些关键路径，你就对linux的进程调度框架有了一个清晰的认识。

1.2、入rq(enqueue)

只有task新创建/或者task从blocked状态被唤醒(wakeup)，task才会被压入rq。涉及到进程调度相关的步骤如下：

1、把task压入rq(enqueue)，且把task->state设置为TASK_RUNNING；

2、判断压入新task以后rq的负载情况，当前task需不需要被调度出去，如果需要把当前task的thread_info->flags其中TIF_NEED_RESCHED bit置位。

重点在这里：如果当前进程需要重新调度的条件成立，这里只是会设置TIF_NEED_RESCHED标志，并不会马上调用schedule()来进行调度。真正的调度时机发生在从中断/异常返回时，会判断当前进程有没有被设置TIF_NEED_RESCHED，如果设置则调用schedule()来进行调度。

为什么唤醒涉及到调度不会马上执行？而是只设置一个TIF_NEED_RESCHED，等到中断/异常返回的时候才执行？

我理解有几点：(1)唤醒操作经常在中断上下文中执行，在这个环境中直接调用schedule()进行调度是不行的；(2)为了维护非抢占内核以来的一些传统，不要轻易中断进程的处理逻辑除非他主动放弃；(3)在普通上下文中，唤醒后接着调用schedule()也是可以的，我们看到一些特殊函数就是这么干的(调用smp_send_reschedule()、resched_curr()的函数)。

3、等待中断/异常的发生、返回，在返回时判读有TIF_NEED_RESCHED，则调用schedule()进行调度；

1.3、出rq(dequeue)

在当前进程调用系统函数进入blocked状态是，task会出rq(dequeue)。具体的步骤如下：

1、当前进程把task->state设置为TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE;

2、立即调用schedule()进行调度；

这里block是和wakeup、scheduler_tick最大的不同，block是马上调用schedule()进行调度，而wakeup、scheduler_tick是设置TIF_NEED_RESCHED标志，等待中断/异常返回时才执行真正的schedule()操作；

3、调用schedule()后，判断当前进程task->state已经非TASK_RUNNING，则进行dequeue操作，并且调度其他进程到rq->curr。

1.4、定时调度rq(scheduler_tick)

前面说了在rq的enqueue、dequeue时刻会计算rq负载，来决定把哪个runnable task放到current running task。除了enqueue/dequeue时候，系统还会周期性的计算rq负载来进行调度，确保多进程在1个cpu上都能得到服务。具体的步骤如下：

1、每1 tick，local timer产生一次中断。中断中调用scheduler_tick()，计算rq的负载重新调度；

2、如果当前进程需要被调度，则设置TIF_NEED_RESCHED标志；

3、在local timer中断返回的时候，时判读有TIF_NEED_RESCHED，则调用schedule()进行调度；

1.5、中断/异常返回(Interrupt/Exception)

在前面几节中有一个重要的概念，wakeup、scheduler_tick操作后，如果需要调度只会设置TIF_NEED_RESCHED，在中断/异常返回时才执行真正的调度schedule()操作；