有以下进程需要调度执行见下表。

进程名	到达时间/ms	运行时间/ms
P1	0.0	9
P2	0.4	4
P3	1.0	1
P4	5.5	4
P5	7	2

问答题如果采用非抢占的短进程优先调度算法，请问这5个进程的平均周转时间和平均响应时间分别是多少?

【正确答案】10.6ms 6.6ms

【答案解析】

问答题如果采用抢占的短进程优先调度算法，请问这5个进程的平均周转时间和平均响应时间分别是多少?

【正确答案】6.8ms 2.8ms

【答案解析】

问答题采用非抢占的短进程优先调度算法存在平均周转时间较大的问题。为了降低平均周转时间，有这样一种解决方案：依旧采用非抢占的短进程优先调度算法，但当就绪队列中只有一个进程等待运行时，不马上运行这个进程，而是让这个进程等待1个单位的时间，然后再选择一个运行时间短的进程投入运行。请问采用这种方法上述5个进程的平均周转时间和平均响应时间分别是多少?

【正确答案】7.48ms 3.48ms

【答案解析】

问答题设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明：
(1)开始运行后，CPU有无空闲等待?若有，在哪段时间内等待?计算CPU的利用率。
(2)进程A运行时有无等待现象?若有，在什么时候出现等待现象?
(3)进程B运行时有无等待现象?若有，在什么时候出现等待现象?

【正确答案】如图所示。 (1)存在CPU空闲(在进程A运行后100～150ms，进程A正打印，进程B正输入)。CPU利用率为(300-50)÷300=83.3%。 (2)进程A运行后无等待现象。 (3)进程B运行后有等待现象(在A开始180～200ms；或进程B在运行后130～150ms)。

【答案解析】

问答题桌子上有一只盘子，每次只能放入或取出一个水果。现有许多苹果和橘子。一家4口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P操作、V操作来实现4人之间的同步算法。

【正确答案】盘子为互斥资源，只能放入一个水果，设信号量empty初值为1；爸爸放苹果前先看看有无空间，若有则抢盘子，放入苹果后向女儿发信号；妈妈放橘子前先看看有无空间，若有则抢盘子，放入橘子后向儿子发信号；女儿先看有无苹果，若有则抢盘子，取走苹果后发出盘子置空的信号；儿子看有无橘子，若有则抢盘子，取走橘子后发出盘子置空的信号；置空信号应是爸爸和妈妈都可以接收的。该题是生产者/消费者问题的变形，有两对生产者和消费者。生产者需要指明是给哪个消费者的产品，但消费者取走产品后无须特别通知某个生产者，因为空出的缓冲区可由两个生产者随意争夺。此处无须设置信号量控制对盘子的互斥访问，因为盘子只能放一个产品；apple表示盘中有苹果，orange表示盘中有橘子，初值均为0。 Parbegin 爸爸:begin L1:p(empty); 放苹果; V(apple); Goto L1; end; 妈妈:begin L2:P(empty); 放橘子; V(orange); Goto L2; end; 女儿:begin L3:P(apple); 取苹果; V(empty); Goto L3; end; 儿子:begin L4:p(orange); 取橘子; V(empty); Goto L4; end; Parend

【答案解析】

问答题 8位哲学家围坐一方桌，桌子每边坐2位，每位哲学家面前放一盘面条，桌子四角和每一边(中间)各放着一把叉子。哲学家只进行两种活动：吃饭和思考问题。当一位哲学家感到饥饿时，先取自己边上的叉子，拿到之后，再取自己角上的叉子，两把叉子到手才能用餐，吃完后把两把叉子放回原处。写一段程序描述哲学家的行为，并讨论这种安排是否可能导致死锁。

【正确答案】对8位哲学家顺序编号为：P1，P2，P3，P4，P5，P6，P7，P8，对8个叉子顺序编号为：1，2，3，4，5，6，7，8。讨论每个哲学家的行为过程，再总结出规律，发现下标为奇数的哲学家是先拿左边的叉子，再拿右边的叉子；下标为偶数的哲学家先拿右边的叉子，再拿左边的叉子。由此得到以下程序，信号量S[i]的初值均为1。又因为编号P8的哲学家拿起的是8号和1号叉子，因此用取余运算令其返回1。 if(i%2==0) { P(S[i]); P(S[(i+1)%8]); 吃; V(S[i]); V(S[(i+1)%8]); } else { P(S[i+1]); P(S[i]); 吃; V(S[i+1]); V(S[i]); } 该题不可能死锁。死锁产生的条件是所有的哲学家都从同一边拿起叉子，导致每个进程占用一个资源(叉子)而等待另一个资源，但该题的取叉子方式避免了这一现象。

