进程同步与互斥——PV信号量操作专题

前言

进程同步与互斥的设计题在考试中分数占比较重（15分），但是题目难度较其它题来说个人认为更大。题目大多以经典的同步互斥问题为框架，换汤不换药地进行出题，所以如果对经典地几个同步互斥题熟练掌握，再对于题目加以剖析，这类题就会显得更为套路了。

几个经典的同步与互斥问题

1. 生产者-消费者问题

题目设定为，存在一个缓冲区，生产者每次可以生产一个产品加入缓冲区，而消费者每次可以从缓冲区中取出一个产品进行消费，生产者消费者不能同时对缓冲区进行操作，缓冲区可能有上限，如果存在上限，则当缓冲区满时生产者无法将产品加入缓冲区，需要等待缓冲区存在空位才能将产品放入。如果缓冲区目前没有产品，消费者就需要等待缓冲区中存在产品后再进行消费。

N空位

semaphore mutex = 1; // 缓冲区保护
semaphore full = 0; // 缓冲区产品数
semaphore empty = N; // 缓冲区空位数

process producer {
    P(empty);
    P(mutex);
    V(full);
    V(mutex);
}

process comsumer {
    P(full);
    P(mutex);
    V(empty);
    V(mutex);
}

理发师问题

理发师问题本身可以用生产者消费者模型刻画。题面如下：

理发店有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子。如果没有顾客，则理发师便在理发椅上睡觉，当一个顾客到来时，他必须先叫醒理发师，如果理发师正在理发时又有顾客到来，则如果有空椅子可坐，他们就坐下来等。如果没有空椅子，他就离开。

这个题面第一次看会觉得有点陌生，下面分析一下题面。

理发店有一位理发师（消费者），一把理发椅和N把供等候理发的顾客坐的椅子（缓冲区）。如果没有顾客（产品），则理发师便在理发椅上睡觉（等待产品），当一个顾客到来时（生产者生产了一个产品），他必须先叫醒理发师，如果理发师正在理发（消费产品）时又有顾客到来（产品被生产出来），则如果有空椅子可坐（缓冲区有空位），他们就坐下来等。如果没有空椅子（缓冲区无空位），他就离开（不等待）。

再剖析地更直接点就是

存在一个缓冲区，生产者每次可以生产一个产品加入缓冲区，而存在一个消费者每次可以从缓冲区中取出一个产品进行消费，生产者消费者不能同时对缓冲区进行操作，缓冲区只能存放N个产品，则当缓冲区满时生产者无法将产品加入缓冲区，直接放弃该产品。如果缓冲区目前没有产品，消费者就会等待缓冲区中存在产品后再进行消费，一旦存在产品，消费者就会开始进行消费。

其中

生产者：使得顾客进来的机制本身
产品：顾客
消费者：理发师
缓冲区：等待椅
消费：理发
等待：理发师睡觉

这个生产者-消费者模型与之前相比，最大的不同在于生产者不会进行等待，会直接结束进程，所以这里对于空位资源不能使用信号量机制，它不是进程执行必须的资源，而是判断的条件。于此同时，这里的消费者只有一个，但是是会不断进行消费的，生产者生产出的产品存在被消费的动作。

对于这道题的生产者-消费者模型，代码如下

semaphore full = 0; // 产品数
semaphore mutex = 1; // 保护缓冲区
semaphore signal = 0; // 唤醒生产者
int empty = N; // 空位数

process comsumer {
    while (true) {
        P(full);
        P(mutex);
        empty++;
        V(signal);
        V(mutex);
        消费
    }
}

process producer {
    P(mutex);
    if (empty == 0) {
        V(mutex);
    } else {
        empty--;
        V(mutex);
        V(full);
        P(signal);
        被消费
    }
}

翻译成理发店问题就是

semaphore customer = 0; // 等待的顾客数
semaphore mutex = 1; // 保护等待椅
semaphore barber = 0; // 理发师是否可用
int chair = N; // 空椅数

process barber {
    while (true) {
        P(customer);
        P(mutex);
        chair++;
        V(barber);
        V(mutex);
        理发
    }
}

process producer {
    P(mutex);
    if (chair == 0) {
        V(mutex);
    } else {
        chair--;
        V(mutex);
        V(customer);
        P(barber);
        被理发
    }
}

仓库问题

1个仓库最多可以容纳30件产品（不分产品类型），每次只允许一个产品进出仓库。甲乙两个车间分别生产A、B两种产品并共用上述仓库。如果仓库满了，则不能进行新的生产。有3个需要A产品的客户和3个需要B产品的客户，分别从仓库提取A、B产品。请用P、V操作来实现上述甲、乙车间以及A、B产品的客户之间的同步与互斥关系。给出伪代码描述，并添加尽量详细的注释，说明使用的信号量含义，以及主要代码含义。

一样进行问题的分析

1个仓库（缓冲区）最多可以容纳30件产品（不分产品类型）（缓冲区容量30），每次只允许一个产品进出仓库（操作互斥）。甲乙两个车间（两个生产者）分别生产A、B两种产品（两种产品）并共用上述仓库（使用同一个缓冲区）。如果仓库满了（缓冲区满），则不能进行新的生产（需要等待）。有3个需要A产品的客户（消费者类1）和3个需要B产品的客户（消费者类2），分别从仓库提取A、B产品（消费产品）。

翻译为生产者-消费者模型

1个缓冲区最多可以容纳30件产品（不分产品类型），每次只允许一个产品进出缓冲区。有两个生产者分别生产A、B两种产品并共用一个缓冲区。如果缓冲区满，则不能进行新的生产，需要等待缓冲区存在空位。有3个需要A产品的消费者和3个需要B产品的消费者，分别从缓冲区消费A、B产品。

其中，生产者说明了数量为2，生产两种不同商品，且每个生产者是需要多次进行生产的，消费者也指明了数量为6，3个消费A产品，3个消费B产品。产品种类是本题最大的不同点。