OS Chap.9 HW

本页面内容可能存在错误

题目 1

Consider the following set of processes:

Process Name	Arrival Time	Processing Time
A	0	1
B	1	9
C	2	1
D	3	9

Perform the same analysis as depicted in Table 9.5 and Figure 9.5 for this set.

题目内容： 对四个进程（A: 到达0/服务1；B: 到达1/服务9；C: 到达2/服务1；D: 到达3/服务9）进行调度算法分析。

概念检查 (Concept Check)

• 周转时间 (Turnaround Time, $T_r$): 进程从提交到完成的总时间 ($T_r = \text{完成时间} - \text{到达时间}$)。
• 归一化周转时间 (Normalized Turnaround Time): $T_r / T_s$，即周转时间与实际服务时间的比值。该值越接近1，说明进程遭受的延迟越小。

原理解析与步骤推演 (The 'Why')

这道题的数据设计非常巧妙，它完美暴露了非抢占式算法的致命缺陷。我们来推演四种经典算法的执行过程：

(1) FCFS (先来先服务) - 非抢占式

• t=0: A到达并执行，t=1完成。
• t=1: B到达并执行，t=10完成。
• t=10: C和D均已到达，C先到，C执行，t=11完成。
• t=11: D执行，t=20完成。
• 分析： A($T_r=1, T_r/T_s=1$)；B($T_r=9, T_r/T_s=1$)；C($T_r=9, T_r/T_s=9$)；D($T_r=17, T_r/T_s=1.89$)。

(2) SPN (最短进程优先) - 非抢占式

• t=0: A(服务1)执行，t=1完成。
• t=1: 此时系统中只有B(服务9)到达。因为是非抢占式，B一旦上CPU就不会下来。B执行至t=10完成。
• t=10: C(服务1)和D(服务9)均在等待。C更短，C执行，t=11完成。
• t=11: D执行，t=20完成。
• 分析： 调度顺序和时间与FCFS完全一模一样！短进程C虽然只需要1秒，但被迫等待了整整8秒。

(3) SRT (最短剩余时间) - 抢占式 为了解决SPN的缺陷，引入抢占机制。

• t=0: A执行，t=1完成。
• t=1: B到达，B开始执行。
• t=2: C到达(需1s)。此时B还剩8s。C的剩余时间更短，C抢占CPU！C执行至t=3完成。
• t=3: D到达(需9s)。此时B剩8s，D需9s。B更短，B恢复执行，至t=11完成。
• t=11: D执行至t=20完成。
• 分析：
  • A: $T_r = 1-0=1$, $T_r/T_s = 1$
  • B: $T_r = 11-1=10$, $T_r/T_s = 10/9 \approx 1.11$
  • C: $T_r = 3-2=1$, $T_r/T_s = 1/1 = 1$ (完美解决饥饿！)
  • D: $T_r = 20-3=17$, $T_r/T_s = 17/9 \approx 1.89$

(4) HRRN (最高响应比优先) - 非抢占式 响应比 $R = 1 + \text{等待时间}/\text{服务时间}$。

• t=0: A执行至1。
• t=1: B执行至10。
• t=10: 重新计算响应比：
  • C等待了8s，服务1s， $R_C = 1 + 8/1 = 9$。
  • D等待了7s，服务9s， $R_D = 1 + 7/9 \approx 1.77$。
• C响应比极高，C执行至11，随后D执行至20。
• 分析： 顺序依然是 A -> B -> C -> D。与 FCFS 和 SPN 完全一致。

常见易错点 (Common Pitfalls)

学生在做 SPN (最短进程优先) 时，经常会看到 C 只有 1s，就理所当然地认为 C 应该插队在 B 前面。绝对不行！ SPN 是非抢占式的，当 t=1 时，C 还没出生，系统根本不知道未来会有短进程，只能让 B 上台，而 B 一旦上台就必须执行到底。

---

题目 2

Consider the following pair of equations as an alternative to Equation (9.3):

$$S_{n+1} = \alpha T_n + (1 - \alpha) S_n$$

