生产者与消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品就放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用（这里的产品可能是某种数据）

生产者和消费者共享一个初始为空，大小为n的缓冲区

  • 只有缓冲区没满时，生产者才能将产品放入缓冲区，否则必须等待
  • 只有缓冲区不空时，消费者才能从缓冲区取出产品，否则必须等待
  • 缓冲区是临界资源，各进程必须互斥访问

PV操作题目常见方法

信号量机制可以实现互斥，同步以及对一类资源的申请和释放

  • 互斥：一般会设置初值为1的互斥信号量
  • 同步：设置初值为0的同步信号量（实现一前一后）
  • 资源的释放和申请：设置一个信号量，初始值即为资源数量（本质还是进程同步）

PV操作题目分析步骤

  1. 关系分析，找出题目中描述的各个进程，分析它们之间的同步互斥关系
    • 本题中，涉及以下几种进程同步，互斥关系
    • 互斥关系：对于临界区的访问，必须互斥进行
    • 同步关系：缓冲区满，生产者必须开始等待，直到消费者取走产品
    • 同步关系：缓冲区空，消费者必须开始等待，直到生产者放入产品
  2. 整理思路，根据各进程的操作流程确定P，V操作的大致顺序
    • 生产者每次要消耗一个空闲缓冲区（P）并生产一个产品（V）
    • 消费者每次要消耗一个产品（P）并释放一个空闲缓冲区（V）
    • 往缓冲区收入/取走产品需要互斥
  3. 设置信号量，根据上文内容确定所需的信号量，并根据题目条件确定信号量初值
    • 互斥信号量一般为1
    • 同步信号量一般为资源初始值

解题

根据上文所述，我们需要三个信号量来解决本问题

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
27
28
semaphore mutex=1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty=n; // 同步信号量，表示空闲缓冲区的数量
semaphore full=0; // 同步信号量，表示产品数量，也即非空闲缓冲区的数量

//生产者
producer (){
    // 执行循环
    while(1){
        生产一个产品
        P(empty); // 消耗一个空闲缓冲区
        P(mutex); // 对缓冲区上锁
        把产品放入缓冲区;
        V(mutex); //对缓冲区解锁
        V(full); //增加一个产品数量
    }
}

//消费者
consumer (){
    while(1){
        P(full); //消耗一个产品
        P(mutex); //对缓冲区上锁
        从缓冲区取出一个产品;
        V(mutex); //释放缓冲区
        V(empty); //增加一个空闲缓冲区数量
        使用产品;
    }
}

在这个过程中相邻的两个P操作不能交换位置，例如，若将生产者中相邻的两个P操作交换位置

1
2
3
4
5
6
7
8
9
10
11
12
//生产者
producer (){
    // 执行循环
    while(1){
        生产一个产品
        P(mutex); // 对缓冲区上锁
        P(empty); // 消耗一个空闲缓冲区
        把产品放入缓冲区;
        V(mutex); //对缓冲区解锁
        V(full); //增加一个产品数量
    }
}

假设此时empty=0,full=n即缓冲区中没有空闲位置，则生产者进程执行

  1. 使mutex变为0
  2. 由于没有空闲缓冲区，所以生产者被阻塞
  3. 消费者进程执行，由于mutex=0，即生产者还没有释放临界资源的“锁”，所以消费者也被阻塞
  4. 生产者等待消费者释放空闲缓冲区，消费者等待生产者释放临界区资源
  5. 造成死锁

同理，若调换消费者相邻P操作的位置，在full=0,empty=n时也会造成死锁

因此，实现互斥的P操作一定要放在实现同步的P操作之后

V操作不会导致进程阻塞，因此相邻V操作的位置可换

多生产者多消费者问题-放取水果问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

  1. 关系分析，找出题目中各个进程以及它们之间的同步互斥关系
    • 可以看到，这个题目中父亲和母亲相当于两个生产者进程，女儿和儿子相当于两个消费者进程
    • 只不过要注意这里的两个生产者生产物品不同，消费者消费的物品也不同
  2. 整理思路，根据各个进程的操作流程确定PV操作大致顺序
    • 互斥操作要在在临界区前后分别PV，同步操作要前V后P
    • 互斥关系：对缓冲区（盘子）的访问要互斥进行
    • 同步关系：父亲将苹果放入盘子，女儿才可以取苹果
    • 同步关系：母亲将橘子放入盘子，儿子才可以取橘子
    • 同步关系：只有盘子为空时，父亲或母亲才能放入水果
  3. 设置信号量（互斥信号量一般为1，同步信号量初值取决于资源初始书目）

示例

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
semaphore mutex=1; //实现互斥访问临界区（盘子）
semaphore apple=0; //盘子中有几个苹果
semaphore orange=0; //盘子中有几个橘子
semaphore plate=1; //盘子中还可以放几个水果

// 父亲进程
dad(){
    while(1){
        准备一个苹果;
        P(plate);  //等待一个盘子位置
        P(mutex);  //临界区上锁
        把苹果放入盘子;
        V(mutex); //临界区解锁
        V(apple); //释放苹果资源（苹果数加一，同时唤醒女儿进程执行）
    }
}

//母亲进程
mom(){
    while(1){
        准备一个橘子;
        P(plate);  //等待一个盘子位置
        P(mutex);  //临界区上锁
        把橘子放入盘子;
        V(mutex); //临界区解锁
        V(orange); //释放橘子资源（橘子数加一，同时唤醒儿子进程执行）
    }
}

//女儿进程
daughter(){
    while(1){
        P(apple); //等待苹果资源
        P(mutex); //临界区上锁
        从盘中取出苹果;
        V(mutex); //临界区解锁
        V(plate); //已经取出了苹果，所以释放盘子资源
        吃掉苹果;
    }
}

//儿子进程
son(){
    while(1){
        P(orange); //等待橘子资源
        P(mutex); //临界区上锁
        从盘中取出橘子;
        V(mutex); //临界区解锁
        V(plate); //已经取出了橘子，所以释放盘子资源
        吃掉橘子;
    }
}