::cck::24::/cck::
::introtext::

Un deadlock, o abbraccio mortale, si ha quando uno o più processi non possono proseguire nel loro lavoro perché bloccati in attesa che si verifichi un evento (il rilascio di una risorsa) che può essere generato solo da un altro processo, anch’ esso in attesa per lo stesso motivo. Attenzione però a non confondere la starvation con il deadlock. In entrambi i casi si tratta di una condizione d’attesa di un processo, ma:

::/introtext::
::fulltext::

1. Nella starvation l’attesa è indefinita, nel deadlock l’attesa è infinita. Ciò vuol dire che un processo che subisce starvation, prima o poi, magari dopo 10 anni, magari l’ultimo giorno di attività del sistema, ovvero quando non sono rimasti altri processi sulla macchina tranne il processo in questione riuscirà a completare il suo lavoro uscendo dall’attesa spontaneamente. Un deadlock invece coinvolge un processo, è questi non uscirà mai più da tale situazione, anzi con il passare del tempo sempre più processi del sistema verranno coinvolti, “abbracciandosi”.
2. La starvation dipende dall’attività del sistema, che magari dà la precedenza a certi processi anziché ad altri, ritardandone l’esecuzione, il deadlock invece dipende dall’attività dei processi, che come nel caso dei processi che usano i semafori (visti precedentemente) possono essere progettati male, introducendo delle regioni critiche che causano un deadlock.

Quindi appare già chiaro che un deadlock, per un progettista di sistemi, è una situazione abbastanza spiacevole da gestire, perché dipende da come sono scritti i processi, e non dalla politica del sistema. Ma analizzando le caratteristiche di un deadlock, è possibile sviluppare strategie per prevenire, evitare, ripristinare un deadlock. Prima di analizzare in dettaglio tali caratteristiche è opportuno specificare che un processo entra in deadlock quando ha bisogno di usare una risorsa che non è disponibile, e quindi attende che chi la detiene la rilasci. Ma se chi detiene la risorsa è anch’esso un processo in attesa per lo stesso motivo, resteranno entrambi bloccati per sempre. Come se non bastasse da questo momento in poi tutti i processi che vorranno usare le risorse possedute dai processi abbracciati ( bloccati ) entreranno anche loro in deadlock, portando col tempo le prestazioni del sistema a un livello inaccettabile.

Quindi le risorse sono la chiave di un deadlock. Un processo per ottenere una risorsa effettua questa sequenza di operazioni:

1. La richiede, usando delle apposite system call, al sistema operativo che, se la risorsa è libera, soddisfa immediatamente il processo altrimenti lo fa attendere.
2. La usa, se è un file ci scrive o ci legge, se è una stampane ci stampa.
3. La rilascia, usando delle system call, quando non gli serve più.

Ovviamente il primo processo che entra in deadlock non effettua il punto 3, gli altri non superano il punto 1.

Il deadlock però non è un evento molto frequente, è perché si verifichi occorre che quattro condizioni, che lo caratterizzano, siano rispettate contemporaneamente. Quindi basta negare una sola delle seguenti caratteristiche perprevenire un deadlock.

1. Mutua esclusione. Questa condizione è vera quando almeno una risorsa tra quelle contese dai processi è non condivisibile, ovvero può essere assegnata in un dato istante a un solo processo per volta, quindi chi si blocca su questa risorsa, bloccherà tutti gli altri che in futuro la vogliano usare. Negare la mutua esclusione è difficile, perché alcune risorse non possono essere condivisibili. Una stampante, infatti, se fosse condivisibile stamperebbe un po’ per un processo, un po’ per un altro sullo stesso foglio! (a meno che non si usi una tecnica di spooling).
2. Possesso attesa. Questa condizione esiste se esiste un processo che richiede risorse già possedute da altri processi mentre continua a detenere almeno una risorsa non condivisibile. Per negare questa condizione bisogna garantire che un processo che detiene una risorsa, non possa chiederne altre. Bisogna quindi progettare un protocollo di richiesta risorse che per esempio imponga al processo richiedente di rilasciare tutte le risorse possedute prima di entrare in attesa di una risorsa non disponibile, oppure che dichiari la sequenza delle richieste che effettuerà durante la sua esecuzione, in modo che il sistema l’ analizzerà per vedere se, quando combinate con la sequenza di un altro processo, possono causare un deadlock. Negare questa condizione adottando queste strategie produce uno scarso uso delle risorse, e può causare starvation per quei processi che dichiarano una sequenza di richieste che il sistema considera rischiosa.
3. Impossibilità di prelazione. Questa condizione è vera se le risorse non sono prelazionabili, cioè non possono essere tolte d’autorità ad un processo. Quindi un processo che le detiene le rilascerà spontaneamente quando avrà finito di usarle. Per negare questa condizione, bisogna progettare un protocollo che, invece di prelazionare le risorse ad un processo che sta per entrare in attesa di un’altra risorsa posseduta da un altro processo, congela tutto il processo. Il processo quindi sarà sospeso, e le risorse che aveva gli possono ora essere tolte, e gli verranno restituite solo quando la nuova risorsa che sta attendendo è disponibile. Il processo riprenderà il lavoro dal punto in cui era stato interrotto come se niente fosse accaduto, ma solo se potrà recuperare tutte le risorse che già deteneva. Infatti, se nel frattempo le risorse che aveva prima dell’interruzione sono state allocate ad altri, il processo non potrà riprendere la sua esecuzione per ora (starvation).
4. Attesa circolare. Questa condizione esiste se in un insieme di processi composto da P0 a Pn, il processo Pi è in attesa delle risorsa posseduta dal processo P(i+1)%n. Per negare questa condizione si potrebbe realizzare una funzione che, in base ad un indice numerico assegnato ad ogni risorsa, stabilisce se quella risorsa una volta concessa al processo “Pi” può portare ad un’attesa circolare, perché esiste già un processo (P(i+1)%n)) in attesa sulla stessa risorsa. Nel problema dei filosofi, l’attesa circolare è stata negata garantendo che dei 5 filosofi solo 4 per volta possono sedersi al tavolo.

