Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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