Bösartige Race Conditions und Data Races

Modernes C++  –  1 Kommentare

In diesem Artikel geht es um bösartige Race Conditions und Data Races. Bösartige Race Conditions sind Race Conditions, die den Bruch von Invarianten eines Programms verursachen, blockierende Threads oder auch Lebenszeitprobleme von Variablen.

Aber zuerst will ich kurz wiederholen, was eine Race Condition ist.

  • Race Condition: eine Konstellation, in dem das Ergebnis einer Operation von der zeitlich verschränkten Ausführung von bestimmten anderen Operationen abhängt.

Mit dieser Definition kann der Artikel schon losgehen. Eine Race Condition kann die Invariante eines Programms brechen.

Bruch von Invarianten

Im letzten Artikel "Race Conditions und Data Races" stellte ich anhand einer Geldüberweisung ein Data Race vor. Es gab in dem Programm eine unkritische Race Condition. Um ehrlich zu sein, es gab auch eine bösartige Race Condition, auf die ich jetzt eingehe.

Die bösartige Race Condition bricht eine wichtige Invariante des Programms. Die Invariante ist, dass die Summe aller Konten immer den gleichen Betrag besitzen soll. Das ist in unserem Fall 200 Euro, da jedes Konto einen initialen Betrag von 100 Euro (1) besitzt. Der Einfachheit nehme ich die Einheit Euro an. Weder will ich durch eine Transaktion zusätzliches Geld erzeugen noch Geld vernichten.

// breakingInvariant.cpp

#include <atomic>
#include <functional>
#include <iostream>
#include <thread>

struct Account{
std::atomic<int> balance{100}; // 1
};

void transferMoney(int amount, Account& from, Account& to){
using namespace std::chrono_literals;
if (from.balance >= amount){
from.balance -= amount;
std::this_thread::sleep_for(1ns); // 2
to.balance += amount;
}
}

void printSum(Account& a1, Account& a2){
std::cout << (a1.balance + a2.balance) << std::endl; // 3
}

int main(){

std::cout << std::endl;

Account acc1;
Account acc2;

std::cout << "Initial sum: ";
printSum(acc1, acc2); // 4

std::thread thr1(transferMoney, 5, std::ref(acc1), std::ref(acc2));
std::thread thr2(transferMoney, 13, std::ref(acc2), std::ref(acc1));
std::cout << "Intermediate sum: ";
std::thread thr3(printSum, std::ref(acc1), std::ref(acc2)); // 5

thr1.join();
thr2.join();
thr3.join();
// 6
std::cout << " acc1.balance: " << acc1.balance << std::endl;
std::cout << " acc2.balance: " << acc2.balance << std::endl;

std::cout << "Final sum: ";
printSum(acc1, acc2); // 8

std::cout << std::endl;

}

Am Anfang beträgt die Summe der Konten 200 Euro. Die Funktion printSum (3) stellt die Summe in dem Aufruf (4) dar. Die Zeile (5) bringt die Invariante zum Vorschein. Dank des kurzen Schlafens von 1ns in Zeile (2) beträgt die Zwischensumme nur 182 Euro. Am Ende passt die Arithmetik wieder. Jedes Konto besitzt den richtigen Betrag (6), und die Gesamtsumme ist 200 Euro (8).

Hier ist die Ausgabe des Programms.

Die bösartige Geschichte geht weiter. Jetzt erzeuge ich ein Deadlock mithilfe einer Bedingungsvariablen ohne Prädikat.

Blockieren mit Race Conditions

Zuerst muss ich klarstellen: Eine Bedingungsvariable sollte zusammen mit einem Prädikat verwendet werden. Die Details dazu finden sich in meinem Artikel "Bedingungsvariablen". Falls kein Prädikat verwendet wird, kann das Programm Opfer eines "spurious wakeup" oder auch "lost wakeup" werden.

Falls man eine Bedingungsvariable ohne ein Prädikat verwendet, kann es passieren, das der benachrichtigende Thread seine Benachrichtigung schickt, bevor der wartende Thread im Wartezustand ist. Daher wartet der wartende Thread für immer, und das Programm verabschiedet sich in den Dornröschenschlaf. Dies Phänomen wird als "lost wakeup" bezeichnet. Hier ist das Programm.

// conditionVariableBlock.cpp

#include <iostream>
#include <condition_variable>
#include <mutex>
#include <thread>

std::mutex mutex_;
std::condition_variable condVar;

bool dataReady;


void waitingForWork(){

std::cout << "Worker: Waiting for work." << std::endl;

std::unique_lock<std::mutex> lck(mutex_);
condVar.wait(lck); // 3
// do the work
std::cout << "Work done." << std::endl;

}