$$X_{n+1} = \min[Ubound, \max[Lbound, (\beta S_{n+1})]]$$

Where $Ubound$ and $Lbound$ are prechosen upper and lower bounds on the estimated value of $T$. The value of $X_{n+1}$ is used in the shortest-process-next algorithm, instead of the value of $S_{n+1}$.

What functions do $\alpha$ and $\beta$ perform, and what is the effect of higher and lower values on each?

题目内容： 分析公式 $S_{n+1} = \alpha T_n + (1 - \alpha) S_n$ 和 $X_{n+1} = \min[Ubound, \max[Lbound, (\beta S_{n+1})]]$ 中 $\alpha$ 和 $\beta$ 的作用及取值影响。

概念检查 (Concept Check)

在 SPN 或 SRT 等算法中，操作系统无法预知用户进程到底要跑多久。因此，必须利用过去的执行历史（$T_n$ 为第 n 次实际执行时间，$S_n$ 为第 n 次的预测时间）来估算下一次的执行时间（$S_{n+1}$）。

原理解析 (The 'Why')

1. 参数 $\alpha$ 的作用 (指数平滑因子)

• 功能： $\alpha$ 决定了操作系统在预测时，是更相信“最近一次的实际表现 ($T_n$)”，还是更相信“长期的历史平均 ($S_n$)”。
• 高低取值的影响：
  • 较高的 $\alpha$ (接近 1)： 系统对进程最近的变化反应极快（比如进程突然从 CPU 密集型变成了 I/O 密集型）。但缺点是，如果只是一次偶然的波动，预测值会产生剧烈的波动（抖动）。
  • 较低的 $\alpha$ (接近 0)： 系统更看重长期历史，预测曲线非常平滑。缺点是对突发变化的适应速度很慢。

2. 参数 $\beta$ 的作用 (延迟方差/安全冗余因子)

• 功能： $S_{n+1}$ 算出来仅仅是一个“平均预测值”。这意味着，在实际运行中，大概有 50% 的概率进程的真实时间会超过 $S_{n+1}$。$\beta$ 的作用是作为一个乘数因子（通常在 1.3 到 2.0 之间），给预测值加上一层“安全冗余”。
• 高低取值的影响：
  • 较高的 $\beta$ (如 2.0)： 预测值 $X_{n+1}$ 会被放大。这减少了“进程未执行完就被系统误判”的情况，但也削弱了系统挑选“最短进程”的敏锐度。
  • 较低的 $\beta$ (如 1.0 或更低)： 预测值紧贴平均值，系统能更快速地适应实际观察时间，但会导致预测误差带来的波动更大。

常见易错点 (Common Pitfalls)

不要把 $\alpha$ 的作用记反了。记住口诀：$\alpha$ 永远与最新的实际值 $T_n$ 绑定。$\alpha$ 越大，系统越“健忘”，越容易被眼前的数据牵着鼻子走。

---

题目 3

Define residence time $Tr$ as the average total time a process spends waiting and being served. Show that for FIFO, with mean service time $Ts$, we have:

$$Tr = \frac{Ts}{1 - \rho}$$

where $\rho$ is utilization.

题目内容： 证明在 FIFO 调度策略中，若平均服务时间为 $T_s$，利用率为 $\rho$，则平均周转时间 $T_r = \frac{T_s}{1 - \rho}$。

概念检查 (Concept Check)

• 排队论基础： 这是一个典型的 M/M/1 排队系统模型。
• 变量定义：
  • $T_r$ (Residence Time / Turnaround Time)：进程在系统中花费的总时间（包含排队等待时间 $W$ 和被服务的实际执行时间 $T_s$）。
  • $\rho$ (Utilization)：系统的处理器利用率，表示 CPU 有多大概率在忙碌。
  • $\lambda$ (Arrival Rate)：进程到达的速率。根据定义，$\rho = \lambda T_s$。

原理解析与推导步骤 (The 'Why')

证明过程：

1. 分解总时间： 一个进程进入系统后的总周转时间 $T_r$，等于它在就绪队列中排队的等待时间 $W$，加上它自己实际占用 CPU 的服务时间 $T_s$。

   $$T_r = W + T_s$$

