1

Lezione T26DeadlockSistemi Operativi (9 CFU), CdL Informatica, A. A. 2013/2014Dipartimento di Scienze Fisiche, Informatiche e MatematicheUniversità di Modena e Reggio Emiliahttp://weblab.ing.unimo.it/people/andreolini/didattica/sistemi-operativi

2

Quote of the day(Meditate, gente, meditate...)

“When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone.”Decreto approvato dalla legislatura del Kansas

3

INTRODUZIONE

4

Il concetto di risorsa(Fornisce servizi agli utenti, che se la contendono)

Un SO multiprogrammato gestisce un insieme di risorse hardware/software.

Hardware: CPU, memoria, disco, rete.Software: descrittori vari, strutture condivise.

I processi competono per l'assegnazione di un sottoinsieme finito di tali risorse.

5

Classificazione delle risorse(Una risorsa di un certo tipo Una classe con N istanze)→

Dal punto di vista modellistico, si preferisce raggruppare tutte le risorse simili in una classe.Esempio: un calcolatore ha 1GB di RAM.

Non ha senso dire: il calcolatore ha 1G risorse di 1 bytel'una.Ha senso dire: esiste una singola risorsa (la memoriacentrale) con 1G istanze disponibili.

Tipicamente, un processo non è interessato ad una specifica istanza della risorsa.

Va bene una qualunque delle istanze disponibili.

6

Proprietà delle risorse(Influenzano i meccanismi di prenotazione e rilascio)

Il comportamento delle risorse è caratterizzato caratterizzato da alcune proprietà.

Risorsa riutilizzabile vs. non riutilizzabile.Risorsa con assegnazione statica vs. dinamica.Risorsa con accesso seriale vs. concorrente.Risorsa prerilasciabile vs. non prerilasciabile.

7

Risorse riutilizzabili e non riutilizzabili(Riutilizzabili Sono allocabili e rilasciabili a più utenti)→

Alcune risorse sono riutilizzabili.Non sono distrutte dopo il loro utilizzo.Il SO determina la loro assegnazione ai processi.Esempi: CPU, canali I/O, memoria centrale.

Altre risorse sono non riutilizzabili.Sono distrutte dopo il loro utilizzo.Possono essere assegnate da processo a processo.Esempi: interruzioni, segnali, messaggi.

8