void setDataReady(){

std::cout << "Sender: Data is ready." << std::endl;
condVar.notify_one(); // 1

}

int main(){

std::cout << std::endl;

std::thread t1(setDataReady);
std::thread t2(waitingForWork); // 2

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

std::cout << std::endl;

}

Der erste Aufruf des Programms geht gut. Der zweite Aufruf blockiert, da die Benachrichtigung (1) stattfindet, bevor der Thread t2 (2) im Wartezustand (3) ist.

Selbstverständlich sind Deadlocks und Livelocks weitere Effekte von Race Conditions. Ein Deadlock hängt im Allgemeinen von dem zeitlichen Zusammenspiel von Threads ab und tritt daher gelegentlich auf. Ein Livelock ist einem Deadlock sehr ähnlich. Während aber ein Deadlock blockiert, scheint ein Livelock Fortschritte zu machen. Meine Betonung liegt auf "scheint". Es sei hier an eine Transaktion in einem Transactional Memory System erinnert. Jedes Mal, wenn die Transaktion veröffentlicht werden soll, tritt ein Konflikt zum Anfangszustand ein. Daher wird die Transaktion ordnungsgemäß zurückgesetzt. Hier ist mein Artikel zu "Transactional Memory".

Lebenszeitprobleme von Variablen zu zeigen, ist nicht so anspruchsvoll.

Lebenszeitprobleme von Variablen

Das Rezept für ein Lebenszeitproblem ist ziemlich einfach. Lass den erzeugten Thread im Hintergrund laufen, und du bist schon halb fertig. Damit meine ich, dass der Erzeuger nicht darauf wartet, bis sein Kind seine Arbeit vollbracht hat. In diesem Fall ist äußerste Vorsicht geboten, damit das Kind nicht etwas verwendet, was dem Erzeuger gehört.

// lifetimeIssues.cpp

#include <iostream>
#include <string>
#include <thread>

int main(){

std::cout << "Begin:" << std::endl; // 2

std::string mess{"Child thread"};

std::thread t([&mess]{ std::cout << mess << std::endl;});
t.detach(); // 1

std::cout << "End:" << std::endl; // 3

}

Das war zu einfach. Der Thread t verwendet std::cout und die Variable mess. Beide gehören dem main-Thread. Das Ergebnis ist, dass wir die Ausgabe des Kinder-Threads nicht in der zweiten Ausführung des Programms sehen. Nur "Begin :" (2) und "End:" (3) werden dargestellt.

Ich will es nochmals ganz explizit sagen: Alle Programme des Artikels enthalten bis hierher kein Data Race. Meine Idee war es aber, über Race Conditions und Data Races zu schreiben. Sie sind ähnliche, aber doch unterschiedliche Konzepte.

Es lässt sich auch ein Data Race ohne eine Race Condition erzeugen.

Ein Data Race ohne eine Race Condition

Zuerst will ich wieder kurz die Definiton eines Data Race wiederholen.

  • Data Race: ist eine Konstellation, in der mindestens zwei Threads zu selben Zeit auf eine gemeinsame Variable zugreifen. Zumindest ein Thread versucht, diese zu verändern.
// addMoney.cpp

#include <functional>
#include <iostream>
#include <thread>
#include <vector>

struct Account{
int balance{100}; // 1
};

void addMoney(Account& to, int amount){
to.balance += amount; // 2
}

int main(){

std::cout << std::endl;

Account account;

std::vector<std::thread> vecThreads(100);

// 3
for (auto& thr: vecThreads) thr = std::thread( addMoney,
std::ref(account), 50);

for (auto& thr: vecThreads) thr.join();

// 4
std::cout << "account.balance: " << account.balance << std::endl;

std::cout << std::endl;

}

100 Threads fügen 50 Euro (3) zu demselben Konto (1) hinzu. Sie verwenden die Funktion addMone. Die entscheidende Beobachtung ist es, dass das Schreiben des Kontos ohne Synchronisation stattfindet. Daher ist dies ein Data Race, und wir erhalten kein eindeutiges Ergebnis. Das Programm besitzt undefiniertes Verhalten und der finale Kontostand (4) schwankt zwischen 5000 und 5100 Euro.

Wie geht's weiter?

Ich verfolge häufig in Konferenzen, die sich mit Gleichzeitigkeit und Parallelität beschäftigen, intensive Diskussionen zu den Begriffen nichtblockierend, lock-frei und wait-frei. Daher werde ich mir im nächsten Artikel die drei Begriffe genauer anschauen.