Appunti di Sistemi operativi

SOLUZIONI SOFTWARE

Questo algoritmo è funzionale nel caso dell’alternanza tra 2 soli processi, perché garantisce tutte le regole

dell’alternanza corretta.

Per risolvere il problema dell’alternanza di n processi è stato implementato il cosiddetto algoritmo del

fornaio. Per farlo ci si appoggia ad un vettore di elementi booleani grande quanto il numero di processi

(choosing[i]). Il numero più basso avrà la precedenza sugli altri.

ALGORITMO DEL FORNAIO

SOLUZIONI HARDWARE

Una soluzione hardware per risolvere il problema della sezione critica è disattivare gli interrupt nel momento

in cui una variabile condivisa viene modificata. Gli interrupt però garantiscono il time-sharing e quindi non

devono essere disattivati a lungo. Un alternativa è creare istruzioni atomiche non interrompibili, come Test-

and-Set e Swap. È vantaggioso adottare soluzioni Hardware perché sono scalabili, cioè indipendenti dal

numero di processi coinvolti. Sono però molto più complesse per un programmatore rispetto alle soluzioni

software e con busy waiting, che è uno spreco di potenza di calcolo per la cpu.

Test-and-Set

Assegna TRUE a var e ritorna il vecchio valore di var. Viene utilizzato per creare una versione ottimizzata

dell’algoritmo del fornaio:

Swap

Scambia i valori di a con i valori di b; viene utilizzato in questo modo:

È da notare che i due algoritmi qui sopra non rispettano il criterio di attesa limitata. Per farli funzionare

bisogna inserire una variabile globale boolean waiting[n] e una variabile locale key = TRUE.

I SEMAFORI

I semafori sono una soluzione generica che funziona sempre. Constano di una variabile intera S a cui si può

accedere solo attraverso due primitive atomiche: Signal V(s) che incrementa di uno la variabile e Wait P(S)

che decrementa di uno oppure se a zero attente. Esistono due tipi di semafori: binari e interi.

I semafori binari hanno lo stesso potere espressivo di quelli a valori interi. Ecco l’implementazione di un

semamofo binario con busy waiting:

I semafori interi contengono al loro interno i semafori binari:

Così facendo si riduce la il busy waiting in termini significativi, ma non lo si elimina. I semafori vengono

utilizzati per:

- Garantire la mutua esclusione (il semaforo binario deve avere valore iniziale 1). L’algoritmo sarà

simmetrico per tutti i processi coinvolti.

- Sincronizzare i processi (il semaforo binario deve essere inizializzato a 0). L’algoritmo non sarà più

simmetrico e cambierà da processo a processo, spesso in modo complementare.

Se due processo devono sincronizzarsi per eseguire una sezione uguale di codice in momenti diversi,

verranno utilizzati due semafori incrociati.

PROBLEMI

Un processo potrà essere bloccato in attesa di un evento che solo lui stesso può generare (Deadlock), oppure

potrà essere in condizione di starvation, attesa indefinita all’interno di un semaforo.

1) PROBLEMA DEL PRODUTTORE-CONSUMATORE

2) PROBLEMA DEI FILOSOFI A CENA (dining philosophers)

Si tratta di n processi, tutti uguali, con a disposizione n risorse e ognuno dei processi ha bisogno di 2

risorse. I processi devono accedere ad entrambe le risorse solo quando sono entrambe libere! In caso

contrario si andrebbe in Deadlock. Bisogna bloccare chi compie l’azione quindi, non la risorsa.

La soluzione ottimale consiste nel dividere i filosofi in 3 stati: pensanti (zona non critica), affamati (vuole

entrare in zona critica) e mangianti (zona critica).

3) PROBLEMA DEL BARBIERE DORMIENTE (sleeping barber)

Due processi diversi, uno per il barbiere e uno per i clienti.

LIMITAZIONI DEI SEMAFORI

L’utilizzo dei semafori porta alcune difficoltà, soprattutto nella scrittura del programma e nella scarsa

visibilità della correttezza delle soluzioni. In alternativa, vengono utilizzati specifici costrutti forniti da

linguaggi di programmazione multilivello come Monitor, Classi synchronized di Java e CCR.

MONITOR

I monitor sono costrutti per la condivisione sicura ed efficiente di dati fra i processi. Sono simili al concetto

di classe. Le variabili del monitor ovviamente sono variabili locali, visibili solo all’interno del monitor e le

procedure del monitor accedono solo alle variabili definite

nel monitor. In un monitor è attivo solo un processo per

volta. Così facendo il programmatore non deve codificare

esplicitamente la mutua esclusione, ma concentrarsi solo

all’attesa di eventi.

Per permettere ad un processo di attendere all’interno del

monitor sono necessari opportuni tipi di sincronizzazione.

Le variabili condition, dichiarate all’interno del monitor e

accessibili solo tramite le due primitive signal() [V()] e wait() [P()]. Ad esempio se un processo invoca x.wait()

sarà bloccato fino alla successiva x.signal() da parte di un altro. La signal() infatti sveglia esattamente un

processo. Se ci sono più processi in attesa, lo scheduler deciderà quale entrerà nella sezione critica. Non ha

nessun effetto se nessun processo è in attesa. Il processo che invoca la signal() può:

- Bloccarsi e lasciare il posto al processo sbloccato;

- Uscire dal monitor, se è l’ultima istruzione di una procedura.

I problemi collegati ai monitor sono dovuti al fatto che:

- Pochi linguaggi forniscono i monitor;

