Chapter 2. The Problem With Concurrency

Table of Contents

Race Conditions and Critical Regions

(Skip this if you know what a Race Condition is).

In a normal program, you can increment a counter like so:

      very_important_count++;
    

This is what they would expect to happen:

Table 2.1. Expected Results

Instance 1Instance 2
read very_important_count (5) 
add 1 (6) 
write very_important_count (6) 
 read very_important_count (6)
 add 1 (7)
 write very_important_count (7)

This is what might happen:

Table 2.2. Possible Results

Instance 1Instance 2
read very_important_count (5) 
 read very_important_count (5)
add 1 (6) 
 add 1 (6)
write very_important_count (6) 
 write very_important_count (6)

Race Conditions and Critical Regions

This overlap, where the result depends on the relative timing of multiple tasks, is called a race condition. The piece of code containing the concurrency issue is called a critical region. And especially since Linux starting running on SMP machines, they became one of the major issues in kernel design and implementation.

Preemption can have the same effect, even if there is only one CPU: by preempting one task during the critical region, we have exactly the same race condition. In this case the thread which preempts might run the critical region itself.

The solution is to recognize when these simultaneous accesses occur, and use locks to make sure that only one instance can enter the critical region at any time. There are many friendly primitives in the Linux kernel to help you do this. And then there are the unfriendly primitives, but I'll pretend they don't exist.