<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN">
<HTML
><HEAD
><TITLE
>Introduction</TITLE
><META
NAME="GENERATOR"
CONTENT="Modular DocBook HTML Stylesheet Version 1.7"><LINK
REL="HOME"
TITLE="Unreliable Guide To Locking"
HREF="book1.html"><LINK
REL="PREVIOUS"
TITLE="Unreliable Guide To Locking"
HREF="book1.html"><LINK
REL="NEXT"
TITLE="Two Main Types of Kernel Locks: Spinlocks and Semaphores"
HREF="c88.html"></HEAD
><BODY
CLASS="CHAPTER"
BGCOLOR="#FFFFFF"
TEXT="#000000"
LINK="#0000FF"
VLINK="#840084"
ALINK="#0000FF"
><DIV
CLASS="NAVHEADER"
><TABLE
SUMMARY="Header navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TH
COLSPAN="3"
ALIGN="center"
>Unreliable Guide To Locking</TH
></TR
><TR
><TD
WIDTH="10%"
ALIGN="left"
VALIGN="bottom"
><A
HREF="book1.html"
ACCESSKEY="P"
><<< Previous</A
></TD
><TD
WIDTH="80%"
ALIGN="center"
VALIGN="bottom"
></TD
><TD
WIDTH="10%"
ALIGN="right"
VALIGN="bottom"
><A
HREF="c88.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
></TABLE
><HR
ALIGN="LEFT"
WIDTH="100%"></DIV
><DIV
CLASS="CHAPTER"
><H1
><A
NAME="INTRO"
></A
>Introduction</H1
><P
> Welcome, to Rusty's Remarkably Unreliable Guide to Kernel
Locking issues. This document describes the locking systems in
the Linux Kernel as we approach 2.4.
</P
><P
> It looks like <A
HREF="g388.html#GLOSS-SMP"
><I
CLASS="FIRSTTERM"
><SPAN
CLASS="ACRONYM"
>SMP</SPAN
>
</I
></A
> is here to stay; so everyone hacking on the kernel
these days needs to know the fundamentals of concurrency and locking
for SMP.
</P
><DIV
CLASS="SECT1"
><H1
CLASS="SECT1"
><A
NAME="RACES"
></A
>The Problem With Concurrency</H1
><P
> (Skip this if you know what a Race Condition is).
</P
><P
> In a normal program, you can increment a counter like so:
</P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
> very_important_count++;
</PRE
></TD
></TR
></TABLE
><P
> This is what they would expect to happen:
</P
><DIV
CLASS="TABLE"
><A
NAME="AEN33"
></A
><P
><B
>Table 1. Expected Results</B
></P
><TABLE
BORDER="1"
BGCOLOR="#E0E0E0"
CELLSPACING="0"
CELLPADDING="4"
CLASS="CALSTABLE"
><THEAD
><TR
><TH
ALIGN="LEFT"
VALIGN="TOP"
>Instance 1</TH
><TH
ALIGN="LEFT"
VALIGN="TOP"
>Instance 2</TH
></TR
></THEAD
><TBODY
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>read very_important_count (5)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>add 1 (6)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>write very_important_count (6)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>read very_important_count (6)</TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>add 1 (7)</TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>write very_important_count (7)</TD
></TR
></TBODY
></TABLE
></DIV
><P
> This is what might happen:
</P
><DIV
CLASS="TABLE"
><A
NAME="AEN60"
></A
><P
><B
>Table 2. Possible Results</B
></P
><TABLE
BORDER="1"
BGCOLOR="#E0E0E0"
CELLSPACING="0"
CELLPADDING="4"
CLASS="CALSTABLE"
><THEAD
><TR
><TH
ALIGN="LEFT"
VALIGN="TOP"
>Instance 1</TH
><TH
ALIGN="LEFT"
VALIGN="TOP"
>Instance 2</TH
></TR
></THEAD
><TBODY
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>read very_important_count (5)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>read very_important_count (5)</TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>add 1 (6)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>add 1 (6)</TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
>write very_important_count (6)</TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
></TR
><TR
><TD
ALIGN="LEFT"
VALIGN="TOP"
> </TD
><TD
ALIGN="LEFT"
VALIGN="TOP"
>write very_important_count (6)</TD
></TR
></TBODY
></TABLE
></DIV
><P
> This overlap, where what actually happens 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.
</P
><P
> 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.
</P
></DIV
></DIV
><DIV
CLASS="NAVFOOTER"
><HR
ALIGN="LEFT"
WIDTH="100%"><TABLE
SUMMARY="Footer navigation table"
WIDTH="100%"
BORDER="0"
CELLPADDING="0"
CELLSPACING="0"
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
><A
HREF="book1.html"
ACCESSKEY="P"
><<< Previous</A
></TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
><A
HREF="book1.html"
ACCESSKEY="H"
>Home</A
></TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
><A
HREF="c88.html"
ACCESSKEY="N"
>Next >>></A
></TD
></TR
><TR
><TD
WIDTH="33%"
ALIGN="left"
VALIGN="top"
>Unreliable Guide To Locking</TD
><TD
WIDTH="34%"
ALIGN="center"
VALIGN="top"
> </TD
><TD
WIDTH="33%"
ALIGN="right"
VALIGN="top"
>Two Main Types of Kernel Locks: Spinlocks and Semaphores</TD
></TR
></TABLE
></DIV
></BODY
></HTML
>
