Semafori e problemi classici

1. Che cos'è un semaforo

Gli algoritmi del capitolo 4 usano solo istruzioni macchina e sono troppo di basso livello per programmare in modo affidabile. Servono meccanismi offerti direttamente dalla macchina concorrente: semafori e monitor. Il semaforo (Dijkstra, 1968) è una struttura semplicissima con cui si risolve quasi ogni problema di mutua esclusione e di sincronizzazione a memoria condivisa. Come il semaforo stradale, col verde si passa e col rosso ci si ferma.

Un semaforo S ha due campi: S.V, un intero ≥ 0, e S.L, l'insieme dei processi bloccati su S. Si crea come S = (k, {}), con k ≥ 0. Le sole operazioni sono wait(S) e signal(S) (P e V per Dijkstra), entrambe atomiche. Qui p è il processo che esegue l'operazione:

wait(S)   = < if S.V > 0
                S.V := S.V - 1          -- verde: passo
              else
                S.L := S.L + {p}        -- rosso: p si blocca su S
                p.state := blocked >

signal(S) = < if S.L = {}
                S.V := S.V + 1          -- nessuno aspetta: il semaforo lo ricorda
              else
                q := un elemento qualsiasi di S.L
                S.L := S.L - {q}
                q.state := ready >      -- sveglio q, S.V non cambia

Se qualcuno aspetta, signal non incrementa: passa il permesso direttamente al processo svegliato, e S.V resta 0. Se nessuno aspetta, incrementa, cioè il semaforo ricorda la segnalazione e una wait successiva passa senza bloccarsi. È la differenza principale rispetto alle variabili condizione dei monitor, dove un segnale senza nessuno in attesa va perso (capitolo 7).

Con k valore iniziale e #wait(S) che conta solo le wait completate (un processo bloccato non ha completato la sua), vale l'invariante del semaforo. Si dimostra per induzione sulle due operazioni ed è la base delle prove di correttezza del capitolo:

S.V ≥ 0
S.V = k + #signal(S) − #wait(S)

Un semaforo non ha proprietario: chiunque può fare signal. E non è rientrante: un processo che ripete wait su un semaforo binario già preso da lui si blocca, a differenza dei lock di Java (capitolo 10).

2. Tre usi, una sola struttura

Ogni uso di un semaforo rientra in uno di tre casi, che differiscono per il valore iniziale e il significato di S.V:

I primi due servono alla competizione, il terzo alla cooperazione (capitolo 2). Un lock invece fa solo mutua esclusione: un semaforo binario fa da lock, mentre per ottenere un semaforo da un lock serve anche una variabile condizione (capitolo 7). Il semaforo generale è lo schema del ticket: per limitare a N i processi che fanno qualcosa insieme, wait prende un ticket e signal lo restituisce. Una soluzione dei filosofi a cena è proprio questa (capitolo 6).

3. Chi viene svegliato? Semafori forti, deboli e busy-wait

Le diverse definizioni del tipo semaforo differiscono solo per la liveness: la safety deriva dall'invariante, che vale per tutte.

• Debole (weak): S.L è un insieme e signal sveglia un processo qualsiasi. È la definizione di base.
• Forte (strong): S.L è una coda, signal sveglia il primo. La starvation è impossibile per qualsiasi numero di processi.
• Busy-wait: non c'è S.L, chi trova il semaforo a 0 continua a ritestarlo.

wait(S)   = < await S.V > 0
              S.V := S.V - 1 >          -- atomica: nessun interleaving tra le due righe
signal(S) = < S.V := S.V + 1 >

Il semaforo busy-wait perde l'assenza di starvation anche con due soli processi: quando il valore torna positivo nessuno decide chi passa. In compenso non coinvolge il sistema operativo. Ha senso su un multiprocessore, quando chi aspetta ha un processore tutto suo e non toglie CPU ad altri calcoli, e con poca contesa, quando le attese sono brevi: girare per pochi istanti costa meno che sospendere il thread e cambiare contesto. Si usa negli algoritmi paralleli.

La await del capitolo 4 è appunto un'attesa attiva, la stessa che il semaforo busy-wait fa dentro la wait. Un semaforo normale invece sospende il processo: nel diagramma di stato un processo bloccato non ha transizioni finché qualcuno non fa signal, e non consuma CPU.

