Risiken von Multicore-Software Data-Races sind niemals harmlos

Multicore-Prozessoren werden immer beliebter. Doch ihre effiziente Programmierung gestaltet sich schwieriger als bei ihren Pendants mit nur einem Rechenkern, denn bei ihnen vollkommen neue Arten von Fehlern ins Spiel kommen, und selbst in harmlos erscheinendem Code können sich knifflige Multithreading-Bugs verbergen, zum Beispiel »Data Races«. Derartige Nebenläufigkeitsfehler schleichen sich leicht ein, sind mit traditionellen Testverfahren sehr schwierig zu finden und können sich teils durch recht rätselhafte Symptome äußern. Was sind die Ursachen und Risiken von Nebenläufigkeitsfehlern? Wie gelangen solche Fehler in den Code? Wie lassen sich derartige Defekte automatisch finden und eliminieren?

Hersteller von Mikroprozessoren stoßen hinsichtlich der Performance-Gewinne, die sich durch weitere Miniaturisierung und Integration realisieren lassen, zunehmend an ihre Grenzen. Multicore-Prozessoren sind deshalb die beste Möglichkeit, die Leistungsfähigkeit in Embedded-Systemen mit hohem Rechenaufkommen weiter zu steigern. Ganz umsonst lassen sich die potenziellen Performance-Steigerungen freilich nicht realisieren.

Single-Threaded-Software, die für Singlecore-Prozessoren geschrieben wurde, verbessert die Verarbeitung auf einem Multicore-Prozessor keineswegs. Um die zusätzlichen Cores nutzen zu können, muss der Entwickler die Software für das Multithreading neu schreiben oder zumindest anpassen. Die entscheidende Herausforderung besteht darin, die Cores einerseits so gut wie möglich auszulasten und andererseits zu gewährleisten, dass ihre Zugriffe auf gemeinsam genutzte Ressourcen einwandfrei koordiniert werden.

Das Schreiben solcher Programme ist leider erheblich schwieriger als das Schreiben von Single-Threaded-Code. Nebenläufiger, also für die Parallelverarbeitung ausgelegter Code ist anfällig für ganze neue Arten von Programmierfehlern wie etwa Deadlocks oder Race-Conditions. Wenn diese Defekte auftreten, manifestieren sie sich unter Umständen auf schwierig zu diagnostizierende Weise.

Traditionelle Techniken zum Einkreisen und Eliminieren von Nebenläufigkeitsfehlern erweisen sich dabei möglicherweise als ineffektiv. Nebenläufigkeitsfehler sind unter anderem deshalb so schwierig, weil sich die Ereignisse in den verschiedenen Threads auf ungeheuer vielfältige Weise miteinander verschachteln können. Tatsächlich nimmt die Zahl der denkbaren Verschachtelungen exponentiell mit der Zahl der Threads beziehungsweise Befehle zu.

Wenn die beiden Threads A (mit M Befehlen) und B (mit N Befehlen) ausgeführt werden, gibt es N+M aus N mögliche Verschachtelungen zwischen den Threads. Wenn wir als Beispiel von zwei eher trivialen Threads mit jeweils zehn Befehlen ausgehen, können sich diese Befehle bereits auf 184 756 verschiedene Arten miteinander verschachteln. Dies macht deutlich, dass es schon bei sehr kleinen Programmen so gut wie unmöglich ist, alle möglichen Kombinationen durchzuprüfen.

Aber selbst wenn es gelänge, eine bestimmte Verschachtelung zu identifizieren, die zu einem Fehler führt, wäre es dennoch schwierig, einen reproduzierbaren Testfall herzustellen, der genau diese Verschachtelung herbeiführt, denn das Scheduling der Threads erfolgt auf nicht-deterministische Weise. Das Debugging nebenläufiger Programme kann sich deshalb sehr teuer und zeitaufwändig gestalten.

Wie entstehen Data-Races?

Unter allen möglichen Nebenläufigkeitsdefekten dürften Race-Conditions die größte Tragweite haben. Schon seit Jahren sind sie Ursache zahlreicher teils spektakulärer Systemfehler. Traurige Berühmthe