Risorse assegnate staticamente e dinamicamente(Assegnazione dinamica Maggiormente soggetta all'accesso concorrente)→

Alcune risorse sono assegnate staticamente.Al momento della creazione di un processo.L'assegnazione rimane valida fino alla terminazionedel processo.Esempi: descrittori di processo.

Alcune risorse sono assegnate dinamicamente.Dal processo durante la sua esecuzione.Sono rilasciate dopo l'uso.Esempi: periferiche I/O.

9

Risorse con accesso seriale e concorrente(Accesso concorrente Va protetto con i lock)→

Alcune risorse sono accessibili serialmente.Solo da un processo alla volta (mutua esclusione).Esempi: CPU, sezioni critiche.

Alcune risorse sono accessibili concorrentemente.

Da più processi simultaneamente.Esempi: file in sola lettura.

10

Risorse prerilasciabili e non prerilasciabili(Risorse non prerilasciabili Rischio di deadlock)→

Alcune risorse sono prerilasciabili.Il SO le può “sottrarre” ad un processo prima chequest'ultimo le abbia rilasciate.Il processo che subisce il prerilascio si sospende.La risorsa prerilasciata sarà restituita successivamenteal processo.Esempi: CPU, pagine di memoria (swap).

Altre risorse non sono prerilasciabili.Il SO non le può sottrarle in anticipo al processo.

11

Modello di accesso e rilascio(Quello classico: lock, uso, unlock)

Su richiesta di un processo, viene assegnata una qualunque istanza della risorsa.Scenario di uso della risorsa.

Richiesta: se non è disponibile una istanza dellarisorsa, il processo “attende” fino a che non se ne liberialmeno una.Uso: il processo opera sulla risorsa.Rilascio: il processo rilascia la risorsa, qualora essa siariutilizzabile.

12

Tipologie delle richieste(Singola, multipla, bloccante, non bloccante)

Richiesta singola: richiesta di un'unica istanza di un'unica classe di risorsa.

Caso standard.Richiesta multipla: richiesta di più istanze di più classi di risorse.

Deve essere soddisfatta integralmente.Richiesta bloccante: il processo richiedente si sospende se non ottiene immediatamente l'assegnazione.Richiesta non bloccante: si notifica al processo richiedente la mancata assegnazione della risorsa, senza provocarne la sospensione.

13

Definizione di deadlock(Semplice e chiara)

Un insieme di processi è in deadlock (morsa letale) se si verificano le seguenti condizioni.

Ciascun processo è in attesa di un evento ben preciso.L'unico processo in grado di scatenare l'evento fa partedell'insieme.Qui, l'evento è il rilascio di una risorsa posseduta da unodei processi nell'insieme.Nessuno dei processi è in grado di eseguire, rilasciarerisorse, risvegliarsi.

→ STALLO.

14

Esempio di stallo(Eloquente)

Nessun autobus può completare l’attraversamento.Ciascun autobus attende che un altro attraversi e liberi l’incrocio.Tutti gli autobus sono in attesa di un evento che non può mai verificarsi.

15

Condizioni necessarie di Coffmann(Meno chiare)

Condizioni necessarie per la presenza di deadlock (1971).

Mutua esclusione: almeno una delle risorse deveessere di tipo seriale.Possesso e attesa: le richieste sono di tipo bloccante,e un processo che ha già ottenuto risorse puòchiederne ancora.Impossibilità di prerilascio: le risorse coinvolte nonsono prerilasciabili.

16

Condizioni necessarie di Coffmann(Meno chiare)

Condizioni necessarie per la presenza di deadlock (1971).

Attesa circolare: esiste un insieme di processiP0, P1,...,Pn} in cui

P0 attende una risorsa posseduta da P1.P1 attende una risorsa posseduta da P2.…Pn attende una risorsa posseduta da P0.

17

Grafo di allocazione di Holt(Modella le prenotazioni e le acquisizioni di risorse)

Grafo orientato e bipartito modellante le relazioni fra processi e risorse.

Grafo orientato: gli archi hanno una direzione.Grafo bipartito: i nodi sono suddivisi in duesottoinsiemi, e non esistono archi colleganti nodidello stesso sottoinsieme.

I due sottoinsiemi sono risorse e processi. Gli archi sono di due tipologie.

Risorsa processo: la risorsa è associata al processo.→Processo risorsa: il processo ha richiesto la risorsa.→

18

Grafo di allocazione di Holt(Modella le prenotazioni e le acquisizioni di risorse)

Formalmente:Set vertici V = P U R.P={P0, P1,...,Pn} (processi).R={R0, R1,...,Rk} (classi di risorse).

Set archi E.Arco di richiesta: Pi→Rj se un processo Pi ha richiestoun'istanza di risorsa Rj.Arco di assegnazione: Rj→Pi se un'istanza di risorsa Rjè stata assegnata al processo Pi.

19

Grafo di allocazione di Holt(Rappresentazione grafica di processi, risorse, richieste, assegnazioni)

Risorsariutilizzabile

Risorsa nonriutilizzabile

Istanza di unadata risorsa

Risorsaassegnata

Richiestapendente

P Processo

Risorsa chepuò esserecreata da

R R

20

Grafo di allocazione di Holt(Grafi di esempio)

P1 P2

R1

R2

R3

R3 distruttaP2 ottiene R1

P1 P2

R1

R2

R3

Evoluzione per stati successiviStato j Stato j+1

21

Strategie di gestione del deadlock(Ostrich algorithm, deadlock detection and recovery)

Ostrich algorithm.Si ignora del tutto il problema.

Deadlock detection and recovery.Si fa evolvere il sistema per stati successivi che

possono condurre al deadlock.Si rileva il deadlock e lo si rimuove.

