Condividi tramite

Considerazioni sulla programmazione senza blocchi per Xbox 360 e Microsoft Windows

  • Articolo

La programmazione senza blocchi è un modo per condividere in modo sicuro i dati in modifica tra più thread senza costi di acquisizione e rilascio di blocchi. Questo sembra una panacea, ma la programmazione senza blocco è complessa e sottile, e a volte non dà i vantaggi che promette. La programmazione senza blocco è particolarmente complessa in Xbox 360.

La programmazione senza blocco è una tecnica valida per la programmazione multithreading, ma non deve essere usata in modo leggero. Prima di usarlo, è necessario comprendere le complessità ed è necessario misurare attentamente per assicurarsi che in realtà vi darà i guadagni previsti. In molti casi, sono disponibili soluzioni più semplici e veloci, ad esempio la condivisione dei dati con minore frequenza, che devono essere invece usate.

L'uso della programmazione senza blocco richiede una conoscenza significativa sia dell'hardware che del compilatore. Questo articolo offre una panoramica di alcuni dei problemi da considerare quando si tenta di usare tecniche di programmazione senza blocco.

Programmazione con blocchi

Quando si scrive codice multithread, spesso è necessario condividere i dati tra thread. Se più thread stanno leggendo e scrivendo contemporaneamente le strutture di dati condivise, può verificarsi un danneggiamento della memoria. Il modo più semplice per risolvere questo problema consiste nell'usare i blocchi. Ad esempio, se ManipulateSharedData deve essere eseguito solo da un thread alla volta, è possibile usare un CRITICAL_SECTION per garantire questo problema, come nel codice seguente:

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

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

// Destroy
DeleteCriticalSection(&cs);

Questo codice è abbastanza semplice e semplice e facile da dire che è corretto. Tuttavia, la programmazione con blocchi presenta diversi potenziali svantaggi. Ad esempio, se due thread tentano di acquisire gli stessi due blocchi, ma li acquisiscono in un ordine diverso, è possibile che si verifichi un deadlock. Se un programma mantiene un blocco troppo lungo, a causa di una progettazione scadente o perché il thread è stato scambiato da un thread con priorità più alta, altri thread potrebbero essere bloccati per molto tempo. Questo rischio è particolarmente grande su Xbox 360 perché ai thread software viene assegnato un thread hardware dallo sviluppatore e il sistema operativo non li sposta in un altro thread hardware, anche se uno è inattiva. Xbox 360 non dispone inoltre di alcuna protezione contro l'inversione prioritaria, in cui un thread con priorità alta ruota in un ciclo in attesa di un thread con priorità bassa per rilasciare un blocco. Infine, se una chiamata di procedura posticipata o una routine di interruzione del servizio tenta di acquisire un blocco, è possibile che si verifichi un deadlock.

Nonostante questi problemi, le primitive di sincronizzazione, ad esempio le sezioni critiche, sono in genere il modo migliore per coordinare più thread. Se le primitive di sincronizzazione sono troppo lente, la soluzione migliore consiste in genere nell'usarle meno frequentemente. Tuttavia, per coloro che possono permettersi la complessità aggiuntiva, un'altra opzione è la programmazione senza blocchi.

Programmazione senza blocchi

La programmazione senza blocchi, come suggerisce il nome, è una famiglia di tecniche per modificare in modo sicuro i dati condivisi senza usare blocchi. Sono disponibili algoritmi senza blocco per il passaggio di messaggi, la condivisione di elenchi e code di dati e altre attività.

Quando si esegue la programmazione senza blocco, è necessario affrontare due problemi: operazioni non atomiche e riordinamento.

Operazioni non atomice

Un'operazione atomica è un'operazione indivisibile, una in cui gli altri thread non vedono mai l'operazione al termine della metà. Le operazioni atomiche sono importanti per la programmazione senza blocco, perché senza di essi, altri thread potrebbero visualizzare valori scritti a metà o in altro modo incoerenti.

In tutti i processori moderni è possibile presupporre che le letture e le scritture di tipi nativi allineati naturalmente siano atomiche. Purché il bus di memoria sia largo quanto il tipo letto o scritto, la CPU legge e scrive questi tipi in una singola transazione bus, rendendo impossibile che altri thread li vedano in uno stato di metà completamento. In x86 e x64 non esiste alcuna garanzia che le letture e le scritture di dimensioni superiori a otto byte siano atomiche. Ciò significa che le letture a 16 byte e le scritture dei registri dell'estensione SIMD (SSE) di streaming, e le operazioni di stringa, potrebbero non essere atomiche.

