进程同步与死锁

(1) 什么是进程同步？什么是进程互斥？

解：

同步是进程间的直接制约关系，这种制约主要源于进程间的合作。进程同步的主要任务就是使并发执行的各进程之间能有效地共享资源和相互合作，从而在执行时间、次序上相互制约，按照一定的协议协调执行，使程序的执行具有可再现性。

进程互斥是进程间的间接制约关系，当多个进程需要使用相同的资源，而此类资源在任一时刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待，进程的运行具有时间次序的特征，谁先从系统获得共享资源，谁就先运行，这种对共享资源的排它性使用所造成的进程间的间接制约关系称为进程互斥。互斥是一种特殊的同步方式。

(2) 进程执行时为什么要设置进入区和退出区？

解：

为了实现多个进程对临界资源的互斥访问，必须在临界区前面增加一段用于检查欲访问的临界资源是否正被访问的代码，如果未被访问，该进程便可进入临界区对资源进行访问，并设置正被访问标志，如果正被访问，则本进程不能进入临界区，实现这一功能的代码成为“进入区”代码；在退出临界区后，必须执行“退出区”代码，用于恢复未被访问标志。

(3) 同步机构需要遵循的基本准则是什么？请简要说明。

解：

同步机制都应遵循下面的4条准则：

1. 空闲让进。当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。
2. 忙则等待。当有一个进程在临界区时，其它欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
3. 有限等待。对要求访问临界资源的进程，应保证进程能在有限时间内进入临界区，以免陷入“饥饿”状态。
4. 让权等待。当进程不能进入临界区时，应立即放弃占用CPU，以使其它进程有机会得到CPU的使用权，以免陷入“饥饿”状态。

(4) 整型信号量是否能完全遵循同步机构的四条基本准则？为什么？

解：

不能。在整型信号量机制中，未遵循“让权等待”的准则。

(5) 在生产者-消费者问题中，若缺少了V(full)或V(empty)，对进程的执行有什么影响？

解：

如果缺少了V(full)，那么表明从第一个生产者进程开始就没有对信号量full值改变，即使缓冲池存放的产品已满了，但full的值还是0，这样消费者进程在执行P(full)时会认为缓冲池是空的而取不到产品，那么消费者进程则会一直处于等待状态。

如果缺少了V(empty)，例如在生产者进程向n个缓冲区放满产品后消费者进程才开始从中取产品，这时empty=0，full=n，那么每当消费者进程取走一个产品时empty并没有被改变，直到缓冲池中的产品都取走了，empty的值也一直是0，即使目前缓冲池有n个空缓冲区，生产者进程要想再往缓冲池中投放产品会因申请不到空缓冲区而被阻塞。

(6) 在生产者-消费者问题中，若将P(full)和P(empty)交换位置，或将V(full)或V(empty)交换位置，对进程执行有什么影响？

解：

对full和empty信号量的P、V操作应分别出现在合作进程中，这样做的目的是能正确表征各进程对临界资源的使用情况，保证正确的进程通信联络。

?(7) 利用信号量写出不会出现死锁的哲学家进餐问题的算法。

解：

对哲学家按顺序从0到4编号，哲学家i左边的筷子的编号为i，哲学家右边的筷子的编号为（i+1）%5。

semaphore?chopstick[5]={1};

?//定义信号量数组chopstick[5]，由于筷子是临界资源（互斥），故设置初值均为1。

Pi(){

//i号哲学家的进程

????do{

?????????if(i<(i+1)%5)

?????????{

?????????????wait(chopstick[i]);

?????????????wait(chopstick[(i+1)%5]);

?????????}

?????????else

?????????{

?????????????wait(chopstick[(i+1)%5]);

?????????????wait(chopstick[i]);

?????????}

?????????eat

?????????signal(chopstick[i]);

?????????signal(chopstick[(i+1)%5]);

?????????think

???????}while(1);

}

(8) 利用AND型信号量和管程解决生产者-消费者问题。

解：

利用AND信号量解决生产者－消费者问题的算法描述如下：

var mutex,empty,full: semaphore:=1,n,0;

buffer: array[0,...,n-1] of item;

in?out: integer?:=?0,?0;

