- Work[m] = Available; Finish[n] = false per ogni 0 < i < n
- Si cerca una i tale per cui:
- Finish[i] == false;
- Needi <= Work (l'i-esima riga di Need è <= del vettore Work)
- Se non esiste una i che soddisfa ciò passo al punto 4
- Work = Work + Allocationi; Finish[i] = true; vado al punto 2
- Se per ogni i, Finish[i] è true, allora sono in uno stato sicuro.
Quello che succede è che per ogni processo controllo se ha abbastanza risorse per soddisfare tutte le sue richieste passate e future.
Le risorse le cerco in 2 punti:
- tra quelle libere
- tra quelle dei processi che vengono prima di lui (vedi definizione di stato sicuro)
Se ogni processo può avere tutte le risorse che chiede (Finish[i] = true, per ogni i), allora sono in uno stato sicuro.
Complessità: O(m * n2)
8.5.3.2 L'algoritmo di richiesta delle risorse
Request[m] è il vettore delle richieste dell'i-esimo processo.
- Se Requesti <= Needi vai al punto 2; altrimenti errore (il processo richiede più di quanto dichiarato in partenza)
- Se Requesti <= Available, vai al punto 3; altrimenti il processo attende (chiede ciò che non può ancora ottenere)
- Il sistema alloca al processo le risorse richieste modificando così lo stato:
- Available = Available - Requesti
- Allocationi = Allocationi + Requesti
- Needi = Needi - Requesti
- se questo stato è sicuro (verifico con l'algoritmo di prima), allora lo confermo. Altrimenti il processo deve attendere, e torno allo stato precedente.
8.6 Rilevazione del deadlock
Il SO lascia accadere i deadlock, ma cerca di rilevarli e poi di porvi rimedio.
Occorre
- un algoritmo che rilevi il deadlock
- un algoritmo che recuperi dallo stato di deadlock
Anche in questo caso, i comportamenti sono diversi a seconda che si abbiano risorse ad istanze singole o multiple.
8.6.1 Singola istanza di ogni tipo di risorsa
Grafo wait-for = variazione del grafo di allocazione delle risorse
- i nodi delle risorse collassano, rimangono quelli dei processi
- un arco da un processo A ad un proceso B indica che A vuole una risorsa posseduta da B
Mantengo il grafo ad ogni richiesta di risorse.
Controllo periodicamente che non ci siano cicli in questo grafo. Se ci sono cicli, è possibile un deadlock.
Complessità: O(n2)
8.6.2 Istanze multiple di un tipo di risorsa
Uso strutture dati simili a quelle dell'algoritmo del banchiere.
Come prima, m è il numero di tipi di risorse, n è il numero dei processi.
- Available[m] = istanze disponibili per ogni tipo di risorsa
- Allocation[n*m] = ogni riga dice quante risorse sono allocate a quel processo
- Request[n*m] = ogni riga indica quante risorse quel processo chiede
- Work[m] = Available; Finish[i] = false se Allocationi = 0, altrimenti Finish[i] = true
- Cerco una i tale che
- Finish[i] == false
- Requesti <= Work
- Se non esiste, vado al punto 4
- Work = Work + Allocationi; Finish[i] = true; vado al punto 2
- Se c'è una Finish[i] == false, allora sono in uno stato di deadlock, e il processo Pi è in stallo
Questo algoritmo all'inizio indica tutti i processi come adatti alla terminazione (Finish[i] = true) se non hanno nessuna risorsa allocata: niente risorse, niente deadlock. Altrimenti, Finish[i] = false.
Poi, analizzo tutte le richieste per ogni processo. Se sono soddisfacibili, allora stabilisco che le risorse di quel processo saranno utilizzabili da altri processo (Work = Work + Allocationi), e che quel processo potrà terminare.
Se c'è qualche processo che, alla fine, è indicato come impossibilitato a terminare, vuol dire che c'è un deadlock nel sistema, e che quel processo è in stallo.
La scelta del punto 3 si spiega in questo modo: se un processo ha le risorse che vuole, suppongo ottimisticamente che potrà finire tranquillamente. Se ciò non accadrà, una successiva passata dell'algoritmo lo rileverà comunque.
Complessità = O(m x n2)
8.6.3 Uso dell'algoritmo di rilevazione
La frequenza con cui invocare questo algoritmo dipende da 2 fattori:
- quanto spesso si verifica un deadlock nel sistema
- quanti processi sono coinvolti in un deadlock, quando questo accade
Se i deadlock sono frequenti, allora l'algoritmo andrebbe invocato frequentemente.
Caso limite = invocarlo ogni volta che c'è una richiesta di allocazione non immediatamente soddisfacibile (quindi, una dipendenza da altri processi).
Questo algoritmo genera overhead => costoso eseguirlo sempre => posso eseguirlo eg solo quando l'uso della CPU scende sotto il 40%, perché i deadlock tendono a paralizzare il sistema.
8.7 Ripristino dal deadlock
Quando è stato rilevato un deadlock, posso
- far intervenire l'operatore
- decidere automaticamente che cosa fare
- abortisco uno o più processi finché il dl non scompare
- preemptivo alcuni processi per riprendermi delle risorse.
8.7.1 Termine del processo
Posso
- Abortire tutti i processi in deadlock => molto costoso, perché posso fermare anche processi che non c'entrano e che magari erano a buon punto
- Abortirne uno alla volta finché il deadlock non scompare => molto overhead dovuto alla ripetizione, ad ogni uccisione, dell'algoritmo di rilevazione
Per decidere quale processo uccidere, posso scegliere tra diversi criteri, eg priorità, interattività etc. => si sceglie quello la cui morte, in base al criterio scelto, sia di costo minimo.
8.7.2 Rilascio anticipato delle risorse
Tolgo le risorse a qualcuno e le do a qualcun altro.
- Scelta della vittima, in base a fattori di costo (tempo già consumato, numero di risorse in uso etc.)
- Rollback = annullare le modifiche eseguite dal processo in corso
- Starvation = se mi si ripresenta una situazione uguale, e uccido con lo stesso criterio, sempre lo stesso processo verrà ucciso => starvation di quel processo => includo nel fattore costo il numero di rollback eseguiti.
