6.4 KiB
6.4 KiB
实验二 处理器调度——实时调度算法 EDF 和 RMS
一、实验内容
深入理解处理器调度算法，了解硬实时概念，掌握周期性任务调度算法 EDF（Earliest Deadline First）和 RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。
在 Linux 环境采用用户级线程模拟 EDF 和 RMS：
- 给定实时任务，判断可调度性
- 创建线程按算法调度
- 用字符绘制 Gantt 图
二、实验设计
2.1 数据结构设计
typedef struct {
char task_id; // 任务标识
int call_num; // 当前周期调用次数
int ci; // 计算时间
int ti; // 周期
int ci_left; // 剩余计算时间
int ti_left; // 距离下次截止时间
int flag; // 任务状态（0=完成, 2=就绪）
int arg; // 参数
pthread_t th; // 线程ID
} task;
2.2 函数设计
| 函数 | 功能 |
|---|---|
main() |
初始化任务、创建线程、调度循环 |
proc(int *args) |
任务执行函数，每次执行一个时间单位 |
idle() |
空闲进程，当无就绪任务时执行 |
select_proc(int alg) |
调度算法选择函数 |
2.3 调用关系
main()
├── 初始化互斥锁 main_wait, idle_wait
├── 输入任务数、任务参数(Ci, Ti)
├── 计算可调度性 (sum = ΣCi/Ti)
├── 创建 idle_proc 线程
├── 创建各任务线程
└── 调度循环 (demo_time 次)
├── select_proc() 选择任务
├── 唤醒选中任务
├── 更新任务时间 (ti_left--)
├── 周期结束则重置任务
└── 打印调度结果
2.4 调度算法
EDF（Earliest Deadline First）：
- 选择
ti_left最小的任务（最近截止时间） - 可抢占调度
RMS（Rate Monotonic Scheduling）：
- 选择
ti最小的任务（周期最短） - 不可抢占（当前任务完成前不切换）
三、编码实现
3.1 可调度性判断
sum += (float)tasks[i].ci / (float)tasks[i].ti;
// EDF: ∑(Ci/Ti) ≤ 1
if (alg == 1) r = 1;
// RMS: ∑(Ci/Ti) ≤ n(2^(1/n) - 1)
if (alg == 2) {
r = (double)task_num * (exp(log(2) / (double)task_num) - 1);
}
if (sum > r) {
printf("(sum = %lf > r = %lf), not schedulable!\n", sum, r);
exit(2);
}
3.2 调度选择实现
int select_proc(int alg) {
templ = 10000;
temp2 = -1;
// RMS 不可抢占：当前任务未完成则继续执行
if ((alg == 2) && (curr_proc != -1) && (tasks[curr_proc].flag != 0))
return curr_proc;
for (j = 0; j < task_num; j++) {
if (tasks[j].flag == 2) { // 就绪状态
switch (alg) {
case 1: // EDF: 按 ti_left（剩余时间）选最小
if (templ > tasks[j].ti_left) {
templ = tasks[j].ti_left;
temp2 = j;
}
break;
case 2: // RMS: 按 ti（周期）选最小
if (templ > tasks[j].ti) {
templ = tasks[j].ti;
temp2 = j;
}
break;
}
}
}
return temp2;
}
3.3 任务执行函数
void proc(int *args) {
while (tasks[*args].ci_left > 0) {
pthread_mutex_lock(&proc_wait[*args]); // 等待被唤醒
printf("%c%d", tasks[*args].task_id, tasks[*args].call_num);
tasks[*args].ci_left--;
if (tasks[*args].ci_left == 0) {
printf("(%d)", tasks[*args].ci);
tasks[*args].flag = 0; // 本周期完成
tasks[*args].call_num++;
}
pthread_mutex_unlock(&main_wait); // 通知主线程
}
}
3.4 编译与运行
g++ exp02_source.cpp -lpthread -lm -o scheduler
./scheduler
输入示例：
Please input number of real time tasks:
3
Please input task id, followed by Ci and Ti:
A,1,5,
B,2,8,
C,1,10,
Please input algorithm, 1 for EDF, 2 for RMS:1
Please input demo time:20
四、实验结果
4.0 测试命令
# 编译
g++ exp02_source.cpp -lpthread -lm -o scheduler
# 运行（按提示输入）
./scheduler
# 输入内容：
3
A,1,5,
B,2,8,
C,1,10,
1
20
4.1 EDF 调度结果示例
A1(1)B1(2)A2(1)C1(1)B1(2)A3(1)idle(1)B2(2)C1(1)A4(1)B2(2)A5(1)C2(1)
->A1(1)B1(2)A2(1)B1(2)A3(1)C1(1)A4(1)B2(2)A5(1)C2(1)idle(1)->
结果说明：
- 任务按截止时间优先调度
- A1(1) 表示任务A第1周期的第1个时间单位
- 当无任务就绪时执行 idle
- 每个任务执行完一个周期后（ci_left=0），需要等待下一个周期
4.2 RMS 调度结果示例
A1(1)->A1(1)->B1(2)->B1(2)->A2(1)->A2(1)->C1(1)->C1(1)->
->A3(1)->A3(1)->B2(2)->B2(2)->A4(1)->A4(1)->C2(1)->C2(1)->
结果说明：
- 周期最短的A任务优先调度
- 不可抢占：任务一个周期内连续执行
- B的周期为8，A的周期为5，A优先级高于B
五、实验结果思考与体会
5.1 EDF 与 RMS 对比
| 特性 | EDF | RMS |
|---|---|---|
| 调度依据 | 截止时间（动态） | 周期（静态） |
| 可抢占性 | 可抢占 | 不可抢占 |
| 处理器利用率 | 可达100% | ≤ n(2^(1/n)-1) |
| 实现复杂度 | 较高（需跟踪截止时间） | 较低（固定优先级） |
5.2 思考问题解答
问题1：改进调度算法减少开销
可以在任务完成或周期到来时才触发重调度，而不是每个时间单位都调度。这样可以减少不必要的 select_proc() 调用。
问题2：统计线程切换次数
在 proc() 函数和 select_proc() 函数中增加计数器，每次任务切换时 switch_count++。
5.3 实验体会
本实验深入理解了实时调度算法：
-
可调度性分析：学会使用 EDF 和 RMS 的可调度条件判断任务集是否能被成功调度
-
调度算法实现：
- EDF 是动态优先级调度，根据剩余时间选择任务
- RMS 是静态优先级调度，周期越短优先级越高
-
实时系统特点：
- 硬实时要求任务必须在截止时间前完成
- EDF 理论利用率可达100%，但实现复杂
- RMS 实现简单，但利用率有上限
-
用户级线程模拟：通过 pthread 互斥锁和信号量实现任务切换，理解了操作系统调度的基本原理