Le letture e le scritture di tipi non allineati naturalmente, ad esempio la scrittura di DWORD che superano limiti a quattro byte, non sono necessariamente atomici. La CPU può dover eseguire queste operazioni di lettura e scrittura come più transazioni del bus, che potrebbero consentire a un altro thread di modificare o visualizzare i dati al centro della lettura o della scrittura.

Le operazioni composite, ad esempio la sequenza read-modify-write che si verifica quando si incrementa una variabile condivisa, non sono atomiche. In Xbox 360 queste operazioni vengono implementate come più istruzioni (lwz, addi e stw) e il thread potrebbe essere scambiato in parte attraverso la sequenza. In x86 e x64 è disponibile una singola istruzione (inc) che può essere usata per incrementare una variabile in memoria. Se si usa questa istruzione, l'incremento di una variabile è atomico nei sistemi a processore singolo, ma non è ancora atomico nei sistemi multiprocessore. Rendere inc atomic su sistemi multiprocessore basati su x86 e x64 richiede l'uso del prefisso di blocco, che impedisce a un altro processore di eseguire la propria sequenza di lettura-modifica-scrittura tra la lettura e la scrittura dell'istruzione inc.

Il codice seguente illustra alcuni esempi:

// 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;

Garanzia dell'atomicità

È possibile assicurarsi di usare operazioni atomiche tramite una combinazione dei seguenti elementi:

  • Operazioni atomica naturalmente
  • Blocchi per eseguire il wrapping delle operazioni composite
  • Funzioni del sistema operativo che implementano versioni atomice delle operazioni composite più diffuse

L'incremento di una variabile non è un'operazione atomica e l'incremento può causare il danneggiamento dei dati se eseguito su più thread.

// This will be atomic.
g_globalCounter = 0;

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

Win32 include una famiglia di funzioni che offrono versioni atomica di lettura-modifica/scrittura di diverse operazioni comuni. Si tratta della famiglia di funzioni InterlockedXxx. Se tutte le modifiche della variabile condivisa usano queste funzioni, le modifiche saranno thread-safe.

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

Riordino

Un problema più sottile è riordinare. Le letture e le scritture non vengono sempre eseguite nell'ordine in cui sono state scritte nel codice e ciò può causare problemi molto confusi. In molti algoritmi multithread, un thread scrive alcuni dati e quindi scrive in un flag che indica ad altri thread che i dati sono pronti. Questa operazione è nota come versione di scrittura. Se le scritture vengono riordinate, altri thread potrebbero vedere che il flag viene impostato prima di poter visualizzare i dati scritti.

Analogamente, in molti casi, un thread legge da un flag e quindi legge alcuni dati condivisi se il flag indica che il thread ha acquisito l'accesso ai dati condivisi. Questa operazione è nota come acquisizione in lettura. Se le letture vengono riordinate, i dati potrebbero essere letti dalla risorsa di archiviazione condivisa prima del flag e i valori visualizzati potrebbero non essere aggiornati.

È possibile riordinare le letture e le scritture sia dal compilatore che dal processore. I compilatori e i processori hanno eseguito questo riordinamento per anni, ma nei computer a processore singolo è stato meno un problema. Ciò è dovuto al fatto che la riorganizzazione della CPU di letture e scritture è invisibile nei computer a processore singolo (per il codice driver non del dispositivo che non fa parte di un driver di dispositivo) e la ridisponizione delle letture e delle scritture è meno probabile che causi problemi nei computer a processore singolo.

Se il compilatore o la CPU riorganizzerà le scritture visualizzate nel codice seguente, un altro thread potrebbe vedere che il flag alive è impostato mentre vengono ancora visualizzati i valori precedenti per x o y. Una riorganizzazione simile può verificarsi durante la lettura.

In questo codice, un thread aggiunge una nuova voce alla matrice sprite:

// 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 questo blocco di codice successivo un altro thread legge dalla matrice sprite:

// 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 );
    }
}

Per rendere questo sistema sprite sicuro, è necessario impedire sia il compilatore che il riordinamento della CPU delle letture e delle scritture.

Informazioni sulla riorganizzazione della CPU delle scritture

Alcune CPU riorganizzano le scritture in modo che siano visibili esternamente ad altri processori o dispositivi in ordine non programmato. Questa ridisposizione non è mai visibile al codice non driver a thread singolo, ma può causare problemi nel codice multithread.