In Java, new Semaphore(n) non garantisce l'ordine di risveglio (debole), mentre new Semaphore(n, true) è fair e concede i permessi in ordine FIFO (forte), a un costo di prestazioni.

4. La sezione critica con un semaforo

Con un semaforo usato come lock il problema del capitolo 4 diventa banale, con lo stesso codice per qualsiasi numero di processi:

binary semaphore S := (1, {})

loop forever
  p1: NCS
  p2: wait(S)         -- prendo il lock
  p3: CS
  p4: signal(S)       -- lo restituisco

Per due processi la correttezza si verifica sul diagramma di stato ridotto: tolte NCS e CS, p1 è la wait e p2 la signal. Il semaforo fa parte dello stato, e un processo bloccato è marcato con B.

Nessuno stato ha entrambi i processi in p2, quindi vale la mutua esclusione, □ ¬(p2 ∧ q2). Da ogni stato parte una transizione, quindi non c'è deadlock. E non c'è starvation: se q è bloccato, la signal di p deve svegliarlo, perché è l'unico in S.L. I blocchi, tra l'altro, tagliano rami del diagramma: meno scenari, ragionamento più facile.

Con N processi mutua esclusione e assenza di deadlock restano, ma con un semaforo debole si perde l'assenza di starvation. Mentre r è in CS, p e q aspettano. La signal di r sveglia q, e r torna subito in attesa accanto a p. La signal di q può svegliare r, quella di r di nuovo q, e così via: p non viene mai scelto.

5. Ordinare le azioni: il semaforo evento

Sincronizzare vuol dire imporre un ordine tra azioni di processi diversi. Il caso più semplice è l'esercizio che Ricci propone all'orale: p esegue le azioni atomiche a1, a2, q esegue b1, b2, b3, e b2 deve essere sempre eseguita dopo a1. Si ragiona così:

1. l'evento da aspettare è «a1 eseguita»;
2. si crea un semaforo evento con quel nome, a1Done, inizializzato a 0 perché l'evento non è ancora accaduto (nomi come S1 non aiutano);
3. chi aspetta, q, fa wait(a1Done) subito prima dell'azione vincolata;
4. chi fa accadere l'evento, p, fa signal(a1Done) subito dopo l'azione.

semaphore a1Done := (0, {})

p                         q
a1                        b1
signal(a1Done)            wait(a1Done)
a2                        b2
                          b3

Funziona in entrambi gli ordini. Se p segnala per primo, a1Done vale 1 e la wait di q passa senza bloccarsi. Se q arriva prima alla wait, si blocca finché p non segnala. A differenza del lock, chi aspetta non segnala mai l'evento che aspetta: se sembra necessario, gli eventi sono due. In Java:

Semaphore a1Done = new Semaphore(0);

Thread p = Thread.ofPlatform().start(() -> {
    a1();
    a1Done.release();              // signal
    a2();
});
Thread q = Thread.ofPlatform().start(() -> {
    b1();
    a1Done.acquireUninterruptibly(); // wait
    b2();
    b3();
});

La rete di Petri dell'esercizio

Si disegnano prima i due processi, ciascuno come una catena di posti e transizioni con un token che rappresenta il flusso di controllo. Poi si aggiunge la «colla»: il semaforo evento diventa un posto a1Done inizialmente vuoto. La transizione a1 produce due token, uno per il flusso di p e uno in a1Done. La transizione b2 ha due posti in ingresso, quindi scatta solo quando q è arrivato lì e a1Done contiene un token. Il lock della sezione critica sarebbe invece un posto con un token iniziale. Il formalismo è nel capitolo 9.

Varianti

Vincolo nei due sensi. Se in più a2 deve seguire b1, servono due eventi. Ognuno prima segnala il proprio e poi aspetta quello dell'altro: è un rendez-vous. Se entrambi aspettano prima di segnalare, ciascuno attende un evento che l'altro produrrà solo dopo: deadlock in ogni esecuzione.

p                         q
a1                        b1
signal(a1Done)            signal(b1Done)
wait(b1Done)              wait(a1Done)
a2                        b2
                          b3

