Sistemi Operativi: Gestione delle risorse e deadlock

Sistemi Operativi: Gestione risorse e deadlock

Copyright c 2002-2005 Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. A copy of the license can be found at: http://www.gnu.org/licenses/fdl.html#Toc1Introduzione

"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" Legge del Kansas di inizio secolo

Risorse

• Un sistema di elaborazione è composto da un insieme di risorse da assegnare ai processi presenti
• I processi competono nell'accesso alle risorse
• Esempi di risorse memoria stampanti
• processore
• dischi
• interfaccia di rete
• descrittori di processo

Classi di risorse

• Le risorse possono essere suddivise in classi
• le risorse appartenenti alla stessa classe sono equivalenti
• esempi: byte della memoria, stampanti dello stesso tipo, etc.
• Definizioni:
• le risorse di una classe vengono dette istanze della classe
• il numero di risorse in una classe viene detto molteplicità del tipo di risorsa
• Un processo non può richiedere una specifica risorsa, ma solo una risorsa di una specifica classe
• una richiesta per una classe di risorse può essere soddisfatta da qualsiasi istanza di quel tipo

Assegnazione delle risorse

• Risorse ad assegnazione statica avviene al momento della creazione del processo e rimane valida fino alla terminazione
• esempi: descrittori di processi, aree di memoria (in alcuni casi)
• Risorse ad assegnazione dinamica
• i processi
• richiedono le risorse durante la loro esistenza
• le utilizzano una volta ottenute
• le rilasciano quando non più necessarie (eventualmente alla terminazione del processo
• esempi: periferiche di I/O, aree di memoria (in alcuni casi)

Tipi di richieste

• Richiesta singola:
• si riferisce a una singola risorsa di una classe definita
• è il caso normale
• Richiesta multipla
• si riferisce a una o più classi, e per ogni classe, ad una o più risorse
• deve essere soddisfatta integralmente

Tipi di richieste bloccanti

Richiesta bloccante il processo richiedente si sospende se non ottiene immediatamente l'assegnazione

• la richiesta rimane pendente e viene riconsiderata dalla funzione di gestione ad ogni rilascio
• Richiesta non bloccante
• la mancata assegnazione viene notificata al processo richiedente, senza provocare la sospensione

Tipi di risorse

• Risorse seriali (o con accesso mutuamente esclusivo) una singola risorsa non può essere assegnata a più processi contemporaneamente
• esempi:
• i processori
• le sezioni critiche
• le stampanti .
• Risorse non seriali esempio:
• file di sola lettura

Risorse prerilasciabili ("preemptable")

Definizione

• una risorsa si dice prerilasciabile se la funzione di gestione può sottrarla ad un processo prima che questo l'abbia effettivamente rilasciata
• Meccanismo di gestione:
• il processo che subisce il prerilascio deve sospendersi
• la risorsa prerilasciata sarà successivamente restituita al processo

Risorse prerilasciabili: stato e esempi

• Una risorsa è prerilasciabile: se il suo stato non si modifica durante l'utilizzo
• oppure il suo stato può essere facilmente salvato e ripristinato
• Esempi: processore
• blocchi o partizioni di memoria (nel caso di assegnazione dinamica)

Risorse non prerilasciabili

Definizione

• la funzione di gestione non può sottrarle al processo al quale sono assegnate
• sono non prerilasciabili le risorse il cui stato non può essere salvato e ripristinato
• Esempi stampanti
• classi di sezioni critiche
• partizioni di memoria (nel caso di gestione statica)

Deadlock

• Come abbiamo visto
• i deadlock impediscono ai processi di terminare correttamente
• le risorse bloccate in deadlock non possono essere utilizzati da altri processi
• Ora vediamo
• le condizioni che necessarie affinché un deadlock si presenti
• le tecniche che possono essere utilizzate per gestire il problema dei deadlock

Condizioni per avere un deadlock

• Mutua esclusione
• le risorse coinvolte devono essere seriali
• Assenza di prerilascio
• le risorse coinvolte non possono essere prerilasciate, ovvero devono essere rilasciate volontariamente dai processi che le controllano
• Richieste bloccanti (detta anche "hold and wait")
• le richieste devono essere bloccanti, e un processo che ha già ottenuto risorse può chiederne ancora Attesa circolare esiste una sequenza di processi P0,P1, ..., Pn, tali per cui P0 attende una risorsa controllata da P1, P1 attende una risorsa controllata da P2, ... , e Pn attende una risorsa controllata da P0

Condizioni per avere un deadlock: necessità e sufficienza

• L'insieme di queste condizioni è necessario e sufficiente
• devono valere tutte contemporaneamente affinché un deadlock si presenti nel sistema

Metodi di gestione dei deadlock

• Deadlock detection and recovery
• permettere al sistema di entrare in stati di deadlock; utilizzare un algoritmo per rilevare questo stato ed eventualmente eseguire un'azione di recovery
• Deadlock prevention / avoidance
• impedire al sistema di entrare in uno stato di deadlock + Ostrich algorithm
• ignorare il problema del tutto!

Deadlock detection

• Descrizione
• mantenere aggiornato il grafo di Holt, registrando su di esso tutte le assegnazioni e le richieste di risorse
• utilizzare il grafo di Holt al fine di riconoscere gli stati di deadlock .
• Problema: come riconoscere uno stato di deadlock?

Grafo di Holt: Caratteristiche

• Caratteristiche
• è un grafo diretto
• gli archi hanno una direzione
• è un grafo bipartito
• i nodi sono suddivisi in due sottoinsiemi e non esistono archi che collegano nodi dello stesso sottoinsieme
• i sottoinsiemi sono risorse e processi
• gli archi risorsa -> processo indicano che la risorsa è assegnata al processo
• gli archi processo -> risorsa indicano che il processo ha richiesto la risorsa

Grafo di Holt - Esempio

1 2 3 p q r

Grafo di Holt generale

• Nel caso di classi contenenti più istanze di una risorsa
• l'insieme delle risorse è partizionato in classi e gli archi di richiesta sono diretti alla classe e non alla singola risorsa
• Rappresentazione
• i processi sono rappresentati da cerchi
• le classi sono rappresentati come contenitori rettangolari
• le risorse come punti all'interno delle classi
• Nota:
• non si rappresentano grafi di Holt con archi relativi a richieste che possono essere soddisfatte
• se esiste almeno un'istanza libera della risorsa richiesta, la risorsa viene assegnata

Grafo di Holt generale - Esempio

18Grafo di Holt - Notazione alternativa

• Alcuni autori preferiscono indicare numericamente:
• sugli archi: la molteplicità della richiesta (archi processo -> classe)
• la molteplicità dell'assegnazione (archi classe -> processo) all'interno delle classi
• il numero di risorse non ancora assegnate 0 0 1 1 1 1 2 1

Caso 1 - Una sola risorsa per classe

Teorema se le risorse sono ad accesso mutualmente esclusivo, bloccanti e non prerilasciabili

• lo stato è di deadlock se e solo se il grafo di Holt contiene un ciclo .
• Dimostrazione
• si utilizza una variante del grafo di Holt, detto grafo Wait-For
• si ottiene un grafo wait-for eliminando i nodi di tipo risorsa e collassando gli archi appropriati
• il grafo di Holt contiene un ciclo se e solo se il grafo Wait-for contiene un ciclo
• se il grafo Wait-for contiene un ciclo, abbiamo attesa circolare

Grafo Wait-for

1 p q p q 2 Grafo di Holt Grafo Wait-For

Caso 2 - Più risorse per classe

• La presenza di un ciclo nel caso di Holt non è condizione sufficiente per avere deadlock Deadlock No Deadlock

Riducibilità di un grafo di Holt

Definizione un grafo di Holt si dice riducibile se esiste almeno un nodo processo con solo archi entranti

• £ Riduzione
• consiste nell'eliminare tutti gli archi di tale nodo e riassegnare le risorse ad altri processi
• Qual è la logica?
• eventualmente, un nodo che utilizza una risorsa prima o poi la rilascerà; a quel punto, la risorsa può essere riassegnata

Esempio di riduzione

P P 2 P P 2 1 1 Riduzione per P1

Deadlock detection con grafo di Holt: Teorema

• Teorema se le risorse sono ad accesso mutualmente esclusivo, bloccanti e non prerilasciabili
• lo stato non è di deadlock se e solo se il grafo di Holt è completamente riducibile, i.e. esiste una sequenza di passi di riduzione che elimina tutti gli archi del grafo

Esercizio 2 - 4/6/2002

p q C'è deadlock? r S

Esercizio 2 - 4/6/2002: Riduzione di p

p q r S Riduzione di p Assegnamento risorsa ar

Esercizio 2 - 4/6/2002: Riduzione di r

p q r S Riduzione di r Assegnamento risorse a q, s

Esercizio 2 - 4/6/2002: Riduzione di q

p q Riduzione di q r S

Esercizio 2 - 4/6/2002: Riduzione di s

p q Riduzione di s Non c'è deadlock r S

Deadlock recovery

• Dopo aver rilevato un deadlock ...
• ... bisogna risolvere la situazione
• La soluzione può essere
• manuale
• l'operatore viene informato e eseguirà alcune azioni che permettano al sistema di proseguire automatica
• il sistema operativo è dotato di meccanismi che permettono di risolvere in modo automatico la situazione, in base ad alcune politiche

Meccanismi per il deadlock recovery

• Terminazione totale tutti i processi coinvolti vengono terminati
• Terminazione parziale viene eliminato un processo alla volta, fino a quando il deadlock non scompare
• Preemption
• una risorsa (o più di una, se necessario) viene sottratta ad uno dei processi coinvolti nel deadlock

Meccanismi per il deadlock recovery: Checkpoint/rollback

• Checkpoint/rollback
• lo stato dei processi viene periodicamente salvato su disco (checkpoint)
• in caso di deadlock, si ripristina (rollback) uno o più processi ad uno stato precedente, fino a quando il deadlock non scompare

Considerazioni sul deadlock recovery

• Terminare processi può essere costoso
• questi processi possono essere stati eseguiti per molto tempo; se terminati, dovranno ripartire da capo
• Terminare processi può lasciare le risorse in uno stato inconsistente se un processo viene terminato nel mezzo di una sezione critica
• Fare preemption
• non sempre è possibile
• può richiedere interventi manuali
• esempio: preemption di una stampante