Il capitolo in un paragrafo. Come impedire a due processi di eseguire insieme la sezione critica, avendo a disposizione solo letture e scritture atomiche? Ogni correzione ingenua rompe una proprietà diversa. Dekker e Peterson risolvono il caso con due processi, il biglietto del fornaio quello con N. Con un'istruzione hardware come test-and-set il problema diventa banale, ed è su queste istruzioni che poggiano lock, semafori e monitor.
Il problema, posto da Dijkstra nel 1965, è il caso tipico di competizione tra processi. Ognuno degli N processi esegue un ciclo infinito diviso in due parti: la sezione critica (CS), che accede a oggetti condivisi, e la sezione non critica (NCS), tutto il resto. Il compito è progettare il protocollo di ingresso e il protocollo di uscita che la racchiudono. Esempio: i chioschi di check-in di un aeroporto che aggiornano lo stesso database dei passeggeri.
loop forever
non-critical section
entry protocol -- da progettare
critical section
exit protocol -- da progettareLa sezione critica è un pezzo di codice, non una zona di memoria. Le proprietà richieste sono tre, più una quarta più forte:
| Proprietà | Tipo | Significato |
|---|---|---|
| Mutua esclusione | safety | Le istruzioni delle sezioni critiche di due processi non si alternano mai: nessuno stato ha due processi in CS. |
| Assenza di deadlock | liveness | Se alcuni processi cercano di entrare in CS, prima o poi uno di loro ci riesce. |
| Assenza di starvation | liveness | Se un processo cerca di entrare in CS, prima o poi quel processo ci riesce. |
| Attesa limitata (k-bounded overtaking) | più forte | Da quando un processo chiede di entrare, gli altri possono entrare al massimo k volte prima di lui. |
Qui l'assenza di deadlock è una liveness («prima o poi qualcuno entra»). Si può anche leggere come safety, «nessuno stato raggiungibile in cui chi vuole entrare è bloccato», ed è così che la controlla un model checker (capitolo 11): le due letture non si contraddicono.
Regole del gioco: chi entra in CS deve prima o poi uscirne; nella NCS invece un processo può restare per sempre, quindi un protocollo non può contare sul fatto che l'altro faccia qualcosa. Le sole istruzioni atomiche sono load e store.
La correttezza si analizza sul diagramma di stato ridotto alle righe che contano per la sincronizzazione. La mutua esclusione è violata se è raggiungibile uno stato con entrambi in CS. Il deadlock è uno stato raggiungibile in cui chi vuole entrare non può più muoversi. La starvation è un ciclo di esecuzione, compatibile con la fairness, in cui un processo resta per sempre nel protocollo di ingresso.
Ricci ha detto che non serve ricordare a memoria tutti gli algoritmi. Conta saper analizzare una soluzione: per ogni proprietà, trovare lo scenario che la viola o spiegare perché non esiste.
I tentativi seguono l'ordine del corso e del libro di Ben-Ari. await c e while c skip sono attese attive (busy-waiting): nel diagramma di stato, un'istruzione che non può essere eseguita finché la condizione è falsa.
integer turn := 1
p q
p1: NCS q1: NCS
p2: await turn = 1 q2: await turn = 2
p3: CS q3: CS
p4: turn := 2 q4: turn := 1turn dice a chi tocca, come un testimone passato avanti e indietro. Mutua esclusione e assenza di deadlock valgono. La starvation no: se p passa il turno a q e q resta per sempre nella NCS, come ha diritto di fare, p non entra più.
boolean wantp := false, wantq := false
p1: NCS q1: NCS
p2: while wantq skip q2: while wantp skip
p3: wantp := true q3: wantq := true
p4: CS q4: CS
p5: wantp := false q5: wantq := falseUn flag per processo dice chi vuole entrare, così nessuno aspetta chi sta nella NCS. La mutua esclusione è violata: test (p2) e set (p3) sono due passi distinti, e con p2, q2, p3, q3 entrambi trovano l'altro flag a false ed entrano.
p1: NCS q1: NCS
p2: wantp := true q2: wantq := true
p3: await wantq = false q3: await wantp = false
p4: CS q4: CS
p5: wantp := false q5: wantq := falseDichiarando l'intenzione prima del controllo la mutua esclusione torna. Ma c'è deadlock: dopo p2, q2 entrambi aspettano per sempre che l'altro flag diventi falso. Poiché l'attesa è attiva, si parla anche di livelock.
p1: NCS q1: NCS
p2: wantp := true q2: wantq := true
p3: while wantq q3: while wantp
p4: wantp := false q4: wantq := false
p5: wantp := true q5: wantq := true
p6: CS q6: CS
p7: wantp := false q7: wantq := falseChi trova l'altro interessato abbassa il flag per un momento e riprova: niente più deadlock. Resta la starvation: con un interleaving perfettamente alternato i due abbassano e rialzano i flag in sincronia per sempre. È improbabile, ma una proprietà deve valere in ogni esecuzione.
| Tentativo | Idea | Proprietà rotta |
|---|---|---|
| 1 | turno alternato | starvation |
| 2 | flag, test poi set | mutua esclusione |
| 3 | flag, set poi await | deadlock |
| 4 | flag con rinuncia | starvation |
Fai avanzare p e q un'istruzione alla volta e prova a violare una proprietà a mano. Poi premi Verifica tutti gli interleaving: il laboratorio esplora tutti gli stati raggiungibili e cerca violazioni, assumendo uno scheduler debolmente equo (chi resta sempre eseguibile prima o poi viene eseguito). Ogni violazione si può riprodurre passo per passo.
La prima soluzione corretta per due processi è di T. J. Dekker, pubblicata da Dijkstra negli anni '60, e unisce il 1° e il 4° tentativo. Se l'altro non è interessato si entra subito. Se lo sono entrambi, turn assegna il diritto di insistere, non di entrare: chi non ha il turno abbassa il flag e aspetta, chi lo ha tiene il flag alzato finché l'altro si ritira.
boolean wantp := false, wantq := false
integer turn := 1
p1: NCS
p2: wantp := true
p3: while wantq
p4: if turn = 2
p5: wantp := false
p6: await turn = 1
p7: wantp := true
p8: CS
p9: turn := 2
p10: wantp := false -- q è simmetrico: scambia p/q e 1/2Peterson (1981) fonde i due controlli in un unico await:
boolean wantp := false, wantq := false
integer turn := 1
p1: NCS q1: NCS
p2: wantp := true q2: wantq := true
p3: turn := 2 q3: turn := 1
p4: await not wantq or turn = 1 q4: await not wantp or turn = 2
p5: CS q5: CS
p6: wantp := false q6: wantq := falseSi legge «entro se l'altro non è interessato, oppure se tocca a me». Ognuno, dopo aver alzato il flag, cede il turno all'altro, così se arrivano insieme perde l'ultimo che ha scritto turn.
turn a proprio favore, e non può favorire entrambi.turn vale 1 o 2 e uno dei due passa.turn := 1 e cede il posto a p. Nessuno sorpassa l'altro più di una volta (k = 1).Entrambi sono corretti con i soli load e store atomici, e il laboratorio lo conferma. Peterson, più corto e simmetrico, torna nel corso in Java.
Entrambi assumono che le scritture siano viste nell'ordine in cui avvengono. CPU moderne e compilatore Java possono riordinarle: con campi normali Peterson fallisce, con flag e turn dichiarati volatile torna corretto (capitolo 10).
Per N processi il corso usa l'idea della panetteria (bakery): chi arriva prende un biglietto numerato e viene servito in ordine.
integer num := 1, next := 1
integer turn[1..n] := [0, …, 0]
p[i]: loop forever
NCS
< turn[i] := num; num := num + 1 > -- atomico: prendi il biglietto
await turn[i] = next
CS
next := next + 1 -- servi il prossimoPrendere il biglietto deve essere atomico, altrimenti due processi ricevono lo stesso numero. Se lo è, si entra in ordine di arrivo (FIFO): tutte e tre le proprietà valgono. Il difetto è l'overflow: num e next crescono per sempre e con interi finiti prima o poi ripartono da zero.
Questa versione è il ticket algorithm di Andrews, che prende il biglietto con fetch-and-add. Il bakery originale di Lamport (1974) non usa istruzioni speciali: il biglietto è il massimo visto più uno, e a parità vince l'identificativo minore.
Tutta la difficoltà nasce dal fatto che leggere e scrivere una variabile sono due passi separati. Le macchine offrono istruzioni atomiche composte che fanno entrambe le cose in un passo (< … > indica un blocco senza interleaving).
| Istruzione | Effetto atomico |
|---|---|
| test-and-set(x, r) | < r := x; x := 1 > |
| exchange(x, r) | < tmp := x; x := r; r := tmp > |
| fetch-and-add(x, v) | < tmp := x; x := x + v; return tmp > |
| compare-and-swap(x, e, v) | < if x = e then x := v; return true else return false > |
Con test-and-set la sezione critica per un numero qualsiasi di processi si scrive in tre righe:
integer lock := 0 -- 0 libero, 1 occupato
loop forever
NCS
repeat test-and-set(lock, r) until r = 0
CS
lock := 0Se r torna 0 il lock era libero e ora è mio; se torna 1 era occupato (e resta 1), quindi riprovo. Mutua esclusione e assenza di deadlock valgono per ogni N. La starvation no: quando il lock si libera nessuno garantisce che vinca chi aspetta da più tempo, e chi è appena uscito può riprenderlo ogni volta (è lo scenario che trova il laboratorio). In più l'attesa consuma CPU.
Nascondendo il ciclo dietro acquire(l) e release(l) si ottiene l'astrazione lock; in Java è synchronized (obj) { … } (capitolo 10). Semafori (capitolo 5) e monitor (capitolo 7) sono costruiti su queste istruzioni e aggiungono attesa senza consumo di CPU ed equità.
Mutua esclusione (safety), assenza di deadlock e assenza di starvation (liveness). Una versione più forte della terza è l'attesa limitata (k-bounded overtaking). In più, chi entra in CS deve uscirne, mentre nella NCS un processo può restare per sempre.
L'assenza di deadlock garantisce che, se qualcuno cerca di entrare, qualcuno entri. L'assenza di starvation garantisce che entri ogni processo che ci prova. Il lock con test-and-set ha la prima ma non la seconda.
turn, non è corretto?Impone un'alternanza rigida. Se il processo che ha ricevuto il turno resta per sempre nella NCS, cosa lecita, l'altro non può più entrare: è starvation.
Dichiarare l'intenzione prima di controllare quella dell'altro chiude la finestra in cui entrambi vedono false, e la mutua esclusione torna a valere. Ma ora entrambi possono dichiararla insieme e poi aspettarsi a vicenda per sempre: deadlock.
turn in Dekker e in Peterson?Fa da arbitro solo in caso di contesa: se l'altro non è interessato si entra subito. In Dekker turn assegna il diritto di insistere. In Peterson ognuno cede il turno all'altro, e se arrivano insieme perde l'ultimo che ha scritto turn.
I contatori dei biglietti crescono senza limite, e con interi finiti vanno in overflow e rompono l'ordine. Inoltre, nella versione del corso, prendere il biglietto deve essere un'operazione atomica.
await fa busy-waiting?Nel modello di questo capitolo sì: il processo continua a ritestare la condizione, e per il diagramma di stato equivale a un'istruzione non eseguibile finché la condizione è falsa. Semafori e monitor invece sospendono il processo e lo risvegliano quando serve, senza consumare CPU.
Legge e scrive il lock in un solo passo atomico, quindi due processi non possono entrambi trovarlo libero; funziona per qualsiasi N. Non garantisce però l'assenza di starvation, perché nessuno sceglie chi vince quando il lock si libera, e l'attesa resta attiva.
20 febbraio 2026 (§13–15: il problema, Dekker e Peterson, istruzioni atomiche) · 23 febbraio (§14–16: primo tentativo, Dekker, lock) · 27 febbraio (§6–11: proprietà, tentativi 1–4, Dekker, Peterson, istruzioni atomiche, bakery) · 13 marzo (§4–6: ripasso dei protocolli e delle istruzioni atomiche). La mappa completa è in coverage-matrix.json.