Esercizio - Sincronizzazione in Go con canali, mutex e variabili condizione (problemi classici)
In questa pagina 4
Testo (esercizio di programmazione concorrente in Go, nello spirito delle prove del corso di Sistemi Operativi, Ing. Informatica UniPD, che richiedono programmi in C e/o Go). Riscrivere in Go tre problemi svolti con i semafori:
- il barbiere che dorme (Esercizio - Il barbiere che dorme con i semafori (eserciziario, esercizio 68));
- il conto bancario con prelievi che aspettano (Esercizio - Monitor per conto bancario, cannibali e fabbrica (eserciziario, esercizi 16, 17 e 103));
- il rendez-vous di Giulio e Giovanni (Esercizio - Grafi di precedenza e ordine di stampa con i semafori (eserciziario, esercizi 19, 52, 60, 91 e 114)).
Teoria: Thread e concorrenza - modelli, Pthreads e goroutineUn thread è un flusso di esecuzione dentro un processo: ha program counter, registri e stack propri ma condivide codice, dati, heap e file aperti del processo, quindi costa meno di un processo (creazione e commutazione) e comunica più facilmente, ma i dati condivisi producono race condition; concorrenza (più compiti che avanzano, anche su un solo core) non è parallelismo (più compiti eseguiti nello stesso istante, serve più di un core); si distinguono parallelismo sui dati e sui compiti e la legge di Amdahl dà lo speedup massimo 1/(S+(1-S)/N) con S frazione seriale; i thread utente sono gestiti da una libreria, quelli kernel dal sistema, e i modelli many-to-one, one-to-one (Linux, Windows) e many-to-many li collegano; in C si usa Pthreads (pthread_create, pthread_join, pthread_exit), in Go le goroutine (parola chiave go, sync.WaitGroup, canali); questioni aperte: fork/exec con i thread, segnali, cancellazione (asincrona o differita), thread-local storage, contention scope (PCS e SCS).Thread e concorrenza - modelli, Pthreads e goroutine → (goroutine, WaitGroup, canali) e Semafori, monitor e problemi classici di sincronizzazioneUn semaforo è un intero accessibile solo con due operazioni atomiche, wait (P: aspetta finché S > 0 e decrementa) e signal (V, in POSIX sem_post: incrementa); il semaforo contatore ha valori illimitati, quello binario vale 0 o 1; con valore iniziale 1 realizza la mutua esclusione, con valore iniziale 0 impone un ordine di esecuzione (S1 prima di S2); senza attesa attiva ogni semaforo ha una coda di processi sospesi (sleep e wakeup); i semafori si usano male con facilità (ordine sbagliato, omissioni); il monitor è un tipo di dato astratto in cui un solo processo alla volta è attivo e le variabili condizione x.wait()/x.signal() sospendono e risvegliano (in POSIX mutex più pthread_cond_t); le anomalie di liveness sono deadlock, starvation e inversione di priorità; i problemi classici sono produttore-consumatore a buffer limitato (mutex, vuote = n, piene = 0; l'ordine delle wait è importante), lettori-scrittori (rw_mutex, mutex, read_count; i lettori possono far morire di fame gli scrittori) e filosofi a cena (la soluzione ingenua con un semaforo per bacchetta va in deadlock; si evita limitando a n-1 filosofi, rompendo la simmetria o ordinando le risorse), con soluzioni in C (POSIX) e in Go (canali e sync).Semafori, monitor e problemi classici di sincronizzazione →. In Go le primitive sono: goroutine (go f()), canali (chan T, con o senza buffer), sync.Mutex, sync.WaitGroup, sync.Cond e il costrutto select.
Traduzione dai semafori ai canali.
| semaforo | canale |
|---|---|
| semaforo contatore di valore iniziale | make(chan struct{}, n) pieno di gettoni, oppure un canale vuoto con capacità in cui si invia per wait e si riceve per signal |
wait(s) |
<-s oppure invio s <- struct{}{} (secondo la convenzione) |
signal(s) |
l'operazione opposta |
| buffer limitato di capacità | make(chan T, n): l'invio blocca se è pieno, la ricezione se è vuoto |
x.wait() / x.signal() di un monitor |
sync.Cond (Wait, Signal, Broadcast) |
| "provare e andarsene se pieno" | select con default |
I programmi sono stati compilati e controllati con go vet (go 1.27, target Linux) e non sono stati eseguiti qui.
1. Barbiere in Go
Le sedie d'attesa sono un canale con buffer di capacità sedie: un cliente che arriva tenta di inviare il proprio id; se il buffer è pieno (select con default) se ne va. Il barbiere riceve dal canale: se è vuoto si blocca (dorme), altrimenti taglia i capelli. Si chiude il canale quando sono arrivati tutti i clienti: il barbiere esce dal range.
package main
import (
"fmt"
"sync"
"time"
)
const (
sedie = 3
clienti = 8
)
func main() {
attesa := make(chan int, sedie) // sedie per i clienti in attesa
var wg sync.WaitGroup
var mu sync.Mutex // protegge i contatori
serviti, persi := 0, 0
finito := make(chan struct{})
go func() { // barbiere
for c := range attesa { // dorme se il canale e' vuoto
time.Sleep(2 * time.Millisecond) // cut_hair()
mu.Lock()
serviti++
mu.Unlock()
fmt.Println("servito il cliente", c)
}
close(finito)
}()
for i := 0; i < clienti; i++ {
wg.Add(1)
go func(id int) {
defer wg.Done()
time.Sleep(time.Duration(id) * 500 * time.Microsecond) // arrivi scaglionati
select {
case attesa <- id: // c'e' una sedia libera: si siede
default: // sedie piene: se ne va
mu.Lock()
persi++
mu.Unlock()
fmt.Println("il cliente", id, "se ne va")
}
}(i)
}
wg.Wait()
close(attesa) // nessun altro cliente: il barbiere finira' i rimasti e uscira'
<-finito
fmt.Println("serviti", serviti, "persi", persi, "totale", serviti+persi)
}Confronto con la versione a semafori: il canale riunisce in un solo oggetto i semafori customers (clienti in attesa), il contatore waiting, il limite di sedie (la capacità) e la mutua esclusione. Il totale serviti + persi è sempre 8.
2. Conto bancario con sync.Cond
Il monitor è un sync.Mutex più una sync.Cond costruita su quel mutex. Wait rilascia il mutex mentre il thread dorme e lo riprende al risveglio; la condizione si controlla sempre in un for:
package main
import (
"fmt"
"sync"
)
type Conto struct {
mu sync.Mutex
sosp *sync.Cond
saldo int
}
func NuovoConto() *Conto {
c := &Conto{}
c.sosp = sync.NewCond(&c.mu)
return c
}
func (c *Conto) Prelievo(cifra int) {
c.mu.Lock()
defer c.mu.Unlock()
for c.saldo < cifra { // il saldo non deve diventare negativo
c.sosp.Wait()
}
c.saldo -= cifra
}
func (c *Conto) Deposito(cifra int) {
c.mu.Lock()
defer c.mu.Unlock()
c.saldo += cifra
c.sosp.Broadcast() // avverte tutti i prelievi in attesa
}
func main() {
conto := NuovoConto()
var wg sync.WaitGroup
for i := 0; i < 2; i++ {
wg.Add(2)
go func() {
defer wg.Done()
for k := 0; k < 5; k++ {
conto.Prelievo(10)
}
}()
go func() {
defer wg.Done()
for k := 0; k < 10; k++ {
conto.Deposito(5)
}
}()
}
wg.Wait()
fmt.Println("saldo finale =", conto.saldo, "(atteso 0)")
}Sono 100 prelevati e 100 depositati: tutti i prelievi terminano e il saldo finale è 0.
3. Rendez-vous in Go
Con canali senza buffer il rendez-vous è naturale: first <- x blocca finché qualcuno riceve. Giovanni invia su first quando il cocktail è pronto (e aspetta che Giulio riceva, cioè che anche il panino sia pronto); Giulio, ricevuto, invia su second per liberare Giovanni:
package main
import (
"fmt"
"sync"
)
const clientiAlGiorno = 3
func main() {
first := make(chan struct{}) // Giovanni -> Giulio: cocktail pronto
second := make(chan struct{}) // Giulio -> Giovanni: panino pronto
var wg sync.WaitGroup
wg.Add(2)
go func() { // Giulio
defer wg.Done()
for i := 1; i <= clientiAlGiorno; i++ {
fmt.Println("Giulio prepara il panino", i)
<-first // aspetta che il cocktail sia pronto
second <- struct{}{}
fmt.Println("Giulio consegna il panino", i)
}
}()
go func() { // Giovanni
defer wg.Done()
for i := 1; i <= clientiAlGiorno; i++ {
fmt.Println("Giovanni prepara il cocktail", i)
first <- struct{}{} // cocktail pronto
<-second // aspetta che il panino sia pronto
fmt.Println("Giovanni consegna il cocktail", i)
}
}()
wg.Wait()
}Ogni "giro" viene consegnato solo dopo che entrambe le preparazioni sono finite, e nessuno può cominciare il giro successivo prima dell'altro (ognuno aspetta all'incontro successivo).
Domande d'esame
Come si realizza in Go un semaforo contatore di valore ?
Traccia. Con un canale con buffer di capacità : wait = invio (blocca quando i gettoni sono finiti), signal = ricezione. È la tecnica usata nei filosofi a cena con posti.
Versione ripasso
- Primitive Go:
go f(),chan T(con/senza buffer),sync.Mutex,sync.WaitGroup,sync.Cond(Wait,Signal,Broadcast),select(condefault). Teoria: Thread e concorrenza - modelli, Pthreads e goroutineUn thread è un flusso di esecuzione dentro un processo: ha program counter, registri e stack propri ma condivide codice, dati, heap e file aperti del processo, quindi costa meno di un processo (creazione e commutazione) e comunica più facilmente, ma i dati condivisi producono race condition; concorrenza (più compiti che avanzano, anche su un solo core) non è parallelismo (più compiti eseguiti nello stesso istante, serve più di un core); si distinguono parallelismo sui dati e sui compiti e la legge di Amdahl dà lo speedup massimo 1/(S+(1-S)/N) con S frazione seriale; i thread utente sono gestiti da una libreria, quelli kernel dal sistema, e i modelli many-to-one, one-to-one (Linux, Windows) e many-to-many li collegano; in C si usa Pthreads (pthread_create, pthread_join, pthread_exit), in Go le goroutine (parola chiave go, sync.WaitGroup, canali); questioni aperte: fork/exec con i thread, segnali, cancellazione (asincrona o differita), thread-local storage, contention scope (PCS e SCS).Thread e concorrenza - modelli, Pthreads e goroutine →, Semafori, monitor e problemi classici di sincronizzazioneUn semaforo è un intero accessibile solo con due operazioni atomiche, wait (P: aspetta finché S > 0 e decrementa) e signal (V, in POSIX sem_post: incrementa); il semaforo contatore ha valori illimitati, quello binario vale 0 o 1; con valore iniziale 1 realizza la mutua esclusione, con valore iniziale 0 impone un ordine di esecuzione (S1 prima di S2); senza attesa attiva ogni semaforo ha una coda di processi sospesi (sleep e wakeup); i semafori si usano male con facilità (ordine sbagliato, omissioni); il monitor è un tipo di dato astratto in cui un solo processo alla volta è attivo e le variabili condizione x.wait()/x.signal() sospendono e risvegliano (in POSIX mutex più pthread_cond_t); le anomalie di liveness sono deadlock, starvation e inversione di priorità; i problemi classici sono produttore-consumatore a buffer limitato (mutex, vuote = n, piene = 0; l'ordine delle wait è importante), lettori-scrittori (rw_mutex, mutex, read_count; i lettori possono far morire di fame gli scrittori) e filosofi a cena (la soluzione ingenua con un semaforo per bacchetta va in deadlock; si evita limitando a n-1 filosofi, rompendo la simmetria o ordinando le risorse), con soluzioni in C (POSIX) e in Go (canali e sync).Semafori, monitor e problemi classici di sincronizzazione →. - Semaforo contatore = canale con buffer di capacità (invio =
wait, ricezione =signal); buffer limitato = canale con capacità; rendez-vous = canale senza buffer; "se pieno me ne vado" =selectcondefault. - Barbiere: sedie =
make(chan int, sedie); cliente:select { case attesa <- id: default: se ne va }; barbiere:for c := range attesa(dorme a canale vuoto);close(attesa)a fine arrivi. - Conto:
sync.Mutex+sync.NewCond(&mu);Prelievo:for saldo < cifra { Wait() };Deposito:saldo += cifra; Broadcast(). - Rendez-vous: Giovanni
first <- {}poi<-second; Giulio<-firstpoisecond <- {}(canali senza buffer). - Traduzione semafori Go: semaforo contatore di valore = canale con buffer (invio =
wait, ricezione =signal, o viceversa con i gettoni); mutex =sync.Mutex; barriera/rendez-vous = canali senza buffer; monitor =sync.Mutex+sync.NewCond(&mu). - Barbiere, controllo:
serviti + persi= numero di clienti; i clienti usano unWaitGroup; la chiusura del canaleattesaavviene dopowg.Wait(); il barbiere segnala la fine con il canalefinito. - Compilazione:
go vetego buildper Linux senza avvisi; non eseguiti qui. - Errori tipici:
ifinvece diforconWait; dimenticarewg.Wait()(ilmaintermina); chiudere un canale due volte o inviare su un canale chiuso.