CFS 负责处理普通非实时进程, 这类进程是我们 linux 中最普遍的进程

1 前景回顾

1.1 CFS 调度算法

CFS 调度算法的思想

理想状态下每个进程都能获得相同的时间片，并且同时运行在 CPU 上，但实际上一个 CPU 同一时刻运行的进程只能有一个。也就是说，当一个进程占用 CPU 时，其他进程就必须等待。CFS 为了实现公平，必须惩罚当前正在运行的进程，以使那些正在等待的进程下次被调度.

1.2 今日主题-唤醒抢占

当在 try_to_wake_up/wake_up_process 和 wake_up_new_task 中唤醒进程时, 内核使用全局 check_preempt_curr 看看是否进程可以抢占当前进程可以抢占当前运行的进程. 请注意该过程不涉及核心调度器.

每个调度器类都因应该实现一个 check_preempt_curr 函数, 在全局 check_preempt_curr 中会调用进程其所属调度器类 check_preempt_curr 进行抢占检查, 对于完全公平调度器 CFS 处理的进程, 则对应由 check_preempt_wakeup 函数执行该策略.

新唤醒的进程不必一定由完全公平调度器处理, 如果新进程是一个实时进程, 则会立即请求调度, 因为实时进程优先极高, 实时进程总会抢占 CFS 进程.

2 Linux 进程的睡眠

在 Linux 中，仅等待 CPU 时间的进程称为就绪进程，它们被放置在一个运行队列中，一个就绪进程的状 态标志位为 TASK_RUNNING. 一旦一个运行中的进程时间片用完, Linux 内核的调度器会剥夺这个进程对 CPU 的控制权, 并且从运行队列中选择一个合适的进程投入运行.

当然，一个进程也可以主动释放 CPU 的控制权. 函数 schedule()是一个调度函数, 它可以被一个进程主动调用, 从而调度其它进程占用 CPU. 一旦这个主动放弃 CPU 的进程被重新调度占用 CPU, 那么它将从上次停止执行的位置开始执行, 也就是说它将从调用 schedule()的下一行代码处开始执行.

有时候,进程需要等待直到某个特定的事件发生,例如设备初始化完成、I/O 操作完成或定时器到时等. 在这种情况下, 进程则必须从运行队列移出, 加入到一个等待队列中, 这个时候进程就进入了睡眠状态.

Linux 中的进程睡眠状态有两种

• 一种是可中断的睡眠状态，其状态标志位 TASK_INTERRUPTIBLE.

  可中断的睡眠状态的进程会睡眠直到某个条件变为真, 比如说产生一个硬件中断、释放进程正在等待的系统资源或是传递一个信号都可以是唤醒进程的条件.

• 另一种是不可中断的睡眠状态，其状态标志位为 TASK_UNINTERRUPTIBLE.

  不可中断睡眠状态与可中断睡眠状态类似, 但是它有一个例外, 那就是把信号传递到这种睡眠 状态的进程不能改变它的状态, 也就是说它不响应信号的唤醒. 不可中断睡眠状态一般较少用到, 但在一些特定情况下这种状态还是很有用的, 比如说: 进程必须等待, 不能被中断, 直到某个特定的事件发生.

在现代的 Linux 操作系统中, 进程一般都是用调用 schedule 的方法进入睡眠状态的, 下面的代码演示了如何让正在运行的进程进入睡眠状态。

1
2
3
4
5

sleeping_task = current;
set_current_state(TASK_INTERRUPTIBLE);
schedule();
func1();
/* Rest of the code ... */12345

在第一个语句中, 程序存储了一份进程结构指针 sleeping_task, current 是一个宏，它指向正在执行的进程结构。set_current_state()将该进程的状态从执行状态 TASK_RUNNING 变成睡眠状态 TASK_INTERRUPTIBLE.

• 如果 schedule 是被一个状态为 TASK_RUNNING 的进程调度，那么 schedule 将调度另外一个进程占用 CPU;
• 如果 schedule 是被一个状态为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 的进程调度，那么还有一个附加的步骤将被执行：当前执行的进程在另外一个进程被调度之前会被从运行队列中移出，这将导致正在运行的那个进程进入睡眠，因为它已经不在运行队列中了.

