Sistemi operativi - Teoria e Pratica

A

signal(A);

Possiamo dire che c’è possibilità di deadlock se sussistono le 3 condizioni, c’è esistenza di deadlock se sussistono tutte e 4

le condizioni contemporaneamente, in particolare l’attesa circolare si verifica se le istanze delle risorse sono tutte occupate.

Come possiamo affrontare questo problema?

Una prima idea è quella di cercare di evitare che si verifichino le prime tre, perché se evitiamo queste cose allora il deadlock

non si potrà mai verificare. Prima di tutto, applichiamo prevenzione del deadlock (prevention), ovvero rimuovere dal

sistema ogni possibilità che ci sia un deadlock; un altro approccio è evitare che si possano verificare le tre condizioni

necessarie oppure che si verifichi la condizione di attesa circolare. Nel primo caso parliamo di tecniche prevenzione indiretta,

nel secondo caso la chiamiamo prevenzione diretta.

La prevenzione indiretta non può fare nulla contro la mutua esclusione, non posso eliminarla dato che è un requisito che si

deve rispettare se c’è una risorsa condivisa, ma può agire sull’impossibilità di prelazione e sul possesso e attesa.

Sull’impossibilità di prelazione potremmo agire in questo modo: se un processo che già possiede risorse, ne richiede un'altra

e quest’ulteriore risorsa è occupata, il processo è forzato a rilasciare tutto. Quindi, ritornando all’esempio precedente se il

processo possiede A e poi chiede B che è occupata, deve fare role-back per tornare alla prima wait, ripristinando tutto anche

il valore originale della risorsa A, tornando indietro alla prima wait. La wait non deve bloccare il processo, ma il processo

dovrebbe verificare lo stato, se è occupato, prima di fare wait torna indietro, ripristina il valore di A e libera A. Questo evita

la prelazione, gestendo la prelazione a livello applicativo, ovviamente il codice si complica, perché si devono inserire

condizioni su B, operazioni inverse.

Nel caso di possesso e attesa, la strategia è permettere ad un processo di avere assegnate le risorse dall’inizio, quindi un

processo quando parte è come se facesse una mega wait su tutte le risorse di cui ha bisogno. Questa funziona come strategia,

ma rende l’esecuzione fortemente sequenziale, anche quando non serve. Un processo che usa 10 risorse le blocca tutte

all’inizio, non quando gli servono, poi magari fa elaborazioni che non richiedono quelle risorse ma comunque le ha bloccate.

Questo sacrifica lo speedup della nostra applicazione, si sacrificano le prestazioni. Potrebbe andare come soluzione quando

i processi hanno burst di esecuzione, non succede che un processo parte e resta in esecuzione per sempre

(monopolizzerebbe le risorse). Va bene quindi per processi che partono, fanno un burst di esecuzione e poi liberano la CPU,

e vengono riesegui più avanti. Questa soluzione potrebbe funzionare, anche se limita il parallelismo, in sistemi critici, dov e

è più importante avere un’ esecuzione corretta piuttosto che performante, magari si impiega di più e non si sfruttano le

risorse al meglio, però almeno siamo certo da design che la soluzione non generi deadlock. Ancora una volta, questa è una

soluzione che possiamo implementare noi a livello applicativo.

La prevenzione diretta si può evitare forzando l’ordinamento dell’uso delle risorse. Tutti le devono usare nello stesso ordine,

per cui per costruzione non potrò mai avere attesa circolare. È semplice come approccio, ma introduce dei vincoli, se ad un

processo servono le risorse in un altro ordine non può farlo, per acquisire la risorsa 3 per esempio deve acquisire 1 e 2 anche

se non gli servono. Ancora una volta questo limita il parallelismo ed introduce un overhead maggiore. Inoltre, la soluzione

funziona se introduciamo regole di codifica ai programmatori, fornendo un manuale, le risorse e tutti devono rispettare il

modo in cui devono utilizzarle. In alcuni ambienti industriali si fa, ma non sempre vengono rispettate.

La prevenzione del deadlock si fonda su strategie che impongono vincoli sulla programmazione e sull’esecuzione dei

processi, danno luogo ad utilizzo inefficiente delle risorse o ad uno inefficiente del processore. Può andare bene se

l’efficienza non è il nostro principale obiettivo, quindi sistemi dove è più importante la safety, piuttosto che l’efficienza, va

bene anche così. Tutte queste tecniche sono dette di prevenzione statica.

Se vogliamo soluzioni meno conservative, cercando di ridurre l’inefficienza della prevenzione, si usano altre tecniche dette

deadlock avoidance, o anche prevenzione dinamica. Si chiamano così perché sono più liberali, si cerca di far eseguire i

processi, di evitare quindi il deadlock dinamicamente, durante l’esecuzione dei processi. Secondo queste tecniche ogni

processo deve dichiarare un numero massimo di risorse di un certo tipo di cui può avere bisogno e l’algoritmo di deadlock

avoidance esamina dinamicamente lo stato di allocazione della risorsa per assicurare che non si possa mai essere una

situazione di attesa circolare, vede se la richiesta può essere soddisfata in quel momento e se può la risorsa viene data,

altrimenti no. Lo stato di allocazione delle risorse è dato dal numero di risorse disponibili e dal numero massimo di risorse

che si possono richiedere.

