Salta al contenuto
Note per Studenti Esercizio - Sincronizzazione in Go con canali, mutex e variabili condizione (problemi classici)

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:

  1. il barbiere che dorme (Esercizio - Il barbiere che dorme con i semafori (eserciziario, esercizio 68));
  2. il conto bancario con prelievi che aspettano (Esercizio - Monitor per conto bancario, cannibali e fabbrica (eserciziario, esercizi 16, 17 e 103));
  3. 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 nn make(chan struct{}, n) pieno di nn gettoni, oppure un canale vuoto con capacità nn 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à nn 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.

barbiere.gogo
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:

conto.gogo
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:

bar.gogo
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 nn? Traccia. Con un canale con buffer di capacità nn: wait = invio (blocca quando i gettoni sono finiti), signal = ricezione. È la tecnica usata nei filosofi a cena con N−1N-1 posti.

Versione ripasso

Teoria collegata