Home

Federica EU

1/29

Marco Lapegna » 10.I semafori

Sistemi operativi

I semafori

Semafori

I meccanismi di sincronizzazione basati su dati condivisi hanno lo svantaggio dell’attesa attiva con conseguente consumo di cicli di cpu
I semafori sono strumenti di sincronizzazione che superano il problema dell’attesa attiva

Semafori

Il semaforo contiene una variabile intera S che serve per proteggere l’accesso alle sezioni critiche.

Si può accedere al semaforo (alla variabile) solo attraverso due operazioni atomiche:

wait(S): il processo chiede di accedere alla propria sezione critica. Esso aspetta se altri processi sono dentro la loro sezione critica
signal(S): il processo vuole uscire dalla propria sezione critica

Definizione di wait e signal

wait (S)
- se S>0 allora S=S-1 e il processo continua l’esecuzione
- altrimenti (S=0) il processo si blocca
signal(S)
- esegue S=S+1

Altri nomi di wait e signal:

wait ( ) == down ( ) == P ( )
signal ( )== up ( ) == V ( )

Sezione critica con n processi

Variabili condivise tra gli n processi:

semaphore mutex; // inizialmente mutex = 1

Processo Pi:

Codice (sezione critica)

Implementazione ingenua dei semafori

S > 0 -> possibile accedere alla regione criticaS = 0 -> non e’ possibile accedere alla regione critica

La mutua esclusione alla variabile S, facilmente realizzabile con TestAndSet o Swap
Non risolve il problema dell’ “attesa attiva”

Codice (implementazione ingenua)

Implementazione reale dei semafori

Si definisce un semaforo come una struttura del tipo in figura:

Si assume che siano disponibili due operazioni (syscall):

block sospende il processo che la invoca
wakeup(P) riprende l’esecuzione di un processo sospeso P

Codice (implementazione reale)

Implementazione di wait

In figura il codice relativo all’implementazione del comando wait.

Codice relativo al comando wait

Implementazione di signal

In figura il codice relativo all’implementazione del comando signal.

Codice relativo al comando signal

Problema

Come garantire che le operazioni wait e signal vengano eseguite atomicamente?

-> (mettiamo un semaforo su un semaforo?)

Essendo funzioni di piccole dimensioni in questi casi si disabilitano le interruzioni durante l’esecuzione delle funzioni

Sincronizzazione con semafori

Ad esempio: si vuole eseguire B in Pj solo dopo che A è stato eseguito in Pi

Si impiega un semaforo flag inizializzato 0

Codice (sincronizzazione)

Un pericolo con i semafori: Deadlock

Due o più processi sono bloccati in attesa di un evento che può essere generato solo da uno dei due processi in attesa.

Siano S e Q due semafori inizializzati a 1.

Codice (deadlock)

Due tipi di semafori

Semaforo contatore — intero che può assumere valori in un dominio non limitato.
Semaforo binario — intero che può essere posto solo a 0 o 1; può essere implementato più semplicemente.

Un semaforo contatore può essere realizzato mediante due semafori binari.

Realizzazione di S con semafori binario

Strutture dati:

binary-semaphore S1, S2;
int C:

Inizializzazione :

S1 = 1
S2 = 0
C = valore iniziale del semaforo S

Funzione wait

In figura il codice relativo al comando wait.

Codice relativo al comando wait

Funzione signal

In figura il codice relativo al comando signal.

Codice relativo al comando signal

Esempio: problema del produttore–consumatore

È un paradigma classico per processi cooperanti. Il processo produttore produce informazioni che vengono consumate da un processo consumatore.

Buffer illimitato: non vengono posti limiti pratici alla dimensione del buffer.
Buffer limitato: si assume che la dimensione del buffer sia fissata.

Esempio: Un programma di stampa produce caratteri che verranno consumati dal driver della stampante.

Buffer limitato e memoria condivisa

in indice della successiva posizione libera
out indice della prima posizione occupata

Codice ed esempio grafico

Prima soluzione

In figura lo schema relativo alla soluzione.

Schema grafico della soluzione

Osservazione

La condizione in == out equivale sia a “buffer pieno” sia a “buffer vuoto”

Non è possibile utilizzare tutti gli elementi del buffer (se ne possono usare solo BUFFER_SIZE – 1)

in == out -> buffer vuoto
(in+1) %BUFFER_SIZE == out -> buffer pieno

Processo produttore

Codice del processo produttore

Processo consumatore

Codice del processo consumatore

Problema

Trovare una soluzione che utilizza tutti gli elementi del buffer
La variabile counter (numero di elementi presenti nel buffer) permette di evitare l’ambiguità

Codice del problema

Processo produttore

Codice del processo produttore

Processo consumatore

Codice del processo consumatore

Soluzione con i semafori

Variabili condivise:

semaphore full, empty, mutex;

// inizialmente full = 0, empty = n, mutex = 1

Il buffer ha n posizioni, ciascuna in grado di contenere un elemento.

Il semaforo binario mutex garantisce la mutua esclusione sugli accessi al buffer.
I semafori contatore empty e full contano, rispettivamente, il numero di posizioni vuote ed il numero di posizioni piene nel buffer.