Marco Lapegna » 4.Lo stallo dei processi – parte terza

Algoritmo del banchiere

L’algoritmo puo’ essere generalizzato al caso di più risorse con le dovute modifiche:

• Available: Vettore di lunghezza m. Available[ j ] è il numero di istanze disponibili della risorsa Rj;
• Max: matrice n x m. Max [ i,j ] è il massimo numero di istanze di R_j che il processo Pi può richiedere;
• Allocation: matrice n x m. Allocation[ i,j ] è il numero di istanze di R_j attualmente allocate a Pi;
• Need: matrice n x m. Need [ i,j ] è il numero di ulteriori istanze di R_j necessarie a P_i per completare il proprio task.

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

Prima di soddisfare una richiesta, bisogna verifica lo stato della sicurezza per tutte le risorse R_j j=1,..,m

Debolezze dell’algoritmo del banchiere

• Richiede che il numero delle risorse rimanga costante, ma questa non è un’ipotesi realistica;
• Richiede che il numero di processi rimanga costante, ma cio’ non è vero;
• Richiede che i processi restituiscano le risorse in un tempo finito (vero in alcuni sistemi, ad es. real time);
• Richiede che i processi dichiarino le proprie necessità prima dell’esecuzione (quasi mai possibile).

Secondo approccio

• Prevenire i deadlock
  • Sottoutilizzo delle risorse

• Evitare i deadlock
  • Necessità di informazioni sulle richieste future dei processi

↓

In entrambi i casi : elevato overhead

• Approccio alternativo: si permette al sistema di entrare in uno stato di deadlock e poi si ripristna il sistema
• Sono necessari:
  • Algoritmo di rilevamento del deadlock
  • Algoritmo di ripristino dal deadlock

Algoritmo di rilevamento

Variante della verifica della sicurezza dell’algoritmo del banchiere per n processi e m risorse multiple.

• Available: vettore di lunghezza m, indica il numero di istanze disponibili di ogni risorsa.
• Allocation: matrice n x m, definisce il numero di istanze di ciascuna risorsa attualmente allocate a ciascun processo.
• Request: matrice n x m, indica la richiesta corrente di ciascun processo. Se Request [i,j ] = k, il processo P_i richiede k istanze supplementari della risorsa R_j .

Osservazione: manca la matrice Max e quindi anche Need

Algoritmo di rilevamento

• Siano Work e Finish due vettori di lunghezza m e n, rispettivamente. Inizialmente si ponga:
  • Work = Available
  • Per i = 1,2, …, n, Finish[ i ] = false;

• Si trovi un indice i tale che valgano entrambe le condizioni:
  • Finish[ i ] = false
  • Requesti ≤ Work

Se tale i non esiste si vada al passo 4.

• Work = Work + Allocation_i
• Finish[i] = true

si vada al passo 2.

• Se Finish[ i ] == false, per qualche i, 1 ≤ i ≤ n, il sistema è in uno stato di deadlock. Inoltre, se Finish[ i ] == false, P_i è in deadlock.

L’algoritmo richiede un numero di operazioni dell’ordine di O(m x n² ) per determinare se il sistema è in uno stato di deadlock.

Impiego dell’algoritmo di rilevamento

• Quando e quanto spesso richiamare l’algoritmo di rilevamento dipende da:
  • Frequenza (presunta) con la quale si verificano i deadlock;
  • Numero di processi che vengono eventualmente influenzati dal deadlock (e sui quali deve essere effettuato un rollback):
    • Almeno un processo per ciascun ciclo.

• Se l’algoritmo viene richiamato in momenti arbitrari, possono essere presenti molti cicli nel grafo delle risorse non si può stabilire quale dei processi coinvolti nel ciclo abbia “causato” il deadlock.
• Alternativamente, l’algoritmo può essere richiamato ogni volta che una richiesta non può essere soddisfatta immediatamente.

Ripristino dal deadlock: Terminazione di processi

• Terminazione in abort di tutti i processi in deadlock.
• Terminazione in abort di un processo alla volta fino all’eliminazione del ciclo di deadlock.
• In quale ordine si decide di terminare i processi? I fattori significativi sono:
  • La priorità del processo.
  • Il tempo di computazione trascorso e il tempo ancora necessario al completamento del processo.
  • Quantità e tipo di risorse impiegate.
  • Risorse ulteriori necessarie al processo per terminare il proprio compito.
  • Numero di processi che devono essere terminati.
  • Tipo di processo: interattivo o batch.

Terzo approccio

Gli approcci per

• Prevenire i deadlock
• Evitare i deadlock

Sono costosi, impongono restrizioni sull’uso delle risorse e possono richiedere informazioni sull’uso futuro delle risorse

Occorre tenere presente che un deadlock dipende dalla schedulazione dei processi, e non solo da come sono fatti i processi quindi un deadlock puo’ essere un evento relativamente raro.

↓

Siamo disposti a prevenire ed evitare sempre qualcosa che potrebbe accadere raramente?

Ignorare il problema

Molti S.O. (tra cui Windows e Unix) ignorano il problema. L’amministratore del sistema provvederà, a mano, a ripristinare il sistema.

Ovviamente S.O. con funzioni particolari, potrebbero richiedere funzionalità di prevenzione dei deadlock (es. sistemi RT).