linux内核笔记（三）进程的调度

发表于 2024/03/24

作者 Symbol Who

21 分钟阅读

进程的调度

概念

内存中保存了对每个进程的唯一描述，并通过若干结构与其他进程连接起来。内核必须提供一种方法，在各个进程之间尽可能公平地共享CPU时间，而同时又要考虑不同的任务优先级，而这就是调度器的目标。

调度器的一般原理是，按所能分配的计算能力，向系统中的每个进程提供最大的公平。如果通过轮流运行各个进程来模拟多任务（现实情况是CPU数目总比要运行的进程数目少），那么当前运行的进程，其待遇显然好于那些等待运行的进程，即等待的进程受到了不公平的对待。不公平的程度正比于等待时间。调度器会挑选具有最高等待时间的进程提供CPU时间以均匀分布资源给所有进程。

虚拟时间是完全公平调度的情况下进程将会得到的CPU时间的度量，该时间慢于实际时间，虚拟时间的速度依赖于等待队列中的进程数量。例如现实时间过去了20秒，有4个进程在等待运行，虚拟时间为5秒（即为每个线程如果轮流执行将得到5秒的运行时间）。内核使用虚拟时间减去等待时间来排序红黑树中的进程。

在进程得到cpu运行时，等待时间会减去它已经运行的时间，这样该进程在选择队列中会往右边一点，给其他进程留出运行机会。

调度器的策略还需要考虑考虑另外两个点：

进程的不同优先级（nice 值）必须考虑，更重要的进程必须比次要进程更多的CPU时间份额。
进程不能切换得太频繁，因为上下文切换具有一定的开销。

数据结构

进程相关结构

  
struct task_struct {
  ...
  /* 
  采用了3个成员来表示进程的优先级：prio 和normal_prio 表示动态优先级，static_prio表示进程的静态优先级。
  静态优先级是进程启动时分配的优先级。它可以用nice和sched_setscheduler系统调用修改，否则在进程运行期间会一直保持恒定。
  normal_priority表示基于进程的静态优先级和调度策略计算出的优先级。因此，即使普通进程和实时进程具有相同的静态优先级，其normal_priority也是不同的。进程分支时，子进程会继承普通优先级。
  调度器考虑的优先级则保存在prio。由于在某些情况下内核需要暂时提高进程的优先级，因此需要第3个成员来表示。由于这些改变不是持久的，因此静态和普通优先级不受影响。
  */
  int prio, static_prio, normal_prio;
  unsigned int rt_priority;             //实时进程的优先级。
  const struct sched_class *sched_class;//进程所属的调度器类
  /*
  调度器不限于调度进程，还可以处理更大的实体。调度器设计为处理可调度的实体，在调度器看来各个进程必须也像是这样的实体。一个实体由sched_entity 的一个实例表示。
  */
  struct sched_entity se;
  struct sched_rt_entity rt;            //用于实时调度器调度的实例表示
  ...
  /*
    进程的调度策略：
    SCHED_NORMAL 普通进程，通过完全公平调度器来处理。
    SCHED_BATCH、SCHED_IDLE 用于次要的进程，也通过完全公平调度器来处理。
    SCHED_RR、SCHED_FIFO 用于实现软实时进程。SCHED_RR 实现了一种循环方法，而SCHED_FIFO 则使用先进先出机制。这些由实时调度器类处理
  */
  unsigned int policy;
  cpumask_t cpus_allowed;               //位域，在多处理器系统上使用，用来限制进程可以在哪些CPU上运行
  ...

}

调度器类

  
struct sched_class {
  /*
  对各个调度类，都必须提供此实例。调度类之间的层次结构是平坦的：实时进程最重要，在完全公平进程之前处理；而完全公平进程则优先于空闲进程；空闲进程只有CPU无事可做时才处于活动状态。next 成员将不同调度类的sched_class实例，按上述顺序连接起来。要注意这个层次结构在编译时已经建立：没有在运行时动态增加新调度器类的机制。
  */
  const struct sched_class *next;
  /* 向就绪队列添加一个新进程。在进程从睡眠状态变为可运行状态时，即发生该操作 */
  void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  /* enqueue_task的逆向操作，将一个进程从就绪队列去除。进程从可运行状态切换到不可运行状态时，就会发生该操作。 */
  void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
  /* sched_yield系统调用即调用此函数，进程想要自愿放弃对CPU执行权时使用 */
  void (*yield_task) (struct rq *rq);
  /* 用于实现优先级调度或抢占式调度策略。它用于强制当前正在运行的任务放弃CPU执行权，并将CPU执行权交给指定的目标任务 */
  bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
  /* 检查当前运行的进程是否应该被抢占，以确保更高优先级的进程能够及时运行 */
  void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
  /* 根据调度策略、优先级、任务状态等因素，从就绪队列中选择一个适当的任务 */
  struct task_struct * (*pick_next_task) (struct rq *rq);
  /* 用户处理当前任务的结束（比如当前任务的一些清理和统计工作等），以确保任务切换的顺利进行 */
  void (*put_prev_task) (struct rq *rq, struct task_struct *p);
  ...
}

