Riassunto capitolo 8 - Lo stallo (deadlock)

 :: title Riassunto capitolo 8 - Lo stallo (deadlock) ::

Torna alla pagina di Sistemi Operativi

La maggior parte dei SO NON fornisce strumenti di prevenzione dello stallo -> probabilmente in futuro.

8.1 Il modello delle risorse di sistema e dei processi

Risorse = di molti tipi, distribuite fra i vari processi.

Se un processo vuole un tipo di risorsa, può ottenere con soddisfazione una qualunque istanza di quella risorsa. Deve chiederla prima di usarla, e rilasciarla dopo:

1. richiesta: se non è soddisfacibile, il processo deve attendere
2. uso: il processo usa la risorsa
3. rilascio: il processo libera la risorsa

Richiesta & rilascio = chiamate di sistema.

Un gruppo di processi è in stallo se ogni processo del gruppo è in attesa di un evento che può essere generato solo da un processo del gruppo.

Multithread => proni al deadlock perché i thread accedono a risorse condivise.

8.2 Caratterizzazione del deadlock

8.2.1 Condizioni per il verificarsi del deadlock

Condizioni affinché si abbia un deadlock:

1. Mutua esclusione nell'uso di una risorsa
2. Hold & wait: stato in cui un processo ha una risorsa (hold) ma ne attende un'altra (wait)
3. Nessun rilascio anticipato: le risorse possono essere liberate solo con un atto volontario del processo
4. Attesa circolare: A attende da B che attende da C che attende da A

Devono verificarsi tutte e 4 le condizioni.

8.2.2 Grafo di allocazione delle risorse

Nodi = 2 tipi

• cerchi = processi
• quadrati = risorse
  • ogni pallino in un quadrato rappresenta un'istanza di quella risorsa

Archi:

• arco di richiesta = da processo a risorsa = il processo è in attesa di quella risorsa
• arco di assegnazione = da risorsa a processo = il processo possiede quella risorsa

Se il grafo NON contiene cicli => di sicuro non ci sarà nessun deadlock.
Se il grafo ha un ciclo => possibile deadlock (condizione necessaria ma non sufficiente)

8.3 Metodi di gestione del deadlock

Ci sono 3 modi per gestire il deadlock:

• impedire o evitare i deadlock, facendo in modo che il SO non entri mai in un deadlock
• permettere l'ingresso in uno stallo, ma rilevarlo e recuperare
• ignorare il problema, perché tanto è raro, e ci penserà l'utente a fermare il processo in dl

Ignorare il problema è il sistema maggiormente utilizzato: spetta al programmatore far sì che i dl non accadano.

Prevenire i dl = impedire in partenza che l'assegnazione delle risorse possa ingenerare una delle 4 condizioni viste prima.

Evitare i dl = se conosco tutte le richieste che il processo farà, so dire in partenza se si può finire in dl.

8.4 Prevenire il deadlock

4 tecniche diverse, ciascuna atta a scongiurare l'avverarsi di una delle 4 condizioni viste sopra.

8.4.1 Mutua esclusione

Le risorse condivisibili non creano dl. Quelle non condivisibili invece potrebbero.

Dovrei impedire la mutua esclusione di risorse non condivisibili => ma è impraticabile perché ho risorse intrinsecamente non condivisibili (eg la stampante).

8.4.2 Possesso ed attesa

Per evitare la condizione di possesso ed attesa, devo fare in modo che un processo che abbia già una risorsa non possa attendere per un'altra.

Posso avere 2 protocolli:

1. un processo deve acquisire tutte le risorse prima di partire
2. un processo può acquisire risorse solo quando non ne ha nessuna

Il problema della tecnica 1 è che un processo può tenere bloccata per lungo tempo una risorsa che userà invece per poco.

=> in generale

• l'uso delle risorse è basso perché vengono assegnate a lungo ma non utilizzate
• può insorgere starvation (un processo attende indefinitamente delle risorse comuni)

8.4.3 Nessun rilascio anticipato

Protocollo 1: Se il processo non può ottenere le risorse che chiede deve mollare tutte quelle che ha, e rimettersi in lista di attesa per tutte.

Protocollo 2: Un processo che chiede risorse le può ottenere:

• o se sono già disponibili;
• o se sono di proprietà di un processo attualmente in attesa di altre risorse => quest'ultimo processo viene preemptivato e privato delle proprie risorse

8.4.4 Attesa circolare

Tutte le risorse vengono numerate in modo crescente (non importa quale).

Si impone poi che un processo può richiedere solamente risorse con un ordine più alto di quelle che già ha => deve chiederle in ordine => si previene l'attesa circolare.

