Chapter 32: Common Concurrency Problems

This page is a generated reference surface for selective reading. It exists to keep the learner apps guide-first while still preserving source access.

Learning objectives

Explain the main ideas and vocabulary in Common Concurrency Problems.
Work through the source examples for Common Concurrency Problems without depending on raw chunk order.
Use Common Concurrency Problems as selective reference when learner modules point back to Ostep.

Prerequisites

Earlier prerequisite concepts leading into Chapter 32: Common Concurrency Problems.

Module targets

module-03-concurrency-synchronization

AI companion modes

Explain simply
Socratic tutor
Quiz me
Challenge my understanding
Diagnose my confusion
Generate extra practice
Revision mode
Connect forward / backward

Source-of-truth note

This unit is anchored to Ostep and the source chapter "Chapter 32: Common Concurrency Problems". Use external resources only to clarify, extend, or modernize details without replacing the chapter's conceptual spine.

External enrichment

No chapter-specific enrichment resources are curated yet. Add them in the unit manifest when a source clearly improves learning.

Source provenance

Primary source: Ostep
Source chapter 32: Chapter 32: Common Concurrency Problems
Raw source file: 153-32-common-concurrency-problems.md
Raw source file: 154-32-2-non-deadlock-bugs.md
Raw source file: 155-32-3-deadlock-bugs.md

Merged source

Common Concurrency Problems

32 Common Concurrency Problems

Researchers have spent a great deal of time and effort looking into concurrency bugs over many years. Much of the early work focused on deadlock, a topic which we've touched on in the past chapters but will now dive into deeply [C+71]. More recent work focuses on studying other types of common concurrency bugs (i.e., non-deadlock bugs). In this chapter, we take a brief look at some example concurrency problems found in real code bases, to better understand what problems to look out for. And thus our central issue for this chapter:

CRUX: HOWTOHANDLECOMMONCONCURRENCYBUGS

Concurrency bugs tend to come in a variety of common patterns.

Knowing which ones to look out for is the first step to writing more robust, correct concurrent code.

32.1 What Types Of Bugs Exist?

The first, and most obvious, question is this: what types of concurrency bugs manifest in complex, concurrent programs? This question is difficult to answer in general, but fortunately, some others have done the work for us. Specifically, we rely upon a study by Lu et al. [L+08], which analyzes a number of popular concurrent applications in great detail to understand what types of bugs arise in practice.

The study focuses on four major and important open-source applications: MySQL (a popular database management system), Apache (a wellknown web server), Mozilla (the famous web browser), and OpenOffice (a free version of the MS Office suite, which some people actually use).

In the study, the authors examine concurrency bugs that have been found and fixed in each of these code bases, turning the developers' work into a quantitative bug analysis; understanding these results can help you understand what types of problems actually occur in mature code bases.

Application What it does Non-Deadlock Deadlock

MySQL Database Server 14

Apache Web Server 13

Mozilla Web Browser 41 16

OpenOffice Office Suite 6 2

Total 74 31

Non Deadlock Bugs

32.2 Non-Deadlock Bugs

Figure 32.1:Bugs In Modern Applications

Figure 32.1 shows a summary of the bugs Lu and colleagues studied.

From the figure, you can see that there were 105 total bugs, most of which were not deadlock (74); the remaining 31 were deadlock bugs. Further, you can see that the number of bugs studied from each application; while

OpenOffice only had 8 total concurrency bugs, Mozilla had nearly 60.

We now dive into these different classes of bugs (non-deadlock, deadlock) a bit more deeply. For the first class of non-deadlock bugs, we use

examples from the study to drive our discussion. For the second class of deadlock bugs, we discuss the long line of work that has been done in either preventing, avoiding, or handling deadlock.

Non-deadlock bugs make up a majority of concurrency bugs, according to Lu's study. But what types of bugs are these? How do they arise?

How can we fix them? We now discuss the two major types of nondeadlock bugs found by Lu et al.: atomicity violationbugs andorder violationbugs.

