Problema classico della programmazione concorrente, introdotto da Dijkstra nel 1971 (originariamente come problema di sincronizzazione per 5 computer in competizione per 5 unita a nastro) e reso celebre da Tony Hoare nella versione dei filosofi a cena.
Descrizione: Cinque filosofi trascorrono la vita alternando due attivita: pensare e mangiare. I pasti sono consumati a un tavolo con 5 piatti e 5 forchette. Al centro c'e una scodiglia di spaghetti sempre piena. Ogni filosofo ha bisogno di due forchette per mangiare — quella a sinistra e quella a destra — ma può raccoglierle solo una alla volta.
L'obiettivo e progettare protocolli pre- e post- che garantiscano: mutua esclusione sulle forchette, assenza di deadlock, assenza di starvation, ed efficienza in assenza di contesa.
Il primo tentativo — modellare ogni forchetta come semaforo binario e far prendere a ogni filosofo prima la sinistra poi la destra — porta a deadlock. Se tutti i filosofi prendono la forchetta sinistra contemporaneamente, nessuno potra mai prendere quella destra. E l'esempio didattico perfetto di circular wait.
Il professor Ricci riassume cosi i requisiti dei protocolli di pre- e post- da progettare:
Il ciclo di vita di un singolo filosofo puo essere esplorato interattivamente:
Il problema fu introdotto da Dijkstra proprio per illustrare il problema del deadlock (che chiamava deadly embrace); oggi e considerato un classico veicolo didattico per confrontare formalismi di programmazione concorrente. La sfida e che le forchette sono condivise tra filosofi adiacenti: la forchetta i e usata dai filosofi i e (i+1)%N.
semaphore array[0..4] fork ← [1,1,1,1,1]
philosopher[i]: { per i = 0..4 }
loop forever
think
wait(fork[i]) { prendi forchetta sinistra }
wait(fork[(i+1)%N]) { prendi forchetta destra }
eat
signal(fork[i])
signal(fork[(i+1)%N])Questo tentativo e corretto per la mutua esclusione (nessuna forchetta e mai tenuta da due filosofi contemporaneamente, perche ogni forchetta e un semaforo binario), ma soffre di deadlock: se tutti i filosofi prendono contemporaneamente la forchetta sinistra prima che qualcuno provi a prendere la destra, nessuno puo mangiare e tutti restano bloccati per sempre in attesa della forchetta destra.
In sintesi: ogni forchetta e modellata come un semaforo binario, e il filosofo puo raccoglierne solo una alla volta. Purtroppo questa soluzione deadlocka: se tutti i filosofi raccolgono la forchetta sinistra prima che qualcuno provi a raccogliere la destra, nessuno puo mai mangiare.
Un deadlock e una situazione in cui due o piu azioni in competizione aspettano che l'altra finisca, e quindi nessuna finisce mai. Il professore lo chiama anche deadly embrace, il termine originale di Dijkstra. Nel 1971, Coffman identifico le quattro condizioni necessarie affinche un deadlock possa verificarsi in un sistema:
Il deadlock puo verificarsi solo in sistemi dove tutte e quattro le condizioni sono vere contemporaneamente. Rimuovendone anche una sola, il deadlock e prevenuto.
Il caso piu semplice: thread A tiene il lock L e cerca di acquisire M, mentre thread B tiene M e cerca di acquisire L. Entrambi aspettano per sempre. Nei database, questo scenario viene gestito automaticamente: il DBMS analizza il grafo delle dipendenze, identifica il ciclo, sceglie una vittima e abortisce la transazione, rilasciando i lock. Nella JVM, invece, non esiste alcun meccanismo automatico di rilevamento e recovery: "if threads deadlock, that's all, folks!" — l'unica opzione pratica e spegnere l'applicazione e fare una diagnosi post-mortem.
Nei database i deadlock vengono rilevati e gestiti automaticamente (si analizza il grafo is-waiting, si cerca un ciclo, si sceglie una vittima). Nella JVM non c'e nulla di tutto questo: se i thread vanno in deadlock, basta. Si puo solo fare post-mortem diagnosis.
Nel caso dei filosofi, la catena circolare di attesa e esattamente questa:
Nella lezione di ripasso il professore richiama le condizioni di Coffman e ripropone la simulazione completa con tutti e cinque i filosofi: guidando a mano l'interleaving si puo riprodurre (o evitare) il deadlock del primo tentativo.
Il professore presenta due soluzioni classiche al problema dei Filosofi, entrambe valide e che soddisfano tutte le proprieta (mutua esclusione, no deadlock, no starvation, comportamento efficiente in assenza di contesa).
Limitiamo il numero di filosofi che possono mangiare contemporaneamente a N-1 (quindi 4 su 5). L'idea e che se solo 4 filosofi possono tentare di prendere le forchette, almeno uno riuscira sempre a prendere entrambe. Si introduce un semaforo counting ticket inizializzato a 4.
Il professore commenta: "Se hai cinque filosofi che vogliono mangiare tutti insieme, metti quattro permessi, fai mangiare solo quattro alla volta. Se metti quattro permessi, come se dovessero prendere un ticket prima di iniziare a mangiare, si risolve il problema."
Si osserva che non c'e deadlock se si impone un ordine totale nell'acquisizione delle forchette. L'idea e che ogni filosofo prende prima la forchetta con indice minore e poi quella con indice maggiore.
Il professore spiega l'intuizione: "Se lui cerca di prendere prima la forchetta con indice minore, e questa e gia stata presa da un altro, si blocca subito senza avere l'altra forchetta. Quindi l'altra forchetta puo essere presa dal filosofo vicino. Non si crea mai un ciclo di attesa."
Limitare il numero di filosofi che possono mangiare simultaneamente a N-1 (4 su 5), introducendo un semaforo ticket inizializzato a 4:
semaphore ticket := (4, {})
loop forever
think
wait(ticket)
wait(fork[i])
wait(fork[(i+1) % N])
eat
signal(fork[i])
signal(fork[(i+1) % N])
signal(ticket)Questa soluzione soddisfa tutte le proprieta.
Rimuovere la condizione di circular wait facendo prendere le forchette in un ordine totale (es., prima la forchetta con indice minore, poi quella con indice maggiore):
integer first = min(i, (i+1) % N)
integer second = max(i, (i+1) % N)
loop forever
think
wait(fork[first])
wait(fork[second])
eat
signal(fork[first])
signal(fork[second])L'ultimo filosofo (indice 4) prendera prima la forchetta 0 e poi la 4, invertendo l'ordine rispetto agli altri — il wait-for chain si spezza.
Un modo intuitivo di vedere la soluzione con ticket e la sala da pranzo: il semaforo ticket inizializzato a N-1 fa entrare in sala al massimo N-1 filosofi su N — solo loro possono competere per le forchette, rompendo la circolarita. Per la soluzione con ordinamento, equivalentemente, si osserva che il deadlock non si verifica se l'ultimo filosofo prende prima la forchetta destra e poi la sinistra: la regola e acquisire sempre i lock in un ordine totale prestabilito, il che rende impossibile la condizione di circular wait.
Dall'esperienza dei Filosofi si generalizza una regola semplice ma potentissima per evitare deadlock in sistemi con lock multipli. Il professore la presenta come forse la cosa piu importante da ricordare quando si scrive codice concorrente:
Rende impossibile la condizione di circular wait, che e una delle quattro condizioni necessarie di Coffman. Se ogni processo acquisisce i lock in ordine crescente, non si puo formare un ciclo: se P aspetta una risorsa tenuta da Q, significa che P ha lock con indici piu piccoli e Q con indici piu grandi, quindi Q non puo a sua volta aspettare una risorsa di P (perche la richiederebbe in ordine crescente, ma ha gia lock con indice maggiore).
Piuttosto che dimostrarlo formalmente, il professore ne da l'intuizione: "Notate che cosa succede se lui cerca di prendere prima la forchetta con indice minore. L'ha gia presa? Se e gia stata presa si blocca in attesa senza avere il possesso dell'altra. Quindi sostanzialmente il fatto di imporre l'ordine permette di fare in modo che, quando si crea una situazione che va verso l'essere ciclico, un processo non riesce a prendere neanche la prima."
La regola "acquisisci sempre i lock nello stesso ordine" e forse il singolo concetto piu importante da ricordare per scrivere codice concorrente corretto. Il deadlock e stato ampiamente studiato, e sono state identificate le condizioni necessarie: romperne anche solo una e sufficiente.
Il professore dedica una parte della lezione alle proprieta di liveness dei thread, riprendendo materiale da "Java Concurrency in Practice". Anche se la sezione critica garantisce mutua esclusione, non e sufficiente: il programma deve anche progressare. Due problemi classici:
Deadlock (stallo): due o piu thread aspettano ciascuno un lock che l'altro possiede, e nessuno puo proseguire. Le condizioni necessarie (Coffman, 1971) sono quattro e devono valere tutte contemporaneamente:
Starvation (inedia): un thread e pronto per eseguire ma non ottiene mai la CPU o il lock che richiede, perche altri thread vengono sempre preferiti dallo scheduler. A differenza del deadlock, il thread non e bloccato permanentemente, ma non fa progressi per un periodo indefinito.
Livelock: i thread non sono bloccati ma continuano a eseguire azioni che non portano a progresso. Un esempio tipico: due thread che rilevano un conflitto e "cedono" il passo all'altro, finendo per oscillare senza mai procedere. Il professore lo menziona a proposito del terzo tentativo di soluzione della sezione critica.
Il professore sottolinea che la JVM non ha un meccanismo automatico di rilevamento o recupero dai deadlock: "if threads deadlock, that's all, folks!" — l'unica opzione e arrestare l'applicazione. Il supporto si limita a strumenti di diagnostica post-mortem (stack trace, thread dump).
Il professore mostra il deadlock nella sua forma piu semplice: deadly embrace (abbraccio mortale). Due thread, A e B, e due lock, L1 e L2:
La soluzione strutturale al deadlock segue una regola semplice ma potente: acquisire i lock sempre nello stesso ordine globale. Se tutti i thread acquisiscono L1 prima di L2, il ciclo di attesa non puo formarsi, perche non ci puo essere un thread che tiene L2 e richiede L1 mentre un altro tiene L1 e richiede L2.
Le condizioni di Coffman sono necessarie ma non sufficienti: se anche tutte valgono, un deadlock potrebbe non verificarsi (serve il giusto interleaving). Per evitarli: (1) acquisire lock in ordine globale, (2) usare tryLock() con timeout, (3) ridurre il numero di lock, (4) usare astrazioni di piu alto livello.