1<html><head><meta http-equiv="Content-Type" content="text/html; charset=ANSI_X3.4-1968"><title>Chapter 2. The Problem With Concurrency</title><meta name="generator" content="DocBook XSL Stylesheets V1.78.1"><link rel="home" href="index.html" title="Unreliable Guide To Locking"><link rel="up" href="index.html" title="Unreliable Guide To Locking"><link rel="prev" href="intro.html" title="Chapter 1. Introduction"><link rel="next" href="locks.html" title="Chapter 3. Locking in the Linux Kernel"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 2. The Problem With Concurrency</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="intro.html">Prev</a> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="locks.html">Next</a></td></tr></table><hr></div><div class="chapter"><div class="titlepage"><div><div><h1 class="title"><a name="races"></a>Chapter 2. The Problem With Concurrency</h1></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl class="toc"><dt><span class="sect1"><a href="races.html#race-condition">Race Conditions and Critical Regions</a></span></dt></dl></div><p> 2 (Skip this if you know what a Race Condition is). 3 </p><p> 4 In a normal program, you can increment a counter like so: 5 </p><pre class="programlisting"> 6 very_important_count++; 7 </pre><p> 8 This is what they would expect to happen: 9 </p><div class="table"><a name="idp1123300436"></a><p class="title"><b>Table 2.1. Expected Results</b></p><div class="table-contents"><table summary="Expected Results" border="1"><colgroup><col><col></colgroup><thead><tr><th align="left">Instance 1</th><th align="left">Instance 2</th></tr></thead><tbody><tr><td align="left">read very_important_count (5)</td><td align="left"> </td></tr><tr><td align="left">add 1 (6)</td><td align="left"> </td></tr><tr><td align="left">write very_important_count (6)</td><td align="left"> </td></tr><tr><td align="left"> </td><td align="left">read very_important_count (6)</td></tr><tr><td align="left"> </td><td align="left">add 1 (7)</td></tr><tr><td align="left"> </td><td align="left">write very_important_count (7)</td></tr></tbody></table></div></div><br class="table-break"><p> 10 This is what might happen: 11 </p><div class="table"><a name="idp1123560364"></a><p class="title"><b>Table 2.2. Possible Results</b></p><div class="table-contents"><table summary="Possible Results" border="1"><colgroup><col><col></colgroup><thead><tr><th align="left">Instance 1</th><th align="left">Instance 2</th></tr></thead><tbody><tr><td align="left">read very_important_count (5)</td><td align="left"> </td></tr><tr><td align="left"> </td><td align="left">read very_important_count (5)</td></tr><tr><td align="left">add 1 (6)</td><td align="left"> </td></tr><tr><td align="left"> </td><td align="left">add 1 (6)</td></tr><tr><td align="left">write very_important_count (6)</td><td align="left"> </td></tr><tr><td align="left"> </td><td align="left">write very_important_count (6)</td></tr></tbody></table></div></div><br class="table-break"><div class="sect1"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="race-condition"></a>Race Conditions and Critical Regions</h2></div></div></div><p> 12 This overlap, where the result depends on the 13 relative timing of multiple tasks, is called a <em class="firstterm">race condition</em>. 14 The piece of code containing the concurrency issue is called a 15 <em class="firstterm">critical region</em>. And especially since Linux starting running 16 on SMP machines, they became one of the major issues in kernel 17 design and implementation. 18 </p><p> 19 Preemption can have the same effect, even if there is only one 20 CPU: by preempting one task during the critical region, we have 21 exactly the same race condition. In this case the thread which 22 preempts might run the critical region itself. 23 </p><p> 24 The solution is to recognize when these simultaneous accesses 25 occur, and use locks to make sure that only one instance can 26 enter the critical region at any time. There are many 27 friendly primitives in the Linux kernel to help you do this. 28 And then there are the unfriendly primitives, but I'll pretend 29 they don't exist. 30 </p></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="intro.html">Prev</a> </td><td width="20%" align="center"> </td><td width="40%" align="right"> <a accesskey="n" href="locks.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 1. Introduction </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 3. Locking in the Linux Kernel</td></tr></table></div></body></html> 31