枕石的个人博客
文章 标签 分类 关于
枕石的个人博客

Contents

Linux内核调度:调度时机与任务选择

 included in Linux内核
   4289 words   9 minutes 

Linux内核调度器是操作系统的核心，它负责决定哪个进程在何时、运行多久。理解其工作原理的关键在于回答两个问题：1. 何时触发调度？ 和 2. 调度时选择哪个任务？ 本文将深入探讨这两个问题，解析其背后的机制、代码和具体场景。

进程的状态与切换

在深入调度机制之前，先简要回顾一下Linux中进程的基本状态：

  • 操作系统理论层面进程状态划分：

    • 就绪（Ready）：进程已准备好运行，等待CPU分配。
    • 运行（Running）：进程正在使用CPU执行指令。
    • 阻塞（Blocked）：进程等待某个事件（如I/O完成、锁释放）而无法继续执行。
    • 创建（New）：进程正在被创建，还未进入就绪状态。
    • 终止（Terminated）：进程已完成执行，等待被系统回收。

  • 五种进程状态的转换：

    • 就绪 → 运行：处于就绪态的进程被调度后，获得CPU资源，进程转换为运行态。
    • 运行 → 就绪：处于运行态的进程在CPU时间片用尽后，不得不让出CPU，转换为就绪态；在可抢占的操作系统中，当有更高优先级的进程就绪时，调度程序也会将当前运行的进程切换回就绪态，以便让更高优先级的进程运行。
    • 运行 → 阻塞：处于运行态的进程在等待某个事件（如I/O操作完成、锁释放）时，无法继续执行，转换为阻塞态。
    • 阻塞 → 就绪：处于阻塞态的进程在等待的事件发生后，中断处理程序把进程状态变为就绪态，等待CPU分配。

  • Linux内核中的进程状态：

    <!-- From linux 5.8 -->
/* Used in tsk->state: */
#define TASK_RUNNING			0x0000
#define TASK_INTERRUPTIBLE		0x0001
#define TASK_UNINTERRUPTIBLE		0x0002
#define __TASK_STOPPED			0x0004
#define __TASK_TRACED			0x0008
/* Used in tsk->exit_state: */
#define EXIT_DEAD			0x0010
#define EXIT_ZOMBIE			0x0020
#define EXIT_TRACE			(EXIT_ZOMBIE | EXIT_DEAD)
/* Used in tsk->state again: */
#define TASK_PARKED			0x0040
#define TASK_DEAD			0x0080
#define TASK_WAKEKILL			0x0100
#define TASK_WAKING			0x0200
#define TASK_NOLOAD			0x0400
#define TASK_NEW			0x0800
#define TASK_STATE_MAX			0x1000

/* Convenience macros for the sake of set_current_state: */
#define TASK_KILLABLE			(TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED			(TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_TRACED			(TASK_WAKEKILL | __TASK_TRACED)

#define TASK_IDLE			(TASK_UNINTERRUPTIBLE | TASK_NOLOAD)

/* Convenience macros for the sake of wake_up(): */
#define TASK_NORMAL			(TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE)

/* get_task_state(): */
#define TASK_REPORT			(TASK_RUNNING | TASK_INTERRUPTIBLE | \
                    TASK_UNINTERRUPTIBLE | __TASK_STOPPED | \
                    __TASK_TRACED | EXIT_DEAD | EXIT_ZOMBIE | \
                    TASK_PARKED)

第一部分：调度时机 —— 何时调用schedule()

schedule() 函数是CPU从一个任务切换到另一个任务的核心枢纽。每当内核认为当前运行的任务应该暂停，以便让另一个任务运行时，就会调用它。

对 schedule() 的调用可以分为两大类：直接调用（自愿调度）和通过标志位的间接调用（强制抢占）。

1. 直接调用：自愿性调度（Voluntary Preemption / Blocking）

这是 schedule() 被调用的最常见场景。当前正在运行的任务意识到它现在无法继续工作，因为它需要等待某个事件或资源。因此，它会自愿地放弃CPU。

内核代码中的典型模式是：

  1. 将当前任务的状态设置为 TASK_INTERRUPTIBLE（可中断睡眠）或 TASK_UNINTERRUPTIBLE（不可中断睡眠）。
  2. 调用 schedule() 函数。

当任务等待的事件发生后（例如，它等待的数据到达了），它会被唤醒，状态重新变回 TASK_RUNNING，从而有资格再次被调度器选中运行。