begin

parbegin

producer: begin

repeat

.

.

.

produce an item in nextp;

.

.

.

Swait(empty, mutex);

buffer(in)?:=?nextp;

in?:=?(in+1) mod n;

Ssignal(mutex, full);

until false;

end

consumer: begin

repeat

Swait(full, mutex);

nextc?:=?buffer(out);

out?:=?(out+1) mod n;

Ssignal(mutex, empty);

consume the item in nextc;

until false;

end

parend

end

利用管程机制解决生产者-消费者问题，首先需要建立一个管程ProducerConsumer，其中包含两个过程insert(item)和consumer(item)。生产者-消费者同步问题可以用伪代码描述如下：

monitor ProducerConsumer

condition full,empty;

int count;

void insert(int item)

{

if (count==N) wait(full);

insert(item);

count=count+1;

if (count==1) signal(empty);

}

int remover()

{

if (count==0) wait(empty);

remove=remove_item;

count=count-1;

if (count==N-1) signal(full);

}

count=0;

end monitor

void producer()

{

????while (true)

????{

???item=produce_item;

???ProducerConsumer.insert(item);

????}

}

void consumer()

{

????while?(true)

????{

???item=ProducerConsumer.remove;

???consume(item)

????}

}

(9) 进程的高级通信机制有哪些？请简要说明。

解：

进程的高级通信机制分为三大类：共享存储系统、消息传递系统和管道通信系统。

1. 共享存储器系统：在共享存储器系统中，相互通信的进程通过共享某些数据结构或共享存储区实现进程之间的通信。该系统又可进一步细分为两种方式：基于共享数据结构的通信方式和基于共享存储区的通信方式。
2. 消息传递系统：消息传递机制可以实现不同主机间多个CPU上进程的通信。这种方式需要使用两条原语send和receive来发送和接收格式化的消息(message)。
3. 管道通信系统：管道通信是一种以文件系统为基础实现的适用于在进程之间实现大量数据传送的通信方式。

(10) 什么是死锁？产生死锁的原因和必要条件是什么？

解：

所谓死锁是指在一个进程集合中的所有进程都在等待只能由该集合中的其它一个进程才能引发的事件而无限期地僵持下去的局面。

????产生死锁的原因可以归结为两点：1）竞争资源， 2）各进程之间的推进顺序不当。

????产生死锁的必要条件有四个：1）互斥条件， 2）不剥夺条件， 3）请求和保持条件， 4）环路条件。

(11) 死锁的预防策略有哪些？请简要说明。

解：

死锁的预防策略有三，说明如下：

1. 摒弃请求和保持条件：为摒弃请求和保持条件，系统中需要使用静态资源分配法，该方法规定每一个进程在开始运行前都必须一次性地申请其在整个运行过程中所需的全部资源。此时，若系统有足够的资源，就把进程需要的全部资源一次性地分配给它；若不能全部满足进程的资源请求，则一个资源也不分给它，即使有部分资源处于空闲状态也不分配给该进程。这样，当一个进程申请某个资源时，它不能占有其它任何资源，在进程运行过程中也不会再提出资源请求。这种方法破坏了请求和保持条件，从而避免死锁的发生。
2. 摒弃不剥夺条件：要摒弃“不剥夺条件”，可以使用如下策略：进程在需要资源时才提出请求，并且进程是逐个地申请所需资源，如果一个进程已经拥有了部分资源，然后又申请另一个资源而不可得时，其现有资源必须全部释放。在这种方法中，进程只能在获得其原有资源和所申请的新资源时才能继续执行。
3. 摒弃环路等待条件：为确保环路等待条件不成立，可以在系统中实行资源有序分配策略，即系统中的所有资源按类型被赋予一个唯一的编号，每个进程只能按编号的升序申请资源。

(12) 某系统中有A、B、C、D四类资源，且其总数量都是8个。某时刻系统中有5个进程，判断下列资源状态是否安全？若进程P2申请资源(1，1，1，1)，能否为其分配？