Più processi aspettano lo stesso evento. Se anche r deve aspettare b2, serve una signal per ogni processo in attesa: con una sola, la wait dell'uno «consuma» l'evento e l'altro resta bloccato per sempre. Due signal sullo stesso semaforo bastano se ciascuno aspetta una volta sola. Se i processi sono cicli, invece, uno veloce può consumare entrambe le segnalazioni dello stesso giro e passare al giro successivo prima che l'evento sia riaccaduto. È un bug difficilissimo da vedere, e si evita con un semaforo per ciascun processo in attesa. Morale: non cercare subito il numero minimo di semafori, perché le ottimizzazioni premature introducono proprio questi errori.

Più eventi, un processo in attesa. È il merge sort delle slide: il processo che fonde le due metà ordinate aspetta un evento per ciascuna, invece di una join sui due processi di ordinamento.

semaphore firstHalfSorted := (0, {}), secondHalfSorted := (0, {})

sort1                        sort2                         merge
p1: sort 1st half of A       q1: sort 2nd half of A        r1: wait(firstHalfSorted)
p2: signal(firstHalfSorted)  q2: signal(secondHalfSorted)  r2: wait(secondHalfSorted)
                                                           r3: merge halves of A

Laboratorio: verifica gli esercizi

Ogni riga è un passo atomico e i semafori sono deboli. Quando una signal trova più processi bloccati, scegli tu chi svegliare. Verifica tutti gli interleaving esplora ogni esecuzione e ogni scelta delle signal e cerca una violazione dell'ordine richiesto, oppure uno stato in cui qualcuno resta bloccato per sempre. Gli scenari seguono questa sezione e la prossima; i processi ciclici sono svolti per due giri.

6. Produttori e consumatori

Il produttore-consumatore è un problema d'ordine di esecuzione, ed è difficile trovare un sistema reale che non ne contenga uno. Un produttore crea un dato con produce e lo invia; un consumatore, ricevuto il dato, esegue consume.

La comunicazione sincrona avviene solo quando produttore e consumatore sono pronti entrambi: chi arriva prima aspetta l'altro. In quella asincrona il canale ha una capacità propria, un buffer: una struttura dati condivisa e mutabile in cui i produttori scrivono e da cui i consumatori leggono. Il buffer disaccoppia i due lati nel tempo, permette un insieme dinamico di partecipanti e assorbe le differenze di velocità. È lo scolapiatti tra chi lava e chi asciuga: senza, chi lava aspetta con il piatto in mano.

Buffer illimitato

Con un buffer infinito c'è un solo vincolo: il consumatore non deve prelevare da un buffer vuoto (append e take si assumono atomiche).

UnboundedQueue<Item> buffer := empty queue
semaphore availItems := (0, {})

producer                          consumer
loop forever                      loop forever
p1: Item el := produce            q1: wait(availItems)
p2: append(buffer, el)            q2: Item el := take(buffer)
p3: signal(availItems)            q3: consume(el)

availItems è un semaforo risorsa che conta gli elementi disponibili: availItems.V = #buffer, ma solo considerando atomiche le coppie p2+p3 e q1+q2. Il produttore non si blocca mai.

Buffer limitato e semafori divisi

Un buffer infinito non esiste: se il produttore è più veloce, la memoria cresce senza limite. Con N posti il produttore non deve inserire in un buffer pieno. La risorsa che gli serve è un posto libero, contato da availPlaces, inizializzato a N. Ciascun processo aspetta sul proprio semaforo e segnala su quello dell'altro.

BoundedQueue<Item> buffer := empty queue
semaphore availItems  := (0, {})
semaphore availPlaces := (N, {})

producer                          consumer
loop forever                      loop forever
p1: Item el := produce            q1: wait(availItems)
p2: wait(availPlaces)             q2: Item el := take(buffer)
p3: append(buffer, el)            q3: signal(availPlaces)
p4: signal(availItems)            q4: consume(el)

availItems e availPlaces sono semafori divisi (split semaphores): la loro somma è costante, availItems + availPlaces = N. L'uguaglianza vale considerando atomica ogni sequenza wait–operazione–signal; in un istante qualsiasi la somma è ≤ N. produce e consume restano fuori da ogni sincronizzazione, così i due lati lavorano davvero in parallelo.

