% -*- 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 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(); end T; task body T is ... accept E() do ... end E; end T; \end{code} \item \begin{description} \item[Gebrauch] Sei {\ttfamily T1:T;}, dann Aufruf des entries mit {\ttfamily T1.E();} \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 private ; end P; protected body P is 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} ::= select [when =>] {or [when =>] } [else ] end select; \end{code} Wobei \begin{code} ::= | | \end{code} Wir betrachten nun diese drei Möglichkeiten. %Folie 131 \subsection{accept\_alternative} \begin{code} ::= [] \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; \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 ; | delay until ; \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} ::= select or end select; \end{code} wobei \begin{code} ::= [] \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} ::= select else 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 } -- 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 .} \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}