第七章--进程调度

        本章讨论进程调度(schednling)，主要关心什么时候进行进程切换及选择哪一个进程来运行。
一、调度策略
        决定什么时候以怎样的方式选择一个新进程运行的这组规则就是所谓的调度策略(scheduling policy)。
        Linux的调度基于分时(time sharing)技术：多个进程以“时间多路复用”方式运行，因为CPU的时间被分成“片(slice)”，给每个可运行进程分配一片。当然，单处理器在任何给定的时刻只能运行一个进程。如果当前运行进程的时间片或时限(quantum)到期时，该进程还没有运行完毕，进程切换就可以发生。分时依赖于定时中断，因此进程是透明的，不需要在程序中插入额外的代码来保证CPU分时。
        当谈及有关调度的问题时，传统上把进程分类为“I/O受限(I/O-bound)”或“CPU受限（CPU-bound)”。前者频繁地使用I/O设备，并花费很多时间等待I/O操作完成；而后者则需要大量CPU时间的数值计算应用程序。
        另一种分类法把进程区分为三类：
        交互式进程(interactive process)：这些进程经常与用户进行交互，因此，要花费很多时间等待键盘和鼠标操作。当接受了输入后，进程必须被很快唤醒，否则用户将发现系统反应迟钝。
        批处理进程(batch process)：这些进程不必与用户交互，因此经常在后台运行。因为这样的进程不必被很快地响应，因此常受到调度程序的慢待。
        实时进程(real-time process)：这些进程有很强的调度需要。这样的进程绝不会被低优先级的进程阻塞，它们应该有一个短的响应时间，更重要的是，响应时间的变化应该很小。
        与批处理进程相比，调度程序有偏爱交互式进程的倾向。
1.1、进程的抢占
        Linux的进程是抢占式的。如果进程进入TASK_RUNNING状态，内核检查它的动态优先级是否大于当前正运行的优先级，如果是，current的执行被中断，并调用调度程序选择另一个进程运行(通常是刚刚变为可运行的进程)。当然，进程在它的时间片到期时也可以被抢占。此时，当前进程thread_info结构中的TIF_NEED_RESCHED标志被设置，以便时钟中断处理程序终止时调度程序被调用。
        被抢占的进程并没有被挂起，因为它还处于TASK_RUNNING状态，只不过不再使用CPU。此外，记住Linux内核是抢占式的，这意味着进程无论是处于内核态还是用户态，都可能被抢占。
1.2、一个时间片必须持续多长？
        选择尽可能长、同时能保持良好响应时间的一个时间片。
二、调度算法
        调度程序总能成功地找到要执行的进程。事实上，总是至少有一个可运行进程，即swapper进程，它的PID等于0，而且它只有在CPU不能执行其他进程时才执行。每个多处理器系统的CPU都有它自己的swapper进程，其PID等于0。
        每个Linux进程总是按照下面的调度类型被调度：
        SCHED_FIFO：先进先出的实时进程。当调度程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。如果没有其他可运行的更高优先级实时进程，进程就继续使用CPU，想用多久就用多久，即使还有其他具有相同优先级的实时进程处于可运行状态。
        SCHED_RR：时间片轮转的实时进程。当调度程序把CPU分配给进程的时候，它把该进程的描述符放在运行队列链表的末尾。这种策略保证对所有具有相同优先级的SCHED_RR实时进程公平地分配CPU时间。
        SCHED_NORMAL：普通的分时进程。
        调度算法根据进程是普通进程还是实时进程而有很大不同。
2.1、普通进程的调度
        内核用从100(最高优先级)到139(最低优先级)的数表示普通进程的静态优先级。注意，值越大静态优先级越低。
        新进程总是继承其父进程的静态优先级。不过，通过把某些“nice值”传递给系统调用nice()和setpriority()，用户可以改变自己拥有的进程的静态优先级。
