更新于 

经典同步问题(2)

吸烟者问题

问题描述

假设有一个系统有三个抽烟者进程和一个供应者进程，每个抽烟者不停地卷烟并抽掉他，但是要卷烟起并抽掉一只烟需要有三种材料：烟草，纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者进程无限的提供这三种材料但是每一次供应者只在桌子上放两种材料，而拥有剩余那种材料的抽烟者才能卷一根并抽掉他，并给供应者一个信号告诉完成了，此时供应者就会将另外两种材料放在桌子上一直重复使得三个抽烟者进程可以轮流的抽烟。

问题分析

我们分析一下题意不难发现这是一个生产者对应多个消费者的问题，并且特殊地是这个生产者可以生产多种产品，如上图：

生产者可以生产三种产品分别是：

  1. 纸+胶水
  2. 烟草+胶水
  3. 烟草+纸

而消费者各自有不同的产品需求分别对应消费生产者的三种产品同时这样看来实际上还是缓冲区只能容下一个产品，并且一次性只能有一个进程访问缓冲区，所以事件关系如下：

  1. 桌子上有组合1的产品->第一个抽烟者取走东西抽烟(同步关系)
  2. 桌子上有组合2的产品->第二个抽烟者取走东西抽烟(同步关系)
  3. 桌子上有组合3的产品->第三个抽烟者取走东西抽烟(同步关系)
  4. 抽烟者发出完成信号->供应者将下一种产品组合放到桌子上(同步关系)
  5. 各进程互斥访问临界资源–桌子(互斥关系)
思考：需要设置，互斥信号量吗？

前面我们提到过对于一个临界资源并且每次都只有一个同步信号量为1的情况可以不设置互斥信号量，此问题也可以不设置互斥信号量。

代码如下：

首先声明信号量其次声明索引值i用来判断供应者该提供那种产品了

1
2
3
4
5
semaphore offer1=0;//桌子上组合1的数量
semaphore offer2=0;//桌子上组合2的数量
semaphore offer3=0;//桌子上组合3的数量
semaphore finish=0;//抽烟是否完成
int i=0;//用于实现"三个抽烟者轮流抽烟"

供应者代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
provider(){
    while(1){
        if(i==0){
            //将组合1的产品放到桌子上
            V(offer1);
        }
        else if(i==1){
            //将组合2的产品放到桌子上
            V(offer2);
        }
        else if(i==2){
            //将组合3的产品放到桌子上
            V(offer3);
        }
        i=(i+1)%3;
        P(finish);
    }
}

抽烟者代码：

思考：为什么这次供应者的P操作放到了后面？

因为初始化时finishi为0，而桌子上一开始是没有组合产品的，所以供应者现需要进行一次产品放置，所以此时P操作放在了最后面实际上就等于放在了下一次循环的开头，如果初始化时finish为1那么P操作就应该放在最前面。并且对于这种可以生产多个产品的供应者一定注意V操作对应着不同事件下。

读者-写者问题

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程用时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或者写进程)同时访问共享数据时则可能导致数据不一致的错误，因此要求：

  1. 允许多个读者进程同时对文件进行读操作
  2. 只允许一个写者往文件中写信息
  3. 任一一个写者在完成写操作之前不允许其他的读者或者写者工作
  4. 写者操作执行写操作之前需要保证已有的读者和写着进程全部已经退出共享文件

注意：这里和生产-消费者最大的不同是共享数据不会被取走所以共享资源不会减少甚至清空，因此多个读者可以同时访问共享数据。

问题分析

首先我们知道无论是写进程-写进程之间还是写进程-读进程之间都是互斥访问共享文件的。而读进程-读进程之间是不互斥的。所以我们首先肯定是需要设置一个互斥变量rw用来保证写-写，写-读之前互斥，同时为了记录此时正在有几个读进程执行我们设置一个参量count用来记录读进程个数，这样我们知道只有count==0时此时写进程才可以进行写操作，当count>0时说明还有读操作进行，每次新加入一个读进程count就++，每次退出一个读进程count–，只有count==0时说明此时没有读进程才能进行写操作。所以我们的代码如下：

首先声明一个互斥信号量和一个记录参量：

1
2
semaphore rw=1;//实现对共享文件的互斥访问
int count=0;//记录当前有几个进程在访问文件

那么写进程代码：

1
2
3
4
5
6
7
writer(){
    while(1){
        P(rw);//写之前“加锁”
        write....//进入共享区域进行写操作
        V(rw);//退出共享区域并“解锁”
    }
}

一个读进程

1
2
3
4
5
6
7
8
9
10
11
12
13
reader(){
    while(1){
        if(count==0){//如果是第一个读进程那么需要进行判断"上锁"
            P(rw);//"上锁"
        }
        count++;//读进程个数加一
        read....//进入共享区域进行读操作
        count--;//读完，退出读进程个数减一
        if(count==0){//如果是最后一个读进程那么退出前解锁
            V(rw);//"解锁"
        }
    }
}
思考：为什么对于读进程只有count==0时进行PV操作？

我们思考，rw实际上是一个用来使得写-写和写-读之间互斥的信号量，所以对于每一个写进程都需要进行P,V操作保证每次共享区域都只有自己一个写进程。而对于读者进程来说，如果他是第一个要进入共享区域的进程，那么他唯一需要做的就是保证此时共享区域里面没有写进程即可，即使里面已经有读进程了没关系因为他们之间不是互斥的。所以对于count!=的读进程来说他不需要进行P操作检验就可以直接进入共享区域因为此时说明共享区域里面有读进程且没有写进程，同理对于退出也是，只有自己是最后一个读进程退出时才需要解锁否则其他读进程直接退出即可。

思考：上面的代码有没有什么问题？

我们想一下，如果此时已经有一个读进程进入共享文件区域了，那么毫无疑问rw=0已经上锁了，此时如果又来了一个读进程我们知道由于count!=0他是不用经过P操作检查就可以直接进入共享区域的，但是我们现在就想对这个后来的读进程进行P操作检查，那么肯定他是通不过的，所以对于第一个if语句的作用除了要做到让第一个读进程上锁同时还要做到避免让其他后来的读进程被P操作检查因为一旦检查他们都是不可能进入的，但是现在上面的if语句操作代码有bug做不到第二个作用。原因如下：我们考虑现在有两个读进程在并发执行此时count==0，好巧不巧第一个读进程刚刚通过if(count==0)的检验还没来得及进行P上锁时间片用完了切换到了第二个读进程他也恰巧刚刚通过if(count==0)的检验也要进行P操作，此时说明这两个读进程都要进行P操作检查此时第二个进程的时间片也用完了有切换到了第一个进程第一个进程此时rw=1可以进入他通过了P操作检查并将rw设置为了0，此时他又用完时间片了切换到进程2PCB状态信息记录着他也要经过P检查，但是此时rw=0!完了第二个度进程是进不去的他过不了P进程的检查所以就一直阻塞到本轮所有的读进程结束才能进入。此时很明显是有问题的，if语句没有做到后来的读进程不用P操作检查。同理对于第二个if操作也会有问题，仔细想想就知道会造成最后一个进程还没有离开共享资源区，倒数第二个离开的进程就已经解锁了，这也很致命，所以我们需要对两个If语句进行优化。

思考：如何优化两个if语句？

分析易知此时会发生这种bug是因为此时的if判断语句和后面的操作语句不想P,V操作可以做到检查和操作一气呵成的原子性特点，所以我们需要借助P,V做到if语句判断和操作一气呵成，因此我们可以再设置一个互斥信号量来实现各读进程对count的访问是互斥的。所以优化后的代码如下：

我们需要再声明一个互斥信号量：

1
semaphore mutex=1;//用于保证对count变量的互斥访问

读进程的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
reader(){
	while(1){
        P(mutex);//对count访问上锁
        if(count==0){//如果是第一个读进程那么需要进行判断"上锁"
            P(rw);//"上锁"
        }
        count++;//访问的进程加一
        V(mutex);//对count访问解锁
        read...
        P(mutex);//对count访问上锁
        count--;//对count访问解锁
        if(count==0){//如果是最后一个读进程退出那么退出前需要解锁
            V(rw);//“解锁”
        } 
        V(mutex);//对count访问解锁
    }
}
思考：上面的代码还有什么问题？

