% -*- LaTeX -*-
%
% Spezielle Anwendersprachen - Concurrent Programming Skriptum
%
% Ronald Blaschke, 9620411
% Copyright 1998 by Dr. Werner Pohlmann
%
% $RCSfile: anwSprach.tex,v $ - $Author: rblasch $
% $Revision: 1.10 $ - $Date: 2001/06/02 10:14:13 $
%

\documentclass[notitlepage,openany,a4paper,austrian]{report}

\usepackage{a4}
\usepackage{isolatin1}
\usepackage{babel}
\usepackage{fancyhdr}
\usepackage{alltt}
\usepackage{latexsym}
\usepackage{tabularx}
\usepackage{cosy_script}
\usepackage{html}
\usepackage{graphicx}

% Kopf- und Fu�zeilen
\lecture{Spezielle Anwendersprachen}
% \date{} use default
\type{Vorlesung}
\names{Werner Pohlmann}
\organization{Universit�t Salzburg}
% \pages{} use default

% Kein Indent
\setlength{\parindent}{0em}

\newcommand{\unreadable}{XXX\ }

\begin{document}

\begin{titlepage}
\null\vfil

\begin{center}
\Huge{
Spezielle Anwendersprachen\\
Concurrent Programming\\
}
\vskip 3em

\LARGE{Dr. Werner Pohlmann}

\vskip 1.5em

\large{Sommersemester 1998}
\end{center}

\vskip 10em

\huge{Vorwort}
\vskip 0.75em

