(总分：99.97，做题时间：90分钟)
一、综合应用题(总题数：25，分数：100.00)
1.某分时系统中的进程可能出现如图所示的状态变化，回答下列问题：
(1)根据图示，该系统采用的是什么进程调度策略?
(2)把图示中的每一个状态变化的原因填在下表相应的栏中。
变化 1 2 3 4 5 6
（分数：4.00）
原因 __________________________________________________________________________________________ 正确答案：()
解析：题目中没有文字的框应该是就绪队列。(1)系统采用的是时间片轮转法(或者剥夺调度)策略。(2)1是调度程序选择了一个进程可以占用CPU；2是时间片到时；3、4是发出I/O请求；5、6是I/O完成。 假设一个计算机系统具有如下性能特征：处理一次中断，平均需要1ms；一次进程调度，平均需要2ms；将CPU分配给选中的进程，平均需要1ms。再假设其定时器芯片每秒产生100次中断。请同答：（分数：4.00） (1).操作系统将百分之几的CPU时间用于处理时钟中断?（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：系统每秒100次时钟中断，时间周期是10ms，因此10%的CPU时间用于时钟中断处理；
(2).如果操作系统采用轮转法调度，10个时钟中断为1个时间片，那么，操作系统将百分之几的CPU时间用于进程调度(包括调度、分配CPU和引起调度的时钟中断处理时间)?（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：10次时钟中断一个时间片，则一个时间片是100ms，因此进程调度占用CPU的时间是4%。 有以下进程需要调度执行见下表。
进程名 到达时间/ms 运行时间/ms P1 P2 P3 P4 P5 （分数：3.99）
0.0 0.4 1.0 5.5 7 9 4 1 4 2 (1).如果采用非抢占的短进程优先调度算法，请问这5个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）
__________________________________________________________________________________________ 正确答案：() 解析：10.6ms 6.6ms
(2).如果采用抢占的短进程优先调度算法，请问这5个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）
__________________________________________________________________________________________ 正确答案：() 解析：6.8ms 2.8ms
(3).采用非抢占的短进程优先调度算法存在平均周转时间较大的问题。为了降低平均周转时间，有这样一种解决方案：依旧采用非抢占的短进程优先调度算法，但当就绪队列中只有一个进程等待运行时，不马上运行这个进程，而是让这个进程等待1个单位的时间，然后再选择一个运行时间短的进程投入运行。请问采用这种方法上述5个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）
__________________________________________________________________________________________ 正确答案：() 解析：7.48ms 3.48ms
2.设某计算机系统有一块CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算50ms，打印信息100ms，再计算50ms，打印信息100ms，结束。进程B的运行轨迹为：计算50ms，输入数据80ms，再计算100ms，结束。试画出它们的时序关系图，并说明：
(1)开始运行后，CPU有无空闲等待?若有，在哪段时间内等待?计算CPU的利用率。 (2)进程A运行时有无等待现象?若有，在什么时候出现等待现象? (3)进程B运行时有无等待现象?若有，在什么时候出现等待现象?
（分数：4.00）
__________________________________________________________________________________________ 正确答案：() 解析：如图所示。
(1)存在CPU空闲(在进程A运行后100～150ms，进程A正打印，进程B正输入)。CPU利用率为(300-50)÷300=83.3%。 (2)进程A运行后无等待现象。
(3)进程B运行后有等待现象(在A开始180～200ms；或进程B在运行后130～150ms)。
3.桌子上有一只盘子，每次只能放入或取出一个水果。现有许多苹果和橘子。一家4口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P操作、V操作来实现4人之间的同步算法。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：盘子为互斥资源，只能放入一个水果，设信号量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
4.8位哲学家围坐一方桌，桌子每边坐2位，每位哲学家面前放一盘面条，桌子四角和每一边(中间)各放着一把叉子。哲学家只进行两种活动：吃饭和思考问题。当一位哲学家感到饥饿时，先取自己边上的叉子，拿到之后，再取自己角上的叉子，两把叉子到手才能用餐，吃完后把两把叉子放回原处。写一段程序描述哲学家的行为，并讨论这种安排是否可能导致死锁。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：对8位哲学家顺序编号为：P 1 ，P 2 ，P 3 ，P 4 ，P 5 ，P 6 ，P 7 ，P 8 ，对8个叉子顺序编号为：1，2，3，4，5，6，7，8。讨论每个哲学家的行为过程，再总结出规律，发现下标为奇数的哲学家是先拿左边的叉子，再拿右边的叉子；下标为偶数的哲学家先拿右边的叉子，再拿左边的叉子。由此得到以下程序，信号量S[i]的初值均为1。又因为编号P 8 的哲学家拿起的是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]); }
该题不可能死锁。死锁产生的条件是所有的哲学家都从同一边拿起叉子，导致每个进程占用一个资源(叉子)而等待另一个资源，但该题的取叉子方式避免了这一现象。
5.下面是两个并发执行的进程。它们能正确运行吗?若不能请举例说明，并改正之。 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
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：遍历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
6.兄弟俩共同使用一个账号，每次限存或取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操作实现两并发进程的互斥执行?
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：哥哥存两次钱后，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;
7.战地指挥官通过无线电不断地向他的3个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“acknowledgement”之后才能下达新的指令。请使用P操作、V操作进行指挥官和士兵之间的协同管理，并对解题思路进行简要解释。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：() 解析：思路如下： 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
8.假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。用信号量实现该过程。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：读者有任意多个，但进入阅览室读最多为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
用P操作、V操作解决读者/写者问题的正确程序如下： Semaphore:S,Sr; int rc: S=1;Sr=1;rc=0; Reader() { P(Sr); rc=rc+1;
if(rc==1) then P(S); V(Sr); read_file(); P(Sr); rc=rc-1;
if(rc==0) then V(S); V(Sr); }
Writer() { P(S);
write_file(); V(S); }
请回答：（分数：3.99）
(1).信号量Sr的作用；（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：Sr用于读者计数rc的互斥信号量；
(2).程序中什么语句用于读、写互斥，写、写互斥；（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：if rc==1 then P(S)中的P(S)用于读/写互斥，写者进程中的P(S)用于写、写互斥，读、写互斥。 (3).若规定仅允许5个进程同时读，怎样修改程序?（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：程序中增加一个信号量S5，初值为5，P(S5)语句加在读者进程P(Sr)之前，V(S5)语句加在读者进程第2个V(Sr)之后。
9.用信号量和P操作、V操作编写程序：多个读进程和多个写进程共享一个文件。要求： (1)写操作只能互斥、独立进行； (2)读操作可以同时共享读文件；
(3)当有写操作请求时，禁止新的读操作；有正在读文件的进程时，在读操作完成后进行写文件操作。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：() 解析：设置信号量：
readcount:=0,nwriter:=0,swriter:=1,mutex:=1,wrt:=1; 读者:P(swriter); if(nwriter==0) { P(mutex);
readcount:=readcount +1; if(readcount==1) P(wrt); V(mutex); V(swriter); } else { V(swriter); block(); } reading; P(mutex);
readcount:=readcount-1; if(readcount==0) V(wrt); V(mutex); 写者:P(swriter); nwriter:=nwriter+1; P(wrt); writing; P(swriter); nwriter:=nwriter-1; if(nwriter==0) { wakeup(读者进程); V(swriter); } else { V(wrt);
V(swriter); }
10.假设具有5个进程的集合P={P 0 ，P 1 ，P 2 ，P 3 ，P 4 }，系统中有3类资源A、B、C，假设在某时刻有如下状态：
请问当前系统是否处于安全状态?如果系统中的可利用资源Available为(0，6，2)，系统是否安全?如果系统处在安全状态，请给出安全序列；如果系统处在非安全状态，说明原因。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：首先在题目的初始条件上找安全序列。要想找安全序列，首先给出进程的剩余需求量，也就是在占有部分资源的基础上，还需要多少资源。列表如下：
检查系统剩余资源数(1，4，0)，看是否可以一次性满足某个进程的全部剩余需求量。找到P 0 和P 2 ，则选其一进入安全序列，并假设该进程已完成，然后将进入安全序列的进程所占有的资源回收，再检查是否可以一次性满足某个进程的全部剩余需求量。依次类推，最后如果所有进程都可以进入安全序列，则系统处于安全状态，不会死锁。本题第一问的答案是：当前系统处于安全状态，因为至少可以找到一个安全序列＜P 0 ，P 2 ，P 1 ，P 3 ，P 4 ＞(答案不定)。
如果系统中可用资源为(0，6，2)，则只可满足P 3 的要求，P 3 归还后，可满足P 4 的要求，P 4 归还后，可满足P 0 的要求，P 0 归还后，无法满足P 1 和P 2 的要求，即找不到安全序列，因此系统处在不安全状态。
一个系统中存在某类资源m个，被n(n≤m)个进程共享，即每个进程至少需要一个资源。资源的分配和释放必须一个一个地进行，请证明在以下两个条件下系统是否会发生死锁：（分数：4.00） (1).每个进程需要资源的最大数在1～m之间；（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：这里要进行一下特别的说明。题目中没有强调m与n的大小关系及取值范围，而实际上这点很重要，影响到该证明的正确与否。举例如下：假设m=6，根据题意，每个进程的最大需求资源数在1～6之间则不会死锁。但请考虑，如果有3个进程，且每个进程最大需要3个资源，则当每个进程占用2个资源的时候，死锁就已经发生，所以该问无法证明。
(2).所有进程需要的资源总数小于m+n。（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：用反证法。假设发生死锁，此时系统的资源已全部分配，即m个资源被n个进程占用，但所有进程仍处于等待状态，说明每个进程至少还需1个资源，n个进程还需要n个资源，即n个进程所需的资源总数至少是m+n个，这与已知条件相矛盾，假设不成立。
11.某银行计算机系统要实现一个电子转账功能，基本的业务流程是首先对转出方和转入方的账号进行加锁，然后进行转账业务，最后对转出方和转入方的账号进行解锁。如果不采取任何措施，系统会不会发生死锁?为什么?请设计一种能够避免死锁的方法。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：会死锁。因为对两个账户进行加锁操作是可以分割进行的，若此时有两个用户同时进行转账，P 先1 对账户A进行加锁，再申请账户B；P 2 先对账户B进行加锁，再申请账户A，此时死锁。解决办法是：可
以采用资源顺序分配法将A、B账户进行编号，用户转账时只能按照编号由小到大进行加锁；也可以采用资源预分配法，要求用户在使用资源之前将所有资源一次性申请到。
12.系统有同类资源m个，供n个进程共享，如果每个进程对资源的最大需求量为由，问m，n，k的值分别是下列情况时(见下表)，是否会发生死锁?
序号 m n k 是否会死锁 1 2 3
（分数：4.00）
说明 6 3 3 9 3 3 13 6 3 __________________________________________________________________________________________ 正确答案：()
解析：不发生死锁必须保证至少有1个进程可以得到所需的全部资源并执行完毕，若m≥n(k-1)+1则一定不会发生死锁(见下表)。
序号 1 2 3 m n k 是否会死锁 6 3 3 可能会 9 3 3 不会 13 6 3 不会 有3个进程P 1 、P 2 和P 3 并发工作。进程P 1 需用资源S 3 和S 1 ；进程P 2 需用资源S 1 和S 2 ；进程P 3 需用资源S 2 和S 3 。问：（分数：4.00）
(1).若对资源分配不加限制，会发生什么情况?为什么?（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：可能会发生死锁。
(2).为保证进程正确工作，应采用怎样的资源分配策略?列举出所有可能的方法。（分数：2.00） __________________________________________________________________________________________ 正确答案：()
解析：可有几种答案：
A．采用静态分配：由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象)。
B．采用按序分配：不会出现循环等待资源现象。 C．采用银行家算法：在分配时保证系统处于安全状态。
有一阅览室，读者进入时必须先在一张表上进行登记。该表为每一个座位列出一个表目(包括座位号、姓名、阅览时间)，读者离开时要撤销登记信息。阅览室有100个座位。（分数：4.00）
(1).为描述读者的动作，应编写几个程序，应设置几个进程?程序和进程之间的对应关系如何?（分数：2.00） __________________________________________________________________________________________ 正确答案：()
解析：在本题中，每个读者都可视为一个进程，有多少读者就有多少进程。这些进程称为读者进程，设为P i (i=0，1，…)。读者进程P i 执行的程序包括：登记、阅览和撤销。每个读者进程的活动都相同，所以其程序也相同。进程和程序的关系是各读者进程共用同一程序。 (2).试用P，V操作描述这些进程间的同步关系。（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：在读者进程所执行的程序中，对登记和撤销都需互斥执行，其信号量的初值为1，而对进入阅览室也需互斥执行，其信号量为100。现用P，V操作描述如下： 读进程P i (i=0,1,...) P(S1)
P(S2) 登记 V(S2) 阅览 P(S2) 撤销 V(S2) V(S1)
其中信号量S1的初值为100，信号量S2的初值为1。
13.有一只铁笼子，每次只能放入一只动物。猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用P，V操作写出能同步执行的程序。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲器。生产者各自生产不同的产品，消费者各自取自己需要的产品。利用P，V操作编程为： begin
semaphore:S,S1,S2; Parbegin Process hunter begin
L1:have a tiger; P(S); put a tiger; V(S1); go to L1; end;
Process peasant begin
L2:have a pig; P(S); put a pig; V(S2); go to L2; end;
Process hotel begin L3:P(S1); get a pig; V(S); eat a pig; go to L3; end; Process zoo begin L4:P(S2); get a tiger; V(S);
eat a tiger; goto L4; end; parend
14.有三个进程P A ，P B 和P C 合作解决文件打印问题：P A 将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；P B 将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；P C 将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V操作来保证文件的正确打印。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：在本题中，进程PA，PB，PC之间的关系为：PA与PB共用一个单缓冲区，而PB又与PC共用一个单缓冲区。当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC可以打印记录。在其他条件下，相应进程必须等待。事实上，这是一个生产者—消费者问题。
为遵循这一同步规则，应设置四个信号量empty1，empty2，full1，full2，信号量empty1及empty2分别表示缓冲区1及缓冲区2是否为空，其初值为1；信号量full1及full2分别表示缓冲区1及缓冲区2是否有记录可供处理，其初值为0。其同步描述如下： int empty1=1; int empty2=1; int full1=0; int full2=0; main() { cobegin PA(); PB(); PC(); coend } PA() { while(1) { 从磁盘读一个记录: P(empty1); 将记录存入缓冲1; V(full1); } } PB() { while(1) {
从缓冲区1中取出记录: V(empty1); P(empty1); 将记录存入缓冲2; V(full2); } } PC() { while(1) {
P(full2);
从缓冲区2中取出记录; V(empty2); 打印记录; } }
本题也是一个典型的生产者一消费者问题。其中的难点在于PB既是一个生产者又是一个消费者。 15.某数据库有一个写进程，多个读进程，它们之间读、写操作的互斥要求是：写进程正在写该数据库时不能有其他进程读该数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。请用信号量及P、V操作描述这一组进程的工作过程。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：在本题中，允许读进程同时读数据库，但写进程正在写数据库时不允许其他进程读数据库，也不允许其他进程写该数据库。为了解决读、写进程之间的同步，应设置两个信号量和一个共享变量：读互斥信号量rmutex，用于使读进程互斥地访问共享变量count，其初值为1；写互斥信号量wmutex用于实现写进程与读进程的互斥及写进程与写进程的互斥，其初值为1；共享变量count用于记录当前正在读数据库的读进程数目，初值为0。其工作过程如下： int rmutex=1; int wmutex=1; int count=0; main() { cobegin Reader(); Writer(); coend }
Reader() { while(1) { P(rmutex): if(count==0)
P(wmutex);//当第一个读进程读数据库时,阻止写进程写; count++; V(rmutex): 读数据库; P(rmutex); count--; if(count==0)
V(wmutex);//当最后一个读进程读完数据库时,允许写进程写; V(rmutex); }
Writer() { while(i) { P(wmutex); 写数据库; V(wmutex); } }
在本题中，要注意对信号量rmutex意义的理解。rmutex是一个互斥信号量，用于使读进程互斥地访问共享变量count。该信号量并不表示读进程的数目，表示读进程数目的是共享变量count。当一个读进程要读数据库时，应将读进程计数count增加1。如果此前(count加1以前)数据库中无读进程，还应对写互斥信号量wmutex做P操作，这样若数据库中无写进程，则通过P操作组织写进程写；若数据库中有写进程，则通过P操作让读进程等待。
同理，当一个读进程完成读数据库操作时，应将读进程计数count减少1；如果此时(count减1以后)数据库中已无读进程，还应对写互斥信号wmutex作V操作，以允许写进程写。
16.抽烟问题：有一个烟草代理和三个抽烟者。抽烟者若要抽烟，必须具有烟草、烟纸和火柴。三个抽烟者中，一个缺烟叶、一个缺烟纸、一个缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将它们放在桌上。如果他放的是烟叶，则缺烟叶的抽烟者会拾起烟叶，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理和三个抽烟者。
（分数：4.00）
__________________________________________________________________________________________ 正确答案：()
解析：semaphore smoker[3];//初始0,三个抽烟者 semaphore material[3];//初始0,三种原料 semaphore agent;//初始1,供应商 int turn;//初始0,轮到谁 agent: while(1) { wait(agent);
signal(smoker[turn]);
signal(material[(turn+1)%3]); signal(material[(turn+2)%3]); turn=(turn+1)%3 }
smoker—i: while(1) { wait(smoker[i]);
wait(material[(i+1)%3]); Wait(material[(i+2)%3]); signal(agent); }
今有三个批处理作业。第一个作业10:00到达，需要执行2小时。第二个作业10:10到达，需要执行1小时。第三个作业10:25到达，需要执行25分钟。分别采取如下(见表(a)，表(b)，表(c))三种作业调度算法：
(a) 算法一 作业号 到达时间 开始执行时间 执行结束时间 1 2 3 (b) 算法二 作业号 到达时间 开始执行时间 执行结束时间 10:00 10:10 10:25 10:00 12:00 13:00 12:00 13:00 13:25 1 2 3 (c) 10:00 10:10 10:25 11:50 10:50 10:25 12:00 13:00 13:25 算法三 作业号 到达时间 开始执行时间 执行结束时间 1 2 3 （分数：4.00） (1).计算各调度算法下的作业平均周转时间。（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：采用调度算法1时： 作业1的周转时间为2h； 作业2的周转时间为2.83h； 作业3的周转时间为3h；
平均周转时间为：(2+2.83+3)/3=2.61(h)。 采用调度算法2时： 作业1的周转时间为3.83h； 作业2的周转时间为1.67h； 作业3的周转时间为0.42h；
平均周转时间为：(3.83+1.67+0.42)/3=1.97(h)。 采用调度算法3时： 作业1的周转时间为2h； 作业2的周转时间为3.25h； 作业3的周转时间为2h；
平均周转时间为：(2+3.25+2)/3=2.42(h)。
(2).调度算法一、三分别是什么作业调度算法?（分数：2.00）
__________________________________________________________________________________________ 正确答案：()
解析：调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。 调度算法3是按照作业执行时间从短到长的次序执行的，所以它是短作业优先调度算法。
17.在单CPU和两台输入/输出设备(I 1 ，I 2 )的多道程序设计环境下，同时投入三个作业Job 1 ，Job 2 ，Job 3 运行。这三个作业对CPU和输入/输出设备的使用顺序和时间如下所示： Job 1 :I 2 (30ms);CPU(10ms);I 1 (30ms)；CPU(10ms)；I 2 (20ms) Job 2 :I 1 (20ms)；CPU(20ms)；I 2 (40ms)
Job 3 :CPU(30ms)；I 1 (20ms)；CPU(10ms)；I 1 (10ms)
假定CPU，I 1 ，I 2 都能并行工作，Job 1 优先级最高，Job 2 次之，Job 3 优先级最低，优先级高的作业可以抢占优先级低的作业的CPU，但不抢占I 1 和I 2 。试求： (1)三个作业从投入到完成分别需要的时间。 (2)从投入到完成的CPU利用率。 (3)I/O设备利用率。
（分数：4.00）
10:00 10:10 10:25 10:00 12:25 12:00 12:00 13:25 12:25 __________________________________________________________________________________________ 正确答案：()
解析：三个作业并发执行时的工作情况如下：
Job 1 的执行顺序为：I 2 (30ms)；CPU(10ms)；I 1 (30ms)；CPU(10ms)；等待I 2 (10ms)；I 2 (20ms)。 Job 2 的执行顺序为：I 1 (20ms)；CPU(10ms)；等待CPU(10ms)；CPU(10ms)；I 2 (40ms)；
Job 的执行顺序为：CPU(20ms)；等待CPU(30ms)；CPU(10ms)；等待I (10ms)；I (20ms)；CPU(10ms)；3 1 1 I 1 (10ms)。
(1)Job 1 从投入到运行完成需要110ms，Job 2 从投入到运行完成需要90ms，Job 3 从投入到运行完成需要110ms。
(2)CPU在时间段60～70ms，80～90ms，100～110ms期间空闲，所以CPU的利用率为：(110-30)/110=72.7%。 (3)设备I 1 在时间段20～40ms，90～100ms期间空闲，所以设备I 1 的利用率为：(110-30)/110=72.7%； 设备I 2 在时间段30～50ms期间空闲，所以设备I 2 的利用率为：(110-20)/110=81.8%。
3种资源A(17)、B(5)、C(20)，5个进程P 1 、P 2 、P 3 、P 4 、P 5 ，初始时刻的系统状态(见下表)：
最大资源需求量 已经分配的数量 剩余的数量 进程 A B C P 1 5 5 9 P 2 5 3 6 P 3 4 0 11 P 4 4 2 5 P 5 2 4 3 （分数：3.99） (1).初始时刻是否是安全状态?给出安全序列。（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：由题目所给出的最大资源需求量和已分配资源数量，可以计算出T 时刻各进程的资源需求量Need。0 Need=最大资源需求量。如下表所示。
A 2 4 4 2 1 B 1 0 0 0 4 C 2 2 5 4 A B C 2 3 3 最大资源需求量 已经分配的数量 资源需求量 剩余的数量 进程 A B C P 1 5 5 9 P 2 5 3 6 P 3 4 0 11 P 4 4 2 5 P 5 4 2 4 A 2 4 4 2 3 B C 1 2 0 2 0 5 0 4 1 4 A B C A B C 3 4 7 1 3 4 0 0 6 2 3 3 2 2 1 1 1 0 初始时刻，系统处于安全状态，存在安全序列：P 5 ，P 4 ，P 3 ，P 2 ，P 1 。 (2).如果P2请求资源(0，3，4)，能否实施资源分配?（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：在T 0 时刻若进程P 2 请求资源(0，3，4)，因请求资源数(0，3，4)＞剩余资源数(2，2，3)，所以不能分配。
(3).在(2)的条件下，P4请求(2，0，1)能否实现资源分配?为什么?（分数：1.33）
__________________________________________________________________________________________ 正确答案：()
解析：在(2)的基础上，若进程P 4 请求资源(2，0，1)，按银行家算法进行检查： P 4 请求资源(2，0，1)＜=P 4 资源需求量(2，2，1) P 4 请求资源(2，0，1)＜=剩余资源数(2，3，3)
分配资源后，系统剩余的资源数量为(0，3，2)，不能分配给任意一个进程，而且P 进程也无法继续执行，4 因此，系统不存在安全序列，不会响应P 4 的请求。
因篇幅问题不能全部显示，请点此查看更多更全内容