Semaforo (informatica)

In informatica, un semaforo è un tipo di dato astratto (Abstract Data Type) gestito da un sistema operativo multitasking per sincronizzare l'accesso a risorse condivise tra task (cioè processi o thread). È composto da una variabile intera e dalla sua interfaccia, e da una coda di processi.

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

Operazioni sui semafori

Il numero contenuto nel semaforo rappresenta il numero di risorse di un certo tipo disponibili ai task (processi). Un caso particolare molto usato è il semaforo binario, in cui gli unici valori possibili sono 0 e 1. Un semaforo che può avere solo valori 0 e 1 viene definito mutex.

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

• Inizializzazione: Il semaforo viene inizializzato con un valore intero e positivo.
• Operazione P o wait: Il semaforo viene decrementato. Se, dopo il decremento, il semaforo ha un valore negativo, il task viene sospeso e accodato, in attesa di essere riattivato da un altro task.
• Operazione V o signal: Il semaforo viene incrementato. Se ci sono task in coda, uno dei task in coda (il primo nel caso di accodamento FIFO) viene tolto dalla coda, posto in stato di ready (sarà perciò eseguito appena schedulato dal sistema operativo) e richiama P per decrementare.

Il valore del semaforo, una volta inizializzato, non può più essere letto, se non indirettamente tramite le primitive P e V.

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

Implementazione

Le operazioni suddette sono corrette soltanto se non vengono interrotte da altri task.

Supponiamo invece che due task si "accavallino" ed eseguano "quasi" contemporaneamente l'operazione P su un semaforo che ha valore 1. Subito dopo che il primo task ha decrementato il semaforo da 1 a 0, il controllo passi ora al secondo task, che decrementa il semaforo da 0 a -1 e quindi si pone in attesa. Allora a questo punto il controllo torna al primo task che, siccome il semaforo ha ora un valore negativo, si pone anche lui in attesa. Il risultato è che entrambi i task sono bloccati, mentre il semaforo a 1 avrebbe consentito a uno dei due task di procedere.

Esistono sofisticati algoritmi per implementare correttamente le operazioni sui semafori senza far uso di istruzioni speciali della CPU. Tuttavia, dato che le operazioni sui semafori vengono eseguite dal kernel del sistema operativo, risulta possibile, e più efficiente, ricorrere ad apposite istruzioni.

Una corretta implementazione si può ottenere disabilitando gli interrupt, e quindi i cambi di contesto, prima delle operazioni P e V, e riabilitandoli subito dopo. Tale implementazione ha il difetto di richiedere due istruzioni aggiuntive.

Su alcuni processori esiste l'istruzione 'Test-and-set', che in modo atomico modifica un registro ed esegue un salto condizionato dal valore precedente di tale registro. Usando tale istruzione è possibile implementare le operazioni sui semafori in modo sicuro ed efficiente.

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 (wait), "Pazienta", 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 (signal),"Vai!", un task rilascia l'unità di cui non ha più bisogno e per la quale altri task potrebbero già essere in attesa.

Esempi di uso di semafori

Pseudo-codice P e V

P()
{
    s--; //variabile del semaforo
    if(s < 0 ){
        mette il Thread nella coda del Semaforo
        s++;
    }
}

V()
{
    s++; //variabile del semaforo
    if(isQueue()){ //E' presente almeno 1 thread nella coda
        mette il primo Thread nella lista dei Pronti (ReadyList)
        s--; //In realtà chiama P() che effettua il decremento
    }
}

P(): decrementa il valore solo se rimane positivo. Nel caso in cui il valore diventi negativo, mettere il thread nella coda del semaforo ed incrementa il valore di s (in pratica viene ripristinato il valore che avevamo prima della chiamata di P).

V(): incrementa il valore. Nel caso in cui ho 1 o più thread nella lista d'attesa, prelevo il primo e lo inserisco nella lista dei pronti. Successivamente effettuo una chiamata a P() che decrementà il valore (N.B: questa chiamata a P() risulterà sempre con un decremento poiché precedemente abbiamo aumentato di 1 il valore della variabile). Se non sono presenti thread nella lista d'attesa il risultato sarà che avremo la variabile incrementata di 1.

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.

Sincronizzazione

Le primitive P e V sono utilizzate per sincronizzare l'esecuzione di due processi o thread, fare cioè in modo che un processo venga eseguito dopo l'esecuzione di un altro processo. Ad esempio se il processo P2 deve essere eseguito dopo il processo P1, si può utilizzare un semaforo s inizializzato a 0. Inserire la primitiva V(s) alla fine del processo P1 e la primitiva P(s) all'inizio del processo P2. Il processo P2 sarà bloccato su P(s) fintantoché il processo P1 non avrà eseguito V(s), cioè non avrà ultimato l'esecuzione del codice posto prima a V(s).

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 (wait) sul semaforo, probabilmente bloccandosi in realtà sulla prima delle 4 P (wait). I thread, quando hanno completato il loro compito, eseguono una V (signal) sul semaforo. Tale operazione risveglia il thread principale che esegue un'altra P (wait) e si blocca nuovamente. Solo l'ultima V (signal) risveglia definitivamente il thread principale.

Produttore-consumatore

Un'applicazione ancora più complessa è il cosiddetto problema 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

I semafori oggi

I semafori sono ancora usati normalmente nei linguaggi di programmazione che non supportano intrinsecamente altre forme di sincronizzazione. Esempi di linguaggi molto noti che non supportano direttamente altre forme di sincronizzazione sono C e C++. 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, ovvero in stallo. 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.

Voci correlate

• Problema delle montagne russe (Roller coaster problem)

Collegamenti esterni

• Esercizi svolti ed esempi di programmazione concorrente, su wiki.altervista.org.