2. Grundlagen

Um das Konzept der Nebenläufigkeit zu integrieren, wurde Haskell um zwei wesentliche Inhalte erweitert:

• Prozesse und Mechanismen zum Erzeugen eines Prozesses
• Interprozesskommunikation mit Hilfe von veränderbaren Zustandsvariablen

Da diese Grundlagen auf dem Konzept der EA-Monads basieren, soll dieses zunächst kurz angerissen werden. Als eine detaillierte Quelle zu Monads sei auf das Seminar Monads von Nils Decker verwiesen. Darüberhinaus ist im Literaturverzeichnis weiterführende Literatur zu finden.

2.1 Konzept der EA-Monads

Haskell ist eine nicht-strikte Programmiersprache, d.h. es kann in einem Ausdruck nicht im Vornherein bestimmt werden, welcher Teilausdruck zuerst ausgewertet bzw. ob ein Teilausdruck überhaupt ausgewertet wird. Die Auswertung ist vom Kontext abhängig und kann daher nicht vorausgesagt werden. Diese Spracheigenschaft ist für die Durchführung von EA gänzlich ungeeignet. Es kann z.B. passieren, dass eine für das Schreiben von Daten in einen Ausgabekanal wichtige Leseoperation erst nach der Schreiboperation ausgeführt wird.

Diesem Problem begegnet man, in dem EA-Operationen als Zustandsveränderungen behandelt werden. Dabei wird unterschieden zwischen dem internen Zustand des Programms und dem externen Zustand in der Umgebung, der auch als "Rest der Welt" bezeichnet wird. Eine EA-Operation macht nun nichts anderes, als den externen Zustand zu verändern und ein Ergebnis dieser Operation zurückzuliefern. Durch Einsatz von EA-Monads ist es möglich, diese EA-Operationen zusammenzufassen und zu sequenzialisieren. Diese Ideen führen zu folgender Typdefinition von EA-Operationen:

type IO a = World -> (a, World)

Hier ist beschrieben, dass eine EA-Operation vom Typ IO a einen externen Zustand (World) als Input nimmt und einen veränderten Zustand mit einem Typ a wieder zurückliefert. Ein Wert vom Typ IO a wird dabei als Aktion bezeichnet.

Zwei einfache Aktionen, die als Beispiel gegeben werden sollen sind:

hGetChar :: Handle -> IO Char 
hPutChar :: Handle -> Char -> IO ()  

Diese Aktionen können durch die Infix-Kombinatoren >> oder >>= miteinander kombiniert werden, sodass z.B. folgendes Programm einen Char als Input nimmt und ihn dann auf dem Bildschirm wieder ausgibt. Die Infix-Operatoren stellen die Grundlage für die Sequenzialisierung von Anweisungen dar. Alternativ kann auch die do-Notation zur Sequenzialisierung verwendet werden.

hGetChar stdin >>= \c -> hPutChar stdout c 

do
c <- hGetChar stdin
hPutChar stdout c

Bei der Kommunikation von Prozessen, die mit Hilfe von veränderbaren Zustandsvariablen durchgeführt wird, wird ebenfalls mit Aktionen gearbeitet, durch die diese Variablen verändert werden. Das ist notwendig, weil diese Variablen global für alle Prozesse zugänglich sein sollen. Für einen Prozess ist also diese Zustandsvariable zum "Rest der Welt" zuzurechnen, genauso, wie die anderen Prozesse aus Sicht des einen Prozesses dem "Rest der Welt" zuzurechnen sind.

newMVar  ::  IO  (MVar  a) 
takeMVar :: MVar  a -> IO a
putMVar  :: MVar a -> a -> IO  ()  

Ein Wert vom type MVar a kann man sich als ein Ort vorstellen, in dem ein Wert vom Typ a gespeichert ist. Da dieser Ort zum externen Zustand also zum "Rest der Welt" gehört, findet der Ansatz mit EA basierend auf Monads hier Anwendung. Mit putMVar und takeMVar wird der Wert, der an dem Ort abgespeichert ist, verändert.

Die EA-Monads sind ein wichtiger Bestandteil der Sprache Haskell. Auch Programme liefern einen Wert vom Typ IO () und machen insofern nichts anderes, als den "Zustand der Welt" zu verändern.

2.2 Prozesse

Um einen Prozess zu starten, wurde die neue Funktion forkIO in Concurrent Haskell bereitgestellt. Der Prozess selbst ist kein zusätzlicher Prozess im Betriebssystem, sondern wird vom Haskell-Laufzeitsystem verwaltet.

forkIO :: IO () -> IO ()

forkIO a ist eine Aktion, die eine Aktion a als ihr Argument nimmt und einen konkurrierenden Prozess startet, um die übergebene Aktion auszuführen. EA und andere Seiteneffekte, die von der Aktion a durchgeführt werden, werden in einer unspezifizierten Weise mit den verflochten, die dem forkIO folgen.

Hierzu ein Beispiel:

main = forkIO (write 'a') >> write 'b'  
       where write c =  
         putChar  c >>  write c

forkIO erzeugt einen Prozess, der die Aktion write 'a' ausführt. Der Vaterprozess führt nach dem forkIO die Aktion write 'z' aus, sodass eine unspezifizierte Reihenfolge der Buchstaben 'a' und 'z' auf dem Bildschirm erscheint.

Im Zusammenhang mit forkIO gilt es, folgende Dinge zu beachten:

