Lezione 7 Sistemi operativi

IMPLEMENTAZIONE DEI SEMAFORI:

Un semaforo può esere concettualmente impemetato così.

Class Semaforo{

Int value;

LinkedList<Process> listaProcessi = new

LinkedList<Process>();}

Per evitare il busy waiting assumiamo di poter usare le

seguenti operazioni:

- Block(): sospende il processo che la invoca;(running

-> ready)

- Wakeup(P): riprende l’esecuzione del processo

bloccato P; (ready-> running)

Supponiamo che sia dichiarato un Semaforo S con valore

iniziale 1:

wait(S):

S.value --;

if (S.value<0){

aggiunge questo processo a S.listaProcessi;

block();}

signal(S):

S.value++;

if (S.value <= 0){

rimuove un processo P da S.listaProcessi;

wakeup(P);}

Il semaforo può assumere valori negativi; in questo caso il

valore assoluto indica il numero di processi in attesa su

quel semaforo.

La wait di fatto fa attendere il processo. Quindi decrementa

il valore del semaforo e fa un controllo. Se la coda è minore

di zero allora aggiunge il processo alla coda di attesa;

La signal vuole far diventare verde il semaforo (se il

semaforo è contatore allora si diminuisce la coda dei

pronti);

Per gestire la mutua esclusione tra N processi si può usare

un semaforo;

I semafori possono essere semafori binari e contatori;

Processo Pi: (Dati condivisi: mutex =1)

while (true){

wait(mutex);

sezione critica;

signal(mutex);

sezione non critica}

L’esempio sopra svolto ci mostra come gestire la mutua

esclusione della sezione critica con i semafori;(mutex =

new Semaforo)

DEADLOCK E STARVATION:

I semafori se non implementati in maniera corretta possono

condurre alla Deadlock o Starvation.

Deadlock: letteralmente traducibile come “stallo”, avviene

quando due o più processi sono indefinitamente in attesa

per un evento che può essere causato da uno soltanto dei

processi in attesa. La situazione di deadlock può verificarsi

con i presupposti, ma anche se questi presupposti ci sono

potrebbe non verificarsi (vd. lezione);

Starvation: blocking indefinito di un processo, ad esempio

un processo potrebbe non essere mai rimosso dalla coda

del semaforo in cui è sospeso. Comunque gli altri processi

potrebbero andare avanti (meno grave del deadlock);

SEMAFORI BINARI:

Il semaforo binario è un semaforo il cui valore intero può

essere solo 0 o 1. Risulta utile nella gestione di due

processi. Si può implementare un semaforo binario a

partire da uno contatore;

SEMAFORO CONTATORE:

Il semaforo contatore è così chiamato poiché mira alla

gestione di più processi, quindi il suo valore intero può

spaziare su un dominio specificato;

LA CLASSE SEMAFORO:

java.util.concurrent.Semaphore

Implementa un semaforo contatore simile a quello definito

in precedenza;

presenta comunque alcune differenze con il semaforo sopra

descritto:

- Al posto dei metodi descritti ci sono i metodi acquire()

e release();

- Il valore massimo del contatore è fissato nel

costruttore;

- Un thread può incrementare o decrementare il

contatore del semaforo di una quantità non

necessariamente unitaria;