Xbox 360

Anche se la CPU Xbox 360 non riordina le istruzioni, esegue operazioni di scrittura riorganizzare, che vengono completate dopo le istruzioni stesse. Questa ridisposizione delle scritture è specificatamente consentita dal modello di memoria PowerPC.

Le scritture su Xbox 360 non passano direttamente alla cache L2. Al contrario, per migliorare la larghezza di banda di scrittura della cache L2, passano attraverso le code di archiviazione e quindi per raccogliere buffer. I buffer store-gather consentono di scrivere blocchi a 64 byte nella cache L2 in un'unica operazione. Sono disponibili otto buffer di raccolta di archivi, che consentono una scrittura efficiente in diverse aree di memoria.

I buffer store-gather vengono normalmente scritti nella cache L2 nell'ordine FIFO (First-In-First-Out). Tuttavia, se la riga di cache di destinazione di una scrittura non si trova nella cache L2, tale scrittura potrebbe essere ritardata mentre la riga della cache viene recuperata dalla memoria.

Anche quando i buffer di raccolta dell'archivio vengono scritti nella cache L2 in ordine FIFO rigoroso, ciò non garantisce che le singole scritture vengano scritte nella cache L2 in ordine. Si supponga, ad esempio, che la CPU scriva nella posizione 0x1000, quindi nella posizione 0x2000 e quindi nella posizione 0x1004. La prima scrittura alloca un buffer store-gather e lo inserisce all'inizio della coda. La seconda scrittura alloca un altro buffer store-gather e lo inserisce successivamente nella coda. La terza scrittura aggiunge i dati al primo buffer store-gather, che rimane all'inizio della coda. Di conseguenza, la terza scrittura finisce per passare alla cache L2 prima della seconda scrittura.

Il riordinamento causato dai buffer di raccolta di archivi è fondamentalmente imprevedibile, soprattutto perché entrambi i thread in un core condividono i buffer store-gather, rendendo elevata l'allocazione e il svuotamento dei buffer store-gather.

Questo è un esempio di come le scritture possono essere riordinate. Ci possono essere altre possibilità.

x86 e x64

Anche se le CPU x86 e x64 eseguono il riordinamento delle istruzioni, in genere non riordinano le operazioni di scrittura rispetto ad altre scritture. Esistono alcune eccezioni per la memoria combinata in scrittura. Inoltre, le operazioni di stringa (MOVS e STOS) e le scritture SSE a 16 byte possono essere riordinate internamente, ma in caso contrario, le scritture non vengono riordinate l'una rispetto all'altra.

Informazioni sulla riorganizzazione della CPU delle letture

Alcune CPU riorganizzano le letture in modo che provengano in modo efficace dall'archiviazione condivisa in ordine non programmato. Questa ridisposizione non è mai visibile al codice non driver a thread singolo, ma può causare problemi nel codice multithread.

Xbox 360

Le interruzioni della cache possono causare un ritardo di alcune letture, che causano in modo efficace le letture provenienti dalla memoria condivisa non in ordine e la tempistica di questi errori della cache è fondamentalmente imprevedibile. Il prefeting e la stima del ramo possono anche causare l'interruzione della memoria condivisa dei dati. Questi sono solo alcuni esempi di come le letture possono essere riordinate. Ci possono essere altre possibilità. Questa riorganizzazione delle letture è specificatamente consentita dal modello di memoria PowerPC.

x86 e x64

Anche se le CPU x86 e x64 reordinano le istruzioni, in genere non riordinano le operazioni di lettura rispetto ad altre letture. Le operazioni stringa (MOVS e STOS) e 16 byte SSE possono essere riordinate internamente, ma in caso contrario, le letture non vengono riordinate tra loro.

Altro riordinamento

Anche se le CPU x86 e x64 non riordinano le scritture relative ad altre scritture o riordinano le letture rispetto ad altre letture, possono riordinare le letture relative alle scritture. In particolare, se un programma scrive in una posizione seguita dalla lettura da una posizione diversa, i dati di lettura possono venire dalla memoria condivisa prima che i dati scritti lo facciano lì. Questo riordinamento può interrompere alcuni algoritmi, ad esempio gli algoritmi di esclusione reciproca di Dekker. Nell'algoritmo di Dekker ogni thread imposta un flag per indicare che vuole immettere l'area critica e quindi controlla il flag dell'altro thread per verificare se l'altro thread si trova nell'area critica o prova a immetterlo. Il codice iniziale segue.

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
    ...
}

Il problema è che la lettura di f1 in P0Acquire può leggere dall'archiviazione condivisa prima della scrittura in f0 lo rende in archiviazione condivisa. Nel frattempo, la lettura di f0 in P1Acquire può leggere dall'archiviazione condivisa prima della scrittura in f1 lo rende in archiviazione condivisa. L'effetto netto è che entrambi i thread impostano i flag su TRUE e entrambi i thread vedono il flag dell'altro thread come false, quindi entrambi entrano nell'area critica. Pertanto, mentre i problemi di riordinazione su sistemi basati su x86 e x64 sono meno comuni rispetto a Xbox 360, possono comunque verificarsi. L'algoritmo di Dekker non funzionerà senza barriere di memoria hardware in una di queste piattaforme.

Le CPU x86 e x64 non riordinano una scrittura prima di una lettura precedente. le CPU x86 e x64 vengono riordinate solo prima delle scritture precedenti se sono destinate a posizioni diverse.

Le CPU PowerPC possono riordinare le letture in anticipo delle scritture e possono riordinare le scritture in anticipo rispetto alle letture, purché siano in indirizzi diversi.

Riepilogo riordinamento

Le CPU Xbox 360 riordinano le operazioni di memoria molto più aggressive di x86 e cpu x64, come illustrato nella tabella seguente. Per altre informazioni, consultare la documentazione del processore.

Attività di riordinamento x86 e x64 Xbox 360
Legge in anticipo le letture No Sì
Scrive in anticipo le scritture No Sì
Scrive in anticipo le letture No Sì
Letture in avanti alle scritture Sì Sì

 

Read-Acquire e barriere Write-Release

I costrutti principali usati per impedire la riordinazione delle letture e delle scritture sono denominate barriere di lettura-acquisizione e rilascio di scrittura. Un'acquisizione di lettura è una lettura di un flag o di un'altra variabile per ottenere la proprietà di una risorsa, associata a una barriera contro il riordinamento. Analogamente, una versione di scrittura è una scrittura di un flag o di un'altra variabile per concedere la proprietà di una risorsa, abbinata a una barriera contro l'ordinamento.

Le definizioni formali, grazie a Herb Sutter, sono:

  • Un'acquisizione di lettura viene eseguita prima di tutte le letture e le scritture dallo stesso thread che lo segue nell'ordine di programma.
  • Una versione di scrittura viene eseguita dopo tutte le letture e le scritture dello stesso thread che lo precede nell'ordine di programma.

Quando il codice acquisisce la proprietà di una memoria, acquisisce un blocco o esegue il pull di un elemento di un elenco collegato condiviso (senza un blocco), è sempre presente un flag o un puntatore per verificare se la proprietà della memoria è stata acquisita. Questa lettura può essere parte di un'operazione InterlockedXxx , nel qual caso implica sia una lettura che una scrittura, ma è la lettura che indica se la proprietà è stata acquisita. Dopo aver acquisito la proprietà della memoria, i valori vengono in genere letti da o scritti in tale memoria ed è molto importante che queste letture e scritture vengano eseguite dopo l'acquisizione della proprietà. Una barriera di acquisizione di lettura garantisce questa operazione.

Quando viene rilasciata la proprietà di una memoria, rilasciando un blocco o eseguendo il push di un elemento in un elenco collegato condiviso, esiste sempre una scrittura che informa altri thread che la memoria è ora disponibile. Anche se il codice aveva la proprietà della memoria, probabilmente leggeva o scriveva in esso ed è molto importante che queste letture e scritture vengano eseguite prima di rilasciare la proprietà. Una barriera di rilascio di scrittura garantisce questa operazione.

È più semplice pensare a barriere di lettura-acquisizione e rilascio di scrittura come singole operazioni. Tuttavia, a volte devono essere costruiti da due parti: una lettura o una barriera che non consente letture o scritture di spostarsi tra di esso. In questo caso, la posizione della barriera è fondamentale. Per una barriera di acquisizione di lettura, la lettura del flag viene prima, quindi la barriera e quindi le letture e le scritture dei dati condivisi. Per una barriera di scrittura le letture e le scritture dei dati condivisi vengono prima, quindi la barriera e quindi la scrittura del flag.

// 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;
}

