|
|
L'Algoritmo del banchiere è utilizzato per prevenire i Deadlock nell'allocazione delle risorse. In particolare questo algoritmo può indicare se un sistema (in particolare un Sistema operativo) si venga a trovare in uno stato sicuro o meno nel caso assegnasse una risorsa ad uno dei processi richiedenti. La Complessità computazionale di questo algoritmo è O(n2m), dove n è il numero di processi e m il numero di tipi di risorse (per ogni tipo possono essere disponibili più risorse - per esempio, due stampanti equivalenti). Un sistema, nell'allocare le risorse che vengono richieste, deve procedere come farebbe una Banca. La similitudine vuole che i processi vengano visti come i clienti che possono richiedere del credito presso la banca (fino ad un certo limite individuale) e che le risorse allocabili siano appunto soldi. È chiaro che il sistema, come la banca, non può permettere a tutti i clienti di raggiungere il loro limite di credito contemporaneamente poiché in tal caso la banca fallirebbe (e il sistema non potrebbe allocare risorse a sufficienza, causando un Deadlock). Si utilizzano 4 strutture dati di tipo Array per memorizzare le seguenti informazioni:
Disponibili [m]: memorizza la quantità di ogni tipo di risorsa disponibile nel sistema
Allocate [m x n]: memorizza quante risorse per ogni tipo sono state allocate ad ognuno dei processi.
Massimo [m x n]: indica la quantità risorse che un processo allocherà al massimo.
Necessità [m x n]: necessità residua di risorse per ogni processo (calcolata sottraendo alla matrice Massimo la matrice Allocate).
L'algoritmo procede iterativamente, garantendo le risorse necessarie ai processi che, confrontando il loro array di Necessità con quello della risorse attualmente disponibili nel sistema, possono terminare la loro esecuzione. A esecuzione terminata, il processo libera le risorse che aveva già precedentemente allocato (ossia, l'array di risorse Allocate al processo viene sommato alle risorse disponibili). In tal modo l'algoritmo può selezionare un ulteriore processo che, con le risorse attualmente disponibili al sistema, può terminare e rilasciare a sua volta le risorse allocate. L'algoritmo può decidere che il sistema si trovi in uno Stato sicuro se, attraverso i suoi tentativi ripetuti di trovare un ordine di esecuzione dei processi, scopre una sequenza per cui a tutti gli n processi vengono allocate le risorse concludendo la loro esecuzione. Gli step dell’ algoritmo possono essere descritti nel seguente modo:
Si cerca nella matrice NEC un processo le cui richieste ancora da soddisfare sono ordinatamente tutte minori delle componenti di DISP: se non si trova alcun processo, il sistema e’ in stato di stallo, dato che nessun processo può arrivare a completarsi;
Si immagina che il processo individuato in 1. riceva le risorse di cui ha ancora bisogno e si completi: il processo viene segnato come completato e si determina il nuovo vettore DISP sommando alle risorse precedentemente disponibili tutte quelle possedute dal processo che può completarsi;
Si ripetono i passi 1. e 2. sino a che o tutti i processi sono segnati come terminati, nel qual caso lo stato di partenza era sicuro, o si arriva ad uno stallo, nel qual caso lo stato di partenza era insicuro.
Si consideri il seguente esempio. Un sistema deve gestire 5 processi che utilizzano 3 tipi di risorse, A, B, e C.
Le matrici ALL, MAX e NEC ed il vettore DISP sono riportati, gli altri due vettori risultano ESISTenti=(10, 5, 7) e ASSegnate=(7, 2, 5). Si può verificare che lo stato è sicuro, per es. esaminando i processi nell’ordine P1, P3, P4, P2, P0. Val la pena di notare che questo algoritmo ha una applicabilità limitata sia perché difficilmente i processi conoscono le proprie esigenze massime di risorse, sia perchè l’insieme di processi da gestire cambia nel tempo, sia infine perchè delle risorse possono diventare non utilizzabili (per es. per guasti).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.