Questa pagina è stata tradotta dall'API Cloud Translation.

Primer SMP per Android

Le versioni della piattaforma Android 3.0 e successive sono ottimizzate per supportare le architetture multiprocessore. Questo documento introduce problemi che potrebbero sorgere durante la scrittura di codice multithread per sistemi multiprocessore simmetrico in C, C++ e nel linguaggio di programmazione Java (di seguito semplicemente "Java" per motivi di brevità). È intesa come un'introduzione per gli sviluppatori di app Android, non come una discussione completa sull'argomento.

Introduzione

SMP è l'acronimo di "Multi-Processor simmetrico". Descrive un design in cui due o più core CPU identici condividono l'accesso alla memoria principale. Fino ad alcuni anni fa, tutti i dispositivi Android erano UP (Uni-Processor).

La maggior parte dei dispositivi Android, se non tutti, avevano sempre più CPU, ma in passato solo una di queste veniva utilizzata per eseguire applicazioni, mentre altri gestiscono vari bit di hardware dei dispositivi (ad esempio, la radio). Le CPU potrebbero avere architetture diverse e i programmi in esecuzione non potevano utilizzare la memoria principale per comunicare tra loro.

La maggior parte dei dispositivi Android venduti oggi si basa su progetti SMP, rendendo le cose un po' più complicate per gli sviluppatori di software. Le condizioni di competizione in un programma multi-thread potrebbero non causare problemi visibili su un uniprocessore, ma potrebbero restituire errori regolarmente quando due o più thread vengono eseguiti contemporaneamente su core diversi. Inoltre, il codice può essere più o meno soggetto a errori se eseguito su diverse architetture di processori o persino su diverse implementazioni della stessa architettura. Il codice testato in modo approfondito su x86 potrebbe non funzionare correttamente su ARM. Il codice potrebbe iniziare a restituire errori quando viene ricompilato con un compilatore più moderno.

La parte restante di questo documento ne spiega il motivo e indica cosa devi fare per assicurarti che il codice funzioni correttamente.

Modelli di coerenza della memoria: perché le SMP sono leggermente diverse

Si tratta di una panoramica ad alta velocità e lucida di un soggetto complesso. Alcune aree saranno incompleta, ma nessuna dovrebbe essere fuorviante o sbagliata. Come vedremo nella prossima sezione, i dettagli riportati qui di solito non sono importanti.

Consulta Per approfondire alla fine del documento per indicare una trattazione più approfondita dell'argomento.

I modelli di coerenza della memoria, o spesso solo "modelli di memoria", descrivono le garanzie che il linguaggio di programmazione o l'architettura hardware garantiscono agli accessi alla memoria. Ad esempio, se scrivi un valore per l'indirizzo A e poi scrivi un valore per l'indirizzo B, il modello potrebbe garantire che ogni core della CPU veda le scritture in quell'ordine.

Il modello a cui la maggior parte dei programmatori è abituata è la coerenza sequenziale, descritta in questo modo (Adve e Gharachorloo):

Sembra che tutte le operazioni di memoria vengano eseguite una alla volta
Tutte le operazioni in un singolo thread sembrano essere eseguite nell'ordine descritto dal programma del processore.

Supponiamo temporaneamente di avere un compilatore o un interprete molto semplice che non presenta sorprese: traduce i compiti nel codice sorgente per caricare e memorizzare le istruzioni esattamente nell'ordine corrispondente, un'istruzione per accesso. Inoltre, supponiamo che ogni thread venga eseguito sul proprio processore.

Se osservi un po' di codice e noti che esegue alcune operazioni di lettura e scrittura dalla memoria, in un'architettura della CPU coerente in sequenza sai che il codice eseguirà queste operazioni di lettura e scrittura nell'ordine previsto. È possibile che la CPU riordina le istruzioni e ritarda le letture e le scritture, ma il codice in esecuzione sul dispositivo non può in alcun modo capire che la CPU stia facendo qualcosa di diverso dall'esecuzione delle istruzioni in modo diretto. (I/O dei driver di dispositivo con mappatura della memoria verranno ignorati).

Per illustrare questi punti è utile prendere in considerazione piccoli snippet di codice, comunemente indicati come test di tornasole.

Ecco un semplice esempio, con il codice in esecuzione su due thread:

Thread 1	Thread 2
`A = 3 B = 5`	`reg0 = B reg1 = A`

