Anhand der im vorigen Abschnitt besprochenen Grundlagen zur MVar lassen sich diverse Standardabstraktionen konstruieren. Dazu gehört die Semaphore, die allerdings von der MVar direkt implementiert wird. Weitere Beispiele für Standardabstraktionen werden im folgenden konstruiert und erläutert.
Bei der Lösung des
Erzeuger-Verbraucher-Problems wird eine MVar herangezogen, in die der Produzent seine
Daten schreibt und der Konsument Daten entnimmt. Um zu Verhindern,
dass der Produzent einen weiteren Wert in die MVar schreibt, ohne
das der Empfänger den ersten ausgelesen hat, wird eine
zweite MVar benutzt, die Produzent und Konsument
synchronisiert.
|
|
| Abbildung: Datenfluss beim Erzeuger-Verbraucher-Problem |
Die resultierende Buffervariable wird als CVar (channel variable) bezeichnet und wird wie folgt konstruiert:
type CVar a = (MVar a, -- Produzent -> Konsument
MVar ()) -- Konsument -> Produzent
Die bereitgestellten Operationen auf MVars werden wie folgt konstruiert:
newCVar :: IO (CVar a)
newCVar
= do
data_var <- newMVar
ack_var <- newMVar
putMVar ack_var ()
return (data_var,ack_var)
Erzeugt einen neue CVar, in dem zwei MVars erzeugt werden. Damit ein Wert mit putCVar in den Puffer geschrieben werden kann, wird in ack_var zunächst ein Wert (leeres Paar) hineingeschrieben.
putCVar :: CVar a -> a -> IO ()
putCVar (data_var,ack_var) val
= do
takeMVar ack_var
putMVar data_var val
Schreibt den übergebenen Wert val in den Puffer. Dazu muss der Puffer jedoch leer sein. Steht im Puffer noch ein Wert, so blockiert der Prozess, der putCVar aufruft bei takeMVar ack_var.
getCVar :: CVar a -> IO a
getCVar (data_var,ack_var)
= do
val <- takeMVar data_var
putMVar ack_var ()
return val
Holt den Wert aus dem Puffer. Ist kein Wert im Puffer, so wird bei Aufruf von takeMVar data_var der Prozess blockiert.
3.2 Kanal mit
unbegrenzter Kapazität
Die vorgestellte CVar
kann lediglich einen einzigen Wert aufnehmen. Ein gebufferter Kanal hingegen
kann unbegrenzt viele Werte aufnehmen. Realisiert wird das Konzept wieder mit Hilfe von MVars.
Der Kanal selbst wird repräsentiert durchdurch zwei MVars, die sicherstellen, dass Schreib- und Leseoperationen, die den Zustand des Kanals verändern, synchronisiert erfolgen. Sie bezeichnen das Ende der Leseposition und das Ende der Schreibposition.
Die Daten in einem Kanal werden durch den Datentyp Stream repräsentiert, der leer ist oder ein Item aufnehmen kann.
Ein Item wiederum ist ein Paar von Streams, von denen der erste das
Datenelement und der zweite den Rest der Daten enthält.
Abbildung: Ein Kanal mit
unbegrenzter Kapazität
Der resultierende Kanal besteht also abwechselnd aus Streams und Items, die wiederum Daten enthalten oder leer sind. Die Zusammenhänge sind in der obigen Abbildung nocheinmal dargestellt. Die Typdeklarationen lauten wie folgt:
type Channel a = (MVar (Stream a), --Lesen
MVar (Stream a)) --Schreiben
type Stream a = MVar (Item a)
type Item a = Item a (Stream a)
Um einen neuen Kanal zu erzeugen, müssen zwei MVars für das Lese- und Schreibende sowie eine leere MVar für den Stream selbst erzeugt werden, der zunächst leer ist.
newChan :: IO (Channel a)
newChan
= newMVar >>= \read ->
newMVar >>= \write ->
newMVar >>= \hole ->
putMVar read hole >>
putMVar write hole >>
return (read,write)
Um in den Kanal zu schreiben, muss zunächst eine neuer Stream erzeugt werden, die zum neuen Schreibende wird. Anschließend wird ein Item in die alte Schreibposition geschrieben(old_hole).
putChan :: Channel a -> a -> IO ()
putChan (read,write) val
= newMVar >>= \new_hole ->
takeMVar write >>= \write ->
putMVar write new_hole >>
putMVar old_hole (Item val new_hole)
Um Daten aus dem Buffer zu lesen, ist das Vorgehen sehr ähnlich. Dazu wird der Item aus der alten Leseposition geholt und der Wert ausgelesen. Die Leseposition wird anschließend um eine Position vorgerückt. Sind keine Daten im Kanal, so wird der Prozess so lange beim Holen des Items blockiert, bis ein Wert in den Kanal hineingeschrieben wurde.
getChan :: Channel a -> IO a
getChan (read,write)
= takeMVar read >>= \cts ->
takeMVar cts >>= \(Item val new) ->
putMVar read new >>
return val