4.4　自测练习

一、填空题

1.系统中各进程之间逻辑上的相互制约关系称为__。

2.并发的实质是一个处理机在多个程序之间的__。

3.通常将并发进程之间的制约关系分为两类：__和__。

4.P、V操作原语是对__执行的操作，其值只能由P、V操作改变。

5.一次只允许一个进程访问的系统资源称为__。

6.若一个进程已经进入临界区，其他欲进入临界区的进程必须__。

7.有m个进程共享一个临界资源，若使用信号量机制实现对临界资源的访问，则信号量的初值应设为__，其取值范围为__。

8.利用信号量实现进程的__，应为临界区设置一个信号量mutex，其初值为1，表示该资源尚未使用，临界区应置于__和__原语之间。

9.并发进程中涉及访问同一个变量的代码段，称为__。

10.关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块称为__。

11.有N个进程共享同一个资源R，如果每次允许M个进程（M＜N）同时访问该资源，则设置互斥信号量的初值为__，取值范围为__。

12.操作系统中信号量的值与__的使用情况有关，它的值仅能由__来改变。

13.实现一个管程时，必须考虑的3个主要问题是互斥、__和__。

14.信箱通信机制通常采用__原语和__原语。

15.每执行一次V操作，信号量的数值s加1。若__，则该进程继续执行；否则，从对应的__队列中移出一个进程并将__状态赋予该进程。

16.在有M个进程的系统中若出现死锁，则死锁进程的个数K应满足的条件是__。

17.进程使用临界区的4个准则是__、__、__和__。

18.不让死锁发生的策略可以分为静态和动态两种，死锁避免属于__策略。

19.死锁的预防中，采用资源预先分配和有序分配分别打破了死锁的四个必要条件中的__和__。

20.银行家算法是一种__算法。

二、单项选择题

1.并发性是指若干事件在__发生。

A.同一时刻

B.同一时间间隔内

C.不同时刻

D.不同时间间隔内

2.在单处理机系统中实现并发技术后，__。

A.系统中的进程在一个时间段内并行运行，CPU与外设之间并行工作

B.系统中的进程在一个时间段内并行运行，CPU与外设之间串行工作

C.系统中的进程在一个时间点上并行运行，CPU与外设之间并行工作

D.系统中的进程在一个时间点上并行运行，CPU与外设之间串行工作

3.进程间的基本关系为__。

A.相互独立

B.同步与互斥

C.信息传递与信息缓冲

D.并行执行与资源共享

4.操作系统中有一组不能被系统中断的特殊系统调用，这组特殊系统调用在操作系统中被称为__。

A.初始化程序

B.原语

C.子程序

D.控制模块

5.操作系统中的P、V操作是一种__。

A.系统调用

B.进程通信原语

C.控制命令

D.软件模块

6.两个进程合作完成一个任务，在并发执行中，一个进程要等待其合作伙伴发来信息或者建立某个条件后再向前执行，这种关系是进程间的__关系。

A.同步

B.互斥

C.竞争

D.合作

7.进程间的同步与互斥，分别表示了各进程之间的__。

A.不同状态

B.协调与竞争

C.相互独立与相互制约

D.动态性与独立性

8.在操作系统中，对信号量s的P操作定义中，使进程进入相应等待队列的条件是__。

A.s＞0

B.s=0

C.s＜0

D.s≤0

9.N个进程访问一个临界资源，则设置的互斥信号量s的取值范围是__。

A.0～N-1

B.1～-(N-1)

C.1～N-1

D.0～-1

10.临界区就是指__。

A.一段程序

B.一段数据区

C.一个缓冲区

D.一个共享资源

11.M个生产者，N个消费者共享长度为L的有界缓冲区，则对缓冲区互斥操作而设置的信号量的初值应设为__。

A.L

B.M

C.N

D.1

12.对于使用一个临界资源的两个并发进程，若互斥信号量等于1，则表示__。