In questo e in tutti i futuri esempi di tornasole, le posizioni di memoria sono rappresentate da lettere maiuscole (A, B, C) e i registri della CPU iniziano con "reg". All'inizio tutta la memoria è pari a zero. Le istruzioni vengono eseguite dall'alto verso il basso. Qui, il thread 1 memorizza il valore 3 nella posizione A e poi il valore 5 nella posizione B. Il thread 2 carica il valore dalla posizione B a reg0, quindi carica il valore dalla posizione A a reg1. (Tieni presente che il testo viene scritto in un ordine e letto nell'altro).

Si presume che i thread 1 e 2 vengano eseguiti su diversi core della CPU. Dovresti prenderlo sempre questo presupposto quando pensi al codice multi-thread.

La coerenza sequenziale garantisce che, al termine dell'esecuzione di entrambi i thread, i registri si troveranno in uno dei seguenti stati:

Registri	Stati
reg0=5, reg1=3	possibile (il thread 1 è stato eseguito per primo)
reg0=0, reg1=0	possibile (il thread 2 è stato eseguito per primo)
reg0=0, reg1=3	possibile (esecuzione simultanea)
reg0=5, reg1=0	mai

Per entrare in una situazione in cui vediamo B=5 prima di vedere l'archivio in A, le letture o le scritture dovrebbero avvenire in ordine. Su una macchina coerente in sequenza, questo non può accadere.

I processori Uni, inclusi x86 e ARM, sono normalmente coerenti in sequenza. I thread sembrano essere eseguiti in modalità interleaving, quando il kernel del sistema operativo passa da uno all'altro. La maggior parte dei sistemi SMP, inclusi x86 e ARM, non è coerente in modo sequenziale. Ad esempio, è frequente che l'hardware esegua il buffering di archivi durante il percorso verso la memoria, in modo da non raggiungere subito la memoria e diventare visibili ad altri core.

I dettagli variano sostanzialmente. Ad esempio, x86, sebbene non sia coerente in sequenza, garantisce comunque che reg0 = 5 e reg1 = 0 rimanga impossibile. I negozi sono sottoposti a buffer, ma il loro ordine viene mantenuto. ARM, invece, non lo fa. L'ordine degli archivi con buffer non viene mantenuto e i negozi potrebbero non raggiungere tutti gli altri core contemporaneamente. Queste differenze sono importanti per i programmatori di assemblaggio. Tuttavia, come vedremo più avanti, i programmatori C, C++ o Java possono e devono programmare in modo da nascondere tali differenze di architettura.

Finora abbiamo ipotizzato in modo irrealistico che sia solo l'hardware a modificare l'ordine delle istruzioni. In realtà, il compilatore riordina anche le istruzioni per migliorare le prestazioni. Nel nostro esempio, il compilatore potrebbe decidere che un po' di codice successivo nel Thread 2 necessitava del valore di reg1 prima di aver bisogno di reg0, quindi caricherà prima reg1. Oppure, il codice precedente potrebbe aver già caricato A e il compilatore potrebbe decidere di riutilizzare quel valore anziché caricare di nuovo A. In entrambi i casi, i caricamenti su reg0 e reg1 potrebbero essere riordinati.

Il riordinamento degli accessi a posizioni di memoria diverse, nell'hardware o nel compilatore, è consentito poiché non influisce sull'esecuzione di un singolo thread e può migliorare notevolmente le prestazioni. Come vedremo, con un po' di attenzione, possiamo anche impedire che influisca sui risultati dei programmi multithread.

Poiché i compilatori possono anche riordinare gli accessi alla memoria, questo problema in realtà non è nuovo per gli SMP. Anche su un uniprocessore, un compilatore potrebbe riordinare i caricamenti in reg0 e reg1 nel nostro esempio e Thread 1 potrebbe essere pianificato tra le istruzioni riordinate. Ma se il nostro compilatore non riordinasse il file, non potremmo mai osservare questo problema. Nella maggior parte delle SMP ARM, anche senza riordinamento del compilatore, è probabile che il riordinamento venga eseguito, probabilmente dopo un numero molto elevato di esecuzioni riuscite. A meno che tu non stia programmando in linguaggio Assembly, le SMP in genere aumentano le probabilità di rilevare problemi che sono sempre presenti.

Programmazione senza gare di dati

Fortunatamente, di solito esiste un modo semplice per evitare di pensare a uno di questi dettagli. Se segui alcune regole chiare, in genere è facile dimenticare tutta la sezione precedente, ad eccezione della parte relativa alla "coerenza sequenziale". Purtroppo, le altre complicazioni potrebbero diventare visibili se violi accidentalmente queste regole.

I linguaggi di programmazione moderni incoraggiano quello che è noto come uno stile di programmazione "senza razza di dati". Purché prometti di non introdurre "razze di dati" ed evita alcuni costrutti che indicano diversamente al compilatore, il compilatore e l'hardware promettono di fornire risultati coerenti in sequenza. Ciò non significa davvero che evitino il riordinamento dell'accesso alla memoria. Ciò significa che se segui le regole, non potrai dire che gli accessi alla memoria sono in fase di riordinamento. È un po' come dirti che la salsiccia è un alimento delizioso e appetitoso, purché prometti di non visitare la fabbrica di salsicce. Le gare di dati sono ciò che espone la brutta verità sul riordinamento della memoria.

Che cos'è una "gara di dati"?

Una gara di dati si verifica quando almeno due thread accedono contemporaneamente agli stessi dati ordinari e almeno uno di loro li modifica. Con "dati ordinari" intendiamo qualcosa che non è specificamente un oggetto di sincronizzazione destinato alla comunicazione thread. I mutox, le variabili di condizione, le volatili Java o gli oggetti atomici C++ non sono dati ordinari e i relativi accessi possono competere. Infatti, vengono utilizzati per impedire le corse di dati su altri oggetti.

Per determinare se due thread accedono contemporaneamente alla stessa posizione di memoria, possiamo ignorare la discussione sul riordinamento della memoria descritta in precedenza e assumere la coerenza sequenziale. Il seguente programma non ha una corsa di dati se A e B sono variabili booleane ordinarie inizialmente false:

Thread 1	Thread 2
`if (A) B = true`	`if (B) A = true`

Poiché le operazioni non vengono riordinate, entrambe le condizioni restituiranno il valore false e nessuna variabile verrà aggiornata. Non può quindi esistere una corsa di dati. Non è necessario pensare a cosa potrebbe accadere se il carico da A e l'archivio a B nel Thread 1 venisse in qualche modo riordinato. Il compilatore non è autorizzato a riordinare il Thread 1 riscrivendolo come "B = true; if (!A) B = false". Ciò sarebbe come preparare una salsiccia in mezzo alla città alla luce del sole.

Le corse di dati sono definite ufficialmente su tipi integrati di base come numeri interi e riferimenti o puntatori. L'assegnazione a un elemento int durante la lettura simultanea in un altro thread è chiaramente una corsa di dati. Tuttavia, sia la libreria standard C++ sia le librerie delle raccolte Java sono scritte per consentirti di ragionare anche sulle corse di dati a livello di libreria. Promettono di non introdurre corse di dati, a meno che non ci siano accessi simultanei allo stesso container, almeno uno dei quali lo aggiorna. L'aggiornamento di un set<T> in un thread e la sua lettura simultanea in un altro consente alla libreria di introdurre una corsa di dati, che può quindi essere considerata informalmente come una "gara di dati a livello di libreria". Al contrario, l'aggiornamento di un set<T> in un thread e la lettura di uno diverso nell'altro non comporta una corsa di dati, perché la libreria promette di non introdurre una corsa di dati (di basso livello) in quel caso.

Normalmente gli accessi simultanei a campi diversi di una struttura di dati non possono introdurre una corsa di dati. Esiste però un'importante eccezione a questa regola: le sequenze contigue di campi di bit in C o C++ vengono trattate come una singola "posizione di memoria". L'accesso a qualsiasi campo di bit in una sequenza di questo tipo viene considerato come l'accesso a tutti i campi allo scopo di determinare l'esistenza di una corsa di dati. Ciò riflette l'incapacità dell'hardware comune di aggiornare singoli bit senza leggere e riscrivere bit adiacenti. I programmatori Java non hanno problemi analoghi.

Evitare le corse di dati

I linguaggi di programmazione moderni offrono una serie di meccanismi di sincronizzazione per evitare corse di dati. Gli strumenti più basilari sono:

Blocchi o silenziatori: mutox (C++11 std::mutex o pthread_mutex_t) o blocchi synchronized in Java per garantire che determinate sezioni di codice non vengano eseguite in concomitanza con altre sezioni di codice che accedono agli stessi dati. Ci riferiremo a queste e ad altre funzionalità simili genericamente con il termine "serrature". L'acquisizione costante di un blocco specifico prima di accedere a una struttura di dati condivisa e rilasciarla in seguito impedisce le corse dei dati quando si accede alla struttura dei dati. Inoltre, assicura che gli aggiornamenti e gli accessi siano atomici, vale a dire che nessun altro aggiornamento alla struttura dei dati può essere eseguito nel mezzo. Questo è sicuramente lo strumento più comune per prevenire le corse di dati. L'utilizzo di blocchi synchronized Java, di C++ lock_guard o unique_lock garantisce il rilascio corretto dei blocchi in caso di eccezione.
Variabili volatili/atomiche: Java fornisce campi volatile che supportano l'accesso simultaneo, senza introdurre gruppi di dati. Dal 2011, C e C++ supportano le variabili atomic e i campi con semantica simile. In genere, sono più difficili da utilizzare rispetto ai blocchi, poiché assicurano solo che gli accessi individuali a una singola variabile siano atomici. In C++ di solito questo si estende a semplici operazioni di lettura, modifica e scrittura, come gli incrementi. Java richiede chiamate a metodi speciali a questo scopo). A differenza dei blocchi, le variabili volatile o atomic non possono essere utilizzate direttamente per impedire ad altri thread di interferire con sequenze di codice più lunghe.

È importante notare che volatile ha significati molto diversi in C++ e Java. In C++, volatile non impedisce le corse di dati, anche se i codici precedenti spesso lo utilizzano come soluzione alternativa per la mancanza di oggetti atomic. Questa opzione non è più consigliata; in C++, utilizza atomic<T> per le variabili a cui è possibile accedere contemporaneamente da più thread. C++ volatile è pensato per i registri dei dispositivi e simili.

Le variabili atomic C/C++ o le variabili volatile Java possono essere utilizzate per evitare corse di dati su altre variabili. Se flag è di tipo atomic<bool>, atomic_bool(C/C++) o volatile boolean (Java) ed è inizialmente false, il seguente snippet è data-race-free:

Thread 1	Thread 2
`A = ... flag = true`	`while (!flag) {} ... = A`

Poiché il Thread 2 attende che sia impostato flag, l'accesso a A nel Thread 2 deve avvenire dopo l'assegnazione a A nel Thread 1 e non contemporaneamente. Quindi non esiste una corsa di dati su A. La corsa su flag non viene conteggiata come una corsa di dati, poiché gli accessi volatili/atomici non sono "accessi alla memoria ordinari".

L'implementazione è necessaria per impedire o nascondere il riordinamento della memoria sufficiente a far sì che il codice come la cartina di tornasole precedente si comporti come previsto. Questo di solito rende gli accessi alla memoria volatile/atomica molto più costosi degli accessi ordinari.

Sebbene l'esempio precedente sia privo di corse di dati, i blocchi insieme a Object.wait() in Java o alle variabili di condizione in C/C++ di solito forniscono una soluzione migliore che non prevede l'attesa in un loop mentre si scarica la batteria.

Quando il riordinamento della memoria diventa visibile

La programmazione senza corsa ai dati ci evita di dover affrontare esplicitamente problemi di riordinamento dell'accesso alla memoria. Tuttavia, in alcuni casi il riordinamento diventa visibile:

Se il tuo programma ha un bug che causa una corsa di dati involontaria, le trasformazioni del compilatore e dell'hardware possono diventare visibili e il comportamento del tuo programma potrebbe sorprenderti. Ad esempio, se abbiamo dimenticato di dichiarare il volatile flag nell'esempio precedente, Thread 2 potrebbe visualizzare un A non inizializzato. Oppure, il compilatore potrebbe decidere che il flag non può cambiare durante il loop di Thread 2

Thread 1 Thread 2

A = ... flag = true reg0 = flag; while (!reg0) {}
... = A

Quando esegui il debug, potresti notare che il loop continua all'infinito, nonostante flag sia vero.
C++ consente di ridurre in modo esplicito la coerenza sequenziale anche in assenza di gruppi etnici. Le operazioni atomiche possono utilizzare argomenti memory_order_... espliciti. Analogamente, il pacchetto java.util.concurrent.atomic fornisce un insieme più limitato di servizi simili, in particolare lazySet(). Inoltre, a volte i programmatori Java usano intenzionali corse di dati per ottenere un risultato simile. Tutte queste caratteristiche migliorano le prestazioni con un costo elevato in termini di complessità di programmazione. Ne parliamo solo di seguito.
Alcuni codici C e C++ sono scritti in uno stile meno recente, non completamente coerente con gli attuali standard di linguaggio, in cui vengono utilizzate le variabili volatile al posto di quelle atomic e l'ordinamento della memoria è vietato in modo esplicito inserendo i cosiddetti recinzioni o barriere. Ciò richiede un ragionamento esplicito relativo al riordinamento dell'accesso e alla comprensione dei modelli di memoria hardware. Uno stile di programmazione di queste righe è ancora utilizzato nel kernel Linux. Non deve essere utilizzato nelle nuove app Android e non viene ulteriormente discusso qui.

Thread 1	Thread 2
`A = ... flag = true`	reg0 = flag; while (!reg0) {} ... = A

Fai pratica

Il debug dei problemi di coerenza della memoria può essere molto difficile. Se un blocco mancante, una dichiarazione atomic o volatile causa la lettura di dati inattivi da parte del codice, potresti non riuscire a capire il motivo esaminando i dump della memoria con un debugger. Quando potrai inviare una query del debugger, tutti i core della CPU potrebbero aver osservato l'intero set di accessi e il contenuto della memoria e i registri della CPU appariranno in uno stato "impossibile".

Cosa non fare in C

Di seguito sono riportati alcuni esempi di codice errato, insieme a semplici soluzioni per correggerli. Prima di farlo, dobbiamo discutere dell'uso di una funzionalità lingua di base.

C/C++ e "volatile"

Le dichiarazioni C e C++ volatile sono uno strumento molto speciale. Impediscono al compilatore di riordinare o rimuovere gli accessi volatili. Questo può essere utile per il codice che accede ai registri dei dispositivi hardware, alla memoria mappata a più di una posizione o in relazione a setjmp. Tuttavia, C e C++ volatile, a differenza di Java volatile, non sono progettati per la comunicazione in thread.

In C e C++, gli accessi ai dati volatile possono essere riordinati con l'accesso a dati non volatili e non esistono garanzie di atomicità. Di conseguenza, volatile non può essere utilizzato per la condivisione di dati tra thread nel codice portabile, anche su un uniprocessore. Di solito C volatile non impedisce il riordinamento dell'accesso da parte dell'hardware, pertanto è ancora meno utile negli ambienti SMP multi-thread. Questo è il motivo per cui C11 e C++11 supportano gli oggetti atomic. Dovresti usarli invece.

Diversi codici C e C++ meno recenti utilizzano ancora volatile in modo improprio per la comunicazione dei thread. Questo spesso funziona correttamente per i dati che rientrano in un registro delle macchine, a condizione che vengano utilizzati con recinzioni espliciti o nei casi in cui l'ordine della memoria non è importante. Ma non è garantito che funzioni correttamente con i compilatori futuri.

Esempi

Nella maggior parte dei casi sarebbe meglio usare un blocco (ad esempio pthread_mutex_t o C++11 std::mutex) piuttosto che un'operazione atomica, ma utilizzeremo quest'ultima per illustrare come viene utilizzata in una situazione pratica.

MyThing* gGlobalThing = NULL;  // Wrong!  See below.
void initGlobalThing()    // runs in Thread 1
{
    MyStruct* thing = malloc(sizeof(*thing));
    memset(thing, 0, sizeof(*thing));
    thing->x = 5;
    thing->y = 10;
    /* initialization complete, publish */
    gGlobalThing = thing;
}
void useGlobalThing()    // runs in Thread 2
{
    if (gGlobalThing != NULL) {
        int i = gGlobalThing->x;    // could be 5, 0, or uninitialized data
        ...
    }
}

L'idea qui è di allocare una struttura, inizializzare i suoi campi e alla fine "pubblicala" memorizzandola in una variabile globale. A quel punto, qualsiasi altro thread può vederlo, ma va bene dato che è completamente inizializzato, giusto?

Il problema è che è possibile osservare l'archivio in gGlobalThing prima dell'inizializzazione dei campi, in genere perché il compilatore o il processore hanno riordinato gli archivi in gGlobalThing e thing->x. Un altro thread letto da thing->x potrebbe vedere 5, 0 o persino dati non inizializzati.

Il problema principale qui è una corsa di dati su gGlobalThing. Se il thread 1 chiama initGlobalThing() mentre il thread 2 chiama useGlobalThing(), gGlobalThing può essere letto durante la scrittura.

Questo problema può essere risolto dichiarando gGlobalThing come atomico. In C++11:

atomic<MyThing*> gGlobalThing(NULL);

Ciò garantisce che le scritture diventino visibili agli altri thread nell'ordine corretto. Garantisce inoltre di impedire altre modalità di errore altrimenti consentite, ma che difficilmente si verificano sull'hardware Android reale. Ad esempio, ci assicura che non sia possibile visualizzare un puntatore gGlobalThing che è stato scritto solo parzialmente.

Che cosa non fare in Java

Non abbiamo ancora parlato di alcune funzionalità pertinenti del linguaggio Java, quindi prima ne esamineremo velocemente.

Java tecnicamente non richiede che il codice sia privo di corse dati. Inoltre, c'è una piccola quantità di codice Java scritto con cura che funziona correttamente anche in presenza di corse di dati. Tuttavia, scrivere questo codice è estremamente difficile e ne parliamo solo brevemente di seguito. A peggiorare la situazione, gli esperti che hanno specificato il significato di questo codice non ritengono più che la specifica sia corretta. (La specifica va bene per il codice data-race-free.)

Per il momento, aderiamo al modello privo di razza di dati, per il quale Java offre sostanzialmente le stesse garanzie di C e C++. Anche in questo caso, il linguaggio fornisce alcune primitive che allentano esplicitamente la coerenza sequenziale, in particolare le chiamate lazySet() e weakCompareAndSet() in java.util.concurrent.atomic. Come con C e C++, per ora li ignoreremo.

Parole chiave "sincronizzate" e "volatili" di Java

La parola chiave "sincronizzata" fornisce il meccanismo di blocco integrato del linguaggio Java. A ogni oggetto è associato un "monitoraggio" che può essere utilizzato per fornire un accesso che si esclude a vicenda. Se due thread tentano di "sincronizzarsi" sullo stesso oggetto, uno attenderà fino al completamento dell'altro.

Come accennato in precedenza, volatile T di Java è l'analogo di atomic<T> di C++11. Gli accessi simultanei ai campi volatile sono consentiti e non comportano corse di dati. Ignorando lazySet() et al. e le razze di dati, è compito della VM Java assicurarsi che il risultato sia ancora coerente in sequenza.

In particolare, se il thread 1 scrive in un campo volatile e in seguito legge lo stesso campo e vede il valore appena scritto, anche il thread 2 vedrà tutte le scritture effettuate in precedenza dal thread 1. In termini di effetto memoria, la scrittura in un volatile è analoga a una release di monitoraggio e la lettura da un volatile è come un'acquisizione monitor.

C'è una differenza notevole rispetto al criterio atomic di C++: se scriviamo volatile int x; in Java, allora x++ equivale a x = x + 1; esegue un carico atomico, incrementa il risultato e quindi esegue un archivio atomico. A differenza di C++, l'incremento nel suo insieme non è atomico. Le operazioni di incremento atomico sono invece fornite da java.util.concurrent.atomic.

Esempi

Ecco una semplice implementazione errata di un contatore monotonico: (Teoria e pratica Java: gestione della volatilità).

class Counter {
    private int mValue;
    public int get() {
        return mValue;
    }
    public void incr() {
        mValue++;
    }
}

Supponiamo che get() e incr() vengano chiamate da più thread e vogliamo assicurarci che ogni thread visualizzi il conteggio attuale quando viene chiamato get(). Il problema più evidente è che mValue++ consiste in tre operazioni:

reg = mValue
reg = reg + 1
mValue = reg

Se due thread vengono eseguiti in incr() contemporaneamente, uno degli aggiornamenti potrebbe andare perso. Per rendere l'incremento atomico, dobbiamo dichiarare incr() "sincronizzato".

Tuttavia, non funziona ancora, specialmente in SMP. Esiste ancora una corsa di dati, in quanto get() può accedere a mValue contemporaneamente a incr(). Nelle regole Java, è possibile che la chiamata get() venga riordinata rispetto ad altro codice. Ad esempio, se leggiamo due contatori di fila, i risultati potrebbero sembrare incoerenti perché le chiamate get() che abbiamo riordinato dall'hardware o dal compilatore. Possiamo risolvere il problema dichiarando che get() deve essere sincronizzato. Con questa modifica, il codice è ovviamente corretto.

Sfortunatamente, abbiamo introdotto la possibilità di un conflitto tra i blocchi, che potrebbe ostacolare le prestazioni. Anziché dichiarare che get() deve essere sincronizzato, potremmo dichiarare mValue con "volatile". (Nota incr() deve comunque usare synchronize poiché mValue++ non è una singola operazione atomica). In questo modo si evitano anche tutte le corse di dati, così viene mantenuta la coerenza sequenziale. incr() sarà un po' più lento, poiché comporta sia overhead di entrata/uscita del monitoraggio sia l'overhead associato a un negozio volatile, ma get() sarà più veloce, quindi anche in assenza di contesa questa è una vittoria se le letture superano notevolmente le scritture. Vedi anche AtomicInteger per un modo per rimuovere completamente il blocco sincronizzato.

Ecco un altro esempio, simile ai precedenti esempi C:

class MyGoodies {
    public int x, y;
}
class MyClass {
    static MyGoodies sGoodies;
    void initGoodies() {    // runs in thread 1
        MyGoodies goods = new MyGoodies();
        goods.x = 5;
        goods.y = 10;
        sGoodies = goods;
    }
    void useGoodies() {    // runs in thread 2
        if (sGoodies != null) {
            int i = sGoodies.x;    // could be 5 or 0
            ....
        }
    }
}

Questo presenta lo stesso problema del codice C, ovvero esiste una corsa di dati su sGoodies. Di conseguenza, l'assegnazione sGoodies = goods potrebbe essere osservata prima dell'inizializzazione dei campi in goods. Se dichiari sGoodies con la parola chiave volatile, la coerenza sequenziale viene ripristinata e il tutto funzionerà come previsto.

Tieni presente che solo il riferimento sGoodies stesso è volatile. Gli accessi ai campi al suo interno non lo sono. Quando sGoodies è volatile e l'ordine della memoria è stato mantenuto correttamente, non è possibile accedere contemporaneamente ai campi. L'istruzione z = sGoodies.x eseguirà un carico volatile pari a MyClass.sGoodies seguito da un carico non volatile di sGoodies.x. Se effettui un riferimento locale MyGoodies localGoods = sGoodies, un elemento z = localGoods.x successivo non eseguirà carichi volatili.

Un modo più comune nella programmazione Java è il famigerato "blocco con doppio controllo":

class MyClass {
    private Helper helper = null;
    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }
}

