Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Domenico Cotroneo » 15.Deadlock


Deadlock

Sommario

  • Deadlock: definizioni e generalità
  • Trattamento del deadlock:
    • Deadlock Prevention
    • Deadlock Avoidance
    • Deadlock Detection

Deadlock

Indica la situazione di un blocco permanente di un insieme di processi in competizione per una o più risorse di sistema.

Non esiste una soluzione generale ed efficiente al problema.

Il deadlock è indice di una conflittualità sulle richieste di risorse tra più processi.

Esempio: attraversamento di un ponte

Sul ponte possono transitare autoveicoli solo in una direzione alla volta.

Ciascuna sezione del ponte può essere vista come una risorsa.

Se si verifica un deadlock, può essere risolto se un’auto torna indietro (rilascia la risorsa).

Può essere necessario che più auto debbano tornare indietro in caso di deadlock.

E’ possibile la starvation (attesa indefinita).


Il problema del deadlock

Esempio

  • Il sistema ha 2 lettori di schede SD.
  • P1 e P2 posseggono un lettore, e ciascuno ha bisogno di quello posseduto dall’altro processo.

Per la sincronizzazione si usano 2 semafori mutex1 e mutex2, inizializzati a 1.

Il problema del deadlock

Codice dei processi

Codice dei processi


Il problema del deadlock

Se si verifica la sequenza di azioni:

  • P1 esegue la wait(mutex1) e acquisisce il lettore 1;
  • P2 esegue la wait(mutex2) e acquisisce il lettore 2;
  • P1 esegue la wait(mutex2) e si blocca;
  • P2 esegue la wait(mutex1) e si blocca;

i due processi rimangono bloccati.

La situazione di deadlock dipende dalla velocità relativa di esecuzione dei processi.

Tipologie di Risorse

Si possono distinguere due categorie di risorse:

  1. risorse riusabili (reusable);
  2. risorse consumabili.

Risorse Riusabili

Di una risorsa ne possono essere presenti più unità (istanze).

Ciascun istanza può essere utilizzata da un solo processo alla volta.

Ciascun processo impiega l’istanza con la seguente sequenza:

  • richiesta;
  • uso;
  • rilascio.

Es. : Processori; canali I/O, dispositivi di memoria, strutture dati, database.

Situazioni di deadlock si possono verficare se ogni processo possiede una risorsa e ne richiede altre.

Un altro esempio di deadlock

Si supponga di avere uno spazio di memoria di 200 Kbytes (risorsa riusabile), se i processi P1 e P2 richiedono memoria nell’ordine seguente:

P1
. . .

Request 80 Kbytes;
. . .
Request 60 Kbytes;

P2
. . .

Request 70 Kbytes;
. . .

Request 80 Kbytes;

… si verifica una situazione di Deadlock

Risorse consumabili

Create (prodotte) e distrutte (consumate).

Disponibili (teoricamente) in numero infinito.

Esempi: interruzioni, segnali, messaggi …

Un deadlock può avvenire se, ad esempio, si utilizza una receive bloccante.

P1
. . .

Receive (P2);
. . .
Send(P2, M1);
P2
. . .

Receive (P1);

. . .
Send(P1, M2);

Grafo di assegnazione delle risorse

Un grafo è un insieme di vertici (o nodi) V e un insieme di archi E.

V è partizionato in due tipi :

  • P = {P1, P2, …, Pn}, è l’insieme costituito da tutti i processi nel sistema.
  • R = {R1, R2, …, Rm}, è l’insieme costituito da tutti i tipi di risorse nel sistema.

Arco di richiesta (arco orientato) P1 → RjArco di assegnazione (arco orientato) Rj → Pi

Grafo di allocazione delle risorse


Grafo di allocazione delle risorse


Osservazioni

Se il grafo non contiene cicli → non si verificano situazioni di stallo.
Se il grafo contiene un ciclo →

  • se c’è solo un’istanza per tipo di risorsa, allora si verifica una situazione di stallo;
  • se vi sono più istanze per tipo di risorsa, allora c’è la possibilità che si verifichi una situazione di stallo.

Deadlock

Problema complesso e di rilievo in quanto può provocare gravi malfunzionamenti (si pensi a sistemi per il controllo di impianti industriali …).