A.没有进程进入临界区

B.有一个进程进入了临界区

C.有一个进程进入了临界区，另一个进程等待进入

D.这两个进程都在等待进入临界区

13.若信号量S的初值为2，当前值为-1，则表示有__个等待进程。

A.0

B.1

C.2

D.3

14.信箱通信是一种__通信方式。

A.低级

B.直接

C.间接

D.中级

15.系统出现死锁的原因是__。

A.计算机系统发生了重大故障

B.资源数大大少于进程数，或进程同时申请的资源数大大超过资源总数

C.有多个封锁的进程同时存在

D.若干进程因竞争资源而无休止地等待着，不释放已占有的资源

16.某系统有3个并发进程，都需要同类资源4个，试问：若不发生死锁，该系统应具有的最少资源数是__。

A.9

B.10

C.11

D.12

17.下列__不属于管程的组成部分。

A.对管程内数据结构进行操作的一组过程

B.管程外过程调用管程内数据结构的说明

C.管程内共享变量的说明

D.共享变量初始化语句序列

18.下面有关管程的说法，不正确的是__。

A.管程是一种进程同步机制

B.管程是一种编程语言成分

C.管程是一种系统调用

D.管程比信号量更容易保证并行编程的正确性

19.关于管程与进程比较的论述中，正确的是__。

A.管程内定义的是公用数据结构，进程内定义的是私有数据结构

B.管程作为操作系统或编程语言成分，与进程一样也具有生命周期，由创建而产生，由撤销而消亡

C.管程能被系统中所有的进程调用

D.管程和调用它的进程能够并行工作

20.任何进程使用管程所管理的临界资源时，需要调用特定的__才能互斥地进入管程，使用资源。

A.系统调用

B.访管指令

C.管程中的有关入口过程

D.同步操作原语

21.解决死锁的途径是__。

A.立即关机再重新开机

B.立即关机排除故障

C.不要共享资源，增加独占资源

D.设计预防死锁方法，运行检测并恢复

22.两个进程争夺同一个资源__。

A.不一定死锁

B.一定死锁

C.不会死锁

D.以上说法都不对

23.在为多道程序所提供的可共享的系统资源不足时，可能出现死锁。但是，不适当的__也可能产生死锁。

A.进程优先权

B.进程推进顺序

C.资源的线性分配

D.分配队列优先权

24.要预防死锁，可以通过打破死锁的4个必要条件，然而，通常不能通过打破__来预防死锁。

A.互斥

B.占有并等待

C.非抢占

D.循环等待

25.在消息缓冲机制中，__就是临界资源。

A.消息缓冲区

B.信箱

C.管道

D.消息队列

26.系统中有多个进程竞争使用多个同类型的独占型资源，每个进程一次只能申请一个，则下列__的情况可能会发生死锁。

A.资源数为4，进程数为3，每个进程最多需要1个资源

B.资源数为4，进程数为3，每个进程最多需要2个资源

C.资源数为6，进程数为2，每个进程最多需要3个资源

D.资源数为6，进程数为2，每个进程最多需要4个资源

27.采用资源的有序分配策略可以使以下__条件不成立。

A.互斥

B.占有并等待

C.非抢占

D.循环等待

28.进程P1使用资源情况：申请资源S1，申请资源S2，释放资源S1；进程P2使用资源情况：申请资源S2，申请资源S1，释放资源S2。若假设系统有1个资源S1，1个资源S2，则系统并发执行进程P1，P2，将__。

A.必定产生死锁

B.可能产生死锁

C.不会产生死锁

D.无法确定是否会产生死锁

29.某系统有同类资源m个供n个进程共享，若每个进程最多申请x个资源(1≤x≤m)，则当__时，系统不会发生死锁。

A.m-n×(x-1)≥0

B.m-n×(x×1)≥1

C.m-n×x≥0

D.m-n×x≥1

30.采用剥夺资源和__是两种常用的解除死锁的方法。

