进程调度

多任务模式

• 非抢占式多任务

  • 需要进程主动让步

• 抢占式多任务

优先级

• nice优先级
  • 它的范围是-20-19越小优先级越高
• 实时优先级
  • 它的范围是0-99，越大优先级越高

I/O消耗型和处理器消耗型进程

• I/O消耗型，就是说cpu等待外设的输入输出并及时的做出响应，例如：键盘，鼠标
• 处理器消耗型，就是说进程一直占用cpu

CFS（Completely Fair Scheduler，完全公平调度器）

1. 核心概念：vruntime（虚拟运行时间）

• 在 CFS 的世界里，没有固定的“时间片（Time Slice）”概念。它唯一在乎的，是一个叫做 vruntime 的变量。

• 什么是 vruntime： 它是记录一个 task_struct 在 CPU 上实际运行时间的一个计数器。进程在 CPU 上跑得越久，它的 vruntime 就越大。

• CFS 的绝对铁律： 调度器每次挑选下一个要运行的进程时，永远只挑当前 vruntime 最小的那个（也就是历史上享受 CPU 服务最少的那个“最惨”的进程）。

• 结果： 只要你跑了一会儿，你的 vruntime 就会增加，超过别人。于是 CFS 就会把你踢下来，换那个 vruntime 比你小的进程上。大家你追我赶，最终所有进程的 vruntime 会齐头并进，实现“完全公平”。

2. 数据结构：红黑树（Red-Black Tree） 如果系统里有 1000 个进程，CFS 每次都要遍历一遍去找出 vruntime 最小的那个吗？那太慢了。CFS 借用了一个极其高效的数据结构——红黑树。

• 内核把所有处于“就绪状态（TASK_RUNNING）”的 task_struct，按照它们的 vruntime 作为 Key，挂在一棵红黑树上。
• 左边小，右边大： vruntime 越小的进程，越靠近树的左侧；跑得越久的进程，越被发配到树的右侧。
• 极致的效率： CFS 调度器找下一个进程时，连树都不用遍历，直接去拔**整棵树最左下角的那个叶子节点（Leftmost Node）**就行了。这个操作的时间复杂度是极低的，而且内核还会把这个节点缓存起来，拿取速度是 $O(1)$。

3. 如何处理优先级（Nice 值）？

这里产生了一个悖论：既然叫“完全公平”，那系统里那些极其重要的进程（比如控制界面的 X11），和那些不重要跑在后台的进程（比如下载任务），怎么体现出优先级的差别呢？

CFS 的魔法在于：它不改变公平的规则，它改变的是“时间的流速”。

• CFS 引入了权重的概念，将 Linux 中的优先级（Nice 值，-20 到 19）映射成了不同的时间流速：

• 高优先级进程（VIP）： 它的时间流速极慢。它在 CPU 上实际跑了 10 毫秒，CFS 在算账时，只给它的 vruntime 加上 1 毫秒。因为它涨得慢，所以它能长时间霸占红黑树的最左侧，获得更多的 CPU 眷顾。

• 低优先级进程（普通人）： 它的时间流速极快。它在 CPU 上才跑了 1 毫秒，CFS 直接给它的 vruntime 加上 10 毫秒。它的 vruntime 瞬间飙升，立刻就被踢到红黑树的右边排队去了。

什么进程使用task_struct表示了还要整出来一个结构体sched_entity

Linux 调度的基本单位不应该是进程（或者线程）即 task_struct 吗？为什么还要凭空造出一个 sched_entity 出来？这正是 Linux 内核设计的高明之处。

1. 为什么需要 sched_entity？（组调度的魔法）

• 如果内核只调度进程，那直接用 task_struct 挂在红黑树上就行了。但是，现代 Linux 引入了 组调度 (Group Scheduling) 的概念（比如配合 cgroups 使用）。
• 假设有两个用户 A 和 B：

  • 用户 A 运行了 1 个吃 CPU 的进程。

  • 用户 B 运行了 99 个吃 CPU 的进程。

如果按“进程”绝对公平来分配，B 会抢占 99% 的 CPU，A 只能拿到 1%，这显然对 A 不公平。 sched_entity 的出现就是为了解决这个问题： 它既可以代表一个独立的进程，也可以代表一个进程组（cgroup）。CFS 调度器在红黑树里挑人时，其实是在挑 sched_entity。它可能先选中了“用户 B 的进程组”这个大实体，然后再进入这个大实体内部的红黑树，去挑具体的进程。

这种高度抽象的设计，让内核代码极其优雅：不管是调度单个进程还是调度一个组，CFS 用的都是同一套逻辑。

进程的睡眠和唤醒

当一个进程需要等待某个外部事件（比如从磁盘读文件、等待网络数据包、或者获取某个内核信号量）时，它绝对不能在 CPU 上“死循环”傻等，那样太浪费计算资源了（也就是截图里说的“轮询”）。 此时，进程会执行一套标准的退场动作：

