Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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)

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)

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)

Codice (implementazione reale)


Implementazione di wait

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

Codice relativo al 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

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)

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)

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

Codice relativo al comando wait


Funzione signal

In figura il codice relativo al comando signal.

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

Codice ed esempio grafico


Prima soluzione

In figura lo schema relativo alla soluzione.

Schema grafico della 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

Codice del processo produttore


Processo consumatore

Codice del 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

Codice del problema


Processo produttore

Codice del processo produttore

Codice del processo produttore


Processo consumatore

Codice del 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.

Processo produttore

Codice del processo produttore

Codice del processo produttore


Processo consumatore

Codice del processo consumatore

Codice del processo consumatore


Prossima lezione

Allocazione contigua dei processi in memoria centrale

  • Background
  • Allocazione a partizioni fisse
  • Allocazione a partizioni variabili
  • Il problema della frammentazione
  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion