L’uso di un numero ridotto di risorse, da parte di un numero elevato di processi, può portare alla formazione di un Deadlock e al successivo blocco del sistema. Tutti i sistemi operativi hanno la capacità (temporanea) di garantire ad un processo l’uso esclusivo di una risorsa, questo potere è necessario per evitare che i processi (interessati all’uso della stessa risorsa) continuino a rubarsela impedendo di fatto il completamento delle reciproche operazioni.

In questo capitolo analizzeremo alcuni algoritmi di rilevamento e di risoluzione dei deadlock, tra cui:

  • Algoritmo di ricerca dei grafi RAG;
  • L’algoritmo del Banchiere.

Formazione di un Deadlock

Analizziamo con questo esempio il processo di formazione di un deadlock:

  • P_1 sta utilizzando la risorsa R_1 e quindi la sta tenendo occupata;
  • Per poter terminare il suo lavoro e quindi sbloccare la risorsa R_1 , P_1 chiede di poter usare la risorsa R_2 ;
  • R_2 è però in uso da P_2 ;
  • Per poter terminare il proprio lavoro P_2 chiede di poter usare R_1 .
Esempio di grafo RAG
Grafo RAG sull’utilizzo delle risorse

Risorse

Una grossa fetta dei deadlock coinvolge l’uso delle risorse, per questo motivo ci concentreremo principalmente su questi ultimi. Un deadlock sulle risorse si verifica quando un processo detiene l’uso esclusivo di una risorsa (es la memoria). Una risorsa può essere un dispositivo hardware: un disco, una stampante; oppure una locazione di memoria: una certa variabile condivisa. Per ogni risorsa possono essere disponibili una o più istanze, ad esempio un computer che possiede più GPU o CPU.

Le risorse si dividono in prelazionabili (preemptable) o non prelazionabili: le risorse prelazionabili possono essere espropriate da un processo all’altro senza causare errori al sistema, questo non è invece possibile per le risorse non prelazionabili. Un esempio di risorsa non prelazionabili è il masterizzatore DVD, interrompere una masterizzazione in corso causa inevitabilimente la bruciatura del supporto (che dovrà essere buttato).

In genere le risorse non possono essere utilizzate da più processi contemporaneamente, in questi casi ad ogni risorsa viene associato un semaforo che ne gestisce l’accesso. Al contrario ogni processo può invece riservarsi l’uso di più risorse, agendo in modo sequenziale.