进程同步问题——生产者—消费者问题

问题梗概

生产者—消费者问题是相互合作关系的进程关系的一种抽象&＃xff0c;是一个广义的概念&＃xff0c;可以代表一类具有相同属性的进程

1. 生产者&＃xff1a;一个或者是多个生产者将生产的数据存入缓冲区中&＃xff0c;通过in指针操作。
2. 消费者&＃xff1a;从缓冲数据中取出数据&＃xff0c;通过out指针取出。
3. 缓冲区&＃xff1a;被消费者和生产者共享&＃xff0c;循环使用&＃xff0c;大小为n&＃xff08;存储单元的格数&＃xff09;
   图示&＃xff1a;
   
   1. 初始化缓冲区&＃xff0c;in和out指针指向缓冲区的同一存储单元
   2. 写入数据&＃xff0c;out指针后移&＃xff0c;指针之前的单元格为满
   3. 取出数据&＃xff0c;in指针后移&＃xff0c;指针之前的单元格为空

访问特征

互斥访问缓冲区——单一访问

生产者和消费者必须一访问临界资源的互斥方式&＃xff0c;访问缓存单元。在某一时间&＃xff0c;仅仅允许一个单一的对象进缓存区访问。生产者放&＃xff0c;消费者等待&＃xff1b;消费者取&＃xff0c;生产者等待&＃xff1b;

同步访问缓冲区——配合访问

生产者和消费者必须相互沟通。即生产者不可以想满的数据里面写入数据&＃xff0c;消费者不可以从空的缓冲区中取出数据。

• 生产者进入缓冲区&＃xff0c;申请空的存储单元&＃xff0c;没有则阻塞
• 消费者进入缓冲区&＃xff0c;申请满的存储单元&＃xff0c;没有则阻塞

访问方式总结

• 在互斥访问的基础上&＃xff0c;外包一个同步访问。
• 互斥信号量&＃xff0c;外套资源信号量。
• 唯一访问的方式&＃xff0c;外包一个配合访问的方式。

问题模拟

生产者的阻塞与唤醒

1. 生产一件商品&＃xff0c;检查缓冲区的个数&＃xff0c;如果已满&＃xff0c;进入阻塞
2. 否则将商品放入到缓冲区&＃xff0c;每放入一件计数器加1&＃xff0c;然后判断计数器的个数&＃xff0c;决定是否需要唤醒消费者

• 如果等于1&＃xff0c;说明在此之前缓冲区商品是0&＃xff0c;消费者见到零为空就去阻塞&＃xff0c;发出唤醒信号
• 不等于1&＃xff0c;说明等待区中还有消费者
• 图例

消费者的阻塞与唤醒

1. 先检查当前缓冲区的个数&＃xff0c;如果为空&＃xff0c;去阻塞
2. 否则&＃xff0c;进入缓冲区&＃xff0c;取走一件商品&＃xff0c;将商品计数器减一&＃xff0c;然后判断计数器的个数&＃xff0c;决定是否需要唤醒生产者

• 如果等于N - 1&＃xff08;N是缓冲区的容量&＃xff09;&＃xff0c;说明再去走之前是满的&＃xff0c;即之前的生产者会陷入阻塞&＃xff0c;需要叫醒
• 如果不等于&＃xff0c;则无需叫醒生产者。
• 图例

总的流程模拟

情景说明&＃xff0c;绿色的是资源所&＃xff0c;对应绿色的符号为资源锁的钥匙&＃xff0c;黄色的位互斥锁&＃xff0c;唤醒两个进程中所有的在互斥锁前等待的对象&＃xff0c;随机进入缓存区。

1. 初始化&＃xff0c;缓存区为空&＃xff0c;所有钥匙都在生产者进程上&＃xff0c;五个生产者&＃xff0c;仅仅四把钥匙&＃xff0c;一个在资源锁门口陷入阻塞。
   

2. 然后生产者开始带着钥匙开始写入数据&＃xff0c;out指针后移一位&＃xff0c;满存储单元数加一&＃xff0c;空存储单元数减一
   

3. 生产者2推出缓存区&＃xff0c;将将钥匙给所有互斥锁前面的阻塞进程&＃xff08;随机分的&＃xff09;&＃xff0c;消费者对应的互斥锁前面没有任何进程&＃xff0c;最终只能是生产者3&＃xff0c;进入缓存区&＃xff0c;继续写入out指针后移。
   

4. 生产者2将钥匙给消费者&＃xff0c;消费者得到资源锁钥匙&＃xff0c;来到互斥锁面前&＃xff0c;并且陷入阻塞。
   

5. 生产者3&＃xff0c;将钥匙送到消费者待机区&＃xff0c;生产者5随机进入缓存区&＃xff0c;写入数据out指针后移&＃xff0c;后将钥匙送到消费者对应的资源锁前面。
   

6. 生产者4&＃xff0c;又随机被唤醒&＃xff0c;解开互斥锁&＃xff0c;进入缓存区写入数据&＃xff0c;out指针后移&＃xff0c;将资源锁钥匙运到消费者资源锁前面。
   

7. 在所有存储单元都满了的情况下&＃xff0c;空存储单元数目为0&＃xff0c;满存储单元数为4&＃xff0c;消费者被唤醒&＃xff0c;进入缓存区&＃xff0c;拿走数据&＃xff0c;in指针后移。
   

8. 消费者和生产者双方都有了资源锁的钥匙&＃xff0c;然后就开始随机进行选择&＃xff0c;进入互斥锁的选择&＃xff0c;为正常情况。
   

总结

1. 资源锁的钥匙的数目就是缓存区存储单元的个数。
2. 生产者少了一把钥匙&＃xff0c;就意味着填满了一个存储单元&＃xff0c;消费者就多了一把钥匙。
3. 消费者少了一把钥匙&＃xff0c;就意味着清空了一个数据单元&＃xff0c;生产者就多了一把钥匙。
4. 通过上述的模拟&＃xff0c;不难看出仅仅只要对信号量机制的程序模板进行简单的修改就可以重复运用&＃xff0c;不需要设置特殊的情况。

伪代码实现

1. 采用信号量机制的模板&＃xff0c;修改S.value的表示方法

总结

1. 互斥信号量的P&＃xff0c;V操作在每一个程序中必须成对出现
2. 资源信号量&＃xff08;full&＃xff0c;empty&＃xff09;也必须成对出现&＃xff0c;但是可以处于不同的进程中
3. 多个P的顺序不能够颠倒
4. 上述问题是一个同步问题

• 消费者取商品&＃xff0c;有界缓冲区至少有一个单元是满的
• 生产者放商品&＃xff0c;有界缓冲区至少有一个是空的

5. 有界缓冲区是临界资源&＃xff0c;因此&＃xff0c;生产者进程和消费者进程必须是互斥执行