# 实验二 处理器调度——实时调度算法 EDF 和 RMS

## 一、实验内容

深入理解处理器调度算法，了解硬实时概念，掌握周期性任务调度算法 EDF（Earliest Deadline First）和 RMS（Rate Monotonic Scheduling）的可调度条件，并能在可调度情况下给出具体调度结果。

在 Linux 环境采用用户级线程模拟 EDF 和 RMS：
- 给定实时任务，判断可调度性
- 创建线程按算法调度
- 用字符绘制 Gantt 图

## 二、实验设计

### 2.1 数据结构设计

```cpp
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 可调度性判断

```cpp
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 调度选择实现

```cpp
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 任务执行函数

```cpp
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 编译与运行

```bash
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 测试命令

```bash
# 编译
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 实验体会

本实验深入理解了实时调度算法：

1. **可调度性分析**：学会使用 EDF 和 RMS 的可调度条件判断任务集是否能被成功调度

2. **调度算法实现**：
   - EDF 是动态优先级调度，根据剩余时间选择任务
   - RMS 是静态优先级调度，周期越短优先级越高

3. **实时系统特点**：
   - 硬实时要求任务必须在截止时间前完成
   - EDF 理论利用率可达100%，但实现复杂
   - RMS 实现简单，但利用率有上限

4. **用户级线程模拟**：通过 pthread 互斥锁和信号量实现任务切换，理解了操作系统调度的基本原理