1

Lezione 13DeadlockSistemi Operativi (9 CFU), CdL Informatica, A. A. 2014/2015Dipartimento 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 Kansasnell'anno 1860.B. A. Botkin, A. F. Harlow,"A Treasury of Railroad Folklore"(pp. 381)

3

PROBLEMI LEGATI AI SEMAFORI

4

Problema: piazzamento wait()/signal()(Il programmatore ne è direttamente responsabile)

Il programmatore è personalmente responsabile del piazzamento opportuno di wait() e signal().Se la sequenza wait(), sezione critica, signal() non è rispettata, ne succedono di tutti i colori.

Accesso non in mutua esclusione.Stallo dei task.

5

Errore: accesso multiplo(Si viola la mutua esclusione)

T0 T2

Errore tipico che porta all'accesso multiplo:si invertono signal() e wait().

T1

6

Errore: accesso multiplo(Si viola la mutua esclusione)

wait(S);<sez. cr.>

T0 acquisisce il semaforo S ed accedealla risorsa in mutua esclusione.

T0 T2T1

7

Errore: accesso multiplo(Si viola la mutua esclusione)

wait(S);<sez. cr.>

signal(S);<sez. cr.>

T1 rilascia il semaforo S invece di acquisirlo.Di conseguenza, entra in sezione critica.

T0 T2T1

8

Errore: accesso multiplo(Si viola la mutua esclusione)

wait(S);<sez. cr.>

signal(S);<sez. cr.>

wait(S);<sez. cr.>

La signal() di T1 potrebbe risvegliare unprocesso T2 precedentemente in attesa della

stessa risorsa.

T0 T2T1T0 T2T1

9

Errore: accesso multiplo(Si viola la mutua esclusione)

wait(S);<sez. cr.>

signal(S);<sez. cr.>

wait(S);<sez. cr.>

Risultato: ben tre task sono riusciti adentrare in sezione critica!

T0 T2T1T0 T2T1

10

“But wait! There's more”(As Capt. James Tiberius Kirk AKA William Shatner would say)

11

Errore: stallo(I processi si bloccano inesorabilmente fra di loro)

A seguito di un errore di uso, può capitare che:un insieme di processi attenda il verificarsi di unevento.l'evento in questione può essere causato solo da unodei processi in attesa.

Tale situazione prende il nome di stallo (deadlock).

12

Errore: stallo(Deadlock di tipo “doppio lock”)

T0 T1

Errore tipico che porta allo stallo:si sostituisce una signal() con una wait().

13

Errore: stallo(Deadlock doppio lock)

wait(S);<sez.cr.>

T0 acquisisce il semaforo S ed accedealla risorsa in mutua esclusione.

T0 T1

14

Errore: stallo(Deadlock doppio lock)

wait(S);wait(S);<sez.cr.>

T1 prova ad acquisire il semaforo Se si blocca.

T0 T1

15

Errore: stallo(Deadlock doppio lock)

wait(S);wait(S);<sez.cr.>wait(S);

T0 invoca wait(S) al posto di signal(S).

T0 T1

16

Errore: stallo(Deadlock doppio lock)

wait(S);wait(S);<sez.cr.>wait(S);

Risultato: T0 e T1 aspettano lo sblocco,in eterno. DEADLOCK.→

T0 T1

17

Un esempio concreto(Il sorgente deadlock_doppio_lock_mutex.c)

Il sorgente deadlock_doppio_lock_mutex.c in 13-esempi.tar.bz2 illustra il deadlock di tipo “doppio lock”.Si compili e si esegua il programma.

./deadlock_doppio_lock_mutexOsservate il blocco.

18

He knows about deadlocks(Satoru Sayama AKA “Tiger Mask”)

19

Esercizi (2 min.)

1. Con riferimento all'eseguibile:./deadlock_doppio_lock_mutexsi verifichi che il thread è in attesa.

21

Errore: stallo(Deadlock ABBA)