22

Strategie di gestione del deadlock(Deadlock avoidance, deadlock prevention)

Deadlock avoidance.Si impedisce al sistema di evolvere verso unacondizione di deadlock.Il deadlock non può mai presentarsi.

Deadlock prevention.Si invalida almeno una delle quattro condizioninecessarie.

23

IGNORARE IL DEADLOCK

24

Ostrich algorithm(Ignorare il problema, nella speranza che non si presenti)

Assicurare l'assenza di deadlock impone costi molto alti in termini di prestazioni e funzionalità. Tali costi sono necessari in alcuni contesti, ma insopportabili in altri.Si considera il rapporto costi/benefici: se la probabilità di ottenere un deadlock è bassa, il costo associato non si giustifica.Approccio adottato dalla maggioranza dei SO (UNIX, Windows): ignorare il problema.L'utente preferisce qualche stallo occasionale (da risolvere “a mano”), piuttosto che restrizioni eccessive.

25

RILEVARE IL DEADLOCK

26

Deadlock detection(Rilevare il deadlock)

Si mantiene costantemente aggiornato il grafo di allocazione risorse.

Si registrano le richieste di risorse da parte deiprocessi.Si registrano le assegnazioni di processi a risorse.

Si usa un algoritmo di riconoscimento di deadlock sul grafo di allocazione risorse ogniqualvolta esso cambia.Problema: come si riconosce uno stato di deadlock?

27

Riconoscimento con una sola istanza(Ipotesi di Coffman più singola istanza Deadlock Ciclo nel grafo di Holt)→ ↔

Nel caso più semplice, ciascuna classe di risorse ha una sola istanza.Teorema: se le risorse sono accedute in mutua esclusione con richieste bloccanti, sono seriali (singola istanza) e non sono prerilasciabili, allora uno stato è di deadlock se e solo se il grafo di allocazione contiene un ciclo.

28

Riconoscimento con una sola istanza(Ipotesi di Coffman più singola istanza Deadlock Ciclo nel grafo di Holt)→ ↔

Quindi, nel caso di una sola istanza per classe di risorsa, al SO basta mantenere aggiornato il grafo di allocazione e controllare, periodicamente, la presenza di cicli in tale grafo.Strategia naive: ricerca depth first con marcatura dei nodi.Se si incontra un nodo già marcato, c'è un ciclo.Nel caso di classi di risorse con singola istanza, le condizioni di Coffman da necessarie diventano necessarie e sufficienti.

29

Riconoscimento con più istanze(Non vale più il teorema)

La presenza di un ciclo nel grafo di allocazione non è più condizione sufficiente per la presenza di un deadlock.

P1 P2 P3

R1

R2

CicloDeadlock

Non c'è modo per cuiR1 possa liberare unaistanza da dare a P1(sbloccando, di fatto,il deadlock).

P1 P2 P3

R1

R2

CicloNO Deadlock

Quando P3 finisce diusare R1, la si assegnaa P1, rompendo difatto il ciclo.

30