就绪队列

  
struct rq {
  ...
  
  unsigned long nr_running;                 //队列上可运行进程的数目，不考虑其优先级或调度类。
  #define CPU_LOAD_IDX_MAX 5                
  unsigned long cpu_load[CPU_LOAD_IDX_MAX]; //跟踪负载状态
  /* 就绪队列的负载情况，用于系统的负载均衡、任务调度和资源分配等方面，就绪队列的虚拟时钟的速度即基于该信息 */
  struct load_weight load;
  ...
  struct cfs_rq cfs;                        //用于完全公平调度器的队列
  struct rt_rq rt;                          //用于实时度器的队列
  struct task_struct *curr, *idle, *stop;   //分别指向当前正在运行、空闲、被暂停执行或挂起的任务实例
  ...
  u64 clock;                                //就绪队列自身的时钟
  ...
}

调度实体

  
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;               //进程执行期间虚拟时钟上流逝的时间数量
    /* 进程被撤销CPU执行时间时，其当前sum_exec_runtime值保存到prev_exec_runtime。此后，在进程抢占时又需要该数据。在prev_exec_runtime中保存sum_exec_runtime的值，并不意味着重置sum_exec_runtime！原值保存下来，而sum_exec_runtime 则持续单调增长。 */
    u64 prev_sum_exec_runtime;
    ...
}

优先级的处理

优先级的度量

内核使用一个从0到139表示进程的优先级。值越低，优先级越高。从0到99的范围专供实时进程使用。nice值[-20, +19]映射到范围100到139，如图所示。实时进程的优先级总是比普通进程更高

优先级计算

进程中的静态优先级数值是计算优先级的基础参数，effective_prio函数用来计算task_struct中的prio值。

  
void set_user_nice(struct task_struct *p, long nice)
{
    /* nice不会影响实时线程的优先级，但仍允许设置nice，但直到任务为sched_fifo/sched_rr时才生效 */
    if (task_has_rt_policy(p)) {
        p->static_prio = NICE_TO_PRIO(nice);
        goto out_unlock;
    }
    ...
    p->prio = effective_prio(p);
    ...
}
static int effective_prio(struct task_struct *p)
{
    p->normal_prio = normal_prio(p);
    /* 如果是实时进程或已经提高到实时优先级，则保持优先级不变。否则，返回普通优先级 */
    if (!rt_prio(p->prio))
        return p->normal_prio;
    return p->prio;
}
static inline int normal_prio(struct task_struct *p)
{
    int prio;
    /* 与rt_prio()函数不同，指函数检测是否是实时进程 而后者则检测是否有实时级优先级（非实时进程也许会被内核临时提升到实时优先级，但进程本身不属于实时进程） */
    if (task_has_rt_policy(p))
        /* 如果是实时进程，则更高的rt_priority 值表示更高的实时优先级，与普通进程相比，它不关心static_prio */
        prio = MAX_RT_PRIO-1 - p->rt_priority;
    else
        prio = __normal_prio(p);// return p->static_prio;
    return prio;
}

进程类型/优先级策略对应的优先级度量指标表格

类型	static_prio	normal_prio	prio
非实时进程	static_prio	static_prio	static_prio
实时进程	static_prio	MAX_RT_PRIO-1 - rt_priority	prio不变
优先级提高的非实时进程	static_prio	static_prio	prio不变

负载权重的计算

进程每降低一个nice值，则多获得10%的CPU时间，每升高一个nice值，则放弃10%的CPU时间。为执行该策略，内核将优先级转换为权重值使用数组维护了一张转换表。

  
//各元素之间的乘数因子是1.25
static const int prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

e.g.

进程$A$与$B$的nice都为0，权重计算为

\[A_w=B_w=1024/1024+1024=0.5\]

进程$A$与$B$的权重各占$50\%$。如果进程B的优先级加1，那么其CPU份额应该减少10%。即

\[B_w=(1024/1.25\approx820)/(1024+820)\approx0.45\] \[A_w=1024/(1024+820)\approx0.55\]

这样就产生了10%的差值。