Grafo di allocazione Risorse

Un sistema costituito da processi che usano o attendono risorse, può essere facilmente rappresentato da una struttura dati come un grafo orientato. Un grafo orientato è costituito da un’insieme di vertici, collegati tra loro da archi. Un arco è orientato se è diretto da un vertice ad un altro, come nella figura:

Un grafo di allocazione risorse è una specializzazione di un grafo orientato, infatti è costituito da due partizioni di vertici. In una partizione si trovano le risorse, rappresentate graficamente da vertici rettangolari, nell’altra partizione, si trovano i processi, rappresentati graficamente da cerchi.

Può esistere un arco orientato da un vertice processo Pi a un vertice risorsa Rj, scrivendo Pi->Rj, per indicare che il processo rappresentato dal vertice P è in attesa di ottenere la risorsa rappresentata dal vertice R, l‘arco in questo caso si chiama arco di richiesta.

Può esistere un arco orientato da Rj a Pi, scrivendo Rj->Pi, in questo caso si legge che la risorsa Rj è usata dal processo Pi, l’arco in questo caso si chiama arco di assegnazione.

In un sistema dinamico, rappresentato da un grafo di allocazione risorse, quando un processo vuole usare una risorsa la richiede, e nel grafo viene inserito un arco di richiesta, che si trasforma immediatamente, se la risorsa è libera, in arco d’assegnazione. Se la risorsa non è libera l’arco di richiesta permane, e indica che il processo, rappresentato dal vertice dal quale parte l’arco, è in attesa, osserva la figura.

Essendo il grafo di allocazione risorse una rappresentazione del sistema, possiamo usarlo per reperire alcune informazioni utili sul sistema, per esempio possiamo determinare se il sistema è in deadlock. Infatti se seguendo gli archi uscenti da un vertice processo, esplorando in profondità il grafo, ritorniamo più di una volta su un vertice, vuol dire che nel grafo esiste un ciclo, e in questo caso nel sistema esiste la condizione di attesa circolare, e quindi esiste un deadlock. Come nella figura seguente.

Esistono degli algoritmi, che partendo da un vertice arbitrario, verificano la presenza di un ciclo in un grafo, e possono essere usati per rilevare un deadlock, e nel caso vi sia, ripristinare la situazione. Per ripristinare la situazione si potrebbe, per esempio, selezionare un processo tra quelli coinvolti nel deadlock (informazione reperibile sempre grazie al grafo) e ucciderlo, riportando però tutti gli altri processi ad uno stato del lavoro, precedentemente salvato. Il problema dei filosofi usa, a titolo dimostrativo, un grafo per verificare il sistema. Questa strategia è un po’ costosa sia in termini di spazio (per la memorizzazione del grafo), sia in termini di tempo (per l’esplorazione periodica dello stesso), e se applicata a sistemi con più istanze per ogni tipo di risorsa, allora la complessità dell’algoritmo di rilevamento cicli, aumenta, perché in questo caso, non basta trovare un ciclo nel grafo per essere certi che nel sistema esiste un deadlock, ma occorre accertarsi che, per ogni risorsa coinvolta,  non vi siano altre istanze allocate a processi bloccati es:

 

Evitare i deadlock

Abbiamo visto come negando una delle condizioni necessarie si possa prevenire un deadlock, e come usando un grafo si possa ripristinare la situazione. Esiste anche una politica che evita il verificarsi di un deadlock.

Tale strategia si basa sul concetto di stato sicuro, associato al concetto di sequenza sicura.

