Appunti di Sistemi Operativi

Z.

Nel grafo di esempio, le precedenze dirette sono per

esempio D,L <• F; Q<• ω; A,B,K,S <• E; α,B <• A.

Consideriamo i nodi legati a rami ridondanti, per esempio α precede B il quale precede A,

dunque ovviamente α precede A e il ramo (α, A) è ridondante.

Possiamo ricavare la partizione I =α; I =B,S; I =A,L; I =D; I =F,K; I =E; I =Q; I =ω. Data

0 1 2 3 4 5 6 7

questa partizione, il grado massimo di parallelismo è 2.

Interferenza e determinatezza

La determinatezza entra in gioco quando più processi cooperano: se le

diverse velocità dei processi e l’ordine di esecuzione non influenzano il

risultato allora si dice che il sistema è determinato; altrimenti si dice

indeterminato.

Per esempio, il processo 1 compie a=a×c+b, il processo 2 compie

b=a×d+b. La prima espressione utilizza un valore di b precedente alla

seconda, la quale utilizza il valore di a successivo alla prima espressione.

Aggiungiamo vincoli di precedenza affinché questo sia rispettato.

Ad ogni processo associamo un dominio, un codominio e la funzione mappa: il dominio

contiene i dati su cui il processo lavora; il codominio contiene i risultati del processo; la

funzione mappa trasforma i dati di input nell’output.

- 27 -

Due processi si dicono non interferenti se almeno una delle due osservazioni è valida:

• Uno è il successore dell’altro

• Non si intersecano i codomini e neppure i domini con i codomini

Condizione necessaria e sufficiente affinché un sistema sia determinato è che sia composto da

processi non interferenti. Due sistemi di processi sono equivalenti se sono costituiti dallo

stesso insieme di processi, sono determinati e partendo dallo stesso input producono lo stesso

output.

Risorse

La risorsa è un’astrazione per rappresentare una entità necessaria ad un processo per svolgere

il proprio lavoro. Se la risorsa non è disponibile, il processo ovviamente dovrà attendere per

utilizzarla. Il termine risorsa è generico, può essere l’output di un altro processo, memoria…

Dividiamo le risorse in due tipi:

• Risorse condivisibili, possono essere usate da più processi in parallelo (più processi

accedono alla RAM)

• Risorse non condivisibili, non possono essere usate nello stesso tempo (stampante)

Si dividono ulteriormente in:

• Non consumabile (es. un core di una CPU può essere riutilizzato)

• Consumabile, e in tal caso si parla di risorse esterne al sistema, es. robot che può

ricaricarsi da power pack separato dalla rete.

Con il termine preemption definiamo la rimozione forzata di una risorsa ad un processo (tale

risorsa viene definita sottraibile), come per es. la CPU viene sottratta ad un processo a bassa

priorità se un processo ad alta priorità necessità di potenza di calcolo.

Evoluzione dei processi

Nel semplice caso di due processi, la loro evoluzione è rappresentabile con un sistema di assi

cartesiani. Un punto in tale piano (piano degli stati) rappresenta l’evoluzione, il punto P

rappresenta la terminazione del sistema (sia esecuzione del processo A che del processo B è

stata completata)

Stallo

Definiamo «stallo» quando più processi si bloccano a vicenda e nessuno può terminare la

propria esecuzione. Nell'esempio precedente non ci sono problemi in quanto ogni processo usa

risorse non condivisibili separate.

Nel seguente esempio sia il processo B che A richiedono la risorsa R1, tutte le traiettorie

dalla fase iniziale alla fase finale che passano attraverso «la zona ombreggiata» (definita

regione vietata) sono impossibili, in quanto R1 non è condivisibile, viene assegnata ad uno

dei due processi. Le due traiettorie in figura sono due possibili traiettorie valide.

- 28 -

Se raggiungiamo uno stallo è necessario eliminare i processi bloccati e a loro volta i processi

che dipendono dai processi bloccati e così via. Ovviamente evitare il più possibile situazioni

di stallo. Elenchiamo le condizioni necessarie per il verificarsi di uno stallo:

1. Mutua esclusione, risorse utilizzate da un solo processo alla volta;

2. Allocazione parziale, processo richiede le diverse risorse durante la sua evoluzione (non

tutte in una singola operazione);

3. Non sottraibilità delle risorse, solo il processo che possiede la risorsa può rilasciarla;

4. Attesa circolare, in cui n processi si bloccano a coppie; ogni processo aspetta una risorsa

che non verrà rilasciata, tutti aspettano, nessuno lavora.

Sono condizioni necessarie ma non sufficienti, infatti nell’esempio precedente esistono

traiettorie che non portano a stalli e permettano ai processi di terminare.

Individuare lo stallo

Introduciamo una rappresentazione grafica denominata grafo di assegnazione delle risorse

(detto grafo di Holt): è un grafo orientato con due tipi di nodi e archi che collegano nodi di

diverso tipo. Un processo è rappresentato da un cerchio etichettato con il suo nome, mentre

un insieme di risorse (denominato magazzino) viene rappresentato mediante un rettangolo

con indicato il numero di risorse di un certo tipo.

Esistono due tipi di archi:

• Arco di richiesta (da processo a magazzino)

• Arco di assegnazione (da magazzino a processo)

La condizione di stallo può essere verificata mediante un

algoritmo denominato «individuazione del blocco critico».

Un grafo di Holt è completamente riducibile se esiste una sequenza di passi di riduzione che

elimina tutti gli archi del grafo:

