loading
S1: a=3-x; S2: b=2*a; S3: c=5+a;
(1) 并发程序执行的Bernstein 条件是什么？ (2) 是画图表示它们执行时的先后次序。
(3) 利用Bernstein 条件证明，S1、S2和S3哪两个可以并发执行，哪两个不能。
答案
1. 答：①为了从变化角度动态地分析研究可以并发执行的程序，真实的反应系统的独立性、
并发性、动态性和相互制约，操作系统中不得不引入进程的概念。 ②为了防止操作系统及其关键的数据结构受到用户程序破坏，将处理机分为核心态和用户态。对进程进行创建、撤销以及在某些进程状态之间的转换控制。
2. 答：①运行状态→就绪状态：此进程根据自身的情况插入到就绪队列的适当位置，系统
收回处理及转入进程调度程序重新进行调度。 ②运行状态→阻塞状态：一个进程从运行状态道阻塞状态后。系统会调用进程调度程序重新选择一个进程投入运行。 3.
（1） 答：为支持多进程的并发执行，系统必须建立的数据结构式PCB，不同状态进程的
PCB用链表组织起来，形成就绪队列、阻塞队列。
（2） 答：阻塞原句、唤醒原句、挂起原句、激活原句
（3） 答：创建原句：建立进程的PCB，并将进程投入就绪队列。 撤销原句：删除进程的PCB，并将进程在其队列中摘除。
阻塞原句：将京城PCB中进程的状态从运行状态改为阻塞状态，并将进程投入阻塞队列。
唤醒原句：将进程PCB中进程的状态从阻塞状态改为就绪状态，并将进程从则色队列摘下，投入到就绪队列中。
4. 答：进程控制块（PCB）是为了描述进程的动态变化而设置的一个与进程相联系的数据
结构，用于记录系统管理进程所需信息。PCB是进程存在的唯一标识，操作系统通过PCB得知进程的寻在。
为了进程管理，进程控制块包括以下几方面。
（1） 进程的描述信息，包括进程标识符、进程名等。 （2） 进程的当前状况。 （3） 当前队列链接指针。 （4） 进程的家族关系。
为了中断处理，进程控制块的内容应该包括处理机状态信息和各种寄存器的内容，如通用寄存器、指令计数器、程序状态字（PSW）寄存器及栈指针等。 为了内存管理的需要，进程控制块的内容应该包括进程使用的信号量、消息队列指针等。
为了设备管理，进程控制块的内容应该包括进程占有资源的情况。
5. 答：就绪队列中有10个进程，这10个进程轮换执行，每隔进程的运行时间是300ms，
切换另一个进程所花费的总时间是10ms，隐刺系统化在进程切换上的时间开销占系统整个时间的比例是：10//(300+10)=3.2%.
6. 答：线程是进程内的一个相对独立的运行单元，是操作系统调度和分派的单位。线程只
拥有一点必不可少的资源（一组寄存器和栈），但可以和同属于一个进程的其他线程共享进程拥有的资源。
线程是进程的一部分，是进程内的一个实体；一个进程可以有多个线程，但至少必须有一个线程。 7.
（1） 答：1表示新进程创建后，进入高优先级就绪队列；3表示进程因请求I/O活等待某
件事儿阻塞；4表示进程运行的时间片到；6表示进程I/O完成或等待的时间到达；7表示进程运行顽皮而退出。
（2） 答：3→2是因果变迁，当一个进程从运行态变为阻塞态时，此时CPU空闲，系统首
先到高优先级队列中选择一个进程投入运行。
4→5是因果变迁，当一个进程运行完毕时，此时CPU空闲，系统首先到高优先级队列中选择进程，但如果高优先级队列为空，则从低优先队列中选择一个进程投入运行。
7→2 是因果变迁，当一个进程运行完毕时，CPU空闲，系统首先到高优先级队列中选择一个进程投入运行。
3→6不是因果变迁。一个进程阻塞时由于自身的原因而发生的，和另一个进程等待的时间到达没有因果关系。
（3） 答：当进程调度时，首先从高优先级就绪队列选择一个进程，赋予它的时间片为
100ms。如果高优先级就绪队列为控，则从低优先级就绪队列选择进程，但赋予该进程的时间片为500ms。
这种策略一方面照顾了短进程，一个进程如果在100ms运行完毕它将退出系统，更主要的是照顾了I/O量大的进程，进程因I/O进入阻塞队列，当I/O完成后它就进入了高优先级就绪队列，在高优先级就绪队列等待的进程总是优于低优先级就绪队列的进程。而对于计算量较大的进程，它的计算如果在100ms的时间内不能完成，它将进入低优先级就绪队列，在这个队列的进程被选中的机会要少，只有当高优先级就绪队列为空，才从低优先级就绪队列选择进程，但对于计算量大的进程，系统给予的适当照顾时间片增大为500ms。
8.
（1） 答：是。若系统中没有运行进程，系统会马上选择一个就绪进程队列中的进程投入
运行。只有在就绪队列为空时，CPU才会空闲。
（2） 答：不一定。当系统中所有进程分别等待各自希望发生的事件时，它们都处于阻塞
状态，此时系统中既没有运行进程，也没有就绪进程。这种情况出现时，如果各个进程没有相互等待关系，只要等待的时间发生了，进程就会从等待状态转化为就绪状态。但如果处于阻塞状态的进程相互等待彼此占有的资源，系统就有可能发生死锁。
（3） 答：不一定。因为高优先级的进程有可能处于等待状态，进程调度程序只能从就绪
队列中挑选一个进程投入运行。被选中进程的优先级在就绪队列中是最高的，但在整个系统中它不一定是最高的，等待队列中进程的优先级有可能高于就绪队列中所有进程的优先级。
9.
（1） 答： P1和P2并发执行的条件是，当且仅当
R(P1)∩W(P2) ∪R(P2) ∩W(P1) ∪W(P1)∩W(P2)={}
（2）
S2 S1 S3
（3） 答：R(S1)={x},W(S2)={a}，R(S2)={a},W(S2)={b}，R(S3)={a},W(S3)={c}
所以W(S1) ∩R(S2)={a}, 因此S1和S2不能并发执行。
W（S1）∩R(S2)={a}, 因此S1和S3也不能并发执行。
而R(S2) ∩W(S3) ∪R(S3) ∩W(S2) ∪W(S2) ∩W(S3)={}, 因此S2和S3可以并发执行。
第三章 进程同步与通信