设置权重的逻辑

  
static void set_load_weight(struct task_struct *p)
{
    if (p->policy == SCHED_IDLE) {
        /* SCHED_IDLE进程得到的权重最小 */
        p->se.load.weight = WEIGHT_IDLEPRIO;
        /* load.inv_weight目的是保存以位运算计算除法时的乘法因子 */
        p->se.load.inv_weight = WMULT_IDLEPRIO;
        return;
    }

    p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
    p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

核心调度器

周期调度器

如果系统正在活动中，内核会按照频率HZ自动调用该函数。

  
void scheduler_tick(void)
{
    //管理调度相关的一些统计指标
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;
    ...
    //将调度工作委托给当前调度器类的task_tick函数
    curr->sched_class->task_tick(rq, curr, 0);
    raw_spin_unlock(&rq->lock);
    perf_event_task_tick();

}

主调度器

在内核中的许多场景，如抢占式调度、进程等待、进程睡眠、任务结束时，都需要调用主调度的核心函数schedule()，还有一个场景是系统调用后，如果进程设置了TIF_NEED_RESCHED，内核也会调用schedule()。该函数假定当前活动进程一定会被另一个进程取代。

  
/*
asmlinkage宏会告诉编译器和链接器不要做额外的处理，因为这个函数的调用约定与普通的C函数不同。在 x86架构上，它会告诉编译器使用寄存器来传递函数参数，而不是通过堆栈。这样做的目的是为了提高性能，避免了函数参数的压栈和出栈操作。使用 asmlinkage 修饰的函数通常是一些内核内部的底层函数，比如系统调用处理函数、中断处理函数等。这些函数不会直接从用户空间被调用，而是由内核自身的其他部分调用，因此它们需要使用特殊的调用约定。
__sched 是内核中用来声明调度相关特性的修饰符。它通常用于函数声明或者变量声明之前，表示该函数或者变量与调度器有关
*/
asmlinkage void __sched schedule(void)
{
need_resched:
    //关闭内核抢占
    preempt_disable();
    cpu = smp_processor_id();
    rq = cpu_rq(cpu);
    rcu_note_context_switch(cpu);
    prev = rq->curr;
    ...
    //获取自旋锁，并禁用当前CPU的中断。这样做是为了确保在获取锁之后，不会被其他中断打断，从而保证临界区的完整性和一致性。
    raw_spin_lock_irq(&rq->lock);
    switch_count = &prev->nivcsw;
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        if (unlikely(signal_pending_state(prev->state, prev))) {
            //如果进程之前被挂起，但现在接收到信号，那么它必须再次提升为运行进程。
            prev->state = TASK_RUNNING;
        } else {
            //否则将进程退出运行队列，并唤醒其他可并行的进程
            if (prev->flags & PF_WQ_WORKER) {
                struct task_struct *to_wakeup;
                to_wakeup = wq_worker_sleeping(prev, cpu);
                if (to_wakeup)
                    try_to_wake_up_local(to_wakeup);
            }
            //deactivate_task实质上最终调用了sched_class->dequeue_task
            deactivate_task(rq, prev, DEQUEUE_SLEEP);
            //处理自旋锁  防止死锁
            if (blk_needs_flush_plug(prev)) {
                raw_spin_unlock(&rq->lock);
                blk_schedule_flush_plug(prev);
                raw_spin_lock(&rq->lock);
            }
        }
        switch_count = &prev->nvcsw;
    }
    ...
    //从就绪队列中选择下一个进程
    next = pick_next_task(rq);
    clear_tsk_need_resched(prev);
    rq->skip_clock_update = 0;
    //不见得必然选择一个新进程。也可能其他进程都在睡眠，当前只有一个进程能够运行，这样它自然就被留在CPU上。但如果已经选择了一个新进程，那么必须准备并执行硬件级的进程切换
    if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;
        context_switch(rq, prev, next); /* unlocks the rq */
        cpu = smp_processor_id();
        rq = cpu_rq(cpu);
    } else
        raw_spin_unlock_irq(&rq->lock);
    ...
    /*
    在没有执行上下文切换时，它在schedule 函数的末尾直接执行。但如果已经执行了上下文切换，当前进程会正好在这以前停止运行，新进程已经接管了CPU。但稍后在前一进程被再次选择运行时，它会刚好在这一点上恢复执行。在这种情况下，由于prev不会指向正确的进程，所以需要通过current和test_thread_flag找到当前线程。
    */
    if (need_resched()) //return unlikely(test_thread_flag(TIF_NEED_RESCHED));
        goto need_resched;
    ...
}

上下文切换的prev和next变化

对于进程切换之后的next和prev指向是不同的，可以参照上图理解：进程A提供给switch_to的参数是A和B，但恢复执行后prev却是C

Linux, task

Linux task

本文由作者按照 CC BY 4.0 进行授权