La complessità risiede nel fatto che il blocco dipende dalla velocità relativa dei processi (race condition): un programma potrebbe funzionare per anni prima di evidenziare un problema.

Il problema cresce in complessità con l’introduzione dei thread, i quali possono condividere e competere per le risorse all’interno di un processo.

Malgrado ciò, la maggior parte dei sistemi operativi non offre strumenti per la prevenzione e trattamento dei deadlock.

Caratterizzazione dei deadlock

Un deadlock può avvenire se sono verificate le seguenti condizioni contemporaneamente (Condizioni Necessarie):

  • mutua esclusione: un solo processo alla volta può usare una risorsa;
  • possesso ed attesa: un processo che possiede almeno una risorsa, attende di acquisire ulteriori risorse possedute da altri processi;
  • impossibilità di prelazione: una risorsa può essere rilasciata dal processo che la possiede solo volontariamente, al termine del suo compito.

Attesa circolare

Esiste un insieme {P0, P1, …, Pn} di processi in attesa, tali che P0 è in attesa per una risorsa che è posseduta da P1, P1 è in attesa per una risorsa che è posseduta da P2, …, Pn–1 è in attesa per una risorsa che è posseduta da Pn, e Pn è in attesa per una risorsa che è posseduta da P0.


Più precisamente

Possibilità di un deadlock se sussistono le prime tre condizioni:

  • mutua esclusione;
  • impossibilità di prelazione;
  • possesso ed attesa.

Esistenza del deadlock se sussistono tutte e quattro le condizioni:

  • mutua esclusione;
  • impossibilità di prelazione;
  • possesso ed attesa:
  • attesa circolare.

Metodi per la gestione dei deadlock

Assicurare che il sistema non entri mai in uno stato di deadlock.

Prevenzione dei deadlock (prevention): rimuovere dal sistema ogni possibilità che ci sia un deadlock => basso utilizzo risorse.

Evitare i deadlock (avoidance): sussistono le condizioni perché intervenga un deadlock, ma si evita di entrarci effettivamente.

Rilevazione del deadlock. Permettere al sistema di entrare in uno stato di deadlock, per poi risolvere “il problema” (ripristino il sistema).

  1. Determinare la presenza di un deadlock.
  2. Ripristinare il sistema da un deadlock.

Ignorare il problema e fingere che i deadlock non avvengano mai nel sistema; impiegato dalla maggioranza dei sistemi operativi, incluso UNIX.

Prevenzione dei deadlock

Un sistema progettato in modo da escludere la possibilità di un deadlock.

Due modalità:

  1. indiretta, che mira ad evitare il verificarsi delle prime tre condizioni (mutua esclusione, impossibilità di prelazione, possesso ed attesa);
  2. diretta, che mira ad evitare il verificarsi di attese circolari.

Prevenzione dei deadlock

Mutua Esclusione – non è richiesta per risorse che possono essere condivise; deve essere concessa per risorse che non possono essere condivise.

Possesso e attesa – si deve garantire che quando un processo richiede una risorsa, questo non possieda altre risorse.

Due strategie: permettere ad un processo di richiedere ed avere assegnate tutte le sue risorse prima che inizi l’esecuzione, o consentire ad un processo di richiedere risorse solo quando non ne possiede alcuna.

Si ha un basso impiego delle risorse. E’ possibile che si verifichi l’attesa indefinita di qualche processo.

Prevenzione dei deadlock

Impossibilità di prelazione

  • Se un processo che possiede alcune risorse richiede un’altra risorsa che non gli può essere allocata immediatamente, allora rilascia tutte le risorse possedute.
  • Le risorse rilasciate (prelazionate dal processo stesso) sono aggiunte alla lista delle risorse che il processo sta attendendo.
  • Il processo viene eseguito nuovamente solo quando può ottenere le sue vecchie e nuove risorse.

Attesa circolare – si impone un ordinamento totale di tutti i tipi di risorsa e si pretende che ciascun processo richieda le risorse con un ordine di numerazione crescente.

Deadlock Prevention

Si può dire che la prevenzione del deadlock si fonda sull’implementazione di strategie che vincolano le richieste di risorse.

Svantaggi:

  • utilizzo delle risorse inefficiente;
  • esecuzione dei processi inefficiente.

