Parallelzugriff auf Daten

Teil 4: Programmieren für Multi-Core-Prozessoren

11.06.2008 von Rami Radi
Parallelverarbeitung mit Multi-Core-Prozessoren kann die Leistung deutlich erhöhen. Aber der Parallelzugriff auf Daten birgt auch Gefahren, die in nicht reproduzierbaren Fehlern resultieren. TecChannel zeigt Ihnen, wie Sie die Gefahren der Multi-Core-Programmierung mit Parallelverarbeitung umgehen.

Die Leistung von Computersystemen steigt seit Jahren kontinuierlich an. Dies betrifft nahezu alle Komponenten der Rechner. Am deutlichsten ist der Leistungsgewinn bei den Prozessoren, dem Arbeitsspeicher und den Festplatten zu verfolgen. Insbesondere die Prozessoren haben nicht nur dank höherer Taktung sondern vor allem durch die Multi-Core-Technologie massiv an Leistungsfähigkeit zugelegt. Einzelne Anwendungen profitieren aber nur von Multi-Core, wenn sie entsprechend programmiert sind.

In dieser mehrteiligen Reihe zur Programmierung für Multi-Core-Prozessoren führen wir Sie nach und nach durch die Besonderheiten der Multi-Core-Programmierung. Angefangen bei den wichtigsten Grundlagen der verschiedenen Parallelisierungs-Verfahren in Prozessoren im ersten Teil. Der zweite Teil drehte sich um die notwendige Modularisierung in Applikationen und das .Net-Framework. Im dritten Teil ging es um Deadlocks, Race Conditions und Zugriffe auf die .Net-Thread-Implementation. Dieser vierte Teil behandelt eine Reihe von Problemen, die beim Parallelzugriff auf gemeinsame Daten auftauchen können, und welche Methoden Sie anwenden, um konsistente Daten zu gewährleisten.

Parallelzugriff auf Daten

Sobald Code parallel auf gemeinsamen Daten ausgeführt wird, sind diese Daten genau zu beobachten. Paralleles Lesen von Daten stellt in der Regel kein Problem dar, aber bei parallelen Schreibzugriffen müssen entsprechende Vorkehrungen getroffen werden.

Das gilt auch für Operationen, die erst einen Lese- und dann einen Update-Zugriff ausführen wollen. Dies tritt beispielsweise bereits dann auf, wenn in einem Objekt ein Zähler mitgeführt wird, der pro Aufruf des Objektes und seiner Methoden inkrementiert wird. Bei parallel ausgeführten Threads können hier Konflikte auftreten:

Um solche Situationen zu umgehen und die parallelen Zugriffe zu koordinieren, werden exklusive Locksperren (Zugriffssperren) verwendet. Das .Net-Framework stellt dazu die Klasse ReaderWriterLock bereit. Diese regelt den Zugriff von Threads auf gemeinsam genutzte Ressourcen und erlaubt mehrere parallele Lesezugriffe, aber nur einen Schreibzugriff. Die Funktionsweise und der Nutzen von Locks orientieren sich an denen der Semaphore.

ReaderWriterLockSlim und ReaderWriterLock

ReaderWriterLock beanspruchte viele Ressourcen und CPU-Laufzeit. Daher stellt .Net 3.5 nun die Klasse ReaderWriterLockSlim bereit. ReaderWriterLockSlim ist bedeutend schneller und geht schonender mit den Ressourcen um.

Beide Klassen jeweils zwei Lock-Operationen bereit: Eine Sperre für Leseoperationen und eine Sperre für Schreiboperationen. Schreibsperren sind im Allgemeinen exklusiv, Lesesperren in der Regel jedoch nicht. Diese können folglich immer parallel existieren.

Ein Thread, der eine Schreibsperre besitzt, blockiert damit alle weiteren Lese- und Schreibsperren. Dies soll verhindern, dass ein anderer Thread auf veralteten Daten operiert, die mittlerweile durch den Schreibzugriff verändert wurden. Hinzu kommt, dass aus Performance-Gründen die gelesenen Daten häufig intern, im Kontext der Threads, gepuffert werden. Wird nun parallel durch einen schreibenden Zugriff von Thread_A das Datum verändert, bevor der Thread_B das Datum intern verarbeitet, so operiert Thread_B auf alten Inhalten.

Der folgende skizzierte Ablauf soll dies verdeutlichen:

Aber es gilt auch in umgekehrter Richtung. Ein Thread, der eine Lesesperre besitz, blockiert alle anderen Threads, die ein Schreibsperre anfordern. Daher verlangt ReaderWriterLock die Freigabe zum Schreiben von allen lesenden Objekten.

