调度算法的模拟及应用

一、经典调度算法初步认识

1. 短作业优先（SJF）

   • 原理：每次从就绪队列中选择估计运行时间最短的作业执行。

   • 优点：平均周转时间一般最小。

   • 缺点：可能导致长作业“饥饿”；需要准确的作业执行时间估计。

2. 时间片轮转（RR）

   • 原理：给每个作业固定长度的时间片（quantum），若在时间片内未完成，则放回队尾，继续等待下一轮。

   • 优点：响应时间有上限，能够较好地兼顾交互性和吞吐量。

   • 缺点：平均周转时间随时间片大小变化而变化；时间片过小，切换开销大；时间片过大，又退化为 FCFS。

3. 优先级调度

   • 原理：每个作业分配一个优先级值，优先级高的先执行。可以是静态也可以动态调整。

   • 优点：可根据作业重要性分配资源。

   • 缺点：可能导致低优先级作业饥饿，需要引入老化（aging）等机制。

4. 最高响应比优先（HRRN）

   • 原理：选择响应比 (等待时间+服务时间)/服务时间(等待时间 + 服务时间) / 服务时间(等待时间+服务时间)/服务时间 最高的作业执行。

   • 优点：兼顾了等待时间和作业长度，能避免长作业饥饿。

   • 缺点：每次调度都要计算响应比，开销更大。

5. 多级反馈队列（MFQ）

   • 原理：将就绪队列分成多个优先级队列，不同队列有不同的时间片和调度策略。新到作业先放高优先级队列，若占用过多就降级，防止短作业被长作业挤占。

   • 优点：兼顾了各种作业类型，既响应短作业，也保证长作业不会饥饿。

   • 缺点：实现复杂，需要调优队列数、时间片长度、升降级策略等。

---

二、Round Robin 模拟与结果

模拟场景

• 作业集：

  作业	到达时间	服务时间
  P1	0	5
  P2	1	3
  P3	2	8
  P4	3	6

• 时间片（quantum）= 2

#include <stdio.h>#define N 4  // 作业数量
#define QUANTUM 2  // 时间片大小typedef struct {char pid[3];int arrival;int burst;int completion;int turnaround;int waiting;int remaining;int finished;
} Process;int main() {Process processes[N] = {{"P1", 0, 5, 0, 0, 0, 5, 0},{"P2", 1, 3, 0, 0, 0, 3, 0},{"P3", 2, 8, 0, 0, 0, 8, 0},{"P4", 3, 6, 0, 0, 0, 6, 0}};int time = 0;int finished_count = 0;int queue[N];int front = 0, rear = 0;int arrived[N] = {0}; // 记录是否已经到达并入队while (finished_count < N) {// 新到达的作业入队for (int i = 0; i < N; i++) {if (processes[i].arrival <= time && !arrived[i]) {queue[rear++] = i;arrived[i] = 1;}}if (front == rear) { // 队列为空，时间前进time++;continue;}int idx = queue[front++];int exec_time = (processes[idx].remaining < QUANTUM) ? processes[idx].remaining : QUANTUM;processes[idx].remaining -= exec_time;time += exec_time;// 在执行期间，可能有新的作业到达for (int i = 0; i < N; i++) {if (processes[i].arrival <= time && !arrived[i]) {queue[rear++] = i;arrived[i] = 1;}}if (processes[idx].remaining == 0) {processes[idx].completion = time;processes[idx].turnaround = processes[idx].completion - processes[idx].arrival;processes[idx].waiting = processes[idx].turnaround - processes[idx].burst;processes[idx].finished = 1;finished_count++;} else {queue[rear++] = idx; // 未完成的重新排队}}// 打印结果printf(" PID  Arr  Burst  Comp  Turn  Wait\n");double total_turnaround = 0.0;for (int i = 0; i < N; i++) {printf(" %s   %3d   %3d   %3d   %3d   %3d\n", processes[i].pid, processes[i].arrival, processes[i].burst,processes[i].completion,processes[i].turnaround,processes[i].waiting);total_turnaround += processes[i].turnaround;}printf("\n平均周转时间 = %.2f\n", total_turnaround / N);return 0;
}

模拟“截图”输出

PID Arr Burst Comp Turn Wait P2 1 3 7 6 3 P1 0 5 10 10 5 P4 3 6 17 14 8 P3 2 8 23 21 13 平均周转时间 = 12.75

注：此处进程完成顺序取决于队列的实时变化，若与其他实现略有差异属于正常。

---

三、为什么要有调度 & Linux 中有哪些算法

1. 为什么要有调度

   • 现代 OS 要同时管理多个进程／线程，单核 CPU 一次只能运行一个上下文，需要决定“下一秒执行谁”。

   • 合理的调度能提升 CPU 利用率、降低响应时间、保证系统公平性、满足不同实时性需求。

2. 为什么要有不同算法

   • 交互式应用（如图形界面）关注响应时间，适合短时间片或 RR；

   • 批处理作业关注吞吐量，适合 SJF；

   • 实时系统关注截止期，需专用实时调度策略；

   • 不同场景／硬件／需求下的权衡不同。

3. Linux 内核中可查到的调度器

   • O(n) 调度器（已淘汰）：早期 2.4／2.6 中的任务数组扫描。

   • O(1) 调度器：Linux 2.6，引入两个就绪数组，常数时间查找。

   • Completely Fair Scheduler (CFS)：从 2.6.23 开始，基于红黑树，按虚拟运行时间（vruntime）分配公平时间片。

   • 实时调度器：SCHED_FIFO（先来先服务）、SCHED_RR（实时轮转）、SCHED_DEADLINE（截止期限调度）。

   • MuQSS/BMQ（补丁）：替代 CFS，用更简单的多队列结构以提高延迟性能。

可在 kernel/sched/ 目录下查看具体实现，如 fair.c（CFS）、rt.c（实时）、deadline.c 等。

---

四、调度中的困惑 & 调试收获

1. 常见困惑

   • “时间片切换频繁到底怎样衡量开销？”

   • “同一算法在不同实现里结果为什么会不一致？”

   • “多级反馈队列中升降级的阈值如何选取？”

2. 通过模拟／调试解决了哪些

   • RR 调度：通过代码精确跟踪“剩余时间”、“队列变化”，体会到时间片大小对平均周转和响应时间的双重影响。

   • 实现差异：明白不同边界（如新进程插队时机）会改变执行顺序，但整体性能指标（平均周转、平均等待）波动有限。

   • Linux 深度：从用户态模拟过渡到内核态，通过阅读 sched_fair.c，看到红黑树上通过 vruntime 完成近似“最短进程优先”的思路，解决了“如何公平地模拟 SJF”这一困惑。

---

后续深挖

• 从用户态模拟切入，阅读 CFS 算法在红黑树上的插入、选择最小 vruntime 节点的实现。

• 分析内核中 sched_tick()、enqueue_task()、dequeue_task() 的调用流程。

• 研究 NUMA 系统下的 CPU 亲和／负载均衡（load_balance()）。

• 实现一个简单的内核模块，打印当前调度统计信息，体会内核调度器的调度周期。