kramann.info
© Guido Kramann

Login: Passwort:










kramann.info
© Guido Kramann

Login: Passwort:




Implementierung und Anwendung von Semaphoren

  • In obigem Beispiel wurden vier boolsche Variablen eingeführt, um die Prozesse aufeinander abzustimmen.
  • Damit liegt der Kontrollmechnismus außerhalb der Thread-Prozesse in einem Extrateil, hier das Hauptprogramm.
  • Die Prozesse schauen in diesen Extrateil, um festzustellen, ob sie eine bestimmte Operation ausführen dürfen oder nicht.
  • Und außerdem können sie andere Prozesse blockieren.
  • Auch unter einer nach ihrem Erfinder Edsger W. Dijkstra so benannten Semaphore muß man sich ein Objekt vorstellen, das außerhalb der zu synchronisierenden Prozesse liegt, auf das aber alle diese Prozesse über spezielle Operationen zugreifen können.
  • Ein Semaphoren-Objekt enthält als Datenstruktur eine Zählvariable und eine Warteschlange, in der Prozesse, die geblockt wurden vermerkt werden können, um sie nach einem Entsperren automatisch starten zu können.
  • Ein Prozeß, der prüfen will, ob er seine Aktion ausführen darf (z.B. Prozeß A will schreiben), dekrementiert den Zähler der Semaphore und führt den Prozeß aus, falls danach der Zähler größer oder gleich Null ist.
  • Ist der Zähler des Semaphoren-Objektes nach dem Dekrementieren durch den anfragenden Prozeß kleiner als Null, so wird der Prozeß nicht fortgesetzt, sondern in die Warteschlange eingereiht.
  • Erst wenn ein anderer Prozeß den Zähler inkrementiert, weil er einen Vorgang abgeschlossen hat (z.B. C hat bei A gelesen), wird der älteste unterbrochene Prozeß in der Warteschlange fortgesetzt.
  • Beschränkt auf Prozeß C (lesen) und A (schreiben) entsprechend obigem Beispiel, würde die Synchronisation beider Prozesse mit Hilfe einer Semaphore folgendermaßen aussehen:
Verwendung eines Semaphor-Objektes

Bild 0-1: Verwendung eines Semaphor-Objektes

  • An dem Beispiel wird deutlich, dass die Verwendung eines Semaphor-Objektes nicht zu dem gleichen zeitlichen Verhalten führt, wie in dem vorangegangenen Beispiel, denn bei einer erfolglosen Anfrage eines Prozesses bei dieser, wird der Prozeß durch die Semaphore angehalten.
  • Er wird erst fortgesetzt, wenn ein anderer auch mit der Semaphore verbundener Prozeß beendet wird und auch nur dann wenn, vor ihm nicht weitere Prozesse in der Warteschlange stehen.
  • In unserem Fall würde das heißen, dass der betroffene Thread, oder Mikrocontroller auch keine anderen Berechnungen weiter durchführen kann, wie Sensordaten skalieren oder PWM-Signale berechnen.
  • Klassischerweise wird die Operation, die die Semaphor dekrementiert als P-Operation bezeichnet, eine klare Bezeichnung wäre z.B. anfordern.
  • Die Operation, die die Semaphor inkrementiert wird als V-Operation bezeichnet, eine klare Bezeichnung wäre z.B. freigeben.
  • Neben der P und der V-Operation gint es noch die Initialisierungsfunktion.
  • Tatsächlich bietet Java auch eine Standard-Klasse "Semaphore" an.
  • Doch zur Veranschaulichung wird diese hier selber entwickelt.
  • Die "Warteschlange" muß hier nur ein einziges Element aufnehmen können.
  • Da die Semaphore einen Prozeß, der nicht weiterlaufen darf anhalten und später wieder fortführen können muß, wird in der Warteschlange eine Referenz auf den anfragenden Prozeß gespeichert.
public class Semaphore
{
    private int zaehler = 0;
    private Thread warteschlange = null;
    public void init(int i)
    {
        zaehler = i;
        warteschlange = null;
    }
    public void anfordern(Thread thread)
    {
        zaehler--;
        if(zaehler<0)
        {
            warteschlange = thread;
            try
            {
              warteschlange.suspend();
            }
            catch(Exception e)
            {
            }
        }
    }
    public void freigeben()
    {
        zaehler++;
//        if(warteschlange!=null)
        if(zaehler<=0)
            warteschlange.resume(); 
    }
}