3 linux 进程的唤醒

当在 try_to_wake_up/wake_up_process 和 wake_up_new_task 中唤醒进程时, 内核使用全局 check_preempt_curr 看看是否进程可以抢占当前进程可以抢占当前运行的进程. 请注意该过程不涉及核心调度器.

3.1 wake_up_process

我们可以使用 wake_up_process 将刚才那个进入睡眠的进程唤醒, 该函数定义在kernel/sched/core.c, line 2043.

1
2
3
4

int wake_up_process(struct task_struct *p)
{
    return try_to_wake_up(p, TASK_NORMAL, 0);
}1234

在调用了 wake_up_process 以后, 这个睡眠进程的状态会被设置为 TASK_RUNNING，而且调度器会把它加入到运行队列中去. 当然， 这个进程只有在下次被调度器调度到的时候才能真正地投入运行.

3.2 try_to_wake_up

try_to_wake_up 函数通过把进程状态设置为 TASK_RUNNING, 并把该进程插入本地 CPU 运行队列 rq 来达到唤醒睡眠和停止的进程的目的.

例如: 调用该函数唤醒等待队列中的进程, 或恢复执行等待信号的进程.

1
2

static int
try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)12

该函数接受的参数有: 被唤醒进程的描述符指针(p), 可以被唤醒的进程状态掩码(state), 一个标志 wake_flags，用来禁止被唤醒的进程抢占本地 CPU 上正在运行的进程.

try_to_wake_up 函数定义在kernel/sched/core.c, line 1906

3.3 wake_up_new_task

1

void wake_up_new_task(struct task_struct *p)1

该函数定义在kernel/sched/core.c, line 2421

之前进入睡眠状态的可以通过 try_to_wake_up 和 wake_up_process 完成唤醒, 而我们 fork 新创建的进程在完成自己的创建工作后, 可以通过 wake_up_new_task 完成唤醒工作, 参见Linux 下进程的创建过程分析(_do_fork/do_fork 详解)–Linux 进程的管理与调度（八）

使用 fork 创建进程的时候, 内核会调用_do_fork(早期内核对应 do_fork)函数完成内核的创建, 其中在进程的信息创建完毕后, 就可以使用 wake_up_new_task 将进程唤醒并添加到就绪队列中等待调度. 代码参见kernel/fork.c, line 1755

3.4 check_preempt_curr

wake_up_new_task 中唤醒进程时, 内核使用全局 check_preempt_curr 看看是否进程可以抢占当前进程可以抢占当前运行的进程.

1

    check_preempt_curr(rq, p, WF_FORK);1

函数定义在kernel/sched/core.c, line 905

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    const struct sched_class *class;

    if (p->sched_class == rq->curr->sched_class)
    {
        rq->curr->sched_class->check_preempt_curr(rq, p, flags);
    }
    else
    {
        for_each_class(class) {
            if (class == rq->curr->sched_class)
                break;
            if (class == p->sched_class) {
                resched_curr(rq);
                break;
            }
        }
    }

    /*
     * A queue event has occurred, and we're going to schedule.  In
     * this case, we can save a useless back to back clock update.
     */
    if (task_on_rq_queued(rq->curr) && test_tsk_need_resched(rq->curr))
        rq_clock_skip_update(rq, true);
}123456789101112131415161718192021222324252627

4 无效唤醒

4.1 无效唤醒的概念

几乎在所有的情况下, 进程都会在检查了某些条件之后, 发现条件不满足才进入睡眠. 可是有的时候进程却会在判定条件为真后开始睡眠, 如果这样的话进程就会无限期地休眠下去, 这就是所谓的无效唤醒问题.

在操作系统中, 当多个进程都企图对共享数据进行某种处理, 而最后的结果又取决于进程运行的顺序时, 就会发生竞争条件, 这是操作系统中一个典型的问题, 无效唤醒恰恰就是由于竞争条件导致的.

设想有两个进程 A 和 B, A 进程正在处理一个链表, 它需要检查这个链表是否为空, 如果不空就对链表里面的数据进行一些操作, 同时 B 进程也在往这个链表添加节点. 当这个链表是空的时候, 由于无数据可操作, 这时 A 进程就进入睡眠, 当 B 进程向链表里面添加了节点之后它就唤醒 A 进程, 其代码如下:

