malcom

Indice:

- Tipi di prevenzione al deadlock
- Prevenzione/avoidance
- Un esempio: Algoritmo del banchiere
- Deadlock detection
- Deadlock recovery

PREVENZIONE/AVOIDANCE
La prevenzione del deadlock si basa su come si fanno le richieste allo scopo di evitare una delle condizioni necessarie del dealock.
In realtà i sistemi di prevenzione permettono poca concorrenza all’interno del sistema. Chiedere risorse in modo crescente non è fattibile.

Per non vincolare i processi a questo genere di richieste, gli algoritmi di deadlock avoidance chiedono informazioni in più ai processi al momento della richiesta della risorsa.
Questi algoritmi cercano di conoscere quanto più possibile sullo stato del sistema – il grafo di allocazione – al momento della richiesta di una risorsa.

Un modello generico sul quale ci si basa per la creazione di un algoritmo di deadlock avoidacne è il seguente.
Ogni processo deve dichiarare il massimo numero di risorse per ogni tip di cui lui può aver bisogno (questo non implica che poi il processo debba effettivamente richiederle in tal ordine).

Il sistema a sua volta dichiara il massimo numero di risorse per ciascun tipo che può allocare al singolo processo.

In base alle richieste fatte ai processi e allo stato attuale, l’algoritmo si incaricherà quindi di dicedire di andare in un altro stato soddisfacendo una richiesta alla volta in uno stato sicuro.
Questo è fatto attraverso una analisi del grafo che evita il caso di una circolarità.

Il sistema all’inizio si trova in uno stato definito “sicuro”. Mano mano che si va avanti ci si potrebbe spostare (mediante una sequenza di richieste) verso uno stato non sicuro fino al deadlock. Per cui si cerca sempre di rimanere nella parte verde.

Una sequenza di processi P1,Pn si dice sicura se le risorse di cui necessita un processo sono libere o sono in possesso di processi che si trovano prima nella sequenza.

Il sistema è sicuro se quando assegna risorse ai processi essi sono parte di una sequenza sicura.
Quando un processo finisce la sua evoluzione e quindi libera risorse, ci sarà almeno un processo che è in grado di evolvere fino alla fine.
UN ESEMPIO: ALGORITMO DEL BANCHIERE
Prima di illustrare l’algoritmo del banchiere è necessario introdurre un’altra operazione all’interno del grafo. Si tratta in particolare del claim con cui un processo dichiara che in futuro avrà bisogno di una determinata risorso. Quando il claim diventa una richiesta vera la freccia diventa da tratteggiata a piena, e più avanti allocando la risorsa chiesta, cambierà verso.

Uno degli algoritmi utilizzati per l’assegnazione delle risorse è quello del banchiere. Esso si basa su una serie di strutture dati:

• Vettore Available[j]: indica il numero di istanze della j-esima risorsa.
• Matrice Max[i,j]: indica il massimo numero di istanze della j-esima risorsa che possono essere richieste dall’i-esimo processo (claim).
• Matrice Allocation[i,j]: indica il numero di istanze della j-esima risorsa che sono attualmente assegnate all’i-esimo processo (stato corrente).
• Matrice Need[i,j]: indica il numero di istanze della j-esima risorsa che potranno essere richieste in futuro dall’i-esimo processo (necessità residua). Essa è pari, per ogni elemento, a Max-Allocation

L’algoritmo è costituito da due parti:

1. safety algorithm che verifica la sicurezza
2. resource request algorithm che decide l’assegnazione. Questa è basata sul fatto che si muova sempre in uno stato sicuro, e per questo si utilizza il punto 1.

Verifica della sicurezza: (costo O(MxN^2))
Consideriamo m risorse e n processi e due vettori:

• Work[m]: vettore che dice quali risorse sono disponibili.
• Finish[n]: vettore che dice che un processo ha finito la sua evoluzione.