Uno stato sicuro è uno stato in cui non esiste un deadlock, per contro uno stato non sicuro non implica necessariamente la presenza di un deadlock, ma indica che, data la configurazione attuale delle allocazioni a i processi, è possibile che una prossima richiesta di risorse, causi un deadlock. Quando il sistema viene avviato e non ha ancora caricato nessun processo è sicuramente in uno stato sicuro. Per evitare un deadlock occorre far persistere questo stato sicuro anche dopo aver assegnato risorse ad un processo. Per far in modo che il sistema resti sempre in uno stato sicuro, gli algoritmi preposti a tale scopo lavorano sul concetto di sequenza sicura. Una sequenza di richieste è sicura se è possibile allocare tutte le risorse richieste dai processi, senza passare in uno stato non sicuro, dove cioè il S.O. non potrebbe far fronte a future richieste senza mettere in attesa circolare uno o più processi. Più formalmente quindi, una sequenza di processi da P0 a Pn è sicura per lo stato di allocazione attuale se, per ogni Pi, le risorse che Pi può ancora chiedere al sistema, gli possono essere date utilizzando quelle ancora disponibili, più quelle possedute da tutti i processi Pj con j<i. Essendo Pj stato soddisfatto con lo stesso criterio, allora lui potrà finire il suo lavoro senza bloccarsi perché Pj-1 gli potrà dare le risorse che eventualmente gli servono e cosi via fino a P0.

Algoritmo del banchiere

Un sistema che voglia evitare i deadlock, può usare un algoritmo noto come algoritmo del banchiere. Questo algoritmo si divide in due parti.

1. Algoritmo di richiesta delle risorse.
2. Algoritmo di verifica della sicurezza.

Utilizza inoltre alcune strutture dati per stabilire se una generica richiesta di risorse di un certo processo, fatta in un dato istante, possa essere soddisfatta perché non porta il sistema in uno stato non sicuro.

Queste strutture dati sono delle matrici e dei vettori, che codificano la rappresentazione dei processi e delle risorse nel sistema. Esse possono facilmente essere realizzate come classi in un linguaggio O.O. come java, e devono supportare uno stile di programmazione che consenta di confrontarle, di sommarle, di sottrarle e di copiarle tra loro.

Le strutture dati sono:

1. Available. Un vettore di m elementi. Ogni elemento indica il numero di istanze disponibili per quella risorsa. Es.: Available[j]=k significa che sono disponibili k istanze della risorsa Rj.
2. Max. Una matrice n x m, che definisce la richiesta massima di risorse da parte di ciascun processo. Questa dichiarazione di richieste viene fatta da un processo appena viene lanciato.
3. Allocation. Una matrice n x m, che definisce il numero di risorse allocate ad ogni processo.
4. Need. Una matrice n x m che indica la necessità residua di risorse che ogni processo ha per terminare il suo lavoro. Need è ottenuta da Max - Allocation.

Un sistema operativo quindi deve avere un processo preposto all’esecuzione dell’algoritmo del banchiere, sempre in esecuzione. Quando un nuovo processo, o un processo già esistente “Pi” ha bisogno di usare delle risorse, invia una richiesta al S.O. che la passa all’algoritmo del banchiere sotto forma di vettore che chiamiamo Request[i]. L’algoritmo del banchiere ora deve dire al S.O. se questa richiesta porta il sistema in uno stato non sicuro, o lo lascia in stato sicuro. Per dare questa risposta l’algoritmo del banchiere esegue l’algoritmo di richiesta risorse:

void RichiestaRisorse(Vettore Request_i){

/*se le richieste attuali sono superiori alla necessità residua del processo, allora il processo sta imbrogliando, e la sua richiesta non è lecita*/

    if(Request_i>=need_i){

      "La richiesta di Pi non è lecita.";

      return;

    }

/*Se le richieste sono superiori alle risorse disponibili, Pi deve attendere*/

    if(Request_i > available){

      "Pi deve attendere, le ris. non sono disp.";

      return;

    }

/*Altrimenti posso simulare l’allocazione delle risorse a Pi, modificando le matrici, per ottenere un nuovo stato di allocazione…*/

      Available=Available-Request_i;

      Allocation_i=Allocation_i+Request_i;

Need_i=Need_i-Request_i;

/*Se questo stato risulta sicuro, risposta che mi dà l’algoritmo di verifica sicurezza, allora dico al S.O. che Pi può essere eseguito...*/

    if(AlgoritmoVerificaSicurezza()==true){

      " Pi viene eseguito";

    }else{

/*Altrimenti Pi deve attendere e io ripristino la situazione così come era prima */

Available.undo();

      Allocation_i.undo();

Need_i.undo();

    }

  }

Nell’algoritmo di richiesta risorse viene chiamato l’algoritmo di verifica sicurezza, che è il seguente:

boolean AlgoritmoVerificaSicurezza(){

//alloca due vettori come di seguito

finish=new Vettore( di lunghezza n e con tutti gli elementi a false );

work=new Vettore( di lunghezza m è = ad available );

//cerca un i che soddisfi contemporaneamente queste condizioni    

while( esiste un finish[i]==false e Need_i<= Work, (ma ripeti questa ricerca per non più di n volte) ){

//modifica i vettori e vedi se esiste un altro i

          work=work + allocation;

          finish[i]=true;

}

//… adesso cerca nel vettore finish un Pì che non può terminare, se esiste lo stato non è sicuro

for( tutti gli i di finish ){

      if(finish[i]==false){

            "Stato NON sicuro";

            return false;

      }

}

return true;

}

::/fulltext:: ::cck::24::/cck::