A 进程:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

spin_lock(&list_lock);
if(list_empty(&list_head))
{
    spin_unlock(&list_lock);
    set_current_state(TASK_INTERRUPTIBLE);
    schedule();
    spin_lock(&list_lock);
}
/* Rest of the code ... */
spin_unlock(&list_lock);
}1234567891011

B 进程:

1
2
3
4

spin_lock(&list_lock);
list_add_tail(&list_head, new_node);
spin_unlock(&list_lock);
wake_up_process(A);1234

这里会出现一个问题，假如当 A 进程执行到第 4 行后第 5 行前的时候, B 进程被另外一个处理器调度投入运行. 在这个时间片内, B 进程执行完了它所有的指令, 因此它试图唤醒 A 进程, 而此时的 A 进程还没有进入睡眠, 所以唤醒操作无效.

在这之后, A 进程继续执行, 它会错误地认为这个时候链表仍然是空的, 于是将自己的状态设置为 TASK_INTERRUPTIBLE 然后调用 schedule()进入睡眠. 由于错过了 B 进程唤醒, 它将会无限期的睡眠下去, 这就是无效唤醒问题, 因为即使链表中有数据需要处理, A 进程也还是睡眠了.

4.2 无效唤醒的原因

如何避免无效唤醒问题呢?

我们发现无效唤醒主要发生在检查条件之后和进程状态被设置为睡眠状态之前, 本来 B 进程的 wake_up_process 提供了一次将 A 进程状态置为 TASK_RUNNING 的机会，可惜这个时候 A 进程的状态仍然是 TASK_RUNNING，所以 wake_up_process 将 A 进程状态从睡眠状态转变为运行状态的努力没有起到预期的作用.

4.3 避免无效抢占

要解决这个问题, 必须使用一种保障机制使得判断链表为空和设置进程状态为睡眠状态成为一个不可分割的步骤才行, 也就是必须消除竞争条件产生的根源, 这样在这之后出现的 wake_up_process 就可以起到唤醒状态是睡眠状态的进程的作用了.

找到了原因后, 重新设计一下 A 进程的代码结构, 就可以避免上面例子中的无效唤醒问题了.

A 进程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if(list_empty(&list_head))
{
    spin_unlock(&list_lock);
    schedule();
    spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);1234567891011

可以看到，这段代码在测试条件之前就将当前执行进程状态转设置成 TASK_INTERRUPTIBLE 了, 并且在链表不为空的情况下又将自己置为 TASK_RUNNING 状态.

这样一来如果 B 进程在 A 进程进程检查了链表为空以后调用 wake_up_process, 那么 A 进程的状态就会自动由原来 TASK_INTERRUPTIBLE 变成 TASK_RUNNING, 此后即使进程又调用了 schedule, 由于它现在的状态是 TASK_RUNNING, 所以仍然不会被从运行队列中移出, 因而不会错误的进入睡眠，当然也就避免了无效唤醒问题.

5 Linux 内核的例子

5.1 一个最基本的例子

在 Linux 操作系统中, 内核的稳定性至关重要, 为了避免在 Linux 操作系统内核中出现无效唤醒问题, Linux 内核在需要进程睡眠的时候应该使用类似如下的操作:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/* ‘q’是我们希望睡眠的等待队列 */
DECLARE_WAITQUEUE(wait,current);
add_wait_queue(q, &wait);
set_current_state(TASK_INTERRUPTIBLE);

/* 或TASK_INTERRUPTIBLE */
while(!condition) /* ‘condition’ 是等待的条件*/
schedule();
set_current_state(TASK_RUNNING);
remove_wait_queue(q, &wait);12345678910

上面的操作, 使得进程通过下面的一系列步骤安全地将自己加入到一个等待队列中进行睡眠: 首先调用 DECLARE_WAITQUEUE 创建一个等待队列的项, 然后调用 add_wait_queue()把自己加入到等待队列中, 并且将进程的状态设置为 TASK_INTERRUPTIBLE 或者 TASK_INTERRUPTIBLE.

