更新于 

信号量与经典同步问题(1)

信号量机制

在信号量机制中一个信号量代表一种资源，信号量的值就是这种资源剩余的值，如果信号量的值小于0，说明此时有进程在等待这种资源。P(s)代表申请一个资源s,如果资源不够就阻塞等待，V(s)代表释放一个资源s,如果有进程在等待该资源，则唤醒一个进程。

信号量机制实现进程互斥

首先我们先看一下信号量的结构体

1
2
3
4
5
//数值型信号量的定义
typedef struct {
    int value;//剩余资源数
    struct process *L;//等待队列
}semaphore

一般我们如果要借用信号量机制实现进程间的互斥，那么首先毫无疑问需要将并发进程间的关键活动划定为临界区，如各进程对临界资源打印机的访问的代码就应该划分到临界区。然后我们这里初始化一个新的信号量mutex（代表一种新的资源）初始化为1，则进入区P(mutex)就是申请资源，退出区的V(mutex)就是释放资源。所以我们对于不同的临界资源都需要设置各自对应的互斥信号量进行判断。并且P,V操作必须成对出现，缺少P就不能保证临界资源的互斥访问，而缺少V就会导致资源永不释放，等待的进程一直永不被唤醒造成饥饿现象。这样当mutex设置为1时每次都保证了只会有一个进程访问临界资源并且做到了进程互斥的四大原则（“空闲让进”，“忙则等待”，“有限等待”，“让权等待”）。如下：

这样P1,P2之间就通过mutex1和P,V操作实现了并发进行间的互斥，而P3,P4之间通过mutex2和P,V操作也实现了并发进行间的互斥。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
semaphore mutex2=1;//初始化信号量
semaphore mutex1=2;//初始化信号量

P1(){
    ...
        P(mutex1)//使用临界资源前需要加锁
        critical section;//临界区
    	V(mutex1);
}
P2(){
    ...
        P(mutex1)//使用临界资源前需要加锁
        critical section;//临界区
    	V(mutex1);
}

P3(){
    ...
        P(mutex2)//使用临界资源前需要加锁
        critical section;//临界区
    	V(mutex2);
}
P4(){
    ...
        P(mutex2)//使用临界资源前需要加锁
        critical section;//临界区
    	V(mutex2);
}

实际上上面这种方法也就是PV互斥锁实现进程互斥，这种方法无疑是最优解他做到了四个原则。

信号量实现进程同步

我们前面学到了进程同步它是一种直接限制关系，即一般发生在某个进程P2必须等待进程P1发生以后才可以发生，这种存在先后关系的并发运行就存在进程同步问题。那么这种让本来异步并发的进程互相配合，有序推进就需要信号量机制加以约数实现。

实现方法如下：

  1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作（或两句代码）
  2. 设置同步信号量S，初始化为0
  3. 在“前操作”之后执行V(s)
  4. 在“后操作”之前执行P(s)

从上面的操作中我们也可以看出P,V操作一定还是成对出现的但是出现顺序可以发生改变，对于进程互斥是P前V后并且每个进程同时拥有P,V操作，而对于进程同步一般是V前P后，且每个进程只拥有P或者V。

代码如下：

我们还是要先声明信号量但是此时一定要注意是初始化为0：

1
semaphore s=0

这样我们可以理解为信号量s代表“某种资源”，刚开始是没有的，而P2需要这种资源才能继续执行，所以他需要等待P1执行完P操作后s++，此时P2才可以继续执行，这种P,V操作就完美实现了进程间的同步。

即如果先执行到了进程1的V(s)操作，那么s++,之后当执行到进程2的P(s)操作时，由于s=1满足条件表示有可用资源，会执行s–，s的值会变回0同时p2进程不会执行block原语而是继续向后执行代码4。

如果先执行到了进程2的P(s)操作，由于s=0,s–后s=-1，此时表示没有可用资源，前面也提到过了当信号量<0表示有进程等待，所以此时进程2执行block原语主动请求阻塞等待。之后当执行到P1的V(s)后s++,使s变回0同时前面也提到过当执行V操作对信号量++的同时还会检查等待队列是够有阻塞进程，如果有就会执行wakeup原语唤醒等待进程，这样P2进程就可以继续执行了。

