Nebenläufige Programmierung Ein Vortrag von Prof. Dr. Gert Smolka Der Vortrag von Herrn Smolka beschäftigte sich mit nebenläufiger Programmierung. Zu Beginn seines Vortrags führte Herr Prof. Smolka insgesamt vier Szenarien an. Zunächst das Telefon-Szenario. Dies muss man sich so vorstellen: es gibt eine Telefonzelle (Ressource) und mehrere Personen (Prozesse) wollen gleichzeitig telefonieren. Dies funktioniert allerdings nicht; es kann immer nur eine Person telefonieren (gegenseitiger Ausschluss). Ein anderes Szenario ist das Brotstand-Szenario. Es gibt wieder nur eine Ressource (einen Brotstand mit einer Verkäuferin) und mehrere Prozesse (mehrere Personen wollen Brot kaufen). Es kann allerdings nur eine Person bedient werden (Warteschlange). In diesem Fall tritt z.B. der Begriff der Fairness auf. Fairness bedeutet, dass z.B. die Verkäuferin nicht plötzlich - nachdem sie Kunde A bedient hat - Kunde D bedient, wenn dieser nach den Kunden B und C gekommen ist, nur weil ihr dessen Gesicht besser gefällt. Handelt sie nicht fair, so kann es im schlimmsten Fall passieren, dass die Kunden B und C verhungern. Um das "Verhungern" zu verhindern, hat man sogenannte Warteschlangen eingeführt. Diese legen eine eindeutige Rangfolge fest, in der die Prozesse bedient werden. Diese Rangfolge garantiert, dass die Prozesse nicht ewig auf die Ressource warten müssen. Ein weiteres Szenario ist das Konto-Szenario. Es gibt ein Konto bei einer Bank und mehrere Zugriffe sollen auf das Konto erfolgen (z.B. durch den Geldautomaten, durch Geschäfte oder durch Banken). Es kann aber immer nur einer auf das Konto zugreifen. Gleiches Spiel wie bei den beiden anderen Szenarien. Was bei diesem Szenario neu auftritt, ist der Begriff des Indeterminismus. Dies bedeutet, dass Auswirkung und Ergebnis nur schwer reproduziert werden können. Man stelle sich nur vor, dass der Mann in Rom von einem Geldautomaten auf sein Konto zugreift und ungefähr zeitgleich seine Frau in Madrid. Auswirkung und Ergebnis können nur schwer reproduziert werden, denn es ist z.B. nicht zu beeinflussen, wer jetzt zuerst den Zugriff auf das Konto erhält. Ein wichtiges Szenario ist das Ski-Szenario. Wir haben zwei Ressourcen: Auto mieten und Skier mieten. Beide Ressourcen werden für ein Wochenende im Schnee benötigt. Das Problem ist jedoch, dass die Autovermietung im Ort nur noch ein Auto hat und das Sportgeschäft nur noch ein Paar Skier. Karl und Berta, die sich jedoch beide nicht kennen, wollen ein Wochenende im Schnee verbringen. Es gibt nun vier Möglichkeiten. 1. Karl bekommt Auto und Skier, 2. Berta bekommt Auto und Skier, 3. Karl bekommt das Auto und Berta die Skier, 4. Berta bekommt das Auto und Karl die Skier. In den letzten beiden Fällen tritt eine sogenannte Verklemmung (Deadlock) auf. Verklemmungsgefahr besteht dann, wenn ein Prozess mehrere Ressourcen benötigt. In dem konkreten Beispiel heißt das in den beiden letzten Fällen, dass für beide das Wochenende im Schnee gestorben ist, wenn sie sich nicht zusammentun. Ein sehr berühmtes Beispiel namens "Dining Philosophers" wurde um 1960 von Dijkstra aufgestellt. Drei Philosophen sitzen an einem Tisch. Es gibt insgesamt nur drei Essstäbchen; man braucht jedoch zum Essen jeweils zwei. Jeder bekommt ein Essstäbchen. Da die Philosophen stur sind, verhungern alle drei, weil jeder nur mit zwei Stäbchen essen kann. Was ihnen nicht in den Sinn kommt, ist die Ressourcen zu teilen. Diese Probleme wurden bei der Konstruktion von Betriebssystemen entdeckt. Wichtige Begriffe der nebenläufigen Programmierung sind also: - Ressourcen und Prozesse - Gegenseitiger Ausschluss - Konkurrenzsituation - Fairness / Verhungern - Verklemmungsgefahr - Indeterminismus Betriebssystem Das Betriebssystem dient als Verwaltungprogramm für den Computer. Es kann mehrere Programme gleichzeitig ausführen. Diese (laufenden) Programme bezeichnet man als Prozesse. Das Betriebssystem bietet die Kommunikationsmöglichkeit für verschiedene Prozesse. Über eine Vernetzung ist es sogar möglich, dass Prozesse auf verschiedenen Computern miteinander kommunizieren können. Parallelität Unter Parallelität versteht man das gleichzeitige Ausführen von Operationen. Dazu gibt es z.B. Computer mit mehreren Prozessoren, wobei Prozesse nicht gleich Prozessoren sind. Des weiteren ist Nebenläufigkeit ungleich Parallelität. Es ist gut, Programme zu parallelisieren und parallele Algorithmen zu entwerfen. Die Prozessoren selbst, parallelisieren intern. Die primäre Hardware/Software-Schnittstelle ist (noch) sequentiell. Das bedeutet, dass auf unterster Ebene der parallele Prozessor sitzt, darüber der sequentielle Befehlssatz und darüber die nebenläufige Software. Threads Ein Thread ist die sequentielle Ausführung innerhalb eines Prozesses. Es gibt mehrere Threads pro Prozess. Die Prozesse selbst haben einen getrennten Speicherbereich, die Threads eines Prozesses sehen jedoch den gleichen Speicherbereich. Die weiteren Ausführungen von Herrn Prof. Smolka basierten auf der am Lehrstuhl Programmiersysteme entwickelten Programmiersprache Alice auf, die eine Erweiterung von Standard ML darstellt. Threads und Futures spawn (Ausdruck) erzeugt einen Thread, der einen Ausdruck auswertet. spawn liefert ein Future als Stellvertreter für den Wert des Ausdrucks. Datenfluss-Synchronisation Operationen blockieren automatisch, wenn sie einen Wert benötigen. Threads können parallelisiert werden. Man denke an Prozessoren mit mehreren Threads. Portale und Ströme Eine nebenläufige Datenstruktur ermöglicht eine many-to-one Kommunikation zwischen Threads. Alice stellt dazu eine Prozedur port bereit, die eine Botschaft in einen Strom legt. Ein Strom ist eine angefangene Liste mit einer Future am Ende. Bedarfsgesteuerte Berechnung Die Prozedur lazy liefert eine Future als Stellvertreter für den Wert eines Ausdrucks. Erst wenn der Wert benötigt wird, wird der Ausdruck ausgewertet. Dies ermöglicht z.B. das Programmieren mit unendlichen Listen. Es ist auch das bedarfsgesteuerte Laden von Programmkomponenten möglich (z. B. in Java). Dadurch wird Software schneller, da man zunächst nur die Teile der Software lädt, die benötigt werden. Wird eine bestimmte Funktion gebraucht, lädt man einfach das entsprechende Modul dazu. Des weiteren kann man dadurch verhindern, dass bei einem Programmierfehler in einem Modul gleich das ganze Programm abstürzt. Der JIT Compiler realisiert eine andere Technik: das bedarfsgesteuerte Übersetzen von Programmen. Es werden nur die Programmteile (neu) übersetzt, die wirklich geändert wurden. Als Beispiel für bedarfsgesteuerte Programmierung kann man etwa die funktionale Sprache Haskell anführen, in welcher diese Art der Programmierung voll ausgereizt wird (lazy functional programming). Monitore Auf Ressourcen wird durch Operationsanwendungen zugegriffen (z.B. auf ein Konto bei einer Bank). Ein Monitor sequentialisiert diese Operationsanwendungen automatisch. Somit wird ein gleichzeitiger Zugriff verhindert. Remote Procedure Calls, Proxies, Offer und Take Es gibt zwei Prozesse A und B. Im Prozess B gibt es eine Prozedur p, welche A aufrufen will. Dazu braucht A eine Referenz auf p in B. Das Argument für die Prozedur p muss von A nach B und das Ergebnis von B nach A gebracht werden. Dazu dient ein Stellvertreter für die Prozedur p: ein Proxy. Dieser erledigt den Transfer von Argumenten und des Ergebnisses und kann zwischen Prozessen hin und her gereicht werden. Das Erzeugen von Proxies ist in Alice kein Problem. Die Frage ist jedoch, wie ein solcher Proxy in einen anderen Prozess kommt. In Alice gibt es dazu die Prozeduren Offer und Take. Take prüft, ob der übergebene Wert den erwarteten Typ hat. Offer übergibt an den Prozess. Das Offerieren von Strukturen wäre zwar besser, jedoch sind Strukturen keine Werte. Pakete Ein Paket enthält eine Struktur und eine Signatur gemäß der die Struktur benutzt werden kann. Alice stellt die Prozeduren pack und unpack bereit. pack bautaus einer Signatur und einer Struktur ein Paket. Unpack erhält ein Paket und eine Signatur und liefert eine Struktur. Die dynamische Typprüfung wird von unpack übernommen. Offer und take tauschen Pakete aus. Dies alles realisiert man mit einem Compute Server, über den die Pakete ausgetauscht werden. Ich persönlich finde nebenläufige Programmierung sehr wichtig, weil in der heutigen Zeit ein Betriebssystem ohne parallel ausführbare Programme nicht mehr denkbar wäre. Alleine das Internet ist ein gutes Beispiel dafür. Ohne einen Prozess, der für den Paketaustausch verantwortlich ist, kann man nicht surfen. Jedoch kann man nur dann surfen, wenn ein Browser läuft. Somit haben wir mindestens zwei Prozesse, die parallel laufen müssen. Nimmt man aber von solch speziellen Anwendungen Abstand, so zeigt sich trotzdem, dass man ohne parallel laufende Prozesse nicht auskommt. Ein Betriebssystem selbst hat viele Dienste, die parallel laufen müssen. Als Beispiele könnte man z.B. den Kernel, eine Shell und eine grafische Oberfläche nennen.