\documentclass{ictlab}

\RCS $Revision: 1.6 $

\usepackage{alltt,key,color,answer2,float,afterpage,biganswerbox,xr}
\externaldocument[proc-]{../../lectures/processes/processes-print-3}
\usepackage[nolineno,noindent]{lgrind}
%\usepackage[leftnum,lineno5,noindent]{lgrind}
\ifx\pdftexversion\undefined \else
  \usepackage[pdfpagemode=None,pdfauthor={Nick Urbanik}]{hyperref}
\fi

\renewcommand*{\subject}{Operating Systems and Systems Integration}

\newcommand*{\labTitle}{Workshop on POSIX Threads and the Problem of Deadlock}


\definecolor{light-blue}{rgb}{0.4,0.4,1}
\newcommand*{\gl}[1]{\textcolor{light-blue}{#1}} % good link
\newcommand*{\ex}[1]{\textcolor{green}{#1}} % executable file
\newcommand*{\bl}[1]{\colorbox{red}{\textcolor{white}{\textbf{#1}}}} % bad link

\renewcommand{\floatpagefraction}{0.75} % default is .5, to increase
% density.
\renewcommand*{\bottomfraction}{0.6} % default is 0.3
\renewcommand*{\topfraction}{0.85} % default is 0.7
\renewcommand*{\textfraction}{0.1} % default is 0.2

\setlength{\extrarowheight}{1pt}
\floatstyle{ruled}
\floatname{program}{Program}
\newfloat{program}{tbh}{lop}

\providecommand*{\SMP}{\acro{SMP}\xspace}%

\begin{document}

\section{Background}
\label{sec:background}
\begin{itemize*}
\item \POSIX is a standard for \UNIX
\item Linux implements \POSIX threads
\item On Red Hat 8.x, documentation is at
\begin{alltt}
$ \textbf{info '(libc) POSIX Threads'}
\end{alltt}%$
\begin{itemize*}
\item or in Emacs, \texttt{C-H m libc} then middle-click on
  \texttt{POSIX threads}
\end{itemize*}
\item Provides:
  \begin{itemize*}
  \item \emph{semaphores},
  \item \emph{mutex}es and
  \item \emph{condition variables}
  \end{itemize*}
  for locking (synchronisation)
\end{itemize*}


\section{Generic Procedure for Compiling POSIX Threads Applications}
\label{sec:generic-instructions}


\begin{enumerate}
  \item You need to use the \texttt{libpthread} library
    \begin{itemize*}
    \item Specify this with the option \texttt{-lpthread}
    \end{itemize*}
  \item Need to tell the other libraries that they should be
    \emph{reentrant} (or ``\emph{thread safe}'')
    \begin{itemize*}
    \item This means that the library uses no static variables that may
      be overwritten by another thread
    \item Specify this with the option \texttt{-D\_REENTRANT}
    \end{itemize*}

  \item So, to compile the program \meta{program}.c, do:
\begin{alltt}\small
$ \textbf{gcc -D_REENTRANT -lpthread -o \meta{program} \meta{program}.c}      
\end{alltt}%$
\end{enumerate}


\section{Procedure}
\label{sec:procedure}


\begin{program}[tbh]
    %\smallskip%
%\begin{verbatim}
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define NUM_THREADS 5

void *print_hello( void *threadid )
{
        printf( "\n%d: Hello World!\n", ( int ) threadid );
        pthread_exit( NULL );
}

int main()
{
        static pthread_t threads[ NUM_THREADS ];
        int rc, t;
        for ( t = 0; t < NUM_THREADS; t++ ) {
                printf( "Creating thread %d\n", t );
                rc = pthread_create( &threads[ t ], NULL, print_hello, ( void * ) t );
                if ( rc ) {
                        printf( "ERROR; pthread_create() returned %d\n", rc );
                        printf( "Error string: \"%s\"\n", strerror( rc ) );
                        exit( -1 );
                }
        }
        pthread_exit( NULL );
}
%]
\vspace*{-3ex}
%\end{verbatim}
\caption{A simple program \texttt{hello.c} that is the
  program \texttt{hello.c} given in the lecture.}
\label{prg:hello}
\end{program}

\newlength{\wid}
\setlength{\wid}{10\linewidth/40}
\newlength{\topspace}
\newlength{\bottomspace}
\setlength{\topspace}{-5.5ex}
\setlength{\bottomspace}{-3.5ex}
  \begin{program}
\begin{tabular}{p{\wid}|p{\wid}|p{\wid}|p{\wid}}
\emph{deadlock} & \emph{no mutual exclusion} & \emph{no hold \& wait}
& \emph{no circular wait}\\
%\hline
\vspace*{\topspace}%
%[
Thread a()
{
    lock mutex1;
    give up CPU;
    lock mutex2;
    unlock mutex1;
    unlock mutex2;
}
Thread b()
{
    lock mutex2;
    give up CPU;
    lock mutex1;
    unlock mutex2;
    unlock mutex1;
}
%]
\vspace*{\bottomspace}
&%
% no mutual exclusion
\begin{solution}%
\vspace*{\topspace}%
%[
/* No locking
   No mutexes */
Thread a()
{
    use resource1;
    use resource2;
}
Thread b()
{
    use resource2;
    use resource1;
}
%]
\vspace*{\bottomspace}%
\end{solution}%
&%
% no hold \& wait
\begin{solution}%
\vspace*{\topspace}
%[
Thread a()
{
    /* no H & W */
    lock mutex1;
    give up CPU;
    unlock mutex1;
    lock mutex2;
    unlock mutex2;
}
Thread b()
{
    lock mutex2;
    give up CPU;
    lock mutex1;
    unlock mutex2;
    unlock mutex1;
}
%]
\vspace*{\bottomspace}%
\end{solution}%
&
% no circular wait
\begin{solution}%
\vspace*{\topspace}%
%[
Thread a()
{
    lock mutex1;
    give up CPU;
    lock mutex2;
    unlock mutex1;
    unlock mutex2;
}
Thread b()
{
    /* same order */
    lock mutex1;
    give up CPU;
    lock mutex2;
    unlock mutex1;
    unlock mutex2;
}
%]
\vspace*{\bottomspace}%
\end{solution}%
\end{tabular}
%\end{verbatim}
\caption{Pseudocode for the two threads.}
\label{prg:deadlock-pseudocode}
  \end{program}

\begin{program}[tbh]
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include "errors.h"

/* Initialize 2 mutexes. */
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void *locking_thread_a( void *arg )
{
        int status;
        printf( "locking_thread_a starting\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "a has lock 1\n" );
        sched_yield();
        printf( "a now trying to get lock 2\n" );
        status = pthread_mutex_lock( &mutex2 );
        printf( "a has lock 2\n" );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_unlock( &mutex2 );
        printf( "locking_thread_a finishing\n" );
        pthread_exit( NULL );
}

void *locking_thread_b( void *arg )
{
        int status;
        printf( "locking_thread_b starting\n" );
        status = pthread_mutex_lock( &mutex2 );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        printf( "b has lock 2\n" );
        sched_yield();
        printf( "b now trying to get lock 1\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "b has lock 1\n" );
        pthread_mutex_unlock( &mutex2 );
        pthread_mutex_unlock( &mutex1 );
        printf( "locking_thread_b finishing\n" );
        pthread_exit( NULL );
}
%]
\vspace*{\bottomspace}
%\end{verbatim}
\caption{The first part of the  program \texttt{deadlock.c} that is
  unable to run to completion.}
\label{prg:deadlock1}
\end{program}

\begin{enumerate}
\item Download the source code for these programs from the subject web
  site: \texttt{hello.c}, \texttt{deadlock.c} and \texttt{error.h}.
\end{enumerate}


\subsection{An Introduction to Posix Threads}
\label{sec:intro-to-posix-threads}

\begin{enumerate}
\item Compile and run program~\vref{prg:hello}, using the generic
  instructions given in section~\vref{sec:generic-instructions}.
  
\item Refer to the lecture notes on the topic \emph{Processes and
    Threads} and read the few slides starting at
  slide~\pageref{proc-sld:pthread_create}.  Read about the four
  parameters that are passed to \texttt{pthread\_create()}.  Note that
  there is a detailed manual page for every single library function
  used here.  For example, you can see \texttt{man pthread\_create},
  and \texttt{man strerror}, \texttt{man 3 exit}, \texttt{man 3
    printf}, and so on.

\item Modify \texttt{hello.c}, increasing the number of threads
  until you find the maximum number of threads that your system can
  support.
  
\item Download the program file \texttt{hello-with-logs.c}, which
  makes each thread do \CPU intensive calculations.  Observe the
  output of \texttt{vmstat~1} and also, run \texttt{top} in another
  window.  Watch the load average.\footnote{\emph{Load Average} is the
    average number of processes that are in the \emph{ready-to-run}
    state.  In other words, the number of additional processes that
    would be running if each had a \CPU.}
\end{enumerate}


\subsection{Deadlock}
\label{sec:deadlock}

\begin{enumerate}
\item Compile and execute the program \texttt{deadlock.c} shown in
  program~\vref{prg:deadlock1} and program~\ref{prg:deadlock-main-function}.
  Observe what happens when you run it.
  
\item Read about \emph{mutexes} in slide~\pageref{proc-sld:mutex} in
  the lecture notes on the topic \emph{Processes and Threads}\e.  Also
  read
  slides~\pageref{proc-sld:mutex-example-1}--\pageref{proc-sld:mutex-example-3}
  showing example code using a mutex.

\item Notice that most of the code of program~\vref{prg:deadlock1} is
  \texttt{printf()} statements, error checking and such.  The code for
  the two threads can be expressed quite simply, as shown in
  program~\vref{prg:deadlock-pseudocode}.  Examine the pseudocode in
  program~\ref{prg:deadlock-pseudocode} and compare it with the C
  program~\ref{prg:deadlock1}, and see how the pseudocode is a
  summary of the C program.

\item The standard \POSIX library function \texttt{sched\_yield()}
  allows a thread or process to voluntarily give up the \CPU, so that
  the scheduler will move it to the end of the queue for its own
  priority, and allow another thread or process to run.  See
  \texttt{man sched\_yield}.

\item Note that there are four conditions required for deadlock; if
  you remove \emph{any} one of these, then deadlock will not happen.
  They are:
  \begin{itemize}
  \item Mutual exclusion
    \begin{itemize*}
    \item where only one process can use a resource at one time
    \end{itemize*}
  \item Hold and Wait
    \begin{itemize*}
    \item Processes holding resources given earlier can request new
      resources
    \end{itemize*}
  \item No Preemption
    \begin{itemize*}
    \item Resources given to a process or thread cannot be taken away
      forcibly by \OS or anything other than that process or thread
    \end{itemize*}
  \item Circular Wait
    \begin{itemize*}
    \item Each process is waiting for a resource held by another
    \end{itemize*}
  \end{itemize}

\newlength{\questionboxheight}
\setlength{\questionboxheight}{2.2cm}

\item \label{que:mutual-exclusion}Describe here how this program
  satisfies the deadlock requirement of \emph{mutual exclusion}

  \begin{biganswerbox}[\questionboxheight]%
    \begin{solution}%
      The program uses mutexes, which by their very nature, enforce
      \textbf{\textit{mut}}ual \textbf{\textit{ex}}clusion.  If one
      thread locks a mutex, no other thread can lock it until the
      first thread unlocks it.
    \end{solution}
  \end{biganswerbox}

\item \label{que:hold-and-wait}Describe here how this program
  satisfies the deadlock requirement of \emph{hold and wait}

  \begin{biganswerbox}[\questionboxheight]%
    \begin{solution}%
      \texttt{locking\_thread\_a()} locks mutex 1, then while still
      holding it, locks mutex 2.

      \texttt{locking\_thread\_b()} locks mutex 2, then while still
      holding it, locks mutex 1.  This is hold and wait.
    \end{solution}
  \end{biganswerbox}

\item \label{que:no-preemption}Describe here how this program
  satisfies the deadlock requirement of \emph{no preemption}
  \begin{biganswerbox}[\questionboxheight]%
    \begin{solution}%
      A thread cannot take a mutex away from another thread by force,
      and the code is not written so that one thread will give up the
      lock voluntarily to the other, so there is no preemption.
    \end{solution}
  \end{biganswerbox}

\item \label{que:circular-wait}Describe here how this program
  satisfies the deadlock requirement of \emph{circular wait}
  \begin{biganswerbox}[\questionboxheight]%
    \begin{solution}%
      \texttt{locking\_thread\_a()} locks \texttt{mutex1} then waits
      for \texttt{mutex2}, which can be held by
      \texttt{locking\_thread\_b()}, whereas
      \texttt{locking\_thread\_b()} locks \texttt{mutex2} then waits
      for \texttt{mutex1}, which can be held by
      \texttt{locking\_thread\_a()}.  The result is that both threads
      are blocked, waiting for the availablity of a resource held by
      the other.
    \end{solution}
  \end{biganswerbox}
  \nopagebreak\mbox{}%

%% \item Examine it carefully, and see if you can make a small change so
%%   that the program can run to completion.  Show the change you made to
%%   your lab supervisor. 
  
\item Copy the original program (\texttt{deadlock.c}) to a new file
  name, and make simple changes to it to remove at least one of the
  conditions required for deadlock.
  \begin{explanation}
    Note that there are \emph{many} ways of solving this problem, not
    just one or two.  Look for as many as you can.  Use simple logic
    rather than spending a lot of time reading the manuals for new
    \POSIX threads library functions.  First, simply try rearranging
    the pseudocode in program~\vref{prg:deadlock-pseudocode}.
  \end{explanation}
  \begin{itemize}
  \item Do this a number of times, using a different method for each
    program.

    \begin{solution}
    \item[\textbf{Solution:}] There are many solutions that may be
      correct, but many are wrong.  For example, removing the call to
      \texttt{shed\_yield()} does not remove any conditions for
      deadlock, since the program is very likely to deadlock on an
      \SMP machine, and on a single \CPU machine if there is some real
      work for the threads to do.
        
      Program~\vref{prg:no-mutual-exclusion} shows the mutual
      exclusion removed.  The \texttt{main()} fucntion is still the
      same as program~\vref{prg:deadlock-main-function}.  Note that
      the danger here is that the data may be corrupted if two threads
      write to it at the same time, or there may be a race condition
      that results in the wrong values stored in or read from the
      data.
      
      Program~\vref{prg:no-hold-and-wait} removes hold and wait from
      \texttt{locking\_thread\_a()}.  Note that this would not always
      be possible; the two resources may be both needed at the same
      time.
      
      Program~\vref{prg:no-hold-and-wait-by-voluntarily-releasing} is
      based on \texttt{backoff.c}; see
      section~\vref{sec:other-resources}.  The idea is that if
      \texttt{locking\_thread\_a()} has \texttt{mutex1}, and cannot
      lock \texttt{mutex2}, it releases \texttt{mutex1} and tries
      again later.  This eliminates hold and wait, since
      \texttt{locking\_thread\_a()} does not continue holding
      \texttt{mutex1} while waiting for \texttt{mutex2}.  Have a good
      look at the code, and see how it works.

      Porgram~\vref{prg:no-circular-wait} simply re-orders the
      requests for resources so that all threads request them in the
      same order.  This is a common practice in operating systems and
      threaded applications, but there may be some situations where it
      cannot be done.

      \item[\textbf{End of Solution.}] \mbox{}

      \begin{program}
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include "errors.h"

void *locking_thread_a( void *arg )
{
        int status;
        printf( "(NON) locking_thread_a starting\n" );
        printf( "a is using data 1\n" );
        sched_yield();
        printf( "a now using data 2\n" );
        printf( "(NON) locking_thread_a finishing\n" );
        pthread_exit( NULL );
}

void *locking_thread_b( void *arg )
{
        int status;
        printf( "(NON) locking_thread_b starting\n" );
        printf( "b is now using data 2\n" );
        sched_yield();
        printf( "b now using data 1\n" );
        printf( "(NON) locking_thread_b finishing\n" );
        pthread_exit( NULL );
}
%]
\vspace*{-3ex}
%\end{verbatim}
\caption{This simple solution removes mutual exclusion by removing the
  mutexes.  Note that although this leaves nothing much, in real life
  a mutex is associated with data, and the data would be accessed,
  even though it is no longer protected by a mutex.}
\label{prg:no-mutual-exclusion}
      \end{program}
      
\begin{program}[tbh]
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include "errors.h"

/* Initialize 2 mutexes. */
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void *locking_thread_a( void *arg )
{
        int status;
        printf( "locking_thread_a starting\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "a has lock 1\n" );
        sched_yield();
        // Note: unlock mutex1 before lock mutex 2:
        pthread_mutex_unlock( &mutex1 );
        printf( "a now trying to get lock 2\n" );
        status = pthread_mutex_lock( &mutex2 );
        printf( "a has lock 2\n" );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        pthread_mutex_unlock( &mutex2 );
        printf( "locking_thread_a finishing\n" );
        pthread_exit( NULL );
}

void *locking_thread_b( void *arg )
{
        int status;
        printf( "locking_thread_b starting\n" );
        status = pthread_mutex_lock( &mutex2 );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        printf( "b has lock 2\n" );
        sched_yield();
        printf( "b now trying to get lock 1\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "b has lock 1\n" );
        pthread_mutex_unlock( &mutex2 );
        pthread_mutex_unlock( &mutex1 );
        printf( "locking_thread_b finishing\n" );
        pthread_exit( NULL );
}
%]
\vspace*{\bottomspace}
%\end{verbatim}
\caption{Here we removed the condition of hold and wait from
  \texttt{locking\_thread\_a()}, by simply unlocking \texttt{mutex1}
  before locking \texttt{mutex2}.}
\label{prg:no-hold-and-wait}
\end{program}
    \end{solution}

\begin{program}[tbh]
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include "errors.h"

/* Initialize 2 mutexes. */
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void *locking_thread_a( void *arg )
{
        printf( "locking_thread_a starting\n" );
        for (;;) {
                int status;
                status = pthread_mutex_lock( &mutex1 );
                if ( status != 0 )
                       err_abort( status, "lock 1" );
                printf( "a has lock 1\n" );
                sched_yield();
                printf( "a now trying to get lock 2\n" );
                status = pthread_mutex_trylock( &mutex2 );
                if ( status == 0 )
                        break;
                printf( "a failed to lock; backing off\n" );
                pthread_mutex_unlock( &mutex1 );
                sched_yield();
        }        
        printf( "a has lock 2\n" );
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_unlock( &mutex2 );
        printf( "locking_thread_a finishing\n" );
        pthread_exit( NULL );
}

void *locking_thread_b( void *arg )
{
        int status;
        printf( "locking_thread_b starting\n" );
        status = pthread_mutex_lock( &mutex2 );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        printf( "b has lock 2\n" );
        sched_yield();
        printf( "b now trying to get lock 1\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "b has lock 1\n" );
        pthread_mutex_unlock( &mutex2 );
        pthread_mutex_unlock( &mutex1 );
        printf( "locking_thread_b finishing\n" );
        pthread_exit( NULL );
}
%]
\vspace*{\bottomspace}
%\end{verbatim}
\caption{This method is based on \texttt{backoff.c}; see
  section~\vref{sec:other-resources}.}
\label{prg:no-hold-and-wait-by-voluntarily-releasing}
\end{program}


\begin{program}[tbh]
\vspace*{-2ex}
%[
#include <pthread.h>
#include <stdio.h>
#include "errors.h"

/* Initialize 2 mutexes. */
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void *locking_thread_a( void *arg )
{
        int status;
        printf( "locking_thread_a starting\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "a has lock 1\n" );
        sched_yield();
        printf( "a now trying to get lock 2\n" );
        status = pthread_mutex_lock( &mutex2 );
        printf( "a has lock 2\n" );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_unlock( &mutex2 );
        printf( "locking_thread_a finishing\n" );
        pthread_exit( NULL );
}

void *locking_thread_b( void *arg )
{
        int status;
        printf( "locking_thread_b starting\n" );
        status = pthread_mutex_lock( &mutex1 );
        if ( status != 0 )
                err_abort( status, "lock 1" );
        printf( "a has lock 1\n" );
        sched_yield();
        printf( "a now trying to get lock 2\n" );
        status = pthread_mutex_lock( &mutex2 );
        printf( "a has lock 2\n" );
        if ( status != 0 )
                err_abort( status, "lock 2" );
        pthread_mutex_unlock( &mutex1 );
        pthread_mutex_unlock( &mutex2 );
        printf( "locking_thread_b finishing\n" );
        pthread_exit( NULL );
}
%]
\vspace*{-3ex}
%\end{verbatim}
\caption{By re-ordering the reequest for resources, we can eliminate
  the condition of circular wait.  We simply request the resources in
  the same order.}
\label{prg:no-circular-wait}
\end{program}
  
\item Put a comment at the top of the program, indicating which
  conditions for deadlock you have removed.
  \item Put your name and class in a comment at the top of each file.

  \item Demonstrate to your lab supervisor.
    
  \item \label{que:make-text-file}Write a text file containing your
    answers to questions~\ref{que:mutual-exclusion},
    \ref{que:hold-and-wait}, \ref{que:no-preemption} and
    \ref{que:circular-wait}.
  
  \item Use the \texttt{tar} or \texttt{zip} program to combine the
    sources and the text file mentioned above into one file, and
    
  \item Submit to the online submission system at
    \sloppypar\url{http://nicku.org/perl2/submit.cgi}.
  \end{itemize}
\end{enumerate}

\clearpage

\begin{program}[t]
    %\smallskip%
%\begin{verbatim}
  \vspace*{-2ex}
%[
int main()
{
        pthread_t thread1, thread2;
        int status;
        printf( "Creating thread a\n" );
        status = pthread_create( &thread1, NULL, locking_thread_a, NULL );
        if ( status )
                err_abort( status, "locking_thread_a" );
        printf( "Creating thread b\n" );
        status = pthread_create( &thread2, NULL, locking_thread_b, NULL );
        if ( status )
                err_abort( status, "locking_thread_b" );
        pthread_exit( NULL );
}
%]
\vspace*{-3ex}
%\end{verbatim}
\caption{The second part of the  program \texttt{deadlock.c} that is
  unable to run to completion.}
\label{prg:deadlock-main-function}
\end{program}

\newpage

\subsection{Some Other Resources}
\label{sec:other-resources}

Some students wanted to know how you check if a mutex is locked
without the calling thread going to sleep if the mutex is already
locked by another thread.  The answer is the \POSIX threads library
function:
\begin{verbatim}
int pthread_mutex_trylock( pthread_mutex_t *MUTEX );
\end{verbatim}
which immediately returns the value \texttt{EBUSY} if the mutex is
locked.  You can see an interesting example from the file
\texttt{backoff.c}, shown on pages 66--69 of Butenhof (see
\cite{bib:But97} below).  You can read \texttt{backoff.c} from the
subject web site at \texttt{http://nicku.org/\allowbreak
  ossi/\allowbreak{}lectures/\allowbreak{}processes/\allowbreak
  programming-posix-threads/\allowbreak{}backoff.c}.

%% \section{References}
%% \label{sec:references}

%%   There are many good sources of information in the library and on the
%%   Web about processes and threads.  Here are some I recommend:
%%   \begin{itemize}
%%   \item\url{http://www.llnl.gov/computing/tutorials/workshops/workshop/pthreads/MAIN.html}

%%   gives a {good online tutorial} about \POSIX threads.
%% \item \url{http://www.humanfactor.com/pthreads/} provides links to a
%%   lot of information about \POSIX threads

%% \item The {best book} about \POSIX threads is
%%   \emph{Programming with POSIX Threads}, David Butenhof,
%%   Addison-Wesley, May 1997.  Even though it was written so long ago,
%%   David wrote much of the \POSIX threads standard, so it really is the
%%   definitive work. It made me laugh, too!
%% \item \emph{Operating Systems: A Modern Perspective: Lab Update}, 2nd
%%   Edition, Gary Nutt, Addison-Wesley, 2002.  A nice text book that
%%   emphasises the practical (like I do!)
%% \end{itemize}

\begin{thebibliography}{widest}
\label{sec:references}
  \item[]There are many good sources of information in the library and on the
  Web about processes and threads.  Here are some I recommend:

  \bibitem[tut]{bib:tut}\url{http://www.llnl.gov/computing/tutorials/workshops/workshop/pthreads/MAIN.html}
  gives a {good online tutorial} about \POSIX threads.
\bibitem[links]{bib:links}\url{http://www.humanfactor.com/pthreads/} provides links to a
  lot of information about \POSIX threads

\bibitem[But97]{bib:But97} The {best book} about \POSIX threads is
  \emph{Programming with POSIX Threads}, David Butenhof,
  Addison-Wesley, May 1997.  Even though it was written so long ago,
  David wrote much of the \POSIX threads standard, so it really is the
  definitive work. It made me laugh, too!
\bibitem[Nut02]{bib:Nut02} \emph{Operating Systems: A Modern Perspective: Lab Update}, 2nd
  Edition, Gary Nutt, Addison-Wesley, 2002.  A nice text book that
  emphasises the practical (like I do!)
\end{thebibliography}


\end{document}