经典进程同步问题

| | |
一、生产者-消费者问题
问题描述：

生产者生产产品到仓库（缓冲区），消费者从缓冲区获取产品，由于进程的异步性，对共享资源（缓冲区）访问是不可控的，因此我们把缓冲区作为临界资源，所以生产者、消费者和临界资源三者是一种互斥的制约关系。同时，消费者也需要等到生产者生产产品才能获取，因此这也是一个同步问题。

1、使用记录型信号量解决

记录性信号量主要是在整型信号量的基础上增加了用于记录等待进程的链表。由问题描述知我们需要解决同步和互斥两个问题。因此设置n为临界资源数量，构建数组存储资源，只有n>0才能存入生产的产品，消费者也才能获取产品。使用mutex作为互斥信号量。

代码描述如下：

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
int in = 0, out = 0;
item[n] buffer;
semaphore mutex = 1, empty = n, full = 0;
void producer() {
    do {
        producer anitem 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;
    }Wwhile(TRUE);
}

解释：mutex作为互斥信号量，empty作为临界资源数量，full表示可用产品数量。producer函数中使用signal(full)表示对消费者可用数量的增加，以便消费者的wait(full)可继续运行，以此保证了同步。

注意的是：wait和signal是成对出现的，而mutex初始值为1，以保证互斥访问。并且，同步层是在互斥层“外”的，顺序不能变。

为什么同步层是外层，而互斥层是内层？

现假设互斥层为外层，同步层为内层。当生产者生产产品进入缓冲区，即调用wait(mutex)，此时锁定了临界资源以实现互斥，继续调用wait(empty)，若empty=0，那么将引起阻塞，临界资源将不可更改。此时的状态是：producer等着consumer将产品消费(signal(empty))，而consumer等着producer将占着的临界资源释放(即signal(mutex))，于是开始循环等待，形成了死锁。因此必须保证同步在外层，互斥在内层。

2、使用AND信号量解决

主要使用AND信号量的特性一次性解决生产者-消费者问题的同步性和互斥行。AND信号量特性是一次性把所有临界资源分配给一个进程（要么拥有全部，要么一个也不能拥有）。即为用Swait(empty, mutex)替代wait(empty)和wait(mutex)，用Ssignal(mutex, full)替代signal(mutex)和signal(full)。consumer中也是如此。