Sistemi Operativi - Lezione del 31 marzo 2008

 :: Sistemi operativi - Lezione del 31 marzo 2008 ::

Torna alla pagina di Sistemi Operativi

Lezione 1: Caratterizzazione dei deadlock

I deadlock (dl da qui in poi) non accadono sempre: devono essere soddisfatte 4 condizioni affinché accadano.

1. C'è una risorsa in mutua esclusione.
2. Hold & wait
3. Assenza di rilascio anticipato
4. Attesa circolare

Mutua esclusione: ovviamente, se non ho risorse per cui "lottare", non c'è nemmeno una possibilità di dl.

Hold & Wait: è una situazione in cui un processo ha già delle risorse (hold), ma deve attenderne ancora delle altre (wait).

Assenza di rilascio anticipato: vuol dire che non posso privare un processo delle risorse che ha già acquisito.

Attesa circolare: Il processo A ha delle risorse e ne attende dal processo B, il quale a sua volta attende le risorse di A. Insomma, un cerchio dell'ammmore, con anche più di 2 processi.

Quando tutte ste condizioni sono verificate, ho un dl.

I grafi di allocazione delle risorse

Suddetti grafi hanno come nodi le risorse ed i processi.

Un arco uscente da una risorsa ed entrante in un nodo significa che quella risorsa è assegnata a quel nodo. Un arco uscente da un nodo ed entrante in una risorsa significa che quel nodo ha fatto richiesta di quella risorsa.

Inoltre, le risorse hanno dei pallini. X pallini nel nodo della risorsa stanno a significare che ci sono X copie di quella risorsa disponibili da dar via.

Ho un dl quando ho un ciclo, e devo verificare anche che i pallini siano tutti esauriti. Ma non è sempre vero che se ho un ciclo ho un dl: infatti, se i pallini non sono esauriti, allora non ho un deadlock. Quindi occhio ai pallini! Non fatemelo disegnare, please...

Attenzione: in un sistema distribuito, il grafo si fa molto più complesso. Noi qui ci occupiamo solo dei sistemi monocalcolatore.

Gestire il deadlock

Un SO può porsi in modi diversi di fronte al problema del deadlock. Mantenere un grafo delle risorse e periodicamente controllarlo può essere una via.

Ci sono però diverse strategie a disposizione:

• Ignorare bellamente il deadlock
• Prevenire il deadlock
• Evitare il deadlock
• Rilevarlo e recuperare

Ignorare il dl vuol dire esattamente quello: ignorare. Perché mai? La risposta è che la frequenza con cui i deadlock si presentano è molto bassa; l'utente in genere dopo un po' se ne accorge, e ci penserà lui ad accoppare i processi. È parimenti molto bassa la probabilità che al prossimo riavvio i processi si metteranno in un ordine tale per cui il dl accada di nuovo.

Prevenire il dl vuol dire invece fare in modo che un processo venga attivato SOLO se c'è certezza che il dl non avvenga mai.

Evitare invece permette che i processi partano, e poi vede di smanettare per evitare che i processi già partiti creino dl. Quindi, a differenza della prevenzione, non impedisce ai processi di essere esguiti.

Rilevazione e recupero sta a significare che il SO permette che il deadlock accada, e poi vedrà in qualche modo di accorgersene, e uccidere processi finché il dl non scompare.

Ognuna di queste scelte ha il suo costo, tenendo in mente sia quanto tempo perdo a rilevare i dl, sia quanto è alta la probabilità che accadano. Quindi occorre bilanciare.

Lezione 2: Tecniche di prevenzione del deadlock

Si tratta di tecniche che cercano di annullare una della 4 condizioni viste prima, dal momento che abbiamo detto che devono verificarsi tutte e 4 per avere un deadlock.

Prevenire la mutua esclusione

Il SO cerca di fare in modo che solo le risorse che ne hanno bisogno possano attivare la mutex, ovvero quello che ne hanno intrinsecamente bisogno. Per le altre, impedisce la mutex: se il loro utilizzo condiviso non crea problemi, perché inventarsene?

Prevenire la hold & wait

È la condizione per cui un processo che ha delle risorse sta attendendo che se ne liberino delle altre. Per evitare una situazione del genere, ci sono 2 approcci:

1. Un processo deve chiedere in blocco tutte le risorse necessarie quando viene avviato. Se non le ha tutte, non viene nemmeno avviato. Alla fine, le rilascia tutte.

Il problema qui è evidente: il programma va scritto nel modo opportuno, innanzitutto. Ma poi, succede anche che si riduce di parecchio il parallelismo, perché un processo può monopolizzare anche delle risorse che usa poco, e impedire che altri ne usufruiscano e avanzino nella loro computazione.

2. Un processo che vuole delle risorse ulteriori rispetto a quelle che ha già, deve rilasciarle tutte e poi, all'occorrenza, riprenderle ancora tutte PIÙ quella che gli serve in quel momento.

Almeno questo sistema garantisce un po' di parallelismo in più rispetto al sistema 1.

