Semaphore Implementierung

Question

Ich habe mich gefragt, ob es eine Möglichkeit gibt, Semaphore in C++ (oder C#) zu implementieren, und ob es Bibliotheken gibt, die dabei helfen würden. Ich habe versucht, OpenMP zu verwenden, aber ich hatte keine Möglichkeit, Threads tatsächlich zu blockieren, stattdessen musste ich auf sie warten, was zu Deadlocks führte, wenn ich nicht genügend Threads hatte. Also zunächst suche ich nach einer Bibliothek, die es mir ermöglichen würde, meine Threads zu blockieren/spawnen/killen.
Zum Zweiten, gibt es bereits Bibliotheken, die Semaphoren implementieren?
Und schließlich, als mir die Bedeutung von Semaphoren erklärt wurde, fand ich es sehr nützlich (vielleicht liege ich falsch?), aber ich sehe nicht viele Bibliotheken (wenn überhaupt), die sie implementieren. Ich kenne OpenMP, habe Intel's TBB durchsucht, Threads in C# angeschaut. Aber in keinem dieser Fälle sehe ich explizit Semaphoren. Sind Semaphoren also nicht so praktisch, wie ich denke? Oder ist es schwer, sie zu implementieren? Oder bin ich einfach nicht informiert?
P.S.
Können Semaphoren plattformübergreifend implementiert werden? Da sie wahrscheinlich mit dem Betriebssystem zusammenhängen.

Answer 1

Gibt es bereits Bibliotheken, die dies implementieren?
Für C++ gibt es mehrere Multithreading-Bibliotheken, die Semaphore-Implementierungen bereitstellen:

• Posix
• Poco Thread
• Tiny Threads

Sie können auch Semaphore mit Boost implementieren. Schauen Sie sich dies an.

Answer 2

Erster Rat: Verwenden Sie den Boost. Die ganze harte Arbeit wurde erledigt.

Wenn Sie sehen möchten, wie es implementiert ist, sollte es so aussehen (obwohl dies nur eine grobe Skizze ist, bin ich sicher, dass es durch einige Recherchen optimiert werden kann). Grundsätzlich wird ein Semaphor aus drei Dingen erstellt:

• Eine Zählung
• Eine Bedingungsvariable (die das Anhalten ermöglicht)
• Ein Mutex, der die Exklusivität zum Ändern der Zählung und zum Warten auf die Bedingung bietet.

Hier ist die einfache Version:

#include 

// Benötigen eine ausnahmesichere Sperrklasse.
struct MutexLocker
{
    MutexLocker(pthread_mutex_t& m) :mutex(m)
    { if (pthread_mutex_lock(&mutex) != 0)      {throw int(1); }}
    ~MutexLocker()
    { if (pthread_mutex_unlock(&mutex) != 0)    {throw int(1); }}
    private:
        pthread_mutex_t&    mutex;
};

class Semaphore
{
    public:
        Semaphore(int initCount = 0)
            : count(initCount)
            , waitCount(0)
        {
            if (pthread_mutex_init(&mutex, NULL) != 0)
            {   throw int(1);
            }
            if (pthread_cond_init(&cond, NULL) != 0)
            {   pthread_mutex_destroy(&mutex);
                throw int(2);
            }
        }

        void wait()
        {
            MutexLocker locker(mutex);

            while(count == 0)
            {
                ++waitCount;
                if (pthread_cond_wait(&cond, &mutex) != 0)
                {   throw int(2);
                }

                // Ein Aufruf von pthread_cond_wait() entriegelt den Mutex und setzt den Thread aus.
                // Der Thread wird nicht durch Busy-Warten aufgehalten, sondern ausgesetzt.
                //
                // Wenn eine Bedingungsvariable apthread_cond_signal() erhält, wird ein zufälliger Thread wieder aktiviert.
                // Er wird jedoch nicht aus dem Aufruf von wait freigegeben, bis der Mutex vom Thread wieder erworben werden kann.
                //
                // Daher kommen wir hier nur an, nachdem der Mutex gesperrt wurde.
                //
                // Sie müssen eine While-Schleife oben verwenden, aufgrund dieser potenziellen Situation.
                //      Thread A:  Ausgesetzt, wartet auf Bedingungsvariable.
                //      Thread B:  Arbeitet an anderer Stelle.
                //      Thread C:  ruft unten signal() auf (inkrementiert Zählung auf 1)
                //                 Dies führt dazu, dass A aufgeweckt wird, aber es kann nicht aufhören, pthread_cond_wait() zu verlassen,
                //                 bis es den Mutex mit einer Sperre benötigt. Während es das versucht,
                //                 Thread B endet, was es tat, und ruft wait() auf.
                //                 Thread C hat die Zählung auf 1 erhöht, also suspendiert Thread B nicht, sondern dekrementiert die Zählung auf Null und verlässt.
                //                 Thread B übernimmt jetzt den Mutex, aber die Zählung wurde auf Null dekrementiert,
                //                 sodass es sofort erneut an der Bedingungsvariable ausgesetzt werden muss.

                // Beachten Sie, dass ein Thread nicht aus wait freigegeben wird, bis
                // er ein Signal erhält und die Mutex-Sperre wiederhergestellt werden kann.

                --waitCount;
            }

            --count;
        }

        void signal()
        {

            // Sie könnten diesen Teil mit interlocked increment optimieren.
            MutexLocker locker(mutex);
            ++count;

            // Dieser Kommentar basiert auf der Verwendung von `interlocked increment` anstelle von Mutex.
            //
            // Da dieser Teil nichts ändert, benötigen Sie eigentlich keine Sperre.
            // Möglicherweise lassen Sie mehr Threads frei als benötigt (da Sie keine Exklusivität beim Lesen von waitCount haben), aber das ist egal, da die
            // wait()-Methode das tut und alle zusätzlichen geweckten Threads wieder in den Schlaf versetzt werden.

            // Wenn noch wartende Threads vorhanden sind, lassen Sie sie raus.
            if (waitCount > 0)
            {   if  (pthread_cond_signal(&cond) != 0)
                {   throw int(2);
                }
            }
        }
    private:
        unsigned int        count;
        unsigned int        waitCount;
        pthread_mutex_t     mutex;
        pthread_cond_t      cond;
};

Answer 3

In .NET gibt es eine Implementierung innerhalb der BCL: System.Threading.Semaphore.

Für nativen Code unter Windows, schauen Sie sich die CreateSemaphore Funktion an. Wenn Sie Linux als Zielplattform haben, können Sie eine Semaphor-Implementierung der Technischen Universität Wien hier finden (die ich bereits verwendet habe und funktioniert).

Answer 4

In C++, für die Möglichkeit, Threads zu blockieren, würde ich Ihnen empfehlen, statt Semaphoren Bedingungsvariablen zu verwenden. In C#, könnten Monitore geeigneter sein.

Sogar für einen eher einfachen Fall des Producer-Consumer-Problem ist eine semaphorenbasierte Lösung schwieriger korrekt auszuführen: Wenn Semaphore-Inkremente und -Dekremente in falscher Reihenfolge durchgeführt werden, können Probleme auftreten. Im Gegensatz dazu hätte eine lösung basierend auf Bedingungsvariablen keine solchen Probleme: Bedingungsvariablen werden mit einem Sperre (Mutex) verwendet und die richtige Reihenfolge der Operationen wird automatisch durchgesetzt; so hat ein Thread nach dem Aufwachen bereits die Sperre erworben.

Siehe auch meine Antwort zu Wann soll ich Semaphoren verwenden?, wo ich ein weiteres Beispiel dafür gebe, dass Bedingungsvariablen meiner Meinung nach für ein Problem, das oft mit Semaphoren gelöst wird, geeigneter sind.

Und um eine weitere Ihrer Fragen zu beantworten, denke ich, dass die höhere Anfälligkeit für fehlerhafte Verwendung und die höhere Komplexität der Lösungen (im Vergleich zu Alternativen) der Grund dafür sind, warum einige Threading-Pakete keine Semaphoren bereitstellen. Für TBB kann ich das mit Sicherheit sagen. Auch Unterstützung für Threads in C++11 (entwickelt nach Boost.Thread) enthält diese nicht; siehe Antwort von Anthony Williams warum.