《Linux内核设计与实现》读书笔记——进程调度

进程调度程序是确保进程能有效工作的一个内核子系统。

多任务

多任务可以分为两类：

• 非抢占式多任务(cooperative multitasking)。除非进程自己主动停止运行，否则它会一直执行。进程主动让出自己的操作称为让步(yielding)。
• 抢占式多任务(preemtive multitasking)。Linux提供了抢占式的多任务模式。由进程调度程序来决定什么时候停止一个进程的运行。这个强制的挂起动作就叫做抢占(preemption)。进程在被抢占之前能够运行的时间叫做时间片(timeslice)。

Linux的进程调度

从1991年的Linux第一版到后来的2.4内核系列，Linux的调度程序都相当简陋，设计近乎原始。在Linux2.5开发系列的内核中，采用了一种叫做O(1)调度程序的新调度程序。就如它的名字，时间复杂度是O(1)。

O(1)调度器在拥有数以十计的多处理器环境下尚能表现出近乎完美的性能和可拓展性，但是对于响应时间敏感的交互进程来说却有一些先天不足。从2.6内核系统开发初期，开发人员引入了新的调度算法。其中最有名的是反转楼梯最后期限调度算法(Rotating Staircase Deadline scheduler)(RSDL)。该算法吸取了队列理论，将公平调度的概念引入了Linux调度程序，并最终在2.6.23内核版本中替代了O(1)调度算法。它被称为完全公平调度算法(CFS)。

策略

策略决定调度程序在何时让什么进程运行。

I/O消耗型和处理器消耗型的进程

进程可被分为I/O消耗型和处理器消耗型。前者指进程的大部分时间都用来提交或等待I/O请求。相反，处理器消耗型则大部分时间都用在执行代码上。当然两者的划分并非泾渭分明。

调度策略通常就要在两个矛盾的目标中寻找平衡：进程相应迅速和最大系统利用率。

进程优先级

Linux采用了两种不同的优先级范围。

第一种是使用nice值，范围是-20～+19，默认为0。越大的nice值意味着优先级越低。nice值代表时间片的比例。可以通过ps -el查看，NI列表示的就是nice值。

第二种范围是实时优先级，其范围是可配置的。默认情况下它的变化范围是[0, 99]。与nice值相反，越高的实时优先级代表进程优先级更高。任何实时进程的优先级都高于普通进程，也就是说nice优先级和实时优先级处于互不相交的两个范畴。

时间片

时间片是一个数值，表明进程在被抢占前能持续运行的时间。调度策略需要规定默认的一个时间片。但时间片过长会导致系统对交互的效应表现欠佳，过段会明显增加进程切换带来的处理器耗时。而且I/O消耗型和处理器消耗型的矛盾也显示出来：I/O消耗型不需要过长时间片，而处理器消耗型则希望越长越好。

Linux的CFS调度并没有直接分配时间片到进程，而是讲处理器的使用比例划分给了进程。这样一来，进程所获得的处理器时间其实是和系统负载有关。抢占时机也取决于新的可运行程序消耗了多少处理器使用比。

Linux调度算法

调度器类

Linux调度器是以模块方式提供的，称为调度器类(scheduler classes)，不同类型的进程可以有针对性地选择调度算法。基础的调度器类代码定义在kernel/sched.c文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出。

CFS是一个针对简单进程的调度类，在Linux中称为SCHED_NORMAL。

Unix系统中的进程调度

在Unix系统上，优先级以nice值形式输出给用户空间。在现实中会产生许多问题。

• 若要讲nice值映射到时间片，就必然需要将nice单位值对应到处理器的绝对时间。但这样做会导致进程切换无法最优化执行。举例说明，默认nice值为0分配100ms的时间片，最高nice值为20分配5ms。如果同时运行时间片5ms的进程，则要在10ms间进行一次上下文切换；而运行时间片是100ms的进程，则要在100ms间进行一次上下文切换。

• 相对nice值。假设两个进程nice值分别是0和1，时间片分别是100ms和95ms，区别微乎其微。而两个进程nice值分别为18和19，时间片分别为10ms和5ms，前者是后者的两倍！

• 如果执行nice值到时间片的映射，需要能分配一个绝对时间片，而这个绝对时间片必须能在内核的测试范围内。

• 最后一个问题是关于基于优先级的调度器会为了优化交互任务而唤醒相关进程的问题。

公平调度

CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了。CFS在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得处理器运行比的权重。

每个进程都按照其权重在其全部可运行进程中所占比例的时间片来运行。CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。这个目标称为目标延迟。假定目标延迟值是20ms，两个同样优先级的可运行任务会分别运行10ms。

CFS还为每个进程设置了时间片底线，这个底线称为最小粒度。默认情况下是1ms。

任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值对应的绝对时差值决定的。nice值对时间片的作用是几何加权。

