Esercizio - Algoritmo del banchiere su quattro risorse (eserciziario, esercizio 5)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 5). Un sistema ha quattro risorse $A, B, C, D$ con 8, 2, 7, 2 istanze, allocate all'istante $t$ a $P_0, \dots, P_4$:

Con $R_i = (a,b,c,d)$ richiesta di $P_i$ (ognuna considerata indipendentemente): (1) $R_0 = (1,0,1,0)$; (2) $R_1 = (1,0,0,0)$; (3) $R_2 = (0,0,1,0)$; (4) $R_3 = (1,1,0,0)$; (5) $R_2 = (0,0,2,0)$. Quali sono soddisfacibili? Alla luce delle risposte, lo stato all'istante $t$ è sicuro? Teoria: Deadlock - condizioni, prevenzione, evitamento e rilevamentoUn deadlock (stallo) è una situazione in cui un insieme di processi attende all'infinito risorse possedute da altri processi dello stesso insieme; può verificarsi solo se valgono insieme quattro condizioni (mutua esclusione, hold and wait, assenza di prelazione, attesa circolare); il grafo di allocazione delle risorse (archi di richiesta P->R e di assegnazione R->P) senza cicli esclude lo stallo, con un ciclo lo implica se ogni risorsa ha una sola istanza, e lo rende solo possibile se ha più istanze; si può prevenire (negare una delle quattro condizioni, per esempio ordinare le risorse per negare l'attesa circolare), evitare (stato sicuro: esiste una sequenza sicura; algoritmo del grafo con archi di rivendicazione per istanza singola, algoritmo del banchiere con Available, Max, Allocation, Need = Max - Allocation e complessità O(m n^2) per istanze multiple), rilevare e ripristinare (grafo wait-for per istanza singola, algoritmo di rilevamento per istanze multiple; terminazione dei processi o prelazione delle risorse con scelta della vittima e rollback), oppure ignorare.Deadlock - condizioni, prevenzione, evitamento e rilevamento →.

Strutture dati

Assegnate in totale: $(1+2+1+0+3,\ 0+0+1+1+0,\ 1+0+1+2+1,\ 1+0+0+0+1) = (7, 2, 5, 2)$; Available $= (8,2,7,2) - (7,2,5,2) = (1,0,2,0)$.

Need $=$ Massimo $-$ Assegnate:

Lo stato a $t$ è sicuro?

Prima di valutare le richieste si verifica la sicurezza dello stato di partenza. Si prova $\langle P_4, P_2, P_1, P_0, P_3 \rangle$:

Lo stato è sicuro. (Ogni passo restituisce le risorse; alla fine Work è uguale al totale.)

Le cinque richieste

1. $R_0 = (1,0,1,0)$. Controllo $R \le Need_0 = (0,1,0,1)$: $1 > 0$ per $A$ e per $C$. Richiesta non valida ($P_0$ eccede il massimo dichiarato).
2. $R_1 = (1,0,0,0)$. $\le Need_1 = (1,1,0,1)$ sì; $\le Available = (1,0,2,0)$ sì. Simulazione: Available $= (0,0,2,0)$, $Need_1 = (0,1,0,1)$. Nessun processo ha $Need \le (0,0,2,0)$: $P_0$ e $P_1$ vogliono $B$ e $D$, $P_2$ vuole $D$, $P_3$ vuole $A$ e $B$, $P_4$ vuole $A$. Stato non sicuro: non soddisfacibile.
3. $R_2 = (0,0,1,0)$. $\le Need_2 = (0,0,2,1)$ sì; $\le (1,0,2,0)$ sì. Simulazione: Available $= (1,0,1,0)$, $Need_2 = (0,0,1,1)$. Con il massimo scritto nel testo ($P_4$ può chiedere 3 di $C$) $Need_4 = (1,0,2,0)$ e $2 > 1$ per $C$: nessun processo può finire (a $P_0$, $P_1$ servono $B$; a $P_2$ serve $D$; a $P_3$ serve $B$): stato non sicuro, non soddisfacibile.
   • Discrepanza nel materiale del corso. La soluzione del corso dice che questa richiesta è soddisfacibile, con la sequenza sicura $\langle P_4, P_2, P_0, P_1, P_3 \rangle$: perché usa $Need_4 = (1,0,1,0)$, cioè un massimo di $P_4$ per $C$ pari a 2 invece di 3. Il corso lo ammette in una nota ("nelle soluzioni si considera come valore Massimo di $P_4$ in $C$ non 3 ma 2"). Con il testo scritto (3) la risposta è no; con 2 è sì.
4. $R_3 = (1,1,0,0)$. $\le Need_3 = (1,1,0,0)$ sì, ma $(1,1,0,0) \le (1,0,2,0)$ no ($B$: 1 > 0). $P_3$ deve attendere (risorse non disponibili).
5. $R_2 = (0,0,2,0)$. $\le Need_2$ sì; $\le Available$ sì. Simulazione: Available $= (1,0,0,0)$, $Need_2 = (0,0,0,1)$. Solo i processi che non chiedono $B$, $C$, $D$ potrebbero finire: nessuno ha $Need \le (1,0,0,0)$ ($P_4$ vuole 2 di $C$, $P_2$ vuole 1 di $D$). Non sicuro: non soddisfacibile.

Ultima domanda. Non ha senso valutare la sicurezza dello stato a $t$ in base al fatto che le richieste risultino o meno soddisfacibili: lo stato a $t$ è sicuro, come verificato all'inizio, e una richiesta rifiutata non lo rende insicuro (viene solo fatta attendere).

Tutti i calcoli sono stati ricontrollati con un programma Python.

Domande d'esame

Prima di valutare una richiesta, perché si controlla che lo stato corrente sia sicuro? Traccia. L'algoritmo di richiesta assume che lo stato di partenza sia sicuro: se non lo fosse, nessuna assegnazione potrebbe garantire di non cadere in deadlock.