我们再仔细想一想，貌似这种代码还是有一个缺陷，我们想每次中途都可以来新的读进程并且如果已知读进程个数不是0那么rw就一直不解锁，也就意味着只要有读进程正在读并且此时又来了新的读进程，那么写进程就得已知阻塞等到所有的读进程全部读完并且没有再来新的读进程，此时rw解锁后写进程才能继续写，这很容易就造成写进程饥饿（即已知有新的读进程源源不断的断断续续的来）。所以上面这种算法是读进程优先的，所以我们需要优化一下代码，即不允许读进程一直插队，当写进程正在等待前面的读进程时新来的读进程只能排在正在的写进程后面等待下一轮的读进程。所以事先代码如下，可能有点不太好理解：

首先还是需要声明信号量，此时还要在上面的基础上在新添加一个信号量w用于实现“写优先”如下：

这样上面加粗部分的就是新家的互斥信号锁，我们来分析以下为什么加上了这个信号量就避免了写进程饥饿。假设现在来了一个读进程R1，他将w上锁然后进行count++和rw上锁等功能，然后在解锁w,此时来了一个写进程W1，他可以通过w的P检验并上锁，此时他还不能通过rw的P操作，因为R1还没有解锁，此时W1在阻塞等待，此时又来了一个读进程R2如果按照上面原先的读者优先算法读进程可以立即进入共享区域执行读操作，但是此时他因为不能通过w的P操作（因为此时W1没有解w锁）所以R2也只能阻塞等待，当R1读完退出临界资源后将rw解锁此时W1可以进行写操作了，此时R2正在阻塞等待W1完成，只有当写进程完成并解锁w后R2才可以开始访问共享文件。我们发现从原来的R1-W1->R1-R2-W1变成了R1-W1->R1-W1-R2即读进程不能随意插队了也就是读写进程公平等待了避免了写进程饥饿的风险。

总结一下我们发现实际上上面这种算法并不是"写优先"算法，他只是做到了保证读进程和写进程公平排队而已。所以有的教材也把这种算法叫做"读写公平法"。

总结：各个信号量的作用？

我们一定要理解上面的代码衍生过程这样才可以深刻记忆各个信号量之间的作用。

  1. rw-保证写写，写读的互斥访问
  2. metux-保证读进程互斥访问count
  3. w-保证读写公平排队

十分注意count不是信号量他只是一个记录读进程数量的参量。

哲学家进餐问题

问题描述

一张圆桌上面坐着5名哲学家，每两个哲学家之间的桌子上摆着一个筷子，桌子的中间是一碗米饭，哲学家们倾注毕生精力用于思考和进餐，哲学家在思考时，并不影响他人，只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根拿起）。如果筷子已经在他人手上时，则需要等待。解饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

问题分析

从上面的描述中我们可以知道其实筷子就好像临界资源，每次都只允许一位哲学家进程访问，所以毋庸置疑这是互斥关系。5位哲学家与左右相邻对其中间的筷子是互斥访问的，但是这个不同于之前的生产者-消费者问题或者多生产者-多消费者问题亦或是吸烟者问题，此时一个进程需要同时访问两个临界资源。如何避免临界资源分配不当造成的死锁现象是哲学家问题的关键所在。

这里我们先设置互斥信号量，定义互斥信号量数组chopsticks[5]={1,1,1,1,1}（互斥信号量初始化为1）用于实现对5个筷子的互斥访问。并对哲学家按照0~4编号，同时哲学家i左边的筷子编号为i，右边的筷子编号为(i+1)%5。

思考：同时先左后右可取吗？

即每一个哲学家都是先尝试拿左边的筷子然后在尝试拿到右边的筷子，如果拿不到就放下筷子。此时代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
semaphore chopsticks[5]={1,1,1,1,1};

pi(){
    while(1){
        P(chopsticks[i])//拿左
        P(chopsticks[(i+1)%5])//拿右
        eat...
        V(chopsticks[i])//放左
        V(chopsticks[(i+1)%5])//放右
        think...
    }
}

很明显这种方法不妥当，会造成死锁最终谁也吃不上饭。因为当所有人都拿起左边的筷子时所有哲学家都不可能能拿到右边的筷子，所以所有哲学家最终都放下筷子重新再按照此方法尝试下去，最终谁也吃不上饭。这种循环等待右边的人放下筷子(阻塞)就是造成"死锁"的原因。

思考：加上某些条件可以避免死锁吗？

