Primer SMP per Android

Le versioni della piattaforma Android 3.0 e successive sono ottimizzate per supportare architetture multiprocessore. Questo documento introduce i problemi che possono emergere durante la scrittura di codice multithread per sistemi multiprocessore simmetrici in C, C++ e Java linguaggio di programmazione (di seguito semplicemente "Java" ai fini brevità). È inteso come un'introduzione per gli sviluppatori di app Android, non come un discussione sull'argomento.

Introduzione

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

La maggior parte dei dispositivi Android, se non tutti, disponeva sempre di più CPU, ma in passato solo uno di questi veniva utilizzato per eseguire applicazioni, mentre altri gestiscono vari frammenti dell'hardware (come la radio). Le CPU potevano avere architetture diverse e che i programmi in esecuzione non potevano usare la memoria principale per comunicare e l'altro.

La maggior parte dei dispositivi Android oggi venduti è progettata su progetti SMP, rendendo le cose un po' più complicate per gli sviluppatori di software. Condizioni gara in un programma multi-thread potrebbe non causare problemi visibili su un uniprocessore, ma potrebbero non riuscire regolarmente quando due o più thread vengono eseguiti contemporaneamente su core diversi. Inoltre, il codice potrebbe essere più o meno soggetto a errori se eseguito su diverse architetture di processori o anche su diverse implementazioni dell'architettura. Il codice che è stato accuratamente testato su x86 potrebbe non funzionare correttamente su ARM. Il codice potrebbe iniziare a non riuscire quando viene ricompilato con un compilatore più moderno.

Il resto del documento spiegherà il motivo e ti dirà cosa devi fare per assicurarti che il codice funzioni correttamente.

Modelli di coerenza della memoria: perché gli SMP sono leggermente diversi

Questa è una panoramica ad alta velocità e lucida di un argomento complesso. Alcune aree saranno incomplete, ma nessuna dovrebbe essere fuorviante o sbagliata. Come vedrai nella sezione successiva, i dettagli riportati di seguito in genere non sono importanti.

Consulta la sezione Per approfondire alla fine del documento per a un trattamento più approfondito dell'argomento.

I modelli di coerenza della memoria, o spesso semplicemente "modelli di memoria", descrivono le garanzie offerte dal linguaggio di programmazione o dall'architettura hardware in merito agli accessi alla memoria. Ad esempio: se scrivi un valore per l'indirizzo A e poi scrivi un valore per l'indirizzo B, può garantire che ogni core della CPU vede le scritture eseguite in quel ordine.

Il modello a cui la maggior parte dei programmatori è abituato è sequenziale coerenza, che viene descritta in questo modo (Adve & Gharachorloo):

  • Tutte le operazioni di memoria sembrano essere eseguite una alla volta
  • Tutte le operazioni in un singolo thread sembrano essere eseguite nell'ordine descritto dal programma di quel processore.

Supponiamo temporaneamente di avere un compilatore o un interprete molto semplice senza sorprese: traduce nel codice sorgente per caricare e memorizzare le istruzioni esattamente nell'ordine corrispondente, un'istruzione per accesso. Supponiamo anche che semplicità dell'esecuzione di ogni thread sul proprio processore.

Se osservi una porzione di codice, ti accorgi che esegue alcune operazioni di lettura e scrittura su un'architettura CPU a coerenza sequenziale, sai che il codice le operazioni di lettura e scrittura nell'ordine previsto. È possibile che La CPU riordina le istruzioni e ritarda le letture e le scritture, ma non è possibile che il codice in esecuzione sul dispositivo indichi che la CPU sta facendo qualcosa non eseguire le istruzioni in modo semplice. (Ignoraremo I/O del driver di dispositivo con mappatura alla memoria).

Per illustrare questi punti, è utile considerare piccoli snippet di codice, comunemente indicate con il nome di test del nove.

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 carosello, le posizioni dei ricordi sono rappresentate lettere maiuscole (A, B, C) e i registri della CPU iniziano con "reg". Tutta la memoria è inizialmente pari a zero. Le istruzioni vengono eseguite dall'alto verso il basso. Qui, thread 1 memorizza il valore 3 nella posizione A e il valore 5 nella posizione B. Il thread 2 carica il valore dalla posizione B in reg0 e poi carica il valore dalla posizione A in reg1. Tieni presente che stiamo scrivendo in un ordine e leggendo in un altro.

Si presume che i thread 1 e il thread 2 vengano eseguiti su core CPU diversi. Tu dovrebbero sempre fare questo presupposto quando si valutano il codice multi-thread.

La coerenza sequenziale garantisce che, al termine dell'esecuzione di entrambi i thread, i registri saranno 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 ottenere una situazione in cui vediamo B=5 prima di vedere il negozio in A, le letture o le scritture devono avvenire fuori ordine. Su un una macchina coerente in sequenza, questo non può accadere.

I processori Uni, inclusi x86 e ARM, sono normalmente a coerenza sequenziale. I thread sembrano essere eseguiti con interfoliazione, quando il kernel del sistema operativo cambia tra di loro. La maggior parte dei sistemi SMP, inclusi x86 e ARM, non sono coerenti in sequenza. Ad esempio, è pratica comune hardware nel buffer archivia in memoria, in modo che non raggiungono immediatamente la memoria e non diventano visibili agli altri core.

I dettagli variano notevolmente. Ad esempio, x86, anche se non in sequenza coerente, garantisce comunque che reg0 = 5 e reg1 = 0 resti impossibile. I negozi sono presenti nel buffer, ma il loro ordine viene mantenuto. ARM, invece, no. L'ordine dei datastore presenti nel buffer non è e i negozi potrebbero non raggiungere tutti gli altri core contemporaneamente. Queste differenze sono importanti per i programmatori di assemblaggio. Tuttavia, come vedremo sotto, i programmatori C, C++ o Java possono e devono essere programmati in modo da nascondere tali differenze architettoniche.

Finora, non realisticamente abbiamo ipotizzato che sia solo l'hardware riordina le istruzioni. In realtà, il compilatore riordina anche le istruzioni per migliorare le prestazioni. Nel nostro esempio, il compilatore potrebbe decidere che alcune nel Thread 2 aveva bisogno del valore di reg1 prima di reg0 e quindi di caricare reg1. Oppure qualche codice precedente potrebbe aver già caricato A e il compilatore potrebbe decidere di riutilizzare quel valore invece di caricare di nuovo A. In entrambi i casi, i caricamenti a reg0 e reg1 potrebbero essere riordinati.

Riordinare gli accessi a posizioni di memoria diverse nell'hardware o nel compilatore, consentito, poiché non influisce sull'esecuzione di un singolo thread e può migliorare significativamente 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 non è la prima volta che usi SMP. Anche su un uniprocessore, un compilatore potrebbe riordinare i caricamenti reg0 e reg1 nel nostro esempio e il Thread 1 potrebbe essere programmato tra istruzioni riordinate. Tuttavia, se il compilatore non dovesse eseguire il riordinamento, potremmo non osservare mai questo problema. Nella maggior parte degli SMP ARM, anche senza compilatore è probabile che la procedura di riordinamento venga mostrata, magari dopo un di esecuzioni riuscite. A meno che non si stia programmando in gruppo un linguaggio naturale, gli SMP di solito aumentano le probabilità che vengano riscontrati per tutto questo tempo.

Programmazione senza gare di dati

Fortunatamente, di solito esiste un modo semplice per evitare di pensare a uno di questi dettagli. Se segui alcune semplici regole, solitamente è sicuro tralasciare tutte le sezioni precedenti tranne la "coerenza sequenziale" . Purtroppo, le altre complicazioni possono diventare visibili violeranno accidentalmente queste regole.

I moderni linguaggi di programmazione incoraggiano quello che è noto come "data-race-free" stile di programmazione. A patto che prometti di non introdurre i "dati race", ed evitare alcuni costrutti che indicano al compilatore altrimenti, e hardware promettono di fornire risultati coerenti con la sequenza. Non evitano il riordinamento dell'accesso alla memoria. Significa che se segui le regole per cui non sarai in grado di capire che gli accessi alla memoria sono riordinato. È un po' come dire che la salsiccia è deliziosa e cibo appetitoso, purché prometti di non visitare i salumeria. Le razze nei dati rivelano la brutta verità sulla memoria e riordinamento.

Cos'è una "razza dei dati"?

Una corsa dei dati si verifica quando almeno due thread accedono contemporaneamente gli stessi dati ordinari e almeno uno di questi li modifica. Di "ordinario dati" intendiamo qualcosa che non è specificamente un oggetto di sincronizzazione destinati alle comunicazioni in thread. Silentx, variabili di condizione, Java volatili o oggetti atomici C++ non sono dati ordinari e i loro accessi possono gareggiare. Infatti, vengono utilizzati per impedire gare di dati su altri di oggetti strutturati.

Per determinare se due thread accedono contemporaneamente allo stesso posizione della memoria, possiamo ignorare la discussione sul riordinamento della memoria di cui sopra e assumono coerenza sequenziale. Il seguente programma non ha una gara di dati se A e B sono normali variabili booleane inizialmente false:

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

Poiché le operazioni non vengono riordinate, entrambe le condizioni verranno valutate come false e nessuna delle due variabili viene mai aggiornata. Pertanto, non può esserci una corsa ai dati. C'è non c'è bisogno di pensare a cosa potrebbe succedere se il carico da A e archivia in B nel Il thread 1 è stato in qualche modo riordinato. Il compilatore non è autorizzato a riordinare la classe Thread 1 riscrivendolo come "B = true; if (!A) B = false". cioè come preparare una salsiccia in mezzo alla città in pieno giorno.

Le esecuzioni dei dati sono ufficialmente definite su tipi integrati di base come i numeri interi e riferimenti o cursori. Assegnazione a int in corso contemporaneamente leggerlo in un altro thread è chiaramente una corsa ai dati. Ma sia la versione C++ libreria standard e le librerie Java raccolte sono scritte per consentire anche di ragionare le corse dei dati a livello di libreria. Promettono di non introdurre gare tra dati a meno che non ci siano accessi simultanei allo stesso contenitore, almeno uno di cui lo aggiorna. Aggiornamento di set<T> in un thread durante l'aggiornamento leggerla contemporaneamente in un altro, la libreria può introdurre e può quindi essere considerato in modo informale come una "corsa ai dati a livello di libreria". Al contrario, l'aggiornamento di un set<T> in un thread durante la lettura uno diverso dall'altro, non porta a una corsa ai dati, perché che promette di non introdurre una corsa ai dati (di basso livello) in questo caso.

In genere, gli accessi simultanei a campi diversi in una struttura di dati non possono introdurre una gara di dati. Tuttavia, c'è un'importante eccezione: 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 simile viene considerato come accesso a tutti per determinare l'esistenza di una gara di dati. Ciò riflette l'incapacità dell'hardware comune di aggiornare i singoli bit senza leggere e riscrivere anche i bit adiacenti. I programmatori Java non hanno problemi analoghi.

Evitare corse con i dati

I linguaggi di programmazione moderni forniscono una serie di meccanismi di sincronizzazione per evitare conflitti di dati. Gli strumenti di base sono:

Blocchi o Mutex
I
mutex (std::mutex o pthread_mutex_t in C++11) o i blocchi synchronized in Java possono essere utilizzati per assicurarsi che determinate sezioni di codice non vengano eseguite contemporaneamente ad altre sezioni di codice che accedono agli stessi dati. Faremo riferimento a queste e ad altre strutture simili in modo generico come "serrature". L'acquisizione coerente di un blocco specifico prima di accedere a una struttura di dati condivisa e la successiva liberazione impediscono le gare di dati durante l'accesso alla struttura di dati. Garantisce inoltre che gli aggiornamenti e gli accessi siano minimi, ovvero un altro aggiornamento della struttura dei dati può essere eseguito nel mezzo. Meritamente è di gran lunga lo strumento più comune per prevenire le corse dei dati. L'utilizzo di Java synchronized blocchi o C++ lock_guard oppure unique_lock per assicurarti che le serrature siano sbloccate correttamente evento di un'eccezione.
Variabili volatili/atomiche
Java fornisce volatile campi che supportano l'accesso simultaneo senza introdurre gruppi di dati. Dal 2011, supporto di C e C++ atomic variabili e campi con semantica simile. Si tratta di di solito più difficili da usare rispetto alle serrature, perché assicurano solo che gli accessi individuali a una singola variabile sono atomici. (In C++, normalmente si estende a semplici operazioni di lettura, modifica e scrittura, come gli incrementi. Java richiede chiamate di metodo speciali.) A differenza dei blocchi, le variabili volatile o atomic non possono essere utilizzato direttamente per evitare che altri thread interferiscano con sequenze di codice più lunghe.

È importante notare che il volatile ha e i relativi significati in C++ e Java. In C++, volatile non impedisce ai dati razze, sebbene il codice meno recente spesso lo usi come soluzione alternativa per la mancanza atomic oggetti. Questa opzione non è più consigliata. In C++, utilizza atomic<T> per le variabili a cui possono accedere contemporaneamente più thread. C++ volatile è pensato per registri dei dispositivi e simili.

Variabili C/C++ atomic o variabili volatile Java può essere usato per evitare gare di dati su altre variabili. Se flag è dichiarati di tipo atomic<bool> o atomic_bool(C/C++) o volatile boolean (Java), e inizialmente è false, il seguente snippet è "data-race-free":

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

Poiché il thread 2 attende la configurazione di flag, l'accesso a A nel thread 2 deve verificarsi dopo e non contemporaneamente al assegnata a A nel thread 1. Di conseguenza, non c'è corsa dei dati. A. La corsa su flag non viene conteggiata come una corsa ai dati, poiché gli accessi volatili/atomici non sono "accessi alla memoria ordinari".

L'implementazione è necessaria per impedire o nascondere il riordinamento della memoria in modo che un codice come la precedente cartina di tornasole comporti il comportamento previsto. Questo di solito rende volatili/atomici gli accessi alla memoria notevolmente più costosi rispetto agli accessi ordinari.

Sebbene l'esempio precedente sia privo di race condition, 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 ciclo con conseguente consumo della batteria.

Quando il riordinamento della memoria diventa visibile

La programmazione senza race condition dei dati di solito ci evita di dover gestire esplicitamente i problemi di ordinamento dell'accesso alla memoria. Tuttavia, ci sono diversi casi il riordinamento diventa visibile:
  1. Se il programma presenta un bug che causa una corsa di dati involontaria, del compilatore e delle trasformazioni hardware, mentre il comportamento del tuo programma potrebbe sorprenderti. Ad esempio, se dimentichiamo di dichiarare flag nell'esempio precedente, il Thread 2 potrebbe notare un A non inizializzato. In alternativa, il compilatore potrebbe decidere che il flag non può essere modificato durante il ciclo del thread 2 e trasformare il programma in
    Thread 1 Thread 2
    A = ...
      flag = true
    reg0 = flag; mentre (!reg0) {}
    ... = A
    Quando esegui il debug, è possibile che il loop continui per sempre nonostante il fatto che flag sia vero.
  2. C++ offre servizi per rilassarsi esplicitamente coerenza sequenziale anche in assenza di razze. Operazioni atomiche può accettare argomenti memory_order_... espliciti. Analogamente, Il pacchetto java.util.concurrent.atomic offre una maggiore limitazione gruppo di strutture simili, in particolare lazySet(). E Java i programmatori a volte usano gare intenzionali tra i dati per ottenere risultati simili. Tutte queste funzionalità forniscono miglioramenti delle prestazioni a livello generale in termini di complessità della programmazione. Ne parliamo solo brevemente di seguito.
  3. Alcuni codici C e C++ sono scritti in uno stile precedente, non del tutto coerente con gli standard di lingua attuali, in cui vengono utilizzate le variabili volatile anziché atomic e l'ordinamento della memoria è esplicitamente vietato inserendo le cosiddette fence o barriere. È necessario un ragionamento esplicito riguardo all'accesso Riordinare e comprendere i modelli di memoria hardware. Uno stile di programmazione lungo queste righe è ancora usato nel kernel Linux. Non dovrebbe nelle nuove app Android, né questo argomento non è disponibile in questa sede.

Fai pratica

Il debug dei problemi di coerenza della memoria può essere molto difficile. Se una dichiarazione di blocco, atomic o volatile mancante causa la lettura di dati non aggiornati da parte di un codice, potresti non essere in grado di capire il motivo esaminando i dump della memoria con un debugger. Quando puoi eseguire una query del debugger, i core della CPU potrebbero aver osservato l'intero insieme di accessi e i contenuti della memoria e dei registri della CPU sembreranno essere in uno stato "impossibile".

Cosa non fare in C

Di seguito vengono presentati alcuni esempi di codice errato, insieme a semplici modi per correggili. Prima di farlo, dobbiamo discutere dell'utilizzo di una funzionalità di base del linguaggio.

C/C++ e "volatile"

Le dichiarazioni volatile C e C++ sono uno strumento molto specifico. Impediscono al compilatore di riordinare o rimuovere gli accessi volatilizzati. Questo può essere utile per il codice che accede ai registri dei dispositivi hardware, alla memoria mappata a più posizioni o in connessione consetjmp. Ma C e C++ volatile, a differenza di Java volatile non è progettato per le comunicazioni in thread.

In C e C++, accede a volatile dati possono essere riordinati e consentire l'accesso a dati non volatili e non sono di atomicità. Di conseguenza, non è possibile utilizzare volatile per la condivisione di dati tra in thread in codice portabile, anche su un uniprocessore. C volatile in genere non impedisce il riarrangiamento dell'accesso da parte dell'hardware, quindi da solo è ancora meno utile in ambienti SMP multi-thread. Questo è il motivo per cui il supporto di C11 e C++11 atomic oggetti. Dovresti usare questi.

Molto codice C e C++ meno recente usa ancora volatile per il thread la comunicazione. Questa opzione spesso funziona correttamente per dati che in un registro di macchine, a condizione che venga utilizzato con recinti espliciti o in casi in cui l'ordinamento della memoria non è importante. Tuttavia, il funzionamento non è garantito in modo corretto con i futuri compilatori.

Esempi

Nella maggior parte dei casi è preferibile avere un lucchetto (ad esempio pthread_mutex_t o C++11 std::mutex) anziché una un'operazione atomica, ma utilizzeremo la seconda per illustrare come 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 è di allocare una struttura, inizializzare i suoi campi e alla fine lo "pubblichiamo" memorizzandolo in una variabile globale. A quel punto, può vederlo qualsiasi altro thread, ma va bene così, dato che è completamente inizializzato, giusto?

Il problema è che è stato possibile osservare il datastore gGlobalThing prima dell'inizializzazione dei campi, in genere perché il compilatore processore ha riordinato i negozi in gGlobalThing e thing->x. Un'altra lettura del thread di thing->x potrebbe vedere 5, 0 o anche dati non inizializzati.

Il problema principale qui è una corsa ai dati su gGlobalThing. Se il thread 1 chiama initGlobalThing() mentre il thread 2 chiama useGlobalThing(), gGlobalThing può essere leggere mentre vengono scritte.

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

atomic<MyThing*> gGlobalThing(NULL);

In questo modo le scritture saranno visibili ad altri thread nell'ordine corretto. Inoltre, garantisce di impedire alcune altre modalità di errore che sono altrimenti consentite, ma che difficilmente si verificano su hardware Android reale. Ad esempio, garantisce che non possiamo vedere Puntatore gGlobalThing scritto solo parzialmente.

Cosa non fare in Java

Non abbiamo discusso di alcune funzionalità del linguaggio Java pertinenti, quindi daremo un'occhiata dare un'occhiata veloce a questi elementi.

Tecnicamente Java non richiede che il codice sia esente da gare di dati. Ed ecco è una piccola quantità di codice Java scritto molto attentamente che funziona correttamente in presenza di gare di dati. Tuttavia, scrivere questo codice è estremamente difficile, ne parleremo solo brevemente di seguito. Per rendere le pratiche peggiori, gli esperti che hanno specificato il significato di tale codice non credono più che la specifica sia corretta. (La specifica è valida per il codice senza race condition sui dati).

Per il momento, seguiremo il modello data-race-free, per il quale Java fornisce essenzialmente le stesse garanzie di C e C++. Anche in questo caso, il linguaggio offre alcune primitive che rilassano esplicitamente la coerenza sequenziale, in particolare lazySet() e weakCompareAndSet() chiamate a java.util.concurrent.atomic. Come per C e C++, per il momento li ignoreremo.

Java "sincronizzato" e "volatile" parole chiave

