Esercizio - Grafo di allocazione delle risorse e individuazione dei cicli (eserciziario, esercizi 20, 21, 56, 106 e 109)

Testo (eserciziario del corso di Sistemi Operativi, Ing. Informatica UniPD). Convenzione dei grafi: processi come cerchi, risorse come rettangoli (un punto per istanza); arco di richiesta $P \to R$, arco di assegnazione $R \to P$, arco di richiesta futura (rivendicazione) tratteggiato $P \dashrightarrow R$. Per cercare un ciclo in un grafo diretto si veda Grafi diretti e ordinamento topologicoGrafi diretti (archi orientati, grado entrante e uscente, cammini e cicli diretti), visite su grafi diretti e tipi di archi; DAG; ordinamento topologico con l'algoritmo basato sui gradi entranti e con la DFS (reverse postorder), correttezza e costo Theta(n+m); esempio svolto.Grafi diretti e ordinamento topologico → e Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →. 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 →.

• Esercizio 20. Sette processi $P_1..P_7$ e sei risorse $R_1..R_6$, ognuna con una sola istanza. Stato: $P_1$ usa $R_1$ e $R_2$; $P_2$ è in attesa di $R_3$; $P_3$ attende $R_2$; $P_4$ usa $R_4$ e attende $R_2$ e $R_3$; $P_5$ usa $R_3$ e attende $R_5$; $P_6$ usa $R_6$ e attende $R_3$; $P_7$ usa $R_5$ e attende $R_4$. Il sistema è in deadlock?
• Esercizio 21. Sette processi, sei risorse a istanza singola. Stato a $t$: $P_1$ attende $R_1$; $P_2$ usa $R_3$ e $R_4$; $P_3$ usa $R_1$ e attende $R_3$; $P_4$ attende $R_3$; $P_5$ attende $R_4$ e $R_5$; $P_6$ usa $R_2$; $P_7$ usa $R_5$ e attende $R_4$. Inoltre $P_1$ e $P_2$ dichiarano che in futuro accederanno a $R_6$, e $P_5$ che accederà a $R_3$. Domande: (1) disegnare il grafo (assegnazione, richiesta e richiesta futura) e mostrare che non c'è deadlock; (2) come si gestisce a $t$ una richiesta di $P_1$ per $R_6$; (3) una richiesta di $P_5$ per $R_3$; (4) una richiesta di $P_1$ per $R_2$; (5) una richiesta di $P_2$ per $R_6$.
• Esercizio 56. Quattro processi $P_1..P_4$ e quattro risorse: $R_1, R_2, R_3$ a istanza singola, $R_4$ con 3 istanze. Allocazioni e massimi (colonne $R_1..R_4$): $P_1$ assegnate $(0,0,0,1)$ massimo $(1,0,0,1)$; $P_2$ $(0,0,0,1)$, $(0,1,1,1)$; $P_3$ $(1,0,1,0)$, $(1,0,1,1)$; $P_4$ $(0,1,0,0)$, $(0,1,0,1)$. Il sistema è in deadlock? Con il banchiere, si può soddisfare una richiesta di $P_3$ di $R_4$?
• Esercizio 106. Sette processi $P_1..P_7$ e sei risorse $R_1..R_6$, ciascuna in singola istanza e ad accesso mutuamente esclusivo. Stato: $P_1$ occupa $R_1$ e richiede $R_2$; $P_2$ non occupa risorse e richiede $R_3$; $P_3$ occupa $R_2$; $P_4$ occupa $R_4$ e richiede $R_2$ e $R_3$; $P_5$ occupa $R_3$ e richiede $R_5$; $P_6$ occupa $R_6$ e richiede $R_2$; $P_7$ occupa $R_5$ e richiede $R_4$. Si determini con il grafo di allocazione se c'è stallo e quali processi e risorse sono coinvolti.
• Esercizio 109. Sette processi e nove risorse; solo $R_8$ ha 2 istanze. $P_1$ occupa $R_3$, richiede $R_1$; $P_2$ occupa $R_1$, richiede $R_4$; $P_3$ occupa una istanza di $R_8$; $P_4$ richiede $R_1$; $P_6$ occupa $R_6$ e $R_8$, richiede $R_3$; $P_7$ occupa $R_4$, richiede $R_9$; $P_9$ occupa una istanza di $R_8$ e $R_9$, richiede $R_6$. Si determini con il grafo di allocazione se il sistema è in stallo, motivando per tutti i cicli; se c'è deadlock, quali processi e risorse sono coinvolti. (Nota: l'elenco è un'istantanea, non una sequenza cronologica: "$P_1$ richiede $R_1$" significa che $R_1$ non è assegnata a $P_1$.)

