Approfondimento sul multi threading secondo James Tiberius Kirk

Miniguida sul Multi-Threading

di James Tiberius Kirk

Sommario:
1. Introduzione
2. Perche' e quando
3. GUI (interfaccia grafica)
4. I/O
5. Multi-core
6. Primitive (operazioni atomiche)
7. Ottimizzazioni del Processore
8. Parallelismo
9. Granularita'
10. Race conditions & dead/livelocks
11. Priority inversion
12. Futuro
13. Conclusioni

1. Introduzione
Il Multi-threading e' una delle cose piu' complicate mai incontrate nella programmazione, almeno finche' altri algoritmi o nuove tecnologie non saranno disponibili. In questo articolo provero' a fare una panoramica (e mi scuso quindi in anticipo per le semplificazioni) del multi-threading senza alcuna pretesa di essere esaustivo: l'argomento e' talmente vasto che richiederebbe un libro a se' stante. Unico prerequisito e' la conoscenza delle basi della programmazione e la consapevolezza di cosa siano i threads e il multi-threading in generale. Qualora tale ultimo prerequisito non sia soddisfatto vi invito a leggere questo articolo prima che continuiate.

2. Perche' e quando

Non posso darvi una risposta semplice su quando usare i threads o no,semplicemente perche' non c'e'. Infatti dobbiamo guardare molteplici aspetti per scegliere se usare o meno il multi-threading (da ora m.t.) per la nostra applicazione. Solitamente il m.t. e' usato nelle speranza che le prestazioni siano migliorate, ma solo voi potete stabilire se questo sia relamente il vostro obbiettivo.
Sarebbe meglio quindi partire dal perche' NON usare il m.t.. E i motivi sono abbastanza semplici e facilmente riassumibili:

-Le applicazioni single-thread non necessitano di sincronizzazione ;
-Le applicazioni single-thread sono piu' facili da scrivere,debuggare ,testare e mantenere.

L'opposto quindi e' vero per il m.t..
Ma prima che diciate "Chi me lo fa fare ad usare tale diavoleria per complicarmi ancor di piu' la vita (gia' problematica) da coder ?", ci sono altre cose da considerare:

- GUI.
- I/O.
- Multi-core

3. GUI (interfaccia grafica)
Questo e' probabilmente il motivo piu' comune per usare il m.t. Le applicazioni che necessitano di GUI sono per sua natura ad eventi( l'utente fa qualcosa-> qualcosa accade). E se l'evento non riesce ad essere processato in un tempo ragionevole l'applicazione non risponde creando frustrazione nell'utente.
Un esempio non tanto calzante ma che rende bene l'idea di cio' e' quando si usa una applicazione che fa innumerevoli calcoli per il brute-forcing di una password.
Per ovviare a questo problema ,infatti, di solito si alloca un thread in background per il calcolo , mentre il thread principale continua ad occuparsi degli eventi della GUI cosi' che l'applicazione rimanga sempre sensible a reagire. In questi casi la sincronizzazione e' abbastanza semplice, in quanto basta indicare all'utente che qualcosa sta accadendo in background(di solito con una semplice barra di progresso)

4. I/O
A volte in alcuni applicazioni (non gli "hello world" ovvio ) e' necessario caricare e memorizzare una notevole quantita' di dati.
Ma gli hard disk si sa sono lenti e sarebbe comodo quindi mettere in background il processo che carica i dati ed utilizzare i dati gia' memorizzati.
Stessa cosa vale per la rete,non sappiamo quanto tempo potrebbe passare prima che i dati arrivino.Cosi' sarebbe perfetto avere un thread che aspetta i dati in arrivo per poi passarli ad un altro che li processa.
C'e' da dire pero' che se il sistema operativo lo supporta si potrebbe usare per entrambi l' I/O asincrono che scarica l'operazione sul sistema operativo medesimo senza preoccuparsi dei threads.

5. Multi-core
Le piattaforme multi-core stanno diventando sempre piu' diffuse.Le case produttrici avendo constatato che l' innalzamento della frequenza avrebbe portato solo a forte dissipazione si sono tutte dirette verso l'uso di due o piu' processori.
E con questo tipo di architetture le applicazioni single-thread non trarrebbero nessun vantaggio dalla presenza di altri processori.Quindi il m.t. in questi casi e' l'unica maniera di sfruttarne a pieno le potenzialita'.

6. Primitive (operazioni atomiche)
Per primo guardiamo a quelle che si chiamano operazioni atomiche.Atomico(dal greco :non disivibile)sta a significare che un task deve essere portato a termine prima che un thread possa cambiare contesto(anche se avviene un interrupt).Cio e' fatto per evitare quelle che vengono chiamate "race conditions",derivanti da operazioni interrotte in una fase in cui non erano ancora state completate(vedi piu' avanti).
Sui processori a 32 bit le operazioni di store/read sono operazioni atomiche.Ma ce ne sono altre tipo:
CAS (Compare And Swap), LL/SC (Load-Link/Store-Conditional)etc etc.. ed anche alcune semplice operazioni tipo incremento/decremento possono essere atomiche.
Ma guardiamo un esempio:

CODE

a = 5
thread 1:
a += 10
thread 2:
a += 10

Di primo acchito il valore di "a" sembrerebbe 25 ma in realta' e' 15.

Infatti:

CODE

thread 1 legge a = 5
---context switch---(ossia passaggio ad un altro thread)
thread 2 legge a = 5
thread 2 assegna a = 15
---context switch---
thread 1 assegna a = 15

Per aggirare cio' potremmo usare il succitato CAS.
Per sommi capi CAS cambia il valore in memoria solo se il valore in memoria e' quello che noi ci aspettiamo che sia e se non lo e' prova di nuovo.
Il codice di sopra con CAS diventerebbe quindi:

CODE

a = 5
thread 1:
do {
old = a
new = a + 10
} while (!CAS(a, old, new))
thread 2:
do {
old = a
new = a + 10
} while (!CAS(a, old, new))

ossia:

CODE

thread 1 legge a = 5
---context switch---
thread 2 legge a = 5
thread 2 testa se a = 5, se e' cosi' assegna a = 15
---context switch---
thread 1 testa se a = 5, se non e' cosi' prova di nuovo
thread 1 legge a = 15
thread 1 testa se a = 15, se e' cosi' asssegna a = 25

Comunque c'e' un problema col CAS e cioe' quando un valore assume un nuovo valore e dopo torna di nuovo al vecchio valore.
In questo caso CAS vede che il valore e' come quello vecchio e pensera' che la memoria non e' stata cambiata.
C'e' un modo comunque di risolvere tale situazione,ma esula da questo articolo.

