以下罗列一些在多道程序环境下，产生的一系列经典的进程同步问题。

生产者-消费者问题

问题描述

生产者-消费者(producer-consumer)问题是有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。在两者之间设置了一个具有 n 个缓冲区的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中，消费者进程可从一个缓冲区中取走产品去消费。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。

可以利用一个数组 buffer 来表示具有 n 个缓冲区的缓冲池，每投入或取出一个产品时，缓冲池 buffer 中暂存产品或或被取走产品的数组单元指针 in 或 out 需要移动，这些用代码描述如下。

int in  = 0;    //输入指针
int out = 0;    //输出指针
item buffer[n];    //缓冲区

由于 buffer 描述的缓冲池是循环队列结构，因此输入指针 in 或输出指针 out 表示成“in = (in + 1) % n” 和 “out = (out + 1) % n”，当 (in + 1) % n = out 时表示缓冲池满，in = out 则表示缓冲池空。

记录型信号量解法

可利用互斥信号 mutex 实现诸进程对缓冲池的互斥使用，利用信号量 empty 和 full 分别表示缓冲池中空缓区和满缓冲区的数量。

semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full  = 0;    //同步信号量，表示非空缓冲区的数量

又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者可将消息送入缓冲池。只要缓冲池未空，消费者便可从缓冲池中取走一个消息。应注意每个程序中用于实现互斥的 wait(mutex) 和 signal(mutex) 必须成对地出现，其次对资源信号量 empty 和 full 的 wait 和 signal 操作。
对生产者而言，可以用代码描述如下：

void proceducer(){
    do{
        producer an item nextp;    //生产一个产品
        wait(empty);    //消耗一个空闲缓冲区
        /*实现互斥*/
        wait(mutex);
        buffer[in] = nextp;    //产品放入缓冲区
        in = (in + 1) % n;    //移动输入指针
        signal(mutex);
        /*实现互斥*/
        signal(full);
    }while(TRUE)；
}

对消费者而言，可以用代码描述如下：

void consumer(){
    do{
        wait(full);    //消耗一个产品
        /*实现互斥*/
        wait(mutex);
        nextc = buffer[out];    //产品拿出缓冲区
        out = (out + 1) % n;    //移动输出指针
        signal(mutex);
        /*实现互斥*/
        signal(empty);    //增加一个空闲缓冲区
        consumer the item in nextc;    //使用产品
    }while(TRUE)；
}

整个生产消费者问题的流程，用代码描述如下：

void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

AND 信号量解法

利用 AND 信号量来解决时，用 Swait(empty，mutex) 来代替 wait(empty) 和 wait(mutex)，用 Ssignal(mutex, full) 来代替 signal(mutex) 和 signal(full)。用 Swait(full，mutex) 代替 wait(full) 和 wait(mutex)，以及用 Ssignal(mutex，empty) 代替 Signal(mutex) 和 Signal(empty)。利用 AND 信号量来解决生产者-消费者问题的代码描述如下：

int in  = 0;    //输入指针
int out = 0;    //输出指针
item buffer[n];    //缓冲区
semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
semaphore full  = 0;    //同步信号量，表示非空缓冲区的数量
void proceducer(){
    do{
        producer an item nextp;
        Swait(empty, mutex);
        buffer[in] = nextp;
        in = (in + 1) % n;
        Ssignal(mutex, full);
    }while(TRUE)；
}
void consumer(){
    do{
        Swait(full, mutex);
        nextc= buffer[out];
        out = (out + 1) % n;
        Ssignal(mutex, empty);
        consumer the item in nextc;
    }while(TRUE);
}
void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

管程解法

利用管程来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为 procducerconsumer(PC)。用整型变量 count 来表示在缓冲池中已有的产品数目，其中包括两个过程：

过程	说明
put(x)	生产者利用该过程将自己生产的产品投放到缓冲池中
get(x)	消费者利用该过程从缓冲池中取出一个产品

对于条件变量 notfull 和 notempty，分别有两个过程 cwait 和 csignal 对它们进行操作：

过程	说明
cwait(condition)	当管程被一个进程占用时，其他进程调用该过程时阻塞，并挂在条件 condition 的队列上
csignal(condition)	唤醒在 cwait 执行后阻塞在条件 condition 队列上的进程

