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 che cambiano tra più thread senza i costi di acquisizione e rilascio di blocchi. Questo sembra una panacea, ma la programmazione senza blocchi è complessa e sottile, e a volte non dà i vantaggi che promette. La programmazione senza blocchi è 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à e si dovrebbe misurare attentamente per assicurarsi che in realtà vi darà i guadagni previsti. In molti casi, esistono soluzioni più semplici e veloci, ad esempio la condivisione dei dati con minore frequenza, che devono essere invece usate.

L'uso della programmazione senza blocchi 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 blocchi.

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, il danneggiamento della memoria può verificarsi. Il modo più semplice per risolvere questo problema consiste nell'usare i blocchi. Ad esempio, se ManipulateSharedData deve essere eseguito da un solo 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 ad alta priorità 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 interrupt 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 blocchi, è necessario affrontare due problemi: operazioni non atomiche e riordinamento.

Operazioni non atomica

Un'operazione atomica è un'operazione indivisibile, una in cui gli altri thread non vedono mai l'operazione quando viene eseguita la metà. Le operazioni atomiche sono importanti per la programmazione senza blocchi, perché senza di esse, altri thread potrebbero visualizzare valori con metà scrittura o altrimenti incoerenti.

In tutti i processori moderni è possibile presupporre che le letture e le scritture di tipi nativi allineati naturalmente siano atomiche. Se il bus di memoria è almeno largo quanto il tipo letto o scritto, la CPU legge e scrive questi tipi in una singola transazione del bus, rendendo impossibile che altri thread li vedano in uno stato di mezzo completamento. In x86 e x64 non esiste alcuna garanzia che le letture e le scritture di dimensioni maggiori di otto byte siano atomiche. Ciò significa che le letture e le scritture a 16 byte dei registri di estensione SIMD in streaming (SSE) 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 garantiti come atomici. La CPU potrebbe 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. Su Xbox 360, queste operazioni vengono implementate come più istruzioni (lwz, addi e stw) e il thread potrebbe essere scambiato in uscita 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. La creazione di inc atomic nei sistemi multiprocessore x86 e x64 richiede l'uso del prefisso di blocco, che impedisce a un altro processore di eseguire una 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 con una combinazione dei seguenti elementi:

  • Operazioni atomica naturalmente
  • Blocchi per eseguire il wrapping delle operazioni composite
  • Funzioni del sistema operativo che implementano versioni atomico di operazioni composite comuni

L'incremento di una variabile non è un'operazione atomica e l'incremento può causare un 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 sempre si verificano 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 è 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.

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

Se il compilatore o la CPU riorganizzerà le scritture mostrate nel codice seguente, un altro thread potrebbe vedere che il flag attivo è impostato mentre visualizza ancora i valori precedenti per x o y. La 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 garantire la sicurezza di questo sistema sprite, è necessario impedire il riordinamento sia del compilatore che della CPU delle letture e delle scritture.

Informazioni sulla ridisistribuzione 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 riorganizzazione 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, viene riorganizzare le operazioni di scrittura, che vengono completate dopo le istruzioni stesse. Questa riorganizzazione delle scritture è consentita in modo specifico 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 dell'archivio e quindi archiviano i buffer. I buffer di raccolta dell'archivio consentono la scrittura di blocchi a 64 byte nella cache L2 in un'unica operazione. Ci sono otto buffer di raccolta di archivi, che consentono una scrittura efficiente in diverse aree di memoria.

I buffer store-gather vengono in genere 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, la 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 davanti alla 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. Pertanto, 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 una condivisione principale condividono i buffer di raccolta dell'archivio, rendendo l'allocazione e il svuotamento dei buffer di raccolta di archivi altamente variabile.

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

x86 e x64

Anche se le CPU x86 e x64 riordinano le istruzioni, in genere non riordinano le operazioni di scrittura relative 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 riorganizza della CPU delle letture

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

Xbox 360

I mancati riscontri nella cache possono causare ritardi in alcune letture, il che causa in modo efficace letture provenienti dalla memoria condivisa non in ordine e la tempistica di questi mancati riscontri nella cache è fondamentalmente imprevedibile. La prelettura e la stima dei rami possono anche causare la perdita di dati dalla memoria condivisa in ordine. Questi sono solo alcuni esempi di come le letture possono essere riordinate. Ci possono essere altre possibilità. Questa ridismissione delle letture è consentita in modo specifico dal modello di memoria PowerPC.

x86 e x64

Anche se le CPU x86 e x64 eseguono il riordino delle istruzioni, in genere non riordinano le operazioni di lettura rispetto ad altre letture. Le operazioni di stringa (MOVS e STOS) e le letture SSE a 16 byte possono essere riordinate internamente, ma in caso contrario, le letture non vengono riordinate l'una rispetto all'altra.