Comunque, quale che sia il mio metodo per prevenire la hold & wait, ho che in generale le risorse vengono sottoutilizzate per via di queste "paranoie" sul lock, e alcuni processi potrebbero morire di starvation, ovvero attendere indefinitamente che i progressi prepotenti liberino le risorse.

Preemption

Vuol dire, in altre parole, prevenire la non-preemption:) Preemption vuol dire che rubo le risorse ad un processo per darle ad un altro. Naturalmente il furto non è sempre giustificato, occorre rispettare delle condizioni, ovvero che il rilascio anticipato NON crei problemi di consistenza.

Se un processo chiede risorse, e ne ha delle altre che non sono rilasciabili, allora

• rilascio anticipatamente tutte le sue risorse;
• metto le mie vecchie risorse nella lista di quelle che vorrei;
• aspetto di riaverle tutte.

È come il sistema 2 della prevenzione della hold & wait, con la differenza che qui rilascio solo le risorse che possono essere ripristinate, ovvero che non creerebbero problemi di consistenza.

Se un processo chiede risorse

• se sono disponibili, pronti, gliele diamo.
• se NON sono disponibili, devo agire in 2 modi diversi
  • se appartengono ad un processo che deve attendere altre risorse, allora gliele posso fregare: aspetterà un po' di più.
  • se appartengono a processi che invece le stanno usando, allora sarò io ad attendere.

Ciò vuol dire che faccio preemption solo se c'è un processo in attesa di altre risorse, altrimenti no.

Prevenzione dell'attesa circolare

Questa mi sa che è la più paranoica. Devo dare un ordinamento globale a TUTTE le mie risorse, in modo che siano numerate, e che date due risorse io sappia sempre dire se l'indice di una è maggiore o minore dell'indice dell'altra.

Fatto ciò (che è una cosa ingrata), obbligo i processi a chiedere SOLO risorse che indice MAGGIORE di quello della risorsa con più grande indice che già ha. In altre parole, se il processo A ha la risorsa R₂₅, potrà chiedere solo risorse indicizzate da R₂₆ in su, e non da R₂₅ in giù.

Se proprio vuole risorse con indice più basso, allora deve mollare tutte quelle che ha con indice maggiore di quella voluta, e ripartire da quella con indice più basso.

Sembrerà balordo, ma evita le attese circolari, perché non potrà mai accadere che due processi si attendano l'un l'altro: gli indici lo proibiscono.

Lezione 4 - Tecniche per rilevazione e ripristino

Permetto che accada il dl, lo rilevo e poi recupero.

Vi ricordate il grafo delle allocazioni di prima? Bene. Facciamo ora la considerazione che, sinceramente, di sapere QUALE sia la risorsa che causa il dilemma, a noi non interessa niente. Ci basta sapere che un processo attende da un'altro processo, e tant'è.

In questo modo, possiamo togliere un sacco di nodi dal grafo, renderlo più semplice e quindi avere un algoritmo di rilevamento dei cicli che lavora su un numero inferiore di nodi, ovvero tendenzialmente più rapido. Questo grafo si chiama wait-for, in cui un arco uscente da un nodo-processo ed entrante in un altro nodo-processo sta a significare che il primo processo vuole qualcosa che il secondo ha.

Purtroppo, questo funziona SOLO se ho risorse con istanze singole. Se ho risorse con istanze multiple (il numero di pallini del grafo di allocazione delle risorse, per intenderci), allora la cosa si fa molto più complicata. Non basta più un grafo, occorrono delle matrici e dei vettori, e l'algoritmo si fa molto più complesso.

Quando faccio partire quest'algoritmo?

Posso decidere di farlo partire ogni volta che un processo chiede una risorsa e scopre che è occupata. Ok, però si capisce subito che l'overhead diventa tanto: chissà quante volte devo controllare il grafo!

Altrimenti, decido di eseguire l'algoritmo ogni tot tempo. Il problema è che magari nel frattempo si possono essere accumulati un po' di stalli. Ma è sicuramente meno costoso che farlo ad ogni richiesta fallita.

E quando ho trovato un dl?

Un sistema un po' barbaro ma efficace consiste nell'accoppare tutti i processi che stanno nel ciclo. Sicuramente risolvo il problema del dl, ma è altrettanto sicuro che spreco un sacco di risorse uccidendo processi magari innocenti.

Oppure, ne posso uccidere uno alla volta (di processi), fintantoché il dl non scompare. Lo svantaggio è che devo ripetere l'algo per ogni uccisione.

Ok, uccido processi. Ma quali?

Posso scegliere un criterio qualsiasi per uccidere i processi, nel caso non voglia compiere un genocidio. Posso ad esempio prendere quelli con priorità più bassa, o quelli che sono in esecuzione da meno tempo o quelli fatti partire da un utente a me antipatico.

Qualsiasi cosa io faccia, devo però stare attento a far sì che le risorse che vengono rilasciate forzatamente possano fare un rollback e tornare in uno stato consistente precedente. E poi, devo anche stare attento quando uso un criterio, perché può darsi che ad ogni deadlock che si ripresenta, uccido sempre il solito processo sfortunato, il quale quindi andrebbe a trovarsi in una situazione di starvation.

Torna alla pagina di Sistemi Operativi