- Richiedono la presenza di memoria condivisa.

DEADLOCK

Un insieme di processi è in deadlock quando ogni processo è in attesa di un evento che può essere causato

da un processo dello stesso insieme. Il deadlock dipende dalla dinamica della esecuzione, infatti in alcuni casi

potrebbe avvenire mentre in altri no.

Le condizioni necessarie sono:

- MUTUA ESCLUSIONE (almeno una risorsa deve essere non condivisibile);

- HOLD AND WAIT (Un processo almeno detiene una risorsa e attende di acquisirne un'altra detenuta

da un altro);

- NO PREEMPTION (Le risorse possono essere rilasciate solo dal processo che le usa);

- ATTESA CIRCOLARE (L’insieme di processi attendono ciclicamente il liberarsi di una risorsa)

Si può verificare un deadlock solo se sono vere contemporaneamente.

RAG

Il RAG (Resource Allocation Graph) è un metodo per scoprire se ci possono essere deadlock.

I nodi (V) sono processi (cerchi) oppure risorse (rettangoli). Gli archi (E) sono direzionali: da processo a risorsa

indica una richiesta, da risorsa a processo indica la detenzione del processo di quella determinata risorsa.

Le possibilità sono tre: 

- Se contiene cicli al suo interno e si ha una sola istanza per risorsa DEADLOCK;



- Se non contiene cicli al suo interno NO DEADLOCK; 

- Se contiene cicli al suo interno e si ha più di una istanza per processo dipende dallo schema di

allocazione.

Alternative per la gestione del Deadlock

1) Prevenzione statica

Evitare che si verifichi almeno una delle quattro condizioni.

La mutua esclusione è irrinunciabile e quindi impossibile toglierla.

Si potrebbe sistemare la hold and wait imponendo che un processo allochi all’inizio tutte le risorse

che deve utilizzare e può richiedere una risorsa solo se non ne ha altre, però le risorse vengono poco

utilizzate, oltre alla possibile starvation e all’impossibilità di conoscere a monte il numero di risorse

richieste.

Si potrebbe sistemare il No preemption imponendo che un processo che richiede una risorsa non

disponibile debba cedere tutte le altre risorse che detiene, oppure cede risorse che detiene su

richiesta di un altro processo; però è fattibile solo per risorse il cui stato può essere facilmente

ristabilito come CPU registri semafori e file, non con risorse come stampanti e nastri.

Si potrebbe sistemare l’attesa circolare assegnando una priorità globale ad ogni risorse, in modo che

un processo possa richiedere solo risorse in ordine crescente di priorità.

Tutte queste soluzioni però possono portare a un basso utilizzo delle risorse con tutti i vincoli sul loro

accesso da parte dei processi.

2) Prevenzione dinamica

Mai utilizzata perché richiede una conoscenza delle risorse troppo approfondita. Si tratta dell’analisi

dinamica del grafo delle risorse per evitare situazioni cicliche. Si applica cercando che il sistema sia

in uno stato safe, cioè se usando le risorse disponibili può allocare risorse ad ogni processo, in qualche

sequenza, in modo che ognuno di essi possa terminare la sua esecuzione. Se tale sequenza non esiste

allora ci si trova in uno stato unsafe, cioè che può andare in deadlock. Due algoritmi per la

prevenzione dinamica sono il RAG e l’algoritmo del banchiere.

L’algoritmo con RAG funziona solo se c’è una sola istanza per risorsa. Vengono aggiunti archi di

richiamo (tratteggiati) che indicano la possibilità di richieste future. All’inizio ogni processo deve dire

quali risorse vorrebbe utilizzare e l’allocazione viene soddisfatta soltanto se non si crea un ciclo nel

2

RAG, con un algoritmo di complessità O(n ), con n numero di processi.

L’algoritmo del banchiere è meno efficiente del precedente ma funziona con più istanze delle risorse.

Ogni processo dichiara la sua massima richiesta. Ogni volta che un processo richiede una risorsa, si

determina se soddisfarla ci lascia uno stato di safe, dividendosi in due algoritmi di allocazione e

verifica dello stato.

3) Rivelazione e ripristino

Permettere che si verifichino deadlock e riportare il sistema bloccato al suo funzionamento normale.

La rilevazione e ripristino tramite RAG funziona solo con una risorsa per tipo e consiste nell’analizzare

periodicamente il RAG per verificare se esistono deadlock e iniziare il ripristino. Così facendo non si

ha bisogno di sapere in anticipo le richieste e viene utilizzato il sistema in modo migliore, a patto di

un elevato costo di ripristino.

L’algoritmo di rilevazione è basato sull’esplorazione di ogni possibile sequenza di allocazione per i

processi che non hanno ancora terminato. Una volta trovata una situazione di deadlock si può:

o Uccisione di tutti i processi: molto costoso perché tutti i processi devono ripartire perdendo

il lavoro svolto;

o Uccisione selettiva: costosa perché invoca l’algoritmo di rilevazione dopo ogni uccisione, fino

alla scomparsa del deadlock;

o Prelazione delle risorse: rollback in uno stato safe e ripartenza da questo stato.

La soluzione è combinata, infatti si partizionano le risorse in classi ordinate e all’interno di ogni classe

utilizzare l’algoritmo più appropriato per quella classe. L’ordine delle classi è: risorse interne,

menoria, risorse di processo e spazio di swap.

4) Algoritmo dello struzzo

Ignorare la possibilità che si verifichi un deadlock per rendere il sistema pi&ug