你几乎可以在内核中所有涉及“等待”的子系统中找到对 schedule() 的直接调用：

  • 等待I/O操作： 当一个进程调用 read() 读取文件或套接字，但数据尚未准备好时，内核的文件系统或网络代码会将其置于休眠状态并调用 schedule()。

    • 代码位置示例： kernel/sched/wait.c 中的 io_schedule() 等函数。

  • 等待锁： 如果一个任务试图获取一个已经被其他任务持有的信号量（semaphore）或互斥锁（mutex），它就必须等待。

    • 代码位置示例： kernel/locking/mutex.c (在 mutex_lock() 函数中) 和 kernel/locking/semaphore.c (在 down() 函数中)。核心的锁逻辑会把任务加入到该锁的等待队列，然后调用 schedule()。

  • 等待定时器或延时： 当进程调用 sleep()、nanosleep() 或带有超时的 select() 时。

    • 代码位置示例： kernel/time/hrtimer.c。内核会设置一个定时器，并将任务休眠，直到定时器触发。

  • 等待内存管理事件： 在处理缺页中断（page fault）时，如果需要的内存页必须从磁盘（交换空间或文件）中读取，内存管理代码会发起I/O请求，将当前任务放入等待队列并休眠，然后调用 schedule() 以便在漫长的磁盘操作期间运行其他任务。

    • 代码位置示例： mm/memory.c, mm/filemap.c。

2. 间接调用：非自愿性抢占（Involuntary Preemption）

在这种情况下，正在运行的任务并没有自愿放弃CPU。内核强制进行一次重新调度，因为发生了更重要的事件。这正是Linux作为抢占式操作系统的体现。

这个过程通常不会在事件处理程序（如中断处理）中直接调用 schedule()。取而代之的是，它会给当前任务设置一个名为 TIF_NEED_RESCHED 的标志位（意为“线程信息标记 - 需要重新调度”）。

然后，内核会在一些安全的时间点（例如，从中断或系统调用返回时）检查这个标志位。只有当该标志位被设置时，才会去调用 schedule()。

TIF_NEED_RESCHED 标志位主要在以下两种情况下被设置：

  • 时间片用尽（定时器中断）： 每隔几毫秒，硬件定时器就会触发一次中断。这个“时钟节拍”（timer tick）的中断处理程序会调用 scheduler_tick() 函数。

    1. scheduler_tick() 会减少当前任务的剩余时间片。
    2. 如果时间片耗尽，scheduler_tick() 就会调用 set_tsk_need_resched() 来设置当前任务的 TIF_NEED_RESCHED 标志。
    3. 当时钟中断处理结束，内核准备将控制权交还给用户任务时，它会检查这个标志位。发现标志被设置，内核就会调用 schedule()，而不是恢复执行原来的任务。
    • 代码位置示例： kernel/sched/core.c 中的 scheduler_tick()。

  • 唤醒了更高优先级的任务： 一个中断到达（例如，收到了一个网络包，或磁盘读取完成）。中断处理程序唤醒了一个正在等待此事件的任务（通过 wake_up_process() 之类的函数）。

    1. 唤醒逻辑（在 try_to_wake_up() 中）会比较新唤醒的任务的优先级和当前正在运行的任务的优先级。
    2. 如果新唤醒的任务优先级更高（例如，一个实时任务被唤醒，而当前运行的是一个普通的CFS任务），唤醒逻辑就会为当前任务设置 TIF_NEED_RESCHED 标志。
    3. 与时钟中断一样，当中断处理完成时，内核会检查此标志并调用 schedule()，从而抢占低优先级任务，让位给刚就绪的高优先级任务。
    • 代码位置示例： kernel/sched/core.c 中的 try_to_wake_up()。

3. 主动出让（Explicit Yielding）

这是一种混合情况，任务主动请求调度器运行其他任务，即便它自己的时间片还没有用完。

  • sched_yield() 系统调用： 用户空间的程序可以调用 sched_yield() 来主动放弃当前时间片的剩余部分。这个系统调用的内核实现会非常直接地调用 schedule()。

    • 代码位置示例： kernel/sched/core.c 中的 sys_sched_yield() 函数。

  • cond_resched()： 这是内核内部使用的函数。如果一个内核代码路径执行一个非常长的循环而从不阻塞，它可能会饿死其他任务。为防止这种情况，这样的循环会周期性地调用 cond_resched()，这个函数的作用就是检查 TIF_NEED_RESCHED 标志是否被设置，如果是，就调用 schedule()。

    • 代码位置示例： 在内核代码中被广泛使用，例如在某些文件系统和VFS代码的长循环中。

总结表格

