操作系统典型例题分析 下载本文

(2)不一定,当系统中所有进程分别等待各自希望发生的事件时,它们都处于阻塞状态,此时系统中既没有运行进程,也没有就绪进程。这种情况出现时,如果各个进程没有相互等待关系,只要等待的事件发生了,进程就会从等待状态转化为就绪状态。但如果处于阻塞状态的进程相互等待彼此占有的资源,系统就可能发生死锁。

(3)不一定。因为高优先级的进程有可能处于等待状态,进程调度程序只能从就绪队列中挑选一个进程投入运行。被选中进程的优先级在就绪队列中是最高的,但在整个系统中它不一定是最高的,等待队列中进程的优先级有可能高于就绪队列中所有进程的优先级。

9、假如有以下程序段,回答下面问题。S1: a=3-x;S2: b=2*a;S3: c=5+a;(1)并发程序执行的Bernstein条件是什么?(2)试画图表示它们执行时的先后次序。(3)利用Bernstain条件证明,S1、S2和S3哪两个可以并发执行,哪两个不能。

(1)Bernstain提出的程序并发执行的条件如下:

R(Pi)={a1,a2,……am}表示程序Pi在执行期间所要参考的所有变量的集合,称为“读集”;W(Pi)={b1,b2,……bn}表示程序Pi在执行期间要改变的所有变量的集合,称为“写集”。两个程序P1和P2并发执行的条件是,当且仅当

R(P1)?W(P2)?R(P2)?W(P1)?W(P1)?W(P2)={}

(2)三个程序段对应的三个进程的先后执行次序是,S1先于S2和S3运行,如下图所示。

S2 S1 S3

(3) R(S1)={x},W(S1)={a} R(S2)={a},W(S2)={b}

R(S3)={a},W(S3)={c}

所以W(S1)?R(S2)={a},因此S1和S2不能并发执行。W(S1)?R(S3)={a},因此S1和S3也不能并发执行。而

R(S2)?W(S3)?R(S3)?W(S2)?W(S2)?W(S3)={},因此S2和S3可以并发执行。

3 进程同步与通信

1、以下进程之间存在相互制约关系吗?若存在,是什么制约关系?为什么?(1)几个同学去图书馆借同一本书;(2)篮球比赛中两队同学争抢篮板球;(3)果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序;(4)商品的入库和出库;(5)工人做工与农民种粮。

进程之间的相互制约分为互斥关系和同步关系。互斥关系是多个进程之间竞争临界资源,而禁止两个以上的进程同时进入临界区所发生的制约关系。同步关系是合作进程之间协调彼此的工作,而控制自己的执行速度,由此产生的相互合作、相互等待的制约关系。

(1)几个同学去图书馆借同一本书。存在互斥关系。因为一本书只能借给一个同学。

(2)篮球比赛中两队同学争抢篮板球。存在互斥关系。因为篮球只有一个,两队只能有一个队抢到篮

球。

(3)果汁流水线生产中捣碎、消毒、灌装、装箱等各道工序。存在同步关系,因为后一道工序的开始依赖于前一道工序的完成。

(4)商品的入库和出库。存在同步关系,因为商品若没有入库就无法出库,若商品没有出库,装满了库房,也就无法再入库。

(5)工人做工与农民种粮。工人和农民之间没有相互制约关系。 2、说明P、V操作为什么要设计成原语?

用信号量S表示共享资源,其初值为1表示有一个资源。设有两个进程申请该资源,若其中一个进程先执行P操作。P操作中的减1操作由3条机器指令组成:取S送寄存器R;R-1送R;R送S。若P操作不用原语实现,在执行了前述三条指令中的2条,即还未执行R送S时(此时S的值仍为1),进程被剥夺CPU,另一个进程执行也要执行P操作,执行后S的值为0,导致信号量的值错误。正确的结果是两个进程执行完P操作后,信号量的值为-1,进程阻塞。

V操作也同样。所以要把信号量的P、V操作设计成原语,要求该操作中的所有指令要么都做,要么都不做。

3、设有一个售票大厅,可容纳200人购票。如果厅内不足200人,则允许进入,超过则在厅外等候;售票员某时只能给一个购票者服务,购票者买完票后就离开。试问:(1)购票者之间是同步关系还是互斥关系?(2)用P、V操作描述购票者的工作过程。

购票者之间是互斥关系。

P、V操作描述购票者的工作过程如下: semaphore empty=2000; semaphore mutex=1; void buyer() { P(empty); P(mutex); 购票; V(mutex); V(empty); }

售票大厅可容纳200人购票,说明最多允许200人共享售票大厅。引入一个信号量empty,初值为200;由于购票者必须互斥地购票,故再设置一个信号量mutex,初值为1。

4、分析生产者和消费者问题中多个P操作颠倒引起的后果。

答:如果将生产进程的两个P操作,即P(empty)和P(mutex)的位置互换,生产者和消费者问题描述如下:

semaphore mutex=1; semaphore empty=n; semaphore full=0; int i,j;

ITEM buffer[n], data_p, data_c;

void producer() /*生产者进程*/ { while(true)

{ produce an item in data_p; P(empty) P(empty)

buffer[i] = data_p;

i=(i+1)%n; V(nutex); V(full); }

}

void consumer() /*消费者进程*/ { while(true) { P(full) P(mutex)

data_c = buffer[j];

j=(j+1)%n; V(nutex); V(empty);

consume the item in data_c; }

}