La parola chiave "sincronizzato" fornisce il blocco incorporato del linguaggio Java meccanismo di attenzione. A ogni oggetto è associato un "monitor" che può essere utilizzato per fornire accesso mutuamente esclusivo. Se due thread tentano di "sincronizzarsi" il lo stesso oggetto, uno attenderà il completamento dell'altro.

Come detto in precedenza, volatile T di Java è l'analogico di atomic<T> di C++11. Gli accessi simultanei ai campi volatile sono consentiti e non generano conflitti di dati. lazySet() e altri utenti ignorati. e le corse dei dati, è compito della VM Java assicurati che i risultati siano ancora coerenti in sequenza.

In particolare, se il thread 1 scrive in un campo volatile e il thread 2 legge successivamente dallo stesso campo e vede il valore appena scritto, è garantito che il thread 2 vedrà anche tutte le scritture effettuate in precedenza dal thread 1. In termini di effetto memoria, scrivendo un volatile è analogo a una release di monitoraggio e la lettura da un elemento volatile è come l'acquisizione di un monitor.

C'è una notevole differenza da atomic in C++: Se scriviamo volatile int x; in Java, allora x++ è lo stesso di x = x + 1; questo elemento esegue un carico atomico, incrementa il risultato e quindi esegue . A differenza di C++, l'incremento nel suo complesso non è atomico. Le operazioni di incremento atomico sono invece fornite java.util.concurrent.atomic.

Esempi

Ecco un'implementazione semplice e errata di un contatore monotono: (Teoria e pratica di 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ù di thread e vogliamo essere sicuri che ogni thread veda il conteggio attuale Chiamata get(). Il problema più evidente è che mValue++ consiste in tre operazioni:

  1. reg = mValue
  2. reg = reg + 1
  3. mValue = reg

Se due thread vengono eseguiti in incr() contemporaneamente, uno dei gli aggiornamenti potrebbero andare persi. Per rendere l'incremento atomico, dobbiamo dichiarare incr() "sincronizzato".

Tuttavia, non funziona ancora, soprattutto su SMP. C'è ancora una corsa ai dati, in quanto get() può accedere a mValue contemporaneamente incr(). Secondo le regole Java, la chiamata get() può essere sembrano essere riordinati rispetto ad altri codici. Ad esempio, se leggiamo due contatori di fila, i risultati potrebbero essere incoerenti perché le chiamate get() che abbiamo riordinato, dall'hardware o compilatore. Possiamo risolvere il problema dichiarando che get() sincronizzati. Con questa modifica, il codice è ovviamente corretto.

Purtroppo, abbiamo introdotto la possibilità di contesa del blocco, che potrebbe ostacolare il rendimento. Invece di dichiarare che get() è sincronizzati, potremmo dichiarare mValue con "volatile". (Nota incr() deve ancora utilizzare synchronize dal giorno mValue++ non è altrimenti una singola operazione atomica. In questo modo vengono evitate anche le race dei dati, quindi la coerenza sequenziale viene preservata. incr() sarà un po' più lento, poiché comporta sia l'accesso sia l'uscita di monitoraggio overhead e l'overhead associato a un archivio volatile, ma get() sarà più veloce, quindi anche in assenza di conflitti è una vittoria se le letture superano di gran lunga le scritture. (Vedi anche AtomicInteger per un modo per completare rimuovi il blocco sincronizzato).

Ecco un altro esempio, simile nella forma 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 una corsa ai dati il giorno sGoodies. Di conseguenza il compito È possibile osservare sGoodies = goods prima dell'inizializzazione dell'output campi in goods. Se dichiari sGoodies con il parametro volatile parola chiave, la coerenza sequenziale viene ripristinata e tutto funzionerà come previsto.

Tieni presente che solo il riferimento sGoodies stesso è volatile. La ai campi al suo interno non lo sono. Una volta che sGoodies è volatile e l'ordine della memoria viene conservato correttamente, i campi non è possibile accedervi contemporaneamente. L'istruzione z = sGoodies.x eseguirà un carico volatile di MyClass.sGoodies seguito da un carico non volatile di sGoodies.x. Se crei una sede riferimento MyGoodies localGoods = sGoodies, un elemento z = localGoods.x successivo non eseguirà alcun caricamento volatile.

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

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

L'idea è di voler avere una singola istanza di un Helper associato a un'istanza di MyClass. Dobbiamo crearlo solo una volta, quindi lo creiamo e lo restituiamo tramite una funzione getHelper() dedicata. Per evitare una situazione di concorrenza in cui due thread creano l'istanza, dobbiamo sincronizzare la creazione dell'oggetto. Tuttavia, non vogliamo pagare l'overhead per il blocco "sincronizzato" a ogni chiamata, quindi lo facciamo solo se Al momento helper è nullo.

C'è una corsa dei dati sul campo helper. È possibile impostato contemporaneamente a helper == null in un altro thread.

Per vedere come ciò può non riuscire, 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 Helper’s attività costruttore):

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'ordine in helper con quelli dei campi x/y. Un altro thread potrebbe trovare helper non null ma i relativi campi non sono ancora impostati e pronti per l'uso. Per ulteriori dettagli e altre modalità di errore, consulta la sezione ""Verifica verificata" il link " Locking is Broken' Claim"" nell'appendice per maggiori dettagli. 71 ("Usa l'inizializzazione lazy con giudizio") in Effective Java di Josh Bloch, seconda edizione.

Puoi risolvere il problema in due modi:

  1. Fai la cosa più semplice ed elimina il controllo esterno. In questo modo ci assicuriamo che esamina il valore di helper all'esterno di un blocco sincronizzato.
  2. Dichiara la volatile di helper. Con questa piccola modifica, il codice nell'esempio J-3 funzionerà correttamente su Java 1.5 e versioni successive. (Potresti prendere hai un minuto per convincerti che è vera.)

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

Se guardi useValues(), se il Thread 2 non ha ancora osservato il viene aggiornato a vol1, non può sapere se data1 o data2 è stato ancora impostato. Una volta individuato l'aggiornamento a vol1, sa che è possibile accedere in sicurezza a data1 e leggere correttamente senza introdurre una corsa ai dati. Tuttavia, non può fare ipotesi su data2, perché quel negozio era eseguite dopo lo spazio di archiviazione volatile.

Tieni presente che volatile non può essere utilizzato per impedire il riordinamento di altri accessi alla memoria in competizione tra loro. Non è garantito che genera un'istruzione di recinto di memoria di una macchina. Può essere usato per prevenire l'esecuzione di codice solo quando un altro thread ha soddisfatto una determinata condizione.

Cosa fare

In C/C++, preferire C++11 classi di sincronizzazione, come std::mutex. In caso contrario, utilizza le operazioni pthread corrispondenti. Includono le corrette restrizioni di memoria, fornendo una definizione corretta (in sequenza coerente se non diversamente specificato) ed efficiente su tutte le versioni della piattaforma Android. Assicurati di utilizzarli in modo corretto. Ad esempio, ricorda che la variabile di condizione attende in modo anomalo ritornano senza essere segnalati e dovrebbero quindi apparire in un loop.

