“操作系统概论”习题解答之并发进程

　　第7章 习题解答

　　1.什么叫并发进程？

　　答：在多道程序设计系统中，作为单个作业可以同时执行，而每一个作业又需要有多个进程的协作来完成。因此，系统会同时存在着许多进程，在单处理器的情况下，这些进程轮流的占用处理器，即一个进程的工作没有全部完成之前，另一个进程就开始工作，我们说这些可同时执行的进程具有并发性，并且把可同时执行的进程称为“并发进程”。

　　2.临界区是怎样定义？对临界区的管理应符合哪些要求？

　　答：并发进程中与共享变量有关的程序段称为“临界区”。对若干个并发进程共享某一变量的相关临界区得管理有三点要求：

　　①一次至多一个进程能够进入临界区，当有进程在临界区执行时，其他想进入临界区执行的进程必须等待。

　　②不能让一个进程无限制的在临界区执行，即任何一个进入临界区的进程必须有限的时间内退出临界区。

　　③不能强迫一个进程无限期等待键入它的临界区，即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区执行。

　　3.采用PV操作作为同步机构时，假定与某共享变量相关的信号量S的值可在[-1，l］之间，问S的初值是哪个值？当S=－1，S=0，S=l时它们各自的物理含义是什么？

　　答：S的初值是 1.

　　S＝－l，表示有一个进程在等待进入临界区执行。

　　S＝0，表示已有一个进程在临界区执行，这时若有进程想进入临界区则必须等待。

　　S＝l，表示无进程在临界区执行，若有进程想进入临界区则可以立即进入。

　　4.A、B两个火车站之间是单轨连接的，现有许多列车同时到A站，须经A再到达B站，列车出B站后又可分路行驶（如图7－2）为保证行车安全，请你当调度时，你将如何调度列车？请你用PV操作为工具设计一个能实现你的调度方案的自动调度系统。

　　答：当A、B两站之间无列车停驶时，可让到达A站的一列车进人A、B站之间行驶。

　　当A石站之间有列车在行驶时，则到达A站者必须在站外等待。

　　当有列车到达B站后，让等在A站外的一列车进入。

　　用一个信号量S来控制到达A站的列车能否进入单轨道行驶，S的初始值为l.列车到达A站后，先执行P（S），若无列车在A、B站之间行驶，则执行P（S）后立即进人单轨道行驶，到达B站后，执行V（S），可释放一个等待进入的列车进入行驶。若A、B站之间已有列车在行驶，则执行P（S）后就等待，直到行驶者到了B站执行V（S）后释放一个欲进入者。

　　5.今有三个进程R、M、P，它们共享一个缓冲区。R负责从输入设备读信息，每次读出一个记录并把它存放在缓冲区中：M在缓冲区加工读入的记录；P把加工后的记录打印输出。输入的记录经加工输出后，缓冲区中又可存放下一个记录。请用P、V操作为同步机构写出他们并发执行时能正确工作的程序。

　　答：三个进程共用一个缓冲区，他们必须同步工作，可定义三个信号量：

　　S1：表示是否可把读人的记录放到缓冲区，初始值为1.

　　S2：表示是否可对缓冲区中的记录加工，初始值为0.

　　S3：表示记录是否加工好，可以输出，初始值也为0.

　　三个进程可如下设计：

　　begin

　　S1，S2，S3：semaphore；

　　S1：＝l；S2：＝S3：＝0；

　　cobegin

　　process R

　　begin

　　L1：读记录；

　　P（S1）；

　　记录存入缓冲区；

　　V（S2）；

　　goto L1；

　　end；

　　process M

　　begin

　　L2：P（S2）；

　　加工记录；

　　V（S3）；

　　goto L2；

　　end；

　　process P

　　begin

　　L3：P（S3）；

　　输出加工后的记录；

　　V（S1）；

　　goto L3；

　　end；

　　coend；

　　end.

　　6.现有4个进程R1，R2，W1，W2，它们共享可以存放一个数的缓冲器B.进程R1每次把从键盘上投入的一个数存放到缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数放到缓冲器B中，供进程W2打印输出。当一个进程把数据存放到缓冲器后，在该数还没有被打印输出之前不准任何进程再向缓冲器中存数。在缓冲器中还没有存入一个新的数之前不允许任何进程加快从缓冲区中取出打印是怎样才能使这四个进程在并发执行是协调的工作？

　　答：这四个进程实际上是两个生产者 R1，R2和两个消费者 W1，W2.各自生成不同的产品中各自的消费对象去消费，他们共享一个的缓冲器。由于缓冲器只能存放一个数，所以，R1和R2在存放数时必须互斥。而R1和W1、R2和W2之间存在同步。为了协调它们的工作可定义三个信号量：

　　S：表示能否把数存人缓冲器B，初始值为1.

　　S1：表示R1是否已向缓冲器存入从键盘上读入的一个数，初始值为0.

　　S2：表示R2是否已向缓冲器存入从磁盘上读入的一个数，初始值为0.

　　begin

　　S，S1，S2：semaphore；

　　S：＝1；S1：＝S2：＝0；

　　cobegin

　　process R1

　　xl ：integer

　　begin

　　L1：从键盘读一个数；

　　x1：=读入的数；

　　P（S）；

　　B：＝xl；

　　V（S1）；

　　goto L1；

　　end；

　　process R2

　　x2：integer；

　　begin

　　L2：从磁盘读一数；

　　x2：=读入的数；

　　P（S）；

　　B：＝x2；

　　V（S2）；

　　goto L2；

　　end；

　　process W1

　　y：integer；

　　begin

　　L3：P（S1）；

　　y：=B；

　　V（S）；

　　打印y中的数；

　　goto L3；

　　end；

　　process W2

　　z：integer

　　begin

　　L4：P（S2）；

　　z：=B；

　　V（S）；

　　打印z中的数；

　　goto L4；

　　end；

　　coend；

　　end.

　　7.两个并发进程的程序如下：

　　begin

　　N：integer；

　　N：=3；

　　cobegin

　　process A

　　begin

　　L1：N：＝N＋5；

　　goto L1；

　　end；

　　process B

　　begin

　　L2：print（N）；

　　N：＝0；

　　goto L2；

　　end；

　　coend；

　　end.

　　若process A先执行了三个循环后，process A和 process B又并发执行了一个循环，写出可能出现的打印值。请用PV操作实现同步，使两并发进程能正确执行。

　　答：可能的值是 18或 23.这是因为 process A执行三个循环后，N＝18，之后 A和 B并发执行，可能先执行A中的N：=N＋5，再执行B中的print（N）；这样就会得到23，也可能先执行B中的pint（N）；这就会得到18.

　　可以利用P、V操作实现同步：

　　begin

　　N：integer；

　　S：semphore；

　　S：＝l；

　　N：＝3；

　　cobegin

　　process A

　　begin

　　L1：P（S）；

　　N：＝N＋5；

　　V（S）；

　　gotO L1；

　　end；

　　process B

　　begin

　　L2：P（S）；

　　print（N）；

　　N：＝0；

　　V（S）；

　　goto L2；

　　end；

　　coend；

　　end.

　　8.通信机制中设置哪些基本通信原语？它们的功能是什么？

　　答：系统提供两个与信箱通信有关的通信原语：send原语（发送）和 receive原语（接收）。send（B，M）原语把信件M送人到信箱B中，receive（B，X）原语从信箱B中取出一封信存放到指定的地址X中。

　　9.什么叫死锁？什么原因会引起死锁？

　　答：若系统中存在一组进程（二个或多个进程），他们中的每一个进程都占用某种资源而又都在等待其中另一个进程所占用的资源，这种等待永远不能结束，就说系统出现“死锁”。

　　进程死锁的起因是系统提供的资源数比要求使用资源的进程数少，或者是若干个个进程要求资源的总数大于系统能提供的资源数。这时，进程间就会出现竞争资源的现象，如果对进程竞争的资源管理和分配不当就会引起死锁。死锁的出现是与资源分配策略和并发进程的执行速度有关。

　　10.有哪些策略可防止和避兔死锁？

　　答：防止死锁的策略有：静态分配、按序分配、剥夺式分配。银行家算法可以避免死锁。

　　11.某系统有输入机和打印机各一台，今有两个进程都要同时使用他们，采用PV操作实现请求使用和归还释放后，还会产生死锁吗？若否，说明理由；若会产生死锁则给出一种防止死锁的方法。

　　答：如果 PV操作设计不当，仍会产生死锁。假如用 S1 S2分别代表输入机和打印机能否被使用的信号量，由于资源是共享的，所以必须互斥使用，因而它们的初始值都为l.

　　如果用如下方式实现请求使用和归还释放：

　　process QI

　　begin

　　P（S1）；

　　使用输入机；

　　P（S2）；

　　使用打印机；

　　V（S2）；

　　V（S1）；

　　end；

　　process Q2

　　begin

　　P（S2）；

　　使用打印机；

　　P（S1）；

　　使用输入机；

　　V（S2）；

　　V（S1）；

　　end；

　　那么就会出现Q1得到输入机而 Q2得到打印机，双方在不释放已经有的资源的情况下又去申请新的资源，就会造成死锁。

　　可以采用为资源编序号的方法，要求按序申请，如下：

　　process Q1

　　begin

　　P（S1）；

　　使用输入机；

　　P（S2）；

　　使用打印机；

　　V（S2）；

　　V（S1）；

　　end；

　　process Q2

　　begin

　　P（S1）；

　　使用输入机；

　　P（S2）；

　　使用打印机；

　　V（S2）；

　　V（S1）；

　　end.

　　12.某一系统分配资源的策略是：当进程提出申请资源时，只要系统有资源中是分配给它，系统无资源时让它登台。任一进程总是先释放以占有的资源后在申请新的资源，且每次申请一个资源，系统中的进程得到资源后总能在有限时间内归还。证明该系统不会发生死锁。

　　答：任一进程P申请资源时出现两种情况：

　　情况一，立即得到满足，此时不会成为等待状态，也就不存在引起死锁的条件。

　　情况二，得不到满足，处于等待资源状态。此时，资源一定被另一进程 Q占有。进程 Q执行时若不在申请资源，则必在有限时间里归还资源，于是 P不会永远等待。如果进程 Q执行时还要申请资源，按题意，它一定先释放占有的资源，于是 P也不会永远等待。所以，任一进程申请资源总能在有限时间得到资源，因而不会产生死锁。