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
 
 
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