Più produttori e più consumatori

In generale il buffer non è thread-safe e più produttori possono fare append insieme. Le operazioni sul buffer diventano sezioni critiche, protette da un terzo semaforo, un mutex:

semaphore availItems := (0, {}), availPlaces := (N, {})
binary semaphore mutex := (1, {})

producer                          consumer
loop forever                      loop forever
p1: Item el := produce            q1: wait(availItems)
p2: wait(availPlaces)             q2: wait(mutex)
p3: wait(mutex)                   q3: Item el := take(buffer)
p4: append(buffer, el)            q4: signal(mutex)
p5: signal(mutex)                 q5: signal(availPlaces)
p6: signal(availItems)            q6: consume(el)

L'ordine delle due wait è essenziale: prima la sincronizzazione, poi il mutex. Se il produttore prende mutex e poi si blocca su availPlaces a buffer pieno, tiene il lock mentre aspetta. Il consumatore che dovrebbe liberare un posto si blocca su mutex: deadlock (ultimo scenario del laboratorio). L'ordine delle signal non conta, perché signal non blocca mai.

In pratica non si riscrive tutto questo: in Java una ArrayBlockingQueue(N) è esattamente un buffer limitato con put e take bloccanti (capitolo 10). Nel capitolo 7 lo stesso buffer diventa un monitor.

7. Lettori e scrittori

Il problema dei lettori e scrittori (Courtois, Heymans e Parnas, 1971) è una sezione critica con due classi di processi: i lettori escludono gli scrittori ma non gli altri lettori, gli scrittori escludono tutti. È l'astrazione dell'accesso a un database: leggere insieme non crea problemi, modificare richiede la mutua esclusione. Con nR lettori e nW scrittori attivi, ogni soluzione deve mantenere:

nR ≥ 0
nW = 0 ∨ nW = 1
(nR > 0 → nW = 0) ∧ (nW = 1 → nR = 0)

Un solo semaforo rw usato come lock da tutti rispetta gli invarianti, ma è sovravincolato: serializza anche i lettori e butta via il parallelismo che si voleva. La soluzione delle slide fa cooperare i lettori tramite un contatore:

binary semaphore mutexR := (1, {})   -- protegge nr
int nr := 0                          -- lettori dentro
binary semaphore rw := (1, {})       -- esclude lettori e scrittori

reader                                        writer
loop forever                                  loop forever
p1:  wait(mutexR)                             q1: wait(rw)
p2:  if nr = 0                                q2: Item el := create_record
p3:    wait(rw)      -- il primo chiude       q3: write(dbase, el)
p4:  nr := nr + 1                             q4: signal(rw)
p5:  signal(mutexR)
p6:  Item el := read(dbase)   -- in parallelo
p7:  wait(mutexR)
p8:  nr := nr - 1
p9:  if nr = 0
p10:   signal(rw)    -- l'ultimo riapre
p11: signal(mutexR)

mutexR rende atomico il check-and-act su nr ed è tenuto per pochissimo. Il primo lettore trova nr = 0 e prende rw: se dentro c'è uno scrittore si blocca, e gli altri lettori aspettano dietro di lui su mutexR. I lettori successivi trovano nr > 0 e non toccano rw. La lettura, p6, avviene senza tenere alcun semaforo, quindi in parallelo. L'ultimo lettore che esce rilascia rw. Per gli scrittori rw è un lock normale.

La soluzione dà priorità ai lettori: se i lettori si danno il cambio, nr non torna mai a 0 e gli scrittori soffrono di starvation. Rendere rw forte non basta, perché su rw compete solo il primo lettore. Serve una politica più fine, per esempio che un nuovo lettore aspetti se c'è uno scrittore in attesa, ed è più facile scriverla con un monitor (capitolo 7).

Questi esempi mostrano il limite dei semafori: sono potenti ma di basso livello. La politica di sincronizzazione è sparsa nel codice dei processi, una signal dimenticata blocca tutto, una wait nel posto sbagliato crea un deadlock, e la strategia va ricostruita riga per riga. Da qui i monitor di Brinch Hansen (1973) e Hoare (1974), che raccolgono dati, operazioni e politica in un unico componente (capitolo 7).

Verifica le tue conoscenze