189 lines
4.8 KiB
Markdown
189 lines
4.8 KiB
Markdown
# 进程调度算法实验
|
||
|
||
## 实验目的
|
||
|
||
1. 理解进程调度的基本概念和原理
|
||
2. 掌握 FCFS、SJF、RR、优先级调度、HRRN、MLFQ 等算法
|
||
3. 通过模拟实验比较各算法的性能指标
|
||
|
||
## 实验环境
|
||
|
||
- Python 3.x
|
||
|
||
## 文件结构
|
||
|
||
```
|
||
experiment/
|
||
├── README.md # 实验文档
|
||
└── code/ # 代码目录
|
||
├── base.py # 基础类：Process, ProcessScheduler
|
||
├── main.py # 主程序入口
|
||
├── fcfs.py # 先来先服务调度
|
||
├── sjf.py # 短作业优先调度 (含 SRTF)
|
||
├── rr.py # 时间片轮转调度
|
||
├── priority.py # 优先级调度
|
||
├── hrrn.py # 高响应比优先调度
|
||
└── mlfq.py # 多级反馈队列调度
|
||
```
|
||
|
||
## 性能指标
|
||
|
||
设进程 $P_i$ 的到达时间为 $AT_i$，完成时间为 $CT_i$，服务时间为 $BT_i$，首次运行时间为 $ST_i$：
|
||
|
||
### 周转时间 (Turnaround Time)
|
||
|
||
$$
|
||
TAT_i = CT_i - AT_i
|
||
$$
|
||
|
||
**定义**：进程从提交到完成的总时间
|
||
|
||
**含义**：衡量进程在系统中停留的总时长，包括等待时间和实际运行时间
|
||
|
||
### 带权周转时间 (Weighted Turnaround Time)
|
||
|
||
$$
|
||
WTAT_i = \frac{TAT_i}{BT_i}
|
||
$$
|
||
|
||
**定义**：周转时间与服务时间的比值
|
||
|
||
**含义**：衡量进程的相对延迟，比值越大说明等待时间相对于服务时间越长
|
||
|
||
- $WTAT_i = 1$：理想情况，无额外等待
|
||
- $WTAT_i > 1$：存在等待时间
|
||
- $WTAT_i$ 越小越好
|
||
|
||
### 等待时间 (Waiting Time)
|
||
|
||
$$
|
||
WT_i = TAT_i - BT_i = (CT_i - AT_i) - BT_i
|
||
$$
|
||
|
||
**定义**：进程在就绪队列中等待的时间总和
|
||
|
||
**含义**：不包含实际运行时间，只计算等待 CPU 的时间
|
||
|
||
### 响应时间 (Response Time)
|
||
|
||
$$
|
||
RT_i = ST_i - AT_i
|
||
$$
|
||
|
||
**定义**：从提交到首次运行的时间
|
||
|
||
**含义**：用户感受到的"启动延迟"，对于交互系统尤为重要
|
||
|
||
### 性能指标总结
|
||
|
||
| 指标 | 公式 | 优化目标 | 适用场景 |
|
||
|------|------|----------|----------|
|
||
| 周转时间 | $CT - AT$ | 越小越好 | 批处理系统 |
|
||
| 带权周转时间 | $(CT-AT)/BT$ | 越小越好 | 公平性评估 |
|
||
| 等待时间 | $TAT - BT$ | 越小越好 | 调度算法比较 |
|
||
| 响应时间 | $ST - AT$ | 越小越好 | 交互系统 |
|
||
|
||
## 算法公式
|
||
|
||
### FCFS 周转时间
|
||
|
||
$$
|
||
TAT_i = \sum_{j=1}^{i} BT_j - AT_i \quad (AT_i \leq AT_{i+1})
|
||
$$
|
||
|
||
### SJF 平均等待时间最小化
|
||
|
||
$$
|
||
\min \frac{1}{n} \sum_{i=1}^{n} WT_i
|
||
$$
|
||
|
||
### RR 吞吐量
|
||
|
||
$$
|
||
\text{吞吐量} = \frac{n}{T_{\text{总}}} \quad \text{其中 } T_{\text{总}} = CT_{\text{max}} - AT_{\text{min}}
|
||
$$
|
||
|
||
### HRRN 响应比
|
||
|
||
$$
|
||
R = \frac{\text{等待时间} + \text{服务时间}}{\text{服务时间}} = 1 + \frac{WT}{BT}
|
||
$$
|
||
|
||
**特点**：
|
||
- 非抢占式
|
||
- 综合考虑等待时间和服务时间
|
||
- 避免长作业饥饿（等待时间越长，响应比越高）
|
||
|
||
## 算法对比
|
||
|
||
| 算法 | 类型 | 优点 | 缺点 |
|
||
|------|------|------|------|
|
||
| FCFS | 非抢占 | 简单、公平 | 平均等待时间长 |
|
||
| SJF | 非抢占/抢占 | 平均等待时间最优 | 长作业饥饿 |
|
||
| HRRN | 非抢占 | 避免长作业饥饿 | 开销较大 |
|
||
| RR | 抢占 | 响应时间短、公平 | 开销较大 |
|
||
| 优先级 | 抢占/非抢占 | 可控性强 | 低优先级饥饿 |
|
||
| MLFQ | 抢占 | 综合性能好 | 实现复杂 |
|
||
|
||
## 运行方式
|
||
|
||
```bash
|
||
cd code
|
||
|
||
# 使用演示数据（5个进程）
|
||
python main.py --demo
|
||
|
||
# 生成随机测试数据（默认5个进程，种子42）
|
||
python main.py
|
||
|
||
# 生成100个随机进程
|
||
python main.py -n 100
|
||
|
||
# 固定种子，生成1000个进程（可复现）
|
||
python main.py -n 1000 -s 42
|
||
|
||
# 自定义参数范围
|
||
python main.py -n 50 --arrival 0,100 --burst 5,50 --priority 1,5
|
||
|
||
# 运行指定算法
|
||
python main.py -n 20 -a FCFS,SJF,RR
|
||
|
||
# 每次运行使用不同随机数据
|
||
python main.py -n 20 -s -1
|
||
```
|
||
|
||
### 命令行参数说明
|
||
|
||
| 参数 | 说明 | 默认值 |
|
||
|------|------|--------|
|
||
| `-n, --num` | 进程数量 | 5 |
|
||
| `-s, --seed` | 随机种子 | 42（固定） |
|
||
| `-a, --algo` | 运行的算法 | 全部 |
|
||
| `--demo` | 使用预设演示数据 | False |
|
||
| `--arrival` | 到达时间范围 | 0,50 |
|
||
| `--burst` | 服务时间范围 | 1,20 |
|
||
| `--priority` | 优先级范围 | 1,10 |
|
||
|
||
### 预设演示数据
|
||
|
||
| PID | 到达时间 | 服务时间 | 优先级 |
|
||
|-----|----------|----------|--------|
|
||
| P1 | 0 | 7 | 3 |
|
||
| P2 | 2 | 4 | 1 |
|
||
| P3 | 4 | 1 | 4 |
|
||
| P4 | 5 | 4 | 2 |
|
||
| P5 | 6 | 2 | 3 |
|
||
|
||
## 思考题
|
||
|
||
1. 分析 FCFS 和 SJF 各自的优缺点
|
||
2. 为什么说 SJF 可以获得最短的平均等待时间？
|
||
3. RR 算法中，时间片大小对系统性能有何影响？
|
||
4. 多级反馈队列如何解决"长作业饥饿"问题？
|
||
5. 如何证明某种调度算法是最优的？
|
||
|
||
## 参考资料
|
||
|
||
- 操作系统概念（Abraham Silberschatz）
|
||
- 现代操作系统（Andrew S. Tanenbaum）
|