1. 改状态： 把自己的状态从“可执行”改成“休眠”。
2. 摘节点：把自己从刚才我们聊的 CFS 红黑树上摘除，这意味着调度器 schedule() 暂时不会再翻它的牌子了。
3. 挂队列： 把自己挂到一个叫做等待队列（Wait Queue）的链表上。这个队列通常和它等待的那个硬件或事件绑定。
4. 让出 CPU： 主动调用 schedule() 函数，通知内核：“我睡了，你让下一个进程上吧”

linux系统中有两种不同的睡眠深度，这在实际系统中非常重要：

TASK_INTERRUPTIBLE（可中断休眠）： 睡得比较“浅”。如果在等数据的过程中，突然收到了一个系统信号（比如你按了 Ctrl+C 发出的 SIGINT），它会被提前唤醒并去处理这个信号，哪怕它要等的数据还没来。

TASK_UNINTERRUPTIBLE（不可中断休眠）： 睡得很“死”。必须死等那个特定的事件发生，谁叫都不醒，连大名鼎鼎的 kill -9 都不好使。这通常发生在进程正与硬件进行极其关键且不能被打断的 I/O 交互时。如果硬件坏了或者驱动写得有问题，进程就会卡在这个状态，变成我们在 top 命令里常看到的 “D 状态”死进程。

唤醒

唤醒通常不会由睡眠的进程自己触发（毕竟它睡着了），而是由外部事件的制造者来触发的

“在事件发生时，对等待队列执行 wake_up() 操作。” 内核提供了一系列 API，最常用的是：

• wake_up(wait_queue_head_t *q)：唤醒队列上的所有进程（或者具有互斥标志的第一个进程）。
• wake_up_interruptible(wait_queue_head_t *q)：只唤醒状态为 TASK_INTERRUPTIBLE 的进程。

当驱动程序调用 wake_up() 时，内核会顺藤摸瓜执行以下操作：

• 遍历等待队列： 找到对应的 wait_queue_head_t 链表，遍历挂在上面的等待节点（也就是截图里用 DEFINE_WAIT() 创建的那个项）。

• 修改状态 (State Change)： 找到对应的 task_struct，把它的状态从 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE 强行改回 TASK_RUNNING（可执行状态）。

• 重返红黑树 (Re-enqueue)： 重点来了！内核会调用调度器的核心函数（如 enqueue_task），最终调用的就是我们第一张截图里的 __enqueue_entity()！它会把这个进程的 sched_entity 重新插入到 CFS 调度器的红黑树中。

• 抢占检查： 内核会顺便比对一下：被唤醒的这个进程，它的 vruntime 是不是比当前正在 CPU 上跑的进程还要小？如果是，内核会设置一个重新调度的标志（TIF_NEED_RESCHED），在中断返回时触发一次进程切换。

上下文切换

当调度器 schedule() 决定让进程 A 下去，让进程 B 上来时，CPU 到底发生了什么

每个用户进程都有自己独立的虚拟地址空间（也就是自己独立的页表）

1. 第一步：换虚拟内存空间

• 内核会调用 switch_mm_irqs_off()（早期叫 switch_mm()）。它的底层动作非常硬核——直接去修改 CPU 的页表基址寄存器
• TLB 刷新： 换了页表，CPU 内部缓存的旧地址映射（TLB）通常就失效了，需要刷新。不过现代 CPU 引入了 ASID（地址空间 ID）等技术来优化这个过程，避免每次切换都清空整个缓存。
• 特例（线程切换）： 如果调度的 A 和 B 是属于同一个进程的两个线程，因为它们共享内存，内核会聪明地跳过这一步，直接进入第二步。这就解释了为什么“线程切换的开销比进程小得多”。

2. 第二步：换寄存器与内核栈 (switch_to) 这部分是由宏 switch_to() 完成的。因为涉及到极底层的硬件寄存器操作，这部分代码通常是用纯汇编语言手写的。

switch_to() 主要切换三个核心部位：

• 通用寄存器： 把 CPU 当前的一堆通用寄存器（如 R0-R15 等）的值，压入进程 A 的内核栈中保存起来。然后从进程 B 的内核栈中，弹出 B 以前保存的寄存器值。

• 栈指针 (Stack Pointer, SP)： 每个进程都有自己专属的“内核栈”。内核把 CPU 的栈指针寄存器从指向 A 的栈，改为指向 B 的栈。这是最致命的一击！栈指针一换，CPU 真正执行的上下文就已经变成 B 了。

• 指令指针 (Program Counter, PC / IP)： 保存 A 下一条要执行的指令地址，并将 CPU 的执行流强行跳转到 B 上次停下来的地方。

抢占

抢占的实现主要分为两步：设置抢占标志（贴罚单） 和 执行真正抢占（清算）。

1. 贴罚单：设置 TIF_NEED_RESCHED 标志当内核发现当前运行的进程应该把 CPU 让出来时，它会在该进程的 thread_info 结构体中设置一个特殊的标志位：TIF_NEED_RESCHED（需要重新调度）。

这通常发生在以下两个核心场景：

场景一：时间片耗尽（Tick 抢占）

• 系统的硬件定时器会周期性地触发中断（这就是大名鼎鼎的 Tick，滴答）。每次中断发生时，内核会调用 scheduler_tick()。 在 CFS 调度器中，这个函数会检查当前进程的虚拟运行时间（vruntime）。如果它运行的时间超过了它应得的份额（或者红黑树里有比它更“委屈”的进程），内核就会给当前进程打上 TIF_NEED_RESCHED 标志。