A.杀死进程

B.修改信号量

C.进程回滚

D.线性分配资源

三、不定项选择题

1.在单处理机系统中，下述__现象可能发生。

A.进程与进程之间的并行

B.进程与进程之间的并发

C.处理机与设备之间的并行

D.处理机与通道之间的并行

E.通道与通道之间的并行

F.设备与设备之间的并行

2.下列叙述中，正确的是__。

A.进程之间同步主要源于进程之间的资源竞争，是指对多个相关进程在执行次序上的协调

B.临界资源是指每次仅允许一个进程访问的资源

C.信号量机制是一种有效的实现进程同步与互斥的工具。信号量只能由P、V操作来改变

D.V操作是对信号量执行加1操作，意味着释放一个单位资源，加1后如果信号量的值小于等于零，则从等待队列中唤醒一个进程，现进程变为等待状态；否则，现进程继续进行

E.消息通信、信箱通信都属于高级通信方式

3.操作系统中并发进程的数目主要受到__的限制。

A.内存空间

B.进程调度策略

C.系统的资源数目

D.CPU速度

E.进程之间的推进速度

4.下列进程互斥方法中，__存在忙式等待问题。

A.软件：Peterson算法

B.硬件提供“开关中断”指令

C.硬件提供“测试并设置”（test and set）指令

D.软件：Dekker算法

E.硬件提供“交换”（swap）指令

5.发生死锁的必要条件有4个，要防止死锁的发生，可以破坏这4个必要条件之一，但要破坏__条件是不太实际的。

A.互斥

B.不可抢占

C.部分等待

D.循环等待

6.设S1和S2为两个信号量，下列__操作可以同时进行。

A.P(S1)、P(S2)

B.P(S2)、V(S2)

C.V(S1)、P(S2)

D.V(S1)、V(S2)

E.P(S1)、V(S2)

F.V(S1)、P(S1)

G.V(S2)、V(S2)

7.下面关于死锁的叙述中，正确的是__。

A.死锁是指因相互竞争资源使得系统中有多个阻塞进程的情况

B.若系统中并发运行的进程和资源之间满足互斥使用、保持和等待、非剥夺性和循环等待，则可判定系统中发生了死锁

C.在对付死锁的策略中，解除死锁通常都是与检测死锁配套使用

D.产生死锁的原因可归结为竞争资源和进程推进顺序不当

E.在死锁的解决方法中，由于避免死锁采用静态分配资源策略，所以对资源的利用率不高

8.下面__属于进程高级通信方式。

A.消息缓冲机制

B.信箱机制

C.共享内存机制

D.管道机制

E.管程机制

四、是非题

1.（　）共享数据的并发访问可能会产生数据的不一致性。

2.（　）系统中只要存在相关进程就有可能存在进程之间的同步和互斥。

3.（　）对临界资源不能实现共享。

4.（　）一个临界资源可能对应多个临界区。

5.（　）不安全序列不一定会导致死锁。

6.（　）P、V操作不仅可用来实现进程的同步和互斥，还可用来防止进程的死锁。

7.（　）进程P1与P2因共享变量C1而具有互斥关系，进程P2与P3因共享变量C2而具有互斥关系，则进程P1与P3也具有互斥关系。

8.（　）所有的共享资源都是临界资源。

9.（　）任何时刻，管程中最多只有一个进程在执行。

10.（　）资源分配图中出现了环路，则说明系统发生了死锁。

11.（　）除了赋予初值外，信号量仅能由同步原语对其进行操作，没有任何其他方法可以检查和操作信号量。

12.（　）用管程实现进程同步时，管程中的过程是不可中断的。

13.（　）资源的按序分配是防止死锁的一种策略。

14.（　）银行家算法是用于预防进程死锁的。

15.（　）死锁是指系统中所有的进程都处于阻塞状态。

