Sistemi Operativi - Il Deadlock (PDF)

Sistemi Operativi Modulo I Secondo canale Corso di Laurea in Informatica Il Deadlock Fabio De Gaspari Sapienza Università di Roma Dipartimento di Informatica slides by: Igor Melatti Il Deadlock o Stallo Blocco permanente di un insieme di proces...

Sistemi Operativi Modulo I Secondo canale Corso di Laurea in Informatica Il Deadlock Fabio De Gaspari Sapienza Università di Roma Dipartimento di Informatica slides by: Igor Melatti Il Deadlock o Stallo Blocco permanente di un insieme di processi, che o competono per delle risorse di sistema o comunicano tra loro Il motivo di base è la richiesta contemporanea delle stesse risorse da parte di due o più processi Non esiste una soluzione efficiente diversi approcci, da valutare nei vari casi Il deadlock potrebbe essere causato da una combinazione rara di eventi corner case Deadlock Deadlock: Joint Progress Diagram Deadlock: Joint Progress Diagram Risorse Riusabili (Reusable Resources) Usabili da un solo processo alla volta Il fatto di essere usate non le “consuma” Una volta che un processo ottiene una risorsa riusabile, prima o poi la rilascia cosicché altri processi possano usarla a loro volta Esempi: processori, I/O channels, memoria primaria e secondaria, dispositivi, file, database, semafori Lo stallo può esistere solo se un processo ha una risorsa e ne richiede un’altra Risorse Riusabili: Esempio 1 con 2 Processi Risorse Riusabili: Esempio 2 con 2 Processi Supponiamo che ci siano 200 KB di memoria disponibili, e che ci sia la seguente sequenza di richieste Il deadlock avverrà quando uno dei due processi farà la seconda richiesta Risorse Non Riusabili (Consumable Resources) Vengono create (prodotte) e distrutte (consumate) Esempi: interruzioni, segnali, messaggi, informazione nei buffer di I/O Deadlock possibile se si fa una richiesta (bloccante) di una risorsa ancora non creata Ad esempio, un deadlock può avvenire su una ricezione bloccante Risorse Non Riusabili: Esempio con 2 Processi Deadlock inevitabile, processi scritti molto male... Grafo dell’Allocazione delle Risorse Grafo diretto che rappresenta lo stato di risorse e processi tanti pallini quante istanze di una stessa risorsa Ok per le risorse riusabili Per le risorse consumabili, non esiste mai l’“Held”; invece, i pallini compaiono e scompaiono... Condizioni per il Deadlock (Risorse Riusabili) Mutua esclusione solo un processo alla volta può usare una data risorsa Richiesta di una risorsa quando se ne ha già una (hold-and-wait) un processo può richiedere risorse mentre ne tiene già bloccate altre Niente preemption per le risorse non si può sottrarre una risorsa ad un processo senza che quest’ultimo non la rilasci Attesa circolare esiste una catena chiusa di processi, in cui ciascun processo detiene una risorsa richiesta (invano) dal processo che lo segue nella catena Condizioni per il Deadlock (Risorse Consumabili) Mutua esclusione ovvia (la risorsa va a chi ne riesce a fare richiesta per primo) Richiesta di una risorsa quando se ne ha già una (hold-and-wait) diventa: si può richiedere (in modo bloccante) una risorsa quando ancora non sia stata creata Niente preemption per le risorse ovvia (non appena viene concessa, una risorsa viene distrutta...) Attesa circolare esiste una catena chiusa di processi, in cui ciascun processo dovrebbe creare una risorsa richiesta (invano) dal processo che lo segue nella catena Grafi dell’Allocazione delle Risorse Grafi dell’Allocazione delle Risorse Grafi dell’Allocazione delle Risorse 1) c’è un ciclo; 2) nessun pallino è scoperto Possibilità di Deadlock Mutua esclusione Richiesta di una risorsa quando se ne ha già una (hold-and-wait) Niente preemption per le risorse Esistenza di Deadlock Mutua esclusione Richiesta di una risorsa quando se ne ha già una (hold-and-wait) Niente preemption per le risorse Attesa circolare Deadlock e SO: Che fare? Prevenire cercando di far sı̀ che una delle 4 condizioni sia sempre falsa Evitare decidendo di volta in volta cosa fare con l’assegnazione di risorse Rilevare il SO lascia che eventualmente ci sia deadlock ogni tanto, il SO vede se si è verificato, e o notifica all’utente o prende decisioni per rimuoverlo Ignorare se dei processi utente vanno in deadlock, è colpa dell’utente non accettabile, in generale, per processi del sistema operativo Prevenzione del Deadlock Mutua esclusione non si può. Punto Hold-and-wait si impone ad un processo di richiedere tutte le sue risorse in una volta può essere difficile per software complessi, e si tengono risorse bloccate per un tempo troppo lungo Niente preemption per le risorse il SO può richiedere ad un processo di rilasciare le sue risorse (le dovrà richiedere in seguito) per esempio, se una sua richiesta di un’altra risorsa non è stata concessa Attesa circolare si definisce un ordinamento crescente delle risorse; una risorsa viene data solo se segue quelle che il processo già detiene Evitare il Deadlock Occorre decidere se l’attuale richiesta di una risorsa può portare ad un deadlock, se esaudita Richiede la conoscenza delle richieste future Due possibilità: non mandare in esecuzione un processo se le sue richieste possono portare a deadlock (abbastanza ovvio) non concedere una risorsa ad un processo se allocarla può portare a deadlock (algoritmo del banchiere) Evitare il Deadlock: Diniego di Risorse Algoritmo del banchiere valido per risorse riusabili Lo stato del sistema è l’attuale allocazione delle risorse ai processi Uno stato è sicuro (safe) se da esso parte almeno un cammino che non porta ad un deadlock Uno stato non sicuro è insicuro (unsafe) Algoritmo del Banchiere: Strutture Dati Determinazione dello Stato Sicuro Determinazione dello Stato Sicuro Determinazione dello Stato Sicuro Determinazione dello Stato Sicuro Determinazione dello Stato Non Sicuro Evitare il Deadlock: Pseudocodice Evitare il Deadlock: Pseudocodice Evitare il Deadlock: Pseudocodice Occorre dichiarare il massimo uso di risorse I processi devono essere indipendenti, senza requisiti di sincronizzazione ovvero, devono essere “liberi” di andare in esecuzione in un qualsiasi ordine altrimenti, non si può simularne l’esecuzione fino al completamento... in sostanza, l’unica sincronizzazione presente è proprio quella sulle richieste di risorse Ci deve essere un numero fissato di risorse da allocare quindi, non va bene per le risorse consumabili Nessun processo deve terminare senza rilasciare le sue risorse Rilevare il Deadlock: Pseudocodice Stesse strutture dati del banchiere, ma la claim matrix è sostituita da Q: le richieste effettuate da tutti i processi come il request del banchiere, ma relativo appunto a tutti i processi e non ad uno solo Algoritmo: 1 marca tutti i processi che non hanno allocato nulla 2 w ←V 3 sia i un processo non marcato t.c. Qik ≤ wk ∀1 ≤ k ≤ m le sue risorse possono essere accordate 4 se i non esiste, vai al passo 6 5 marca i e aggiorna w ← w + Ai ; poi torna al passo 3 facciamo finta che le sue risorse vengano liberate 6 c’è un deadlock se e solo se esiste un processo non marcato Rilevare il Deadlock: Esempio Deadlock Rilevato: e Poi? Terminare forzosamente tutti i processi coinvolti nel deadlock cosı̀ fan (quasi) tutti almeno un processo non in deadlock resta sempre, basta che non faccia richiesta di risorse... Mantenere dei punti di ripristino, ed effettuare il ripristino al punto precedente lo stallo può verificarsi nuovamente, ma è improbabile che lo faccia all’infinito Terminare forzosamente i processi coinvolti nel deadlock uno ad uno, finché lo stallo non c’è più Sottrarre forzosamente risorse ai processi coinvolti nel deadlock uno ad uno, finché lo stallo non c’è più Vantaggi e Svantaggi Approccio Politica di Allo- Possibili Schemi Vantaggi Principali Svantaggi Principali cazione Prevenire Conservativa: Richiesta contemporanea OK per processi con singolo Inefficiente: ritarda concede meno di tutte le risorse burst di computazione; Non l’inizializzazione dei pro- risorse di quelle richiede preemption cessi; Un processo deve richieste conoscere tutte le sue richieste future, difficile per gli interattivi Preemption OK se le risorse hanno uno La preemption può avvenire stato facile da salvare e troppo spesso ripristinare Ordinamento delle risorse Possibile con controlli a Non possibile per processi tempo di compilazione; interattivi Niente controlli a run-time, risolto con il progetto del SO Evitare A metà tra pre- Si cerca di trovare almeno Niente prevenzione Necessità di risorse future venire e rilevare un cammino sicuro da conoscere in anticipo Rilevare Molto lib- Controllo del deadlock da Niente ritardo Gesione del deadlock erale: concede fare periodicamente sull’inizializzazione; Fa- quando avviene più risorse di cilita la gestione delle risorse quelle possibili online Deadlock e Linux Come sempre, gestione minimale ma il più possibile efficiente Quindi: se dei processi utente sono “scritti male” e possono andare in deadlock, peggio per loro, che ci vadano semplicemente, vorrà dire che saranno tutti bloccati (TASK INTERRUPTIBLE) sta all’utente accorgersene e killarli sono solo processi utente, non possono fare chissà che danno Invece, per quanto riguarda il kernel, c’è la prevenzione dell’attesa circolare i lock vengono sempre acquisiti in un ordine fisso e predeterminato I Filosofi a Cena I Filosofi a Cena: Prima Soluzione I Filosofi a Cena: Prima Soluzione La dichiarazione della variabile i globale (terza riga) è inutile vale anche per gli altri pseudocodici Per il filosofo i, fork[i] è la forchetta sinistra, fork[(i + 1) mod n] è la destra Ci può essere deadlock lo scheduler fa sı̀ che ogni processo faccia la wait sulla sua forchetta sinistra nessuno viene bloccato e poi fa fare a tutti la wait su quelle destre tutti vengono bloccati I Filosofi a Cena: Seconda Soluzione I Filosofi a Cena: Seconda Soluzione Non si pensa al tavolo, ma in un’altra stanza Quando si ha fame, si entra nella sala da pranzo C’è un cameriere che fa entrare al massimo n − 1 filosofi alla volta semaforo room Niente più deadlock I Filosofi a Cena: III, IV e V Soluzione Nella soluzione precedente, si sono leggermente variati i termini del problema Si impone ai filosofi di non mangiare tutti insieme o meglio, tutti seduti a tavola Ma può essere fatto, perché limitarsi? È possibile risolvere il problema dei filosofi senza deadlock e senza queste assunzioni Lo vedremo con i semafori e con i messaggi per quella con i messaggi, due varianti (più una versione errata) I Filosofi a Cena: Terza Soluzione semaphore fork [ N ] = {1 , 1 ,... 1}; philosopher ( i n t me ) { i n t left , right , first , second ; left = me ; right = ( me + 1) % N ; first = right < left ? right : left ; second = right < left ? left : right ; while (1) { think () ; wait ( fork [ first ]) ; wait ( fork [ second ]) ; eat () ; signal ( fork [ first ]) ; signal ( fork [ second ]) ; } } I Filosofi a Cena: Terza Soluzione È come la prima soluzione, ma si fa in modo che non tutti i filosofi prendano prima la forchetta sinistra e poi la destra Uno di loro farà il contrario ovvero, quello con PID n − 1 A questo punto, il deadlock non è più possibile anche considerando il caso di prima, il filosofo n − 1 non riuscirà a prendere la sua prima forchetta, che è già bloccata quindi, almeno il filosofo n − 2 può procedere I Filosofi a Cena: Quarta Soluzione (Sbagliata) Attenzione, ci può essere stallo mailbox fork [ N ]; init_forks () { int i; f o r ( i = 0; i < N ; ++ i ) nbsend ( fork [ i ] , " fork " ) ; } I Filosofi a Cena: Quarta Soluzione (Sbagliata) Attenzione, ci può essere stallo philosopher ( i n t me ) { i n t left , right ; message fork1 , fork2 ; left = me ; right = ( me + 1) % N ; while (1) { thi nk_for _a_whi le () ; receive ( fork [ left ] , fork1 ) ; receive ( fork [ right ] , fork2 ) ; eat () ; nbsend ( fork [ left ] , fork1 ) ; nbsend ( fork [ right ] , fork2 ) ; } } I Filosofi a Cena: Quarta Soluzione (Corretta) philosopher ( i n t me ) { i n t left , right ; message fork1 , fork2 ; left = me ; right = ( me + 1) % N ; first = right < left ? right : left ; second = right < left ? left : right ; while (1) { } } I Filosofi a Cena: Quinta Soluzione philosopher ( i n t me ) { i n t left , right ; message fork1 , fork2 ; left = me ; right = ( me + 1) % N ; while (1) { t h i n k _ f o r _ a _ r a n d o m _ t i m e () ; i f ( nbreceive ( fork [ left ] , fork1 ) ) { i f ( nbreceive ( fork [ right ] , fork2 ) ) { eat () ; nbsend ( fork [ right ] , fork2 ) ; } nbsend ( fork [ left ] , fork1 ) ; } } } I Filosofi a Cena: Quinta Soluzione Ci possono essere livelock e starvation Ma non lo stallo Si basa sul fatto che i filosofi “pensino” per un tempo casuale, scorrelato da quello degli altri