Litmus Test (Concurrency)

Als Kernel-Hacker oder Compiler-Bauer. Wenn du an Linux arbeitest (tools/memory-model/litmus-tests), nutzt du das, um zu beweisen, dass deine Locks korrekt sind. Als Java/C++ Entwickler nutzt du Tools wie JCStress, die Litmus-Tests generieren, um zu prüfen, ob deine JVM/Compiler Bugs hat.

1. MP (Message Passing) Test

Der Klassiker. Thread 1: Data = 42; Flag = 1; Thread 2: if (Flag == 1) assert(Data == 42); Auf Hardware mit Weak Memory Model (ARM, POWER) kann das fehlschlagen! Die CPU kann Flag = 1 vor Data = 42 ausführen (Reordering). Thread 2 sieht Flag 1, aber alte Daten (z. B. 0). Lösung: Memory Barriers (smp_wmb()).

2. Store Buffering (SB)

Total Store Order (TSO) bei x86 erlaubt, dass Reads vor Writes vorgezogen werden (aus dem Buffer). Das führt zu dem Paradoxon, dass beide Threads "in die Vergangenheit" schauen.

1. TSO vs. Weak Ordering

Die Welt der Litmus Tests teilt sich in zwei Lager:

• TSO (Total Store Order): Genutzt von x86. Hier sind fast alle Litmus Tests "langweilig", weil die Hardware sehr brav ist. Nur der "Store Buffering" Test (SB) zeigt Anomalien.
• Weak Ordering: Genutzt von ARM und POWER. Hier ist die Hölle los. Instruktionen können fast beliebig vertauscht werden. Ein Read kann vor einem Write passieren, ein Write kann für einen Thread sichtbar sein, für einen anderen aber noch nicht (Non-multi-copy-atomicity). Experten nutzen Litmus-Kataloge, um die exakte Grenze zwischen "gerade noch erlaubt" und "definitiv ein Hardware-Bug" zu definieren.

2. Operational vs. Axiomatic Models

Wie beschreibt man das Ergebnis eines Litmus Tests formal?

• Operational Models: Beschreiben eine abstrakte Maschine mit Puffern und Warteschlangen. Man "spielt das Programm durch". Intuitiv, aber schwer für komplexe CPUs.
• Axiomatic Models: Beschreiben Relationen zwischen Events (Reads/Writes). z. B. "Reads-From" ($rf$) oder "Coherence-Order" ($co$). Man stellt Regeln auf wie: "Es darf keinen Zyklus aus diesen Relationen geben." Das Linux Kernel Memory Model (LKMM) nutzt ein axiomatisches Modell, um sicherzustellen, dass die READ_ONCE() und WRITE_ONCE() Makros auf allen Architekturen die gleichen Litmus-Garantien liefern.

3. Fence Insertion & Optimization

In der Produktion (Compiler-Bau) ist der Litmus Test das Tool zur Korrektureitsprüfung. Wenn ein Compiler eine Schleife optimiert, könnte er Instruktionen so verschieben, dass ein Litmus Test plötzlich fehlschlägt. Hochleistungskerne (wie der M1/M2 von Apple) haben extrem aggressive Out-of-Order Execution. Sie nutzen interne Litmus-Check-Einheiten, um zu verhindern, dass spekulativ ausgeführte Befehle die Speicherkonsistenz verletzen. Wenn du std::atomic in C++ nutzt, fügt der Compiler genau dort "Fences" (Barrieren) ein, wo ein Litmus Test sonst ein illegales Verhalten zeigen würde.