3.进程调度：常见算法

进程调度算法

1. 调度基本概念

为什么需要进程调度？

目的：当有多个进程/线程竞争CPU时，操作系统按照某种规则（算法）决定下一个该谁运行。目标是达到：

• 高CPU利用率

• 高系统吞吐量（单位时间完成的任务数）

• 低周转时间（任务从提交到完成的时间）

• 低响应时间（从提交请求到第一次产生响应的时间）

• 公平性

调度队列模型

+-------------------+     +-------------------+
|  就绪队列           |     |  各种等待队列       |
|  (Ready Queue)     |     |  (I/O, Sleep等)   |
|                   |     |                   |
|  Process A        |     |  Process B (I/O)  |
|  Process C        |     |  Process D (Sleep)|
|  Process E        |     |                   |
+-------------------+     +-------------------+↓                         ↑|        调度器            |+-------------------------+

2. 调度算法分类

2.1 先来先服务（FCFS - First Come First Served）

// 最简单的调度算法
struct fcfs_scheduler {Process* queue;  // 简单的FIFO队列int front, rear;
};void fcfs_schedule(struct fcfs_scheduler* sched) {while (!queue_empty(sched->queue)) {Process* p = dequeue(sched->queue);execute_process(p);  // 一直执行直到完成或阻塞if (p->state == READY) {enqueue(sched->queue, p);  // 如果没完成，重新入队}}
}

特点：

• 优点：实现简单，公平

• 缺点： convoy效应（短进程等待长进程），平均等待时间长

• 时间复杂度：O(1) 入队/出队

示例：

进程   到达时间   执行时间
P1     0         24
P2     1         3
P3     2         3调度顺序：P1 → P2 → P3
等待时间：P1=0, P2=23, P3=25
平均等待时间：(0+23+25)/3 = 16

2.2 短作业优先（SJF - Shortest Job First）

// 非抢占式版本
struct sjf_scheduler {PriorityQueue* queue;  // 按执行时间排序的优先队列
};void sjf_schedule(struct sjf_scheduler* sched) {while (!pq_empty(sched->queue)) {Process* p = pq_extract_min(sched->queue);  // 取执行时间最短的execute_process(p);  // 执行直到完成}
}

特点：

• 优点：平均等待时间最小（理论最优）

• 缺点：可能饥饿（长进程永远得不到执行），需要预知执行时间

• 时间复杂度：O(log n) 维护优先队列

示例：

进程   执行时间
P1     6
P2     8
P3     7
P4     3调度顺序：P4 → P1 → P3 → P2
等待时间：P4=0, P1=3, P3=9, P4=16
平均等待时间：(0+3+9+16)/4 = 7

3 优先级调度（Priority Scheduling）

// 静态优先级调度
struct priority_scheduler {PriorityQueue* queue;  // 按优先级排序
};void priority_schedule(struct priority_scheduler* sched) {while (!pq_empty(sched->queue)) {Process* p = pq_extract_max(sched->queue);  // 取优先级最高的execute_process(p);if (p->state == READY) {pq_insert(sched->queue, p);  // 重新插入}}
}// 动态优先级：避免饥饿
void aging_mechanism() {// 定期增加等待进程的优先级for (each process in wait_queue) {if (process.wait_time > AGING_THRESHOLD) {process.priority += AGING_BONUS;}}
}

特点：

• 优点：反映进程重要性

• 缺点：可能饥饿（低优先级进程）

• 解决方案：老化机制（Aging）

2.4 时间片轮转（RR - Round Robin）

// 最常用的调度算法
struct rr_scheduler {CircularQueue* queue;  // 循环队列int time_quantum;      // 时间片大小（通常10-100ms）
};void rr_schedule(struct rr_scheduler* sched) {while (!queue_empty(sched->queue)) {Process* p = dequeue(sched->queue);// 执行一个时间片int actual_time = min(sched->time_quantum, p->remaining_time);execute_for(p, actual_time);p->remaining_time -= actual_time;if (p->remaining_time > 0) {enqueue(sched->queue, p);  // 重新入队} else {process_complete(p);}}
}

特点：

• 优点：公平，响应性好

•  缺点：上下文切换开销大

• 性能：时间片大小很重要（太小：开销大；太大：响应慢）

示例（时间片=4）：

进程   执行时间
P1     24
P2     3
P3     3调度顺序：P1(4) → P2(3) → P3(3) → P1(4) → ...

2.5 多级队列调度（Multilevel Queue）

// 多个队列，不同调度策略
struct multilevel_scheduler {Queue* system_queue;    // 系统进程，高优先级Queue* interactive_queue; // 交互进程，RR调度Queue* batch_queue;     // 批处理进程，FCFS调度Queue* background_queue; // 后台进程，低优先级
};void multilevel_schedule(struct multilevel_scheduler* sched) {// 1. 首先调度系统队列if (!queue_empty(sched->system_queue)) {Process* p = dequeue(sched->system_queue);execute_process(p);return;}// 2. 然后交互队列（RR）if (!queue_empty(sched->interactive_queue)) {Process* p = dequeue(sched->interactive_queue);execute_for(p, TIME_QUANTUM);if (p->remaining_time > 0) {enqueue(sched->interactive_queue, p);}return;}// 3. 批处理队列（FCFS）// ... 以此类推
}

特点：

• 优点：区分进程类型，针对性优化

• 缺点：配置复杂，可能饥饿

2.6 多级反馈队列（MLFQ - Multilevel Feedback Queue）

// 最复杂的通用调度算法
struct mlfq_scheduler {Queue* queues[NUM_QUEUES];  // 多个优先级队列int time_quantums[NUM_QUEUES]; // 每个队列的时间片
};void mlfq_schedule(struct mlfq_scheduler* sched) {// 从最高优先级队列开始检查for (int i = 0; i < NUM_QUEUES; i++) {if (!queue_empty(sched->queues[i])) {Process* p = dequeue(sched->queues[i]);// 执行相应时间片execute_for(p, sched->time_quantums[i]);if (p->remaining_time > 0) {// 降级到下一队列if (i < NUM_QUEUES - 1) {enqueue(sched->queues[i + 1], p);} else {enqueue(sched->queues[i], p);  // 最低队列循环}} else {process_complete(p);}return;}}
}// 定期提升优先级（避免饥饿）
void mlfq_boost() {// 将所有进程移动到最高优先级队列for (int i = 1; i < NUM_QUEUES; i++) {while (!queue_empty(sched->queues[i])) {Process* p = dequeue(sched->queues[i]);enqueue(sched->queues[0], p);}}
}

特点：

• 优点：自适应，兼顾响应时间和吞吐量

• 缺点：实现复杂，参数调优困难

• 应用：Unix、Linux、Windows等现代操作系统

3. 调度算法对比表

4. 实时调度算法

4.1 最早截止时间优先（EDF - Earliest Deadline First）

// 动态优先级实时调度
struct edf_scheduler {PriorityQueue* queue;  // 按截止时间排序
};void edf_schedule(struct edf_scheduler* sched) {Process* p = pq_extract_min(sched->queue);  // 取截止时间最早的execute_process(p);// 检查是否满足截止时间if (current_time > p->deadline) {handle_deadline_miss();}
}

4.2 速率单调调度（RMS - Rate Monotonic Scheduling）

// 静态优先级实时调度
void rms_assign_priority() {// 周期越短，优先级越高for (each process) {process.priority = 1 / process.period;}
}

5. Linux调度器演变

CFS（Completely Fair Scheduler）

// Linux默认调度器
struct cfs_scheduler {RedBlackTree* runqueue;  // 红黑树，按vruntime排序
};void cfs_schedule(struct cfs_scheduler* sched) {// 选择vruntime最小的进程Process* p = rb_tree_min(sched->runqueue);// 计算动态时间片int timeslice = calculate_timeslice(p->weight);execute_for(p, timeslice);// 更新虚拟运行时间p->vruntime += actual_runtime * (NICE_0_LOAD / p->weight);
}

CFS特点：

• 使用红黑树高效管理进程

• 基于虚拟运行时间（vruntime）保证公平性

• 支持优先级（nice值）

• 时间复杂度：O(log n)

6. 调度算法性能指标

重要评估指标

struct scheduler_metrics {float throughput;          // 单位时间完成进程数float turnaround_time;     // 完成时间 - 到达时间float waiting_time;        // 等待CPU时间float response_time;       // 首次获得CPU时间float cpu_utilization;     // CPU利用率int context_switches;      // 上下文切换次数
};

7. 常见问题

Q1: RR算法中时间片大小如何选择？

答：时间片需要在响应时间和上下文切换开销之间权衡。通常10-100ms，太小则切换开销大，太大则响应性差。

Q2: 什么是 convoy 效应？

答：在FCFS算法中，一个长进程阻塞后面所有短进程的现象。

Q3: MLFQ如何避免饥饿？

答：通过定期提升所有进程的优先级（优先级boost）来避免低优先级进程永远得不到执行。

Q4: CFS如何保证公平性？

答：通过虚拟运行时间（vruntime）概念，每个进程的vruntime增加速度与其权重成反比，保证所有进程公平分享CPU。

Q5: 实时调度算法的区别？

答：EDF是动态优先级（按截止时间），RMS是静态优先级（按周期）。EDF利用率更高但实现复杂。

8. 算法选择建议

根据场景选择

• 桌面系统：CFS或MLFQ（响应性重要）

• 服务器：CFS或RR（公平性重要）

• 实时系统：EDF或RMS（保证截止时间）

• 嵌入式系统：优先级调度（资源受限）

• 批处理系统：SJF（吞吐量重要）

9.编程实现：模拟调度过程

模拟调度过程、计算平均等待时间或比较算法优劣。

我们来实现最经典的 时间片轮转 (RR) 算法模拟。

问题描述：
给定一组进程的到达时间和服务时间（CPU执行时间），以及时间片大小 quantum，模拟RR调度过程，计算每个进程的完成时间、周转时间和带权周转时间。

C++ 代码实现：

#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>using namespace std;struct Process {int id;int arriveTime; // 到达时间int burstTime;  // 服务时间/执行时间int remainingTime; // 剩余执行时间int finishTime; // 完成时间
};void simulateRR(vector<Process>& processes, int quantum) {queue<Process*> readyQueue; // 就绪队列int currentTime = 0;int completed = 0;int n = processes.size();// 初始化剩余时间for (auto& p : processes) {p.remainingTime = p.burstTime;}int idx = 0; // 用于遍历进程列表的索引cout << "\n时间片轮转 (RR) 调度模拟 (时间片Q = " << quantum << "):\n";cout << "时间\t进程\n";while (completed < n) {// 将当前时间点所有已到达的进程加入就绪队列while (idx < n && processes[idx].arriveTime <= currentTime) {readyQueue.push(&processes[idx]);idx++;}if (readyQueue.empty()) {// 就绪队列为空，时间推进到下一个进程到达currentTime = processes[idx].arriveTime;continue;}Process* currentProcess = readyQueue.front();readyQueue.pop();cout << currentTime << "\tP" << currentProcess->id << " 开始执行\n";// 执行一个时间片int timeSpent = min(quantum, currentProcess->remainingTime);currentTime += timeSpent;currentProcess->remainingTime -= timeSpent;// 再次将期间到达的新进程加入队列while (idx < n && processes[idx].arriveTime <= currentTime) {readyQueue.push(&processes[idx]);idx++;}// 如果进程还没执行完，重新放回就绪队列末尾if (currentProcess->remainingTime > 0) {readyQueue.push(currentProcess);cout << currentTime << "\tP" << currentProcess->id << " 时间片用完，重新入队\n";} else {// 进程执行完毕currentProcess->finishTime = currentTime;completed++;cout << currentTime << "\tP" << currentProcess->id << " 执行完成\n";}}// 计算并输出指标int totalTurnaround = 0;int totalWeightedTurnaround = 0;cout << "\n进程明细:\n";cout << "PID\t到达\t执行\t完成\t周转\t带权周转\n";for (const auto& p : processes) {int turnaround = p.finishTime - p.arriveTime;double weightedTurnaround = (double)turnaround / p.burstTime;totalTurnaround += turnaround;totalWeightedTurnaround += weightedTurnaround;cout << "P" << p.id << "\t"<< p.arriveTime << "\t"<< p.burstTime << "\t"<< p.finishTime << "\t"<< turnaround << "\t"<< fixed << setprecision(2) << weightedTurnaround << endl;}cout << "\n平均周转时间: " << (double)totalTurnaround / n << endl;cout << "平均带权周转时间: " << (double)totalWeightedTurnaround / n << endl;
}int main() {// 示例：4个进程，到达时间分别为0,1,2,3，执行时间分别为8,4,9,5vector<Process> processes = {{1, 0, 8}, // P1在时间0到达，需要执行8个单位时间{2, 1, 4}, // P2在时间1到达，需要执行4个单位时间{3, 2, 9}, // P3在时间2到达，需要执行9个单位时间{4, 3, 5}  // P4在时间3到达，需要执行5个单位时间};int timeQuantum = 4; // 时间片大小simulateRR(processes, timeQuantum);return 0;
}

结果：

1. 必知概念：

   • 能清晰说出FCFS、SJF、RR、MLFQ的核心思想和优缺点。

   • 理解抢占式 vs 非抢占式调度的区别。

   • 知道响应时间和周转时间分别对什么类型的应用更重要（交互式 vs 批处理）。

2. 必会分析：

   • 给定一个进程序列和调度算法（如RR），能手工模拟调度过程，画出甘特图。

   • 能计算平均等待时间和平均周转时间。

   • 能解释为什么SJF能获得最短平均等待时间，以及什么是“护航效应”。

3. 深入问题：

   • Linux的CFS调度器是基于什么原则？（完全公平调度，基于虚拟运行时间vruntime）

   • 多级反馈队列（MLFQ）是如何“反馈”的？（如果一个进程频繁用完时间片，说明是CPU密集型，降低其优先级；如果一个进程经常在时间片用完前阻塞，说明是I/O密集型，提高其优先级）

总结

进程调度是操作系统的核心功能：

• ✅ 算法多样性：不同算法适合不同场景

• ✅ 性能权衡：响应时间 vs 吞吐量 vs 公平性

• ✅ 现代趋势：CFS、MLFQ等自适应算法

• ✅ 实时需求：EDF、RMS等保证时序要求

4.死锁：条件及避免

//TODO:keep learning.