进程	Need A ?B ?C ?D	Allocation A ?B ?C ?D
P0	0 ?0 ?4 ?3	0 ?0 ?2 ?2
P1	2 ?6 ?3 ?0	1 ?1 ?0 ?0
P2	3 ?2 ?1 ?5	2 ?1 ?0 ?3
P3	4 ?0 ?2 ?0	2 ?0 ?0 ?0
P4	0 ?5 ?5 ?4	0 ?2 ?2 ?2

解：

现在对该时刻的状态进行安全分析：

????由于Available向量为（3，4，4，1），所以Work向量初始化为（3，4，4，1）

此时的Work小于任意的Need[i]向量，所以系统处于不安全状态

????由于Request2(1,1,1,1)<Available（3,4,4,1）且Request2（1,1,1,1）<Need2（1,1,1,2）

????所以先试着把P2所申请的资源分配给它，Available变为（2,3,3,0）得到系统状态如下表所示：

	Allocation				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	2	2	0	0	4	3	2	3	3	0
P1	1	1	0	0	2	6	3	0
P2	3	2	1	4	2	1	0	4
P3	2	0	0	0	4	0	2	0
P4	0	2	2	2	0	5	5	4

然后进行安全性检测：

此时Available向量为（2,3,3,0），所以Work向量初始化为（2,3,3,0），此时的Work小于任意的Need[i]向量，所以系统处于不安全状态，所以不可以为P2分配资源

(13) 三个进程P1、P2、P3都需要5个同类资源才能正常执行直到终止，且这些进程只有在需要设备时才申请，则该系统中不会发生死锁的最小资源数量是多少？请说明理由。

解：

系统中不会发生死锁的最小资源数量是13，这样可以保证当每一个进程都占有4个资源的时候，有一个进程可以获得最后一个资源后被运行，运行完毕后释放资源，于是其余进程也能顺利运行完，所以不会死锁。

(14) 在解决死锁问题的几个方法中，哪种方法最易于实现，哪种方法使资源的利用率最高？

解：

预防死锁这个方法实现简单，效果突出；避免死锁这种方法系统吞吐量和资源利用率较高。

?(15) 考虑由n个进程共享的具有m个同类资源的系统，如果对于i=1,2,3,…,n,有Need[i]>0并且所有进程的最大需求量之和小于m+n，试证明系统不会产生死锁。

解：

本题中只有一种资源，不妨设Max[i]为第i个进程的资源总共需要量，Need[i]为第i个进程还需要的资源数量，Allocation[i]表示第i个进程已经分配到的资源数量，Available为系统剩余的资源数，其中i=1,2,3,…,n。

假设此系统可以发生死锁。

系统剩余的资源数量为Available（Available>=0），由假设，因为系统处于死锁状态，所以Available个资源无法分配出去，所以每个进程的Need[i]都大于Available，

即 ?????????????Need[i]>=Available+1

所以 ???????????∑Need[i]>=n*(Available+1)=n*Available+n, ??????????????????①

因为剩下的资源数是Available，所以已经分配出去的资源数为m –?Available;

即 ?????????????∑Allocation[i]=m –?Available ???????????????????????????????②

由①式和②式可以得到：

∑Need[i] + ∑Allocation[i]>=n*Available+n+ m –?Available=（n-1）*Available+m+n ?③

又因为n>=1，所以（n-1）>=0，又因为Available>=0，所以（n-1）*Available>=0 ??④

由③式和④式可以得到∑Need[i] + ∑Allocation[i]>=0+m+n=m+n ????????????????⑤

根据题意知： ????????∑Max[i]<m+n ???????????????????????????????????????⑥

又因为：Max[i]=Need[i]+Allocation[i],所以∑Max[i]= ∑Need[i] + ∑Allocation[i] ???⑦

由⑥式和⑦式得：∑Need[i] + ∑Allocation[i]<m+n ????????????????????????????⑧

由假设推出的⑤式和由题意推出的⑧式相矛盾，所以假设是错误的，即系统不会产生死锁。

?(16) 某车站售票厅，在任何时刻最多可以容纳 20 名购票者进入，当售票厅中少于20名购票者时，厅外的购票者可立即进入，否则需要在外面等待。若把一个购票者看作一个进程，请回答以下问题：

① 用信号量管理这些并发进程时，应该怎样定义信号量，写出信号量的初值以及信号量的各取值的含义。