ReaderWriterLockSlim umfasst die folgenden Methoden zur Verwaltung der Schreib-/Lesesperren:

Deadlocks durch Schreib-/Lesesperren

Bei der Anforderung von Locks durch mehrere Threads können prinzipiell auch so genannte Deadlocks auftreten. Dies gilt immer dann, wenn mehrere Threads mehrere Locks beanspruchen, diese in unterschiedlicher Reihenfolge aufrufen und jeweils der andere Thread einen Lock belegt.

Der folgende skizzierte Ablauf soll dies verdeutlichen:

Um das zu umgehen, wird vorher geprüft, ob ein Lock verfügbar wäre. Ist dies der Fall, so wird die Sperre dem anfordernden Thread zugewiesen. Andernfalls wird eine bestimmte Zeit abgewartet und dann der Versuch abgebrochen, den Lock zu erhalten. .Net kennt dazu für jede Enter-Methode eine Variante mit „Try“. Diese beinhalten das Timeout.

Beispiel für ReaderWriterLockSlim

Das folgende Beispiel zeigt die Verwendung der ReaderWriterLockSlim. Die drei Read-Threads lesen dabei eine Liste aus. Diese wird von zwei weiteren Write-Threads gefüllt.

class Program {
static ReaderWriterLockSlim rw = new ReaderWriterLockSlim();
static List<int> items = new List<int>();
static Random rand = new Random();

static void Main() {
new Thread (Read).Start();
new Thread (Read).Start();
new Thread (Read).Start();
new Thread (Write).Start("A");
new Thread (Write).Start("B");
}

static void Read() {
while(true) {
rw.EnterReadLock();
foreach (int i in items) Thread.Sleep(10);
rw.ExitReadLock();
}
}

static void Write(object threadID) {
while(true) {
int newNumber = GetRandNum(100);
rw.EnterWriteLock();
items.Add(newNumber);
rw.ExitWriteLock();
Console.WriteLine(threadID+ " added " + newNumber);
Thread.Sleep(100);
}
}

static int GetRandNum(int max) {
lock(rand) return rand.Next(max);
}
}

Asynchrone Delegaten

Asynchrone Delegaten bieten eine angenehme Möglichkeit, um Werte zwischen einem gerufenen Thread (Worker) und seinem Aufrufer (Caller) auszutauschen. Es lassen sich beliebig viele Parameter zwischen dem Caller und Worker Thread übergeben. Entweder als Argumente im Aufruf des Worker Threads oder als Rückgabewerte bei der Beendigung des Worker.

Darüber hinaus werden Exceptions an den Ursprungs-Thread des asynchronen Delegaten weitergeleitet. Dabei ist allerdings zu beachten, dass der Worker asynchron zum Caller läuft. Dazu das folgende Beispiel, in dem zwei Strings verglichen werden, die beispielsweise aus einer Datenbank stammen können.

Zuerst das synchrone und traditionelle Modell. In dem Beispiel erfolgt zuerst das Lesen des ersten Strings (dbr.GetResult(1)) und dessen Zuweisung in String s1. Schließend wird dieser Vorgang in dbr.GetResult(2) und der Zuweisung zu String s2 wiederholt. Beachten Sie, dass die beiden Leseoperationen nacheinander ausgeführt werden:

static void CompareResults() {
DBRetriever dbr = new DBRetriever();
string s1 = dbr.GetResult(1);
string s2 = dbr.GetResult(2);
Console.WriteLine(s1 == s2 ? "Same" : "Different");
}

Um den gesamten Durchlauf dieser Prozedur zu beschleunigen, sollen im folgenden Codebeispiel die beiden Datenbankzugriffe parallel angestoßen werden. Dies ist der asynchrone Lesevorgang. An dieser Stelle nun kommen asynchrone Delegaten zum Einsatz. Der Caller einigt sich mit dem Worker Thread dabei über die Rückgabewerte. Im folgenden Beispiel ist die Verwendung der asynchronen Delegation aufgezeigt. Dabei werden zwei Rückgabewerte zurückgereicht.

Asynchrone Datenbankabfrage

delegate string GetResult(int i);
static void CompareResults() {
// Deklaration und Instantiierung der beiden Delegaten
// mit der GetResult -Signature:
GetResult result1 = new DBRetriever().GetResult;
GetResult result2 = new DBRetriever().GetResult;

// Start the retrieval from the database:
IAsyncResult cookie1 = result1.BeginInvoke (1, null, null);
IAsyncResult cookie2 = result2.BeginInvoke (2, null, null);

// Perform some random calculation:
double seed = 1.23;
for (int i = 0; i < 1000000; i++)
seed = Math.Sqrt(seed + 1000);

// Get the results, waiting for completion if necessary.
// Here's where any exceptions will be thrown:
string s1 = result1.EndInvoke(cookie1);
string s2 = result2.EndInvoke(cookie2);
Console.WriteLine(s1 == s2 ? "Same" : "Different");
}

