Semaphoren in C++20

Inhaltsverzeichnis

Semaphoren bieten sich an, um den gemeinsamen Zugriff auf geteilte Ressourcen zu koordinieren. Zusätzlich lässt sich mit ihnen Ping-Pong spielen.

Eine zählende Semaphore ist eine spezielle Semaphore, die einen Zähler größer Null besitzt. Dieser Zähler wird im Konstruktor initialisiert. Das Anfordern der Semaphore dekrementiert und das ihr Freigeben inkrementiert den Zähler. Wenn ein Thread versucht, die Semaphore anzufordern, falls der Zähler den Wert Null besitzt, wird dieser Thread blockiert, bis ein anderer Thread die Semaphore freigibt, indem er den Zähler inkrementiert.

Wer hat's erfunden?

Der niederländische Informatiker Edsger W. Dijkstra stellte 1965 das Konzept einer Semaphore vor. Eine Semaphore ist eine Datenstruktur mit einer Queue und einem Zähler. Der Zähler wird auf einen Wert größer oder gleich Null initialisiert. Sie unterstützt die zwei Operationen wait und signal. Erstere fordert die Semaphore an und dekrementiert den Zähler. In diesem Fall wird der ausführende Thread blockiert, falls die Semaphore den Wert Null besitzt. signal gibt die Semaphore frei und inkrementiert den Zähler. Blockierte Threads werden zur Queue hinzugefügt, um Starvation zu vermeiden.

Der Begriff Semaphore steht ursprünglich für ein Eisenbahnsignal.

Zählende Semaphoren in C++20

C++20 unterstützt eine std::binary_semaphore, die ein Alias auf eine std::counting_semaphore<1> ist. In diesem Fall ist der maximale Wert für den Zähler 1. Eine std::binary_semaphore kann dazu verwendet werden, einen Lock zu implementieren:

using binary_semaphore = std::counting_semaphore<1>;

Im Gegensatz zu einem std::mutex ist eine std::counting_semaphore nicht an einen Thread gebunden. Das heißt, dass das Anfordern und Freigeben der Semaphore in verschiedenen Threads stattfinden kann. Die folgende Tabelle stellt das Interface einer std::counting_semaphore vor:

Der Aufruf des Konstruktors std::counting_semaphore<10> sem(5) erzeugt die Semaphore sem, die maximal den Wert 10 annehmen kann. Der Zähler besitzt den Wert 5. sem.max() gibt den maximalen Wert für den Zähler zurück.try_aquire_for(relTime) benötigt eine Zeitdauer, die Funktion sem.try_acquire_until(absTime) einen Zeitpunkt. In meinen Artikeln zur Zeitbibliothek lassen sich die Details zu Zeitdauern und Zeitpunkten genauer nachlesen: time. Die drei Aufrufe sem.try_acquire, sem.try_acquire_for und sem.try_acquire_until geben einen Wahrheitswert zurück, der den Erfolg der Operation anzeigt.

Semaphoren werden typischerweise in Sender-Empfänger-Abläufen verwendet. Wird zum Beispiel eine Semaphore auf 0 initialisiert, blockiert der Empfänger-Aufruf sem.acquire(), bis der Sender sem.release() ausführt. Damit wartet der Empfänger auf die Benachrichtigung des Senders. Die einmalige Synchronisation von Threads lässt sich einfach mit Semaphoren umsetzen:

// threadSynchronizationSemaphore.cpp

#include <iostream>
#include <semaphore>
#include <thread>
#include <vector>

std::vector<int> myVec{};

std::counting_semaphore<1> prepareSignal(0);              // (1)

void prepareWork() {

    myVec.insert(myVec.end(), {0, 1, 0, 3});
    std::cout << "Sender: Data prepared."  << '\n';
    prepareSignal.release();                              // (2)
}

void completeWork() {

    std::cout << "Waiter: Waiting for data." << '\n';
    prepareSignal.acquire();                              // (3)
    myVec[2] = 2;
    std::cout << "Waiter: Complete the work." << '\n';
    for (auto i: myVec) std::cout << i << " ";
    std::cout << '\n';
    
}

