# 2.6.2.5 调度逻辑 - 任务抢占

所谓抢占，就是停止当前正在执行的任务，换另一个任务来执行。导致这种情况发生的原因很多，例如当前任务已经运行了太长时间，需要让出CPU; 用户修改了任务优先级，导致当前任务应该被换下；或者优先级更高的任务被唤醒，需要立刻开始运行。但当这种情况发生时，调度器并不会真的立刻切换任务，而是调用 `resched_curr()` 函数为当前任务设置一个叫着 `TIF_NEED_RESCHED` 的标记位，该函数的主要逻辑如下：

```
/* file: kernel/sched/core.c */
void resched_curr(struct rq *rq) {
struct task_struct *curr = rq->curr;
int cpu;

lockdep_assert_held(&rq->lock);

/* 如果当前任务已经设置了 TIF_NEED_RESCHED 标记位，则返回 */
if (test_tsk_need_resched(curr))
return;

cpu = cpu_of(rq);

if (cpu == smp_processor_id()) {
/* 设置标记位 */
set_tsk_need_resched(curr);
set_preempt_need_resched();
return;
}
}
```

调用该函数的地方非常多，这里主要介绍两个典型场景：

**1. 任务运行时间耗尽**

经过前面的讨论，我们知道任务在每个调度周期内的时间配额是有限的，当任务耗尽了该时间片之后就需要让出CPU, 以便给其它任务提供运行的机会。上一节在讨论周期性调度时，我们看到函数 `entity_tick` 最后调用了 `check_preempt_tick`, 后者就是检查任务时间是否耗尽的函数，我们来看一下它的实现：

```
/* file: kernel/sched/fair.c */
static void check_preempt_tick(struct cfs_rq *cfs_rq,
                        struct sched_entity *curr) {
unsigned long ideal_runtime, delta_exec;
struct sched_entity *se;
s64 delta;

/* 计算出当前任务在一个调度周期内的时间配额 */
ideal_runtime = sched_slice(cfs_rq, curr);
/* 计算出当前任务已经运行了多长时间 */
delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
if (delta_exec > ideal_runtime) {
/* 如果运行时长已经超过了任务自己的时间配额，则对任务进行抢占 */
resched_curr(rq_of(cfs_rq));
return;
}

/* 避免任务抢占发生得太过频繁 */
if (delta_exec < sysctl_sched_min_granularity)
return;

/* 从cfs_fq中挑出vruntime最小的任务，即红黑树中最左子节点；并计算出当前任务与该任务的vruntime的差值
*/
se = __pick_first_entity(cfs_rq);
delta = curr->vruntime - se->vruntime;

/* 如果当前任务的vruntime依然小于红黑树中所有任务的vruntime, 则不发生抢占 */
if (delta < 0)
return;

/* 如果已经多除了相当部分，则可以抢占当前任务了 */
if (delta > ideal_runtime)
resched_curr(rq_of(cfs_rq));
}
```

**2. 新任务被创建**

新任务创建后可能需要立刻投入运行，这时候也需要检查抢占情况。从用户态（user mode）来看，Linux的新任务通过系统调用 `clone()` 创建，其最终会调用到 `kernel_clone` 方法，该方法中与调度相关的逻辑裁剪如下：

```
/* file: kernel/fork.c */

pid_t kernel_clone(struct kernel_clone_args *args) {
struct task_struct *p;
pid_t nr;

/* 删除了巨多的代码 */

p = copy_process(NULL, trace, NUMA_NO_NODE, args);

/* 删除了巨多的代码 */
wake_up_new_task(p);

/* 删除了巨多的代码 */
return nr;
}
```

函数 `copy_process` 为新的任务创建并初始化 `task_struct`, 中途会调用函数 `sched_fork` 对与调度相关的字段进行初始化：

```
/* file: kernel/fork.c */
static __latent_entropy struct task_struct *
copy_process(struct pid *pid, int trace, int node,
        struct kernel_clone_args *args) {
struct task_struct *p;
u64 clone_flags = args->flags;

/* 初始化调度相关的数据 */
retval = sched_fork(clone_flags, p);

return p;
}
```

函数 `sched_fork` 与 `wake_up_new_task` 都定义在调度文件 `kernel/sched/core.c` 中，前者用来初始化各种调度相关的字段，而后者用来检查新创建的任务是否需要抢占当前任务，我们这里着重看一下后者的实现：

```
void wake_up_new_task(struct task_struct *p) {
struct rq_flags rf;
struct rq *rq;

p->state = TASK_RUNNING;

/* 最终会调用 sched_class 中的 enqueue_task 将该任务放入队列 */
activate_task(rq, p, ENQUEUE_NOCLOCK);

/* 调用 sched_class.check_preempt_curr 函数 */
check_preempt_curr(rq, p, WF_FORK);

#ifdef CONFIG_SMP
if (p->sched_class->task_woken) {
p->sched_class->task_woken(rq, p);
}
#endif
}
```

函数体中的 `activate_task` 最终会将新任务放入运行队列中，而 `check_preempt_curr` 就是最终判断抢占逻辑的函数。CFS 中实现该方法的函数是 `check_preempt_wakeup`, 仅保留主干逻辑，代码如下：

```
/* file: kernel/sched/fair.c */
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p,
                            int wake_flags) {
struct task_struct *curr = rq->curr;
struct sched_entity *se = &curr->se, *pse = &p->se;
struct cfs_rq *cfs_rq = task_cfs_rq(curr);
int scale = cfs_rq->nr_running >= sched_nr_latency;

if (unlikely(se == pse))
return;

if (test_tsk_need_resched(curr))
return;

/* 如果当前CPU 上正在运行 idle 任务，则任何非 idle 任务都应该发生抢占 */
if (unlikely(task_has_idle_policy(curr)) && likely(!task_has_idle_policy(p)))
goto preempt;

/* Batch and idle tasks do not preempt non-idle tasks (their preemption, is
* driven by the tick) */
if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
return;

/* 不考虑组调度的情况下，该函数为空，因此 se 为当前任务的调度实体 */
find_matching_se(&se, &pse);
/* 更新当前任务的各种时间信息 */
update_curr(cfs_rq_of(se));
BUG_ON(!pse);

/* 判断需不需要用 pse 抢占 se */
if (wakeup_preempt_entity(se, pse) == 1) {
goto preempt;
}

return;

preempt:
/* 设置调度的标记位 */
resched_curr(rq);
}

static int wakeup_preempt_entity(struct sched_entity *curr,
                            struct sched_entity *se) {
s64 gran, vdiff = curr->vruntime - se->vruntime;

/* curr.vruntime 依然小于 se.vruntime, 不抢占 */
if (vdiff <= 0)
return -1;

gran = wakeup_gran(se);
/* 只有se.vruntime相对于curr.vruntime大出一定的范围之后，才发生抢占。gran实际上是1ms对应到se的vruntime,
* 也就是说如果se已经比curr多出了1ms的墙上时间, 那么就可以发生抢占 */
if (vdiff > gran)
return 1;

return 0;
}

static unsigned long wakeup_gran(struct sched_entity *se) {
/* sysctl_sched_wakeup_granularity: 1ms */
unsigned long gran = sysctl_sched_wakeup_granularity;

/* 返回结果就是 1ms 相当于 se 的虚拟时间 */
return calc_delta_fair(gran, se);
}
```

`TIF_NEED_RESCHED` 位被设置之后，调度器在下一次调度发生时就会将该任务换下，并从runqueue中挑选出下一个合适的任务来执行，下一节中我们将探讨调度时机的问题。