:: 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.
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:
Potete vedere anche voi che non sono presupposti da poco.
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.
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.
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.
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:
Per verificare che lo stato sia 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: