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 » 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 Rj che il processo Pi può richiedere;
  • Allocation: matrice n x m. Allocation[ i,j ] è il numero di istanze di Rj attualmente allocate a Pi;
  • Need: matrice n x m. Need [ i,j ] è il numero di ulteriori istanze di Rj necessarie a Pi 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 Rj j=1,..,m

Esempio di applicazione dell’algoritmo del banchiere

  • 5 processi, da P0 a P4;
  • 3 tipi di risorse: A (10 istanze), B (5 istanze), e C (7 istanze);
  • Nella figura a lato: Istantanea al tempo T0
Il contenuto della matrice Need  è definito come Max – Allocation.

Il contenuto della matrice Need è definito come Max – Allocation.


Passo 1

  • è possibile soddisfare le richieste di P1
  • Alla fine dell’esecuzione P1 rilascia le risorse _ Available = (5 3 2)
  • Sequenza sicura < P1 >

Passo 2

  • è possibile soddisfare le richieste di P3
  • Alla fine dell’esecuzione P3 rilascia le risorse _ Available = (7 4 3)
  • Sequenza sicura < P1 , P3 >

Passo 3

  • è possibile soddisfare le richieste di P4
  • Alla fine dell’esecuzione P4 rilascia le risorse → Available = (7 4 5)
  • Sequenza sicura < P1 , P3 , P4 >

Passo 4

  • è possibile soddisfare le richieste di P0
  • Alla fine dell’esecuzione P0 rilascia le risorse → Available = (7 5 5)
  • Sequenza sicura < P1 , P3 , P4, P0 >

Passo 5

  • è possibile soddisfare le richieste di P2
  • Alla fine dell’esecuzione P2 rilascia le risorse → Available = (10 5 7)
  • Sequenza sicura < P1 , P3 , P4 , P0 , P2 >

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 Pi richiede k istanze supplementari della risorsa Rj .

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 + Allocationi
  • 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, Pi è in deadlock.

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

Esempio di applicazione dell’algoritmo di rilevamento

  • Cinque processi, da P0 a P4;
  • tre tipi di risorse: A (7 istanze), B (2 istanze), e C (6 istanze);
  • Nella Figura a lato: Istantanea al tempo T0

La sequenza <P0, P2, P3, P1, P4 >

conduce a Finish[ i ] = true per tutti gli i.


Esempio di applicazione dell’algoritmo di rilevamento

  • P2 richiede un’istanza supplementare della risorsa C.
  • Stato del sistema?
    • Il sistema può riprendere le risorse possedute dal processo P0, ma il numero di risorse disponibili non è sufficiente a soddisfare gli altri processi
    • deadlock: processi P1, P2, P3, e P4.

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

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

  • 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