|
ATTIVITÀ
:
Programmare
:
Linguaggi
:
Linguaggio C
:
Semafori
Semafori
Lo spunto per aggiungere questa pagina alla sezione dedicata al linguaggio C, deriva dal fatto che i sistemi operativi UNIX (dei quali tanto il Mac OS X quanto Linux fanno parte) vengono scritti in questo linguaggio e
quindi si trovano nella naturale condizione per essere illustrati con esempi scritti in C.
In realtà il Mac OS X è scritto in C++, ma essendo il C++ compatibile con il C, la validità del tutto non ne
risente.
Parimenti devo avvertitvi: in questa pagina si userà uno pseudo codice molto simile al C, ma non del C in senso stretto.
Ora, il problema è il seguente: supponiamo che io sappia cos'è un processo e
supponiamo che io esegua un sistema operativo (d'ora in poi OS) capace di essere multiprogrammato, ovvero di eseguire concorrentemente più processi.
Supponiamo anche che tra i processi che eseguo ce ne siano quattro
(tanto per fare un esempio) che sono in qualche modo in rapporto tra loro.
Diciamo che tre di questi, A, B, C, hanno bisogno dei dati prodotti da D.
Siccome in un sistema multiprogrammato non c'è modo di sapere
quanto dura ed in che ordine avviene l'elaborazione dei quattor processi suddetti, ho un problema.
Il problema è: siccome A, B, e C hanno bisogno di ricevere dati da D, devo garantirmi in qualche modo che A, B e C non
facciano nulla se D non fornisce loro i dati.
Mettiamo a fattor comune e noterete che ho un problema:
Non so in che ordine eseguono, ma è necessario che eseguano in modo che D fornisca dati agli altri.
Questo
tipo di problema nei sistemi operativi viene definito Concorrenza, e viene risolto con una tecnica detta Sincronizzazione.
Indice
- SO multiprogrammati
- Interrompere con educazione
- I semafori
- Un esempio pratico
- Bibliografia & Links
- Copyright e Licenza
SO multiprogrammati
Pensare di comandare il meccanismo di sincronizzazione dall'esterno, ovvero imponendo ai processi un comportamento che garantisca che A, B e C ricevano dati da D e solo da D, e solo in questo caso specifico, è
impossibile. Si rassegnigno coloro che hanno visioni deterministiche del mondo artificiale.
C'è solo un modo per fare sì che tutto quanto sopra funzioni: lasciare che i processi collaborino.
Collaborare, per un
processo, significa dotarlo di una capacità (a livello di SO) di segnalare agli altri la possibilità di essere eseguito al momento giusto.
Ora, sorprenda o meno, l'unico modo di rendere un computer capace di eseguire
più processi concorrentemente (anzi, dare l'illusione che ciò avvenga) è quello di interromperli ed eseguirne altri.
Siccome i computer sono molto veloci nel farlo, la sensazione che se ne ricava è che la macchina stia
portando avanti più compiti contemporaneamente, esegua cioé processi in maniera concorrente.
Ma, rassegnamoci, un processore anche molto forte non può che eseguire una istruzione per volta.
I processi sono fatti di
istruzioni (e dati), e quindi delle due l'una:
1) eseguire tutte le istruzioni di un processo fino alla sua fine naturale
2) eseguire un po' di istruzioni di uno, poi un po' di un altro, poi un po' di un altro
ancora e così via, dando solo l'illusione che i processi avanzino in parallelo.
Il secondo caso è quello dei sistemi multiprogrammati, che interrompono continuamente l'esecuzione di un processo per dedicarsi
all'esecuzione di parte di un altro.
Nulla di male se i processi concorrenti non hanno rapporti reciproci, ovvero se non contano l'uno sull'altro per essere eseguiti.
Ma se contano l'uno sull'altro?!
 Interrompere con educazione
