Stallo di Processi (Deadlock) PDF

1 8. Stallo di Processi (deadlock) Definizione: situazione in cui ciascun processo in un insieme di n processi (n ≥ 2) si trova in uno stato di attesa per il verificarsi di un evento che solo uno degli altri processi dell’insieme può provocare. Risultato: attesa infinita da p...

1 8. Stallo di Processi (deadlock) Definizione: situazione in cui ciascun processo in un insieme di n processi (n ≥ 2) si trova in uno stato di attesa per il verificarsi di un evento che solo uno degli altri processi dell’insieme può provocare. Risultato: attesa infinita da parte di tutti gli n processi!  2 8. Stallo di Processi (deadlock) Situazioni simili si verificano anche nella realtà: “When two trains approach each other at a crossing, both shall come to a full stop and neither shall start up again until the other has gone” (da una vecchia norma di legge del Kansas) I SO di oggi non affrontano il problema, ci devono pensare gli utenti. In futuro potrà diventare un compito dei SO  3 8. Stallo di Processi (deadlock) I processi P1 e P2 usano entrambi uno dei due nastri e hanno bisogno di un secondo nastro. L’accesso ai nastri e’ regolato dal semaforo avail, inizializzato a 2. P1 P2 begin begin : : wait(avail) wait(avail) : : wait(avail) wait (avail) : : signal(avail) signal(avail) signal(avail) signal (avail) end end  8. Stallo di Processi (deadlock) 4 Un ponte ad una sola corsia Ciascuna posizione di marcia può essere vista come una risorsa. Una situazione di deadlock può essere risolta se un auto torna indietro (libera una risorsa già occupata). Si verifica starvation se ciascuna auto sul ponte attende che l’altra liberi l’unica corsia di marcia  5 8.1 Modello del Sistema Un sistema (HW + SO) può essere visto come formato da: un insieme finito di tipi di risorse R (cicli di CPU, spazio di memoria, device di I/O), Ogni tipo di risorsa è formata da un certo numero di istanze indistinguibili fra loro (ad esempio la ram può essere divisa in porzioni identiche, ciascuna delle quali può ospitare un processo) Un insieme di processi P che hanno bisogno di una o più istanze di alcune delle risorse per portare a termine la computazione  6 8.1 Modello del Sistema Si definisce deadlock di un sottoinsieme di processi del sistema {P1, P2, …,Pn} ⊆ P la situazione in cui ciascuno degli n processi Pi e’ in attesa del rilascio di una risorsa detenuta da uno degli altri processi del sottoinsieme; si forma cioè una catena circolare per cui: P1 aspetta P2 … aspetta Pn aspetta P1 Anche se non tutti i processi del sistema sono bloccati, la situazione non è desiderabile in quanto può bloccare alcune risorse, e dunque danneggiare anche i processi non coinvolti nel deadlock  7 8.3 Caratterizzazione del deadlock Il SO può avvalersi di una opportuna rappresentazione detta grafo di assegnazione delle risorse che in ogni istante registra quali risorse sono assegnate a quale processo, e quali risorse sta aspettando ciascun processo In questo esempio (fig. 8.5), c’è deadlock perché: T1 attende che T2 liberi R1, T2 attende che T3 liberi R3, T3attende che T1 o T2 liberino R2 Ossia, il grafo contiene almeno un ciclo  8 8.3 Metodi per la gestione dei Deadlock 1. Prevenire o evitare i deadlock, usando un opportuno protocollo di richiesta e assegnamento delle risorse 2. lasciare che il deadlock si verifichi, ma fornire strumenti per la scoperta e il recupero dello stesso, esplorando il grafo di assegnazione delle risorse alla ricerca di cicli. Tuttavia, la soluzione 1 genera un eccessivo sottoutilizzo delle risorse, mentre la soluzione 2 non evita il problema e richiede lavoro al SO per eliminare il deadlock, dunque i SO moderni adottano la soluzione 3: 3. lasciare agli utenti la prevenzione/gestione dei deadlock