调度原因类型机制内核代码位置示例
等待I/O、锁、定时器自愿直接调用 schedule()io_schedule(), mutex_lock()
时间片用尽非自愿/抢占时钟中断设置 TIF_NEED_RESCHED 标志scheduler_tick() in kernel/sched/core.c
更高优先级的任务被唤醒非自愿/抢占唤醒逻辑设置 TIF_NEED_RESCHED 标志try_to_wake_up() in kernel/sched/core.c
用户请求出让CPU自愿来自系统调用的直接调用sys_sched_yield() in kernel/sched/core.c
内核长循环需要出让自愿cond_resched() 检查标志并可能调用遍布于内核源码中

第二部分：任务选择 —— pick_next_task的决策逻辑

当schedule()被触发后，它的核心任务是调用pick_next_task()函数来决定下一个应该运行谁。这个决策过程是基于一个优雅且严格的优先级层次结构。

1. 架构基础：struct sched_class

Linux将不同的调度算法（如实时、公平）封装在struct sched_class结构中。它定义了一套标准的函数接口，任何调度算法都必须实现。

struct sched_class {
    // 关键成员：指向下一个优先级更低的调度类
    const struct sched_class *next;

    // 关键函数：从本类的运行队列中挑选下一个任务
    struct task_struct *(*pick_next_task)(struct rq *rq);

    // 其他函数，如入队、出队、时钟节拍处理等...
    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    // ...
};

next指针是整个设计的核心，它将所有调度类链接成一个单向链表，定义了它们的优先级。

2. 调度类优先级层次

这个链表的顺序是静态定义的，代表了不可逾越的优先级： stop_sched_class (最高优先级，用于停止CPU) -> dl_sched_class (Deadline调度) -> rt_sched_class (实时调度) -> fair_sched_class (CFS公平调度) -> idle_sched_class (最低优先级，在CPU空闲时运行)

3. pick_next_task的决策算法

此函数的逻辑清晰地反映了上述优先级。

代码解析 - 优化路径 (Fast Path):

if (likely((prev->sched_class == &idle_sched_class ||
        prev->sched_class == &fair_sched_class) &&
       rq->nr_running == rq->cfs.h_nr_running)) {

    p = pick_next_task_fair(rq, prev, rf);
    // ...
    if (!p) {
        p = pick_next_task_idle(rq);
    }
    return p;
}
  • 目的：在大多数系统中，几乎所有任务都是普通CFS任务。此优化旨在避免每次都从头遍历整个优先级链表。
  • 条件解读：rq->nr_running == rq->cfs.h_nr_running 这个判断至关重要。它检查当前CPU的运行队列（rq）中的总可运行任务数是否等于CFS类别的可运行任务数。如果相等，意味着当前CPU上没有任何可运行的实时或Deadline任务。
  • 行为：如果条件成立，代码会直接调用CFS调度器的pick_next_task_fair。如果CFS没有任务可选，则直接选择空闲任务。这极大地提高了常见场景下的调度效率。

代码解析 - 通用路径 (General Path):

如果优化路径的条件不满足（意味着有更高优先级的任务存在），代码将执行标准遍历流程。

restart:
    // ...
    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }

    BUG();
  • for_each_class(class): 这个宏展开后是一个for循环，从最高优先级的stop_sched_class开始，沿着next指针遍历。
  • 短路机制：if (p) return p; 是该逻辑的核心。一旦某个调度类的pick_next_task函数返回了一个有效的任务指针（非NULL），整个pick_next_task函数就会立即返回这个任务。
  • 运行示例:
    1. 假设一个CPU的运行队列中同时有一个实时（RT）任务和多个公平（CFS）任务。
    2. pick_next_task被调用，优化路径失败，进入通用路径。
    3. 循环开始。stop_class->pick_next_task()被调用，返回NULL。
    4. dl_class->pick_next_task()被调用，返回NULL。
    5. rt_class->pick_next_task()被调用。它从自己的运行队列中找到了那个可运行的RT任务，并返回其指针。
    6. if (p) 条件为真，pick_next_task函数立即带着这个RT任务返回。
    7. fair_sched_class的pick_next_task根本没有机会被调用。这完美地实现了RT任务对CFS任务的绝对抢占。

总结

Linux的调度系统是一个设计精良的工程典范，其运作可以归纳为：

  1. 调度触发：由任务自愿等待资源（直接调用schedule）或被更高优先级事件（通过TIF_NEED_RESCHED标志间接触发schedule）来启动调度过程。
  2. 任务选择：一旦调度开始，pick_next_task函数会严格按照stop -> deadline -> rt -> fair -> idle的优先级链进行查找。高优先级调度类享有绝对优先权，确保了系统的实时性和响应性，同时通过优化路径保证了通用场景下的高效率。
Updated on 2025-10-11
 Linux内核, 进程调度
Back | Home