L'unica differenza tra un'acquisizione di lettura e una versione di scrittura è la posizione della barriera di memoria. Un'acquisizione di lettura ha la barriera dopo l'operazione di blocco e una versione di scrittura ha la barriera prima. In entrambi i casi la barriera è tra i riferimenti alla memoria bloccata e i riferimenti al blocco.

Per comprendere perché le barriere sono necessarie sia quando si acquisiscono sia quando si rilasciano dati, è preferibile (e più accurato) pensare a queste barriere come garantire la sincronizzazione con memoria condivisa, non con altri processori. Se un processore usa una versione di scrittura per rilasciare una struttura di dati in memoria condivisa e un altro processore usa un'acquisizione di lettura per ottenere l'accesso a tale struttura di dati dalla memoria condivisa, il codice funzionerà correttamente. Se entrambi i processori non usano la barriera appropriata, la condivisione dei dati potrebbe non riuscire.

L'uso della barriera corretta per impedire il riordinamento del compilatore e della CPU per la piattaforma è fondamentale.

Uno dei vantaggi dell'uso delle primitive di sincronizzazione fornite dal sistema operativo è che tutte includono le barriere di memoria appropriate.

Prevenzione della riordinazione del compilatore

Il processo di un compilatore consiste nell'ottimizzare in modo aggressivo il codice per migliorare le prestazioni. Ciò include istruzioni di riorganizzazione ovunque sia utile e ovunque non cambierà il comportamento. Poiché lo standard C++ non parla mai di multithreading e perché il compilatore non sa quale codice deve essere thread-safe, il compilatore presuppone che il codice sia a thread singolo quando decide quali riorganizze può eseguire in modo sicuro. Pertanto, è necessario indicare al compilatore quando non è consentito riordinare le letture e le scritture.

Con Visual C++ è possibile impedire la riordinazione del compilatore usando il _ReadWriteBarrier intrinseco del compilatore. Dove si inserisce _ReadWriteBarrier nel codice, il compilatore non sposta le letture e scrive in esso.

#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;

Nel codice seguente un altro thread legge dalla matrice sprite:

// 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 );
    }
}

È importante comprendere che _ReadWriteBarrier non inserisce istruzioni aggiuntive e non impedisce alla CPU di riorganiare le letture e le scritture, impedisce solo al compilatore di riorganizzerli. Pertanto, _ReadWriteBarrier è sufficiente quando si implementa una barriera di rilascio di scrittura su x86 e x64 (perché x86 e x64 non riordinano le scritture e una scrittura normale è sufficiente per rilasciare un blocco), ma nella maggior parte degli altri casi, è anche necessario impedire alla CPU di riordinare le letture e le scritture.

È anche possibile usare _ReadWriteBarrier quando si scrive in memoria combinata di scrittura non memorizzata nella cache per impedire la riordinazione delle scritture. In questo caso _ReadWriteBarrier consente di migliorare le prestazioni, garantendo che le scritture si verifichino nell'ordine lineare preferito del processore.

È anche possibile usare i _ReadBarrier e _WriteBarrier intrinseci per un controllo più preciso del riordinamento del compilatore. Il compilatore non sposta le letture in un _ReadBarrier e non sposta le scritture in un _WriteBarrier.

Prevenzione della riordinazione della CPU

Il riordinamento della CPU è più sottile rispetto al riordinamento del compilatore. Non è mai possibile vederlo direttamente, si vedono solo bug inesplicabili. Per evitare la riordinazione della CPU di letture e scritture, è necessario usare le istruzioni sulla barriera di memoria in alcuni processori. Il nome all-purpose per un'istruzione di barriera di memoria, in Xbox 360 e in Windows, è MemoryBarrier. Questa macro viene implementata in modo appropriato per ogni piattaforma.

Su Xbox 360, MemoryBarrier è definito come lwsync (sincronizzazione leggera), disponibile anche tramite l'intrinseco __lwsync , definito in ppcintrinsics.h. __lwsync funge anche da barriera di memoria del compilatore, impedendo la riorganizzazione delle letture e delle scritture dal compilatore.

L'istruzione lwsync è una barriera di memoria su Xbox 360 che sincronizza un core del processore con la cache L2. Garantisce che tutte le scritture prima di lwsync lo facciano nella cache L2 prima di tutte le scritture che seguono. Garantisce inoltre che le letture che seguono lwsync non ottengono dati precedenti da L2 rispetto alle letture precedenti. Il tipo di riordinamento che non impedisce è uno spostamento di lettura in avanti di una scrittura in un indirizzo diverso. Pertanto, lwsync applica l'ordinamento della memoria che corrisponde all'ordinamento di memoria predefinito nei processori x86 e x64. Per ottenere l'ordinamento completo della memoria, è necessaria l'istruzione di sincronizzazione più costosa (nota anche come sincronizzazione dei pesi pesanti), ma nella maggior parte dei casi non è necessaria. Le opzioni di riordinamento della memoria in Xbox 360 sono visualizzate nella tabella seguente.

