Semaforo (informatica)

In informatica, un semaforo è un tipo di dato astratto gestito da un sistema operativo in 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 "proberen" ("verificare") e "verhogen" ("incrementare").

Implementazione

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

Si supponga 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 c'era prima della chiamata di P).

V(): incrementa il valore. Nel caso in cui si avessero 1 o più thread nella lista d'attesa, si preleva il primo e si inserisce nella lista dei pronti. Successivamente si effettua una chiamata a P() che decrementerà il valore (N.B: questa chiamata a P() risulterà sempre con un decremento poiché precedentemente si è aumentato di 1 il valore della variabile). Se non sono presenti thread nella lista d'attesa il risultato sarà che 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.

Si supponga 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 si possono chiamare "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

Pattern generici

I semafori sono stati proposti come base in diversi schemi risolutivi generici per problemi di programmazione concorrente in cui più processi competono per una stessa risorsa con condizioni complesse di accesso (come ad esempio soddisfare specifici criteri di priorità o evitare la starvation). Il "passaggio del testimone" e "ci penso io" sono due possibili schemi di questo tipo; entrambi richiedono un semaforo privato "priv" (inizializzato a zero) per ciascun processo coinvolto e un unico semaforo "mutex" di mutua esclusione (inizializzato a uno). Per entrambi i pattern, lo pseudo-codice di ciascun processo è:

void processo(int proc_id)
{

	acquisizione_risorsa(proc_id);
	uso_risorsa;
	rilascio_risorsa(proc_id);
}

I due pattern si differenziano per il modo leggermente diverso in cui definiscono le primitive di acquisizione e rilascio della risorsa.

Passaggio del testimone

Lo pseudo-codice delle primitive di acquisizione e rilascio della risorsa nello schema "Passaggio del testimone" è:

void acquisizione_risorsa(int proc_id)
{
	P(&mutex);
	if !(<condizione_verificata_per(proc_id)>)
	{
		<indicazione che proc_id è sospeso>;
		V(&mutex);
		P(&priv[proc_id]);
		<indicazione che proc_id non è più sospeso>;
	}
	<allocazione della risorsa a proc_id>;
	V(&mutex);
}

void rilascio_risorsa(int proc_id)
{
	P(&mutex);
	<rilascio della risorsa da proc_id>;
	if <esiste almeno un processo sospeso per cui vale condizione_verificata_per()>
	{
		int p = <scelta processo da riattivare>;
		signal(&priv[p]);
	}
	else
	{
		signal(Mutex)
	}
}

Osservazioni

Lo schema prende il nome di "passaggio del testimone" perché il processo che rilascia la risorsa attiva al massimo un processo sospeso; sarà compito di quest'ultimo provvedere a sua volta alla riattivazione di eventuali altri processi al momento del rilascio. Poiché il codice che segnala che la risorsa è allocata a un processo è presente solo nella primitiva di acquisizione, risulta più complesso rimuovere dalla sospensione più processi per i quali la condizione di accesso alla risorsa è diventata vera.

Ci penso io

Lo pseudo-codice delle primitive di acquisizione e rilascio della risorsa nello schema "Ci penso io" è:

void acquisizione_risorsa(int proc_id)
{
	P(&mutex);
	if (<condizione_verificata_per(proc_id)>)
	{
		<allocazione della risorsa a proc_id>;
		V(&mutex);
	}
	else
	{
		<indicazione che proc_id è sospeso>;
		V(&mutex);
		P(&priv[proc_id]);
	}
}

void rilascio_risorsa(int proc_id)
{
	P(&mutex);
	<rilascio della risorsa da proc_id>;
	if <esiste almeno un processo sospeso per cui vale condizione_verificata_per()>
	{
		int p = <scelta del processo da riattivare>;
		<indicazione che p non è più sospeso>;
		<allocazione della risorsa a p>;
		signal(&priv[p]);
	}
	V(&mutex);
}

Osservazioni

Lo schema prende il nome di "ci penso io" perché anche al processo che rilascia la risorsa e attiva un processo P sospeso spettano compiti che riguardano P, ovvero segnalare che P non è più bloccato e che la risorsa è stata appena allocata a P. Nella primitiva di rilascio, di conseguenza, è possibile sostituire lo "if" con un "while" e rimuovere dalla sospensione più di un processo.

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 rendez vous.

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.

Bibliografia

• Andrea de Prisco, Concorrenza, semafori, monitor (JPG), in MCmicrocomputer, n. 52, Roma, Technimedia, maggio 1986, pp. 117-120, ISSN 1123-2714. Trascrizione del testo, su digiTANTO.it.

Voci correlate

• Problema delle montagne russe (Roller coaster problem)

Collegamenti esterni

• (EN) computer semaphore, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) semaphore, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL