Semaforo (informatica)

Da Wikipedia, l'enciclopedia libera.

In informatica, un semaforo è una struttura dati gestita da un sistema operativo multitasking per sincronizzare l'accesso a risorse condivise tra task (cioè processi o thread). È composta da una variabile intera e da una coda di task.

Tale concetto è stato inventato da Edsger Dijkstra, e usato per la prima volta nel sistema operativo THEOS.

[modifica] Operazioni sui semafori

Il numero contenuto nel semaforo rappresenta il numero di risorse di un certo tipo disponibili ai task. Un caso particolare molto usato è il semaforo binario, in cui gli unici valori possibili sono 0 e 1.

Un semaforo può essere modificato da parte del codice utente solamente con tre chiamate di sistema:

Inizializzazione: Il semaforo riceve un valore intero.
Operazione P o wait': Il semaforo viene decrementato. Se il semaforo ha un valore negativo, il task viene sospeso e accodato, in attesa che il valore del semaforo torni positivo.
Operazione V o signal': Il semaforo viene incrementato. Se il semaforo ha un valore negativo o nullo, il primo dei task in coda viene tolto dalla coda e posto in stato di pronto.

I nomi P e V, sono stati proposti da Dijkstra come le iniziali delle parole olandesi "proberen" ("tentare") e "verhogen" ("incrementare").

Per garantire la coerenza semantica, le suddette operazioni devono essere atomiche, ossia non interrompibili. A tale scopo, il sistema operativo può disabilitre gli interrupt, oppure può usare un'istruzione speciale della CPU, come la 'test-and-set'.

[modifica] Significato intuitivo

Intuitivamente, il significato delle operazioni è il seguente.

Con l'inizializzazione si dichiarano quante unità di un tipo di risorsa sono disponibili.

Con l'operazione P, un task chiede di riservare un'unità della risorsa. Se non sono disponibili unità, il task viene messo in attesa, per essere risvegliato solo quando gli sarà assegnata l'unità richiesta.

Con l'operazione V, un task rilascia un'unità di un tipo di risorsa di cui non ha più bisogno, e per la quale altri task potrebbero già essere in attesa.

[modifica] Esempi di uso di semafori

[modifica] Mutua esclusione

Un utilizzo molto semplice dei semafori si ha per garantire la mutua esclusione nell'accesso a una risorsa semplice. In tal caso basta usare un semaforo binario.

Si chiama la P prima di iniziare a usare la risorsa, e si chiama la V dopo averla usata.

[modifica] Attesa di completamento multiplo

Un utilizzo più complesso è l'attesa del completamento di N operazioni simultanee.

Per esempio, un browser Web carica una pagina che contiene 4 immagini. Per velocizzare il caricamento, lancia 4 thread di caricamento delle immagini, uno per ogni immagine. Deve scoprire quando sono state caricate tutte le immagini.

A tale scopo, inizializza un semaforo a 0, lancia i 4 thread, ed esegue per 4 volte la P sul semaforo, probabilmente bloccandosi in realtà sulla prima delle 4 P. I thread, quando hanno completato il loro compito, eseguono una V sul semaforo. Tale operazione risveglia il thread principale che esegue un'altra P e si blocca nuovamente. Solo l'ultima V risveglia definitivamente il thread principale.

[modifica] Produttore-consumatore

Un'applicazione ancora più complessa è il problema cosiddetto del produttore-consumatore a buffer circolare.

Supponiamo di avere un task che acquisisce dei blocchi di dati da una periferica, e li deve passare a un task che li visualizza sullo schermo. Il primo task viene detto "produttore", in quanto trasmette i dati, e il secondo viene detto "consumatore", in quanto riceve i dati.

Questa situazione è la stessa che si verifica a livello di sistema operativo nelle pipe e nelle code di messaggi.

Lo scambio dei dati tra i due task avviene in un buffer circolare che contiene N record. Ogni record contiene un blocco di dati acquisibile dalla periferica.

Si vuole fare in modo che man mano che il produttore scrive i dati nel buffer, il consumatore proceda nel leggerli, senza attendere che il buffer sia pieno, ma evitando le seguenti situazioni:

Il produttore scrive i dati in un record sovrascrivendo dati non ancora letti dal consumatore.
Il consumatore legge da un record dati non validi, in quanto il produttore non ha ancora scritto i nuovi dati in quel record.
Il produttore e il consumatore accedono simultaneamente, non entrambi in lettura, alla stessa struttura dati.

Si può risolvere il problema usando tre semafori, che chiameremo "mutex", "pieno", "vuoto".

Il semaforo "mutex", inizializzato a 1, garantisce la mutua esclusione nell'accesso al buffer.
Il semaforo "pieno", inizializzato a 0, memorizza il numero di record pronti nel buffer, cioè scritti ma non ancora letti, e blocca chi tentasse di leggere da un buffer vuoto.
Il semaforo "vuoto", inizializzato a N, memorizza il numero posti liberi nel buffer, cioè di spazi in cui si possono scrivere record senza sovrascrivere record non ancora letti, e blocca chi tentasse di scrivere in un buffer pieno.

Il task produttore, quando ha acquisito un record da passare al consumatore, esegue le seguenti istruzioni (commentate):

P(vuoto) // Riserva un posto vuoto in cui scrivere il nuovo record
P(mutex) // Riserva l'accesso al buffer
Scrittura del record nel buffer
V(mutex) // Rilascia l'accesso al buffer
V(pieno) // Rende disponibile un record da leggere

Il task consumatore, quando ha bisogno di leggere dal buffer un nuovo record da visualizzare, esegue le seguenti istruzioni (commentate):

P(pieno) // Riserva un record da leggere
P(mutex) // Riserva l'accesso al buffer
Lettura del record dal buffer
V(mutex) // Rilascia l'accesso al buffer
V(vuoto) // Libera un posto in cui scrivere un nuovo record

[modifica] I semafori oggi

I semafori sono ancora usati normalmente nei linguaggi di programmazione che non supportano intrinsecamente altre forme di sincronizzazione. La tendenza nello sviluppo dei linguaggi di programmazione, tuttavia, è verso forme più strutturate di sincronizzazione come i monitor e i rendezvous.

Infatti, i semafori hanno due grossi difetti:

È facile per i programmatori eseguire una P su un semaforo già tenuto dallo stesso thread, e di dimenticare di eseguire la V dopo aver eseguito la P.
Si corre il rischio di incappare in deadlock. Per esempio, se il task T1 esegue una P sul semaforo S1, mentre il task T2 esegue una P sul semaforo S2, e poi T1 esegue una P su S2, poi T2 esegue una P su S1, si ha un deadlock.

Pertanto, i maggiori teorici della programmazione concorrente, compreso lo stesso Dijkstra, hanno dichiarato obsoleti i semafori, come tecnica di programmazione, anche se possono essere utili per implementare i costrutti di livello più alto.