Racebedingung in C++

1. Was sind Fäden
2. Was ist eine Race-Condition
3. Race-Condition vermeiden
4. Race-Condition mit Mutex vermeiden
5. Race-Condition mit Semaphor vermeiden
6. Abschluss

In diesem Tutorial lernen wir das Konzept einer Race Condition kennen. Zuerst nehmen wir eine Einführung in Threads und diskutieren dann die Race Condition in Threads mit Beispielen.

Schließlich werden wir Lösungen sehen, um die Race Condition zu vermeiden/kontrollieren.

Was sind Fäden

Threads sind leichtgewichtige Prozesse. Prozesse können mehrere Threads haben, die sich viele Ressourcen des Prozesses teilen.

Threads sollen kooperieren; Daher teilen sie Speicher/Variablen mit anderen Ressourcen.

Threads werden verwendet, um gleichzeitige Aufgaben innerhalb eines Prozesses auszuführen. Beispielsweise werden in einem MS-Word-Verarbeitungsprozess mehrere Aufgaben gleichzeitig ausgeführt.

Zu diesen Aufgaben gehören Rechtschreibung, Grammatik, automatisches Speichern, Kennzeichnen von Stichwörtern, Einrücken und Formatieren. Wir können separate Threads verwenden, um diese gleichzeitigen Aufgaben gleichzeitig auszuführen.

Gleichzeitiges Sortieren und Drucken

Hier werden wir ein Codierungsbeispiel besprechen, um die Threads besser zu verstehen. Angenommen, wir müssen viele Werte sortieren und drucken.

Zuerst müssen wir sie komplett aussortieren, bevor wir sie drucken können.

Es gibt jedoch einige Sortiertechniken wie selection sort, die Zahlen so sortiert, dass wir bei jeder Iteration kleinere Elemente am Anfang der Liste erhalten. Daher können wir parallel mit dem Drucken beginnen.

Hier ist der Code:

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

#define SIZE 1000
int x[SIZE];
void init() {
  int i;
  for (i = 0; i < SIZE; i++) x[i] = rand() % 1000;
}
void* print(void* a) {
  int i;
  for (i = 0; i < SIZE; i++) printf("%d ", x[i]);
  printf("\n");
}
void* sort(void* b) {
  int i, j, temp;
  for (i = 0; i < SIZE - 1; i++)
    for (j = SIZE - 1; j >= 1; j--)
      if (x[j] < x[j - 1]) {
        temp = x[j];
        x[j] = x[j - 1];
        x[j - 1] = temp;
      }
}
int main() {
  srand(time(0));
  init();
  pthread_t tSort, tPrint;
  pthread_create(&tSort, NULL, sort, NULL);
  pthread_create(&tPrint, NULL, print, NULL);
  pthread_join(tSort, NULL);
  pthread_join(tPrint, NULL);
  return 0;
}

In diesem Code laufen die Funktionen Sortieren und Drucken parallel; Wenn Sie jedoch die Ausgabe sehen, ist sie nicht korrekt.

Der Grund dafür ist, dass der Sortier-Thread langsamer ist als der Druck-Thread und es keine Synchronisation zwischen ihnen gibt. Daher druckt der Druckthread schnell Werte, die noch nicht sortiert sind; Daher ist die Ausgabe unsortiert.

Ein Multi-Thread-Programm ist anfällig für diese Synchronisierungsprobleme und einige andere Probleme. Als nächstes werden wir ein solches Problem erörtern, das Race Condition genannt wird.

Was ist eine Race-Condition

Eine Racebedingung ist eine unerwünschte Bedingung, die auftreten kann, wenn mehrere Prozesse oder Threads gleichzeitig auf einige gemeinsam genutzte Daten zugreifen.

Der endgültige Wert hängt von dem Prozess/Thread ab, der zuletzt auf die Daten zugreift. Lassen Sie es uns an einem Beispiel erklären.

Angenommen, wir haben zwei Threads, A und B, und eine gemeinsam genutzte Variable x. Beide Threads führen parallel eine Anweisung x++ aus.

Wenn Sie diese Anweisung in einer niedrigen Sprache kritisch prüfen, besteht diese Anweisung aus drei Anweisungen. Die drei Anweisungen lauten:

read x inc x write x

Die erste Anweisung liest die Variable aus dem Speicher in ein Register (innerhalb des Prozessors). Im zweiten Befehl wird eine Variable um 1 erhöht und das Ergebnis in einem Register abgelegt.

Die Variable wird im dritten und letzten Befehl in den Speicher zurückgeschrieben.

Angenommen, zwei Threads führen diese Anweisungen parallel aus. Wir haben keine Ahnung von ihrer Ausführungsreihenfolge; es hängt von verschiedenen Faktoren ab, wie Scheduling-Algorithmus, Zeitscheibe, Priorität der Prozesse und Satz von laufenden/neuen Prozessen usw.

Wir können mehrere mögliche Sequenzen haben, die diese Anweisungen ausführen, und jedes Mal kann eine andere Sequenz auftreten. Beispielsweise kann Thread A die ersten beiden Anweisungen ausführen, und das Betriebssystem wechselt den Kontext.

Angenommen, der Wert der Variablen ist 5, Thread A hat 5 gelesen und um 1 erhöht, also ist der Wert jetzt 6 (aber innerhalb des Registers). Wenn der Kontext wechselt und Thread B seine Ausführung beginnt, liest er auch denselben Wert 5.

Thread B erhöht den Wert um 1. Der Wert wird zu 6.

Thread B vervollständigt die letzte Anweisung und schreibt einen 6-Wert in den Speicher.

Der Kontext wechselt erneut und die Kontrolle kommt schließlich zu Thread A; Jetzt führt Thread A die letzte Anweisung aus, schreiben Sie x.

Denken Sie daran, dass Thread A den Wert 5 gelesen hat und ihn um 1 erhöht. Thread A schreibt auch 6 in den Speicher.

Als Ergebnis ist der Wert 6 statt 7, da zwei Threads die Inkrementoperation ausgeführt haben und der Wert 7 sein sollte. Daher ist das Ergebnis aufgrund eines unerwarteten Kontextwechsels falsch.

Erzeuger-Verbraucher-Problem

Sehen wir uns das folgende Codierungsbeispiel an, bevor wir das Producer-Consumer-Problem diskutieren.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) count++;
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) count--;
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  printf("Count = %d\n", count);
  return 0;
}

Dieser Code demonstriert das klassische Betriebssystemproblem, das als Producer-Consumer-Problem bezeichnet wird. Dieser Code hat eine globale (gemeinsame) Variable count, initialisiert mit 0.

Die Funktion producer erhöht den Zählerstand um 1 und die Funktion consumer verringert den Zählerstand um 1.

Beide Funktionen werden jedoch von zwei verschiedenen Threads ausgeführt, in denen jederzeit ein Kontextwechsel stattfinden kann. Sie können dies leicht erfahren, indem Sie den Code ausführen.

Wenn es keine Race-Condition gibt, sollte das Ergebnis 0 sein, da beide Funktionen gleich oft inkrementieren und dekrementieren. Die Einheit Inkrement und Dekrement bedeutet, dass der Wert des count am Ende Null sein soll.

Wenn Sie diesen Code ausführen, werden Sie jedoch feststellen, dass der Wert nicht Null ist. Vielmehr werden in jeder Iteration unterschiedliche Werte auftreten, was deutlich zeigt, dass die Planung unvorhersehbar ist.

Einige praktische Producer-Consumer-Beispiele

Das oben diskutierte Inkrementbeispiel der zwei Threads ist kein hypothetisches Problem; Beim Arbeiten mit Multithreading gibt es viele solcher praktischen Szenarien.

Beispielsweise hat ein Kunde im Bankensystem zwei Möglichkeiten, einen Betrag abzuheben. Einer besteht darin, der Bank einen Scheck vorzulegen, während gleichzeitig jemand den Betrag mit der Bankautomatenkarte des Kunden am Geldautomaten abheben kann.

Ebenso ist es möglich, dass zwei oder mehr Lehrer zufällig die Noten derselben Schüler aktualisieren/posten, was wiederum die Gesamtnoten der Schüler erhöht/verringert. Zwei oder mehr Unternehmen können gleichzeitig das Wochen-, Monats- oder Jahresabonnement des Kunden abziehen.

Die Rennbedingung kann zu falschen Ergebnissen führen, was nicht erschwinglich ist. Sollten wir daher ankündigen, dass die Anwendbarkeit von Multi-Threading aufgrund von Race-Condition-Problemen in vielen Szenarien nicht praktikabel ist?

Nein, wir haben die Lösung, um die Race Condition zu vermeiden/kontrollieren.

Race-Condition vermeiden

Wir haben sowohl Hardware- als auch Softwarelösungen für Rennbedingungen. Die Hardwarelösung besteht darin, verwandte atomare Anweisungen als Teil des CPU-Anweisungssatzes bereitzustellen (z. B. CMPXCHG in der x86-Architektur).

