4. 调度算法(下)：优先级调度、多级反馈队列、EDF最早截止时间优先算法详解

上一章我们聊了时间片轮转和协作式调度，那些算法比较“公平”，但不够“聪明”。今天要讲的这三种算法，才是真正能解决复杂实时问题的利器。我个人习惯把优先级调度比作“社会阶层”，把多级反馈队列比作“动态晋升通道”，而EDF则是“死线战士”——谁先到截止时间谁先跑。

好，我们一个一个来拆。

4.1 优先级调度：静态与动态的博弈

优先级调度，说白了就是给每个任务贴个数字标签。数字越小（或越大），优先级越高。调度器每次就挑优先级最高的那个任务执行。

这里有两个流派：静态优先级和动态优先级。

我在项目中遇到过一个问题：一个传感器采集任务，周期是10ms，但偶尔会被一个中断服务函数打断。中断服务函数里有个延时循环，导致传感器数据采集超时。后来我把传感器任务的优先级调高，并且把中断服务函数里的延时改成信号量等待，问题就解决了。

4.2 多级反馈队列：动态晋升的艺术

多级反馈队列（MLFQ），你想想看，它解决了什么问题？

传统优先级调度有个毛病：如果所有任务都是高优先级，那跟没优先级一样。如果低优先级任务一直得不到CPU，就会“饿死”。MLFQ的思路是：让任务在多个队列之间动态移动。

它的核心规则很简单：

1. 系统有N个优先级队列，从高到低排列。
2. 新任务进入最高优先级队列。
3. 每个队列内部采用时间片轮转。
4. 任务用完当前队列的时间片还没完成，就降级到下一级队列。
5. 如果任务主动让出CPU（比如等待I/O），优先级不变或提升。

你可能会问：“为什么要降级？”

因为CPU密集型任务如果一直占着高优先级队列，交互型任务就得不到响应。降级机制保证了交互型任务（通常是短任务）能快速完成，而计算型任务（长任务）慢慢在低优先级队列里跑。

下面是一个简化的MLFQ调度器核心代码：

// 多级反馈队列调度器核心
#define NUM_QUEUES 3
#define TIME_SLICE_HIGH 1   // 高优先级队列时间片(ms)
#define TIME_SLICE_MID  5   // 中优先级队列时间片(ms)
#define TIME_SLICE_LOW  20  // 低优先级队列时间片(ms)

typedef struct {
    uint8_t current_queue;      // 当前所在队列
    uint32_t time_slice_used;   // 当前时间片已使用量
    void (*task_func)(void);
} MLFQ_TCB;

MLFQ_TCB task_table[MAX_TASKS];

void mlfq_scheduler(void) {
    // 从高到低查找非空队列
    for (int q = 0; q < NUM_QUEUES; q++) {
        if (!is_queue_empty(q)) {
            MLFQ_TCB *task = get_next_task_from_queue(q);
            uint32_t slice = get_time_slice(q);
            
            // 执行任务
            task->task_func();
            task->time_slice_used += get_elapsed_time();
            
            // 判断是否降级
            if (task->time_slice_used >= slice) {
                if (q < NUM_QUEUES - 1) {
                    move_task_to_queue(task, q + 1);
                }
                task->time_slice_used = 0;
            }
            break;
        }
    }
}

4.3 EDF最早截止时间优先：理论最优的调度器

EDF，全称Earliest Deadline First。它的思想极其简单：谁先到截止时间，谁先执行。

你想想看，这跟人赶火车一样。你的火车是10:00发车，我的火车是10:05发车，那肯定你先检票。EDF就是这种逻辑。

EDF在理论上是最优的——如果一组任务能被任何调度算法调度，那么EDF也一定能调度它们。而且EDF的CPU利用率理论上可以达到100%。

但现实很骨感。EDF有两个致命问题：

• 实现复杂度高：每次调度都要找截止时间最近的任务，如果任务数量多，查找开销很大。
• 过载时性能崩溃：当CPU利用率超过100%时，EDF会毫无征兆地让所有任务都错过截止时间。这叫做“多米诺效应”。

我记得有一次做无人机飞控，用了EDF调度。正常情况下一切完美，但有一次遇到强风，计算量暴增，CPU过载了。结果所有控制任务都错过了截止时间，无人机直接失控。从那以后，我在硬实时系统中再也不敢裸用EDF了。

下面是一个EDF调度器的核心实现：

// EDF调度器核心
typedef struct {
    uint32_t deadline;      // 绝对截止时间
    uint32_t period;        // 周期
    uint32_t execution_time;// 最坏执行时间
    void (*task_func)(void);
    uint8_t is_active;
} EDF_TCB;

EDF_TCB edf_tasks[MAX_TASKS];

void edf_scheduler(void) {
    uint32_t now = get_system_tick();
    uint32_t nearest_deadline = UINT32_MAX;
    int selected_task = -1;
    
    // 查找截止时间最近的任务
    for (int i = 0; i < MAX_TASKS; i++) {
        if (edf_tasks[i].is_active && edf_tasks[i].deadline <= now) {
            // 已经错过截止时间的任务，紧急处理
            if (edf_tasks[i].deadline < nearest_deadline) {
                nearest_deadline = edf_tasks[i].deadline;
                selected_task = i;
            }
        }
    }
    
    // 如果没有错过截止时间的任务，找最近的任务
    if (selected_task == -1) {
        for (int i = 0; i < MAX_TASKS; i++) {
            if (edf_tasks[i].is_active && edf_tasks[i].deadline < nearest_deadline) {
                nearest_deadline = edf_tasks[i].deadline;
                selected_task = i;
            }
        }
    }
    
    if (selected_task != -1) {
        edf_tasks[selected_task].task_func();
        // 任务执行完后，更新下一次的截止时间
        edf_tasks[selected_task].deadline += edf_tasks[selected_task].period;
    }
}

4.4 三种算法的对比与选型

说了这么多，到底该用哪个？我个人的经验是：