经典进程同步与互斥问题

经典进程同步与互斥问题

1. 生产者－消费者问题

1.1 简单的“生产者-消费者”问题

设进程A、B是两个相互合作的进程，它们共享一个缓冲区，进程A向其中写入数据，进程B从中读出数据。producer：生产者进程，consumer：消费者进程。当缓冲区不空时，消费者便可以读数据；当缓冲区为空时，生产者便可以写数据。

设置信号量：
full：表示有数据缓冲区的数目，初值为0；
empty：表示空缓冲区的数目，初值为1；

生产者：

do  {
    //   produce an item
    wait (empty);
    //  add the item to the  buffer
    signal (full);
} while (TRUE);

消费者：

do {
    wait (full);    
    //  remove an item from  buffer
    signal (empty);
    //  consume the item
} while (TRUE);

1.2 复杂的““生产者-消费者”问题”

特点：
1. 若干进程通过有限的共享缓冲池交换数据。
2. 一组“生产者”进程不断写入，而一组“消费者”进程不断读出；
3. 任何时刻只能有一个进程可对共享缓冲池进行操作

分析：
1. 消费者取数据时，缓冲池至少有一个有数据的缓冲区
2. 生产者发送数据时，缓冲池至少有一个空缓冲区
3. 缓冲池是临界资源，各个生产者和消费者之间必须互斥访问

设置信号量：
empty ：表示空缓冲区个数，初值为n；
full ：表示有数据的缓冲区个数，初值为0；
mutex ：用来控制互斥的访问缓冲区，初值为1；

生产者：

do  {      
    //   produce an item
    wait (empty);   
    wait(mutex);
    //  add the item to the  buffer
    signal(mutex);
    signal (full);
} while (TRUE);

消费者：

do {
        wait (full);
        wait(mutex);
        //  remove an item from  buffer
        signal(mutex); 
        signal (empty);
       //  consume the item
} while (TRUE);

在生产者—消费者问题中，不能将生产者进程的wait(empty)和wait(mutex)语句互换。因为生产者若是先拿到了mutex锁，然后发现没有空缓冲区，那么就会一直等待，同时一直拿着mutex锁。要注意到，mutex锁是生产者和消费者共享的，此时生产者拿着锁一直等待消费者消费，而消费者一直拿不到mutex锁，则会造成死锁。

2. 读者－写者问题

一些进程只读数据，称“读者”；另一些会对数据进行修改，称“写者”。写者与写者互斥，写者与读者互斥；读者之间不互斥。

对于写进程而言：
1. 一定是互斥访问。要保证写者和读者互斥，以及写者和写者互斥。

对于读进程而言：
1. 如果是第1个读者，要实现与写者的互斥；如果是后继读者，则不需要。
2. 如果是最后一个读者，需要考虑唤醒阻塞的写者，以便能够让写者有机会进入临界区。

设置信号量：
wmutex ：控制写者互斥的访问共享数据，初值为1；
readcount ：读者计数器，记录当前读者数，初值为0；
rmutex ：控制读者互斥访问readcount，初值为1；

二者流程图如下：

写进程：

do {
    wait (wmutex) ;
    //    writing is performed
    signal (wmutex) ;
} while (TRUE);

读进程：

do {
    wait (rmutex) ;
    readcount ++ ;
    if (readcount == 1)  
    wait (wmutex) ;
    signal (rmutex)

    // reading is performed     //注意这里特意空出来的原因

    wait (rmutex) ;
    readcount  - - ;
    if (readcount  == 0)  
    signal (wmutex) ;
    signal (rmutex) ;
} while (TRUE);

在读进程读的过程中，只需保证在对读者数量变化时是互斥即可。

3. 哲学家进餐问题

假设5个哲学家围绕一张圆桌而坐，桌上放着5根筷子，哲学家进餐时需要同时拿起他左边和右边的两根筷子。

思路一：
1. 对于每一个哲学家，先等待左边的筷子可用，然后等待右边的筷子可用
2. 吃饭
3. 放下两根筷子

do  { 
    wait ( chopstick[i] );
    wait ( chopStick[ (i + 1) % 5] );
    //  eat
    signal ( chopstick[i] );
    signal (chopstick[ (i + 1) % 5] );
    //  think
} while (TRUE);

这样势必会导致一个问题：在极端情况下，5个哲学家同时拿起左边的筷子，那么势必会造成每个人都只有左筷子而没有右筷子，每个人都在等待右筷子。造成死锁现象。

解决死锁问题的方法：
方法一：同时最多允许四个哲学家围坐在桌子周围。
方法二：只有在哲学家两侧的筷子都可用时才允许她捡起筷子。

思路二：
对于每一个哲学家，要求同时拿起两根筷子，要么一根都不拿。

do  { 
    Swait ( chopStick[ (i + 1) % 5], chopstick[i] );
    //  eat
    Ssignal (chopstick[ (i + 1) % 5], chopstick[i] );
    //  think
} while (TRUE);