2. 计算等待时间 $W$： 当一个新进程到达时，它需要等待排在它前面的所有进程都被处理完。根据排队论的 PASTA 定理（泊松到达见时间平均），新到达的进程看到的系统内平均进程数（包括正在排队和正在执行的）就是整个系统的平均进程数，设为 $q$。 因为是 FIFO 且处于平衡状态，每个进程的平均处理时间都是 $T_s$。所以，清空前面 $q$ 个进程所需的总时间就是：

   $$W = q \times T_s$$

3. 引入利特尔法则 (Little's Law)： 利特尔法则告诉我们，系统内的平均进程数 $q$ 等于到达率 $\lambda$ 乘以进程在系统内的平均总逗留时间 $T_r$。即：

   $$q = \lambda \times T_r$$

4. 合并替换： 将 $q$ 的表达式代入 $W$ 的公式中：

   $$W = (\lambda \times T_r) \times T_s$$

   我们知道利用率 $\rho = \lambda \times T_s$。整理可得：

   $$W = \rho \times T_r$$

5. 得出最终公式： 把 $W$ 的结果带回步骤1的公式中：

   $$T_r = \rho T_r + T_s$$

   $$T_r - \rho T_r = T_s$$

   $$T_r (1 - \rho) = T_s$$

   $$T_r = \frac{T_s}{1 - \rho}$$

   证明完毕。

常见易错点 (Common Pitfalls)

这个推导的核心在于巧妙地利用了 Little's Law ($q = \lambda T_r$) 将未知的等待队列长度 $q$ 转换成了包含 $T_r$ 的表达式。很多学生在推导时，试图用微积分或复杂的概率密度函数去硬解，反而会陷入死胡同。

你好！我是你的专属操作系统专家导师。你带来的这批题目（4~10题）非常精彩，它们不仅是操作系统中“进程调度”与“多道程序系统”的精髓，更是各类考试中最容易“挖坑”的计算大题。

尤其是**“多道限制下的双层调度（第8、9题）”**，它要求你同时扮演“长程调度器（决定谁进内存）”和“短程调度器（决定谁上CPU）”两个角色。

请放心，我会继续运用**“概念核对 (Concept Check)”、“底层的为什么 (The 'Why')”以及“易错点 (Common Pitfalls)”**的模式，为你逐一拆解这些硬核题目。

---

4、证明短作业优先 (SJF) 算法能获得最小平均周转时间

题目内容： 若后备作业队列中等待运行的同时有N个作业 $J_1, J_2, \dots, J_n$，已知它们各自的运行时间为 $t_1, t_2, \dots, t_n$，且满足 $t_1 < t_2 < \dots < t_n$。试证明采用短作业优先算法调度能获得最小平均周转时间。

概念核对 (Concept Check)

• 周转时间 (Turnaround Time)： 作业从提交到完成的总时间。由于这 $N$ 个作业是“同时”在队列中等待的，所以某个作业的周转时间 = 它自己的等待时间 + 它的运行时间。

原理解析与证明 (The 'Why')

假设这 $N$ 个作业按照某种任意的顺序执行，我们把它们实际执行的顺序记为：第1个执行的运行时间为 $x_1$，第2个为 $x_2$，...，第 $n$ 个为 $x_n$（注意这里的 $x$ 是打乱后的 $t$）。

1. 第1个作业执行时，后面 $n-1$ 个作业都在陪着它等。因此，$x_1$ 这段执行时间，被累计计入了 $n$ 个作业的周转时间中。
2. 第2个作业执行时，$x_2$ 被累计计入了 $n-1$ 个作业的周转时间中。
3. 依此类推，第 $n$ 个作业执行时，只有它自己在跑， $x_n$ 被累计计入 $1$ 次。

总周转时间 $Sum$ 的公式可以写为 [cite: 160]： $Sum = n \cdot x_1 + (n-1) \cdot x_2 + (n-2) \cdot x_3 + \dots + 1 \cdot x_n$ 平均周转时间 $T = Sum / n$。

证明： 为了让 $Sum$（也就是平均周转时间 $T$）尽可能地小，根据数学上的排序不等式原理（或贪心思想）：我们必须把最小的值分配给最大的权重（乘数）。

• 最大的乘数是 $n$，所以应该把最短的时间分配给它，即 $x_1 = t_1$。
• 第二大的乘数是 $n-1$，所以应该把第二短的时间分配给它，即 $x_2 = t_2$。
• 以此类推，最终的执行顺序必须严格遵守 $x_1 < x_2 < \dots < x_n$。 这恰恰就是短作业优先 (SJF) 的调度逻辑。证毕。

---

5、单处理器经典调度算法模拟

题目内容： 5个作业在时刻0按次序1、2、3、4、5进入系统。运行时间分别为10, 1, 2, 1, 5；优先权分别为3, 1, 3, 4, 2（数值小优先权高）。求 FCFS、RR、SJF、非抢占优先权调度算法的执行次序、平均周转时间和平均带权周转时间。

详细讲解与答案

由于作业同时在时刻0到达，周转时间 = 完成时间，带权周转时间 = 周转时间 / 执行时间。

(1) 先来先服务 (FCFS)

• 执行次序： 1 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 4 $\rightarrow$ 5
• 完成时间 (周转时间)： 1:10, 2:11, 3:13, 4:14, 5:19
• 带权周转： 1:(10/10=1), 2:(11/1=11), 3:(13/2=6.5), 4:(14/1=14), 5:(19/5=3.8)
• 平均周转时间： $(10+11+13+14+19) / 5 = 67 / 5 = \mathbf{13.4}$
• 平均带权周转： $(1+11+6.5+14+3.8) / 5 = 36.3 / 5 = \mathbf{7.26}$

(2) 短作业优先 (SJF)

• 排序原则： 按照执行时间从短到长，时间相同则按到达次序(FCFS)。
• 执行次序： 2(1) $\rightarrow$ 4(1) $\rightarrow$ 3(2) $\rightarrow$ 5(5) $\rightarrow$ 1(10)
• 完成时间 (周转时间)： 2:1, 4:2, 3:4, 5:9, 1:19
• 带权周转： 2:(1/1=1), 4:(2/1=2), 3:(4/2=2), 5:(9/5=1.8), 1:(19/10=1.9)
• 平均周转时间： $(1+2+4+9+19) / 5 = 35 / 5 = \mathbf{7.0}$
• 平均带权周转： $(1+2+2+1.8+1.9) / 5 = 8.7 / 5 = \mathbf{1.74}$

(3) 非抢占优先权调度

• 排序原则： 优先权数值越小优先级越高。若优先级相同（如作业1和3），按到达次序先调度1。
• 执行次序： 2(优1) $\rightarrow$ 5(优2) $\rightarrow$ 1(优3) $\rightarrow$ 3(优3) $\rightarrow$ 4(优4)
• 完成时间 (周转时间)： 2:1, 5:6, 1:16, 3:18, 4:19
• 带权周转： 2:(1/1=1), 5:(6/5=1.2), 1:(16/10=1.6), 3:(18/2=9), 4:(19/1=19)
• 平均周转时间： $(1+6+16+18+19) / 5 = 60 / 5 = \mathbf{12.0}$
• 平均带权周转： $(1+1.2+1.6+9+19) / 5 = 31.8 / 5 = \mathbf{6.36}$

(4) 时间片轮转 (RR，假设时间片 q=1)

• 执行过程模拟 (队列轮转)：
  • t=1: 1(剩9)，2完成。
  • t=2: 3(剩1)。
  • t=3: 4完成。
  • t=4: 5(剩4)。
  • 后续由于2和4已完成，只剩下1、3、5轮转。t=7时3完成。t=14时5完成。最后剩下1跑完剩下的5个时间片（t=19完成）。
• 完成时间 (周转时间)： 2:2, 4:4, 3:7, 5:14, 1:19
• 带权周转： 2(2), 4(4), 3(3.5), 5(2.8), 1(1.9)
• 平均周转时间： $(2+4+7+14+19) / 5 = 46 / 5 = \mathbf{9.2}$
• 平均带权周转： $(2+4+3.5+2.8+1.9) / 5 = 14.2 / 5 = \mathbf{2.84}$

---

6、同时到达的5个作业调度 (包含 RR q=2)

题目内容： A(2), B(4), C(6), D(8), E(10) 同时到达。优先级 1~5（5为最高）。求下列情况的平均周转时间。

详细讲解与答案

(4) FCFS (按指定次序 C, D, B, E, A)

• 顺序：C(6) $\rightarrow$ D(8) $\rightarrow$ B(4) $\rightarrow$ E(10) $\rightarrow$ A(2)
• 完成时间：C:6, D:14, B:18, E:28, A:30
• 平均周转时间： $(6+14+18+28+30) / 5 = \mathbf{19.2 \text{ 分钟}}$

(3) 短作业优先 (SJF)

• 顺序：A(2) $\rightarrow$ B(4) $\rightarrow$ C(6) $\rightarrow$ D(8) $\rightarrow$ E(10)
• 完成时间：A:2, B:6, C:12, D:20, E:30
• 平均周转时间： $(2+6+12+20+30) / 5 = \mathbf{14.0 \text{ 分钟}}$

(2) 优先数算法 (5为最高级)

• 顺序：E(5级,10) $\rightarrow$ D(4级,8) $\rightarrow$ C(3级,6) $\rightarrow$ B(2级,4) $\rightarrow$ A(1级,2)
• 完成时间：E:10, D:18, C:24, B:28, A:30
• 平均周转时间： $(10+18+24+28+30) / 5 = \mathbf{22.0 \text{ 分钟}}$

(1) 时间片轮转算法 (RR, q=2) 获得两分钟时间片假设按 A,B,C,D,E 的初始顺序入队： 第一轮：A完成(2)；B剩2；C剩4；D剩6；E剩8。 第二轮：B完成(10)；C剩2；D剩4；E剩6。 第三轮：C完成(16)；D剩2；E剩4。 第四轮：D完成(20)；E剩2。 第五轮：E完成(22)。(注：总时间应该为30，前面算错：A2+B2+C2+D2+E2=10；第二轮 B2(12完成)+C2+D2+E2=18；第三轮 C2(20完成)+D2+E2=24；第四轮 D2(26完成)+E2=28；第五轮 E2(30完成)。)

• 正确完成时间： A:2, B:12, C:20, D:26, E:30
• 平均周转时间： $(2+12+20+26+30) / 5 = \mathbf{18.0 \text{ 分钟}}$

---

7、FCFS 与 HRRN 性能对比

题目内容： 单道批处理，3个作业。比较 FCFS 和 HRRN（最高响应比）性能。完成表格

作業	提交時間	運行時間	開始時間	完成時間	周轉時間	帶權周轉時間
1	10:00	2:00
2	10:10	1:00
3	10:25	0:25

平均作業周轉時間 T =平均作業帶權周轉時間 W =

详细讲解与答案

为了方便计算，将运行时间统一转换为分钟：1(120m), 2(60m), 3(15m)。

(1) FCFS 算法

• J1: 10:00~12:00。周转=120m。带权=1.0。
• J2: 12:00~13:00。周转=180m (10:10到达)。带权=180/60=3.0。
• J3: 13:00~13:15。周转=170m (10:25到达)。带权=170/15≈11.33。
• 性能： 平均周转 = $(120+180+170)/3 = \mathbf{156.67 \text{ 分钟}}$；平均带权 = $(1+3+11.33)/3 = \mathbf{5.11}$。

(2) HRRN (最高响应比优先) 算法

• 10:00: J1执行，至 12:00 结束。
• 12:00 重新计算响应比 $R = 1 + \text{等待时间}/\text{运行时间}$：
  • J2 已等 110m (12:00 - 10:10)。$R_2 = 1 + 110/60 = 2.83$。
  • J3 已等 95m (12:00 - 10:25)。$R_3 = 1 + 95/15 = 7.33$。
  • J3 响应比最高，抢得CPU。J3 运行 15m，至 12:15 结束。
• 12:15: 仅剩 J2，J2 运行 60m，至 13:15 结束。
• 性能指标：
  • J1: 周转=120m, 带权=1.0。
  • J3: 周转=110m (10:25~12:15), 带权=110/15=7.33。
  • J2: 周转=185m (10:10~13:15), 带权=185/60=3.08。
  • 平均周转 = $(120+110+185)/3 = 415/3 = \mathbf{138.33 \text{ 分钟}}$
  • 平均带权 = $(1+7.33+3.08)/3 = \mathbf{3.80}$

结论： HRRN 性能更好，因为它成功让极其短小的作业 J3 免受了长时间的饥饿等待，大幅拉低了平均值。

---

8、四道系统的双层调度 (内存容量限制 + SRT 抢占)

若有一个四道作业系统，如果在一段时间内先后有6个作业，它们提交和运行时间由下表给出(时间单位为分钟)。系统采用短作业优先(SJF)调度算法，作业被调度进入系统后中途不会退出，但是作业会被更短的作业抢占。问题： (1) 画图给出6个作业的执行时间序列； (2) 完成各个作业的开始时间、完成时间、周转时间和带权周转时间。 (3) 计算平均作业周转时间和平均作业带权周转时间。

作业序号	提交时间	运行时间	开始时间	完成时间	周转时间	带权周转时间
1	8:00	60
2	8:20	35
3	8:25	20
4	8:30	25
5	8:35	5
6	8:40	10

⚠️ 易错点 (Common Pitfalls)： 这是本卷最难的题目！题目明确说明这是**“四道作业系统”，这意味着内存中最多只能装入4个作业**。当第5个作业到达时，即便它再短，只要内存没空位，它就只能在“外存后备队列”死等！ 同时，“中途不退出但会被抢占”意味着进程调度是最短剩余时间优先 (SRT)。

详细讲解推演

• 8:00 J1(60) 到达。内存(1/4)。J1 运行。
• 8:20 J2(35) 到达。内存(2/4)。J1还剩40，J2比J1短，J2 抢占 J1。J2 运行。
• 8:25 J3(20) 到达。内存(3/4)。J2还剩30，J3比J2短，J3 抢占 J2。J3 运行。
• 8:30 J4(25) 到达。内存(4/4)。此时内存已满！ J3还剩15，继续运行。
• 8:35 & 8:40 J5(5) 和 J6(10) 到达。因为内存已满，它们被关在门外排队。
• 8:45 J3 执行完毕！内存腾出1个位置。作业调度器使用 SJF 检查门外排队的 J5(5) 和 J6(10)。J5 更短，J5 被调入内存。
  • 此时内存有 J1(剩40), J2(剩30), J4(25), J5(5)。J5 最短，J5 抢得CPU开始运行。
• 8:50 J5 执行完毕！内存腾出。J6 被调入内存。
  • 内存有 J1(40), J2(30), J4(25), J6(10)。J6 最短，J6 运行。
• 9:00 J6 执行完毕！外存没作业了。
  • 内存有 J1(40), J2(30), J4(25)。J4 运行。
• 9:25 J4 完毕。J2 恢复运行。
• 9:55 J2 完毕。J1 恢复运行。
• 10:35 J1 完毕。全剧终。

答案表格

作业	提交时间	运行时间	开始时间	完成时间	周转时间	带权周转时间
1	8:00	60	8:00	10:35	155	155/60 ≈ 2.58
2	8:20	35	8:20	9:55	95	95/35 ≈ 2.71
3	8:25	20	8:25	8:45	20	20/20 = 1.00
4	8:30	25	9:00	9:25	55	55/25 = 2.20
5	8:35	5	8:45	8:50	15	15/5 = 3.00
6	8:40	10	8:50	9:00	20	20/10 = 2.00
(注意：J4虽然8:30进内存，但9:00才真正“开始”分配到CPU)

• 平均周转时间： $(155+95+20+55+15+20) / 6 = 360 / 6 = \mathbf{60.0 \text{ 分钟}}$。
• 平均带权周转时间： $(2.58+2.71+1.00+2.20+3.00+2.00) / 6 = 13.49 / 6 \approx \mathbf{2.25}$。

---

9、两道系统双层调度 (内存容量 2 + 抢占式优先权)

题目内容： 两道作业系统。作业调度: SJF；进程调度: 抢占式优先数（越小越高）。A(10:00, 40m, 优5), B(10:20, 30m, 优3), C(10:30, 50m, 优4), D(10:50, 20m, 优6)。

作业名	提交时间	估计运行时间	优先数
A	10:00	40 分	5
B	10:20	30 分	3
C	10:30	50 分	4
D	10:50	20 分	6

详细讲解推演

• 10:00: A 到达。进内存 (1/2)。A(优5) 运行。
• 10:20: B 到达。进内存 (2/2，已满)。A 还剩 20m。B 的优先级(3)高于 A(5)，B 抢占 A。B 运行。
• 10:30 & 10:50: C 和 D 到达。因为内存已满，在外存队列等待。
• 10:50: B 运行 30m 结束！内存腾出 1 个空位。
  • 作业调度 (SJF)： 外存队列有 C(50m) 和 D(20m)。D 更短，D 被选中调入内存。
  • 进程调度 (抢占优先权)： 当前内存有 A(剩20m, 优5) 和 D(20m, 优6)。A 优先级比 D 高 (5<6)，所以 A 恢复运行。
• 11:10: A 执行结束！内存腾出 1 个空位。
  • 作业调度： 将 C(50m) 调入内存。
  • 进程调度： 内存有 D(20m, 优6) 和 C(50m, 优4)。C 优先级更高 (4<6)，C 抢占执行。
• 12:00: C 执行结束！D 开始执行。
• 12:20: D 执行结束！全剧终。

答案整理

• A: 10:00 进内存，11:10 结束。周转 = 70 分钟。
• B: 10:20 进内存，10:50 结束。周转 = 30 分钟。
• C: 11:10 进内存，12:00 结束。周转 = 90 分钟 (10:30~12:00)。
• D: 10:50 进内存，12:20 结束。周转 = 90 分钟 (10:50~12:20)。
• 平均周转时间： $(70+30+90+90) / 4 = \mathbf{70.0 \text{ 分钟}}$。

---

10、实时系统调度允许的最大执行时间

题目内容： 4个周期性事件，周期 $T$ 为 50, 100, 300, 250ms；处理时间 $C$ 为 35, 20, 10, $\delta$ ms。系统可调度的最大 $\delta$ 是多少？

原理解析 (The 'Why')

实时系统的核心指标是 CPU 利用率 ($U$)。利用率定义为所有任务处理时间与其周期的比值之和：$U = \sum \frac{C_i}{T_i}$。

• 如果采用固定的速率单调调度 (RMS)，能保证调度的理论安全上限大约是 0.69（针对无限个任务），本题若严格按RMS算将不满足。
• 通常在这种不指定具体算法求绝对理论上限的考题中，我们使用动态调度算法（如最早截止时间优先 EDF）的理论极限，即只要总CPU利用率不超过 100%（$\sum U_i \le 1$），系统在理论上就是“可调度的” [cite: 120]。

计算步骤： 前 3 个任务的利用率为： $U_{1,2,3} = \frac{35}{50} + \frac{20}{100} + \frac{10}{300} = 0.7 + 0.2 + 0.0333 \approx 0.9333$ 要让系统可调度，总利用率必须 $\le 1$： $0.9333 + \frac{\delta}{250} \le 1$$\frac{\delta}{250} \le 1 - 0.9333 = 0.0667$ （即 $1/15$） $\delta \le 250 \times \frac{1}{15} \approx 16.67 \text{ ms}$

答案： 该系统可调度允许的 $\delta$ 最大值为 $16.67 \text{ ms}$ （若要求整数则为 16 ms）。