int main() {

    std::cout << '\n';

    std::thread t1(prepareWork);
    std::thread t2(completeWork);

    t1.join();
    t2.join();

    std::cout << '\n';
  
}

Die std::counting_semaphore prepareSignal (Zeile 1) kann die Werte 0 oder 1 besitzen. Im konkreten Anwendungsfall wird sie auf 0 (Zeile 1) initialisiert. Das heißt, dass der Aufruf prepareSignal.release() den Wert auf 1 (Zeile 2) setzt und den Aufruf prepareSignal.acquire() entblockt (Zeile 3).

Nun möchte ich einen Performanztest mit einem Ping-Pong-Spiel durchführen.

Ein Ping-Pong-Spiel

In meinem letzten Artikel "Performanzvergleich von Bedingungsvariablen und Atomics in C++20" implementierte ich ein Ping-Pong-Spiel. Das war die zentrale Idee des Spiels: Ein Thread führt eine ping- und ein anderer eine pong-Funktion aus. Der Ping-Thread wartet bei dem Spiel auf die Benachrichtigung des Pong-Threads. Der Pong-Thread schickt wiederum die Benachrichtigung zurück. Das Spiel soll nach 1.000.000 Ballwechseln beendet sein. Jedes Spiel führe ich fünfmal aus, um vergleichbare Performanzzahlen zu erhalten. Los geht das Spiel:

// pingPongSemaphore.cpp

#include <iostream>
#include <semaphore>
#include <thread>

std::counting_semaphore<1> signal2Ping(0);       // (1)
std::counting_semaphore<1> signal2Pong(0);       // (2)

std::atomic<int> counter{};
constexpr int countlimit = 1'000'000;

void ping() {
    while(counter <= countlimit) {
        signal2Ping.acquire();                  // (5)
        ++counter;
        signal2Pong.release();
    }
}

void pong() {
    while(counter < countlimit) {
        signal2Pong.acquire();
        signal2Ping.release();                  // (3)
    }
}

int main() {

    auto start = std::chrono::system_clock::now();

    signal2Ping.release();                     // (4)
    std::thread t1(ping);
    std::thread t2(pong);

    t1.join();
    t2.join();

    std::chrono::duration<double> dur = std::chrono::system_clock::now() - start;
    std::cout << "Duration: " << dur.count() << " seconds" << '\n';

}

Das Programm pingPongsemaphore.cpp verwendet zwei Semaphoren: signal2Ping und signal2Pong (1 und 2). Beide können die Werte 0 und 1 annehmen und werden auf 0 initialisiert. Das bedeutet, wenn der Wert des Zählers von signal2Ping 0 ist, dass der Aufruf signal2Ping.release() (3 und 4) den Zähler auf 1 setzt und damit eine Benachrichtigung darstellt. Der Aufruf signal2Ping.acquire() (5) blockiert, bis der Zähler den Wert 1 hat. Die entsprechende Argumentation gilt für die zweite Semaphore signal2Pong.

Im Durchschnitt benötigt die Ausführung des Spiels 0,33 Sekunden.

Gerne möchte ich die Performanzzahlen aus meinem letzten Artikel "Performanzvergleich von Bedingungsvariablen und Atomics in C++20" ins Spiel bringen.

Alle Zahlen

std::condition_variable stellt die langsamste und std::atomic_flag die schnellste Art dar, Threads zu synchronisieren. Die Performanz von std::atomic liegt dazwischen. std::atomic besitzt einen großen Nachteil. Der Standard sichert nicht zu, dass diese lock-frei implementiert sind. std::atomic_flag ist die einzige, garantiert lock-freie atomare Variable. Semaphoren haben mich am meisten beeindruckt, denn sie sind fast so schnell wie std::atomic_flag.

Mein C++20 Buch

Dieser Artikel basiert auf Auszügen meines englischen Buchs zu C++20. Es ist mittlerweile zu 70 Prozent abgeschlossen und auf LeanPub in mehreren digitalen Formaten erhältlich. Natürlich erhältst du automatisch jedes Update des Buchs.

Wie geht's weiter?

Mit Latches und Barriers erhalten wir mehr Koordinationsdatentypen in C++20. In meinem nächsten Artikel schaue ich mir diese genauer an. ()