Some Well-Known Concurrency Problems

This chapter is about some well-known concurrency problems that have many practical applications. The problems we will look at are as follows:

• The producer-consumer problem
• The dining philosophers problem
• Rate limiting

At the end of this chapter, you will have seen multiple implementations of these problems with some practical considerations on how to approach concurrency issues.

Technical Requirements

The source code for this particular chapter is available on GitHub at https://github.com/PacktPublishing/Effective-Concurrency-in-Go/tree/main/chapter4.

The producer-consumer problem

In the previous chapter, we implemented a version of the producer-consumer problem using condition variables and mentioned that most of the time, the condition variables can be replaced by channels. The producer-consumer implementations we will work on in this chapter demonstrate this point. Some concurrency problems, such as the producer-consumer problem, are by their nature message-passing problems, and trying to solve them using shared-memory utilities results in unnecessarily complicated and lengthy code.

At the core of the producer-consumer problem is limited intermediate storage. At a high level, the producer-consumer problem contains processes that produce objects at various rates, and consumers that consume those objects at various rates, with limited storage in between the two that is used to store the produced objects until they are consumed. The producer-consumer problem is relevant in any system where a balance between the production of...

The dining philosophers problem

We visited the dining philosopher’s problem in Chapter 1, Concurrency: A High-Level Overview, while discussing concurrency at a higher level. This is an important problem in the study of critical sections. The problem may seem contrived, but it shows a problem that comes up often in real-world situations: entering the critical section may require the acquisition of multiple resources (mutexes). Any time you have a critical section that relies on multiple mutexes, you have a chance of deadlock and starvation.

Now, we will study some solutions to this problem in Go. We will begin by restating the problem:

There are five philosophers dining together at the same round table. There are five plates, one in front of each philosopher, and one fork between each plate, five forks total. The dish they are eating requires them to use both forks, one on their left side and the other on their right side. Each philosopher thinks for a random interval and...

Rate limiting

Limiting the rate of requests for a resource is important to maintain a predictable quality of service. There are several ways rate control can be achieved. We will study two implementations of the same algorithm. The first one is a relatively simple implementation of the token bucket algorithm that uses channels, a ticker, and a goroutine. Then, we will study a more advanced implementation that requires fewer resources.

First, let’s take a look at the token bucket algorithm and show how it is used for rate limiting. Imagine a fixed-sized bucket containing tokens. There is a producer process that deposits tokens into this bucket at a fixed rate, say two tokens/second. Every 500 milliseconds, this process adds a token to the bucket if the bucket has empty slots. If the bucket is full, it waits for another 500 milliseconds and checks the bucket again. There is also a consumer process that consumes tokens at random intervals. However, in order for the consumer...

Summary

In this chapter, we studied three well-known concurrency problems that show up consistently when working with non-trivial problems. Producer-consumer implementations have uses in data processing pipelines, crawlers, device interactions, network communications, and more. The dining philosophers problem is a good demonstration of critical sections that require multiple mutexes. Finally, rate-limiting has applications in ensuring the quality of service, limiting resource utilization, and API accounting.

In the next chapter, we will start looking at more realistic examples of concurrent programming, in particular, worker pools, concurrent data pipelines, and fan-in/fan-out.