Deadlock Avoidance

Il sistema decide dinamicamente se una richiesta di una risorsa può portare ad un deadlock (prevenzione dinamica del deadlock).

Tali tecniche richiedono la conoscenza di tutte le richieste che un processo può fare nell’arco di tutta la sua vita.

Il modello più semplice: ogni processo dichiara il numero massimo di risorse di ciascun tipo di cui può avere bisogno.

L’algoritmo di deadlock avoidance esamina dinamicamente lo stato di allocazione delle risorse per assicurare che non ci possa mai essere una condizione di attesa circolare.

Stato di allocazione delle risorse:

  • numero di risorse disponibili ed allocate;
  • massimo numero di richieste dei processi.

Due approcci

Non iniziare un processo se le sue richieste potrebbero portare ad un deadlock (Process Initiation Denial).

Non accettare richieste di una o più risorse ad un processo se queste potrebbero portare ad una situazione di deadlock (Resource Allocation Denial).

Process Initiation Denial

Sia n = numero di processi, e m = numero di tipi di risorse.
Resource= R= (R1,…, Rm)
Risorse totali nel sistema. Ri è il numero di istanze presenti nel sistema della risorsa Ri.

Avalaible=V= (V1,…,Vm)
Numero di istanze per ogni risorsa non allocate ad alcun processo. Vi rappresenta il n.ro di istanze della risorsa Ri non ancora allocata.

Claim= C = matrice n×m
Cij= richiesta del processo Pi per la risorsa Rj.

Allocation=A=matrice n×m
Aij= allocazione corrente al processo Pi della risorsa Rj.

Process Initiation Denial

La matrice C (di necessità) indica il numero massimo di richieste per ciascun processo (righe) di una certa risorsa.

Questa matrice deve essere fornita prima dell’esecuzione del processo.

Si può definire una politica di deadlock avoidance che rifiuti di eseguire un processo, data la sua matrice C (o meglio la sua riga).

Un processo Pn+1 viene eseguito solo se:

R_j\geq C_{(n+1)j}+\sum_{i=1}^nC_{ij}\;\;\;\forall j

..cioé un processo viene eseguito se il numero massimo di richieste di tutti i processi più quelle del nuovo possono essere soddisfatte.

Resource Allocation Denial

Riferito anche come algoritmo del bancherie.

La strategia consiste nell’assicurare che il sistema (processi + risorse) sia sempre in uno stato sicuro.

Stato sicuro

Quando un processo richiede una risorsa disponibile, il sistema deve decidere se l’allocazione immediata porti il sistema in uno stato sicuro.
Il sistema è in uno stato sicuro se esiste una sequenza sicura di esecuzione di tutti i processi.
La sequenza <P1, P2, .. , Pn>  è sicura se per ogni Pi, le risorse che Pi può ancora richiedere possono essere soddisfatte dalle risorse correntemente disponibili + risorse possedute da tutti i Pj, con j<i.

  • Se le risorse richieste da Pi non sono immediatamente disponibili, allora Pi può attendere finché ogni Pj è terminato.
  • Quando Pj ha terminato, Pi può ottenere le risorse richieste, eseguire i suoi compiti, restituire le risorse allocate e terminare.
  • Quando Pi termina, Pi+1 può ottenere le risorse richieste, e così via.

Stato sicuro

Se un sistema è in uno stato sicuro => non si evolve verso il deadlock.

Se un sistema è in uno stato non sicuro => possibilità di un deadlock.

Avoidance => assicura che un sistema non entri mai in uno stato non sicuro.


Strategia

Quando un processo richiede un insieme di risorse,

  • si assume che la richiesta venga accettata;
  • lo stato del sistema viene aggiornato;
  • si determina, applicando l’alg. del bancherie, se il nuovo stato è uno stato sicuro.

In caso affermativo la richiesta viene effettivamente soddisfatta, viceversa no (il processo è sospeso).

Un esempio

Due processi: P1 e P2
Due risorse riusabili: R1 e R2
Il processo P1 richiede

  • al tempo t1 R1 (rilasciata al tempo t3 )
  • al tempo t2 R2 (rilasciata al tempo t4 )

