Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Marco Lapegna » 3.Lo stallo dei processi – parte seconda


Metodi per la gestione dei deadlock

Assicurare che il sistema non entri mai in uno stato di deadlock.

  • Prevenzione dei deadlock: evitare che si verifichino contemporaneamente le condizioni per il deadlock;
  • Evitare i deadlock: se sta per verificarsi un deadlock esso viene evitato.

Permettere al sistema di entrare in uno stato di deadlock, quindi ripristinare il sistema.

  • Determinare la presenza di un deadlock;
  • Ripristinare il sistema da un deadlock.

Ignorare il problema e fingere che i deadlock non avvengano mai nel sistema;

Prevenire i deadlock

Mutua esclusione — in generale non è richiesta per risorse condivisibili (es. file in sola lettura), ma alcune risorse non possono essere condivise quindi in generale non è possibile prevenire i deadlock evitando la condivisione delle risorse (es. File in scrittura).

Prevenire i deadlock

Possesso e attesa — evitare “possesso e attesa” significa “non possedere” oppure “non attendere”. Quindi:

  • Richiedere ad un processo di allocare tutte le risorse necessarie prima che inizi l’esecuzione (evitare l’attesa);
  • consentire la richiesta di risorse solo quando il processo non ne possiede alcuna (evitare il possesso);
  • Basso impiego delle risorse (risorse possedute e non utilizzate, rilasciare e riprendere più volte le risorse);
  • È possibile che si verifichi l’attesa indefinita (vedi pbl. dei filosofi a cena).

Prevenire i deadlock

Impossibilità di prelazione:

  • Se un processo, che possiede alcune risorse, richiede un’altra risorsa che non gli può essere allocata immmediatamente, allora rilascia tutte le risorse possedute,
  • Le risorse rilasciate (prelazionate al processo) vengono aggiunte alla lista delle risorse che il processo sta attendendo;
  • Il processo viene avviato nuovamente solo quando può ottenere sia le vecchie che le nuove risorse;
  • scarsa efficienza (le risorse vengono acquisite e rilasciate).

Prevenire i deadlock

Attesa circolare — si impone un ordinamento totale su tutti i tipi di risorsa e si pretende che ciascun processo richieda le risorse in ordine crescente.

Ordinamento delle risorse
1 : stampante
2: scanner
3: plotter
4: unita’ nastro
5: unita’ CD

Due risorse: R e S

  • se R > S allora A non può richiedere S
  • se R < S allora B non può richiedere R

Assenza di cicli

Evitare i deadlock

Presuppone che il sistema conosca a priori informazioni addizionali sulle richieste future dei processi.

  • Il modello più semplice e utile richiede che ciascun processo dichiari il numero massimo di risorse di ciascun tipo di cui può usufruire;
  • Un algoritmo (alg. di deadlock–avoidance) esamina dinamicamente lo stato di allocazione delle risorse per assicurare che non si possa verificare mai una condizione di attesa circolare;
  • Gli algoritmi di deadlock-avoidance si basano sul concetto di stato sicuro.

Stato sicuro

  • Uno stato e’ sicuro se:
    • non è in stallo;
    • e’ possibile soddisfare le richieste pendenti eseguendo i processi in un qualche ordine (sequenza sicura).
  • Se un sistema è in stato sicuro allora non evolve verso il deadlock.
  • Se un sistema è in stato non sicuro allora può evolvere verso un deadlock.
    (potrebbe ad esempio rilasciare autonomamente alcune risorse)
  • Quando un processo richiede una risorsa disponibile, il sistema deve decidere se l’allocazione immediata lasci il sistema in stato sicuro.

Sequenza sicura

Una sequenza <P1, P2, …, Pn > è sicura se, per ogni Pi, le risorse che Pi può ancora richiedere possono essergli allocate sfruttando le risorse disponibili + le risorse possedute da tutti i Pj, con j < i.

  • Se le richieste di Pi non possono essere soddisfatte immediatamente, allora Pi deve attendere finché Pj ha terminato.
  • Quando Pj ha terminato, Pi può ottenere le risorse richieste, eseguire i suoi compiti, restituire le risorse allocate e terminare.
  • Quando Pi termina, Pi+1 può ottenere le risorse richieste, etc.

Esempio di stato sicuro

La matrice di allocazione di una risorsa riporta, per ogni processo, il numero di istanze possedute e il massimo numero di istanze che utilizzerà.


Esempio di stato sicuro

Lo stato a) e’ sicuro, infatti.

  • si assegnano 2 istanze a P2
    • → 1 istanza libera (stato b)
  • P2 termina e rilascia le sue istanze
    • → 5 istanze libere (stato c)
  • si assegnano 5 istanze a P3
    • → 0 istanze libere (stato d)
  • P3 termina e rilascia le sue istanze
    • → 7 istanze libere (stato e)
  • si possono assegnare 6 risorse a P1
    • che termina regolarmente
  • < P2, P3, P1 > è una sequenza sicura

Esempio di stato non sicuro