然后循环检查条件是否为真: 如果是的话就没有必要睡眠, 如果条件不为真, 就调用 schedule

当进程检查的条件满足后, 进程又将自己设置为 TASK_RUNNING 并调用 remove_wait_queue 将自己移出等待队列.

从上面可以看到, Linux 的内核代码维护者也是在进程检查条件之前就设置进程的状态为睡眠状态, 然后才循环检查条件. 如果在进程开始睡眠之前条件就已经达成了, 那么循环会退出并用 set_current_state 将自己的状态设置为就绪, 这样同样保证了进程不会存在错误的进入睡眠的倾向, 当然也就不会导致出现无效唤醒问题.

内核中有很多地方使用了避免无效唤醒的时候, 最普遍的地方是内核线程的, 因为内核线程的主要功能是辅助内核完成一定的工作的, 大多数情况下他们处于睡眠态, 当内核发现有任务要做的时候, 才会唤醒它们.

2 号进程的例子-避免无效抢占

下面让我们用 linux 内核中的实例来看看 Linux 内核是如何避免无效睡眠的, 我还记得 2 号进程吧, 它的主要工作就是接手内核线程 kthread 的创建, 其工作流程函数是 kthreadd

代码在kernel/kthread.c, kthreadd 函数, line L514

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

for (;;) {
    set_current_state(TASK_INTERRUPTIBLE);
    if (list_empty(&kthread_create_list))
        schedule();
    __set_current_state(TASK_RUNNING);

    spin_lock(&kthread_create_lock);
    /*  ==do_something start==  */
    while (!list_empty(&kthread_create_list)) {
        struct kthread_create_info *create;

        create = list_entry(kthread_create_list.next,
                    struct kthread_create_info, list);
        list_del_init(&create->list);
        spin_unlock(&kthread_create_lock);

        create_kthread(create);
        /*  ==do_something end == */

        spin_lock(&kthread_create_lock);
    }
    spin_unlock(&kthread_create_lock);12345678910111213141516171819202122

5.2 kthread_worker_fn

kthread_worker/kthread_work 是一种内核工作的更好的管理方式, 可以多个内核线程在同一个 worker 上工作, 共同完成 work 的工作, 有点像线程池的工作方式.

内核提供了 kthread_worker_fn 函数一般作为 kthread_create 或者 kthread_run 函数的 threadfn 参数运行, 可以将多个内核线程附加的同一个 worker 上面，即将同一个 worker 结构传给 kthread_run 或者 kthread_create 当作 threadfn 的参数就可以了.

其 kthread_worker_fn 函数作为 worker 的主函数框架, 也包含了避免无效唤醒的代码, kernel/kthread.c, kthread_worker_fn 函数, line573, 如下所示

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int kthread_worker_fn(void *worker_ptr)
{
    /* ......*/
    set_current_state(TASK_INTERRUPTIBLE);  /* mb paired w/ kthread_stop */

    if (kthread_should_stop()) {
        __set_current_state(TASK_RUNNING);
        spin_lock_irq(&worker->lock);
    worker->task = NULL;
    spin_unlock_irq(&worker->lock);
    return 0;
    }
    /* ......*/
}1234567891011121314

此外内核的__kthread_parkme 函数中也包含了类似的代码

6 总结

通过上面的讨论, 可以发现在 Linux 中避免进程的无效唤醒的关键是

• 在进程检查条件之前就将进程的状态置为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE
• 并且如果检查的条件满足的话就应该将其状态重新设置为 TASK_RUNNING.

这样无论进程等待的条件是否满足, 进程都不会因为被移出就绪队列而错误地进入睡眠状态, 从而避免了无效唤醒问题.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

set_current_state(TASK_INTERRUPTIBLE);
spin_lock(&list_lock);
if(list_empty(&list_head))
{
    spin_unlock(&list_lock);
    schedule();
    spin_lock(&list_lock);
}
set_current_state(TASK_RUNNING);
/* Rest of the code ... */
spin_unlock(&list_lock);

参考资料

• https://blog.csdn.net/gatieme/article/details/52068061
• https://blog.csdn.net/gatieme/article/details/106315848