Un programma concorrente non banale si basa su processi che interagiscono tra loro. Il professor Ricci distingue tre tipi fondamentali di interazione:
Interazioni attese e volute: fanno parte della semantica del programma concorrente.
Interazioni attese e necessarie, ma non volute: nascono dalla necessità di coordinare l'accesso a risorse condivise.
Il professor Ricci usa l'analogia del lock: quando due processi competono per una risorsa, non ci interessa chi arriva prima, ma vogliamo evitare interferenze. La competizione va gestita, non è un'interazione voluta ma è inevitabile.
Interazioni né attese né volute: producono effetti dannosi solo quando il rapporto tra le velocità dei processi assume valori specifici (errori tempo-dipendenti).
La stessa classificazione, in forma tabellare:
| Tipo | Natura | Descrizione |
|---|---|---|
| Cooperazione | Prevista e desiderata | I processi collaborano per un obiettivo comune. Include comunicazione (scambio di informazioni, tipicamente messaggi) e sincronizzazione (relazioni temporali tra processi, segnali temporali). |
| Competizione/Contention | Prevista ma non desiderata | Necessaria per coordinare l'accesso a risorse condivise. Include mutua esclusione (regolare l'accesso a sezioni critiche) e critical sections (esecuzione concorrente di blocchi di azioni). |
| Interferenza | NON prevista ne' desiderata | Produce effetti negativi solo quando il rapporto tra le velocita' dei processi assume valori specifici (errori tempo-dipendenti). Sono gli "heisen-bug" della programmazione concorrente. |
Il professor Ricci cita Buhr & Harji (2005): sostengono che "sincronizzazione = mutua esclusione" e' una leggenda metropolitana ancora presente in libri di testo e articoli di ricerca. I due concetti sono diversi:
Definisce una relazione temporale tra processi: azioni che avvengono nello stesso momento, alla stessa velocita', o in una relazione di precedenza. Non richiede necessariamente dati condivisi.
Definisce una restrizione sull'accesso a dati condivisi. E' priva di significato se non ci sono dati condivisi. La mutua esclusione richiede forme implicite di sincronizzazione (bloccare azioni, attendere altre).
Un processo e l'unita base di un sistema concorrente: un singolo flusso di controllo (thread of control), una sequenza di istruzioni che opera come gruppo. E un concetto astratto, non necessariamente legato ai processi del sistema operativo. Caratteristiche importanti: speed independence (l'esecuzione e asincrona, non si possono fare assunzioni sulle velocita relative) e non-determinismo.
Il professor Ricci illustra il problema della sincronizzazione con un esempio memorabile. Alice e Bob vivono insieme e sono entrambi responsabili di comprare il latte quando finisce. Senza coordinamento, puo succedere questo:
L'esempio di Alice e Bob mostra come la sincronizzazione sia diversa dalla mutua esclusione. La sincronizzazione definisce relazioni temporali tra processi (es. azioni che devono avvenire prima di altre); la mutua esclusione definisce restrizioni sull'accesso a dati condivisi. La mutua esclusione richiede tipicamente forme implicite di sincronizzazione (bloccare azioni, attendere che altre completino), ma la sincronizzazione non richiede necessariamente dati condivisi o mutua esclusione.
Una possibile soluzione usa biglietti sul frigorifero. Ma anche questa fallisce se Alice si distrae e non vede il biglietto di Bob:
| Tempo | Alice | Bob |
|---|---|---|
| 5:00 | Arriva a casa | |
| 5:05 | Guarda il frigo: nessun biglietto | |
| 5:10 | Ops, deve andare in bagno | |
| 5:15 | Ancora in bagno | Arriva a casa |
| 5:20 | Ancora in bagno | Guarda il frigo: nessun biglietto |
| 5:21 | Ancora in bagno | Guarda nel frigo: niente latte |
| 5:22 | Ancora in bagno | Lascia un biglietto |
| 5:25 | Ancora in bagno | Va a comprare il latte |
| 5:45 | Guarda nel frigo: niente latte | |
| 5:50 | Lascia un biglietto... |
La soluzione ingenua con biglietti non basta: serve un protocollo piu robusto che garantisca l'atomicita del controllo e dell'aggiornamento dello stato condiviso.
La lezione del 16 febbraio presenta lo stesso problema in una seconda variante, con un protocollo leggermente diverso:
Entrambi controllano il frigo; se non c'e' latte e non c'e' un biglietto sul frigo, lasciano un biglietto, vanno a comprare il latte, lo mettono in frigo e rimuovono il biglietto. Il programma sembra funzionare ma in realta' e' soggetto a race conditions.
Una race condition (o race hazard) si verifica quando due o piu' processi accedono e aggiornano concorrentemente risorse condivise, e il risultato dell'aggiornamento dipende dall'ordine specifico in cui avvengono gli accessi. Si manifesta in due forme principali:
I problemi nei programmi concorrenti possono portare a tre situazioni critiche:
Deadlock (o "abbraccio mortale" secondo Dijkstra): situazione in cui due o piu' azioni (processi) sono in attesa che l'altra finisca, e nessuna delle due procede mai. Riguarda tipicamente il rilascio di una risorsa condivisa bloccata, la ricezione di un segnale temporale o un messaggio. Coinvolge piu' processi.
Esempio classico: Processo A tiene il lock su risorsa 1 e attende risorsa 2; Processo B tiene il lock su risorsa 2 e attende risorsa 1.
Starvation (o mancanza di equita'): situazione in cui un processo viene bloccato in un'attesa infinita. La starvation di risorse si verifica quando a un processo viene negato perpetuamente l'accesso alle risorse necessarie. Riguarda un singolo processo.
Esempio: Uno scheduler che favorisce sempre i processi ad alta priorita' e non concede mai CPU a quelli a bassa priorita'.
Livelock: simile al deadlock, ma gli stati dei processi coinvolti cambiano continuamente l'uno rispetto all'altro, senza che nessuno progredisca. E' un caso speciale di starvation: la definizione generale dice solo che un processo specifico non sta progredendo.
Esempio: Due processi che si passano continuamente una risorsa senza mai utilizzarla, in un "cortese" scambio infinito.
Una race condition (o race hazard, o semplicemente race) si verifica quando due o piu processi accedono e aggiornano simultaneamente risorse condivise, e il risultato dell'aggiornamento dipende dall'ordine specifico in cui avvengono gli accessi. Le race condition portano a due tipi principali di errori: gestione scorretta di interazioni attese e presenza di interazioni impreviste.
Le tre situazioni critiche possono essere esplorate anche come un diagramma di stato:
Distinguere bene le tre situazioni: deadlock coinvolge piu processi che si aspettano a vicenda, starvation riguarda un singolo processo perpetuamente negato nell'accesso alle risorse, livelock e simile al deadlock ma con processi che cambiano stato continuamente senza progredire. Il livelock e un caso speciale di starvation.
Le interferenze sono il «incubo» della programmazione concorrente. Si manifestano solo in specifiche condizioni di scheduling (heisenbug) e sono difficilissime da riprodurre in debug perché il debugger stesso altera i tempi di esecuzione.
In sintesi, una race condition si verifica quando due o più processi accedono e modificano risorse condivise contemporaneamente e il risultato finale dipende dall'ordine specifico in cui gli accessi avvengono. Tabella riassuntiva delle situazioni critiche:
| Problema | Descrizione | Riguarda |
|---|---|---|
| Deadlock | Due o più processi aspettano ciascuno che l'altro rilasci una risorsa, nessuno procede. | Più processi |
| Starvation | Un processo è bloccato in attesa infinita, negato perpetuamente nell'accesso alle risorse necessarie. | Un singolo processo |
| Livelock | Simile al deadlock, ma gli stati dei processi cambiano continuamente senza che nessuno progredisca. | Più processi (caso speciale di starvation) |
Riassumendo l'analogia del latte e del frigo, senza coordinamento possono verificarsi scenari in cui:
Questa analogia illustra chiaramente il problema della sezione critica: servono protocolli di ingresso e uscita per garantire l'accesso esclusivo a una risorsa condivisa.
Il professor Ricci sottolinea con forza un punto spesso frainteso: sincronizzazione e mutua esclusione sono concetti diversi, anche se correlati.
| Sincronizzazione | Mutua Esclusione |
|---|---|
| Definisce una relazione temporale tra processi | Definisce una restrizione sull'accesso a dati condivisi |
| Mantenere relazioni temporali: azioni che avvengono "nello stesso momento" o "prima/dopo" | Non ha senso se non ci sono dati condivisi |
| Non richiede necessariamente dati condivisi | Richiede tipicamente forme implicite di sincronizzazione (blocco di azioni, attesa) |
In Java, la parola chiave synchronized è stata scelta per denotare la mutua esclusione, non la sincronizzazione. Questo crea confusione nella letteratura. Quando un metodo ha l'attributo synchronized, significa che la sua esecuzione richiede l'acquisizione del lock dell'oggetto — è mutua esclusione, non sincronizzazione nel senso proprio del termine.
Il professor Ricci cita l'articolo di Buhr e Harji: "Concurrent Urban Legends" (2005). Saper distinguere questi due concetti è un punto fondamentale che viene regolarmente chiesto al colloquio.
L'esempio classico di race condition è quello di due processi che incrementano la stessa variabile condivisa in modo non atomico. Il professor Ricci lo introduce come segue.
Supponiamo di avere una variabile n inizializzata a 0, e due processi P e Q che eseguono ciascuno n := n + 1. Se l'incremento non è atomico, l'esecuzione si può spacchettare in due operazioni:
tmp := n /* lettura */
n := tmp + 1 /* scrittura */A seconda dell'interleaving, possono verificarsi scenari in cui entrambi i processi leggono il valore 0 prima che uno dei due lo scriva, portando entrambi a scrivere 1 — il cosiddetto lost update (aggiornamento perso).
Il problema nasce quando un'operazione che a livello di linguaggio sembra singola (n := n + 1) viene tradotta in più operazioni a livello macchina (leggi, modifica, scrivi). L'interleaving può avvenire nel mezzo, causando risultati inaspettati.
Per esplorare interattivamente il fenomeno, provate il simulatore seguente.
Notate come, anche se entrambi i processi eseguono le stesse istruzioni, l'ordine in cui vengono eseguite le letture e le scritture può portare a risultati diversi. Su 6 scenari possibili, solo 2 portano al valore finale corretto n = 2.
Questo è un errore subdolo: il programma può funzionare correttamente milioni di volte, e poi fallire per una specifica combinazione di eventi di scheduling. Ecco perché è così difficile debuggare i programmi concorrenti.
Prima di introdurre i meccanismi di coordinamento, e importante avere un modello formale di cosa significa eseguire un programma concorrente. Il professore sottolinea che questo modulo — Modeling Concurrent Program Execution — e il piu teorico del corso, ma costituisce il nucleo concettuale per comprendere davvero la programmazione concorrente, non solo dal punto di vista dello sviluppo ma anche della modellazione.
Un programma concorrente non ha un unico scenario di esecuzione: ne ha molti, potenzialmente esponenziali. Il nondeterminismo e intrinseco, e la correttezza non puo essere verificata con il solo testing tradizionale.
Ogni processo viene modellato come una sequenza di azioni atomiche. L'esecuzione concorrente e rappresentata come un interleaving arbitrario delle azioni dei vari processi, eseguite da un singolo processore astratto globale. Questa astrazione — detta speed independence assumption — ignora il tempo reale e si concentra sugli ordini parziali tra le azioni. E robusta rispetto a cambiamenti hardware e software perche indipendente da variazioni di velocita e tempistiche.
flowchart LR
subgraph P["Processo P"]
direction LR
p1("p1: n := k1") --> p2("p2: ...")
end
subgraph Q["Processo Q"]
direction LR
q1("q1: n := k2") --> q2("q2: ...")
end
p1 --> q1
p1 --> p2
q1 --> q2
q1 --> p2
Con due processi che hanno m azioni ciascuno, il numero di scenari possibili e dato dal coefficiente binomiale C(2m, m). Con 3 processi la crescita e ancora piu rapida: bastano 3 azioni per processo per avere 1680 scenari diversi. Questo rende il testing esaustivo sostanzialmente impossibile per programmi reali (i valori sono tabulati nella sezione sulla combinatoria degli scenari).
Il professore mostra anche un esempio cruciale: un incremento n := n + 1 sembra un'operazione singola, ma a livello macchina si scompone in load R1, n; add R1, #1; store n, R1. Se due processi eseguono questa sequenza in parallelo, il risultato finale puo essere 1 invece di 2 — una race condition. L'atomicita delle operazioni e fondamentale: se un'operazione non e atomica, processi concorrenti possono osservare stati intermedi inconsistenti.
Scegliere il giusto livello di atomicita e cruciale nella modellazione. Operazioni su tipi di dato astratti (classi, struct) sono tipicamente non atomiche a meno di sincronizzazione esplicita. Gli stati interni inconsistenti sono invisibili in programmazione sequenziale ma diventano problematici in contesto concorrente.
In ingegneria del software, i modelli sono descrizioni rigorose della struttura e del comportamento di un programma a un adeguato livello di astrazione. Per i programmi concorrenti, definire modelli appropriati permette di:
Un buon modello include le informazioni rilevanti e astrae da quelle non rilevanti, permettendo di ragionare sul comportamento dinamico dei programmi concorrenti e sulla loro verifica.
Il modello classico per l'esecuzione concorrente si basa su due assunzioni fondamentali:
In pratica si immagina un singolo processore globale astratto che esegue tutte le azioni, una dopo l'altra, in un ordine non determinato a priori. Una computazione o scenario è una sequenza di esecuzione che può effettivamente verificarsi come risultato dell'interleaving.
Nella lezione del 16 marzo il modello viene ripreso in forma schematica:
Questo modello e una astrazione: nella realta, i sistemi non hanno uno stato globale (questione di fisica). Ma l'astrazione e giustificata perche permette l'analisi formale, indipendente da tempi e velocita dei processori.
La formulazione più completa, dalla lezione del 13 marzo, distingue tre assunzioni fondamentali:
In questo modello, il puntatore di controllo (control pointer) di un processo indica la prossima istruzione eseguibile. Una computazione (o scenario) e una sequenza di esecuzione che puo verificarsi come risultato dell'interleaving. Uno stato e definito da una tupla composta da: un'etichetta per ogni processo (la prossima istruzione da eseguire) e un valore per ogni variabile globale o locale.
flowchart LR
subgraph P[Processo P]
p1["p1: n := k1"]-->p2["p2: (fine)"]
end
subgraph Q[Processo Q]
q1["q1: n := k2"]-->q2["q2: (fine)"]
end
INIT["
n=0, k1=1, k2=2
P=p1, Q=q1"]-->p1
INIT-->q1
p1-->|"n=1"|Q
q1-->|"n=2"|P
Q-->q2
P-->p2
k1=1 e k2=2 vengono assegnate a n. Se esegue prima P, n=1; se esegue prima Q, n=2. Lo stato finale dipende dall'ordine di interleaving.
Come possiamo studiare il comportamento di un programma concorrente in modo rigoroso, quasi matematico? Il professor Ricci introduce la rappresentazione a stati e transizioni.
Lo stato del sistema è definito da una tupla composta da:
C'è una transizione tra due stati s1 e s2 se l'esecuzione di un'istruzione in s1 porta a s2. L'istruzione eseguita deve essere una di quelle puntate dai puntatori di controllo in s1.
Il diagramma di stato è il grafo che contiene tutti gli stati raggiungibili del programma. Gli scenari (o tracce di esecuzione) sono i cammini nel grafo a partire dallo stato iniziale. I cicli rappresentano la possibilità di computazione infinita in un grafo finito.
Una volta costruito il diagramma di stato, possiamo esplorarlo per verificare proprietà. Per ogni stato, possiamo controllare se una condizione indesiderata è vera o falsa. Questo rende deterministico il modo di stabilire se un programma concorrente è corretto. Il problema è il numero di stati: l'esplosione dello spazio degli stati.
Due processi P e Q che assegnano valori a una variabile condivisa n:
integer k1 := 1
p1: n := k1
integer k2 := 2
q1: n := k2
integer n := 0L'esecuzione puo seguire due scenari:
p1, q1 → n = 2q1, p1 → n = 1Il risultato finale dipende dall'ordine con cui le istruzioni vengono interleave: questo e il cuore del non-determinismo nei programmi concorrenti. Per comprendere il comportamento di un programma concorrente non possiamo affidarci all'esecuzione reale: il non-determinismo dell'interleaving fa si che uno stesso input possa produrre output diversi a seconda dello scenario.
Con due processi e un'azione ciascuno, ci sono solo 2 scenari possibili:
Esplorate i due scenari con questo strumento interattivo:
Questo esempio fondamentale mostra che lo stesso input può produrre output diversi a seconda dello scenario di interleaving. È questa la radice della difficoltà della programmazione concorrente.
Il diagramma di stato rappresenta formalmente l'esecuzione dell'esempio: ogni stato e una tupla che contiene il control pointer di ogni processo e i valori di tutte le variabili (globali e locali). Lo stato e definito come:
<p_i, q_j, n, k1, k2>dove p_i e il control pointer di P, q_j quello di Q, e gli altri sono i valori delle variabili. Dal punto di partenza, si costruiscono incrementalmente tutti gli stati raggiungibili. Il grafo risultante ha 5 stati e 2 scenari per l'esempio sopra.
Il modello a interleaving arbitrario e una potente astrazione: ignora il tempo e si concentra sull'ordine parziale delle azioni e sulla loro atomicita. Questo rende i programmi concorrenti trattabili con l'analisi formale, indipendentemente dalla velocita dei processori o dal carico di sistema.
Il diagramma di stato completo del primo esempio (5 stati e 2 scenari):
flowchart LR s0["<p1,q1,0,1,2>"] s1["<end,q1,1,1,2>"] s2["<p1,end,2,1,2>"] s3["<end,end,2,1,2>"] s4["<end,end,1,1,2>"] s0 -->|p1: n:=k1| s1 s0 -->|q1: n:=k2| s2 s1 -->|q1: n:=k2| s3 s2 -->|p1: n:=k1| s4
Consideriamo due processi che stampano due messaggi ciascuno:
/* Processo P */
p1: print("p1")
p2: print("p2")
/* Processo Q */
q1: print("q1")
q2: print("q2")Quanti scenari possibili? Se proviamo a elencarli:
In totale 6 scenari. Il professor Ricci fa notare come già con solo due azioni per processo la complessità inizi a crescere. Il diagramma di stato corrispondente:
flowchart LR s0["<p1,q1>"] s1["<p2,q1>"] s2["<p1,q2>"] s3["<p2,q2>"] s4["<-,q1>"] s5["<p1,->"] s6["<-,q2>"] s7["<p2,->"] s8["<-,->"] s0 -->|p1| s1 s0 -->|q1| s2 s1 -->|p2| s4 s1 -->|q1| s3 s2 -->|p1| s3 s2 -->|q2| s5 s3 -->|p2| s6 s3 -->|q2| s7 s4 -->|q1| s6 s5 -->|q2| s7 s6 -->|q2| s8 s7 -->|p2| s8
Esplorate i vari stati del diagramma con questo strumento interattivo:
Il professor Ricci osserva che se aggiungiamo un terzo processo (R con due azioni), gli scenari diventano 90. Con 6 azioni per processo? L'esplosione combinatoria è evidente.
Il diagramma degli stati si costruisce incrementalmente: per ogni stato, si considera ogni processo e si esegue la sua prossima istruzione atomica, generando un nuovo stato. Si continua fino a coprire tutti gli stati raggiungibili.
Lo stesso primo esempio, esplorabile stato per stato con le tuple complete:
Il numero di scenari possibili cresce in modo combinatorio. Con 2 processi che hanno ciascuno m azioni atomiche, il numero di scenari possibili e dato da:
(2m)! / (m! m!)
Questa crescita esplosiva e la ragione per cui la verifica manuale dei programmi concorrenti e complessa e per cui servono strumenti automatici come il model checker.
Valori validi quando le azioni dei processi non hanno dipendenze. Con operazioni in competizione su variabili condivise, alcuni scenari sono equivalenti ma il numero totale resta elevato.
Il numero di scenari possibili cresce in modo esplosivo all'aumentare del numero di processi e di azioni atomiche. Il professore mostra una tabella che lo dimostra in modo concreto:
| Azioni per processo | 2 processi | 3 processi |
|---|---|---|
| 1 | 2 | 6 |
| 2 | 6 | 90 |
| 3 | 20 | 1.680 |
| 4 | 70 | 34.650 |
| 5 | 252 | — |
| 6 | 924 | — |
| 7 | 3.432 | — |
| 8 | 12.820 | — |
La formula generale per m processi ciascuno con n azioni atomiche e data dal coefficiente multinomiale: (m * n)! / (n!)^m. Questo spiega il fenomeno noto come state-space explosion: anche con pochi processi e poche azioni, il numero di scenari da esplorare cresce vertiginosamente, rendendo necessario l'uso di tecniche di riduzione (come l'esplorazione incrementale o la riduzione dell'ordine parziale).
Il professore fa notare che questa crescita e rilevante quando le azioni non hanno dipendenze fra loro. Se ci sono dipendenze (es. un processo deve attendere il risultato di un altro), il numero di scenari diminuisce perche alcuni interleaving sono invalidati dalle condizioni di sincronizzazione.
La formula generale per k processi con n1, n2, ..., nk azioni ciascuno è:
(n1 + n2 + ... + nk)! / (n1! · n2! · ... · nk!)
Il professor Ricci osserva che questi numeri crescono così rapidamente che bastano poche azioni e pochi processi per avere miliardi di scenari. È il fenomeno dell'esplosione dello spazio degli stati.
Nel caso di m processi ciascuno con n azioni la formula si scrive anche così:
Numero scenari = (m * n)! / (n!)^mProvate a costruire una a una le 6 sequenze possibili dell'esempio dei print:
Questa crescita esponenziale (chiamata esplosione degli scenari) è uno dei problemi fondamentali della verifica dei programmi concorrenti.
Una delle questioni più delicate nella modellazione concorrente è cosa si considera atomico. Il docente mostra la differenza cruciale tra un incremento atomico e uno non atomico.
Scegliere il giusto livello di atomicità è fondamentale nella modellazione. Se si considera atomica un'operazione che in realtà non lo è (dal punto di vista del supporto hardware/sistema), il modello potrebbe nascondere scenari errati che in pratica si verificano.
Un'istruzione atomica viene eseguita fino al completamento senza possibilita di interleaving con altre istruzioni.
Nel caso non-atomico, solo 2 scenari su 6 producono il valore finale n = 2. Gli altri 4 scenari producono n = 1 perche entrambi i processi leggono il valore iniziale 0 prima che l'altro lo incrementi.
Le due versioni dello stesso programma a confronto:
/* Processo P */
p1: n := n + 1
/* Processo Q */
q1: n := n + 1
/* Variabile condivisa */
integer n := 0Se l'incremento è atomico, il risultato finale è sempre n = 2. Un solo scenario possibile.
/* Processo P */
integer tmp;
p1: tmp := n
p2: n := tmp + 1
/* Processo Q */
integer tmp;
q1: tmp := n
q2: n := tmp + 1
/* Variabile condivisa */
integer n := 0Se l'incremento è non atomico (spacchettato in lettura e scrittura), il risultato finale può essere n = 1 o n = 2, a seconda dell'interleaving. Su 12 stati, solo 2 scenari su 6 portano a n = 2.
Il diagramma di stato per il caso non atomico mostra 12 stati:
flowchart LR s0["<p1,q1,0,0,0>"] s1["<p2,q1,0,0,0>"] s2["<p1,q2,0,0,0>"] s3["<p2,q2,0,0,0>"] s4["<-,q1,1,0,0>"] s5["<p1,-,1,0,0>"] s6["<-,q2,1,0,1>"] s7["<p2,-,1,0,0>"] s8["<p2,-,1,1,0>"] s9["<-,q2,1,0,0>"] s10["<-,-,2,0,1>"] s11["<-,-,1,0,0>"] s0 -->|p1| s1 s0 -->|q1| s2 s1 -->|p2| s4 s1 -->|q1| s3 s2 -->|p1| s3 s2 -->|q2| s5 s3 -->|p2| s6 s3 -->|q2| s7 s4 -->|q1| s6 s5 -->|q2| s9 s6 -->|q2| s10 s7 -->|p2| s11 s8 -->|q2| s6 s9 -->|p1| s11 s10 -->|p2| s8
Il professor Ricci spiega che l'incremento atomico può essere ragionevole come assunzione di modellazione (se la macchina concorrente lo supporta), mentre l'incremento non atomico è più realistico rispetto a ciò che accade realmente a livello hardware. Ad esempio, l'istruzione assembly INC lavora sul registro, non direttamente sulla memoria: è inevitabile un passaggio lettura-modifica-scrittura.
Il professor Ricci mostra anche come le stesse operazioni appaiono a livello di macchina, sia su stack machine che su register machine:
/* Processo P */
p1: push n
p2: push #1
p3: add
p4: pop n
/* Processo Q */
q1: push n
q2: push #1
q3: add
q4: pop n/* Processo P */
p1: load R1, n
p2: add R1, #n
p3: store n, R1
/* Processo Q */
q1: load R1, n
q2: add R1, #n
q3: store n, R1Il professor Ricci sottolinea che la scelta del livello di atomicità ha un impatto diretto sul numero di stati e scenari. Azioni atomiche più grandi riducono la complessità del modello, ma potrebbero non essere realistiche rispetto all'implementazione sottostante. È un trade-off fondamentale nella modellazione.
Una variante della decomposizione, mostrata il 13 marzo, spacchetta l'incremento in tre passi — tmp := n, tmp := tmp + 1, n := tmp: il numero di scenari sale a 6 e in alcuni di essi il valore finale di n e 1 (non 2). Per esempio: P legge n=0, Q legge n=0, Q scrive n=1, P scrive n=1. Due incrementi concorrenti producono un solo incremento effettivo. Ecco la race condition classica.
double in Java non lo e). I tipi astratti composti da piu oggetti semplici sono tipicamente non atomici: il problema e che un processo puo lavorare su un oggetto mentre un altro lo sta modificando, trovandosi in uno stato interno inconsistente.
Il professore ha enfatizzato: la scelta di cosa e atomico e fondamentale. Un'incremento (n = n + 1) e atomico? Se si, uno scenario. Se e scomposto in (tmp = n; n = tmp + 1), ci sono 6 scenari e in 4 di questi il risultato finale non e 2 ma 1. Questa e la radice di tutti i bug di concorrenza.
Interagite con il diagramma di stato del problema dell'incremento non atomico. Cliccate sugli stati per vedere le transizioni possibili.
Il concetto di atomicità si estende anche alle strutture dati. Un oggetto dati atomico può trovarsi in un numero finito di stati pari al numero di valori che può assumere. I tipi primitivi nei linguaggi concorrenti sono generalmente atomici (ma non sempre: es. double in Java non è atomico su tutte le piattaforme).
I tipi di dato astratti (ADT) composti da più oggetti semplici sono tipicamente non atomici (es. classi in linguaggi OO, struct in C). Per un ADT si distinguono:
La corrispondenza tra stati interni ed esterni è parziale: esistono stati interni che non hanno un corrispondente stato esterno (stati consistenti).
L'esecuzione di un'operazione su un ADT non atomico può attraversare stati inconsistenti. In programmazione sequenziale questo non è un problema (grazie all'information hiding), ma in programmazione concorrente si crea una situazione pericolosa: un processo potrebbe operare su un oggetto mentre un altro processo lo sta modificando, trovandolo in uno stato inconsistente.
Serve introdurre meccanismi che garantiscano che i processi lavorino sempre su oggetti dati in stati consistenti. È qui che entrano in gioco lock, semafori, monitor e altri meccanismi di sincronizzazione.
Nella ripresa del 2 marzo il professore precisa: gli stati interni che hanno un corrispondente esterno sono detti consistenti; quando si esegue un'operazione su un ADT non atomico si possono attraversare stati interni non consistenti, e in un contesto concorrente un thread potrebbe osservare l'oggetto proprio in uno di questi stati.
Il non atomiche delle strutture dati e la ragione profonda per cui serve la sincronizzazione. Non basta rendere atomiche le singole operazioni: bisogna garantire che nessun thread veda mai l'oggetto in uno stato intermedio inconsistente. synchronized, i lock e i monitor servono proprio a questo.
Il professore mostra l'esempio del contatore a livello macchina per illustrare come anche un semplice count++ sia in realta una sequenza di 3-4 istruzioni macchina (su stack machine: push n, push #1, add, pop n), e come l'interleaving fra queste istruzioni produca risultati errati.
flowchart LR
subgraph P["Processo P"]
direction TB
p1["p1: push n"] --> p2["p2: push #1"]
p2 --> p3["p3: add"]
p3 --> p4["p4: pop n"]
end
subgraph Q["Processo Q"]
direction TB
q1["q1: push n"] --> q2["q2: push #1"]
q2 --> q3["q3: add"]
q3 --> q4["q4: pop n"]
end
Se l'interleaving e p1, q1, p2, p3, p4, q2, q3, q4, entrambi i processi leggono n=0 e scrivono n=1, producendo il lost update.
Non tutti i processi terminano. Il professor Ricci introduce il caso di processi con comportamento ciclico infinito:
/* Processo P - cerca di portare n ad almeno 1 */
p1: while (n < 1)
p2: n := n + 1
/* Processo Q - cerca di portare n a 0 o meno */
q1: while (n >= 0)
q2: n := n - 1
/* Variabile condivisa */
integer n := 1Questo esempio è tratto dal libro di Ben-Ari. I due processi hanno obiettivi opposti: P vuole incrementare n fino a 1, Q vuole decrementarlo fino a 0 o meno.
Il diagramma di stato è complesso, con molteplici cicli che rappresentano computazioni potenzialmente infinite. A seconda dell'interleaving, il sistema può terminare (quando entrambi i processi escono dai loro cicli) o continuare indefinitamente.
I processi ciclici sono la norma, non l'eccezione, nei sistemi concorrenti. Un sistema operativo, un server web, un controller industriale: sono tutti progettati per non terminare. La correttezza riguarda ciò che accade durante l'esecuzione, non solo alla fine.
I cicli nel diagramma di stato rappresentano la possibilità di computazione infinita in un grafo finito. L'analisi di questi cicli è cruciale per le proprietà di liveness.
Sullo stesso esempio, la lezione del 23 febbraio osserva che si possono costruire scenari in cui il ciclo in P esegue esattamente una iterazione oppure tre iterazioni, a seconda dell'interleaving con Q.
I cicli nei processi concorrenti rendono il diagramma di stato potenzialmente infinito (o molto grande). La non-terminazione è una possibilità reale in molti sistemi concorrenti (sistemi di controllo, server, sistemi operativi).
Accanto al modello a interleaving e ai diagrammi di stato, il corso introduce un secondo formalismo per modellare la concorrenza. Il professor Ricci apre la lezione ricordando che le reti di Petri sono un formalismo già introdotto in altri corsi, ma che in questo contesto vengono utilizzate con un obiettivo molto specifico: modellare sistemi di processi concorrenti per analizzarne il comportamento, verificare proprietà di safety e liveness, e progettare la coordinazione.
Una rete di Petri è composta da place (piazze, che rappresentano stati) e transizioni (che rappresentano azioni). I token forniscono una "fotografia runtime" dello stato del sistema: ogni token rappresenta un flusso di controllo, cioè un'istanza di un processo che segue lo schema di comportamento definito dalla rete.
Quando modellate un processo con una rete di Petri, le piazze rappresentano lo stato del processo, il token rappresenta il suo flusso di controllo. Le transizioni sono le azioni che il processo può compiere. Una transizione scatta se per ogni arco in ingresso c'è almeno un token nel place sorgente.
La semantica delle reti di Petri è semplice ma potente: una transizione consuma un token da ogni place in ingresso e produce un token in ogni place in uscita. Due token in uno stesso place rappresentano due processi distinti con la stessa struttura comportamentale.
Il consiglio del professore è di pensare sempre a cosa si vuole modellare: se il token rappresenta un flusso di controllo, consumare un token significa "il flusso prosegue"; se invece il token rappresenta una risorsa (come un permesso), la semantica cambia. Le reti di Petri unificano entrambi i concetti in un unico formalismo.
Il professore mostra come modellare costrutti di programmazione sequenziale con le reti di Petri. Consideriamo un programma che esegue A, poi valuta una condizione C e, a seconda del risultato, esegue B oppure C (if-then-else), e infine D.
La modellazione introduce una transizione che rappresenta la valutazione della condizione. Da questa partono due archi: uno verso il ramo B (condizione vera), l'altro verso il ramo C (condizione falsa). Non esiste un unico modo corretto di modellare: il livello di astrazione lo definite voi.
flowchart LR
subgraph "Processo P"
direction TB
start((i)) --> A[A]
A --> cond{C?}
cond -->|true| B[B]
cond -->|false| C[C]
B --> D[D]
C --> D[D]
D --> loop(( ))
end
La trascrizione originale dice: "Le azioni le modello sempre come transizione. Poi introduco una transizione che rappresenta la valutazione della condizione. C'è un solo modo? No. E questo vale per tutti i formalismi. Siete voi che definite il livello di astrazione che volete."
Il professore applica l'approccio metodologico per modellare il problema classico dei produttori e consumatori con buffer. La strategia è sempre: prima rappresentare lo schema di comportamento dei singoli processi, poi aggiungere la "colla" della coordinazione.
Il produttore è un ciclo che produce un item e lo inserisce nel bounded buffer (transizioni produce e insert). Il consumatore prende un item dal buffer (transizione get) e poi lo consuma (transizione consume). N token per N produttori, M token per M consumatori.
La coordinazione emerge introducendo place che rappresentano i permessi: un place per i posti disponibili nel buffer (inizializzato con N token) e uno per gli item disponibili (inizializzato a 0). Questi place "risorsa" sono concettualmente diversi dai place che rappresentano il flusso di controllo, ma il formalismo li unifica.
flowchart LR
subgraph Produttore[i-esimo Producer]
p1[produce] --> p2[insert]
p2 --> p1
end
subgraph Consumatore[j-esimo Consumer]
q1[get] --> q2[consume]
q2 --> q1
end
p2 -- item --> buffer[(Buffer)]
buffer -- item --> q1
places[(N posti)] -- permesso --> p2
q1 -- rilascio --> places
La bellezza delle reti di Petri è che con un unico formalismo catturano sia il flusso di controllo (token = istanza del processo) sia le risorse di coordinazione (token = permesso). I place hanno lo stesso aspetto ma significato diverso a seconda del contesto.
Il problema Readers-Writers introduce una sfida più sottile: i lettori non devono escludersi tra loro, ma devono escludere gli scrittori (e viceversa). Nella modellazione con reti di Petri, l'approccio naive che usa un singolo permesso porta a una sezione critica pura: se un lettore prende il permesso, blocca anche gli altri lettori, il che non è desiderabile.
La soluzione mostrata dal professore introduce N token nel place dei permessi per i lettori: ogni lettore consuma un token per entrare, ma se ci sono N token iniziali, fino a N lettori possono entrare simultaneamente. Finché c'è almeno un lettore attivo, gli scrittori sono bloccati.
Se usate un singolo token (semaforo binario) per il problema Readers-Writers, ottenete una soluzione over-constrained che serializza anche i lettori, perdendo il vantaggio del parallelismo in lettura. Il professore sottolinea: "Se consumo il token per poter entrare, il reader passa ma blocca tutti gli altri — sto serializzando i readers che non va bene."
La sincronizzazione definisce relazioni temporali tra processi ("A deve avvenire prima di B"), mentre la mutua esclusione definisce una restrizione sull'accesso a dati condivisi ("un solo processo alla volta può accedere a questa risorsa"). La mutua esclusione è una forma implicita di sincronizzazione, ma la sincronizzazione non richiede necessariamente dati condivisi. In Java, synchronized è un esempio di naming che crea confusione: denota mutua esclusione, non sincronizzazione.
Le race condition si verificano quando due o più processi accedono concorrentemente a risorse condivise e il risultato dipende dall'ordine specifico delle operazioni. Sono difficili da debuggare perché sono tempo-dipendenti: producono errori solo per specifici interleaving. Inoltre, il debugging stesso altera i tempi di esecuzione, facendo sparire il bug (fenomeno degli heisenbug). L'esempio classico è il lost update nell'incremento non atomico di una variabile condivisa.
La formula generale è (n1 + n2)! / (n1! · n2!). Per 2 processi con 3 azioni ciascuno: (3+3)! / (3! · 3!) = 720 / (6 · 6) = 20 scenari. L'esplosione combinatoria è evidente: con 6 azioni per processo si arriva a 924 scenari, con 8 a 12.820.
Le proprietà di safety richiedono che "le cose cattive non accadano mai", e sono verificate se sono vere in ogni stato di ogni computazione (es. mutua esclusione, assenza di deadlock). Sono più facili da verificare: basta uno stato che le violi per falsificarle. Le proprietà di liveness richiedono che "le cose buone prima o poi accadano", e sono verificate se in ogni computazione esiste qualche stato in cui la proprietà è vera (es. assenza di starvation, comunicazione affidabile). Sono più difficili da verificare perché richiedono di analizzare l'intera traccia di esecuzione.
I tre tipi di fairness riguardano il scheduling:
La differenza sta in quante volte la condizione deve diventare vera perché l'azione sia garantita. La strong fairness è più difficile da garantire ma è necessaria per alcuni tipi di algoritmi.
Quattro proprietà fondamentali:
Inoltre, la CS deve avere la proprietà di progress (una volta iniziata, deve terminare), mentre la NCS no.
L'overtaking descrive la situazione in cui un processo Q può entrare in sezione critica ripetutamente mentre un processo P è in attesa. Non è starvation (P prima o poi entra), ma è ingiusto. La proprietà di k-bounded overtaking limita a k il numero di volte che Q può sorpassare P. Si esprime con l'operatore Weak Until W. Esempio di 1-bounded overtaking:
tryp → (¬ CSq) W (CSq W ((¬ CSq) W CSp))
Il testing verifica che una proprietà valga per alcuni scenari selezionati; rivela la presenza di errori ma non la loro assenza. La verification usa tecniche formali (model checking o dimostrazione induttiva) per verificare che una proprietà valga per tutti gli scenari possibili. Per i programmi concorrenti, il testing tradizionale è insufficiente perché lo stesso input può dare output diversi e gli heisenbug possono sparire durante il debugging.
I principali operatori LTL sono:
[] p (Always/Box): p è vera in tutti gli stati futuri → esprime proprietà di safety.<> p (Eventually/Diamond): p è vera in qualche stato futuro → esprime proprietà di liveness.O p (Next/X): p è vera nello stato successivo.p U q (Until): q diventa vera prima o poi e p è vera fino a quel momento.p W q (Weak Until): come Until ma q non è obbligata a diventare vera.Sono strumenti di verifica formale:
Tutti risolvono il problema di verificare la correttezza di sistemi concorrenti dove il testing tradizionale è insufficiente.
Lo speedup è il rapporto S = T1 / TN, dove T1 è il tempo di esecuzione sequenziale e TN il tempo parallelo con N processori. Misura quanto più veloce è l'esecuzione parallela.
In un workload CPU-bound i thread eseguono computazione pura: aumentare i thread oltre il numero di core peggiora le prestazioni (context switch). In un workload IO-bound i thread passano gran parte del tempo bloccati in attesa: avere più thread del numero di core è utile perché mentre uno è bloccato, un altro può usare la CPU.
I platform thread sono mappati 1:1 su thread del sistema operativo: sono pesanti da creare e il context switch è costoso. I virtual thread (Java 21+) sono gestiti dalla JVM su un pool di pochi OS thread: sono leggerissimi e se ne possono creare centinaia di migliaia senza overhead significativo.
20 scenari. La formula generale è (m × n)! / (n!)m, dove m = processi e n = azioni per processo. Per 2 processi e 3 azioni: 6! / (3! × 3!) = 720 / 36 = 20.
Una proprietà di safety deve essere sempre vera in ogni stato di ogni computazione («cose brutte non devono mai accadere»). Esempi: mutua esclusione, assenza di deadlock. Si esprime in LTL con l'operatore □ (always).
1) Mutua esclusione (mai due processi contemporaneamente in CS). 2) Assenza di deadlock (se qualcuno cerca di entrare, prima o poi qualcuno ci riesce). 3) Assenza di starvation individuale (se un processo cerca di entrare, prima o poi ci riesce). A queste si aggiunge il bounded waiting.
L'istruzione test-and-set(x, r) esegue atomicamente: r := x; x := 1. Restituisce il vecchio valore di x in r e setta x a 1. È utile per implementare lock: se il lock era 0 (libero), diventa 1 (acquisito); se era 1 (occupato), il processo deve riprovare.
Il testing verifica una proprietà per alcuni scenari selezionati (rivela la presenza di errori, non la loro assenza). Il model checking verifica ESAUSTIVAMENTE tutti gli scenari possibili (rivela l'assenza di errori, ma soffre di esplosione dello spazio degli stati).
□ (p2 ⇒ ◇ p3)?Significa: «in ogni stato, se il controllo è a p2 (sto cercando di entrare in CS), allora prima o poi sarà a p3 (sarò nella CS)». È una proprietà di liveness (assenza di starvation).
TLA+ (Lamport) è un linguaggio di specifica formale per descrivere comportamenti di sistemi concorrenti e verificare proprietà di correttezza. PlusCal è un linguaggio algoritmico che si traduce in TLA+. Entrambi supportano il model checking con TLC.