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

Antonino Mazzeo » 19.Il Deadlock


Sommario

  • Introduzione al Deadlock
  • Caratterizzazione dei Deadlock
  • Metodi per la gestione dei Deadlock

Il Deadlock

  • Indica la situazione di un blocco permanente di un insieme di processi in competizione per una o più risorse di sistema
  • Problema complesso e di rilievo in quanto può provocare gravi malfunzionamenti
  • 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
  • Malgrado ciò, la maggior parte dei sistemi operativi non offre strumenti per la prevenzione e il trattamento dei deadlock
  • Non esiste una soluzione generale ed efficiente al problema

Tipologie di Risorse

  • Risorse Riusabili (reusable)
    • 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
    • Situazioni di Deadlock si possono verificare se ogni processo possiede una risorsa e richiede altre
  • Risorse Consumabili
    • Create e distrutte; disponibili (teoricamente) in numero infinito
    • Esempi: interruzioni, segnali, messaggi …
    • Un Deadlock può avvenire se, ad esempio, si utilizza una receive bloccante

Grafo di assegnazione delle risorse

  • Un grafo (V,E) in cui 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 (orientato) di richiesta P1 Rj
    • Arco (orientato) di assegnazione Rj Pi
  • 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 è possibile che si verifichi una situazione di stallo.
Grafo di assegnazione delle risorse

Grafo di assegnazione delle risorse


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.
    • 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…c’è possibilità di un Deadlock se sussistono le prime tre condizioni, esistenza del Deadlock se sussistono tutte

Metodi per la gestione dei Deadlock: Deadlock Prevention

  • Rimuovere dal sistema ogni possibilità che ci sia un Deadlock
  • Due modalità
    • Indiretta, che mira ad evitare il verificarsi delle prime tre condizioni
    • Diretta, che mira ad evitare il verificarsi di attese circolari
      • 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.
  • 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

Metodi per la gestione dei Deadlock: Deadlock Avoidance

  • Il sistema decide dinamicamente se una richiesta di una risorsa può portare ad un Deadlock (prevenzione dinamica del Deadlock)
  • 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 opportuni algoritmi (es l’alg. del bancherie) se il nuovo stato è uno stato sicuro: in caso affermativo la richiesta viene soddisfatta, viceversa no
  • 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
    • Deve esserci un numero predeterminato e costante di risorse da allocare
    • Nessun processo può terminare mentre è in possesso di una risorsa

Metodi per la gestione dei Deadlock: Deadlock Detection

  • Non vincola le richieste alle risorse
    • Periodicamente il sistema esegue un algoritmo per il rilevamento dell’attesa circolare
    • Nel caso in cui venga trovata una condizione di attesa circolare il sistema applica un algoritmo di ripristino
  • Una strategia di detection:
    • Impiega un grafo di attesa in cui i nodi sono processi e un arco Pi -> Pj indica che Pi è in attesa che Pj rilasci una risorsa
    • Periodicamente viene richiamato un algoritmo che ricerca un ciclo nel grafo.
  • Sono possibili diverse strategie di ripristino
Grafo di allocazione delle risorse

Grafo di allocazione delle risorse


Prossima lezione

Dai Processi ai Thread

I materiali di supporto della lezione

P. Ancilotti, M.Boari, A. Ciampolini, G. Lipari, “Sistemi Operativi”, Mc-Graw-Hill (Cap. 3 par 3.7)

Deadlock

  • 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