La programmazione sequenziale offre la garanzia che le istruzioni siano sempre eseguite in ordine, senza possibili variazioni. Il comportamento che ne deriva è di tipo deterministico: inserendo gli stessi input, si ottiene in output sempre il medesimo risultato. Per ogni programma in esecuzione il sistema operativo crea un processo cui assegna uno spazio di memoria protetto. Questo garantisce la possibilità che processi indipendenti operino simultaneamente senza che si verifichino errori.
Diversa (e più evoluta) è la programmazione concorrente. Prima di siegare cos’è e come funziona è bene introdurre, a mio avviso, un particolare tipo di oggetto Kernel chiamato Thread.
In qualità di oggetti Kernel i Thread sono gestiti dal sistema operativo, e hanno due particolarità fondamentali:
- Ogni Thread ha una struttura dati riservata, in cui viene memorizzato uno stack proprio, informazioni sulle eccezioni, prossima istruzione da eseguire;
- Ogni Thread condivide con l’intero processo una zona di memoria comune.
L’utilizzo dei Thread offre diversi vantaggi a livello di esecuzione. In particolare si sfruttano appieno le prestazioni delle CPU multi-core, le quali costituiscono attualmente la tecnologia dominante nel mercato dei personal computer. Non è pensabile che applicazioni moderne di una certa complessità siano concepite in maniera sequenziale, in tal modo potrebbero sfruttare alla volta, uno solo dei core che la macchina mette a disposizione.
Come altro vantaggio, si può notare come due processi diversi che eseguono lo stesso codice, magari con diversi parametri, hanno minore efficienza di due thread che possono sfruttare in modo diretto la memoria condivisa. In un sistema che non supporta i thread, se si vuole eseguire contemporaneamente più volte lo stesso programma, è necessario creare più processi basati sullo stesso programma. Tale tecnica funziona, ma è dispendiosa di risorse ed è più lenta.
In terzo luogo, i thread offrono vantaggio nel caso in cui vengano chiamate operazioni di I/O bloccanti: invece che attendere l’evento scatenato dall’utente fermando l’esecuzione dell’algoritmo, è possibile avviare un nuovo thread evitando un inutile tempo morto che peggiora le prestazioni globali.
Di contro la programmazione concorrente necessita del supporto dei costrutti di sincronizzazione, fondamentali per evitare che accessi casuali alla memoria condivisa causino errori in output. Inoltre espone il programmatore ad una serie nutrita di errori spesso poco prevedibili a causa del comportamento non deterministico del programma.
Oltre questo i costrutti di sincronizzazione hanno un costo, sia in termini di tempo macchina necessario ad eseguire il loro codice che soprattutto in perdita di prestazioni causata dalle attese generate dai costrutti stessi al fine di garantire la correttezza nell’esecuzione concorrente.
Gli oggetti principali che permettono la gestione della concorrenza sono anticipati di seguito e descritti per esteso nei paragrafi successivi:
- Elementi volatile
- Funzioni Interlocked
- Semafori
- Sezioni critiche
- Eventi
- Timer
- Mutex
Ognuno di questi elementi si adatta in modo naturale alla risoluzione di una classe specifica di problemi semplici. Per i problemi più complessi è sufficiente combinare gli stessi oggetti tra loro per ottenere un risultato corretto e soddisfacente; il passaggio tra la risoluzione di problemi che richiedono l’utilizzo di una sola delle primitive ed i problemi che sopra sono definiti come complessi è un punto fortemente critico. La combinazione degli oggetti di sincronizzazione può rivelarsi complicatissima, nel migliore dei casi perchè non si riesce ad ottenere una prestazione sufficientemente elevata, in un caso peggiore, perchè non si riesce a trovare facilmente la soluzione che assicura la correttezza del risultato. Non ultimo il caso pessimo: è presente un bug grave e non lo si individua immediatamente. Questo frangente è frequentissimo, sia per la delicatezza dei problemi di cui si sta trattando, sia per il fatto che il debugging in ambiente concorrente è sempre problematico, i flussi di esecuzione non sono infatti deterministici, ad ogni esecuzione del programma, l’ordine con cui il processore esegue le operazioni è sempre diverso.
Reference per le funzioni di sincronizzazione
Il reference completo, importantissimo per il programmatore che deve destreggiarsi fra le numerose funzioni di libreria che gestiscono la sincronizzazione si trova a questo indirizzo. Le funzioni citate in questo articolo sono un sottoinsieme rappresentativo e rilevante di quelle elencate nella MSDN Library al link indicato.
Elementi "volatile"
Se due thread diversi eseguono operazioni sullo stesso dato è possibile che si verifichino immediatamente questi due tipi di errori:
Un thread scrive un dato su una variabile, la quale viene letta non aggiornata da un altro thread perchè il dato stesso è stato allocato ad esempio in un registro.
Il compilatore ottimizza il codice come se questo fosse sequenziale, generando errori del tipo di quelli illustrati nell’esempio:
//Thread 1
int i=0;
dato1 = *dato_arcano;
dato2 = datoCasuale();
i=1;¯
il compilatore ottimizza con:
//Thread 1
int i=1;
dato1 = *dato_arcano;
dato2 = datoCasuale();
se un altro thread esegue un test per capire se i dati sono stati scritti… l’errore è alle porte. Naturalmente con una esecuzione sequenziale l’ottimizzazione non avrebbe prodotto alcun danno.
//Thread 2
while (i!=1);
[..codice..]
La parola chiave volatile evita questi tipi di errori. Forza il compilatore a non fare alcun tipo di ottimizzazione sulla variabile e si assicura che un accesso alla variabile in questione avvenga realmente: volatile impedisce al compilatore di allocare una variabile in un registro, anche per un breve periodo. Questo fa si che la variabile possa essere modificata in qualsiasi momento da qualsiasi processo.
Ecco un esempio del codice concorrente corretto per il caso precedente:
//Thread 1
volatile int i=0;
dato1 = *dato_arcano;
dato2 = datoCasuale();
i=1;
Creazione di un thread
Come ogni oggetto kernel in C++, i thread sono generati da una funzione del tipo Create[Oggetto](parametri). In particolare dalla funzione CreateThread, la cui definizione è citata di sotto.
HANDLE WINAPI CreateThread(
__in_opt LPSECURITY_ATTRIBUTES lpThreadAttributes,
__in SIZE_T dwStackSize,
__in LPTHREAD_START_ROUTINE lpStartAddress,
__in_opt LPVOID lpParameter,
__in DWORD dwCreationFlags,
__out_opt LPDWORD lpThreadId );
In particolare i parametri indicano:
- lpThreadAttributes: contesto di sicurezza (NULL assegna quello corrente)
- dwStackSize: dimensione dello stack dedicato (0 assegna la dimensione di default)
- lpStartAddress: indirizzo della funzione principale (di ingresso)
- lpParameter: puntatore all’eventuale parametro della start routine
- dwCreationFlags: principalmente puo assumere due valori principali: 0 se il thread è attivato immediatamente oppure CREATE_SUSPENDED se lo si vuole inizializzare in attesa
- lpThreadId: parametro di uscita in cui è scritto l’ID numerico del thread
Il valore di ritorno è un HANDLE all’oggetto kernel. Tramite esso il programmatore può gestire le operazioni relative al thread.
Terminazione di un thread
La terminazione di un thread avviene nei seguenti modi:
1) Un thread appartenente al processo esegue la funzione TerminateThread();
BOOL WINAPI TerminateThread(
__inout HANDLE hThread,
__in DWORD dwExitCode);
2) Il thread stesso chiama ExitThread()
VOID WINAPI ExitThread(
__in DWORD dwExitCode);
3) Il thread chiama un return
In C++ è fortemente consigliato utilizzare la terza possibilità, in modo tale che gli oggetti allocati nello stack del thread vengano distrutti correttamente. Un metodo efficace per implementare questo sistema è condizionare l’esecuzione del return al valore di una variabile condivisa e dichiarata volatile, sulla quale il thread esegue il test periodicamente.
Esempio:
//Dichiarazioni globali
volatile bool ammazza_thread=false;
//Codice Thread
{
[..]
while(true)
{
if (ammazza_thread == true) return;
else
{
[..]
}
}
[..]
}
// Funzione qualsiasi del programma
[..]
ammazza_thread = true;
[..]
Priorità di un thread
Il sistema operativo si occupa di gestire il multitasking, ed assegna periodicamente l’uso della CPU a thread e processi per mezzo di un suo componente detto scheduler. Ogni volta che a un thread/processo viene assegnato un suo quanto di tempo, questo ha diritto ad essere eseguito fino al termine del tempo assegnato, poi viene rimesso in coda ad attendere il suo turno.
Il flusso di esecuzione dipende fortemente dalla priorità, che in un sistema Windows è un valore numerico compreso fra 1 e 31. In ambiente multithreading, un processo contiene vari thread, la priorità effettiva del singolo thread è data dalla combinazione di due valori: priorità del processo e priorità del thread.
La priorità dei processi e dei thread è settata all’atto della creazione e può essere modificata durante l’esecuzione. In particolare, per i Thread le funzioni che gestiscono la priorità sono:
BOOL WINAPI SetPriorityClass( __in HANDLE hProcess, __in DWORD dwPriorityClass);
BOOL WINAPI SetThreadPriority( __in HANDLE hThread, __in int nPriority);
Modificare le priorità rispetto ai valori di default può essere deleterio e costituisce un’operazione critica. Elevarla troppo può dare origine all’eccessivo consumo di CPU da parte del thread a scapito di operazioni critiche del sistema, abbassarla oltre il dovuto può dare origine a fenomeni di starvation, tali per cui il thread non viene mai eseguito perchè nella coda dei thread in attesa ce n’è sempre un altro con priorità maggiore che viene schedulato al suo posto.
I valori dwPriorityClass e nPriority assumono valori mnemonici che consistono in costanti standard (differenti per i processi e per i thread). Come anticipato dalle righe precedenti, per definire la priorità globale si combinano i valori per darne origine ad uno nuovo compreso fra 1 e 31.
Ecco un campione rappresentativo di queste costanti, l’elenco completo è interamente tabulato nella MSDN library alla sezione relativa alle ultime due funzioni citate: SetPriorityClass e SetThreadPriority.
Valore costante | Significato |
HIGH_PRIORITY_CLASS | Priorità del processo: alta |
IDLE_PRIORITY_CLASS | Priorità del processo: minima |
THREAD_PRIORITY_ABOVE_NORMAL | Priorità del processo: superiore al normale |
THREAD_PRIORITY_NORMAL | Priorità del thread: normale |
THREAD_PRIORITY_LOWEST | Priorità del thread: bassissima |
THREAD_PRIORITY_TIME_CRITICAL | Priorità del thread: in tempo reale |
Sincronizzazione
Esistono diversi costrutti di sincronizzazione che garantiscono l’accesso sicuro alla risorsa in diverse maniere e per diversi tipi di errore. E’ compito del programmatore effettuare la scelta migliore su quali usare caso per caso, tenendo conto del contesto, dei vantaggi offerti dalla soluzione scelta e dei suoi svantaggi. In prima istanza, per evitare gli errori, è necessario che le scritture su uno stesso oggetto siano eseguite da un solo thread alla volta. Inoltre le operazioni di aggiornamento su un oggetto devono essere sempre atomiche (indivisibili), ovvero non consentono l’esecuzione di altre operazioni per tutta la durata della la loro esecuzione.
Gli errori di interferenza avvengono quando una operazione viola questo concetto. Un breve esempio può essere il seguente:
int risultato=0;
//Codice Thread
for (int i=0; i<500000; i++) risultato++;
//Fine codice thread
Eseguendo concorrentemente due thread caratterizzati da un codice del tipo illustrato sopra, la non atomicità dell’incremento su ‘risultato’ farà in modo che il valore finale sia quello sbagliato (provare per credere..), sebbene eseguendo sequenzialmente due volte lo stesso codice, non ci sia possibilità alcuna di errore.
Dichiarare la variabile risultato volatile non è sufficiente a risolvere i problemi, perchè la causa dell’errore è da ricercarsi nella non atomicità della variabile in questione.
Quest’ultimo concetto è fondamentale nel caso di dati mutabili. I dati immutabili invece non sono soggetti ad errori di interferenza. Si ricorda che un dato è immutabile quando l’oggetto che lo rappresenta non può essere cambiato dopo la sua creazione.
Funzioni Interlocked
Il costrutto più semplice di sincronizzazione consiste nell’utilizzo diretto di alcune funzioni speciali chiamate interlocked. Le funzioni interlocked eseguono col massimo dell’efficienza (relativamente all’ambito della programmazione concorrente) alcune azioni comuni in modo atomico come incremento, decremento e scambio. Di seguto un esempio di alcune di queste funzioni:
- InterlockedIncrement( long volatile * );
- InterlockedDecrement( long volatile * );
- InterlockedCompareExchange( long volatile *, long, long );
- InterlockedExchange( long volatile *, long );
- InterlockedExchangeAdd( long volatile *, long );
Come prova tangibile dell’utiltà delle funzioni interlocked convertiamo l’esempio precedente in qualcosa di funzionante:
//Codice Thread
for (int i=0; i<500000; i++) InterlockedIncrement(risultato);
//Fine codice thread
Semafori
Un semaforo è un oggetto kernel che può essere immaginato come un particolare tipo di contatore, il quale può assumere tutti i valori interi positivi e lo zero.
Sul semaforo sono possibili due tipi fondamentali di operazioni:
- Wait: decrementa il valore del contatore se questo era positivo e va avanti, altimenti, in caso di valore nullo, aspetta finchè qualcuno non incrementa il valore del contatore.
- Release: incrementa il valore del contatore.
Inizializzare il semaforo ad 1 o ad un valore positivo può risolvere tipologie di problemi diverse:
- Utilizzo esclusivo di una risorsa.
- Concessione di risorse disponibili in quantità limitata.
Soprattutto la seconda tipologia di problemi trova spesso nei semafori la miglior soluzione. I semafori sono gestiti mediante le funzioni C++ CreateSemaphore, OpenSemaphore, WaitForSingleObject, ReleaseSemaphore.
I prototipi delle funzioni principali sono:
HANDLE WINAPI CreateSemaphore(__in_opt LPSECURITY_ATTRIBUTES
lpSemaphoreAttributes, __in LONG lInitialCount, __in LONG
lMaximumCount, __in_opt LPCTSTR lpName);
HANDLE WINAPI OpenSemaphore(__in DWORD dwDesiredAccess,
__in BOOL bInheritHandle, __in LPCTSTR lpName);
DWORD WINAPI WaitForSingleObject( __in HANDLE hHandle,
__in DWORD dwMilliseconds);
BOOL WINAPI ReleaseSemaphore( __in HANDLE hSemaphore,
__in LONG lReleaseCount, __out_opt LPLONG lpPreviousCount);
Sezioni critiche
Una sezione critica è una parte di codice che può essere eseguita da un solo processo o thread alla volta. Tutte le operazioni effettuabili su una sezione critica sono implementate da librerie standard C++. Tramite chiamate dirette il programmatore ha il compito di gestire le seguenti quattro operazioni fondamentali:
- Inizializzazione
- Entrata
- Uscita
- Rilascio
Esempio di utilizzo della sezione critica:
static CRITICAL_SECTION cs;
[..]
/* Inizializza la sezione critica. */
InitializeCriticalSection(&cs);
[..]
void codiceThread()
{
/* Entra nella sezione critica: gli altri thread che
vogliono entrarci dovranno attendere */
EnterCriticalSection(&cs);
/* Codice operativo del thread*/
/* Esci dalla sezione critica */
LeaveCriticalSection(&cs);
}
[..]
/*Rilascia la risorsa acquisita*/
DeleteCriticalSection(&cs);
Uno stesso thread può entrare più di una volta in una sezione critica, quando questo accade viene incrementato un contatore; sarà poi necessario rilasciarla tante volte quanti sono stati gli ingressi, e ad ogni accesso corrisponderà un decremento.
Due consigli utili:
1) Limitiamo fortemente la quantità di codice eseguito all’interno di una sezione critica. Quel codice infatti non è eseguito in concorrenza, le prestazioni diminuiscono moltissimo.
2) Se dall’interno di una sezione critica si entra in un’altra (cosa da evitare sempre se possibile) bisogna fare attenzione all’ordine in cui si effettua il rilascio. Un errore in questa fase è fonte di problemi gravissimi di tipo deadlock (attesa infinita reciproca, il processo va in blocco eterno). Questo è il modo corretto di farlo:
EnterCriticalSection(&cs1);
EnterCriticalSection(&cs2);
// Codice...
LeaveCriticalSection(&cs2);
LeaveCriticalSection(&cs1);
Mutex
Offrono l’accesso in mutua esclusione ad una risorsa, alla stregua delle sezioni critiche. La differenza sta nel fatto che un mutex è un oggetto kernel. A livello operativo, se un thread che possiede il mutex termina, il mutex viene resettato. D’altra parte garantisce prestazioni fortemente peggiori rispetto all’utilizzo della semplice sezione critica.
Le funzioni che gestiscono i Mutex hanno sintassi molto simile a quella degli altri oggetti appena visti ed hanno il significato gia enunciato di creazione, ingresso e rilascio:
HANDLE WINAPI CreateMutex( __in_opt LPSECURITY_ATTRIBUTES
lpMutexAttributes, __in BOOL bInitialOwner, __in_opt LPCTSTR lpName);
HANDLE WINAPI OpenMutex(__in DWORD dwDesiredAccess,
__in BOOL bInheritHandle, __in LPCTSTR lpName);
BOOL WINAPI ReleaseMutex(__in HANDLE hMutex);
Eventi
Gli eventi sono un particolare tipo di oggetto kernel che decretano con il loro stato quello dei thread in attesa. Si noti che un thread entra nello stato di attesa chiamando una funzione di Wait (esempio: WaitForSingleObject). Lo stato di un evento può assumere due soli valori:
- Segnalato: un thread in stato di attesa può finire di aspettare e continuare la sua esecuzione
- Non Segnalato: tutti gli elementi in attesa mantengono il loro stato
Gli eventi sono di tipo MANUAL_RESET se quando entrano nello stato non segnalato svegliano tutti i thread in attesa su quell’evento finchè non viene eseguito un reset manuale che forza sull’oggetto event lo stato non segnalato, di tipo AUTO_RESET se, non appena viene svegliato il primo thread, viene assegnato immediatamente lo stato non segnalato
Le funzioni che operano sugli eventi sono:
- CreateEvent: crea un nuovo evento
- OpenEvent: si collega ad un evento gia esistente
- SetEvent: l’evento passa allo stato segnalato
- ResetEvent: reset manuale, passa immediatamente allo stato non segnalato
- PulseEvent: se l’evento è di tipo MANUAL_RESET tutti i thread in attesa vengono rilasciati e l’evento passa allo stato non segnalato; se l’evento è di tipo AUTO_RESET solamente uno dei thread è rilasciato. Se nessun thread è in attesa non succede niente, la chiamata non ha effetto.
HANDLE WINAPI CreateEvent(__in_opt LPSECURITY_ATTRIBUTES
lpEventAttributes, __in BOOL bManualReset, __in BOOL
bInitialState, __in_opt LPCTSTR lpName);
HANDLE WINAPI OpenEvent(__in DWORD dwDesiredAccess,
__in BOOL bInheritHandle, __in LPCTSTR lpName);
BOOL WINAPI SetEvent(__in HANDLE hEvent);
OOL WINAPI ResetEvent(__in HANDLE hEvent);
BOOL WINAPI PulseEvent(__in HANDLE hEvent);
Timer
Allo stesso modo degli Eventi, esistono oggetti kernel di tipo timer il cui stato (segnalato/non segnalato) produce gli stessi effetti, ma dipende da alcune condizioni relative all’orologio di sistema, di cui ne vengono riportate alcune significative.
- Il timer entra nello stato segnalato allo scoccare di coordinate temporali specifiche (es: il 25 dicembre 2013 alle 23:57)
- Il timer entra nello stato segnalato ad intervalli regolari (es: ogni 40 secondi)
Come nel caso degli eventi sono previsti i timer di tipo AUTO_RESET e MANUAL_RESET, il cui comportamento si mantiene lo stesso.
Le seguenti funzioni gestiscono gli oggetti di tipo Timer:
Thread Pool
la gestione manuale dei thread può essere difficilissima a causa di alcune variabili di cui il programmatore si deve prendere cura ma che non sono sempre sotto il suo controllo. Si risponda ad esempio alle seguenti domande:
- Qual’è il numero di thread ideale che ottimizza le prestazioni del sistema?
- Quanto si perde in termini di prestazioni nel creare un thread?
Per quanto concerne la prima domanda la risposta è: "dipende dal sistema". Il numero di thread ottimale dipende infatti non solo dalla qualità del codice eseguito dal thread, ma anche dall’hardware della macchina su cui si sta lavorando (quantità di RAM, numero di core della CPU ecc..). In secondo luogo creare un nuovo thread ha un costo iniziale alto, circa tre ordini di grandezza superiore rispetto alla semplice chiamata di funzione. Il sistema operativo, per aiutare il programmatore a risolvere questi due problemi supporta un oggetto kernel denominato Thread Pool, il quale consiste in una coda di thread che vengono mandati in esecuzione progressivamente, in concorrenza, con parallelismo scelto dal sistema e con risorse preallocate (ma anche con tempistica di esecuzione decisa dal sistema: si sa che il lavoro accodato sarà eseguito, ma non si hanno garanzie sul quando).
Si hanno cosi prestazioni almeno 10 volte migliori in termini di tempi di creazione del singolo Thread e un numero di thread mandati in esecuzione parallelamente, congruo alle caratteristiche della macchina su cui il programma viene eseguito. Come svantaggio si ha che l’accodamento di un lavoro al ThreadPool non è una operazione reversibile.
L’unica chiamata che cito, sufficiente ad operare a livello base con il thread pool è la seguente:
QueueUserWorkItem((LPTHREAD_START_ROUTINE)codiceThread,
(PVOID)parametro , WT_EXECUTEDEFAULT);
essa accoda un thread al Thread Pool.