Errore tipico che porta allo stallo:non viene preservato l'ordine

di richiesta/rilascio delle sezioni critiche.

T0 T1

22

Errore: stallo(Deadlock ABBA)

wait(S);

T0 prenota due semafori S e Q nell'ordine S, Q.

T0 T1

23

Errore: stallo(Deadlock ABBA)

wait(S); wait(Q);

T1 prenota due semafori S e Q nell'ordine Q, S.

T0 T1

24

Errore: stallo(Deadlock ABBA)

wait(S); wait(Q);wait(Q);

T0 si blocca perché T1 ha già preso il lock su Q.

T0 T1

25

Errore: stallo(Deadlock ABBA)

wait(S); wait(Q);wait(Q); wait(S);

T1 si blocca perché T0 ha già preso il lock su S.

T0 T1

26

Errore: stallo(Deadlock ABBA)

wait(S); wait(Q);wait(Q); wait(S);

Chi può sbloccare T0? Solo T1.Chi può sbloccare T1? Solo T0.

→ DEADLOCK.

∞

T0 T1

27

Un esempio concreto(Il sorgente deadlock_abba_mutex.c)

Il sorgente deadlock_abba_mutex.c in13-esempi.tar.bz2 illustra il deadlock di tipo “ABBA”.Si compili e si esegua il programma.

./deadlock_abba_mutexOsservate il blocco.

28

Warning: it's “A-BI-BI-A”, not “ABBA”!(Please, please, please, guys!)

This is “ABBA” This is “A-BI-BI-A”wait(S);

T0 T1wait(S); wait(Q);wait(Q); wait(S);

29

Esercizi (2 min.)

2. Con riferimento all'eseguibile:./deadlock_abba_mutexsi verifichi che i thread siano in attesa.

31

Che fare?(Occorre capire, modellare, riparare/rilevare/inibire/aggirare il deadlock)

Bella domanda!Occorre innanzitutto capire sotto quali condizioni si verifica un deadlock.Possibilmente, occorre anche saper modellare tali condizioni matematicamente, in modo tale da poterle rilevare tramite opportuni algoritmi.Occorre capire come rimuovere un deadlock una volta subito.

32

CARATTERIZZAZIONEDEL DEADLOCK

33

Il concetto di risorsa(Entità hardware/software contesa tra e usata dagli utenti)

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

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

I task (processi, thread) competono per l'assegnazione di un sottoinsieme finito di tali risorse.Tipicamente:

numero risorse < numero di task.

34

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 task non è interessato ad una specifica istanza della risorsa.

Va bene una qualunque delle istanze disponibili.

35

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.

36

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.

37

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

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

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

38

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 in maniera concorrente.

Ossia, da più processi simultaneamente.Esempi: file in sola lettura.

39

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 task che subisce il prerilascio si sospende.La risorsa prerilasciata sarà restituita successivamenteal task.Esempi: CPU, pagine di memoria (swap).

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

40

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 task “attende” fino a che non se ne liberialmeno una.Uso: il task opera sulla risorsa.Rilascio: il task rilascia la risorsa, qualora essa siariutilizzabile.

41

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 task richiedente si sospende se non ottiene immediatamente l'assegnazione.Richiesta non bloccante: si notifica al task richiedente la mancata assegnazione della risorsa, senza provocarne la sospensione.

42

Definizione di deadlock(Semplice e chiara)

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

Ciascun task è in attesa di un evento ben preciso. Qui,l'evento è il rilascio di una risorsa posseduta da unodei task nell'insieme.L'unico task in grado di scatenare l'evento fa partedell'insieme.

→ Nessuno dei task è in grado di eseguire, rilasciarerisorse, risvegliarsi.

43

Un'immagine (vale più di 1k parole)

44