信号量机制实现前驱关系

进程P1有句代码S1,P2有句代码S2，P3有句代码S3,…，P6有句代码S6，这些代码需要按照如下图的先后顺序执行，其实仔细看对于每一对前驱关系都对应一个信号量一组P,V操作所以前驱关系的子问题就是进程同步。因此对于前驱关系(具有多组进程同步关系的问题)需要为每一对前驱关系都设置一个同步信号量，在“前操作”之后设置相对应的V操作(由于信号量不同，V操作并不相同)同时对于“后操作”之前对应的同步信号量也需要执行P操作(由于信号量的不同，P操作也不相同)。

各进程之间的代码如下：

我们可以画出树状结构来更好的看出前驱关系如下：

总结

生产者-消费者问题

我们首先看一下问题描述

问题描述

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品都会放入缓冲区，而消费者进程每次从缓冲区都取出一个产品使用(这里的"产品"就是一种数据)。所以生产者和消费者共享一个初始为空，大小为n的缓冲区，只有缓冲区没满时生产者才能把产品放入缓冲区，否则就要阻塞等待。只有缓冲区不空时消费者才能从产品中取出产品，否则必须阻塞等待。并且缓冲区是临界资源，需要各进程互斥的访问。

问题分析

我们对于这种问题很容易就能想到刚刚介绍的PV操作实现同步互斥关系。一般对于PV操作解决问题就是分析出题目中的各个进程之间的关系，然后画图确定P,V操作的大致顺序，同时设置信号量(一般都是数值型)进程互斥设置为1就行，而对于同步信号量的处置要根据对应资源的初始值设置。对于生产/消费者问题我们分析一下题目要求：

  1. 缓冲区没空的时候消费者可以消费(同步关系)
  2. 缓冲区没满的是够生产者才可以生产(同步关系)
  3. 进程之前（即生产者-消费者，消费者-消费者）之间都需要互斥访问临界资源缓冲区(互斥关系)

所以我们需要设置三个信号量如下：

1
2
3
4
semaphore mutex=1;//互斥信号量，实现对缓冲区的互斥访问
semaphore empty=n;//同步信号量，表示空闲缓冲区的数量，当<=0表示缓冲区满
semaphore full=0;
//同步信号量，表示产品的数量即非空缓冲区的数量当<=N时表示缓冲区没满

那么我们可以用如下代码实现：

首先无论是哪个进程进入临界资源都要新进行mutex互斥锁判断，然后对于生产者和消费者之间的同步关系分别具有一个P,V同步锁的一部分。一定要记住P操作每次都–，V操作每次都++同时V操作每次还会进行唤醒等待进程的操作。所以一定要理解并不是每次产品者都把缓冲区用产品填满以后才唤醒消费者，而是当生产出了产品就可以唤醒等待的消费者了同时也并不是消费者每次都用空了缓冲区才唤醒生产者，而是只要缓冲区没满就会唤醒生产者，即边生产边消费的现象出现，但是最终边生产边消费的现象会趋于一个稳态：

  1. 生产的速度和吃的速度整体看来相当，那么缓冲区既不空也不满整体上看来生产者和消费者都有并发互斥访问临界资源
  2. 生产的速度整体上比消费的速度快，最终缓冲区满了以后生产者沉睡并且直至缓冲区再次没满的情况出现前一直沉睡直至消费者消费了产品后再次唤醒生产者
  3. 生产的速度整体上慢于消费的速度，那么缓冲区空了以后消费者全部沉睡等待，当生产者再次生产出产品时就会再次唤醒消费者
思考：相邻的P操作能够更改顺序？

即如下图：

临界区访问互斥锁的P操作和同步信号量检验的P操作进行了交换，此时是先检验能否进入临界资源在检验能否生产或者消费的情况。

