Dopo aver letto questo mio precedente post , dovrebbe essere chiaro come sia possibile che stores/loads possano essere riordinati nel rispetto delle regole del memory model in cui il nostro codice gira.

Se ci pensiamo un attimo, la cosa non dovrebbe toccarci, nel senso che se il compilatore/processore aggiunge/toglie/sposta istruzioni per rendere tutto più performante a noi dovrebbe andare più che bene. Questo è effettivamente vero finchè non facciamo uso di tecniche di programmazione “lock free”, ovvero quando non viene fatto uso di primitive di sincronizzazione(lock(…),Monitor,Events,Mutex) per sincronizzare l’accesso a zone di memoria condivise da più thread. Questa tecnica, rende molto più scalabili e performanti le applicazioni multithread su più processori, in quanto il fatto di non mettere mai il thread in “wait” permette di avere un “throughput” maggiore a confronto di tecniche che utilizzano i lock(nessun thread “blocca” nessun altro thread, se non a basso livello, ma è trasparente a noi e viene fatto dal processore, niente context switch insomma). 

Perchè dovrebbero essere un problema quindi queste ottimizzazioni?
Perchè, mentre muovere istruzioni dal punto di vista di un solo thread quindi di un solo percorso di esecuzione non da nessuna inconsistenza, quando sono più di uno i thread che devono eseguire questo percorso in modo parallelo/contemporaneo il riordinamento di una store/load potrebbe inficiare il corretto funzionamento dell’algoritmo portando a inconsistenze e a difficili bugs da scovare/risolvere.

Per poter avere il controllo sul riordinamento(ottimizzazione) fatto da processore/compilatore, possiamo usare delle istruzioni cosiddette fences/barriers(recinto/barriera), attraverso le quali possiamo indicare al processore/compilatore quali tipi ottimizzazioni(spostamenti) sono possibili.

Ricordiamoci che le ottimizzazioni possono essere fatte a qualsiasi livello dello stack software, quindi sia a livello di compilazione che a livello di esecuzione(processore), mettere delle fence a livello di codice(compilatore) non significa metterle anche a livello di processore, tutto questo dipende dal runtime su cui state sviluppando, es:.NET, VC++, C etc..

Detto questo esistono vari tipi di fence(da ora in poi li chiamerò così e non barrier, ma sono la stessa cosa, dipende dal runtime/ambiente in cui state lavorando):

Full fence: nessuna stores o loads possono essere spostate al di là della fence, in tutte e due le direzioni(molte architetture mettono ad disposizione delle istruzioni come ad esempio MFENCE) quindi(pseudo codice):

load A
load B
store A

Fence

store B
store C
load C

le istruzioni stores/loads ABA e BCC non possono essere spostate al di là della fence in nessuna delle due direzioni, le istruzioni dopo la fence non possono muoversi prima, quelle prima non possono spostarsi dopo. Le full fence sono quelle più “rigide” e tutti gli altri tipi vengono usati per non sacrificare troppo le ottimizzazioni.

Store fence: simili alle full fence eccetto che si applicano solo alle istruzioni di stores e permettono lo spostamento delle loads. Quindi(pseudo codice):

load A
load B
store A

Store fence

store B
store C
load C

Le istruzioni loads A,B,C possono essere spostate prima/dopo della fence(questa fence è disponibile su x86 e x64 e viene generalmente esposta con l’istruzione SFENCE)

Load fence: sono il perfetto contrario delle store fence(e vengono comunemente espresse con l’istruzione LFENCE)

load A
load B
store A

Load fence

store B
store C
load C

Le istruzioni di stores A,B,C possono essere spostate prima/dopo della fence.

Come abbiamo detto prima le fence possono essere utilizzate a livello di processore(full fence, store fence, load fence), ma anche a livello di compilazione:

Acquire fence: assicurano che ne le stores ne le loads che ci sono dopo la fence possano essere spostate prima di questa. Le istruzioni che vengono prima possono essere spostate dopo.

load A
load B
store A

Acquire fence

store B
store C
load C

store B,c e load C non possono essere spostate prima della fence.

Release fence: assicurano che ne le stores ne le loads che ci sono prima della fence possano muoversi dopo della stessa. Le istruzioni dopo la fence possono essere spostate prima

load A
load B
store A

Release fence

store B
store C
load C

load A,B e store A non possono essere spostate dopo la fence.

Queste ultime due fence vengono usate dai complilatori e dall’architettura IA64, e hanno la peculiarità di essere applicate solo alla direzione e non al tipo di istruzione.

Dobbiamo assicurarci di applicare la fence sia a livello di compilatore che a livello di processore, in quanto sono 2 layer separati che possono in modo indipendente effettuare dei riordinamenti(in gergo si dice “move” o meglio “move after..” “move before..”).

Esistono vari modi di introdurre delle fence nel nostro codice e questo varia dalla piattaforma che stiamo usando(.NET,VC++, C), come ad esempio il marcare “volatile” una variabile con .NET o usare delle macro in VC++, ma ce ne sono altri e questo è argomento per un’altro post.

Per concludere è bene sottolineare che il riordinamento che viene effettuato a livello di compilatore/processore, rispetta sempre la “data dependence”(dipendenza dei dati) per non provocare errori logici durante le stores/loads(altro argomento un pò complesso che è bene trattare separatamente).

Fonti: Concurrent programming on Windows(Joe Duffy)

Nel precedente post sui memory model ho parlato spesso di loads e stores.

Si ok, ma cosa vuol dire?

Allora quando parliamo di loads si intendono quelle istruzioni che spostano i dati da una locazione di memoria in un registro del processore, mentre le stores sono quelle istruzioni che spostano i dati da un registro del processore ad una locazione di memoria.

In una architettura load/store, le istruzioni di load e store solo le uniche istruzioni che accedono ai dati in memoria.

Esempio ad alto livello:

x = 1  Store, il valore 1 verrà spostato da un registro del processore all’indirizzo in memoria x
y = x Load, il valore in memoria x verrà spostato in un registro  del processore per essere utilizzato

Così…per chiarezza.

Fonti: Concurrent Programming on Windows( Joe Duffy)

Se vi è per caso capitato di approfondire, per qualche motivo, tematiche legate all’implementazione di soluzioni che fanno uso di codice parallelo/multithread/sincronizzazione probabilmente avete finito leggendo che vi è la possibilità di aumentare le performance usando tecniche di sincronizzazione “lock free”, ovvero senza ricorrere alle primitive di sincronizzazione messe a disposizione dal sistema operativo(che consumano risorse e vanno usate con attenzione).

Molto probabilmente qualche riga sotto l’espressione “lock free” avrete sicuramente trovato che tutto questo è possibile grazie al “Memory consistency model” (anche detto semplicemente memory model) implementato dall’hardware su cui il vostro codice gira.

Ma cos’è il memory model ?Perchè è importante conoscerlo ?

Per spiegarlo facciamo un passo indietro. Quando noi scriviamo codice sorgente ci immaginiamo che l’esecuzione dello stesso sarà così come l’abbiamo scritta. Purtroppo nei moderni processori non è così, nel senso che l’esecuzione del codice macchina potrebbe risultare diversa da quella da noi pensata anche senza inficiare il corretto funzionamento dei nostri algoritmi.

Le motivazioni principali sono:

1)I compilatori ottimizzano (Jit compiler compreso) il codice, spostando (code motion),cancellando, aggiungendo istruzioni per renderne più performante l’esecuzione.
2)I processori impiegano tecniche di “instruction level parallelism” (ILP) permettendo la parallelizzazione delle istruzione così da ridurre i cicli di clock totali.
3)I processori fanno uso di cache locali per velocizzare la scrittura (stores) e lettura (loads) delle locazioni di memoria, in sistemi multiprocessore la sincronizzazione tra le varie cache può portare ad uno spostamento delle istruzioni(cache coherency).

Tutto questo passa sotto il nome di instruction reordering.

Chi scrive codice a basso livello o compilatori o codice lock free, deve conoscere molto bene questi comportamenti per poter effettuare ottimizzazioni e far funzionare come si deve il codice (cioè come noi lo abbiamo scritto o senza provocare race condition).

Per concludere il memory model specifica precisamente quali tipi di scritture (stores) e letture (loads) possono essere spostate (o riordinate), in quali circostanze e come vengono spostate l’una rispetto all’altra.

I memory model si dividono tra weak (deboli) o strong (forti). Un “weak memory model” permette il riordinamento delle letture/scritture, un “strong memory model” (sequential consistency) proibisce tale riordinamento. Molti sistemi come quelli dal quale sto scrivendo questo post (architettura Intel x86) e la maggior parte dei sistemi sul quale Windows gira utilizzano un “weak memory model”.

Fonti: Concurrent Programming on Windows (Joe Duffy)