Il processo P2 richiede

  • al tempo t5 R2 (rilasciata al tempo t7 )
  • al tempo t6 R1 (rilasciata al tempo t8 )

Prevenzione dinamica del blocco critico


Come determinare uno stato sicuro

Si consideri lo stato di un sistema di 4 processi e tre risorse.

E’ questo uno stato sicuro?

Per rispondere a questa domanda bisogna capire se ognuno dei quattro processi sia in grado di terminare la propria esecuzione con le risorse disponibili. In altri termini per un processo Pi bisogna verificare che:

C_{ij}-A_{ij}\leq V_j\;\;\;\forall j


Come determinare uno stato sicuro

E’ evidente che la condizione non è verificata per P1 (che possiede un’istanza di R1 e ne richiede altre due).

In ogni caso, se si assegnasse a P2 un’istanza di R3, P2 potrebbe completare l’esecuzione (la condizione è vera per P2).

Quando P2 finisce le sue risorse verrebbero liberate.


Come determinare uno stato sicuro

Lo stato raggiunto è sicuro?

Per analogia al passo precedente, se si assegnassero a P1 le risorse richieste, P1 potrebbe terminare la sua esecuzione liberando le risorse allocate.


Come determinare uno stato sicuro

Lo stato raggiunto è sicuro?

Per analogia al passo precedente, se si assegnassero a P3 le risorse richieste, P3 potrebbe terminare la sua esecuzione liberando le risorse allocate. P4 ora avrebbe tutte le risorse…


Come determinare uno stato sicuro

Possiamo quindi concludere che lo stato  è uno stato SICURO

Possiamo quindi concludere che lo stato è uno stato SICURO


Determinare uno stato NON sicuro

Tutti i processi hanno bisogno di almeno un’unità di R1….quindi la richiesta di R1 non dovrebbe essere accolta

Tutti i processi hanno bisogno di almeno un’unità di R1….quindi la richiesta di R1 non dovrebbe essere accolta


L’algoritmo del bancherie


L’algoritmo del bancherie


Problematiche

La strategia di deadlock avoidance

  • richiede che ogni processo dichiari preventivamente il numero max di risorsa che utilizzerà;
  • i processi che vengono analizzati dall’alg. devono essere indipendenti (non possono essere sincronizzati);
  • ci deve essere un numero predeterminato e costante di risorse da allocare;
  • nessun processo può terminare mentre è in possesso di una risorsa.

Deadlock detection

Non vincola le richieste alle risorse (non c’è alcun controllo).

Periodicamente (oppure ad ogni richiesta, oppure quando il grado di uso della CPU scende sotto certi livelli) il sistema esegue un algoritmo di per il rilevamento dell’attesa circolare.

Nel caso in cui venga trovata una condizione di attesa circolare il sistema applica un algoritmo di ripristino (recovery).

Deadlock detection

Una strategia di detection:

  1. impiega un grafo di attesa;
  2. i nodi sono processi;
  3. Pi -> Pj se Pi è in attesa che Pj rilasci una risorsa che gli occorre;
  4. periodicamente viene richiamato un algoritmo che ricerca un ciclo nel grafo;
  5. un algoritmo per trovare un ciclo in un grafo richiede un numero di operazioni dell’ordine di n2, dove n è il numero di vertici del grafo.

Deadlock detection

Grafo di allocazione delle risorse

Grafo di allocazione delle risorse

Corrispondente grafo di attesa

Corrispondente grafo di attesa


Strategie di ripristino

Si “killano” tutti i processi in uno stato di deadlock.

Si esegue un checkpoint di uno stato precedente al deadlock e si fanno ripartire i processi.

Si fa abortire un processo alla volta fino a quando il deadlock non esiste più.

Si prelazionano le risorse ai processi bloccati fino a quando il deadlock non esiste più.

Criterio di selezione dei processi da abortire o delle risorse da prelazionare

Minor tempo di CPU consumato finora.

Minor numero di linee di output prodotte finora.

Maggior tempo stimato per la terminazione.

Minor numero di risorse allocate finora.

Minore priorità.

I materiali di supporto della lezione

Ancillotti Boari, “Sistemi Operativi”, par 3.7

Stallings, “Operating Systems” 6th ed., par. 6.3

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion