【C/C++】内核开发之进程调度大纲

内核开发之进程调度大纲

1 进程调度基础

1. 多任务系统类型

   • 抢占式：调度器强制切换进程（基于时间片/优先级）
   • 非抢占式：进程主动让步（yield），易导致饥饿
   • 时间片（Timeslice）：进程被抢占前持续运行的时间段，影响响应与吞吐平衡。

2. 进程分类与调度目标

   • I/O消耗型：频繁阻塞（如GUI应用），需高响应优先级
   • CPU消耗型：长期占用CPU（如计算任务），适合长时片
   • 核心矛盾：响应速度（低延迟） vs. 系统吞吐量（高利用率）

3. 优先级模型

   • Nice值（-20~19）：值越大优先级越低，影响普通进程时间片比例
   • 实时优先级（0~99）：值越大优先级越高，用于SCHED_FIFO/SCHED_RR
   • 优先级映射：实时进程 > 普通进程（Nice值无效）

---

2 核心调度算法：CFS（完全公平调度器）

1. 设计目标

   • 公平性：各进程获得CPU时间与其权重成比例
   • 低开销：O(1)时间复杂度选择进程
   • 交互优化：保障I/O型进程响应速度。

2. 关键机制

   • 虚拟运行时（vruntime）：

     // struct sched_entity (kernel/sched/sched.h)
     u64 vruntime; // 标准化后的运行时间（纳秒）
     

     公式：vruntime += 实际运行时间 × (NICE_0_LOAD / 进程权重)
   • 红黑树（rbtree）：
     • 以vruntime为键值组织可运行进程
     • 选择最小vruntime的节点（最左侧叶子）作为下一个进程
   • 时间分配：
     • 进程时间片 = (进程权重 / 总权重) × 调度周期
     • 最小粒度（1ms）：避免过多进程时切换开销

---

3 调度器实现机制

1. 时间记账（Time Accounting）

   • update_curr()：周期性更新当前进程的vruntime（位于kernel/sched/fair.c）
   • 计算实际运行时间并转换为加权虚拟时间。

2. 进程选择

   • 入队：enqueue_entity() → 插入红黑树（新进程/唤醒进程）
   • 出队：dequeue_entity() → 移出红黑树（阻塞/终止）
   • 挑选下一进程：__pick_next_entity() → 返回最小vruntime节点

3. 调度入口

   • schedule()：核心入口函数 → 调用pick_next_task()
   • 按调度类优先级遍历（实时类 > CFS类）

4. 睡眠与唤醒

   • 睡眠：进程移入等待队列，状态置为TASK_INTERRUPTIBLE
   • 唤醒：wake_up() → 移回红黑树，触发抢占检查

---

4 高级主题

1. 抢占（Preemption）

   • 用户抢占：从系统调用/中断返回用户空间时检查need_resched标志
   • 内核抢占：中断返回内核空间时，若preempt_count=0且需调度则抢占

2. 实时调度策略

   • SCHED_FIFO：无时间片，高优先级进程独占CPU直至阻塞
   • SCHED_RR：带时间片的轮转实时调度

3. 多核负载均衡

   • 每个CPU维护独立运行队列（struct rq）
   • 周期性负载均衡（load_balance()）迁移任务

---

5 实践与扩展

1. 调度相关系统调用

   系统调用	功能描述
   sched_setscheduler()	设置进程调度策略与优先级
   sched_yield()	主动让出CPU
   sched_setaffinity()	绑定进程到特定CPU核心

2. 性能调优

   • 调整Nice值：nice命令
   • 实时进程优先级：chrt -p <prio> <pid>
   • 监控工具：ftrace（跟踪调度事件）、perf sched

3. 扩展阅读

   • 源码重点文件：
     • kernel/sched/fair.c（CFS实现）
     • kernel/sched/rt.c（实时调度）
   • 研究趋势：异构调度（如ARM big.LITTLE）、低延迟优化（BPF调度器）