Die Softwarelösung verwendet Mutex oder Semaphoren, um den Eintritt des Prozesses in die kritischen Abschnitte zu regulieren.

Atomare Operation

Der Hersteller kann atomare Operationen in der Hardware implementieren. Nach der Implementierung einer atomaren Operation in der Hardware wird eine solche Anweisung ihre Ausführung ohne Kontextumschaltung abschließen. Mit anderen Worten, die Prozess-/Thread-Ausführung sollte nicht in Teile aufgeteilt werden.

Diese Lösung ist jedoch für Hersteller gedacht und kann von normalen Benutzern nicht implementiert werden.

Gegenseitiger Ausschluss

Ein gegenseitiger Ausschluss bedeutet, dass, wenn ein Prozess/Thread auf eine gemeinsam genutzte Variable zugreift, kein anderer Prozess/Thread auf die gemeinsam genutzte Variable zugreifen darf, die bereits von einem anderen Prozess/Thread gehalten wird.

Der gegenseitige Ausschluss kann mithilfe eines Mutex (Sperre) oder eines Semaphors implementiert werden. Sie können auf klicken, um über Mutex vs. Semaphore zu lesen, um die Konzepte zu verdeutlichen.

Race-Condition mit Mutex vermeiden

Mutex ist ein Konzept einer speziellen Sperre. Diese Sperre wird von Threads geteilt; Wenn jedoch mehrere Threads den Mutex sperren möchten, wird nur ein (erster) Thread erfolgreich sperren und in den kritischen Abschnitt eintreten.

Die verbleibenden Threads, die versuchen, den Mutex zu sperren, werden blockiert, bis der erste Thread den kritischen Abschnitt verlässt und den Mutex entsperrt.

Ein entsperrter Mutex kann jederzeit von einem Thread gesperrt werden. Beim Entsperren des Mutex kann jeder der blockierenden Threads die Möglichkeit erhalten, den Mutex zu sperren und in den kritischen Abschnitt einzutreten.

Es gibt kein Konzept der Warteschlange in Mutex. Jeder der blockierenden/wartenden Threads kann die Chance bekommen, den Mutex zu bekommen und ihn zu sperren.

Es ist eine sehr einfache Lösung und äußerst nützlich, wenn wir zwei Threads in Race-Bedingungen oder mehrere Threads in Race-Bedingungen haben und es kein Problem mit Turn/Queue gibt.

Lassen Sie uns die Lösung anhand des folgenden C-Beispiels realisieren, das eine Mutex-Sperre mit der Linux-Bibliothek pthread implementiert.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;
pthread_mutex_t lock;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    pthread_mutex_lock(&lock);
    count++;
    pthread_mutex_unlock(&lock);
  }
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    pthread_mutex_lock(&lock);
    count--;
    pthread_mutex_unlock(&lock);
  }
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  pthread_mutex_init(&lock, NULL);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  pthread_mutex_destroy(&lock);
  printf("Count = %d\n", count);
  return 0;
}

Sie können diesen Code mehrmals ausführen. Jedes Mal wird der Wert der Zählung 0 ausgegeben.

Der Code hat eine gemeinsam genutzte Variablensperre eines speziellen Typs, pthread_mutex_t. Producer- und Consumer-Funktionen werden gesperrt, bevor die kritischen Abschnittsanweisungen count++ und count-- ausgeführt werden.

Auch hier geben beide Mutex frei, indem sie die Unlock-Funktion nach dem Ende ihres kritischen Abschnitts aufrufen.

In der Funktion main initialisieren wir Mutex und zerstören Mutex nach der Verwendung von Mutex.

Race-Condition mit Semaphor vermeiden

Semaphore ist eine vom Betriebssystem bereitgestellte Lösung. Semaphore ist eine Lösung für die Thread-Synchronisation.

Wir möchten möglicherweise eine bestimmte Reihenfolge der Ausführung von Anweisungen; Wir können es jedoch verwenden, um Rennbedingungen zu vermeiden, aber es ist keine exakte Lösung; später werden wir diskutieren, warum.

Hier vermeiden wir das lange und detaillierte Thema der Synchronisation und nähern uns der Verwendung von Semaphoren, um Race-Conditions zu vermeiden. Die Verwendung eines Semaphors stoppt den Thread an einem bestimmten Punkt und wartet auf ein Signal von einem anderen Thread.

