Non-Reentrant Locking in C#

Es ist gut bekannt, dass einen kritischen Codeabschnitt (einfachheitshalber kritische Methode) mit Synchronisierungsobjekten davor beschützt werden muss, dass verschiedene Threads auf ihn nebenläufig zugreifen. Wie genau die Synchronisierung geht, hängt von der Art des Problems ab. Man kann die Aufrufe anstellen, damit sie in der richtige Reihenfolge ablaufen können, oder der kritische Abschnitt kann übersprungen werden, wenn ein Thread ihn schon laufen lässt. In diesem Beitrag wird der zweite Fall untersucht.

Mehrere Threads versuchen, eine kritische Methode auf nicht-rekursive (nach links) und auf rekursive Weise (nach rechts) durchzuführen, ohne blockiert zu werden

Der erste und einfachste Mechanismus basiert auf der Verwendung der Monitor Klasse. Die TryEnter Methode versucht den Monitor zu sperren. Wenn es fehlschlägt, dann kehrt die TryEnter Methode mit false zurück, und wird der kritische Abschnitt nicht betreten. Einfach und elegant, aber es gibt ein Problem damit. Wenn die kritische Methode während ihres Ablaufs nochmals vom gleichen Thread aufgerufen wird, das heißt, die Methode direkt oder indirekt rekursiv ist, entsteht eine Endlosschleife. Daraus ergeben sich zwei Fragen. Wieso würde die kritische Methode rekursiv aufgerufen und genau warum entsteht die Endlosschleife?

private object lockObject = new object();
public void CriticalMethod_Monitor()
{
    bool lockAcquired = false;
    try
    {
        Monitor.TryEnter(lockObject, TimeSpan.Zero, ref lockAcquired);
        if (lockAcquired)
        {
            /*Critical section starts here*/
            Console.WriteLine("In the critical section");
            /* It does not have to be a recursive method. Data changes in the
             * critical section can fire events that invoke (that is, reenter)
             * this method again.
             * Note, that the following call results in an infinite loop!
             */
            CriticalMethod_Monitor();
            /*Critical section ends here*/
        }
    }
    finally
    {
        if (lockAcquired)
        {
            Monitor.Exit(lockObject);
        }
    }
}

Die erste Frage ist einfach zu beantworten. Stellen wir uns das folgende Szenario vor. Ein Ereignisbehandler (Eventhandler) ruft die kritische Methode auf, Änderungen werden durchgeführt und dadurch neue Ereignisse werden ausgelöst. Diese Ereignisse können auf direkte oder indirekte Weise dieselbe Methode nochmal aufrufen (und zwar auf dem gleichen Thread) und so schließt sich der Kreis und entsteht ein indirekt rekursiver Aufruf.

Um die andere Frage zu beantworten, was zur Endlosschleife führt, muss man den Unterschied zwischen eintrittsinvarianten und nicht-eintrittsinvarianten Locks verstehen. Der Monitor ist ein eintrittsinvariantes Synchronisierungsobjekt. Es heißt, dass ein Thread den Monitor mehrmals sperren kann. Also wenn TryEnter true auf einem Thread zurückgibt, gibt sie immer wieder true auf dem selben Thread zurück, bis der Monitor von einem anderen Thread belegt wird. (Man muss darauf aufpassen, dass der Monitor genauso vielmals entsperrt werden muss, wie vielmals er zuvor gesperrt wurde, sonst bleibt er gesperrt.) Aus diesem Grund wird die lockAcquired Variable immer auf true gesetzt, wenn ein Thread den Lock vorherig erfolgreich gesperrt hat, und deshalb gibt es nichts, was die Rekursion aufhalten könnte.

Um die Endlosschleife zu beheben, braucht man einen von Threads unabhängigen Mechanismus, ein Synchronisierungsobjekt, das sich so einstellen lässt, dass ein Thread ihn nur einmal sperren kann. Die Semapahore Klasse steht genau dafür. Der Semaphor ist nicht eintrittsinvariant (non-reentrant), jeder Aufruf von gleichem Thread wird den Semaphor sperren, es sei denn, dass der Semaphor schon belegt ist. Deswegen gibt der zweite WaitOne Aufruf im folgenden Beispiel false zurück und wird der kritische Abschnitt übersprungen. Sollte die CriticalMethod_Semaphore Methode ausgeführt werden, würde der Text “In the critical section” einmal am Bildschirm angezeigt.

Semaphore semaphore = new Semaphore(1, 1);

public void CriticalMethod_Semaphore()
{
    bool isSemaphoreTaken = false;
    try
    {
        isSemaphoreTaken = semaphore.WaitOne(TimeSpan.Zero);
        if (isSemaphoreTaken)
        {
            /*Critical section starts here*/
            Console.WriteLine("In the critical section");
            /* It does not have to be a recursive method. Data changes in the
             * critical section can fire events that invoke (that is, reenter)
             * this method again
             */
            CriticalMethod_Semaphore();
            /*Critical section ends here*/
        }
    }
    finally
    {
        if (isSemaphoreTaken)
        {
            semaphore.Release();
        }
    }
}

Die zweite Umsetzung folgt dem gleichen Prinzip wie die Vorige. Der einzige Unterschied besteht darin, dass der Zugang auf den kritischen Abschnitt statt des Semaphors durch die Interlocked Klasse kontrolliert wird. Aus meiner Ansicht ist diese Lösung viel weniger überschaubar, aber die Interlocked Klasse kann – im Vergleich zum Semaphor – viel effizienter sein.

private int entryCount = 0;

public void CriticalMethod_Interlocked()
{
    int currentEntryCount = 0;

    try
    {
        //If it was 0 set it to 1

        currentEntryCount = Interlocked.CompareExchange(ref entryCount, 1, 0);
        if (currentEntryCount == 0)
        {
            /*Critical section starts here*/
            Console.WriteLine("In the critical section");
            /* It does not have to be a recursive method. Data changes in the
             * critical section can fire events that invoke (that is, reenter)
             * this method again
             */
            CriticalMethod_Interlocked();
            /*Critical section ends here*/
        }
    }
    finally
    {
        if (currentEntryCount == 1)
        {
            Interlocked.Decrement(ref entryCount);
        }
    }
}

Meine Experimente ergeben, dass 20 Threads und 500.000 Aufrufe je Thread laufen mit der Interlocked Klasse in 0,24 sec und in 1,473 sec mit dem Semaphor ab.