Il meccanismo semaforico

IL MECCANISMO SEMAFORICO

Soffermiamoci ora sul modello di programmazione a memoria globale. Un meccanismo elementare messo a disposizione dal SO per risolvere conflitti nell'attribuzione delle risorse è quello dei SEMAFORI. Un semaforo è, come ogni risorsa, una struttura dati corredata di due procedure che consentono di utilizzarla.

Il primo modello di semaforo fu ideato da Dijkstra ed era un semaforo booleano: in pratica, una variabile booleana condivisa fra tutti i processi. Il semaforo generalizzato è invece costituito da una variabile intera che può assumere valori in un certo range.

Indicando con s un semaforo, su s è possibile effettuare le seguenti due operazioni:

WAIT(s)  REPEAT UNTIL s > 0 ;

s : = s - 1

SIGNAL(s) : s : = s + 1

Wait ritarda il processo finché s diviene maggiore di 0 ("semaforo verde"), e quindi lo decrementa di 1. Signal incrementa il semaforo di 1. Si tratta di operazioni atomiche, cioè non interrompibili, che sono parte del nucleo del SO. Le definizioni appena date hanno un senso generale e nella realtà vengono implementate in modo diverso e diversamente a seconda del contesto. Ad esempio, la wait, che viene invocata dai processi per tentare di aggiudicarsi l'attribuzione di una risorsa, nella versione generale comporterebbe una ripetizione continua dell'esame del valore del semaforo. Questo costituisce un'evidente spreco di tempo e perciò viene evitato. La signal ha l'effetto, quando invocata da un processo, di liberare una risorsa e quindi di renderla disponibile per altri processi, inclusi quelli che in precedenza erano stati sospesi in fase di wait proprio perché quella risorsa era occupata ('risveglio' di un processo).

In un semaforo binario può 'passare' un solo processo per volta. In uno intero, con s I (0, 1, , N), ne possono passare fino a N.

Vediamo adesso come si realizzano i semafori nei sistemi multiprocessore e monoprocessore.

SISTEMI MULTIPROCESSORE (una sola memoria e più processori). Supponiamo che un processo A giri sul processore P₁ e simultaneamente un secondo processo B giri sul processore P₂. Il SO mette a disposizione un semaforo binario. Ad un certo punto, per aggiudicarsi l'attribuzione di una risorsa, A effettua una WAIT(s).

s

MEMORIA

A P₁ B P₂ P₃ . . . . .

Già ora si comprende l'importanza che sia garantita l'atomicità di tale primitiva.. Infatti la WAIT(s) comporta che si prelevi s dalla memoria e si testi il suo valore. Supponiamo sia s = 1. Può darsi che subito dopo anche B effettui una WAIT. Può accadere allora che B legga il valore s = 1 prima ancora che A abbia il tempo di effettuare il decremento s : = s - 1, e quindi entrambi i processi passerebbero, cosa non possibile, avendo supposto binario il semaforo. Quindi occorre un meccanismo che blocchi l'accesso al BUS da parte di qualunque altro processo mentre A sta leggendo s.

Allo scopo è spesso usata l'istruzione TEST AND SET, che legge s e nello stesso ciclo di bus lo pone in ogni caso a 0. Se s valeva 1, si ottiene il cambiamento di stato del semaforo. Se era s = 0, non cambia nulla.

Dunque, la WAIT(s) si può realizzare mediante un loop sull'istruzione TEST AND SET, che dura fintantoché s = 0 (e quindi si interrompe non appena s = 1). Il loop si effettua mediante un istruzione di salto, tipo JUMP. Fra TEST & SET e JUMP devono esserci delle NOP (no operation), poiché bisogna dare il tempo agli altri processi di porre, eventualmente, s = 1[1].

SISTEMI MONOPROCESSORE. A causa della non-interrompibilità, su di un sistema a monoprocessore questa istruzione non può essere realizzata direttamente come a pag. 32. Invocando infatti WAIT(s) con s = 0, il sistema si 'impallerebbe' perché, dato che un simile sistema può far girare un solo processo per volta, verrebbe meno ogni possibilità di rendere la s positiva, uscendo dal REPEAT. Se si ha a disposizione un sistema multiprocesso si può usare il meccanismo dei processori virtuali e far sì che la WAIT operi un'attesa non sul processore reale, ma su un processore virtuale. In tal modo, l'attesa generata dal REPEAT.. UNTIL potrà terminare, poiché sarà sufficiente che un altro processo in esecuzione incrementi s tramite l'operazione SIGNAL(s).

Più in generale, le due primitive vengono realizzate come segue.

WAIT(s) : begin

if s = 0 then

< il processo viene sospeso e il suo descrittore inserito nella coda Q_s >

else s : = s - 1

end

Il ricorso all'istruzione WAIT genera un'interruzione. D'altra parte, la end della WAIT corrisponde sempre all'istruzione RTE (return ecception - ritorno da interruzione).

In breve, l'operazione WAIT viene usata per verificare lo stato di un semaforo. Se è positivo, questo viene decrementato di un'unità e il processo prosegue l'esecuzione. Se è nullo, il processo viene sospeso e l'unità di elaborazione così liberata viene assegnata ad un altro processo.