È meglio evitare di utilizzare direttamente le funzioni atomiche, a meno che la struttura dei dati che stai implementando è estremamente semplice, come un contatore. Blocco e lo sblocco di un mutex pthread richiede una singola operazione atomica ciascuno, e spesso costano meno di un singolo fallimento della cache, se non , quindi non risparmierai molto sostituendo le chiamate mutex con operazioni atomiche. I progetti senza blocco per strutture di dati non banali richiedono molto più impegno per garantire che le operazioni di livello superiore sulla struttura di dati appaiano atomiche (nel loro complesso, non solo nei loro componenti esplicitamente atomici).

Se si usano operazioni atomiche, si può rallentare l'ordinamento con memory_order... o lazySet() potrebbero fornire risultati vantaggi, ma richiede una conoscenza più approfondita di quanto abbiamo comunicato finora. Una grande parte del codice esistente che li utilizza viene rilevata con bug a posteriori. Se possibile, evita questi comportamenti. Se i tuoi casi d'uso non corrispondono esattamente a uno di quelli descritti nella sezione successiva, assicurati di essere un esperto o di averne consultato uno.

Evita di utilizzare volatile per le comunicazioni thread in C/C++.

In Java, i problemi di contemporaneità sono spesso risolti al meglio utilizzando una classe di utilità appropriata il 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. Oggetti da classi come Stringhe e Integer di Java che non possono essere modificate una volta ed evitare tutte le possibili corse di dati su questi oggetti. Il libro in vigore Java, 2nd Ed. contiene istruzioni specifiche in "Elemento 15: ridurre al minimo la modificabilità". Nota in in particolare l'importanza di dichiarare i campi Java "finali" (Bloch).

Anche se un oggetto è immutabile, ricorda che comunicarlo a un altro un thread senza alcun tipo di sincronizzazione è una corsa ai dati. A volte questo può essere accettabile in Java (vedi di seguito), ma richiede molta attenzione e può portare a un codice fragile. Se non sono estremamente critici, aggiungi un Dichiarazione volatile. In C++, comunicare un puntatore o riferimento a un oggetto immutabile senza un'adeguata sincronizzazione, come in qualsiasi etnia tra dati e dati, è un bug. In questo caso, è ragionevolmente probabile che si verifichino arresti anomali intermittenti poiché, ad esempio, il thread ricevente potrebbe visualizzare una tabella di metodo non inizializzata dovuto al riordinamento del negozio.

Se né una classe di libreria esistente né una classe immutabile sono appropriate, deve essere utilizzata l'istruzione synchronized di Java o lock_guard/unique_lock di C++ per proteggere gli accessi a qualsiasi campo a cui è possibile accedere da più thread. Se i mutex non adatta alla tua situazione, devi dichiarare i campi condivisi volatile o atomic, ma devi prestare molta attenzione a comprendere le interazioni tra i thread. Queste dichiarazioni non ti salveranno dagli errori comuni di programmazione concorrente, ma ti aiuteranno a evitare gli errori misteriosi associati all'ottimizzazione dei compilatori e ai problemi SMP.

Da evitare "pubblicazione" riferimento a un oggetto, ovvero rendendolo disponibile ad altri nel suo costruttore. Ciò è meno importante in C++ o se agisci la nostra "concorrenza senza dati" consigli in Java. Ma è sempre un buon consiglio e diventa è fondamentale se il tuo codice Java vengono eseguiti in altri contesti in cui il modello di sicurezza Java è importante e non sono attendibili potrebbe introdurre una corsa di dati accedendo a quel file come riferimento all'oggetto. È fondamentale anche se scegli di ignorare i nostri avvisi e utilizzare alcune delle tecniche nella prossima sezione. Consulta (Tecniche di costruzione sicure in Java) per dettagli

Qualche informazione in più sugli ordini di memoria inefficaci

C++11 e versioni successive forniscono meccanismi espliciti per allentare il flusso sequenziale in modo coerente per programmi senza gare di dati. Esplicito memory_order_relaxed, memory_order_acquire (caricamenti) solo) e memory_order_release(solo archivia) per i dati atomici ciascuna delle operazioni fornisce garanzie decisamente più deboli rispetto a quelle predefinite, tipicamente implicito, memory_order_seq_cst. memory_order_acq_rel fornisce sia memory_order_acquire che Garanzie memory_order_release per la scrittura atomica di lettura e modifica operazioni aziendali. memory_order_consume non è ancora sufficiente ben specificato o implementato per essere utile, e per il momento dovrebbe essere ignorato.

I metodi lazySet in Java.util.concurrent.atomic sono simili ai datastore C++ memory_order_release. di Java le variabili ordinarie vengono talvolta utilizzate in sostituzione memory_order_relaxed accessi, anche se in realtà sono ancora più debole. A differenza di C++, non esiste un vero meccanismo per accede a variabili dichiarate come volatile.

In genere, dovresti evitarli, a meno che non ci siano motivi urgenti di rendimento per usarli. Sulle architetture delle macchine debolmente ordinate come ARM, il loro utilizzo di solito risparmiano nell'ordine di qualche decina di cicli di macchina per ogni operazione atomica. Su x86, il miglioramento delle prestazioni è limitato ai negozi e probabilmente meno evidente. In modo un po' controintuitivo, il vantaggio potrebbe diminuire con un numero maggiore di core, poiché il sistema di memoria diventa un fattore limitante.

La semantica completa degli elementi atomici con ordine debole è complicata. In generale richiedono una comprensione precisa delle regole del linguaggio, che analizzeremo non entrare qui. Ad esempio:

  • Il compilatore o l'hardware può spostare memory_order_relaxed accede a (ma non all'esterno) una sezione critica delimitata da un blocco acquisizione e rilascio. Ciò significa che due memory_order_relaxed negozi potrebbero diventare visibili fuori sequenza, anche se sono separati da una sezione critica.
  • Potrebbe essere visualizzata una variabile Java ordinaria, se utilizzata in modo illecito come contatore condiviso a un altro thread per diminuire, anche se viene incrementato di un solo in un altro thread. Ma questo non è vero per i modelli atomici C++ memory_order_relaxed.

Detto questo, diamo un piccolo numero di espressioni idiomatiche che sembrano coprire molti degli usi casi di atomici debolmente ordinati. Molti di questi sono applicabili solo a C++.

Accessi non in gare

È abbastanza comune che una variabile sia atomica perché a volte lo è. lettura contemporaneamente a una scrittura, ma non tutti gli accessi presentano questo problema. Ad esempio, una variabile potrebbe dover essere atomico perché viene letto al di fuori di una sezione critica, aggiornamenti sono protetti da un blocco. In questo caso, una lettura che si verifica dalla stessa serratura non può gareggiare, poiché non possono essere eseguite scritture simultanee. In tal caso, (in questo caso, carica), 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 merito all'accesso da parte di altri thread e memory_order_relaxed che sostanzialmente non richiede ulteriori vincoli di ordinamento applicati in modo forzato per l'accesso atomico.

Non esiste un reale analogo in Java.

Il risultato non è affidabile per la correttezza

Quando usiamo un carico racing solo per generare un suggerimento, in genere va bene anche per non applicare alcun ordinamento della memoria per il carico. Se il valore è non è affidabile, né possiamo usare in modo affidabile il risultato per dedurre e altre variabili. Va bene quindi se l'ordinamento della memoria non è garantito e il carico viene fornito con un argomento memory_order_relaxed.

Un comune di questo è l'uso di C++ compare_exchange per sostituire atomicamente x con f(x). Il caricamento iniziale di x per il calcolo di f(x) non deve essere affidabile. Se sbagliamo, compare_exchange non riuscirà e riproveremo. Il caricamento iniziale di x può essere utilizzato un argomento memory_order_relaxed; solo ordine della memoria per le pratiche compare_exchange effettive.

Dati modificati atomicamente, ma non letti

A volte i dati vengono modificati in parallelo da più thread, non viene esaminata finché non è completato il calcolo parallelo. Un buon un esempio è un contatore con incrementi atomici (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 una volta completati tutti gli aggiornamenti.

In questo caso, non è possibile stabilire se gli accessi a questi dati è stato riordinato, quindi il codice C++ potrebbe utilizzare un memory_order_relaxed .

Un esempio comune di ciò sono i contatori di eventi semplici. Dato che è così 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 rendimento più importante: ogni aggiornamento richiede l'accesso esclusivo alla riga della cache che contiene il contatore. Questo determina un fallimento della cache ogni volta che un nuovo thread accede al contatore. Se gli aggiornamenti sono frequenti e si alternano tra thread, è molto più veloce per evitare di aggiornare ogni volta il contatore condiviso, ad esempio utilizzando i contatori locali dei thread e sommandoli alla fine.
  • Questa tecnica è combinabile con la sezione precedente: è possibile leggere contemporaneamente valori approssimati e inaffidabili durante l'aggiornamento, con tutte le operazioni che utilizzano memory_order_relaxed. Tuttavia, è importante considerare i valori risultanti come completamente inaffidabili. Il semplice fatto che il conteggio sia stato incrementato una volta sola non significa che è possibile contare su un altro thread per raggiungere il punto a cui è stato eseguito l'incremento. L'incremento può invece avere sono state riordinate con il codice precedente. (Per quanto riguarda il caso simile, abbiamo detto in precedenza, C++ garantisce che un secondo caricamento di questo contatore non restituiscono un valore inferiore a quello di un caricamento precedente nello stesso thread. A meno che durante l'overflow.)
  • È comune trovare codice che tenta di calcolare valori approssimativi del contatore eseguendo singole letture e scritture atomiche (o meno), ma non rendendo atomico l'incremento nel suo complesso. L'argomento di solito è che si tratta di un valore "sufficientemente simile" per i contatori delle prestazioni o simili. In genere non è così. Quando gli aggiornamenti sono sufficientemente frequenti (un caso che probabilmente ti interessano), un'ampia parte dei conteggi è in genere hanno perso. Su un dispositivo quad core, in genere può essere persa più della metà dei conteggi. (esercizio semplice: crea uno scenario a due thread in cui il contatore venga aggiornato un milione di volte, ma il valore finale del contatore è uno.

Comunicazione semplice delle segnalazioni

Un archivio memory_order_release (o un'operazione di lettura, modifica e scrittura) garantisce che, in caso di successivo caricamento di memory_order_acquire (o l'operazione di lettura, modifica e scrittura) legge il valore scritto, osservare anche gli eventuali archivi (ordinari o atomici) che hanno preceduto il Un negozio memory_order_release. Al contrario, qualsiasi caricamento che precede il memory_order_release non osserverà alcuna negozi che hanno seguito il caricamento di memory_order_acquire. A differenza di memory_order_relaxed, questo consente di utilizzare queste operazioni atomiche per comunicare l'avanzamento di un thread a un altro.

Possiamo riscrivere l'esempio di blocco controllato dall'alto in C++ come

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'acquisizione, il caricamento e il rilascio dello spazio di archiviazione assicurano che, se viene visualizzato un valore non nullo helper, verranno visualizzati anche i relativi campi inizializzati correttamente. Abbiamo anche incorporato l'osservazione precedente secondo cui i carichi non correlati alle corse possono usare memory_order_relaxed.

Un programmatore Java potrebbe rappresentare ovviamente helper come un java.util.concurrent.atomic.AtomicReference<Helper> e usa lazySet() come archivio per le release. Il carico operazioni continueranno a utilizzare le chiamate get() semplici.

In entrambi i casi, la nostra modifica delle prestazioni si è concentrata sull'inizializzazione che probabilmente è 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;
    }

In questo modo si presenta lo stesso percorso veloce, ma viene utilizzato il modello predefinito. le operazioni coerenti in sequenza sul piano del tuo percorso di apprendimento.

Anche qui, helper.load(memory_order_acquire) è probabilmente genererà lo stesso codice sulla versione attuale supportata da Android di architetture come un semplice riferimento (coerente in sequenza) 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'acquisizione/rilascio degli ordini non impedisce ai negozi di acquisire visibilità in ritardo e non assicura che i negozi diventino visibili ad altri thread in un ordine coerente. Di conseguenza, non supporta una ma un pattern di programmazione abbastanza comune esemplificato dall'esclusione reciproca di Dekker algoritmo: tutti i thread impostano prima un flag che indica che vogliono eseguire l'operazione qualcosa; se un thread t nota che non sono presenti altri thread di fare qualcosa, può procedere tranquillamente, sapendo che non vi saranno interferenze. Nessun altro thread potrà procedere, poiché il flag di t è ancora impostato. Operazione non riuscita se si accede al flag usando l'ordinamento di acquisizione/release, dato che evitare di rendere visibile il flag di un thread agli altri in ritardo, dopo che proceduto erroneamente. Valore predefinito: memory_order_seq_cst lo impedisce.

Campi immutabili

Se un campo oggetto viene inizializzato al primo utilizzo e poi non viene mai modificato, può essere possibile inizializzarlo e poi leggerlo usando un linguaggio per gli accessi ordinati. In C++, potrebbe essere dichiarato atomic. e se si accede utilizzando memory_order_relaxed o in Java, possono essere dichiarati senza volatile e accedervi senza misure speciali. Ciò richiede la conservazione di tutti i seguenti elementi:

  • Deve essere possibile distinguere il valore del campo stesso se è già stato inizializzato. Per accedere al campo, il valore di prova e ritorno del percorso rapido deve leggere il campo una sola volta. Quest'ultimo è essenziale in Java. Anche se il campo viene verificato come inizializzato, un secondo caricamento potrebbe leggere il valore non inizializzato precedente. In C++ "Leggi una volta" è solo una buona pratica.
  • Sia l'inizializzazione sia i caricamenti successivi devono essere atomici, nel senso che gli aggiornamenti parziali non devono essere visibili. Per Java, il campo non deve essere long o double. Per C++, è necessaria un'assegnazione atomica; non sarà efficace perché la costruzione di un atomic non è atomica.
  • Le inizializzazioni ripetute devono essere sicure, poiché più thread può leggere contemporaneamente il valore non inizializzato. In C++, generalmente segue dal "banale copiabile" requisito imposto per tutti tipi atomici; tipi con puntatori di proprietà nidificati richiederebbero deallocation nel e non sarebbe banalmente copiabile. Per Java, sono accettabili alcuni tipi di riferimento:
  • I riferimenti Java sono limitati a tipi immutabili contenenti solo tipi finali campi. Il costruttore del tipo immutabile non deve pubblicare un riferimento all'oggetto. In questo caso, le regole del campo finale Java assicurati che se un lettore vede il riferimento, vedrà anche inizializzati con i campi finali. C++ non ha analogie con queste regole e anche i puntatori a oggetti posseduti non sono accettabili per questo motivo (in oltre a violare il "banale copiabile" requisiti).

Note di chiusura

Questo documento non si limita a graffiare la superficie, non si tratta solo di una sgorbia superficiale. Questo è un argomento molto ampio e approfondito. Alcune aree di approfondimento:

  • Gli effettivi modelli di memoria Java e C++ sono espressi in termini di La relazione happens-before che specifica quando sono garantite due azioni devono verificarsi in un determinato ordine. Quando abbiamo definito una corsa ai dati, in modo informale abbiamo parlato di due accessi alla memoria che avvengono "contemporaneamente". Ufficialmente, si tratta di un evento che non si verifica prima dell'altro. È istruttivo apprendere le effettive definizioni di happens-before e synchronizes-with nel modello di memoria Java o C++. Sebbene la nozione intuitiva di "simultaneamente" è generalmente buono abbastanza, queste definizioni sono istruttive, in particolare se stanno contemplando l'utilizzo di operazioni atomiche debolmente ordinate in C++. (La specifica Java corrente definisce solo lazySet() in modo molto informale).
  • Scopri quali sono i compilatori e quali non sono autorizzati a fare quando riordina il codice. Le specifiche JSR-133 presentano alcuni ottimi esempi di trasformazioni legali che portano risultati imprevisti).
  • Scopri come scrivere classi immutabili in Java e C++. Ma non è tutto che non limitarti a "non cambiare nulla dopo la costruzione".)
  • Interiorizzare i suggerimenti nella sezione Contemporaneità di Efficaci Java, seconda edizione. Ad esempio, evita di chiamare metodi che deve essere ignorata mentre si trova all'interno di un blocco sincronizzato).
  • Consulta le API java.util.concurrent e java.util.concurrent.atomic per scoprire cosa è disponibile. Valuta l'uso annotazioni di contemporaneità come @ThreadSafe e @GuardedBy (da net.jcip.annotations).

La sezione Per approfondire nell'appendice contiene link a documenti e siti web che chiariscano meglio questi argomenti.

Appendice

Implementazione degli archivi di sincronizzazione

(Non è un'applicazione che la maggior parte dei programmatori si ritrova a implementare, ma la discussione è illuminante.)

Per tipi integrati di piccole dimensioni come int e hardware supportato da Android, il caricamento ordinario e le istruzioni di archiviazione assicurano che saranno resi visibili nella loro interezza o addirittura non a un altro di un processore che carica la stessa posizione. Di conseguenza, un concetto di base di "atomicità" è offerto senza costi.

Come abbiamo visto prima, questo non basta. Per garantire l'uso di e coerenza, dobbiamo anche impedire il riordinamento delle operazioni e garantire le operazioni di memoria diventano visibili ad altri processi ordine. Risulta che quest'ultima è automatica sulle app supportate da Android. hardware, a condizione che facciamo delle scelte ponderate per far valere il primo, quindi lo ignoriamo ampiamente.

L'ordine delle operazioni di memoria viene mantenuto impedendo il riordinamento da parte del compilatore e impedisce il riordinamento da parte dell'hardware. In questo caso concentriamo quest'ultimo.

L'ordinamento di memoria su ARMv7, x86 e MIPS viene applicato con "recinto" le istruzioni evitare all'incirca le istruzioni che seguono il recinto di diventare visibili prima delle istruzioni che precedono il recinto. (anche questi sono comunemente chiamata "barriera" istruzioni, ma questo rischia di fare confusione con Barriere in stile pthread_barrier, che fanno molto di più di questo.) Il significato esatto di le istruzioni per il recinto è un argomento piuttosto complicato che deve affrontare il modo in cui le garanzie fornite da più tipi diversi di recinti interagiscono e come queste si combinano con altre garanzie di ordinazione solitamente forniti dall'hardware. Questa è una panoramica generale, quindi lucida questi dettagli.

Il tipo più semplice di garanzia di ordinazione è quello fornito da C++ memory_order_acquire e memory_order_release operazioni atomiche: operazioni di memoria che precedono un archivio di release dovrebbe essere visibile dopo un carico di acquisizione. Su ARMv7, questo viene applicato da:

  • Deve precedere l'istruzione store con un'istruzione di recinzione adatta. In questo modo si impedisce che tutti gli accessi precedenti alla memoria vengano riordinati con istruzione del negozio. (Inoltre, impedisce inutilmente il riordinamento con per archiviare in un secondo momento.)
  • Seguendo le istruzioni di caricamento con un'istruzione di recinzione adatta, impedendo il riordinamento del carico con accessi successivi. Ancora una volta, fornendo gli ordini non necessari con almeno i caricamenti precedenti.

Insieme sono sufficienti per ordinare le release in C++. Sono necessari, ma non sufficienti, per Java volatile o C++ coerente in sequenza atomic.

Per capire di cosa abbiamo bisogno, consideriamo il frammento dell'algoritmo di Dekker che abbiamo menzionato brevemente in precedenza. flag1 e flag2 sono C++ atomic o variabili 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 flagn deve essere prima eseguita e deve essere visualizzata dal nell'altro thread. Pertanto, non vedremo mai questi thread eseguire contemporaneamente le "cose critiche".

Tuttavia, la recinzione richiesta per l'ordinamento di acquisizioni-release aggiunge solo all'inizio e alla fine di ogni thread, il che non aiuta qui. Dobbiamo inoltre garantire che, se volatile/atomic negozio è seguito da a un caricamento di volatile/atomic, i due elementi non vengono riordinati. In genere, questo viene applicato aggiungendo una barriera non solo prima di un magazzino coerente in sequenza, ma anche dopo. Anche in questo caso è molto più forte di quanto richiesto, dato che questa recinzione in genere ordina a tutti gli accessi precedenti alla memoria rispetto a quelli successivi.)

Potremmo invece associare in sequenza la recinzione aggiuntiva a carichi costanti. Poiché i negozi sono meno frequenti, la convenzione che abbiamo descritto è più comune e usato 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 avrà il seguente aspetto:

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 forniscono comunemente più tipi di barriere, che ordinano diversi tipi di accessi e possono avere costi diversi. La scelta tra queste è sottile e influenzata dalla necessità di garantire che gli store siano resi visibili agli altri core in un ordine coerente e che l'ordinamento della memoria imposto dalla combinazione di più recinti sia composto correttamente. Per ulteriori dettagli, consulta la pagina dell'Università di Cambridge con raccolte di mappature degli atomici ai processori effettivi.

In alcune architetture, in particolare x86, il processo "acquisire" e "release" le barriere non sono necessarie, in quanto l'hardware è sempre implicitamente applica un ordine sufficiente. Perciò su x86 solo l'ultima recinzione (3) viene generato. Analogamente, su x86, le funzionalità di lettura, modifica e scrittura atomiche le operazioni includono implicitamente un forte recinto. Di conseguenza, richiedono recinti. Su ARMv7 sono obbligatori tutti i recinti discussi sopra.

ARMv8 fornisce istruzioni LDAR e STLR che applicare i requisiti di Java volatile o C++ coerente in modo sequenziale carichi di lavoro e archiviazione. In questo modo si evitano i vincoli inutili di riordinamento di cui sopra. Il codice Android a 64 bit su ARM li utilizza; abbiamo scelto di concentrarci sul posizionamento dei recinti ARMv7 perché chiarisce meglio i requisiti effettivi.

Continua a leggere

Pagine web e documenti che forniscono maggiore profondità o ampiezza. Gli articoli più utili in generale si trovano più in alto nell'elenco.

Modelli di coerenza della memoria condivisi: un tutorial
Scritto nel 1995 da Adve & Questo è un buon punto di partenza se vuoi approfondire i modelli di coerenza della memoria.
http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf
Barriere della memoria
Un piccolo articolo carino che riassume i problemi.
https://it.wikipedia.org/wiki/Memory_barrier
Nozioni di base sui thread
Un'introduzione alla programmazione multi-thread in C++ e Java, a cura di Hans Boehm. Discussione sulle corse dei 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 con grande dettaglio. Altamente consigliato per chiunque scriva codice multi-thread in Java.
http://www.javaconcurrencyinpractice.com
Domande frequenti sulla JSR-133 (modello di memoria Java)
Una leggera introduzione al modello di memoria Java, che include una spiegazione della sincronizzazione, delle variabili volatili e della costruzione dei campi finali. (Un po' datato, soprattutto 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 relativi alla modello di memoria Java. Questi problemi non si applicano ai data-race-free programmi.
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 è presente una sezione intitolata "Proprietà di coerenza della memoria" che spiega le garanzie offerte dalle varie classi.
java.util.concurrent Riepilogo del pacchetto
Teoria e pratica di Java: tecniche di costruzione sicure in Java
Questo articolo esamina in dettaglio i pericoli dell'escape dei riferimenti durante la creazione di oggetti e fornisce linee guida per i costruttori sicuri per i thread.
http://www.ibm.com/developerworks/java/library/j-jtp0618.html
Teoria e pratica Java: gestione della volatilità
Un bel articolo che descrive ciò che si può e non si può ottenere con i campi volatili in Java.
http://www.ibm.com/developerworks/java/library/j-jtp06197.html
Dichiarazione "Il blocco a doppio controllo è rotto"
Spiegazione dettagliata di Bill Pugh dei vari modi in cui la serratura controllata si rompe senza volatile o atomic. Include C/C++ e Java.
http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html
[ARM] Barrier Litmus Tests e ricettario
Una discussione sui problemi di ARM SMP, illuminata da brevi snippet di codice ARM. Se ritieni che gli esempi in questa pagina non siano abbastanza specifici o se vuoi leggere la descrizione formale dell'istruzione DMB, leggi questo articolo. Descrive anche le istruzioni utilizzate per le barriere di memoria sul codice eseguibile (probabilmente utili se stai generando codice al volo). È antecedente ad ARMv8, che a sua volta supporta istruzioni di ordinamento della memoria aggiuntive e si sposta in una struttura un modello di memoria. (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 della memoria del kernel Linux
Documentazione per le barriere della memoria del kernel Linux. Sono inclusi alcuni esempi utili e grafica ASCII.
http://www.kernel.org/doc/Documentation/memory-barriers.txt
ISO/IEC JTC1 SC22 WG21 (standard C++) 14882 (linguaggio di programmazione C++), sezione 1.10 e clausola 29 ("Libreria operazioni atomiche")
Standard in bozza per le caratteristiche delle operazioni atomiche C++. Questa versione è vicino allo standard C++14, che include piccole modifiche in quest'area da C++11.
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4527.pdf
(introduzione: http://www.hpl.hp.com/techreports/2008/HPL-2008-56.pdf)
ISO/IEC JTC1 SC22 WG14 (standard C) 9899 (linguaggio di programmazione C) capitolo 7.16 (“Atomics <stdatomic.h>”)
Standard bozza per caratteristiche operative atomiche ISO/IEC 9899-201x C. Per informazioni dettagliate, controlla anche i report sui problemi in seguito.
http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf
Mappature C/C++11 ai processori (University of Cambridge)
Raccolta di traduzioni di Jaroslav Sevcik e Peter Sewell di atomici C++ a vari set di istruzioni comuni del processore.
http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
Algoritmo di Dekker
La "prima soluzione corretta nota al problema di mutua esclusione nella programmazione concorrente". 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://it.wikipedia.org/wiki/Algoritmo_di_Dekker
Commenti su ARM rispetto ad alpha e dipendenze degli indirizzi
Un'email alla mailing list di Catalin Marinas. Include un riepilogo delle dipendenze di indirizzi e controlli.
http://linux.derkeiler.com/Mailing-Lists/Kernel/2009-05/msg11811.html
Cosa ogni programmatore dovrebbe sapere sulla memoria
Un articolo molto lungo e dettagliato di Ulrich Drepper sui diversi tipi di memoria, in particolare sulle cache della CPU.
http://www.akkadia.org/drepper/cpumemory.pdf
Ragionamento sul modello di memoria poco coerente ARM
Questo documento è stato scritto da Chong e Ishtiaq di ARM, Ltd. Cerca di descrivere il modello di memoria ARM SMP in modo rigoroso ma accessibile. La definizione di "osservabilità" utilizzata qui proviene da questo documento. Anche in questo caso, è precedente ad 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 lo ha scritto come complemento della documentazione JSR-133 (Java Memory Model). Contiene l'insieme iniziale di linee guida per l'implementazione per il modello di memoria Java utilizzato da molti autori di compilatori ed è ancora ampiamente citato e probabilmente in grado di fornire informazioni. Purtroppo, le quattro varietà di recinzioni discusse qui non sono buone corrispondono alle architetture supportate da Android e alle mappature C++11 di cui sopra sono ora una fonte migliore di formule precise, anche per Java.
http://g.oswego.edu/dl/jmm/cookbook.html
x86-TSO: a Rigorous and Usable Programmer’s Model for x86 Multiprocessors
Una descrizione precisa del modello di memoria x86. Descrizioni precise di i modelli di memoria ARM sono purtroppo molto più complicati.
http://www.cl.cam.ac.uk/~pes20/weakmemory/cacm.pdf