Wir initialisieren die Semaphore mit Null und rufen die Wait-Funktion auf, verringern die Semaphore um 1 und gehen in einen Ruhezustand.

Später wird ein anderer Thread die Signaloperation aufrufen, das Semaphor um 1 erhöhen und einen schlafenden Thread in der Warteschlange aufwecken.

Unter Linux ist die Semaphore in der Bibliothek semaphore.h verfügbar. Wir haben Wait- und Post-Funktionen für die Wait- und Signal-Operationen.

Siehe Code:

#include <pthread.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>

int count = 0;
sem_t semaphore1, semaphore2;

void* producer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    count++;
    sem_post(&semaphore1);
    sem_wait(&semaphore2);
  }
}
void* consumer(void* arg) {
  for (int i = 0; i < 50000; i++) {
    sem_wait(&semaphore1);
    count--;
    sem_post(&semaphore2);
  }
}
int main() {
  pthread_t tid1, tid2;
  printf("Count = %d\n", count);
  sem_init(&semaphore1, 0, 0);
  sem_init(&semaphore1, 0, 0);
  pthread_create(&tid1, NULL, producer, NULL);
  pthread_create(&tid2, NULL, consumer, NULL);
  pthread_join(tid1, NULL);
  pthread_join(tid2, NULL);
  sem_destroy(&semaphore1);
  sem_destroy(&semaphore2);
  printf("Count = %d\n", count);
  return 0;
}

Auch hier können Sie diesen Code ausführen und den genauen/korrekten Wert einer gemeinsam genutzten Variablen abrufen. Die Implementierung ähnelt einem Mutex; Ein wesentlicher Unterschied ist jedoch der Initialisierungsschritt.

Es gibt drei Parameter in der Initialisierungsfunktion. Die erste ist die Semaphor-Variable.

Die zweite ist entweder 0 oder 1. Hier bedeutet 0, dass das Semaphor von Threads desselben Prozesses gemeinsam genutzt wird, während 1 bedeutet, dass das Semaphor von Threads verschiedener Prozesse gemeinsam genutzt wird.

Der dritte Parameter ist der Wert des Semaphors; Wenn Sie möchten, dass mehrere Threads (aber auf eine bestimmte Anzahl begrenzt) gemeinsam in den kritischen Abschnitt eintreten können, können Sie den Semaphorwert mit der Anzahl initialisieren.

Der zweite Unterschied in dieser Implementierung besteht darin, dass wir zwei Semaphoren verwenden, während wir im Fall des Mutex nur eine Sperre verwendet haben.

Der Mutex-Code setzt die Sperre vor der Verwendung einer gemeinsam genutzten Variablen und gibt die Sperre nach der Verwendung einer gemeinsam genutzten Variablen frei. Wann immer ein Kunde ein Schließfach in der Umkleidekabine der Bank bedient, gibt das Personal dem Kunden einen Schlüssel, um das Schließfach zu verschließen, bevor es das Schließfach öffnet, und öffnet den Umkleideraum, nachdem das Schließfach abgeschlossen ist.

Bei Semaphore verwenden wir jedoch zwei Semaphore; beide werden mit 0 initialisiert, was bedeutet, dass das Warten des aufrufenden Threads blockiert wird, bis ein anderer Thread ein Signal gibt. Hier wartet der Konsument auf die vom Producer-Thread signalisierte Semaphore 1, nachdem er den Count erhöht hat.

Gleichzeitig wartet der Producer-Thread auf die Semaphore 2, die der Consumer-Thread nach dem Dekrementieren des Zählers signalisieren soll.

Auf diese Weise erhöhen und verringern der Produzent und der Konsument die Zählung nacheinander, was eine Synchronisierung ist. Mit Semaphor halten wir die Zählung korrekt; wir schränken jedoch die Threads so ein, dass sie nacheinander ausgeführt werden.

Im Fall von Mutex können beide Threads in beliebiger Reihenfolge ausgeführt werden, ohne den Wert der gemeinsam genutzten Variablen count zu beeinträchtigen.

Abschluss

Die Threads sind sehr nützlich, um Codes/Funktionen parallel auszuführen; Es gibt jedoch einige Probleme mit Threads, z. B. eine Racebedingung. Die Bedingung kann zu unerwarteten Ergebnissen führen.

Glücklicherweise können wir Mutex-Sperren und Semaphoren verwenden, um Race-Conditions zu vermeiden. Der beste und richtige Weg, um mit Rennbedingungen umzugehen, ist ein Mutex.