② 根据所定义的信号量，写出相应的程序来保证进程能够正确地并发执行。

③ 如果购票者最多为n个人，试写出信号量取值的可能变化范围(最大值和最小值)。

解：

①定义信号量S,初值为20，当s > 0时，它表示可以继续进入购票厅的人数，当s = 0时表示厅内已有20人正在购票，当s < 0时| s |表示正等待进入的人数。

②semaphore?S=20;

begin

parbegin

procedure:begin

repeat

wait(s);

????????????Enter and buy ticket;

????????????signal(s);

????????????until false;

end

??????parend

????????end

????③最大值为20，最小值为20-n

(17) 在测量控制系统中的数据采集任务时，把所采集的数据送往一单缓冲区；计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两个任务共享单缓冲区的同步算法。

解：

semaphore mutex = 1;

semaphore full = 0;

semaphore empty = 1;

begin

??parbegin

collect:

begin

???????????????repeat

???????????????……

???????????????collect data in nextp;

???????????????wait(empty);

???????????????wait(mutex);

buffer:=nextp;

signal(mutex);

signal(full);

until false;

???????????end

compute:

begin

???????????????repeat

???????????????……

???????????????wait(full);

???????????????wait(mutex);

nextc:=buffer;

signal(mutex);

signal(empty);

???????????????compute data in nextc;

until false;

???????????end

?????????parend

???????end

(18) 桌上有一空盘，允许存放一只水果。爸爸可以向盘中放苹果，也可以向盘中放桔子，儿子专等着吃盘中的桔子，女儿专等着吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者用，请用信号量实现爸爸、儿子和女儿3个并发进程的同步。

解：

本题中应设置三个信号量S、So、Sa，信号量S表示盘中是否为空，其初值为1；So表示盘中是否有桔子，其初值为0；Sa表示盘中是否有苹果，其初值为0。同步描述如下：

爸爸: P(S); ????????????????????儿子：P(So); ?????????????女儿：P(Sa);

??????将水果放入盘中 ???????????从盘子中取出桔子 ??????????从盘子中取出苹果

??????if (放入的是桔子) ?v(So)； ??????V（S）； ??????????????????V（S）；

??????else ?v(Sa)； ??????????????????吃桔子?????????????????????吃苹果；

(19) 设某系统中有3个进程Get、Process和Put，共用两个缓冲区buffer1和buffer2。假设buffer1中最多可以放11个信息，现在已经放入了两个信息；buffer2最多可以放5个信息。Get进程负责不断地将输入信息送入buffer1中，Process进程负责从buffer1中取出信息进行处理，并将处理结果送到buffer2中，Put进程负责从buffer2中读取结果并输出。试用信号量机制实现它们的同步与互斥。

解：

semaphore empty1=9; //buffer1空的数量

semaphore full1=2; //buffer1满的数量

semaphore empty2=5; //buffer2空的数量

semaphore full2=0; //buffer2满的数量

in1,in2,out1,out2:integer := 2,0,1,0;

Get(){

while(1){

wait(empty1)

??????????in1=(in1+1)mod11

??????????signal(full1)

??????}

}

Process（）{

while(1){

wait(full1)

??????????out1=(out1+1)mod11

??????????signal(empty1)

??????????signal(empty2)

??????????in2=(in2+1)mod5

??????????signal(full2)

???????}

}

Put(){

while(1){

wait(full2)

???????????out2=(out2+1)mod5

???????????signal(empty2)

???????}

}

(20) 某寺庙有大、小和尚若干，另有一水缸。由小和尚挑水入缸供大和尚饮用。水缸可以容10桶水，水取自同一井。水井很窄，每次只能容一个水桶取水。水桶总数为3。每次入、取缸水仅为1桶，且不可同时进行。试给出取水、入水的同步算法。

解：

semaphore well=1; // 保证互斥地访问水井的信号量

semaphore vat=1; // 保证互斥地访问水缸的信号量

semaphore empty=10; // 表示水缸中剩余的空间能容纳的水的桶数

semaphore full=0; // 表示水缸中水的桶数

semaphore pail=3; // 保证互斥地访问临界资源水桶的信号量