Es gibt viele Arten von Race-Conditions. Im Folgenden soll auf die verbreitetste und heimtückischste Art eingegangen werden, nämlich auf Data-Races. Hierbei handelt es sich um Race-Conditions, die mit dem gleichzeitigen Zugriff auf Speicherstellen zu tun haben. Zu einem Data-Race kommt es, wenn es zwei oder mehr Threads gibt, die auf eine gemeinsam genutzte Speicherstelle zugreifen, wenn mindestens ein Thread die dort abgelegten Daten ändert und wenn es keinen expliziten Mechanismus gibt, um die Zugriffe zu koordinieren.

Kommt es zu einem Data-Race, kann das Programm in einen inkonsistenten Zustand geraten. Bild 1 zeigt ein Beispiel dafür. Eine Fertigungsstraße ist an ihrem Beginn und an ihrem Ende mit Sensoren ausgestattet, welche die Objekte zählen, die in die Straße herein- und aus ihr herauskommen. Die Zahl der in der Linie befindlichen Objekte wird mit jedem Impuls des Eingangssensors inkrementiert und mit jedem Impuls des Ausgangssensors dekrementiert.

Wenn ein Objekt exakt dann in die Fertigungsstraße eintritt, wenn ein anderes Objekt sie verlässt, müsste der Zählerstand inkrementiert und dekrementiert werden (bzw. umgekehrt) und anschließend unverändert sein. Die normalen Inkrementierungs- und Dekrementierungsvorgänge sind jedoch keine unteilbaren Operationen, sondern setzen sich aus mehreren Einzelbefehlen zusammen, die den Wert aus dem Speicher holen, lokal modifizieren und anschließend wieder im Speicher ablegen.

Erfolgen diese Aktualisierungen in einem Multi-Threaded-System ohne hinreichende Schutzmaßnahmen, so kann es zu einer Race-Condition kommen, weil die Sensoren ein gemeinsames Datenelement - nämlich den Zählwert - lesen und schreiben.

Die in Bild 1 gezeigte Verschachtelung resultiert in dem falschen Zählwert 69. Möglich sind außerdem Verschachtelungen, die den unrichtigen Wert 71 beziehungsweise den korrekten Wert 70 hervorbringen.

Dieses kleine Beispiel zeigt anschaulich eine der Eigenschaften von Data-Races, die ihre Diagnose so schwierig machen: Die Symptome der Verfälschung lassen sich möglicherweise erst lange nach dem Auftreten des Data-Race erkennen. Im vorliegenden Fall wird der Zählerstand unter Umständen erst dann als falsch erkannt, wenn er 1 beträgt, nachdem alle Objekte die Fertigungsstraße verlassen haben.

Sind Data-Races unkritisch?

Sehr verbreitet ist die Auffassung, bestimmte Data-Races seien unkritisch und könnten toleriert werden. Inzwischen steht jedoch außer Zweifel, dass dies - von äußerst seltenen Ausnahmen abgesehen - nicht der Fall ist. Der C-Standard besagt eindeutig, dass die Compiler davon ausgehen dürfen, dass keine Data-Races existieren. Optimizer können daher Transformationen vornehmen, die für die Performance-Verbesserung von Single-Threaded-Code zulässig sind, aber zu Bugs führen, wenn scheinbar gutartige Race-Conditions auftreten.

Selbst erfahrene Programmierer werden regelmäßig von solchen subtilen Effekten überrascht. Ist ein hohes Maß an Sicherheit gewünscht, kommt es deshalb entscheidend darauf an, sämtliche Data-Races aufzudecken und zu eliminieren. Betrachten wir dazu das Singleton-Entwurfsmuster. Dieses sehr verbreitete Idiom wird häufig verwendet, wenn ein Programm ein einziges zugrundeliegendes Objekt referenziert und wenn eine Boolesche Variable kodiert, ob dieses Objekt initialisiert wurde. Dieses Muster wird als »Lazy Initialization« (Initialisierung bei Bedarf) bezeichnet.

Listing 1:  Singleton-Entwurfsmuster in »Lazy Initialization«

if  (!initialized)  {
        object  =  create () ;
        initialized  =  true;

}
... object ...

