Esercizio - Assegnare risorse a un processo e mantenere lo stato sicuro (eserciziario, esercizio 117)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD, esercizio 117). Dato il sistema seguente (in stato sicuro), si determini se l'assegnazione di 6 istanze aggiuntive di $C$ a $P_3$ garantisce il mantenimento dello stato sicuro. 4 processi $P_1..P_4$; 3 tipi di risorse: $A$ (5 istanze), $B$ (8), $C$ (16).

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 →.

Stato di partenza

Assegnate in totale: $A$: $0+2+1+1 = 4$; $B$: $1+0+2+0 = 3$; $C$: $4+1+1+3 = 9$. Available $= (5-4,\ 8-3,\ 16-9) = (1, 5, 7)$.

Need $=$ Massimo $-$ Assegnate: $P_1 = (4,0,0)$, $P_2 = (1,1,3)$, $P_3 = (4,5,12)$, $P_4 = (0,1,3)$.

Lo stato è sicuro (come dice il testo): sequenza $\langle P_2, P_4, P_1, P_3 \rangle$: $P_2$ ($(1,1,3) \le (1,5,7)$) $\to$ Work $(3,5,8)$; $P_4$ ($(0,1,3)$) $\to (4,5,11)$; $P_1$ ($(4,0,0)$) $\to (4,6,15)$; $P_3$ ($(4,5,12)$) $\to (5,8,16)$.

Assegnazione di 6 istanze di $C$ a $P_3$

Controllo la richiesta $(0,0,6)$: $\le Need_3 = (4,5,12)$ sì; $\le Available = (1,5,7)$ sì. Si simula:

• $Alloc_3 = (1,2,7)$ (la riga di $P_3$ diventa 1 2 7);
• Available $= (1,5,1)$;
• $Need_3 = (4,5,6)$.

Tutti i bisogni ora: $P_1 = (4,0,0)$, $P_2 = (1,1,3)$, $P_3 = (4,5,6)$, $P_4 = (0,1,3)$.

Si cerca un processo con $Need \le (1,5,1)$:

• $P_1$: $A$: $4 > 1$, no;
• $P_2$: $C$: $3 > 1$, no;
• $P_3$: $A$: $4 > 1$, no;
• $P_4$: $C$: $3 > 1$, no.

Nessun processo può terminare: stato non sicuro. Quindi l'assegnazione non garantisce il mantenimento dello stato sicuro e non va fatta; $P_3$ attende. (Il corso spiega: $P_1$ chiede 4 di $A$ ma ne resta 1; tutti gli altri chiedono più di 1 istanza di $C$ e ne rimane una sola.)

Verificato con un programma Python.

Domande d'esame

Si può dare a $P_3$ solo 2 istanze di $C$? Traccia. Con $(0,0,2)$: Available $= (1,5,5)$, $Need_3 = (4,5,10)$. $P_2$ ($(1,1,3) \le (1,5,5)$) finisce: $(3,5,6)$, $P_4$: $(4,5,9)$, $P_1$: $(4,6,13)$, $P_3$ ($(4,5,10)$): sì, stato sicuro. La quantità conta: 6 sì rompe, 2 no.