• 场景二：被高优先级唤醒（Wakeup 抢占） 这正是我们上一个话题聊到的。当进程 A 正在运行，此时硬件中断发生，唤醒了沉睡在等待队列上的进程 B。内核在把进程 B 插回 CFS 红黑树时，会比较 A 和 B 的 vruntime。如果 B 的 vruntime 更小（比 A 更需要 CPU），内核就会立刻给正在运行的 A 打上 TIF_NEED_RESCHED 标志。

2. 找机会清算：什么时候真正执行 schedule()？ “贴了罚单”之后，当前进程还在继续跑。但它跑不长了，因为内核在几个极其关键的咽喉要道设立了检查站。只要进程路过这些检查站，内核就会摸一下它的 TIF_NEED_RESCHED 标志。如果被置位了，就会立刻强制调用 schedule()，触发我们上一节聊的上下文切换。

这些检查站分为两类，对应了 Linux 的两种抢占类型：

A. 用户抢占 (User Preemption) 这是最基础的抢占。当进程在内核态办完事，准备返回用户态时，必须经过检查站： 从系统调用返回用户态时： 比如你的程序调用了 read()，内核读完数据准备返回你的 C 代码时。 从中断处理程序返回用户态时： 硬件中断打断了用户进程，中断处理完准备恢复用户进程时。

B. 内核抢占 (Kernel Preemption) 这是 Linux 2.6 引入的杀手级特性。如果进程正在内核态执行（比如正在遍历链表），能不能抢占它？ 答案是：只要不持有锁，就可以抢占。 内核为此引入了一个计数器叫 preempt_count。

当进程获取自旋锁（Spinlock）时，preempt_count 加 1（关抢占）。

当释放锁时，preempt_count 减 1（开抢占）。

检查站： 当 preempt_count 减到 0 时，或者当中断处理程序准备返回内核态时，内核会检查 TIF_NEED_RESCHED。如果有标志且 preempt_count 为 0，就会立刻触发内核抢占。

实时调度

我们之前聊的 CFS（完全公平调度器）就像是“吃大锅饭”，讲究雨露均沾，通过红黑树和 vruntime 努力做到绝对公平。

但现实世界中，有些任务是“救火队员”，它们根本不在乎公不公平，它们只在乎**“我必须立刻马上执行，谁也别拦我”**。比如控制机械臂移动的程序、处理音频缓冲区的防爆音程序，或者汽车的防抱死制动系统（ABS）

这就是实时调度（Real-Time Scheduling）。

实时调度的核心目标不是吞吐量最大化，也不是公平，而是确定性（Determinism）和低延迟。它必须保证任务在规定的时间内完成。

在 Linux 内核中，实时调度完全绕开了 CFS 的红黑树，它有一套自己独立的、极度“霸道”的规则。主要分为三种调度策略：

1.SCHED_FIFO（先进先出：霸道总裁模式） 这是最纯粹、最暴力的实时策略。

规则： 当一个 SCHED_FIFO 进程变成可执行状态时，它会立刻抢占当前运行的普通进程。

霸道之处： 一旦它拿到 CPU，只要它不主动调用阻塞函数（比如去等待 I/O、请求锁或者主动调用 sched_yield()），且没有更高优先级的实时进程出现，它就会一直霸占 CPU 跑到死。

后果： 哪怕 CFS 队列里有成百上千个饥肠辘辘的普通进程，只要 FIFO 进程不放手，那些普通进程连 1 毫秒的执行时间都拿不到

2.SCHED_RR（轮转调度：兄弟平分模式） SCHED_RR 是 SCHED_FIFO 的一个温和变种。

规则： 它和 FIFO 基本一样，唯一的区别在于它引入了时间片（Time Slice）的概念，但这仅仅是针对同等优先级的其他实时进程。

机制： 如果系统里有三个优先级都是 50 的 SCHED_RR 进程，内核会给它们分配固定的时间片（比如 100 毫秒）。进程 A 跑完 100 毫秒后，会被强制放到同优先级队列的末尾，让进程 B 跑。

注意： 即使它们之间互相轮转，对于底层的普通 CFS 进程来说，依然是绝对的压制

3.SCHED_DEADLINE（截止时间调度：契约精神模式） 这是 Linux 3.14 版本引入的最顶级的实时策略，基于最早截止时间优先（EDF, Earliest Deadline First）算法。 相比于前两种靠优先级硬抢，DEADLINE 策略要求你必须和内核“签合同”。你需要向内核提供三个参数：

运行时间 (Runtime)： 我每次唤醒最多需要执行多久。

截止时间 (Deadline)： 我被唤醒后，必须在这个时间内完成工作。

周期 (Period)： 我多久被唤醒一次。

机制： 内核会进行“准入测试”。如果内核算了一下当前的 CPU 负载，发现无法满足你的这个契约，会直接拒绝你的启动请求。如果接受了，调度器会优先调度那个离 Deadline 最近的进程。