悉尼科技大学重磅突破：让AI学会“看-想-编辑“的视频编辑新方法
2026/1/5 22:27:32
该算法是多级反馈队列调度算法（Multilevel Feedback Queue Scheduling, MLFQ）。
1. 算法定位
多级反馈队列调度算法结合了**时间片轮转（Round Robin）和优先级调度（Priority Scheduling）**的优点，是一种动态优先级调度算法。其主要优势包括：
- 兼顾短进程：短作业或交互式进程能快速完成，提升系统吞吐量并缩短平均周转时间；
- 优化 I/O 型进程响应：I/O 密集型进程在高优先级队列中迅速响应，提高设备利用率与用户体验；
- 无需预知执行时间：通过动态调整进程优先级，避免对运行时间的先验估计；
- 自动调节行为：根据进程的历史行为（如是否频繁 I/O、是否耗尽时间片）动态调整其所处队列。
2. 实现思路
队列设置：
- 设置多个就绪队列（例如队列 1 到队列 n），优先级从高到低排列；
- 每个队列拥有不同的时间片长度，通常为逐级加倍（如队列 1 时间片为 2ms，队列 2 为 4ms，队列 3 为 8ms……）；
- 越高层的队列时间片越小，适合短任务快速响应。
进程调度逻辑：
- 新创建的进程进入最高优先级队列（队列 1）尾部，采用 FCFS 方式等待调度；
- 若进程在一个时间片内未完成，则被“降级”至下一级队列的末尾；
- 最底层队列通常使用时间片轮转方式持续执行直至完成；
- 高优先级队列中的进程始终优先获得 CPU 资源。
抢占机制：
- 只要更高优先级队列中有可运行进程，当前正在低优先级队列运行的进程就会被抢占；
- 被抢占的进程回到原队列末尾，等待下次调度；
- 这保证了系统的响应性，尤其是对交互式和 I/O 密集型任务。
3. 进程优先级动态调整规则
| 进程类型 | 处理策略 |
|---|---|
| I/O 型进程 | 执行完 I/O 后返回高优先级队列，确保快速响应键盘、鼠标、磁盘读写等操作； |
| 计算型进程 | 每次耗尽时间片后逐步降级，最终在低优先级长时间片队列中运行，减少上下文切换开销； |
| 混合型进程（少量 I/O） | I/O 完成后恢复至原有优先级队列，保持一定调度公平性与效率。 |
⚠️ 注：某些实现中还会引入“老化机制”——长时间停留在低优先级队列的进程会被提权，防止饥饿。
多级反馈队列调度算法通过引入“老化机制”（Aging）来防止计算密集型进程长期占据低优先级队列而导致其他进程饥饿。
防止饥饿的机制详解：
问题背景：
- 计算密集型进程在每一级时间片耗尽后不断降级，最终停留在最低优先级队列中；
- 若系统持续有新进程或高优先级任务进入，低优先级队列中的进程可能长时间得不到调度，造成饥饿（Starvation）。
解决方案：老化机制（Aging）
- 老化是一种动态提升优先级的技术：当一个进程在低优先级队列中等待时间超过某个阈值时，系统将其提升到更高优先级队列；
- 例如：若某进程在队列 5 中等待超过 5 秒，则自动将其移动至队列 2 或队列 3，增加其获得 CPU 的机会；
- 这种提权是临时且可控的，不会破坏整体调度策略对短进程和 I/O 型进程的优化目标。
实现方式示例：
structProcess{intpriority;// 当前优先级队列编号clock_tlast_executed;// 上次执行时间intwait_time_threshold;// 提升优先级的等待时间阈值};// 定期检查就绪队列中等待过久的进程if(current_time-process->last_executed>process->wait_time_threshold){promote_to_higher_queue(process);// 提升优先级}与其他策略结合：
- 操作系统可监控各队列的平均等待时间，若发现底层队列积压严重，则批量提升部分进程优先级；
- 可设定规则如：“每等待 10 个时间片周期，优先级上升一级”，从而保障公平性。