Code 0-1: Semaphore.java in Projekt 003_semaphore

public class SchreibenA extends Thread
{
    public boolean einser = false;
    public void run()
    {
        while(true)
        {
            Hauptprogramm.semaphore.anfordern((Thread)this);
            System.out.println("A schreibt.");
            for(int i=0;i<30;i++)
            {
                if(einser)
                    Hauptprogramm.arrA[i]=1;
                else
                    Hauptprogramm.arrA[i]=0;
                Hauptprogramm.pausieren(20);
            }
            System.out.println("A fertig.");
            Hauptprogramm.semaphore.freigeben();
            //Erledige andere Aufgaben:
            Hauptprogramm.pausieren(50);
            einser = !einser;
        }
    }
}

Code 0-2: SchreibenA.java in Projekt 003_semaphore

public class LesenC extends Thread
{
    public void run()
    {
        while(true)
        {
            Hauptprogramm.semaphore.anfordern((Thread)this);
            System.out.println("C  liest nun arrA aus:");
            for(int i=0;i<30;i++)
            {
                System.out.print(Hauptprogramm.arrA[i]);
                Hauptprogramm.pausieren(100);
            }
            System.out.println();
            Hauptprogramm.semaphore.freigeben();
            //Erledige andere Aufgaben:
            Hauptprogramm.pausieren(200);
        }
    }
}

Code 0-3: LesenC.java in Projekt 003_semaphore

public class Hauptprogramm
{
    public static Semaphore semaphore = new Semaphore();
    public static int[] arrA={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    public static int[] arrB={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    public static void pausieren(long ms)
    {
        try
        {
            Thread.sleep(ms);
        }
        catch(Exception e)
        {
        }
    }
    public static void main(String[] args)
    {
        semaphore.init(1);
        SchreibenA schreibenA = new SchreibenA();
        LesenC lesenC = new LesenC();
        schreibenA.start();
        lesenC.start();
        pausieren(20000);
        while(lesenC==Thread.currentThread());        
        lesenC.stop();
        while(schreibenA==Thread.currentThread());        
        schreibenA.stop();
    }
}

Code 0-4: Hauptprogramm.java in Projekt 003_semaphore

A schreibt.
A fertig.
C  liest nun arrA aus:
000000000000000000000000000000
A schreibt.
A fertig.
C  liest nun arrA aus:
111111111111111111111111111111
A schreibt.
A fertig.
C  liest nun arrA aus:
000000000000000000000000000000
A schreibt.
A fertig.
C  liest nun arrA aus:
111111111111111111111111111111
A schreibt.
A fertig.
C  liest nun arrA aus:
000000000000000000000000000000

Code 0-5: Konsolenausgabe

  • Nun wird also dafür gesorgt, dass erste der eine Prozeß durchgelaufen ist, bevor der jeweils andere gestartet werden kann.
  • Der Fall, dass eine Anzahl an Prozessen größer als eins gleichzeitig eine bestimmte Operation ausführen können, kann dadurch abgedeckt werden, dass die Semaphore mit einem Zählerstand größer als eins initialisiert wird.
Übung
  • Erweitern Sie obiges Semaphoren-Beispiel so, dass das Problem der Laufkatze realisiert wird.
  • Wandeln Sie erst obiges Semaphoren-Beispiel so ab, dass die Java-Standard-Klasse Semaphor benutzt wird und übertragen Sie dies dann auch auf die Umsetzung des Laufkatzenproblems.
  • Erweitern Sie die Semaphoren-Warteschlange auf eine mögliche Länge von zwei Elementen.
  • Implementieren Sie dann drei Prozesse (Nachtwächter), von denen immer zwei gleichzeitig schlafen gehen können.
Aufgaben
  • Setzen Sie das Semaphoren-Beispeil im RTAIlab-Tutorial auf Seite 22-24 (Kapitel 4.2) um und versuchen es zu verstehen.
  • Gehen Sie zuhause die Java-Beispiele durch und erweitern dann die Semaphoren-Warteschlange auf eine mögliche Länge von zwei Elementen.
  • Implementieren Sie dann drei Prozesse (Nachtwächter), von denen immer zwei gleichzeitig schlafen gehen können.