Riconoscimento con più istanze(Il concetto di riducibilità permette di stabilire se l'intreccio si scioglie o no)

Un grafo di allocazione è detto riducibile se esiste almeno un nodo processo con soli archi entranti.Significato: il processo ha terminato di richiedere risorse, e le sta solo possedendo.Il processo di riduzione consiste nell'eliminare tutti gli archi di un siffatto nodo, riassegnando le istanze liberate ad altri processi.Un grafo di allocazione è completamente riducibile se esiste una sequenza di riduzioni tale da eliminare tutti gli archi del grafo.

31

Motivazioni(Del concetto di riducibilità)

Un nodo con soli archi entranti rappresenta un processo che ha ottenuto tutte le istanze di risorse che voleva.Tale processo, prima o dopo, rilascerà le istanze prenotate.Tale processo non può, per definizione, essere responsabile di un deadlock (non fa parte di un ciclo).Togliendo gli archi al processo, si simula la situazione immediatamente successiva al rilascio.Si vuole capire se le istanze rilasciate sono sufficienti a rimuovere un eventuale deadlock.

32

Riconoscimento con più istanze(Esempio della riduzione)

Riduzione

P1 P2

R1

R2

Nodo processo con soli archi entranti; si rimuovono gli archi.

Riduzione

P1 P2

R1

R2

33

Riconoscimento più istanze(Ipotesi di Coffman più multiple istanze Deadlock Incompleta riducibilità)→ ↔

Teorema: se le risorse sono accedute in mutua esclusione con richieste bloccanti, sono seriali (multipla istanza) e non sono prerilasciabili, allora uno stato non è di deadlock se e solo se il grafo di allocazione è completamente riducibile.

34

Riconoscimento più istanze(Ipotesi di Coffman più multiple istanze Deadlock Incompleta riducibilità)→ ↔

Quindi, nel caso in cui ho più istanze per classe di risorsa, il SO:

mantiene aggiornato il grafo di allocazione.calcola le riduzioni.scopre se il grafo è completamente riducibile.deduce la non presenza di un deadlock.

35

Esempio(C'è deadlock?)

R1 R2

R3

P1 P3

P2

P4

36

Esempio(C'è deadlock?)

R1 R2

R3

P1 P3

P2

P4

Si riduce P1. Siassegna l'istanzadi risorsa liberataa P2.

37

Esempio(C'è deadlock?)

R1 R2

R3

P1 P3

P2

P4

Si riduce P2. Siassegnano le istanzedi risorse liberatea P3 e P4.

38

Esempio(C'è deadlock?)

R1 R2

R3

P1 P3

P2

P4

Si riduce P3.

39

Esempio(C'è deadlock?)

R1 R2

R3

P1 P3

P2

P4

Si riduce P4. Il grafoè completamenteriducibile non c'è→il deadlock.

40

Riconoscimento con richieste singole(Il concetto di annodamento permette di stabilire se l'intreccio si scioglie o no)

L'ultimo caso degno di menzione è quello in cui un processo non può mai richiedere più di una risorsa alla volta. In tal caso, si usa la nozione di knot (annodamento) di un grafo.Dato un nodo n di un grafo orientato, l'insieme dei nodi raggiungibili da n viene detto insieme di raggiungibilità R(n).Un knot del grafo è il massimo sottoinsieme non banale di nodi M tale che, nM, R(n)=M.Partendo da un qualunque nodo di M, si possono raggiungere tutti i nodi di M e nessun altro all'infuori di esso.

41

Riconoscimento con richieste singole(Esempio di grafo con e senza knot)

a

b c

d

a

b c

d

{a, c, d} non èun nodo

{b, c, d} èun nodo

42

Riconoscimento con richieste singole(Ipotesi di Coffman più multiple istanze Deadlock Esiste un knot nel grafo→ ↔ )

Teorema: se le risorse sono accedute in mutua esclusione con richieste bloccanti e singole, sono seriali e non sono prerilasciabili, allora uno stato è di deadlock se e solo se esiste un knot nel grafo di allocazione.

43

Riconoscimento con richieste singole(Ipotesi di Coffman più multiple istanze Deadlock Esiste un knot nel grafo→ ↔ )

In definitiva, se le richieste sono sempre singole, il SO deve:

mantenere aggiornato il grafo di allocazione.controllare periodicamente la presenza di un knot.decidere della presenza di un deadlock.

44

Uso degli algoritmi di detection(Quando si usano?)

Ad ogni richiesta di risorsa da parte di un processo.

Capacità di determinare la richiesta e, dunque, ilprocesso, che causa il deadlock.Costo molto elevato.Capacità di intervento tempestivo (non degradaeccessivamente l'utilizzo delle risorse).

45

Uso degli algoritmi di detection(Quando si usano?)

Su base periodica.Incapacità di determinare la richiesta e, dunque, ilprocesso, che causa il deadlock.Costo ridotto.Ridotta capacità di intervento tempestivo (maggioredegradazione dell'utilizzo delle risorse).

46

Deadlock recovery(Quando si applica?)

Terminazione del processo.Approccio non incrementale: si terminano tutti iprocessi coinvolti nel deadlock.Approccio incrementale: si terminano i processicoinvolti nel deadlock uno alla volta, fino allarisoluzione del deadlock.

Criteri di scelta: priorità, tempo di calcolo, tipo dirisorse occupate (per alcune il rilascio potrebbeessere più semplice di altre).

47

Deadlock recovery(Quando si applica?)

Prelazione.Deassegnazione di risorse ad un processo coinvoltonel deadlock.Occorre selezionare un processo vittima e cercare diimpedire il fenomeno di starvation fra processi.

Checkpoint/Rollback.Lo stato dei processi viene periodicamente salvato sudisco (checkpoint).In caso di deadlock, si ripristina (rollback) uno o piùprocessi ad uno stato precedente, fino a quando ildeadlock non scompare.

48

Deadlock recovery: considerazioni(Non è sempre così semplice ripristinare il sistema dopo un deadlock)

Terminare processi può essere costoso.Tali processi possono essere stati eseguiti per moltotempo (long-lived).Se terminati, dovranno ripartire da capo.

Terminare processi può lasciare le risorse in uno stato inconsistente.

Se un processo viene terminato nel bel mezzo di unasezione critica.

Operare una prelazione:non sempre è possibile.può richiedere interventi manuali (ad esempio: unastampante).

49

PREVENIRE IL DEADLOCK

50

Deadlock prevention(Prevenzione del deadlock; si annulla almeno una condizione di Coffman)

Se sono verificate tutte le condizioni necessarie, c'è rischio di deadlock.Se si invalida almeno una condizione necessaria, il deadlock non può verificarsi.

51

Rimozione della mutua esclusione(Non sempre fattibile)

Si permette la condivisione delle risorse. Ad esempio: spool di stampa.

Tutti i processi credono di usare la stampantecontemporaneamente.

Problemi.Lo spooling non è sempre applicabile (ad esempio, non lo ai descrittori di processo).Si sposta il problema verso altre risorse (ad esempio, ildisco nel caso di spool di stampa).Cosa succede se due processi che vogliono stampare duedocumenti esauriscono lo spazio su disco?

52

Rimozione di possesso e attesa(Si riduce l'efficienza del programma)

Si deve garantire che, quando un processo richiede una risorsa, non ne possieda già altre.

Un processo richiede tutte le risorse che gli servonoall'inizio della computazione.

Non sempre l'insieme delle richieste è noto findall'inizio.Si riduce il parallelismo.

Un processo richiede una risorsa solo se non nepossiede nessuna.

Bassa utilizzazione delle risorse.Starvation.

53

Rimozione dell'impossibilità di prelazione(Non sempre è applicabile)

Se il processo possiede risorse e ne richiede un'altra, gli si fanno rilasciare tutte le risorse.

Il processo attenderà anche le risorse che possedevaprima del rilascio.

Quando un processo richiede risorse, si verifica la loro disponibilità.

Se sono disponibili, vengono assegnate.Se non sono disponibili, si verifica se sono assegnate adun processo che attende altre risorse.

Se il processo attende altre risorse, gli si sottraggonoquelle richieste.

Questo protocollo non sempre è applicabile (ad es.,stampanti, nastri).

54

Rimozione dell'attesa circolare(Si riduce l'efficienza del programma)

Si impongono:un ordinamento totale all'insieme di tutti i tipi di risorse.un ordinamento crescente di numerazione alle risorserichieste da ciascun processo.

Ogni processo può richiedere risorse solo in ordine crescente di numerazione.

Pn non può più attendere P0.Altamente inefficiente.

55

AGGIRARE IL DEADLOCK

56

Deadlock avoidance(Si impedisce che il sistema arrivi ad uno stato di deadlock)

Prima di assegnare una risorsa ad un processo, si controlla se l'operazione può portare al pericolo di deadlock.In tal caso, l'operazione viene ritardata.I processi dichiarano l'ordine di prenotazione delle risorse.

57

A cosa serve la deadlock avoidance(E cosa deve fare il SO per implementarla)

Conoscendo la sequenza completa di richieste e rilascio, si sa per ogni processo se esso deve attendere oppure no.Per stabilire se una richiesta possa essere soddisfatta o si debba attendere per evitare un deadlock, il SO deve:

esaminare le risorse attualmente disponibili.esaminare le risorse attualmente assegnate ad ogniprocesso.esaminare le richieste ed i rilasci futuri di ciascunprocesso.

58

Stato sicuro e sequenza sicura(Sicuro non può progredire verso un deadlock)→

Stato sicuro: uno stato del sistema si dice sicuro se si possono assegnare risorse a ciascun processo in un qualunque ordine, senza il verificarsi di un deadlock.Sequenza sicura: una sequenza di processi (P1, P2, ..., Pn) è detta sicura se, per ogni Pi, le risorse di cui Pi necessita sono libere oppure in possesso di processi Pj, j<i.

59

Deadlock avoidance e stati sicuri(Stato sicuro nessun rischio di deadlock; Stato non sicuro potrebbe esserci)→ →

Uno stato non sicuro non è uno stato di deadlock.Uno stato di deadlock è uno stato non sicuro.Dunque: uno stato non sicuro può condurre ad uno stallo.

Tipicamente, attraverso una sfortunata serie diprenotazioni.

60

Algoritmi di deadlock avoidance(Partono da uno stato sicuro e mantengono il sistema in stati sicuri)

Il sistema è in uno stato sicuro se esiste almeno una sequenza sicura.Algoritmi per evitare deadlock:

partono da uno stato sicuro.mantengono il sistema in stati sicuri, applicando dellescelte ad ogni richiesta di risorsa.

61

Suddivisione degli stati(Sicuri, non sicuri, deadlock)

Diagramma di Venn dei possibili stati del sistema.

Stati sicuri

Stati non sicuri

Stati dideadlock

62

Grafo di allocazione con archi di reclamo(Modellano le future allocazioni Dicono se uno stato è sicuro o no)→

Algoritmo con grafo di allocazione.Si utilizza un nuovo tipo di arco nel grafo di allocazione delle risorse.Arco di reclamo Pi R→ j: Pi può richiedere Rj in un qualsiasi istante futuro.

Quando Pi richiede Rj, l'arco di reclamo diventa un arco dirichiesta.Quando Pi ottiene Rj, l'arco di richiesta diventa un arco diassegnazione.Quando Pi rilascia Rj, l'arco di assegnazione diventa unarco di reclamo.

63

Alcune osservazioni(Sul costo computazionale)

Gli archi di reclamo devono essere inseriti all'attivazione del processo (necessità di conoscere le risorse di cui il processo può far richiesta).Per verificare la possibilità di trasformare gli archi di reclamo in archi di richiesta, è necessario visitare il grafo di allocazione per ogni richiesta di risorsa.Costo: O(n2) nel numero di processi.

64

Grafo di allocazione con archi di reclamo(Uno schema aggiornato)

Risorsariutilizzabile

Risorsa nonriutilizzabile

Istanza di unadata risorsa

Risorsaassegnata

Richiestapendente

P Processo

Risorsa chepuò esserecreata da

R R

Arco di reclamo

65

Grafo di allocazione con archi di reclamo(Un esempio)

P1 P2

R1

R2

Sia P1 che P2 intendono,durante la loro esecuzione,utilizzare R2.

66

Deadlock avoidance(Ipotesi di Coffman più arco di reclamo Deadlock Ciclo nel grafo→ ↔ )

Teorema: nell'ipotesi che Pi R→ j, se le risorse sono accedute in mutua esclusione con richieste bloccanti, sono seriali e non sono prerilasciabili:

il sistema è in uno stato sicuro se e solo se la conversionedell'arco di richiesta Pi R→ j in un arco di assegnazioneRj P→ i non introduce un ciclo nel grafo di allocazionedelle risorse con archi di reclamo.Altrimenti, il sistema è in uno stato non sicuro.