Xbox 360 Riordinazione Nessuna sincronizzazione lwsync sync
Legge in anticipo le letture Sì No No
Scrive in anticipo le scritture Sì No No
Scrive in anticipo le letture Sì No No
Letture in avanti alle scritture Sì Sì No

 

PowerPC include anche le istruzioni di sincronizzazione isync e eieio (che viene usato per controllare la riordinazione per memorizzare nella cache la memoria inibita). Queste istruzioni di sincronizzazione non devono essere necessarie a scopo di sincronizzazione normale.

In Windows MemoryBarrier è definito in Winnt.h e offre un'istruzione di barriera di memoria diversa a seconda che si stia compilando per x86 o x64. L'istruzione della barriera di memoria funge da barriera completa, impedendo tutto il riordinamento di letture e scritture attraverso la barriera. Quindi, MemoryBarrier in Windows offre una garanzia di riordinamento più forte rispetto a quella che fa su Xbox 360.

Su Xbox 360 e su molte altre CPU è possibile impedire un altro modo per riordinare la CPU. Se si legge un puntatore e quindi si usa tale puntatore per caricare altri dati, la CPU garantisce che le letture del puntatore non siano precedenti alla lettura del puntatore. Se il flag di blocco è un puntatore e se tutte le letture di dati condivisi sono disattivate dal puntatore, è possibile omettere MemoryBarrier , per un risparmio di prestazioni modesto.

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;
}

L'istruzione MemoryBarrier impedisce solo di riordinare le letture e le scritture nella memoria memorizzata nella cache. Se si alloca memoria come PAGE_NOCACHE o PAGE_WRITECOMBINE, una tecnica comune per gli autori di driver di dispositivi e per gli sviluppatori di giochi su Xbox 360, MemoryBarrier non ha alcun effetto sugli accessi a questa memoria. La maggior parte degli sviluppatori non necessita della sincronizzazione della memoria non memorizzata nella cache. Questa operazione non rientra nell'ambito di questo argomento.

Funzioni interlocked e riordinamento DELLA CPU

A volte la lettura o la scrittura che acquisisce o rilascia una risorsa viene eseguita usando una delle funzioni InterlockedXxx . In Windows questo semplifica le operazioni; poiché in Windows, le funzioni InterlockedXxx sono tutte barriere full-memory. Hanno effettivamente una barriera di memoria CPU prima e dopo di loro, che significa che sono una barriera completa di lettura o rilascio di scrittura per se stessi.

In Xbox 360 le funzioni InterlockedXxx non contengono barriere di memoria CPU. Impediscono il riordinamento delle letture e delle scritture del compilatore, ma non il riordinamento della CPU. Pertanto, nella maggior parte dei casi quando si usano funzioni InterlockedXxx in Xbox 360, è necessario precederle o seguirle con un __lwsync, per renderle una barriera di lettura-acquisizione o rilascio di scrittura. Per praticità e facilità di lettura, sono disponibili versioni Di acquisizione e rilascio di molte delle funzioni InterlockedXxx . Questi sono dotati di una barriera di memoria predefinita. Ad esempio, InterlockedIncrementAcquire esegue un incremento interlocked seguito da una barriera di memoria __lwsync per offrire la funzionalità di acquisizione di lettura completa.

È consigliabile usare le versioni Di acquisizione e rilascio delle funzioni InterlockedXxx (la maggior parte delle quali sono disponibili anche in Windows, senza penalità sulle prestazioni) per rendere più evidente la finalità e rendere più facili le istruzioni sulla barriera di memoria nel posto corretto. Qualsiasi uso di InterlockedXxx su Xbox 360 senza una barriera di memoria deve essere esaminato molto attentamente, perché spesso è un bug.

Questo esempio illustra come un thread può passare attività o altri dati a un altro thread usando le versioni Di acquisizione e rilascio delle funzioni InterlockedXxxSList . Le funzioni InterlockedXxxSList sono una famiglia di funzioni per mantenere un elenco collegato condiviso senza un blocco. Si noti che le varianti di acquisizione e rilascio di queste funzioni non sono disponibili in Windows, ma le versioni regolari di queste funzioni sono una barriera di memoria completa in 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;
}