16.（　）死锁既可能发生在相关进程之间，也可能发生在无关进程之间，即死锁可发生在任意进程之间。

17.（　）当每个资源类中仅有一个资源实例时，资源分配图中的环路是死锁的充要条件。

18.（　）死锁就是循环等待。

19.（　）参与死锁的所有进程都占有资源。

20.（　）假设系统中只有一个资源类，其中有m个资源实例，有n个使用此类资源的进程，它们所需资源的最大数量为S，则发生死锁的必要条件是S≥m+n。

五、综合题

1.何谓与时间有关的错误？举例说明之。

2.以下两个优先级相同的进程PA和PB在并发执行结束后，x、y和z的值分别为多少（信号量S1和S2的初值均为0）？

3.以下两个优先级相同的进程PA和PB在并发执行结束后，x、y和z的值分别为多少（信号量S1和S2的初值均为0）？

4.试比较“忙式等待”（忙等待）与“让权等待”的异同。

5.存在一组合作进程，执行顺序如图4-8所示。试用P、V操作实现进程之间的同步操作。

图　4-8　进程执行顺序

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

7.有一个仓库，可以存放A和B两种产品，仓库的空间足够大，但要求：

1）每次只能存入一种产品（X或Y）；

2）-N＜A的产品数量-B的产品数量＜M。

其中，N和M是正整数。试用P、V操作描述产品A与产品B的入库过程。

8.何谓临界区？下面给出的实现两个进程互斥的算法是安全的吗？为什么？

define true;

define false;

int flag[2];

flag[0]=flag[1]=flase;

enter-crtsec(i)

int i;

{

while(flag[1-i])

flag[i]=true;

}

leave-crtsec(i)

int i;

{

flag[i]=flase;

}

P_i://i=0 OR i=1

{

…

enter-crtsec(i);

In critical section;

Leave-crtsec(i);

…

}

9.设有8个程序，它们分别为prog1、prog2、…、prog8。它们在系统中执行时，存在如图4-9所示的制约关系，试用P、V操作实现这些程序间同步。

图　4-9　各进程之间的相互制约关系

10.多个进程共享一个文件，其中只读文件的称为读者；只写文件的称为写者。读者可以同时读，但是写者只能独立地写。要求完成：

1）说明进程间的相互制约关系，应设立哪些信号量？

2）用P、V操作写出其同步算法。

3）修改上述的同步算法，使得它对写者优先，即一旦有写者到达，无论是否有读者在读文件，所有的读者都必须等待。

11.设有一个具有N个信息元素的环形缓冲区，A进程顺序地把信息写入缓冲区，B进程依次地从缓冲区读出信息。回答下列问题：

1）叙述A、B两进程的相互制约关系；

2）用P、V操作表示两进程之间的同步算法。

12.图书阅览室共有座位200个，并提供一个登记表，表中每一行内容为读者姓名、座位号、进入时间和离开时间。读者进入并找到座位后必须在登记表上登记姓名、座位号、进入时间。读者离开阅览室时也必须在登记表中记录离开时间。试用P、V操作描述读者进程的并发过程。

13.试用P、V操作描述第12题中读者进入进程和读者离开进程的并发过程。

14.简述管程如何解决进程互斥和同步问题的。试用管程实现生产者-消费者问题（两个进程分别是生产者和消费者，并且共享一个公共的固定大小的有界缓冲区）。

15.试用消息传递解决第13题中的生产者-消费者问题。假设将相当于共享内存缓冲区的大小N，换为N条消息，N＞0，且为整数；所有的消息大小相同，并且在尚未接收到发出的消息时，由操作系统自动进行缓冲。

16.信箱通信中，对于只有一个发送进程和一个接收进程使用的信箱，若将信箱考虑成发送进程和接收进程之间大小固定的私有数据结构，并且进程间的通信应满足如下条件：

1）发送进程在发送消息时，信箱中至少要有一个空格能存放该消息。