PC 管程可描述如下：

Monitor procducerconsumer {
    int in  = 0;    //输入指针
    int out = 0;    //输出指针
    item buffer[n];    //缓冲区
    condition notfull, notempty;    //条件变量
    int count = 0;    //缓冲池中已有的产品数目
    public void put(item x){
        if(count >= N)    //缓冲池已满
        {
            cwait(notfull)；    //生产者等待
        }
        buffer[in] = x;
        in = (in + 1) % N;
        count++;
        csignal(notempty);
    }
    public void get(item x){
        if (count<= 0)    //缓冲池没有可用的产品
        {
            cwait(notempty)；    //消费者等待
        }
        x = buffer[out];
        out =(out+1) % N;
        count--;
        csignal(notfull);
   }
}PC;

在利用管程解决生产者-消费者问题时，可用代码描述为：

void producer(){
    item x;
    while(TRUE){
        produce an item in nextp;
        PC.put(x)；
    }
}
void consumer(){
    item x;
    while(TRUE){
        PC.get(x);
        consume the item in nextc;
    }
}
void main() {
    cobegin
        proceducer(); 
        consumer();
    coend
}

哲学家进餐问题

问题描述

一张圆桌上坐着 5 名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学家只做思考和进餐两件事情，哲学家在思考时不影响他人，只有当哲学家饥饿时才试图拿起左、右两根筷子(一根一根地拿起)。如果筷子已在他人手上则需等待，饥饿的哲学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

解法

经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。

semaphore chopstick[5] = {1,1,1,1,1};

所有信号量均被初始化为 1，当哲学家饥饿时总是先去拿他左边的筷子，成功后再去拿他右边的筷子便可进餐。进餐完毕时先放下他左边的筷子，然后再放他右边的筷子。

do{
    wait(chopstick[i]);              //拿起左边的筷子
    wait(chopstick[(i + 1) % 5]);    //拿起右边的筷子
    eat
    signal(chopstick[i]);              //放下左边的筷子
    signal(chopstick[(i + 1) % 5]);    //放下右边的筷子
    think
}while(TRUE);

除了利用记录型信号量，也可以使用 AND 型信号量来解决，这样的写法更为简洁。

do{
    Sswait(chopstick[(i + 1) % 5], chopstick[i]);    //拿起筷子
    eat
    Ssignal(chopstick[(i+1)%5],chopstick[i]);    //放下筷子
    think
}while(TRUE);

可能的死锁

假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量 chopstick 均为 0，当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。对于这样的死锁问题，可采取以下几种解决方法：

至多允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子；
仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。
奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子，而偶数号哲学家则相反。按此规定将是 1、2 号哲学家竞争 1 号筷子，3、4 号哲学家竞争 3 号筷子。即五位哲学家都先竞争奇数号筷子，获得后再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。

读者-写者问题