Altri riordinati

Anche se le CPU x86 e x64 non riordinano le scritture relative ad altre scritture o riordinano le letture relative ad altre letture, possono riordinare le letture relative alle scritture. In particolare, se un programma scrive in un'unica posizione seguita dalla lettura da un percorso diverso, i dati di lettura possono provenire dalla memoria condivisa prima che i dati scritti lo rendano 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 dalla risorsa di archiviazione condivisa prima della scrittura in f0 lo rende nell'archiviazione condivisa. Nel frattempo, la lettura di f0 in P1Acquire può leggere dalla risorsa di archiviazione condivisa prima della scrittura in f1 lo rende nell'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, anche se i problemi di riordinamento nei 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 su nessuna di queste piattaforme.

Le CPU x86 e x64 non riordinano una scrittura prima di una lettura precedente. Le CPU x86 e x64 riordinano le letture in anticipo rispetto alle scritture precedenti se sono destinate a posizioni diverse.

Le CPU PowerPC possono riordinare le letture prima delle scritture e possono riordinare le scritture prima delle letture, purché si trovino in indirizzi diversi.

Riepilogo riordinamento

La CPU Xbox 360 riordina le operazioni di memoria in modo molto più aggressivo rispetto alle CPU x86 e x64, come illustrato nella tabella seguente. Per altri dettagli, vedere la documentazione del processore.

Attività di riordinamento x86 e x64 Xbox 360
Letture in anticipo rispetto alle letture No Sì
Scritture in anticipo rispetto alle scritture No Sì
Scritture in anticipo rispetto alle letture No Sì
Letture in anticipo rispetto alle scritture Sì Sì

 

Barriere di lettura/acquisizione e rilascio in scrittura

I costrutti principali usati per impedire il riordinamento delle letture e delle scritture sono denominati barriere di lettura-acquisizione e rilascio di scrittura. Un'acquisizione in lettura è una lettura di un flag o di un'altra variabile per ottenere la proprietà di una risorsa, insieme 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, insieme a una barriera contro il riordinamento.

Le definizioni formali, per gentile concessione di 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 certa memoria, acquisendo un blocco o eseguendo il pull di un elemento da un elenco collegato condiviso (senza un blocco), è sempre presente una lettura, ovvero il test di un flag o un puntatore per verificare se la proprietà della memoria è stata acquisita. Questa lettura può far parte di un'operazione InterlockedXxx , nel qual caso comporta sia una lettura che una scrittura, ma è la lettura che indica se la proprietà è stata acquisita. Dopo l'acquisizione della proprietà della memoria, i valori vengono in genere letti 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 questo.

Quando viene rilasciata la proprietà di una memoria, rilasciando un blocco o eseguendo il push di un elemento in un elenco collegato condiviso, è sempre presente una scrittura interessata che notifica ad altri thread che la memoria è ora disponibile. Anche se il codice aveva la proprietà della memoria, probabilmente legga o lo scrive, ed è molto importante che queste letture e scritture vengano eseguite prima di rilasciare la proprietà. Una barriera di rilascio in scrittura garantisce questo problema.

È più semplice considerare le barriere di lettura-acquisizione e rilascio di scrittura come singole operazioni. Tuttavia, a volte devono essere costruiti da due parti: una lettura o una scrittura e una barriera che non consente letture o scritture di spostarsi. 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 rilascio in 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 durante l'acquisizione che per il rilascio dei dati, è preferibile (e più accurato) pensare a queste barriere come garantire la sincronizzazione con la memoria condivisa, non con altri processori. Se un processore usa una versione di scrittura per rilasciare una struttura di dati nella memoria condivisa e un altro processore usa un'acquisizione in lettura per ottenere l'accesso a tale struttura di dati dalla memoria condivisa, il codice funzionerà correttamente. Se uno dei responsabili del trattamento non usa la barriera appropriata, la condivisione dei dati potrebbe non riuscire.

L'uso della barriera giusta 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 del riordinamento del compilatore

Il processo di un compilatore consiste nell'ottimizzare in modo aggressivo il codice per migliorare le prestazioni. Sono incluse le istruzioni di riorganizzazione ovunque sia utile e ovunque non cambierà il comportamento. Poiché lo standard C++ non menziona mai il multithreading e poiché 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 il riordinamento del compilatore usando il _ReadWriteBarrier intrinseco del compilatore. Quando si inseriscono _ReadWriteBarrier nel codice, il compilatore non sposta le letture e le scritture.

#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 ridisporre le letture e le scritture, ma impedisce solo al compilatore di ridisporli. Pertanto, _ReadWriteBarrier è sufficiente quando si implementa una barriera di rilascio in scrittura su x86 e x64 (poiché 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 memorizzabile nella cache per impedire il riordinamento delle scritture. In questo caso _ReadWriteBarrier consente di migliorare le prestazioni, garantendo che le scritture vengano eseguite nell'ordine lineare preferito del processore.

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

Prevenzione del riordinamento della CPU

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

In Xbox 360 MemoryBarrier è definito come lwsync (sincronizzazione leggera), disponibile anche tramite il __lwsync intrinseco, definito in ppcintrinsics.h. __lwsync funge anche da barriera di memoria del compilatore, impedendo la ridismissione di letture e scritture da parte del compilatore.

L'istruzione lwsync è una barriera di memoria in Xbox 360 che sincronizza un core del processore con la cache L2. Garantisce che tutte le scritture prima di lwsync lo rendano nella cache L2 prima di eventuali scritture successive. Garantisce inoltre che le letture che seguono lwsync non ottengano dati meno recenti da L2 rispetto alle letture precedenti. L'unico tipo di riordinamento che non impedisce è un passaggio 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 heavyweight), ma nella maggior parte dei casi questa operazione non è necessaria. Le opzioni di riordinamento della memoria in Xbox 360 sono illustrate nella tabella seguente.

Riordinamento di Xbox 360 Nessuna sincronizzazione lwsync sync
Letture in anticipo rispetto alle letture Sì No No
Scritture in anticipo rispetto alle scritture Sì No No
Scritture in anticipo rispetto alle letture Sì No No
Letture in anticipo rispetto alle scritture Sì Sì No

 

PowerPC include anche le istruzioni di sincronizzazione isync e eieio (che viene usato per controllare il riordinamento alla memoria inibita dalla memorizzazione nella cache). 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 riordino di letture e scritture attraverso la barriera. Pertanto, MemoryBarrier in Windows offre una garanzia di riordinamento più forte rispetto a quella su Xbox 360.

Su Xbox 360 e su molte altre CPU è possibile impedire un altro modo per riordinare la lettura dalla 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, memoryBarrier può essere omesso 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 il riordinamento delle letture e delle scritture nella memoria memorizzabile nella cache. Se allochi memoria come PAGE_NOCACHE o PAGE_WRITECOMBINE, una tecnica comune per gli autori di driver di dispositivo 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 memorizzabile 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 cose; poiché in Windows, le funzioni InterlockedXxx sono tutte barriere di memoria completa. Hanno effettivamente una barriera di memoria della CPU sia prima che dopo, il che significa che sono una barriera completa di acquisizione o rilascio di scrittura tutto da soli.

In Xbox 360 le funzioni InterlockedXxx non contengono barriere di memoria della 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 precederli o seguirli con un __lwsync, per renderli una barriera di lettura-acquisizione o rilascio di scrittura. Per praticità e per semplificare la leggibilità, sono disponibili versioni Acquire e Release di molte delle funzioni InterlockedXxx . Questi sono dotati di una barriera di memoria incorporata. Ad esempio, InterlockedIncrementAcquire esegue un incremento interlocked seguito da una barriera di memoria __lwsync per fornire la funzionalità di acquisizione di lettura completa.

È consigliabile usare le versioni Acquire e Release delle funzioni InterlockedXxx (la maggior parte delle quali sono disponibili anche in Windows, senza penalità sulle prestazioni) per rendere più ovvio l'intento e semplificare l'acquisizione delle istruzioni sulla barriera di memoria nella posizione corretta. 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 Acquire e Release delle funzioni InterlockedXxxSList . Le funzioni InterlockedXxxSList sono una famiglia di funzioni per la gestione di un elenco collegato condiviso senza blocco. Si noti che le varianti Acquire e Release 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 volatile per il multithreading. Lo standard C++ non impedisce al compilatore di riordinare letture e scritture non volatili in relazione a letture e scritture volatili e non dice nulla di impedire il riordinamento della CPU.

Visual C++ 2005 va oltre lo standard C++ per definire una semantica descrittiva multithreading per l'accesso a variabili volatili. A partire da Visual C++ 2005, le letture da variabili volatili vengono definite in modo da avere semantica di acquisizione in lettura e le scritture nelle variabili volatili sono definite in modo da avere una semantica di rilascio in scrittura. Ciò significa che il compilatore non riorganizzerà le letture e le scritture incollate e in Windows garantirà che la CPU non lo faccia neanche.

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

