4. Scheduling

4.1 Grundideen

Mitunter ist es sinnvoll, partielle Kontrolle über das Scheduling zu besitzen um somit als Programmierer direkten Einfluss auf den Prozessablauf nehmen zu können. Um dieses Ziel zu erreichen, ist das Vorgehen, einen blockierten Prozess durch eine leere MVar zu repräsentieren. Das Scheduling kann dann durch Schreiben in die MVar gesteuert werden.

Realisiert werden kann z.B. die Kontrolle von kritischen Abschnitten, die stets nur von einer definierten Anzahl von Prozessen betreten werden dürfen, mit Hilfe einer quantitativen Semaphore:

type QSem = MVar (Int, [MVar ()])
newQSem    :: Int -> IO QSem
waitQSem   :: QSem -> IO ()
signalQSem :: QSem -> IO ()

Eine QSem beeinhaltet einen Integer-Wert, der zu Beginn auf die entsprechende Kapazität gesetzt ist. Wird die Kapazität auf 1 gesetzt, so kann damit z.B. eine binäre Semaphore simuliert werden, durch die z.B. die exklusive Verfügbarkeit von Betriebsmitteln gesichert werden kann. waitQSem dekrementiert den Wert der QSem und blockiert, wenn der Wert bereits 0 ist. signalQSem erhöht diesen Wert und deblockiert evtl. wartende Prozesse, wenn der Wert der QSem 0 ist.

Abbildung: Flussdiagramm Zusammenhang der waitQSem- und signalQSem-Operation

4.2 Implementierung

Eine QSem ist eine MVar, die ein Paar bestehend aus einem Integer und einer Liste von MVars beeinhaltet. Im Integer wird die Kapazität der quantitativen Semaphore angegeben. Im MVar-Feld wird pro MVar exakt ein Prozess blockiert, für den Fall, dass überhaupt blockiert wird.

Wenn waitQSem ausgeführt wird und der Wert des Integers ist 0, wird eine neue MVar erzeugt, zur Liste hinzugefügt und das resultierende Paar in die MVar der QSem gepackt:

waitQSem sem
  = takeMVar sem >>= \(avail,blkd) -> 
  if avail >  0 then
	putMVar (avail-1, [])   >>
  else
	newMVar                 >>=\block ->
	putMVar (0, block:blkd) >>
	takeMVar block          -- hier blockiert der laufende Prozess

signalQSem deblockiert blockierte Prozesse wenn vorhanden und inkrementiert der Zähler wenn nicht:

signalQSem sem
  = takeMVar sem >>=\(avail,blkd) -> 
    case blkd of 
	[]                    -> putMVar (avail+1, []) --es gab keinen wartenden Prozess
	[blocked:blockedTail] -> putMVar (0, blockedTail) >> 
	     putMVar blocked () --in MVar schreiben, so dass Prozess deblockiert wird

Diese Variante ist beliebig erweiterbar bzw. den Anforderungen entsprechend anzupassen. Es ist beispielsweise für bestimmte Anwendungsfälle denkbar, eine Variante zu implementieren, in der der Zähler nicht nur um 1 sondern um eine beliebig hohe Anzahl inkrementiert und dekrementiert werden kann. Die Implementierung soll jedoch hier nicht weiter besprochen werden.

4.3 Priorität

Concurrent Haskell bietet von sich aus keine prioritätsgesteuerten Prozessauswahlstrategien an. Sind mehrere Prozesse an einer MVar blockiert, ist nicht weiter spezifieziert, welcher der Prozesse fortgeführt wird, wenn ein Wert in die MVar geschrieben wird.

Um prioritätsgesteuerte Strategien einzuführen, müssen diese selbst implementiert werden. Der Ansatz ist sehr ähnlich zu dem der quantitativen Semaphore. Es muss eine Datenstruktur geschaffen werden, die eine Liste der blockierten Prozesse (über MVars) gepaart mit ihren Prioritäten beeinhaltet. Aus der Liste der blockierten Prozesse ist dann jeweils immer der nächstwichtigste als nächstes fortzuführen.

Weiter Zurück Inhalt