1.2 综合题：甘特图、资源冲突与 CPU 利用率

综合题的核心不是画得漂亮，而是同时满足两类约束：每个程序内部阶段顺序不能变；同一独占资源同一时刻只能服务一个程序。

1. 题目数据

程序 A：CPU 10 s → 设备甲 5 s → CPU 5 s → 设备乙 10 s → CPU 10 s。
程序 B：设备甲 10 s → CPU 10 s → 设备乙 5 s → CPU 5 s → 设备乙 10 s。

2. 单道环境

A 总长 40 s，其中 CPU 25 s；B 总长 40 s，其中 CPU 15 s。先 A 后 B，总时间 80 s，CPU 忙碌 40 s：

$$U_{CPU}=\frac{40}{80}=50\%.$$

单道环境中，作业等待设备时 CPU 不能转去运行另一作业，因此所有 I/O 等待都进入总时间。

3. 多道环境逐事件推进

时间	CPU	设备甲	设备乙	说明
0–10	A	B	空闲	A、B 各执行第一阶段
10–15	B	A	空闲	B 获得 CPU
15–20	B	空闲	空闲	A 等 CPU
20–25	A	空闲	B	两程序继续下一阶段
25–30	B	空闲	A	B 的第二段 CPU
30–35	空闲	空闲	A	B 等待设备乙
35–45	A	空闲	B	两程序同时完成最后阶段

总完成时间 45 s；CPU 忙碌仍为 40 s，所以

$$U_{CPU}=\frac{40}{45}\approx 88.9\%.$$

最容易漏掉的是 30–35 s：A 占用设备乙，B 的下一阶段也要设备乙，二者都不能使用 CPU，故 CPU 空闲。多道程序能减少空闲，却不保证消灭所有空闲。

4. 通用事件推进算法

每到一个事件时刻，依次做三件事：释放刚完成的资源；把程序推进到下一阶段并加入对应资源等待队列；给空闲资源选择可运行阶段。时间跳到下一次完成事件，而不是每秒模拟。

busy_cpu = [(0, 10), (10, 20), (20, 25), (25, 30), (35, 45)]
finish = 45
busy = sum(end - start for start, end in busy_cpu)
print("CPU busy:", busy)
print("finish:", finish)
print("utilization: {:.1%}".format(busy / finish))

5. 作答检查表

1. 是否保持每个程序的阶段顺序？
2. 同一资源是否出现重叠占用？
3. 等待区间是否明确标出原因？
4. 利用率分子只算忙碌时间，分母用全部程序完成时刻。
5. 百分比是否保留合理精度并写单位？

验收

闭卷复画表格，并解释为什么 30–35 s 不能让 B 使用设备乙或让 A 使用 CPU。只写 88.9% 而无资源时间线，不算完成综合题。