L'idea è che vogliamo avere una singola istanza di un oggetto Helper associata a un'istanza di MyClass. Dobbiamo crearlo una sola volta, quindi lo creiamo e restituiamo tramite una funzione getHelper() dedicata. Per evitare che l'istanza venga creata da due thread, devi sincronizzare la creazione dell'oggetto. Tuttavia, non vogliamo pagare l'overhead per il blocco "sincronizzato" per ogni chiamata, quindi facciamo quella parte solo se al momento helper è nullo.

È presente una corsa di dati nel campo helper. Può essere impostato contemporaneamente a helper == null in un altro thread.

Per un errore, considera lo stesso codice riscritto leggermente, come se fosse compilato in un linguaggio di tipo C (ho aggiunto un paio di campi interi per rappresentare l'attività del costruttore Helper’s):

if (helper == null) {
    synchronized() {
        if (helper == null) {
            newHelper = malloc(sizeof(Helper));
            newHelper->x = 5;
            newHelper->y = 10;
            helper = newHelper;
        }
    }
    return helper;
}

Non c'è nulla che impedisca all'hardware o al compilatore di riordinare l'archivio in helper con quelli nei campi x/y. Un altro thread potrebbe trovare helper con valore non null, ma i suoi campi non sono ancora impostati e pronti per l'uso. Per maggiori dettagli e altre modalità di errore, consulta il link "Dichiarazione ''Double Checked Locking is Broken'" nell'appendice per maggiori dettagli o la voce 71 ("Usa l'inizializzazione lazy con prudenza") in Effective Java, 2nd Edition di Josh Bloch.

Esistono due modi per risolvere questo problema:

Fai la cosa più semplice ed elimina il controllo esterno. Ciò garantisce che non venga mai esaminato il valore di helper al di fuori di un blocco sincronizzato.
Dichiara il valore volatile di helper. Con questa piccola modifica, il codice nell'Esempio J-3 funzionerà correttamente su Java 1.5 e versioni successive. (Potresti voler dedicare un minuto per convincerti che è vero.)

Ecco un'altra illustrazione del comportamento di volatile:

class MyClass {
    int data1, data2;
    volatile int vol1, vol2;
    void setValues() {    // runs in Thread 1
        data1 = 1;
        vol1 = 2;
        data2 = 3;
    }
    void useValues() {    // runs in Thread 2
        if (vol1 == 2) {
            int l1 = data1;    // okay
            int l2 = data2;    // wrong
        }
    }
}

Guardando useValues(), se Thread 2 non ha ancora osservato l'aggiornamento a vol1, non può sapere se data1 o data2 sono stati ancora impostati. Una volta che vede l'aggiornamento a vol1, sa che è possibile accedere in sicurezza a data1 e leggerlo correttamente senza introdurre una corsa di dati. Tuttavia, non possiamo fare ipotesi su data2, perché tale negozio è stato eseguito dopo il negozio volatile.

Tieni presente che non è possibile usare volatile per impedire il riordinamento di altri accessi alla memoria che competono tra loro. Non è garantito che generi un'istruzione di recinzione della memoria della macchina. Può essere utilizzato per evitare corse di dati eseguendo codice solo quando un altro thread ha soddisfatto una determinata condizione.

Cosa fare

In C/C++, preferisci le classi di sincronizzazione C++11, come std::mutex. In caso contrario, utilizza le operazioni pthread corrispondenti. Questi includono i recinzioni di memoria appropriati, che forniscono un comportamento corretto (coerente in sequenza, se non diversamente specificato) ed efficiente su tutte le versioni della piattaforma Android. Assicurati di usarle correttamente. Ad esempio, ricorda che le attese delle variabili di condizione potrebbero tornare spuricamente senza essere segnalate e quindi dovrebbero apparire in un loop.

È preferibile evitare di utilizzare direttamente le funzioni atomiche, a meno che la struttura dei dati che stai implementando sia estremamente semplice, come un contatore. Il blocco e lo sblocco di un mutex pthread richiede una singola operazione atomica ciascuna e spesso costano meno di un singolo fallimento della cache, se non c'è alcuna contesa, quindi non risparmierai molto sostituendo le chiamate mutex con operazioni atomiche. I progetti senza blocco per strutture di dati non banali richiedono molta più attenzione per garantire che le operazioni di livello superiore sulla struttura dei dati sembrino atomici (nell'insieme, non solo nei loro pezzi esplicitamente atomici).

