Überlegungen zur Programmierung ohne Sperren für Xbox 360 und Microsoft Windows

  • Artikel

Programmierung ohne Sperren ist eine Möglichkeit, um Daten zwischen mehreren Threads sicher freizugeben, ohne dass Sperren erworben und freigegeben werden müssen. Das erscheint wie ein Universalmittel, aber die Programmierung ohne Sperren ist komplex und subtil und bringt manchmal nicht die Vorteile, die sie verspricht. Die Programmierung ohne Sperren ist besonders komplex auf Xbox 360.

Die Programmierung ohne Sperren ist eine gültige Technik für die Multithread-Programmierung, sollte aber nicht unüberlegt verwendet werden. Bevor Sie es verwenden, müssen Sie die Komplexität verstehen, und Sie sollten sorgfältig prüfen, ob es Ihnen tatsächlich die erwarteten Vorteile bringt. In vielen Fällen gibt es einfachere und schnellere Lösungen, z. B. durch eine geringere Häufigkeit des Datenaustauschs, die stattdessen verwendet werden sollten.

Die ordnungsgemäße Verwendung der Programmierung ohne Sperren erfordert erhebliche Kenntnisse sowohl der Hardware als auch des Compilers. In diesem Artikel finden Sie eine Übersicht über einige der Probleme, die Sie berücksichtigen sollten, wenn Sie versuchen, Programmiertechniken ohne Sperren zu verwenden.

Programmieren mit Sperren

Beim Schreiben von Multithreadcode ist es häufig erforderlich, Daten zwischen Threads freizugeben. Wenn mehrere Threads gleichzeitig die freigegebenen Datenstrukturen lesen und schreiben, können Speicherbeschädigungen auftreten. Die einfachste Möglichkeit, dieses Problem zu lösen, ist die Verwendung von Sperren. Wenn ManipulationSharedData beispielsweise nur jeweils von einem Thread ausgeführt werden soll, kann ein CRITICAL_SECTION verwendet werden, um dies wie im folgenden Code zu gewährleisten:

// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);

// Use
void ManipulateSharedData()
{
    EnterCriticalSection(&cs);
    // Manipulate stuff...
    LeaveCriticalSection(&cs);
}

// Destroy
DeleteCriticalSection(&cs);

Dieser Code ist ziemlich einfach und unkompliziert, und es ist leicht zu erkennen, dass er korrekt ist. Die Programmierung mit Sperren hat jedoch mehrere mögliche Nachteile. Wenn beispielsweise zwei Threads versuchen, dieselben zwei Sperren zu erhalten, aber in unterschiedlicher Reihenfolge, kann es zu einem Deadlock kommen. Wenn ein Programm eine Sperre für zu lange hält – aufgrund eines schlechten Designs oder weil der Thread durch einen Thread mit höherer Priorität ausgetauscht wurde – werden andere Threads möglicherweise lange blockiert. Dieses Risiko ist besonders gut auf Xbox 360, da den Software Threads vom Entwickler ein Hardwarethread zugewiesen werden und das Betriebssystem sie nicht in einen anderen Hardwarethread verschiebt, auch wenn ein Thread leer ist. Die Xbox 360 bietet auch keinen Schutz gegen Prioritätsinversion, bei der ein Thread mit hoher Priorität in einer Schleife läuft, während er darauf wartet, dass ein Thread mit niedriger Priorität eine Sperre freigibt. Wenn schließlich ein verzögerter Prozeduraufruf oder eine Unterbrechungsdienstroutine versucht, eine Sperre zu erwerben, erhalten Sie möglicherweise einen Deadlock.

Trotz dieser Probleme sind Synchronisierungsgrundtypen wie kritische Abschnitte im Allgemeinen die beste Möglichkeit, mehrere Threads zu koordinieren. Wenn die Synchronisierungsgrundtypen zu langsam sind, besteht die beste Lösung in der Regel darin, sie weniger häufig zu verwenden. Für diejenigen, die sich die zusätzliche Komplexität leisten können, ist eine andere Option jedoch eine Programmierung ohne Sperren.

Programmierung ohne Sperren

Die Programmierung ohne Sperren, wie der Name schon sagt, ist eine Reihe von Techniken zum sicheren Bearbeiten freigegebener Daten ohne Sperren. Es stehen Algorithmen ohne Sperren zum Übergeben von Nachrichten, Freigabelisten und Warteschlangen von Daten und anderen Aufgaben zur Verfügung.

Beim Programmieren ohne Sperren gibt es zwei Herausforderungen, mit denen Sie umgehen müssen: nicht-atomische Operationen und Neuanordnung.

Nicht-atomische Operationen

Eine atomische Operation ist eine, die unteilbar ist – eine, bei der andere Threads garantiert niemals den Vorgang sehen, wenn die Hälfte abgeschlossen ist. Atomische Operationen sind für die Programmierung ohne Sperren wichtig, da ohne sie andere Threads halb geschriebene Werte oder anderweitig inkonsistenten Zustand sehen können.

Bei allen modernen Prozessoren können Sie davon ausgehen, dass Lese- und Schreibvorgänge natürlich ausgerichteter systemeigener Typen atomisch sind. Solange der Speicherbus mindestens so breit ist wie der Typ, der gelesen oder geschrieben wird, liest und schreibt die CPU diese Typen in einer einzelnen Bustransaktion, wodurch es für andere Threads unmöglich ist, sie in einem halb abgeschlossenen Zustand zu sehen. Auf x86 und x64 gibt es keine Garantie, dass Lese- und Schreibvorgänge größer als acht Byte atom sind. Dies bedeutet, dass 16-Byte-Lese- und Schreibvorgänge von Streaming-SIMD-Erweiterungsregistern (SSE) und Zeichenfolgen-Operationen möglicherweise nicht atomisch sind.

Lese- und Schreibvorgänge von Typen, die nicht auf natürliche Weise ausgerichtet sind , z. B. das Schreiben von DWORDs, die vier Bytegrenzen überschreiten, sind nicht garantiert atomisch. Die CPU muss diese Lese- und Schreibvorgänge als mehrere Bustransaktionen ausführen, wodurch ein anderer Thread die Daten in der Mitte des Lese- oder Schreibvorgangs ändern oder anzeigen kann.

Zusammengesetzte Vorgänge, z. B. die Sequenz mit Lese-/Schreibzugriff, die auftritt, wenn Sie eine freigegebene Variable erhöhen, sind nicht atomar. Auf Xbox 360 werden diese Vorgänge als mehrere Anweisungen (lwz, addi und stw) implementiert, und der Thread könnte über die Sequenz ausgetauscht werden. Auf x86 und x64 gibt es eine einzelne Anweisung (inc), die verwendet werden kann, um eine Variable im Arbeitsspeicher zu erhöhen. Wenn Sie diese Anweisung verwenden, ist das Inkrementieren einer Variablen auf einzelprozessorbasierten Systemen atomar, aber es ist immer noch nicht atomar auf Multiprozessorsystemen. Um inc auf x86- und x64-basierten Multiprozessorsystemen atomar zu machen, muss das Sperrpräfix verwendet werden, das einen anderen Prozessor daran hindert, seine eigene Lese-Änderungs-Schreib-Sequenz zwischen dem Lesen und dem Schreiben der inc-Anweisung durchzuführen.

Der folgende Code zeigt einige Beispiele:

// This write is not atomic because it is not natively aligned.
DWORD* pData = (DWORD*)(pChar + 1);
*pData = 0;

// This is not atomic because it is three separate operations.
++g_globalCounter;

// This write is atomic.
g_alignedGlobal = 0;

// This read is atomic.
DWORD local = g_alignedGlobal;

Garantieren der Atomarität

Sie können sicher sein, dass Sie atomische Operationen verwenden, indem Sie eine Kombination der folgenden Aktionen verwenden:

  • Natürlich atomische Operationen
  • Sperrungen zum Umschließen zusammengesetzter Vorgänge
  • Betriebssystemfunktionen, die atomische Versionen beliebter Verbundvorgänge implementieren

Das Erhöhen einer Variablen ist keine atomische Operation, und das Erhöhen kann zu Datenbeschädigungen führen, wenn sie in mehreren Threads ausgeführt werden.

// This will be atomic.
g_globalCounter = 0;

// This is not atomic and gives undefined behavior
// if executed on multiple threads
++g_globalCounter;

Win32 verfügt über eine Reihe von Funktionen, die atomische Lese-/Schreibzugriffsversionen mehrerer gängiger Vorgänge bieten. Dies sind die InterlockedXxx-Funktionsfamilie. Wenn alle Änderungen der freigegebenen Variablen diese Funktionen verwenden, sind die Änderungen threadsicher.

// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);

Neuanordnung

Ein subtileres Problem ist eine Neuanordnung. Lese- und Schreibvorgänge erfolgen nicht immer in der Reihenfolge, in der Sie sie in Ihrem Code geschrieben haben, und dies kann zu sehr verwirrenden Problemen führen. In vielen Multithreadalgorithmen schreibt ein Thread einige Daten und schreibt dann in ein Flag, das anderen Threads angibt, dass die Daten bereit sind. Dies wird als Schreibversion bezeichnet. Wenn die Schreibvorgänge neu angeordnet sind, sehen andere Threads möglicherweise, dass das Flag festgelegt ist, bevor sie die geschriebenen Daten sehen können.

Ebenso liest ein Thread in vielen Fällen aus einem Flag und liest dann einige freigegebene Daten, wenn das Flag besagt, dass der Thread Zugriff auf die freigegebenen Daten erworben hat. Dies wird als „Read-Acquire” bezeichnet. Wenn Lesevorgänge neu angeordnet sind, werden die Daten möglicherweise aus freigegebenem Speicher vor dem Flag gelesen, und die angezeigten Werte sind möglicherweise nicht auf dem neuesten Stand.

Die Neuanordnung von Lese- und Schreibvorgängen kann sowohl vom Compiler als auch vom Prozessor erfolgen. Compiler und Prozessoren haben diese Neuanordnung seit Jahren durchgeführt, aber auf Einzelprozessorcomputern war es weniger ein Problem. Dies liegt daran, dass die CPU-Neuanordnung von Lese- und Schreibvorgängen auf Einzelprozessorcomputern nicht sichtbar ist (für Nichtgerätetreibercode, der nicht Teil eines Gerätetreibers ist), und die Neuanordnung von Lese- und Schreibvorgängen ist weniger wahrscheinlich, dass Probleme auf Einzelprozessorcomputern auftreten.

Wenn der Compiler oder die CPU die im folgenden Code gezeigten Schreibvorgänge neu anordnen, kann ein anderer Thread sehen, dass das Alive-Flag festgelegt ist, während die alten Werte für „x” oder „y” weiterhin angezeigt werden. Eine ähnliche Neuanordnung kann beim Lesen auftreten.

In diesem Code fügt ein Thread dem Sprite-Array einen neuen Eintrag hinzu:

// Create a new sprite by writing its position into an empty
// entry and then setting the 'alive' flag. If 'alive' is
// written before x or y then errors may occur.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
g_sprites[nextSprite].alive = true;

In diesem nächsten Codeblock liest ein anderer Thread aus dem Sprite-Array:

