队列调度算法：从FIFO到多级反馈队列

调度算法这东西，说白了就是决定「下一个该谁上」。我在做消息中间件的时候，经常要跟这些算法打交道。不同的场景，选错了调度策略，性能能差出一个数量级。今天咱们就把五种经典算法掰开揉碎讲清楚。

一、FIFO调度：最简单的，也是最容易被欺负的

FIFO（First In First Out），先来先服务。就像银行排队，谁先到谁先办。实现起来极其简单，一个队列就搞定。

// 伪代码示例
Queue taskQueue = new Queue();

void enqueue(Task t) {
    taskQueue.push(t);
}

Task dequeue() {
    return taskQueue.pop(); // 从队头取
}

但问题也很明显——一个长任务能堵死后面所有短任务。我遇到过线上事故，一个批量处理任务跑了20秒，后面几百个实时查询全部超时。这就是FIFO的「 convoy effect 」（ convoy 效应）。

二、优先级调度：给任务分个三六九等

优先级调度给每个任务分配一个优先级，高优先级的先执行。你想想看，实时任务肯定比后台批处理任务重要，对吧？

实现上可以用多个队列，每个优先级一个队列。或者用优先队列（堆）结构。

// 优先队列实现
PriorityQueue<Task> pq = new PriorityQueue<>(
    (a, b) -> b.priority - a.priority
);

void enqueue(Task t) {
    pq.offer(t);
}

Task dequeue() {
    return pq.poll(); // 取优先级最高的
}

但这里有个大坑——优先级反转。低优先级任务持有高优先级任务需要的锁，高优先级任务反而被阻塞。我记得在某个嵌入式项目中，一个低优先级的日志任务锁住了共享资源，导致高优先级的控制任务卡死，整个设备重启了。

三、最短作业优先：听起来很美，做起来很难

SJF（Shortest Job First），谁执行时间短谁先上。理论上平均等待时间最短，但有个致命问题——你怎么知道任务要跑多久？

实际系统中，我们通常用「预估执行时间」。比如在数据库查询调度中，可以根据查询的复杂度、数据量来估算。但估算不准的话，效果还不如FIFO。

// 最短作业优先调度
Task selectNext(List<Task> readyQueue) {
    return readyQueue.stream()
        .min(Comparator.comparingLong(Task::getEstimatedDuration))
        .orElse(null);
}

另一个问题是饥饿——长任务可能永远得不到执行。我见过一个Hadoop集群，因为持续有短任务进来，一个需要跑2小时的大任务被饿死了整整一天。

四、时间片轮转：公平，但未必高效

RR（Round Robin），每个任务分一个时间片，轮流执行。就像自助餐厅，每个人吃30秒，然后换下一个人。

// 时间片轮转调度
int TIME_SLICE = 100; // 毫秒

void schedule(List<Task> readyQueue) {
    while (!readyQueue.isEmpty()) {
        Task current = readyQueue.remove(0);
        current.run(TIME_SLICE);
        if (!current.isFinished()) {
            readyQueue.add(current); // 放回队尾
        }
    }
}

时间片的大小很关键。设得太小，上下文切换开销太大；设得太大，就退化成FIFO了。我个人习惯是：I/O密集型的任务，时间片设小一点（10-50ms）；CPU密集型的，设大一点（100-200ms）。

五、多级反馈队列：集大成者

MLFQ（Multi-Level Feedback Queue），这是目前操作系统和很多中间件里最常用的调度算法。它结合了前面几种算法的优点。

核心思想：

• 设置多个优先级队列，每个队列有自己的时间片
• 高优先级队列时间片短，低优先级队列时间片长
• 新任务先进入最高优先级队列
• 任务用完时间片还没完成，就降级到下一级队列
• 高优先级队列不空，就不执行低优先级队列

// 多级反馈队列简化实现
class MLFQ {
    Queue<Task>[] queues = new Queue[3]; // 3级队列
    int[] timeSlices = {50, 100, 200};   // 每级时间片
    
    void enqueue(Task t) {
        queues[0].add(t); // 新任务进最高级
    }
    
    Task dequeue() {
        for (int i = 0; i < 3; i++) {
            if (!queues[i].isEmpty()) {
                Task t = queues[i].poll();
                t.level = i;
                return t;
            }
        }
        return null;
    }
    
    void onTimeSliceEnd(Task t) {
        if (!t.isFinished()) {
            int nextLevel = Math.min(t.level + 1, 2);
            queues[nextLevel].add(t);
        }
    }
}

这个算法妙在哪里？短任务在高优先级队列里很快就能完成，长任务虽然降级了，但总能得到执行。既保证了响应速度，又避免了饥饿。

六、五种算法对比

七、调度算法的选择策略

没有银弹。我这些年总结的经验是：

• 任务类型单一：FIFO就够了，别折腾
• 有明确的优先级需求：优先级调度 + 优先级继承
• 交互式系统：时间片轮转或MLFQ
• 批处理系统：SJF或FIFO
• 混合负载：MLFQ是首选

嗯，五种调度算法就讲到这里。每种算法都有它的脾气，选对了事半功倍，选错了...嗯，你懂的。