Modellazione dell'esecuzione concorrente

1. Processi e interazione

Un processo è l'esecuzione di un programma sequenziale: un singolo flusso di controllo logico, l'unità di base di un sistema concorrente. Non va confuso con il processo del sistema operativo: i thread di Java, le goroutine di Go e gli attori sono processi in questo senso. Un programma concorrente è un insieme finito di programmi sequenziali eseguiti sovrapposti nel tempo. Vale la speed independence: i processi sono del tutto asincroni e non si può supporre nulla sulle loro velocità relative. Da qui il non determinismo: con lo stesso input, il programma può comportarsi diversamente a ogni esecuzione.

I processi interagiscono quando tra loro c'è una dipendenza: un dato prodotto da un altro, un'azione che deve venire prima di un'altra, una risorsa che non si può usare insieme. Le slide distinguono tre tipi di interazione:

Nella competizione non interessa chi arriva prima: interessa solo che due processi non usino la risorsa insieme. È un'interazione che non si desidera ma che va gestita, altrimenti diventa interferenza.

Memoria condivisa o scambio di messaggi

Nel modello a memoria condivisa i processi (per esempio i thread) leggono e scrivono le stesse variabili: la comunicazione è implicita, ma servono meccanismi espliciti di mutua esclusione e sincronizzazione (lock, semafori, monitor, capitoli 5 e 7). Nel modello a scambio di messaggi ogni processo ha la sua memoria e interagisce solo con send e receive: non ci sono dati condivisi da proteggere, e comunicazione e sincronizzazione coincidono, perché un messaggio si riceve solo dopo che è stato inviato. È il modello dei sistemi distribuiti e degli attori (capitoli 14 e 15).

2. Come si esprime la concorrenza in un linguaggio

Un programma concorrente si scrive in un linguaggio concorrente e si esegue su una macchina concorrente, anche astratta come la JVM. La macchina offre tanti processori virtuali quanti sono i processi, e meccanismi per la multiprogrammazione (crearli e assegnare loro i processori fisici), per la sincronizzazione e comunicazione e per il controllo dell'accesso alle risorse. Il linguaggio offre i costrutti per creare processi e farli interagire, con tre approcci di progetto:

• linguaggio sequenziale più una libreria di primitive concorrenti: C con i Pthreads: il linguaggio non sa nulla di concorrenza, tutto passa per chiamate di libreria;
• linguaggio progettato per la concorrenza, con i processi come costrutto di prima classe: Occam, Ada, Erlang, Go (go f() avvia una goroutine);
• approccio ibrido: un paradigma sequenziale esteso con un supporto nativo. È il caso di Java e Scala: i thread sono oggetti di libreria, ma il linguaggio aggiunge synchronized e un lock in ogni oggetto, e java.util.concurrent offre librerie e pattern costruiti su questi meccanismi (capitolo 10).

3. Sincronizzazione non è mutua esclusione

Le slide citano Buhr e Harji (Concurrent Urban Legends, 2005): «sincronizzazione = mutua esclusione» è una leggenda metropolitana ancora presente in libri e articoli. I due concetti sono collegati ma distinti.

• La sincronizzazione stabilisce una relazione temporale tra processi. Può chiedere che due azioni avvengano insieme o alla stessa velocità, ma soprattutto che un'azione avvenga prima di un'altra (precedenza). Il merger che parte solo dopo i sorter è sincronizzazione, e non richiede dati condivisi.
• La mutua esclusione è una restrizione sull'accesso a dati condivisi: al più un processo alla volta. Senza dati condivisi non ha senso.

La mutua esclusione richiede una forma implicita di sincronizzazione, perché chi trova la risorsa occupata deve aspettare. Il contrario non vale: la sincronizzazione non richiede né dati condivisi né mutua esclusione. In Java la parola synchronized indica proprio la mutua esclusione: eseguire un blocco synchronized (obj) significa prendere il lock di obj, e non impone alcun ordine tra processi.

Mutua esclusione e sezione critica sono due facce dello stesso problema. La mutua esclusione è la proprietà richiesta. La sezione critica è il tratto di codice che accede agli oggetti condivisi e che deve essere eseguito in mutua esclusione. Il problema della sezione critica chiede di progettare i protocolli che la racchiudono (capitolo 4).

4. Race condition e situazioni critiche

Si ha una race condition (race hazard, o solo race) quando due o più processi accedono e aggiornano concorrentemente risorse condivise e il risultato dipende dall'ordine in cui avvengono gli accessi. «Corsa critica» è la traduzione italiana dello stesso termine, non un concetto diverso. Una race nasce in due modi: da una cattiva gestione di interazioni previste o da interazioni spurie che il problema non prevedeva.

