Stallo

Nelle lezioni precedenti abbiamo visto alcuni casi in cui processi o thread rimangono in attesa di un evento che non avverrà mai, perché il processo o thread che deve causare tale evento è anch’esso in attesa. In particolare, quando tale attesa diventa circolare parliamo di stallo o deadlock. Più precisamente, diamo la seguente definizione:

Stallo o deadlock: Un insieme S di processi o thread è in stallo se ogni p in S attende un evento che può essere causato solo da processi o thread appartenenti ad S.

Condizioni necessarie per lo stallo

Per quanto riguarda l’allocazione delle risorse, lo stallo avviene solo sotto alcune condizioni:

  1. Mutua esclusione. Se una risorsa può essere utilizzata contemporaneamente da più processi o thread non è necessario attendere quindi non si forma una situazione di stallo. Ad esempio la lettura simultanea di dati condivisi non richiede mutua esclusione.
  2. Possesso e attesa. Se i processi o thread non allocano mai le risorse in modo incrementale, acquisendo una risorsa (possesso) e poi chiedendone altre in seguito (attesa) allora non può succedere che si formi un attesa circolare.
  3. Assenza di preemption. Se il sistema può far rilasciare in modo forzato le risorse a thread o processi, allora è possibile risolvere situazioni di stallo tramite preemption.
  4. Attesa circolare. Per definizione, lo stallo avviene quando c’è una attesa circolare che fa sì che nessun processo o thread uscirà mai dallo stato di attesa.

Gestione delle situazioni di stallo

Lo stallo può essere gestito in vari modi a seconda di se e quando si evidenziano (potenziali) situazioni si attesa circolare.

  • Prevenzione: vengono messe in atto alcune strategie che prevengono la formazione di stalli;
  • Controllo: l’assegnamento delle risorse è consentito solo nel caso in cui il sistema possa garantire che tale assegnamento non porterà a una situazione di stallo;
  • Riconoscimento: il sistema individua situazioni di stallo e cerca di ripristinare uno stato precedente senza stallo;
  • Nessuna azione: il sistema ignora lo stallo e lascia ai programmatori l’onere di evitarlo o gestirlo.

Prevenzione dello stallo

Per prevenire lo stallo di fatto dobbiamo negare una delle condizioni necessarie discusse sopra. Le discutiamo una alla volta

Negare la mutua esclusione

Il fatto che l’accesso a una risorsa sia in mutua esclusione dipende dalla risorsa stessa e dal tipo di accesso, quindi non possiamo evitare la mutua esclusione per prevenire lo stallo, quando essa è necessaria.

Evitare il possesso e attesa

Possiamo evitare possesso e attesa allocando tutte le risorse assieme. Questo non è però sempre possibile perché non è detto che si conoscano tutte le risorse necessarie a un thread o processo a priori. Inoltre allocare tutte le risorse all’inizio può essere inefficiente in quanto priva gli altri thread o processi di tali risorse.

Ci sono casi in cui però questo approccio è possibile. Abbiamo visto ad esempio che nel problema dei filosofi, la raccolta atomica delle bacchette risolve lo stallo e in effetti questo equivale a negare il possesso e attesa (il filosofo che raccoglie la bacchetta sx e poi attende per la dx). I filosofi con la raccolta atomica sono quindi un esempio di prevenzione dello stallo evitando situazioni di possesso e attesa.

Starvation: allocare le risorse tutte assieme può causare starvation in quanto un thread potrebbe attendere indefinitamente la presenza simultanea di tutte le risorse necessarie che vengono, alternativamente, allocate e utilizzate da altri thread. Si pensi ad esempio ai filosofi con raccolta atomica delle bacchette. Se i due filosofi vicini mangiano continuamente un filosofo potrebbe attendere indefinitamente che le proprie bacchette si liberino entrambe.

Preemption

La preemption, come la mutua esclusione, dipende dal tipo di risorsa. Ci sono risorse per loro natura preemptable e altre no. Tipicamente, se la risorsa può salvare completamente il proprio stato e ripristinarlo può essere preemptable come la CPU. Non possiamo quindi imporre preemption quando essa non è possibile per la natura stessa delle risorse.

Prevenire l’attesa circolare: l’allocazione gerarchica

È possibile evitare l’attesa circolare con opportune strategie di allocazione delle risorse. Un esempio interessante è l’allocazione gerarchica: le risorse sono raggruppate in insiemi Ri ordinati tra loro: R1 < R2 < … < Rm. Se un thread chiede istanze di risorse appartenenti a Rj deve prima rilasciare tutte le risorse che possiede appartenenti ad insiemi Ri tali che Rj ≤ Ri. In altre parole il possesso e attesa è ammesso ma solo secondo l’ordinamento (stretto) degli insiemi Ri.

Questa politica di allocazione previene l’attesa circolare. Usiamo la seguente notazione:

R -> P indica che P possiede almeno una risorsa di tipo R
P -> R indica che P sta chiedendo una risorsa di tipo R

Supponiamo per assurdo che ci sia un assegnamento di risorse che crea un attesa circolare. Avremo quindi

R1 -> P-> R2  -> P2 …  Rw -> P -> R1

l’allocazione gerarchica richiede che R1 < R2 < … < R< Rche implica l’assurdo R1 < R1 . Abbiamo quindi dimostrato che l’allocazione gerarchica previene l’attesa circolare e di conseguenza lo stallo.

Cosa accade se un processo viola la politica di allocazione gerarchica? La richiesta di una risorsa che non rispetta la gerarchia (che non è quindi strettamente maggiore delle risorse attualmente possedute dal processo) viene rifiutata e ritorna un apposito codice di errore. Il processo dovrà gestire l’errore.

Esempio: il filosofo mancino

Un esempio di prevenzione dello stallo tramite allocazione gerarchica è la soluzione del filosofo mancino che abbiamo visto nelle lezioni precedenti. Uno dei filosofi raccoglie prima la bacchetta destra e poi quella sinistra, a differenza di tutti gli altri. Se numeriamo le bacchette e i filosofi da 0 a 4 immaginandoci di andare in senso antiorario intorno alla tavola, abbiamo che i filosofi da 0 a 3 raccoglieranno rispettivamente le bacchette 0 e 1, 1 e 2, 2 e 3, 3 e 4. Il filosofo n. 4 è il nostro filosofo mancino. Dovrebbe raccogliere le bacchette 4 e 0 ma (sx e dx) ma invece lo forziamo a raccogliere prima la bacchetta 0 e poi la 4. Possiamo notare come tutti i filosofi raccolgano le bacchette in ordine crescente di indice rispettando quindi una “naturale” allocazione gerarchica 0 < 1 < 2 < 3 < 4. Sappiamo che questo previene l’attesa circolare e quindi lo stallo. In pratica la soluzione del filosofo mancino non è altro che un caso particolare dell’allocazione gerarchica.