1. forkIO funktioniert nur dann einwandfrei, wenn die zugrundeliegende Implementierung von Haskell Interprozesskommunikation unterstützt. Dies ist notwendig, weil Haskellprogramme nicht-strikt ausgewertet werden. Versucht ein Prozess, einen Teilausdruck auszuwerten, der bereits von einem anderen Prozess ausgewertet wird, muss der erste Prozess blockiert werden, bis der andere seine Auswertung beendet hat. Diese Funktionalität muss von der Haskell-Implementierung gesichert werden.
   
2. Da Prozesse sich möglicherweise die gleichen Ressourcen teilen bzw. sich einen gemeinsamen "Rest der Welt" teilen, wird durch forkIO Nichtdeterminismus eingeführt. Denn durch forkIO wird es möglich, dass ein Prozess eine Datei lesen will, während ein anderer Prozess diese löscht. Der Effekt auf den Ablauf des Programms ist nicht mehr vorhersehbar. Die Lösung dieses Problems ist ein Mechanismus, der eine sichere Zustandsveränderung von geteilten Ressourcen ermöglicht (siehe Abschnitt 2.3).
   
3. forkIO ist asymmetrisch , da es einen Prozess startet, der konkurrierend zum fortlaufenden Vaterprozess läuft. Es gibt eine Funktion symFork, die zwei Prozesse startet die symmetrisch sind und deren Ergebnis zusammengeführt wird, wenn beide Prozesse beendet sind. Da dieser Ansatz jedoch mithilfe von MVars (siehe Abschnitt 2.3) simuliert werden kann, wird in dieser Ausführung nicht darauf eingegangen.
   
4. Der durch forkIO erzeugte Prozess besitzt keinen Namen, wie es in Betriebssystemen normalerweise für Prozesse üblich ist. Es gibt daher keine Möglichkeit, einen Prozess zu zerstören oder auf seine Beendigung zu warten. Durch MVars (siehe Abschnitt 2.3) wird es allerdings möglich, auf die Beendigung eines Prozesses zu warten. Die Zerstörung eines Prozesses ist jedoch weiterhin nicht möglich.

2.3 Synchronisation und Kommunikation

Man könnte vermuten, dass forkIO für die Implementierung von Nebenläufigkeit alleine bereits ausreicht, vorausgesetzt, die Haskell-Implementierung stellt die Synchronisation zwischen zwei Prozessen sicher, die versuchen, den gleichen Teilausdruck auszuwerten. Die Prozesskommunikation könnte dann über Streams (z.B. in Form von genügend großen Listen) erfolgen, in den ein Prozess hineinschreibt und ein anderer die Daten wieder ausliest. Die folgenden Gründe zeigen jedoch, dass zusätzliche Mechanismen zur Synchronisation und Kommunikation notwendig sind:

1. Prozesse müssen die Möglichkeit haben, Betriebsmittel wie z.B. Dateien exklusiv zu belegen. Steuert nur die Haskell-Implementierung mit Interprozesskommunikation das Betreten bestimmter Abschnitte, ist die exklusive Verfügbarkeit nicht gegeben. Für die Implementierung dieses exklusiven Belegungszustands ist eine Semaphore bzw. eine globale, veränderbare Variable zum Sperren notwendig.
   
2. Programme, die Streams verarbeiten, sind mitunter schwierig zu programmieren. Diese Erfahrung wurde beim Design von Concurrent Haskell berücksichtigt. Streams sollten durch ein Konzept ersetzt werden, dass einfacher zu handhaben ist.
   
3. Für Server-Prozesse ist es mitunter notwendig, bestimmte Ein- und Ausgabedatenströme zusammenzuführen bzw. aufzuspalten. Von einem Server müssen z.B. Datenströme mehrerer Clients zusammengeführt werden, oder es soll ein Eingabedatenstrom auf mehrere Serverprozesse aufgeteilt und verarbeitet werden. Dazu ist es notwendig, Operationen bereitzustellen, die nicht-deterministisches Zusammenführen und Aufspalten ermöglichen.
   

Zur Lösung dieser Anforderungen an Synchronisation und Kommunikation wird ein neuer primitiver Typ eingeführt:

type MVar a

Ein Wert vom Typ MVar t mit t für einen beliebigen Typ, ist der Name einer veränderbaren Stelle, die entweder leer ist oder einen Wert vom Typ t enthält. Für MVars werden folgende primitive Operationen zur Verfügung gestellt:

newMVar :: IO (MVar a)

Liefert eine neue MVar.

takeMVar :: MVar a -> IO a

Blockiert bis die Variable nicht leer ist, liest anschließend den Wert und liefert diesen zurück. Die Stelle wird leer hinterlassen.

putMVar :: MVar a -> a -> IO ()

Schreibt einen Wert in an die spezifizierte Stelle. Gibt es durch takeMVar blockierte Prozesse, wird einer deblockiert. Zu beachten gilt, dass ein Fehler ausgelöst wird, wenn versucht wird, die Operation auf eine bereits volle Stelle anzuwenden ^[1]. Es handelt sich also bei takeMVar und putMVar nicht um symmetrische Operationen, obwohl der symmetrische Ansatz aus Sicht des Sprachdesigns vernünftig wäre.

Der Typ MVar kann aus folgenden Blickwinkeln betrachtet werden:

• Zur Verwaltung des synchronisierten Zugriffs auf eine bestimmte Stelle
• Sie kann als Kanal betrachten werden, über die die Kommunikation zwischen zwei Prozessen abläuft. Dabei ist putMVar äquivalent zum Senden und takeMVar äquivalent zum Empfangen.
• Oder ganz simpel als eine binäre Semaphore, in denen die signal- and wait Operationen durch putMVar und takeMVar realisiert werden.