问题描述
有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用。但若某个 Writer 进程和其他进程(Reader 进程或 Writer 进程）同时访问共享数据时，则可能导致数据不一致的错误。因此要求：
允许多个 Reader 可以同时对文件执行读操作；
只允许一个 Writer 往文件中写信息；
任一 Writer 在完成写操作之前不允许其他 Reader 或 Writer 工作；
Writer 执行写操作前，应让已有的 Reader 者和 Writer 全部退出。

记录型信号量解法

为实现 Reader 与 Writer 进程间在读或写时的互斥，设置一个互斥信号量 Wmutex，再设置一个整型变量 Readcount 表示正在读的进程数目。又因为 Readcount 是一个可被多个 Reader 进程访问的临界资源，因此也应该为它设置一个互斥信号量 rmutex。

semaphore rmutex = 1;    //用于保证对 count 变量的互斥访问
semaphore wmutex = 1;    //用于实现对文件的互斥访问，表示当前是否有进程在访问共享文件
int readcount = 0;    //记录当前有几个读进程在访问文件

对 reader 而言，可以用代码描述如下：

void reader(){
    do{
        wait(rmutex)；    //reader 进程互斥访问 readcount
        if(readcount == 0)    //第一个 reader 进程开始读
        {
            wait(wmutex)；    //给共享文件“加锁”
        }
        readcount++;    //访问文件的 reader 进程数加 1
        signal(rmutex);
        perform read operation;    //读文件
        wait(rmutex)；    //各个 reader 进程互斥访问 readcount
        readcount--;    //访问文件的 reader 进程数减 1
        if(readcount == 0)
        {
            signal(wmutex);    //最后一个 reader 进程“解锁”
        }
        signal(rmutex);
    }while(TRUE);
}

对 Writer 而言，可以用代码描述如下：

void writer()
{
    do{
        wait(wmutex);    //写之前“加锁”
        perform write operation;
        signal(wmutex);    //写之后“解锁”
    }while(TRUE);
}

对于整个读者-写者问题过程，可以用代码描述如下：

void main() {
    cobegin
        reader();
        writer();
    coend
}

信号量集机制解法

此时读者一写者问题引入一个限制，最多只允许 RN 个读者同时读，为此又引入了一个信号量 L，并赋予其初值为 RN。通过执行 wait(L, 1, 1) 操作来控制读者的数目，每当有一个读者进入时，就要先执行 wait(L，1，1) 操作，使 L 的值减 1。当有 RN 个读者进入读后，L 便减为 0，第 RN + 1 个读者要进入读时，必然会因 wait(L，1，1) 操作失败而阻塞。

int RN;    //最多允许同时读取文件的 reader 进程数
semaphore L = RN；    //保证最多只有 RN 个 reader 进程同时读
semaphore mx = 1;    //标志是否有 writer 进程在操作文件 
void reader(){
    do{
        Swait(L, 1, 1);    //增加一个 reader 进程读文件
        Swait(mx, 1, 0);    //无 writer 进程写文件
        perform read operation;
        Ssignal(L, 1);    //减少一个正在读文件的 reader 进程
    }while(TRUE)；
}
void writer(){
    do{
        Swait(mx, 1, 1; L, RN, 0)    //无 reader 或 writer 进程在操作，“加锁”
        perform write operation;
        Ssignal(mx, 1);    //writer 进程“解锁”
    }while(TRUE);
}
void main(){
    cobegin
        reader();
        writer();
    coend
}

吸烟者问题

问题描述

假设一个系统有三个抽烟者进程和一个供应者进程，每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟需要有三种材料：烟草、纸和胶水。三个抽烟者中第一个拥有烟草，第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复。

解法

从事件的角度来分析，吸烟者问题有 4 个同步关系，分别是桌上有组合一时第一个抽烟者取走东西，桌上有组合二时第二个抽烟者取走东西，桌上有组合三时第三个抽烟者取走东西，最后是吸烟者发出完成信号，供应者将下一个组合放到桌上。因此需要设置 4 个信号量，来分别对应 4 个同步关系。

semaphore offerl = 0;    //桌上组合一的数量
semaphore offer2 = 0;    //桌上组合二的数量
semaphore offer3 = 0;    //桌上组合三的数量
semaphore finish = 0;    //抽烟是否完成
int i = 0;    //正在吸烟的吸烟者序号

对于材料提供者而言，可以用代码描述如下：

void provider(){
    while(1){
        if(i == 0){
            将组合一放桌上；
            wait(offer1);
        } 
        else if(i == l){
            将组合二放桌上；
            wait(offer2);
        } 
        else if(i == 2){
            将组合三放桌上；
            wait(offer3);
        }
        i = (i + 1) % 3;
        signal(finish);
    }
}

对于 3 位吸烟者，可以用代码描述如下：

void smoker1(){
    while(1){
        signal(offer1);
        从桌上拿走组合一，卷烟抽；
        wait(finish);
    }
}
void smoker2(){
    while(1){
        signal(offer2);
        从桌上拿走组合二，卷烟抽；
        wait(finish);
    }
}
void smoker3(){
    while(1){
        signal(offer3);
        从桌上拿走组合三，卷烟抽；
        wait(finish);
    }
}

参考资料

《计算机操作系统(第四版)》，汤小丹梁红兵哲凤屏汤子瀛编著，西安电子科技大学出版社

物联网工程专业知识学习

七，经典同步问题

生产者-消费者问题

问题描述

记录型信号量解法

AND 信号量解法

管程解法

哲学家进餐问题

问题描述

解法

可能的死锁

读者-写者问题

问题描述

记录型信号量解法

信号量集机制解法

吸烟者问题

问题描述

解法

参考资料