Ma l'imporre un ordinamento alle risorse di per sé non cambia nulla => occorre che il programmatore rispetti l'ordinamento.

8.5 Evitare il deadlock

Gli algoritmi di prevenzione del deadlock impediscono l'insorgere delle condizioni del deadlock => tuttavia le periferiche vengono sottoutilizzate.

=> si richiedono informazioni supplementari al processo, relativamente alle risorse che vorrà chiedere => sapendo in anticipo che cosa vorrà, si sa subito se far attendere o meno il processo.

8.5.1 Lo stato sicuro

Sequenza sicura = una sequenza di processi P_i ... P_n tale che le richieste del P_i-esimo programma possono essere soddisfatte

• con le risorse ancora libere
• e con le risorse dei P_j con j < i

Esiste una sequenza sicura => siamo in uno stato sicuro.

Ocio: stato non sicuro non implica un dl, però non può garantirne la non insorgenza.

Un sistema può passare da uno stato sicuro ad uno non sicuro => occorre controllare le richieste e verificare che ciò possa non avvenire => le richieste vengono soddisfatte solo se mantengono il sistema in uno stato sicuro.

8.5.2 Algoritmo del grafo di allocazione delle risorse

Si usa nel caso ci sia un'istanza per ogni tipo di risorsa.

Rispetto al grafo "normale" viene introdotto l'arco di prenotazione = da un processo ad una risorsa = vuol dire che il processo vorrà in futuro quella risorsa.

È necessario conoscere le richieste future quando un processo viene avviato.

Il sistema è in uno stato sicuro se non ci sono cicli, considerando anche gli archi di prenotazione.

8.5.3 Algoritmo del banchiere

Si usa quando ci sono più istanze per la stessa risorsa. Il processo deve dichiarare all'ingresso nel sistema quante istanze di ogni risorsa richiederà in futuro.

Occorrono parecchie strutture dati per implementare questo algoritmo.
n = numero di processi m = numero di tipi di risorse

• Vettore Available[m] = la i-esima posizione ci dice quante istanze di quella risorsa ci sono
• Matrice Max[n*m] = ogni riga esprime le massime richieste di quel processo per ogni tipo di risorsa
• Matrice Allocation[n*m] = ogni riga esprime le risorse correntemente allocate a quel processo
• Matrice Need[n*m] = ogni riga indica il bisogno restante di risorse per quel processo.

Attenzione: Need[i][j] = Max[i][j] - Allocation[i][j], il che vuol dire che le risorse di cui un processo ha ancora bisogno devno essere pari a quelle che ha chiesto all'inizio in totale (max) meno quelle già allocate (Allocation).

Ci sono poi 2 algoritmi:

• algoritmo di sicurezza = controlla se uno stato è sicuro
• algoritmo di richiesta = controlla se una richiesta conduce ad uno stato sicuro

8.5.3.1 L'algoritmo di sicurezza