Se però dallo stato (a) si assegna una ulteriore istanza al processo P1 si ottiene uno stato non sicuro (stato b) che conduce a un deadlock (stato d).

Osservazione: nello stato (b), anche assegnando le 2 risorse libere a P1 o P3 (invece che a P2) si ottiene un deadlock.


Algoritmo del banchiere

IDEA : in base delle risorse disponibili soddisfare prima le richieste di un processo che, può completare la propria esecuzione, permettendo così il rilascio di tutte le risorse in suo possesso.

Ciascun processo deve dichiarare a priori il massimo impiego di risorse.
Quando un processo richiede una risorsa si verifica prima che il nuovo stato sia uno stato sicuro. In caso contrario il processo attende.

Il nome deriva dal fatto che esso può essere applicato in una banca per evitare che il cassiere consegni tutto il denaro disponibile (le risorse), e non possa piuù soddisfare le richieste di tutti i suoi clienti (i processi).

Algoritmo del banchiere

Dati necessari per l’algoritmo nel caso di

  • 1 risorsa R con più istanze
  • n processi Pi i=1,..,n
  • Available: numero di istanze disponibili della risorsa R
  • Max: array di lunghezza n. Max [ i ] è il massimo numero di istanze che Pi può richiedere
  • Allocation: array di lunghezza n. Allocation[ i ] è il numero di istanze attualmente allocate a Pi
  • Need: array di lunghezza n. Need [ i ] è il numero di ulteriori istanze necessarie a Pi per completare il proprio task.

( Need [ i ] = Max [ i ] – Allocation [ i ] )

Algoritmo di richiesta delle risorse per il processo Pi

Sia Request [i ], numero di istanze richieste dal processo Pi.

Se Request [i ] ≤ Need [i ] , si vada al passo 2. Altrimenti, si riporti una condizione di errore, poiché il processo ha ecceduto il massimo numero di richieste.
Se Request [i ] ≤ Available , si vada al passo 3. Altrimenti Pi deve attendere, poiché le risorse non sono disponibili.
Il sistema simula l’allocazione al processo Pi delle risorse richieste, modificando lo stato di allocazione delle risorse come segue:

Available = Available – Request [i ]
Allocation [i ] = Allocation [i ] + Request [i ]
Need [i ] = Need [i ] – Request [i ]

  • Se lo stato è sicuro _ le risorse vengono definitivamente allocate a Pi .
  • Se lo stato è non sicuro → Pi deve attendere, e viene ripristinato il vecchio stato di allocazione delle risorse.

Algoritmo di verifica della sicurezza

Come fare a vedere se uno stato e’ sicuro?
Cerchiamo una sequenza sicura

Siano Finish vettore di lunghezza n e Work un intero. Si inizializzi:

  • Work = Available ( così non perdiamo Available )
  • Finish[i ] = false per i = 1,2, …, n

Si cerchi i tale che valgano contemporaneamente:

  • Finish[i ] = false
  • Need[i ] _ Work

Se tale i non esiste, si esegua il passo 4.

  • Work = Work + Allocation[i ]
  • Finish[i ] = true torna al passo 2.

Se Finish [i ] == true per ogni i, il sistema è in stato sicuro.

Esempio: n=3 processi

Finish[1] = Finish[2] = Finish[3] = false
Work = Available = 3

i=1 Need[1] _ Work e Finish[i ] = false ? no
i=2 Need[2] _ Work e Finish[2 ] = false ? Si
Work = 3+2 = 5 Finish[2] = true

i=1 Need[1 ] _ Work e Finish[1 ] = false ? no
i=2 Need[2 ] _ Work e Finish[2] = false ? no
i=3 Need[3 ] _ Work e Finish[3 ] = false ? Si
Work = 5+2 = 7 Finish[3] = true

i=1 Need[1 ] _ Work e Finish[1 ] = false ? Si
Work = 7+3 = 10 Finish[1] = true

Fine → Stato sicuro
La sequenza <P2, P3, P1 > soddisfa i criteri di sicurezza
(Finish[i] == true per ogni i)


Esempio: n=3 processi

Finish[1] = Finish[2] = Finish[3] = false
Work = Available = 2

i=1 Need[1] _ Work e Finish[1 ] = false ? no
i=2 Need[2] _ Work e Finish[2 ] = false ? Si
Work = 2+2 = 4 Finish[2] = true

i=1 Need[1 ] _ Work e Finish[1 ] = false ? no
i=2 Need[2 ] _ Work e Finish[2] = false ? no
i=3 Need[3 ] _ Work e Finish[3 ] = false ? no
dopo P2 nessuno riesce a terminare
(Finish[1] = Finish[3] = false )


I materiali di supporto della lezione

Silberschatz , Galvin, Gagne – Sistemi Operativi 8a ed. Capitolo 6

Tanenbaum – Moderni sistemi operativi 3a ed. Capitolo 7

Deitel, Deitel, Choffnes - Sistemi operativi 3a ed. Capitolo 5

Sistema operativo

  • 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