Se utilizzi le operazioni atomiche, la riduzione dell'ordinamento con memory_order... o lazySet() potrebbe offrire vantaggi in termini di prestazioni, ma richiede una comprensione più approfondita di quella fornita finora. Si scopre che una gran parte del codice esistente che utilizza questi modelli presenta bug. Se possibile, evitali. Se i tuoi casi d'uso non rientrano esattamente in uno di quelli della sezione successiva, assicurati di essere un esperto o di averne consultato uno.

Evita di utilizzare volatile per la comunicazione thread in C/C++.

In Java, i problemi di contemporaneità vengono spesso risolti utilizzando una classe di utilità appropriata dal pacchetto java.util.concurrent. Il codice è ben scritto e testato su SMP.

Forse la cosa più sicura che puoi fare è rendere i tuoi oggetti immutabili. Gli oggetti di classi come il numero intero e la stringa di Java conservano dati che non possono essere modificati dopo la creazione dell'oggetto, evitando qualsiasi possibile corsa di dati su questi oggetti. Il libro Effective Java, 2nd Ed. contiene istruzioni specifiche nella sezione "Elemento 15: riduci al minimo la mutabilità". Tieni presente in particolare l'importanza di dichiarare i campi Java "finali" (Bloch).

Anche se un oggetto è immutabile, ricorda che comunicarlo a un altro thread senza alcun tipo di sincronizzazione è una sfida ai dati. A volte questa operazione può essere accettabile in Java (vedi sotto), ma richiede molta attenzione e probabilmente genererà codice fragile. Se non è estremamente importante per le prestazioni, aggiungi una dichiarazione volatile. In C++, comunicare un puntatore o un riferimento a un oggetto immutabile senza una sincronizzazione adeguata, come qualsiasi corsa di dati, è un bug. In questo caso è ragionevolmente probabile che si verifichino arresti anomali intermittenti poiché, ad esempio, il thread ricevente potrebbe visualizzare un puntatore della tabella del metodo non inizializzato a causa del riordinamento dell'archivio.