Esempio di pipe dei dati senza blocco

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 e a scrittura singola 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 un secondo momento, senza mai bloccare. Se la pipe si riempie, le scritture hanno esito negativo e il thread producer dovrà riprovare più tardi, ma ciò si verifica solo se il thread producer è in anticipo. Se la pipe svuota, le letture hanno esito negativo e il thread consumer dovrà riprovare più tardi, ma ciò si verifica solo se non è necessario eseguire alcuna operazione per il thread consumer. Se i due thread sono ben bilanciati e la pipe è abbastanza grande, la pipe consente 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 quale altro codice è in esecuzione. L'acquisizione dei blocchi richiederà molto più tempo se un altro thread è attualmente proprietario del blocco. Le operazioni interlockedIncrement e sezione critica richiedono molto più tempo se altri thread scrivono nella stessa riga della cache. Anche il contenuto delle code dell'archivio può influire sulle prestazioni. Di conseguenza, tutti questi numeri sono solo approssimazioni, generati da test molto semplici:

  • Lwsync è stato misurato come prendendo 33-48 cicli.
  • InterlockedIncrement è stato misurato come prendendo 225-260 cicli.
  • L'acquisizione o il rilascio di una sezione critica è stata misurata come l'assunzione di 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 notevolmente a seconda del tipo e della configurazione del processore e dell'altro codice in esecuzione. I sistemi multi-core e multi socket richiedono spesso più tempo per eseguire le istruzioni di sincronizzazione e l'acquisizione dei 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 cicli da 36 a 90.
  • L'acquisizione o il rilascio di una sezione critica è stata misurata come l'assunzione di 40-100 cicli.
  • 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 su una gamma di processori diversi. I tempi brevi erano in un computer a processore singolo e i tempi più lunghi erano in un computer multiprocessore.

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

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 il fallback a un mutex, se necessario. Dovresti essere prudente di implementare la tua sezione critica, perché girare in un ciclo in attesa che un blocco sia libero, senza tornare a un mutex, può sprecare prestazioni notevoli. Per le sezioni critiche che sono molto contese ma non mantenute per molto tempo, è consigliabile usare InitializeCriticalSectionAndSpinCount in modo che il sistema operativo si spin 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 acquisirlo. Per identificare le sezioni critiche che possono trarre vantaggio da un conteggio di rotazioni, è necessario misurare la lunghezza dell'attesa tipica per un determinato blocco.

Se un heap condiviso viene usato per le allocazioni di memoria, ovvero il comportamento predefinito, ogni allocazione di memoria e libera comporta l'acquisizione di un blocco. Man mano che il numero di thread e il numero di allocazioni aumenta, i livelli di prestazioni sono disattivati e alla fine iniziano a diminuire. L'uso di heap 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 sta consumando dati, potrebbero finire per condividere i dati di frequente. Ciò può verificarsi se un thread sta caricando 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, l'overhead di blocco sarà elevato. È possibile ottenere prestazioni molto migliori se ogni thread dispone di strutture di dati private che vengono quindi sincronizzate una volta per ogni fotogramma o meno.

Gli algoritmi senza blocco non sono sicuramente più veloci rispetto agli algoritmi che usano blocchi. È consigliabile verificare se i blocchi causano effettivamente problemi prima di tentare di evitarli e valutare se il codice senza blocco migliora effettivamente le prestazioni.

Riepilogo delle differenze della piattaforma

  • Le funzioni InterlockedXxx impediscono il riordinamento di lettura/scrittura della CPU in Windows, ma non in Xbox 360.
  • La lettura e la scrittura di variabili volatili con Visual Studio C++ 2005 impedisce il riordinamento di lettura/scrittura della CPU in Windows, ma in Xbox 360 impedisce solo il riordinamento di lettura/scrittura del compilatore.
  • Le scritture vengono riordinate in Xbox 360, ma non su x86 o x64.
  • Le letture vengono riordinate in Xbox 360, ma in x86 o x64 vengono riordinate solo in relazione alle scritture e solo se le letture e le scritture sono destinate a 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 tenere le serrature troppo lunghe, per evitare lunghe stalle.
  • Usare la programmazione senza blocchi quando appropriato, ma assicurarsi che i guadagni giustificano la complessità.
  • Usare la programmazione senza blocchi o i blocchi di selezione in situazioni in cui altri blocchi sono vietati, ad esempio quando si condividono dati tra chiamate di routine posticipate e codice normale.
  • Usare solo algoritmi di programmazione senza blocco standard che hanno dimostrato di essere corretti.
  • Quando si esegue la programmazione senza blocchi, assicurarsi di usare variabili flag volatili e istruzioni per la barriera di memoria in base alle esigenze.
  • Quando si usa InterlockedXxx in Xbox 360, usare le varianti Acquire and Release .

Riferimenti