【Operating System】进程 - 生产者消费者问题(Producer-consumer Problem)

Posted by 西维蜀黍 on 2021-07-30, Last Modified on 2021-09-21

生产者-消费者问题(The Producer-Consumer Problem)

也称为有界缓冲区问题(Bounded-buffer Problem)。

In the producer–consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N and are subject to the following conditions:

  • the consumer must wait for the producer to produce something if the queue is empty;
  • the producer must wait for the consumer to consume something if the queue is full.

The semaphore solution to the producer–consumer problem tracks the state of the queue with two semaphores: emptyCount, the number of empty places in the queue, and fullCount, the number of elements in the queue. To maintain integrity, emptyCount may be lower (but never higher) than the actual number of empty places in the queue, and fullCount may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphores emptyCount and fullCount maintain control over these resources.

The binary semaphore useQueue ensures that the integrity of the state of the queue itself is not compromised, for example by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively a mutex could be used in place of the binary semaphore.

Solution

生产者-消费者问题是利用 Sleep and Wakeup 方案提供进程间互斥(Mutual Exclusion)的一个具体实例。

两个进程共享一个大小固定的缓冲区,其中的一个进程(称为生产者),将信息放入缓冲区中;而另一个进程(称为消费者),将信息从缓冲区中取出。

事实上,包含 m 个生产者和 n 个消费者是完全有可能的,只是我们通过最小化数量突出解决方案模型本身。

当缓冲区满时,生产者进行休眠,直到有任何消费者从缓冲区中移除内容时而被唤醒;当缓冲区为空时,消费者进行休眠,直到有生产者将内容放入缓冲区时而被唤醒。

Golang Solution

Refer to https://swsmile.info/post/golang-producerconsumer-problem/

Reference