按上面的描述,当生产者进程生产了n个产品而使缓冲区满时,生产者如若继续执行,可能顺利通过P(mutex)。但当执行P(empty)时,由于缓冲区已满,生产者将在信号量empty上等待。若之后消费者欲取产品,执行P(full)顺利通过,但当执行P(mutex)时,由于生产者获得了进入临界区的权力,消费者只能在mutex上等待。此时生产者在empty上等待,消费者在mutex上等待,从而导致生产者等待消费者取走产品,消费者等待生产者释放缓冲区,这种相互等待就造成系统死锁。

4 调度与死锁

1、某进程被唤醒后立即投入运行,能说明系统采用的是可剥夺调度算法吗?

不能。如果当前就绪队列为空,被样被唤醒的进程就是就绪队列中唯一的一个进程,于是调试程序自然选中它投入运行。

2、在哲学家进餐问题中,如果将先拿起左边筷子的哲学家称为左撇子,将先拿起右边筷子的哲学家称为右撇子。请说明在同时存在左、右撇子的情况下,任何的就座安排都不能产生死锁。

该题的关键是证明该情况不满足产生的四个必要条件之一。在死锁的四个必要条件中,本题对于互斥条件、请求与保持条件、不可剥夺条件肯定是成立的,因此必须证明环路条件不成立。

对于本题,如果存在环路条件必须是左、右的哲学家都拿起了左(或右)边的筷子,而等待右(或左)边的筷子,而这种情况只能出现在所有哲学家都是左(或右)撇子的情况下,但由于本题有右(或左)撇子存在,因此不可能出现循环等待链,所以不可能产生死锁。

3、系统中有5个资源被4个进程所共享,如果每个进程最多需要两个资源,试问系统是否会产生死锁? 由于资源数大于进程数,所以系统中总会有一个进程获得的资源数大于等于2,该进程已经满足了它的最大需求,当它运行完毕后会把它占有的资源归还给系统,此时其余3个进程也能满足最大需求而顺利运行完毕。因此系统不会产生死锁。

4、计算机系统中有8台磁带机,由N个进程竞争使用,每个进程最多需要3台。问当N为多少时,系统没有死锁的危险?

当N<4时,系统没有死锁的危险。因为当N为1时,它最多需要3台磁带机,系统中共有8台,其资源数已足够1个进程使用,因此绝对不会产生死锁;当N为2时,两个进程最多需要6台磁带机,系统中共有8台,其资源数也足够两个进程使用,因此也不会产生死锁;当N为3时,无论如何分配,3个进程中必有进程得到3台磁带机,该进程已经达到它的最大需求,当它运行完毕后可释放这3台磁带机,这就保证了其他两个进程也可顺利执行完毕。因此当N<4时,系统没有死锁的危险。

当N=4时,假设4个进程都得到两个资源,此时系统中已没有剩余资源,而4个进程都没有到达它们的最大需求,所以系统有可能产生死锁。同理,当N>4时,也有产生死锁的危险。

5、设系统中有5个进程P1、P2、P3、P4和P5,有三种类型的资源A、B和C,其中A资源的数量是17,B资源的数量是5,C资源的数量是20,T0时刻系统状态如下表。回答以下问题:(1)计算每个进程还可能需要的资源,并填入表的“仍需要资源数”栏目中。(2)T0时刻系统是否处于安全状态?为什么?(3)如果T0时刻进程P2又有新的资源请求(0,3,4),是否实施资源分配?为什么?(4)如果T0时刻进程P4又有新的资源请求(2,0,1),是否实施资源分配?为什么?(5)在第(4)题的基础上,若进程P1又有新的资源请求(0,2,0),是否实施资源分配?为什么? 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A B C

(1)5个进程P1、P2、P3、P4和P5仍然需要A、B和C,三类资源数量如下表: 进程 P1 P2 P3 P4 P5 已分配资源数量 A 2 4 4 2 3 B 1 0 0 0 1 C 2 2 5 4 4 最大资源需求量 A 5 5 4 4 4 B 5 3 0 2 2 C 9 6 11 5 4 仍然需求资源数 A 3 1 0 2 1 B 4 3 0 2 1 C 7 4 6 1 0 (2)由已知条件,系统中A、B和C,三类资源的总数是(17,5,20),从表中可以计算出已分配情况是(15,2,17),剩余可用资源的数量是(2,3,3),如果先让进程P5执行,可以满足它的最大需求。当进程P5运行完毕,又可释放它占有的资源,使系统中可用资源的数量增加为(5,4,7);此时可让P4执行,满足它的最大需求后又可释放它占有的资源,使系统中可用资源的数量增加为(7,4,11);然后让P3执行,满足它的最大需求后又可释放它占有的资源,使系统中可用资源的数量增加为(11,4,16);之后可让P2和P1执行。这样所有进程都可运行完毕,系统是在T0时刻存在安全序列{P5,P4,P3,P2,P1},所以系统是安全的。

(3)如果T0时刻进程P2又有新的资源请求(0,3,4),进程P2请求资源数(C资源只剩下3个,而进程P2请求4个)大于剩余可用资源的数据(2,3,3),所以不能分配。

(4)如果T0时刻进程P4又有新的资源请求(2,0,1),按银行家算法进行检查,进程P4请求资源数(2,0,1)+已分配资源数量(2,0,4)小于进程P4的最大需求数量(4,2,5);另外进程P4请求资源数(2,0,1)小于剩余可用资源的数量(2,3,3);如果满足进程P4新的资源请求,进程P4新仍然需求资源数变为(0,2,0),如下表所示。 进程 已分配资源数量 A B C 最大资源需求量 A B C 仍然需求资源数 A B C