Concorrenza (informatica)

In informatica la concorrenza è una caratteristica dei sistemi di elaborazione nei quali può verificarsi che un insieme di processi o sottoprocessi (thread) computazionali sia in esecuzione nello stesso istante. Tale sistema viene appunto chiamato sistema a concorrenza o sistema concorrente. L'esecuzione contemporanea può condurre a interazione tra processi quando viene coinvolta una risorsa condivisa. Un'importante classe di sistemi informatici nei quali gli aspetti di concorrenza sono fondamentali è quella dei sistemi operativi.

Il problema dei filosofi a cena, un classico problema inerente concorrenza e condivisione di risorse

Introduzione

Il concetto di concorrenza è contrapposto a quello di sequenzialità. In un sistema sequenziale i processi vengono eseguiti uno per volta e non si verifica alcuna forma di interazione tra essi durante l'esecuzione.

Dato che in un sistema concorrente la varietà di interazioni che si possono verificare tra processi in esecuzione è notevole, sono state elaborate delle teorie in merito alla gestione delle problematiche connesse alla concorrenza. Sulla base di queste teorie sono state sviluppate sia delle tecniche di programmazione (programmazione concorrente) sia dei linguaggi che integrano nativamente primitive per la corretta gestione della concorrenza.

Problematiche

La concorrenza può portare ad una serie di problematiche legate all'utilizzo di una stessa risorsa condivisa da parte di più processi. Un determinato susseguirsi di eventi può causare condizioni critiche. La programmazione concorrente sfrutta alcuni principi per fronteggiare e risolvere questo tipo di problematiche.