我们假设此时缓冲区已经满了，即empty=0,full=n。此时生产者又生产了一个产品按照① 使mutex变为0，然后在执行②，由于此时已经没有空闲缓冲区了，所以生产者被阻塞沉睡，由于生产者阻塞，因此切换回消费者进程，消费者进程执行③，由于mutex=0即生产者还没有释放对临界资源的"锁"，所以生产者就一直沉睡等待与此用时生产者也在沉睡等待消费者消费产品造成了"死锁"现象的出现。

同样的假设缓冲区现在没有产品，即empty=n,full=0。那么此时消费者进入临界区想取出一个产品，此时mutex=0，发现没有产品可以取出了，所以阻塞沉睡切换到生产者进程生产者生产了产品想放入临街资源缓冲区中，但是此时mutex=0消费者还没有释放"锁"所以生产者只能也沉睡等待消费者出来在放入产品，而此时消费者也在等待生产者放入产品也造成了"死锁"现象。

所以我们可以总结出来无论是哪个进程实现互斥的P操作必须放在实现同步的P操作之后。

思考：上图右边的问题：能否把使用产品放到PV操作之前

即如下图：

1
2
3
4
5
6
7
8
9
10
consumer(){
	while(1){
        //使用产品
        P(mutex);
        P(full);
        //从缓冲区取产品
        V(mutex);
        V(empty);
    }
}

想也不要想这种情况会造成一个很离谱的情况就是此时如果缓冲区已但是消费者却可以不经过检验继续先使用产品，但是此时缓冲区已经没产品了他消费的产品从哪里来呢？

思考：相邻的V操作能够更改顺序？

事实证明，V操作之间是可以更改顺序的，此时不会造成"死锁"现象仍可以正常执行。

多生产者-多消费者问题

问题描述

桌子上有一只盘子，每次只能向其中放一个水果，爸爸专向盘子中放苹果，妈妈专向盘子放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果，只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果，仅当盘子中有自己需要的水果，儿子或者女儿才可以从盘子中取水果。

问题分析

我们发现有如下几个关系：

  1. 盘子需要互斥访问(互斥关系)
  2. 只有盘子中为苹果时女儿才取(同步关系)
  3. 只有盘子中为橘子时儿子才取(同步关系)
  4. 只有盘子为空时爸爸或者妈妈才可以放水果(同步关系)

所以我们第一想法就是设置4个信号量如下：

1
2
3
4
semaphore mutex=1;//实现盘子互斥访问的信号量
semaphore apple=0;//盘子中有几个苹果<=0为无苹果
semaphore orange=0;//盘子中有几个橘子<=0为无橘子
semaphore plate=1;//盘子中还可以放几个水果<=0表示不可以放水果

那么4个进程之间的代码实现如下：

很明显确实实现了题目要求。

思考：可不可以不要互斥信号量？

即plate互斥信号量删除不用能否满足要求，如下：

我们发现也没有太大的问题，因为此时apple,orange,plate三个信号量永远只有一个会是1也就说明每次都只会有一个进程是非阻塞状态，所以也就只有他可以访问临界区完全不可能出现多个进程用时访问临界资源的情况，所以完全不需要互斥信号量mutex。所以这种方法更好，但是注意仅适用于plate=1的情况，如果一次性可以放入2个或多个水果，即缓冲区容量>1的情况就必须使用mutex互斥信号量了。

思考：为什么缓冲区容量>1时必须使用互斥信号量mutex?

因为此时假设缓冲区容量为2，即盘子可以放2个水果，那么此时假设父亲P(plate)可以访问盘子(此时plate初始值为2，一次P操作plate–=1)，母亲此时也进行P(plate)也可以访问盘子(因为此时plate>0还可以通过检验)此时就出现了两个进程同时访问缓冲区的情况，有可能导致两个进程写入的缓冲区数据相互覆盖。因此当缓冲区大于1的情况时就必须专门设置一个互斥信号量mutex来实现互斥访问了。

总结

对于无论是生产者-消费者问题还是多生产者-多消费者问题最好都加上mutex锁以避免特殊情况出现。

快来参与讨论吧