可以我们尝试每次都只限制至多4名哲学家同时吃饭，这样就会由5双筷子4个人分，至少保证了有一名哲学家可以吃饭，不会在造成死锁现象。但是貌似效率太低，究其原因是虽然某些哲学家不能吃上饭但是还是会拿起一根筷子占为己有进行尝试。即某些进程明明已经不可能访问到临界资源了却还是占用了一部分临界资源。我们最好能够避免不能立刻执行的进程占用临界资源。

思考：加上某些条件可以避免进程占用不必要的临界资源？

我们可以要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家正相反。这样可以保证当相邻的奇偶数号哲学家都想吃饭时，只会有一个哲学家获得第一个筷子，而另一名哲学家连第一个临街资源都没有获得就阻塞了，这样就避免了占有一支后再等待另一支的情况了。

思考：还有没有其他方法？

归根结底上面的方法都是在还没能确保能获得全部临界资源时就拿起了部分临界资源然后再尝试获取另一部分临界资源，这样就可能会造成大家都拿到了一部分临界资源然后等待。所以我们可以规定只有进程一次性可以获得全部临界资源才执行即仅当一个哲学家左右两支筷子都可以使用时才允许他抓起来。这种方法貌似最合适代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
semaphore chopsticks[5]={1,1,1,1,1};
semaphore mutex=1;//互斥的拿筷子

pi(){
    while(1){
        P(mutex);
        P(chopsticks[i])//拿左
        P(chopsticks[(i+1)%5])//拿右
        V(mutex);
        eat...
        V(chopsticks[i])//放左
        V(chopsticks[(i+1)%5])//放右
        think...
    }
}

我们对比之前的发现只是在取筷子时加上了互斥锁，这样各个哲学家拿筷子这件事必须是互斥进行的，这样就保证了即使一个哲学家在拿筷子时如果拿到一半被阻塞了，也不会有别的哲学家会继续尝试拿筷子，这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。我们发现这种方法虽然可以避免死锁，但是貌似和上面的思路不太一样，实际上他并没有真正的实现满足有两个筷子的哲学家尝试吃饭，而是保证了每次都只允许一名哲学家尝试拿筷子，如果他能一次性拿齐两双就吃饭如果拿不齐就阻塞等待，并且在他等待期间其他哲学家也禁止尝试拿筷子，必须等到这个阻塞的哲学家能够拿齐筷子吃饭后其他哲学家才可以尝试。这样的方法可以至少保证有一个哲学家能够进餐同时最好情况还可以有两名哲学家同时进餐。

思考：上面的方法有没有什么瑕疵？

我们发现上面这种方法并不能保证只有两边的筷子都可用湿才允许哲学家拿起筷子。例如：

此时1号哲学家已经尝试拿齐了右边筷子(2号筷子)，但是由于0号此时在吃饭所以1号筷子不能拿齐，所以此时1号哲学家不拿起筷子进入阻塞等待，而此时虽然2号哲学家可以同时拿齐2,3号筷子，但是由于mutex此时在1号筷子处为1，其他哲学家此时都不能拿筷子，所以2号哲学家此时虽然可以同时拿齐两双筷子但是却没有资格去尝试拿，而1号哲学家虽然不能用时拿齐两双筷子但是他却可以等待0号进程吃完然后拿齐1,2号筷子吃饭。

思考：三种方法哪种更好?

对于上面所说的三种方法：

  1. 每次最多允许4名哲学家拿筷子
  2. 奇偶号哲学家反方向拿筷子
  3. 互斥锁保证每次一个哲学家拿筷子(两个筷子都能拿才有资格拿筷子)

实际上没有好坏之分，都是最好情况为同时2名哲学家进餐，对于多个进程访问临界资源并且一个进程需要同时访问两个临界资源的变式题参考哲学家问题。

各种问题总结

问题类型

  1. 生产者-消费者问题：一个临界资源，两个进程互斥访问，互斥+同步关系
  2. 多生产者-多消费者问题：一个临界资源，多个进程互斥访问，互斥+同步关系
  3. 吸烟者问题：一个临界资源，一个生产者-多个消费者问题，互斥+同步关系
  4. 读者-写者问题:一个临界资源，部分进程互斥访问，互斥+同步关系同时有优先级问题
  5. 哲学家进餐问题：多个临界资源，进程需要两个临界资源，纯互斥关系
快来参与讨论吧