Solutions to the Producers-Consumers Problem

With the Readers-Writers problem out of the way, let’s talk about another synchronization problem: Producers-Consumers.

Producers-Consumers Problem Overview

Unlike Reader and Writers, Producers and Consumers do not compete over resources. Instead, they rely on each other to balance some shared resource. For instance, Producers might be creating messages that are added to a queue, and Consumers are responsible for processing those messages.

More formally, Producers and Consumers share a queue. When the queue contains items, one and only one Consumer should claim the first item for processing. Specifically, we don’t want multiple Consumers processing the same item. Likewise, as long as the queue is not full, Producers can add items to the queue.

Also unlike the Readers-Writers problem, the Producers-Consumers problem doesn’t really have any permutations. Since there isn’t any competing for resources, there’s no need to give priority to any processes. As a result, we only have to go through one solution for each synchronization mechanism. In the future, we’ll go through some more complicated Producer-Consumer problems (i.e. reusable resources, etc.).

In this article, we’ll take a look at two solutions to the Producers-Consumers problem: one with semaphores and one with monitors. As always, examples are borrowed from The Ohio State University’s CSE 6431 lecture notes:

• OSU CSE 6431 Process Synchronization Part 2 (Semaphores)
• OSU CSE 6431 Process Synchronization Part 3 (Semaphores)
• OSU CSE 6431 Process Synchronization Part 4 (Monitors)

Of course, all analysis is strictly my own.

Producers-Consumers Problem Solutions

In this section, we’ll implement a couple solutions to the Producers-Consumers problem. In particular, we’ll be looking at the semaphore solution and contrasting it with the monitor solution. Once again, I’ll be using pseudocode that mimics Python.

Semaphores

In order to implement this solution, we’ll need three semaphores: mutex, prod_mutex, cons_mutex. In other words, we’ll need a binary semaphore to globally protect the queue and a handful of shared variables. In addition, we’ll need a pair of counting semaphores to ensure mutual exclusion between the sets of the same processes. Incidentally, the additional mutexes are useful for communication between Consumers and Producers.

On top of that, we’ll need to introduce a few shared variables like count which is the number of elements in the queue and SIZE which is a constant for the max size of the queue.

procedure producer(): 
  P(mutex) 
  if count = SIZE: 
    V(mutex) 
    P(prod_mutex) 
    P(mutex) 
  else: 
    P(prod_mutex) 
  count++ 
  # Add item to queue 
  V(cons_mutex) 
  V(mutex)

procedure consumer(): 
  P(mutex) 
  if count = 0: 
    V(mutex) 
    P(cons_mutex) 
    P(mutex) 
  else: 
    P(cons_mutex) 
  count-- 
  # Remove item from queue 
  V(prod_mutex) 
  V(mutex)

As we can see, only one process can ever be running at a time except under special conditions described below. In the case of a Producer, it’s going to check if there is room in the queue. If there is, it’s going to try to acquire the prod_mutex, produce an item, and increment count. Otherwise, it’s going to release the mutex and wait until there is room in the queue. When everything is said and done, the Producer lets any waiting Consumers know that there is at least one item waiting in the queue.

Meanwhile, the Consumer is going to check if there is anything in the queue. If there is, it tries to acquire the cons_mutex, consume an item, and decrement count. Otherwise, it’s going to release the mutex and wait until there is something in the queue. When everything is said and done, the Consumer lets any waiting Producers know that there is at least one vacant space in the queue.

Notice how these two processes perfectly mirror each other. As a result, you should be asking a followup question: is this solution deadlock prone? In fact, that’s a question I asked myself. Is it possible that a Producer grabs the mutex while another Producer has the prod_mutex? After all, a Producer needs both to produce.

Here is the scenario I’m imagining. Let’s say the shared queue is full, and a new Producer (P1) comes along. At that point, P1 will inevitably find itself stuck on the prod_mutex queue. At that point, a new Consumer (C1) shows up. About halfway through its job, another Producer shows up (P2). As C1 finishes, it hands off the prod_mutex to P1 while also handing off the mutex to P2. We’re now deadlocked.

As it turns out, the solution I’ve provided only works for a single Consumer and a single Producer.

Monitors

As is often the case, the monitor solution is typically a lot easier to implement. In general, we just need to define a shared queue as well as a shared count variable. In addition, we’ll need to maintain two condition variables similar to the counting semaphores: can_consume and can_produce. Finally, we’ll define two procedures: producer and consumer.

procedure producer(): 
  if count = SIZE: 
    can_produce.wait 
  count++ 
  # Add item to queue 
  can_consume.signal

procedure consumer(): 
  if count = 0: 
    can_consume.wait 
  count-- 
  # Remove item from queue 
  can_produce.signal

Since monitor procedures are serialized, we only have to worry about one procedure running at a time. When a Producer comes along, it will check how many items are in our shared queue. If the queue is full, the Producer will wait. Otherwise, the Producer will add an item to the queue and signal a consumer to consume it.

Likewise, when a Consumer comes along, it will check if there is anything to consume. If not, it will wait. Otherwise, it will consume an item from the queue and signal a Producer to let it know there’s space.

As with the last solution, I was curious to know if there were any opportunities for deadlocks, but I don’t believe there are any. The issue we had before was related to two process getting stuck waiting on each other. In this case, I don’t think that’s possible. For sanity sake, I tried replicating the issue described before, but it just doesn’t exist thanks to the way this solution is structured.

Want to Learn More?

At this point, that’s all I have to say about the Producers-Consumers problem. Naturally, I’d like to move on to study some other concepts like Inter-Process Communication which is up next.

In the meantime, if you liked this article, give it a share! Also, I’d appreciate it if you started supporting me over on Patreon or at least hopped on my mailing list.

If addition, I have plenty of articles I think you might like including:

• Solutions to the Readers-Writers Problem
• Understanding Process Synchronization
• Be Careful When Copying Mutable Data Types

At any rate, thanks again for your support! Come back soon.

The post Solutions to the Producers-Consumers Problem appeared first on The Renegade Coder.