// Draw all sprites. If the reads of x and y are moved ahead of
// the read of 'alive' then errors may occur.
for( int i = 0; i < numSprites; ++i )
{
    if( g_sprites[nextSprite].alive )
    {
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Um dieses Sprite-System sicher zu machen, müssen wir sowohl die Compiler- als auch die CPU-Neuanordnung von Lese- und Schreibvorgängen verhindern.

Grundlegendes zur CPU-Neuanordnung von Schreibvorgängen

Einige CPUs ordnen Schreibvorgänge so neu an, dass sie extern für andere Prozessoren oder Geräte in nicht programmbasierter Reihenfolge sichtbar sind. Diese Neuanordnung ist niemals für Nicht-Treibercode sichtbar, kann jedoch Probleme im Multithread-Code verursachen.

Xbox 360

Während die Xbox 360-CPU keine Anweisungen neu anordnet, werden Schreibvorgänge neu angeordnet, die nach den Anweisungen selbst abgeschlossen werden. Diese Neuanordnung von Schreibvorgängen ist speziell durch das PowerPC-Speichermodell zulässig.

Schreibvorgänge auf Xbox 360 gehen nicht direkt zum L2-Cache. Um die L2-Cache-Schreibbandbreite zu verbessern, durchlaufen sie stattdessen Speicherwarteschlangen und dann Speichersammlungspuffer. Die Speichersammlungspuffer ermöglichen das Schreiben von 64-Byte-Blöcken in den L2-Cache in einem einzigen Vorgang. Es gibt acht Speichersammlungspuffer, die effizientes Schreiben in mehrere verschiedene Speicherbereiche ermöglichen.

Die Speichersammlungspuffer werden normalerweise in den L2-Cache in der FiFO-Reihenfolge (First-in-first-out) geschrieben. Wenn sich die Zielcachezeile eines Schreibvorgangs jedoch nicht im L2-Cache befindet, kann dieser Schreibvorgang verzögert werden, während die Cachezeile aus dem Speicher abgerufen wird.

Selbst wenn die Speichersammlungspuffer in den L2-Cache in strenger FIFO-Reihenfolge geschrieben werden, garantiert dies nicht, dass einzelne Schreibvorgänge in den L2-Cache geschrieben werden. Stellen Sie sich beispielsweise vor, dass die CPU an die Position 0x1000 schreibt, dann an die Position 0x2000 und dann an die Position 0x1004. Der erste Schreibvorgang weist einen Speichersammlungspuffer zu und platziert ihn an der Vorderseite der Warteschlange. Der zweite Schreibvorgang weist einen anderen Speichersammlungspuffer zu und fügt ihn als Nächstes in die Warteschlange ein. Der dritte Schreibvorgang fügt seine Daten zum ersten Speichersammlungspuffer hinzu, der sich am Anfang der Warteschlange befindet. Daher endet der dritte Schreibvorgang vor dem zweiten Schreibvorgang mit dem L2-Cache.

Die Neuanordnung, die durch Speichersammlungspuffer verursacht wird, ist grundsätzlich unvorhersehbar, insbesondere, weil beide Threads auf einer Kernfreigabe die Speichersammlungspuffer verwenden, wodurch die Zuordnung und Leerung der Speichersammlungspuffer sehr variabel ist.

Dies ist ein Beispiel dafür, wie Schreibvorgänge neu angeordnet werden können. Es kann andere Möglichkeiten geben.

x86 und x64

Auch wenn x86- und x64-CPUs Anweisungen neu anordnen, werden Schreibvorgänge im Verhältnis zu anderen Schreibvorgängen in der Regel nicht neu angeordnet. Es gibt einige Ausnahmen für den kombinierten Arbeitsspeicher. Darüber hinaus können Zeichenfolgen-Operationen (MOVS und STOS) und 16-Byte-SSE-Schreibvorgänge intern neu angeordnet werden, andernfalls werden Schreibvorgänge nicht relativ zueinander neu angeordnet.

Grundlegendes zur CPU-Neuanordnung von Lesevorgängen

Einige CPUs ordnen Lesevorgänge neu an, sodass sie effektiv aus freigegebenem Speicher in nicht programmbasierter Reihenfolge stammen. Diese Neuanordnung ist niemals für Nicht-Treibercode sichtbar, es kann jedoch Probleme im Multithread-Code verursachen.

Xbox 360

Cachefehler können dazu führen, dass einige Lesevorgänge verzögert werden, was effektiv dazu führt, dass Lesevorgänge aus freigegebenem Speicher in der richtigen Reihenfolge stammen, und die Anzeigedauer dieser Cachefehler ist grundsätzlich unvorhersehbar. Die Vor- und Verzweigungsvorhersage kann auch dazu führen, dass Daten aus freigegebenem Speicher nicht mehr ordnungsgemäß verwendet werden. Dies sind nur einige Beispiele dafür, wie Lesevorgänge neu angeordnet werden können. Es kann andere Möglichkeiten geben. Diese Neuanordnung von Lesevorgängen ist speziell durch das PowerPC-Speichermodell zulässig.

x86 und x64

Auch wenn x86- und x64-CPUs Anweisungen neu anordnen, werden Lesevorgänge im Verhältnis zu anderen Lesevorgängen in der Regel nicht neu angeordnet. Zeichenfolgen-Operationen (MOVS und STOS) und 16-Byte-SSE-Lesevorgänge können intern neu angeordnet werden, andernfalls werden Lesevorgänge nicht relativ zueinander neu angeordnet.

Andere Neuanordnung

Obwohl x86- und x64-CPUs Schreibvorgänge nicht relativ zu anderen Schreibvorgängen neu anordnen oder Lesevorgänge relativ zu anderen Lesevorgängen neu anordnen, können sie Lesevorgänge relativ zu Schreibvorgängen neu anordnen. Wenn ein Programm an einen Speicherort schreibt, gefolgt vom Lesen von einem anderen Speicherort, können die Lesedaten aus dem freigegebenen Speicher stammen, bevor die geschriebenen Daten dort erstellt werden. Diese Neuanordnung kann einige Algorithmen unterbrechen, z. B. die gegenseitigen Ausschlussalgorithmen von Dekker. Im Dekker-Algorithmus legt jeder Thread ein Flag fest, um anzugeben, dass er in den kritischen Bereich gelangen möchte, und überprüft dann das Flag des anderen Threads, um festzustellen, ob sich der andere Thread im kritischen Bereich befindet oder versucht, ihn einzugeben. Der ursprüngliche Code folgt.

volatile bool f0 = false;
volatile bool f1 = false;

void P0Acquire()
{
    // Indicate intention to enter critical region
    f0 = true;
    // Check for other thread in or entering critical region
    while (f1)
    {
        // Handle contention.
    }
    // critical region
    ...
}


void P1Acquire()
{
    // Indicate intention to enter critical region
    f1 = true;
    // Check for other thread in or entering critical region
    while (f0)
    {
        // Handle contention.
    }
    // critical region
    ...
}

Das Problem besteht darin, dass der Lesevorgang von f1 in P0Acquire aus freigegebenem Speicher gelesen werden kann, bevor der Schreibvorgang in f0 zum freigegebenen Speicher führt. Unterdessen kann der Lesevorgang von f0 in P1Acquire aus freigegebenem Speicher lesen, bevor der Schreibvorgang in f1 zum freigegebenen Speicher führt. Der Nettoeffekt besteht darin, dass beide Threads ihre Flags auf TRUE festlegen, und beide Threads sehen die Kennzeichnung des anderen Threads als FALSE, sodass beide in den kritischen Bereich gelangen. Daher sind Probleme mit der Neuanordnung auf x86- und x64-basierten Systemen weniger verbreitet als auf Xbox 360, aber sie können definitiv noch passieren. Der Algorithmus von Dekker funktioniert nicht ohne Hardwarespeicherbarrieren auf einer dieser Plattformen.

x86- und x64-CPUs ordnen keine Schreibvorgänge vor einem vorherigen Lesevorgang neu an. x86- und x64-CPUs werden nur vor vorherigen Schreibvorgängen neu angeordnet, wenn sie auf unterschiedliche Speicherorte ausgerichtet sind.

PowerPC-CPUs können Lesevorgänge vor Schreibvorgängen neu anordnen und Schreibvorgänge vor Lesevorgängen neu anordnen, solange sie sich an unterschiedlichen Adressen befinden.

Zusammenfassung der Neuanordnung

Die Xbox 360 CPU sortiert Arbeitsspeichervorgänge wesentlich aggressiver an als x86- und x64-CPUs, wie in der folgenden Tabelle dargestellt. Weitere Informationen finden Sie in der Dokumentation des Prozessors.

Aktivität der Neuanordnung x86 und x64 Xbox 360
Lesevorgänge, die sich vor Lesevorgängen bewegen No Ja
Schreibvorgänge, die sich vor Schreibvorgängen bewegen No Ja
Schreibvorgänge, die sich vor Lesevorgängen bewegen No Ja
Lesevorgänge, die sich vor Schreibvorgängen bewegen Ja Ja

 

Lese-Erwerb- und Schreibschutzbarrieren

Die Hauptkonstrukte, die verwendet werden, um die Neuanordnung von Lese- und Schreibvorgängen zu verhindern, werden als Lese-Erwerb- und Schreibschutzbarrieren bezeichnet. Ein Lese-Erwerb ist ein Lesevorgang einer Kennzeichnung oder einer anderen Variablen, um den Besitz einer Ressource zu erhalten, gekoppelt mit einer Barriere gegen die Neuanordnung. Ebenso ist eine Schreibversion ein Schreibzugriff auf ein Flag oder eine andere Variable, um den Besitz einer Ressource freizugeben, gekoppelt mit einer Barriere gegen die Neuanordnung.

Die formalen Definitionen, die Herb Sutter zur Verfügung gestellt hat, sind:

  • Ein Lese-Erwerb wird ausgeführt, bevor alle Lese- und Schreibvorgänge durch denselben Thread ausgeführt werden, der in der Programmreihenfolge folgt.
  • Eine Schreibversion wird nach allen Lese- und Schreibvorgängen durch denselben Thread ausgeführt, der ihm in der Programmreihenfolge vorausgeht.

Wenn Ihr Code den Besitz eines Speichers erwirbt, entweder durch den Erwerb einer Sperre oder durch Ziehen eines Elements aus einer freigegebenen verknüpften Liste (ohne Sperre), ist immer ein Lesevorgang erforderlich, indem ein Flag oder Zeiger getestet wird, um festzustellen, ob der Besitz des Speichers erworben wurde. Dieser Lesevorgang kann Teil eines InterlockedXxx-Vorgangs sein, in diesem Fall umfasst es sowohl einen Lese- als auch einen Schreibvorgang, aber es ist der Lesevorgang, der angibt, ob der Besitz gewonnen wurde. Nachdem der Besitz des Speichers erworben wurde, werden Werte in der Regel aus diesem Speicher gelesen oder in diesen geschrieben, und es ist sehr wichtig, dass diese Lese- und Schreibvorgänge nach dem Erwerb des Besitzes ausgeführt werden. Eine Lese-Erwerb-Barriere garantiert dies.

Wenn der Besitz eines Speichers freigegeben wird, entweder durch Freigeben einer Sperre oder durch Pushen eines Elements an eine freigegebene verknüpfte Liste, ist immer ein Schreibvorgang beteiligt, der andere Threads benachrichtigt, dass der Speicher jetzt für sie verfügbar ist. Während Ihr Code über den Besitz des Speichers verfügte, liest er wahrscheinlich aus dem Speicher oder schrieb in ihm, und es ist sehr wichtig, dass diese Lese- und Schreibvorgänge ausgeführt werden, bevor sie den Besitz freigeben. Eine Schreibschutzbarriere garantiert dies.

Es ist am einfachsten, sich Lese- und Schreibschutzbarrieren als einzelne Vorgänge zu vorstellen. Manchmal müssen sie jedoch aus zwei Teilen bestehen: einem Lese- oder Schreibzugriff und einer Barriere, die das Überschreiten von Lese- oder Schreibzugriffen verhindert. In diesem Fall ist die Platzierung der Barriere kritisch. Bei einer Lese-Erwerb-Barriere kommt das Lesen der Kennzeichnung zuerst, dann die Barriere und dann die Lese- und Schreibvorgänge der freigegebenen Daten. Bei einer Schreibschutzbarriere werden die Lese- und Schreibvorgänge der freigegebenen Daten zuerst, dann die Barriere und dann das Schreiben der Kennzeichnung erfolgen.

// Read that acquires the data.
if( g_flag )
{
    // Guarantee that the read of the flag executes before
    // all reads and writes that follow in program order.
    BarrierOfSomeSort();

    // Now we can read and write the shared data.
    int localVariable = sharedData.y;
    sharedData.x = 0;

    // Guarantee that the write to the flag executes after all
    // reads and writes that precede it in program order.
    BarrierOfSomeSort();
    
    // Write that releases the data.
    g_flag = false;
}

Der einzige Unterschied zwischen lese- und schreibgeschützter Sperre ist der Speicherort der Speicherbarriere. Bei einem Lesezugriff erfolgt die Sperrung nach dem Sperrvorgang, bei einer Schreibfreigabe davor. In beiden Fällen befindet sich die Barriere zwischen den Verweisen auf den gesperrten Speicher und den Verweisen auf die Sperre.

Um zu verstehen, warum Barrieren sowohl beim Abrufen als auch beim Freigeben von Daten erforderlich sind, ist es am besten (und am genauesten), diese Barrieren als Garantie für die Synchronisierung mit gemeinsam genutztem Speicher und nicht mit anderen Prozessoren zu betrachten. Wenn ein Prozessor eine Schreibfreigabe verwendet, um eine Datenstruktur für gemeinsam genutzten Speicher freizugeben, und ein anderer Prozessor verwendet einen Lesezugriff auf diese Datenstruktur aus freigegebenem Speicher, funktioniert der Code dann ordnungsgemäß. Wenn der Prozessor die entsprechende Barriere nicht verwendet, schlägt die Datenfreigabe möglicherweise fehl.

Die Verwendung der richtigen Barriere, um die Compiler- und CPU-Neuanordnung für Ihre Plattform zu verhindern, ist wichtig.

Einer der Vorteile der Verwendung der vom Betriebssystem bereitgestellten Synchronisierungsgrundtypen besteht darin, dass alle die entsprechenden Speicherbarrieren enthalten.

Verhindern der Neuanordnung des Compilers

Der Auftrag eines Compilers besteht darin, Ihren Code aggressiv zu optimieren, um die Leistung zu verbessern. Dazu gehört das Neuanordnen von Anweisungen, wo es hilfreich ist und wo sich das Verhalten nicht ändert. Da der C++-Standard niemals Multithreading erwähnt, und da der Compiler nicht weiß, welcher Code threadsicher sein muss, geht der Compiler davon aus, dass ihr Code single-threaded ist, wenn er entscheidet, welche Neuanordnungen es sicher ausführen kann. Daher müssen Sie dem Compiler mitteilen, wann es nicht erlaubt ist, Lese- und Schreibvorgänge neu anzuordnen.

Mit Visual C++ können Sie die Neuanordnung des Compilers mithilfe der systeminternen _ReadWriteBarrier des Compilers verhindern. Wenn Sie _ReadWriteBarrier in Ihren Code einfügen, überträgt der Compiler keine Lese- und Schreibvorgänge.

#if _MSC_VER < 1400
    // With VC++ 2003 you need to declare _ReadWriteBarrier
    extern "C" void _ReadWriteBarrier();
#else
    // With VC++ 2005 you can get the declaration from intrin.h
#include <intrin.h>
#endif
// Tell the compiler that this is an intrinsic, not a function.
#pragma intrinsic(_ReadWriteBarrier)

// Create a new sprite by filling in a previously empty entry.
g_sprites[nextSprite].x = x;
g_sprites[nextSprite].y = y;
// Write-release, barrier followed by write.
// Guarantee that the compiler leaves the write to the flag
// after all reads and writes that precede it in program order.
_ReadWriteBarrier();
g_sprites[nextSprite].alive = true;

Im folgenden Code liest ein anderer Thread aus dem Sprite-Array:

// Draw all sprites.
for( int i = 0; i < numSprites; ++i )
{

    // Read-acquire, read followed by barrier.
    if( g_sprites[nextSprite].alive )
    {
    
        // Guarantee that the compiler leaves the read of the flag
        // before all reads and writes that follow in program order.
        _ReadWriteBarrier();
        DrawSprite( g_sprites[nextSprite].x,
                g_sprites[nextSprite].y );
    }
}

Es ist wichtig zu verstehen, dass _ReadWriteBarrier keine zusätzlichen Anweisungen einfügt, und sie verhindert nicht, dass die CPU Lese- und Schreibvorgänge neu anordnen kann – sie verhindert nur, dass der Compiler sie neu anordnen kann. Daher ist _ReadWriteBarrier ausreichend, wenn Sie eine Schreibsperre auf x86 und x64 implementieren (da x86 und x64 Schreibvorgänge nicht neu anordnen und ein normaler Schreibzugriff für die Freigabe einer Sperre ausreicht), aber in den meisten anderen Fällen ist es auch erforderlich, die CPU daran zu hindern, Lese- und Schreibvorgänge neu anzuordnen.

Sie können auch _ReadWriteBarrier verwenden, wenn Sie in nicht zwischengespeicherten schreibgeschützten Arbeitsspeicher schreiben, um die Neuanordnung von Schreibvorgängen zu verhindern. In diesem Fall hilft _ReadWriteBarrier, die Leistung zu verbessern, indem sichergestellt wird, dass die Schreibvorgänge in der bevorzugten linearen Reihenfolge des Prozessors erfolgen.

Es ist auch möglich, die _ReadBarrier und _WriteBarrier systeminternen Elemente zur präziseren Steuerung der Compileranordnung zu verwenden. Der Compiler bewegt sich nicht über eine _ReadBarrier und es werden keine Schreibvorgänge über eine _WriteBarrier verschoben.

Verhindern der CPU-Neuanordnung

Die CPU-Neuanordnung ist dezenter als die Neuanordnung des Compilers. Man kann es nie direkt sehen, man sieht nur unerklärliche Fehler. Um die CPU-Neuanordnung von Lese- und Schreibvorgängen zu verhindern, müssen Sie Anweisungen zur Speicherbarriere für einige Prozessoren verwenden. Der allzweckbezogene Name für eine Speicherbarriere-Anweisung, auf Xbox 360 und unter Windows, ist MemoryBarrier. Dieses Makro wird für jede Plattform entsprechend implementiert.

Auf Xbox 360 wird MemoryBarrier als lwsync (einfache Synchronisierung) definiert, die auch über das systeminterne __lwsync verfügbar ist, das in ppcintrinsics.h definiert ist. __lwsync dient auch als Compilerspeicherbarriere und verhindert das Neuanordnen von Lese- und Schreibvorgängen durch den Compiler.

Die lwsync-Anweisung ist eine Speicherbarriere auf Xbox 360, die einen Prozessorkern mit dem L2-Cache synchronisiert. Es garantiert, dass alle Schreibvorgänge vor lwsync in den L2-Cache vor allen folgenden Schreibvorgängen führen. Außerdem wird sichergestellt, dass alle Lesevorgänge, die lwsync folgen, keine älteren Daten von L2 erhalten als vorherige Lesevorgänge. Der eine Typ der Neuanordnung, der nicht verhindert wird, ist ein Lesevorgang, der vor einem Schreibvorgang an eine andere Adresse wechselt. Daher erzwingt lwsync die Speicherreihenfolge, die der Standardspeicherreihenfolge auf x86- und x64-Prozessoren entspricht. Zum Abrufen der vollständigen Speicheranordnung ist die teurere Synchronisierungsanweisung (auch als Schwergewichtssynchronisierung bezeichnet) erforderlich, in den meisten Fällen ist dies jedoch nicht erforderlich. Die Optionen für die Neuanordnung des Arbeitsspeichers auf Xbox 360 sind in der folgenden Tabelle aufgeführt.

Xbox 360 Neuanordnung Keine Synchronisierung lwsync sync
Lesevorgänge, die sich vor Lesevorgängen bewegen Ja Nr. No
Schreibvorgänge, die sich vor Schreibvorgängen bewegen Ja Nr. No
Schreibvorgänge, die sich vor Lesevorgängen bewegen Ja Nr. No
Lesevorgänge, die sich vor Schreibvorgängen bewegen Ja Ja No

 

PowerPC verfügt auch über die Synchronisierungsanweisungen isync und eieio (die zur Steuerung der Neuordnung des für das Caching gesperrten Speichers verwendet wird). Diese Synchronisierungsanweisungen sollten nicht für normale Synchronisierungszwecke erforderlich sein.

Unter Windows ist MemoryBarrier in Winnt.h definiert und gibt Ihnen eine andere Speicherbarriere-Anweisung, je nachdem, ob Sie für x86 oder x64 kompilieren. Die Speicherbarriere-Anweisung dient als vollständige Barriere und verhindert die Neuanordnung von Lese- und Schreibvorgängen über die Barriere. Daher bietet MemoryBarrier unter Windows eine stärkere Neuanordnungsgarantie als auf Xbox 360.

Auf Xbox 360 und auf vielen anderen CPUs gibt es eine zusätzliche Möglichkeit, die Neuanordnung durch die CPU zu verhindern. Wenn Sie einen Zeiger lesen und dann diesen Zeiger verwenden, um andere Daten zu laden, garantiert die CPU, dass die Lesevorgänge aus dem Zeiger nicht älter sind als der Lesevorgang des Zeigers. Wenn es sich bei der Sperrkennzeichnung um einen Zeiger handelt und alle Lesevorgänge freigegebener Daten vom Zeiger entfernt sind, kann MemoryBarrier ausgelassen werden, um eine geringe Leistungsersparnis zu erzielen.

Data* localPointer = g_sharedPointer;
if( localPointer )
{
    // No import barrier is needed--all reads off of localPointer
    // are guaranteed to not be reordered past the read of
    // localPointer.
    int localVariable = localPointer->y;
    // A memory barrier is needed to stop the read of g_global
    // from being speculatively moved ahead of the read of
    // g_sharedPointer.
    int localVariable2 = g_global;
}

Die MemoryBarrier-Anweisung verhindert nur die Neuanordnung von Lese- und Schreibvorgängen in zwischenspeicherbaren Arbeitsspeicher. Wenn Sie Speicher als PAGE_NOCACHE oder PAGE_WRITECOMBINE zuweisen, hat MemoryBarrier keine Auswirkungen auf den Zugriff auf diesen Speicher, eine gängige Technik für Gerätetreiberautoren und für Spieleentwickler auf Xbox 360. Die meisten Entwickler benötigen keine Synchronisierung nicht zwischenspeicherbarer Arbeitsspeicher. Dies geht jedoch über den Rahmen dieses Artikels hinaus.

Verriegelte Funktionen und CPU-Neuanordnung

Manchmal erfolgt der Lese- oder Schreibzugriff, der eine Ressource erwirbt oder freigibt, mithilfe einer der InterlockedXxx-Funktionen. Unter Windows vereinfacht dies die Angelegenheit; da unter Windows die InterlockedXxx-Funktionen alle Vollspeicherbarrieren sind. Sie verfügen sowohl vor als auch nach ihnen über eine CPU-Speicherbarriere, was bedeutet, dass sie eine vollständige Lese- oder Schreibschutzbarriere sind.

Auf Xbox 360 enthalten die InterlockedXxx-Funktionen keine CPU-Speicherbarrieren. Sie verhindern die Neuanordnung von Lese- und Schreibvorgängen, aber keine CPU-Neuanordnung. Daher sollten Sie in den meisten Fällen bei der Verwendung von InterlockedXxx-Funktionen auf Xbox 360 ihnen eine __lwsync voranstellen oder ihnen folgen, um sie zu einer Lese- oder Schreibzugriffsbarriere zu machen. Zur Benutzerfreundlichkeit und zur besseren Lesbarkeit gibt es Acquire- und Release-Versionen vieler InterlockedXxx-Funktionen. Diese verfügen über eine integrierte Speicherbarriere. Beispielsweise führt InterlockedIncrementAcquire ein verriegeltes Inkrement gefolgt von einer __lwsync Speicherbarriere aus, um die volle Leseerfassungsfunktionalität zu gewährleisten.

Es wird empfohlen, die Acquire- und Release-Version der InterlockedXxx-Funktionen zu verwenden (die meisten sind auch unter Windows verfügbar, ohne Leistungseinbußen), um Ihre Absicht deutlicher zu machen und die Anweisungen zur Speicherbarriere an der richtigen Stelle zu erleichtern. Jede Verwendung von InterlockedXxx auf Xbox 360 ohne Speicherbarriere sollte sehr sorgfältig untersucht werden, da es sich häufig um einen Fehler handelt.

In diesem Beispiel wird veranschaulicht, wie ein Thread Aufgaben oder andere Daten mithilfe der Acquire- und Release-Version der InterlockedXxxSList-Funktionen an einen anderen Thread übergeben kann. Die InterlockedXxxSList-Funktionen sind eine Familie von Funktionen zum Verwalten einer freigegebenen, einfach verknüpften Liste ohne Sperre. Beachten Sie, dass Acquire- und Release-Varianten dieser Funktionen unter Windows nicht verfügbar sind, aber die regulären Versionen dieser Funktionen sind eine vollständige Speicherbarriere unter Windows.

// Declarations for the Task class go here.

// Add a new task to the list using lockless programming.
void AddTask( DWORD ID, DWORD data )
{
    Task* newItem = new Task( ID, data );
    InterlockedPushEntrySListRelease( g_taskList, newItem );
}

// Remove a task from the list, using lockless programming.
// This will return NULL if there are no items in the list.
Task* GetTask()
{
    Task* result = (Task*)
        InterlockedPopEntrySListAcquire( g_taskList );
    return result;
}

Veränderliche Variablen und Neuanordnung

Der C++ Standard sagt, dass Lesevorgänge von veränderliche Variablen nicht zwischengespeichert werden können, veränderliche Schreibvorgänge können nicht verzögert werden, und veränderliche Lese- und Schreibvorgänge können nicht übereinander verschoben werden. Dies reicht für die Kommunikation mit Hardwaregeräten aus, was der Zweck des veränderliche Schlüsselworts im C++-Standard ist.

Die Garantien des Standards reichen jedoch nicht aus, um veränderlich für Multithreading zu verwenden. Der C++-Standard hält den Compiler nicht davon ab, permanente Lese- und Schreibvorgänge im Verhältnis zu flüchtigen Lese- und Schreibvorgängen neu zu ordnen, und er sagt nichts darüber aus, wie die Neuordnung durch die CPU zu verhindern ist.

Visual C++ 2005 geht über den Standard C++ hinaus, um multithreadingfreundliche Semantik für den veränderlichen Variablenzugriff zu definieren. Ab Visual C++ 2005 werden Lesevorgänge von veränderlichen Variablen mit der Semantik Read-Acquire und Schreibvorgänge auf veränderliche Variablen mit der Semantik Write-Release definiert. Dies bedeutet, dass der Compiler keine Lese- und Schreibvorgänge über sie neu anordnet, und unter Windows wird sichergestellt, dass die CPU dies auch nicht tut.

Es ist wichtig zu verstehen, dass diese neuen Garantien nur für Visual C++ 2005 und zukünftige Versionen von Visual C++ gelten. Compiler von anderen Anbietern implementieren im Allgemeinen unterschiedliche Semantik, ohne die zusätzlichen Garantien von Visual C++ 2005. Außerdem fügt der Compiler auf Xbox 360 keine Anweisungen ein, um zu verhindern, dass die CPU Lese- und Schreibvorgänge neu anordnen kann.

Beispiel für eine sperrfreie Datenpipeline

Eine Pipe ist ein Konstrukt, mit dem ein oder mehrere Threads Daten schreiben können, die dann von anderen Threads gelesen werden. Eine Version ohne Sperren einer Pipe kann eine elegante und effiziente Möglichkeit sein, Arbeit von Thread zu Thread zu Thread zu übergeben. Das DirectX SDK liefert LockFreePipe, eine Single-Reader, Single-Writer Pipe ohne Sperren, die in DXUTLockFreePipe.h verfügbar ist. Das gleiche LockFreePipe ist im Xbox 360 SDK in AtgLockFreePipe.h verfügbar.

LockFreePipe kann verwendet werden, wenn zwei Threads über eine Produzenten-/Verbraucherbeziehung verfügen. Der Producer-Thread kann Daten in die Pipe schreiben, damit der Consumer-Thread zu einem späteren Zeitpunkt verarbeitet wird, ohne es zu blockieren. Wenn die Pipe voll ist, schlagen die Schreibvorgänge fehl, und der Producer-Thread muss es später erneut versuchen, aber das würde nur passieren, wenn der Producer-Thread voraus ist. Wenn die Pipe leer ist, schlägt der Lesevorgang fehl, und der Consumer-Thread muss es später erneut versuchen. Dies würde jedoch nur passieren, wenn es keine Arbeit für den Consumer-Thread gibt. Wenn die beiden Threads gut ausbalanciert sind und die Pipe groß genug ist, ermöglicht die Pipe einen reibungslosen Datenaustausch ohne Verzögerungen oder Blockierungen.

Xbox 360-Leistung

Die Leistung von Synchronisierungsanweisungen und -funktionen auf Xbox 360 hängt davon ab, welcher andere Code ausgeführt wird. Das Abrufen von Sperren dauert viel länger, wenn ein anderer Thread zurzeit die Sperre besitzt. InterlockedIncrement und kritische Abschnittsvorgänge dauern viel länger, wenn andere Threads in dieselbe Cachezeile schreiben. Der Inhalt der Speicherwarteschlangen kann sich auch auf die Leistung auswirken. Daher sind alle diese Zahlen nur Annäherungen, die aus sehr einfachen Tests generiert werden:

  • lwsync wurde als 33-48 Zyklen gemessen.
  • InterlockedIncrement wurde als 225-260 Zyklen gemessen.
  • Das Abrufen oder Freigeben eines kritischen Abschnitts wurde gemessen, da etwa 345 Zyklen berücksichtigt wurden.
  • Das Abrufen oder Freigeben eines Mutex wurde als 2350 Zyklen gemessen.

Windows-Leistung

Die Leistung von Synchronisierungsanweisungen und -funktionen unter Windows variiert stark je nach Prozessortyp und Konfiguration und davon, welcher andere Code ausgeführt wird. Multi-Core- und Multi-Socket-Systeme dauern häufig länger, um Synchronisierungsanweisungen auszuführen, und das Abrufen von Sperren dauert viel länger, wenn ein anderer Thread derzeit die Sperre besitzt.

Aber auch einige Messungen, die aus sehr einfachen Tests generiert wurden, sind hilfreich:

  • MemoryBarrier wurde als 20-90 Zyklen gemessen.
  • InterlockedIncrement wurde als 36-90 Zyklen gemessen.
  • Das Abrufen oder Freigeben eines kritischen Abschnitts wurde gemessen, da etwa 40-100 Zyklen berücksichtigt wurden.
  • Das Abrufen oder Freigeben eines Mutex wurde als 750-2500 Zyklen gemessen.

Diese Tests wurden unter Windows XP auf einer Reihe verschiedener Prozessoren durchgeführt. Die kurzen Zeiten waren auf einem Single-Processor-Computer, und die längeren Zeiten waren auf einem Multiprozessorcomputer.

Während das Abrufen und Freigeben von Sperren teurer ist als die Verwendung der sperrlosen Programmierung, ist es sogar besser, Daten weniger häufig freizugeben, wodurch die Kosten insgesamt vermieden werden.

Überlegungen zur Leistung

Das Abrufen oder Freigeben eines kritischen Abschnitts besteht aus einer Speicherbarriere, einem InterlockedXxx-Vorgang und einer zusätzlichen Überprüfung zur Behandlung der Rekursion und zum Zurückwechseln auf einen Mutex, falls erforderlich. Sie sollten vorsichtig sein, wenn Sie einen eigenen kritischen Abschnitt implementieren, denn wenn Sie in einer Schleife darauf warten, dass eine Sperre frei wird, ohne auf einen Mutex zurückzugreifen, kann dies zu erheblichen Leistungseinbußen führen. Bei kritischen Abschnitten, die stark behauptet, aber nicht lange gehalten werden, sollten Sie die Verwendung von InitializeCriticalSectionAndSpinCount in Betracht ziehen, damit das Betriebssystem eine Weile auf die Verfügbarkeit des kritischen Abschnitts wartet, anstatt sofort auf einen Mutex zurückzuweisen, wenn der kritische Abschnitt im Besitz ist, wenn Sie versuchen, ihn zu erhalten. Um kritische Abschnitte zu identifizieren, die von einer Drehzahl profitieren können, ist es notwendig, die Länge der typischen Wartezeit für eine bestimmte Sperre zu messen.

Wenn ein gemeinsam genutzter Heap für Speicherzuweisungen verwendet wird – das ist das Standardverhalten –, muss bei jeder Speicherzuweisung und -freigabe eine Sperre erworben werden. Wenn die Anzahl der Threads und der Zuordnungen steigt, nimmt die Leistung ab und verringert sich schließlich. Die Verwendung von Thread-Heaps oder das Verringern der Anzahl von Zuordnungen kann diesen Sperrengpässe vermeiden.

Wenn ein Thread Daten generiert und ein anderer Thread Daten verbraucht, können sie häufig Daten freigeben. Dies kann passieren, wenn ein Thread Ressourcen lädt und ein anderer Thread die Szene rendert. Wenn der Rendering-Thread bei jedem Zeichenaufruf auf die gemeinsam genutzten Daten verweist, ist der Sperr-Overhead hoch. Eine wesentlich bessere Leistung kann erzielt werden, wenn jeder Thread über private Datenstrukturen verfügt, die dann einmal pro Frame oder weniger synchronisiert werden.

Sperrlose Algorithmen sind nicht garantiert schneller als Algorithmen, die Sperren verwenden. Überprüfen Sie, ob Sperren tatsächlich Probleme verursachen, bevor Sie versuchen, sie zu vermeiden, und Sie sollten messen, ob der Code ohne Sperren tatsächlich die Leistung verbessert.

Zusammenfassung der Plattformunterschiede

  • InterlockedXxx-Funktionen verhindern die Neuanordnung von CPU-Lese-/Schreibzugriff unter Windows, aber nicht auf Xbox 360.
  • Das Lesen und Schreiben von veränderliche Variablen mit Visual Studio C++ 2005 verhindert die Neuanordnung von CPU-Lese-/Schreibzugriff unter Windows, aber auf Xbox 360 verhindert die Neuanordnung des Compilers mit Lese-/Schreibzugriff.
  • Schreibvorgänge werden auf Xbox 360 neu angeordnet, jedoch nicht auf x86 oder x64.
  • Lesevorgänge werden auf Xbox 360 neu angeordnet, aber auf x86 oder x64 werden sie nur relativ zu Schreibvorgängen neu angeordnet, und nur, wenn die Lese- und Schreibvorgänge auf unterschiedliche Speicherorte ausgerichtet sind.

Empfehlungen

  • Verwenden Sie Sperren, wenn möglich, da sie einfacher zu verwenden sind.
  • Vermeiden Sie zu häufiges Sperren, damit die Sperrkosten nicht zu hoch werden.
  • Vermeiden Sie es, die Sperren zu lange zu halten, um einen langen Stillstand zu vermeiden.
  • Verwenden Sie bei Bedarf Programmierung ohne Sperren, aber stellen Sie sicher, dass die Vorteile die Komplexität rechtfertigen.
  • Verwenden Sie Programmierung ohne Sperren oder Drehsperren in Situationen, in denen andere Sperren verboten sind, z. B. beim Freigeben von Daten zwischen verzögerten Prozeduraufrufen und normalem Code.
  • Verwenden Sie nur Standard-Lockless-Programmieralgorithmen, die als korrekt erwiesen wurden.
  • Achten Sie beim Programmieren ohne Sperren darauf, bei Bedarf veränderliche Flag-Variablen und Speicherbarrieren-Anweisungen zu verwenden.
  • Verwenden Sie bei Verwendung von InterlockedXxx auf Xbox 360 die Acquire- und Release-Varianten.

References