Der Codeabschnitt in Listing 1 zeigt ein Beispiel für dieses Muster. Für ein Single-Thread-Programm reicht dieser Code absolut aus, doch bei mehreren Threads ist er nicht sicher, denn er kann ein Data-Race bei der Variable »initialized« hervorrufen. Wird der Code durch zwei verschiedene Threads aufgerufen, besteht das Risiko, dass beide Threads »!initialized« zum exakt gleichen Zeitpunkt sehen und beide »create()« aufrufen, womit das Singleton-Kriterium verletzt wird.

Um hier Thread-Sicherheit herzustellen, würde man normalerweise die gesamte »if«-Anweisung mit einer Sperre (Lock) schützen  (Listing 2).

Listing 2: Singleton-Entwurfsmuster mit Sperren (Locks)

if  (!initialized)  {
         lock () ;
         if  (!initialized)   {
               object = create () ;
               initialized = true;
         }
         unlock () ;
} ...
object ...

Da das Anfordern und Freigeben von Sperren jedoch aufwändig ist, versuchen die Programmierer meist, stattdessen eine doppelt überprüfte Sperrung (double-checked locking) zu verwenden, wobei die eine Prüfung außerhalb, die andere dagegen innerhalb der Sperre erfolgt. Die innere Prüfung soll bestätigen, dass die erste Prüfung immer noch gilt, nachdem die Sperre angefordert wurde.

Auf den ersten Blick scheint dies ausreichend zu sein, und in der Tat genügt diese Maßnahme auch, solange die Befehle garantiert in dieser Reihenfolge ausgeführt werden. Ein optimierender Compiler aber könnte die Reihenfolge von »object = create()« und »initialized = true« vertauschen, denn schließlich besteht keine Abhängigkeit zwischen beiden Anweisungen. Wenn in diesem Fall ein zweiter Thread nach der Zuweisung zu »initialized« auf diesen Code trifft, wird er den Wert von »object« verwenden, bevor dieser initialisiert wurde. Dies ist keineswegs ein isoliertes oder konstruiertes Beispiel.

Neben einer detaillierten Erläuterung enthält eine Reihe weiterer überzeugender Fälle. Es wäre falsch, darauf zu schließen, dass nur ein fehlerhafter Compiler eine solche Transformation vornehmen würde, denn nach den Sprachspezifikationen für C und C++ dürfen die Compiler ausdrücklich davon ausgehen, dass der zu compilierende Code keine Data-Races enthält. Die Semantik für das Auftreten eines Data-Race ist nicht definiert, und folglich ist der Compiler berechtigt, in beliebiger Weise zu handeln. Man bezeichnet dies gelegentlich als »Catch Fire«-Semantik.

Nebenläufigkeitsfehler beseitigen

Die traditionellen dynamischen Tests sind nicht deterministisch und eignen sich deshalb nicht sehr gut zum Auffinden vieler Nebenläufigkeitsfehler. Ein Programm, das einen Test viele hundert Mal besteht, kann später in derselben Umgebung und mit den exakt gleichen Eingangswerten versagen, wenn der Fehler bezüglich des Timings besonders empfindlich ist. Wenn Entwickler ein hohes Maß an Sicherheit anstreben, müssen sie auf andere Techniken setzen, um Nebenläufigkeitsdefekte zu vermeiden.

Inzwischen gibt es neue dynamische Techniken zum Aufdecken von Data Races. Corensic etwa bietet ein Tool an, das Applikationen bei der Ausführung überwacht und dabei versucht, solche Verschachtelungen zu wählen, die Nebenläufigkeitsfehler provozieren. Dieses Verfahren kann die Effektivität der Tests verbessern helfen. »ThreadSanitizer« findet Data-Races, indem es die Verarbeitung des Programms ins-trumentiert und nach potenziellen Races absucht.

