经典同步问题

生产者——消费者问题

生产者——消费者问题是一个经典的同步问题，生产者生成的数量存在一个上限，不能生成超出这个上限。消费者不能消费未生产的东西。假设如下：mutex信号量是生产者和消费者共享缓冲区的互斥要求，缓冲区的大小为n。设缓冲区空用empty表示，并初始化为1，设缓冲区满为full，并初始化为0。那么生产者进程和消费者进程如下：

生产者进程：

代码语言：javascript复制

do
{
    ...
    produce
    ...
    wait(empty);
    wait(mutex);
    ...
    signal(mutex);
    signal(full);

}while(1);

消费者进程：

代码语言：javascript复制

do
{
    wait(full);
    wait(mutex);
    ...
    remove
    ...
    signal(mutex);
    signal(empty);
    ...
}while(1);

假设消费者进程先执行，那么由于full初始化为0，经过wait操作。必将引起进程忙等待。（此处假设了full为整数，那么wait函数就是经典意义下的）。那么消费者进程在等待生产者进程。生产者进程即将退出临界区的时候signal(full)和signal(mutex)。这样full不在是0，而是变成了1，那么引起消费者进程不在等待，（当然当消费之进程执行了wait操作之后，full还是变成了0.）。在消费者进程退出临界区之前执行了signal(mutex)和signal(empty)；这样使得生成者能继续执行。signal(mutex)和wait(mutex)是解决进程互斥的信号量，这两个操作在消费者进程和生产者进程都必须执行，以保证同一时刻只有一个进程访问公共资源。

上述的生产者——消费者模型两个进程都会去修改缓冲区的内容。另外一个例子是读者——作者问题，其中读者只读取内容，而不修改内容，而作者肯定能写入内容，可能会读取内容。由于读取并不改变共享的数据对象，那么同时读取并不会产生什么错误，关键在于写入的时候。

读者——作者问题

一个数据对象可以为多个并发进程所共享，其中一部分进程只需要读取，也只能读取，另外一部分进程能写入，也许也能读取。我们将只能读取的称之为“读者”，其他的称为“作者”。

最为简单的读者——作者问题是：第一读者——作者问题，要求没有读者需要等待，除非有一个作者已经获得了使用这个共享数据对象的权利。他们共享以下的数据结构：

代码语言：javascript复制

semaphore mutex,wrt;
int readcount;

readconut表示当前有多少个进程正在读共享对象，mutex用于确保更新readcount时的互斥。wrt为作者之间的互斥，同时它还作为第一个进入临界区的读者和最后一个离开临界区的读者所使用。mutex和wrt初始化为1，readcount初始化为0.

作者进程如下：

代码语言：javascript复制

wait(wrt);
...
write;
...
signal(wrt);

读者进程如下：

代码语言：javascript复制

wait(mutex);
readcount  ;
if(1 == readcount)  //为第一个读者所用
{
    wait(wrt);      //不让作者写了
}
signal(mutex);      //可以让其他读者读了
...
read;
...
wait(mutex);        //读完了
readcount--；       //读者数量减1

if (0 == readcount)
{
    signal(wrt);    //最后一个离开后，作者就可以写了
}
signal(metux);      //为读者做准备

在第一读者——作者这个问题之中，作者可能出现饥饿（starvation），即进程在信号量内无穷等待。因为如果读者一直在读，那么作者根本就没有写的机会。作者只能等待。

哲学家进餐问题

假设有5个哲学家，他们的一生只在思考和吃饭之中度过。这些哲学家共用一个圆桌，每个哲学家都有一把椅子。在圆桌上有5个碗和5个筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，哲学家进餐完毕，放下筷子又继续思考。

哲学家进餐问题是在多个进程之间分配多个资源而且不会出现死锁和饥饿形式的简单表示。

一个简单的解决方法是每只筷子都用一个信号量来表示。哲学家通过对信号量执行wait操作试图取得相应的筷子来吃饭，吃完饭以后执行signal操作来放下筷子。因此共享的数据结构是：semaphore chopstick5;并将数组元素初始化为1.那么第i个哲学家如下：

代码语言：javascript复制

do
{
    wait(chopstick[i]);         //如果自己的筷子被别人拿走了，必须等待别人吃完饭，还给你筷子
    wait(chopstick[(i 1)%5]);   //试图拿跟他挨着的人的筷子
    ...
    eat；
    ...
    signal(chopstick[i]);
    signal(chopstick[(i 1)%5]);
    ...
    think;
    ...
} while (1);

这个方案保证没有相邻的哲学家在同时进餐。因此显而易见的是他可能引起的死锁情形是5个哲学家同时变得饥饿，那么他们将要吃饭。这个时候所有的哲学家拿起了自己的筷子。同时试图去拿起跟他相邻的人的筷子，但是这时没有一个哲学家能拿到第二根筷子，那么所有哲学家都在等待另一只筷子，他们将被饿死。

如果还是上面的哲学家结构，那么解决办法可以是：

圆桌上最多只能有4个哲学家，那么必将有一个座位没有人，他的筷子会被相邻的哲学家拿到。
只有两只筷子都可用时才允许哲学家吃饭。（必须在临界区内有两只可用的筷子）
奇数哲学家先拿起他左边的筷子，接着拿起他右边的筷子，而偶数哲学家则先拿起右边的筷子，接着拿起左边的筷子

有关哲学家进餐问题的任何满意的解答方案必须保证没有一个哲学家会被饿死。

mutex wait 进程

0 人点赞