Abbiamo visto come sia possibile prevenire lo stallo mettendo in atto alcune strategie che negano una delle condizioni necessarie allo stallo. Tramite tali strategie, lo stallo non può formarsi. Vediamo ora come sia possibile, invece, controllare a run-time lo stallo.
Per poter controllare ed evitare la formazione degli stalli a run-time l’idea è di consentire l’assegnamento delle risorse solo nel caso in cui il sistema possa garantire che tale assegnamento non porterà a una situazione di stallo.
Grafo di assegnazione
Per svolgere un controllo è necessario mantenere lo stato degli assegnamenti delle risorse a processi e thread e delle richieste di risorse da parte di processi e thread. Il grafo di assegnazione mantiene proprio tale informazione. Il grafo è composto da 2 tipi di nodi: processi/thread (P) e risorse (R). Esistono tre tipi di arco che connettono un processo/thread a una risorsa:
P ← R : La risorsa R è assegnata al processo P
P → R : Il processo P chiede la risorsa R
P ⇢ R : Il processo P potrà chiedere in futuro la risorsa R
Una risorsa può offrire una o più istanze. La molteplicità viene rappresentata indicando all’interno del nodo un • per ogni istanza presente. Ad esempio:
rappresenta una situazione in cui:
- Le risorse R1 e R2 hanno ognuna una singola istanza
- La risorsa R1 è assegnata a P2 e la risorsa R2 è assegnata a P1
- Il processo P1 chiede la risorsa R1
- Il processo P3 chiede la risorsa R2
Nell’esempio successivo:
in aggiunta rispetto all’esempio precedente, abbiamo:
- Una ulteriore risorsa R1 assegnata a P3
- Una possibile richiesta futura da parte di P2 della risorsa R2. Questa richiesta non è stata effettuata ma il grafo indica la possibilità che tale richiesta avvenga in futuro
Grafo sicuro
Un grafo di assegnazione è sicuro se è privo di stallo anche considerando le richieste future. Come si fa a decidere se, dato un grafo, esiste una situazione di stallo?
- Se c’è una sola istanza per risorsa: stallo ⇔ ∃ ciclo nel grafo;
- Se ci sono più istanze per risorsa (caso generale): stallo ⇒ ∃ ciclo nel grafo;
Quindi nel primo caso è sufficiente verificare se il grafo è ciclico. Nel secondo caso, invece, ci serve un algoritmo diverso che vedremo in seguito.
Algoritmo con grafo di assegnazione
Vediamo prima il caso con una sola istanza per risorsa, in cui l’individuazione di uno stallo equivale alla ricerca di un ciclo nel grafo.
L’algoritmo funziona nel modo seguente. Per ogni richiesta di risorsa, se la risorsa non è disponibile il processo attende, altrimenti:
- Simula, sul grafo, l’assegnamento della risorsa al processo
- Verifica se il grafo contiene uno stallo (in questo caso se è presente un ciclo), considerando anche tutte le richieste future
- In caso di stallo: il processo viene messo in attesa della risorsa
- Altrimenti: la risorsa viene assegnata e la modifica sul grafo viene confermata
Esempio: Filosofi a cena
Consideriamo il problema dei filosofi a cena. Possiamo rappresentarlo nel modo seguente:
Se il filosofo 0 chiede la bacchetta di sinistra dobbiamo simulare l’assegnamento:
Vediamo che nel grafo non c’è nessun ciclo e quindi nessuno stallo, nemmeno considerando tutte le richieste future. Possiamo quindi assegnare la risorsa e procedere. Il caso interessante si verifica quando quattro filosofi ricevono la bacchetta sinistra (in quanto non genera cicli) e anche il quinto filosofo chiede la propria bacchetta sinistra. Simulando l’assegnamento otteniamo:
Vediamo che l’assegnamento della bacchetta a F4 va a formare un ciclo. In questo caso il processo viene messo in attesa:
Vediamo quindi che la situazione di stallo viene evitata in quanto F3 può richiedere la bacchetta destra e iniziare a mangiare.
Algoritmo del banchiere
Nel caso generale in cui abbiamo più istanze per ogni risorsa non possiamo più utilizzare la presenza di cicli come criterio per individuare potenziali stalli. L’esempio seguente mostra un grafo in cui non c’è stallo ma è presente un ciclo:
P2 può rilasciare la risorsa R2 che può essere assegnata a P0 che a sua volta libererà R1 per P1. Intuitivamente i processi possono “terminare” nella sequenza <P2,P0,P1>. In questo caso diciamo che tale sequenza è una sequenza “sicura” o di “terminazione”.
Più precisamente una sequenza <P1,P2, …, Pi, …, Pk> di processi è una sequenza sicura se ogni processo Pi nella sequenza può ottenere tutte le risorse che necessita (incluse quelle future) da quelle disponibili inizialmente più quelle possedute dai processi che lo precedono nella sequenza, cioè dai processi Pj tali che j < i. Intuitivamente una sequenza sicura è una sequenza che permette ai processi di ottenere tutte le risorse che necessitano e quindi di rilasciarle a vantaggio dei processi successivi.
Per computare se esiste almeno una sequenza sicura si può utilizzare il seguente algoritmo:
- Cerca un processo che possa ottenere tutte le risorse necessarie (incluse quelle future) da quelle disponibili. Se tale processo non c’è l’algoritmo fallisce (non esiste una sequenza sicura)
- Rilascia tutte le risorse possedute dal processo, aggiungilo alla sequenza sicura e toglilo dal grafo
- Se ci sono ancora processi nel grafo vai al punto 1, altrimenti dai in output la sequenza sicura
L’algoritmo del banchiere è identico all’algoritmo con grafo di assegnazione ma utilizza la non esistenza di una sequenza sicura per individuare potenziali stalli:
Per ogni richiesta di risorsa, se la risorsa non è disponibile il processo attende, altrimenti:
- Simula, sul grafo, l’assegnamento della risorsa al processo
- Verifica se il grafo contiene uno stallo (se non esiste una sequenza sicura), considerando anche tutte le richieste future.
- In caso di stallo: il processo viene messo in attesa della risorsa
- Altrimenti: la risorsa viene assegnata e la modifica sul grafo viene confermata
Esempio
Consideriamo il seguente esempio in cui P2 ha già assegnata una risorsa di tipo R1 (di cui esistono 2 istanze) e tutte le richieste future dei vari processo sono indicate con le frecce tratteggiate:
Supponiamo che i processi richiedano le risorse nel seguente ordine:
- P1 chiede R1
- P3 chiede R2
- P1 chiede R2
- P2 chiede R2
Se non effettuiamo nessun controllo dello stallo e tutti i processi chiedono tutte le risorse disponibili è possibile raggiungere la seguente situazione che non ammette nessuna sequenza sicura e rappresenta quindi una situazione di stallo:
Analizziamo, invece, un assegnamento alla volta, applicando l’algoritmo del banchiere.
P1 chiede R1. Se simuliamo l’assegnamento otteniamo:
< P1,P2,P3 > è una sequenza sicura in quanto P1 può ottenere R2, rilasciando le proprie risorse permette a P2 di ottenere R2, che a sua volta può rilasciare le risorse permettendo a P3 di ottenere R1 e R2. Procediamo quindi con l’assegnamento.
P3 chiede R2. Se simuliamo l’assegnamento otteniamo:
In questo caso nessuno dei tre processi può ottenere tutte le risorse necessarie e quindi non esiste una sequenza sicura. L’algoritmo del banchiere mette P3 in attesa:
Se procediamo con le richieste di P1 e P2 giungiamo in questa situazione:
in cui <P1,P2,P3> è sempre una sequenza sicura e, di conseguenza, non è presente uno stallo. Abbiamo quindi visto come l’algoritmo del banchiere sia in grado di evitare, a run-time, la formazione di stalli.
Esercizio
Applicare l’algoritmo del banchiere ai casi 1 e 2 dell’esercizio 2 di questo compito.