\normalsize
Dieses Skriptum ist w�hrend der Vorlesung "`Spezielle Anwendersprachen 
-- Concurrent Programming"' im Sommersemester 1998 entstanden. Der
Inhalt wurde direkt von den Folien des Dozenten Dr. Werner Pohlmann
�bernommen, wobei kleinere Korrekturen w�hrend der Vorlesung
ber�cksichtigt wurden. Getippt wurde dieser Text von Ronald Blaschke
im Satzprogramm \LaTeX. Die aktuelle Version dieses Dokumentes kann
von seiner Homepage \footnote{http://www.cosy.sbg.ac.at/$\sim$rblasch} bezogen
werden. \\

Ein herzliches Dankesch�n ergeht an dieser Stelle an den Dozenten Dr. Werner
Pohlmann f�r seine freundliche Unterst�tzung und an Peter Meerwald f�r sein
umst�ndliches Korrekturlesen dieses Skriptums. \\

Das Copyright liegt nat�rlich beim Dozenten bzw. bei der Universit�t
Salzburg. \\

Inhaltlich wurde die Erstellung dieses Skriptums am 02.07.1998 mit Revision 1.9 
abgeschlossen.
\vfil

\large{RCS Information}
\vskip 0.75em

\normalsize
\begin{code}
$Revision: 1.10 $ 
$Date: 2001/06/02 10:14:13 $
\end{code}

\null

\end{titlepage}


\tableofcontents

%Folie 1
\chapter{Einleitung}

\section{Worum geht's?}
\begin{itemize}
\item Zwei Handlungen sind \emph{sequentiell} zueinander, wenn die
  eine die andere voraussetzt; sonst sind sie \emph{konkurrent}
  (\emph{nebenl�ufig}). \\
  \emph{Beispiel}
  \begin{itemize}
  \item Kaffee kochen, Kaffe trinken: sequentiell
  \item Kaffee trinken, Kuchen essen: konkurrent
  \end{itemize}
\item Sequentielle Handlungen m�ssen \emph{seriell} (hintereinander)
  ausgef�hrt werden, konkurrente Handlungen k�nnen \emph{parallel}
  (zeitlich �berlappt) ausgef�hrt werden.
\end{itemize}

\begin{important}
Also: Konkurrent = \emph{potentiell} parallel
\end{important}

D.\,h. \emph{Abstraktion} von tats�chlicher Ausf�hrungsweise, die in
Abh�ngigkeit von pragmatischen Zwecken und technischen Gegebenheiten
\emph{verschiedene} Formen annehmen kann.

%Folie 2
\subsection{Technische Gegebenheiten}
\begin{itemize}
\item 1 Prozessor ("`Ausf�hrer"'),
\item 1 Prozessor + Hilfsprozessoren (z.\,B. f�r I/O),
\item mehrere Prozessoren mit gemeinsamen Speicher,
\item mehrere Prozessoren ohne gemeinsamen Speicher (insbesondere
  "`verteilte"' Ausf�hrung mit relativ zeitaufwendiger Kommunikation
  �ber Netze).
\end{itemize}

\subsection{Ausf�hrungsmodi}
\begin{itemize}
\item Parallel: "`echt parallel"'
\item Serialisiert
\item Willk�rliche Verzahnung ("`interleaving"') wenn zerlegbar in
  Teil-Handlungen : "`pseudo-parallel"'; verbreitet im
  1-Prozessor-Fall, dabei Strategie n�tig (Betriebssystem) wie
  z.\,B. "`round robin"' (Zeitscheibenverfahren); die Strategie der
  Prozessorzuteilung sollte \emph{fair} sein (schwieriger Begriff, von 
  uns nicht detailiert betrachtet; nicht notwendig: Jeder kriegt
  gleich viel Prozessorzeit, aber: Keiner wird unendlich
  benachteiligt, also eher qualitative als quantitative Perspektive).
\end{itemize}

%Folie 3
\subsection{Konkurrente Programme, konkurrentes Programmieren}
= Es gibt konkurrente (parallel ausf�hrbare) Programmteile.

\begin{important}
  �bliche Programme sind sequentiell, Reihenfolge durch �bliche
  Semantik (z.\,B. Folge von Anweisungen, getrennt durch "`;"', oder
  rechte/linke Seite von Zuweisung) festgelegt.
\end{important}

Typisch organisiert als: \\
Kollektion von \emph{Prozessen} (tasks, aktive Objekte) mit eigenen
Daten und Handlungen und Kontrollflu�; Proze� in sich sequentiell,
aber konkurrent (�berwiegend, s\,. u.) zu anderen. \\

Das Problem dann:
\subsection{\emph{Interaktion} von Prozessen}
Prozesse i.\,A. nicht unabh�ngig voneinander, sondern
\begin{itemize}
\item in \emph{Kooperation} zur Bew�ltigung einer gemeinsamen Aufgabe.
\item in \emph{Konkurrenz} um gemeinsame Betriebsmittel.
\end{itemize}

%Folie 4
\begin{important}
  Nicht verwechseln:
  \begin{itemize}
  \item "`Konkurrent"' (engl: concurrent) = nebenl�ufig, potentiell
    parallel
  \item "`Konkurrenz"' (engl: competition) = Wettbewerb
  \end{itemize}
\end{important}

Das erfordert:
\begin{itemize}
\item \emph{Synchronisation}, z.\,B. Zustand erreicht, Betriebsmittel
  frei, gemeinsamer Start, \dots
\item \emph{Kommunikation}, z.\,B. Austausch von Zwischenergebnissen
\end{itemize}

\begin{important}
  Synchronisation ist \emph{keine} Frage von gemeinsamer Zeit, also
  von Intervall�nge, Dauer, u.\,�., sondern einer der Logik;
  Zeitfehler ("`race conditions"') entstehen, wenn der konkurrente
  Programmierer sich darauf verl��t, da� Handlung A schneller fertig
  wird als Handlung B: Das mag stimmen, aber beim n�chsten
  Betriebssystem-Release, der n�chsten Hardware-Aufr�stung ung�ltig
  werden \dots
\end{important}

%Folie 5
\subsection{Zwecke, Anwendungsbereiche}
Grunds�tzlich 2 Ziele m�glich:
\begin{enumerate}
\item Zeitgewinn (oder Steigerung der behandelbaren Problemgr��e),
\item Problemad�quate (logische Struktur, technischer Kontext)
  Systemstruktur,
\end{enumerate}
sowie Mischformen.

\begin{important}
Wir verfolgen Ziel 2!
\end{important}

Ziel 1: vgl. VL "`Paralleles Rechnen"'; setzt \emph{echte}
Parallelit�t voraus; typisch: Feink�rnige Parallelit�t mit gro�er
Regelm��igkeit, spezielle Algorithmen, spezielle Programmiermodelle
(z.\,B. PRAM-, Datenflu� \dots) und Rechnerarchitekturen (massiv
parallele Rechner nach SIMD und MIMD Prinzip);

Klassisches Anwendungsfeld: z.\,B. Numerik f�r physik.-technische
Aufgaben wie Wettervorhersage oder Bildverarbeitung.

%Folie 6
\subsection{Beispiele/Anwendungsgebiete f�r konkurrentes
  Programmieren}
\begin{itemize}
\item Informationsverarbeitung in Stufen (Flie�bandprinzip), vgl. Unix 
  pipes
\item Benutzer-(Dialog-) und Anwendungssysteme
\item Mehrbenutzersysteme
\item Verteilte Transaktionen in Datenhaltungssystemen
\item Allg. Client-Server-Systeme
\item Betriebssysteme
\item Rechnernetze, Telematik
\item Eingebettete ("`embedded"') Systeme, Echtzeitsysteme
\end{itemize}

Betriebssysteme \\
= historisch \emph{das} Gebiet der Entwicklung konkurrenten
Programmierens \\

Eingebettete Systeme \\
= Software kontolliert technische Prozesse z.\,B. Fahrzeugsteuerung,
Flug�berwachung \dots

\begin{important}
Technisches System enth�lt \emph{"`nat�rliche"' Parallelit�t}
(z.\,B. Flugzeug = H�henruder, Seitenruder \dots) die abgebildet wird
auf konkurrente Softwarekomponenten.
\end{important}

%Folie 7
\section{Kleines Beispiel}
Eine \emph{Geb�udeheizung} werde wie folgt gesteuert:
\begin{itemize}
\item Wenn die Temperatur im \emph{Heizkessel} ein vorgegebenes
  Intervall nach unten (oben) verl��t, wird der \emph{Brenner} ein-
  (aus-)geschaltet;
\item Wenn die Temperatur im \emph{Geb�ude} ein vorgegebenes Intervall 
  nach unten (oben) verl��t, wird die \emph{Umw�lzpumpe} ein-
  (aus-)geschaltet;
\item Alle diese Aktivit�ten werden ausf�hrlich auf dem \emph{Monitor} 
  des Hausmeisters angezeigt.
\end{itemize}

\emph{Klar:} \\
Softwarel�sung sollte reales System widerspiegeln, also aus \emph{3
  Komponenten} "`Kessel"', "`Haus"' und "`Monitor"' bestehen, die die
offensichtlichen Verantwortlichkeiten und Kollaborationen haben:

\begin{tabular}{l|l}
  \multicolumn{2}{l}{Kessel} \\ \hline
  Kesselsteuerung & KesselTemp. Sensor \\
                  & Brenner \\
                  & Monitor
\end{tabular}

\begin{tabular}{l|l}
  \multicolumn{2}{l}{Haus} \\ \hline
  Haussteuerung & HausTemp. Sensor \\
                & Pumpe \\
                & Monitor
\end{tabular}

\begin{tabular}{l|l}
  \multicolumn{2}{l}{Monitor} \\ \hline
  anzeigen & \\
\end{tabular}

%Folie 8
\subsection{L�sung mit \emph{passiven} Objekten}

\begin{tabular}{|l|} \hline
  \underline{\underline{Kessel}} \\
  Low: Temperature \\
  High: Temperature \\ \hline
  Control \\ \hline
\end{tabular} \\

control =
\begin{code}
Actual := Kessel_Sensor.Read;
if Actual < Low then
   Brenner.On;
   Monitor.Write(Clock, Actual, "on");
elsif Actual > High then
   Brenner.Off;
   Monitor.Write(Clock, Actual, "off");
end if;
\end{code}

\begin{tabular}{|l|} \hline
  \underline{\underline{Haus}} \\
  Low: Temperature \\
  High: Temperature \\ \hline
  Control \\ \hline
\end{tabular} \\

Control = \\
wie oben \\

\begin{tabular}{|l|} \hline
  \underline{\underline{Monitor}} \\
  \  \\ \hline
  Write() \\ \hline
\end{tabular} \\

\emph{ und Hauptschleife} ("`cyclic executive"'):
\begin{code}
loop
   Kessel.Control;
   Haus.Control;
end loop;
\end{code}

%Folie 9
\subsection{Kritik}
Kontrolle von Kessel und Haus der Sache nach unabh�ngig voneinander,
aber hier \emph{eng gekoppelt} \\
$\Rightarrow$
\begin{itemize}
\item Beide Aktivit�ten werden mit \emph{derselben H�ufigkeit} (Rate)
  ausgef�hrt; aber m�glicherweise sinnvoll, verschiedene oder sogar
  dynamisch �nderbare Raten einzuf�hren (z.\,B. Kessel genauer
  �berwachen, wenn Brenner angeschaltet ist); diese Forderung ist nur
  sehr schwer in die Schleifenkonstruktion aufzunehmen!
\item Fehler in einer Komponente wirkt auf andere Komponente,
  z.\,B. Aufruf von Haus.control terminiert nicht \emph{und} Kessel
  eingeschaltet $\Rightarrow$ Bumm!
\item Schwierig, weitere Aktivit�ten in das Programm zu integrieren.
\end{itemize}

%Folie 10
\subsection{Konkurrente L�sung mit \emph{aktiven} Objekten
  (Prozessen)}
= Kontrollflu� (Schleife) in Komponenten!

\begin{code}
process Kessel_Control is
   Low: Temperature := ...;
   High: Temperature := ...;
   Actual: Temperature;

   begin
      loop
         Actual := ...;
         if Actual < Low then
            ...                -- wie oben!
     end loop;
end process;

process Haus_Control is
   ...                       -- wie Kessel
end process;
\end{code}
und Hauptprogramm =
\begin{code}
start Kessel_Control;
start Haus_Control;
\end{code}

%Folie 11
\subsection{Kritik}
logisch �berzeugende L�sung, aber noch \emph{unvollst�ndig}!

\begin{itemize}
\item Aufnahme von delay-statements (Verz�gerungen) in die Schleife
  zur Herstellung der gew�nschten Wiederholrate; bei
  1-Prozessor-time-slicing: Unsch�rfen unvermeidbar ($\Rightarrow$
  sp�ter)
\item Monitor ist jetzt \emph{konkurrent} genutzte \emph{Ressource},
  aber verwandtes Schreiben erfordert vermutlich \emph{exklusiven}
  Besitz \\
  $\Rightarrow$ spezielles \emph{Protokoll} n�tig, um Chaos zu
  vermeiden; evtl. \emph{Pufferung} von Output, um Wartezeiten zu
  vermeiden. \\
\end{itemize}

(\emph{Protokoll:} Vereinbarung �ber \emph{Form} (Parameter u.\,�.)
und \emph{Reihenfolge} von \emph{Operationsaufrufen} an
Schnittstellen von Objekten \dots)

%Folie 12.1
\section{Vorgehensweise und Plan der Vorlesung}
\begin{itemize}
\item Grunds�tzlich 2 Vorgehensweisen bei konkurrenter Programmierung
  m�glich:
  \begin{itemize}
  \item sequentielle Programmiersprache \emph{plus} Dienste eines
    geeigneten Betriebssystems
  \item Konkurrente Programmiersprache
  \end{itemize}

  Unentschieden: Vor- und Nachteile (z.\,B. Portabilit�t, Effizienz)
  beider Vorgehensweisen. \\
  Einigerma�en klar: Variante 2 sorgt f�r besser les- und wartbare
  Programme!

  Wir w�hlen deshalb Variante 2!
\item Es gibt mehrere Sprachen f�r konkurrente Programmierung, mit
  unterschiedlichen Mitteln, zum Teil nur akademisch, z.\,B. Modula
  (und Pascal Varianten), CHILL, Mesa, CSP, occam, PEARL, LINDA, Ada
  \dots

  Wir nehmen Ada95
  \begin{itemize}
  \item Relativ wichtig in der Praxis auf diesem Gebiet, vor allem f�r 
    "`eingebettete Systeme"',

%Folie 12.2
  \item Unterst�tzt OOP und verteilte Ausf�hrung (Ada95!),
  \item Implementierung f�r gebr�uchliche Maschinen/BS (auch
    PC/Windows95) vorhanden und frei zug�nglich (GNAT),
  \item Im Haus gelehrt und benutzt.
  \end{itemize}
\item Plan der Vorlesung
  \begin{itemize}
  \item Falls n�tig: Kurze Einf�hrung in Ada,
  \item Grundprobleme, L�sungen und Konzepte konkurrenter
    Programmierung,
  \item Ada-spezifische Mittel (tasks, rendezvous, protected objects)
    und ihr Gebrauch,
  \item Soweit Zeit reicht: Einblicke in Themen wie real time
    programming, conncurrency \& objects, distributed computing.
  \end{itemize}
\end{itemize}

%Folie 13
\subsection{Literatur}
\begin{description}
\item[Skriptum] Kopien dieser Folien schritthaltend mit VL,
\item[Zu Ada] \ 
  \begin{itemize}
  \item J. Barnes: "`Programming in Ada95"', 1996
  \item J. Skanskolm: "`Ada from the Beginning"', 2nd ed, 1994
  \item Website: http://www.adahome.com/, http://www.epfl.ch/Ada/
  \end{itemize}
\item[Wichtigste Quellen zur VL] \ 
  \begin{itemize}
  \item M. Ben-Ari: "`Principles of Concurrent Programming"', 1982
  \item A. Burns, A. Wellings: "`Concurrency in Ada"', 1995
  \end{itemize}
\item[Andere Quellen zu Concurrency] \ 
  \begin{itemize}
  \item G. R. Andrews: "`Concurrent Programming"', 1991
  \item J. Bacon: "`Concurrent Systems"', 1993
  \item C.A.R. Hoare: "`Communcating Sequential Processes"', 1985
  \item A. Skipo: "`Concurrent Programming"', 1989
  \item O. Whiddett: "`Conncurrent Programming for Software
    Engineers"', 1987
  \item T. Axford: "`Concurrent Programming"', 1989
  \end{itemize}
\end{description}

%Folie 14
\chapter{Ada Tasks I}
\begin{important}
Hier: Nur ganz kurze Darstellung (mehr $\Rightarrow$ sp�ter) \\
Zweck: Einfache Beispiele programmieren zu k�nnen
\end{important}

\begin{itemize}
\item Tasks k�nnen im Deklarationsteil eines Hauptprogramms eingef�hrt 
  werden;
\item Syntax: \\
  Spezifikationsteil, Schnittstelle nach au�en
  \begin{code}
task T is
   ...
end T;
  \end{code}
  Falls Schnittstelle leer gen�gt die Deklaration
  \begin{code}
task T;
  \end{code}
  Rumpf, enth�lt (�hnlich Prozeduren) lokale Deklarationen und eine
  Folge von Anweisungen (also ein "`Programm"')
  \begin{code}
task body T is
   ...
end T;
  \end{code}
\end{itemize}

%Folie 15
\section{Beispiel}
\begin{code}
with Stringpack; use Stringpack;
procedure Tierwelt is

   task Hund;
   task body Hund is
   begin
      Print("wau");
      Print("wau");
   end Hund;

   task Katz;
   task body Katz is
   begin
      Print("miau");
   end Katz;

begin
   Print("hello world");
end Tierwelt;

----------------------------------------------------------------------
6 pohlmann@pavian:Tierwelt
wau
wau
miau
hello world
\end{code}

\emph{Wirkung}
\begin{itemize}
\item Tasks Hund und Katz werden \emph{aktiviert} zugleich mit
  Hauptprogramm; d.\,h. alles geht los bei "`begin"' des
  Hauptprogramms.

%% INSERT: Skizze (easy, lowest) done!
%\begin{figure}[htbp]
\includegraphics{progRun.eps}
%\end{figure}

%Folie 16
\item Tasks Hund und Katz \emph{terminieren} jeweils bei \emph{end}
  ihres Rumpfs; Hauptprogramm terminiert bei end seines
  Anweisungsteils \emph{und} nachdem die beiden tasks beendet sind;
\item Hauptprogramm und die beiden tasks sind \emph{konkurrent}
  zueinander;
\item Tats�chliche Ausf�hrungsweise h�ngt von technischen Umst�nden
  ab; bei 1-Prozessor-System wahrscheinlich pseudoparallele
  (= verzahnte) Ausf�hrung nach Zeitscheibenverfahren in willk�rlicher
  Reihenfolge
  \begin{important}
    Ada schreibt Verfahren nicht vor; Ada Implementierung/System kann
    Optimierungen vornehmen, z.\,B. einfache tasks ganz abarbeiten.
  \end{important}
\end{itemize}

%Folie 17
\begin{important}
  Ergebnis des Beispielprogramms tats�chlich unsicher: Alle drei
  konkurrente Teile greifen zu auf Stringpack/task.io/standard.io
  \dots, d.\,h. laufen Gefahr, sich dabei gegenseitig zu st�ren.
\end{important}

\chapter{Wechselseitiger Ausschlu� und gemeinsame Variablen}
\begin{important}
  Die in diesem Kapitel benutzten Programmiertechniken und -l�sungen
  taugen nichts; von ihrem Gebrauch wird dringend abgeraten!
\end{important}

Warum werden sie hier benutzt?
\begin{enumerate}
\item Historisch-didaktische Gr�nde: Problemlage kennenlernen
\item Hier noch nicht ad�quate Ada- (oder sonstwas) Konzepte
  einf�hren, aber trotzdem Beispiele programmieren wollen.
\end{enumerate}

%Folie 18
\section{Wechselseitiger Ausschlu� ("`mutual exclusion"')}
Ist eines der wichtigsten und fundamentalsten Probleme der
konkurrenten Programmierung.

\emph{Problem} \\
Zwei (oder mehr) konkurrente Prozesse benutzen dasselbe
Betriebsmittel; dieses Betriebsmittel kann aber nicht von mehreren
gleichzeitig benutzt werden.

\emph{Beispiel} \\
\begin{description}
\item[Auf ger�tetechnischer Ebene] massenhaft, z.\,B. Floppies
  kopieren bei nur 1 Laufwerk
\item[auf Programmebene] z.\,B. Programmvariable oder komplizierte
  Datenstruktur (Container-Typ), I/O \dots
\end{description}

%Folie 19
$\Rightarrow$ \emph{Problem} \\
Konkurrentes Verhalten ad�quat einschr�nken (also so konkurrent wie
m�glich, aber nicht mehr), d.\,h. sicherstellen, da� kein zweiter
zugreift (also notfalls nix tut = wartet), wenn der erste grad
zugreift. \\
$\Rightarrow$ Prozesse \emph{synchronisieren} (koordinieren)

\begin{important}
In Ermangelung von etwas Besserem benutzen wir in diesem Kapitel
lediglich
\end{important}
\section{Gemeinsame Variablen ("`shared variables"')}
zur Proze�kommunikation (und dann Synchronisation), d.\,h. Proze� A
teilt Proze� B was mit, indem er die Information in eine \emph{beiden} 
zug�ngliche Programmvariable schreibt. \\
Klar: Diese L�sungstechnik unterliegt selbst dem Problem.

%Folie 20
\section{Terminologie/Problemstruktur}
\begin{itemize}
\item \emph{Kritischer Abschnitt} ("`critical section"') = Teil der
  Handlungsfolge eines Prozesses, der unter \emph{Ausschlu�} aller
  anderen Prozesse von der Ausf�hrung ihrer entsprechenden
  Handlungsfolge ausgef�hrt werden mu�; d.\,h. die kritischen
  Abschnitte verschiedener Prozesse sind sequentiell zueinander.

\item Zur Sicherstellung des Ausschlusses ist ein Protokoll
  (entsprechende Anweisungen vor und nach kritischem Abschnitt) n�tig, 
  also exemplarische Struktur eines Prozesses:
  \begin{code}
loop
   Non_Critical_Part1;
   Pre_Protocol;
   Critical_Section;
   Post_Protocol;
   Non_Critical_Part2;
end loop;
  \end{code}

%Folie 21
\item Wobei critical\_section und Protokollausf�hrung \emph{kurz} sein
  sollten im Verh�ltnis zur �brigen Rechnung.
  \begin{important}
    Nie etwas in kritische Abschnitte setzen, was da nicht unbedingt
    sein mu�.
  \end{important}
\item Wobei critical\_section und Protokollteile besonders
  \emph{sicher} sein sollten. (z.\,B. Proze� darf nicht im Besitz des
  gemeinsamen Betriebsmittels sterben)
\end{itemize}

\section{Beispiel: Gemeinsame Variablen (Shared\_Demo1)}
\begin{itemize}
\item Das folgende Programm enth�lt Prozesse, die \emph{nur} aus
  kritischen Abschnitten bestehen, n�mlich eine gemeinsame Variable
  modifizieren.
\item Effekt war ohne das Zwischenspeichern in lokaler Variable nicht
  zu sehen, und auch erst f�r lange L�ufe.
\item Technik des "`busy waiting"' in Hauptprogramm ist ungut, mehr
  dazu sp�ter.
\end{itemize}

%Folie 22
\label{code:sd1}
\begin{code}
with Stringpack; use Stringpack;
procedure Shared_Demo1 is

N: Integer :=0; --shared variable
Anz: Positive := 1_000_000;

task Up;
task body Up is
   My_N: Integer;
begin
   for I in 1..Anz loop
      My_N := N;        -- -+
      My_N := My_N+1;   --  | Kritischer Abschnitt: Zugriff auf n
      N := My_N;        -- -+
   end loop;
end Up;

task Down;
task body Down is
   My_N: Integer;
begin
   for I in 1..Anz loop
      My_N := N;        -- -+
      My_N := My_N-1;   --  | Kritischer Abschnitt
      N := My_N;        -- -+
   end loop;
end Down;

begin
   while not(Up'Terminated and Down'Terminated) loop
      null;
   end loop; -- sehr schlechter Stil !!!!!!!!!!!!!!!

   Print("n= " & N);
end Shared_Demo1;

----------------------------------------------------------------------
39 pohlmann@pavian:shared_demo1
n= 517520
40 pohlmann@pavian:shared_demo1
n= 6204
41 pohlmann@pavian:shared_demo1
n= -97962
42 pohlmann@pavian:shared_demo1
n= 433532
\end{code}

%Folie 23
Programm sollte als "`Netto"'-Effekt die Variable n wieder auf 0 setzen 
(=  1 Mio. inkrementieren/dekrementieren) aber offenbar unsicher; \\
\emph{Grund:} Ungesch�tzter Gebrauch der gemeinsamen Variablen; also
Abl�ufe m�glich wie

\begin{tabular}{rll}
            & \underline{task up} & \underline{task down} \\
\fbox{n=0}  &                     &                       \\
            & My\_N := N;         &                       \\
            & My\_N := My\_N+1;   &                       \\
            &                     & My\_N := N;           \\
            &                     & My\_N := My\_N-1;     \\
            &                     & N := My\_N;           \\
\fbox{n=-1} &                     &                       \\
            & N := My\_N;         &                       \\
\fbox{n=1}  &                     &                       \\
\end{tabular} \\
D.\,h. 1 mal dekrementieren ist durch die Art der �berlappung mit
Inkrementieren wirkungslos geworden!

%Folie 24
\section{Hausaufgabe}
Programmieren/untersuchen Sie �hnliche Beispiele, z.\,B.
\begin{enumerate}
\item Zwei Prozesse machen Eintr�ge in eine gemeinsam benutzte Liste
  (Warteschlange, Keller)
\item Zwei Prozesse benutzen Stringpack oder direkt task\_io f�r
  Ein-/Ausgaben.
\end{enumerate}

\section{Anmerkung zum Hauptprogramm}
\begin{description}
\item[Zweck] Endergebnis ausdrucken, \emph{nachdem} die beiden tasks
  beendet sind.
\item[Technik] \emph{"`busy waiting"'} (gesch�ftiges Warten)
  d.\,h. Hauptprogramm fragt st�ndig nach, ob tasks schon fertig. \\
  $\Rightarrow$ furchtbar viel Rechenaufwand f�r Nichts-tun! \\
  $\Rightarrow$ andere Synchronisationstechniken m�ssen her!
  ($\Rightarrow$ sp�ter)
\end{description}

%Folie 25
\section{Wie Problem l�sen?}
\begin{itemize}
\item Wir betrachten im folgenden einige Ideen (von denen erst die letzte
  wichtig ist).
\item Die alle \emph{keine} besondere Unterst�tzung durch z.\,B.
  \begin{itemize}
  \item spezielle Programmiersprachen-Konstrukte
  \item spezielle Maschinenbefehle
  \item Betriebssystemdienste
  \end{itemize}
  verwenden;
\item Was bleibt sind dann:
  \begin{itemize}
  \item Gew�hnliche Programmvariable + �bliche Konstruktoren und Anweisungen!
  \item Wobei man voraussetzen mu�:
    \begin{enumerate}
    \item \label{enum:atomar}
      Schreiben und Lesen von Variablen primitiver Datentypen (Boolean,
      Integer) erfolgt \emph{atomar} (ungeteilt, ununterbrochen) und unter
      Ausschlu� eines gleichzeitigen anderen Zugriffs.

%Folie 26
    \item \label{enum:global}
      Die Prozesse benutzen die Variablen selbst und \emph{nicht} lokale
      Kopien davon, die sie anfangs erstellen und sp�ter zur�ckschreiben.
    \end{enumerate}
  \end{itemize}
\end{itemize}

\begin{description}
\item[\ref{enum:atomar}] Kann man als durch die Hardware garantiert ansehen --
  keine 2 gleichzeitigen Speicherzugriffe!
\item[\ref{enum:global}] Geht durch Optimierungen des Compilers oft verloren!
\end{description}
Der Compiler sorgt daf�r, da� Variablenwert in Register �bernommen und dort
�ber mehrere Bearbeitungsschritte hinweg gehalten wird, z.\,B.

\begin{tabular}{lcl}
  \underline{Programm} & $\Rightarrow$ & \underline{Maschineninstruktionen} \\
  x := x+1;            &               & load x into register; \\
                       &               & add 1 to register; \\
  if x = 10            &               & compare register with 10; \\
      then x := 0;     &               & if equal then set register to 0; \\
  end if;              &               & store register into x; \\
\end{tabular} \\
D.\,h. �quivalenz zum Quellcode entsteht erst am \emph{Ende} des
Programmst�cks! \\

%Folie 27
Um solche Optimierungen zu verhindern und \ref{enum:global} sicherzustellen,
kann man in Ada ein "`pragma"' (= Compilerdirektive) verwenden:
\begin{code}
pragma Volatile (x);
\end{code}
Will man ganz sicher gehen (f�r \ref{enum:atomar} und \ref{enum:global})
schreibt man
\begin{code}
pragma Atomic (x);
\end{code}

\section{Idee 1}
\label{sec:idee1}
Jeder Proze� zeigt an, da� er sich im kritischen Abschnitt befindet, und wartet 
(busy waiting), wenn der andere sich grad dort befindet:

\underline{task 1}
\begin{code}
loop
   ...
   Flag1 := True;
   while Flag2 loop
      null;
   end loop;
   Critical_Section;
   Flag1 := False;
   ...
end loop;
\end{code}

\underline{task 2}
\begin{code}
loop
   ...
   Flag2 := True;
   while Flag1 loop
      null;
   end loop;
   Critical_Section;
   Flag2 := False;
   ...
end loop;
\end{code}

%Folie 28
Wobei global vereinbart ist:
\begin{code}
Flag1, Flag2: Boolean := False;
\end{code}

Es gilt:
\begin{enumerate}
\item \label{enum:idee1_safe}
  Das Verfahren ist \emph{sicher} ("`safe"')
\item \label{enum:idee1_deadlock}
  Das Programm kann in eine \emph{Verklemmungssituation} ("`deadlock"') geraten
\end{enumerate}

\begin{description}
\item[safety] Es kann nichts B�ses getan werden, d.\,h. Form von partieller
  Korrektheit.
\item[deadlock] Zwei (oder mehrere) Prozesse sind verklemmt, wenn \emph{jeder}
  auf ein Ergebnis wartet, das erst durch den Fortschritt des anderen eintreten
  kann, z.\,B. p1 wartet auf p2 w�hrend p2 auf p1 wartet.
\end{description}

%Folie 28a
\subsection{Safety des Verfahrens}
Nimm an, es g�be Zeitpunkt t soda� \emph{beide} Prozesse in critical\_section \\
$\Rightarrow$ $\exists t_1, t_1', t_2, t_2', t_1<t_1'<t, t_2<t_2'<t$ soda�
\begin{itemize}
\item flag1 im Intervall ($t_1$, t] \emph{und}
\item flag2 im Intervall ($t_2$, t] \emph{und}
\item $\neg$flag2 in $t_1'$ \emph{und}
\item $\neg$flag1 in $t_2'$.
\end{itemize}
Dies ist unm�glich denn: \\
Entweder \\
$ t_1 < t_2 \Rightarrow t_2' \in (t_1, t] $ \\
oder \\
$ t_1\ge t_2 \Rightarrow t_1' \in (t_2, t] $. \\

Bildlich:
2 Gummib�nder, fixiert am rechten Ende (= t) repr�sentieren G�ltigkeitsbereich
von flag1 und flag2. 2 Marken auf den B�ndern (= $t_1'$, $t_2'$) repr�sentieren
da� $\neg$flag1 und $\neg$flag2 gefunden werden. \emph{Unm�glich}, die B�nder
so zu dehnen da� \emph{beide} Marken \emph{vor Beginn} des jeweils anderen
Bandes! \\

%% INSERT: Skizze (easy, low) done!
%\begin{figure}[htbp]
\includegraphics{gummiband.eps}
%\end{figure}

%Folie 28b
\emph{Korrektheitsbeweise} f�r konkurrente Programme sind
\begin{itemize}
\item sehr w�nschenswert, weil man die m�glichen Abl�ufe noch schlechter
  �bersieht als im sequentiellen Fall,
\item besonders schwierig, weil man immer an mehreren Programmstellen zugleich
  ist.
\end{itemize}

\emph{Methoden}
\begin{itemize}
\item Gew�hnliche Pr�dikatenlogik, wobei man au�er Zustandsgr��en auch noch
  �ber Zeitpunkte (oder Programmstellen, -z�hler) reden mu�, (s.\,o.)
\item Tempor�re Logik, die spezielle Konstrukte wie "`letztendlich"', "`als
  n�chstes"' u.\,�. verwendet und dadurch die explizite Verwendung von Zeit
  erspart
\item (In einfachen F�llen) Zustandsdiagramme, endliche Automaten
\item Spezielle Formalismen zur Algorithmenbeschreibung wie Petri-Netze oder
  CSP und zugeh�rige Beweistechniken.
\end{itemize}

%Folie 29
\subsection{Verklemmung des Verfahrens}
M�glicher Ablauf:

\begin{tabular}{ll}
  \underline{task 1} & \underline{task 2} \\
  flag1 := True;     &                    \\
                     & flag2 := True;     \\
                     & while flag1 loop   \\
                     &     null;          \\
                     & end loop;          \\
  while flag2 loop   &                    \\
      null;          &                    \\
  end loop;          &                    \\
  \multicolumn{2}{c}{Ab jetzt beide Tasks in Warteschleife.} \\
\end{tabular}

%Folie 30
Verklemmung schwierig durch Tests zu entdecken weil
\begin{enumerate}
\item eintreten von Zuf�llen abh�ngig (timing, Verzahnung),
\item oft durch andere Aktivit�ten im System verdeckt.
\end{enumerate}

\section{Idee 2}
\label{sec:idee2}
Verbessere Idee 1 dadurch, da� Prozesse zeitweilig ihre Absicht preisgeben. \\

\underline{task 1}
\begin{code}
loop
   ...
   Flag1 := True;
   while Flag2 loop
      Flag1 := False;
      delay 1.0;
      Flag1 := True;
   end loop;
   Critical_Section;
   Flag1 := False;
   ...
end loop;
\end{code}

\underline{task 2} verl�uft analog. \\

%Folie 31
Es gilt
\begin{enumerate}
\item \emph{Safety}, aus �hnlichen Gr�nden wie bei Idee 1
\item \emph{Deadlockfrei}, jedenfalls in dem Sinn, da� das erwartete Ergebnis
  ($\neg$flag1 bzw. $\neg$flag2) immer wieder angeboten wird.
\item \emph{Lockout} m�glich!
\end{enumerate}

\begin{description}
\item[Lockout/Starvation (Verhungern)] Proze� wird unbestimmt (ewig) lange von
  seinem Ziel abgehalten, wenn ein bestimmtes timing gerade eingehalten wird.
\end{description}

\begin{tabular}{lll}
           & \underline{flag1} & \underline{flag2} \\
  init     & False & False \\
  p1 sets  & True  & False \\
  p2 sets  & True  & True  \\
           &       &       \\
  p1 tests & True  & True  \\
  p2 tests & True  & True  \\
  p1 sets  & False & True  \\
  p2 sets  & False & False \\
  p1 sets  & True  & False \\
  p2 sets  & True  & True  \\
\end{tabular}

%Folie 32
Dieser Fall ist weniger schwerwiegend als deadlock, da die Blockierung jetzt
nicht zwangsl�ufig, sondern nur durch sehr \emph{unwahrscheinliche}
Aufrechterhaltung der Reihenfolge der Aktionen resultiert, aber praktisch
insofern st�rend, als beliebig gro�e Verz�gerungen resultieren k�nnen;
deadlock und starvation sind Verst��e gegen \emph{liveness} (= Lebendigkeit) des 
Verfahrens.

\begin{description}
\item[Safety] Es passiert nix B�ses, z.\,B. beide Prozesse in kritischem
  Abschnitt.
\item[liveness] Letztendlich passiert was Gutes (= Zweck der Veranstaltung),
  z.\,B. jeder Proze� kriegt einmal das gew�nschte Betriebsmittel.
\end{description}

\subsection{Hausaufgabe}
Konstruieren Sie ein anderes lockout-Szenario f�r das Idee 2-Verfahren unter
der Annahme, da� Proze� 1 immer (und nur) in seinem kritischen Abschnitt
unterbrochen wird.

%Folie 33
\section{Idee 3}
\label{sec:idee3}
Striktes \emph{Abwechseln}, totsicher aber (zu) unflexibel.

\underline{task 1}
\begin{code}
loop
   ...
   while Turn = 2 loop
      null;
   end loop;
   Critical_Section;
   Turn := 2;
   ...
end loop;
\end{code}

\underline{task 2}
\begin{code}
loop
   ...
   while Turn = 1 loop
      null;
   end loop;
   Critical_Section;
   Turn := 1;
   ...
end loop;
\end{code}

Verfahren ist sicher und frei von deadlock/starvation, bedeutet aber \emph{enge 
  Kopplung} beider Prozesse.
\begin{itemize}
\item Wenn einer aussteigt kann der andere nicht mehr weiter.
\item Beide arbeiten mit \emph{derselben Rate}.
\end{itemize}

\emph{Keine} ad�quate L�sung des Problems!

%Folie 34
\section{Idee 4}
\label{sec:idee4}
Kombination von Ideen 1 und 2.
Dekker 1965, Peterson 1981 (Vereinfacht). \\

Gemeinsame Variablen
\begin{code}
Flag1, Flag2: Boolean := False;
Turn: Positive range 1..2;
\end{code}

\underline{task 1}
\begin{code}
loop
   ...
   Flag1 := True;
   Turn := 1;
   while Flag2 and Turn = 1 loop
      null;
   end loop;
   Critical_Section;
   Flag1 := False;
   ...
end loop;
\end{code}

\underline{task 2}
\begin{code}
loop
   ...
   Flag2 := True;
   Turn := 2;
   while Flag1 and Turn = 2 loop
      null;
   end loop;
   Critical_Section;
   Flag2 := False;
   ...
end loop;
\end{code}

Es gilt
\subsection{\emph{Kombination vermeidet deadlock}-Gefahr von Idee 1}
Angenommen, beide Prozesse w�ren ewig in Warteschleife.
\begin{list}{$\Rightarrow$}{}
\item Keine �nderung der Variablenwerte
\item dauerhaft (flag2 and turn = 1) und (flag1 and turn = 2)
\end{list}
Dies ist unm�glich, da turn nicht gleichzeitig den Wert 1 und 2 haben kann!

%Folie 35
\subsection{\emph{Kombination vermeidet} strikte \emph{Abwechslung} wie in Idee 
  3}
Angenommen, Proze� 2 befindet sich l�ngere Zeit (oder ewig) im
\emph{unkritischen} Teil "`..."' seines Programms.
\begin{list}{$\Rightarrow$}{}
\item l�ngere Zeit oder ewig: $\neg$flag2
\item l�ngere Zeit oder ewig: Bedingung der Warteschleife von Proze� 1 ist
  False!
\end{list}

\emph{Korrektheitsbeweis} f�r das Verfahren ist kompliziert und aufwendig,
deshalb hier unterlassen.
F�r Interessierte: Das Buch von T. Axford (p. 203-205) pr�sentiert einen auf
Zustandsdiagramme gest�tzten Beweis.

%Folie 36
\subsection{Beispiel (Shared\_Demo2)}
\begin{code}
with Stringpack; use Stringpack;
procedure Shared_Demo2 is

N: Integer := 0; --shared variable
Anz: Positive := 1_000_000;

TURN: POSITIVE range 1..2;
FLAG1, FLAG2: BOOLEAN := FALSE;
pragma ATOMIC(TURN); --sicher ist sicher
pragma ATOMIC(FLAG1);
pragma ATOMIC(FLAG2);

task Up;
task body Up is
   My_N: Integer;
begin
   for I in 1..Anz loop
      FLAG1 := TRUE;
      TURN := 1;
      while FLAG2 and TURN = 1 loop null; end loop;
      My_N := N;
      My_N := My_N+1;
      N := My_N;
      FLAG1 := FALSE;
   end loop;
end Up;

task Down;
task body Down is
   My_N: Integer;
begin
   for I in 1..Anz loop
      FLAG2 := TRUE;
      TURN := 2;
      while FLAG1 and TURN = 2 loop null; end loop;
      My_N := N;
      My_N := My_N-1;
      N := My_N;
      FLAG2 := FALSE;
   end loop;
end Down;

begin
   while not(Up'Terminated and Down'Terminated) loop
      null;
   end loop; -- sehr schlechter Stil !!!!!!!!!!!!!!!

   Print("n= " & N);
end Shared_Demo2;

----------------------------------------------------------------------
70 pohlmann@pavian:shared_demo2
n= 0
\end{code}

%Folie 37
\subsection{Kritik an L�sung und verwendeten Mitteln}
L�sung ist
\begin{enumerate}
\item Schwer zu \emph{verstehen}, \emph{fehleranf�llig} im Gebrauch, schwer zu
  \emph{variieren} (z.\,B.
  \begin{itemize}
  \item Verallgemeinerung auf n Prozesse,
  \item Verallgemeinerung auf verteilte Systeme).
  \end{itemize}
\item (Sehr) \emph{ineffizient}, da Warten als gesch�ftiges Warten ("`busy
  waiting"') realisiert wird, d.\,h. wartender Proze� beansprucht Prozessor und 
  verz�gert damit, da� anderer Proze� vorankommt und insbesondere
  Wartebedingung aufl�st. (Illustration siehe unten, mit Z�hlern in
  Warteschleifen.) Diese Kritik immer dann berechtigt, wenn wartender Proze�
  nicht Prozessor f�r sich alleine hat!
\end{enumerate}

%Folie 38
\begin{code}
with Stringpack; use Stringpack;
procedure Shared_Demo2a is

N: Integer := 0; --shared variable
Anz: Positive := 1_000_000;

TURN: POSITIVE range 1..2;
FLAG1, FLAG2: BOOLEAN := FALSE;
pragma ATOMIC(TURN); --sicher ist sicher
pragma ATOMIC(FLAG1);
pragma ATOMIC(FLAG2);

BUSY1, BUSY2: Natural := 0;

task Up;
task body Up is
   My_N: Integer;
begin
   for I in 1..Anz loop
      FLAG1 := TRUE;
      TURN := 1;
      while FLAG2 and TURN = 1 loop BUSY1 := BUSY1+1; end loop;
      My_N := N;
      My_N := My_N+1;
      N := My_N;
      FLAG1 := FALSE;
   end loop;
end Up;

task Down;
task body Down is
   My_N: Integer;
begin
   for I in 1..Anz loop
      FLAG2 := TRUE;
      TURN := 2;
      while FLAG1 and TURN = 2 loop BUSY2 := BUSY2+1; end loop;
      My_N := N;
      My_N := My_N-1;
      N := My_N;
      FLAG2 := FALSE;
   end loop;
end Down;

begin
   delay 120.0;
   Print("BUSY1= " &BUSY1 & " BUSY2= " & BUSY2);
end Shared_Demo2a;

----------------------------------------------------------------------
pohlmann@pavian:shared_demo2a
BUSY1= 79802288 BUSY2= 78124617
^C

...
begin
   while not(Up'Terminated and Down'Terminated) loop
      null;
   end loop; -- sehr schlechter Stil !!!!!!!!!!!!!!!

   Print("BUSY1= " &BUSY1 & " BUSY2= " & BUSY2);
end Shared_Demo2a;

----------------------------------------------------------------------
rbla@bravo:shared_demo2a
BUSY1= 2147483647 BUSY2= 2147483647
\end{code}

%Folie 39
\subsection{Konsequenz daraus}
\begin{itemize}
\item Erfinde \emph{programmiersprachliche} Konstrukte, die Details der n�tigen 
  Protokolle verbergen.
\item \emph{Implementiere} solche Konstrukte so, da� \emph{kein} busy waiting,
  vielmehr: benutze Proze�verwaltung des \emph{Betriebssystems} mit Diensten
  wie "`Proze� schlafen legen"'/"'Proze� aufwecken"'.
\end{itemize}

\subsection{Hausaufgabe}
Studieren Sie einige der Varianten im Ben-Ari, p. 43-49.

%Folie 40
\chapter{Semaphore und Monitore}
\label{cha:semUndMon}
\section{Semaphore}
\begin{itemize}
\item Wurden 1965 von Dijkstra eingef�hrt.
\item Gibt es in mehreren Varianten, hier eine:
\end{itemize}

\subsection{Ein Sempaphor S ist eine Variable mit Natural-Werten und zwei
  Operationen}
\begin{description}
\item[Wait(S)] \
  \begin{code}
if S > 0 then
   S := S-1;
else
   setze ausf�hrenden Proze� wartend;
end if;
  \end{code}
\item[Signal(S)] \
  \begin{code}
if es gibt auf S wartende Prozesse then
   lasse ersten (FIFO) dieser Prozesse weitermachen;
else
   S := S+1;
end if;
  \end{code}
\end{description}

%Folie 41
\begin{itemize}
\item Wait und signal werden \emph{atomar} (= unteilbar) ausgef�hrt,
  d.\,h. keine andere Aktion zwischen Test und zugeh�riger Handlung;
\item wait und signal sind neben einer Initialisierung vor Proze�start die
  \emph{einzigen} Operationen auf dem Semaphor.
\end{itemize}
Statt {\ttfamily wait(S)} und {\ttfamily signal(S)} sagt man oft auch
{\ttfamily P(S)} und {\ttfamily V(S)} -- niederl�ndisch (Passeren und
Vrijmaken)!

\subsection{F�r Sempaphor S gilt folgende Invariante}
\[ S \ge 0\ and\ S = S_{init} + \#signals - \#compl\_wait \]

\paragraph{Beweis}
\begin{description}
\item[compl\_wait] Proze� ist �ber das wait-statement hinausgekommen, hat
  Operation abgeschlossen.
\end{description}

Formel richtig falls signal/wait Zuweisung an S machen, andernfalls: signal
ver�ndert S nicht gdw. wartender Proze� wird aufgeweckt gdw. wait abgeschlossen 
ohne Ver�nderung von S.

%Folie 42
\subsection{Beispiel: Wechselseitiger Ausschlu�}
\begin{code}
S: Semaphore := 1;
\end{code}

\underline{process 1}
\begin{code}
loop
   ...
   Wait(S);
   Critical_Section;
   Signal(S);
   ...
end loop;
\end{code}

\underline{process 2}
Genau wie bei process 1.

\begin{important}
  L�sung erweiterbar auf n $\ge$ 2 Prozesse.
\end{important}

\section{Korrektheit der L�sung}
Sei \#CS = Zahl der Prozesse im kritischen Abschnitt, dann nach
Programmstruktur \#CS = \#compl\_waits - \#signals. \\
Invariante $\Rightarrow$ S = 1 - \#CS. (*)

%Folie 43
\begin{enumerate}
\item
  \begin{description}
  \item[Safety] \#CS $>$ 1 wegen (*) unm�glich.
  \end{description}

\item
  \begin{description}
  \item[Deadlockfrei] Beide Prozesse warten
    \begin{list}{$\Rightarrow$}{}
    \item S = 0 and \#CS = 0
    \item 1 = 0 (aus (*))
    \end{list}
  \end{description}

\item
  \begin{description}
  \item[No starvation] Process 1 wartet
    \begin{list}{$\Rightarrow$}{}
    \item S = 0
    \item \#CS = 1 (wegen (*))
    \item Process 2 in critical\_section
    \item Process 2 macht als n�chstes signal
    \item Process 1 wird aufgeweckt!
    \end{list}
  \end{description}
\end{enumerate}

%Folie 44
\subsection{Varianten}
\begin{description}
\item[Boolesche Semaphore] Einschr�nkung des Wertebereichs auf 0..1.
\item[Schw�chere Fairne�forderung] Z.\,B. Auswahl des wartenden Prozesses
  unbestimmt (nicht FIFO-Garantie); oder signalisierender Proze� kann sofort
  wieder wait ausf�hren.
\item[Implementierung] Durch Betriebssystemdienst oder (problematisch) busy
  waiting.
\end{description}

\begin{important}
Korrektheit der Anwendung h�ngt ab von solchen Eigenschaften! Z.\,B. schw�chere 
Fairne� kann bei obiger L�sung des mutual-exclusion Problems zu starvation
f�hren!
\end{important}

%Folie 45
\section{Producer-Consumer Problem}
\label{sec:prodConsProblem}
Muster eines Kommunikationsproblems

\begin{description}
\item[\emph{Producer}-Proze�] erzeugt Daten.
\item[\emph{Consumer}-Proze�] verarbeitet Daten.
\item[\emph{Puffer}] Datenstruktur f�r Zwischenspeicherung, gleicht
  vor�bergehende(!) Unterschiede in Geschwindigkeit aus.
\end{description}

%% INSERT: Skizze (easy, med) done!
%\begin{figure}[htbp]
\includegraphics{prodBufCon.eps}
%\end{figure}

Dabei \emph{Synchronisation} n�tig.
\begin{itemize}
\item Consumer kann Datenelement erst lesen, wenn producer es geschrieben hat.
\item Producer kann Datenelement erst schreiben, wenn Puffer freien Platz
  enth�lt.

%Folie 46
\item Ferner: Je nach Implementierung des Puffers sind Zugriffe unter
  wechselseitigen Ausschlu� zu stellen!
\end{itemize}

\subsection{Beispiel}
Implementierung Puffer
\begin{itemize}
\item
  \begin{description}
  \item[Puffer] Vektor mit n $>$ 0 Pl�tzen und zyklischer (circular buffer)
    Verwendung (i := (i+1) mod n);
  \end{description}
\item Private Zeiger (Indizes) f�r producer und consumer, Lesezeiger folgt
  Schreibzeiger, beide zeigen jeweils auf n�chste Position
\end{itemize}

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{bufImpl.eps}
%\end{figure}

%Folie 47
Also
\begin{code}
N: constant Positive := ...;
type Data is ...;
Buffer: array(0..N-1) of Data;
In_Ptr, Out_Ptr: Natural := 0;
Elements: Semaphore := 0; -- Daten da?
Spaces: Semaphore := N; -- noch Platz?
\end{code}

\underline{producer}
\begin{code}
D: Data;
begin
   loop
      Produce(D);
      Wait(Spaces);
      Buffer(In_Ptr) := D;
      In_Ptr := (In_Ptr+1) mod N;
      Signal(Elements);
   end loop;
end Producer;
\end{code}

\underline{consumer}
\begin{code}
D: Data;
begin
   loop
      Wait(Elements);
      D := Buffer(Out_Ptr);
      Out_Ptr := (Out_Ptr+1) mod N;
      Signal(Spaces);
      Consume(D);
   end loop;
end Consumer;
\end{code}

%Folie 48
\begin{important}
  beachte Reihenfolge
  \begin{itemize}
  \item Erst Element schreiben, dann Signal(Element)
  \item Erst Element lesen, dann Signal(Spaces)
  \end{itemize}
\end{important}

\begin{important}
  Schleifeninvariante
  \begin{itemize}
  \item Elements = \#(noch nicht gelesene Elemente)
  \item Spaces = N - \#(noch nicht gelesene Elemente)
  \end{itemize}
\end{important}

Daraus folgt die Korrektheit
\begin{itemize}
\item Puffer kann nicht gelesen (geschrieben) werden, wenn er leer (voll) ist
\item
  \begin{description}
  \item[No deadlock] Spaces = Elements = 0 $\Rightarrow$ N = 0 (aus Invariante).
  \end{description}
  
\item
  \begin{description}
  \item[No starvation] Klar: Einer verhungert $\Rightarrow$ der andere auch
    $\Rightarrow$ deadlock.
  \end{description}
\end{itemize}

%Folie 49
\subsection{Hausaufgabe}
�berlegen Sie, ob die folgende L�sung, die busy-waiting benutzt, korrekt ist.

\underline{producer}
\begin{code}
loop
   Produce(D);
   while((In_Ptr+1) mod N = Out_Ptr) loop
      null;
   end loop;
   Buffer(In_Ptr) := D;
   In_Ptr := (In_Ptr+1) mod N;
end loop;
\end{code}

\underline{consumer}
\begin{code}
loop
   while(Out_Ptr = In_Ptr) loop
      null;
   end loop;
   D := Buffer(Out_Ptr);
   Out_Ptr := (Out_Ptr+1) mod N;
   Consume(D);
end loop;
\end{code}

%Folie 50
\section{Monitore}
Wurden von \emph{Hoare} 1974 vorgeschlagen und in verschiedenen
Pascal-Abk�mmlingen realisiert. Ausgangspunkt ist \emph{Kritik} an
\emph{Semaphoren}: Zusammengeh�rendes \emph{Paar} von Operationen, aber
\emph{verteilt} �ber Programmtext/Prozesse, also \emph{Fehlergefahr} durch
\begin{itemize}
\item Operationsaufruf auslassen.
\item Operation (wait/signal) verwechselt.
\item Operand (S) verwechselt.
\end{itemize}

Stattdessen: Zust�ndigkeit f�r Schutz- und Synchronisationsma�nahmen wird dem
\emph{Objekt} �bertragen, das von mehreren Prozessen benutzt wird, ohne
Kopplung.

\begin{description}
\item[Schnittstelle] Zugriffsoperationen, \emph{kein} Protokoll auf Proze�seite
\item[intern] Implementierung durch Operationen \emph{inklusive}
  Synchronisation.
\end{description}

%Folie 51
Eine solche Datenstruktur/Objekt hei�t \emph{Monitor}.

\begin{important}
Monitore sind \emph{passiv}, d.\,h. werden bei Aufruf ihrer Operationen t�tig,
sind \emph{nicht} selbst Prozesse.
\end{important}

%Folie 52
\subsection{Beispiel: Producer-Consumer}
Ada �hnliche Syntax, aber \emph{nicht} Ada!
\begin{code}
Monitor Buffer is
  procedure Insert(D: Data);
  procedure Take(D: out Data);
end Buffer;

Monitor body Buffer is
  N: Positive := ...;
  B: array(0..N-1) of Data;
  In_Ptr, Out_Ptr: natural := 0;
  Count: Natural := 0; -- Anzahl Elemente
  Not_Full, Not_Empty: Condition; -- Bedingungsvariablen

  procedure Insert(D: Data) is
  begin
     if Count = N then
        Wait(Not_Full);
     end if;
     B(In_Ptr) := D;
     In_Ptr := (In_Ptr+1) mod N;
     Count := Count+1;
     Signal(Not_Empty);
  end Insert;

  procedure Take(D: out Data) is
  begin
     if Count = 0 then
        Wait(Not_Empty);
     end if;
     D := B(Out_Ptr);
     Out_Ptr := (Out_Ptr+1) mod N;
     Count := Count-1;
     Signal(Not_Full);
  end Take;
end Buffer;
\end{code}

%Folie 53
Gebrauch unit:

\underline{producer}
\begin{code}
D: Data;

begin
   loop
      Produce(D);
      Insert(D);
   end loop;
end;
\end{code}

\underline{consumer}
\begin{code}
D: Data;

begin
   loop
      Take(D);
      Consume(D);
   end loop;
end;
\end{code}
d.\,h. Synchronisation ist \emph{nicht} Sache der Klienten!

\subsection{Semantik der Monitor-Konstruktion}
\begin{itemize}
\item Jeweils nur 1 Monitor Operation in Ausf�hrung, d.\,h. \emph{mutual
    exclusion}.
\item Operationen auf \emph{condition variables} (C)
  \begin{description}
  \item[Wait(C)] Ausf�hrender Proze� wird suspendiert und in eine mit C
    assozierte FIFO-queue eingereiht; andere Prozesse jetzt zugelassen zur
    Operationsausf�hrung.

%Folie 54
  \item[Signal(C)] Falls die mit C assozierte FIFO-queue nicht leer ist, wird
    der erste der wartenden Prozesse aufgeweckt.
  \item[Is\_Empty(C)] True gdw. Queue f�r C nicht leer (reine Abfrage!)
  \end{description}
\end{itemize}

\subsection{Interpretation von Signal}
Heikler Punkt! Wenn der erste auf die Bedingung wartende Proze� aufgeweckt
wird, sollte er \emph{sofort} arbeiten k�nnen und \emph{nicht} auf Beendigung
des signalisierenden Prozesses warten (sonst: Bedingung vielleicht wieder
False).
Aber: Was tun mit signalisierendem Proze�, wie h�lt man Ausschlu�eigenschaft
des Monitors aufrecht? \\

Sinnvolle Konvention: Signal \emph{letztes} statement einer Prozedur und intern 
blockierte Prozesse haben Priorit�t �ber extern aufrufende!

%Folie 55
\begin{important}
  Mehrere Festlegungen und Konventionen im Gebrauch! Wir verfolgen die Sache
  hier nicht weiter, sondern studieren (sp�ter) die Ada-L�sung!
\end{important}

\subsection{Kritik an Monitoren}
Schwierig, eine Strategie f�r die Bedienung von Operationsaufrufen zu
realisieren.

%Folie 56
\chapter{Zwischenbilanz, Ausblick Ada}
\begin{itemize}
\item Bisher haben wir betrachtet: Prozesse interagieren mit Hilfe
  \emph{gemeinsamer} Variablen $\Rightarrow$ Protokolle und Schutzma�nahmen
  n�tig!
\item Technischer/historischer Ausgangspunkt daf�r: Rechner mit 1 Prozessor
  (meist, oder mehrere) und \emph{1 Speicher}.
\end{itemize}

Aber: Technische Alternative ist ein \emph{verteiltes} System mit
\emph{Nachrichtenaustausch} (message passing). \\

$\Rightarrow$ plausibel, konkurrente Programmierung an diesem technischen
Paradigma zu orientieren.

%Folie 57
\begin{important}
  Technische Basis nicht zwingend, man kann
  \begin{itemize}
  \item eine Struktur durch eine anderen \emph{simulieren},
  \item eine aus Gr�nden der \emph{Programmierung} bevorzugen!
  \end{itemize}
\end{important}  

\section{Analogie}
\begin{tabular}{ccc}
  shared variables           & $\sim$ & global variables               \\
  \& processes               &        & \& procedures                  \\
  $\Bigg\downarrow$          &        & $\Bigg\downarrow$              \\
  ? \emph{message passing} ? & $\sim$ & \emph{explizite Schnittstelle} \\
  Typ der Nachricht,         &        & Parameter�bergabe              \\
  wer an wen,                &        &                                \\
  wenn \dots                 &        &                                \\
\end{tabular}

%Folie 58
\section{Message passing}
M�glich in verschiedenen Grundformen.
\begin{enumerate}
\item \label{enum:asynchron}
  \begin{description}
  \item[asynchron (nicht blockierend)] Sender wartet nicht auf Empfang, sondern 
    macht weiter.
    \begin{description}
    \item[Vorteil] Kein Zeitverlust
    \item[Nachteil] R�ckflu� von Informationen nicht im selben Akt m�glich;
      Info aktuell.
    \item[Beispiel] Briefpost
    \end{description}
  \end{description}    

\item \label{enum:synchron}
  \begin{description}
  \item[synchron] Gemeinsamer Akt von Sender und Empf�nger, jeder mu� auf
    anderen warten.
    \begin{description}
    \item[Vorteil/Nachteil] siehe oben
    \item[Beispiel] Telephon
    \end{description}
  \end{description}

\item \label{enum:kanal}
  Fest vorgegebene (uni-, bidirektionale) \emph{Kan�le}.
\item \label{enum:anschrift}
  Sender kennt Empf�nger"`anschrift"', nicht umgekehrt.
\item \label{enum:broadcast}
  Broadcast ("`Rundfunk"', Info �ffentlich)
\end{enumerate}

%Folie 59
\subsection{Beispiele}
\begin{tabular}{r@{:}l}
  \ref{enum:synchron}  + \ref{enum:kanal}     & occam          \\
  \ref{enum:asynchron} + \ref{enum:broadcast} & Linda          \\
  \ref{enum:synchron}  + \ref{enum:anschrift} & Ada Rendezvous \\
\end{tabular}

\subsection{Die Techniken in Ada}
\begin{description}
\item[Rendezvous] Synchrone Kommunikation mit M�glichkeit zur Antwort und
  Hilfsberechnung; z.\,B. Telephonauskunft.

%% INSERT: Skizze (hard, high) done!
%\begin{figure}[htbp]
\includegraphics{telAuskunft.eps}
%\end{figure}

%Folie 60
\item[Protected objects] Gekapselte passive Struktur, �hnlich Monitor.
\end{description}

\begin{important}
  Die verschiedenen f�r konkurrente Programmierung vorgeschlagenen / benutzten
  Konstrukte (Semaphore, Monitore, asynchrone/synchrone Nachrichten, \dots)
  sind gleichwertig in dem Sinn, da� sie sich wechselseitig simulieren k�nnen;
  also nur Unterschiede in
  \begin{itemize}
  \item Effizienz (je nach Kontext und Problemstellung)
  \item Sicherheit, Klarheit im Gebrauch
  \item Modellierungsqualit�t
  \end{itemize}
\end{important}

\begin{important}
  Ada hatte urspr�nglich nur rendezvous; protected objects in Ada95 weil manchmal 
  \begin{itemize}
  \item Klarer und einfacher im Gebrauch.
  \item Effizienter zu implementieren.
  \end{itemize}
\end{important}
  
\subsection{Hausaufgabe}
\begin{itemize}
\item \emph{Monitor} simuliert \emph{Semaphore}.
\item \emph{Asynchrone} Nachrichtenkommunikation simuliert synchrone.
\end{itemize}

%Folie 61
\chapter{Ada Tasking II}
\begin{important}
  Immer noch nicht volle Syntax, sondern nur Basisform von rendezvous und
  protected objects; mehr sp�ter.
\end{important}

\section{Tasks}
\begin{itemize}
\item Haben �hnlich wie packages \emph{Spezifikationsteil} und \emph{Rumpf},
  m�ssen aber in �bergeordnetem Programmteil (z.\,B. Hauptprogramm, Paket)
  deklariert werden, sind also selber \emph{nicht} Bibliothekseinheiten!
\item Beinhalten wie Unterprogramme eigene \emph{Deklarationen} und eine
  \emph{Anweisungsfolge}, werden aber nicht durch Aufruf gestartet (und im
  Kontrollflu� des Aufrufers ausgef�hrt), sondern implizit und konkurrent zu
  anderen.
\item Lassen sich wie Datenstrukturen unterscheiden in \emph{Typ}
  (z.\.B. {\ttfamily type vector is array(1..n) of \dots}) und zugeh�rige
  \emph{Objekte} (z.\,B. {\ttfamily v1, v2: vector}), sind aber nicht passiv,
  sondern haben eigenen Kontrollflu�!
\end{itemize}

%Folie 62
Wir betrachten den letzten Punkt. Bisher nur "`Einmal-tasks"', die einen
\emph{anonymen} Typ haben!
\begin{code}
task Hund;
task body Hund is
   print("wau wau");
end Hund;
\end{code}

Allgemein deklariert man den Typ mit
\begin{code}
task type T is
   ...
end T;

task body T is
   ...
end T;
\end{code}
und die Objekte davon mit
\begin{code}
t1, t2: T;
\end{code}

\begin{important}
  Task-Typen sind \emph{limited}, d.\,h. Vergleich und Zuweisung ist nicht
  erlaubt. (Task Objekte also insbesondere konstant).
\end{important}

%Folie 63
Task Typen erlauben wie andere Typen die Bildung von \emph{zusammengesetzten}
Datenstrukturen, z.\,B.
\begin{code}
T_Vector: array(1..10) of T;
\end{code}
und \emph{dynamische Erzeugung}, z.\,B.
\begin{code}
type T_pointer is access T;
p: T_pointer;
   ...
begin
   ...
   p := new T;
   ...
end;
\end{code}

\subsection{Beispiele}
\begin{itemize}
\item
  \begin{description}
  \item[Array of tasks] Geb�udeheizung mit \emph{Sensor}-task f�r jeden Raum.
  \end{description}
  
\item
  \begin{description}
  \item[Dynamische Erzeugung] Luftraum�berwachung mit task f�r jedes gesteuerte 
    Flugzeug.
  \end{description}
\end{itemize}

%Folie 64
\subsection{Verschiedene Tasks desselben Typs}
\begin{itemize}
\item Zeigen \emph{gleichartiges} Verhalten.
\item Haben ihre \emph{eigenen} Daten und Kontrollflu� (speziell: 2 Tasks rufen 
  dieselbe Prozedur auf $\Rightarrow$ 2 Inkarnationen der Prozedur, wie bei
  Rekursion).
\end{itemize}

\section{Aktivierung, Ausf�hrung, Terminierung}
\begin{itemize}
\item Ist ein komplexes Thema, weil so viele Kontexte m�glich.
\item Wir beschr�nken uns auf einfache/fundamentale F�lle (und warnen vor
  exotischen Konstruktionen).
\end{itemize}

\subsection{Task Objekt deklariert in Hauptprogramm}
z.\,B.
\begin{code}
procedure Main is
  ...
  task type T;
  A: T;
  B: T;
  ...
begin
   ...
end;
\end{code}

%Folie 65
dann
\begin{itemize}
\item Hauptprogramm wird angesehen als von einer "`Umgebungs-Task"' aufgerufen
  und ausgef�hrt. Dies ist die "`\emph{Mutter}"' (der "`\emph{Vater}"') der im
  Hauptprogramm deklarierten Tasks, die von ihr \emph{abh�ngen} ("`are
  dependent on"').
\item Deklarierte Task Objekte werden
  \begin{description}
  \item[aktiviert] Ihre internen Deklarationen werden elaboriert.
  \item[exekutiert] Anweisungsfolge wird ausgef�hrt.
  \end{description}
\end{itemize}

%% INSERT: Skizze (hard, high) done!
%\begin{figure}[htbp]
\includegraphics{aktExeTasks.eps}
%\end{figure}

\begin{important}
  Hauptprogramm arbeitet erst selbst, wenn Aktivierung aller Tasks gelungen
  ist. Grund: Fehler auffangen.
\end{important}

%Folie 66
\paragraph{Terminierung in 2 Stufen}
\begin{description}
\item[completed] Task erreicht Ende ihrer Anweisungsfolge.
\item[terminated] Completed + alle abh�ngigen Tasks sind terminiert
  $\Rightarrow$ Hauptprogramm terminiert als letztes)
\end{description}

\paragraph{Spezialf�lle}
z.\,B. Abort-statement (= andere Task abbrechen).
\begin{important}
  Unsch�n und wegen komplexer Semantik fehleranf�llig.
\end{important}
Gibt's in Ada als letztes Mittel zur Behandlung von Ausnahmesituationen (= Task
l�uft Amok). Aber: Angenommen, es gibt b�se Menschen (R�uber, M�rder, \dots).
Frage: Soll man dann Waffenerwerb \emph{erleichtern} oder \emph{erschweren}?

%Folie 67-76 existieren nicht

%Folie 77
\subsection{Task deklariert in (library-) Package}
\begin{itemize}
\item Wird aktiviert mit "`begin"' des Paketrumpfs; gibt es dort keinen
  Anweisungsteil, wird "`{\ttfamily begin null; end;}"' angenommen.
\item Main-Environment-Task terminiert erst, wenn
  \begin{enumerate}
  \item Hauptprogramm terminiert.
  \item Library (package) Task terminiert.
  \end{enumerate}
\end{itemize}

\subsection{Task wird dynamisch erzeugt durch Allokator}
\begin{itemize}
\item Aktivierung w�hrend Ausf�hrung der Allokationsanweisung, dann Ausf�hrung
  konkurrent zum Erzeuger.
\item Solche Tasks h�ngen \emph{nicht} ab vom Erzeuger, sondern von
  Programmeinheit, die den zugeh�rigen \emph{access-Typ} eingef�hrt hat!
\end{itemize}

%Folie 78
\section{Rendezvous}
\begin{itemize}
\item Ist Mittel zur Synchronisation \emph{und} Kommunikation.
\item Geschieht �ber im Task-Spezifikationsteil deklarierte "`entries"'
  \begin{code}
task type T is
   entry E(<Param. Spec.>);
end T;

task body T is
   ...
   accept E(<Param. Spec.>) do
     ...
   end E;
end T;
\end{code}
\item
  \begin{description}
  \item[Gebrauch] Sei {\ttfamily T1:T;}, dann Aufruf des entries mit {\ttfamily
      T1.E(<Actuals>);}
  \end{description}
\item

%Folie 79
  \begin{description}
  \item[Wirkung]
    \begin{itemize}
    \item Parameter�bergabe (in, out, inout) �hnlich Prozedur.
    \item Aufrufer wartet w�hrend Ausf�hrung des accept-statements, �hnlich
      Prozedur.
    \item Aufrufer wartet, \emph{bis} Aufgerufener accept-statement ausf�hrt.
    \item Aufgerufener wartet, bis jemand entry aufruft.
    \end{itemize}
  \end{description}

%% INSERT: Skizze (hard, high) done!
%\begin{figure}[htbp]
\includegraphics{rendezvous.eps}
%\end{figure}

%Folie 80
\item Task body kann \emph{mehrere} accept-statements f�r dasselbe entry
  enthalten (insbesondere in Schleife -- typischer Fall einer Server-Task).
\item Entry kann von mehreren Tasks gerufen werden $\Rightarrow$ Warteschlange!
\item Accept-statement mu� direkt im task body stehen, aber nicht in
  Unterprogramm. (Aufruf aber durchaus in Unterprogramm. M�glich und manchmal
  sinnvoll: {\ttfamily procedure \dots \emph{renames} entry \dots}).
\item Accept statement sollte nur Anweisungen enthalten, die f�r das Rendezvous 
  (Ergebnisr�ckgabe) unbedingt n�tig sind -- also den Anrufer nicht sinnlos
  verz�gern.
\item Entries \emph{ohne} Parameter sind n�tzlich f�r Synchronisationszwecke,
  z.\,B.

%Folie 81
  \begin{code}
----------------------------------------------------------------------
-- Demo: rendezvous zur Synchronisation
----------------------------------------------------------------------

with stringpack; use Stringpack;
procedure Tierwelt2 is

   task type Hund is
      entry Los;
   end Hund;

   task body Hund is
   begin
      accept Los;
      Print("wau");
      Print("wau");
   end Hund;

   Rex, Pluto, Fifi: Hund;

   task Katz is
      entry Los;
      entry Nochmal;
   end Katz;

   task body Katz is
   begin
      accept Los;
      Print("miau");
      accept Nochmal;
      Print("miau");
   end Katz;

begin
   Print("hello world");
   Rex.Los; Fifi.Los; Katz.Los; Pluto.Los; Katz.Nochmal;
end Tierwelt2;
  \end{code}
\end{itemize}

Synchronisation mittels Rendezvous kann man benutzen, um
\begin{itemize}
\item Andere Synchronisationsmittel wie Semaphore zu realisieren, oder
\item die mit z.\,B. Semaphoren l�sbaren Aufgaben \emph{direkt} anzugehen.
\end{itemize}

\begin{important}
  Letzteres ist vorzuziehen, wobei -- wie sp�ter besprochen --
  \begin{itemize}
  \item Verfeinerung der Rendezvous Konstruktion
  \item Protected types
  \end{itemize}
  wichtig sind f�r gute L�sung.
\end{important}

Hier einstweilen eine \emph{schlechte} L�sung.
\begin{itemize}
\item Imitiere (Bin�res-) Semaphor.
\item L�se damit Problem des wechselseitigen Ausschlusses.
\end{itemize}

\subsection{Beispiel: Imitation einer bin�ren Semaphore}
Programm von \ref{code:sd1} (Seite \pageref{code:sd1}); Tasks  "`Up"' und
"`Down"' manipulieren gemeinsame Variable.

%Folie 83
\begin{important}
  So nicht!
\end{important}

%Folie 84
\begin{code}
with Stringpack, Ada.Calendar;
use Stringpack, Ada.Calendar;

procedure Shared_Demo3 is

   Start_Work, End_Work: Time;

   N: Integer := 0;  --shared variable
   Anz: Positive := 1_000_000;

   task Binary_Semaphore is
      entry Wait;
      entry Signal;
   end Binary_Semaphore;

   task body Binary_Semaphore is
   begin
      loop
         accept Wait;
         accept Signal;
      end loop;
   end Binary_Semaphore;

   task Up is
      entry Start;
      entry Finish;
   end Up;

   task body Up is
      My_N: Integer;
   begin
      accept Start;
      for I in 1..Anz loop
         Binary_Semaphore.Wait;
         My_N := N;
         My_N := My_N+1;
         N := My_N;
         Binary_Semaphore.Signal;
      end loop;
      accept Finish;
   end Up;

   task Down is
      entry Start;
      entry Finish;
   end Down;

   task body Down is
      My_N: Integer;
   begin
      accept Start;
      for I in 1..Anz loop
         Binary_Semaphore.Wait;
         My_N := N;
         My_N := My_N-1;
         N := My_N;
         Binary_Semaphore.Signal;
      end loop;
      accept Finish;
   end Down;

begin
   Start_Work := Clock;  -- Zeiterfassung
   Up.Start; Down.Start;
   Up.Finish; Down.Finish;
   Print("n= " & N);
   End_Work := Clock;    -- Zeiterfassung
   Print("time spent= " & Float(Ada.Calendar."-"(End_Work, Start_Work)));
   abort Binary_Semaphore;  -- sehr schlechter Stil !!!!!!!!!!!!!!!
end Shared_Demo3;

----------------------------------------------------------------------
11 pohlmann@pavian:shared_demo3
n= 0
time spent= 1086.25

rbla@bravo:shared_demo3
n= 0
time spent= 424.29 (AMD K6, 200MHz, GNAT, Linux)
\end{code}

\subsection{Zur Zeitmessung}
Hier: Einfache, ungenaue(!) Methode: Gemessen wird "`\emph{Wall-clock-time}"',
also \emph{nicht} die Rechenzeit, die speziell auf \emph{mein} Programm
entf�llt.

\paragraph{Methode}
Ada.Calendar
\begin{description}
\item[mit {\ttfamily type time}] (Datum, Uhrzeit) wobei Uhrzeit = Sekunden und
  einschl�gige Arithmetik.
\item[und {\ttfamily function clock}] current time
\end{description}

%Folie 85
\begin{code}
package Ada.Calendar is

-> type Time is private;

   subtype Year_Number  is Integer range 1901 .. 2099;
   subtype Month_Number is Integer range 1 .. 12;
   subtype Day_Number   is Integer range 1 .. 31;

   subtype Day_Duration is Duration range 0.0 .. 86_400.0;

-> function Clock return Time;

   function Year    (Date : Time) return Year_Number;
   function Month   (Date : Time) return Month_Number;
   function Day     (Date : Time) return Day_Number;
   function Seconds (Date : Time) return Day_Duration;

   procedure Split
     (Date    : Time;
      Year    : out Year_Number;
      Month   : out Month_Number;
      Day     : out Day_Number;
      Seconds : out Day_Duration);

   function Time_Of
     (Year    : Year_Number;
      Month   : Month_Number;
      Day     : Day_Number;
      Seconds : Day_Duration := 0.0)
      return    Time;

   function "+" (Left : Time;     Right : Duration) return Time;
   function "+" (Left : Duration; Right : Time)     return Time;
   function "-" (Left : Time;     Right : Duration) return Time;
-> function "-" (Left : Time;     Right : Time)     return Duration;

   function "<"  (Left, Right : Time) return Boolean;
   function "<=" (Left, Right : Time) return Boolean;
   function ">"  (Left, Right : Time) return Boolean;
   function ">=" (Left, Right : Time) return Boolean;

   Time_Error : exception;

private
   -- implementation-dependent
end Ada.Calendar;
\end{code}

%Folie 86
Bessere L�sung $\Rightarrow$ sp�ter.

\section{Beispiel f�r Kooperation von Tasks}
Berechne $\sum^n_{i=1}i$ durch tats�chliches Addieren, und verteile die Arbeit
unter mehreren Task!

\begin{important}
  Beispiel ist an sich \emph{nicht} sinnvoll weil
  \begin{itemize}
  \item Formel,
  \item Arbeitsteilung nur bei echter Parallelit�t schneller,
  \end{itemize}
  aber hier Zweck: Zeige verschiedene M�glichkeiten der Interaktion durch
  Rendezvous!
\end{important}

\subsection{Beispiel 1}
2 Tasks, jeder verantwortlich f�r halbe Summe, Start und Zusammenfassung der
Ergebnisse durch Hauptprogramm, also Rendezvous Task-Hauptprogramm.

%% INSERT: Skizze (hard, high) done!
%\begin{figure}[htbp]
\includegraphics{rendBsp1.eps}
%\end{figure}

%Folie 87
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen 1..n/2, n/2+1..n,
--          Start u. Zusammenfassung durch Hauptprogramm
----------------------------------------------------------------------
with Stringpack; use Stringpack;
procedure Arbeitsteilung is

   task type Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Worker;

   task body Worker is
      Local_From, Local_To, Local_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Local_Res := 0;
      for I in Local_From..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Result(Res: out Integer) do
         Res := Local_Res;
      end Result;
   end Worker;

   W1, W2: Worker;
   N, Sum1, Sum2: Integer;

begin
   Print("give natural");
   N := Getint;
   W1.Start(1, N/2);
   W2.Start(N/2 +1, N);
   W1.Result(Sum1);
   W2.Result(Sum2);
   Print("Summe= " & (Sum1 + Sum2));
end Arbeitsteilung;

----------------------------------------------------------------------
7 pohlmann@pavian:Arbeitsteilung
give natural
100
Summe= 5050
\end{code}

%Folie 88
\subsection{Beispiel 2}
Diesselbe Aufteilung der Arbeit, aber andere Organisation.

%% INSERT: Skizze (hard, high) done!
%\begin{figure}[htbp]
\includegraphics{rendBsp2.eps}
%\end{figure}

%Folie 89
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen 1..n/2, n/2+1..n
--          erste task startet die zweite und bildet Gesamtergebnis
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Arbeitsteilung2 is

   task Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Worker;

   task Helper is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Helper;

   task body Worker is
      Local_From, Local_To, Local_Res, Remote_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Helper.Start(Local_From, (Local_From + Local_To)/2);
      Local_Res := 0;
      for I in ((Local_From + Local_To)/2 +1)..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      Helper.Result(Remote_Res);
      accept Result(Res: out Integer) do
         Res := Local_Res + Remote_Res;
      end Result;
   end Worker;

   task body Helper is
      Local_From, Local_To, Local_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Local_Res := 0;
      for I in Local_From..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Result(Res: out Integer) do
         Res := Local_Res;
      end Result;
   end Helper;

   N, Sum: Integer;

begin
   Print("give natural");
   N := Getint;
   Worker.Start(1, N);
   Worker.Result(Sum);
   Print("Summe= " & Sum);
end Arbeitsteilung2;

----------------------------------------------------------------------
16 pohlmann@pavian:Arbeitsteilung2
give natural
100
Summe= 5050
\end{code}

%Folie 90
\subsection{Beispiel 3}
Dieselbe Teilung der Arbeit, Organisation und Datenflu� fast genauso: Aber
jetzt "`Rendezvous zu Dritt"' beim abschlie�enden Resultat einsammeln.

%% INSERT: Skizze (med, med) no info, left out!

%Folie 91
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen 1..n/2, n/2+1..n
--          erste task startet die zweite und bildet Gesamtergebnis
--                                        mit three-way-rendezvous
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Arbeitsteilung2a is

   task Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Worker;

   task Helper is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Helper;

   task body Worker is
      Local_From, Local_To, Local_Res, Remote_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Helper.Start(Local_From, (Local_From + Local_To)/2);
      Local_Res := 0;
      for I in ((Local_From + Local_To)/2 +1)..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Result(Res: out Integer) do  --Rendezvous zu dritt
         Helper.Result(Remote_Res);
         Res := Local_Res + Remote_Res;
      end Result;
   end Worker;

   task body Helper is
      Local_From, Local_To, Local_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Local_Res := 0;
      for I in Local_From..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Result(Res: out Integer) do
         Res := Local_Res;
      end Result;
   end Helper;

   N, Sum: Integer;

begin
   Print("give natural");
   N := Getint;
   Worker.Start(1, N);
   Worker.Result(Sum);
   Print("Summe= " & Sum);
end Arbeitsteilung2a;

----------------------------------------------------------------------
30 pohlmann@pavian:Arbeitsteilung2a
give natural
100
Summe= 5050
\end{code}

%Folie 92
\subsection{Beispiel 4}
Dieselbe Teilung der Arbeit und Grundstruktur, aber jetzt gibt die Helper-Task
das Ergebnis \emph{aktiv} zur�ck.
Dazu erh�lt die Helper-Task beim Start eine sog. "`call-back"' Prozedur, die
R�ckruf (bei entsprechendem entry) beim Auftraggeber ausf�hrt.

%% INSERT: Skizze (med, med) done!
%\begin{figure}[htbp]
\includegraphics{rendBsp4.eps}
%\end{figure}

%Folie 93
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen 1..n/2, n/2+1..n
--          erste task startet die zweite und bildet Gesamtergebnis
--                                        mit call-back procedure
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Arbeitsteilung2b is

   task Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
      entry Call_Back(Res: Integer);
   end Worker;

   type Call_Back_Proc is access procedure(X: Integer);

   procedure Call_Back_Worker(R: Integer) is --proc must not be deeper than access type
   begin
      Worker.Call_Back(R);
   end Call_Back_Worker;

   task Helper is
      entry Start(From, To: Integer; Cb: Call_Back_Proc);
   end Helper;

   task body Worker is
      Local_From, Local_To, Local_Res, Remote_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Helper.Start(Local_From, (Local_From + Local_To)/2, Call_Back_Worker'access);
      Local_Res := 0;
      for I in ((Local_From + Local_To)/2 +1)..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Call_Back(Res: Integer) do
         Remote_Res := Res;
      end Call_Back;
      accept Result(Res: out Integer) do
         Res := Local_Res + Remote_Res;
      end Result;
   end Worker;

   task body Helper is
      Local_From, Local_To, Local_Res: Integer;
      My_Call_Back_Proc: Call_Back_Proc;
   begin
      accept Start(From, To: Integer; Cb: Call_Back_Proc) do
         Local_From := From;
         Local_To := To;
         My_Call_Back_Proc := Cb;
      end Start;
      Local_Res := 0;
      for I in Local_From..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      My_Call_Back_Proc(Local_Res);
   end Helper;

   N, Sum: Integer;

begin
   Print("give natural");
   N := Getint;
   Worker.Start(1, N);
   Worker.Result(Sum);
   Print("Summe= " & Sum);
end Arbeitsteilung2b;

----------------------------------------------------------------------
47 pohlmann@pavian:Arbeitsteilung2b
give natural
100
Summe= 5050
\end{code}

%Folie 94
Klar: Helper Task k�nnte auch direkt entsprechendes entry von Worker Task
aufrufen, aber dann w�re das R�ckgabe-Ziel fest in den Programmtext von Helper
zu schreiben, d.\,h. Helper k�nnte nicht von \emph{mehreren} Klienten-Tasks
benutzt werden!

%Folie 95
\subsection{Beispiel 5}
�hnlich Beispiel 2, aber Helper nach Bedarf \emph{dynamisch} erzeugt.

\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen 1..n/2, n/2+1..n falls n>50,
--          erste task erzeugt und startet die zweite und bildet
--          Gesamtergebnis
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Arbeitsteilung3 is

   task Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Worker;

   task type Helper is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Helper;

   type Helper_Ptr is access Helper;

   task body Worker is
      Local_From, Local_To: Integer;
      Local_Res, Remote_Res: Integer := 0;
      H: Helper_Ptr;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      if Local_To-Local_From >50 then
         H := new Helper;
         H.Start(Local_From, (Local_From+Local_To)/2);
         for I in ((Local_From + Local_To)/2 +1)..Local_To loop
            Local_Res := Local_Res+I;
         end loop;
         H.Result(Remote_Res);
      else
         for I in Local_From+Local_To..Local_To loop
            Local_Res := Local_Res + 1;
         end loop;
      end if;
      accept Result(Res: out Integer) do
         Res := Local_Res + Remote_Res;
      end Result;
   end Worker;

   task body Helper is
      Local_From, Local_To, Local_Res: Integer;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      Local_Res := 0;
      for I in Local_From..Local_To loop
         Local_Res := Local_Res+I;
      end loop;
      accept Result(Res: out Integer) do
         Res := Local_Res;
      end Result;
   end Helper;

   N, Sum: Integer;

begin
   Print("give natural");
   N := Getint;
   Worker.Start(1, N);
   Worker.Result(Sum);
   Print("Summe= " & Sum);
end Arbeitsteilung3;

----------------------------------------------------------------------
21 pohlmann@pavian:Arbeitsteilung3
give natural
100
Summe= 5050
\end{code}

%Folie 96
\subsection{Beispiel 6}
Verallgemeinerung von Beispiel 5, aber jetzt zus�tzliche Tasks entsprechend
Bedarf \emph{rekursiv} erzeugt.

%% INSERT: Skizze (med, med) done!
%\begin{figure}[htbp]
\includegraphics{rendBsp6.eps}
%\end{figure}

%Folie 97
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: summiere 1..n.
-- Methode: tasks fuer Teilsummen aus 10 Elementen,
--          tasks nach Bedarf rekursiv erzeugt und gestartet,
--          Ergebnis wandert zurueck durch Erzeugertasks
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Arbeitsteilung4 is

   task type Worker is
      entry Start(From, To: Integer);
      entry Result(Res: out Integer);
   end Worker;

   type Worker_Ptr is access Worker;

   function Get_New_Worker return Worker_Ptr is --Hilfsfunktion, erzeugt neue task
   begin
      return new Worker;
   end Get_New_Worker;

   task body Worker is
      Local_From, Local_To: Integer;
      Local_Res, Remote_Res: Integer := 0;
      Colleague: Worker_Ptr;
   begin
      accept Start(From, To: Integer) do
         Local_From := From;
         Local_To := To;
      end Start;
      if Local_To-Local_From >10 then
         Colleague := Get_New_Worker; --task type cannot be used as type mark within its own body
         Colleague.Start(Local_From+10, Local_To);
         for I in Local_From..(Local_From+9) loop
            Local_Res := Local_Res+I;
         end loop;
         Colleague.Result(Remote_Res);
      else
         for I in Local_From..Local_To loop
            Local_Res := Local_Res+I;
         end loop;
      end if;
      accept Result(Res: out Integer) do
         Res := Local_Res+Remote_Res;
      end Result;
   end Worker;

   N, Sum: Integer;
   W: Worker_Ptr := new Worker;

begin
   Print("give natural");
   N := Getint;
   W.Start(1, N);
   W.Result(Sum);
   Print("Summe= " & Sum);
end Arbeitsteilung4;

----------------------------------------------------------------------
49 pohlmann@pavian:Arbeitsteilung4
give natural
100
Summe= 5050
53 pohlmann@pavian:Arbeitsteilung4
give natural
1000
Summe= 500500
54 pohlmann@pavian:Arbeitsteilung4
give natural
1000000
^C       -- nach 5 Minuten warten ....................................
\end{code}

%Folie 98
\paragraph{Problem}
\begin{enumerate}
\item Zeit?
\item System vertr�gt nicht so viele (100000) Prozesse?
\end{enumerate}

%Folie 99
\begin{code}
----------------------------------------------------------------------
-- Demo: Anzahl tasks
----------------------------------------------------------------------

with Stringpack, Ada.Calendar;
use Stringpack, Ada.Calendar;
procedure Task_Nr_Demo is

   N: Natural;
   Start_Work, End_Work: Time;

   task type T is
      entry Start;
      entry Finish;
   end T;

   task body T is
   begin
      accept Start;
      accept Finish;
   end T;

begin
   Print("give natural");
   N := Getint;
   Start_Work := Clock;
   declare
      Ts: array(1..N) of T;
   begin
      End_Work := Clock;  --for declare tasks
      Print("time spent on decl= " & Float(Ada.Calendar."-"(End_Work, Start_Work)));
      for I in Ts'Range loop Ts(I).Start; end loop;
      for I in Ts'Range loop Ts(I).Finish; end loop;
   end;
   End_Work := Clock;     --for everything
   Print("time spent on everything= " & Float(Ada.Calendar."-"(End_Work, Start_Work)));
end Task_Nr_Demo;

----------------------------------------------------------------------
10 pohlmann@pavian:task_nr_demo
give natural
100
time spent on decl= 0.16
time spent on everything= 0.34
11 pohlmann@pavian:task_nr_demo
give natural
1000
time spent on decl= 2.29
time spent on everything= 7.57
12 pohlmann@pavian:task_nr_demo
give natural
10000
^C       -- nach 15 min...............................................
\end{code}

%Folie 99a
\subsection{Hausaufgabe}
Schreiben Sie ein Programm, in dem mehrere Tasks zu einer
\emph{Flie�band-} (oder pipeline-) \emph{Verarbeitung} kombiniert sind, also \\

%% INSERT: Skizze (med, med) done!
%\begin{figure}[htbp]
\includegraphics{pipeline.eps}
%\end{figure}

Beispiel f�r sowas k�nnte sein:
\paragraph{Textverarbeitung}
\begin{itemize}
\item �berfl�ssige blanks und Formatierungsinformationen entfernen,
\item neue Formatierung vornehmen.
\end{itemize}

%Folie 100
\section{Protected types \& protected objects}
Objekte mit prozedualer Schnittstelle und Aufrufkontrolle (mutual exclusion).

\subsection{Syntax f�r Deklaration}
\begin{code}
protected type P is
  <protected Operations>
  private
     <protected Data Declarations>;
end P;

protected body P is
   <Impl. protected Operations>
end P;
\end{code}

\begin{itemize}
\item Es gibt wieder "`einmal"' Objekte vom anonymen Typ.
\item Der private-Teil mit den Attributen des Objekts kann auch fehlen.

%Folie 101
\item Gebrauch wie �blich mit Typen -- z.\,B. in Objektdeklaration {\ttfamily
    p1: P;} --
  \begin{important}
    Protected types sind limited, d.\,h. kein Vergleich, keine Zuweisung.
  \end{important}
\end{itemize}

\paragraph{Beispiel}
\begin{code}
protected Flag is
  procedure Up;
  procedure Down;
  function Read return Boolean;
private
  The_Flag: Boolean := True;
end Flag;

protected body Flag is
   procedure Up is
   begin
      The_Flag := Ture;
   end;
   ...
end Flag;
\end{code}

%Folie 102
\subsection{Semantik}
\begin{description}
\item[Protected procedures] Erlauben zustands�ndernden Zugriff und werden unter 
  \emph{wechselseitigem Ausschlu�} ausgef�hrt, d.\,h. Prozedur hat Objekt f�r
  sich allein, andere Aufrufe einer Operation warten.
\item[Protected functions] Mehrere Aufrufe gleichzeitig m�glich, da nur
  "`read-only"'.
  \begin{important}
    Aber nicht zugleich mit Prozedur!
  \end{important}
\end{description}

Mit protected objects lassen sich mutual exclusion Probleme einfach und
effizient l�sen, siehe Beispiel auf Seite \pageref{code:sd4}.

%Folie 103
\paragraph{Beispiel}
\label{code:sd4}
\begin{code}
with Stringpack, Ada.Calendar;
use Stringpack, Ada.Calendar;
procedure Shared_Demo4 is

   Start_Work, End_Work: Time;
   Anz: Positive := 1_000_000;

   protected Shared_N is
      procedure Incr_N;
      procedure Decr_N;
      function Give_N return Integer;
   private
      N: Integer := 0;
   end Shared_N;

   protected body Shared_N is
      procedure Incr_N is
      begin
         N := N+1;
      end Incr_N;

      procedure Decr_N is
      begin
         N := N-1;
      end Decr_N;

      function Give_N return Integer is
      begin
         return N;
      end Give_N;
   end Shared_N;

   task Up is
      entry Start;
      entry Finish;
   end Up;

   task body Up is
   begin
      accept Start;
      for I in 1..Anz loop
         Shared_N.Incr_N;
      end loop;
      accept Finish;
   end Up;

   task Down is
      entry Start;
      entry Finish;
   end Down;

   task body Down is
   begin
      accept Start;
      for I in 1..Anz loop
         Shared_N.Decr_N;
      end loop;
      accept Finish;
   end Down;

begin
   Start_Work := Clock;  --Zeiterfassung
   Up.Start; Down.Start;
   Up.Finish; Down.Finish;
   Print("n= " & Shared_N.Give_N);
   End_Work := Clock;  --Zeiterfassung
   Print("time spent= " & Float(Ada.Calendar."-"(End_Work, Start_Work)));
end Shared_Demo4;

----------------------------------------------------------------------
3 pohlmann@pavian: shared_demo4
n= 0
time spent= 14.45
\end{code}

%Folie 104

%Folie 105
\begin{important}
  \subsection{Wichtige Einschr�nkung}
\end{important}
Protected operations d�rfen \emph{nicht} "`\emph{potentiell blockierend}"'
sein, d.\,h. nicht dazu f�hren, da� die aufrufende task suspendiert werden
mu�, also ein Proze�wechsel n�tig ist.

\paragraph{Beispiel}
Protected operation ruft \emph{entry} einer task auf! (denn dann mu� die andere
task dran kommen).

\paragraph{Grund}
Andernfalls Komplikationen mit

\begin{description}
\item[Programmlogik] z.\,B. deadlock Gefahr.
\item[\emph{Implementierung} des wechselseitigen Ausschlusses f�r protected
  operations] Unter der genannten Einschr�nkung kann 1-Prozessor Implementierung 
  darin bestehen, da� die, eine protected Operation aufrufende, task bis zur
  Beendigung der Operation \emph{nicht} unterbrochen wird. $\Rightarrow$
  Effizienz.
\end{description}

%Folie 106
aber erlaubt

\begin{itemize}
\item Aufruf von protected operation (eines \emph{anderen} protected objects)
  \emph{innerhalb} einer protected operation, denn das alles bei 1-Prozessor
  Implementierung ununterbrechbar.
\end{itemize}

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{protOpFlow.eps}
%\end{figure}

\begin{important}
  Verst��e gegen die Regel k�nnen nicht immer erkannt werden (wenn erkannt:
  Warnung des Compilers, Laufzeitfehler program error).
\end{important}

%Folie 107
\subsection{Bedingungssynchronisation (conditional synchronisation)}
Operation kann nur ausgef�hrt werden, wenn betroffenes Objekt in einem
bestimmten Zustand ist.\\

Beispiel: Puffer schreiben erfordert: Puffer nicht voll.

Daf�r erlauben protected objects:

\paragraph{Protected entries}
�hnlich wie protected procedures (Parameter, Ausschlu�) aber zus�tzlich mit
\emph{Barriere} ("`barrier"', "`guard"' = Boolscher Ausdruck) die true sein
mu�, damit Operation ausgef�hrt wird.

%Folie 108
\paragraph{Beispiel}
\begin{code}
protected Bahnuebergang is
   procedure Oeffne;
   procedure Schliesse;
   entry Fahre_Weiter;

private
   Offen: Boolean := True;
end Bahnuebergang;

protected body Bahnuebergang is
   procedure Oeffne is
   begin
      Offen := True;
   end Oeffne;

   Procedure Schliesse is
   begin
     Offen := False;
   end Schliesse;

   entry Fahre_Weiter
     when Offen is       --Barriere
   begin
      null;
   end;
end Bahnuebergang;
\end{code}

%Folie 109
Wirkung:

\begin{itemize}
\item Bei Aufruf des entry wird Barriere \emph{ausgewertet}.
  \begin{code}
falls true
   dann Rumpf des entry ausf�hren;
   sonst Aufrufer wartend setzen;
  \end{code}

\item Bei �nderung des Zustands (= Ausf�hrung von protected procedure oder
  entry) wird Barriere \emph{wieder ausgewertet}.
  \begin{code}
wenn true
   dann lasse einen der darauf wartenden Prozesse weitermachen;
  \end{code}

  \begin{important}
    Unbedingt beachten: tasks, die "`innerhalb"' des protected objects auf
    Barriere warten, haben \emph{Vorrang} vor tasks, die "`von au�en"'
    protected objects aufrufen.
  \end{important}
\end{itemize}

%Folie 110
Barrieren (Boolsche Ausdr�cke)
\begin{itemize}
\item D�rfen \emph{nicht} Parameter des entry benutzen.
\item D�rfen globale Variablen enthalten, was \emph{nicht} zu empfehlen ist!
\end{itemize}

\paragraph{Beispiel}
\emph{Producer-Consumer-Problem} mit endlichem \emph{Puffer}
(vgl. \ref{sec:prodConsProblem}, Seite \pageref{sec:prodConsProblem}).

\begin{description}
\item[Producer] kann nur schreiben, wenn Puffer nicht voll,
\item[Consumer] kann nur lesen, wenn Puffer nicht leer.
\end{description}

im Beispiel:
\begin{description}
\item[Producer] erzeuge 1\dots n
\item[Consumer] summiere Zahlen
\end{description}

%Folie 111
\label{code:bounded_buffer}
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: producer-consumer (summation_of_naturals) with bounded buffer
-- Methode: tasks for producer-consumer (simple sum_of_naturals problem)
--          protected object for buffer
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Bounded_Buffer is

   Length: constant Natural := 10;
   type Buff_Type is array(0..Length-1) of Natural;

   protected Buffer is
      entry Insert(D: Natural);
      entry Take(D: out Natural);
   private
      B: Buff_Type;
      In_Ptr, Out_Ptr: Natural := 0;
      Count: Natural := 0;
   end Buffer;

   task Producer is
      entry Start(How_Many: Natural);
   end Producer;

   task Consumer is
      entry Start(Break: Natural);
   end Consumer;

   task body Producer is
      Local_How_Many: Natural;
   begin
      accept Start(How_Many: Natural) do
         Local_How_Many := How_Many;
      end Start;

      Consumer.Start(Local_How_Many+1);

      for I in 1.. (Local_How_Many+1) loop
         Buffer.Insert(I);
      end loop;
   end Producer;

   task body Consumer is
      Over, Item, Result: Natural;
   begin
      accept Start(Break: Natural) do
         Over := Break;
      end Start;

      Result := 0;
      Buffer.Take(Item);
      while Item /= Over loop
         Result := Result+Item;
         Buffer.Take(Item);
      end loop;
      Print("Summe= " & Result);
   end Consumer;

   protected body Buffer is
      entry Insert(D: Natural)
        when Count < Length is
      begin
         B(In_Ptr) := D;
         In_Ptr := (In_Ptr +1) mod Length;
         Count := Count +1;
      end Insert;

      entry Take(D: out Natural)
        when Count > 0 is
      begin
         D := B(Out_Ptr);
         Out_Ptr := (Out_Ptr +1) mod Length;
         Count := Count -1;
      end Take;
   end Buffer;

   N: Natural;

begin
   Print("give natural");
   N := Getint;
   Producer.Start(N);
end Bounded_Buffer;

----------------------------------------------------------------------
11 pohlmann@pavian:bounded_buffer
give natural
100
Summe= 5050
\end{code}

%Folie 112

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{bounded_buffer.eps}
%\end{figure}

%Folie 113
\section{Tasking \& Exceptions}
Ist wieder hochkomplizierte Materie; hier die fundamentals. Als Neuerung gibt
es:

\subsection{tasking-error}
Ausgel�st ("`raised"') wenn

\paragraph{Beliebige exception \emph{w�hrend task Aktivierung}}
Dann:
\begin{itemize}
\item Task wird sofort \emph{completed} (= Totgeburt)
\item Tasking\_error wird ausgel�st im \emph{Eltern-task} ($\Rightarrow$
  Begr�bnis organisieren)
\end{itemize}

Beispiel:

%Folie 114
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo1 is

   task T;

   task body T is
      function F return Natural is begin return 0; end F;
      N: Natural := 1 mod F;         -- 1/0 in init!
   begin
      null;
   end T;

begin
   null;
exception
   when Tasking_Error => Print("Fehler bei Aktivierung");
end Exception_Demo1;

----------------------------------------------------------------------
6 pohlmann@pavian:exception_demo1
Fehler bei Aktivierung
\end{code}

%Folie 115
Tasking\_error wird weiters ausgel�st bei

\paragraph{Kommunikationsproblemen}
Aufruf eines entry einer task, die schon "`completed ist"', also den Aufruf
nicht mehr entgegennehmen kann (= kein Anschlu� unter dieser Nummer).\\

Dann: \emph{Tasking\_error} wird ausgel�st bei \emph{Aufrufer}.

\begin{important}
  F�r diesen Fall ist es egal, ob aufgerufener task \emph{normal} endete oder
  z.\,B. mit "`\emph{abort}"' abgeschossen wurde.
\end{important}

\paragraph{Beispiel}

%Folie 116
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo2 is

   task T1;
   task T2 is
      entry Hallo;
   end T2;

   task body T1 is
   begin
      loop
         T2.Hallo;
      end loop;

   exception
      when Tasking_Error => Print("Fehler bei entry call");
   end T1;

   task body T2 is
   begin
      loop
         accept Hallo;
      end loop;
   end T2;

begin
   abort T2;
end Exception_Demo2;

----------------------------------------------------------------------
9 pohlmann@pavian:exception_demo2
Fehler bei entry call
\end{code}

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{excDemo2.eps}
%\end{figure}

%Folie 117
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo2a is

   task T1;
   task T2 is
      entry Hallo;
   end T2;

   task body T1 is
   begin
      loop
         T2.Hallo;
      end loop;

   exception
      when Tasking_Error => Print("Fehler bei entry call");
   end T1;

   task body T2 is
   begin
      for I in 1..4711 loop
         accept Hallo;
      end loop;
   end T2;

begin
   null;
end Exception_Demo2a;

----------------------------------------------------------------------
3 pohlmann@pavian:exception_demo2a
Fehler bei entry call
\end{code}

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{excDemo2a.eps}
%\end{figure}

%Folie 118
Jetzt umgekehrte Perspektive: wie \emph{wirkt} das Ausl�sen einer exception
\emph{auf} task?

\paragraph{Exception ausgel�st durch gew�hnliche \emph{Anweisung} im
  \emph{Rumpf} einer task}
\begin{code}
falls task besitzt passenden handler
   dann f�hre handler aus;
        beende task;
   andernfalls task stirbt;
\end{code}

\begin{important}
  Man beachte: Im 2. Fall stirbt die task sang- und klanglos, \emph{ohne} letzte 
  Worte, Testament, etc., \emph{ohne} Propagation der exception irgendwohin
  (Grund: task $\sim$ selbst�ndiges Programm).
  $\Rightarrow$ zumindest zum \emph{Debuggen} versehe man jede task mit einem
  exception handler, der Tod und Todesursache anzeigt!
\end{important}

%Folie 119
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo3 is

   task T;

   task body T is
      function F return Natural is begin return 0; end F;
      N: Natural;
   begin
      N := 1 mod F;     -- 1/0 in body => exiting
      Print("alles ok");
   end T;

begin
   Print("fertig");

exception
   when others => Print("Fehler in task");
end Exception_Demo3;

----------------------------------------------------------------------
5 pohlmann@pavian:exception_demo3
fertig
\end{code}
\begin{important}
  Keiner hat's gemerkt!
\end{important}

%Folie 120
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo4 is

   task T;

   task body T is
      function F return Natural is begin return 0; end F;
      N: Natural;
   begin
      N := 1 mod F;     -- 1/0 in body => exiting
      Print("alles ok");

   exception         -- handler in task
      when others => Print("Fehler in body");
   end T;

begin
   Print("fertig");

exception
   when others => Print("Fehler in task");
end Exception_Demo4;

----------------------------------------------------------------------
13 pohlmann@pavian:exception_demo4
Fehler in body
fertig
\end{code}
\begin{important}
  So sollte man's machen!
\end{important}

%Folie 121
\paragraph{Exception tritt auf \emph{w�hrend Rendezvous}}
(d.\,h. innerhalb der Ausf�hrung des accept-statements).

\subparagraph{Fall 1}
Accept statement enth�lt selbst keinen handler. \\
$\Rightarrow$ Exception wird propagiert zu beiden Beteiligten, genauer: Wieder
ausgel�st auf der Ebene des entry-accept \emph{und} des entry-calls. \\
$\Rightarrow$ Dann unabh�ngige Behandlung durch die beiden tasks, also im
Idealfall: Beide haben eigenen handler.

\subsubparagraph{Beispiel}

%Folie 122
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo5 is

   task T1;
   task T2 is
      entry Hallo;
   end T2;

   task body T1 is
   begin
      loop
         T2.Hallo;
      end loop;

   exception
      when Constraint_Error => Print("t1: Fehler in rendezvous");
   end T1;

   task body T2 is
      function F return Natural is begin return 0; end F;
      N: Natural;
   begin
      loop
         accept Hallo do
            N := 1 mod F;     -- 1/0 in Rendezvous
         end Hallo;
      end loop;

   exception
      when Constraint_Error => Print("t2: Fehler in rendezvous");
   end T2;

begin
   null;
end Exception_Demo5;

----------------------------------------------------------------------
15 pohlmann@pavian:exception_demo5
t2: Fehler in rendezvous
t1: Fehler in rendezvous
\end{code}

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{excDemo5.eps}
%\end{figure}

%Folie 123
\subparagraph{Fall 2}
Accept statement enth�lt geeigneten handler $\Rightarrow$ Exception wird lokal
behandelt, und alles ist gut!

\begin{important}
  Folgendes Beispiel erbrachte nicht den gew�nschten Effekt, sondern (bei 2
  Unix Implementierungen von GNAT) einen Programmabbruch.
\end{important}

wegen

\begin{description}
\item["`Floating Exception"'] nix Ada! Vermutlich: System versucht doch noch
  exception zuzustellen und wei� nicht wo.
\end{description}

\subsection{Hausaufgabe}
Probieren Sie dieses Beispiel und/oder Varianten auf Ihrer Maschine aus; suchen 
Sie in der Literatur oder (besser) im Netz nach Aufkl�rung!

%Folie 124
\begin{code}
with Stringpack; use Stringpack;
procedure Exception_Demo6 is

   task T1;
   task T2 is
      entry Hallo;
   end T2;

   task body T1 is
   begin
      for I in 1..3 loop
         T2.Hallo;
      end loop;

   exception
      when others => Print("t1: Fehler in rendezvous");
   end T1;

   task body T2 is
      function F return Natural is begin return 0; end F;
      N: Natural;
   begin
      for I in 1..3 loop
         accept Hallo do
            N := 1 mod F;     -- 1/0 in Rendezvous

         exception
            when Constraint_Error => Print("t2: Fehler in rendezvous");
         end Hallo;
      end loop;
   end T2;

begin
   null;
exception
   when Constraint_Error => Print("main: Fehler in rendezvous");
end Exception_Demo6;

----------------------------------------------------------------------
37 pohlmann@pavian:exception_demo6
t2: Fehler in rendezvous
Floating exception
\end{code}

\paragraph{Anmerkung des Tippers}
Ich habe das Beispiel auf meinem Rechner(Linux Kernel 2.0.33, gcc version
egcs-2.90.23 980102 (egcs-1.0.1 release), GNAT 3.10p) ausprobiert und erhielt
das gew�nschte Ergebnis:
\begin{code}
rbla@bravo:exception_demo6
t2: Fehler in rendezvous
t2: Fehler in rendezvous
t2: Fehler in rendezvous                             
\end{code}

%Folie 125
\section{Exkurs: Diskriminanten (= Parameter f�r Typen)}

\begin{itemize}
\item sind Typkomponenten mit speziellen Eigenschaften.
\item gibt es f�r zusammengesetzte Typen (au�er f�r arrays!).
\item m�ssen selber von \emph{diskreten} oder \emph{access} Typ sein!
\end{itemize}

\subsection{Klassischer Fall: \emph{Record} Typ mit Diskriminante}

\paragraph{Beispiel}
\begin{code}
type Matrix_Type is
   array(Positive range <>, Positive range <>) of Float;

type Square_Matrix(size: Positive) is record
   Matrix: Matrix_Type(1..Size, 1..Size);
end record;
\end{code}

Also:
\begin{itemize}
\item Record Typ mit \emph{zwei} Komponenten: 1. Size, 2. Matrix
\item 
  \begin{description}
  \item[1. Komponente] Diskriminante
  \item[2. Komponente] gew�hnliche record Komponente aber \emph{abgest�tzt} auf 
    Diskriminante.
  \end{description}
\end{itemize}

%Folie 126
Anwendung z.\,B. so:
\begin{code}
M1: Square(3);
M2: Square(Size => 3);
M3: Square := (3, (1..3 => (1..3 => 0.0)));
\end{code}

Zugriff auf Diskriminante wie sonst auf Komponente, z.\,B
\begin{code}
M2.Size
\end{code}

\begin{important}
Klar: Wert von Diskriminante ist bei Objektvereinbarung n�tig und sp�ter nicht
mehr �nderbar.
\end{important}

Wichtiger Spezialfall:
\begin{description}
\item[Variante Records] Struktur des Records h�ngt ab von der Diskriminante.
\end{description}

z.\,B.
\begin{code}
type Sex is (Male, Female);

type Person(Which: Sex) is record
   Name: ...;
   case Which is
      when Female =>
         Children: Integer;
      when Male =>
         null;
   end case;
end record;
\end{code}

%Folie 127
\begin{important}
Variante Records sind primitiver Ersatz f�r Klassen/Vererbung $\Rightarrow$
Literatur f�r N�heres.
\end{important}

\subsection{Task types mit Diskriminante}
�hnlich: protected objects. \\
Diskriminanten sind insbesondere zur Spezialisierung in Initialisierung
n�tzlich:

\paragraph{Beispiel}

\begin{itemize}
\item Initialisierung durch entry
  \begin{code}
task type Hund is
   entry Start(Wie_Oft: Positive);
end Hund;

task body Hund is
   N: Positive;
begin
   accept Start(Wie_Oft: Positive) do
      N := Wie_Oft;
   end Start;

   for I in 1..N loop
      Print("wau wau");
   end loop;
end Hund;
  \end{code}

%Folie 128
\item Initialisierung �ber Diskriminante
  \begin{code}
task type Hund(Wie_Oft: Positive);

task body Hund is
begin
   for I in 1..Wie_Oft loop
      Print("wau wau");
   end loop;
end Hund;
  \end{code}
\end{itemize}

Unterschiede:
\begin{itemize}
\item Entry kann Werte von beliebigem Typ einbringen,
\item Entry ist synchronisierend,
\item Diskriminante oft bequemer.
\end{itemize}

%Folie 129
\chapter{Rendezvous mit Alternativen}
\paragraph{Problem}
Proze�, der \emph{entry call} oder \emph{accept} Anweisung ausf�hrt, ist
dadurch \emph{festgelegt}: Er \emph{mu�} warten, bis Rendezvous zustande kommt;
aber z.\,.B m�glich
\begin{itemize}
\item da� kein \emph{Partner} mehr \emph{vorhanden} ($\Rightarrow$
  Tasking\_error),
\item da� Rendezvous nur sinnvoll, wenn \emph{sofort} oder \emph{bald}
  stattfindet,
\item da� Proze� \emph{verschiedene} Rendezvous eingehen k�nnte.
\end{itemize}
Also mehr Flexibilit�t n�tig!

Wir beginnen mit entsprechdener Differenzierung beim accept-statement.

%Folie 130
\section{Accept-Alternativen}
\begin{code}
<selective_accept> ::=
   select
     [when <condition> =>]
     <selective_accept_alternative>

  {or
     [when <condition> =>]
     <selective_accept_alternative>}

  [else
     <statement_sequence>]
   end select;
\end{code}
Wobei
\begin{code}
<selective_accept_alternative> ::=
   <accept_alternative>
 | <delay_alternative>
 | <terminate_alternative>
\end{code}
Wir betrachten nun diese drei M�glichkeiten.

%Folie 131
\subsection{accept\_alternative}
\begin{code}
<accept_alternative> ::=
   <accept_statement> [<statement_sequence>]
\end{code}
Erlaubt warten auf \emph{mehrere} Rendezvous und Akzeptieren der \emph{ersten}
M�glichkeit; typisch n�tig f�r \emph{server tasks}, die "`ewig"'
\emph{verschiedene Dienste} aus�ben.

\begin{code}
task Server is
   entry Service1(...);
   ...
   entry ServiceN(...);
end Server;

task body Server is
   ...
begin
   loop
      select
         accept Service1(...) do
            ...
         end Service1;
         -- internal work 1 --
      or
         ...
      or
         accept ServiceN(...) do
           ...
         end ServiceN;
         -- internal work N --
      end select;
   end loop;
end Server;
\end{code}

%Folie 132
\paragraph{Wirkung}
\begin{itemize}
\item Bei jedem Schleifendurchgang 1 Rendezvous,
\item wenn \emph{kein} call vorhanden $\Rightarrow$ Server wartet, bis ein(!)
  Anruf kommt,
\item wenn calls f�r \emph{mehrere} entries vorhanden $\Rightarrow$ akzeptiere
  \emph{einen} (unbestimmt welcher).
\end{itemize}

\subsection{Guards}
Erlauben, die select-Alternativen durch Bedingungen zu sch�tzen.
\begin{code}
select
   when -- Dienst m�glich -- =>
      accept Service1(...) do
         ...
      end Service1;
      -- interne Arbeit --
or
   ...  
end select;
\end{code}

\paragraph{Wirkung}
\begin{itemize}
\item Bedingungen werden ausgewertet bei \emph{Beginn} der Ausf�hrung des
  select-statements.
%Folie 133
\item Alternativen \emph{ohne} Bedingungen oder mit \emph{wahren} Bedingungen
  hei�en \emph{offen} (open), die anderen \emph{geschlossen} (closed).
  \begin{important}
    Program\_error, wenn alle Alternativen geschlossen.
  \end{important}
\item Offene Alternativen werden behandelt wie beim einfachen select.
\item Wie bei guards bei protected objects gilt: Guard darf nicht entry
  Parameter benutzen, guard sollte nicht globale Variablen benutzen.
\end{itemize}

\subsection{terminate Alternative}
\begin{code}
<terminate_alternative> ::= terminate;
\end{code}
Erlaubt \emph{Terminierung} einer "`endlosen"' server-task, wenn keine Klienten 
mehr \emph{da sind}. Z.\,B.
\begin{code}
loop
   select
      accept Service1(...) do
         ...
      end Service1;
   or
      ...
   or terminate;
   end select;
end loop;  
\end{code}

%Folie 134
\paragraph{Wirkung}
Server wird \emph{completed} wenn
\begin{itemize}
\item Elterntask ist completed.
\item Alle anderen task mit derselben Elterntask sind schon fertig \emph{oder}
  warten selber in einem select-statement mit terminate-Alternative.
\end{itemize}

\subsection{Methodische Bemerkung}
Bei Entwurf/Programmierung von \emph{Servern} hat man 2 M�glichkeiten:
\begin{enumerate}
\item \label{enum:protObj}
  \emph{protected object} mit service = protected operation oder entry
\item \label{enum:task}
\emph{task} mit Endlosschleife + select accept service
\end{enumerate}

Variante \ref{enum:protObj} (= \emph{passives} Objekt) ist oft besser (einfaches 
Programm, effiziente Realisierung), es sei denn der Server mu� \emph{zwischen}
den Diensten lokal Arbeit leisten (aufr�umen, n�chsten Dienst vorbereiten,
\dots), wodurch der Klient nicht verz�gert werden sollte.

%Folie 135
\subsection{Beispiel: server task}
Vergleiche L�sung Seite \pageref{code:bounded_buffer}.

\begin{code}
----------------------------------------------------------------------
-- Aufgabe: producer-consumer (summation_of_naturals) with bounded buffer
-- Methode: tasks for producer-consumer (simple sum_of_naturals problem)
--          AND task for buffer
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Bounded_Buffer2 is

   task Buffer is                -- server task
      entry Insert(D: Natural);
      entry Take(D: out Natural);
   end Buffer;

   task Producer is
      entry Start(How_Many: Natural);
   end Producer;

   task Consumer is
      entry Start(Break: Natural);
   end Consumer;

   task body Producer is
      Local_How_Many: Natural;
   begin
      accept Start(How_Many: Natural) do
         Local_How_Many := How_Many;
      end Start;

      Consumer.Start(Local_How_Many +1);
      for I in 1..(Local_How_Many +1) loop
         Buffer.Insert(I);
      end loop;
   end Producer;

task body Consumer is
   Over, Item, Result: Natural;
begin
   accept Start(Break: Natural) do
      Over := Break;
   end Start;

   Result := 0;
   Buffer.Take(Item);
   while Item /= Over loop
      Result := Result +Item;
      Buffer.Take(Item);
   end loop;

   Print("Summe= " & Result);
end Consumer;

task body Buffer is
   Length: constant Natural := 10;
   B: array(0..Length-1) of Natural;
   In_Ptr, Out_Ptr: Natural := 0;
   Count: Natural := 0;
begin
   loop
      select
         when Count < Length =>
            accept Insert(D: Natural) do
               B(In_Ptr) := D;
            end Insert;

            In_Ptr := (In_Ptr +1) mod Length;
            Count := Count +1;
      or
         when Count > 0 =>
            accept Take(D: out Natural) do
               D := B(Out_Ptr);
            end Take;

            Out_Ptr := (Out_Ptr +1) mod Length;
            Count := Count -1;
      or
         terminate;
      end select;
   end loop;
end Buffer;

N: Natural;
begin
   Print("give natural");
   N := Getint;
   Producer.Start(N);
end Bounded_Buffer2;

----------------------------------------------------------------------
45 pohlmann@mandrill:bounded_buffer2
give natural
100
Summe= 5050
\end{code}

%Folie 136

%Folie 137
\subsection{Beispiel: Primzahlen durch Siebmethode}
In der VL Programmieren 3, Funktionale Programmierung, haben wir Programmierung 
mit "`\emph{unendlichen Listen}"' kennengelernt; f�r solche unendlichen Listen
l��t sich ein (mehr oder weniger vollst�ndiges) �quivalent schaffen durch
\emph{Prozesse}, die auf Aufforderung das \emph{n�chste Element} der Liste
erzeugen; Realisierung durch:
\begin{itemize}
\item Passive Objekte mit internem Zustand + give\_next-Operation.
\item Aktive Objekte wie Ada task mit give\_next-entry.
\end{itemize}
Hier: Illustration mittels task.

\paragraph{Anwendungsbeispiel: Primzahlerzeugung durch Sieben} \ \\
Dazu:

Beginne mit Zahlenfolge $s_1$ = 2, 3, 4, 5, \dots; \\
Erzeuge $s_{i+1}$ durch Elimination aller Vielfachen des ersten Elements von
$s_i$ aus $s_i$; \\
Die Kopfelemente dieser Folgen sind die Primzahlen.

%Folie 138
Also:
\begin{code}
prim|
[ 2,| 3,  4,  ... ]  Startfolge s1
[ 3,| 5,  7,  ... ]             s2
[ 5,| 7, 11,  ... ]             s3
...                             ...
\end{code}
in \emph{Haskell}
\begin{code}
crossout :: [Int]->[Int]
crossout (x:xs) = filter ({\bkslash}y -> y `rem` x /= 0) xs

primeNumbers :: [Int]
primeNumbers = map head (iterate crossout [2..])
\end{code}
Dieser elegante 4-Zeiler l��t sich mit Ada tasks ungef�hr so nachmachen:

\begin{description}
\item[task type seq] repr�sentiert Folge ganzer Zahlen, entweder 2, 3, 4, \dots 
  (Start) oder crossout (Vorg�ngerfolge).
\item[task seq\_of\_seqs] repr�sentiert Folge \emph{von} solchen Folgen.
\end{description}

%Folie 139
\begin{code}
----------------------------------------------------------------------
-- Primzahlen durch Siebmethode:
-- erzeuge Folge von Folgen [[2,3,4,5,...],[3,5,7,9],...]
-- durch Elimination aller Fielfachen des 1. Elements der Vorgaengerfolge;
-- die jeweils ersten Elemente bilden Folge der Primzahlen
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Primes is

   ----------------------------------------------- Typ der Zahlenfolge
   type Seq;  -- incomplete type declaration to allow recursive construction
   type A_Seq is access Seq;

   task type Seq(Pred: A_Seq) is     -- discriminant names predecessor sequence
      entry Head(Item: out Integer); -- gives first element
      entry Next(Item: out Integer); -- gives all elements on iterated calls
   end Seq;

task body Seq is
   First, Elem, Prime: Integer;
begin
   if Pred = null then  -- base case: seq= 2,3,4,5,...
      First := 2; Elem := 2;
      loop
         select
            accept Head(Item: out Integer) do
               Item := First;
            end Head;
         or
            accept Next(Item: out Integer) do
               Item := Elem;
            end Next;

            Elem := Elem +1;
         or
            terminate;
         end select;
      end loop;

   else  -- general case: seq = crossout multiples in predecessor seq
      Pred.Head(Prime); Pred.Next(Elem);
      while (Elem mod Prime = 0) loop
         Pred.Next(Elem);
      end loop;
      First := Elem;

      loop
         select
            accept Head(Item: out Integer) do
               Item := First;
            end Head;
         or
            accept Next(Item: out Integer) do
               Item := Elem;
            end Next;

            Pred.Next(Elem);
            while (Elem mod Prime = 0) loop
               Pred.Next(Elem);
            end loop;
         or
            terminate;
         end select;
      end loop;
   end if;
end Seq;  ------------------------------------------------------------

----------------------------------------------- Folge von Zahlenfolgen
task Seq_Of_Seqs is
   entry Next(Item: out A_Seq);  -- gives all elements on iterated calls
end Seq_Of_Seqs;

task body Seq_Of_Seqs is
   Previous, Elem: A_Seq;  -- previous = null on initialization!
begin
   loop
      Elem := new Seq(Previous); -- create next seq (with a link to previous sequence)
      select
         accept Next(Item: out A_Seq) do
            Item := Elem;
         end Next;
      or
         terminate;
      end select;

      Previous := Elem;
   end loop;
end Seq_Of_Seqs; -----------------------------------------------------

Res, From, To: Integer;
Current_Seq: A_Seq;
begin
   Print("give from and to");
   From := Getint;
   To := Getint;
   for I in 1..From-1 loop  -- skip
      Seq_Of_Seqs.Next(Current_Seq);
   end loop;

   for I in From..To loop
      Seq_Of_Seqs.Next(Current_Seq);
      Current_Seq.Head(Res);
      Print(">" & Res);
   end loop;
end Primes;

----------------------------------------------------------------------
25 pohlmann@mandrill:primes
give from and to
1 3
>2
>3
>5
26 pohlmann@madrill:primes
100 100
>541
\end{code}

%Folie 141

%Folie 142
Klar: L�sung nicht praktikabel f�r gro�e Primzahlen.

\subsection{Hausaufgabe}
\begin{enumerate}
\item Die tasks, die die unendlichen Folgen repr�sentieren, k�nnen nur
  \emph{einen} Klienten bedienen (entry next = Einmal-Durchlauf). �berlegen Sie 
  sich eine Realisierung, die beliebig viele Klienten bedienen kann (und dazu
  bereits erzeugte Folgenelemente jeweils speichert).

\item In der Literatur (z.\,B. Barnes, Burns/Wellings) wird die
  Primzahl/Sieb-Aufgabe meist anders gel�st, n�mlich mit umgekehrter
  Aufrufstruktur: Zahlenfolge st��t \emph{Nachfolger}-Zahlenfolge an.
  Betrachten (realisieren) Sie eine solche L�sung und �berlegen Sie Vor- und
  Nachteile!
\end{enumerate}

%Folie 143
\subsection{Delay-Alternative}
\begin{code}
<delay_alternative> ::=
   <delay_statement> [<sequence_of_statements>]

<delay_statement> ::=   delay <expr>;
                      | delay until <expr>; 
\end{code}
Wird f�r \emph{timeouts} mit relativer/absoluter Zeitangabe benutzt,
d.\,h. task kann ihre Bereitschaft zu Rendezvous beenden.

\paragraph{Wirkung}
Task f�hrt delay-Alternative aus, falls keines der Rendezvous des
select-statements in der angegebenen Frist/ bis zum angegebenen Zeitpunkt
m�glich ist.

\paragraph{Typische Anwendung}
\begin{itemize}
\item F�hre default-Handlung aus, wenn nichts anderes gew�nscht wurde
  (z.\,B. unterbliebene Initialisierung)

\item L�se Alarm aus, wenn andere task sich nicht als "`lebendig"' erweist
  (d.\,h. meldet).
\end{itemize}

%Folie 144
\begin{code}
----------------------------------------------------------------------
-- Demo: delay alternative
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Watchdog_Demo is

   task type Get_Info;
   type A_Get_Info is access all Get_Info;

   task type Watchdog(For_Whom: A_Get_Info) is
      entry Start(T: Duration);
      entry Ok;
   end Watchdog;

   G: aliased Get_Info;
   W: Watchdog(G'Access);

   task body Get_Info is
      Vs: Varstring;
   begin
      Print("give info");
      W.Start(60.0);
      Vs := Gettext;
      W.Ok;
   end Get_Info;

   task body Watchdog is
      D: Duration;
   begin
      accept Start(T: Duration) do
         D := T;
      end Start;

      select
         accept Ok;
         Print("got it");
      or
         delay D;
         abort For_Whom.all;
         Print("time expired");
      end select;
   end Watchdog;

begin
   null;
end Watchdog_Demo;

----------------------------------------------------------------------
40 pohlmann@mandrill:watchdog_demo
give info
hallo
got it
41 pohlmann@mandrill:watchdog_demo
give info
time expired
\end{code}

\paragraph{Anmerkung des Tippers}
Ich habe das Beispiel auf meinem Rechner(Linux Kernel 2.0.33, gcc version
egcs-2.90.23 980102 (egcs-1.0.1 release), GNAT 3.10p) ausprobiert und erhielt:
\begin{code}
rbla@bravo:watchdog_demo
give info
hallo
got it
rbla@bravo:watchdog_demo
give info
time expired

raised STORAGE_ERROR
\end{code}

%Folie 145
\begin{important}
  Delay-Alternative \emph{nicht verwechseln} mit normalem delay-statement (=
  \emph{verz�gere} task).
\end{important}

\paragraph{Beispiele}
\begin{itemize}
\item Verz�gerung um 10 Sekunden.
  \begin{code}
...
accept E;
delay 10.0;
...
  \end{code}

\item 10 Sekunden auf Rendezvous warten.
  \begin{code}
...
select
   accept E;
or delay 10.0;
end select;
...
  \end{code}

\item 20 Sekunden auf Rendezvous warten.
  \begin{code}
...
select
   accept E;
or 
   delay 20.0;
end select;
...    
  \end{code}

\item 10 Sekunden auf Rendezvous warten; falls keines kommt weitere 10 Sekunden
  verz�gern.
  \begin{code}
...
select
   accept E;
or 
   delay 10.0;
   delay 10.0;
end select;
...        
  \end{code}
\end{itemize}

%Folie 146
\subsection{else-Teil des select-statements}
Wird ausgef�hrt, wenn Rendezvous \emph{nicht sofort} m�glich ist, also
�quivalent:

\begin{code}
...                  ...
select               select
   accept E;            accept E;
or                   else
   delay 0.0;           Statement;
   Statement;        end select;
end select;          ...
...
\end{code}

\begin{important}
  Man vermeide "`\emph{polling}"' d.\,h. st�ndiges Abfragen (busy waiting).
\end{important}

\begin{code}
...
loop
   select
      accept E;
   else
      null;
   end select;
end loop;
...
\end{code}

\begin{important}
  Sinnvolle Anwendungen von "`else"' sind selten!
\end{important}

%Folie 147
\section{Entry-Call mit Alternative}
(hier: f�r Tasks, gilt analog f�r protected objects)

\begin{important}
Anders als bei selective-accept ist bei Aufrufen \emph{nur 1 Alternative}
m�glich.
\end{important}

N�mlich:
\subsection{Timed entry call}
\begin{code}
<timed_entry_call> ::=
   select
      <entry_call_alternative>
   or
      <delay_alternative>
   end select;
\end{code}
wobei
\begin{code}
<entry_call_alternative> ::=
   <entry_call_statement>
      [<statement_sequence>]
\end{code}

%Folie 148
Also z.\,B.:
\begin{code}
loop
   select
      Buffer.Take(X);
      Consume(X);
   or
      delay 5.0;
      raise Alarm;   -- exception
   end select;
end loop;
\end{code}

\paragraph{Wirkung}
Aufrufer wartet f�r die angegebene Zeit, da� Aufruf angenommen wird, also wieder
time-out.

\begin{important}
Time-out betrifft nur Beginn des Rendezvous, \emph{nicht} Ende (insbesondere
Informations�bertragung).
\end{important}

%Folie 149
\subsection{Conditional entry call}
\begin{code}
<conditional_entry_call> ::=
   select
      <entry_call_alternative>
   else
      <statement_sequence>
   end select;
 \end{code}
 
\paragraph{Wirkung}
Rendezvous sofort oder gar nicht, enspricht {\ttfamily timed\_entry\_call} mit
{\ttfamily delay 0.0;}

\begin{important}
  Insbesondere in Schleife (= polling) nur sinnvoll, wenn Aufrufer wirklich was 
  zu tun hat: \\
  {\ttfamily else null;} $\Rightarrow$ busy waiting, kontraproduktiver
  Rechenzeitverbrauch.
\end{important}

%Folie 150
\subsection{Auswahl unter mehreren entry calls}
Ist in Ada \emph{nicht} vorgesehen! Grund: im Allgemeinen gro�er Aufwand f�r
Implementierung. Man kann aber selber \emph{Ersatzl�sungen} bauen:

\begin{enumerate}
\item \label{enum:aufrufumkehr}
  Umkehrung der Aufrufrichtung: call $\leftrightarrow$ accept. \\
  Oft unnat�rlich!
\item Einf�hrung von Hilfstask als Zwischenglied, kann Probleme bei
  \ref{enum:aufrufumkehr} l�sen.
\item \emph{Wiederversuch} (polling) mit "`sinnvollem"' Abstand (ungleich 0,
  eventuell random).
\end{enumerate}

z.\,B.:
\begin{code}
task type Server is
   entry Service;
end Server;

Server_List: array(1..N) of Server;

task Client;

task body Client is
begin
L: loop
       for I in Server_List'Range loop
          select
             Server(I).Service;
             exit L;
          else
             null;
          end select;
       end loop;
       
       delay Some_Ticks;
end loop L;
end Client;
\end{code}

%Folie 151
\begin{itemize}
\item �hnlich: Mischung von entry-calls f�r tasks un protected objects.
\item Klar: Ersatz ist nicht dasselbe wie ein ordentliches select: \\
  \begin{tabular}{l@{$\Rightarrow$}l}
    Kleines Warteintervall & Ineffizient                            \\
    Gro�es Warteintervall  & Langes Warten m�glich (Pr�fung \emph{selten}) \\
  \end{tabular}
\end{itemize}

%Folie 152
\section{Deadlock revisited}
Zur Erinnerung: Wir haben \emph{Verklemmung} (deadlock) in Abschnitt
\ref{cha:semUndMon} in Zusammenhang mit wechselseitigem Ausschlu�
kennengelernt.

Dort: Gebrauch von gemeinsamen Variablen, z.\,B. 2 tasks haben jeweils
sperrendes Signal gesetzt.

Hier: Verklemmungsgefahr bei \emph{Rendezvous}.

\begin{enumerate}
\item \label{enum:rendLock}
  \begin{code}
task T1 is               task T2 is
   entry E1;                entry E2;
end T1;                  end T2;

task body T1 is          task body T2 is
begin                    begin
   T2.E2; (*)          (**) T1.E1;
   accept E1; (**)      (*) accept E2;
end T1;                  end T2;    
  \end{code}

\item \label{enum:rendNoCall}
  \begin{code}
...                           ...
task body T1 is               task body T2 is
begin                         begin
   accept E1;                    accept E2;
   T2.E2;                        T1.E1;
end T1;                       end T2;    
  \end{code}
\end{enumerate}

%Folie 153
Unterschied von \ref{enum:rendLock} und \ref{enum:rendNoCall}:
\begin{description}
\item[\ref{enum:rendLock}] Beide tasks unweigerlich verklemmt.
\item[\ref{enum:rendNoCall}] Keine Verklemmung, wenn es dritte task gibt, die
  E1 oder E2 aufruft. Allerdings: Den letzten bei�t der Hund \dots
\end{description}

Wichtig im \emph{Kampf gegen deadlocks}:
\begin{itemize}
\item Gro�e Sorgfalt bei Entwurft/Verfeinerung von Algorithmen.
\item Vorher Nachdenken (m�glicherweise Beweise f�hren) anstatt auf Tests
  verlassen. Deadlock kann selten sein, kann durch anderweitige Systemaktivit�t 
  verdeckt werden, und grunds�tzlich: "`ewige"' Inaktivit�t kann empirisch
  nicht von "`langer"' aber endlicher Wartezeit unterschieden werden.

%Folie 154
\item Anwendung \emph{methodischer Regeln}, falls f�r konkreten Fall passend,
  z.\,B.: Aufteilung in tasks, die \emph{ausschlie�lich} entry-\emph{call}-statements
  enthalten ("`clients"') und tasks, die \emph{ausschlie�lich}
  entry-\emph{accept}-statements enthalten ("`server"').
\end{itemize}

\chapter{Beispiele}
\section{Readers-Writers-Problem}
Klassisches Problem-"'Muster"' im Bereich wechselseitiger
Ausschlu�/Bedingungssynchronisation, mit vielen m�glichen Verfeinerungen und
auch praktischen Anwendungen.

%Folie 155
\subsection{Gegeben}
Ressource wie "`Datenbasis"' (Tabelle, Datei, \dots) und zwei Klassen von
Nutzern:
\begin{description}
\item[reader] K�nnen \emph{konkurrent} (gleichzeitig, �berlappend) zugreifen.
\item[writer] Ben�tigen \emph{exklusiven} Besitz der Ressource.
\end{description}

\subsection{Gesucht}
Geeignetes Protokoll.

Offensichtliche L�sung in Ada95: \\
Ressource = \emph{protected object} mit \\
{\ttfamily procedure write(\dots)} $\Rightarrow$ exklusiv, darf Zustand �ndern \\
{\ttfamily function read(\dots)} $\Rightarrow$ nicht exklusiv. Aber schlie�t
gleichzeitiges write aus.

%Folie 156
\subsection{Illustration: Ressource = gemeinsame Variable}
\begin{code}
----------------------------------------------------------------------
-- Readers-Writers Demo, mit simpler integer-Variablen
--
-- Version 1: protected object, => no preference for writer,
--                                 no potentially blocking ops
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Readers_Writers1 is

protected Variable is
   procedure Write (X : Integer);
   function Read return Integer;
private 
   V : Integer := 0; -- na ja
end Variable;

protected body Variable is
   procedure Write (X : Integer) is
      begin V := X; end Write;
   function Read return Integer is
      begin return V; end Read;
end Variable;

task type Reader;
task body Reader is
      Local_X : Integer;
   begin
      for I in 1..100000 loop
           Local_X := Variable.Read;
      end loop;
      Print("> " & Local_X);
end Reader;

task type Writer;
task body Writer is
      Local_X : Integer := 1;
   begin
      for I in 1..100000 loop
           Variable.Write(Local_X);
           Local_X := Local_X + 1;
      end loop;
end Writer;

Anz_R, Anz_W : Natural;

begin

   Print("give #readers, #writers"); 
   Anz_R := Getint; Anz_W := Getint;
   declare
       R : array(1..Anz_R) of Reader;
       W : array(1..Anz_W) of Writer;
   begin null; end;

end Readers_Writers1;

----------------------------------------------------------------------
26 pohlmann@mandrill:readers_writers1
give #readers, #writers
3 1
> 97951
> 100000
> 100000
27 pohlmann@mandrill:

43 pohlmann@mandrill:readers_writers1
give #readers, #writers
3 1
> 90700
> 90700
> 90700
44 pohlmann@mandrill:
\end{code}

%Folie 157
\begin{important}
  Nichtdeterminismus des Ablaufs und daher Nichtdeterminiertheit des
  Ergebnisses. Ergebnis = Letzter gelesener Wert bei 100000 Zugriffen.
\end{important}

\subsection{M�ngel der L�sung}
\begin{itemize}
\item Ada erlaubt keine "`blockierenden Operationen in protected operations,
  also z.\,B. I/O.
\item \emph{Starvation} (= Aushungern) der Schreiber m�glich:

%% INSERT: Skizze (easy, low) done!
%\begin{figure}[htbp]
\includegraphics{writerStarvation.eps}
%\end{figure}

\end{itemize}

%Folie 158
Ergebnis unseres Laufs brauchbar, da 1-Prozessor Implementierung vorliegt und
reader wahrscheinlich \emph{nicht} w�hrend seiner read-operation
\emph{unterbrochen}, bei Proze�wechsel aber jeder Proze�typ gleicherma�en
m�glich.

Das umgekehrte Problem -- Leser verhungern wegen Unfairness -- ist auch denkbar:

%% INSERT: Skizze (easy, low) done!
%\begin{figure}[htbp]
\includegraphics{readerStarvation.eps}
%\end{figure}

Erfordert aber "`b�sartiges"' Verhalten der Proze�verwaltung und gen�gend dichte
(h�ufige) Aufrufe von write; praktisch weniger wichtiges Problem und von uns
\emph{nicht} behandelt!

Aber jetzt Verbesserung:
\begin{itemize}
\item Wenn writer Ressource benutzen will, werden \emph{keine neuen}
  Lesew�nsche mehr zugelassen.
\item Protokoll realisiert duch Kontroll-Task, die �ber Ressourcenbenutzung
  Buch f�hrt und �hnlich wie Semaphor-Kombination wirkt.
\end{itemize}

%Folie 159
\begin{code}
----------------------------------------------------------------------
-- Readers-Writers Demo, mit simpler integer-Variablen
--
-- Version 2: control task in package =>  preference for writer,
--                                        potentially blocking ops allowed
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Readers_Writers2 is

   package Variable is
      procedure Write (X : Integer);
      function Read return Integer;
   end Variable;

   package body Variable is

      V : Integer := 0; -- na ja

      task Control is
         entry Start_Read;
         entry Finish_Read;
         entry Start_Write;
         entry Finish_Write;
      end Control;

      task body Control is
         Readers, Writers : Natural := 0;
      begin
         loop
            select
               when Writers = 0  and Start_Write'Count = 0 => -- no writer inside or waiting
                  accept Start_Read;
                  Readers := Readers + 1;
            or
               accept Finish_Read;
               Readers := Readers - 1;
            or
               when Readers = 0 and Writers = 0  =>  -- nobody inside
                  accept Start_Write;
                  Writers := 1;
            or
               accept Finish_Write;
               Writers := 0;
            or
               terminate;
            end select;
         end loop;
      end Control;

      procedure Write (X : Integer) is
      begin
         Control.Start_Write; 
         V := X;
         Control.Finish_Write; 
      end Write;

      function Read return Integer is
         X : Integer;
      begin
         Control.Start_Read;
         X := V;
         Control.Finish_Read;
         return V; 
      end Read;

   end Variable;

   task type Reader;
   task body Reader is
      Local_X : Integer;
   begin
      for I in 1..100000 loop
         Local_X := Variable.Read;
      end loop;
      Print("> " & Local_X);
   end Reader;

   task type Writer;
   task body Writer is
      Local_X : Integer := 1;
   begin
      for I in 1..100000 loop
         Variable.Write(Local_X);
         Local_X := Local_X + 1;
      end loop;
   end Writer;

   Anz_R, Anz_W : Natural;

begin

   Print("give #readers, #writers"); 
   Anz_R := Getint; Anz_W := Getint;
   declare
      R : array(1..Anz_R) of Reader;
      W : array(1..Anz_W) of Writer;
   begin null; end;

end Readers_Writers2;

----------------------------------------------------
35 pohlmann@mandrill:readers_writers2
give #readers, #writers
3 1
> 100000
> 100000
> 100000
36 pohlmann@mandrill:
\end{code}

%Folie 160

%Folie 161
\begin{important}
  Beachte:
\end{important}

\begin{itemize}
\item Zugangskontrolle durch task, aber eigentliche Nutzung der Ressource
  au�erhalb.
\item Alles verpackt in package mit read/write-ops als Schnittstelle, aber
  Protokollimplementierung vor Klient gesch�tzt.
\item Guard vor accept-read ber�cksichtigt Anzahl der bereits wartenden
  Schreiber verm�ge des \emph{Attributs} "`start\_write'count"' = Zahl der
  aktuell wartenden Aufrufer dieses entry.
\end{itemize}

Zum Vergleich: Die folgende Programmversion unterl��t die Bedingung
"`{\ttfamily when start\_write'count = 0}"' und l��t im Beispiel-Lauf die Leser 
\emph{�fter} zum Zuge kommen:

%Folie 162
\begin{code}
----------------------------------------------------------------------
-- Readers-Writers Demo, mit simpler integer-Variablen
--
-- Version 2: control task in package => *no* preference for writer,
--                                       potentially blocking ops allowed
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Readers_Writers2a is

   package Variable is
      procedure Write (X : Integer);
      function Read return Integer;
   end Variable;

   package body Variable is

      V : Integer := 0; -- na ja

      task Control is
         entry Start_Read;
         entry Finish_Read;
         entry Start_Write;
         entry Finish_Write;
      end Control;

      task body Control is
         Readers, Writers : Natural := 0;
      begin
         loop
            select
               when Writers = 0   => -- no writer inside, no preference for writers
                  accept Start_Read;
                  Readers := Readers + 1;
            or
               accept Finish_Read;
               Readers := Readers - 1;
            or
               when Readers = 0 and Writers = 0  =>  -- nobody inside
                  accept Start_Write;
                  Writers := 1;
            or
               accept Finish_Write;
               Writers := 0;
            or
               terminate;
            end select;
         end loop;
      end Control;

      procedure Write (X : Integer) is
      begin
         Control.Start_Write; 
         V := X;
         Control.Finish_Write; 
      end Write;

      function Read return Integer is
         X : Integer;
      begin
         Control.Start_Read;
         X := V;
         Control.Finish_Read;
         return V; 
      end Read;

   end Variable;

   task type Reader;
   task body Reader is
      Local_X : Integer;
   begin
      for I in 1..100000 loop
         Local_X := Variable.Read;
      end loop;
      Print("> " & Local_X);
   end Reader;

   task type Writer;
   task body Writer is
      Local_X : Integer := 1;
   begin
      for I in 1..100000 loop
         Variable.Write(Local_X);
         Local_X := Local_X + 1;
      end loop;
   end Writer;

   Anz_R, Anz_W : Natural;

begin

   Print("give #readers, #writers"); 
   Anz_R := Getint; Anz_W := Getint;
   declare
      R : array(1..Anz_R) of Reader;
      W : array(1..Anz_W) of Writer;
   begin null; end;

end Readers_Writers2a;

----------------------------------------------------
37 pohlmann@mandrill:readers_writers2a
give #readers, #writers
3 1
> 3751    -+
> 3751     | Also Leser viel schneller fertig als Schreiber!
> 4274    -+
38 pohlmann@mandrill:
\end{code}

%Folie 163

%Folie 164
Zur \emph{Korrektheit} der L�sung (= "`readers\_writers2"'):
\begin{description}
\item[Safety] (= "`writer hat exklusiven Gebrauch"') Ist klar, wegen guards und 
  Z�hlern.
\item[No deadlock] Klar, wenn Gebrauch der Ressource nur endlich dauert.
\item[No starvation] Auch klar, wenn Ada-Implementierung offene
  selective-accept-Alternativen fair bedient.
\end{description}

%Folie 165
\begin{important}
  Angegebene L�sung hat \emph{erheblichen Zeitbedarf}, weil pro Zugriff
  (read/write) \emph{2 Rendezvous} n�tig.
\end{important}

Kleine Verbesserungsm�glichkeit: Eigentliche write-T�tigkeit in die task
integrieren und den Z�hler f�r writers sowie finish\_write einsparen:
\begin{code}
select
   ...
or
   when Readers = 0 =>
      accept Start_Write(X: Integer)
        do V := X; end Start_Write;
or
   terminate;
end select;
\end{code}
Also ausnutzen, da� task selber schon den wechselseitigen Ausschlu� herstellt.

\subsection{Alternative}
Statt Kontroll-Task ein \emph{protected-object} mit analoger Struktur nehmen:

%Folie 166
\begin{code}
----------------------------------------------------------------------
-- Readers-Writers Demo, mit simpler integer-Variablen
--
-- Version 3: protected object in package =>  preference for writer,
--                                            potentially blocking ops allowed
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Readers_Writers3 is

   package Variable is
      procedure Write (X : Integer);
      function Read return Integer;
   end Variable;

   package body Variable is

      V : Integer := 0; -- na ja

      protected Control is
         entry Start_Read;
         procedure Finish_Read;
         entry Start_Write;
         procedure Finish_Write;
      private
         Readers, Writers : Natural := 0;
      end Control;

      protected body Control is

                                                      -- no writer waiting or working
         entry Start_Read when Writers = 0 and Start_Write'Count = 0 is   
         begin Readers := Readers + 1; end Start_Read;

         procedure Finish_Read is
         begin Readers := Readers - 1; end Finish_Read;
         
         entry Start_Write when Readers = 0 and Writers = 0   is   -- nobody inside
         begin Writers := 1; end Start_Write;
         
         procedure Finish_Write is
         begin Writers := 0; end Finish_Write;

      end Control;

      procedure Write (X : Integer) is
      begin
         Control.Start_Write; 
         V := X;
         Control.Finish_Write; 
      end Write;

      function Read return Integer is
         X : Integer;
      begin
         Control.Start_Read;
         X := V;
         Control.Finish_Read;
         return V; 
      end Read;

   end Variable;

   task type Reader;
   task body Reader is
      Local_X : Integer;
   begin
      for I in 1..100000 loop
         Local_X := Variable.Read;
      end loop;
      Print("> " & Local_X);
   end Reader;

   task type Writer;
   task body Writer is
      Local_X : Integer := 1;
   begin
      for I in 1..100000 loop
         Variable.Write(Local_X);
         Local_X := Local_X + 1;
      end loop;
   end Writer;

   Anz_R, Anz_W : Natural;

begin

   Print("give #readers, #writers"); 
   Anz_R := Getint; Anz_W := Getint;
   declare
      R : array(1..Anz_R) of Reader;
      W : array(1..Anz_W) of Writer;
   begin null; end;

end Readers_Writers3;

----------------------------------------------------
36 pohlmann@mandrill:readers_writers3
give #readers, #writers
3 1
> 71215
> 89096
> 100000
44 pohlmann@mandrill:readers_writers3
give #readers, #writers
3 1
> 44358
> 45480
> 52115
\end{code}

%Folie 167

%Folie 168
\subsection{Unterschiede} (bei wenigen Testl�ufen)
Variante mit protected-objects
\begin{itemize}
\item ist \emph{schneller}: Einige Sekunden statt Minuten.
\item streut st�rker im Resultat, mit Tendenz zur Bevorzugung von Lesern!
\end{itemize}

Korrektheit (Schreiber verhungert nicht) bleibt nat�rlich erhalten, trotzdem
m�glich, da� "`endliche"' Bevorzugung von Lesern:
\begin{itemize}
\item Wegen anderer task-Verwaltung, also Frage von Implementierung,
  Scheduling, \dots, insbesondere Proze�wechsel bei Rendezvous.
\item Beachte auch Ada-Semantik: Bei Ende von protected procedure/entry werden
  guards neu ausgewertet \emph{und} dann ausf�hrbare entries \emph{sofort}
  (also nicht in Konkurrenz zu \emph{neuen} Ank�nften) ausgef�hrt.
\end{itemize}
$\Rightarrow$ Zur Detail-Gestaltung von Reihenfolgen u.\,�. gibt es Hilfsmittel 
im "`Realtime Annex"'.

%Folie 169
\section{Dining Philosophers}
Traditionsreiches akademisches Problem (Dijkstra '71), oft benutzt, um
N�tzlichkeit von Sprachkonstrukten und Programmiertechniken zu illustrieren. \\

Praktischer Hintergrund:
Prozesse ben�tigen \emph{mehrere} exklusive Betriebsmittel gleichzeitig -- dann 
kann ungeschickte Zuteilung zu \emph{Verklemmung} f�hren, z.\,B. 2 K�che in 1
K�che, 1 Topf, 1 L�ffel, jeder braucht beides. Koch 1 ergreift L�ffel, Koch 2
ergreift Topf $\Rightarrow$ Deadlock. \\

Gebr�uchliche \emph{Vermeidungsstrategie}: Lege fest, da� Prozesse die
Betriebsmittel in \emph{derselben Reihenfolge} belegen.
Z.\,B. 1. L�ffel, 2. Topf $\Rightarrow$ Wenn Koch 1 L�ffel hat, mu� Koch 2
warten, bis Koch 1 fertig.

"`Dining philosophers"' Problem ist so konstruiert, da� diese L�sung nicht m�glich.

%Folie 170
\subsection{Gegeben}
\begin{itemize}
\item Gemeinschaft von (z.\,B.) 5 Philosophen, die ihr Leben mit \emph{Denken}
  und \emph{Essen} zubringen.
\item Speisesaal mit Tisch mit 5 Tellern, 5 Gabeln und Spaghettihaufen
  (unersch�pflich).

%% INSERT: Skizze (med, med) done!
%\begin{figure}[htbp]
\includegraphics{diningPhil.eps}
%\end{figure}

\item Regel: Jeder Philisoph hat seinen Platz (Teller), ben�tigt aber
  \emph{beide} danebenliegenden Gabeln (wobei er eine Gabel nicht mehr
  freigibt, bis er fertig gegessen hat)!
\end{itemize}

\subsection{Gesucht}
Protokoll, das alle Philosophen vor dem Verhungern bewahrt.

(Fragen der Hygiene, des Anstands usw. spielen keine Rolle; es ist aber
zugesichert, da� kein Philosoph endlos i�t oder �ber seinem Teller stirbt!
Anmerkung des Tippers: Auch der Diebstahl einer Gabel sei ausgeschlossen!)

%Folie 171
\subsection{Offensichtlich n�tig}
Stelle exklusiven Gebrauch der Gabeln sicher, z.\,B. Gabel = protected-object
mit
\begin{code}
entry Pick_Up when Frei is
begin Free := False; end Pick_Up;

protected Put_Down is
begin Free := True; end Put_Down;
\end{code}
= bin�res Semaphor.

\begin{description}
\item[Klar] Safety (= keine 2 Philosophen haben dieselbe Gabel).
\item[Aber] \emph{Verklemmung} m�glich: Jeder Philosoph ergreift linke Gabel
  und findet dann rechte Gabel benutzt.
\item[L�sung] Erlaube \emph{h�chstens 4} Philosophen im Speisesaal!
\end{description}

$\Rightarrow$ liveness, denn

%Folie 172
\subsection{Schubfachprinzip (=pigeonhole principle)}
\emph{Jede} Verteilung von n Objekten auf n-1 F�cher mu� in mindestens 1 Fach
mindestens 2 Objekte unterbringen:

%% INSERT: Skizze (med, med) done!
%\begin{figure}[htbp]
\includegraphics{pigeon.eps}
%\end{figure}

Identifiziere: Objekt = Gabel, Fach = Philosoph und beschr�nke
Verteilungsm�glichkeit auf die f�r unser Problem legalen F�lle (linke, rechte
Gabel pro Philosoph). \\

Das folgende Programm f�hrt zur Beschr�nkung der im Speisesaal anwesenden
Philosophen ein weiteres protected-object ein (task w�re auch m�glich); zur
Dokumentation wird bei jedem Ereignis (= Gabel ergreifen oder niederlegen) der
aktuelle Stand protokolliert und ausgegeben:

%Folie 173
\begin{code}
----------------------------------------------------------------------
-- Dining Philosophers 
--
-- synchronisation by protected objects room and fork (1..#phils):
--                room (always less than #phils inside) => deadlock prevention, 
--                                                 fork => mutual exclusion; 
-- for demo, phils call trace task whenever having seized/released a fork
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Philosophers is

   How_Many : constant Natural := 5; 
   subtype Phil_Range is Integer range 0..How_Many-1;
   How_Often : constant Natural := 5;          -- Zahl der Speisungen/Philosoph

   task Trace is --------------------------------------------------------
      entry Up(Where : Phil_Range);
      entry Down(Where : Phil_Range);
   end Trace;

   task body Trace is
      Busy : array(Phil_Range) of Boolean := (others => False);
   begin
      loop
         Outbuffer := Varnull;
         select
            accept Up(Where : Phil_Range)
            do Busy(Where) := True; end Up;
            for J in Phil_Range loop
               if Busy(J) then Outbuffer := Outbuffer & " X";
               else Outbuffer := Outbuffer & " +"; end if;
            end loop;
            Print;
         or
            accept Down(Where : Phil_Range)
         do Busy(Where) := False; end Down;
            for J in Phil_Range loop
               if Busy(J) then Outbuffer := Outbuffer & " X";
               else Outbuffer := Outbuffer & " -"; end if;
            end loop;
            Print;
         or
            terminate;
         end select;
      end loop;
   end Trace;  ----------------------------------------------------------

   


   protected Room is  ---------------------------------------------------
      entry Enter;
      procedure Leave;
   private
      Present : Natural := 0;
   end Room;

   protected body Room is
      entry Enter when Present < How_Many -1 is
      begin Present := Present +1; end Enter;
      procedure Leave is
      begin Present := Present -1; end Leave;
   end Room;  -----------------------------------------------------------

   protected type Forks is  ---------------------------------------------
      entry Pick_Up;
      procedure Put_Down;
   private
      Free : Boolean := True;
   end Forks;

   protected body Forks is
      entry Pick_Up when Free is
      begin Free := False; end Pick_Up;
      procedure Put_Down is
      begin Free := True; end Put_Down;
   end Forks;

   Fork : array(Phil_Range) of Forks; -----------------------------------
   
   task type Philosophers (Me : Phil_Range);   --------------------------

   task body Philosophers is
   begin
      for I in 1..How_Often loop
         delay 0.0001; -- think
         Room.Enter;
         Fork(Me).Pick_Up;  --left fork
         Trace.Up(Me);
         Fork((Me + 1) mod How_Many).Pick_Up; --right fork
         Trace.Up((Me + 1) mod How_Many);
         delay 0.0001; -- eat
         Fork(Me).Put_Down;  --left fork
         Trace.Down(Me);
         Fork((Me + 1) mod How_Many).Put_Down; --right fork
         Trace.Down((Me + 1) mod How_Many);
         Room.Leave;
      end loop;
   end Philosophers;

   type A_Philosophers is access Philosophers;
   Philosopher : array(Phil_Range) of A_Philosophers;  ------------------

begin  -----------------------------------------------------------main

   for I in Phil_Range loop Philosopher(I) := new Philosophers(I); end loop;

end Philosophers;  ---------------------------------------------------

----------------------------------------------------------------------
Legende: Spalte = fork-nr, 'X' = belegt, '+' und '-' = frei, 
                wobei ' -' =Freigabeereignis, '+' = Belegungsereignis.

33 pohlmann@pavian:philosophers
 Spalte 1       Spalte 2       Spalte 3       Spalte 4
 X + + + +      - - X X -      - X - - -      X - - X -
 X X + + +      + X X X +      - - - - -      - - - X -
 - X - - -      - X - X -      + X + + +      + + + X X
 - - - - -      - X - - -      + X X + +      - - - - X
 + X + + +      + X X + +      - - X - -      - - - - -
 + X X + +      X X X + +      - - - - -      + + + + X
 X X X + +      X - X - -      + + X + +      X + + + X
 X - X - -      X - - - -      + + X X +      X + + X X
 X - - - -      X + X + +      - - - X -      X - - X -
 X + X + +      X + X X +      - - - - -      - - - X -
 X + X X +      X X X X +      + + + X +      + + + X X
 X X X X +      X X - X -      + + + X X      - - - - X
 - X X X -      X X - - -      - - - - X      - - - - -
 - - X X -      - X - - -      - - - - -      + + + + X
 - - - X -      - - - - -      + + + + X      X + + + X
 - - - - -      + X + + +      X + + + X      X + + X X
 + X + + +      + X X + +      X + + X X      X - - X -
 + X X + +      X X X + +      X - - X -      - - - X -
 X X X + +      X - X - -      - - - X -      + + + X X
 X - X - -      X - - - -      + + + X X      - - - - X
 X - - - -      X + X + +      - - - - X      - - - - -
 X X + + +      X + X X +      - - - - -      + + + + X
 X X X + +      X X X X +      + + + + X      X + + + X
 X X X X +      X X - X -      X + + + X      X - - - -
 - X X X -      X X - - -      X + + X X      - - - - -
weiter in       weiter in      weiter in
Spalte 2        Spalte 3       Spalte 4
34 pohlmann@pavian:
\end{code}

%Folie 174
%Folie 175

%Folie 165
\section{Asynchrone Iteration}
Zur L�sung eines \emph{Fixpunktproblems} der Form \\
$ \begin{array}{rcl}
  x_1 & = & f_1(x_1, \dots, x_n) \\
      & \vdots &                 \\
  x_n & = & f_n(x_1, \dots, x_n) \\
\end{array} $ \\
kann man eine Iteration wie z.\,B. \\
$ \begin{array}{rclr}
  x_1^{s+1} &    =   & f_1(x_1^s, \dots, x_n^s) & (Jakobi) \\
            & \vdots &                          &          \\
  x_n^{s+1} &    =   & f_n(x_1^s, \dots, x_n^s) &          \\
\end{array} $ \\
oder auch \\
$ \begin{array}{rclr}
  x_1^{s+1} &    =   & f_1(x_1^s, \dots, x_n^s) & (Gauss-Seidl) \\
  x_2^{s+1} &    =   & f_2(x_1^{s+1}, x_2^s, \dots, x_n^s) &    \\
            & \vdots &                          &               \\
  x_n^{s+1} & =      & f_n(x_1^{s+1}, \dots, x_{n-1}^{s+1}, x_n^s) & \\
\end{array} $ \\
verwenden. \\

Solche Iterationen legen fest, welche \emph{Vor-Versionen} von Werten zur
Berechnung der \emph{n�chsten} Version $x_i^{s+1}$ zu benutzen sind und hei�en
deshalb \emph{synchron}. \\

%Folie 177
Zur \emph{Parallelisierung} -- z.\,B. f�r jede Komponente $x_i$ eigenen Proze�
-- kann man sich andere sinnvolle Reihenfolgen ausdenken, \emph{oder} die
Reihenfolge �berhaupt \emph{freigeben} = \emph{asynchrone} oder
\emph{chaotische Iteration}.

\subsection{Standard Iteration}

%% INSERT: Skizze (high, med) done!
%\begin{figure}[htbp]
\includegraphics{stdIteration.eps}
%\end{figure}

\subsection{Chaotische Iteration}

%% INSERT: Skizze (high, med) done!
%\begin{figure}[htbp]
\includegraphics{chaosIteration.eps}
%\end{figure}

Bez�ge so, wie sie sich \emph{faktisch} ergeben, also durch relative
Geschwindigkeit der beteiligten Prozesse bzw. Verf�gbarkeit von Werten!!
("`asynchron"' = ohne festen zeitlichen Bezug, insbesondere Reihenfolge). \\

%Folie 178
Wir betrachten ein

\subsection{Beispiel}
vgl. Barnes 95, p. 443 ff.

\paragraph{Gegeben} \ \\
\emph{Partielle Differentialgleichung} wie \\
$ \frac{\partial^2 P(x,y)}{\partial x^2} + \frac{\partial^2 P(x,y)}{\partial
  y^2} = F(x,y) $ \\
auf Gebiet mit gegebenen Randwerten.

\paragraph{Methode} zu numerischen L�sung.

Diskretisierung durch Erf�llung von \emph{Gitterpunkten} und �bergang zu
\emph{Differenzengleichung}: \\
  P(i-1, j) - P(i, j) + P(i+1, j) - P(i, j)
+ P(i, j-1) - P(i, j) + P(i, j+1) - P(i, j) = F(i, j) \\
$\iff$ \\
P(i, j) = $\frac{1}{4}$[P(i-1, j) + P(i+1, j) + P(i, j-1) + P(i, j+1) - 
F(i, j)] \\
also spezielles lineares Gleichungssystem. \\

L�sung durch Iteration, hier: Ordne jedem Punkt (i, j) eine \emph{task} zu und
rechne \emph{asynchron} unter Verwendung von \emph{globalen}
(\emph{gemeinsamen}) Variablen.

%Folie 179
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: partielle Differentialgleichung wie zB Laplace,
--                 diskretisiert ueber Gitter: 4*P(i,j) =   P(i-1,j) + P(i+1,j)
--                                                        + P(i,j-1) + P(i,j+1)
--                                                        - F(i,j)
-- Methode: tasks fuer Gitterpunkte, asynchrone Iteration, shared variables
--                 Hauptprogramm ueberwacht Konvergenz
-- Quelle:    Barnes95,p.443...
--                                   !!! problematic termination method !!!!
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Grid is
   N: constant := 5;
   subtype Full_Grid is Integer range 0 .. N;  -- grid with border
   subtype Grid is Full_Grid range 1 .. N-1;   -- grid without border
   type Real is digits 7;  -- declare our own type
   type Matrix is array(Integer range <>, Integer range <>) of Real;
   pragma Atomic_Components(Matrix);  -- shared!
   P: Matrix(Full_Grid, Full_Grid)  := (others=>(others=>0.0));
   Delta_P: Matrix(Grid, Grid) := (others=>(others=>1.0));
   Tolerance: constant Real := 0.0001;
   Error_Limit: constant Real := Tolerance * Real(N-1)**2;
   Converged: Boolean := False;
   pragma Atomic(Converged);  -- shared!
   Error_Sum: Real;


   function F(I, J: Grid) return Real is   -- keep it simple
   begin return 0.0; end F;

   task type Iterator is
      entry Start(I, J: in Grid);
   end;

   Process: array (Grid, Grid) of Iterator;

   task body Iterator is
      I, J: Grid;
      New_P: Real;
   begin

      accept Start(I, J: in Grid) do
         Iterator.I := Start.I;
         Iterator.J := Start.J;
      end Start;

      loop
         New_P := 0.25 * (P(I-1, J) + P(I+1, J) + P(I, J-1)
                          + P(I, J+1) -  F(I, J));
         Delta_P(I, J) := New_P - P(I, J);
         P(I, J) := New_P;
         exit when Converged;
      end loop;

   end Iterator;

begin            -- main subprogram, Iterator tasks now active
   
   for I in Full_Grid loop  --init P;
      P(I,0) := 1.0; 
   end loop;

   for I in Grid loop
      for J in Grid loop
         Process(I, J).Start(I, J);  -- tell them who they are
      end loop;
   end loop;

   loop  -- Konvergenzpr�fung
      Error_Sum := 0.0;
      for I in Grid loop
         for J in Grid loop
            Error_Sum := Error_Sum + Delta_P(I, J)**2;
         end loop;
      end loop;

      Converged := Error_Sum < Error_Limit;  -- problematic method !!!!!!!!!!!!
      exit when Converged;
   end loop;

   for I in Full_Grid loop        -- output results
      Outbuffer := Varnull;
      for J in Full_Grid loop
         Outbuffer := Outbuffer & Cvfs(Float(P(I,J)),1,3) & " ";
      end loop;
      Print;
   end loop;


end Grid;

----------------------------------------------------------------------
20 pohlmann@pavian:grid
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.250 0.063 0.016 0.004 0.000 
1.000 0.313 0.094 0.027 0.008 0.000 
1.000 0.328 0.105 0.033 0.010 0.000 
1.000 0.332 0.109 0.036 0.011 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
21 pohlmann@pavian:grid
\end{code}

%Folie 180

%Folie 181
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: partielle Differentialgleichung wie zB Laplace,
--                 diskretisiert ueber Gitter: 4*P(i,j) =   P(i-1,j) + P(i+1,j)
--                                                        + P(i,j-1) + P(i,j+1)
--                                                        - F(i,j)
-- Methode nur zum Vergleich: Standard Iteration(Gauss Seidel Typ)
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Gridsynchro is
   N: constant := 5;
   subtype Full_Grid is Integer range 0 .. N;
   subtype Grid is Full_Grid range 1 .. N-1;   -- without border
   type Real is digits 7;  -- declare our own type
   type Matrix is array(Integer range <>, Integer range <>) of Real;
   P: Matrix(Full_Grid, Full_Grid)  := (others=>(others=>0.0));
   Delta_P: Matrix(Grid, Grid) := (others=>(others=>1.0));
   Tolerance: constant Real := 0.0001;
   Error_Limit: constant Real := Tolerance * Real(N-1)**2;
   Converged: Boolean := False;
   Error_Sum: Real;
   New_P: Real;


   function F(I, J: Grid) return Real is   -- keep it simple
   begin return 0.0; end F;


begin            -- main subprogram
   
   for I in Full_Grid loop  --init P;
      P(I,0) := 1.0; 
   end loop;

   loop  -- siehe folgender Text
      Error_Sum := 0.0;
      for I in Grid loop
         for J in Grid loop
            New_P := 0.25 * (P(I-1, J) + P(I+1, J) + P(I, J-1)
                             + P(I, J+1) -  F(I, J));
            Delta_P(I, J) := New_P - P(I, J);
            P(I, J) := New_P;
            Error_Sum := Error_Sum + Delta_P(I, J)**2;
         end loop;
      end loop;
      Converged := Error_Sum < Error_Limit;  
      exit when Converged;
   end loop;

   for I in Full_Grid loop        -- output results
      Outbuffer := Varnull;
      for J in Full_Grid loop
         Outbuffer := Outbuffer & Cvfs(Float(P(I,J)),1,3) & " ";
      end loop;
      Print;
   end loop;


end Gridsynchro;

----------------------------------------------------------------------
45 pohlmann@pavian:gridsynchro
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.438 0.203 0.093 0.037 0.000 
1.000 0.573 0.302 0.148 0.061 0.000 
1.000 0.577 0.307 0.153 0.063 0.000 
1.000 0.446 0.212 0.101 0.041 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
\end{code}
F�r alle Gitterpunkte gilt: \\
$ P^{t+1}(i,j) = \frac{1}{4}[P^{t+1}(i-1,j) + P^t(i+1,j) + P^{t+1}(i,j-1) +
P^t(i,j+1) - F(i,j)] $ \\

%Folie 182
Ergebnisse sehen anders aus als bei asynchronem Programm! \\
M�glich:
\begin{itemize}
\item Konvergenzkriterium zu lax, na ja.
\item \emph{Terminierungsprotokoll} in asynchronem Fall \emph{ungeeignet}!
  Klar: Wenn process(i, j) \emph{zweimal} mit \emph{demselben} Argumenten
  rechnet, dann ist Delta\_P(i, j) = 0 ! \\

  Aber:
  \begin{itemize}
  \item Generell m�glich, da� dies eintritt.
  \item Bei 1-Prozessor Implementierung (interleaving) sogar wahrscheinlich.
  \end{itemize}

%Folie 183
  Also z.\,B. Reihenfolge der Ausf�hrung:
  \begin{code}
process(1,1);
process(1,1);
process(1,2);
process(1,2);
...
process(n-1,n-1);
process(n-1,n-1);
main;  -- findet System konvergiert obwohl process(1,1) nie von
          process(1,2)... process(n-1,n-1) beeinflu�t wurde.
  \end{code}
\end{itemize}

\paragraph{Offenbare Abhilfe} \ \\
�berpr�fe im Falle von Konvergenz (im obigen Sinne), ob Ergebnis (innerhalb der 
gew�nschten Genauigkeit) Gleichung l�st, d.\,h. wende jeden Iterator noch
einmal an!

%Folie 184
\begin{code}
----------------------------------------------------------------------
-- Aufgabe: partielle Differentialgleichung wie zB Laplace,
--                 diskretisiert ueber Gitter: 4*P(i,j) =   P(i-1,j) + P(i+1,j)
--                                                        + P(i,j-1) + P(i,j+1)
--                                                        - F(i,j)
-- Methode: tasks fuer Gitterpunkte, asynchrone Iteration, shared variables
--                 Hauptprogramm ueberwacht Konvergenz
-- Modifikation von Barnes95,p.443...:
--    Terminierung erst wenn Fehlerschranke simultan unterschritten
--
----------------------------------------------------------------------

with Stringpack; use Stringpack;
procedure Grid2 is
   N: constant := 5;
   subtype Full_Grid is Integer range 0 .. N;
   subtype Grid is Full_Grid range 1 .. N-1;   -- without border
   type Real is digits 7;  -- declare our own type
   type Matrix is array(Integer range <>, Integer range <>) of Real;
   pragma Atomic_Components(Matrix);
   P: Matrix(Full_Grid, Full_Grid)  := (others=>(others=>0.0));
   Delta_P: Matrix(Grid, Grid) := (others=>(others=>1.0));
   Tolerance: constant Real := 0.0001;
   Error_Limit: constant Real := Tolerance * Real(N-1)**2;
   Converged, NoChange: Boolean := False;
   pragma Atomic(Converged); pragma Atomic(NoChange);
   Error_Sum: Real;

   I : Positive := 1;  -- for counting interim output


   function F(I, J: Grid) return Real is   -- keep it simple
   begin return 0.0; end F;

   task type Iterator is
      entry Start(I, J: in Grid);
      entry Begin_Verify_Result;
      entry End_Verify_Result;
   end;

      Process: array (Grid, Grid) of Iterator;

      task body Iterator is
         I, J: Grid;
         New_P: Real;
      begin

         accept Start(I, J: in Grid) do
            Iterator.I := Start.I;
            Iterator.J := Start.J;
         end Start;

         loop
            New_P := 0.25 * (P(I-1, J) + P(I+1, J) + P(I, J-1)
                             + P(I, J+1) -  F(I, J));
            Delta_P(I, J) := New_P - P(I, J);
            P(I, J) := New_P;
            if Converged
            then accept Begin_Verify_Result  do  -- do it again!
               New_P := 0.25 * (P(I-1, J) + P(I+1, J) + P(I, J-1)
                                + P(I, J+1) -  F(I, J));
               Delta_P(I, J) := New_P - P(I, J);
               P(I, J) := New_P;
            end Begin_Verify_Result;
            accept End_Verify_Result;  -- synchro
            exit when NoChange;
            end if;
         end loop;

      end Iterator;

begin            -- main subprogram, Iterator tasks now active

   for I in Full_Grid loop  --init P;
      P(I,0) := 1.0;
   end loop;

   for I in Grid loop
      for J in Grid loop
         Process(I, J).Start(I, J);  -- tell them who they are
      end loop;
   end loop;

   loop
      Error_Sum := 0.0;
      for I in Grid loop
         for J in Grid loop
            Error_Sum := Error_Sum + Delta_P(I, J)**2;
         end loop;
      end loop;
      Converged := Error_Sum < Error_Limit;
      if Converged
      then                   -- make sure that error bounds hold simultaneously
         Error_Sum := 0.0;
         for I in Grid loop
            for J in Grid loop
               Process(I,J).Begin_Verify_Result;
               Error_Sum := Error_Sum + Delta_P(I, J)**2;
            end loop;
         end loop;
         Converged := False;
         NoChange := Error_Sum < Error_Limit;
         for I in Grid loop
            for J in Grid loop
               Process(I,J).End_Verify_Result;  -- synchro
            end loop;
         end loop;
      end if;
      if NoChange
      then exit;
      else
         if I < 5 then
            I := I + 1;
            Print("--------------------------------------------------");
            for I in Full_Grid loop        -- output state
               Outbuffer := Varnull;
               for J in Full_Grid loop
                  Outbuffer := Outbuffer & Cvfs(Float(P(I,J)),1,3) & " ";
               end loop;
               Print;
            end loop;
         end if;
      end if;
   end loop;

   Print("results: ----------------------------------------------");
   for I in Full_Grid loop        -- output results
      Outbuffer := Varnull;
      for J in Full_Grid loop
         Outbuffer := Outbuffer & Cvfs(Float(P(I,J)),1,3) & " ";
      end loop;
      Print;
   end loop;


end Grid2;

----------------------------------------------------------------------
rbla@bravo:grid2
--------------------------------------------------
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.429 0.190 0.083 0.032 0.000 
1.000 0.527 0.255 0.114 0.043 0.000 
1.000 0.518 0.248 0.083 0.032 0.000 
1.000 0.414 0.166 0.062 0.000 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
--------------------------------------------------
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.429 0.190 0.083 0.032 0.000 
1.000 0.527 0.255 0.114 0.043 0.000 
1.000 0.518 0.248 0.083 0.032 0.000 
1.000 0.414 0.166 0.062 0.000 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
--------------------------------------------------
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.429 0.190 0.083 0.032 0.000 
1.000 0.527 0.255 0.114 0.043 0.000 
1.000 0.518 0.248 0.083 0.032 0.000 
1.000 0.414 0.166 0.062 0.000 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
--------------------------------------------------
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.429 0.190 0.083 0.032 0.000 
1.000 0.527 0.255 0.114 0.043 0.000 
1.000 0.518 0.248 0.083 0.032 0.000 
1.000 0.414 0.166 0.062 0.000 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
results: ----------------------------------------------
1.000 0.000 0.000 0.000 0.000 0.000 
1.000 0.446 0.212 0.099 0.040 0.000 
1.000 0.582 0.311 0.154 0.064 0.000 
1.000 0.583 0.313 0.157 0.065 0.000 
1.000 0.448 0.215 0.103 0.042 0.000 
1.000 0.000 0.000 0.000 0.000 0.000 
\end{code}

%Folie 185
%Folie 186

%Folie 187
Ergebnis entspricht dem der synchronen Iteration, aber ziemlich viel
�berfl�ssige Arbeit! \\

\emph{Grunds�tzlich} gilt f�r asynchrone Itertation:
\begin{itemize}
\item Kann
  \begin{itemize}
  \item Arbeit/Zeit sparen:
    \begin{itemize}
    \item Kein Warten darauf, da� anderer Proze� fertig mit Schritt.
    \item Kein Synchronisationsaufwand.
    \end{itemize}

  \item Arbeit/Zeit vermehren:
    \begin{itemize}
    \item Benutzung evtl. veralteter Werte $\Rightarrow$ unproduktive,
      evtl. sch�dliche Berechnungsschritte.
    \end{itemize}
  \end{itemize}

  \begin{important}
    Also asynchrone Iteration \emph{nicht} sinnvoll f�r
    1-Prozessor-Implementierung, da Spekulation auf Zeitersparnis entf�llt.
  \end{important}
  
\item \emph{Konvergenz} ist i.\,A. schwieriger zu beweisen, insbesondere
  beachte man: Standard-Iteration konvergiert $\not\Rightarrow$
  Asynchrone-Iteration konvergiert.

%Folie 188
  \paragraph{Hausaufgabe} \ \\
  �berlegen Sie sich, warum unser Beispiel konvergiert! \\
  Hinweis:
  \begin{enumerate}
  \item Klar, da� Werte f�r P bzw. Delta\_P beschr�nkt.
  \item Nimm an, da� Nicht-Konvergenz in einem Punkt, d.\,h. Differenz von
    P-Werten nicht unter eine gewisse \emph{Schwelle} zu dr�cken; betrachte Punkt 
    mit \emph{maximalem} Schwellwert und erschlie�e Widerspruch.
  \end{enumerate}

\item \emph{Terminierung} (d.\,h. praktische Anwendung eines
  Konvergenzkriteriums) ist schwieriges Problem, zu dem allerdings L�sungen in
  der Literatur existieren. Unsere L�sung ist sehr grob und l�uft auf
  wiederholte asynchrone Phasen mit Synchro-Punkten dazwischen hinaus.

%Folie 189
\item \emph{Brauchbarkeit}
  \begin{itemize}
  \item Als Ausf�hrungsmodus am ehesten brauchbar f�r \emph{verteilte} Systeme
    mit sehr hohen Synchronisationskosten. Beispiel: Verteilte Berechnung von
    routing-Tafeln (= shortest-path Problem) u.\,�. in Netzen.

  \item Als algorithmische Vorstufe im Programmentwurf: Erfinde \emph{erst}
    asynchrones Verfahren f�r gegebenes Problem \emph{und} f�ge \emph{dann}
    Synchronisation entsprechend technischen Gegebenheiten,
    Effizienzbed�rfnissen u.\,�., hinzu.
  \end{itemize}
\end{itemize}

\subsection{Literatur}
Asynchrone Iteration als
\begin{description}
\item [Programmentwicklungs-Philosophie]
  Clandy/Misra: "`Parallel Program Design"', 19..
\item[Technik f�r numerische Probleme] 
  Bertsekas/Tsitsiktis: "`Parallel \& Distributed Computations: Numerical Methods"', 1984
\end{description}

%Folie 190
\subsection{Hausaufgabe}
n Professoren m�ssen f�r das Semester (Tag 1 \dots k) einen Termin f�r die
Fakult�tssitzung festlegen. Da sie alle einen Terminkalender mit vielen
Eintr�gen haben, selten da sind und auch nicht gern miteinander reden, wird
folgendes Verfahren gew�hlt:
\begin{itemize}
\item Im Sekretariat wir ein \emph{Terminvorschlag} ausgeh�ngt.
\item Jeder Professor kommt sooft wie m�glich im Sekretariat vorbei, vergleicht 
  seinen Terminkalender mit dem aktuellen Vorschlag und verschiebt, \emph{wenn
    n�tig}, letzteren auf den \emph{fr�hesten individuell m�glichen sp�teren
    Termin}.
\item Alle sind bereit, die Sitzung am \emph{letzten} Tag des Semesters
  abzuhalten (weil sonst die Fakult�t geschlossen wird), so da� das Problem
  eine L�sung hat.
\end{itemize}

\begin{enumerate}
\item �berlegen Sie sich, da� das beschriebene Verfahren die fr�heste f�r alle
  Profs m�gliche L�sung findet.
\item Realisieren Sie das Verfahren mit Ada-tasks und statten Sie das Programm
  mit einem geeignetem Terminierungsprotokoll aus. (z.\,B. Terminvorschlag
  gilt, wenn von allen n Profs \emph{gesehen und nicht ge�ndert}).
\end{enumerate}

%Folie 191
\chapter{Ada "`requeue"' Konstrukt}
Bedingungs-Synchronisation mit Hilfe von W�chtern (guards, barriers) vor
entries -- {\ttfamily when <condition>} -- erlaubt, die Erf�llung eines
Bedienwunsches vom \emph{Zustand des Bedieners} abh�ngig zu machen; aber
W�chter darf \emph{nicht} Parameter des entry-call benutzen \\

$\Rightarrow$ Erf�llung des Bedienwunsches kann \emph{nicht} durch Barriere an
\emph{Art des Wunsches} (z.\,B. \emph{Umfang}, \emph{Dringlichkeit}) gekn�pft
werden. \\

Klar: Wenige(!) diskrete F�lle k�nnen durch Vermehrung der entries gehandhabt
werden. \\


%Folie 192
Allgemein:
\section{Abhilfe}
= \emph{doppelte} Interaktion:
\begin{enumerate}
\item Sagen, was man will.
\item Daf�r anstehen, da� man das kriegt.
\end{enumerate}

Mit unseren bisherigen Mitteln bedeutet das, da� der Klient auch \emph{zwei
  entry-calls} ben�tigt; das folgende Programm illustriert die Technik, wobei
der Server/Ressourcenverwalter durch ein protected-object repr�sentiert wird
(�hnlich: task);

\section{Prinzip der L�sung}
Klient, der nicht sofort bedient werden kann (= Entscheidung bei Aufruf der
Prozedur "`{\ttfamily request(\dots)}"') reiht sich durch Aufruf von entry
"`{\ttfamily wait}"' in eine Warteschlange ein; alle unter "`{\ttfamily wait}"' 
aufgef�hrten Bedienw�nsche werden auf Erf�llbarkeit �berpr�ft, sobald eine
R�ckgabe von Betriebsmitteln erfolgt; nicht befriedigte Klienten m�ssen sich
immer \emph{neu} anstellen!

%Folie 193
\begin{code}
----------------------------------------------------------------------
-- resource management for varying requests
--
-- structure:  requesters = task, resourcepool(+mangement) = protected object
-- version1: double interaction
----------------------------------------------------------------------

with Stringpack, Ada.Numerics.Float_Random; use Stringpack, Ada.Numerics.Float_Random;
procedure Resources1 is

   G : Generator;
   Number_Of_Clients : constant Natural := 3;
   Number_Of_Resources : constant Natural := 5;
   How_Often : constant Natural := 5;


   protected Resource_Manager  is ---------------------------------------
      procedure Request(How_Many : Positive; Ok : out Boolean); --+ double interaction
      entry Wait (How_Many : Positive; Ok : out Boolean);       --+
      procedure Release(How_Many : Positive);
   private
      Free : Natural := Number_Of_Resources;
      Release_Event : Boolean := False;
      Wanted : Natural := 0;     -- for trace only, offene W�nsche
   end Resource_Manager;

   protected body Resource_Manager is

      procedure Trace is
         Not_Free : Natural := Number_Of_Resources - Free;
      begin
         Outbuffer := Varnull;
         for I in 1..Number_Of_Resources loop
            if I <= Not_Free then Outbuffer := Outbuffer & " X";
            else Outbuffer := Outbuffer & " -";
            end if;
         end loop;
         Outbuffer := (Outbuffer & "  wanted = ") & Wanted;
         Print;
      end Trace;

      procedure Request(How_Many : Positive; Ok : out Boolean) is
         -- this could be an entry with "when free > 0"
      begin
         if How_Many <= Free
         then Free := Free - How_Many; Ok := True;  --allocate
         else Ok := False;
         Wanted := Wanted + How_Many;   -- for trace
         end if;
         Trace;
      end Request;

      entry Wait (How_Many : Positive; Ok : out Boolean) when Release_Event  is
      begin
         if Wait'Count = 0 then Release_Event := False; end if;
         -- => loop over all waiting requesters !!!
         if How_Many <=  Free
         then Free := Free - How_Many; Ok := True;  --allocate
         Wanted := Wanted - How_Many;   -- for trace
         Trace;
         else Ok := False;
         end if;
      end Wait;

      procedure Release(How_Many : Positive) is
      begin
         Free := How_Many + Free;  -- release
         if Wait'Count > 0 then Release_Event := True; end if;
         Trace;
      end Release;


   end Resource_Manager;  -----------------------------------------------


   task type Clients is   -----------------------------------------------
      entry Start(How_Many : Natural);
   end Clients;

   task body Clients is
      My_Need : Natural;
      Done : Boolean;
   begin
      accept Start(How_Many : Natural)
      do My_Need := How_Many; end Start;
      for I in 1..How_Often loop
         delay Duration(0.001* Random(G));
         Resource_Manager.Request(My_Need, Done);
         while not Done loop                                 --+ immer neu "wait"
            Resource_Manager.Wait(My_Need, Done); end loop;  --+ aufrufen!
         delay Duration(0.001 * Random(G));
         Resource_Manager.Release(My_Need);
      end loop;
   end Clients;

   Client : array(1..Number_Of_Clients ) of Clients;  ----------------

begin  -----------------------------------------------------------main

   Client(1).Start(1); Client(2).Start(2); Client(3).Start(5);

end Resources1;  -----------------------------------------------------

----------------------------------------------------------------------
32 pohlmann@pavian:resources1
X - - - -  wanted = 0
X - - - -  wanted = 5  ! Client 3 fordert 5 Einheiten !
X X X - -  wanted = 5
X X - - -  wanted = 5
- - - - -  wanted = 5
X - - - -  wanted = 5  ! Client 3 wird von Client 1 �berholt !
X X X - -  wanted = 5
X X - - -  wanted = 5
- - - - -  wanted = 5
X X X X X  wanted = 0
X X X X X  wanted = 1
X X X X X  wanted = 3
- - - - -  wanted = 3
X - - - -  wanted = 2
X X X - -  wanted = 0
X X X - -  wanted = 5
X - - - -  wanted = 5
- - - - -  wanted = 5
X X X X X  wanted = 0
X X X X X  wanted = 2
X X X X X  wanted = 3
- - - - -  wanted = 3
X X - - -  wanted = 1
X X X - -  wanted = 0
X X X - -  wanted = 5
X X - - -  wanted = 5
- - - - -  wanted = 5
X X X X X  wanted = 0
X X X X X  wanted = 1
X X X X X  wanted = 3
- - - - -  wanted = 3
X - - - -  wanted = 2
X X X - -  wanted = 0
X X - - -  wanted = 0
X X - - -  wanted = 5
- - - - -  wanted = 5
X X X X X  wanted = 0
- - - - -  wanted = 0
X X X X X  wanted = 0
- - - - -  wanted = 0
33 pohlmann@pavian:
\end{code}

\paragraph{Anmerkung des Tippers}
Auf meinem Rechner (Linux Kernel 2.0.33, gcc version egcs-2.90.23 980102
(egcs-1.0.1 release), GNAT 3.10p) konnte ich diesen �berholvorgang nicht
nachvollziehen, was aber nicht weiter ungew�hnlich ist. Schlie�lich �ndert
allein die Art der Ausgabe (Bildschirm/Datei) die Reihenfolge komplett:

\begin{code}
rbla@bravo:resources1                rbla@bravo:resources1 >output
 X - - - -  wanted = 0                X - - - -  wanted = 0
 X X X - -  wanted = 0                X X X - -  wanted = 0
 X X X - -  wanted = 5                X X X - -  wanted = 5
 X X - - -  wanted = 5                X - - - -  wanted = 5
 - - - - -  wanted = 5                - - - - -  wanted = 5
 X X X X X  wanted = 0                X X X X X  wanted = 0
 X X X X X  wanted = 1                - - - - -  wanted = 0
 - - - - -  wanted = 1                X - - - -  wanted = 0
 X - - - -  wanted = 0                X X X - -  wanted = 0
 X X X - -  wanted = 0                X - - - -  wanted = 0
 X X - - -  wanted = 0                - - - - -  wanted = 0
 - - - - -  wanted = 0                X X X X X  wanted = 0
 X X X X X  wanted = 0                - - - - -  wanted = 0
 X X X X X  wanted = 1                X - - - -  wanted = 0
 - - - - -  wanted = 1                X X X - -  wanted = 0
 X - - - -  wanted = 0                X - - - -  wanted = 0
 X X X - -  wanted = 0                - - - - -  wanted = 0
 X X - - -  wanted = 0                X X X X X  wanted = 0
 - - - - -  wanted = 0                - - - - -  wanted = 0
 X X X X X  wanted = 0                X - - - -  wanted = 0
 X X X X X  wanted = 1                X X X - -  wanted = 0
 - - - - -  wanted = 1                X - - - -  wanted = 0
 X - - - -  wanted = 0                - - - - -  wanted = 0
 X X X - -  wanted = 0                X X X X X  wanted = 0
 X X - - -  wanted = 0                - - - - -  wanted = 0
 - - - - -  wanted = 0                X - - - -  wanted = 0
 X X X X X  wanted = 0                X X X - -  wanted = 0
 X X X X X  wanted = 2                X - - - -  wanted = 0
 X X X X X  wanted = 3                - - - - -  wanted = 0
 - - - - -  wanted = 3                X X X X X  wanted = 0
 X X - - -  wanted = 1                - - - - -  wanted = 0
 X X X - -  wanted = 0
 X - - - -  wanted = 0
 - - - - -  wanted = 0
 X X X X X  wanted = 0
 - - - - -  wanted = 0
\end{code}

%Folie 194
%Folie 195

%Folie 196
\subsection{Kritik}
Verfahren mit doppelter Interaktion ist
\begin{itemize}
\item Umst�ndlich + fehleranf�llig \\
$\Rightarrow$ Operation f�r Betriebsmittel anfordern in Paket verkapseln, soda� 
Klient-Programm nur 1 Aufruf.

\item Ineffizient (wiederholter Aufruf von "`{\ttfamily wait}"', aber
  aufrufende task jedesmal sinnlos aktivieren).

\item Unsicher im Hinblick auf \emph{Reihenfolge} der Betriebsmittelzuteilung
  (d.\,h. $\neq$ FIFO), siehe Beispiel-Protokoll: \\
  \begin{tabular}{rcl}
    client 3 & $\stackrel{5}{\longrightarrow}$     & request \\
             & $\stackrel{not ok}{\longleftarrow}$ &         \\
    client 1 & $\longrightarrow$                   & release \\
    client 2 & $\longrightarrow$                   & release \\
    client 1 & $\stackrel{1}{\longrightarrow}$     & request \\
             & $\stackrel{ok}{\longleftarrow}$     &         \\
    client 2 & $\stackrel{2}{\longrightarrow}$     & request \\
             & $\stackrel{ok}{\longleftarrow}$     &         \\
    client 3 & $\longrightarrow$                   & wait    \\
  \end{tabular} \\
d.\,h. Problem, da� Klient \emph{zwischen} request und wait \emph{unterbrochen} 
wird.
\end{itemize}

%Folie 197
Abhilfe durch neues \emph{Sprachmittel}: \\
"`\emph{private entry}"' und "`\emph{requeue}"' erlauben, die Doppel-Aktion
allein durch den entry-Akzeptor ausf�hren zu lassen, d.\,h. Klient wird nicht
t�tig, Server kann Klienten \emph{ohne} Gefahr des �berholens in Warteschlange
einf�gen, d.\,h. als atomare Aktion. \\

\begin{tabular}{rcl}
  client & $\longrightarrow$ & request              \\
         &                   & $\downarrow$ requeue \\
         &                   & wait                 \\
\end{tabular} \\

Anstatt: \\
\begin{tabular}{rcl}
  client & $\longrightarrow$ & request           \\
         & $\stackrel{not ok}{\longleftarrow}$ & \\
  client & $\longrightarrow$ & wait              \\
\end{tabular}

%Folie 198
\begin{code}
----------------------------------------------------------------------
-- resource management for varying requests
--
-- structure:  requesters = task, resourcepool(+mangement) = protected object
-- version2:   requeue unserviced requests
----------------------------------------------------------------------

with Stringpack, Ada.Numerics.Float_Random; use Stringpack, Ada.Numerics.Float_Random;
procedure Resources2 is

   G : Generator;
   Number_Of_Clients : constant Natural := 3;
   Number_Of_Resources : constant Natural := 5;
   How_Often : constant Natural := 5;


   protected Resource_Manager  is ------------------------------------
      entry Request(How_Many : Positive);
      procedure Release(How_Many : Positive);
   private
      entry Wait (How_Many : Positive);            -- private entry for requeue
      Free : Natural := Number_Of_Resources;
      Release_Event : Boolean := False;
      To_Try : Natural := 0;  -- # requests to be tried on release; <= wait'count
      Wanted : Natural := 0;  -- for trace only
   end Resource_Manager;

   protected body Resource_Manager is

      procedure Trace is
         Not_Free : Natural := Number_Of_Resources - Free;
      begin
         Outbuffer := Varnull;
         for I in 1..Number_Of_Resources loop
            if I <= Not_Free then Outbuffer := Outbuffer & " X";
            else Outbuffer := Outbuffer & " -";
            end if;
         end loop;
         Outbuffer := (Outbuffer & "  wanted = ") & Wanted;
         Print;
      end Trace;

      entry Request(How_Many : Positive) when True is  -- could be "when free > 0"
      begin
         if How_Many <= Free
         then Free := Free - How_Many;   --allocate
         Trace;
         else  Wanted := Wanted + How_Many;   -- for trace
         Trace;
         requeue Wait;
         end if;
      end Request;

      entry Wait (How_Many : Positive) when Release_Event  is
      begin
         To_Try := To_Try - 1; --  loop over all waiting requesters !!!
         if To_Try = 0 then Release_Event := False; end if;
         if How_Many <=  Free
         then Free := Free - How_Many;   --allocate
         Wanted := Wanted - How_Many;   -- for trace
         Trace;
         else requeue Wait;
         end if;
      end Wait;

      procedure Release(How_Many : Positive) is
      begin
         Free := How_Many + Free;  -- release
         if Wait'Count > 0 then To_Try := Wait'Count; Release_Event := True; end if;
         Trace;
      end Release;


   end Resource_Manager;  --------------------------------------------


   task type Clients is   --------------------------------------------
      entry Start(How_Many : Natural);
   end Clients;

   task body Clients is
      My_Need : Natural;
   begin
      accept Start(How_Many : Natural)
      do My_Need := How_Many; end Start;
      for I in 1..How_Often loop
         delay Duration(0.001* Random(G));
         Resource_Manager.Request(My_Need);
         delay Duration(0.001 * Random(G));
         Resource_Manager.Release(My_Need);
      end loop;
   end Clients;

   Client : array(1..Number_Of_Clients ) of Clients;  ----------------

begin  -----------------------------------------------------------main

   Client(1).Start(1); Client(2).Start(2); Client(3).Start(5);

end Resources2;  -----------------------------------------------------

----------------------------------------------------------------------
35 pohlmann@pavian:resources2
 X - - - -  wanted = 0
 X - - - -  wanted = 5
 X X X - -  wanted = 5
 X X - - -  wanted = 5
 - - - - -  wanted = 5
 X X X X X  wanted = 0  ! Client 3 (mit Bedienversuch 5) kommt durch, weil
 X X X X X  wanted = 1    sofort im Anschlu� "requeue" in Warteschlange von
 X X X X X  wanted = 3    "wait" eingef�gt !
 - - - - -  wanted = 3
 X - - - -  wanted = 2
 X X X - -  wanted = 0
 X - - - -  wanted = 0
 - - - - -  wanted = 0
 X X X X X  wanted = 0
 X X X X X  wanted = 2
 X X X X X  wanted = 3
 - - - - -  wanted = 3
 X X - - -  wanted = 1
 X X X - -  wanted = 0
 X X - - -  wanted = 0
 - - - - -  wanted = 0
 X X X X X  wanted = 0
 X X X X X  wanted = 1
 X X X X X  wanted = 3
 - - - - -  wanted = 3
 X - - - -  wanted = 2
 X X X - -  wanted = 0
 X - - - -  wanted = 0
 X - - - -  wanted = 5
 - - - - -  wanted = 5
 X X X X X  wanted = 0
 X X X X X  wanted = 2
 X X X X X  wanted = 3
 - - - - -  wanted = 3
 X X - - -  wanted = 1
 X X X - -  wanted = 0
 X X X - -  wanted = 5
 X X - - -  wanted = 5
 - - - - -  wanted = 5
 X X X X X  wanted = 0
 - - - - -  wanted = 0
36 pohlmann@pavian:
\end{code}

\paragraph{Anmerkung des Tippers}
Zum Vergleich hier wieder das Ergebnis auf meiner Maschine:
\begin{code}
rbla@bravo:resources2                rbla@bravo:resources2 
 X - - - -  wanted = 0                X - - - -  wanted = 0
 X X X - -  wanted = 0                X X X - -  wanted = 0
 X X X - -  wanted = 5                X X X - -  wanted = 5
 X X - - -  wanted = 5                X - - - -  wanted = 5
 - - - - -  wanted = 5                - - - - -  wanted = 5
 X X X X X  wanted = 0                X X X X X  wanted = 0
 X X X X X  wanted = 1                - - - - -  wanted = 0
 - - - - -  wanted = 1                X - - - -  wanted = 0
 X - - - -  wanted = 0                X X X - -  wanted = 0
 X X X - -  wanted = 0                X - - - -  wanted = 0
 X X - - -  wanted = 0                - - - - -  wanted = 0
 X X - - -  wanted = 5                X X X X X  wanted = 0
 - - - - -  wanted = 5                - - - - -  wanted = 0
 X X X X X  wanted = 0                X - - - -  wanted = 0
 X X X X X  wanted = 1                X X X - -  wanted = 0
 - - - - -  wanted = 1                X - - - -  wanted = 0
 X - - - -  wanted = 0                - - - - -  wanted = 0
 X X X - -  wanted = 0                X X X X X  wanted = 0
 X X - - -  wanted = 0                - - - - -  wanted = 0
 X X - - -  wanted = 5                X - - - -  wanted = 0
 - - - - -  wanted = 5                X X X - -  wanted = 0
 X X X X X  wanted = 0                X - - - -  wanted = 0
 X X X X X  wanted = 1                - - - - -  wanted = 0
 - - - - -  wanted = 1                X X X X X  wanted = 0
 X - - - -  wanted = 0                - - - - -  wanted = 0
 X X X - -  wanted = 0                X - - - -  wanted = 0
 X X - - -  wanted = 0                X X X - -  wanted = 0
 X X - - -  wanted = 5                X - - - -  wanted = 0
 - - - - -  wanted = 5                - - - - -  wanted = 0
 X X X X X  wanted = 0                X X X X X  wanted = 0
 X X X X X  wanted = 1                - - - - -  wanted = 0
 - - - - -  wanted = 1
 X - - - -  wanted = 0
 X X X - -  wanted = 0
 X X - - -  wanted = 0
 X X - - -  wanted = 5
 - - - - -  wanted = 5
 X X X X X  wanted = 0
 - - - - -  wanted = 0
\end{code}

%Folie 199
%Folie 200

%Folie 201
\section{Zur Syntax und Semantik von "`requeue"'}
\begin{itemize}
\item Gibt's f�r tasks und protected-objects, oft f�r "`\emph{private}"' entry.
\item Entry von requeue mu� \emph{dasselbe} Parameterprofil haben wie das
  �rspr�ngliche entry oder mu� \emph{parameterlos} sein. Parameter m�ssen bei
  requeue nicht extra genannt werden.
\item Requeue kann auch entries \emph{anderer} Objekte ansprechen.
\item Mit Ausf�hrung des "`requeue"' ist der Aufruf des urspr�nglichen entry
  erstmal zuende (d.\,h. insbesondere, da� jetzt andere Aufrufe des
  protected-objects durchkommen k�nnen).
\item Task, die auf ein entry (insbesondere infolge requeue wartet) hat die
  �bliche Pr�ferenz gegen Aufrufer von au�en: Nach jeder Zustands�nderung des
  Objekts werden die W�chter neu ausgewertet und die darauf wartenden tasks
  bedient: "`Internal-Progress-First Rule"'.
\end{itemize}

%Folie 202
Requeue ist bequemes Mittel zu L�sung kompilzierter
\emph{Synchronisationsprobleme}: \emph{Ein} Aufruf einer protected-operation
von au�en wird \emph{intern}, kann \emph{intern zerlegt} werden in eine Folge
\emph{gesch�tzter Teiloperationen}, die in genau festgelegter Weise mit anderen 
Operationen \emph{verzahnt} sind.

\section{Beispiel}
Zu modellieren ist ein \emph{Verkehrssystem} bestehend aus
\begin{itemize}
\item einer ringf�rmigen U-Bahn(o.\,�.)-Linie mit \emph{Bahnh�fen}.
\item einer dieser Linien (in fester Richtung) bedienender \emph{Zug}.
\item Kunden.
\end{itemize}

%% INSERT: Skizze (high, low)
%\begin{figure}[htbp]
%\includegraphics{.eps}
%\end{figure}

%Folie 203
Wir realisieren den \emph{Zug} und die \emph{Passagiere} durch \emph{tasks} und 
den \emph{Bahnhof} (naheliegend) als \emph{protected-object}; im Bahnhof werden 
Zug \emph{und} Passagiere \emph{gemeinsam} aktiv, Aufenthalt des Zugs im
Bahnhof ist charakterisiert durch \emph{2 Phasen}:

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{reqZug.eps}
%\end{figure}

Au�erdem modellieren wir die \emph{Fahrt} eines \emph{Passagiers} durch
\emph{requeue} bei der gew�nschten \emph{Ziel-Station}:

%% INSERT: Skizze (med, high) done!
%\begin{figure}[htbp]
\includegraphics{reqPassagier.eps}
%\end{figure}

%Folie 204
\begin{code}
----------------------------------------------------------------------
-- metro  - illustrates use of requeue
--
-- problem: model circular metro line with 1 train and stations where
--          passengers enter/leave
--
-- structure: passengers & train = task, stations = protected objects
-- requeue is used to 1. delay passengers for trip to their destination,
--                                2. guide train through phases
--                                   (passengers alight/board) at stations
-- cf: Burns/Wellings ch.8.6 (does not use 2.)
--
-- !!! start protocol ( cf.main ) necessary for initialisation !!!
-- !!! program does NOT terminate (just stops producing output) !!!
----------------------------------------------------------------------

with Stringpack, Ada.Numerics.Discrete_Random; use Stringpack;
procedure Metro is

   Number_Of_Stations : constant Natural := 5;
   subtype Station_Range is Integer range 1..Number_Of_Stations;

   package Random_Destination is new Ada.Numerics.Discrete_Random(Station_Range);
   use Random_Destination;
   G : Generator;

   Number_Of_Clients : constant Natural := 100; -- small town
   Capacity : Integer  := 50;  -- (relatively) big train

   How_Often : constant Natural := 4;  -- traced rounds in sample run

   --------------------------------------------------------------trace

   type Trace_Type is record
      Train_At_Station : Boolean := False;
      Clients_At_Station : Natural := 0; -- initially there or alighted
      Passenger_Count : Natural := 0;  -- in train on leaving station
   end record;
   Station_Trace : array(Station_Range) of Trace_Type;      --global!!

   procedure Trace is
   begin
      Outbuffer := Varnull;
      for I in Station_Range  loop
         Outbuffer := Outbuffer & Cvis(Station_Trace(I).Clients_At_Station,3);
         if Station_Trace(I).Train_At_Station
         then Outbuffer := Outbuffer &
           " |" & Cvis(Station_Trace(I).Passenger_Count,2) &"> ";
         else Outbuffer := Outbuffer & "      ";
         end if;
      end loop;
      Print;
   end Trace;

   -------------------------------------------------------------------

   protected type Stations  is ---------------------------------------
      procedure Start(Id : Station_Range);
      entry Train_Comes_In(On_Board : in out Natural);
      entry Board_The_Train(Where : Station_Range);
   private
      My_Id : Station_Range;                        -- must be set initially!!!
      entry Alight_At_Destination;           -- private entry to requeue client
                                              -- private entry to requeue train
      entry Passengers_Board(On_Board : in out Natural);
                                              -- private entry to requeue train
      entry Close_Doors(On_Board : in out Natural);
      Passenger_Count : Natural := 0;                    -- # Passagiere in Zug
      Boarding, Alighting : Boolean := False;            --  Phase
   end Stations;

   Station : array(Station_Range) of Stations;

   protected body Stations is

      procedure Start(Id : Station_Range) is
      begin My_Id := Id; end Start;

      entry Board_The_Train(Where : Station_Range)
      when Boarding and then Passenger_Count < Capacity is
      begin
         Passenger_Count := Passenger_Count + 1;                  -- fuelle Zug
         Station_Trace(My_Id).Clients_At_Station :=
           Station_Trace(My_Id).Clients_At_Station - 1;   -- trace
         requeue Station(Where).Alight_At_Destination;        -- Ziel der Reise
      end Board_The_Train;

      entry Train_Comes_In(On_Board : in out Natural)
      when True is                           -- requeue nur in entry erlaubt!!!
      begin
         Station_Trace(My_Id).Train_At_Station := True; -- trace
         Passenger_Count := On_Board;
         Alighting := True;
         requeue Passengers_Board;
      end Train_Comes_In;

      entry Alight_At_Destination when Alighting is
      begin
         Passenger_Count := Passenger_Count - 1;   -- leave train
         Station_Trace(My_Id).Clients_At_Station :=
           Station_Trace(My_Id).Clients_At_Station + 1;  -- trace
      end Alight_At_Destination;

      entry Passengers_Board(On_Board : in out Natural)
      when Alight_At_Destination'Count = 0 is
      begin
         Alighting := False;
         Boarding := True;
         requeue Close_Doors;
      end Passengers_Board;

      entry Close_Doors(On_Board : in out Natural)
      when  Boarding and (Board_The_Train'Count = 0 or Passenger_Count = Capacity) is
      begin
         Boarding := False;
         On_Board := Passenger_Count;  -- out Parameter von train_comes!!
         Station_Trace(My_Id).Passenger_Count := Passenger_Count;  --trace
         Trace;
         Station_Trace(My_Id).Train_At_Station := False; -- trace
      end Close_Doors;

   end Stations; -----------------------------------------------------

   task type Clients is   --------------------------------------------
      entry Start;
   end Clients;

   task body Clients is
      From, To : Station_Range;
   begin
      accept Start;
      From := Random(G);
      Station_Trace(From).Clients_At_Station :=
        Station_Trace(From).Clients_At_Station + 1;  -- trace
      loop  -- infinite loop !!!!
         To := Random(G);
         Station(From).Board_The_Train(To);
         From := To;
      end loop;
   end Clients;

   Client : array(1..Number_Of_Clients ) of Clients;  ----------------

   task Train is   ---------------------------------------------------
      entry Start;
   end Train;

   task body Train is
      Nr_Passengers : Natural := 0;
   begin
      accept Start;
      for I in 1..How_Often loop  --sample run
         for J in Station_Range loop
            Station(J).Train_Comes_In(Nr_Passengers);
         end loop;
      end loop;
   end Train;


begin  -----------------------------------------------------------main

   for I in Station_Range loop Station(I).Start(I); end loop;
   for I in 1..Number_Of_Clients loop Client(I).Start; end loop;
   Train.Start;

end Metro;  ----------------------------------------------------------

----------------------------------------------------------------------
24 pohlmann@pavian:metro
  0 |32>  20       20       18       10
  0        7 |45>  20       18       10
  0        7       15 |50>  18       10
  0        7       15       18 |50>  10
  0        7       15       18       12 |48>
 27 |21>   7       15       18       12
 27       11 |17>  15       18       12
 27       11       12 |20>  18       12
 27       11       12        7 |31>  12
 27       11       12        7        9 |34>
 20 |41>  11       12        7        9
 20        9 |43>  12        7        9
 20        9       14 |41>   7        9
 20        9       14       14 |34>   9
 20        9       14       14        8 |35>
 16 |39>   9       14       14        8
 16        8 |40>  14       14        8
 16        8       15 |39>  14        8
 16        8       15       14 |39>   8
 16        8       15       14        6 |41>
^C
25 pohlmann@pavian
\end{code}

%Folie 205
%Folie 206

%Folie 207
= Situation bei \emph{Abfahrt} des Zugs: \\
\#(Passagiere) in Stationen (nicht notwendig in queue!), \#(Passagiere) im Zug
{\ttfamily |>}, $\sum = 100$.

%Folie 208
\section{Hausaufgabe}
Das vorstehende Programm ist verbesserungsf�hig:

\begin{enumerate}
\item Der Gebrauch der Zustandsvariablen/private entries ist etwas �bertrieben
  f�r den Anla�; vereinfachen Sie das Programm.
\item �berlegen Sie sich M�glichkeiten, das Programm ordentlich terminieren zu
  lassen! Schwierigkeit ist offenbar, da� clients auf ein entry warten k�nnen,
  wenn der Zug Feierabend macht.
  Diskutieren/probieren Sie L�sungen, bei denen
  \begin{itemize}
  \item der Ablauf in "`station"' durch weitere
    Zustandsgr��en/Handlungsalternativen verfeinert wird.
  \item die Klienten fr�her Schlu� machen (nach n Fahrten) als der Zug.
  \item von uns noch nicht behandelte Sprachmittel Adas (insbesondere
    "`{\ttfamily requeue \dots with abort}"' sowie "`asynchronous transfer of
    control"', kurz ATC) eingesetzt werden.
  \end{itemize}
\end{enumerate}

%Folie 209-228; OOP revision; nothing important, left out!

%Folie 229
\chapter{Concurrency and Objects}

\section{Grunds�tzliches}
\begin{important}
  Nebenl�ufigkeit (tasks, protected objects) und Vererbung (extendible types)
  sind in Ada \emph{getrennte Konzepte}.
  Grund: Prinzipielle semantische Schwierigkeiten, Effizienzprobleme.
\end{important}

$\Rightarrow$ Der Programmierer mu� fallweise selbst geeignete
\emph{Kombination} von tasks/protected objects und Typhierachien bilden, wobei

\begin{itemize}
\item Tasks/protected objects definieren allgemeines
  Verhaltens-/Synchronisationsschema.
\item Damit gekapselte Objektdefinitionen beinhalten Spezialisierungen,
  Varianten.
\end{itemize}

%Folie 230
Offenbar 2 M�glichkeiten der \emph{Kombination}.
\begin{enumerate}
\item Objekt hat task/protected object als Attribut.
\item Task/protected object ist �ber Diskriminante (access Typ!) mit
  task/protected object gekoppelt.
\end{enumerate}

Grunds�tzlich gibt es 2 Anwendungszwecke, mit flie�enden �berg�ngen.
\begin{enumerate}
\item Mache Objekte \emph{aktiv}, d.\,h. statte sie mit eigenem Verhalten aus
  (vgl. z.\,B. Simula Prozesse). \\
  $\sim$ Proze� + Vererbung, wobei letzters problematisch.
\item Erlaube, da� \emph{passives} Objekt in Umgebung mit
  \emph{Nebenl�ufigkeit} benutzt wird, z.\,B. mehrere tasks greifen auf Objekt
  zu, d.\,h. statte Objekt mit \emph{Synchronisationsmechanismus} aus. \\
  $\sim$ Protected object + Vererbung.
\end{enumerate}

%Folie 231
Wir betrachten im folgenden die zweite Zielsetzung!

\section{Einfache Synchronisationsmechanismen f�r Objektzugriffe}
\paragraph{Aufgabe}
Zugriffe auf Objekt-Operationen sollen unter \emph{wechselseitigem Ausschlu�}
erfolgen.

\subsection{Objekte enthalten Synchronisationsmechanismen als Attribut}
\label{sec:ObjSyncAtt}
\paragraph{Sei definiert}
\begin{code}
protected type Mutex is
   entry Lock;
   procedure Unlock;

private
   Open: Boolean := True;
end Mutex;

protected body Mutex is
   entry Lock when Open is
   begin
      Open := False;
   end Lock;

   procedure Unlock is
   begin
      Open := True;
   end Unlock;
end Mutex;
\end{code}

%Folie 232
Dann bilde \emph{Wurzeltyp} f�r beabsichtigte Typen:
\begin{code}
package Lockable_Pack is
   type Lockable is abstract tagged limited private; -- Wurzeltyp

                          -- eine Methode, gesch�tzt durch mutex!
   procedure Synchronized_Op(Object: in out Lockable�Class); 

private
   type Lockable is tagged limited record
      Synchronizer: Mutex;
   end record;

   procedure Op(Object: in out Lockable) is abstract;
end Lockable_Pack;

package body Lockable_Pack is
   procedure Synchronized_Op(Object: in out Lockable�Class) is
   begin
      Object.Synchronizer.Lock;
      Op(Object);  -- dispatch to actual operation
      Object.Synchronizer.Unlock;
   end Synchronized_Op;
end Lockable_Pack;
\end{code}

%Folie 233
\paragraph{Also}
\begin{itemize}
\item Umgebe tats�chliche Operation mit Protokolloperation lock/unlock.
\item Mache tats�chliche Operation \emph{privat} und exportiere \emph{nur} die 
  um das Protokoll bereicherte Operation.
\item Tats�chliche Operation ist hier noch abstrakt und kann sp�ter bei
  Typableitung deklariert werden.
\end{itemize}

%Folie 234
\paragraph{Kleines Problem}
Wenn abstrakte Operation op \emph{privat}, wie kann sie dann f�r Typerweiterung 
sichtbar gemacht werden?

\paragraph{Ada-Ausweg}
\begin{description}
\item[Child-packages] Pakete, die privaten Teil des Eltern-Pakets anschauen
  d�rfen. \\
  Notation: {\ttfamily <Elternname>.<Paketname>}
\end{description}

\paragraph{Also}
\begin{code}
package Lockable_Pack.Child is
   type Lockable_Concrete is new Lockable with private;

private
   procedure Op(Object: in out Lockable_Concrete);
end Lockable_Pack.Child;

package body Lockable_Pack.Child is
   type Lockable_Concrete is new Lockable with null record;

   procedure Op(Object: in out Lockable_Concrete) is
   begin
      ...
   end Op; -- override abstract op
end Lockable_Pack.Child;  
\end{code}

%Folie 235
Nat�rlich kann man auch weitere Dinge hinzuf�gen, z.\,B.
\begin{code}
package Lockable_Pack.Child2 is
   type Extended_Lockable is new Lockable with private;

   procedure Synchronized_Op2(Object: in out Extended_Lockable);

private
   type Extended_Lockable is new Lockable with record
      ...  -- new state variables
   end record;

   procedure Op(Object: in out Extended_Lockable);  -- override
   procedure Op2(Object: in out Extended_Lockable);
end Lockable_Pack.Child2;
\end{code}

Und im Rumpf dann Synchronized\_Op2 wieder unter Anwendung des Protokolls
definieren.

%Folie 236
\begin{code}
package body Lockable_Pack.Child2 is
   procedure Op...
   procedure Op2...

   procedure Synchronized_Op2(Object: in out Extended_Lockable) is
   begin
      Object.Synchronizer.Lock;
      Op2(Object);
      Object.Synchronizer.Unlock;
   end Synchronized_Op2;
end Lockable_Pack.Child2;
\end{code}

\begin{important}
  Nachteil: Klient greift nicht selbst (nicht direkt) auf protected object zu,
  soda� z.\,B. Timeouts schwieriger zu realisieren sind.
\end{important}

%Folie 237
\subsection{Protected object ist �ber Diskriminante mit zu sch�tzendem Object
  verbunden}
\label{sec:projObjDis}
\begin{code}
package Lockable_Pack is
   type Objects is abstract tagged null record;  -- Wurzeltyp

   protected type Mutex_Plus(O: access Objects�Class) is
      procedure Synchronized_Op;
   end Mutex_Plus;

private
   procedure Op(Object: in out Objects) is abstract;
end Lockable_Pack;

package body Lockable_Pack is
   protected body Mutex_Plus is
      procedure Synchronized_Op is
         begin 
            Op(O.all);
         end Synchronized_Op;
   end Mutex_Plus;
end Lockable_Pack;
\end{code}

%Folie 238
Anwendung dann wieder so, da� im child-package eine konkrete Version f�r op
definiert wird.
\begin{code}
package Lockable_Pack.Child is
   type Concrete_Objects is private;

private
   type Concrete_Objects is new Objects with null record;
                                       -- k�nnte nat�rlich auch was dazukommen!
   procedure Op(Object: in out Concrete_Objects);  -- override abstract op
                                       
   O: aliased Concrete_Objects;  -- erzeuge Objekt,
   Synchronizer: Mutex_Plus(O�access);  -- und kopple mit mutex!
end Lockable_Pack.Child;

package body Lockable_Pack.Child is
   procedure Op(Object: in out Concrete_Objects) is
   begin
      ...
   end Op;
end Lockable_Pack.Child;
\end{code}

%Folie 239
\begin{important}
  Gro�er Nachteil der Methode: Zu Beginn, d.\,h. bei Definition des protected
  objects "`mutex\_plus"' mu� Anzahl (und Art) der Operationen (Methoden) der
  Objektfamilie schon feststehen -- man kann sp�ter nichts mehr hinzuf�gen zu
  dein Operationen des protected\_objects.
\end{important}

Was bleibt dann bei dieser Methode noch f�r Typerweiterung �brig? Man kann:
\begin{itemize}
\item Beteiligte Datentypen \emph{variieren} (z.\,B. Keller f�r Integer, Char,
  \dots = generics!)
\item Implementierung \emph{variieren} (z.\,B. Keller durch array, linked list)
\end{itemize}
\emph{und} diese Varianten als zu \emph{einem} Typ geh�rig behandeln und
verwalten ( Unterschied zu generics).

%Folie 240
\section{"`Bounded Buffer"' im Stil \ref{sec:projObjDis} (Code aus
  Burns/Wellings)}
\begin{code}
package Buffers is
   type Data abstract tagged null record;  -- lasse Elementtyp offen
   type Bufer is abstract tagged private;  -- lasse Implementierung offen

   -- Basic protected Buffer
   protected type Buffer_Controller(B: access Buffer�Class) is
      entry Put(D: in Data�Class);  -- entries, weil condition snychro
      entry Get(D: out Data�Class);
   end Buffer_Controller;

   procedure Put(D: Data�Class; B: access Buffer) is abstract;
   procedure Get(D: Data�Class; B: access Buffer) is abstract;
   function Buffer_Not_Full(B: access Buffer) return Boolean is abstract;
   function Buffer_Not_Empty(B: access Buffer) return Boolean is abstract;

private
   type Buffer is abstract tagged null record;
end Buffers;

package body Buffer is
   protected body Buffer_Controller is
      entry Put(D: in Data�Class) when Buffer_Not_Full(B) is
         -- note Buffer_Not_Full(B) is a dispatching operation
      begin
         Put(D, B); -- dispatching operation
      end Put;

      entry Get(D: in Data�Class) when Buffer_Not_Empty(B) is
         -- note Buffer_Not_Empty(B) is a dispatching operation
      begin
         Get(D, B); -- dispatching operation
      end Get;
   end Buffer_Controller;
end Buffers;
\end{code}

%% INSERT: Skizze (easy, lowest)
%\begin{figure}[htbp]
%\includegraphics{.eps}
%\end{figure}

%Folie 241
Jetzt Typerweiterung: Puffer soll als Vektor realisiert werden und kriegt hier
entsprechende Attribute.
\begin{code}
package Buffers.Array_Based_Buffers is
   type Array_Buffer is abstract new Buffer with private;
   Buffer_Size: constant Natural := 10;

   procedure Put(D: Data�Class; B: access Array_Buffer) is abstract;
   procedure Get(D: out Data�Class; B: access Array_Buffer) is abstract;

   function Buffer_Not_Full(B: access Array_Buffer) return Boolean is abstract;
   function Buffer_Not_Empty(B: access Array_Buffer) return Boolean is abstract;

private
   -- The package could be made generic, and the size passed as a generic parameter
   subtype Index is mod Buffer_Size;
   subtype Count is Natural range 0..Buffer_Size;

   type Array_Buffer is abstract new Buffer with record
      First: Index := Index�First;
      Last: Index := Index�First;
      Number_In_Buffer: Count := 0;
   end record;
end Buffers.Array_Based_Buffers;
\end{code}

\begin{important}
  Hier noch als \emph{abstrakt}, \emph{keine} Implementierung, da
  \emph{Elementtyp} noch nicht feststeht.
\end{important}

Zwischenschritt ist sinnvoll, wenn man array-basierte Puffer f�r verschiedene
Elementtypen haben will.

%Folie 242
Implementierung: Integer Elemente
\begin{code}
package Buffers.Array_Based_Buffers.Integer_Buffers is
   type Integer_Data is new Data with record
      X: Integer;
   end record;

   type Integer_Array_Buffer is new Array_Buffer with private;

private
   -- a bounded buffer

   type Integer_Array is array(Index) of Integer_Data;
   -- child package has visibility of the private part of the parent

   type Integer_Array_Buffer is new Array_Buffer with record
      Mb1: Integer_Array;
   end record;

   procedure Put(D: Data�Class; B: access Integer_Array_Buffer);
   procedure Get(D: out Data�Class; B: access Integer_Array_Buffer);

   function Buffer_Not_Full(B: access Integer_Array_Buffer) return Boolean;
   function Buffer_Not_Empty(B: access Integer_Array_Buffer) return Boolean;
end Buffers.Array_Based_Buffers.Integer_Buffers;
\end{code}
Jezt Implementierung m�glich.

%Folie 243
Implementierung:
\begin{code}
package body Buffers.Array_Based_Buffers.Integer_Buffers is
   procedure Put(D: Data�Class; B: access Integer_Array_Buffer) is
   begin
      B.Mb1(B.Last) := Integer_Data(D);  -- may generate Constraint_Error
      B.Last := B.Last +1;
      B.Number_In_Buffer := B.Number_In_Buffer +1;
   exception
      when Contraint_Error =>
         -- potential error recovery
         raise;
   end Put;

   procedure Get(D: out Data�Class; B: access Integer_Array_Buffer) is
   begin
      D := Data�Class(B.Mb1(B.First));
      B.First := B.First +1;
      B.Number_In_Buffer := B.Number_In_Buffer -1;
   end Get;

   function Buffer_Not_Full(B: access Integer_Array_Buffer) return Boolean is
   begin
      return B.Number_In_Buffer = Buffer_Size;
   end Buffer_Not_Full;

   function Buffer_Not_Empty(B: access Integer_Array_Buffer) return Boolean is
   begin
      return B.Number_In_Buffer /= 0;
   end Buffer_Not_Empty;
end Buffers.Array_Based_Buffers.Integer_Buffers;
\end{code}

\begin{important}
  Eleganz der Gesamtkonzeption ist wie oft bei OO verbunden mit
  Laufzeit-Unsicherheit: Weil Put/Get f�r Datenelemente Parameter von
  \emph{klassenweiten} Typ haben, ist Aufruf mit anderem (von Data
  abgeleitetem) Typ ebenfalls m�glich.
\end{important}

%Folie 244
\section{Inheritance Anomaly}
Die beiden oben dargestellten Techniken sind in ihrer Anwendbarkeit sehr
beschr�nkt:
\begin{itemize}
\item \ref{sec:projObjDis} verlangt, da� vorweg klar ist, welche Operationen
  der Synchronisation durch das protected object unterworfen werden sollen,

\item \ref{sec:ObjSyncAtt} erlaubt zwar, weitere Operationen hinzuzuf�gen,
  erm�glicht aber \emph{keine freie Gestaltung/�nderung/Bedingungssynchronisation}.
\end{itemize}

In dem in \ref{sec:ObjSyncAtt} beschriebenem Verfahren kann man beliebig viele
Operationen op2, op3 usw. dazunehmen und dem wechselseitigen Ausschlu�
unterwerfen (oder eben nicht), aber es ist \emph{unm�glich}, da� z.\,B.
\begin{itemize}
\item op1 mu� allein sein, op2, op3 zusammen.
\item Zustandsabh�ngige Synchronisation/Ausschlu� (z.\,B. Puffer voll/leer).
\end{itemize}

Solche �nderungen sind nur unter \emph{Aufhebung} des \emph{Geheimnisprinzips}
und \emph{�nderung} fr�her definierter Operationen m�glich. = Inheritance
anomaly!

%Folie 245
\paragraph{Im folgenden}
Diskussion des Problems unabh�ngig von Ada.

\begin{description}
\item[Klassische �bersicht] \ 
  \begin{itemize}
  \item S. Matsoka, A. Yonezawa: "`Analysis of Inheritence Anomaly in OO
    Concurrent Languages"', Proc. Research Directions in concurrent OOP (Ayha,
    Wegno, ed.), MIT, 1993
  \end{itemize}
\item[Ada95-spezifischer Artikel] \ 
  \begin{itemize}
  \item G. Schumacher, W. Nebel: "`How to Avoid the Inheritance Anomaly in
    Ada"', Proc. Ada-Europe �98, Springer LNCS 1411, 1998

    Ziemlich weitreichende L�sung in Ada95, aufwendig und zum Teil unsch�n,
    z.\,B. massiver Gebrauch von exceptions zur Ablaufsteuerung.
  \end{itemize}
\end{description}

%Folie 246
\paragraph{Allgemeine Aufgabe}
\begin{itemize}
\item Methoden eines Objekts unterliegen hinsichtlich Aufrufbarkeit
  \emph{Synchronisationsbedingungen}, also zu jedem Zeitpunkt immer nur
  Teilmenge der existierenden Methoden aufrufbar, um Integrit�t des Objekts zu
  sch�tzen: Konkurrenter (mehrere Klienten Prozesse) Zugriff kann
  z.\,B. erfordern:
  \begin{itemize}
  \item Wechselseitiger Ausschlu�
  \item Objekt in bestimmtem Zustand.
  \end{itemize}

\item Deshalb enth�lt Klassen- (Objekt-) Definition \emph{Synchronisationscode} 
  (insbesondere als Teil von Methodenimplementierungen) zur Realisierung der
  Synchro-Bedingungen.

\item Dann \emph{Konflikt} Vererbung $\leftrightarrow$ Synchronisation:
  Neueinf�hrung/�berschreibung einer Methode kann zu massiven �nderungen
  scheinbar unbeteiligter Elemente in der Klassenhierarchie f�hren!
\end{itemize}

%Folie 247
Problem hat noch keine befriedigende und allgemein akzeptierte L�sung und ist
Gegenstand aktueller Forschung und Diskussion; aber beachte: Abh�ngig von
Sprachmitteln, je nach Formulierung verschieden schwerwiegend.

Wir betrachten \emph{Beispiele}, die alle beruhen auf dem \emph{Anwendungsfall} 
"`bounded buffer"' mit Get/Put Operationen.

\subsection{Objekte mit Rumpf (body)}
Aktives Objekt mit eigenem Kontrollflu� (= spezielle Methode, "`Hauptprogramm"'
des Objekts, Proze�).

Rumpf \emph{kontrolliert} Methodenausf�hrung, vgl. Ada: Service\_Task (=
Endlosschleife mit selektivem accept).

%Folie 248
Dabei kann dann akzeptierter Methodenaufruf konkurrent oder innerhalb des
Rumpf-Prozesses ausgef�hrt werden.

\begin{important}
  Offenbar: F�r jede Unterklasse, die neue Methoden einf�hrt oder
  Synchronisationsbedingungen �ndert, mu� \emph{body neu definiert} werden.
\end{important}

\subsection{Akzeptanz-Mengen ("`enabled sets"')}
Am Ende der Ausf�hrung einer Methode wird jeweils explizit die Menge der
Methoden festgelegt, die als n�chstes akzeptiert werden; dabei:
\begin{itemize}
\item wechselseitiger Ausschlu� unterstellt
\item Bezeichner f�r enabled sets
\end{itemize}

%Folie 249
\paragraph{Beispiel}
\begin{code}
Class Bounded_Buffer is
  procedure Put(...);
  procedure Get(...);

  Enabled Sets:
    Empty := {Put},
    Partial := {Put, Get},
    Full := {Get};

Implementation
  In, Out: Integer := ...;
  Buf: array(Size) of ...;

  procedure Put(...) is
  begin
     ...
     if In = Out then
       Become Full;
     else
       Become Partial;
     end if;
  end Put;

  procedure Get(...) is
  begin
     ...
     if In = out then
       Become Empty;
     else
       Become Partial;
     end if;
  end Get;
end Bounded_Buffer;
\end{code}

%Folie 250
Jetzt neue Operation: {\ttfamily procedure last(\dots)} entnimmt \emph{letzten} 
Eintrag.

\begin{code}
Class X_Buffer Extends Bounded_Buffer is
  procedure Last(...);

  Enabled Sets:
    Partial := {Put, Get, Last},
    Full := {Get, Last};

Implementation
  procedure Last(...) is
  begin
    ...
    if In = out then
      Become Emtpy;
    else
      Become Partial;
    end if;
  end Last;
end X_Buffer;  
\end{code}

D.\,h. einfache \emph{Erweiterung} von enabled-set! Aber das ist \emph{nicht
  immer} m�glich:

%Folie 251
\paragraph{Beispiel}
F�hre neue Operation "`Get2"' ein.

Bedeutung: Hole 2 Elemente auf einmal; das ist offenbar \emph{nicht} durch
zweimaliges Get zu machen, weil anderer Klienten-Proze� intervenierend Puffer
leeren k�nnte \dots

$\Rightarrow$ Get erfordert \emph{Aufspaltung} eines vorhandenen enabled sets,
d.\,h. \emph{Verfeinerung} von Partial -- nur 1 Element - 2 oder mehr Elemente
- vorhanden.

$\Rightarrow$ Get/Put m�ssen in ihrem \emph{becomes}-Teil ge�ndert werden.

\begin{important}
  Immerhin nur lokalisierte �nderung, \emph{ferner}: become-Teil kann
  \emph{interne Methode} sein, die man \emph{�berschreibt}.
\end{important}

%Folie 252
\subsection{W�chter (guards) f�r Methoden}
�hnlich in Problemen und M�glichkeiten wie letzter Ansatz. W�chter: Vgl. Ada
entries.

Anwendung auf Beispiel: Klar, z.\,B. {\ttfamily procedure Get(\dots) when (In
  >= Out +1) is \dots}

\begin{important}
  Kann F�lle wie "`Get2"' vereinfachen, wichtig auch hier: Guard �berschreibbar?
\end{important}

\begin{important}
  Aber: Methode versagt, wenn vorhandene \emph{Zustandsgr��en} die gew�nschte
  Bedingung \emph{nicht auszudr�cken} verm�gen.
\end{important}

Typisches Beispiel: Zustand = Details der Vor-Geschichte, z.\,B. Reihenfolge
fr�herer Methodenaufrufe.

%Folie 253
\begin{important}
  Nat�rlich gilt immer: Zustand = Akkumulierte Vorgeschichte, aber tats�chliche 
  Wahl von Zustandsbegriff immer bezogen auf Funktion,
  d.\,h. Abstraktion/�quivalenzklassenbildung; Vorgeschichte = \emph{feinster}
  Zustandsbegriff.
\end{important}

\paragraph{Beispiel}
F�hre Operation "`Gget"' ein, Bedeutung: Wie Get, \emph{aber nur ausf�hrbar,
  wenn} letzte vorangegangene Operation auch ein Get war.

\begin{important}
  Offenbar nicht ausdr�ckbar mit vorhandenen Variablen (Zustandsattributen),
  man mu� zus�tzlich festhalten, ob letzte Operation Get oder Put war.
\end{important}

%Folie 254
Dies ist immerhin noch als \emph{Verfeinerung} des Zustandsraums zu machen:
Gget enabled $\Rightarrow$ Get enabled, aber auch m�glich, \emph{inkompatibles
  Verhalten} einzuf�hren: Operation \emph{Lock/Unlock}, die Ausf�hrung anderer
Operationen \emph{sperren} oder wieder freigeben, d.\,h. Get/Put nicht immer
zul�ssig unter alten Bedingungen, sondern nur unter \emph{Einschr�nkungen}
davon.

$\Rightarrow$ Neue Guards f�r Get/Put n�tig.

\end{document}