SIGNAL(s) : begin

if < esiste un processo in coda > then

< il suo descrittore è rimosso da Q_s ed il suo stato diviene READY >

else s : = s + 1

end

La coda Q_s contiene i descrittori dei processi in attesa di ricevere il 'via libera' dal semaforo. Essa è gestita, solitamente, mediante una classica lista dinamica.

In questo caso, il semaforo è un record a due campi: uno di essi è una variabile booleana che rappresenta il semaforo vero e proprio. L'altro campo contiene due puntatori: uno punta alla testa della coda Q_s, ossia al processo in attesa che sarà servito per primo, il secondo punta all'ultimo processo in attesa. Si noti il prospetto seguente, dove figura anche un terzo campo, non indispensabile ma utile, contenente il numero dei processi presenti nella coda.

VALORE DEL SEMAFORO

puntatore puntatore

testa coda

(NUMERO PROCESSI)

descrittore descrittore

processo processo

Ogni transizione dei processi fra gli stati running, ready e wait prevede il trasferimento del descrittore del processo coinvolto fra due diverse code: la Q_s appena menzionata, detta CODA DI ATTESA o anche CODA DEI SEMAFORI, e la CODA DEI PROCESSI READY (pronti).

Il nucleo del SO dispone di un'area stack, ossia gestita come una pila (secondo la disciplina LIFO). [Inoltre, ad ogni processo è associata, all'interno della regione privata di memoria ed esso riservata, una propria area stack, contenente ad esempio le variabili temporanee usate dal processo]. L'invocazione di una primitiva come la WAIT o la SIGNAL da parte di un processo corrisponde ad una supervisor call, il che genera, come si è detto, un'interruzione. Il program counter (PC) e il registro di stato del processo vengono quindi messi in testa allo stack del kernel.

Se in particolare la primitiva richiesta è la WAIT, si provvede innanzitutto all'esame del semaforo.

Se esso è diverso da zero, viene percorso il ramo else il che comporta in tempi brevi il proseguimento del processo in esame. Infatti la WAIT si limita in questo caso a decrementare il semaforo. Subito dopo il kernel rimette in esecuzione il processo (RTE) ripristinando il PC e lo stato del processo temporaneamente interrotto, contenuti nel suo stack.

Più articolato è l'andamento dei fatti nel caso in cui il valore del semaforo sia invece uguale a zero. Viene percorso il ramo then, il che comporta la trasformazione del processo da running a wait ed il ripristino di un diverso processo. In questo caso infatti la primitiva provvede a salvare nel descrittore del processo il PC, lo stato (che si trovano nello stack; ciò è indispensabile, dato che lo stack è un'area temporanea) e il 'contesto' (valori dei registri di macchina). Questo salvataggio è possibile, dal momento che fintantoché un processo è running la posizione del suo descrittore in memoria (puntatore) è conosciuta.

Successivamente, il descrittore viene messo nella coda dei processi di attesa e si dà la parola allo SCHEDULER dei processi. Lo scheduler determina il processo da rendere running, prende il suo stato, il suo PC e il suo contesto - memorizzato nel descrittore - e li pone nello stack, dopodiché fa puntare il puntatore al processo running corrente al suo descrittore. Quindi mediante la RTE quest'ultimo viene messo in esecuzione.

Il processo prescelto è il processo che si trova in testa alla coda dei processi pronti, o comunque quello considerato a maggiore priorità (cfr. nota 7 a pag. 15). Il vantaggio di usare una coda anziché il meccanismo delle priorità sta nel fatto che se viene seguito l'ordine di sospensione dei processi è impossibile che si verifichi un fenomeno di attesa indefinita da parte di un processo (che potrebbe non riuscire mai ad avere la priorità).

Si ricordi che la primitiva WAIT è non interrompibile. Di conseguenza, tutte le operazioni che ne fanno parte vengono eseguite con le interruzioni disabilitate. Un'eccezione a questa regola si applica quando lo scheduler non trova processi ready, giacché la coda è vuota. In tal caso lo scheduler abilita le interruzioni. A questo punto, potrebbe iniziare ad effettuare un proprio ciclo di attesa. Tipicamente, però, si preferisce seguire una diversa strategia: si inserisce fra i processi di sistema un apposito processo 'fittizio' (dummy process) che ha la priorità più bassa, in modo da essere chiamato solo quando non ci sono altri ready, ed è sempre nello stato ready. In generale un processo dummy si limita ad eseguire un ciclo senza fine e rimane in esecuzione fino a quando un qualunque altro processo non diviene ready. Nel nostro caso, l'interruzione del dummy è garantita dal fatto che, come abbiamo precisato, la WAIT termina sempre con una RTE [2].

Un processo sospeso può venire 'risvegliato' come conseguenza dell'esecuzione da parte di un altro processo di una SIGNAL sullo stesso semaforo. Se non vi sono processi in attesa nella coda associata al semaforo, la SIGNAL si limita ad incrementare il valore del semaforo. Se ce ne sono, il descrittore del processo che si trova in testa alla coda dei processi in attesa viene trasferito nella coda dei processi ready. In tutti e due i casi il processo che ha invocato la SIGNAL prosegue la sua esecuzione [3].