Inoltre molte applicazioni hanno bisogno di strutture dati che consistono di valori multipli per definire il loro stato.
In questo caso persino con le operazioni atomiche un thread potrebbe riuscire a cambiare lo stato ad un altro valore della stessa struttura dati, lasciandola in uno stato incosistente.Ed e' in questa situazione che ci vengono in soccorso i MUTEX. I Mutex dal nome sembrano la cosa piu' arcana in programmazione, invece permettono solo che due thread non possano accedere allo stesso segmento di codice contemporaneamente(mutual exclusion).
(Nota a margine: quella che viene chianmata Critical section(sezione critica) fa praticamente la stessa cosa,ma questa puo essere usata all'interno di un solo processo mentre i mutex no,anche se la critical section e' molto piu' veloce).

Comunque assumiamo di avere un struttura "struct" con due valori a e b e che la somma di questi due valori per qualche oscuro disegno divino debba essere 15:

CODE

thread 1:
struct.a = 10
struct.b = 5
thread 2:
struct.a = 5
struct.b = 10

cioe':

CODE

thread 1 assegna struct.a = 10
---context switch---
thread 2 assegna struct.a = 5
thread 2 assegna struct.b = 10
---context switch---
thread 1 assegna struct.b = 5

mmmm la somma si vede sarebbe 10 e non 15.
Coi mutex invece il codice diventerebbe:

CODE

thread 1:
lock mutex m
struct.a = 10
struct.b = 5
free mutex m
thread 2:
lock mutex m
struct.a = 5
struct.b = 10
free mutex m

che sarebbe:

CODE

thread 1 acquisisce mutex m
---context switch---
thread 2 cerca di acquisire il mutex m ma fallisce e si "addormenta"
---context switch---
thread 1 assegna struct.a = 10
thread 1 assegna struct.b = 5
thread 1 libera mutex m, thread 2 ora si risveglia
---context switch---
thread 2 acquisisce mutex m
thread 2 assegna struct.a = 5
thread 2 assegna struct.b = 10
thread 2 libera mutex m

Perfetto, abbiamo ottenuto quello che volevamo.
Pero' nessuno di questi metodi a pensarci bene ci danno la sincronizzazione reale.Infatti non c'e' garanzia che il thread 1 funzionera' prima del thread 2.
Per questo ci vengono in aiuto EVENTI e SEMAFORI che possono essere utilizzati per iniziare azioni in un thread basandosi su cio che e' successo in un altro thread.

Il semaforo e' praticamente un contatore che deve essere atteso:se il suo valore e' 0 il thread sara' bloccato fino a che non cambiera' valore.
Un classico per la comprensione dei semafori e' una coda .Infatti usando un semaforo come contatore per i messaggi che si hanno in coda possiamo aver uno o piu' thread in attesa di un messaggio da processare. Di solito si usera' anche un mutex per evitare accessi simultanei alla coda ma cercheremo di semplificare lasciando al lettore,se vorra', il compito di approfondire.
Comunque:

CODE

semaforo s = 0
thread 1:
aspetta semaforo s
thread 2:
aggiunge un messaggio alla coda
aumenta il semaforo s di 1
thread 1:
decrementa il semaforo s di nuovo a 0
legge il messaggio dalla coda
processa il messaggio
ritorna ad aspettare il semaforo s

Gli eventi invece sono una maniera piu' generica di passare messaggi tra threads.
Basti pensare ad un processo attivo a lungo in background e ad un thread in attesa di un evento di completamento/stop/timeout/.

CODE

thread 1:
setta il tempo di timeout a 15 minuti
parte il thread 2 per fare il suo lavoro
aspetta un evento
se (completo) mostra risultato
se (stop o timeout) continua con un altro lavoro
thread 2:
esegue il suo lungo processo che comunque deve essere completato in 15 minuti
manda l'evento di completamento

Ora se il thread 2 non finisce prima dello scadere dei 15 min. abbiamo un timeout e possiamo continuare un altro lavoro.Ma anche se l'utente manda un segnale di stop(per es ctrl-c) possiamo continuare un altro lavoro.
Se invece il thread 2 finisce ci mostrera' il risultato.Semplice no?Cosa vogliamo farne del thread 2 quindi dipende solo dal tipo di task:potremmo lasciarlo in background o potremmo terminare il thread.

7. Ottimizzazioni del Processore
I moderni processori usano dei "trucchetti" per aumentare la performance ed uno di questi e' chiamato "out-of-order execution".
Ossia il processore esegue le istruzioni in un ordine diverso da quello per cui sono in coda ,comprese le operazioni di assegnamento sulla memoria.
In una applicazione single thread cio' non sarebbe un problema, ma non in una m.t. :

CODE

a = 1
b = 2
thread 1:
while (a == 0) aspetta
print b
thread 2:
b = 5
a = 0

che dovrebbe logicamente stampare 5.
Comunque potremmo volere che il processore legga prima il valore b e lo tenga in cache oppure che assegni il nuovo valore di a prima del nuovo valore di b etc etc.
Per risolvere questo si usa un accorgimento chiamato "memory barrier".Semplificando questo dice al processore che tutte le operazioni di assegnamento "dietro" la barriera devono avvenire prima di quelle poste "dopo" la barriera.
Molte primitive multi-treading contengono gia' il memory barrier e comunque sono specifiche della piattaforma.

8. Parallelismo
Generalmente parlando ci sono due modi per ottenre il parallelismo.

- Functional parallelism:
Ove si cercano blocchi di codice che hanno poco o nulla a che fare l'un l'altro su cui usare i thread.

oppure

- Data parallelism:
Quando si hanno invece una pletora di dati e ad ogni thread viene assegnata parte dei dati.

Scegliere l'uno o per l'altro dipende dal tipo di applicazione.Comunque con il data parallelism non si e' limitati dalle parti funzionali di cui e' composta una applicazione e si possono sfruttare al meglio i 2,4,8,80 core(e chi piu' ne ha piu' ne metta).

9. Granularita'
Come detto il m.t. e' utilizzato per aumentare la performance.Ma bisogna comunque stare attenti dato che troppa sincronizzazione otterrebbe l'effetto contrario(mentre poca sincronizzazione porterebbe a race conditions etc etc).
Per comprendere questo guardiamo un attimo i vari livelli di sincronizzazione:

-Generale:

Il modo piu' facile di sincronizzare e' mettere un mutex all'inizio di ogni funzione/metodo che ha dati condivisi.
Naturalmente bisogna evitare che gli stessi dati non siano condivisi da funzioni/metodi multipli con differenti mutex(il dead-lock e' dietro l'angolo :P);

-Particolare:

Si potrebbero sincronizzare solo le parti che hanno a che fare con dati condivisi, ma questo alla lunga potrebbe comportare dei problemi;

-Lock-free:

Lock-free si intende che il thread non deve essere locked(bloccato) (da un mutex etc.).Ogni sincronizzazione e' fatta dalle operazioni atomiche.

-Wait-free:
Le operazioni vengono portate a termine con una serie di passi che non possono essere messe in attesa (wait) per nessun motivo.Ma con algoritmi di grossa scala sarebbe impossibile praticare questa strada.

10. Race conditions & dead/livelocks
Una race condition e' definita come " un comportamento anomalo che si verifica quando due o piu' processi stanno leggendo o scrivendo un qualche dato condiviso e il risultato finale dipende dall'ordine in cui vengono schedulati i processi".
E questo spiega appunto la difficolta' di debugging e testing di cui si parlava sopra.
Prendiamo questa porzione di pseudo-codice:

CODE

a = null
if (a == null) alloca un nuovo oggetto in a;

sembra semplice ma guardiamo piu' attentamente:

CODE

thread 1 legge a = null
---context switch---
thread 2 legge a = null
thread 2 crea una nuova istanza
---context switch---
thread 1 crea una nuova istanza

Come si buon ben intuire nessun thread potra' mai completare il ciclo e si ottiene quello che si chiama un dead-lock, che potrebbe manifestarsi quando meno te lo aspetti bloccando il software senza nessun tipo di errore e rendendone difficile quindi l' individuazione.
Ci sono comunque metodi per evitarli ed il piu' semplice e' quello di stabilire in che ordine i locks devono essere acquisiti (se locks multipli sono necessari).

Un'altra situazione ma meno conosciuta e' il livelock.Ossia quando due thread vengono esguiti ma non c'e' progresso.
Un esempio preso dalla vita reale e' quando due persone camminano in direzione opposta lungo un corridoio e l'una e l'altra si spostano a destra e a manca cercando di far passare l'altra.

11. Priority inversion
Questa si ha quando un thread con minore priorita' blocca una risorsa che serve ad un thread con priorita' piu' alta. Fortunatamente cio' accade solo in applicazioni real-time.Un buon esempio potrebbe essere questo.La sincronizzazione wait-free potrebbe essere comunque l'ideale qua , in quanto non si deve aspettare per nulla(inversioni comprese).

12. Futuro
Come detto con le piattaforme multi-core il m.t. diverra' sempre piu' presente.
La ricerca si sta spingendo sempre piu' verso l'implementazione di strumenti che possano permettere agli sviluppatori di usare il m.t. senza problemi.Alcuni algoritmi lock-free e la Cliff Click's lock-free Hash Table sono gia' apparsi e molti altri ne appariranno.

13. Conclusioni
Quando si pensa al m.t. non si deve mai dimenticare la complessita' che lo sottende. Molti programmi non necessitano affatto di esso:
utilizzarlo non farebbe altro che rendere piu' farraginoso il codice facendo calare anche le prestazioni.
Quindi si al m.t. ma da usare con cautela stando attendi a tutti i possibili problemi solo qua accennati per limiti di spazio.
La mia raccomandazione e' sempre quella di informarsi e studiare il piu' possible evitando di spargere codice inutile per il mondo.
Per qualsiasi info,commento,correzione,lamentala potete scrivermi qua marionebbia[at]hackroom[dot]org o trovarmi come al solito in wpn.

Bibliografia:
- http://www.devspy.com/public/viewer/show.aspx?guid=d1
- http://www.lilik.it/~mirko/gapil/
- Advanced Programming in the UNIX Environ Advanced Programming in the UNIX Environment
Rago, Stephen A.; Stevens, W. Richard; Addison-Wesley Professional
- Architettura dei Sistemi di Elaborazione, volume 1 e 2 (F. Baiardi, A. Tomasi e Marco Vanneschi, 1988, Franco Angeli Edizioni)
Fondamenti, firmware, architetture parallele
- A.Tanenbaum, I moderni sistemi operativi, Jackson Milano, 2002, pp.66-144

Ecco cosa pensano le persone...

Loggati e scrivi il tuo commento, e' molto importante per noi conoscere il tuo parere sui nostri articoli, grazie.