C语言公平调度算法详解（从零实现操作系统中的完全公平调度器）

什么是公平调度？

公平调度的核心思想是：每个可运行的进程应公平地获得 CPU 时间。传统调度器可能基于优先级或时间片轮转，而 CFS 则通过追踪每个进程的“虚拟运行时间”（vruntime）来实现公平——运行时间越少的进程，vruntime 越小，越有资格获得 CPU。

关键概念解析

• vruntime：虚拟运行时间，用于衡量进程已使用的 CPU 时间（经过权重调整）。
• 红黑树：CFS 使用红黑树按 vruntime 排序进程，最小 vruntime 的进程总在最左侧，优先调度。
• 时间片：CFS 不使用固定时间片，而是根据系统负载动态计算。

用 C 语言实现简化版公平调度器

为了便于理解，我们省略红黑树，改用数组模拟进程队列，并手动维护 vruntime。以下是完整代码：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_PROCESSES 10#define NICE_TO_WEIGHT(nice) (120 - (nice))  // 简化权重映射// 进程结构体typedef struct {    int pid;    int nice;        // 优先级（-20 ~ 19），值越小优先级越高    long vruntime;   // 虚拟运行时间    int weight;      // 权重，由 nice 值决定} Process;Process processes[MAX_PROCESSES];int process_count = 0;// 添加新进程void add_process(int pid, int nice) {    if (process_count >= MAX_PROCESSES) return;        processes[process_count].pid = pid;    processes[process_count].nice = nice;    processes[process_count].weight = NICE_TO_WEIGHT(nice);    processes[process_count].vruntime = 0;    process_count++;}// 查找 vruntime 最小的进程int find_min_vruntime_index() {    int min_idx = 0;    for (int i = 1; i < process_count; i++) {        if (processes[i].vruntime < processes[min_idx].vruntime) {            min_idx = i;        }    }    return min_idx;}// 模拟调度一个时间单位void schedule_tick() {    if (process_count == 0) return;        int idx = find_min_vruntime_index();    Process* p = &processes[idx];        // 更新 vruntime: 实际运行时间 / 权重 * 默认权重（这里简化为 +1/weight）    p->vruntime += 1024 / p->weight;  // 1024 是 Linux 中默认权重基准        printf("调度进程 PID=%d, nice=%d, vruntime=%ld\n",            p->pid, p->nice, p->vruntime);}int main() {    // 添加几个测试进程    add_process(101, 0);   // 默认优先级    add_process(102, -5);  // 高优先级    add_process(103, 10);  // 低优先级        printf("开始 C语言公平调度算法 模拟...\n\n");        // 模拟 10 个调度周期    for (int i = 0; i < 10; i++) {        schedule_tick();    }        return 0;}

代码说明

上述代码实现了 操作系统调度 的核心逻辑：

1. 每个进程有 nice 值，决定其权重（权重越高，获得 CPU 时间越多）。
2. 每次调度选择 vruntime 最小的进程执行。
3. 执行后更新该进程的 vruntime += 1024 / weight，确保高权重进程增长更慢，从而获得更多调度机会。

虽然真实 Linux CFS 使用红黑树和更复杂的数学计算，但这个简化模型能帮助你理解 CFS调度器实现 的基本原理。

为什么公平调度重要？

公平调度能有效避免低优先级进程“饿死”，提升系统响应性和用户体验。它是现代多任务操作系统（如 Linux、Android）的基石，也是学习 进程调度算法 必不可少的一环。

总结

通过本教程，你已经掌握了 C 语言公平调度算法的基本思想和简易实现。下一步可以尝试：

• 用红黑树优化查找效率
• 加入睡眠/唤醒机制
• 模拟 I/O 阻塞对调度的影响

希望这篇教程能为你打开操作系统内核的大门！如果你喜欢，请分享给更多学习 C语言公平调度算法 的朋友。