Gli approcci sono due, di cui il primo è la Process Initiation Denial somiglia un po’ a quelli statici, per cui non si fa iniziare un

processo se le richieste che farà non sono compatibili con la situazione corrente di disponibilità delle risorse. È comunque

diverso dal meccanismo precedente, perché in questo caso le risorse non vengono assegnate tutte insieme, vengono

assegnate man mano che il processo le richiede, però all’inizio si fa un check. Data la situazione corrente di richieste del

sistema e le massime richieste che ogni processo in esecuzione può fare sulle risorse, si viene ammessi nel sistema se le

richieste, che sono extra, rientrano ancora nel budget. Quando poi vengono utilizzate, viene fatto dinamicamente, il che

vuol dire che l’esecuzione sarà meno restrittiva del caso in cui si acquisiscono tutte insieme, ma al contrario vengono

assegnate man mano che sono necessarie al processo che può effettivamente avere un’istanza di risorsa perché le

disponibilità sono a sufficienza rispetto alla richiesta.

L’altro tipo di approccio è il Resource Allocation Denial, in cui i processi partono, fanno richieste di risorse dinamicamente

e le risorse vengono assegnate/allocate ai processi sulla base della verifica di allocazione dello stato, purché il sistema evolva

in uno stato sicuro, che per definizione è uno stato in cui non si possono verificare deadlock.

Il modello su cui si basano queste tecniche sono le strutture dati, per cui il sistema operativo deve conoscere tutte le risorse

possibili, devono essere predefinite; per ogni risorsa il vettore R contiene il numero di istanze massime presenti; il vettore

available V stabilisce per ogni risorsa quante istanze sono rimaste, è un vettore che varia dinamicamente nel tempo; matrice

di claim C, di dimensione nxm, dove n è il numero di processi in esecuzione e m il numero risorse. Ogni processo dichiara il

proprio claim, per cui comunica che, pur non sapendo precisamente quando, avrà bisogno di determinate risorse ed in

particolare il numero di istanze di ognuna. Infine, c’è la matrice di allocazione A, in cui ogni elemento i-esimo indica

l’allocazione del processo i-esimo alla risorsa j-esima.

Facciamo un esempio: supponiamo di avere 3 risorse disponibili in queste quantità R=(7 3 1). Quando parte P1 dichiara un

claim C =(1 0 1), da cui costruiamo si viene a costruire la matrice di claim che inizialmente è proprio il vettore di claim di P1.

1

Successivamente parte un altro processo P2 con il suo claim C =(2 3 0).

2

La matrice di claim C diventa allora: 1 0 1

C = 2 3 0

Man mano che nascono i processi, aumentano le righe della matrice C, mentre se un processo dichiara uno o più risorse,

aumentano le colonne della matrice C. R e C sono matrici statiche perché sono dichiarate all’inizio, perché indicano quante

risorse abbiamo, in termini di istanze, e quali sono i claim, cioè quante potranno essere utilizzate al massimo. Non è detto

nemmeno che le userò tutte. Ecco perché il Process Initiation Denial è più liberale.

Le altre due matrici sono V, che dice quante istanze ancora si hanno disponibili per ciascuna risorsa: inizialmente sarà V=(7

3 1), ma man mano che le risorse vengono usate, si aggiorna. Quindi se P1 si prende un’istanza della risorsa 1, V viene

aggiornato e diventa V=(6 3 1). L’altra matrice è l’allocation matrix A, dato che a P1 abbiamo concesso un’unità della risorsa

R1, è : 1 0 0

A = 0 0 0

Il vettore V e la matrice A variano nel tempo, perché mi dicono qual è lo stato corrente di assegnazione delle risorse, mentr e

R e C sono costanti, più precisamente crescono nel tempo perché si possono aggiungere risorse, ma una volta aggiunta

quella è la dichiarazione.

La difficoltà di queste tecniche è che bisogna inventare librerie, attraverso cui il programmatore dichiara dei claim.

Il Process Initiation Denial consente l’attivazione di un processo se il claim del

nuovo processo, cioè l’n+1 rispetto ad n processi che già eseguono, il che

comporta l’aggiunta di una nuova riga alla matrice dei claim, dopo la verifica della

seguente condizione: verifichiamo per ogni j, cioè per ogni colonna, che il numero

di risorse totali disponibili di tipo j sia maggiore uguale del nuovo claim più tutti i

claim passati. Stiamo dicendo che un processo viene eseguito se il numero

massimo di richieste di tutti i processi più quelle del nuovo possono essere soddisfatte.

In pratica nell’esempio posso ammettere il processo due perché 1 (primo elemento della matrice C ) +2 (primo elemento

1

della matrice C ) è minore uguale di 7, ovvero del primo elemento del vettore R, che definisce le quantità disponibili; perché

2

0 (secondo elemento della matrice C ) + 3 (secondo elemento della matrice C ) è minore uguale di 3, secondo elemento del

1 2

vettore R; perché 1 (terzo elemento della matrice C ) + 0 (terzo elemento della matrice C ) è minore uguale di 1, terzo

1 2

elemento del vettore R. In questa situazione non posso ammettere processi che richiedono le risorse 2 e 3 perché per

chiunque chiede 2 e 3, avendo già assegnato tutte le istanze tra P1 e P2, trova che i vincoli non vengono rispettati. Potrann o

essere ammessi solo processi che chiedono la risorsa 1. Quando uno di questi due processi termina, si libera il cla