8.1. Synchronization Patterns and Problems¶
“If you’re not failing 90% of the time, then you’re probably not working on sufficiently challenging problems.”
From the earliest work on synchronization, it became clear that there were common software patterns that could solve key timing issues and race conditions that frequently occurred. Edsger Dijkstra characterized one such pattern as the Dining Philosophers problem in 1965. Tony Hoare—while working on his Communicating Sequential Processes (CSP) language to support formal analysis of concurrency—revisited this problem in 1985 and defined the standard version of it. Solutions for these types of synchronization problems are powerful and reusable techniques for creating robust and safe implementations of concurrent software.
Chapter Objectives
In this chapter, we will address the following instructional objectives:
- We will illustrate several design patterns that can be used for simple synchronization tasks.
- We will examine classical synchronization problems that have been studied extensively, with well-known solutions.
- We will highlight classical synchronization problems that demonstrate the limitations of basic synchronization primitives.
- We will consider additional synchronization problems with more complex requirements that can be mapped to simpler design patterns.
Race condition bugs can be extremely difficult to diagnose and fix. Observing these bugs depends on the programmer’s ability to reconstruct the timing that makes the bug manifest. This task becomes even more difficult when the bug is caused by the interaction of multiple system components that may or may not be under that programmer’s control. Fortunately, many common tasks in concurrent software are simple in nature and can be achieved by applying basic synchronization design patterns with semaphores, locks, or other synchronization primitives. Other tasks are variations on well-known synchronization problems. These problems tend to have an underlying structure that has a known solution that provides safe and efficient execution.
This chapter will focus on known solutions to common tasks that arise in concurrent software. We will describe the scenarios in which these design patterns and solutions apply and provide informal explanations of why they work. For the more complex problems, we will consider how the requirements can be decomposed into pieces that map to the more basic design patterns.