Das Beispiel beginnt mit der Deklaration und Instantiierung der beiden Delegaten, deren referenzierte Methoden asynchron ausgeführt werden sollen. Jeder diese beiden Delegaten bezieht sich dabei auf ein DBRetriever-Objekt. Im Beispiel gehen wir ferner davon aus, dass DBRetriever keinen konkurrierenden Zugriff erlaubt. Andernfalls würde ein einziger Delegate genügen.

Anschließend werden durch BeginInvoke die Methoden aktiviert und dann sofort zum Caller zurückverzweigt. Als Übergabeparameter und in Abstimmung mit den Delegaten wird ein Integer-Datum verlangt. Des Weiteren müssen zwei Parameter, ein optionaler Callback und ein Daten-Objekt übergeben werden. Im Beispiel allerdings werden diese nicht verwendet und daher durch Null ersetzt.

BeginInvoke liefert ein Objekt vom Typ IASynchResult zurück. Dieses dient als Cookie für den Aufruf von EndInvoke weiter unten. IASynchResult besitzt ferner das Attribut IsCompleted zur Überwachung des Prozessfortschritts und dessen Beendigung.Nach dem Aufruf von BeginInvoke kann die Routine mit weiteren Arbeiten fortfahren. Im Beispiel erfolgen hier einige mathematische Berechnungen.

Der Aufruf von EndInvoke liefert die Ergebnisse zurück, im Beispiel Strings. Sollten die aufgerufen Worker-Threads noch nicht beendet sein, wartet EndInvoke an dieser Stelle. Wenn während der Ausführung der asynchronen Methode eine Exception auftritt, so wird diese an den Caller weitergeschleust.

Asynchrone Methoden

Für manche Objekttypen in .Net sind deren Methoden auch als asynchrone Versionen verfügbar. Ihre Namen beginnen mit "Begin" und "End". Diese asynchronen Methoden weisen ähnliche Signaturen auf wie die der asynchronen Delegaten, lösen aber komplexere Probleme und ermöglichen weitaus mehr konkurrierende Aktionen.

Ein Web- oder TCP-Socket-Server zum Beispiel kann somit durch nur wenige Threads im Pool mehrere hundert konkurrierende Zugriffe verwalten. Dabei verwendet er die asynchronen Methoden NetworkStream.BeginRead und NetworkStream.BeginWrite.

Dennoch sollten Sie asynchrone Methoden, wenn möglich, aus folgenden Gründen vermeiden:

Wenn das Ziel lediglich in der parallelen Ausführung des Threads liegt, sollten Sie besser die synchronen Varianten der jeweiligen Methoden in Verbindung mit asynchronen Delegaten verwenden, wie beispielsweise NetworkStream.Read. Eine weitere Möglichkeit ist der Gebrauch des ThreadPool.QueueUserWorkItem oder BackgroundWorker und natürlich auch die Erzeugung eines eigenen neuen Threads.

Asynchrone Events

Durch ein weiteres Pattern lassen sich asynchrone Versionen der Methoden realisieren. Sie werden als “event-based asynchronous pattern" bezeichnet. Die Namen der Methoden enden mit den Begriff „Async". Die Namen der korrespondierenden Events enden mit "Completed".

Diese eventbasierten Methoden liefern Events für den Prozessfortschritt (das “Progress Reporting”) und den Abbruch der Operationen. Sie sind damit geeignet, Forms und Controls in Windows-Applikationen zu aktualisieren. Wenn diese Funktionen in Verbindung mit einem Objekttyp eingesetzt werden sollen, der das eventbasierte asynchrone Verarbeitungsmodell nicht unterstützt, so kann es auch durch eine BackgroundWorker Helper Klasse umgesetzt werden.

Timer

Um Methoden oder Code im Allgemeinen periodisch auszuführen, werden Timer eingesetzt. Bereits seit der Version 1.1. des .Net-Framework existiert der Namespace System.Threading mit der Klasse Timer. Diese Klasse nutzt den Thread-Pool und ermöglicht die Verwendung mehrerer Timer. Die Timer-Klasse ist recht einfach und besteht lediglich aus einem Konstruktor und zwei Methoden (dispose und change). Die Methode change erwartet zwei Parameter: Der Parameter 1st definiert den ersten Timer-Tick und der Parameter subsequent das Intervall in Millisekunden.

