背景痛点

单级调度算法（如单纯的时间片轮转）在处理长短进程混合的场景时表现不佳。长进程会长时间占用CPU，导致短进程等待时间过长；而短进程优先又可能导致长进程饥饿。这时候就需要多级反馈队列调度算法来平衡响应时间和吞吐量。

算法解剖

二级反馈队列调度算法主要包含两个队列：

• Q1：采用时间片轮转调度算法，时间片为10ms
• Q2：采用短进程优先调度算法

调度规则如下：

1. 新创建的进程首先进入Q1
2. 系统优先调度Q1中的进程
3. Q1中的进程执行一个时间片后，若未结束，则转入Q2
4. 当Q1为空时，系统才会调度Q2中的进程

真题实战

题目场景：当前Q1和Q2为空，系统依次创建进程P1(30ms)和P2(20ms)后开始调度。

调度过程如下：

1. 初始状态：P1和P2都进入Q1
2. 第一次调度：选择P1执行10ms（剩余20ms），然后转入Q2
3. 第二次调度：Q1中剩下P2，执行10ms（剩余10ms），然后转入Q2
4. 第三次调度：Q1为空，调度Q2中最短的进程P2(剩余10ms)，执行完成
5. 第四次调度：Q2中剩下P1(剩余20ms)，执行完成

甘特图表示：

时间轴(ms):
0-10: P1
10-20: P2
20-30: P2完成
30-50: P1完成

代码实现

class Process:
    def __init__(self, pid, burst_time):
        self.pid = pid
        self.burst_time = burst_time
        self.remaining_time = burst_time

class Scheduler:
    def __init__(self):
        self.q1 = []  # 时间片轮转队列
        self.q2 = []  # 短进程优先队列
        self.current_time = 0

    def add_process(self, process):
        self.q1.append(process)

    def schedule(self):
        while self.q1 or self.q2:
            # 优先调度Q1
            if self.q1:
                current_process = self.q1.pop(0)
                time_slice = min(10, current_process.remaining_time)
                print(f"时间 {self.current_time}-{self.current_time + time_slice}: 执行进程 {current_process.pid}")

                self.current_time += time_slice
                current_process.remaining_time -= time_slice

                if current_process.remaining_time > 0:
                    self.q2.append(current_process)
            else:
                # Q1为空时调度Q2，按短进程优先
                if self.q2:
                    self.q2.sort(key=lambda p: p.remaining_time)
                    current_process = self.q2.pop(0)
                    print(f"时间 {self.current_time}-{self.current_time + current_process.remaining_time}: 执行进程 {current_process.pid}")

                    self.current_time += current_process.remaining_time
                    current_process.remaining_time = 0

# 测试代码
if __name__ == "__main__":
    scheduler = Scheduler()
    p1 = Process("P1", 30)
    p2 = Process("P2", 20)

    scheduler.add_process(p1)
    scheduler.add_process(p2)

    scheduler.schedule()

避坑指南

1. 新进程误入Q2：题目明确要求新进程必须先进入Q1，这是反馈机制的关键
2. 时间片结束后未正确迁移进程：Q1中的进程执行完一个时间片后，如果未完成必须转入Q2
3. 短进程优先导致长进程饥饿：虽然题目中没有出现这种情况，但在实际系统中需要考虑对长进程的保护机制

延伸思考

1. 如何动态调整时间片长度优化响应时间？可以考虑根据系统负载动态调整Q1的时间片大小
2. 是否应该引入第三级队列处理I/O密集型进程？对于频繁进行I/O操作的进程，可能需要特殊的调度策略

通过这个例子，我们可以看到二级反馈队列调度算法如何平衡长短进程的需求。理解这些基本原理，可以帮助我们在实际系统开发中设计更合理的调度策略。