Esercizio 20

Archi di assegnazione $R \to P$: $R_1 \to P_1$, $R_2 \to P_1$, $R_4 \to P_4$, $R_3 \to P_5$, $R_6 \to P_6$, $R_5 \to P_7$. Archi di richiesta $P \to R$: $P_2 \to R_3$, $P_3 \to R_2$, $P_4 \to R_2$, $P_4 \to R_3$, $P_5 \to R_5$, $P_6 \to R_3$, $P_7 \to R_4$.

Ricerca di un ciclo seguendo gli archi da un processo "in attesa": $P_4 \to R_3 \to P_5 \to R_5 \to P_7 \to R_4 \to P_4$. È un ciclo: $P_4$ attende $R_3$, posseduta da $P_5$; $P_5$ attende $R_5$, posseduta da $P_7$; $P_7$ attende $R_4$, posseduta da $P_4$. Tutte le risorse hanno una sola istanza, quindi il ciclo è sufficiente: deadlock tra $P_4, P_5, P_7$.

Gli altri processi: $P_2$ e $P_6$ aspettano $R_3$ (posseduta dal deadlock): sono bloccati indirettamente ma non nel ciclo; $P_3$ attende $R_2$, posseduta da $P_1$, che non attende nulla e prima o poi la rilascia: $P_3$ non è in stallo. Verificato con una ricerca dei cicli: il grafo contiene un solo ciclo.

Esercizio 21

Archi di assegnazione: $R_3 \to P_2$, $R_4 \to P_2$, $R_1 \to P_3$, $R_2 \to P_6$, $R_5 \to P_7$. Richiesta: $P_1 \to R_1$, $P_3 \to R_3$, $P_4 \to R_3$, $P_5 \to R_4$, $P_5 \to R_5$, $P_7 \to R_4$. Richiesta futura: $P_1 \dashrightarrow R_6$, $P_2 \dashrightarrow R_6$, $P_5 \dashrightarrow R_3$.

(1) Nessun deadlock. Il grafo (con i soli archi veri, senza quelli tratteggiati) non contiene cicli: i cammini sono $P_1 \to R_1 \to P_3 \to R_3 \to P_2$, $P_4 \to R_3 \to P_2$, $P_5 \to R_4 \to P_2$ e $P_5 \to R_5 \to P_7 \to R_4 \to P_2$, e $P_2$ non attende nessuno. Ordine di completamento possibile: $P_2$, poi $P_3$ e $P_7$, poi $P_1$, $P_4$, $P_5$. Con istanza singola, niente cicli = niente deadlock.

(2) Richiesta di $P_1$ per $R_6$ a $t$. $R_6$ è libera, ma assegnarla trasformerebbe $P_1 \dashrightarrow R_6$ in $R_6 \to P_1$ e creerebbe il ciclo $P_1 \to R_1 \to P_3 \to R_3 \to P_2 \dashrightarrow R_6 \to P_1$ (contando l'arco di richiesta futura $P_2 \dashrightarrow R_6$). Lo stato diventerebbe non sicuro: la richiesta non può essere soddisfatta, anche se la risorsa è disponibile; $P_1$ attende.

(3) Richiesta di $P_5$ per $R_3$. $R_3$ è già assegnata a $P_2$: non soddisfacibile, $P_5$ deve attendere (la richiesta è consentita perché esiste l'arco di richiesta futura).

(4) Richiesta di $P_1$ per $R_2$. Non esiste in $P_1$ un arco di richiesta futura verso $R_2$: la richiesta eccede quanto $P_1$ aveva dichiarato ed è non valida.

(5) Richiesta di $P_2$ per $R_6$. $R_6$ è libera e l'arco di richiesta futura esiste. Convertire $P_2 \dashrightarrow R_6$ in $R_6 \to P_2$ non crea cicli (da $P_2$ non partono archi di richiesta veri, e da $R_6$ l'unico arco va a $P_2$): la richiesta viene soddisfatta.

Esercizio 56

R4 ha tre istanze, quindi un ciclo non basta a concludere il deadlock. Si usa il banchiere (colonne $R_1..R_4$): totali $(1,1,1,3)$.

• Assegnate in totale $= (0+0+1+0,\ 0+0+0+1,\ 0+0+1+0,\ 1+1+0+0) = (1,1,1,2)$; Available $= (0,0,0,1)$.
• Need $=$ Massimo $-$ Assegnate: $P_1 = (1,0,0,0)$, $P_2 = (0,1,1,0)$, $P_3 = (0,0,0,1)$, $P_4 = (0,0,0,1)$.

Sequenza di sicurezza:

La sequenza $\langle P_3, P_1, P_4, P_2 \rangle$ è sicura: nessun deadlock.

Richiesta di $P_3$ per $R_4$, cioè $(0,0,0,1)$: $\le Need_3 = (0,0,0,1)$ sì; $\le Available = (0,0,0,1)$ sì. Nuovo stato: Available $= (0,0,0,0)$, $Alloc_3 = (1,0,1,1)$, $Need_3 = 0$. $P_3$ può finire subito e restituire $(1,0,1,1)$, e da lì in poi la stessa sequenza funziona ($P_1$, $P_4$, $P_2$): lo stato resta sicuro e la richiesta può essere soddisfatta. Il materiale del corso aggiunge che il testo della slide parla di "deadlock" per un grafo con più cicli come $P_2, R_2, P_4, R_4$: con $R_4$ a più istanze quel ciclo è solo necessario, non sufficiente.

Esercizio 106

Archi di assegnazione: $R_1 \to P_1$, $R_2 \to P_3$, $R_4 \to P_4$, $R_3 \to P_5$, $R_6 \to P_6$, $R_5 \to P_7$. Archi di richiesta: $P_1 \to R_2$, $P_2 \to R_3$, $P_4 \to R_2$, $P_4 \to R_3$, $P_5 \to R_5$, $P_6 \to R_2$, $P_7 \to R_4$.

Ciclo: $P_4 \to R_3 \to P_5 \to R_5 \to P_7 \to R_4 \to P_4$ (è il ciclo in rosso del grafo del corso, e la soluzione scrive: "$P_4 \to R_3 \to P_5 \to R_5 \to P_7 \to R_4 \to P_4$ sono in deadlock"). $P_4$ attende $R_3$ (di $P_5$), $P_5$ attende $R_5$ (di $P_7$), $P_7$ attende $R_4$ (di $P_4$). Tutte le risorse del ciclo sono a istanza singola: deadlock tra $P_4, P_5, P_7$ con le risorse $R_3, R_4, R_5$. Il grafo ha un solo ciclo (controllato con una ricerca di cicli): $P_1$, $P_6$ aspettano $R_2$, posseduta da $P_3$ che non attende nulla e prima o poi la rilascia, quindi non sono in stallo; $P_2$ attende $R_3$ (in mano a $P_5$, che è nel deadlock) ed è bloccato indirettamente, senza far parte del ciclo.

Esercizio 109

Archi di assegnazione: $R_3 \to P_1$, $R_1 \to P_2$, $R_8 \to P_3$, $R_6 \to P_6$, $R_8 \to P_6$, $R_4 \to P_7$, $R_8 \to P_9$, $R_9 \to P_9$. Archi di richiesta: $P_1 \to R_1$, $P_2 \to R_4$, $P_4 \to R_1$, $P_6 \to R_3$, $P_7 \to R_9$, $P_9 \to R_6$.

Ciclo (diretto): $P_1 \to R_1 \to P_2 \to R_4 \to P_7 \to R_9 \to P_9 \to R_6 \to P_6 \to R_3 \to P_1$. Lo si controlla seguendo gli archi: $P_1$ attende $R_1$ (di $P_2$), $P_2$ attende $R_4$ (di $P_7$), $P_7$ attende $R_9$ (di $P_9$), $P_9$ attende $R_6$ (di $P_6$), $P_6$ attende $R_3$ (di $P_1$). Le risorse del ciclo ($R_1, R_4, R_9, R_6, R_3$) hanno tutte una sola istanza: deadlock tra $P_1, P_2, P_7, P_9, P_6$. $P_4$ (attende $R_1$) è bloccato dal deadlock ma non ne fa parte; $P_3$ non attende nulla e non è coinvolto.

La soluzione del corso parla di due cicli, "stallo nel ciclo giallo" e "nel ciclo rosso c'è $R_8$ con 2 risorse". Il secondo è il giro $R_6, P_6, R_8, P_9$: in senso diretto non è un ciclo, perché $P_6$ non richiede $R_8$ (la possiede); cercando i cicli diretti, l'unico è quello giallo. In ogni caso, se lo si volesse considerare, passa per $R_8$ che ha due istanze (una è di $P_3$, che non è bloccato): non produrrebbe stallo.

Domande d'esame

Con più istanze per risorsa, un ciclo implica deadlock? Traccia. No, solo se le istanze di tutte le risorse del ciclo sono tutte assegnate a processi del ciclo; se un'istanza è posseduta da un processo fuori dal ciclo, può liberarsi e sciogliere l'attesa. Si usa il banchiere (o l'algoritmo di rilevamento) come in Esercizio - Algoritmo del banchiere su tre risorse con richieste (eserciziario, esercizio 4).