Im folgenden Beispiel, ruft der Timer die Methode Tick erstmals nach einer Wartezeit von fünf Sekunden und dann periodisch jede Sekunde auf, bis der Benutzer eine Taststureingabe macht.

class Program {
static void Main() {
Timer tmr = new Timer (Tick, "tick...", 5000, 1000);
Console.ReadLine();
tmr.Dispose(); // End the timer
}

static void Tick (object data) {
// This runs on a pooled thread
Console.WriteLine (data); // Writes "tick..."
}
}

Erweiterte Timer

Neben diesem Timer im Namespace System.Threading, stellt das .Net-Framework eine weitere Timer-Klasse im Namensraum System.Timers zur Verfügung. Diese Timer-Klasse erweitert den bestehenden Timer und stellt bedeutend mehr Nutzerkomfort zur Verfügung. Zu diesen Erweiterungen zählen:

Eine dritte Timer-Variante stellt .Net in System.Windows.Forms bereit. Obgleich ihr Interface jenem aus dem Namespace System.Timers ähnelt, ist ihre Funktion gänzlich anders: Der Timer aus Windows.Forms verwendet nicht den Thread-Pool, sondern feuert den „Timer Tick“ immer aus dem Kontext des Threads, der ursprünglich den Timer erzeugte.

Wenn der Haupt-Thread für die Instantiierung aller Forms und Controls in einer Windows-Forms-Applikation verantwortlich ist, kann der Event-Handler des Timers mit allen Forms und Controls interagieren, ohne Sicherheitsbeschränkungen (thread-safety) zu verletzen. Der Aufruf von Control.Invoke wird dabei nicht benötigt.

Windows Forms- und WPF-Timers sind für all jene Belange gedacht, die eine zeitnahe Aktualisierung des Benutzerinterface benötigen. Entscheidend dabei ist die schnelle Ausführung, denn der Tick-Event wird im Kontext des Haupt-Threads ausgeführt.

Non-Blocking Synchronisation

Die Notwendigkeit zur Synchronisation besteht bereits bei einfachen Zuweisungen oder der Inkrementierung einer Variablen. Dies kann zwar immer durch die oben erwähnten Lock-Techniken und deren Methoden koordiniert werden, dabei wird allerdings der Thread blockiert und muss erneut zugeteilt (gescheduled) werden.

Dies führt zu Verzögerungen und Verwaltungs-Overhead. Um das zu umgehen, bietet das .Net-Framework neben den Lock-Techniken auch Mechanismen zur Synchronisation an, die die Ausführung nicht blockieren. Diese verhindern das Blockieren, Pausieren oder Wartezustände für die Threads und sind vor allem für einfache Operationen gedacht. Diese nicht blockierenden Synchronisierungen (Non-blocking syncs) sind aber nur bei der Verwendung von nicht unterbrechbaren (atomic) Instruktionen möglich. Dies ist jedoch nicht ohne Unterstützung durch den Compiler und der Verwendung von „volatiler" Read- und Write-Semantik möglich.

Atomic Statement

Ein Statement gilt dann als “atomic”, wenn es als eine Instruktion ausgeführt wird. Atomare Instruktionen können durch den Task-Scheduler nicht unterbrochen oder verdrängt werden. In C# beispielsweise ist eine einfache Lese- oder Schreiboperation auf einem 32-Bit-Feld, die auf einer 32-Bit-CPU ausgeführt wird, vom Typ „atomic“, denn sie wird in einem Befehl abgearbeitet.

class Atomicity {
static int x, y;
static long z;
static void Test() {
long myLocal;
x = 3; // Atomic
z = 3; // Nicht atomic (z ist 64 Bit)
myLocal = z; // Nicht atomic (z ist 64 Bit)
y += x; // Nicht atomic (Lese- UND Schreibzugriff)
x++; // Nicht atomic (Lese- UND Schreibzugriff)
}
}

Lese- und Schreiboperationen mit größerer Datenbreite (beispielsweise 64 Bit) hingegen, sind auf der 32-Bit-CPU nicht atomic, da sie sich aus mehreren einzelnen und nacheinander auszuführenden Operationen zusammensetzen. Hierbei müssen zwei separate Instruktionen, die jeweils 32-Bit lesen, ausgeführt werden. Zwischen diesen beiden einzelnen Schritten allerdings kann es zum Task-Switch, also der Verdrängung eines Threads kommen. Wenn nun Thread_A ein 64-Bit-Datum lesen will, während Thread_B just dieses Datum verändert, erhält Thread_A einen falschen Wert bzw. eine Mischung aus altem und neuen Inhalt.