Corse critiche (Race conditions)
In alcuni sistemi può accadere che i processi in esecuzione condividano una risorsa comune di qualsiasi natura (sia essa un'area di memoria condivisa o una periferica). In particolare se si verifica che il risultato finale dell'esecuzione di più processi dipende dall'ordine in cui essi vengono eseguiti, questa è una condizione di corsa critica (race condition). Il risultato dell'esecuzione nel caso di corse critiche è assolutamente impredicibile.

Il problema delle "corse critiche" può essere evitato impedendo che più di un processo per volta acceda a risorse condivise. Con la mutua esclusione si evita che più processi che contendono una risorsa riescano ad accedervi contemporaneamente.

Stallo (Deadlock)
Quando ad un processo viene garantito l'accesso esclusivo (ad esempio tramite una mutua esclusione) ad una risorsa, possono crearsi situazioni di stallo. Formalmente un insieme di processi è in stallo (deadlock) quando ogni processo dell'insieme attende un evento che può avvenire soltanto tramite un altro processo dell'insieme. Essendo tutti i processi in attesa, nessuno potrà mai creare l'evento di sblocco protraendo l'attesa all'infinito. Le tecniche per individuare situazioni di stallo prevedono l'analisi di grafi delle risorse allocate oppure mediante la creazione di cosiddette "matrici di allocazione". La risoluzione degli stalli può essere affrontata in vari modi. Concettualmente si possono suddividere in:
- Risoluzione mediante prerilascio: viene scelto un processo che detiene una risorsa dall'insieme dei processi in stallo e viene tolto l'accesso esclusivo (prerilascio o preemption) ad una risorsa condivisa (causa di stallo). L'operazione è talvolta difficile, talvolta impossibile e dipende dal tipo di risorsa che il processo stava bloccando.
- Risoluzione mediante punto di controllo: vengono creati dei registri (checkpoint) che descrivono lo stato di utilizzo delle risorse condivise. Quando viene rilevato uno stallo si effettua un "ritorno" (rollback to checkpoint) alle condizioni precedenti. Anche questa tecnica è di difficile o addirittura impossibile realizzazione poiché il ritorno potrebbe causare perdita o inconsistenza di dati.
- Risoluzione mediante eliminazione: viene scelto un processo e viene terminato. Questa tecnica è anch'essa molto complessa e richiede di fare stime e assunzioni sul tipo di processo da eliminare. Inoltre non è garantita l'uscita dalla condizione di stallo per cui potrebbe essere necessario terminare altri processi, situazione che complica ulteriormente la problematica.

È anche possibile effettuare delle stime sulle risorse che verranno impegnate da un processo. Grazie a tali stime, esistono sistemi in cui invece di risolvere le situazioni di stallo risulta più semplice evitarle a priori.

Tutte le tecniche prevedono la costruzione di matrici che tengono traccia dell'utilizzo delle risorse (matrici di traiettoria di risorse) o si basano su algoritmi noti come l'algoritmo del banchiere.

Starvation
Letteralmente inedia, è un problema in stretta relazione con lo stallo. Quando le politiche di assegnazione delle risorse condivise favoriscono un processo rispetto ad un altro, il processo a cui vengono assegnate in minor misura soffre di starvation. Esso è infatti bloccato e non può proseguire sebbene non si trovi in una condizione di stallo. Nei sistemi in cui si accede a risorse condivise è sempre necessario stabilire una politica per le priorità e l'ordine con cui esse vengono ripartite. Sebbene queste politiche possano risultare quanto più eque, esse possono portare a condizioni di starvation.

Comunicazione interprocesso

Nell'ambito della programmazione concorrente la comunicazione interprocesso (IPC o InterProcess Communication) è di fondamentale importanza per gestire correttamente possibili situazioni di accesso a risorse condivise. I sistemi concorrenti mettono a disposizione delle primitive di comunicazione che permettono di alternarsi (escludendosi a vicenda) nell'accesso ad una risorsa condivisa oltre a primitive di sincronizzazione che permettono di intervenire sulla sequenza secondo la quale avverranno determinati eventi. Ogni sistema concorrente implementa e mette a disposizione le proprie primitive, ma nonostante ciò i sistemi si rifanno ad una base teorica comune. Per questo è possibile creare una panoramica d'insieme.

Le più comuni vie di comunicazioni interprocessuali sono:

Mutex: variabili binarie che permettono di gestire l'accesso ad una risorsa condivisa mediante accesso esclusivo di uno dei contendenti. Le operazioni di blocco (in termini semplicistici richiesta di accesso alla risorsa condivisa) e sblocco (rilascio della risorsa) sono atomiche.

Semafori n-ari: variabili n-arie che possono essere incrementate e decrementate. Il processo che decrementa il semaforo si bloccherà appena raggiunto lo zero della variabile. Un processo che incrementa il semaforo invece risveglia tutti i processi che si erano bloccati in fase di decremento. Questa è una delle primitive base che consentono la sincronizzazione. Le operazioni di incremento, decremento e controllo del semaforo sono atomiche.

Variabili di tipo condizione: conosciute anche come Condition Variables, sono variabili con associate due primitive: wait (aspetta) e signal (segnala, risveglia). Una procedura che richiama la primitiva wait si pone in attesa indefinita, una procedura che richiama la primitiva signal ne risveglia una in attesa su wait. Anche in questo caso le operazioni sono atomiche.

Scambio di messaggi: due procedure, send (invia) e receive (ricevi), permettono a due processi di scambiarsi messaggi. Lo scambio di messaggi è solitamente usato in sistemi paralleli.

Barriere: talvolta le applicazioni sono divise in fasi con la regola che nessun processo può proseguire se prima tutti i suoi simili non sono pronti a farlo. Le barriere implementano questo concetto: un processo che ha terminato la sua fase chiama una primitiva barrier e si blocca. Quando tutti i processi coinvolti hanno terminato il loro stadio di esecuzione invocando anch'essi la primitiva barrier, il sistema li sblocca tutti permettendo di passare ad uno stadio successivo.

Il concetto di atomicità nei sistemi concorrenti ha due fondamentali caratteristiche:

La sua esecuzione non può essere prelazionata: il blocco e lo sblocco di un mutex non possono essere interrotti durante la loro esecuzione.
La sua esecuzione è unica: non può avvenire che contemporaneamente due processi riescano a bloccare lo stesso mutex. Nei sistemi uniprocessore questa affermazione è una conseguenza della precedente poiché il concetto di "contemporaneità" è solo virtuale.

È evidente che tutte le primitive di comunicazione e sincronizzazione intraprocesso debbano rispettare questa condizione di atomicità.

Problemi classici

Esiste una serie di problemi classici nella programmazione concorrente. Essi vengono utilizzati per dimostrare l'efficienza di determinate teorie o algoritmi e forniscono una base comune per potere effettuare dei paragoni. Tra quelli più famosi si elencano:

Produttore e Consumatore: anche conosciuto come problema del buffer a capienza limitata (bounded buffer problem). Un insieme di processi detti produttori producono dati per inserirli in un buffer di dimensioni finite mentre un altro insieme, i consumatori, estrae dati da questo buffer rappresentante la risorsa condivisa. Una programmazione concorrente ideale prevede un accesso esclusivo al buffer e arbitra correttamente il comportamento dei produttori quando il buffer è pieno e dei consumatori quando il buffer è vuoto.

Lettori e scrittori: modella l'accesso a basi di dati. Su una base di dati agiscono scrittori, che ne modificano il contenuto, e lettori che ne recuperano il contenuto. Una corretta programmazione concorrente prevede l'accesso di un solo scrittore in fase di modifica (e di nessun lettore onde evitare inconsistenza) mentre l'accesso di tanti lettori è possibile a patto che non ci siano scrittori attivi contemporaneamente. Vedi anche la voce "Sezione critica".

Filosofi a cena: formulato da Edsger Dijkstra come dining philosophers problem. Alcuni filosofi (5 nel testo originale) sono seduti a tavola di fronte al loro piatto ed a due forchette (condivise con i loro vicini). I filosofi alternano momenti durante i quali meditare e momenti durante i quali mangiare. Per mangiare devono prendere le due forchette accanto al loro piatto e mangiare mentre durante la meditazione devono tenere le forchette sul tavolo. Risulta evidente che il numero di forchette impedisce a tutti i filosofi di mangiare contemporaneamente quindi una corretta programmazione concorrente deve essere in grado di far mangiare alternativamente tutti i filosofi evitando che qualcuno in particolare soffra la fame ed evitando che si verifichino stalli in fase di "acquisizione delle forchette".

Barbiere sonnolento: un barbiere possiede un negozio con una sola sedia da lavoro e un certo numero limitato di posti per attendere. Se non ci sono clienti il barbiere dorme. All'arrivo del primo cliente il barbiere si sveglia ed inizia a servirlo. Se dovessero sopraggiungere clienti durante il periodo di attività del barbiere, essi si mettono in attesa sui posti disponibili. Al termine dei posti di attesa, un ulteriore cliente viene scartato. Questa problematica è molto vicina al sistema di funzionamento degli helpdesk informatizzati dove l'operatore serve, uno per volta, tutti i clienti in coda oppure attende, senza effettuare alcuna operazione in particolare, l'arrivo di nuove chiamate. Una corretta programmazione concorrente deve far "dormire" il barbiere in assenza di clienti, attivare il barbiere sul primo cliente al suo arrivo e mettere in coda tutti i successivi clienti tenendoli inattivi.

Modelli matematici

Le reti di Petri sono un ottimo strumento per la descrizione di sistemi dotati di concorrenza.

Bibliografia

Testi di approfondimento

Paolo Ancilotti, Maurelio Boari, Programmazione concorrente e distribuita, McGraw-Hill, gennaio 2007, ISBN 88-386-6358-0. Le soluzioni degli esercizi di riepilogo sono scaricabili gratuitamente on-line.