Linux内核学习笔记(7)--完全公平调度(CFS)

时间:2022-05-16 01:44:12

一、完全公平调度算法

  完全公平调度 CFS 的出发点基于一个简单的理念:进程调度的效果应该如同系统具备一个理想中的完美多任务处理器。在这种系统中,每个进程能够获得 1/n 的处理器时间(n 为可运行进程数)。同时,我们可以调度给它们无限小的时间周期,所以,在任何可测量周期内,我们给予 n 个进程中每个进程同样多的运行时间。 

  但是,上述模型并不现实,因为我们无法再一个处理器上真的同时运行多个进程。而且,如果每个进程运行无限小的时间周期也并不高效(调度时的进程抢占会带来一定的代价)。因此,虽然我们希望所有的进程能只运行一个非常短的周期(这样会带来较好的交互性),但是 CFS 充分考虑了这样将带来的额外消耗,实现中首先要确保系统性能不受损失。 CFS 的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程,而不再采用分配时间片的方式。 CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久,而不是依靠 nice 值来计算时间片。 nice 值在 CFS 中被作为进程获得的处理器运行比的权重,越高的 nice 值将获得更低的处理器使用比。

  接下来,我们将在上述思想下,讨论 CFS 是如何实现的。

 

二、时间记账

  所有的调度器都必须对进程运行时间做记账。多数 Unix 系统通过给进程分配时间片的方式来进行时间记账,每当系统时钟发生变化时,时间片都会被减少一个节拍周期。当一个进程的时间片被减到 0 时,它就会被另一个时间片尚未减到 0 的可运行进程抢占。

  我们已经知道,CFS不再有时间片的概念。尽管如此,我们依然需要对每个进程运行的时间记账,以保证每个进程只在公平分配给它的处理器时间内运行。CFS 使用调度器实体结构sched_entity)来追踪进程运行记账,其定义在 include/linux/sched.h 中:

/*
 * CFS stats for a schedulable entity (task, task-group etc)
 *
 * Current field usage histogram:
 *
 *     4 se->block_start
 *     4 se->run_node
 *     4 se->sleep_start
 *     6 se->load.weight
 */
struct sched_entity {
    struct load_weight    load;               // 权重,与优先级有关
    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            last_wakeup;
    u64            avg_overlap;

    u64            nr_migrations;

    u64            start_runtime;
    u64            avg_wakeup;
   ... ...

#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
};

 

  调度器实体结构作为一个名为 se 的成员变量,嵌入在进程描述符 task_struct 内。实际上,在 task_struct 结构中,还定义了一个调度器实体结构 sched_rt_entity,这是实时调度的调度器实体。如下:

struct task_struct{
        ......
        struct sched_entity se;
        struct sched_rt_entity rt;
        ......
}

  回到 sched_entity 结构。注意到该结构里面有一个元素 vruntime(虚拟运行时间),调度器实体结构就是用这个来对进程运行时间进行记账的。使用 vruntime 进行时间记账的步骤如下:

1)调用 update_curr() 函数,计算当前进程的执行时间,并将结果存放在变量 delta_exec 中;

2)将 delta_exec 作为参数传递给 _update_curr() 函数,该函数将根据当前可运行的进程总数对运行时间进行加权运算;

3)将权值与当前运行进程的 vruntime 相加得到新的 vruntime 值。

  update_curr() 函数是由系统定时器周期性调用的,无论进程是处于可运行状态,还是被堵塞处于不可运行状态。根据这种方式,vruntime 可以准确地测量给定进程的运行时间,而且可知道谁应该是下一个被运行的进程。

 

三、进程选择

  当 CFS 需要选择下一个运行进程时,它会挑一个具有最小 vruntime 的进程。CFS 算法的核心就是选择具有最小 vruntime 的任务。CFS 使用红黑树来组织可运行进程队列,并利用其迅速找到最小 vruntime 值(红黑树最左叶子结点)的进程。

  CFS 通过调用 _pick_next_entity() 函数来寻找红黑树最左叶子结点,即最小 vruntime 值,如下:

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->rb_leftmost;    // rb_leftmost 字段中缓存着红黑树最左叶子结点的值

    if (!left)
        return NULL;

    return rb_entry(left, struct sched_entity, run_node);
}

  _pick_next_entity() 函数本身并不会遍历整个红黑树来寻找最左叶子结点,最左叶子结点的值已经缓存到了 rb_leftmost 字段中,直接调用就行,这样可以节省时间。当没有最左叶子结点(也即没有任何结点)的时候,函数返回值为 NULL,表明没有可运行的进程,此时 CFS 调度器将选择 idle 任务运行。 

 

四、调度器入口

  进程调度的主要入口点是函数 schedule(),其定义在 kernel/sched.c 中。它正式内核其他部分用于调度进程调度器的入口:选择哪个进程可以运行,何时将其投入运行。 schedule() 通常都需要和一个具体的调度类相关联,也就是说,它会找到一个最高优先级的调度类(这个调度类需要有自己的可运行队列),然后向这个调度类询问下一个该运行的进程是哪个。

  系统通过 schedule() 函数进入进程调度器,然后schedule() 函数调用 pick_next_task() 函数来选择下一个将要执行的进程:

/*
 * Pick up the highest-prio task:
 */
static inline struct task_struct *
pick_next_task(struct rq *rq)
{
    const struct sched_class *class;
    struct task_struct *p;

    /*
     * Optimization: we know that if all tasks are in
     * the fair class we can call that function directly:
     */
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }

    class = sched_class_highest;
    for ( ; ; ) {
        p = class->pick_next_task(rq);    // 每个调度类都实现了 pick_next_task()函数,它会返回指向下一个可运行进程的指针,若没有,则返回 NULL
                           // 从第一个返回非 NULL 值的类中选择下一个可运行进程
if (p) return p; /* * Will never be NULL as the idle class always * returns a non-NULL p: */ class = class->next; } }

   picke_next_task() 函数会以优先级为顺序,从高到低,依次检查每一个调度类,并且从最高优先级的调度类中,选择最高优先级的进程

 

五、睡眠和唤醒

  休眠(被阻塞)的进程处于一个特殊的不可执行状态。如果没有这种状态的话,调度程序就可能选出一个本不愿意被执行的进程,因此,休眠状态是很重要的。进程休眠有多种原因,但肯定都是为了等待一些事件。进程有两种休眠相关的状态:TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE。其中,TASK_INTERRUPTIBLE 在接收到一个信号时,可以被提前唤醒并响应该信号,而后者则会忽略该信号。

  当进程把自己标记成休眠状态时,从可执行红黑树中移除,放入等待队列,然后调用 schedule() 选择和执行一个其他进程;唤醒过程刚好相反,进程被设置为执行状态,然后再从等待队列中移到可执行红黑树中。

5.1、等待队列

  休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用 wake_queue_head_t 来代表等待队列。等待队列可以通过 DECLARE_WAITQUEUE() 静态创建,也可以由 init_waitqueue_head() 动态创建。进程把自己放入等待队列中并设置为不可执行状态。当与等待队列相关的事件发生时,队列上的进程会被唤醒。进程通过以下几个步骤将自己加入到一个等待队列中:

1)调用宏 DEFINE_WAIT() 创建一个等待队列的项;

2)调用 add_wait_queue() 把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它,通过在事件发生时对等待队列执行 wake_up() 操作;

3)调用 prepare_to_wait() 方法将进程的状态变更为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 。如果有必要的话,会将进程加入到等待队列;

4)若进程被设置为 TASK_INTERRUPTIBLE ,则信号唤醒进程。这就是所谓的伪唤醒(唤醒并不是因为事件的发生),因此检查并处理信号;

5)当进程被唤醒时,它会再次检查条件是否为真。如果为真,则退出循环;否则,再次调用 schedule() 并重复这一步;

6)当条件满足后,进程将自己设置为 TASK_RUNNING 并调用 finish_wait() 方法把自己移除等待队列。

 

5.2 唤醒

  唤醒操作通过函数 wake_up() 进行,它会唤醒指定的等待队列上的所有进程。它调用函数 try_to_wake_up() ,该函数负责将进程设置为 TASK_RUNNING 状态,然后调用 enqueue_task() 将此进程放入红黑树中,如果被唤醒的进程优先级比当前正在执行的进程的优先级高,还要设置 need_resched 标志。另外,关于休眠,存在虚假的唤醒。有时候进程被唤醒并不是因为他所等待的条件达成了,因此需要用一个循环处理来保证等待的条件真正达成(上文中的第5步)。

 

参考书籍:Linux内核设计与实现(第三版)