(*<*)
theory Slides1
imports "../CpsG" "../ExtGG" "~~/src/HOL/Library/LaTeXsugar"
begin
notation (latex output)
set ("_") and
Cons ("_::/_" [66,65] 65)
ML {*
open Printer;
show_question_marks_default := false;
*}
notation (latex output)
Cons ("_::_" [78,77] 73) and
vt ("valid'_state") and
runing ("running") and
birthtime ("last'_set") and
If ("(\<^raw:\textrm{>if\<^raw:}> (_)/ \<^raw:\textrm{>then\<^raw:}> (_)/ \<^raw:\textrm{>else\<^raw:}> (_))" 10) and
Prc ("'(_, _')") and
holding ("holds") and
waiting ("waits") and
Th ("T") and
Cs ("C") and
readys ("ready") and
depend ("RAG") and
preced ("prec") and
cpreced ("cprec") and
dependents ("dependants") and
cp ("cprec") and
holdents ("resources") and
original_priority ("priority") and
DUMMY ("\<^raw:\mbox{$\_\!\_$}>")
(*>*)
text_raw {*
\renewcommand{\slidecaption}{Nanjing, P.R. China, 1 August 2012}
\newcommand{\bl}[1]{#1}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\Large Priority Inheritance Protocol \\[-3mm]
\Large Proved Correct \\[0mm]
\end{tabular}}
\begin{center}
\small Xingyuan Zhang \\
\small \mbox{PLA University of Science and Technology} \\
\small \mbox{Nanjing, China}
\end{center}
\begin{center}
\small joint work with \\
Christian Urban \\
Kings College, University of London, U.K.\\
Chunhan Wu \\
My Ph.D. student now working for Christian\\
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\large Prioirty Inheritance Protocol (PIP)}
\large
\begin{itemize}
\item Widely used in Real-Time OSs \pause
\item One solution of \textcolor{red}{`Priority Inversion'} \pause
\item A flawed manual correctness proof (1990)\pause
\begin{itemize} \large
\item {Notations with no precise definition}
\item {Resorts to intuitions}
\end{itemize} \pause
\item Formal treatments using model-checking \pause
\begin{itemize} \large
\item {Applicable to small size system models}
\item { Unhelpful for human understanding }
\end{itemize} \pause
\item Verification of PCP in PVS (2000)\pause
\begin{itemize} \large
\item {A related protocol}
\item {Priority Ceiling Protocol}
\end{itemize}
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Our Motivation}
\large
\begin{itemize}
\item Undergraduate OS course in our university \pause
\begin{itemize}
\item {\large Experiments using instrutional OSs }
\item {\large PINTOS (Stanford) is chosen }
\item {\large Core project: Implementing PIP in it}
\end{itemize} \pause
\item Understanding is crucial for the implemention \pause
\item Existing literature of little help \pause
\item Some mention the complication
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\mbox{Some excerpts}}
\begin{quote}
``Priority inheritance is neither ef$\!$ficient nor reliable.
Implementations are either incomplete (and unreliable)
or surprisingly complex and intrusive.''
\end{quote}\medskip
\pause
\begin{quote}
``I observed in the kernel code (to my disgust), the Linux
PIP implementation is a nightmare: extremely heavy weight,
involving maintenance of a full wait-for graph, and requiring
updates for a range of events, including priority changes and
interruptions of wait operations.''
\end{quote}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Our Aims}
\large
\begin{itemize}
\item Formal specification at appropriate abstract level,
convenient for:
\begin{itemize} \large
\item Constructing interactive proofs
\item Clarifying the underlying ideas
\end{itemize} \pause
\item Theorems usable to guide implementation, critical point:
\begin{itemize} \large
\item Understanding the relationship with real OS code \pause
\item Not yet formalized
\end{itemize}
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Real-Time OSes}
\large
\begin{itemize}
\item Purpose: gurantee the most urgent task to be processed in time
\item Processes have priorities\\
\item Resources can be locked and unlocked
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Problem}
\Large
\begin{center}
\begin{tabular}{l}
\alert{H}igh-priority process\\[4mm]
\onslide<2->{\alert{M}edium-priority process}\\[4mm]
\alert{L}ow-priority process\\[4mm]
\end{tabular}
\end{center}
\onslide<3->{
\begin{itemize}
\item \alert{Priority Inversion} @{text "\<equiv>"} \alert{H $<$ L}
\item<4> avoid indefinite priority inversion
\end{itemize}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Priority Inversion}
\begin{center}
\includegraphics[scale=0.4]{PriorityInversion.png}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Mars Pathfinder Mission 1997}
\Large
\begin{center}
\includegraphics[scale=0.2]{marspath1.png}
\includegraphics[scale=0.22]{marspath3.png}
\includegraphics[scale=0.4]{marsrover.png}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Solution}
\Large
\alert{Priority Inheritance Protocol (PIP):}
\begin{center}
\begin{tabular}{l}
\alert{H}igh-priority process\\[4mm]
\textcolor{gray}{Medium-priority process}\\[4mm]
\alert{L}ow-priority process\\[21mm]
{\normalsize (temporarily raise its priority)}
\end{tabular}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{A Correctness ``Proof'' in 1990}
\Large
\begin{itemize}
\item a paper$^\star$
in 1990 ``proved'' the correctness of an algorithm for PIP\\[5mm]
\end{itemize}
\normalsize
\begin{quote}
\ldots{}after the thread (whose priority has been raised) completes its
critical section and releases the lock, it ``returns to its original
priority level''.
\end{quote}\bigskip
\small
$^\star$ in IEEE Transactions on Computers
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{}
\Large
\begin{center}
\begin{tabular}{l}
\alert{H}igh-priority process 1\\[2mm]
\alert{H}igh-priority process 2\\[8mm]
\alert{L}ow-priority process
\end{tabular}
\end{center}
\onslide<2->{
\begin{itemize}
\item Solution: \\Return to highest \alert{remaining} priority
\end{itemize}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Event Abstraction}
\begin{itemize}\large
\item Use Inductive Approach of L. Paulson \pause
\item System is event-driven \pause
\item A \alert{state} is a list of events
\end{itemize}
\pause
\begin{center}
\includegraphics[scale=0.4]{EventAbstract.png}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Events}
\Large
\begin{center}
\begin{tabular}{l}
Create \textcolor{gray}{thread priority}\\
Exit \textcolor{gray}{thread}\\
Set \textcolor{gray}{thread priority}\\
Lock \textcolor{gray}{thread cs}\\
Unlock \textcolor{gray}{thread cs}\\
\end{tabular}
\end{center}\medskip
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Precedences}
\large
\begin{center}
\begin{tabular}{l}
@{thm preced_def[where thread="th"]}
\end{tabular}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{RAGs}
\begin{center}
\newcommand{\fnt}{\fontsize{7}{8}\selectfont}
\begin{tikzpicture}[scale=1]
%%\draw[step=2mm] (-3,2) grid (1,-1);
\node (A) at (0,0) [draw, rounded corners=1mm, rectangle, very thick] {@{text "th\<^isub>0"}};
\node (B) at (2,0) [draw, circle, very thick, inner sep=0.4mm] {@{text "cs\<^isub>1"}};
\node (C) at (4,0.7) [draw, rounded corners=1mm, rectangle, very thick] {@{text "th\<^isub>1"}};
\node (D) at (4,-0.7) [draw, rounded corners=1mm, rectangle, very thick] {@{text "th\<^isub>2"}};
\node (E) at (6,-0.7) [draw, circle, very thick, inner sep=0.4mm] {@{text "cs\<^isub>2"}};
\node (E1) at (6, 0.2) [draw, circle, very thick, inner sep=0.4mm] {@{text "cs\<^isub>3"}};
\node (F) at (8,-0.7) [draw, rounded corners=1mm, rectangle, very thick] {@{text "th\<^isub>3"}};
\draw [<-,line width=0.6mm] (A) to node [pos=0.54,sloped,above=-0.5mm] {\fnt{}holding} (B);
\draw [->,line width=0.6mm] (C) to node [pos=0.4,sloped,above=-0.5mm] {\fnt{}waiting} (B);
\draw [->,line width=0.6mm] (D) to node [pos=0.4,sloped,below=-0.5mm] {\fnt{}waiting} (B);
\draw [<-,line width=0.6mm] (D) to node [pos=0.54,sloped,below=-0.5mm] {\fnt{}holding} (E);
\draw [<-,line width=0.6mm] (D) to node [pos=0.54,sloped,above=-0.5mm] {\fnt{}holding} (E1);
\draw [->,line width=0.6mm] (F) to node [pos=0.45,sloped,below=-0.5mm] {\fnt{}waiting} (E);
\end{tikzpicture}
\end{center}\bigskip
\begin{center}
\begin{minipage}{0.8\linewidth}
\raggedleft
@{thm cs_depend_def}
\end{minipage}
\end{center}\pause
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Good Next Events}
%%\large
\begin{center}
@{thm[mode=Rule] thread_create[where thread=th]}\bigskip
@{thm[mode=Rule] thread_exit[where thread=th]}\bigskip
@{thm[mode=Rule] thread_set[where thread=th]}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Good Next Events}
%%\large
\begin{center}
@{thm[mode=Rule] thread_P[where thread=th]}\bigskip
@{thm[mode=Rule] thread_V[where thread=th]}\bigskip
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
(*<*)
context extend_highest_gen
begin
(*>*)
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\mbox{\large Theorem: ``No indefinite priority inversion''}}
\pause
Theorem $^\star$: If th is the thread with the highest precedence in state
@{text "s"}: \pause
\begin{center}
\textcolor{red}{@{thm highest})}
\end{center}
\pause
and @{text "th"} is blocked by a thread @{text "th'"} in
a future state @{text "s'"} (with @{text "s' = t@s"}): \pause
\begin{center}
\textcolor{red}{@{text "th' \<in> running (t@s)"} and @{text "th' \<noteq> th"}} \pause
\end{center}
\fbox{ \hspace{1em} \pause
\begin{minipage}{0.95\textwidth}
\begin{itemize}
\item @{text "th'"} did not hold or wait for a resource in s:
\begin{center}
\textcolor{red}{@{text "\<not>detached s th'"}}
\end{center} \pause
\item @{text "th'"} is running with the precedence of @{text "th"}:
\begin{center}
\textcolor{red}{@{text "cp (t@s) th' = preced th s"}}
\end{center}
\end{itemize}
\end{minipage}}
\pause
\small
$^\star$ modulo some further assumptions\bigskip\pause
It does not matter which process gets a released lock.
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Implementation}
s $=$ current state; @{text "s'"} $=$ next state $=$ @{text "e#s"}\bigskip\bigskip
When @{text "e"} = \alert{Create th prio}, \alert{Exit th}
\begin{itemize}
\item @{text "RAG s' = RAG s"}
\item No precedence needs to be recomputed
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Implementation}
s $=$ current state; @{text "s'"} $=$ next state $=$ @{text "e#s"}\bigskip\bigskip
When @{text "e"} = \alert{Set th prio}
\begin{itemize}
\item @{text "RAG s' = RAG s"}
\item No precedence needs to be recomputed
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Implementation}
s $=$ current state; @{text "s'"} $=$ next state $=$ @{text "e#s"}\bigskip\bigskip
When @{text "e"} = \alert{Unlock th cs} where there is a thread to take over
\begin{itemize}
\item @{text "RAG s' = RAG s - {(C cs, T th), (T th', C cs)} \<union> {(C cs, T th')}"}
\item we have to recalculate the precedence of the direct descendants
\end{itemize}\bigskip
\pause
When @{text "e"} = \alert{Unlock th cs} where no thread takes over
\begin{itemize}
\item @{text "RAG s' = RAG s - {(C cs, T th)}"}
\item no recalculation of precedences
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Implementation}
s $=$ current state; @{text "s'"} $=$ next state $=$ @{text "e#s"}\bigskip\bigskip
When @{text "e"} = \alert{Lock th cs} where cs is not locked
\begin{itemize}
\item @{text "RAG s' = RAG s \<union> {(C cs, T th')}"}
\item no recalculation of precedences
\end{itemize}\bigskip
\pause
When @{text "e"} = \alert{Lock th cs} where cs is locked
\begin{itemize}
\item @{text "RAG s' = RAG s - {(T th, C cs)}"}
\item we have to recalculate the precedence of the descendants
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Conclusion}
\begin{itemize} \large
\item Aims fulfilled \medskip \pause
\item Alternative way \pause
\begin{itemize}
\item using Isabelle/HOL in OS code development \medskip
\item through the Inductive Approach
\end{itemize} \pause
\item Future research \pause
\begin{itemize}
\item scheduler in RT-Linux\medskip
\item multiprocessor case\medskip
\item other ``nails'' ? (networks, \ldots) \medskip \pause
\item Refinement to real code and relation between implementations
\end{itemize}
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
text_raw {*
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Questions?}
\begin{itemize} \large
\item Thank you for listening!
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
*}
(*<*)
end
end
(*>*)