Alice, Bob e il latte

Alice e Bob vivono insieme, senza cellulare, e sono entrambi responsabili di comprare il latte quando finisce. Senza coordinamento può succedere che entrambi trovino il frigo vuoto ed escano a comprarlo. Vogliono allora due proprietà: se manca il latte qualcuno lo compra, e lo compra uno solo. Provano con un biglietto sul frigo:

1 if (nessun biglietto) then
2   if (niente latte) then
3     lascia il biglietto
4     compra il latte
5     togli il biglietto

Alice guarda il frigo: nessun biglietto. Prima di controllare il latte va in bagno. Arriva Bob, non trova biglietti, vede che il latte manca, lascia il biglietto ed esce. Alice torna e riprende dal punto in cui era: il biglietto l'ha già controllato, quindi guarda nel frigo, non trova latte, lascia un secondo biglietto ed esce anche lei. Il latte viene comprato due volte. Il difetto è l'atomicità: controllare il biglietto e poi agire sono due passi distinti, e in mezzo può succedere di tutto. È lo stesso schema del check-then-act e dell'incremento non atomico di un contatore (sezione 8). Una race si elimina rendendo atomica la sequenza «controlla e agisci»: con la mutua esclusione (lock, semafori, monitor) o con un'istruzione atomica della macchina.

Le interferenze sono l'incubo della programmazione concorrente perché producono heisenbug: bug che cambiano o spariscono quando li si osserva. Un debugger, un breakpoint o una stampa alterano i tempi di esecuzione e rendono più probabili certi scenari: il bug sparisce sotto debugger e ricompare senza.

Situazioni critiche

Interferenze ed errori possono portare il sistema in tre situazioni critiche, trattate nel capitolo 6:

• Deadlock (l'«abbraccio mortale» di Dijkstra): due o più processi aspettano ciascuno un evento che solo un altro di loro potrebbe produrre (il rilascio di una risorsa, un segnale, un messaggio), in un'attesa circolare. Riguarda un insieme di processi.
• Starvation (o unfairness): un singolo processo resta in attesa per sempre, perché gli viene negato di continuo l'accesso a una risorsa che gli serve. Riguarda un processo. Il deadlock implica la starvation dei processi coinvolti, non il viceversa.
• Livelock: come il deadlock, ma i processi non sono bloccati. Cambiano stato di continuo l'uno in risposta all'altro senza che nessuno progredisca, come due persone che in un corridoio stretto si spostano entrambe dalla stessa parte, all'infinito. È un caso particolare di starvation.

5. Il modello a interleaving

Capire la dinamica di più processi dal solo codice è quasi impossibile. Servono modelli: descrizioni rigorose di struttura e comportamento, a un livello di astrazione che tiene ciò che conta. Quelli diagrammatici servono al progetto, quelli formali all'analisi e alla verifica. Nel corso si usano il modello a interleaving con i diagrammi di stato (questo capitolo), la logica temporale per le proprietà (capitolo 3) e i formalismi visuali come reti di Petri e statechart (capitolo 9). Il modello a interleaving, dal libro di Ben-Ari, si basa su due scelte:

1. ogni processo è una sequenza di azioni atomiche, e ogni azione è l'esecuzione atomica di un'istruzione. Le istruzioni hanno un'etichetta (p1, p2, …). Il puntatore di controllo di un processo indica la prossima istruzione che eseguirà;
2. per la speed independence, l'esecuzione del programma è una sequenza ottenuta intercalando in modo arbitrario (arbitrary interleaving) le azioni atomiche dei processi. È come se un unico processore globale astratto eseguisse tutte le azioni, una alla volta, scegliendo ogni volta in modo arbitrario quale processo far avanzare.

Una sequenza che può risultare da questo intercalamento si chiama computazione o scenario. Un programma sequenziale ha un solo scenario per ogni input. Un programma concorrente ne ha molti, e deve essere corretto in tutti.

È un buon modello?

Nella realtà non esiste uno stato globale, ma l'astrazione regge nei casi che interessano:

• multitasking su una CPU: è esattamente ciò che fa lo scheduler, che alterna i processi con la preemption (ma a quanti di tempo, non ad azioni);
• multicore e multiprocessore: le istruzioni avvengono davvero in parallelo, ma gli accessi alla stessa cella di memoria vengono serializzati dal bus e dal controller di memoria, quindi si ricade in uno dei due ordini;
• sistemi distribuiti: azioni indipendenti su macchine diverse danno lo stesso effetto in qualsiasi ordine, e l'unica interazione è send/receive, in cui la ricezione segue sempre l'invio.

Intercalare in modo arbitrario significa ignorare il tempo: contano solo l'ordine parziale tra le azioni e la scelta di che cosa è atomico. Il modello è così robusto a cambi di hardware, software e prestazioni, e rende i programmi analizzabili formalmente.

Il modello non dice nulla sulla probabilità degli scenari. In pratica alcuni sono molto più probabili di altri, ed è per questo che un test può passare mille volte. Ma se su dieci scenari otto sono corretti, il programma è sbagliato: prima o poi lo scenario sbagliato si presenta.

6. Stati, transizioni e diagrammi di stato

Nel modello a interleaving l'esecuzione si descrive con stati e transizioni:

• uno stato è una tupla con un elemento per ogni processo, l'etichetta della sua prossima istruzione, e uno per ogni variabile, globale o locale, con il suo valore. Le variabili locali fanno parte dello stato del sistema;
• c'è una transizione da s₁ a s₂ se eseguire in s₁ una delle istruzioni indicate dai puntatori di controllo porta in s₂;
• il diagramma di stato è il grafo di tutti gli stati raggiungibili dallo stato iniziale. Gli scenari sono i cammini orientati che partono dallo stato iniziale; un ciclo rappresenta una computazione infinita in un grafo finito.

È un sistema di transizione etichettato (LTS), e si costruisce in modo incrementale. Si parte dallo stato iniziale, in cui ogni processo deve eseguire la prima istruzione. In ogni stato si prova la prossima istruzione di ciascun processo, una alla volta, e si ripete finché non compaiono stati nuovi. Il risultato è un grafo e non un albero, perché scenari diversi possono portare allo stesso stato.

Primo esempio. P esegue p1: n := k1 con k1 = 1, Q esegue q1: n := k2 con k2 = 2, e n vale inizialmente 0. Gli stati sono tuple <p, q, n, k1, k2> e sono 5; - indica un processo che ha finito. Gli scenari sono 2: p1 q1 termina con n = 2, q1 p1 con n = 1. Conta l'ultimo assegnamento, e lo stesso programma dà due risultati diversi.

Secondo esempio. P esegue print("p1"); print("p2"), Q esegue print("q1"); print("q2"). Senza variabili lo stato è solo la coppia dei puntatori di controllo: 9 stati e 6 scenari.

Il diagramma trasforma la domanda «il programma è corretto?» in una visita del grafo. Una proprietà che deve valere in ogni stato, come la mutua esclusione, è violata se e solo se è raggiungibile uno stato che la viola. Un deadlock è uno stato raggiungibile senza transizioni uscenti in cui non tutti hanno finito. Il procedimento è meccanico, ed è quello che automatizza un model checker (capitolo 11). Il limite è il numero di stati.

7. Quanti scenari?

Se i processi non hanno dipendenze, uno scenario è una qualsiasi permutazione delle azioni che rispetti l'ordine interno di ciascun processo. Con k processi di n₁, …, n_k azioni gli scenari sono

(n₁ + n₂ + … + n_k)! / (n₁! · n₂! · … · n_k!)

e con m processi di n azioni ciascuno diventano (m·n)! / (n!)^m.

Il numero cresce più in fretta con i processi che con le azioni. Le dipendenze riducono gli scenari: se un processo deve aspettare un evento, gli intercalamenti che lo anticipano non sono possibili. Anche così, per programmi reali lo spazio degli stati e degli scenari diventa enorme: è l'esplosione dello spazio degli stati, il problema centrale del model checking.

8. L'importanza di essere atomici

Un'azione è atomica se viene eseguita fino in fondo senza interleaving: gli altri processi vedono lo stato di prima o quello di dopo, mai uno intermedio. Che cosa è atomico è una scelta di modellazione: azioni più grandi danno meno stati e scenari, ma l'assunzione deve essere garantita dalla macchina concorrente, altrimenti il modello nasconde proprio gli scenari sbagliati.

L'esempio classico sono due processi che incrementano lo stesso contatore n, inizialmente 0:

p1: n := n + 1          q1: n := n + 1

p1: tmp := n            q1: tmp := n
p2: n := tmp + 1        q2: n := tmp + 1      -- ogni processo ha il suo tmp

La versione non atomica è quella realistica: anche un'istruzione INC su memoria legge, modifica e riscrive la cella in passi distinti. Al livello del codice macchina gli scenari si moltiplicano:

macchina a registri (3 azioni)      macchina a stack, come la JVM (4 azioni)
p1: load R1, n                      p1: push n
p2: add R1, #1                      p2: push #1
p3: store n, R1                     p3: add
                                    p4: pop n

Con i registri gli scenari sono 20 e solo 2 terminano con n = 2; con lo stack sono 70, e ancora solo 2 sono corretti. La JVM è una macchina a stack, e il bytecode di count++ ha la stessa struttura: carica, somma, salva.

Che cosa è atomico in Java

La JVM garantisce che letture e scritture di variabili di tipo boolean, byte, char, short, int, float e dei riferimenti siano atomiche. Per long e double, che sono a 64 bit, la specifica non lo garantisce (JLS §17.7): una scrittura può avvenire in due metà da 32 bit, e un altro thread può leggere un valore mai scritto da nessuno, con la metà alta nuova e la bassa vecchia. Dichiararli volatile rende atomiche le singole letture e scritture. Né volatile né l'atomicità dell'int rendono però atomico count++, che resta un leggi-modifica-scrivi:

class Counter {
  private int count;                        // letture e scritture di int: atomiche
  void inc() { count++; }                   // leggi, somma, scrivi: lost update
}
class SafeCounter {
  private final AtomicInteger count = new AtomicInteger();
  void inc() { count.incrementAndGet(); }   // un solo passo atomico dell'hardware
}

In alternativa si dichiara synchronized void inc(), che esegue l'incremento in mutua esclusione (capitolo 10).

Laboratorio: tutti gli interleaving

Scegli un programma e fai avanzare i processi a mano: lo stato è scritto come nelle slide. Poi premi Esplora tutti gli interleaving: il laboratorio costruisce il diagramma di stato completo, conta stati e scenari e riporta i valori finali di n. Confronta l'incremento atomico con le tre versioni non atomiche, e prova i processi ciclici della sezione 10.

9. Strutture dati non atomiche

Anche un oggetto dati può essere atomico o no. È atomico se ha tanti stati quanti sono i valori che può assumere, e le operazioni passano da uno stato all'altro atomicamente. I tipi primitivi dei linguaggi concorrenti di solito lo sono, ma non sempre: long e double in Java no. I tipi di dato astratti composti da più oggetti semplici, come le classi o le struct del C, in generale non lo sono.

Per un oggetto non atomico si distinguono due tipi di stato. Lo stato interno è quello che interessa a chi definisce la classe, lo stato esterno quello che vede chi la usa. La corrispondenza è parziale: gli stati interni che hanno un corrispondente esterno si dicono consistenti, e gli altri no. Un'operazione può attraversare stati inconsistenti: inserire un nodo in una lista concatenata significa crearlo, collegarlo al successivo, aggiornare la testa, e tra un passo e l'altro la lista non è una lista valida.

Nella programmazione sequenziale questo non è un problema, grazie all'information hiding: nessuno può osservare l'oggetto a metà operazione. In un programma concorrente sì: un processo può operare sull'oggetto mentre un altro è a metà di un aggiornamento. Servono meccanismi che garantiscano che i processi vedano l'oggetto solo in stati consistenti. È ciò che fanno le classi thread-safe e i monitor (capitolo 7). Le collezioni standard di Java non sono thread-safe perché la sicurezza ha un costo in prestazioni, ma la correttezza non si baratta con le prestazioni.

10. Processi ciclici

Un processo ha un numero finito di istruzioni, ma con un ciclo il suo comportamento può essere infinito. È la norma, non l'eccezione: sistemi operativi, server e controllori sono progettati per non terminare. L'esempio delle slide:

integer n := 1
p1: while (n < 1)          q1: while (n >= 0)
p2:   n := n + 1           q2:   n := n - 1

Da soli, entrambi terminano: P trova n = 1 ed esce subito, Q porta n a 0 e poi a −1 ed esce. Insieme possono non terminare mai. Il diagramma di stato ha 20 stati e contiene cicli. Alcuni scenari:

• il ciclo di P non viene mai eseguito: p1 per primo, con n = 1;
• una volta: q1 q2 p1 p2 p1. Q porta n a 0, P lo riporta a 1 ed esce, poi Q termina con n = −1;
• tre volte: (q1 q2 p1 p2) ripetuto tre volte, poi p1: ogni volta Q abbassa n prima che P lo ricontrolli;
• per sempre: q1 q2 p1 p2 ripetuto all'infinito, che nel diagramma è un ciclo percorso senza fine.

Gli stati sono finiti, ma le computazioni no. La correttezza di un programma concorrente va quindi espressa come proprietà di computazioni possibilmente infinite, non dello stato finale: è il tema del capitolo 3.

Verifica le tue conoscenze