Auf dem Embedded-Sektor bieten einige Anbieter von Echtzeitbetriebssystemen Möglichkeiten für eine erleichterte Diagnose von Data-Races, indem die zu einer Anomalie führenden Ereignisse noch einmal abgespielt werden können. Ein Beispiel hierfür ist »TraceX« von Express Logic. Statische Analysewerkzeuge können solche Fehler aufdecken. Während die dynamische Analyse die genaue Verarbeitung eines Programms bei bestimmten vorgegebenen Eingangszuständen prüft, ermittelt die statische Analyse Eigenschaften, die für alle denkbaren Ausführungsarten und alle möglichen Eingangswerte gelten.

In der Praxis verwenden die Tools Näherungen, um akzeptable Performance und Genauigkeit zu erzielen, und bleiben somit hinter diesem Ideal zurück. Dennoch decken sie bedeutend mehr Fälle ab als traditionelle Testmethoden. Grob gesagt erstellen statische Analysetools ein Modell des Programms und führen dieses symbolisch aus, wobei die Werkzeuge nach fehlerhaften Zuständen Ausschau halten.

»CodeSonar« von GrammaTech findet Data-Races durch das Aufstellen einer Karte (Map) darüber, welche Sperren von welchen Threads gehalten werden, sowie durch eine Analyse der möglichen Verschachtelungen, die unsynchronisierte Zugriffe auf gemeinsam genutzte Variablen verursachen können. Deadlocks und weitere Nebenläufigkeitsdefekte (darunter auch falsches Sperren-Management) lassen sich mit ähnlichen Techniken finden (Bild 2).

Individuelle Nebenläufigkeitskonstrukte

Die standardmäßigen Defekt-erkennungsverfahren sind dann am nützlichsten, wenn die Nebenläufigkeit der Programme mit ebenso standardmäßigen Mitteln realisiert wurde. Die meisten Tools kennen die besonderen Eigenschaften von Standardbibliotheken wie der Thread-Bibliothek »POSIX« oder proprietärer Schnittstellen wie »VxWorks«.

Viele Systeme aber bedienen sich individueller Techniken für das Management der Nebenläufigkeit. Zum Beispiel beschreibt Rigdon in ein medizinisches Gerät auf der Basis eine Plattform, die eine individuelle präemptive Multithreaded-Softwareschnittstelle nutzte. Eine wichtige Vorgabe bei diesem Designprojekt besagte, dass alle Daten-Instanzen, auf die von Threads verschiedener Prioritätsebenen zugegriffen werden kann, mit geeigneten Schutzkons-trukten abzusichern seien.

Als es die statische Analyse noch nicht gab, war ein voller Mannmonat an manueller Analyse notwendig, um die Einhaltung dieser Vorgabe zu verifizieren. Aus Gründen der Kostensenkung wurde deshalb nach einer Lösung auf der Basis der statischen Analyse Ausschau gehalten. Ein entscheidendes Merkmal moderner statischer Analysewerkzeuge ist ihre Erweiterbarkeit. Sie besitzen eine API mit Abstraktionen, um individuelle statische Analysealgorithmen komfortabel implementieren zu können.

Mithilfe der API von CodeSonar konnte das Unternehmen eine Lösung programmieren, die auf die Algorithmen im Kern der bestehenden Analysen aufsetzt, um jene Stellen im Code zu finden, an denen die Designvorgabe verletzt wird. Das daraus resultierende, als Plug-in implementierte Tool kann Verletzungen der wichtigen Vorgabe automatisch erkennen, und zwar zu einem Bruchteil der Kosten und in deutlich kürzerer Zeit als bisher.

Über den Autor:

Dr. Paul Anderson ist Vice President of Engineering bei GrammaTech.

Neue Version von »CodeSonar«
Anfang diesen Jahres hat GrammaTech die neue Version 3.6 ihres Quellcode-Analyse-Tools »Code-Sonar« vorgestellt. Das Unternehmen hat die grafische Benutzeroberfläche (GUI) zur Interaktion mit dem Entwickler verbessert. Darüber hinaus arbeitet die Analyse-Engine nun effizienter. Für eine große Codebasis hat die sich die Zeit für die Analyse um ein Drittel verkürzt, wie GrammaTech betont. CodeSonar 3.6 ist ab 18.000 US-Dollar für eine Einzelplatz-Lizenz verfügbar. Interessenten können eine kostenlose Testversion der Software herunterladen.