1. Work[m] = Available; Finish[n] = false per ogni 0 < i < n
2. Si cerca una i tale per cui:
   • Finish[i] == false;
   • Need_i <= Work (l'i-esima riga di Need è <= del vettore Work)
   • Se non esiste una i che soddisfa ciò passo al punto 4
3. Work = Work + Allocation_i; Finish[i] = true; vado al punto 2
4. Se per ogni i, Finish[i] è true, allora sono in uno stato sicuro.

Quello che succede è che per ogni processo controllo se ha abbastanza risorse per soddisfare tutte le sue richieste passate e future.
Le risorse le cerco in 2 punti:

• tra quelle libere
• tra quelle dei processi che vengono prima di lui (vedi definizione di stato sicuro)

Se ogni processo può avere tutte le risorse che chiede (Finish[i] = true, per ogni i), allora sono in uno stato sicuro.

Complessità: O(m * n²)

8.5.3.2 L'algoritmo di richiesta delle risorse

Request[m] è il vettore delle richieste dell'i-esimo processo.

1. Se Request_i <= Need_i vai al punto 2; altrimenti errore (il processo richiede più di quanto dichiarato in partenza)
2. Se Request_i <= Available, vai al punto 3; altrimenti il processo attende (chiede ciò che non può ancora ottenere)
3. Il sistema alloca al processo le risorse richieste modificando così lo stato:
   • Available = Available - Request_i
   • Allocation_i = Allocation_i + Request_i
   • Need_i = Need_i - Request_i
   • se questo stato è sicuro (verifico con l'algoritmo di prima), allora lo confermo. Altrimenti il processo deve attendere, e torno allo stato precedente.

8.6 Rilevazione del deadlock

Il SO lascia accadere i deadlock, ma cerca di rilevarli e poi di porvi rimedio.

Occorre

• un algoritmo che rilevi il deadlock
• un algoritmo che recuperi dallo stato di deadlock

Anche in questo caso, i comportamenti sono diversi a seconda che si abbiano risorse ad istanze singole o multiple.

8.6.1 Singola istanza di ogni tipo di risorsa

Grafo wait-for = variazione del grafo di allocazione delle risorse

• i nodi delle risorse collassano, rimangono quelli dei processi
• un arco da un processo A ad un proceso B indica che A vuole una risorsa posseduta da B

Mantengo il grafo ad ogni richiesta di risorse.
Controllo periodicamente che non ci siano cicli in questo grafo. Se ci sono cicli, è possibile un deadlock.

Complessità: O(n²)

8.6.2 Istanze multiple di un tipo di risorsa

Uso strutture dati simili a quelle dell'algoritmo del banchiere.

Come prima, m è il numero di tipi di risorse, n è il numero dei processi.

• Available[m] = istanze disponibili per ogni tipo di risorsa
• Allocation[n*m] = ogni riga dice quante risorse sono allocate a quel processo
• Request[n*m] = ogni riga indica quante risorse quel processo chiede

1. Work[m] = Available; Finish[i] = false se Allocation_i = 0, altrimenti Finish[i] = true
2. Cerco una i tale che
   • Finish[i] == false
   • Request_i <= Work
   • Se non esiste, vado al punto 4
3. Work = Work + Allocation_i; Finish[i] = true; vado al punto 2
4. Se c'è una Finish[i] == false, allora sono in uno stato di deadlock, e il processo P_i è in stallo

Questo algoritmo all'inizio indica tutti i processi come adatti alla terminazione (Finish[i] = true) se non hanno nessuna risorsa allocata: niente risorse, niente deadlock. Altrimenti, Finish[i] = false.

Poi, analizzo tutte le richieste per ogni processo. Se sono soddisfacibili, allora stabilisco che le risorse di quel processo saranno utilizzabili da altri processo (Work = Work + Allocation_i), e che quel processo potrà terminare.

Se c'è qualche processo che, alla fine, è indicato come impossibilitato a terminare, vuol dire che c'è un deadlock nel sistema, e che quel processo è in stallo.

La scelta del punto 3 si spiega in questo modo: se un processo ha le risorse che vuole, suppongo ottimisticamente che potrà finire tranquillamente. Se ciò non accadrà, una successiva passata dell'algoritmo lo rileverà comunque.

Complessità = O(m x n²)

8.6.3 Uso dell'algoritmo di rilevazione

La frequenza con cui invocare questo algoritmo dipende da 2 fattori:

1. quanto spesso si verifica un deadlock nel sistema
2. quanti processi sono coinvolti in un deadlock, quando questo accade

Se i deadlock sono frequenti, allora l'algoritmo andrebbe invocato frequentemente.

Caso limite = invocarlo ogni volta che c'è una richiesta di allocazione non immediatamente soddisfacibile (quindi, una dipendenza da altri processi).

Questo algoritmo genera overhead => costoso eseguirlo sempre => posso eseguirlo eg solo quando l'uso della CPU scende sotto il 40%, perché i deadlock tendono a paralizzare il sistema.

8.7 Ripristino dal deadlock

Quando è stato rilevato un deadlock, posso

• far intervenire l'operatore
• decidere automaticamente che cosa fare
  • abortisco uno o più processi finché il dl non scompare
  • preemptivo alcuni processi per riprendermi delle risorse.

8.7.1 Termine del processo

Posso

• Abortire tutti i processi in deadlock => molto costoso, perché posso fermare anche processi che non c'entrano e che magari erano a buon punto
• Abortirne uno alla volta finché il deadlock non scompare => molto overhead dovuto alla ripetizione, ad ogni uccisione, dell'algoritmo di rilevazione

Per decidere quale processo uccidere, posso scegliere tra diversi criteri, eg priorità, interattività etc. => si sceglie quello la cui morte, in base al criterio scelto, sia di costo minimo.

8.7.2 Rilascio anticipato delle risorse

Tolgo le risorse a qualcuno e le do a qualcun altro.

1. Scelta della vittima, in base a fattori di costo (tempo già consumato, numero di risorse in uso etc.)
2. Rollback = annullare le modifiche eseguite dal processo in corso
3. Starvation = se mi si ripresenta una situazione uguale, e uccido con lo stesso criterio, sempre lo stesso processo verrà ucciso => starvation di quel processo => includo nel fattore costo il numero di rollback eseguiti.

Torna alla pagina di Sistemi Operativi