%\documentclass[dvips,ignorenonframetext,handout]{beamer}
\documentclass[dvips,ignorenonframetext]{beamer}

\usepackage[english]{babel}
\usepackage[latin1]{inputenc}
\usepackage{times}
\usepackage[T1]{fontenc}
\usepackage{rtsched}
\usepackage{graphicx}
\usepackage{xmpmulti}
\usepackage{listings}
\usepackage{pst-node}
\usepackage{amsmath}

\mode<handout>
{
\usepackage{pgfpages}
\pgfpagesuselayout{2 on 1}[a4paper, border shrink=5mm]

\setbeamercolor{background canvas}{bg=black!5}
}

\mode<presentation>
{
  \usetheme{default}   
  \usecolortheme{orchid}
  \useinnertheme{rounded}
}

\newcommand{\Ceil}[2]{\ensuremath{\left\lceil \frac{#1}{#2} \right\rceil}}
\newcommand{\Floor}[2]{\ensuremath{\left\lfloor \frac{#1}{#2} \right\rfloor}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%5

\title[Shared Resources and blocking]
{Shared Resources and Blocking in Real-Time Systems}

\author[G. Lipari]{Giuseppe Lipari \\ \url{http://feanor.sssup.it/~lipari}}

\institute[Scuola Superiore Sant'Anna]{Scuola Superiore Sant'Anna -- Pisa}


\subject{Talks}

\pgfdeclareimage[height=0.5cm]{retis_logo}{../retis_logo}

\lstset{language=C, %
basicstyle=\ttfamily\small, %
}

\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
  \frametitle{Outline}
  \tableofcontents
  % You might wish to add the option [pausesections]
\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Priority inversion}


\begin{frame}{Blocking and priority inversion}
  \begin{itemize}
  \item A blocking condition happens when a high priority tasks wants to
    access a resource that is held by a lower priority task.
    
  \item Consider the following example, where $p_1 > p_2$.
  \end{itemize}
  \begin{center}
    \RTGridBegin[height=2cm,width=8cm,numbersize=6]{2}{25}
    \TaskArrDead{2}{0}{20}
    \TaskExecution{2}{0}{2}
    \TaskLock{2}{2}{S}
    \TaskExecution[color=white,execlabel=S]{2}{2}{3}
    \TaskArrDead{1}{3}{16}  
    \TaskExecution{1}{3}{4}
    \TaskLock{1}{4}{S}
    \TaskExecution[color=white,execlabel=S]{2}{4}{7}
    \TaskUnlock{2}{7}{S}
    \TaskExecution[color=white,execlabel=S]{1}{7}{9}
    \TaskUnlock{1}{9}{S}
    \TaskExecution{1}{9}{10}
    \TaskExecution{2}{10}{12}
    \RTGridEnd
  \end{center}
  \vspace{.3cm}
  \begin{itemize}
  \item From time $4$ to $7$, task $\tau_1$ is blocked by a lower priority
    task$\tau_2$; this is a {\em priority inversion}. 

  \item Priority inversion is not avoidable; in fact, $\tau_1$ must wait for
    $\tau_2$ to leave the critical section. 

  \item However, in some cases, the priority inversion could be too large.
  \end{itemize}
\end{frame}

\begin{frame}{Example of priority inversion}
  \begin{itemize}
  \item Consider the following example, with $p_1 > p_2 > p_3$. 
  \end{itemize}
  \begin{center}
    \RTGridBegin[height=3cm,width=8cm,numbersize=6]{3}{25}
    \TaskArrDead{3}{0}{20}
    \TaskExecution{3}{0}{2}
    \TaskLock{3}{2}{S}
    \TaskExecution[color=white,execlabel=S]{3}{2}{3}
    \TaskArrDead{1}{3}{9}  
    \TaskExecution{1}{3}{4}
    \TaskLock{1}{4}{S}
    \TaskExecution[color=white,execlabel=S]{3}{4}{5}
    \TaskArrDead{2}{5}{12}
    \TaskExecution{2}{5}{10}
    \TaskExecution[color=white,execlabel=S]{3}{10}{12}
    \TaskUnlock{3}{12}{S}
    \TaskExecution[color=white,execlabel=S]{1}{12}{14}
    \TaskUnlock{1}{14}{S}
    \TaskExecution{1}{14}{15}
    \TaskExecution{3}{15}{17}
    \RTGridEnd
  \end{center}
  \vspace{.3cm}
  \begin{itemize}
  \item This time the priority inversion is very large: from $4$ to
    $12$.
  \item The problem is that, while $\tau_1$ is blocked, $\tau_2$
    arrives and preempt $\tau_3$ before it can leave the critical
    section. 
  \item If there are other medium priority tasks, they could preempt
    $\tau_3$ as well.
  \item Potentially, the priority inversion could be unbounded!
  \end{itemize}
\end{frame}


\section{Priority Inheritance Protocol}


\begin{frame}{Example}
  \begin{itemize}
  \item In the previous example:
  \end{itemize}
  \begin{center}
    \RTGridBegin[height=3cm,width=8cm,numbersize=6]{3}{25}
    \only<1->{
      \TaskArrDead{3}{0}{20}
      \TaskExecution{3}{0}{2}
      \TaskLock{3}{2}{S}
      \TaskExecution[color=white,execlabel=S]{3}{2}{3}
    }
    \only<+->{%1
      \TaskArrDead{1}{3}{9}  
    }
    \only<+->{%2
      \TaskExecution{1}{3}{4}
      \TaskLock{1}{4}{S}
      \Inherit{1}{3}{4}
    }
    \only<+->{%3
      \TaskExecution[color=white,execlabel=S]{3}{4}{5}
    }
    \only<+->{%4
      \TaskArrDead{2}{5}{12}
    }
    \only<+->{%5
      \TaskExecution[color=white,execlabel=S]{3}{5}{7}
      \TaskUnlock{3}{7}{S}
    }
    \only<+->{%6
      \TaskExecution[color=white,execlabel=S]{1}{7}{9}
      \TaskUnlock{1}{9}{S}
    }
    \only<+->{%7
      \TaskExecution{1}{9}{10}
    }
    \only<+->{%8
      \TaskExecution{2}{10}{15}
    }
    \only<+->{%9
      \TaskExecution{3}{15}{17}
    }
    \RTGridEnd
  \end{center}
  \vspace{.5cm}
  \begin{itemize}
  \item \uncover<4->{Task $\tau_3$ inherits the priority of $\tau_1$}

  \item \uncover<5->{Task $\tau_2$ cannot preempt $\tau_3$ ($p_2 <
      p_1$)}
  \end{itemize}
\end{frame}


\begin{frame}[label=my8]{Multiple inheritance}
  \begin{itemize}
  \item Task $\tau_1$ uses resource $S_1$; Task $\tau_2$ uses $S_1$
    and $S_2$ nested inside $S_1$; Task $\tau_3$ uses only $S_2$.
  \item $p_1 > p_2 > p_3$;
  \end{itemize}
  \begin{center}
    \RTGridBegin[height=3.75cm,width=10cm,numbersize=6]{3}{25}
    \TaskArrDead{3}{0}{24}
    \only<+->{\TaskExecution{3}{0}{1}
      \TaskLock{3}{1}{S$_2$}
      \TaskExecution[color=white,execlabel=S$_2$]{3}{1}{2}
    }
    \only<+->{
      \TaskArrDead{2}{2}{20}
      \TaskExecution{2}{2}{3}
      \TaskLock{2}{3}{S$_1$}
      \TaskExecution[color=white,execlabel=S$_1$]{2}{3}{4} 
    }
    \only<+->{
      \TaskArrDead{1}{4}{15}
      \TaskExecution{1}{4}{5}
      \TaskLock{1}{5}{S$_1$}
    }
    \only<+->{\Inherit{1}{2}{5}}
    \only<+->{
      \TaskExecution[color=white,execlabel=S$_1$]{2}{5}{7} 
      \TaskLock{2}{7}{S$_2$}
    }
    \only<+->{\Inherit{2}{3}{7}}
    \only<+->{
      \TaskExecution[color=white,execlabel=S$_2$]{3}{7}{10}
      \TaskUnlock{3}{10}{S$_2$}
    }
    \only<+->{
      \TaskExecution[color=white,execlabel=S$_2$]{2}{10}{12} 
      \TaskUnlock{2}{12}{S$_2$}
    }
    \only<+->{
      \TaskExecution[color=white,execlabel=S$_1$]{2}{12}{14} 
      \TaskUnlock{2}{14}{S$_1$}
    }
    \only<+->{
      \TaskExecution[color=white,execlabel=S$_1$]{1}{14}{16} 
      \TaskUnlock{1}{16}{S$_1$}
    }
    \only<+->{
      \TaskExecution{1}{16}{17} 
      \TaskExecution{2}{17}{18} 
      \TaskExecution{3}{18}{19} 
    }
    \RTGridEnd
  \end{center}
  \vspace{.25cm}
  \begin{itemize}
  \item<7-> At time $t=7$ task $\tau_3$ inherits the priority of $\tau_2$,
    which at time $5$ had inherited the priority of $\tau_1$. Hence,
    the priority of $\tau_3$ is $p_1$.
  \end{itemize}
\end{frame}


\section{Priority Ceiling}

\begin{frame}[label=my2]
  \frametitle{Multiple blocking example}
  \animate<2-6>
  \begin{center}
    \begin{RTGrid}[height=4cm,width=10cm]{3}{25}
      \only<+->{%1
        \TaskArrival{3}{0}
        \TaskExecution{3}{0}{1}
        \TaskLock{3}{1}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{1}{3}
      }
      \only<+->{%2
        \TaskArrival{2}{3}
        \TaskExecution{2}{3}{4}
        \TaskLock{2}{4}{S$_2$}
        \TaskExecution[color=white,execlabel=S$_2$]{2}{4}{6}
      }
      \only<+->{%3
        \TaskArrival{1}{6}
        \TaskExecution{1}{6}{8}
        \TaskLock{1}{8}{S$_2$}
      }
      \only<+->{%4
        \Inherit{1}{2}{8}
        \TaskExecution[color=white,execlabel=S$_2$]{2}{8}{10}
        \TaskUnlock{2}{10}{S$_2$}
      }
      \only<+->{%5
        \TaskExecution[color=white,execlabel=S$_2$]{1}{10}{12}
        \TaskUnlock{1}{12}{S$_2$}
        \TaskExecution{1}{12}{14}
        \TaskLock{1}{14}{S$_1$}
      }
      \only<+->{%6
        \Inherit{1}{3}{14}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{14}{17}
        \TaskUnlock{3}{18}{S$_1$}
      }
      \only<+->{%7
        \TaskExecution[color=white,execlabel=S$_1$]{1}{18}{20}
        \TaskUnlock{1}{20}{S$_1$}
        \TaskExecution{1}{20}{22}
      }
    \end{RTGrid}
  \end{center}

  \pause
  \begin{itemize}
  \item task $\tau_1$ is blocked twice on two different resources
  \end{itemize}
\end{frame}


\begin{frame}[label=my1]
  \frametitle{Example:}
  $\text{ceil}(S_1) = p_1$  and $\text{ceil}(S_2) = p_1$
  %\animate<2-6>
  \begin{center}
    \begin{RTGrid}[height=4cm,width=10cm]{3}{25}
      \only<+->{%1
        \TaskArrival{3}{0}
        \TaskExecution{3}{0}{1}
        \TaskLock{3}{1}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{1}{3}
      }
      \only<+->{%2
        \TaskArrival{2}{3}
        \TaskExecution{2}{3}{4}
        \TaskLock{2}{4}{S$_2$}
        \Inherit{2}{3}{4}
        %\TaskExecution[color=white,execlabel=S$_2$]{2}{4}{6}
      }
      \only<+->{%3
        \TaskExecution[color=white,execlabel=S$_1$]{3}{4}{6}
        \TaskArrival{1}{6}
        \TaskExecution{1}{6}{8}
        \TaskLock{1}{8}{S$_2$}
        \Inherit{1}{3}{8}
      }
      \only<+->{%4
        \TaskExecution[color=white,execlabel=S$_1$]{3}{8}{10}
        \TaskUnlock{3}{10}{S$_1$}
      }
      \only<+->{%5
        \TaskExecution[color=white,execlabel=S$_2$]{1}{10}{12}
        \TaskUnlock{1}{12}{S$_2$}
        \TaskExecution{1}{12}{14}
        \TaskLock{1}{14}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{1}{14}{16}
        \TaskUnlock{1}{16}{S$_1$}
        \TaskExecution{1}{16}{18}

        \TaskExecution[color=white,execlabel=S$_2$]{2}{18}{22}
        \TaskUnlock{2}{22}{S$_1$}
      }
    \end{RTGrid}
  \end{center}

  \begin{itemize}
  \item<1-> task $\tau_3$ acquires the lock
  \item<2-> task $\tau_2$ is blocked because $p_2 < \text{maxceil} =
    p_1$

  \item<2-> task $\tau_3$ inherits $\tau_2$'s priority

  \item<3-> task $\tau_1$ is blocked for the same reason
  \item<3-> task $\tau_3$ inherits $\tau_1$'s priority

  \item<4-> task $\tau_3$ returns to its original priority, since it is
    not blocking anyone
  \end{itemize}
\end{frame}


\begin{frame}{Blocking}
  In the previous example:
  \begin{center}
    \begin{RTGrid}[height=4cm,width=10cm]{3}{25}
      \only<2>{\RTBox{8}{10}}
      \only<3>{\RTBox{4}{6}}
        \TaskArrival{3}{0}
        \TaskExecution{3}{0}{1}
        \TaskLock{3}{1}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{1}{3}
        \TaskArrival{2}{3}
        \TaskExecution{2}{3}{4}
        \TaskLock{2}{4}{S$_2$}
        \Inherit{2}{3}{4}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{4}{6}
        \TaskArrival{1}{6}
        \TaskExecution{1}{6}{8}
        \TaskLock{1}{8}{S$_2$}
        \Inherit{1}{3}{8}
        \TaskExecution[color=white,execlabel=S$_1$]{3}{8}{10}
        \TaskUnlock{3}{10}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_2$]{1}{10}{12}
        \TaskUnlock{1}{12}{S$_2$}
        \TaskExecution{1}{12}{14}
        \TaskLock{1}{14}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{1}{14}{16}
        \TaskUnlock{1}{16}{S$_1$}
        \TaskExecution{1}{16}{18}

        \TaskExecution[color=white,execlabel=S$_2$]{2}{18}{22}
        \TaskUnlock{2}{22}{S$_1$}
    \end{RTGrid}
  \end{center}
  
  \begin{itemize}
  \item<2-> Blocking time for $\tau_1$: 2

  \item<3-> Blocking time for $\tau_2$: 2

  \item<4-> No multiple blockings!
  \end{itemize}

\end{frame}



\section{Stack Resouce Policy}


\begin{frame}[label=my3]
  \frametitle{Example}
  \begin{center}
    \begin{RTGrid}[height=4cm,width=10cm]{3}{25}
      \only<+->{%1
        \TaskArrival{3}{0}
        \TaskExecution{3}{0}{1}
        \TaskLock{3}{1}{S$_1$}
      }
      \only<+->{%2
        \TaskExecution[color=white,execlabel=S$_1$]{3}{1}{3}
        \TaskArrival{2}{3}
      }
      \only<+->{%3
        \TaskExecution[color=white,execlabel=S$_1$]{3}{3}{6}
        \TaskArrival{1}{6}
      }
      \only<+->{%4
        \TaskExecution[color=white,execlabel=S$_1$]{3}{6}{7}
        \TaskUnlock{3}{7}{S$_1$}
      }
      \only<+->{%5
        \TaskExecution{1}{7}{9}
        \TaskLock{1}{9}{S$_2$}
        \TaskExecution[color=white,execlabel=S$_2$]{1}{9}{11}
        \TaskUnlock{1}{11}{S$_2$}
        \TaskExecution{1}{11}{13}
        \TaskLock{1}{13}{S$_1$}
        \TaskExecution[color=white,execlabel=S$_1$]{1}{13}{15}
        \TaskUnlock{1}{15}{S$_1$}
        \TaskExecution{1}{15}{17}

        \TaskLock{2}{17}{S$_2$}
        \TaskExecution{2}{17}{18}
        \TaskExecution[color=white,execlabel=S$_2$]{2}{18}{22}
        \TaskUnlock{2}{22}{S$_1$}
      }
    \end{RTGrid}
  \end{center} 
  \begin{itemize}
  \item<1-> Task $\tau_3$ raises the sys ceiling to $p_1$ 

  \item<2-> Task $\tau_2$ cannot start because $p_2 < \Pi_s = p_1$
  \item<3-> Task $\tau_1$ cannot start because $p_1 = \Pi_s = p_1$
  \item<4-> When task $\tau_3$ unlocks, the sys ceiling goes down, and
    all other tasks can start executing
  \end{itemize}
\end{frame}


\end{document}
