slides/slides09.tex
author Christian Urban <urbanc@in.tum.de>
Sun, 24 Sep 2017 18:03:21 +0100
changeset 529 9b01bb695b22
parent 518 e1fcfba63a31
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     1
\documentclass[dvipsnames,14pt,t]{beamer}
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
     2
\usepackage{../slides}
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
     3
\usepackage{../langs}
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
     4
\usepackage{../graphics}
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
     5
\usepackage{../grammar}
337
92a718b88e14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
     6
\usepackage{soul}
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     7
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
     8
% beamer stuff 
381
036a762b02cf updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
     9
\renewcommand{\slidecaption}{SEN 09, King's College London}
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    10
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    11
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    12
\begin{document}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    13
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    14
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    15
\begin{frame}[t]
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    16
\frametitle{%
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    17
  \begin{tabular}{@ {}c@ {}}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    18
  \\
381
036a762b02cf updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 337
diff changeset
    19
  \LARGE Security Engineering (9)\\[-3mm] 
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    20
  \end{tabular}}\bigskip\bigskip\bigskip
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    21
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
    22
  \normalsize
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    23
  \begin{center}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    24
  \begin{tabular}{ll}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    25
  Email:  & christian.urban at kcl.ac.uk\\
518
e1fcfba63a31 updated
Christian Urban <urbanc@in.tum.de>
parents: 434
diff changeset
    26
  Office: & N7.07 (North Wing, Bush House)\\
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    27
  Slides: & KEATS (also homework is there)\\
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    28
  \end{tabular}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    29
  \end{center}
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    30
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    31
\end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    32
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    33
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    34
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    35
  \begin{frame}[c]
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
    36
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    37
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    38
  \includegraphics[scale=0.6]{../pics/bridge-limits.png}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    39
  \end{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    40
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    41
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    42
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
    43
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    44
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    45
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    46
  \frametitle{Old-Fashioned Eng.~vs.~CS}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    47
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    48
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    49
  \begin{tabular}{@{}cc@{}}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    50
  \begin{tabular}{@{}p{5.2cm}} 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    51
  \includegraphics[scale=0.058]{../pics/towerbridge.jpg}\\ 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    52
  {\bf bridges}: \\
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    53
  \raggedright\small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    54
  engineers can ``look'' at a bridge and have a pretty good
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    55
  intuition about whether it will hold up or not\\ 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    56
  (redundancy; predictive theory)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    57
  \end{tabular} &
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    58
  \begin{tabular}{p{5cm}} 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    59
  \includegraphics[scale=0.265]{../pics/code.jpg}\\
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    60
  \raggedright
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    61
  {\bf code}: \\
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    62
  \raggedright\small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    63
  programmers have very little intuition about their code; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    64
  often it is too expensive to have redundancy;
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    65
  not ``continuous'' 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    66
  \end{tabular}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    67
  \end{tabular}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    68
  \end{center}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
    69
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    70
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    71
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    72
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
    73
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    74
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    75
\begin{frame}[c]
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    76
\frametitle{Trusting Computing Base}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    77
  
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    78
When considering whether a system meets some security
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    79
objectives, it is important to consider which parts of that
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    80
system are trusted in order to meet that objective (TCB).
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    81
\bigskip\pause
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    82
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    83
The smaller the TCB, the less effort it takes to get
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    84
some confidence that it is trustworthy, by doing a code 
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    85
review or by performing some (penetration) testing.
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    86
\bigskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    87
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    88
\footnotesize
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    89
CPU, compiler, libraries, OS, NP $\not=$ P,
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    90
random number generator, \ldots
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    91
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    92
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    93
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    94
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
    95
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    96
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    97
  \frametitle{Dijkstra on Testing}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    98
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
    99
  \begin{bubble}[10cm]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   100
  ``Program testing can be a very effective way to show the
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   101
  presence of bugs, but it is hopelessly inadequate for showing
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   102
  their absence.''
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   103
  \end{bubble}\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   104
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   105
  unfortunately attackers exploit bugs (Satan's computer vs 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   106
  Murphy's)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   107
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   108
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   109
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   110
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   111
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   112
\begin{frame}[c]
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   113
\frametitle{\Large Proving Programs to be Correct}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   114
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   115
\begin{bubble}[10cm]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   116
\small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   117
{\bf Theorem:} There are infinitely many prime 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   118
numbers.\medskip\\
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   119
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   120
{\bf Proof} \ldots\\
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   121
\end{bubble}\bigskip
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   122
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   123
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   124
similarly\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   125
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   126
\begin{bubble}[10cm]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   127
\small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   128
{\bf Theorem:} The program is doing what 
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   129
it is supposed to be doing.\medskip
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   130
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   131
{\bf Long, long proof} \ldots\\
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   132
\end{bubble}\bigskip\medskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   133
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   134
\small This can be a gigantic proof. The only hope is to have
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   135
help from the computer. `Program' is here to be understood to be
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   136
quite general (protocols, OS, \ldots).
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   137
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   138
\end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   139
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   140
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   141
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   142
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   143
  \frametitle{\Large{}Mars Pathfinder Mission 1997}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   144
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   145
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   146
  \includegraphics[scale=0.15]{../pics/marspath1.png}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   147
  \includegraphics[scale=0.16]{../pics/marspath3.png}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   148
  \includegraphics[scale=0.3]{../pics/marsrover.png}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   149
  \end{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   150
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   151
  \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   152
  \item despite NASA's famous testing procedures, the lander crashed frequently on Mars
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   153
  \item a scheduling algorithm was not used in the OS
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   154
  \end{itemize}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   155
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   156
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   157
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   158
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
   159
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   160
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   161
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   162
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   163
  \begin{textblock}{11}(1,3)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   164
  \begin{tabular}{@{\hspace{-10mm}}l}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   165
  \begin{tikzpicture}[scale=1.1]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   166
  \node at (-2.5,-1.5) {\textcolor{white}{a}};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   167
  \node at (8,4) {\textcolor{white}{a}};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   168
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   169
    
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
   170
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   171
  \only<1>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   172
   \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   173
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   174
  \only<2>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   175
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   176
   \draw[fill, blue!50] (3,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   177
   \draw[fill, blue!100] (2,3) rectangle (3,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   178
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   179
  \only<3>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   180
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   181
   \draw[fill, blue!50] (3,0) rectangle (4.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   182
   \draw[fill, blue!50] (5.5,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   183
   \draw[fill, blue!100] (2,3) rectangle (3,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   184
   \draw[fill, blue!100] (4.5,3) rectangle (5.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   185
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   186
  \only<4>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   187
   \node at (2.5,0.9) {\small locked a resource};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   188
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   189
   \draw[blue!50, very thick] (2,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   190
   \draw[blue!100, very thick] (2,3) rectangle (3, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   191
   \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   192
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   193
  \only<5>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   194
   \node at (2.5,0.9) {\small locked a resource};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   195
   \draw[fill, blue!50] (1,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   196
   \draw[blue!100, fill] (4,3) rectangle (5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   197
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   198
  \only<6>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   199
   \node at (2.5,0.9) {\small locked a resource};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   200
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   201
   \draw[blue!50, very thick] (2,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   202
   \draw[blue!100, very thick] (2,3) rectangle (3, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   203
   \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   204
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   205
  \only<7>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   206
   \node at (2.5,0.9) {\small locked a resource};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   207
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   208
   \draw[blue!50, very thick] (2.5,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   209
   \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   210
   \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   211
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   212
  \only<8>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   213
   \node at (2.5,0.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   214
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   215
   \draw[blue!50, very thick] (2.5,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   216
   \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   217
   \draw[blue!100, very thick] (2.5,3) rectangle (3.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   218
   \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   219
   \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   220
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   221
  \only<9>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   222
   \node at (2.5,0.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   223
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   224
   \draw[blue!50, very thick] (3.5,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   225
   \draw[blue!100, very thick] (3.5,3) rectangle (4.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   226
   \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   227
   \draw[red, <-, line width = 2mm] (3.5,-0.1) -- (3.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   228
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   229
  \only<10>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   230
   \node at (2.5,0.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   231
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   232
   \draw[blue!50, very thick] (3.5,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   233
   \draw[blue!100, very thick] (3.5,3) rectangle (4.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   234
   \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   235
   \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   236
   \draw[red, <-, line width = 2mm] (3.5,-0.1) -- (3.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   237
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   238
  \only<11>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   239
   \node at (2.5,0.9) {\small locked a resource};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   240
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   241
   \draw[blue!50, very thick] (4.5,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   242
   \draw[blue!100, very thick] (4.5,3) rectangle (5.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   243
   \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   244
   \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   245
   \draw[red, <-, line width = 2mm] (4.5,-0.1) -- (4.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   246
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   247
  \only<12>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   248
   \node at (2.5,0.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   249
   \draw[fill, blue!50] (1,0) rectangle (2.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   250
   \draw[blue!50, very thick] (5.5,0) rectangle (7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   251
   \draw[blue!100, very thick] (5.5,3) rectangle (6.5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   252
   \draw[red, fill] (2.5,1.5) rectangle (3.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   253
   \draw[red, fill] (3.55,1.5) rectangle (4.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   254
   \draw[red, fill] (4.55,1.5) rectangle (5.5,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   255
   \draw[red, <-, line width = 2mm] (5.5,-0.1) -- (5.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   256
   \node [anchor=base] at (6.3, 1.8) {\Large\ldots};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   257
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   258
  \only<13>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   259
   \node at (2.5,0.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   260
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   261
   \draw[blue!50, very thick] (2,0) rectangle (4,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   262
   \draw[blue!100, very thick] (2,3) rectangle (3, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   263
   \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   264
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   265
  \only<14>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   266
   \node at (2.5,3.9) {\small locked a resource}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   267
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   268
   \draw[blue!50, fill] (2,3) rectangle (4,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   269
   \draw[blue!100, very thick] (4,3) rectangle (5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   270
   \draw[blue!50, ->, line width = 2mm] (2,1) -- (2, 2.5);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   271
   \draw[red, <-, line width = 2mm] (2,-0.1) -- (2, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   272
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   273
  \only<15>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   274
   \node at (2.5,3.9) {\small locked a resource};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   275
   \draw[fill, blue!50] (1,0) rectangle (2,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   276
   \draw[blue!50, fill] (2,3) rectangle (4,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   277
   \draw[blue!100, very thick] (4,3) rectangle (5, 3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   278
   \draw[red, <-, line width = 2mm] (2.5,-0.1) -- (2.5, -1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   279
   \draw[red, very thick] (2.5,1.5) rectangle (3.5,2.1); 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   280
  }
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   281
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   282
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   283
  \draw[very thick,->](0,0) -- (8,0);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   284
  \node [anchor=base] at (8, -0.3) {\scriptsize time};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   285
  \node [anchor=base] at (0, -0.3) {\scriptsize 0};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   286
  \node [anchor=base] at (-1.2, 0.2) {\small low priority};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   287
  \only<2->{\node [anchor=base] at (-1.2, 3.2) {\small high priority};}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   288
  \only<8->{\node [anchor=base] at (-1.5, 1.7) {\small medium pr.};}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   289
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   290
  \end{tikzpicture}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   291
  \end{tabular}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   292
  \end{textblock}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   293
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   294
  \begin{textblock}{0}(2.5,13)%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   295
  \small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   296
  \onslide<3->{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   297
  \begin{bubble}[8cm]%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   298
  Scheduling: You want to avoid that a high 
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   299
  priority process is starved indefinitely.
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   300
  \end{bubble}}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   301
  \end{textblock}
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
   302
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   303
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   304
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   305
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   306
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   307
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   308
  \frametitle{\Large Priority Inheritance Scheduling}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   309
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   310
  \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   311
  \item Let a low priority process $L$ temporarily inherit 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   312
    the high priority of $H$ until $L$ leaves the critical 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   313
    section unlocking the resource.\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   314
  \item Once the resource is unlocked $L$ returns to its original 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   315
    priority level.
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   316
  \end{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   317
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   318
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   319
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   320
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   321
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   322
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   323
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   324
  \begin{textblock}{11}(1,3)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   325
  \begin{tabular}{@{\hspace{-10mm}}l}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   326
  \begin{tikzpicture}[scale=1.1]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   327
  \node at (-2.5,-1.5) {\textcolor{white}{a}};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   328
  \node at (8,4) {\textcolor{white}{a}};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   329
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   330
  \only<1>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   331
    \draw[fill, blue!50] (1,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   332
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   333
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   334
    \node at (3.5,0.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   335
    \node at (5.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   336
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   337
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   338
    \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   339
    \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   340
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   341
  \only<2>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   342
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   343
    \draw[very thick, blue!50] (3,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   344
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   345
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   346
    \node at (3.5,0.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   347
    \node at (5.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   348
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   349
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   350
    \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   351
    \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   352
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   353
  \only<3>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   354
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   355
    \draw[very thick, blue!50] (3,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   356
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   357
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   358
    \node at (3.5,0.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   359
    \node at (5.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   360
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   361
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   362
    \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   363
    \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   364
    \draw[very thick,blue!100] (3,3) rectangle (4,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   365
    \node at (3.5,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   366
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   367
  \only<4>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   368
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   369
    \draw[very thick, blue!50] (3,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   370
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   371
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   372
    \node at (3.5,0.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   373
    \node at (5.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   374
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   375
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   376
    \draw[very thick,blue!100] (3.5,0) -- (3.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   377
    \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   378
    \draw[very thick,blue!100] (3,3) rectangle (4,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   379
    \node at (3.5,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   380
    \draw[very thick,blue!100] (4,3) rectangle (5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   381
    \node at (4.5,3.3) {\small $B$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   382
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   383
  \only<5>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   384
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   385
    \draw[very thick, blue!50] (3,3) rectangle (6,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   386
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   387
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   388
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   389
    \node at (5.7,3.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   390
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   391
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   392
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   393
    \draw[very thick,blue!100] (5.7,3) -- (5.7,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   394
    \draw[very thick,blue!100] (6,3) rectangle (7,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   395
    \node at (6.5,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   396
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   397
    \node at (7.5,3.3) {\small $B$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   398
    \draw[blue!50, ->, line width = 2mm] (3,1) -- (3, 2.5);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   399
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   400
  \only<6>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   401
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   402
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   403
    \draw[very thick, blue!50] (3.5,3) rectangle (6,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   404
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   405
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   406
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   407
    \node at (5.7,3.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   408
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   409
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   410
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   411
    \draw[very thick,blue!100] (5.7,3) -- (5.7,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   412
    \draw[very thick,blue!100] (6,3) rectangle (7,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   413
    \node at (6.5,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   414
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   415
    \node at (7.5,3.3) {\small $B$}; 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   416
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   417
  \only<7>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   418
   \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   419
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   420
    \draw[very thick, blue!50] (3.5,0) rectangle (6,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   421
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   422
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   423
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   424
    \node at (5.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   425
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   426
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   427
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   428
    \draw[very thick,blue!100] (5.7,0) -- (5.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   429
    \draw[very thick,blue!100] (6,3) rectangle (7,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   430
    \node at (6.5,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   431
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   432
    \node at (7.5,3.3) {\small $B$};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   433
    \draw[blue!50, <-, line width = 2mm] (3.5,1) -- (3.5, 2.5);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   434
    \draw[blue!50, <-, line width = 2mm] (4,3.3) -- (5.5,3.3);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   435
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   436
  \only<8>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   437
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   438
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   439
    \draw[very thick, blue!50] (4.5,0) rectangle (7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   440
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   441
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   442
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   443
    \node at (6.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   444
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   445
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   446
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   447
    \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   448
    \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   449
    \node at (4,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   450
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   451
    \node at (7.5,3.3) {\small $B$};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   452
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   453
  \only<9>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   454
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   455
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   456
    \draw[fill, blue!50] (4.5,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   457
    \draw[very thick, blue!50] (5,0) rectangle (7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   458
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   459
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   460
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   461
    \node at (6.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   462
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   463
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   464
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   465
    \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   466
    \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   467
    \node at (4,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   468
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   469
    \node at (7.5,3.3) {\small $B$};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   470
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   471
  \only<10>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   472
    \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   473
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   474
    \draw[fill, blue!50] (4.5,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   475
    \draw[very thick, blue!50] (5,0) rectangle (7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   476
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   477
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   478
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   479
    \node at (6.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   480
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   481
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   482
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   483
    \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   484
    \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   485
    \node at (4,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   486
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   487
    \node at (7.5,3.3) {\small $B$};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   488
    \draw[red, fill] (5,1.5) rectangle (6,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   489
    \draw[red, fill] (6.05,1.5) rectangle (7,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   490
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   491
  \only<11>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   492
   \draw[fill, blue!50] (1,0) rectangle (3,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   493
    \draw[fill, blue!50] (3,3) rectangle (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   494
    \draw[fill, blue!50] (4.5,0) rectangle (5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   495
    \draw[very thick, blue!50] (5,0) rectangle (7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   496
    \node at (1.5,0.9) {\small $A_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   497
    \node at (2.0,0.9) {\small $B_L$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   498
    \node at (3.5,3.9) {\small $A_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   499
    \node at (6.7,0.9) {\small $B_R$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   500
    \draw[very thick,blue!100] (1.5,0) -- (1.5,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   501
    \draw[very thick,blue!100] (2.0,0) -- (2.0,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   502
    \draw[very thick,blue!100] (3.5,3) -- (3.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   503
    \draw[very thick,blue!100] (6.7,0) -- (6.7,0.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   504
    \draw[fill,blue!100] (3.5,3) rectangle (4.5,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   505
    \node at (4,3.3) {\small $A$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   506
    \draw[very thick,blue!100] (7,3) rectangle (8,3.6);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   507
    \node at (7.5,3.3) {\small $B$};  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   508
    \draw[red, fill] (5,1.5) rectangle (6,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   509
    \draw[red, fill] (6.05,1.5) rectangle (7,2.1);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   510
    \draw[blue!50, ->, line width = 2mm] (7.1,0.4) -- (8, 0.4);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   511
    \draw[blue!50, ->, line width = 2mm] (7.1,4) -- (8,4);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   512
  }
76
dde58256fc35 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   513
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   514
  \draw[very thick,->](0,0) -- (8,0);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   515
  \node [anchor=base] at (8, -0.3) {\scriptsize time};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   516
  \node [anchor=base] at (0, -0.3) {\scriptsize 0};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   517
  \node [anchor=base] at (-1.2, 0.2) {\small low priority};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   518
  \only<2->{\node [anchor=base] at (-1.2, 3.2) {\small high priority};}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   519
  \only<10->{\node [anchor=base] at (-1.5, 1.7) {\small medium pr.};}
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
   520
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   521
  \end{tikzpicture}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   522
  \end{tabular}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   523
  \end{textblock}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   524
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   525
  \begin{textblock}{0}(2.5,13)%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   526
  \small
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   527
  \onslide<11>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   528
  \begin{bubble}[8cm]%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   529
  Scheduling: You want to avoid that a high 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   530
  priority process is staved indefinitely.
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   531
  \end{bubble}}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   532
  \end{textblock}
79
2eaca58f9bcc updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 78
diff changeset
   533
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
   534
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   535
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   536
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   537
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   538
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   539
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   540
  \frametitle{\Large Priority Inheritance Scheduling}
146
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 145
diff changeset
   541
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   542
  \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   543
  \item Let a low priority process $L$ temporarily inherit 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   544
    the high priority of $H$ until $L$ leaves the critical 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   545
    section unlocking the resource.\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   546
  \item Once the resource is unlocked $L$ returns to its original 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   547
    priority level. \alert{\bf BOGUS}\pause\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   548
  \item \ldots $L$ needs to switch to the highest 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   549
    \alert{remaining} priority of the threads that it blocks.
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   550
  \end{itemize}\bigskip
76
dde58256fc35 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   551
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   552
  \small this error is already known since around 1999
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   553
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   554
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   555
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
76
dde58256fc35 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   556
dde58256fc35 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
   557
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   558
  \begin{frame}[c]
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   559
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   560
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   561
  \includegraphics[scale=0.25]{../pics/p3.jpg}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   562
  \end{center}
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   563
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   564
   \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   565
  \item by Rajkumar, 1991
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   566
  \item \it ``it resumes the priority it had at the point of entry into the critical 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   567
  section''
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   568
  \end{itemize}
148
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 147
diff changeset
   569
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   570
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   571
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   572
     
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   573
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   574
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   575
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   576
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   577
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   578
  \includegraphics[scale=0.25]{../pics/p2.jpg}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   579
  \end{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   580
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   581
   \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   582
  \item by Jane Liu, 2000
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   583
  \item {\it ``The job $J_l$ executes at its inherited 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   584
    priority until it releases $R$; at that time, the 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   585
    priority of $J_l$ returns to its priority 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   586
    at the time when it acquires the resource $R$.''}\medskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   587
  \item \small gives pseudo code and totally bogus data structures  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   588
  \item \small interesting part ``{\it left as an exercise}''
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   589
  \end{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   590
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   591
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   592
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   593
     
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   594
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   595
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   596
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   597
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   598
  \includegraphics[scale=0.15]{../pics/p1.pdf}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   599
  \end{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   600
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   601
  \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   602
  \item by Laplante and Ovaska, 2011 (\$113.76)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   603
  \item \it ``when $[$the task$]$ exits the critical section that
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   604
        caused the block, it reverts to the priority it had
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   605
        when it entered that section'' 
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   606
  \end{itemize}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   607
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   608
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   609
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   610
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   611
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   612
  \begin{frame}[c]
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   613
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   614
  \begin{center}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   615
  \includegraphics[scale=0.25]{../pics/p4.jpg}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   616
  \end{center}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   617
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   618
  \begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   619
  \item by Silberschatz, Galvin, and Gagne, 2013 (OS-bible)
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   620
  \item \it ``Upon releasing the lock, the 
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   621
  $[$low-priority$]$ thread will revert to 
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   622
  its original priority.''
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   623
  \end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   624
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   625
  \end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   626
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   627
   
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   628
  
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   629
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   630
  \begin{frame}[c]
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   631
  \frametitle{Priority Scheduling}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   632
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   633
  \begin{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   634
  \item a scheduling algorithm that is widely used in real-time operating systems
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   635
  \item has been ``proved'' correct by hand in a paper in 1983
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   636
  \item but this algorithm turned out to be incorrect, despite its ``proof''\bigskip\pause
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   637
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   638
  \item we corrected the algorithm and then {\bf really} proved that it is correct	
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   639
  \item we implemented this algorithm in a small OS called PINTOS (used for teaching at Stanford)
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   640
  \item our implementation was much more efficient than their reference implementation
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   641
  \end{itemize}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   642
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   643
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   644
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   645
   
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   646
   
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   647
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   648
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   649
  \frametitle{Design of AC-Policies}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   650
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   651
  Imagine you set up an access policy (root, lpd, users, staff, etc)
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   652
  \bigskip\pause
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   653
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   654
  \Large
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   655
  \begin{quote}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   656
  ``what you specify is what you get but not necessarily what you want\ldots''
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   657
  \end{quote}\bigskip\bigskip\bigskip
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   658
  
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   659
  \normalsize main work by Chunhan Wu (a PhD-student in Nanjing)
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   660
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   661
  \end{frame}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   662
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   663
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   664
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   665
  \begin{frame}[c]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   666
  \frametitle{Testing Policies}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   667
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   668
  \begin{center}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   669
  \begin{tikzpicture}[scale=1]
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   670
  %\draw[black!10,step=2mm] (-5,-3) grid (5,4);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   671
  %\draw[black!10,thick,step=10mm] (-5,-3) grid (5,4);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   672
  \draw[white,thick,step=10mm] (-5,-3) grid (5,4);
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   673
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   674
  \draw [black!20, line width=1mm] (0,0) circle (1cm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   675
  \draw [line width=1mm] (0,0) circle (3cm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   676
  \node [black!20] at (0,0) {\begin{tabular}{c}core\\[-1mm] system\end{tabular}};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   677
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   678
  \draw [red, line width=2mm, <-] (-2.1,2.1) -- (-3.5,3.2);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   679
  \node at (-3.5,3.6) {your system};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   680
  \node at (-4.8,0) {\Large policy $+$};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   681
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   682
  
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   683
  \only<2>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   684
  \draw [black, fill=red, line width=0.5mm] (2,1) circle (3mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   685
  \draw [red, line width=2mm, <-] (2.3,1.2) -- (3.5,2);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   686
  \node at (3.8,2.6) {\begin{tabular}{l}a seed\\[-1mm] \footnotesize virus, Trojan\end{tabular}};}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   687
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   688
  \only<3>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   689
  \draw [black, fill=red, line width=0.5mm] (2,1) circle (7mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   690
  \node[white] at (2,1) {\small tainted};}
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   691
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   692
  \only<4>{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   693
  \begin{scope}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   694
  \draw [clip] (0,0) circle (2.955cm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   695
  \draw [black, fill=red, line width=0.5mm] (2,1) circle (9mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   696
  \node[white] at (2,1) {\small tainted};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   697
  \end{scope}}
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   698
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   699
  \only<5->{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   700
  \begin{scope}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   701
  \draw [clip] (0,0) circle (2.955cm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   702
  \draw [black, fill=red, line width=0.5mm] (2,1) circle (13mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   703
  \node[white] at (2,1) {\small tainted};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   704
  \end{scope}}
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   705
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   706
  \only<6->{
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   707
  \draw[fill=white, line width=1mm] (1.265,2.665) arc (-35:183:5mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   708
  \draw[fill=white, line width=1mm] (1.25,3.25) arc (-35:183:3mm);
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   709
  \node[black, rotate=10] at (1.9,3.6) {\LARGE\ldots};
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   710
  }
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   711
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   712
  \end{tikzpicture}
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   713
  \end{center}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   714
  
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   715
  \only<7->{
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   716
  \begin{textblock}{4}(1,12)
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   717
  \small
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   718
  reduced the problem to a finite problem; gave a proof
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   719
  \end{textblock}} 
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   720
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   721
  \end{frame}
83
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   722
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 82
diff changeset
   723
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   724
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   725
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   726
\begin{frame}[c]
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   727
\frametitle{Big Proofs in CS (1)}
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   728
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   729
Formal proofs in CS sound like science fiction? Completely
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   730
irrelevant! Lecturer gone mad?\pause
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   731
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   732
\begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   733
\item in 2008, verification of a small C-compiler
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   734
\begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   735
\item ``if my input program has a certain behaviour, then the compiled machine code has the same behaviour''
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   736
\item is as good as \texttt{gcc -O1}, but much less buggy 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   737
\end{itemize}
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   738
\end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   739
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   740
\begin{center}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   741
  \includegraphics[scale=0.12]{../pics/compcert.png}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   742
\end{center}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   743
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   744
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   745
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   746
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   747
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   748
\begin{frame}[c]
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   749
\frametitle{Fuzzy Testing C-Compilers}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   750
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   751
\begin{itemize}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   752
\item tested GCC, LLVM and others by randomly generating 
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   753
C-programs
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   754
\item found more than 300 bugs in GCC and also
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   755
many in LLVM (some of them highest-level critical)\bigskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   756
\item about CompCert:
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   757
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   758
\begin{bubble}[10cm]\small ``The striking thing about our CompCert
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   759
results is that the middle-end bugs we found in all other
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   760
compilers are absent. As of early 2011, the under-development
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   761
version of CompCert is the only compiler we have tested for
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   762
which Csmith cannot find wrong-code errors. This is not for
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   763
lack of trying: we have devoted about six CPU-years to the
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   764
task.'' 
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   765
\end{bubble} 
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   766
\end{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   767
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   768
\end{frame}
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   769
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   770
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   771
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   772
\begin{frame}[c]
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   773
\frametitle{Big Proofs in CS (2)}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   774
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   775
\begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   776
\item in 2010, verification of a micro-kernel operating system (approximately 8700 loc)
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   777
  \begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   778
  \item used in helicopters and mobile phones
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   779
  \item 200k loc of proof
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   780
  \item 25 - 30 person years
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   781
  \item found 160 bugs in the C code (144 by the proof)
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   782
  \end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   783
\end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   784
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   785
\begin{bubble}[10cm]\small
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   786
``Real-world operating-system kernel with an end-to-end proof
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   787
of implementation correctness and security enforcement''
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   788
\end{bubble}\bigskip\pause
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   789
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   790
unhackable kernel (New Scientists, September 2015)
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   791
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   792
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   793
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   794
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   795
\begin{frame}[c]
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   796
\frametitle{Big Proofs in CS (3)}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   797
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   798
\begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   799
\item verified TLS implementation\medskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   800
\item verified compilers (CompCert, CakeML)\medskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   801
\item verified distributed systems (Verdi)\medskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   802
\item verified OSes or OS components\\
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   803
(seL4, CertiKOS, Ironclad Apps, \ldots)\medskip
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   804
\item verified cryptography
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   805
\end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   806
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   807
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   808
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   809
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   810
\begin{frame}[c]
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   811
\frametitle{How Did This Happen?}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   812
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   813
Lots of ways!
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   814
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   815
\begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   816
\item better programming languages
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   817
  \begin{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   818
  \item basic safety guarantees built in
  \item powerful mechanisms for abstraction and modularity
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   819
  \end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   820
\item better software development methodology
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   821
\item stable platforms and frameworks
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   822
\item better use of specifications\medskip\\
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   823
  \small If you want to build software that works or is secure, 
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   824
    it is helpful to know what you mean by ``works'' and by ``is secure''!
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   825
\end{itemize}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   826
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   827
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   828
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   829
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   830
147
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 146
diff changeset
   831
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
149
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 148
diff changeset
   832
\begin{frame}[c]
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   833
\frametitle{Goal}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   834
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   835
Remember the Bridges example?
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   836
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   837
\begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   838
\item Can we look at our programs and somehow ensure
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   839
they are secure/bug free/correct?\pause\bigskip
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   840
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   841
\item Very hard: Anything interesting about programs is equivalent
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   842
to halting problem, which is undecidable.\pause\bigskip
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   843
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   844
\item \alert{Solution:} We avoid this ``minor'' obstacle by
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   845
      being as close as possible of deciding the halting
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   846
      problem, without actually deciding the halting problem.
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   847
      \small$\quad\Rightarrow$ yes, no, don't know (static analysis)
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   848
\end{itemize}
87
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 86
diff changeset
   849
331
54a1fbe96b14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 151
diff changeset
   850
\end{frame}
87
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 86
diff changeset
   851
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   852
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   853
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   854
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   855
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   856
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   857
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   858
  \includegraphics[scale=0.4]{../pics/state.png}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   859
  \end{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   860
  
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   861
  \begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   862
  \item depending on some initial input, a program 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   863
  (behaviour) will ``develop'' over time.
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   864
  \end{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   865
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   866
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   867
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   868
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   869
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   870
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   871
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   872
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   873
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   874
  \includegraphics[scale=0.4]{../pics/state2.png}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   875
  \end{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   876
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   877
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   878
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   879
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   880
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   881
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   882
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   883
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   884
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   885
  \includegraphics[scale=0.4]{../pics/state3.jpg}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   886
  \end{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   887
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   888
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   889
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   890
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   891
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   892
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   893
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   894
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   895
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   896
  \includegraphics[scale=0.4]{../pics/state4.jpg}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   897
  \end{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   898
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   899
  \begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   900
  \item to be avoided
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   901
  \end{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   902
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   903
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   904
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   905
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   906
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   907
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   908
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   909
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   910
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   911
  \includegraphics[scale=0.4]{../pics/state5.png}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   912
  \end{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   913
  
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   914
  \begin{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   915
  \item this needs more work
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   916
  \end{itemize}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   917
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   918
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   919
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   920
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   921
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   922
  \begin{frame}[c]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   923
  \frametitle{What is Static Analysis?}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   924
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   925
  \begin{center}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   926
  \includegraphics[scale=0.4]{../pics/state6.png}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   927
  \end{center}
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   928
  
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   929
  for example no key is leaked
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   930
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   931
  \end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   932
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   933
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
   934
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   935
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   936
\begin{frame}[fragile]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   937
\frametitle{\large Concrete Example: Sign-Analysis}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   938
\mbox{}\\[-20mm]\mbox{}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   939
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   940
\bl{\begin{plstx}[rhs style=,one per line]
: \meta{Exp} ::= \meta{Exp} + \meta{Exp}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   941
         | \meta{Exp} * \meta{Exp}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   942
         | \meta{Exp} = \meta{Exp} 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   943
         | \meta{num}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   944
         | \meta{var}\\
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   945
: \meta{Stmt} ::= \meta{label} :
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   946
         | \meta{var} := \meta{Exp}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   947
         | \pcode{jmp?} \meta{Exp} \meta{label}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   948
         | \pcode{goto} \meta{label}\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   949
: \meta{Prog} ::= \meta{Stmt} \ldots{} \meta{Stmt}\\
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   950
\end{plstx}}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   951
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   952
\begin{textblock}{0}(7.8,2.5)
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   953
\small
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   954
\begin{bubble}[5.6cm]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   955
\begin{lstlisting}[numbers=none,
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   956
                   basicstyle=\ttfamily,
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   957
                   language={},xleftmargin=3mm]
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   958
      a := 1
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   959
      n := 5 
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
   960
top:  jmp? n = 0 done 
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   961
      a := a * n 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   962
      n := n + -1 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   963
      goto top 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   964
done:
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   965
\end{lstlisting}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   966
\end{bubble}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   967
\end{textblock}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   968
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   969
\end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   970
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   971
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   972
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   973
\begin{frame}[fragile]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   974
\frametitle{\large Concrete Example: Sign-Analysis}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   975
\mbox{}\\[-20mm]\mbox{}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   976
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   977
\bl{\begin{plstx}[rhs style=,one per line]
: \meta{Exp} ::= \meta{Exp} + \meta{Exp}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   978
         | \meta{Exp} * \meta{Exp}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   979
         | \meta{Exp} = \meta{Exp} 
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   980
         | \meta{num}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   981
         | \meta{var}\\
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   982
: \meta{Stmt} ::= \meta{label} :
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   983
         | \meta{var} := \meta{Exp}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   984
         | \pcode{jmp?} \meta{Exp} \meta{label}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   985
         | \pcode{goto} \meta{label}\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
   986
: \meta{Prog} ::= \meta{Stmt} \ldots{} \meta{Stmt}\\
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   987
\end{plstx}}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   988
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   989
\begin{textblock}{0}(7.8,3.5)
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   990
\small
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   991
\begin{bubble}[5.6cm]
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   992
\begin{lstlisting}[numbers=none,
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   993
                   basicstyle=\ttfamily,
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   994
                   language={},xleftmargin=3mm]
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   995
      n := 6
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   996
      m1 := 0
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   997
      m2 := 1
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
   998
top:  jmp? n = 0 done
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
   999
      tmp := m2
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1000
      m2 := m1 + m2
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1001
      m1 := tmp
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1002
      n := n + -1
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1003
      goto top
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1004
done:
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1005
\end{lstlisting}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1006
\end{bubble}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1007
\end{textblock}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1008
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1009
\end{frame}
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1010
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1011
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1012
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1013
\begin{frame}[fragile]
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1014
\frametitle{\large Concrete Example: Sign-Analysis}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1015
\mbox{}\\[-20mm]\mbox{}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1016
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1017
\bl{\begin{plstx}[rhs style=,one per line]
: \meta{Exp} ::= \meta{Exp} + \meta{Exp}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1018
         | \meta{Exp} * \meta{Exp}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1019
         | \meta{Exp} = \meta{Exp} 
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1020
         | \meta{num}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1021
         | \meta{var}\\
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1022
: \meta{Stmt} ::= \meta{label} :
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1023
         | \meta{var} := \meta{Exp}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1024
         | \pcode{jmp?} \meta{Exp} \meta{label}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1025
         | \pcode{goto} \meta{label}\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1026
: \meta{Prog} ::= \meta{Stmt} \ldots{} \meta{Stmt}\\
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1027
\end{plstx}}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1028
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1029
\end{frame}
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1030
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1031
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1032
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1033
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1034
\begin{frame}[fragile]
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1035
\frametitle{Eval: An Interpreter}
433
b1272782f902 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 381
diff changeset
  1036
\mbox{}\\[-14mm]\mbox{}
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1037
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1038
\small
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1039
\begin{center}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1040
\bl{\begin{tabular}{lcl}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1041
$[n]_{env}$ & $\dn$ & $n$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1042
$[x]_{env}$ & $\dn$ & $env(x)$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1043
$[e_1 + e_2]_{env}$ & $\dn$ & $[e_1]_{env} + [e_2]_{env}$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1044
$[e_1 * e_2]_{env}$ & $\dn$ & $[e_1]_{env} * [e_2]_{env}$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1045
$[e_1 = e_2]_{env}$ & $\dn$ & 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1046
$\begin{cases}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1047
1 & \text{if}\quad[e_1]_{env} = [e_2]_{env}\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1048
0 & \text{otherwise}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1049
\end{cases}$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1050
\end{tabular}}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1051
\end{center}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1052
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1053
\footnotesize
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1054
\begin{lstlisting}[numbers=none,xleftmargin=-5mm]
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1055
def eval_exp(e: Exp, env: Env) : Int = e match {
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1056
  case Num(n) => n
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1057
  case Var(x) => env(x)
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1058
  case Plus(e1, e2) => eval_exp(e1, env) + eval_exp(e2, env)
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1059
  case Times(e1, e2) => eval_exp(e1, env) * eval_exp(e2, env)
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1060
  case Equ(e1, e2) => 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1061
    if (eval_exp(e1, env) == eval_exp(e2, env)) 1 else 0
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1062
}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1063
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1064
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1065
\end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1066
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1067
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1068
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1069
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1070
\begin{frame}[fragile]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1071
\small
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1072
A program
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1073
\begin{bubble}[6cm]\footnotesize
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1074
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1075
                   language={},
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1076
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1077
                   xleftmargin=1mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1078
      a := 1
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1079
      n := 5 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1080
top:  jmp? n = 0 done 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1081
      a := a * n 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1082
      n := n + -1 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1083
      goto top 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1084
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1085
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1086
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1087
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1088
The \emph{snippets} of the program:
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1089
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1090
\footnotesize
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1091
\begin{columns}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1092
\begin{column}[t]{5cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1093
\begin{bubble}[4.5cm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1094
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1095
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1096
                   language={},xleftmargin=1mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1097
""    a := 1
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1098
      n := 5 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1099
top:  jmp? n = 0 done 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1100
      a := a * n 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1101
      n := n + -1 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1102
      goto top 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1103
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1104
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1105
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1106
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1107
\begin{column}[t]{5cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1108
\begin{bubble}[4.5cm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1109
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1110
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1111
                   language={},xleftmargin=1mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1112
top:  jmp? n = 0 done 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1113
      a := a * n 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1114
      n := n + -1 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1115
      goto top 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1116
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1117
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1118
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1119
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1120
\begin{column}[t]{2cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1121
\begin{bubble}[1.1cm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1122
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1123
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1124
                   language={},xleftmargin=1mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1125
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1126
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1127
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1128
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1129
\end{columns}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1130
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1131
\end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1132
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1133
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1134
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1135
\begin{frame}[fragile]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1136
\frametitle{Eval for Stmts}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1137
\mbox{}\\[-12mm]\mbox{}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1138
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1139
Let \bl{$sn$} be the snippets of a program
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1140
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1141
\small
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1142
\begin{center}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1143
\bl{\begin{tabular}{lcl}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1144
$[\texttt{nil}]_{env}$ & $\dn$ & $env$\medskip\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1145
$[\texttt{Label}(l:)::rest]_{env}$ & $\dn$ & $[rest]_{env}$\medskip\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1146
$[x \,\texttt{:=}\, e::rest]_{env}$ & $\dn$ & 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1147
$[rest]_{(env[x:= [e]_{env}])}$\medskip\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1148
$[\texttt{jmp?}\;e\;l::rest]_{env}$ & $\dn$ & 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1149
$\begin{cases}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1150
[sn(l)]_{env} & \text{if}\quad[e]_{env} = 1\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1151
[rest]_{env}  & \text{otherwise}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1152
\end{cases}$\medskip\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1153
$[\texttt{goto}\;l::rest]_{env}$ & $\dn$ & $[sn(l)]_{env}$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1154
\end{tabular}}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1155
\end{center}\bigskip
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1156
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1157
Start with \bl{$[sn(\mbox{\code{""}})]_{\varnothing}$}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1158
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1159
\end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1160
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1161
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1162
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1163
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1164
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1165
\begin{frame}[fragile]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1166
\frametitle{Eval in Code}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1167
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1168
\footnotesize
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1169
\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1170
def eval(sn: Snips) : Env = {
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1171
  def eval_stmts(sts: Stmts, env: Env) : Env = sts match {
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1172
    case Nil => env
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1173
    case Label(l)::rest => eval_stmts(rest, env)
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1174
    case Assign(x, e)::rest => 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1175
      eval_stmts(rest, env + (x -> eval_exp(e, env)))
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1176
    case Jmp(b, l)::rest => 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1177
      if (eval_exp(b, env) == 1) eval_stmts(sn(l), env) 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1178
      else eval_stmts(rest, env)
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1179
    case Goto(l)::rest => eval_stmts(sn(l), env)
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1180
  }
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1181
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1182
  eval_stmts(sn(""), Map())
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1183
}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1184
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1185
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1186
\end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1187
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1188
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1189
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1190
\begin{frame}[fragile]
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1191
\frametitle{The Idea of Static Analysis}
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1192
\small
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1193
\mbox{}\bigskip\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1194
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1195
\begin{columns}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1196
\begin{column}{5cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1197
\begin{bubble}[4.5cm]\footnotesize
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1198
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1199
                   language={},
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1200
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1201
                   xleftmargin=1mm]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1202
      a := 1
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1203
      n := 5 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1204
top:  jmp? n = 0 done 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1205
      a := a * n 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1206
      n := n + -1 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1207
      goto top 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1208
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1209
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1210
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1211
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1212
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1213
\begin{column}{1cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1214
\raisebox{-20mm}{\LARGE\bf$\Rightarrow$}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1215
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1216
\begin{column}{6cm}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1217
\begin{bubble}[4.7cm]\footnotesize
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1218
\begin{lstlisting}[numbers=none,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1219
                   language={},
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1220
                   basicstyle=\ttfamily,
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1221
                   xleftmargin=1mm,
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1222
                   escapeinside={(*}{*)}]
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1223
      a := (*\hl{'+'}*)
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1224
      n := (*\hl{'+'}*) 
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1225
top:  jmp? n = (*\hl{'0'}*) done 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1226
      a := a * n 
336
3cb200fa6d6a updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 335
diff changeset
  1227
      n := n + (*\hl{'-'}*) 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1228
      goto top 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1229
done:
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1230
\end{lstlisting}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1231
\end{bubble}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1232
\end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1233
\end{columns}\bigskip\bigskip
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1234
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1235
Replace all constants and variables by either 
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1236
\pcode{+}, \pcode{-} or \pcode{0}. What we want to find out
337
92a718b88e14 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 336
diff changeset
  1237
is what the sign of \texttt{a} and \texttt{n} is (they should 
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1238
always positive).
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1239
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1240
\end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1241
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1242
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1243
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1244
  \begin{frame}[c]
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1245
  \frametitle{Sign Analysis?}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1246
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1247
  
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1248
  \begin{columns}
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1249
  \begin{column}{3cm}
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1250
  \begin{tabular}{cc|l}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1251
  $e_1$ & $e_2$ & $e_1 + e_2$\\\hline{}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1252
  - & - & -\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1253
  - & 0 & -\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1254
  - & + & -, 0, +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1255
  0 & $x$ & $x$\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1256
  + & - & -, 0, +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1257
  + & 0 & +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1258
  + & + & +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1259
  \end{tabular}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1260
  \end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1261
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1262
  \begin{column}{3cm}
333
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1263
  \begin{tabular}{cc|l}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1264
  $e_1$ & $e_2$ & $e_1 * e_2$\\\hline{}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1265
  - & - & +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1266
  - & 0 & 0\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1267
  - & + & -\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1268
  0 & $x$ & 0\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1269
  + & - & -\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1270
  + & 0 & 0\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1271
  + & + & +\\
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1272
  \end{tabular}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1273
  \end{column}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1274
  \end{columns}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1275
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1276
  \end{frame}
cf02511469d6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 332
diff changeset
  1277
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1278
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1279
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1280
\begin{frame}[fragile]
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1281
\mbox{}\\[-13mm]\mbox{}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1282
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1283
\small
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1284
\begin{center}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1285
\bl{\begin{tabular}{lcl}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1286
$[n]_{aenv}$ & $\dn$ & 
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1287
$\begin{cases}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1288
\{+\} & \text{if}\; n > 0\\
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1289
\{-\} & \text{if}\; n < 0\\
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1290
\{0\} & \text{if}\; n = 0
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1291
\end{cases}$\\
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1292
$[x]_{aenv}$ & $\dn$ & $aenv(x)$\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1293
$[e_1 + e_2]_{aenv}$ & $\dn$ & $[e_1]_{aenv} \oplus [e_2]_{aenv}$\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1294
$[e_1 * e_2]_{aenv}$ & $\dn$ & $[e_1]_{aenv} \otimes [e_2]_{aenv}$\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1295
$[e_1 = e_2]_{aenv}$ & $\dn$ & $\{0, +\}$\\
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1296
\end{tabular}}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1297
\end{center}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1298
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1299
\scriptsize
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1300
\begin{lstlisting}[language=Scala,numbers=none,xleftmargin=-5mm]
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1301
def aeval_exp(e: Exp, aenv: AEnv) : Set[Abst] = e match {
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1302
  case Num(0) => Set(Zero)
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1303
  case Num(n) if (n < 0) => Set(Neg)
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1304
  case Num(n) if (n > 0) => Set(Pos)
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1305
  case Var(x) => aenv(x)
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1306
  case Plus(e1, e2) => 
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1307
    aplus(aeval_exp(e1, aenv), aeval_exp(e2, aenv))
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1308
  case Times(e1, e2) => 
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1309
    atimes(aeval_exp(e1, aenv), aeval_exp(e2, aenv))
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1310
  case Equ(e1, e2) => Set(Zero, Pos)
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1311
}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1312
\end{lstlisting}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1313
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1314
\end{frame}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1315
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1316
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1317
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1318
\begin{frame}[fragile]
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1319
\frametitle{AEval for Stmts}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1320
\mbox{}\\[-12mm]\mbox{}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1321
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1322
Let \bl{$sn$} be the snippets of a program
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1323
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1324
\small
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1325
\begin{center}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1326
\bl{\begin{tabular}{lcl}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1327
$[\texttt{nil}]_{aenv}$ & $\to$ & $(\texttt{nil},aenv)$\medskip\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1328
$[\texttt{Label}(l:)::rest]_{aenv}$ & $\to$ & $(rest, aenv)$\medskip\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1329
$[x \,\texttt{:=}\, e::rest]_{aenv}$ & $\to$ & 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1330
$(rest, aenv[x:= [e]_{aenv}])$\medskip\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1331
$[\texttt{jmp?}\;e\;l::rest]_{aenv}$ & $\to$ & 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1332
$(sn(l),aenv)$ \textcolor{black}{and} $(rest, aenv)$\medskip\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1333
$[\texttt{goto}\;l::rest]_{aenv}$ & $\to$ & $(sn(l), aenv)$\\
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1334
\end{tabular}}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1335
\end{center}\bigskip
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1336
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1337
Start with \bl{$[sn(\mbox{\code{""}})]_{\varnothing}$}, try to 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1338
reach all \emph{states} you can find (until a fix point is reached).
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1339
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1340
Check whether there are only $aenv$ in the final states that have 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1341
your property.
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1342
\end{frame}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1343
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1344
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1345
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1346
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1347
  \begin{frame}[c]
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1348
  \frametitle{Sign Analysis}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1349
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1350
  \begin{itemize}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1351
  \item We want to find out whether \texttt{a} and \texttt{n}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1352
  are always positive?\medskip
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1353
  \item After a few optimisations, we can indeed find this out.
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1354
  \begin{itemize}
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1355
  \item \texttt{equations} return \texttt{+} or \texttt{0}
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1356
  \item branch into only one dircection if you know
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1357
  \item if $x$ is \texttt{+}, then $x + \texttt{-1}$ 
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1358
  cannot be negative 
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1359
  \end{itemize}\bigskip
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1360
  
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1361
  \item What is this good for? Well, you do not need 
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1362
  underflow checks (in order to prevent buffer-overflow
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1363
  attacks). In general this technique is used to make sure 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1364
  keys stay secret.
334
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1365
  \end{itemize}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1366
  
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1367
  \end{frame}
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1368
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
6f08b13c0242 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 333
diff changeset
  1369
434
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1370
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1371
  \begin{frame}[c]
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1372
  \frametitle{Take Home Points}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1373
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1374
  \begin{itemize}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1375
  \item While testing is important, it does not show the 
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1376
    absence of bugs/vulnerabilities.\medskip
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1377
  \item More and more we need (formal) proofs that show
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1378
    a program is bug free.
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1379
  \end{itemize}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1380
  
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1381
  \end{frame}
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1382
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1383
73e6076b9225 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 433
diff changeset
  1384
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1385
76
dde58256fc35 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 75
diff changeset
  1386
\end{document}
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1387
332
8eab185fb187 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 331
diff changeset
  1388
75
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1389
%%% Local Variables:  
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1390
%%% mode: latex
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1391
%%% TeX-master: t
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1392
%%% End: 
df7cf3d07bd8 added slides
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents:
diff changeset
  1393