Esercizio - Algoritmo del banchiere su tre risorse con richieste (eserciziario, esercizio 4)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 4). Un sistema ha tre risorse $A, B, C$ con 10, 3 e 8 istanze. All'istante $t$ sono in esecuzione $P_0, P_1, P_2, P_3$ con le allocazioni e le richieste massime seguenti.

Con l'algoritmo del banchiere: (1) la sequenza $\langle P_0, P_1, P_2, P_3 \rangle$ è sicura? (2) $\langle P_0, P_2, P_1, P_3 \rangle$? (3) $\langle P_3, P_2, P_0, P_1 \rangle$? (4) $\langle P_3, P_1, P_2, P_0 \rangle$? (5) All'istante $t$ lo stato è sicuro? Se sì, quali richieste (da considerare indipendentemente, partendo dallo stato a $t$) possono essere soddisfatte: (6) $R_1 = (0,0,1)$, (7) $R_1 = (2,0,0)$, (8) $R_1 = (0,0,2)$? 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 (Allocation): somma per colonna $= (3+2+0+1,\ 1+0+2+0,\ 2+1+1+1) = (6, 3, 5)$.
• Disponibili $=$ totale $-$ assegnate $= (10-6,\ 3-3,\ 8-5) = (4, 0, 3)$.
• Necessità (Need $=$ Massimo $-$ Assegnate):

Domande 1-4: verificare una sequenza

Una sequenza è sicura se, partendo da Work = Disponibili, ogni processo ha Need <= Work al suo turno, e poi restituisce le risorse (Work += Allocation).

1. $\langle P_0, \dots \rangle$: $P_0$ ha bisogno di $(4,1,2)$ ma Work $= (4,0,3)$ e $1 > 0$ per $B$: non sicura. (Manca un'istanza di $B$.)
2. $\langle P_0, \dots \rangle$: lo stesso primo passo: non sicura.
3. $\langle P_3, P_2, P_0, P_1 \rangle$:

Sicura (alla fine Work $=$ totale delle risorse). 4. $\langle P_3, P_1, \dots \rangle$: dopo $P_3$ Work $= (5,0,4)$ ma $P_1$ ha bisogno di $(0,1,2)$ e $1 > 0$ per $B$: non sicura.

Domanda 5

Esiste almeno una sequenza sicura (quella del punto 3): lo stato a $t$ è sicuro.

Domande 6-8: richieste

Per ogni richiesta $R_1$ di $P_1$ si applica l'algoritmo di richiesta: (i) $R_1 \le Need_1 = (0,1,2)$? (ii) $R_1 \le Available = (4,0,3)$? (iii) simulare l'assegnazione e controllare la sicurezza.

• 6. $R_1 = (0,0,1)$. (i) sì; (ii) sì. Nuovo stato: Available $= (4,0,2)$, $Alloc_1 = (2,0,2)$, $Need_1 = (0,1,1)$. Si cerca un processo con $Need \le (4,0,2)$: solo $P_3$, $(2,0,1)$. Dopo di lui Work $= (5,0,3)$: $P_0$ vuole $B$ (1 > 0), $P_1$ vuole $B$, $P_2$ vuole 4 di $C$ (4 > 3). Nessuno può proseguire: stato non sicuro, la richiesta non va soddisfatta.
• 7. $R_1 = (2,0,0)$. (i) $2 > 0$ per $A$: supera la necessità $(0,1,2)$ del processo: richiesta non valida (errore, il processo eccede il massimo dichiarato). Le risorse ci sarebbero ($4 \ge 2$), ma la richiesta non si prende in considerazione.
• 8. $R_1 = (0,0,2)$. (i) $(0,0,2) \le (0,1,2)$ sì; (ii) $\le (4,0,3)$ sì. Nuovo stato: Available $= (4,0,1)$, $Need_1 = (0,1,0)$. Solo $P_3$, $(2,0,1) \le (4,0,1)$, può finire: Work $= (5,0,2)$. Nessun altro ($B$ manca a $P_0$ e $P_1$, $P_2$ vuole 4 di $C$): non sicuro, non soddisfacibile.

Quindi nessuna delle tre richieste aggiuntive può essere soddisfatta. (Verificato con un programma Python che applica gli algoritmi di sicurezza e di richiesta; i risultati coincidono con quelli del corso.)

Domande d'esame

Una richiesta può essere negata anche se le risorse sono disponibili? Traccia. Sì: il banchiere nega ($6$ e $8$) le richieste che porterebbero in stato non sicuro, anche se Request <= Available. Una richiesta oltre il massimo dichiarato ($7$) è invece un errore.