%\documentclass[colorBG,slideColor,troispoints,pdf]{prosper}
\documentclass[colorBG,total,slideColor,pdf]{prosper}
%\documentclass[colorBG,slideColor,ps]{prosper}

\usepackage{alltt,key,xr,cols,rcs,acro,nick,%
  graphicx,varioref,explanation,booktabs,multicol}
\usepackage[nolineno,noindent]{lgrind}

%\definecolor{green}{rgb}{0,1,0}

\RCS $Revision: 1.1 $

\renewcommand*{\bs}{\texttt{\char '134}} % Backslash `\'
%\newcommand*{\labTitle}{LDAP Directories}1
\newcommand*{\subject}{Operating Systems and Systems Integration}
\newcommand*{\emphcolour}[1]{\emph{\red#1}}

\providecommand*{\RPM}{\acro{RPM}\xspace}
\providecommand*{\CD}{\acro{CD}\xspace}
\providecommand*{\IPC}{\acro{IPC}\xspace}
\providecommand*{\UID}{\acro{UID}\xspace}
\providecommand*{\GID}{\acro{GID}\xspace}
\providecommand*{\SMP}{\acro{SMP}\xspace}
\providecommand*{\API}{\acro{API}\xspace}
\providecommand*{\OK}{\acro{OK}\xspace}
\providecommand*{\IETF}{\acro{OK}\xspace}
\providecommand*{\MS}{\acro{MS}\xspace}
\providecommand*{\LILO}{\acro{LILO}\xspace}
\providecommand*{\HCI}{\acro{HCI}\xspace}
\providecommand*{\KDE}{\acro{KDE}\xspace}
\providecommand*{\MBR}{\acro{MBR}\xspace}
\providecommand*{\BSD}{\acro{BSD}\xspace}
\providecommand*{\MB}{\acro{MB}\xspace}
\providecommand*{\LBA}{\acro{LBA}\xspace}


\title{\mbox{}\blue{}Deadlock}%
\subtitle{How to Prevent It}
\author{Nick Urbanik \texttt{<nicku(at)nicku.org>}\\
  \footnotesize{}Copyright Conditions: GNU FDL (see
  \url{http://www.gnu.org/licenses/fdl.html})}%
\institution{A computing department}%
\slideCaption{OSSI --- Deadlock --- ver. \RCSRevision}
%%%\Logo{\includegraphics[width=15mm]{ict-logo-smaller}}

\begin{document}
\maketitle

\begin{slide}{Deadlock}\

  \vspace*{0.1\slideWidth}

\begin{center}\Large
  \mbox{}\blue{}What is deadlock?

    \vspace*{0.01\slideWidth}

    How do we prevent it?

    \vspace*{0.05\slideWidth}

    \normalsize
    Reference:

    \vspace*{0.01\slideWidth}
    
    William Stallings, \emph{Operating Systems and Design Principles},
    4th Edition, 2001, Chapter 6
  \end{center}
\end{slide}

\begin{slide}{What is deadlock?}
  \begin{itemize}
  \item A set of processes or threads is in deadlock if:
  \item Each process is waiting for something that can only be offered
    by another process in the set.
  \item The set of processes is stuck
  \item To the user, they appear to have hung
\end{itemize}
\end{slide}

\begin{slide}{Concurrent Systems}
  \begin{itemize}
  \item A \emphcolour{concurrent system} is one where more than one
    process or thread is executing at the same time
    \begin{itemize}
    \item I.e., is running or is ready to run
    \end{itemize}
  \item Examples:
    \begin{itemize}
    \item operating system
    \item multiprocessing application (e.g., Apache 1.3.x)
    \item multithreaded application (e.g., Apache 2.x.x)
    \end{itemize}
  \item Deadlock can occur in a concurrent system
  \end{itemize}
\end{slide}

\begin{slide}{Starvation}
  \begin{itemize}
  \item \emphcolour{Starvation} is a second danger for concurrent
    systems besides deadlock
  \item Involves {\green{}a process not getting access to a resource}
    because {\green{}other processes are unfairly granted access}
  \item We do not discuss starvation further here.
  \end{itemize}
\end{slide}

\begin{slide}{Gridlock on physical road}
  \begin{itemize}
  \item Deadlock is like gridlock at an intersection
  \item Cars cannot move forward, because the space in front is
    occupied by another car
  \item Cannot move back
  \item Very similar to deadlock in \OS
  \end{itemize}
\end{slide}

\begin{slide}{Gridlock --- 2}
  \begin{center}
    \begin{minipage}[c]{0.37\slideWidth}
      \begin{center}
        \includegraphics[width=0.37\slideWidth]{gridlock-before}%
      \end{center}
    \end{minipage}%
    \hspace{0.06\slideWidth}%
    \begin{minipage}[c]{0.45\slideWidth}
      \begin{center}
        \includegraphics[width=0.45\slideWidth]{gridlock-after}
      \end{center}
    \end{minipage}%
  \end{center}
\end{slide}

\begin{slide}{Requirements for Deadlock}
  \begin{itemize}
  \item Mutual exclusion
    \begin{itemize}
    \item only one process can use a resource at one time
    \item result of locking access to the resource
    \end{itemize}
  \item Hold and Wait
    \begin{itemize}
    \item Processes in the set holding resources given earlier can
      request new resources
    \end{itemize}
  \item No Preemption
    \begin{itemize}
    \item Resources given to process cannot be taken away forcibly by
      OS or other process
    \item the process needs to surrender the resource itself
    \end{itemize}
  \item Circular Wait
    \begin{itemize}
    \item Each process is waiting for a resource held by another
      process in the set (the actual deadlock)
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Deadlock Avoidance}
  \begin{itemize}
  \item The first three conditions are necessary for deadlock to occur
  \item The fourth condition can result because the first three are true
  \item A set of processes can reach an \emphcolour{unsafe} state
    where deadlock is possible
  \item \emphcolour{Deadlock avoidance} involves detecting unsafe
    states and not allocating resources that would cause an unsafe
    state
    \begin{itemize}
    \item {\mbox{}\green{}We do not investigate deadlock avoidance
        here.}
    \end{itemize}
  \item Need balance cost of deadlock against cost of preventing it
  \end{itemize}
\end{slide}

\begin{slide}{Two processes that can deadlock}
  \hspace{0.1\slideWidth}%
  \begin{minipage}[t]{0.47\slideWidth}
\begin{verbatim}
Process P
. . .
Get A
. . .
Get B
. . .
Release A
. . .
Release B
. . .
\end{verbatim}
  \end{minipage}%
  \hspace{0.05\slideWidth}%
  \begin{minipage}[t]{0.37\slideWidth}
\begin{verbatim}
Process Q
. . .
Get B
. . .
Get A
. . .
Release B
. . .
Release A
. . .
\end{verbatim}
  \end{minipage}
\end{slide}

\begin{slide}{Deadlock Example --- 2}
  \begin{center}
    \begin{minipage}[c]{0.7\slideWidth}
      \begin{center}
        \includegraphics[width=0.7\slideWidth]{deadlock-path}%
      \end{center}
    \end{minipage}%
    \begin{minipage}[c]{0.3\slideWidth}
      \tiny
      \begin{itemize}
      \item[\textbf{1.}] Only Q executes.
      \item[\textbf{6.}] Only P executes.
      \item[\textbf{2.}] Q gets B, then A.  P blocks waiting for A,
        resumes after Q releases A
      \item[\textbf{5.}] P gets A, then B.  Q blocks waiting for B,
        resumes after P releases B
      \end{itemize}
    \end{minipage}
  \end{center}
\end{slide}

\begin{slide}{Deadlock Example --- 3}
  \begin{itemize}
  \item {\mbox{}\blue{}Path 1}: only Q executes, no deadlock
  \item {\mbox{}\blue{}Path 6}: only P executes, no deadlock
  \item {\mbox{}\blue{}Path 2}: Q gets B, then A.  P executes, blocks
    waiting for A, resumes after Q releases A.  No deadlock.
  \item {\mbox{}\blue{}Path 5}: P gets A, then B.  Q executes, blocks
    waiting for B, resumes after P releases B.  No deadlock.
  \end{itemize}
\end{slide}

\begin{slide}{Deadlock Example --- 4}
  \begin{itemize}
  \item No problem if only P or Q executing
  \item No problem if Q gets B then A, P executes, but blocks waiting
    for A.  Q releases A and B.  P can then run OK
  \item No problem if either process gets both resources before the
    other starts.
  \end{itemize}
\end{slide}

\begin{slide}{Deadlock Example --- 5}
  \begin{itemize}
  \item But if:
  \item Q gets B, then P gets A ({\blue{}Path 3}), or
  \item P gets A, then Q gets B {\blue{}(Path 4})
  \item Deadlock must happen since both will block waiting for the other.
  \end{itemize}
\end{slide}

\begin{slide}{How to prevent deadlock?}
  \begin{itemize}
  \item Two main methods:
    \begin{itemize}
    \item Indirect method: prevent one of the first three conditions
    \end{itemize}
  \item Direct method:
    \begin{itemize}
    \item Prevent the last condition.
    \end{itemize}
  \item All methods of prevention may have some {\red{}cost} in
    \begin{itemize}
    \item execution time, or
    \item more limited access to resources
    \item design and programming time
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Indirect: preventing mutual exclusion}
  \begin{itemize}
  \item This condition depends on the nature of the resource.
  \item If resource must be locked, then the \OS must support mutual
    exclusion.
    \begin{itemize}
    \item If concurrent processes share data, there is a {\red{}danger
        of data corruption}
    \item i.e., two or more threads both write to same file at the
      same time
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Indirect: prevent hold \& wait --- 1}
  \begin{itemize}
  \item Process does not proceed until allocated all resources it will
    ever need.
  \item Wasteful, since:
    \begin{itemize}
    \item process may wait much longer for all resources rather than
      enough to start with.
    \item Resources locked while not being used.
    \end{itemize}
  \end{itemize}
\end{slide}

\begin{slide}{Indirect: prevent hold \& wait --- 2}
  \begin{itemize}
  \item Another way to prevent hold and wait:
  \item Process holds only one resource at one time
  \item Example: modify P as shown
  \item Note no deadlock possible even if do not change Q
  \end{itemize}
\end{slide}

\begin{slide}{Indirect: prevent hold \& wait --- 3}
  \begin{itemize}
  \item Another strategy is for a thread or process to test if
    additional resources are available before waiting for them
  \item If any resource is not available,
    \begin{itemize}
    \item then release all resources,
    \item yield the \CPU and then try again
      \begin{itemize}
      \item yield = give up, i.e, thread voluntarily goes to the end
        of the scheduler queue for threads of its own priority
      \item means another thread gets the \CPU instead
      \end{itemize}
    \end{itemize}
  \item See \texttt{backoff.c} from \emph{Programming with POSIX
      Threads}, pp. 67--69
  \end{itemize}
\end{slide}

\begin{slide}{Indirect: prevent hold \& wait 3}
  \hspace{0.1\slideWidth}%
  \begin{minipage}[t]{0.47\slideWidth}
\begin{verbatim}
Process P
. . .
Get A
. . .
Release A
. . .
Get B
. . .
Release B
. . .
\end{verbatim}
  \end{minipage}%
  \hspace{0.05\slideWidth}%
  \begin{minipage}[t]{0.37\slideWidth}
\begin{verbatim}
Process Q
. . .
Get B
. . .
Get A
. . .
Release B
. . .
Release A
. . .
\end{verbatim}
  \end{minipage}
\end{slide}

\begin{slide}{Indirect: prevent hold \& wait 4}
  \begin{center}
    \begin{minipage}[c]{0.7\slideWidth}
      \begin{center}
        \includegraphics[width=0.7\slideWidth]{deadlock-path-no-hw2}%
      \end{center}
    \end{minipage}%
    \begin{minipage}[c]{0.3\slideWidth}
      \tiny
      \begin{itemize}
      \item some paths result in P or Q being \emphcolour{temporarily}
        blocked
      \item but the other process can always complete
      \item no chance of deadlock
      \end{itemize}
    \end{minipage}
  \end{center}
\end{slide}

\begin{slide}{Indirect: allow preemption}
  \begin{itemize}
  \item OS or concurrent application could order a hierarchy of
    processes
  \item Highest priority could always get resources used by a lower
    priority process.
  \item Drawback: must be able to resume the preempted task at the
    point where the resource was taken away.
  \end{itemize}
\end{slide}

\begin{slide}{Direct: prevent circular wait}
  \begin{itemize}
  \item Define an order in which resources are always requested
  \item For example, in previous example, if always allocate A then B,
    no deadlock can occur.
  \item This method is a part of strategy used in Linux and Windows
    operating system design
  \end{itemize}
\end{slide}

\begin{slide}{Direct: prevent circular wait --- 2}
  \hspace{0.1\slideWidth}%
  \begin{minipage}[t]{0.47\slideWidth}
\begin{verbatim}
Process P
. . .
Get A
. . .
Get B
. . .
Release A
. . .
Release B
. . .
\end{verbatim}
  \end{minipage}%
  \hspace{0.05\slideWidth}%
  \begin{minipage}[t]{0.37\slideWidth}
\begin{verbatim}
Process Q
. . .
Get A
. . .
Get B
. . .
Release A
. . .
Release B
. . .
\end{verbatim}
  \end{minipage}
\end{slide}

\begin{slide}{Direct: prevent circular wait --- 3}
  \begin{center}
    \begin{minipage}[c]{0.7\slideWidth}
      \begin{center}
        \includegraphics[width=0.7\slideWidth]{deadlock-path-no-wait}%
      \end{center}
    \end{minipage}%
    \begin{minipage}[c]{0.3\slideWidth}
      \tiny
      \begin{itemize}
      \item some paths result in P or Q being \emphcolour{temporarily}
        blocked
      \item but the other process can always complete
      \item again, no possibility of deadlock
      \end{itemize}
    \end{minipage}
  \end{center}
\end{slide}

\begin{slide}{Conclusion}
  \begin{itemize}
  \item Deadlock is very undesirable
  \item Occurs within a set of processes or threads
  \item The processes ``lock up'', each process waiting for the other.
  \item 4 conditions \emphcolour{all} required for deadlock
  \item deadlock avoidance detects and avoids \emphcolour{unsafe}
    states
  \item Prevention involves removing/preventing \emphcolour{one} or
    more of these conditions
  \end{itemize}
\end{slide}

\end{document}