C'è un problema ulteriore, ovvero: riesco a garantirmi a monte che un processo venga interrotto solo al momento giusto?
No, la risposta è no.
Se lascio che il SO e il processore collaborino nell'esecuzione dei
processi, l'unica cosa di cui sono capaci è ottimizzare l'uso del processore, interrompendo un processo quando ritengono che sia giusto farlo, e quindi quando pare a loro.
Voi direte: non sta bene interrompere in
questo modo chi sta lavorando.
E' vero, ma abbiamo scritto i SO per essere dei gran cafoni, dei rudi personaggi che hanno solo la produttività in mente.
Pertanto, non è possibile scrivere il codice di un processo
che attenda dati da un altro e sperare che il SO lo capisca.
Se fosse possibile, torneremmo all'inizio del discorso, ovvero avremmo un metodo che sappia riconoscere la situazione da sé e la gestisca senza essere
specificamente istruito a farlo nel caso specifico.
Ahinoi, non c'è.
L'unico modo, quindi, è quello di scrivere il codice di questi processi in modo da prevedere esplicitamente il fatto che debbano
collaborare.
Naturalmente non è necessario inventare ogni volta, l'ha già fatto per noi Edsger Wybe Dijkstra nel
1965.
Da allora è sufficiente implementare il suo algoritmo nelle primitive dei SO multiprogrammati perché il codice faccia in modo di istruire il SO sul fatto che un certo numero di processi sta collaborando e quindi
crea delle dipendenze tra loro al momento dell'esecuzione.
Questo sistema si chiama semaforo, ma prima dobbiamo garantirci che il processo che lo usa non venga interrotto sul più bello, ovvero mentre usa un
semaforo.
Il modo è semplice.
Si prende una parte di codice e si dice al SO che quella parte di codice non è interrompibile.
Quindi il SO ha due scelte:
1) Interrompere l'elaborazione prima che quel pezzo di
codice sia eseguito
2) Eseguire tutto il pezzo di codice non interrompibile, una volta che l'esecuzione sia iniziata.
Stiamo cioè forzando il SO a non utilizzare la macchina come un sistema multiprogrammato, anche
se solo per un po'.
Un pezzo di codice di una processo che non sia interrompibile si dice (non c'è un motivo, si chiama così e basta) Sezione Critica.
I semafori
Mi dispiace non poterlo dire a Dijkstra, ma il nome semafori per questo meccanismo è semanticamente sbagliato.
Mi dispiace non poterlo conoscere e non averlo conosciuto molto più che non mettergli nelle orecchie il
ronzio del mio pensiero in merito, ma tant'è.
Il semaforo non lo possono gestire gli automobilisti, lo trovano già messo lì e non possono altro che subirlo.
Abbiamo detto che nel caso dei processi concorrenti NON è
così.
Allora com'è?!
E' un meccanismo del tutto simile al semaforo, salvo il fatto che sono i processi stessi (quelli che stanno collaborando) a chiedere al SO di impostarlo per loro ed a loro piacimento.
Ecco
che la semantica del nome semaforo non coglie appieno la potenza dello strumento.
Comunque si chiamano semafori.
Il semaforo di Dijkstra è una primitiva di sistema che funziona in questo modo:
1) il semaforo è un
valore intero inizialmente non negativo (dunque 0 o un numero positivo)
2) un processo cui servano dati generati da un altro processo può solo chiamare una funzione che segnali questa sua necessità agli altri
3) un
processo in grado di fornire dati agli altri può solamente chiamare una funzione che segnali questa sua capacità agli altri
4) il valore del semaforo (che è un intero) determina se il processo corrente (quello che il
processore sta eseguendo) può continuare o meno l'elaborazione.
Fine.
Nello specifico:
un semaforo ha una struttura di memoria di questo tipo:
struct
{
int counter;
queue Blocked;
} Semaforo;
ovvero è una struct di nome Semaforo composta di un intero di nome counter e di una coda di nome Blocked.
Non è negli scopi di questa pagina definire una coda, ma possiamo pensarla come una struct
che contenga almeno un PID (Prcess ID - Identificatire di processo) e un puntatore ad un oggetto analogo, in modo da creare una
catena di elementi.
Se nell'estrarre oggetti da questa catena estraiamo quello che vi è entrato a far parte da più tempo parliamo di coda, altrimenti (se cioè estraiamo per primo quello che ne è entrato a far
parte per ultimo) parliamo di pila.
Possiamo creare un semaforo con una normale dichiarazione.
Abbiamo due funzioni per manipolare un semaforo.
La prima la possiamo chiamare wait() e la chiameranno i
processi che stanno aspettando di poter essere eseguiti, la seconda la possiamo chiamare signal() e la chiameranno i processi che vogliono segnalare che hanno eseguito quento gli altri si aspettavano da loro.
Possiamo
dare una pseudo-definizione di queste due funzioni, supponendo di aver creato (per i nostri processi A, B, C e D) un semaforo di nome s:
void wait (Semaforo s)
{
s.counter--;
if (s.counter < 0)
{
}
}
Quindi con questa funzione un processo che attende un segnale dagli altri, lo fa presente e viene bloccato se il valore di counter (in ultima analisi del semaforo) è negativo.
Notate che sebbene la scelta di invocare
la gestione del semaforo sia lasciata al processo che chiama la funzione wait(), non c'è modo, da perte di quel processo di sapere se questa sua necessità possa essere soddisfatta, perché non conosce e non può conoscere
il valore del semaforo. Certo è che l'aver fatto presente questa sua necessità modifica lo stato del semaforo (ne decrementa il contatore).
Se il contatore, dopo la chiamata, è non negativo (ovvero 0 o positivo), il
processo chiamante verrà messo tra quelli che possono essere eseguiti; per fare questo verrà accodato in una coda di nome Ready.
Si noti che da questo momento in poi, la decisione di eseguire o meno il
processo ricade solamente sul SO, e rientra nel normale modo di gestire i processi concorrenti.
Se un processo ha prodotto dati per gli altri, ovviamente chiama una funzione che lo segnala, per mezzo del solito
semaforo:
void signal (Semaforo s)
{
s.counter++;
if (s.counter <= 0)
{
}
}
In entrambi i casi se la if fallisce, il processo chiamante viene riaccodato alla coda Ready.
Tutto qui.
E la Sezione Critica?
La Sezione Critica sarà quella in cui il processo chiama la funzione di
gestione del semaforo, per essere certi che non possa essere interrotto mentre lo fa.
Un esempio pratico
Facciamo un esempio pratico, e consideriamo i nostri quattro processi A, B, C e D.
Nel nostro esempio, A, B e C contano sul processo D che produce dei dati, per poterli elaborare.
Contano anche sul semaforo
s che ovviamente conoscono tutti e solo loro per potersi sincronizzare.
Rappresentiamo graficamente una parte della situazione (non tutta, i processori sono molto veloci, possono fare centinaia di
migliaia di cicli al secondo, noi ne considereremo solo otto... :).
Nella rappresentazione, che è in lingua inglese solo perché è stata utilizzata dal sottoscritto in un contesto in cui la lingua era quella, il tutto
dovrebbe essere piuttosto autoesplicativo comunque.
Va solo chiarito che ad ogni passo (indicato con il cerchietto ed il numero sulla sinistra) si è rappresentato tanto lo stato effettivo dell'elaborazione (con
righe continue) quanto gli effetti sulle variabili che avrebbe avuto la chiamata opposta a quella reale (quindi la wait() invece della signal() e viceversa).
Questo percorso
alternativo è rappresentato con righe tratteggiate e con colori più tenui.
In figura sono indicati lo stato iniziale del processore (che sta eseguendo il processo A), della coda Ready (che
contiene gli altri tre B, D e C) e del semaforo s che è stato inizializzato ad 1 per quanto riguarda il contatore ed ha la coda Blocked vuota.
Bibliografia & Links
|