Se né una classe di libreria esistente né una classe immutabile sono appropriate, è necessario utilizzare l'istruzione synchronized Java o C++ lock_guard / unique_lock per proteggere gli accessi a qualsiasi campo a cui può accedere più di un thread. Se i mutex non funzionano per la tua situazione, devi dichiarare i campi condivisi volatile o atomic, ma devi comprendere attentamente le interazioni tra i thread. Queste dichiarazioni non ti salveranno da errori di programmazione comuni e simultanei, ma ti aiuteranno a evitare i misteriosi errori associati all'ottimizzazione dei compilatori e degli errori SMP.

Dovresti evitare di "pubblicare" un riferimento a un oggetto, ovvero renderlo disponibile ad altri thread, nel suo costruttore. Questo aspetto è meno critico in C++ o se segui il nostro consiglio "nessuna corsa ai dati" in Java. È sempre un buon consiglio e diventa fondamentale se il codice Java viene eseguito in altri contesti in cui il modello di sicurezza Java è importante, mentre il codice non attendibile potrebbe introdurre una corsa di dati tramite l'accesso al riferimento all'oggetto "fugato". È fondamentale anche ignorare i nostri avvisi e utilizzare alcune delle tecniche illustrate nella prossima sezione. Consulta (Tecniche di costruzione sicure in Java) per i dettagli

Qualche informazione in più sugli ordini di memoria deboli

C++11 e versioni successive forniscono meccanismi espliciti per allentare le garanzie di coerenza sequenziale per i programmi privi di corsa di dati. Gli argomenti espliciti memory_order_relaxed, memory_order_acquire (solo caricamento) e memory_order_release(solo archiviazione) per le operazioni atomiche forniscono garanzie strettamente più deboli rispetto al valore predefinito, in genere implicito, memory_order_seq_cst. memory_order_acq_rel offre garanzie memory_order_acquire e memory_order_release per le operazioni di scrittura atomica di lettura e modifica. memory_order_consume non è ancora sufficientemente ben specificato o implementato per essere utile e per il momento deve essere ignorato.

I metodi lazySet in Java.util.concurrent.atomic sono simili agli archivi C++ memory_order_release. Le variabili ordinarie di Java vengono a volte utilizzate in sostituzione degli accessi a memory_order_relaxed, anche se in realtà sono ancora più deboli. A differenza di C++, non esiste un meccanismo reale per gli accessi non ordinati alle variabili dichiarate come volatile.

In genere, dovresti evitarli, a meno che non ci siano motivi di prestazioni urgenti per utilizzarli. Sulle architetture delle macchine con ordine debole, come ARM, il loro utilizzo solitamente consente di risparmiare sull'ordine di alcune decine di cicli di macchina per ogni operazione atomica. Su x86, la vittoria in termini di rendimento è limitata ai negozi e probabilmente sarà meno evidente. In modo un po' incomprensibile, il vantaggio potrebbe diminuire con un numero maggiore di core, in quanto il sistema di memoria diventa un fattore limitante.

La semantica completa degli atomici in ordine debole è complicata. In generale richiedono una comprensione precisa delle regole linguistiche, cosa che non entreremo in questa sede. Ecco alcuni esempi:

Il compilatore o l'hardware possono spostare gli accessi memory_order_relaxed all'interno (ma non all'esterno) di una sezione critica limitata da un'acquisizione e una release di blocco. Ciò significa che due negozi memory_order_relaxed potrebbero diventare visibili in disordine, anche se sono separati da una sezione critica.
Una variabile Java ordinaria, se utilizzata in modo illecito come contatore condiviso, potrebbe apparire in un altro thread per diminuire, anche se incrementata solo da un singolo altro thread. Ma questo non è vero per C++ atomico memory_order_relaxed.

Con questo come avviso, forniamo qui un piccolo numero di espressioni idiomatiche che sembrano coprire molti dei casi d'uso degli atomici con ordine debole. Molte di queste soluzioni sono applicabili solo a C++.

Accessi non correlati alle corse

È abbastanza comune che una variabile sia atomica perché a volte viene letta in concomitanza con una scrittura, ma non tutti gli accessi presentano questo problema. Ad esempio, potrebbe essere necessario che una variabile sia atomica perché viene letta all'esterno di una sezione critica, ma tutti gli aggiornamenti sono protetti da un blocco. In questo caso, una lettura che è protetta dallo stesso blocco non può essere avviata, dato che non possono verificarsi scritture simultanee. In tal caso, l'accesso non racing (caricamento in questo caso) può essere annotato con memory_order_relaxed senza modificare la correttezza del codice C++. L'implementazione del blocco applica già l'ordinamento della memoria richiesto in relazione all'accesso da parte di altri thread e memory_order_relaxed specifica che sostanzialmente non è necessario applicare vincoli di ordinamento aggiuntivi per l'accesso atomico.

Non esiste un vero analogo in Java.

Non viene fatto affidamento sul risultato per la correttezza

Quando utilizziamo un carico in corsa solo per generare un suggerimento, in genere è anche opportuno non applicare alcun ordinamento della memoria per il carico. Se il valore non è affidabile, non possiamo nemmeno utilizzare in modo affidabile il risultato per dedurre informazioni su altre variabili. Pertanto, va bene se l'ordinamento della memoria non è garantito e il carico viene fornito con un argomento memory_order_relaxed.

Un'istanza comune è l'uso di C++ compare_exchange per sostituire atomicamente x con f(x). Il caricamento iniziale di x per calcolare f(x) non deve essere affidabile. In caso di errore, compare_exchange non andrà a buon fine e riproveremo. Per il caricamento iniziale di x non c'è problema con l'utilizzo di un argomento memory_order_relaxed; è importante solo l'ordinamento della memoria per compare_exchange effettivo.

Dati modificati atomicamente, ma da leggere

A volte i dati vengono modificati in parallelo da più thread, ma non vengono esaminati fino al completamento del calcolo parallelo. Un buon esempio di ciò è un contatore con incremento atomico (ad es. utilizzando fetch_add() in C++ o atomic_fetch_add_explicit() in C) da più thread in parallelo, ma il risultato di queste chiamate viene sempre ignorato. Il valore risultante viene letto solo alla fine, dopo che tutti gli aggiornamenti sono stati completati.

In questo caso, non è possibile stabilire se gli accessi a questi dati sono stati riordinati e, di conseguenza, il codice C++ può utilizzare un argomento memory_order_relaxed.

Un esempio comune è costituito dai contatori di eventi semplici. Poiché è molto comune, vale la pena fare alcune osservazioni su questo caso:

L'utilizzo di memory_order_relaxed migliora le prestazioni, ma potrebbe non risolvere il problema di prestazioni più importante: ogni aggiornamento richiede l'accesso esclusivo alla riga della cache che contiene il contatore. Ciò comporta un fallimento della cache ogni volta che un nuovo thread accede al contatore. Se gli aggiornamenti sono frequenti e si alternano tra i thread, è molto più rapido evitare di aggiornare ogni volta il contatore condiviso, ad esempio utilizzando contatori locali dei thread e sommandoli alla fine.
Questa tecnica è combinabile con la sezione precedente: è possibile contemporaneamente leggere valori approssimativi e non affidabili mentre vengono aggiornati, con tutte le operazioni che utilizzano memory_order_relaxed. Tuttavia, è importante trattare i valori risultanti come completamente inaffidabili. Il semplice fatto che il conteggio sia stato incrementato una volta non significa che sia possibile conteggiare un altro thread per aver raggiunto il punto in cui è stato eseguito l'incremento. L'incremento potrebbe invece essere stato riordinato con codice precedente. Per quanto riguarda il caso simile citato in precedenza, C++ garantisce che un secondo caricamento di un contatore non restituirà un valore inferiore a un caricamento precedente nello stesso thread. a meno che, ovviamente, il contatore non abbia superato un overflow).
È comune trovare codice che tenta di calcolare i valori approssimativi del contatore eseguendo letture e scritture individuali o meno di un atomico, ma non generando l'incremento come un intero atomico. In genere, questo è "abbastanza simile" per i contatori delle prestazioni o simili. In genere non è così. Quando gli aggiornamenti sono sufficientemente frequenti (un caso che probabilmente ti interessa), una gran parte dei conteggi in genere viene persa. Su un dispositivo quad core, più della metà dei conteggi potrebbe andare perduta. (Facile esercizio: crea uno scenario con due thread in cui il contatore viene aggiornato un milione di volte, ma il valore del contatore finale è uno).

Comunicazione semplice

Un archivio memory_order_release (o un'operazione di lettura, modifica e scrittura) assicura che, se successivamente un caricamento memory_order_acquire (o un'operazione di lettura, modifica e scrittura) legge il valore scritto, osserverà anche eventuali archivi (ordinari o atomici) che hanno preceduto l'archivio memory_order_release. Al contrario, qualsiasi caricamento precedente a memory_order_release non osserverà alcun archivio che ha seguito il carico memory_order_acquire. A differenza di memory_order_relaxed, questo consente di utilizzare le operazioni atomiche per comunicare l'avanzamento di un thread a un altro.

Ad esempio, possiamo riscrivere l'esempio di blocco verificato sopra in C++

class MyClass {
  private:
    atomic<Helper*> helper {nullptr};
    mutex mtx;
  public:
    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper == nullptr) {
        lock_guard<mutex> lg(mtx);
        myHelper = helper.load(memory_order_relaxed);
        if (myHelper == nullptr) {
          myHelper = new Helper();
          helper.store(myHelper, memory_order_release);
        }
      }
      return myHelper;
    }
};

L'archivio di acquisizione del carico e di release garantisce che se rileviamo un valore helper diverso da null, anche i relativi campi verranno inizializzati correttamente. Inoltre, abbiamo incorporato l'osservazione precedente secondo cui i carichi non da gara possono utilizzare memory_order_relaxed.

Un programmatore Java potrebbe rappresentare helper come java.util.concurrent.atomic.AtomicReference<Helper> e utilizzare lazySet() come archivio release. Le operazioni di caricamento continueranno a utilizzare le chiamate get() normali.

In entrambi i casi, le nostre modifiche alle prestazioni si sono concentrate sul percorso di inizializzazione, che è improbabile che sia critico per le prestazioni. Un compromesso più leggibile potrebbe essere:

    Helper* getHelper() {
      Helper* myHelper = helper.load(memory_order_acquire);
      if (myHelper != nullptr) {
        return myHelper;
      }
      lock_guard&ltmutex> lg(mtx);
      if (helper == nullptr) {
        helper = new Helper();
      }
      return helper;
    }

Fornisce lo stesso percorso rapido, ma ricorre a operazioni predefinite e coerenti in sequenza sul percorso lento non critico per le prestazioni.

Anche qui, è probabile che helper.load(memory_order_acquire) generi lo stesso codice sulle attuali architetture supportate da Android come un semplice riferimento (coerente in sequenza) a helper. L'ottimizzazione più vantaggiosa in questo caso potrebbe essere l'introduzione di myHelper per eliminare un secondo caricamento, anche se un compilatore futuro potrebbe farlo automaticamente.

L'ordinamento di acquisizione/release non impedisce che i negozi subiscano ritardi visibilmente e non garantisce che i negozi diventino visibili ad altri thread in un ordine coerente. Di conseguenza, non supporta un pattern di codifica complicato, ma abbastanza comune, esemplificato dall'algoritmo di esclusione reciproca di Dekker: tutti i thread impostano prima un flag che indica l'intenzione di eseguire qualcosa; se un thread t nota che nessun altro thread sta cercando di fare qualcosa, può procedere in sicurezza, sapendo che non ci saranno interferenze. Nessun altro thread potrà continuare, dato che il flag di t è ancora impostato. L'operazione non riesce se si accede al flag utilizzando l'ordinamento di acquisizione/rilascio, poiché non impedisce di rendere visibile ad altri il flag di un thread in ritardo dopo che l'operazione è stata eseguita in modo errato. L'impostazione predefinita memory_order_seq_cst lo impedisce.

Campi immutabili

Se un campo oggetto viene inizializzato al primo utilizzo e poi non viene mai modificato, potrebbe essere possibile inizializzarlo e successivamente leggerlo utilizzando accessi con ordine debole. In C++, potrebbe essere dichiarato come atomic e accedervi utilizzando memory_order_relaxed o in Java, potrebbe essere dichiarato senza volatile e accedervi senza misure speciali. Ciò richiede la conservazione di tutti i seguenti elementi:

Dovrebbe essere possibile stabilire dal valore del campo stesso se è già stato inizializzato. Per accedere al campo, il valore test-and-return del percorso rapido deve leggere il campo solo una volta. In Java, quest'ultimo è essenziale. Anche se i test sul campo sono stati inizializzati, un secondo caricamento potrebbe leggere il valore non inizializzato precedente. In C++, la regola "Leggi una volta" è solo una buona pratica.
Sia l'inizializzazione che i caricamenti successivi devono essere atomici, in quanto gli aggiornamenti parziali non devono essere visibili. Per Java, il campo non deve essere long o double. Per C++, è necessaria un'assegnazione atomica; la sua costruzione on-premise non funzionerà, poiché la costruzione di un atomic non è atomica.
Le inizializzazioni ripetute devono essere sicure, poiché più thread potrebbero leggere contemporaneamente il valore non inizializzato. In C++, questo in genere segue il requisito "incredibilmente copiabile" imposto per tutti i tipi atomici; i tipi con puntatori di proprietà nidificati richiedono la deallocation nel costruttore della copia e non sono banali copiabili. Per Java, alcuni tipi di riferimento sono accettabili:
I riferimenti Java sono limitati a tipi immutabili contenenti solo campi finali. Il costruttore del tipo immutabile non deve pubblicare un riferimento all'oggetto. In questo caso, le regole del campo finale Java assicurano che se un lettore vede il riferimento, vedrà anche i campi finali inizializzati. C++ non ha un analogo a queste regole e i puntatori a oggetti di proprietà sono inaccettabili anche per questo motivo (oltre a violare i requisiti di "benché copiabile").

Note di chiusura

Questo documento non si limita a graffiare la superficie, ma contiene solo una piccola sgorbia. Si tratta di un argomento molto ampio e profondo. Alcuni aspetti da approfondire:

I modelli di memoria Java e C++ effettivi sono espressi in termini di relazione happens-before, che specifica quando è garantito che due azioni si verifichino in un determinato ordine. Quando abbiamo definito una corsa ai dati, abbiamo parlato in modo informale di due accessi alla memoria che avvengono "contemporaneamente". Ufficialmente, ciò significa che né l'uno né l'altro avvengono prima dell'altro. È istruttivo imparare le definizioni effettive di happens-before e synchronizes-with nel modello di memoria Java o C++. Sebbene la nozione intuitiva di "contemporaneamente" sia in genere abbastanza buona, queste definizioni sono istruttive, in particolare se stai pensando di utilizzare operazioni atomiche con ordine debole in C++ (l'attuale specifica Java definisce solo lazySet() in modo molto informale).
Scopri cosa sono e cosa non possono fare i compilatori quando riordina il codice. (la specifica JSR-133 contiene alcuni ottimi esempi di trasformazioni legali che portano a risultati inaspettati).
Scopri come scrivere classi immutabili in Java e C++. C'è molto altro oltre al semplice "non cambiare nulla dopo la creazione".
Internalizza i suggerimenti nella sezione Contemporaneità di Java efficace, seconda edizione. Ad esempio, evita di chiamare metodi che possono essere sostituiti all'interno di un blocco sincronizzato.
Leggi le API java.util.concurrent e java.util.concurrent.atomic per scoprire le API disponibili. Potresti utilizzare annotazioni di contemporaneità come @ThreadSafe e @GuardedBy (da net.jcip.annotations).

La sezione Ulteriori letture nell'appendice contiene link a documenti e siti web che spiegheranno meglio questi argomenti.

Appendice

Implementazione degli archivi di sincronizzazione

(non è una cosa che la maggior parte dei programmatori si ritrovano a implementare, ma la discussione è illuminante.)

Per i tipi integrati di piccole dimensioni come int e l'hardware supportato da Android, le normali istruzioni per il caricamento e lo store assicurano che uno store venga reso visibile nella sua interezza o per niente a un altro processore che carica la stessa posizione. Pertanto, alcune nozioni di base di "atomicità" sono fornite senza costi.

Come abbiamo visto, non è sufficiente. Per garantire la coerenza sequenziale, dobbiamo anche impedire il riordinamento delle operazioni e garantire che le operazioni di memoria diventino visibili ad altri processi in un ordine coerente. Abbiamo scoperto che il secondo è automatico sull'hardware supportato da Android, a condizione che facciamo scelte obiettive per far rispettare il primo, quindi in questo caso la ignoriamo in gran parte.

L'ordine delle operazioni sulla memoria viene mantenuto sia impedendo il riordinamento da parte del compilatore sia impedendo il riordinamento da parte dell'hardware. Qui ci concentriamo su quest'ultimo.

L'ordinamento della memoria su ARMv7, x86 e MIPS viene applicato con istruzioni "fence" che impediscono approssimativamente le istruzioni che seguono il recinto prima di diventare visibili prima delle istruzioni che lo precedono. (Anche queste sono comunemente chiamate istruzioni "barriere", ma ciò rischia di creare confusione con barriere in stile pthread_barrier, che fanno molto di più). Il significato preciso delle istruzioni di recinzione è un argomento piuttosto complicato che deve affrontare il modo in cui interagiscono le garanzie fornite da più tipi diversi di recinzioni e il modo in cui queste si combinano con altre garanzie di ordinamento solitamente fornite dall'hardware. Si tratta di una panoramica generale, quindi tratteremo questi dettagli.

Il tipo più semplice di garanzia di ordinamento è quello fornito dalle operazioni atomiche memory_order_acquire e memory_order_release di C++: le operazioni di memoria che precedono un release store devono essere visibili dopo un carico di acquisizione. Su ARMv7, questo è applicato da:

Prima delle istruzioni del negozio con un'istruzione adatta di recinzione. In questo modo tutti gli accessi alla memoria precedenti non vengono riordinati con l'istruzione di archiviazione. Inoltre, impedisce inutilmente il riordinamento con istruzioni di archiviazione successive.
Seguire l'istruzione di caricamento con un'istruzione di recinzione appropriata, per evitare che il carico venga riordinato con accessi successivi. (e ancora una volta fornendo ordini non necessari con almeno caricamenti precedenti).

Insieme, questi elementi sono sufficienti per l'ordine di acquisizione/rilascio di C++. Sono necessari, ma non sufficienti, per Java volatile o C++ per coerenza in sequenza atomic.

Per capire di cosa abbiamo bisogno, considera il frammento dell'algoritmo di Dekker che abbiamo brevemente accennato in precedenza. flag1 e flag2 sono variabili C++ atomic o volatile Java, entrambe inizialmente false.

Thread 1	Thread 2
`flag1 = true if (flag2 == false) critical-stuff`	`flag2 = true if (flag1 == false) critical-stuff`

La coerenza sequenziale implica che una delle assegnazioni a flagn deve essere eseguita per prima ed essere visualizzata dal test nell'altro thread. Pertanto, non vedremo mai questi thread eseguire i "contenuti critici" contemporaneamente.

Tuttavia, la limitazione necessaria per l'ordinamento di acquisizione-release aggiunge recinzioni solo all'inizio e alla fine di ogni thread, il che non è utile in questo caso. Dobbiamo inoltre garantire che se un negozio volatile/atomic è seguito da un caricamento volatile/atomic, i due non vengano riordinati. In genere questo viene applicato aggiungendo una barriera non solo prima di un archivio coerente in sequenza, ma anche dopo. (Questo è ancora una volta molto più forte del necessario, poiché questo recinto in genere ordina tutti gli accessi precedenti alla memoria rispetto a tutti gli accessi successivi).

Potremmo invece associare il recinto aggiuntivo a caricamenti coerenti sequenziali. Poiché gli store sono meno frequenti, la convenzione che abbiamo descritto è più comune e utilizzata su Android.

Come abbiamo visto in una sezione precedente, dobbiamo inserire una barriera negozio/carico tra le due operazioni. Il codice eseguito nella VM per un accesso volatile sarà simile al seguente:

carico volatile	negozio volatile
`reg = A fence for "acquire" (1)`	`fence for "release" (2) A = reg fence for later atomic load (3)`