Linux调度的实现

CFS位于kernel/sched_fair.c中。特别关注四个组成部分：

• 时间记账
• 进程选择
• 调度器入口
• 睡眠和唤醒

时间记账

所有调度器都必须对进程运行时间做记账。

调度器实体结构

CFS不再有时间片的概念，但是它也必须维护每个进程运行的时间记账。CFS使用sched_entity来跟踪进程运行记账：

struct sched_entity
{
    struct load_weight load; /* for load-balancing */
    struct rb_node run_node;
    struct list_head group_node;
    unsigned int on_rq;

    u64 exec_start;
    u64 sum_exec_runtime;
    u64 vruntime;
    u64 prev_sum_exec_runtime;

    u64 nr_migrations;

#ifdef CONFIG_SCHEDSTATS
    struct sched_statistics statistics;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity *parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq *my_q;
#endif
};

sched_entity作为PCB中一个名为se的成员变量。

虚拟实时

vruntime变量存放进程的虚拟运行时间，该运行时间的计算是经过了所有可运行进程总数的标准化。虚拟时间是以ns为单位的。CFS用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。

进程选择

CFS调度算法的核心：当CFS需要选择下一个运行进程时，它会挑一个具有最小vruntime的进程。接下来就讨论如何选择具有最小vruntime值的进程。

CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。

挑选下一个任务

先假设，红黑树存储了系统中所有的可运行进程，其中节点的键值是可运行进程的虚拟运行时间。那么树中最左侧的叶子节点，就是所有vruntime最小的那个。

向树中加入进程

CFS在进程变为可运行状态(被唤醒)或者通过fork()调用第一次创建进程时，将进程加入rbtree中，并且缓存最右子节点。

从树中删除进程

CFS从红黑树中删除进程，删除动作发生在进程堵塞(变为不可运行态)或者终止时(结束运行)。

调度器入口

进程调度的主要入口点是函数schedule()。它选择哪个进程可以运行，何时将其投入运行。schedule()会找到一个最高优先级的调度类——后者需要有自己的可运行队列，然后问后者谁才是下一个该运行的进程。

睡眠和唤醒

休眠(被阻塞)的进程处于一个特殊的不可执行状态。当进程休眠时，内核的操作如下：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。唤醒的过程正好相反：进程被设置成可执行状态，然后从可执行队列中移到可执行红黑树中。

等待队列

休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核通过wake_queue_head_t来代表等待队列。

在内核中进行休眠的推荐操作相对复杂：

// q是我们希望休眠的等待队列
DEFINE_WAIT(wait);

add_wait_queue(q, &wait);
while (!condition)
{
    prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE)；
    if (signal_pending(current))
        /* 处理信号 */
    schedule();
}
finish_wait(&q, &wait);

唤醒

唤醒操作通过函数wake_up()进行。它会唤醒执行的等待队列上的所有进程。

抢占和上下文切换

这里的上下文切换是指进程间的切换，由定义在kernel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来投入运行的时候，schedule()会调用该函数。它完成两个基本的工作：

-调用声明在asm/mmu_context.h中的switch_mm()，负责把虚拟内存从上一个进程映射切换到新进程中。

• 调用声明asm/system.h中的switch_to()，负责从上一个进程的处理器状态切换到新进程的处理器状态。

内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时，scheduler_tick()就会设置这个标志；当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志，内核检查该标志，确认其被设置，调用schedule()来切换到一个新的进程。

在2.2以前的内核版本中，该标志位曾是一个全局变量，2.2~2.4版的内核中它在task_struct中。而在2.6版中，它被移到thread_info结构体里，用一个特别的标志变量中的一位来表示。

用户抢占

用户抢占发生在一下情况：

• 从系统调用返回用户空间时
• 从中断处理程序返回用户空间时

总而言之，内核即将返回用户空间的时候，如果need_resched标志被置位，会导致schedule()被调用。

内核抢占

大部分的Unix变体不支持内核抢占，调度程序没有办法在内核级的任务正在执行的时候重新调度——内核中的任务是以协作的方式调度的，不具备抢占性。

Linux在2.6版本的内核中，引入了内核抢占。只要重新调度是安全的，内核就可以在任何时候抢占正在执行的任务。它发生在：

• 中断处理程序正在运行，并且返回内核空间之前。
• 内核代码再一次具有可抢占性的时候。
• 如果内核中的任务显示地调用schedule()。
• 如果内核中的任务阻塞(这也会导致调用schedule())。

实时调度策略

Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。而普通的非实时的调度策略是SCHED_NORMAL。这些实时调度器并不被CFS管理，而是被一个特殊的实时调度器管理。

与调度相关的系统调用

主要通过C库提供的nice()和sched_xxxx()系列函数。基本都是和系统调用的简单对应。