1. Das Muster „Ohne Sperre“ (Lock-Free / Wait-Free)
Ihr wisst schon, dass Concurrent-Collections thread-safe sind. Aber wie machen sie das, ohne dass ihr euren Code mit lock-Blöcken vollstopft? Die Antwort liegt in fortgeschrittenen Algorithmen — lock-free (ohne Sperren) und wait-free (ohne Warten).
Knappe Erklärung der Konzepte von lock-free und wait-free Algorithmen
Lock-Free (ohne Sperren)
Kernidee: Garantiert, dass mindestens ein Thread immer einen Schritt vorankommt, selbst wenn andere Threads Verzögerungen oder Unterbrechungen haben.
Unterschied zu lock: Bei Verwendung von lock warten konkurrierende Threads, bis die Sperre frei wird. In lock-free Algorithmen warten Threads nicht im klassischen Sinn: bei einem Konflikt wiederholen sie einfach den Versuch.
Beispiel: Warteschlange an der Kasse: mit lock stehst du und wartest. In lock-free gehst du hin, siehst, dass besetzt ist, und versuchst es kurz später nochmal — ohne in einer gemeinsamen Schlange zu „stehen“.
Wait-Free (ohne Warten)
Kernidee: Eine stärkere Garantie: jeder Thread macht innerhalb einer endlichen Anzahl eigener Schritte Fortschritt, unabhängig von anderen. Niemand dreht sich endlos im Kreis.
Unterschied: In lock-free kann ein Thread wegen Konflikten eine Operation theoretisch unendlich oft neu starten; in wait-free passiert das nicht.
Praxis: Wait-free zu implementieren ist deutlich komplizierter, deshalb trifft man häufiger lock-free oder hybride Ansätze an.
2. Wie Concurrent-Collections Thread-Sicherheit erreichen
Der grundlegende Baustein von lock-free Algorithmen sind atomare Operationen auf CPU-Ebene. In .NET greifen wir darauf über die Klasse System.Threading.Interlocked zu.
Interlocked-Operationen
Schnelle atomare Operationen auf Primitiven (int, long): z.B. Interlocked.Increment, Interlocked.Decrement, Interlocked.CompareExchange.
Beispiele: Interlocked.Increment(ref value) — atomare Erhöhung; Interlocked.CompareExchange(ref location, value, comparand) — vergleicht atomar und aktualisiert, falls gleich.
CAS (Compare-And-Swap) — Vergleichen-und-Tauschen
Die CAS-Operation ist in .NET als Interlocked.CompareExchange realisiert. Allgemeine Logik:
- Aktuellen Wert der Variable lesen.
- Neuen Wert basierend auf dem gelesenen berechnen.
- Versuchen, ihn zu schreiben nur wenn die Variable noch dem ursprünglichen Wert entspricht. Wenn nicht — wiederholen.
Beispiel: einfacher lock-free Zähler mit Interlocked
using System.Threading;
using System.Threading.Tasks;
class CounterExample
{
static int regularCounter = 0;
static int interlockedCounter = 0;
static void IncrementRegular(int iterations)
{
for (int i = 0; i < iterations; i++)
{
regularCounter++; // Nicht thread-safe!
}
}
static void IncrementInterlocked(int iterations)
{
for (int i = 0; i < iterations; i++)
{
Interlocked.Increment(ref interlockedCounter); // Atomar!
}
}
}
//In Main:
Task t1 = Task.Run(() => IncrementRegular(500_000));
Task t2 = Task.Run(() => IncrementRegular(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Gewöhnlicher Zähler: {regularCounter}"); // wird fast immer weniger als 1_000_000 sein
regularCounter = 0; // Zurücksetzen für den nächsten Test
t1 = Task.Run(() => IncrementInterlocked(500_000));
t2 = Task.Run(() => IncrementInterlocked(500_000));
Task.WaitAll(t1, t2);
Console.WriteLine($"Interlocked Zähler: {interlockedCounter}"); // Wird genau 1_000_000 sein
Die Methode Interlocked.Increment garantiert die Atomarität des Inkrements: Daten gehen nicht verloren, selbst bei konkurrierendem Zugriff vieler Threads.
3. Warum das für Skalierbarkeit und Performance wichtig ist
Senkung der Overheads: klassische Locks (lock) können Context-Switches und Wartezeiten im OS-Kernel verursachen. Lock-free minimiert diese Kosten.
Keine Deadlocks: Threads warten nicht aufeinander — es gibt nichts, was zu Deadlocks führen könnte.
Bessere Skalierbarkeit: Auf Mehrkernsystemen stören sich Threads weniger gegenseitig, es gibt kein „Flaschenhals“-Problem durch eine einzige gemeinsame Sperre.
Höhere Reaktionsfähigkeit: Niemand „hängt“ wegen langer Wartzeiten.
Sehr kurzer Blick auf den internen Aufbau von ConcurrentQueue<T>
Vereinfacht: die Queue besteht aus verknüpften Segmenten. Bei Enqueue bewegt ein Thread atomar den „Tail“ mittels CompareExchange; bei TryDequeue wird atomar der „Head“ verschoben, nur wenn er sich nicht geändert hat. Reale Implementierungen sind komplizierter (lösen ABA-Probleme und berücksichtigen Garbage Collection), aber der Schlüssel ist: atomare Operationen statt „schwerer“ Locks.
4. Performance von Concurrent-Collections
Performance-Vergleich mit lock auf normalen Collections
Bei geringer Konkurrenz ist der Unterschied klein, und manchmal ist ein einfacher lock auf einer normalen Collection vergleichbar. Bei hoher Konkurrenz sind Concurrent-Collections in der Regel
Beispiel: Vergleich (Idee, ohne Ausführung)
using System.Collections.Generic;
using System.Collections.Concurrent;
using System.Diagnostics; // Für Stopwatch
using System.Threading.Tasks;
class PerformanceTest
{
static List<int> regularList = new List<int>();
static ConcurrentQueue<int> concurrentQueue = new ConcurrentQueue<int>();
static object lockObject = new object();
const int Iterations = 1_000_000;
const int NumTasks = 4; // Anzahl paralleler Tasks
public static void RunTests()
{
Console.WriteLine("Performance-Test (Hinzufügen):");
// Test mit normaler List und lock
regularList.Clear();
Stopwatch sw = Stopwatch.StartNew();
Parallel.For(0, NumTasks, (i) =>
{
for (int j = 0; j < Iterations / NumTasks; j++)
{
lock (lockObject)
{
regularList.Add(j);
}
}
});
sw.Stop();
Console.WriteLine($"List mit lock: {sw.ElapsedMilliseconds} ms. Count: {regularList.Count}");
// Test mit ConcurrentQueue
concurrentQueue.Clear();
sw = Stopwatch.StartNew();
Parallel.For(0, NumTasks, (i) =>
{
for (int j = 0; j < Iterations / NumTasks; j++)
{
concurrentQueue.Enqueue(j);
}
});
sw.Stop();
Console.WriteLine($"ConcurrentQueue: {sw.ElapsedMilliseconds} ms. Count: {concurrentQueue.Count}");
// Erwarten Sie, dass ConcurrentQueue deutlich schneller ist bei NumTasks > 1
}
}
Fazit: Wenn Sie ein lock um Collections sehen, ist das oft ein Signal, auf Concurrent-Äquivalente umzusteigen.
6. Nützliche Feinheiten
Einfluss von contention auf die Performance
Contention — wenn viele Threads gleichzeitig auf dieselbe Ressource zugreifen. Je höher die Konkurrenz, desto mehr Wartezeiten und schlechtere Performance.
Concurrent-Collections sind so entworfen, contention zu reduzieren: z.B. verwendet ConcurrentBag<T> thread-lokale Speicher, und ConcurrentDictionary<TKey, TValue> segmentierte Locks (striped locking).
Der Schlüssel zur Performance ist Reduzierung von contention: wenn möglich, teilt Daten zwischen Threads auf oder verwendet mehrere Collections.
Die richtige Collection für ein bestimmtes Szenario wählen
| Collection | Ordnung | Wann verwenden | Wann nicht verwenden |
|---|---|---|---|
|
FIFO (First-In, First-Out) | Task-Queues, Logging, asynchrone Event-Verarbeitung, Producer-Consumer. | Wenn die Reihenfolge unwichtig ist, LIFO gebraucht wird oder eine Größenbegrenzung mit Blocking benötigt wird. |
|
LIFO (Last-In, First-Out) | Operation-Historie (Undo/Redo), Graphdurchlauf (DFS), Objekt-Pools mit „zuletzt hinzugefügt“-Priorität. | Wenn FIFO kritisch ist oder Reihenfolgestabilität wichtig ist. |
|
Nicht garantiert | Objekt-Pools, wenn Produzent und Konsument oft derselbe Thread sind; TPL-Szenarien mit wichtiger Lokalität. | Wenn die Reihenfolge der Elemente wichtig ist. |
|
Nein | Caching, User-Sessions, Statistik-Zählungen, parallele Aggregation. | Wenn Sie kein Dictionary brauchen. |
| BlockingCollection<T> (aufbauend auf ConcurrentQueue) | FIFO (oder die zugrundeliegende Collection) | Producer-Consumer mit blockierenden Operationen und Größenbegrenzung, sauberes Beenden. | Wenn blockierende Operationen oder Größenbegrenzung nicht nötig sind. |
7. Optimierungstipps
Vermeide häufiges ToArray() an heißen Stellen
ToArray() erstellt eine neue Kopie der gesamten Collection — teuer in Speicher und Zeit. Nutze es nur, wenn du einen „Schnappschuss“ brauchst, und so selten wie möglich. Für die Größe gibt es Count (beachte, dass das ein Snapshot zum Zeitpunkt des Aufrufs ist).
Vorsicht bei der Iteration über Concurrent-Collections
Iteratoren garantieren keine Stabilität bei parallelen Modifikationen: du kannst Elemente überspringen oder eine inkonsistente Sicht bekommen. Für eine stabile Sicht mache zuerst ein Snapshot via ToArray().
// Schlecht: kann Elemente überspringen oder Änderungen während der Iteration sehen
foreach (var item in myConcurrentQueue) { /* ... */ }
// Gut: Iteration über einen festen Snapshot
var snapshot = myConcurrentQueue.ToArray();
foreach (var item in snapshot) { /* ... */ }
Minimiere den „Traffic“ durch die Collection
Gruppiere Aufgaben/Daten: weniger Aufrufe von Add/Take — weniger potentielles contention. Zum Beispiel statt 1000 Einzel-Nachrichten ein Paket mit 1000.
Identifiziere Quellen von Konkurrenz
Wenn du Leistungseinbußen siehst, messe, wo die meiste contention auftritt. Möglicherweise lässt sich das Design so ändern, dass Threads mit lokalen Daten oder unterschiedlichen Collections arbeiten.
GO TO FULL VERSION