Atomicity-Violation Bugs

The first type of problem encountered is referred to as anatomicity violation. Here is a simple example, found in MySQL. Before reading the explanation, try figuring out what the bug is. Do it!

1 Thread 1::

if (thd->proc_info) {
...
fputs(thd->proc_info, ...);
...
}

7 8 Thread 2::

thd->proc_info = NULL;

In the example, two different threads access the fieldprocinfoin the structurethd. The first thread checks if the value is non-NULL and then prints its value; the second thread sets it to NULL. Clearly, if the first thread performs the check but then is interrupted before the call to fputs, the second thread could run in-between, thus setting the pointer to NULL; when the first thread resumes, it will crash, as a NULL pointer will be dereferenced byfputs.

The more formal definition of an atomicity violation, according to Lu et al, is this: "The desired serializability among multiple memory accesses is violated (i.e. a code region is intended to be atomic, but the atomicity is not enforced during execution)." In our example above, the code has anatomicity assumption(in Lu's words) about the check for non-NULL of procinfoand the usage ofprocinfoin thefputs()call; when the assumption is incorrect, the code will not work as desired.

Finding a fix for this type of problem is often (but not always) straightforward. Can you think of how to fix the code above?

In this solution, we simply add locks around the shared-variable references, ensuring that when either thread accesses theprocinfofield, it has a lock held (procinfolock). Of course, any other code that accesses the structure should also acquire this lock before doing so.

pthread_mutex_t proc_info_lock = PTHREAD_MUTEX_INITIALIZER;

2 3 Thread 1::

pthread_mutex_lock(&proc_info_lock);
if (thd->proc_info) {
...
fputs(thd->proc_info, ...);
...
}
pthread_mutex_unlock(&proc_info_lock);

11 12 Thread 2::

pthread_mutex_lock(&proc_info_lock);
thd->proc_info = NULL;
pthread_mutex_unlock(&proc_info_lock);

Order-Violation Bugs

Another common type of non-deadlock bug found by Lu et al. is known as anorder violation. Here is another simple example; once again, see if you can figure out why the code below has a bug in it.

1 Thread 1::

void init() {
...
mThread = PR_CreateThread(mMain, ...);
...
}

7 8 Thread 2::

void mMain(...) {
...
mState = mThread->State;
...
}

As you probably figured out, the code in Thread 2 seems to assume

that the variablemThreadhas already been initialized (and is not NULL);

however, if Thread 2 runs immediately once created, the value ofmThread will not be set when it is accessed withinmMain()in Thread 2, and will likely crash with a NULL-pointer dereference. Note that we assume the value ofmThreadis initially NULL; if not, even stranger things could happen as arbitrary memory locations are accessed through the dereference in Thread 2.

The more formal definition of an order violation is this: "The desired order between two (groups of) memory accesses is flipped (i.e.,Ashould always be executed beforeB, but the order is not enforced during execution)" [L+08].

The fix to this type of bug is generally to enforce ordering. As we discussed in detail previously, usingcondition variablesis an easy and robust way to add this style of synchronization into modern code bases.

In the example above, we could thus rewrite the code as follows:

pthread_mutex_t mtLock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t mtCond = PTHREAD_COND_INITIALIZER;
int mtInit = 0;

4 5 Thread 1::

void init() {
...
mThread = PR_CreateThread(mMain, ...);

9 10 // signal that the thread has been created...

pthread_mutex_lock(&mtLock);
mtInit = 1;
pthread_cond_signal(&mtCond);
pthread_mutex_unlock(&mtLock);
...
}

17 18 Thread 2::

void mMain(...) {
...

21 // wait for the thread to be initialized...

pthread_mutex_lock(&mtLock);
while (mtInit == 0)
pthread_cond_wait(&mtCond, &mtLock);
pthread_mutex_unlock(&mtLock);
mState = mThread->State;
...
}

In this fixed-up code sequence, we have added a lock (mtLock) and corresponding condition variable (mtCond), as well as a state variable (mtInit). When the initialization code runs, it sets the state ofmtInit to 1 and signals that it has done so. If Thread 2 had run before this point, it will be waiting for this signal and corresponding state change; if it runs later, it will check the state and see that the initialization has already occurred (i.e.,mtInitis set to 1), and thus continue as is proper. Note that we could likely usemThreadas the state variable itself, but do not do so for the sake of simplicity here. When ordering matters between threads, condition variables (or semaphores) can come to the rescue.

Deadlock Bugs

32.3 Deadlock Bugs

Non-Deadlock Bugs: Summary

A large fraction (97%) of non-deadlock bugs studied by Lu et al. are either atomicity or order violations. Thus, by carefully thinking about these types of bug patterns, programmers can likely do a better job of avoiding them. Moreover, as more automated code-checking tools develop, they should likely focus on these two types of bugs as they constitute such a large fraction of non-deadlock bugs found in deployment.

Unfortunately, not all bugs are as easily fixable as the examples we looked at above. Some require a deeper understanding of what the program is doing, or a larger amount of code or data structure reorganization to fix. Read Lu et al.'s excellent (and readable) paper for more details.

Beyond the concurrency bugs mentioned above, a classic problem that arises in many concurrent systems with complex locking protocols is known asdeadlock. Deadlock occurs, for example, when a thread (say Thread

is holding a lock (L1) and waiting for another one (L2); unfortunately,

the thread (Thread 2) that holds lockL2is waiting forL1to be released.

Here is a code snippet that demonstrates such a potential deadlock:

Thread 1: Thread 2:

lock(L1); lock(L2);
lock(L2); lock(L1);

Note that if this code runs, deadlock does not necessarily occur; rather,

it may occur, if, for example, Thread 1 grabs lockL1and then a context switch occurs to Thread 2. At that point, Thread 2 grabsL2, and tries to acquireL1. Thus we have a deadlock, as each thread is waiting for the other and neither can run. See Figure 32.2 for a graphical depiction; the presence of acyclein the graph is indicative of the deadlock.

The figure should make clear the problem. How should programmers write code so as to handle deadlock in some way?

CRUX: HOWTODEALWITHDEADLOCK

How should we build systems to prevent, avoid, or at least detect and recover from deadlock? Is this a real problem in systems today?

Why Do Deadlocks Occur?

As you may be thinking, simple deadlocks such as the one above seem readily avoidable. For example, if Thread 1 and 2 both made sure to grab locks in the same order, the deadlock would never arise. So why do deadlocks happen?

Holds

Thread 1 Lock L1

Wanted by

Lock L2 Thread 2

Holds

Figure 32.2:The Deadlock Dependency Graph

One reason is that in large code bases, complex dependencies arise between components. Take the operating system, for example. The virtual memory system might need to access the file system in order to page in a block from disk; the file system might subsequently require a page of memory to read the block into and thus contact the virtual memory system. Thus, the design of locking strategies in large systems must be carefully done to avoid deadlock in the case of circular dependencies that may occur naturally in the code.

Another reason is due to the nature ofencapsulation. As software developers, we are taught to hide details of implementations and thus make software easier to build in a modular way. Unfortunately, such modularity does not mesh well with locking. As Jula et al. point out [J+08], some seemingly innocuous interfaces almost invite you to deadlock. For example, take the Java Vector class and the methodAddAll(). This routine would be called as follows:

Vector v1, v2;

v1.AddAll(v2);

Internally, because the method needs to be multi-thread safe, locks for both the vector being added to (v1) and the parameter (v2) need to be acquired. The routine acquires said locks in some arbitrary order (say v1 then v2) in order to add the contents of v2 to v1. If some other thread callsv2.AddAll(v1)at nearly the same time, we have the potential for deadlock, all in a way that is quite hidden from the calling application.

Learning objectives​

Prerequisites​

Module targets​

AI companion modes​

Source-of-truth note​

External enrichment​

Source provenance​

Merged source​

Common Concurrency Problems​