如何在 Java 中利用数组实现简单的多级反馈队列调度算法以模拟操作系统的任务分配

如何在 Ja va 中利用数组实现简单的多级反馈队列调度算法以模拟操作系统的任务分配

想在Ja va里模拟操作系统的多级反馈队列（MLFQ）调度算法？其实核心逻辑并不复杂。关键在于用数组模拟出多个优先级队列、时间片递减以及任务动态升降级这一套机制。整个过程无需动用真实的线程或进程控制，仅凭数组和状态模拟，就能把MLFQ的核心思想展现得清清楚楚。

Ja va中用数组模拟三级MLFQ调度：queue[0]（时间片2）、queue[1]（时间片4）、queue[2]（FCFS，时间片8），任务按剩余时间、队列层级和等待时间动态升降级，通过循环模拟CPU时间推进与上下文切换。

设计三级队列结构与数组表示

首先，得把队列架子搭起来。通常，用三个一维数组（或者更灵活的ArrayList）来分别代表高、中、低三个优先级的就绪队列就足够了：

• queue[0]：这是最高优先级队列，时间片最短，设为2个单位时间。所有新到达的任务，或者因为“表现好”而被提升权级的任务，都从这里开始。
• queue[1]：中等优先级队列，时间片放宽到4个单位。如果任务在queue[0]里没能在时间片内完成，就会被“降级”到这里。
• queue[2]：最低优先级队列，采用先来先服务（FCFS）策略，时间片可以设得很大（比如8个单位），或者干脆不设硬性限制。进入这个队列的任务，除非特殊规则，否则不会再被主动降级。

那么，如何表示一个任务呢？用一个简单的类来封装所有必要信息是最清晰的做法：

class Task {
  int id; // 任务标识
  int remainingTime; // 剩余需要执行的时间
  int queueLevel;    // 当前所在队列的层级（0, 1, 2）
  int timeInQueue;   // 在当前队列已等待的时间（用于判断是否该升级）
}

模拟调度主循环逻辑

调度器的“心脏”是一个while循环，用它来模拟CPU时间的推进。每次循环可以步进1个单位时间，或者直接跳到下一个关键事件点（如时间片用完或新任务到达）。循环体内的逻辑，严格遵循MLFQ的优先级规则：

• 第一步，看最高队列：如果queue[0]非空，就取出队首任务执行。执行1个单位时间（或直接消耗完其2个单位的时间片），并减少其remainingTime。任务若就此完成，则移出系统；若时间片用尽却还没干完活，那就抱歉了，它会被移到queue[1]的尾部等待下次机会。
• 第二步，轮到中级队列：只有当queue[0]为空时，才去检查queue[1]。处理逻辑类似，但时间片是4个单位。同样，超时未完成的任务会被降级到queue[2]。
• 最后，处理最低队列：只有当前两个高优先级队列都清空时，才执行queue[2]的队首任务。为了简化并体现FCFS的精神，可以规定这里每次最多只执行1个单位时间（尽管时间片可能很长），然后任务重新排队。
• 别忘了“升权”机制：为了防止低优先级任务饥饿，可以在每轮循环开始前，加入一个简单的提升规则。例如，检查queue[2]中的任务，如果某个任务的timeInQueue等待时间超过了某个阈值（比如10个单位），并且期间没有更高优先级的任务到达，就可以把它提升回queue[1]。这需要额外记录任务进入当前队列的起始时间。

任务到达与队列管理细节

真实的系统任务可不是同时出现的，我们需要模拟它们动态到达的情景。这可以通过预设一个到达时间数组，或者实时输入来实现。

立即学习“Ja va免费学习笔记（深入）”；

• 新任务入场：所有新任务默认进入queue[0]。为了公平，建议放在队列尾部，而不是头部。
• 时间同步：用一个clock全局变量记录当前时间，再配合一个arrivalTimes数组记录每个任务的到达时刻，就能准确判断何时该将新任务加入就绪队列。
• 数组操作技巧：强烈建议使用ArrayList来代替原始数组。它的add()和remove()方法让队列管理直观很多。如果坚持使用基础数组，就必须手动维护每个队列的有效长度（例如size[0], size[1], size[2]），并进行繁琐的元素搬移工作。
• 避免饥饿是关键：MLFQ算法本身不保证实时性，但必须防止低优先级任务永远得不到执行。除了上述的“升权”规则，还可以考虑一种“老化”机制：当queue[2]中的任务被执行过若干轮后，将其中等待时间最长的那个临时提升到queue[1]。

输出与验证调度行为

代码写好了，怎么知道它跑得对不对呢？丰富的日志输出是调试和验证的不二法门。可以在每单位时间，或者每次发生任务切换（上下文切换）时，打印出关键信息：

• 当前的模拟时钟clock值。
• 正在执行的任务ID及其剩余时间。
• 各个队列里当前排队的任务ID列表，例如：queue0: [T1, T3], queue1: [T2], queue2: []。
• 每当有任务完成时，记录并计算其周转时间（完成时间 - 到达时间）和响应时间（首次开始执行的时间 - 到达时间）。

最后，用几个典型用例跑一跑，逻辑就一目了然了。比如，设置三个任务：T1（到达时间0，总耗时1）、T2（到达时间1，总耗时10）、T3（到达时间2，总耗时3）。运行后观察：T1是否被快速处理完？T2是否先在高优先级队列抢跑，然后因为执行时间长被逐步降级？T3到达后，是否会短暂抢占正在中低队列执行的T2？如果这些现象都出现了，那么恭喜，你的MLFQ模拟程序已经成功捕捉到了其“优待短任务、兼顾响应性”的精髓。