// 大和尚进程

big_monk(){

????while(1){

????????wait(full);

????????wait(pail);

????????wait(vat);

????????use pail to get water from vat

????????signal(vat);

????????signal(empty);

????????drink water in the pail

????????signal(pail);

????} ???????

?}

?// 小和尚进程

?little_monk(){

???while(1){

??????wait(empty);\

??????wait(pail);

??????wait(well);

??????use pail to get water from well

??????signal(well);

??????wait(vat);

??????pour water to the vat

??????signal(vat);

??????signal(full);

??????signal(pail);

???}

}

(21) 在银行家算法中，若出现下述资源分配情况：

Process Allocation ???Need ??????Available

P0 ?????0 0 3 2 ????0 0 1 2 ??????1 6 2 2

P1 ?????1 0 0 0 ????1 7 5 0

P2 ?????1 3 5 4 ????2 3 5 6

P3 ?????0 0 3 2 ????0 6 5 2

P4 ?????0 0 1 4 ????0 6 5 6

试问：

① 该状态是否安全？

② 若进程 P2 提出请求 Request( 1, 2, 2, 2 )后，系统能否将资源分配给它？

解：

现在对该时刻的状态进行安全分析：

????由于Available向量为（1，6，2，2），所以Work向量初始化为（1，6，2，2）该时刻的安全性检查表如下：

	Work				Need				Allocation				Work+Allocation				Finish
	A	B	C	D	A	B	C	D	A	B	C	D	A	B	C	D
P0	1	6	2	2	0	0	1	2	0	0	3	2	1	6	5	4	True
P3	1	6	5	4	0	6	5	2	0	0	3	2	1	6	8	6	True
P4	1	6	8	6	0	6	5	6	0	0	1	4	1	6	9	10	True
P2	1	6	9	10	2	3	5	6	1	3	5	4	2	9	14	14	True
P1	2	9	14	14	1	7	5	0	1	0	0	0	3	9	14	14	True

????如表所示，存在安全序列<P0，P3，P4，P2，P1>，所以该时刻处于安全状态。

????由于Request2(1,2,2,2)<Available（1,6,2,2）且Request2（1,2,2,2）<Need2（2,3,5,6），所以先试着把P2所申请的资源分配给它，Available变为（0,4,0,0）得到系统状态如下表所示：

	Allocation				Need				Available
	A	B	C	D	A	B	C	D	A	B	C	D
P0	0	0	3	2	0	0	1	2	0	4	0	0
P1	1	0	0	0	1	7	5	0
P2	2	5	7	6	1	1	3	4
P3	0	0	3	2	0	6	5	2
P4	0	0	1	4	0	6	5	6

????然后进行安全性检测，此时Available为（0,4,0,0），所以Work初始化为（0,4,0,0）。

????此时的Work小于任意的Need[i]向量，所以系统处于不安全状态，即认为不能分配资源（0,2,0）给P2。

(22) 设系统中仅有一类数量为M的独占型资源，系统中有N个进程竞争该类资源，其中各进程对该类资源的最大需求量为W。当M、N、W分别取下列值时，试判断哪些情形可能会发生死锁，为什么？

(1)M=2，N=2，W=1； ?????????(2)M=3，N=2，W=2；

(3)M=3，N=2，W=3； ?????????(4)M=5，N=3，W=2；

解：

1. 不会发生死锁。因为两个进程需要的最多资源量都是1个，而系统拥有的资源量正好是2个，两个进程都能顺利运行完，所以不会死锁。
2. 不会发生死锁。因为2个进程需要的最多的资源量都是2个，而系统拥有的资源量是3个，所以总会有1个进程得到2个资源后被运行，运行完毕后释放资源，于是另一个进程也能顺利运行完，所以不会死锁。
3. 会发生死锁。当一个进程占有1个资源，另一个进程占有2个资源时，2个进程都要再申请资源，但是系统已经没有资源了，所以就发生死锁了。
4. 不会发生死锁。因为三个进程需要的资源最大数量都是2个，而系统有5个资源，所以至少有2个进程可以拿到足够的资源运行，运行完后再释放资源，最后一个进程也能得到运行，所以不会死锁。