操作系统期末复习题答案

第2章 进程管理 1

3. 某系统的进程状态转换图如图所示，请说明：

执行 2 3

1

4 阻塞 就绪

（1）引起各种状态转换的典型事件有哪些?

（2）当我们观察系统中某些进程时，能够看到某一进程产生的一次状态转换能引

起另一进程作一次状态转换。在什么情况下，当一个进程发生转换3时能立即引起另一个进程发生转换1？ （3）试说明是否会发生下述因果转换：

2 → 1 3 → 2 4 → 1

解：

（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，就意味着有一个进程从阻塞状态变为就绪状态，因而调度程序就会将就绪队列中的此进程投入运行。

2 操作系统习题与解析

4. 在单处理机的分时系统中，分配给进程P的时间片用完后，系统进行切换，结果调度到的仍然是进程P。有可能出现上述情形吗?如果可能请说明理由。

解：有可能出现上述情况。例如，若在进程P时间片用完后，被迫回到就绪队列时，就绪队列为空，这样进程P就是就绪队列中惟一的一个进程，于是调度程序选中的进程必然是进程P；又如在按优先级调度的系统中，就绪队列按进程优先级排列，在进程P时间片用完之后回到就绪队列时，若其优先级高于当前就绪队列中的其他进程，则它将排在就绪队列之首，从而再次被调度程序选中并投入运行。

5.（北京大学1990年试题） ① 写出P、V操作的定义。

② 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P、V操作来保证文件的正确打印。

解：① P、V操作是两条原语，它们的定义如下： P操作 P操作记为P（S），其中S为一信号量，它执行时主要完成下述动作：

S = S－1

若S≥0，则进程继续运行。

若S＜0，则该进程被阻塞，并将它插入该信号量的等待队列中。

V操作 V操作记为V（S），S为一信号量，它执行时主要完成下述动作： S = S＋1

若S＞0，则进程继续执行。

若S≤0，则从信号量等待队列中移出队首进程，使其变为就绪状态。

② 在本题中，进程PA、PB、PC之间的关系为：PA与PB共用一个单缓冲区，而PB又与PC共用一个单缓冲区，其合作方式可用图2.12表示。当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程PC可以打印记录。在其他条件下，相应进程必须等待。事实上，这是一个生产者-消费者问题。

PA PC PB 缓冲区1 缓冲区2

复制 打印 从磁盘读入

为遵循这一同步规则。应设置四个信号量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；

第2章 进程管理 3

main（ ） {

cobegin PA（ ）； PB（ ）； PC（ ）； coend }

PA（ ） {

while （1） {

从磁盘读一个记录； p（empty1）；

将记录存入缓冲区1； v（full1）； } }

PB（ ） {

while（1） {

p（full1）；

从缓冲区1中取出记录； v（empty1）； p（empty2）；

将记录存入缓冲区2； v（full2）； } }

PC（ ） {

while（1） {

p（full2）；

从缓冲区2中取出记录； v（empty2）； 打印记录； } }

6.有一个仓库，可以存放A和B两种产品，但要求： （1）每次只能存入一种产品（A或B）； （2）－N＜A产品数量－B产品数量＜M。

4 操作系统习题与解析

其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。 本题给出的第一个条件是临界资源的访问控制，可用一个互斥信号量解决该问题。第二个条件可以分解为： －N＜A产品数量－B产品数量 A产品数量－B产品数量＜M

也就是说，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上。

解：在本题中，我们可以设置两个信号量来控制A、B产品的存放数量，sa表示当前允许A产品比B产品多入库的数量，即在当前库存量和B产品不入库的情况下，还可以允许sa个A产品入库；sb表示当前允许B产品比A产品多入库的数量，即在当前库存量和A产品不入库的情况下，还可以允许sb个B产品入库。初始时，sa为M－1，sb为N－1。当往库中存放入一个A产品时，则允许存入B产品的数量也增加1；当往库中存放入一个B产品时，则允许存入A产品的数量也增加1。

产品A、B的入库过程描述如下： int mutex=1； /*互斥信号量*/ int sa=M－1； int sb=N－1； main（ ） {

while（1） {

取一个产品；

if（取的是A产品） {

p（sa）； p（mutex）； 将产品入库； v（mutex）； v（sb）； }

else /*取的产品是B*/ {

p（sb）； p（mutex）； 将产品入库； v（mutex）； v（pa）； } } }

从本题的解法可以看出，当有比较复杂条件出现时，可以把复杂条件分解成一组简单条件，这样就能很容易地写出对应的程序流程了。