Condizioni necessarie di Coffmann(http://www.ccs.neu.edu/home/pjd/cs7600-s10/Tuesday_January_26_01/p67-coffman.pdf)

Sono quattro condizioni necessarie per la presenza di deadlock.Sono state formalizzate da Ed Coffman nel 1971.

Edward Grant Coffman Jr.(1934-)

45

Condizioni necessarie e/o sufficienti(Repetita iuvant!)

Le condizioni di Coffman sono NECESSARIE.C'è un deadlock Ci sono le quattro condizioni.→

Le condizioni di Coffman non sono, in generale, SUFFICIENTI.

Ci sono le quattro condizioni Non è detto che ci sia→deadlock!

46

Le quattro condizioni(In questa slide, le prime tre)

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 non sono prerilasciabili.

47

Le quattro condizioni(In questa slide, l'ultima)

Attesa circolare: esiste un insieme di task{T0, T1,..., Tn} in cui:

T0 attende una risorsa posseduta da T1.T1 attende una risorsa posseduta da T2.…Tn attende una risorsa posseduta da T0.

48

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

Grafo orientato e bipartito modellante le relazioni fra task 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 task. Gli archi sono di due tipologie.

Risorsa task: la risorsa è associata al task.→Task risorsa: il task ha richiesto la risorsa.→

49

Grafo di allocazione di Holt(Definizione formale in termini di set di vertici e archi)

Formalmente, siano dati:un set di task T={T0, T1,...,Tn}.un set di classi di risorse R={R0, R1,...,Rk}.

Il grafo di allocazione di Holt è un grafo con: un set di vertici V = T U R.

un set di archi E partizionato in due sottoinsiemi.Arco di richiesta: Ti→Rj se un task Ti ha richiestoun'istanza di risorsa Rj.Arco di assegnazione: Rj T→ i se un'istanza di risorsa Rjè stata assegnata al task Ti.

50

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

Risorsariutilizzabile

Risorsa nonriutilizzabile

Istanza di unadata risorsa

Risorsaassegnata

Richiestapendente

T Task

Risorsa chepuò esserecreata da

R R

51

Grafo di allocazione di Holt(Grafi di esempio)

T1 T2

R1

R2

R3

T2 ottiene R1

T1 T2

R1

R2

R3

Evoluzione per stati successiviStato j Stato j+1

52

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

Ostrich algorithm.Si ignora del tutto il problema.Si correggono i deadlock a mano quando capitano.

Deadlock detection and recovery.Si fa evolvere il sistema per stati successivi chepossono condurre al deadlock.Si rileva il deadlock e lo si rimuove.

53

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.

54

IGNORARE IL DEADLOCK

55

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

L'algoritmo dello struzzo (ostrich algorithm) è semplice: si “mette la testa sotto la sabbia” e si ignora il problema del deadlock.RATIONALE: se la probabilità di ottenere un deadlock è bassa, non vale la pena ingegnarsi per prevenirlo.

Si preferisce identificare la causa del deadlock e →rimuoverla (correggendo il codice sorgente delle applicazioni coinvolte).

56

“Hi! I'm an ostrich!”(I like to put my head under the sand; not to ignore problems, but to lay eggs)

57

Correzione manuale di un deadlock(Compilazione con i simboli, uso di gdb, e tanta pazienza)

INPUT: una applicazione che va in deadlock per via di un uso sbagliato dei lock.PROCEDURA.Si ricompila l'applicazione con i simboli di debug.Si carica l'applicazione con un debugger.Si esegue l'applicazione all'interno del debugger fino al deadlock.Si esamina lo “stato” dell'applicazione in deadlock.Si identifica la sequenza di lock che porta al deadlock.Si corregge la sequenza di lock errata.OUTPUT: l'applicazione corretta.

58

Un esempio concreto(Correzione del deadlock in deadlock_abba_mutex.c)

Nelle slide seguenti si applica la procedura ora vista all'esempio deadlock_abba_mutex.c.

59

Ricompilazione con i simboli(Opzione -g di gcc)

È possibile ricompilare il programma con una speciale opzione di gcc (-g).gcc -pthread -g -o deadlock_abba_mutex deadlock_abba_mutex.c

Tale opzione crea ed inserisce nel binario eseguibile una tabella dei simboli.Tabella dei simboli: fa corrispondere ad un simbolo diverse informazioni utili in fase di debug.

Posizione (file, riga).Tipo.Indirizzo in memoria centrale.

60

Esecuzione tramite debugger(gdb programma)

Si carica il programma tramite il debugger.gdb ./deadlock_abba_mutex

Si esegue il programma.run

Si attende il deadlock.

61

Recupero stato dei thread(Si interrompe l'applicazione e si stampano le stack trace dei thread)

Si interrompe l'applicazione con la sequenza di tasti CTRL-C.Si stampano le stack trace di tutti i thread (con annessi valori delle variabili locali).thread apply all bt full

Grazie alla tabella dei simboli, gdb è in grado di tradurre gli indirizzi nei nomi delle funzioni.

→ Altrimenti, vedreste solo una sfilza di indirizzi esadecimali.

62

Analisi backtrace: Thread 1(Lo si può trascurare)

Sono presenti tre thread: Thread 1, Thread 2 e Thread 3.Thread 1 sembra essere il programma principale.Nel momento in cui è stato interrotto, Thread 1 stava eseguendo

main() → pthread_join()Thread 1 aspetta due thread in deadlock fra loro; lui non partecipa al deadlock.

→ Si può trascurarlo.

63

Analisi backtrace: Thread 2, Thread 3(Sono in deadlock fra loro)

Si osservino le backtrace di Thread 2 e Thread 3.Entrambi sono bloccati nella do_work().

Thread 2: do_work() (linea 39).Thread 3: do_work() (linea 51).

Si individui la porzione di codice che contiene tali righe, ad es. con il seguente comando di gdb:list 30,60

Thread 2 e 3 sono bloccati durante l'ottenimento dell'ultimo lock.

64

Ricostruzione sequenza deadlock(Analisi combinata)

Combinando:il codice sorgente ( cosa viene eseguito)→l'output generato ( in che sequenza temporale)→le stack trace ( dove avviene il blocco)→

si ricostruisce la sequenza di eventi mostrata nelle slide seguenti.OCCHIO: la sequenza si riferisce all'esecuzione del programma sulla macchina del docente.La sequenza potrebbe cambiare in funzione della macchina e delle scelte effettuato dallo scheduler dei processi.

65

Ricostruzione sequenza deadlock(T2 inizia l'esecuzione)

T2

66

Ricostruzione sequenza deadlock(T2 chiede il lock sulla risorsa condivisa R1)

T2

R1

OCCHIO: in realtà nel programmadeadlock_abba_mutex non c'èalcuna risorsa condivisa.Immaginiamo che tale risorsa siapresente in singola istanza (ad es.,una variabile intera condivisa).Essa è rappresentata con la labelR1.

67

Ricostruzione sequenza deadlock(T2 ottiene il lock sulla risorsa condivisa R1)

T2

R1

68

Ricostruzione sequenza deadlock(T3 inizia l'esecuzione)

T2

R1

T3

69

Ricostruzione sequenza deadlock(T3 chiede il lock sulla risorsa condivisa R2)

T2

R1

T3

R2

70

Ricostruzione sequenza deadlock(T3 ottiene il lock sulla risorsa condivisa R2)

T2

R1

T3

R2

71

Ricostruzione sequenza deadlock(T2 chiede il lock sulla risorsa condivisa R2)

T2

R1

T3

R2

72

Ricostruzione sequenza deadlock(T3 chiede il lock sulla risorsa condivisa R1)

T2

R1

T3

R2

73

Ricostruzione sequenza deadlock(T2 attende T3 e T3 attende T2)

T2

R1

T3

R2

T2 attende che T3sblocchi R2.T3 attende che T2sblocchi R1.T2 e T3 si attendonoa vicenda, per sempre.

→ DEADLOCK ABBA.

74

Esercizi (5 min.)

3. Si corregga deadlock_abba_mutex.c in modo tale da rimuovere il deadlock.

76

RILEVARE IL DEADLOCK

77

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?

78

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

Teorema: siano verificate le seguenti ipotesi.Le risorse

sono presenti in singola istanza;sono accedute in mutua esclusione.

Le richiestesono bloccanti;sono seriali;non sono prerilasciabili.

Allora uno stato è di deadlock se e solo se il grafo di allocazione contiene un ciclo.

79

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.

80

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

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

T1 T2 T3

R1

R2

CicloDeadlock

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

T1 T2 T3

R1

R2

CicloNO Deadlock

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

81

Esercizi (10 min.)4. Si copi il programma sorgente deadlock_abba_mutex.c nel programma sorgente abba_molteplici_istanze.c.Si corregga abba_molteplici_istanze.c nel modo seguente:

si sostituisca al mutex lockA un semaforo semA;si inizializzi semA a 2.

Si compili il programma e lo si esegua.C'è deadlock? Se sì, perché? Se no, perché?

83

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 task con soli archi entranti.Significato: il task ha terminato di richiedere risorse, e le sta solo possedendo.La procedura 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.

84

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.

85

Riconoscimento con più istanze(Esempio della riduzione)

Riduzione

T1 T2

R1

R2

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

Riduzione

T1 T2

R1

R2

86

Riconoscimento più istanze(Ipotesi di Coffman più multiple istanze: Deadlock Non completa riducibilità)↔

Teorema: siano verificate le seguenti ipotesi.Le risorse

sono presenti in multipla istanza (almeno una risorsa);sono accedute in mutua esclusione.

Le richiestesono bloccanti;sono seriali;non sono prerilasciabili.

Se il grafo di allocazione è completamente riducibile, uno stato non è di deadlock.

87

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

Quindi, nel caso di molteplici 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.

OCCHIO: la condizione è sufficiente, non necessaria.

Se vale sicuramente non c'è deadlock.Se non vale, non è detto che ci sia deadlock!Se non c'è deadlock, non è detto che valga!

88

Esempio(C'è deadlock?)

R1 R2

R3

T1 T3

T2

T4

89

Esempio(C'è deadlock?)

R1 R2

R3

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

T1 T3

T2

T4

90

Esempio(C'è deadlock?)

R1 R2

R3

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

T1 T3

T2

T4

91

Esempio(C'è deadlock?)

R1 R2

R3

Si riduce P3.

T1 T3

T2

T4

92

Esempio(C'è deadlock?)

R1 R2

R3

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

T1 T3

T2

T4

93

Esercizi (10 min.)

5. Si disegni il grafo di allocazione di Holt per abba_molteplici_istanze nell'istante in cui i due thread hanno prenotato tutte le loro risorse.Il grafo è completamente riducibile?

100

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, n M, 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.

101

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

a

b c

d

a

b c

d

{a, c, d} non èun annodamento

{b, c, d} èun annodamento

102

Grafo di attesa (wait-for)(Il grafo di allocazione senza nodi risorsa e con i Pj connessi direttamente)

Dato un grafo di allocazione di Holt, il grafo di attesa (o grafo wait-for) si ottiene nel seguente modo:

si eliminano tutti i nodi risorsa Rj.se nel grafo di allocazione Ti → Rj T→ j, allora nel grafodi attesa Ti T→ j.

103

Grafi di allocazione e di attesa(Un esempio vale più di 1000 parole)

T1

R1

R3

T3

R2

T2

Grafo diallocazione

Grafo diattesa

T1

T3

T2

104

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

Teorema: siano verificate le seguenti ipotesi.Le risorse

sono accedute in mutua esclusione.Le richieste

sono bloccanti;sono singole;non sono prerilasciabili.

I taskcon richieste pendenti sono tutti bloccati.

Se esiste un knot nel grafo di attesa allora lo stato è di deadlock.

105

Esempio(C'è un knot C'è deadlock)→

T1

R1

R3

T3

R2

T2

Grafo diallocazione

Grafo diattesa

T1

T3

T2

C'è unknot!

C'è undeadlock!

106

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

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.

OCCHIO: la condizione è sufficiente, non necessaria.

Se vale c'è sicuramente deadlock.Se c'è deadlock, non è detto che valga!

107

Controesempio(C'è un deadlock ma non c'è un knot)

T1

R1

R3

T3

R2

T2

Grafo diallocazione

Grafo diattesa

T1

T3

T2

Non c'èun knot!

C'è undeadlock!

X

108

RECAP(Utilissimo)Le risorse

sono accedute in mutua esclusione.Le richieste

sono bloccanti;non sono prerilasciabili.

Se:risorse seriali in singola istanza: deadlock ciclo nel↔grafo di allocazione.risorse seriali, almeno una in multipla istanza: grafo diallocazione completamente riducibile assenza di→deadlock.richieste singole: esiste un knot nel grafo di attesa →deadlock.

109

Uso degli algoritmi di detection(Quando si usano?)

Ad ogni richiesta di risorsa da parte di un task.Capacità di determinare la richiesta e, dunque, iltask che causa il deadlock.Costo molto elevato.Capacità di intervento tempestivo (non degradaeccessivamente l'utilizzo delle risorse).

110

Uso degli algoritmi di detection(Quando si usano?)

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

111

Deadlock recovery(Quando si applica?)

Terminazione del task.Approccio non incrementale: si terminano tutti itask coinvolti nel deadlock.Approccio incrementale: si terminano i taskcoinvolti 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).

112

Deadlock recovery(Quando si applica?)

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

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

113

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

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

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

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

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

114

PREVENIRE IL DEADLOCK

115

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.

116

Rimozione della mutua esclusione(Non sempre fattibile)

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

Tutti i task credono di usare la stampantecontemporaneamente.

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

117

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

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

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

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

Un task richiede una risorsa solo se non nepossiede nessuna.

Bassa utilizzazione delle risorse.Starvation.

118

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

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

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

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

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

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

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

119

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

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

Tn non può più attendere T0.Altamente inefficiente.

120

Esercizi (10 min.)

6. Si copi il programma sorgente deadlock_abba_mutex.c nel programma sorgente abba_no_possesso.c.Si riscriva abba_no_possesso.c in modo tale che nessun thread possieda e attenda risorse.

C'è deadlock? Se sì, perché? Se no, perché?

122

AGGIRARE IL DEADLOCK

123

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

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

124

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 task 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 ognitask.esaminare le richieste ed i rilasci futuri di ciascuntask.

125

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 task in un qualunque ordine, senza il verificarsi di un deadlock.Sequenza sicura: una sequenza di task (T1, T2, ..., Tn) è detta sicura se, per ogni Ti, le risorse di cui Ti necessita sono libere oppure in possesso di processi Tj, j<i.

126

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.

127

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.

128

Suddivisione degli stati(Sicuri, non sicuri, deadlock)

Diagramma di Venn dei possibili stati del sistema.

Stati sicuri

Stati non sicuri

Stati dideadlock

129

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 Ti T→ j: Ti può richiedere Rj in un qualsiasi istante futuro.

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

130

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

131

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

Risorsariutilizzabile

Risorsa nonriutilizzabile

Istanza di unadata risorsa

Risorsaassegnata

Richiestapendente

T Task

Risorsa chepuò esserecreata da

R R

Arco di reclamo

132

Grafo di allocazione con archi di reclamo(Un esempio)

T1 T2

R1

R2

Sia T1 che T2 intendono,durante la loro esecuzione,utilizzare R2.

133

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

Teorema: nell'ipotesi che Ti 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 Ti R→ j in un arco di assegnazioneRj T→ i non introduce un ciclo nel grafo di allocazionedelle risorse con archi di reclamo.Altrimenti, il sistema è in uno stato non sicuro.