• Una riduzione è possibile se un processo può vedersi assegnate risorse in modo tale da

soddisfare la sua richiesta.

• Essenzialmente, se un processo può acquisire tutte le risorse che necessita, allora potrà

terminare.

• Se tutti i processi terminano allora il sistema non sarà in stallo.

Un sistema non è in stallo se e solo se il grafo di Holt è completamente riducibile.

- 29 -

Esempio. Abbiamo un sistema con 4 processi (P1…P4) e 3 risorse. Il DECL R1 R2 R3

grafo di Holt può essere descritto dalle seguenti tabelle: S 3 3 1

• una tabella Allocated Quantities, che descrive gli archi di P1 2 1 0

assegnazione da Rx a Px; P2 2 1 1

P3 0 2 1

• una tabella Requests, che descrive gli archi di richiesta da Px a Rx; P4 1 1 1

• una tabella Declarations, che contiene tutte le somme AQ R1 R2 R3

Dunque, per esempio, si evince che P1 ha un solo arco di assegnazione da S 2 3 0

R2, e P1 richiede 2 R1 e non ha altri archi di richiesta verso altre Rx. P1 0 1 0

Una riga Px della tabella REQ può essere ridotta se è vettorialmente ≤ P2 1 0 0

della riga S della tabella REQ, e dunque le sue richieste possono essere P3 0 1 0

soddisfatte. P4 1 1 0

La riduzione implica di eliminare il processo dalla tabella REQ e REQ R1 R2 R3

incrementare S delle risorse assegnate (tabella AQ) al processo ridotto. S 1 0 1

La riduzione è completa quando tutte le righe della tabella REQ sono P1 2 0 0

eliminate, se avviene allora il sistema non è in stallo. P2 1 1 1

P3 0 1 1

Nel nostro caso, per esempio: P4 0 0 1

• P4 può terminare perché REQ[P4] REQ[S], dunque libera le sue

≤

risorse assegnate e REQ[S] += AQ[P4] = [1 0 1] + [1 1 0] = [2 1 1]

• P1 può terminare, similarmente REQ[S] += AQ[P1] = [2 1 1] + [0 1 0] = [2 2 1]

• P2 può terminare, similarmente REQ[S] += AQ[P2] = [2 2 1] + [1 0 0] = [3 2 1]

• P3 può terminare e dunque il sistema non è in stallo.

Prevenzione dello stallo

Allocazione globale

Questo metodo è realizzabile quando sono note esattamente le risorse utilizzate dai processi.

Semplicemente richiede tutte le risorse che necessita per il suo completamento. Permette

senza problemi di evitare lo stallo in sistema di più processi, ma dalla descrizione è ovvio il

problema, la cattiva utilizzazione delle risorse.

Allocazione gerarchica

Per prima cosa stabilire un ordinamento delle risorse assegnando ad ognuna di esse un

numero intero proporzionale all’importanza.

Allora un processo che sta usando risorse può acquisirne altre più importanti. Se invece il

processo richiede una risorsa meno importante rispetto a quella usata deve prima rilasciare la

risorsa e poi richiedere la meno importante.

Algoritmo del banchiere

Le risorse vengono allocate solo se la concessione non rende possibile uno stallo, e le risorse

residue sono sufficienti alla terminazione del processo richiedente. Si definiscono:

• Sequenza sicura: un ordinamento dei processi t.c. le richieste di un processo sono

soddisfacibili dalle risorse disponibili + quelle possedute dai processi inferiori

• Stato sicuro: assegnazione di risorse che ammette almeno una sequenza sicura

- 30 -

Per esempio, un semplice caso con risorse di un solo tipo. Siano:

• M il numero massimo di risorse che P necessita, e D il totale di risorse disponibili;

i i

• A e R il numero di risorse assegnate-al e richieste-dal processo P nella fase j;

ij ij i

• Sia D il totale di risorse disponibili durante la fase j.

j

Solo i processi che possono portare a termine la propria esecuzione avranno concesse le risorse

richieste. La condizione di terminazione del processo P è che M - A D , cioè che il numero di

≤

i i ij j

risorse disponibili del sistema sia maggiore delle risorse necessarie al processo.

Poniamo dunque per esempio di avere un magazzino e due processi:

• D = 3; M = 2; M = 3

0 1 2

• D = 2; A = 1; A = 0: in questa situazione non verrebbero concesse risorse a P , dato che

1 11 21 2

M – A D non è verificata (3 – 0 2 falso)

≤ ≤

2 21 1

• Se tale concessione invece avvenisse avremmo D = 1; A = 1; A = 1. Allora P potrebbe

2 12 22 1

ancora terminare (M – A D → 2 – 1 1 vero) e rilasciare le risorse in modo tale che P

≤ ≤

1 12 2 2

possa a sua volta terminare.

Se a un processo viene negata una concessione, può:

• Attendere

• Svolgere altre attività

• Sospendersi e riattivarsi solo quando le risorse sono disponibili

Regioni critiche

Abbiamo n processi che competono per utilizzare dati condivisi. Ciascun processo è costituito

da un segmento di codice, chiamato sezione critica (o regione critica), in cui accede a dati

condivisi.

Problema: assicurarsi che, quando un processo accede alla propria sezione critica, a nessun

altro processo sia concessa l’esecuzione di un’azione analoga. L’esecuzione di sezioni critiche

da parte di processi cooperanti è mutuamente esclusiva nel tempo.

Definiamo regioni critiche condizionali quando esistono condizioni d