18
3、 图2.7给出了四个进程合作完成某一任务的前趋图，试说明这四个进程间的同步关系，并用P、V操作描述它。
图2.7四个合作进程的前趋图
解：图2.7说明任务启动后S1先执行。当S1结束后，S2、S3可以开始执行。S2、S3完成
后，S4才能开始执行。为、了确保这一执行顺序，设三个同步信号量b2，b3，b4分别表示进程S2、S3、S4是否可以开始执行，其初值均为0。这四个进程的同步描述如下：
int b2=0; /*表示进程S2是否可以开始执行*/ int b3=0; /*表示进程S3是否可以开始执行*/ int b4=0; /*表示进程S4是否可以开始执行*/ main() {
cobegin S1(); S2(); S3(); S4(); coend } S1() { .
. .
v(b2); v(b3); } S2() {
P(b2)
19
v(b4); } S3() {
p(b3); v(b4); } S4()
{ p(b4);
p(b4); /*因在S2及S3完成时均对b4做了v操作，因此这里
要用两个p操作*/
}
4、 某系统的进程状态转换图如图2.8所示，请说明：
图2.8 某系统的进程状态转换图
（1）引起各种状态转换的典型事件有哪些？
（2）当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引起另一个进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？
（3）试说明是否会发生下述因果转换： 2 -> 1 3 -> 2 4 -> 1
解：
20
（1）在本题所给的进程状态转换图中，存在四种状态转换。当进程调度程序从就绪队列中选取一个进程投入执行时引起转换1；正在执行的进程如因时间片用完而被暂停执行就会引起转换2；正在执行的进程因等待的事件尚未发生而无法执行（如进程请求完成I/O）则会引起转换3；当进程等待的事件发生时（如I/O完成）则会引起转换4。
（2）如果就绪队列非空，则一个进程的转换3会立即引起另一个进程的转换1。这是因为一个进程发生转换3意味着正在执行的进程由执行状态变为阻塞状态，这时处理机空闲，进程调度程序必然会从就绪队列中选取一个进程并将它投入执行，因此只要就绪队列非空，一个进程的转换3能立即引起另一个进程的转换1。
（3）所谓因果转换指的是有两个转换，一个转换的发生会引起另一个转换的发生，前一个转换称为因，后一个转换称为果，这两个转换称为因果转换。当然这种因果关系并不是什么时候都能发生，而是在一定条件下才会发生。
? 2-> 1: 当某进程发生转换2时，就必然引起另一个进程的转换1。因为当发
生转换2时，正在执行的进程从执行状态变为就绪状态，进程调度程序必然会从就绪队列中选取一个进程投入执行，即发生转换1。
? 3-> 2：某个进程的转换3决不可能引起另一进程发生转换2。这是因为当前
执行进程从执行状态变为阻塞状态，不可能又从执行状态变成就绪状态。 ? 4-> 1：当处理机空闲且就绪队列为空时，某一进程的转换4就会引起该进程
的转换1。因为此时处理机空闲，一旦某个进程发生转换4，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入执行。
5、 在单处理机的分时系统中，分配给进程P的时间片用完后，系统进行切换，结果调度到的仍然是进程P。可能出现上述情形吗？如果可能请说明理由。
解：有可能出现上述情况，例如，若在进程P时间片用完后，被迫回到就绪
队列时，就绪队列为空，这样进程P就是就绪队列中唯一的一个进程，于是队列按进程优先级排列，在进程P时间片用完之后回到就绪队列时，若其优先级高于当前就绪队列中的其他进程，则它将排在就绪队列之首，从而再次被调度程序选中并投入执行。
21
6、
试利用Bernstein条件证明S2和S3语句是可以并发执行的，而S3和S4
语句是不能并发执行的?\\
S1: a=5-x; S2: b=a*x; S3: c=4*x; S4: d=b+c; S5: e=d+3.
证明:
R(S2)={x，a}， W(S2)={b}， R(S3)={x}， W(S3)={c};
可见，S2与S3的读集与写集两两不相交，S2与S3的读集之间也不相交，因而，他们满足Bernstein条件， S2与S3语句是可以并发执行的.
同理可证S3和S4不能满足Bernstein条件，是不能并发执行的.
7、 如图一所示的进程状态，图中标出的数字分别表示一种形式的状态变迁。现设分别有进程处于执行态、就绪态和等待态，试判别下列诸条件式是否成立？为什么？
1→2，1→3，2→1，2→4，3→1，3→4，4→1，4→2，4→3，5→1 条件式\x，则导致另一进程产生状态变迁y。
答：
? 1→2不成立。一进程由执行状态到就绪状态是因为时间片用完而引起。 ? 1→3不成立。一进程由执行状态到等待状态是因为发生某事件（例I/O请求）
而使进程执行受阻。
? 2→1成立。如果一进程由于时间片用完由执行状态回复到就绪状态。则另一
进程在调度程序分配处理机后，由就绪状态转变为执行状态。
? 2→4不成立。由于一进程由执行状态回复到就绪状态时还占有着资源，另一
进程将仍处于等待状态。
22