Überlegungen zur blockierfreien Programmierung für Xbox 360 und Microsoft Windows
Die sperrlose Programmierung ist eine Möglichkeit, sich ändernde Daten sicher zwischen mehreren Threads freizugeben, ohne die Kosten für das Abrufen und Freigeben von Sperren zu tragen. Dies klingt wie eine Sperre, aber die sperrlose Programmierung ist komplex und dezent und bietet manchmal nicht die Vorteile, die sie zusichert. Die sperrlose Programmierung ist bei Xbox 360 besonders komplex.
Die sperrlose Programmierung ist ein gültiges Verfahren für die Multithreadprogrammierung, sollte aber nicht einfach verwendet werden. Bevor Sie es verwenden, müssen Sie die Komplexität verstehen, und Sie sollten sorgfältig messen, um sicherzustellen, dass sie Ihnen tatsächlich die erwarteten Vorteile bietet. In vielen Fällen gibt es einfachere und schnellere Lösungen, z. B. die seltenere Freigabe von Daten, die stattdessen verwendet werden sollten.
Die ordnungsgemäße und sichere Verwendung der sperrlosen Programmierung erfordert umfassende Kenntnisse sowohl ihrer Hardware als auch Ihres Compilers. Dieser Artikel bietet eine Übersicht über einige der Probleme, die beim Versuch, sperrlose Programmiertechniken zu verwenden, zu berücksichtigen sind.
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, kann es zu Speicherbeschädigungen kommen. Die einfachste Möglichkeit, dieses Problem zu lösen, ist die Verwendung von Sperren. Wenn ManipulatSharedData z. B. nur von einem Thread gleichzeitig ausgeführt werden soll, kann ein CRITICAL _ SECTION verwendet werden, um dies zu gewährleisten, wie im folgenden Code:
// Initialize
CRITICAL_SECTION cs;
InitializeCriticalSection(&cs);
// Use
void ManipulateSharedData()
{
EnterCriticalSection(&cs);
// Manipulate stuff...
LeaveCriticalSection(&cs);
}
// Destroy
DeleteCriticalSection(&cs);
Dieser Code ist recht einfach und unkompliziert, und es ist leicht zu erkennen, dass er richtig ist. Die Programmierung mit Sperren hat jedoch mehrere potenzielle Nachteile. Wenn z. B. zwei Threads versuchen, die gleichen beiden Sperren abzurufen, sie jedoch in einer anderen Reihenfolge abzurufen, erhalten Sie möglicherweise einen Deadlock. Wenn ein Programm zu lange eine Sperre aufhält – aufgrund eines schlechten Entwurfs oder weil der Thread durch einen Thread mit höherer Priorität ausgetauscht wurde – können andere Threads für einen längeren Zeitraum blockiert werden. Dieses Risiko ist besonders groß bei Xbox 360 da den Softwarethreads vom Entwickler ein Hardwarethread zugewiesen wird und das Betriebssystem sie nicht in einen anderen Hardwarethread verschieben wird, auch wenn sich einer im Leerlauf befindet. Die Xbox 360 bietet auch keinen Schutz vor Prioritätsumkehr, bei der ein Thread mit hoher Priorität in einer Schleife gedreht wird, während darauf gewartet wird, dass ein Thread mit niedriger Priorität eine Sperre freigibt. Wenn ein verzögerter Prozeduraufruf oder eine Unterbrechungsdienstroutine versucht, eine Sperre abzurufen, kann es schließlich zu einem Deadlock kommen.
Trotz dieser Probleme sind Synchronisierungsprimitiven, wie z. B. kritische Abschnitte, im Allgemeinen die beste Möglichkeit, mehrere Threads zu koordinieren. Wenn die Synchronisierungsprimitiven zu langsam sind, besteht die beste Lösung in der Regel darin, sie seltener zu verwenden. Für diejenigen, die sich die zusätzliche Komplexität leisten können, ist eine weitere Option die sperrenlose Programmierung.
Sperrenlose Programmierung
Die sperrlose Programmierung ist, wie der Name schon sagt, eine Reihe von Techniken zum sicheren Bearbeiten freigegebener Daten ohne Verwendung von Sperren. Es stehen sperrenlose Algorithmen zum Übergeben von Nachrichten, freigeben von Listen und Warteschlangen von Daten und anderen Aufgaben zur Verfügung.
Bei der sperrlosen Programmierung gibt es zwei Herausforderungen, mit denen Sie umgehen müssen: nicht atomische Vorgänge und Neuanordnung.
Nicht atomische Vorgänge
Ein atomarer Vorgang ist ein unteilbarer Vorgang, bei dem andere Threads den Vorgang garantiert nie sehen, wenn er halbiert ist. Atomare Vorgänge sind wichtig für die sperrlose Programmierung, da ohne sie andere Threads möglicherweise halb geschriebene Werte oder einen anderweitig inkonsistenten Zustand sehen.
Auf allen modernen Prozessoren können Sie davon ausgehen, dass Lese- und Schreibvorgänge von natürlich ausgerichteten nativen Typen atomar sind. Solange der Speicherbus mindestens so breit wie der gelesene oder geschriebene Typ ist, liest und schreibt die CPU diese Typen in einer einzelnen Bustransaktion, sodass andere Threads sie nicht in einem halb abgeschlossenen Zustand sehen können. Auf x86 und x64 gibt es keine Garantie dafür, dass Lese- und Schreibvorgänge, die größer als acht Bytes sind, atomar sind. Dies bedeutet, dass 16-Byte-Lese- und Schreibvorgänge von SSE-Registern (Streaming SIMD Extension) und Zeichenfolgenvorgängen möglicherweise nicht atomar sind.
Lese- und Schreibvorgänge von Typen, die nicht natürlich ausgerichtet sind , z. B. das Schreiben von DWORDs, die vier Byte-Grenzen überschreiten, sind nicht garantiert atomar. Die CPU muss diese Lese- und Schreibvorgänge möglicherweise als mehrere Bustransaktionen durchführen, sodass ein anderer Thread die Daten während des Lese- oder Schreibvorgangs ändern oder anzeigen kann.
Zusammengesetzte Vorgänge, z. B. die Sequenz mit Lese-/Änderungs-/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 kann teilweise durch die Sequenz getauscht werden. Bei x86 und x64 gibt es eine einzelne Anweisung (inc), mit der eine Variable im Arbeitsspeicher erhöht werden kann. Wenn Sie diese Anweisung verwenden, ist das Inkrementieren einer Variablen auf Einzelprozessorsystemen atomar, bei Systemen mit mehreren Prozessoren jedoch immer noch nicht atomar. Um Inc auf x86- und x64-basierten Multiprozessorsystemen atomar zu machen, ist die Verwendung des Sperrpräfixes erforderlich, wodurch verhindert wird, dass ein anderer Prozessor eine eigene Lese-/Änderungs-/Schreibsequenz zwischen dem Lese- und dem Schreibvorgang der inc-Anweisung vornimmt.
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;
Gewährleisten der Atomarität
Sie können sicher sein, dass Sie atomare Vorgänge verwenden, indem Sie folgende Kombinationen verwenden:
- Natürlich atomare Vorgänge
- Sperren zum Umschließen zusammengesetzter Vorgänge
- Betriebssystemfunktionen, die atomare Versionen gängiger zusammengesetzter Vorgänge implementieren
Das Erhöhen einer Variablen ist kein atomarer Vorgang, 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 atomare Lese-/Änderungs-/Schreibversionen mehrerer gängiger Vorgänge bieten. Dies sind die Funktionen der InterlockedXxx-Familie. Wenn alle Änderungen der freigegebenen Variablen diese Funktionen verwenden, sind die Änderungen threadsicher.
// Incrementing our variable in a safe lockless way.
InterlockedIncrement(&g_globalCounter);
Neuanordnen
Ein feinerer Problem ist die Neuanordnung. Lese- und Schreibvorgänge erfolgen nicht immer in der Reihenfolge, in der Sie sie in Ihrem Code geschrieben haben. Dies kann zu sehr verwirrenden Problemen führen. In vielen Multithreadalgorithmen schreibt ein Thread einige Daten und dann in ein Flag, das andere Threads darüber informiert, dass die Daten bereit sind. Dies wird als Schreibversion bezeichnet. Wenn die Schreibvorgänge neu angeordnet werden, sehen andere Threads möglicherweise, dass das Flag festgelegt ist, bevor sie die geschriebenen Daten sehen können.
Auf ähnliche Weise 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 erhalten hat. Dies wird als Lese-/Erwerb bezeichnet. Wenn Lesefunktionen neu angeordnet werden, werden die Daten möglicherweise vor dem Flag aus dem freigegebenen Speicher 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 durchgeführt werden. Compiler und Prozessoren haben diese Neuanordnung seit Jahren durchgeführt, aber auf Einzelprozessorcomputern war dies weniger ein Problem. Dies liegt daran, dass die CPU-Neusortierung von Lese- und Schreibvorgängen auf Computern mit nur einem Prozessor nicht sichtbar ist (für Nicht-Gerätetreibercode, der nicht Teil eines Gerätetreibers ist), und die Neusortierung von Lese- und Schreibvorgängen durch den Compiler weniger wahrscheinlich Probleme auf Computern mit nur einem Prozessor verursacht.
Wenn der Compiler oder die CPU die im folgenden Code gezeigten Schreibvorgänge neu anordnt, kann ein anderer Thread sehen, dass das Alive-Flag festgelegt ist, während weiterhin die alten Werte für x oder y angezeigt werden. Eine ähnliche Neuordnung kann beim Lesen erfolgen.
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 compiler- als auch CPU-Neuanordnung von Lese- und Schreibvorgängen verhindern.
Grundlegendes zur CPU-Neusortierung von Schreibvorgängen
Einige CPUs ordnen Schreibvorgänge neu an, sodass sie extern für andere Prozessoren oder Geräte in nicht programmbasierter Reihenfolge sichtbar sind. Diese Neuordnung ist für Singlethreadcode, der nicht treiberseitig ist, nie sichtbar, kann jedoch Probleme in Multithreadcode verursachen.
Xbox 360
Während die Xbox 360 CPU Keine Anweisungen neu anordnt, ordnet sie Schreibvorgänge neu an, die nach den Anweisungen selbst abgeschlossen werden. Diese Neuordnung von Schreibvorgängen wird speziell vom PowerPC Speichermodell zugelassen.
Schreibvorgänge in Xbox 360 werden nicht direkt in den L2-Cache übertragen. Um die Schreibbandbreite des L2-Caches zu verbessern, durchlaufen sie stattdessen Speicherwarteschlangen und dann Puffer zum Speichern und Sammeln. Die Speicher-Gather-Puffer ermöglichen das Schreiben von 64-Byte-Blöcken in den L2-Cache in einem Vorgang. Es gibt acht Speicher-Gather-Puffer, die effizientes Schreiben in mehrere verschiedene Speicherbereiche ermöglichen.
Die Speicher-Gather-Puffer werden normalerweise in FIFO-Reihenfolge (First In First Out) in den L2-Cache geschrieben. Wenn sich die Zielcachezeile eines Schreibzugriffs jedoch nicht im L2-Cache befindet, kann dieser Schreibvorgang verzögert werden, während die Cachezeile aus dem Arbeitsspeicher abgerufen wird.
Selbst wenn die Speicher-Gather-Puffer in strikter FIFO-Reihenfolge in den L2-Cache geschrieben werden, garantiert dies nicht, dass einzelne Schreibvorgänge in der reihenfolge in den L2-Cache geschrieben werden. Stellen Sie sich z. B. vor, dass die CPU an den Speicherort 0x1000 schreibt, dann an den Speicherort 0x2000 und dann an den Speicherort 0x1004. Beim ersten Schreibvorgang wird ein Speicher-Gather-Puffer zugeordnet und am Anfang der Warteschlange abgelegt. Der zweite Schreibvorgang ordnet einen weiteren Speicher-Gather-Puffer zu und fügt ihn als Nächstes in die Warteschlange ein. Der dritte Schreibvorgang fügt seine Daten dem ersten Speicher-Gather-Puffer hinzu, der am Anfang der Warteschlange verbleibt. Daher wird der dritte Schreibvorgang vor dem zweiten Schreibvorgang in den L2-Cache übertragen.
Die neu angeordnete Reihenfolge, die durch Speicher-Gather-Puffer verursacht wird, ist grundsätzlich unvorhersehbar, insbesondere, weil beide Threads auf einem Kern die Speicher-Gather-Puffer gemeinsam nutzen, sodass die Zuordnung und das Leeren der Speicher-Gather-Puffer stark variabel sind.
Dies ist ein Beispiel dafür, wie Schreibvorgänge neu angeordnet werden können. Es gibt möglicherweise noch weitere Möglichkeiten.
x86 und x64
Obwohl x86- und x64-CPUs Anweisungen neu anordnen, werden Schreibvorgänge im Allgemeinen nicht im Vergleich zu anderen Schreibvorgängen neu angeordnet. Es gibt einige Ausnahmen für den kombinierten Schreibspeicher. Darüber hinaus können Zeichenfolgenvorgänge (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-Neuordnung von Lesefunktionen
Einige CPUs ordnen Lesefunktionen neu an, sodass sie effektiv aus freigegebenen Speicher in nicht programmbasierter Reihenfolge stammen. Diese Neuordnung ist für Singlethreadcode ohne Treiber nie sichtbar, kann aber Probleme im Multithreadcode verursachen.
Xbox 360
Cachefehler können dazu führen, dass einige Lesezugriffe verzögert werden. Dies führt effektiv dazu, dass Lesezugriffe aus dem freigegebenen Speicher nicht in der richtigen Reihenfolge erfolgen, und der Zeitpunkt dieser Cachefehler ist grundsätzlich unvorhersehbar. Das Vorabrufen und die Verzweigungsvorhersage können auch dazu führen, dass Daten aus dem freigegebenen Speicher nicht in der reihenfolgengeordneten Reihenfolge stammen. Dies sind nur einige Beispiele dafür, wie Lesefunktionen neu angeordnet werden können. Es gibt möglicherweise noch weitere Möglichkeiten. Diese Neuordnung von Lese- und Schreib schreibgeschützten Lesefunktionen wird vom PowerPC Speichermodells ausdrücklich zugelassen.
x86 und x64
Obwohl x86- und x64-CPUs Anweisungen neu anordnen, ordnen sie Lesevorgänge im Allgemeinen nicht im Vergleich zu anderen Lesevorgängen neu an. Zeichenfolgenvorgänge (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. Insbesondere wenn ein Programm an einen Speicherort schreibt, auf den das Lesen von einem anderen Speicherort folgt, können die gelesenen Daten aus dem freigegebenen Speicher stammen, bevor die geschriebenen Daten dort abgelegt werden. Diese Neuanordnung kann einige Algorithmen unterbrechen, z. B. die Algorithmen für gegenseitigen Ausschluss von Dekker. Im Dekker-Algorithmus legt jeder Thread ein Flag fest, um anzugeben, dass er in den kritischen Bereich eintreten möchte, und überprüft dann das Flag des anderen Threads, um festzustellen, ob sich der andere Thread in der kritischen Region befindet oder versucht, ihn einzugeben. Der erste 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 freigegebenen Speicher lesen kann, bevor der Schreibvorgang in f0 in den freigegebenen Speicher erfolgt. In der Zwischenzeit kann der Lesevorgang von f0 in P1Acquire aus freigegebenen Speicher lesen, bevor der Schreibvorgang in f1 in den freigegebenen Speicher übergibt. Der Effekt ist, dass beide Threads ihre Flags auf TRUE festlegen und beide Threads das Flag des anderen Threads als FALSE sehen, sodass beide in den kritischen Bereich gelangen. Daher sind Probleme bei der Neuanordnung auf x86- und x64-basierten Systemen weniger häufig als bei Xbox 360, aber sie können definitiv trotzdem auftreten. Der Dekker-Algorithmus funktioniert auf keiner dieser Plattformen ohne Hardware-Speicherbarrieren.
x86- und x64-CPUs ordnen einen Schreibvorgang vor einem vorherigen Lesevorgang nicht neu an. x86- und x64-CPUs ordnen Lesevorgänge nur vor vorherigen Schreibvorgängen neu an, wenn sie auf verschiedene 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 verschiedenen Adressen befinden.
Zusammenfassung der Neuanordnung
Die Xbox 360 CPU ordnet Speichervorgänge wesentlich aggressiver an als x86- und x64-CPUs, wie in der folgenden Tabelle gezeigt. Weitere Informationen finden Sie in der Prozessordokumentation.
| Neuanordnungsaktivität | x86 und x64 | Xbox 360 |
|---|---|---|
| Lesefunktionen, die lesebewegt sind | Nein | Ja |
| Schreibvorgänge, die vor Schreibvorgängen vorangehen | Nein | Ja |
| Schreibvorgänge, die Lesevorgängen voraus sind | Nein | Ja |
| Lesevorgänge vor Schreibvorgängen | Ja | Ja |
Read-Acquire und Write-Release Barriers
Die wichtigsten Konstrukte, die verwendet werden, um das Neuanordnen von Lese- und Schreibvorgängen zu verhindern, werden als Barrieren für Lese-/ Lese- und Schreibvorgänge bezeichnet. Ein Lese-/Erwerb ist ein Lesen eines Flags oder einer anderen Variablen, um den Besitz einer Ressource zu erlangen, gekoppelt mit einer Barriere gegen neu angeordnete Elemente. Ebenso ist ein Write-Release ein Schreibvorgang eines Flags oder einer anderen Variablen, um den Besitz einer Ressource zu vererben, gekoppelt mit einer Barriere gegen die Neuanordnung.
Die formalen Definitionen von Herb Sutter sind:
- Ein Lese-/Lesezugriff wird ausgeführt, bevor alle Lese- und Schreibvorgänge von demselben Thread ausgeführt werden, der ihm in Programmreihenfolge folgt.
- Ein Write-Release wird ausgeführt, nachdem alle Lese- und Schreibvorgänge durch denselben Thread ausgeführt wurden, der ihm in Programmreihenfolge vorangeht.
Wenn Ihr Code den Besitz eines Bestimmten Arbeitsspeichers übernimmt, entweder durch Abrufen einer Sperre oder durch Ziehen eines Elements aus einer freigegebenen verknüpften Liste (ohne Sperre), ist immer ein Leseaufwand erforderlich– das Testen eines Flags oder Zeigers, um festzustellen, ob der Besitz des Arbeitsspeichers abgerufen wurde. Dieser Lesevorgang kann Teil eines InterlockedXxx-Vorgangs sein. In diesem Fall umfasst er sowohl einen Lese- als auch einen Schreibvorgang, aber es ist der Lesevorgang, der angibt, ob der Besitz erlangt wurde. Nachdem der Besitz des Arbeitsspeichers erworben wurde, werden Werte in der Regel aus diesem Arbeitsspeicher gelesen oder in diesen Speicher geschrieben. Es ist sehr wichtig, dass diese Lese- und Schreibvorgänge nach dem Erwerb des Besitzes ausgeführt werden. Dies wird durch eine Lese-/Erwerb-Barriere garantiert.
Wenn der Besitz eines Arbeitsspeichers freigegeben wird, entweder durch Freigeben einer Sperre oder durch Pushen eines Elements in eine freigegebene verknüpfte Liste, ist immer ein Schreibvorgang beteiligt, der andere Threads benachrichtigt, dass der Arbeitsspeicher jetzt für sie verfügbar ist. Während Ihr Code besitzer des Arbeitsspeichers war, hat er wahrscheinlich aus ihm gelesen oder in ihn geschrieben, und es ist sehr wichtig, dass diese Lese- und Schreibvorgänge ausgeführt werden, bevor der Besitz freigegeben wird. Dies wird durch eine Barriere für Schreib-/Freigaben garantiert.
Es ist am einfachsten, sich Barrieren für Lese- und Schreibzugriff als einzelne Vorgänge zu vorstellen. Manchmal müssen sie jedoch aus zwei Teilen erstellt werden: einem Lese- oder Schreibvorgang und einer Barriere, die es nicht zulässt, dass Lese- oder Schreibvorgänge darauf verschoben werden können. In diesem Fall ist die Platzierung der Barriere entscheidend. Bei einer Barriere mit Lese-/Lesezugriff wird zuerst das Flag gelesen, dann die Barriere und dann die Lese- und Schreibvorgänge der freigegebenen Daten. Bei einer Schreib-/Freigabebarriere werden zuerst die Lese- und Schreibvorgänge der freigegebenen Daten, dann die Barriere und dann der Schreibvorgang des Flags verwendet.
// 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 einem Lese-/Lesezugriff und einem Write-Release ist die Position der Speicherbarriere. Ein Lese-/Lesezugriff verfügt nach dem Sperrvorgang über die Barriere, und eine Schreibfreigabe verfügt über die Barriere vorher. 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 präziser), sich diese Barrieren als Garantie für die Synchronisierung mit gemeinsam genutzten Speicher und nicht mit anderen Prozessoren zu vorstellen. Wenn ein Prozessor eine Schreibfreigabe verwendet, um eine Datenstruktur im freigegebenen Arbeitsspeicher freizugeben, und ein anderer Prozessor einen Lese-/Abrufvorgang verwendet, um aus dem freigegebenen Speicher auf diese Datenstruktur zuzugreifen, funktioniert der Code ordnungsgemäß. Wenn keiner der Prozessoren die entsprechende Barriere verwendet, kann die Datenfreigabe fehlschlagen.
Es ist wichtig, die richtige Barriere zu verwenden, um eine Neuanordnung des Compilers und der CPU für Ihre Plattform zu verhindern.
Einer der Vorteile der Verwendung der vom Betriebssystem bereitgestellten Synchronisierungsprimitiven 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. Dies schließt das Neuanordnen von Anweisungen ein, wo immer dies hilfreich ist und an welchen Stellen sich das Verhalten nicht ändert. Da der C++-Standard multithreading nie erwähnt und der Compiler nicht weiß, welcher Code threadsicher sein muss, geht der Compiler davon aus, dass Ihr Code singlethreading ist, wenn er entscheidet, welche Neuordnungen er sicher durchführen kann. Daher müssen Sie dem Compiler mitteilen, wann es nicht zulässig ist, Lese- und Schreibvorgänge neu anzuordnen.
Mit Visual C++ können Sie die Neuanordnung des Compilers verhindern, indem Sie den systeminternen _ Compiler ReadWriteBarrierverwenden. Wenn Sie _ ReadWriteBarrier in Ihren Code einfügen, wird der Compiler keine Lese- und Schreibvorgänge darin verschieben.
#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 die CPU nicht daran hindert, Lese- und Schreibvorgänge neu zu anordnen– sie verhindert nur, dass der Compiler sie neu anordnen kann. Daher ist _ ReadWriteBarrier ausreichend, wenn Sie eine Schreibfreigabebarriere für x86 und x64 implementieren (da x86 und x64 keine Schreibvorgänge neu anordnen und ein normaler Schreibvorgang zum Freigeben einer Sperre ausreicht), aber in den meisten anderen Fällen ist es auch notwendig, zu verhindern, dass die CPU Lese- und Schreibvorgänge neu anordnt.
Sie können _ readWriteBarrier auch verwenden, wenn Sie in nicht zwischenspeicherbaren kombinierten Schreibspeicher schreiben, um eine Neuanordnung von Schreibvorgängen zu verhindern. In diesem Fall trägt _ ReadWriteBarrier zur Verbesserung der Leistung bei, indem sichergestellt wird, dass die Schreibvorgänge in der bevorzugten linearen Reihenfolge des Prozessors erfolgen.
Es ist auch möglich, die intrinsischen _ Funktionen ReadBarrier und _ WriteBarrier zu verwenden, um die Neuanordnung des Compilers präziser zu steuern. Der Compiler bewegt Keine Lesevorgänge über einen _ ReadBarrier und keine Schreibvorgänge über einen _ WriteBarrier.
Verhindern der Neuanordnung der CPU
Die Neuanordnung der CPU ist feiner als die Neuanordnung des Compilers. Sie können es nie direkt sehen, Sie sehen nur unerklärliche Fehler. Um eine CPU-Neuanordnung von Lese- und Schreibvorgängen zu verhindern, müssen Sie Speicherbarrierenanweisungen auf einigen Prozessoren verwenden. Der Allzweckname für eine Speicherbarrierenanweisung auf Xbox 360 und auf Windows ist MemoryBarrier. Dieses Makro wird für jede Plattform entsprechend implementiert.
Auf Xbox 360 ist MemoryBarrier als lwsync (lightweight sync) definiert und auch über die systeminterne _ _ lwsync-Synchronisierung verfügbar, die in ppimptrinsics.h definiert ist. _ _ lwsync dient auch als Speicherbarriere des Compilers und verhindert das Neuordnen 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 wird sichergestellt, dass alle Schreibvorgänge vor lwsync vor den nachfolgenden Schreibvorgängen in den L2-Cache übertragen werden. Außerdem wird sichergestellt, dass alle Lesefunktionen, die auf lwsync folgen, keine älteren Daten von L2 als vorherige Lesefunktionen erhalten. Die einzige Art der Neuanordnung, die nicht verhindert wird, ist ein Lesevorgang vor einem Schreibvorgang an eine andere Adresse. Daher erzwingt lwsync die Speicherreihenfolge, die der Standardspeicherreihenfolge auf x86- und x64-Prozessoren entspricht. Um vollständige Speicherreihenfolge zu erhalten, ist die teurere Synchronisierungsanweisung (auch als Synchronisierung mit hohem Gewicht 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 |
|---|---|---|---|
| Lese-Vorlese vor Lese-/Lese-Lese-/Lese-Lese | Ja | Nein | Nein |
| Schreibvorgänge vor Schreibvorgängen | Ja | Nein | Nein |
| Schreibvorgänge vor Lesevorgängen | Ja | Nein | Nein |
| Lesevorgänge vor Schreibvorgängen | Ja | Ja | Nein |
PowerPC verfügt auch über die Synchronisierungsanweisungen isync und eieio (die verwendet werden, um die Neuanordnung des zwischenspeichernden Speichers zu steuern). Diese Synchronisierungsanweisungen sollten für normale Synchronisierungszwecke nicht erforderlich sein.
Auf Windows ist MemoryBarrier in Winnt.h definiert und bietet Ihnen eine andere Speicherbarrierenanweisung, je nachdem, ob Sie für x86 oder x64 kompilieren. Die Speicherbarrierenanweisung dient als vollständige Barriere, die jede Neuanordnung von Lese- und Schreibvorgängen über die Barriere hinweg verhindert. Daher bietet MemoryBarrier auf Windows eine stärkere Neuanordnungsgarantie als bei Xbox 360.
Auf Xbox 360 und vielen anderen CPUs gibt es eine zusätzliche Möglichkeit, das Neuordnen von Lese-/Neuanordnungen 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 Lese-/Ablesedaten des Zeigers nicht älter sind als der Lese-/Lesezeitpunkt des Zeigers. Wenn Es sich bei Ihrem Sperrflag um einen Zeiger handelt und alle Lesedaten von freigegebenen Daten nicht vom Zeiger gelesen werden, kann MemoryBarrier ausgelassen werden, um geringfügige Leistungseinsparungen 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 das Neuordnen von Lese- und Schreibvorgängen in zwischenspeicherbaren Arbeitsspeicher. Wenn Sie Arbeitsspeicher als PAGE NOCACHE oder _ PAGE WRITECOMBINE zuweisen, ein gängiges Verfahren für Gerätetreiberautoren und für Spieleentwickler auf Xbox 360, hat _ MemoryBarrier keine Auswirkungen auf den Zugriff auf diesen Arbeitsspeicher. Die meisten Entwickler benötigen keine Synchronisierung von nicht zwischenspeicherbarem Arbeitsspeicher. Dies geht jedoch über den Rahmen dieses Artikels hinaus.
Interlocked Functions and CPU Reordering
Manchmal erfolgt der Lese- oder Schreibzugriff, der eine Ressource erhält oder frei gibt, mithilfe einer der InterlockedXxx-Funktionen. Auf Windows vereinfacht dies die Dinge. da Windows die InterlockedXxx-Funktionen alle Vollspeicherbarrieren sind. Sie verfügen effektiv sowohl vor als auch nach ihnen über eine CPU-Arbeitsspeicherbarriere, was bedeutet, dass sie selbst eine vollständige Barriere für Lese-/Lese- oder Schreibfreigabe darstellen.
Auf Xbox 360 enthalten die InterlockedXxx-Funktionen keine CPU-Arbeitsspeicherbarrieren. Sie verhindern die Neuanordnung von Lese- und Schreibvorgängen durch den Compiler, aber keine NEUANORDNUNG DER CPU. Daher sollten Sie in den meisten Fällen, wenn Sie InterlockedXxx-Funktionen auf Xbox 360 verwenden, eine _ _ lwsync-Sperre voran- oder folgen, um sie zu einer Barriere für Lese-/Lese- oder Schreibfreigaben zu machen. Der Einfachheit halber und zur besseren Lesbarkeit gibt es Acquire- und Releaseversionen vieler InterlockedXxx-Funktionen. Diese sind mit einer integrierten Speicherbarriere integriert. InterlockedIncrementAcquire führt z. B. ein interlocked-Inkrement gefolgt von einer _ _ lwsync-Speicherbarriere aus, um die vollständige Read-Acquire-Funktionalität zu bieten.
Es wird empfohlen, die Acquire- und Release-Versionen der InterlockedXxx-Funktionen (die meisten sind auch in Windows verfügbar, ohne Leistungsverlust) zu verwenden, um Ihre Absicht offensichtlicher zu machen und es einfacher zu machen, die Speicherbarriereanweisungen an der richtigen Stelle zu erhalten. 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-Versionen der InterlockedXxxSList-Funktionen an einen anderen Thread übergeben kann. Die InterlockedXxxSList-Funktionen sind eine Funktionsfamilie zum Verwalten einer freigegebenen, einfach verknüpften Liste ohne Sperre. Beachten Sie, dass acquire- und release-Varianten dieser Funktionen in Windows nicht verfügbar sind, die regulären Versionen dieser Funktionen jedoch eine vollständige Speicherbarriere 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;
}
Flüchtige Variablen und Neuanordnung
Der C++-Standard besagt, dass Lesevorgänge von flüchtigen Variablen nicht zwischengespeichert werden können, flüchtige Schreibvorgänge nicht verzögert werden können und flüchtige Lese- und Schreibvorgänge nicht übereinander verschoben werden können. Dies ist ausreichend für die Kommunikation mit Hardwaregeräten. Dies ist der Zweck des volatile-Schlüsselworts im C++-Standard.
Die Garantien des Standards reichen jedoch nicht aus, um volatile für Multithreading zu verwenden. Der C++-Standard hindert den Compiler nicht daran, nicht flüchtige Lese- und Schreibvorgänge relativ zu flüchtigen Lese- und Schreibvorgängen neu zu anordnen, und er sagt nichts darüber aus, wie die Neuanordnung der CPU verhindert wird.
Visual C++ 2005 geht über C++-Standard hinaus, um multithreadingfreundliche Semantik für den Zugriff auf flüchtige Variablen zu definieren. Ab Visual C++ 2005 werden Lesevorgänge aus flüchtigen Variablen so definiert, dass sie Semantik zum Lesen und Erwerben haben, und Schreibvorgänge in flüchtige Variablen werden so definiert, dass sie semantische Schreibfreigaben haben. Dies bedeutet, dass der Compiler keine Lese- und Schreibvorgänge neu ansortiert, und auf 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++. Compiler von anderen Anbietern implementieren in der Regel unterschiedliche Semantik, ohne die zusätzlichen Garantien Visual C++ 2005. Außerdem fügt der Xbox 360 keine Anweisungen ein, um zu verhindern, dass die CPU Lese- und Schreibvorgänge neu anordnen kann.
Beispiel für eine Lock-Free Data Pipe
Eine Pipe ist ein Konstrukt, mit dem ein oder mehrere Threads Daten schreiben können, die dann von anderen Threads gelesen werden. Eine sperrlose Version einer Pipe kann eine elegante und effiziente Möglichkeit sein, Arbeit vom Thread an den Thread zu übergeben. Das DirectX SDK stellt LockFreePipe bereit, eine single-reader- und single-writer-Pipe ohne Sperre, die in DXUTLockFreePipe.h verfügbar ist. Die gleiche LockFreePipe ist im Xbox 360 SDK in AtgLockFreePipe.h verfügbar.
LockFreePipe kann verwendet werden, wenn zwei Threads eine Producer/Consumer-Beziehung haben. Der Producerthread kann Daten in die Pipe schreiben, damit der Consumerthread zu einem späteren Zeitpunkt ohne Blockierung verarbeiten kann. Wenn die Pipe auffüllt, können Schreibvorgänge nicht ausgeführt werden, und der Producerthread muss den Vorgang später erneut versuchen. Dies geschieht jedoch nur, wenn der Producerthread voraus ist. Wenn die Pipe geleert wird, können Lese-/Lese-Fehler ausgeführt werden, und der Consumerthread muss den Vorgang später erneut versuchen. Dies geschieht jedoch nur, wenn für den Consumerthread keine Arbeit ausgeführt werden muss. Wenn die beiden Threads gut ausgeglichen sind und die Pipe groß genug ist, können sie datenfrei und ohne Verzögerungen oder Blöcke übergeben.
Xbox 360 Leistung
Die Leistung von Synchronisierungsanweisungen und -Xbox 360 hängt davon ab, welcher andere Code ausgeführt wird. Das Abrufen von Sperren dauert viel länger, wenn die Sperre derzeit von einem anderen Thread besitzt wird. 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 Näherungen, die aus sehr einfachen Tests generiert wurden:
- lwsync wurde mit 33 bis 48 Zyklen gemessen.
- InterlockedIncrement wurde mit 225 bis 260 Zyklen gemessen.
- Das Abrufen oder Freigeben eines kritischen Abschnitts wurde mit einer Zeit von etwa 345 Zyklen gemessen.
- Das Abrufen oder Freigeben eines Mutex wurde mit einer Zeit von etwa 2350 Zyklen gemessen.
Windows-Leistung
Die Leistung von Synchronisierungsanweisungen und -funktionen auf Windows je nach Prozessortyp und Konfiguration und dem ausgeführten anderen Code stark variieren. Die Ausführung von Synchronisierungsanweisungen für Systeme mit mehreren Kernen und Multisocket dauert häufig länger, und das Abrufen von Sperren dauert viel länger, wenn die Sperre derzeit von einem anderen Thread besitzt wird.
Allerdings sind auch einige Messungen, die aus sehr einfachen Tests generiert wurden, hilfreich:
- MemoryBarrier wurde mit 20 bis 90 Zyklen gemessen.
- InterlockedIncrement wurde mit 36 bis 90 Zyklen gemessen.
- Das Abrufen oder Freigeben eines kritischen Abschnitts wurde als 40-100 Zyklen gemessen.
- Das Abrufen oder Freigeben eines Mutex wurde mit einer Zeit von etwa 750 bis 2500 Zyklen gemessen.
Diese Tests wurden auf Windows XP auf einer Reihe verschiedener Prozessoren durchgeführt. Die kurzen Zeiten waren auf einem Computer mit nur einem Prozessor und die längeren Zeiten auf einem Computer mit mehreren Prozessoren.
Das Abrufen und Freigeben von Sperren ist zwar teurer als die Verwendung der sperrenlosen Programmierung, aber es ist noch besser, Daten seltener frei zu geben, um die Kosten zu vermeiden.
Überlegungen zur Leistung
Das Abrufen oder Freigeben eines kritischen Abschnitts besteht aus einer Speicherbarriere, einem InterlockedXxx-Vorgang und einigen zusätzlichen Überprüfungen, um die Rekursion zu behandeln und bei Bedarf auf einen Mutex zurückfallen zu können. Sie sollten vor der Implementierung Ihres eigenen kritischen Abschnitts zurückdeuten, da das Drehen in einer Schleife, die darauf wartet, dass eine Sperre frei ist, ohne auf einen Mutex zurückfallen zu müssen, eine erhebliche Leistung verschwenden kann. Bei kritischen Abschnitten, die stark umkäundbar, aber nicht lange gehalten werden, sollten Sie die Verwendung von InitializeCriticalSectionAndSpinCount in Betracht ziehen, damit das Betriebssystem eine Weile lang auf die Verfügbarlassung des kritischen Abschnitts wartet, anstatt sofort auf einen Mutex zu warten, wenn sich der kritische Abschnitt im Besitz des Unternehmens befindet, wenn Sie versuchen, ihn zu erhalten. Um kritische Abschnitte zu identifizieren, die von einer Drehungsanzahl profitieren können, ist es erforderlich, die Länge des typischen Wartens auf eine bestimmte Sperre zu messen.
Wenn ein freigegebener Heap für Speicherzuweisungen verwendet wird – das Standardverhalten –, umfasst jede Speicherzuordnung und jede freie Speicherzuweisung das Abrufen einer Sperre. Wenn die Anzahl der Threads und die Anzahl der Zuordnungen zunimmt, werden die Leistungsstufen deaktiviert, und schließlich beginnt die Verringerung. Durch die Verwendung von Pro-Thread-Heaps oder das Reduzieren der Anzahl von Zuordnungen kann dieser Sperrengpass vermieden werden.
Wenn ein Thread Daten generiert und ein anderer Thread Daten verwendet, werden daten möglicherweise häufig gemeinsam genutzt. Dies kann passieren, wenn ein Thread Ressourcen lädt und ein anderer Thread die Szene rendert. Wenn der Renderingthread bei jedem Zeichnen-Aufruf auf die freigegebenen Daten verweist, ist der Sperraufwand hoch. Eine deutlich bessere Leistung kann realisiert werden, wenn jeder Thread über private Datenstrukturen verfügt, die dann einmal pro Frame oder weniger synchronisiert werden.
Sperrenlose Algorithmen sind nicht garantiert schneller als Algorithmen, die Sperren verwenden. Sie sollten überprüfen, ob Sperren tatsächlich Probleme verursachen, bevor Sie versuchen, sie zu vermeiden, und Sie sollten messen, um zu überprüfen, ob Ihr sperrloser Code tatsächlich die Leistung verbessert.
Zusammenfassung der Plattformunterschiede
- InterlockedXxx-Funktionen verhindern eine Neuanordnung von CPU-Lese-/Schreibzugriffen auf Windows, aber nicht auf Xbox 360.
- Das Lesen und Schreiben von flüchtigen Variablen mithilfe von Visual Studio C++ 2005 verhindert die Neuanordnung von CPU-Lese-/Schreibzugriffen auf Windows, aber bei Xbox 360 wird nur die Neuanordnung von Lese-/Schreibzugriffen durch den Compiler verhindert.
- Schreibvorgänge werden auf Xbox 360 neu angeordnet, jedoch nicht auf x86 oder x64.
- Lesevorgänge werden auf Xbox 360 neu angeordnet, aber bei x86 oder x64 werden sie nur relativ zu Schreibvorgängen neu angeordnet, und nur, wenn die Lese- und Schreibvorgänge auf unterschiedliche Speicherorte zielen.
Empfehlungen
- Verwenden Sie sperren, wenn möglich, da sie einfacher richtig zu verwenden sind.
- Vermeiden Sie zu häufige Sperren, damit die Sperrkosten nicht signifikant werden.
- Vermeiden Sie es, Sperren zu lange zu halten, um lange Stags zu vermeiden.
- Verwenden Sie gegebenenfalls die locklose Programmierung, aber stellen Sie sicher, dass die Vorteile die Komplexität rechtfertigen.
- Verwenden Sie sperrenlose Programmierung oder Spinsperren in Situationen, in denen andere Sperren nicht zulässig sind, z. B. beim Freigeben von Daten zwischen verzögerten Prozeduraufrufen und normalem Code.
- Verwenden Sie nur standardmäßige algorithmen für die sperrenlose Programmierung, die sich als richtig erwiesen haben.
- Achten Sie beim Programmieren ohne Sperren darauf, dass Sie bei Bedarf volatile Flagvariablen und Speicherbarrierenanweisungen verwenden.
- Wenn Sie InterlockedXxx für Xbox 360 verwenden, verwenden Sie die Varianten Acquire und Release.
Referenzen
- MSDN Library. "volatile (C++)." C++-Sprachreferenz.
- Vance Sollon. "Understand the Impact of Low-Lock Techniques in Multithreaded Apps." MSDN Magazine, Oktober 2005.
- Bes, Michael. "PowerPC Storage Model and AIX Programming." IBM developerWorks, 16 November 2005.
- McKenney, Paul E. "Memory Ordering in Modern Microprocessors, Part II." Linux Journal, September 2005. [Dieser Artikel enthält einige x86-Details.]
- Intel Corporation. "Intel® 64 Architecture Memory Ordering." August 2007. [Gilt für IA-32- und Intel 64-Prozessoren.]
- Niebler, Eric. "Trip Report: Ad-hoc Meeting on Threads in C++." Die C++-Quelle, 17. Oktober 2006.
- Hart, Thomas E. 2006. "Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation." Proceedings of the 2006 International Parallel and Distributed Processing Symposium (IPDPS 2006), Island, Island, April 2006.