提交时间和估计运行时间由下表给出：

作业 提交时间 估计运行时间（分钟） 1 8：00 60 2 8：20 35

3 8：25 20 4 8：30 25 5 8：35 5 6 8：40 10

系统采用短作业优先调度算法，作业被调度进入系统后中途不得退出。但作业运行时可被更短的作业抢占。分别给出6个作业的执行时间序列，作业的周转时间， 平均周转时间。

答：

作业的执行顺序为：1（8：20），2（8：25），3（8：45），5（8：50），6（9：00），4（9：25），2（9：55），1（10：35）

作业1的周转时间 = 155 min 作业2的周转时间 = 95 min 作业3的周转时间 = 20 min 作业4的周转时间 = 55 min 作业5的周转时间 = 15 min 作业6的周转时间 = 20 min

作业的平均周转时间为：360/6=60

3.20 在一个实时系统中有4个周期性事件，周期分别为50、100、150、200ms。假设其处理时间分别需要30、25、20和xms，则该系统可调度允许的x值最大为多少？ 解:

30/50 + 25/100 +150/20 +200/x =1 X = 10/3

3.21 某系统的进程状态变化如图3.23所示，该系统的进程调度为非抢占方式，根据该状态图叙述系统的调度策略、调度效果。 低优先级就绪 运行 其次选择100ms 首先选择100ms

阻塞 高优先级就绪

图3.23 状态变化图

y答：首先采用优先权高者优先调度算法，然后采用时间片为100ms的调度算法。

该调度算法如果调度效果考虑更周到的话，应该让阻塞队列上的进程唤醒后进入低优先级就绪队列，这样能够保证优先级高的进程及时调度，优先级低的进程能够合理的得到调度。

第4章

4.13 如果有n个进程共享一个互斥段

（1）如果每次只允许一个进程进入互斥段。

（2）如果每次最多允许m个进程同时进入互斥段（m

（1）互斥信号量初值为1，变化范围为[-n+1，1]。 当没有进程进入互斥段时，信号量值为1；

当有1个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为0； 当有1个进程进入互斥段，有1个进程等待进入互斥段时，信号量值为-1； 最多可有n-1个进程等待进入互斥段，故此时信号量的值为-（n-1）。 （2）互斥信号量初值为m，变化范围为[m-n，m]。 当没有进程进入互斥段时，信号量值为m；

当有1个进程进入互斥段时，但没有进程等待进入互斥段时，信号量值为m-1； 当有m个进程进入互斥段，但没有进程等待进入互斥段时，信号量值为0； 当有m个进程进入互斥段，有1个进程等待进入互斥段时，信号量值为-1； 最多可有n-m个进程等待进入互斥段，故此时信号量的值为-（n-m）。

4.14 在两条双向道路的交叉路口，没有行人通过，只有汽车通过。交通情况如 下：

（1）任何给定的时刻只能有一辆车过马路；

（2）当一辆车到达交叉路口并且另一条街道上没有车来到的时候，应该允许此车通过；

（3）当两个方向上都有车到达的时候，它们应该轮流通过，以防止在其中一个方向上的无限期延迟。

用信号量操作实现道路交通问题。 解：

semphore S1=0,S2=0;//有无车到达，为0时无到达 semphore M1=1,M2=0;//路中被占 P1:

if(车到达) v(S1);

while(!S1); if(!S2) 过一辆车； else {

p(M2);

p(M1);

过一辆车； v(M1); } P2:

if(车到达) v(S2);

while(!S2); if(!S1) 过一辆车； else {

p(M1); p(S2);

过一辆车； v(M2); }

4.15 在哲学家进餐问题中，假设5个哲学家中第i个执行下面的代码段 p(mutex); p(fork[i]);

p(fork[i+1%5]); v(mutex); eat;

v(fork[i]);

v(fork[i+1%5]);

（1）说明这段代码是否满足哲学家进餐问题的所有需求。

（2）如果V(mutex)语句改在第二个V()操作之后，或者在两个P()操作之间，说明这两种解决方法是改进了算法还是变坏了算法。 答：

(a)满足 (b)都不行

4.16 有两个优先级相同的进程P1和P2，各自执行的操作如下，信 号量S1和S2的初值都为0，试问P1、P2并发执行后，x、y、z 的值各为多少？

P1： P2： begin begin

y: = 1; （1） x: = 1; （5）

y: = y + 3; （2） x: = x + 5; （6） V(S1); P(S1);

z: = y + 1; （3） x: = x + y; （7） P(S2); V(S2);

y: = y + z; （4） z: = x + z; （8）

end; end;

答：语句（1）（2）（5）（6）不相交，任何执行顺序，结果相同。 情况1：语句（4）先执行x=10，y=9，z=15；

情况2：语句（8）先执行x=10，y=19，z=15；

情况3：语句（3）推迟到语句（8）之后，x不定，y=4，z不定；

?

4.17 两个进程A、B，考虑下面的信号量编码 semaphore s = 1; int x=10,y=2; fork(A，0); fork(B，0);

A( ) { B( ) { （1） x++; （4） if (x>10) （2） V(s); （5） x??; （3） y=x?2; （6） else {P(s); } x?? ;} } 分别说明（1）、（2）、（3）、（4）、（5）、（6）语句之后的x、y值为多少？ 答：

（1）x=11,y=2 (2) x=11,y=2 (3) x=11,y=9 (4)x=11,y=9 (5) x=10,y=9 (6) x=10,y=8

4.18 三个进程：输入、计算、输出。它们通过两个缓冲区传递数据，如图4.11所示。

每个缓冲区一次只能放入一条数据。写出用信号量进行同步。

解：var empty1,full1,empty2,full2:semaphore:=1,0,1,0; begin

parbegin I:begin repeat

wait(empty1); put to buffer1; signal(full1); until false;