Producer-consumer problem using queues

10 Oct 2023

The producer-consumer problem is a classic synchronization problem in computer science. It involves two processes, the producer and the consumer, accessing a shared resource, often referred to as a buffer. The producer is responsible for adding items into the buffer while the consumer is responsible for consuming those items from the buffer. The challenge is to ensure that the producer does not add items to a full buffer and the consumer does not consume items from an empty buffer.

One common solution to this problem is by using queues. A queue is a data structure that follows the First-In-First-Out (FIFO) principle. In the context of the producer-consumer problem, the queue acts as the buffer.

Implementing the Queue

Before we can solve the producer-consumer problem using queues, let’s first implement a simple queue data structure. We’ll be using Python for this example.

class Queue:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.items.pop(0)

    def size(self):
        return len(self.items)

The Queue class has four methods:

is_empty(): Returns True if the queue is empty, False otherwise.
enqueue(item): Adds an item to the end of the queue.
dequeue(): Removes and returns the item at the front of the queue.
size(): Returns the number of items in the queue.

Solving the Producer-Consumer Problem

With the queue implementation in place, we can now solve the producer-consumer problem. Let’s assume that we have two processes, the producer and the consumer, that will run concurrently. To ensure synchronization, we’ll be using a mutex (a binary semaphore) and a full/empty semaphore.

import threading

queue = Queue()
mutex = threading.Semaphore(1)
full = threading.Semaphore(0)
empty = threading.Semaphore(10)

def producer():
    while True:
        item = produce_item()
        empty.acquire()
        mutex.acquire()
        queue.enqueue(item)
        mutex.release()
        full.release()

def consumer():
    while True:
        full.acquire()
        mutex.acquire()
        item = queue.dequeue()
        mutex.release()
        empty.release()
        consume_item(item)

# Start producer and consumer threads
producer_thread = threading.Thread(target=producer)
consumer_thread = threading.Thread(target=consumer)

producer_thread.start()
consumer_thread.start()

In this solution, the producer function continuously produces items, adds them to the queue, and releases the full semaphore to signal the consumer that there is an item in the queue. The consumer function waits for the full semaphore, dequeues an item from the queue, consumes it, and releases the empty semaphore to signal the producer that there is an empty slot in the queue.

The mutex semaphore ensures that only one process can access the queue at a time, preventing race conditions.

Conclusion

By using queues and semaphores, we can effectively solve the producer-consumer problem and achieve synchronization between processes. The queue acts as a buffer between the producer and the consumer, ensuring that the producer does not add items to a full buffer and the consumer does not consume items from an empty buffer.