:: Sistemi operativi - Lezione del 1° aprile 2008 ::
Torna alla pagina di Sistemi Operativi
Lezione 3 - Tecniche per evitare il deadlock
Evitare il deadlock vuol dire che non faccio nemmeno partire un processo, se anche solo sento l'odore di un dl in arrivo. Però, devo anche cercare di non esagerare, altrimenti il mio sistema passerebbe la giornata ad evitare i dl, e i processi non andrebbero più avanti.
Occorre verificare a priori le richieste che 1 processo fa, e vedere se possono essere soddisfatte senza causare dl, tenendo conto dei processi già presenti nel systema.
Informazioni da avere a priori
Occorre sapere in anticipo alcune cose sui processi e sulle risorse, altrimenti tutti quello che diremo da qui in poi non può nemmeno accadere.
In particolare, dobbiamo basarci sul presupposto che il SO sa:
- il numero massimo di risorse che un processo andrà a chiedere;
- tutte le risorse già assegnate;
- il numero di risorse disponibili;
- la sequenza delle richieste e dei rilasci da parte di un processo.
Potete vedere anche voi che non sono presupposti da poco.
Stato sicuro
Uno stato è detto sicuro se il SO può allocare risorse a tutti i processi attualmente presenti in un ordine tale da non causare dl. Ho la garanzia che non ci saranno dl.
Uno stato è invece insicuro se non ho questa garanzia. Non è detto che cascherò inevitabilmente in un dl, anzi, probabilmente no, ma non ne ho la certezza.
Sequenza sicura
Una sequenza sicura è una sequenza di processi tale che le richieste di tutti sti processi possono essere soddisfatte con le risorse già disponibili o in via di rilascio dai processi precedenti ad ogni singolo i-esimo processo.
Uno stato è sicuro se esiste una sequenza sicura, il che vuol dire che il mio i-esimo processo non sta attendendo risorse da in processo con indice maggiore di i, ma solo da processi con indice minore di i.
Per passare da uno stato sicuro ad un altro stato sicuro, bisogna controllare bene ogni richiesta che i processi fanno, e vedere se è possibile soddisfarla o meno rimanendo in uno stato sicuro.
Il grafo di allocazione delle risorse
Si usa quando ho risorse con istanze singole
È il nostro solito grafo, solo che aggiungiamo degli archi, detti archi di prenotazione, che indicano le risorse che un processò chiederà.
Ecco perché nei presupposti abbiamo messo la conoscenza a priori delle risorse che un processo vorrà avere in tutta la sua vita: altrimeni, non sarebbe possibile costruire degli archi di prenotazione!
Quindi, se trovo un ciclo sugli archi di prenotazione, allora quel processo sta facendo delle richieste che il SO non può soddisfare: vada da chi è più accondiscendente.
Algoritmo del banchiere
Quando ho risorse con istanze muliple, il grafo non va più bene, quindi devo usare questo algoritmo, che nel nome si rifà al fatto che un banchiere prima di prestare soldi ci pensa su bene.
Per funzionare, questo algoritmo deve mantenere alcuni dati:
- m = numero risorse; n = numero processi
- available[1...m]: ogni i-esima posizione dice quante risorse del tipo i sono ancora disponibili
- max[1...n, 1...m]: una matrice che dice quante risorse al max un processo può chiedere
- allocation[1...n, 1...m]: una matrice che dice quale processo sta usando quale risorsa
- need[1...n, 1...m]: una matrice che dice quante risorse un processo chiederà nella sua vita
Per verificare che lo stato sia sicuro:
- creo due vettori ausiliari, work[1...m] e finish[1...n]
- work = available; finish[1...n] = false
- cerco il processo i tale che finish[i] sia false, e che la sua riga nella matrice need contenga risorse <= a quelle indicate in work. Se esiste, vado al punto 3, se no al punto 4.
- work = work + allocation[i]; finish[i] = true. Torno al punto 2
- Se, per ogni i, Finish[i] è true, allora lo stato è sicuro.
In pratica questo algoritmo dice che, se un processo può finire con le risorse disponibili, allora queste risorse saranno disponibili per i processi che seguiranno.
Poi, quando arriva una richiesta, faccio queste azioni:
- Request[i] contiene le richieste del processo i
- Se Request[i] <= Need[i], vado al passo 2. Se no vuol dire che il processo chiede di più di quanto dichiarato, e quindi ha barato.
- Se Request[i] <= Available, allora vado al passo 3, perché vuol dire che in teoria ho risorse per soddisfarlo. Se no, lo metto in attesa.
- Faccio la simulazione di un'allocazione di risorse al processo. Se va a buon fine, ok, lo aggiungo, altrimenti lo metto in attesa.
Torna alla pagina di Sistemi Operativi