【答案解析】

问答题下面是两个并发执行的进程。它们能正确运行吗?若不能请举例说明，并改正之。
Var x:integer;
Process p1 Process p2
Var y,z:integer; Var t,u:integer;
Begin Begin
x:=1; ① x:=0; ②
y:=0; ③ t:=0; ⑥
if x＞=1 then y:=y+1; ④ if x＜=1 then t:=t+2; ⑦
z:=y; ⑤ u:=t; ⑧
end end

【正确答案】遍历x是两个进程的共享资源，在进程同时申请访问时很容易出错。若采用顺序执行的方法，结构为y=1，z=1，t=2，u=2；若采用并发的方式，并按顺序①②③④⑤⑥⑦⑧执行，则结果为y=0，z=0，出错。改正的方法是为临界资源x设置信号量S，初值为1。程序如下： Parbegin Var x:integer; Process P1 Process P2 Vat y,z:integer; Var t,u:integer; Begin Begin P(S); P(S); x:=1; ① x:=0; ② y:=0; ③ t:=0; ⑥ if x＞=1 then y:=y+1; ④ if x＜=1 then t:=t+2; ⑦ V(S); V(S); z:=y; ⑤ u:=t; ⑧ end end Parend

【答案解析】

问答题兄弟俩共同使用一个账号，每次限存或取10元，存钱与取钱的进程分别如下所示：
begin
amount:integer:
amount:=0;
cobegin
Process SAVE
m1:integer:
begin
m1:=amount:
m1:=m1+10;
amount:=m1;
end;
Process TAKE
m2:integer;
begin
m2:=amount;
m2:=m2-10;
amount:=m2;
end;
coend;
end;
由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第3次存钱的时候弟弟在取钱，请问最后账号amount上面可能出现的值?如何用P操作、V操作实现两并发进程的互斥执行?

【正确答案】哥哥存两次钱后，amount=20，第三次存钱时，弟弟正在取钱，因没有对amount互斥操作，故发生错误。最后amount上可能出现的值应与两进程相对执行速度有关；若TAKE执行结束后SAVE才开始，则剩20元；若SAVE执行结束后TAKE才开始，也剩20元；问题就出在两个进程交替使用CPU时，则会出现不同值。关键在于最后被执行的语句是amount:=m1，还是amount:=m2，若先amount:=m1后amount:=m2，则amount=10，反之，先amount:=m2后amount:=m1，则amount=30。设信号量mutex(初值为1)控制两进程对变量amount的互斥使用。正确过程如下： begin amount:integer; amount:=0; cobegin Process SAVE m1:integer; Begin P(mutex); m1:=amount; m1:=m1+10; amount:=m1; V(mutex); end; Process TAKE m2:integer; Begin P(mutex); m2:=amount; m2:=m2-10; amount:=m2; V(mutex); end; coend; end;

【答案解析】

问答题战地指挥官通过无线电不断地向他的3个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“acknowledgement”之后才能下达新的指令。请使用P操作、V操作进行指挥官和士兵之间的协同管理，并对解题思路进行简要解释。

【正确答案】思路如下： type semaphore=monitor; var acknowledgement1,acknowledgement2,acknowledgement3:boolean; x,y:condition; a,b,c:integer; 指挥官:begin while acknowledgement1==false or acknowledgement2==false or acknowledgement3==false do x.wait; 下达命令; a:=1; b:=1; c:=1; y.signal; end 士兵1:begin while a==0 do y.wait; 接收命令; acknowledgement1=true; x.signal; end 士兵2:begin while a==0 do y.wait; 接收命令; acknowledgement2:true; x.signal: end 士兵3:begin while a==0 do y.wait; 接收命令; acknowledgement3:true; X.signal; end begin a:=0; b:=0; c:=0; acknowledgement1:=false; acknowledgement2:=false; acknowledgement3:=false; end

【答案解析】

问答题假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。用信号量实现该过程。

【正确答案】读者有任意多个，但进入阅览室读最多为100人，为此可设一个信号量s，代表空座位的数目；另登记表为临界资源，需设一个用于互斥的信号量mutex，防止2个及2个以上的读者进程同时对此表访问。每个读者的动作包括进入、阅读、离开。 struct semaphore:s,mutex=100,1; cobegin void readeri(void)(i=1,2,...,k) { while(TRUE) { P(s); P(mutex); 查登记表,置某座位为占用; V(mutex); ... reading; ... P(mutex); 查登记表,置某座位为空; V(mutex); V(s); } } coend

【答案解析】