# 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中挑选出下一个合适的任务来执行，下一节中我们将探讨调度时机的问题。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/cfs-sched/logic-preempt.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.