Betriebssysteme (20) - Prozesssynchronisation II : Semaphor

In dem letzten Beitrag wurden zwei Nachteile der switch-variante genannt. Diese Schwierigkeiten lassen sich vermeiden, wenn man das Konzept des Semaphors verwendet.
Semaphore wurden zur Lösung von Problemen entwickelt, bei denen mehrere Prozesse oder Threads ein Betriebsmittel belegen wollen, von dem insgesamt n Stück zur Verfügung stehen. Dabei kann es sich um n freie Speicherplätze handeln, um n CPUs oder um das Recht, in den kritischen Abschnitt eintreten zu dürfen. Im letzten Fall ist n=1, weil ja zu einem Zeitpunkt immer nur ein Prozess seinen kritischen Abschnitt betreten darf.

Semaphor

Ein Semaphor S kann als Datentyp spezifiziert werden. Der Zustand von S besteht aus der Anzahl freier Betriebsmittel, gespeichert in einer Zählvariablen count, und einer Prozessmenge P.

Falls count != 0 (ungleich null), so ist P leer, ansonsten enthält P alle Prozesse, die sich bisher vergeblich um ein Betriebsmittel bemüht haben und darauf warten, dass wieder eines frei wird.

Auf S sind zwei Operationen definiert, down und up. Wenn ein Prozess ein Betriebsmittel benutzen will, ruft er die Operation down auf.

program down(S);
start
    if S.count > 0
        then S.count := S.count - 1;
        /* aufrufender Prozess kann Betriebsmittel benutzen */
        else
        /* Alle Betriebsmittel belegt */
            start
                füge aufrufenden Prozess in die Menge S.P ein
                blockiere aufrufenden Prozess
            end
end;

Wenn ein Prozess sein Betriebsmittel wieder freigibt, ruft er die Operation up auf

program up(S);
start
    if S.P ist nicht leer
        then /* andere Prozesse warten. S.count ist 0 */
            start
                entferne einen Prozess aus S.P
                mache ihn bereit
            end
    else
        S.count := S.count + 1
end;

Damit lässt sich das Problem vom Beobachter und Berichterstatter (vgl. Beispiel ) folgendermaßen lösen. Zunächst wird eine Semaphorvariable S definiert und ihre Zählvariable count auf 1 gesetzt. Die Variable Zähler erhält den Anfangswert 0.

Process Beobachter;
start
    do
        down(S)
        
        /* Beginn kritischer Abschnitt */
        beobachte Ereignis
        Zähler := Zähler + 1
        /* Ende kritischer Abschnitt */
        
        up(S)
    until false
end;

Process Berichterstatter;
start
    do
        down(S)
        
        /* Beginn kritischer Abschnitt */
        println(Zähler)
        Zähler := 0
        /* Ende kritischer Abschnitt */
        
        up(S)
    until false
end;

Damit der Semaphor korrekt arbeitet, müssen die Operationen down und up in geeigneter Weise implementiert sein. So darf zum Beispiel bei einem Aufruf down(S) nach dem Test der Zählvariablen count kein anderer Prozess down(S) aufrufen, bevor der Wert von count um eins heruntergezählt worden ist. Operationen, die nicht unterbrochen werden dürfen, nennt man atomare Operationen.

Die Semaphor-Operationen down und up zur Realisierung kritischer Abschnitte enthalten selbst kritische Abschnitte! Haben wir also unser Problem nur verlagert? Ja; aber dadurch wird es leichter lösbar. Wenn man die Semaphor-Operationen nämlich im Betriebssystem implementiert, kann man während der Ausführung von down oder up alle Unterbrechungen sperren und damit den gerade beschriebenen Fehler verhindern.

Falls die Semaphorvariable count nur die Werte 0 oder 1 annehmen kann, spricht man von einem binären Semaphor, der meistens dazu verwendet wird, den wechselseitigen Ausschluss (mutual exclusion) von zwei Prozessen sicherzustellen. Allerdings gibt es auch Semaphore, die nicht binär sind. Dazu mehr im nächsten Artikel zur Prozesssynchronisation.

Quelle
https://web.cs.wpi.edu/~cs3013/c07/lectures/Section06-Sync.pdf [letzter Zugriff: 24.11.2019, 16:54]