Unäre Operationen

Unäre Operatoren wie beispielsweise x++ verlangen in ersten Schritt das Lesen der Variablen (x), dann wird diese erhöht und im dritten Schritt wieder zurück geschrieben. Dazu ein Beispiel:

class ThreadUnsafe {
static int x = 1000;
static void Go () {
for (int i = 0; i < 100; i++)
x--;
}
}

In obigen Beispiel wird x zuerst mit 1000 initialisiert und in der for-Schleife 100 Mal dekrementiert. Wenn nun dieser Code von 10 Threads ausgeführt wird, könnte man vermuten, dass dann der Wert von x = 0 ist (1000 – 10 * 100). Dies ist allerdings nicht sicher! Die Ursache dafür liegt erneut in der Pufferung der Datenwerte von x.

Wenn Thread_A vor dem Zurückspeichern von x verdrängt wird und in der Zwischenzeit Thread_B x ausliest, arbeitet Thread_B mit einem alten Wert für x. Beide Threads bemerken davon nichts und effektiv wurde x nur einmal statt zweimal dekrementiert.

Die Klasse Interlocked

Um diese Situation zu umgehen, können nicht-atomare Operationen durch ein Lock-Statement abgesichert werden. Locking bildet quasi einen Rahmen um diese Operationen. Weitaus schneller und einfacher aber geht es durch die Verwendung der Klasse Interlocked.

Die Verwendung dieser Klasse ist nicht nur effizienter als ein Lock, sie verhindert auch das Blockieren oder Verdrängen des Threads. Und schließlich greift Interlocked auch über Prozessgrenzen hinweg, während das Lock-Statement nur auf Threads im aktuellen Prozess anzuwenden ist.

class Program {
static long sum;
static void Main() {
// Simple increment/decrement operations:
Interlocked.Increment(ref sum); // 1
Interlocked.Decrement(ref sum); // 0
// Add/subtract a value:
Interlocked.Add(ref sum, 3); // 3
// Read a 64-bit field:
Console.WriteLine(Interlocked.Read(ref sum)); // 3
// Write a 64-bit field while reading previous value:
// (This prints "3" while updating sum to 10)
Console.WriteLine(Interlocked.Exchange (ref sum, 10)); // 10
// Update a field only if it matches value (10):
Interlocked.CompareExchange (ref sum, 123, 10); // 123
}
}

Speicherbarrieren und Volatilität

Variablen werden, um die Zugriffsgeschwindigkeit zu verbessern, in schnellen Speichern wie CPU-Registern und Caches zwischengepuffert. Auf diesem Prinzip basieren auch die Caches.

Wenn auf einem Multi-Core-System der Scheduler zwei Threads zwei unterschiedlichen Cores zuweist, so können die gepufferten Variablen unterschiedliche Inhalte in den Registern aufweisen. Ferner kann es beim Zurückschreiben der Variablen zu Fehlern in der Reihenfolge führen, so dass falsche Werte zurück geschrieben werden. Um dies zu umgehen, stehen zum Schreiben von Objekten und Feldern die Methoden Thread.VolatileRead und Thread.VolatileWrite zur Verfügung.

Ersteres erzwingt das Lesen des aktuellen Wertes der Variablen aus dem Speicher und letzteres wiederum verlangt das sofortige Schreiben eines Wertes in den Speicher. Die gleiche Wirkung erzielt aber auch der Zusatz "volatile“ bei der Felddeklaration der Variablen.

Auch durch das Locking des Zugriffs ist ein vergleichbarer Effekt zu erreichen. Hierbei werden Lese- oder Schreibzugriff mit der Lock-„Klammer“ umgeben, beispielsweise EnterReadLock(); ... ExitReadLock();.

Vorteilhaft ist die Lock-Klammer immer dann, wenn die damit gesicherte Variable öfter benötigt wird – beispielsweise bei einer Schleife. Dabei umschließt die Lock-Klammer die gesamte Schleife. Die Sperre muss also nur einmal zu Beginn eingerichtet werden und wird am Ende wieder aufgelöst.

Wenngleich ein einzelner volatiler Schreib- oder Lesevorgang (Thread.VolatileRead, VolatileWrite) im Vergleich zum Lock-Statement bedeutend schneller ist, wird bei vielen Schleifendurchläufen die Lock-Klammer die bessere, weil leistungsfähigere, Variante sein.

Im nächsten und vorerst letzten Teil geht es um die Optimierung von .Net-Applikationen für Multi-Core-Architekturen - insbesondere darum, wie man Flaschenhälse und Probleme erkennt und behebt. (mha)