2）接收进程接收消息时，信箱内至少有一个消息存在。

试使用用P、V操作来实现send原语和receive原语。

17.考虑由n个进程共享的具有m个同类资源的系统，证明：如果对i=1，2，…，n，有0＜need(i)≤m，且所有进程最大需求量之和小于m+n，那么该系统是死锁无关的。

18.用信号量及P、V操作解决生产者-消费者问题，并改动操作使之产生死锁。

19.什么叫饥饿？什么叫饿死？举例说明。什么叫活锁？

20.比较死锁与饿死的异同点。

21.两个进程A和B，每一个进程都需要读取数据库中的记录1、2、3，假如这两个进程都以1、2、3的次序读取记录，系统将不会发生死锁。但如果A以3、2、1的次序读取记录，B以1、2、3的次序读取记录，则死锁可能发生。试计算两个进程读取记录的次序如果不确定，那么系统保证不发生死锁的概率是多少？

22.消息缓冲通信技术是一种高级通信机制，由Hansen首先提出：

1）试叙述高级通信机制与低级通信机制P、V原语的主要区别。

2）给出消息缓冲机制（有限缓冲）的基本原理。

3）消息缓冲通信机制（有限缓冲）中提供发送原语send(a)和receive(a)，参数a表示发送消息的内存首地址。设计相应的数据结构，利用P、V操作，实现send原语。

23.下面给出了两种使用P、V操作解决司机-售票员问题的并发控制算法。请在每个空栏处填写一条P操作或V操作，并说明所用信号量的含义和初值。

算法1：

算法2：

24.考虑下列资源分配策略：对资源的申请和释放，可以在任何时刻进行。如果一个进程的资源得不到满足，则检查所有等待资源而被阻塞的进程。如果它们有申请进程所需要的资源，则将这些资源取出分配给申请进程。

例如，考虑一个有3类资源的系统，系统所有可用资源为（4，2，2），进程A申请（2，2，1），可满足；进程B请求（1，0，1），可以满足；若A再申请（0，0，1），则被阻塞。此时，若C进程请求（2，0，0），它可以分到剩余资源（1，0，0）并从A已分到的资源中获得一个资源，于是进程A的分配向量变成（1，2，1），而需求向量变成（1，0，1）。

1）这种分配方式会导致死锁吗？如果会，请举一个例子；如果不会，请说明产生死锁的哪一个条件不成立。

2）这种分配方式会导致某些进程的无限等待吗？为什么？

25.在银行家算法中，T₀时刻若出现表4-1所示资源分配情况，问：

1）在表中填写T₀时刻各进程的最大资源需求数。

2）T₀时刻是否为安全状态？并说出理由（要求给出检测过程）。

3）若在T₁时刻进程P1请求资源（1，2，2，2），系统能否将资源分配给它？请说出理由（要求给出检测过程）。

26.系统中有A、B、C三类资源，并且拥有P1、P2、P3、P4、P5五个进程，在T₀时刻，系统的状态如表4-2所示。

1）在T₀时刻，系统是否处于安全状态，如果是，给出安全序列；否则，简述原因。

2）在T₀时刻，如果有一个请求（0，3，4），这个请求能否被立即允许？简述原因。

3）在第2问的基础上，如果P4有一个请求（2，0，1），这个请求能否被立即允许？简述原因。

27.请写出一种检测进程死锁的方法及相应的结论（或算法）。

28.分析下面信号量解决哲学家进餐问题的同步算法，是否满足同步机制的准则。若不满足说明为什么，并给出同步机制准则的同步算法。

VAR fork:array[0..4] of semaphore;

fork[0]:=fork[1]:=fork[2]:=fork[3]:=fork[4]:=1;

cobegin

Pi:repeat//第i个哲学家的生活过程

think for while;

P(fork[i]);

P(for[i+1]MOD 5);

eat for while;

V(fork[i]);

V(fork[(i+1)MOD 5]);

until false

coend