東京大学情報理工学系研究科コンピュータ科学専攻 2016年8月実施専門科目II 問題4

标签：

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

单处理器调度如下五个进程，忽略上下文切换开销，执行时间均预先已知。

进程	A	B	C	D	E
到达时刻（ms）	0	30	40	40	80
执行时间（ms）	90	10	50	30	20

周转时间为到达至完成（含等待）的时间；等待时间为在就绪队列中的总时间；响应时间为到达至首次开始执行的时间。

（1）采用 FCFS 时，求平均周转、等待、响应时间。

（2）采用非抢占式 SJF 时，求上述三个平均值。

（3）采用抢占式 SJF 时，求上述三个平均值。

（4）采用时间片为 $20\rm\,ms$ 的轮转调度时，求上述三个平均值。时间片按 A、B、C、D、E 的顺序轮转；进程提前结束时下一个时间片立即开始。

（5）现令五个进程周期到达，首次到达时刻同上，周期如下。采用抢占式 Rate Monotonic 调度；周期越短优先级越高，周期相同时首次到达较早者优先级更高。求第一次截止期违约的时刻和进程。

进程	A	B	C	D	E
周期（ms）	200	100	400	100	100

对每个进程，使用

T_{\rm turn}=t_{\rm finish}-t_{\rm arrival},\qquad T_{\rm wait}=T_{\rm turn}-T_{\rm exec},\qquad T_{\rm resp}=t_{\rm first}-t_{\rm arrival}.

FCFS 的执行顺序为

A[0,90),\ B[90,100),\ C[100,150),\ D[150,180),\ E[180,200).

非抢占式 SJF 的顺序为

A[0,90),\ B[90,100),\ E[100,120),\ D[120,150),\ C[150,200).

抢占式 SJF（最短剩余时间优先）的执行区间为

A[0,30),\ B[30,40),\ D[40,70),\ C[70,80),\ E[80,100),\ C[100,140),\ A[140,200).

跳过尚未到达或已经结束的进程，可得

\begin{aligned} &A[0,20),A[20,40),B[40,50),C[50,70),D[70,90),E[90,110),\\ &A[110,130),C[130,150),D[150,160),A[160,180),C[180,190),A[190,200). \end{aligned}

固定优先级为

B>D>E>A>C.

到 $200\rm\,ms$ 为止的执行为

\begin{aligned} &A[0,30),B_1[30,40),D_1[40,70),A[70,80),E_1[80,100),\\ &A[100,130),B_2[130,140),D_2[140,170),A[170,180),E_2[180,200). \end{aligned}

进程 A 的首个实例只执行了 $30+10+30+10=80\rm\,ms$ ，还剩 $10\rm\,ms$ ，而其下一实例在 $200\rm\,ms$ 到达。因此第一次截止期违约发生在

\boxed{t=200\rm\,ms，进程\ A}.