Variabili volatili e riordinamento

Lo standard C++ indica che le letture di variabili volatili non possono essere memorizzate nella cache, le scritture volatili non possono essere ritardate e le letture volatili e le scritture non possono essere spostate tra loro. Questo è sufficiente per comunicare con i dispositivi hardware, che è lo scopo della parola chiave volatile nello standard C++.

Tuttavia, le garanzie dello standard non sono sufficienti per l'uso di volatili per il multi-threading. Lo standard C++ non impedisce al compilatore di riordinare letture non volatili e scritture relative a letture e scritture volatili e non dice nulla sulla prevenzione della riordinazione della CPU.

Visual C++ 2005 supera lo standard C++ per definire semantiche descrittive multi-threading per l'accesso a variabili volatili. A partire da Visual C++ 2005, le letture dalle variabili volatili sono definite per avere semantiche di acquisizione di lettura e le scritture nelle variabili volatili sono definite per avere semantica di scrittura. Ciò significa che il compilatore non riorganizzerà le letture e le scrive in passato e in Windows garantisce che la CPU non lo faccia.

È importante comprendere che queste nuove garanzie si applicano solo a Visual C++ 2005 e versioni future di Visual C++. I compilatori di altri fornitori implementeranno in genere semantiche diverse, senza garanzie aggiuntive di Visual C++ 2005. Inoltre, in Xbox 360 il compilatore non inserisce istruzioni per impedire che la CPU riordina le letture e le scritture.

Esempio di una pipe dati Lock-Free

Una pipe è un costrutto che consente a uno o più thread di scrivere dati che vengono quindi letti da altri thread. Una versione senza blocchi di una pipe può essere un modo elegante ed efficiente per passare il lavoro dal thread al thread. DirectX SDK fornisce LockFreePipe, una pipe senza blocchi a lettore singolo disponibile in DXUTLockFreePipe.h. Lo stesso LockFreePipe è disponibile in Xbox 360 SDK in AtgLockFreePipe.h.

LockFreePipe può essere usato quando due thread hanno una relazione producer/consumer. Il thread producer può scrivere dati nella pipe per il thread consumer da elaborare in una data successiva, senza mai bloccare. Se il riempimento della pipe viene riempito, le scritture non riescono e il thread del produttore dovrà riprovare più tardi, ma questo accadrà solo se il thread del produttore è in anticipo. Se la pipe svuota, le letture non riesce e il thread consumer dovrà riprovare in un secondo momento, ma questo accadrà solo se non esiste alcun lavoro per il thread consumer da eseguire. Se i due thread sono ben bilanciati e la pipe è abbastanza grande, la pipe consente loro di passare senza problemi i dati senza ritardi o blocchi.

Prestazioni di Xbox 360

Le prestazioni delle istruzioni e delle funzioni di sincronizzazione in Xbox 360 variano a seconda di ciò che è in esecuzione. L'acquisizione di blocchi richiede molto più tempo se un altro thread è attualmente proprietario del blocco. Le operazioni di interlockedIncrement e sezione critica richiedono molto più tempo se altri thread scrivono nella stessa riga della cache. Il contenuto delle code dell'archivio può influire anche sulle prestazioni. Pertanto, tutti questi numeri sono solo approssimazioni, generate da test molto semplici:

  • lwsync è stato misurato come prendere 33-48 cicli.
  • InterlockedIncrement è stato misurato come l'assunzione di cicli da 225 a 260.
  • L'acquisizione o il rilascio di una sezione critica è stata misurata con circa 345 cicli.
  • L'acquisizione o il rilascio di un mutex è stata misurata come l'assunzione di circa 2350 cicli.

Prestazioni Windows

Le prestazioni delle istruzioni e delle funzioni di sincronizzazione in Windows variano ampiamente a seconda del tipo di processore e della configurazione e su quale altro codice è in esecuzione. I sistemi multi-core e multi socket spesso richiedono più tempo per eseguire le istruzioni di sincronizzazione e l'acquisizione di blocchi richiedono molto più tempo se un altro thread è attualmente proprietario del blocco.

Tuttavia, anche alcune misurazioni generate da test molto semplici sono utili:

  • MemoryBarrier è stato misurato come prendendo 20-90 cicli.
  • InterlockedIncrement è stato misurato come prendendo 36-90 cicli.
  • L'acquisizione o il rilascio di una sezione critica è stata misurata in base all'assunzione di cicli da 40 a 100.
  • L'acquisizione o il rilascio di un mutex è stata misurata come l'assunzione di circa 750-2500 cicli.

Questi test sono stati eseguiti in Windows XP in un'ampia gamma di processori diversi. I tempi brevi erano in una macchina a processore singolo e i tempi più lunghi erano in una macchina a più processori.

Durante l'acquisizione e il rilascio di blocchi è più costoso rispetto all'uso della programmazione senza blocchi, è anche meglio condividere i dati meno frequentemente, evitando così il costo completamente.

Pensieri sulle prestazioni

L'acquisizione o il rilascio di una sezione critica è costituita da una barriera di memoria, un'operazione InterlockedXxx e un controllo aggiuntivo per gestire la ricorsione e per tornare a un mutex, se necessario. È consigliabile prestare attenzione all'implementazione della propria sezione critica, perché la rotazione in un ciclo attende che un blocco sia libero, senza tornare a un mutex, può perdere prestazioni notevoli. Per le sezioni critiche che sono fortemente accodati, ma non mantenute per molto tempo, è consigliabile usare InitializeCriticalSectionAndSpinCount in modo che il sistema operativo si spinerà per un po' in attesa che la sezione critica sia disponibile anziché rinviare immediatamente a un mutex se la sezione critica è di proprietà quando si tenta di acquisire. Per identificare le sezioni critiche che possono trarre vantaggio da un conteggio di spin, è necessario misurare la lunghezza della tipica attesa per un determinato blocco.

Se un heap condiviso viene usato per le allocazioni di memoria, il comportamento predefinito, ogni allocazione di memoria e libera implica l'acquisizione di un blocco. Poiché il numero di thread e il numero di allocazioni aumentano, i livelli di prestazioni sono disattivati e infine iniziano a diminuire. L'uso degli heaps per thread o la riduzione del numero di allocazioni può evitare questo collo di bottiglia di blocco.

Se un thread genera dati e un altro thread utilizza i dati, possono finire per condividere i dati di frequente. Ciò può verificarsi se un thread sta caricando le risorse e un altro thread esegue il rendering della scena. Se il thread di rendering fa riferimento ai dati condivisi in ogni chiamata di disegno, il sovraccarico di blocco sarà elevato. È possibile realizzare prestazioni molto migliori se ogni thread ha strutture di dati private che vengono quindi sincronizzate una volta per fotogramma o meno.

Gli algoritmi senza blocco non sono garantiti per essere più veloci rispetto agli algoritmi che usano i blocchi. È consigliabile verificare se i blocchi stanno effettivamente causando problemi prima di tentare di evitarli e si dovrebbe misurare se il codice senza blocco migliora effettivamente le prestazioni.

Riepilogo delle differenze della piattaforma

  • Le funzioni InterlockedXxx impediscono la riordinazione della CPU in lettura/scrittura in Windows, ma non in Xbox 360.
  • La lettura e la scrittura di variabili volatili con Visual Studio C++ 2005 impedisce la riordinazione di lettura/scrittura della CPU in Windows, ma in Xbox 360 impedisce solo la riordinazione di lettura/scrittura del compilatore.
  • Le scritture vengono riordinate su Xbox 360, ma non su x86 o x64.
  • Le letture vengono riordinate su Xbox 360, ma in x86 o x64 vengono riordinate solo rispetto alle scritture e solo se le letture e scrive posizioni diverse.

Consigli

  • Usare i blocchi quando possibile perché sono più facili da usare correttamente.
  • Evitare di bloccare troppo spesso, in modo che i costi di blocco non diventino significativi.
  • Evitare di contenere blocchi troppo lunghi, per evitare blocchi lunghi.
  • Usare la programmazione senza blocchi quando appropriato, ma assicurarsi che i guadagni giustificano la complessità.
  • Usare la programmazione senza blocchi o i blocchi di spin in situazioni in cui altri blocchi sono vietati, ad esempio quando si condividono i dati tra chiamate di routine posticipate e codice normale.
  • Usare solo algoritmi di programmazione senza blocco standard che sono stati dimostrati corretti.
  • Quando si esegue la programmazione senza blocchi, assicurarsi di usare variabili di flag volatili e istruzioni sulla barriera di memoria in base alle esigenze.
  • Quando si usa InterlockedXxx in Xbox 360, usare le varianti Di acquisizione e rilascio .

Riferimenti