2.1.1、基本时间片
        基本时间片(ms) = (140 - 静态优先级） * 20        若静态优先级  < 120
                               = (140 - 静态优先级） * 5          若静态优先级  >= 120
        静态优先级越高(其值越小)，基本时间片就越长。其结果是，与优先级低的进程相比，通常优先级较高的进程获得更长的CPU时间片。
2.1.2、动态优先级和平均睡眠时间
        普通进程除了静态优先级，还有动态优先级，其值的范围是100(最高优先级)~139(最低优先级)。动态优先级是调度程序在选择新进程来运行的时候使用的数。它与静态优先级的关系用下面的经验公式表示：
        动态优先级 = max(100， min(静态优先级 - bonus + 5, 139))
        bonus是范围从0~10的值，值小于5表示降低动态优先级以示惩罚，值大于5表示增加动态优先级以示奖赏。bonus的值依赖于进程过去的情况，说得更准确一些，是与进程的平均睡眠时间相关。
        平均睡眠时间是进程在睡眠状态所消耗的平均纳秒数。进程在运行的过程中平均睡眠时间递减。最后，平均睡眠时间永远不会大于1s。
2.1.3、活动和过期进程
        即使具有较高静态优先级的普通进程获得了较大的CPU时间片，也不应该使静态优先级较低的进程无法运行。为了避免进程饥饿，当一个进程用完它的时间片时，它应该被还没有用完时间片的低优先级进程取代。为了实现这种机制，调度程序维持两个不相交的可运行进程的集合。
        活动进程：这些进程还没有用完它们的时间片，因此允许它们运行。
        过期进程：这些可运行进程已经用完了它们的时间片，并因此被禁止运行，直到所有活动进程都过期。
        如果最老的过期进程已经等待了很长时间，或者过期进程比交互式进程的静态优先级高，调度程序就把用完时间片的交互式进程移到过期进程集合中。结果，活动进程集合最终会变为空，过期进程将有机会运行。
2.2、实时进程的调度
        每个实时进程都与一个实时优先级相关，实时优先级是一个范围从1(最高优先级)~99(最低优先级)的值。调度程序总是让优先级高的进程运行，换句话说，实时进程运行的过程中，禁止低优先级进程的执行。
        只有在下述事件之一发生时，实时进程才会被另外一个进程取代：
        * 进程被另外一个具有更高实时优先级的实时进程抢占。
        * 进程执行了阻塞操作并进入睡眠(处于TASK_INTERRUPTIBLE或TASL_UNINTERRUPTIBLE状态)。
        * 进程停止(处于TASK_STOPPED或TASK_TRACED状态)或被杀死(处于EXIT_ZOMBIE或EXIT_DEAD状态)。
        * 进程通过调用系统调用sched_yield()自愿放弃CPU。
        * 进程是基于时间片轮转的实时进程(SCHED_RR)，而且用完了它的时间片。
        当系统调用nice()和setpriority()用于基于时间片轮转的实时进程时，不改变实时进程的优先级而会改变其基本时间片的长度。实际上，基于时间片轮转的实时进程的基本时间片的长度与实时进程的优先级无关，而依赖于进程的静态优先级。
三、调度程序所使用的数据结构
        进程链表链接所有的进程描述符，而运行队列链表链接所有的可运行进程(也就是处于TASK_RUNNING状态的进程)的进程描述符，swapper进程(idle进程)除外。
3.1、数据结构runqueue
        系统中的每个CPU都有它自己的运行队列，所有的runqueue结构存放在runqueues每CPU变量中。
        runqueue数据结构中最重要的字段是与可运行进程的链表相关的字段。系统中的每个可运行进程属于且只属于一个运行队列。只要可运行进程保持在同一个运行队列中，它就只可能在拥有该运行队列的CPU上执行。但是，正如我们将要看到的，可运行进程会从一个运行队列迁移到另一个运行队列。
3.2、进程描述符
        一个进程不能通过创建多个后代来霸占资源。

四、调度程序所使用的函数
        调度程序依靠几个函数来完成调度工作，其中最重要的函数是：
        scheduler_tick()：维持当前最新的time_slice计数器。
        try_to_wake_up()：唤醒睡眠进程。
        recalc_task_prio()：更新进程的动态优先级
        schedule()：选择要被执行的新进程。
        load_balance()：维持多处理器系统中运行队列的平衡。
4.1、scheduler_tick()函数

4.1.1、更新实时进程的时间片
        如果当前进程是先进先出(FIFO)的实时进程，函数scheduler_tick()什么都不做。实际上在这种情况下，current所表示的进程(当前进程)不可能被比其优先级低或其优先级相等的进程所抢占，因此，维持当前进程的最新时间片计数器是没有意义的。
        如果current表示基于时间片轮转的实时进程，scheduler_tick()就递减它的时间片计数器并检查时间片是否被用完。
        如果函数确定时间片确实用完了，就执行一系列操作以达到抢占当前进程的目的，如果必要的话，就尽快抢占。

4.1.2、更新普通进程的时间片

4.2、try_to_wake_up()函数
        try_to_wake_up()函数通过把进程状态设置为TASK_RUNNING，并把该进程插入本地CPU的运行队列来唤醒睡眠或停止的进程。例如，调用该函数唤醒等待队列中的进程或恢复执行等待信号的进程。该函数接受的参数有：
        * 被唤醒进程的描述符指针(p)。
        * 可以被唤醒的进程状态掩码(state)。
        * 一个标志(sync)，用来禁止被唤醒的进程抢占本地CPU上正在运行的进程。

4.3、recalc_task_prio()函数
        函数recalc_task_prio()更新进程的平均睡眠时间和动态优先级。它接收进程描述符的指针p和由函数sched_clock()计算出的当前时间戳now作为参数。
4.4、schedule()函数
        函数schedule()实现调度程序。它的任务是从运行队列的链表中找到一个进程，并随后将CPU分配给这个进程。schedule()可以由几个内核控制路径调用，可以采取直接调用或延迟(lazy)调用(可延迟的)的方式。
4.4.1、直接调用
        如果current进程因不能获得必须的资源而要立刻被阻塞，就直接调用调度程序。在这种情况下，要阻塞进程的内核控制路径按下述步骤执行：
        1、把current进程插入适当的等待队列。
        2、把current进程的状态改为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。
        3、调用schedule()。
        4、检查资源是否可用，如果不可用就转到第2步。
        5、一旦资源可用，就从等待队列中删除current进程。
        内核例程反复检查进程需要的资源是否可用，如果不可用，就调用schedule()把CPU分配给其他进程。稍后，当调度程序再次允许把CPU分配给这个进程时，要重新检查资源的可用性。这些步骤与wait_event()所执行的步骤很相似。
        许多执行长迭代任务的设备驱动程序也直接调用调度程序。每次迭代循环时，驱动程序都检查TIF_NEED_RESCHED标志，如果需要就调用schedule()自动放弃CPU。
4.4.2、延迟调用
        也可以把current进程的TIF_NEED_RESCHED标志设置为1,而以延迟方式调用调度程序。由于总是在恢复用户态进程的执行之前检查这个标志的值，所以schedule()将在不久之后的某个时间被明确地调用。
        以下是延迟调用调度程序的典型例子：
        * 当current进程用完了它的CPU时间片时，由scheduler_tick()函数完成schedule()的延迟调用。
        * 当一个被唤醒进程的优先级比当前进程的优先级高时，由try_to_wake_up()函数完成schedule()的延迟调用。
        * 当发出系统调用sched_setscheduler()时。
4.4.3、进程切换之前schedule()所执行的操作
        schedule()函数的任务之一是用另外一个进程来替换当前正在执行的进程。因此，该函数的关键结果是设置一个叫做next的变量，使它指向被选中的进程，该进程将取代current进程。如果系统中没有优先级高于current进程的可运行进程，那么最终next与current相等，不发生任何进程切换。

表：进程描述符中activated字段的含义
        值            说明
        0            进程处于TASK_RUNNING
        1            进程处于TASK_INTERRUPTIBLE或TASK_STOPPED状态，而且正在被系统调用服务例程或内核线程唤醒
        2            进程处于TASK_INTERRUPTIBLE或TASK_STOPPED状态，而且正在被中断处理程序或可延迟函数唤醒
        -1           进程处于TASK_UNINTERRUPTIBLE状态而且正在被唤醒
        要说明的是，调度程序把被中断处理程序和可延迟函数所唤醒的进程与被系统调用服务例程和内核线程所唤醒的进程区分开来。在前一种情况下，调度程序增加全部运行队列等待时间，而在后一种情况下，它只增加等待时间的部分。这是因为交互式进程更可能被异步事件(考虑用户在键盘上按键操作)而不是同步事件唤醒。
4.4.4、schedule()完成进程切换时所执行的操作

4.4.5、进程切换后schedule()所执行的操作

        schedule()在需要的时候重新获得大内核锁，重新启用内核抢占，并检查是否一些其他的进程已经设置了当前进程的TIF_NEED_RESCHED标志。如果是，则整个schedule()函数重新开始执行，否则，函数结束。
五、多处理器系统中运行队列的平衡
        schedule()函数从本地CPU的运行队列挑选新进程运行。因此，一个指定的CPU只能执行其相应的运行队列中的可运行进程。另外，一个可运行进程总是存放在某一个运行队列中。任何一个可运行进程都不可能同时出现在两个或多个运行队列中。因此，一个保持可运行状态的进程通常被限制在一个固定的CPU上。
        内核周期性地检查运行队列的工作量是否平衡，并在需要的时候，把一些进程从一个运行队列迁移到另一个运行队列。但是，为了从多处理器系统获得最佳性能，负载平衡算法应该考虑系统中CPU的拓扑结构。从内核2.6.7版本开始，Linux提出一种基于“调度域”概念的复杂的运行队列平衡算法。正是有了调度域这一概念，使得这种算法能够很容易适应各种已有的多处理器体系结构(甚至诸如那些基于新近出现的“多核”微处理器的体系结构)。
5.1、调度域
        调度域(scheduling domain)实际上是一个CPU集合，它们的工作量应当由内核保持平衡。一般来说，调度域采取分层的组织形式：最上层的调度域(通常包括系统中的所有CPU)包括多个子调度域，每个子调度域包括一个CPU子集。调度域实现：
        每个调度域被依次划分成一个或多个组，每个组代表调度域的一个CPU子集。工作量的平衡总是在调度域的组之间来完成。换言之，只有在某调度域的某个组的总工作量远远低于同一个调度域的另一个组的工作量时，才把进程从一个CPU迁移到另一个CPU。

5.2、rebalance_tick()函数

5.3、load_balance()函数
        load_balance()函数检查是否调度域处于严重的不平衡状态。更确切地说，它检查是否可以通过把最繁忙的组中的一些进程迁移到本地CPU的运行队列来减轻不平衡的状况。如果是，函数尝试实现这个迁移。它接收四个参数：
        this_cpu：本地CPU的下标。
        this_rq：本地运行队列的描述符的地址。
        sd：指向被检查的调度域的描述符。
        idle：取值为SCHED_IDLE(本地CPU空闲)或NOT_IDLE。

5.4、move_tasks()函数
        move_tasks()函数把进程从源运行队列迁移到本地运行队列。

六、与调度相关的系统调用
        作为一般原则，总是允许用户降低其进程的优先级。然而，如果他们想修改属于其他某一用户进程的优先级，或者如果他们想增加自己进程的优先级，那么，他们必须拥有超级用户的特权。
6.1、nice()系统调用
        nice()系统调用允许进程改变它们的基本优先级。
        sys_nice()服务例程处理nice()系统调用。尽管nicrement参数可以有任何值，但是大于40的绝对值会被截为40。从传统上来说，负值相当于请求优先级增加，并请求超级用户特权，而正值相当于请求优先级减少。
6.2、getpriority()和setpriority()系统调用
        nice()系统调用只影响调用它的进程，而另外两个系统调用getpriority()和setpriority()则作用于给定组中所有进程的基本优先级。getpriority()返回20减去给定组中所有进程之中最低nice字段的值(即所有进程中的最高优先级)；setpriority()把给定组中所有进程的基本优先级都设置为一个给定的值。

6.3、sched_getaffinity()和sched_setaffinity()系统调用
        sched_getaffinity()和sched_setaffinity()系统调用分别返回和设置CPU进程亲和力掩码，也就是允许执行进程的CPU的位掩码。该掩码存放在进程描述符的cpus_allowed字段中。
6.4、与实时进程相关的系统调用
        现在我们介绍一组系统调用，它们允许进程改变自己的调度规则，尤其是可以变为实时进程。进程为了修改任何进程(包括自己)的描述符的rt_priority和policy字段，同样必须具有CAP_SYS_NICE权能。
6.4.1、sched_getscheduler()和sched_setscheduler()系统调用

6.4.2、sched_getparam()和sched_setparam()系统调用

6.4.3、sched_yield()系统调用
        sched_yield()系统调用允许进程在不被挂起的情况下自愿放弃CPU，进程仍然处于TASK_RUNNING状态，但调度程序把它放在运行队列的过期进程集合中(如果进程是普通进程)，或放在运行队列链表的末尾(如果进程是实时进程)。随后调用schedule()函数。在这种情况下，具有相同动态优先级的其他进程将有机会运行，这个调用主要由SCHED_FIFO实时进程使用。
6.4.4、sched_get_priority_min()和sched_get_priority_max()系统调用
        sched_get_priority_min()和sched_get_priority_max()系统调用分别返回最小和最大实时静态优先级的值，这个值由policy参数所标识的调度策略来使用。
        如果current是实时进程，则sched_get_priority_min()服务例程返回1，否则返回0。
        如果current是实时进程，则sched_get_priority_max()服务例程返回99(最高优先级)，否则返回0。
6.4.5、sched_rr_get_interval()系统调用