1. Il vettore Finish è inizializzato tutto a FALSE e Work è inizialmente posto come Available, ossia tutte le risorse sono inizialmente disponibili.Si cerca un i tale che Finish[i]=FALSE ossia si cerca un processo che non ha ancora terminato e che allo stesso tempo abbia bisogno di una quantità di risorse minore o uguale a quelle disponibili. Se non si trova nessun processo vuol dire che il sistema è sicuro. Se i non esiste si va al passo 3 dove il sistema però non si sa se è sicuro o no.
2. (Viene messo a TRUE mano mano che i processi terminano la loro evoluzione)Se si è trovato un processo con quelle caratteristiche allora si aggiorna Work aggiungendo alle risorse disponibili quella allocate per il processo (in questo modo lo scheduler indica che prima o poi il processo terminerà rilasciando le risorse che saranno nuovamente disponibili) e lo si mette in Finish[i]=TRUE segnalandolo com fine evoluzione.
3. Si nota che se tutti gli elementi sono TRUE allora si è in uno stato sicuro (tutti i processi hanno terminato).

Assegnazione:
La verifica della sicurezza serve per la decisione di assegnazione. Il processo invia una richiesta. Si ha un vettore Request-i[m] che indica l’attuale richiesta delle m risorse da pate del processo i.

Si hanno quindi quattro passi:

1. Se la richiesta (per ogni risorsa) è minore o al più uguale a Need (Request-i <= Need-i) allora si va al passo 2, altrimenti il processo ha richiesto più risorse di quelle che ha dichiarato aver bisogno.
2. Se la richiesta fatta è minore o uguale alla disponibilità (Request-i <= Available-i) allora si va al passo 3, altrimenti si mette il processo in uno stato di attesa.
3. Al passo 3 si simula l’allocazione delle risorse
   - Available = Available – Request i
   (Si sottrae alle risorse disponibili quelle richieste dal processo)
   - Allocation i = Allocationi + Requesti
   (si aggiungono le risorse richieste a quelle allocate per il processo)
   - Need i = Needi – Requesti
   (si sottraggono le risorse richieste a quelle necessarie per il processo)
4. Si chiama l’algoritmo di verifica della sicurezza. Se lo stato sarà sicuro allora l’allocazione è resa permanente, altrimenti si ripristina il vecchio stato.

DEADLOCK DETECTION
L’algoritmo di rilevamento, al contrario del precedente che verifica lo stato di sicurezza del sistema, scopre se il sistema si trova in uno stato di deadlock.
Questo genere di algoritmo può essere fatto seguendo due differenti criteri:

• ad ogni richiesta di risorsa da parte di un processo
  - capacità di determinare la richiesta che causa il deadlock
  - costo elevato
  - capacità tempestiva di intervento
• su base periodica
  - incapacità di determinare il processo di deadlock
  - costo ridotto
  - ridotta tempestività di intervento

L’algoritmo è diverso a seconda delle istanze di risorse.
Se c’è una sola istanza per ogni risorsa si procede esaminando il grafo di allocazione per la presenza di cicli.
Se ci sono istanze multiple per risorsa allora si procede in due passi:

1. Inizializzazione
   Si cerca un processo che non ha finito ossia che la sua richiesta sia minore o uguale alle risorse disponibili (Request-i <= Work). Si verifica quindi lo stato di deadlock (e non la sicurezza); se nessun processo soddisfa le richieste si passa al passo 3.
2. Computazione (1/2)
   Se esiste un processo con queste caratteristiche lo si fa evolvere. Per cui considerandolo terminato si aggiungono le risorse da lui allocate tra quelle disponibili e si setta il processo a TRUE (Work=Work+Allocation, Finish[i]=true)
3. Computazione (2/2)
   Se Finish[i]=FALSE per qualche i, allora il sistema è in deadlock, e i processi in deadlock hanno il flag Finish a FALSE. Altrimenti significa che sono state soddisfatte tutte le richieste, e tutti i processi hanno terminato.

DEADLOCK RECOVERY
In caso di rilevamento del deadlock ci sono due approcci che si possono seguire:

• Approccio non incrementale: si eliminano tutti i processi che sono coinvolti nel deadlock
• Approccio incrementale: si si elimina un processo per volta fino all’eliminazione del deadlock. Il processo scelto di volta in volta può essere selezionato per priorità, tempo di calcolo, tipo di risorse occupate.

Si può inoltre deassegnare le risorse ad un processo coinvolto nel deadlock. Occorre in questo
modo selezionare una vittima e evitare la starvation.

(3/3/2007)

[tags]Tipi di prevenzione al deadlock,Prevenzione/avoidance,Un esempio: Algoritmo del banchiere,Deadlock detection,Deadlock recovery [/tags]