Le architetture di macchine reali offrono in genere più tipi di recinzioni, che ordinano tipi diversi di accessi e possono avere costi diversi. La scelta tra questi è sottile e influenzata dalla necessità di garantire che gli archivi siano resi visibili agli altri core in un ordine coerente e che l'ordine della memoria imposto dalla combinazione di più recinzioni sia corretto. Per ulteriori dettagli, consulta la pagina della University of Cambridge in cui raccolte le mappature degli atomici agli attuali processori.

In alcune architetture, in particolare x86, le barriere di "acquisizione" e "rilascio" non sono necessarie, poiché l'hardware impone sempre implicitamente un ordine sufficiente. In questo modo su x86 viene effettivamente generato l'ultimo recinto (3). Analogamente, su x86, le operazioni atomiche di lettura, modifica e scrittura includono implicitamente una barriera efficace. Pertanto, questi non richiedono mai recinzioni. Su ARMv7 sono obbligatorie tutte le barriere di cui abbiamo parlato sopra.

ARMv8 fornisce istruzioni LDAR e STLR che applicano direttamente i requisiti di carichi e archivi Java volatili o C++ coerenti sequenziali. In questo modo si evitano gli inutili vincoli di riordinamento citati in precedenza. Questi sono utilizzati dal codice Android a 64 bit su ARM. In questo caso, abbiamo scelto di concentrarci sul posizionamento della recinzione ARMv7 perché fa luce sui requisiti effettivi.

Continua a leggere

Pagine web e documenti che offrono maggiore profondità o portata. Gli articoli più generalmente utili si trovano in cima all'elenco.

Modelli di coerenza della memoria condivisa: un tutorial: Scritto nel 1995 da Adve & Gharachorloo, questo è un buon punto di partenza se si vuole approfondire i modelli di coerenza della memoria.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Barriere di memoria: Bellissimo articolo che riassume i problemi.
https://en.wikipedia.org/wiki/Memory_barrier
Nozioni di base sui Thread: Un'introduzione alla programmazione multi-thread in C++ e Java, di Hans Boehm. Discussione sulle corse di dati e sui metodi di sincronizzazione di base.
http://www.hboehm.info/c++mm/threadsintro.html
Contemporaneità Java in pratica: Pubblicato nel 2006, questo libro tratta una vasta gamma di argomenti in modo molto dettagliato. Altamente consigliato per chiunque scriva codice multi-thread in Java.
http://www.javaconcurrencyinpractice.com
Domande frequenti su JSR-133 (modello di memoria Java): Un'introduzione delicata al modello di memoria Java, che include una spiegazione della sincronizzazione, delle variabili volatili e della costruzione dei campi finali. (Un po' datato, in particolare quando si parla di altre lingue.)
http://www.cs.umd.edu/~pugh/java/memoryModel/jsr-133-faq.html
Validità delle trasformazioni del programma nel modello di memoria Java: Una spiegazione piuttosto tecnica dei problemi rimanenti con il modello di memoria Java. Questi problemi non si applicano ai programmi data-race-free.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.1790&rep=rep1&type=pdf
Panoramica del pacchetto java.util.concurrent: La documentazione per il pacchetto java.util.concurrent. Nella parte inferiore della pagina c'è una sezione intitolata "Proprietà di coerenza della memoria" che spiega le garanzie offerte dalle varie classi.
Riepilogo del pacchetto per java.util.concurrent
Teoria e pratica Java: tecniche di costruzione sicure in Java: Questo articolo esamina in dettaglio i pericoli dell'escape dei riferimenti durante la creazione degli oggetti e fornisce linee guida per i costruttori thread-safe.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Teoria e pratica Java: gestire la volatilità: Un bel articolo che descrive ciò che è possibile o meno ottenere con i campi volatili in Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
Dichiarazione "La serratura di due controlli è rotta": La spiegazione dettagliata di Bill Pugh dei vari modi in cui la chiusura a chiave viene rotta senza volatile o atomic. Include C/C++ e Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Test di tornasole e ricettario: Una discussione sui problemi della SMP ARM, evidenziata con brevi snippet di codice ARM. Se ritieni che gli esempi riportati in questa pagina siano troppo poco specifici o vuoi leggere la descrizione formale dell'istruzione DMB, leggi questo articolo. Descrive anche le istruzioni utilizzate per le barriere di memoria sul codice eseguibile (potrebbero essere utili se si genera il codice al volo). Tieni presente che è precedente ad ARMv8, che supporta anche istruzioni aggiuntive per l'ordinamento della memoria ed è passato a un modello di memoria in qualche modo migliore. Per maggiori dettagli, consulta il "Manuale di riferimento dell'architettura ARM® ARMv8 per il profilo dell'architettura ARMv8-A".
http://infocenter.arm.com/help/topic/com.arm.doc.genc007826/Barrier_Litmus_Tests_and_Cookbook_A08.pdf
Barriere di memoria del kernel Linux: Documentazione sulle barriere alla memoria del kernel di Linux. Include alcuni esempi utili e la grafica ASCII.
http://www.kernel.org/doc/Documentazione/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21 (standard C++) 14882 (linguaggio di programmazione C++), sezione 1.10 e clausola 29 ("Libreria delle operazioni atomiche"): Bozza di standard per le caratteristiche delle operazioni atomiche in C++. Questa versione è simile allo standard C++14, che include piccole modifiche in quest'area rispetto a C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(intro: http://www.hpl.hp.com/tech0reports/2008
ISO/IEC JTC1 SC22 WG14 (standard C) 9899 (linguaggio di programmazione C) capitolo 7.16 (“Atomica <stdatomic.h>”): Bozza di standard per le funzionalità operative atomiche ISO/IEC 9899-201x C. Per maggiori dettagli, consulta anche le segnalazioni sui difetti successive.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
Mappature C/C++11 ai processori (Università di Cambridge): La raccolta di Jaroslav Sevcik e Peter Sewell per la traduzione degli atomici C++ in vari set di istruzioni per processori comuni.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
L'algoritmo di Dekker: La "prima soluzione corretta nota al problema di esclusione reciproca nella programmazione contemporanea". L'articolo di Wikipedia contiene l'algoritmo completo, con una discussione su come dovrebbe essere aggiornato per funzionare con i compilatori di ottimizzazione moderni e l'hardware SMP.
https://en.wikipedia.org/wiki/Dekker's_algorithm
Commenti su ARM e alpha e gestire le dipendenze: Un'email sulla mailing list arm-kernel di Catalin Marinas. Include un breve riepilogo delle dipendenze di indirizzo e controllo.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
Cosa dovrebbe sapere ogni programmatore sulla memoria: Un lungo articolo dettagliato sui diversi tipi di memoria, in particolare sulle cache della CPU, di Ulrich Drepper.
http://www.akkadia.org/drepper/cpumemory.pdf
Ragionamento sul modello di memoria ARM con coerenza debole: Questo articolo è stato scritto da Chong & Ishtiaq di ARM, Ltd. Il suo obiettivo è descrivere il modello di memoria ARM SMP in modo rigoroso ma accessibile. La definizione di "osservabilità" utilizzata qui deriva da questo articolo. Ancora una volta, la data precedente a ARMv8.
http://portal.acm.org/ft_gateway.cfm?id=1353528&type=pdf&coll=dl=CFID=96099715&CFTOKEN=57505711
The JSR-133 Cookbook for Compiler Writers: Doug Lea ha scritto questo testo come complementare alla documentazione JSR-133 (Java Memory Model). Contiene l'insieme iniziale di linee guida per l'implementazione del modello di memoria Java utilizzato da molti scrittori di compilatori ed è ancora ampiamente citato e probabilmente fornisce insight. Sfortunatamente, le quattro varietà di recinzioni illustrate qui non sono adatte alle architetture supportate da Android e le precedenti mappature C++11 sono ora una fonte migliore di ricette precise, anche per Java.
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO: un modello di programmatore rigoroso e utilizzabile per multiprocessori x86: Una descrizione precisa del modello di memoria x86. Descrizioni precise del modello di memoria ARM sono purtroppo molto più complicate.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf