Thread e concorrenza - modelli, Pthreads e goroutine

Un processo (Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →) ha un solo flusso di istruzioni. Un thread permette più flussi dentro lo stesso processo. Questa nota spiega perché servono, come il sistema li realizza, come si programmano in C con Pthreads e in Go con le goroutine, e quali problemi nascono; la condivisione dei dati tra thread apre il capitolo della sincronizzazione (Sincronizzazione - sezione critica, race condition e mutexQuando più processi o thread accedono agli stessi dati e il risultato dipende dall'ordine degli accessi si ha una race condition (esempio: counter++ e counter-- sono tre istruzioni macchina ciascuna, e interleaving diversi danno 4, 5 o 6 partendo da 5); il problema della sezione critica chiede un protocollo (entry section, sezione critica, exit section, remainder section) che garantisca mutua esclusione, progresso e attesa limitata; disabilitare gli interrupt non scala sui multiprocessori, l'alternanza stretta con turn viola il progresso, la soluzione di Peterson (flag[2] e turn) soddisfa i tre requisiti ma può fallire su hardware moderno per il riordino delle istruzioni, per cui servono barriere di memoria; l'hardware offre test_and_set e compare_and_swap (atomiche) e variabili atomiche; il mutex lock (acquire/release, in POSIX pthread_mutex_t) è lo strumento di alto livello, con attesa attiva se è uno spinlock oppure con sospensione del thread se è un mutex di sistema; bloccare due volte lo stesso mutex senza sbloccarlo causa deadlock.Sincronizzazione - sezione critica, race condition e mutex →).

Che cosa è un thread

Definizione (thread). Un thread è l'unità di utilizzo della CPU: ha un identificatore, un program counter, un insieme di registri e uno stack propri, e condivide con gli altri thread dello stesso processo il codice, i dati globali, l'heap e le risorse del sistema operativo (come i file aperti).

Un processo con un solo thread è il caso di prima; con più thread, il PCB contiene più program counter e più stato.

La differenza con fork (Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →): un figlio ha una copia della memoria, un thread vede la stessa memoria.

Perché i thread

La maggior parte delle applicazioni moderne è multithread (e anche i kernel): compiti diversi (leggere dati, aggiornare lo schermo, rispondere a una richiesta di rete) diventano thread separati. Un server multithread riceve una richiesta e fa creare un thread che la serve, mentre il thread principale torna ad ascoltare. I vantaggi:

• reattività (responsiveness): il programma continua se una sua parte è bloccata (decisivo per le interfacce grafiche);
• condivisione delle risorse: i thread condividono la memoria senza i meccanismi di memoria condivisa o messaggi;
• economia: creare un thread e commutare tra thread costa molto meno di creare un processo e di un cambio di contesto tra processi;
• scalabilità: anche un solo processo sfrutta più core.

Concorrenza e parallelismo

Un sistema può essere concorrente senza essere parallelo (un solo core), non il contrario. Il parallelismo si presenta in due forme:

• parallelismo sui dati (data parallelism): lo stesso insieme di dati è diviso in parti, e su ogni core gira la stessa operazione su una parte (per esempio $M$ thread riempiono ciascuno $N/M$ elementi di un array: è il compito di Esercizio - Thread, race condition e parallelismo sui dati (laboratorio 3));
• parallelismo sui compiti (task parallelism): thread diversi eseguono operazioni diverse, anche sugli stessi dati.

La legge di Amdahl

Teorema (legge di Amdahl). Se una frazione $S$ del programma è seriale (non parallelizzabile) e il sistema ha $N$ core, lo speedup massimo è $$\text{speedup} \le \frac{1}{S + \dfrac{1-S}{N}}$$

Esempio: applicazione al 75% parallela e 25% seriale ($S = 0{,}25$). Con $N = 2$ core:

$$\frac{1}{0{,}25 + 0{,}75/2} = \frac{1}{0{,}625} = 1{,}6.$$

Con $N = 4$: $1/(0{,}25 + 0{,}1875) = 2{,}29$. Per $N \to \infty$ lo speedup tende a $1/S = 4$: la parte seriale pesa in modo sproporzionato, e aggiungere core non basta. La legge non considera del tutto i sistemi multicore moderni. Quando un ciclo è parallelizzabile? Se le iterazioni sono indipendenti (arr[i] = i * i), sì; se ognuna dipende dalla precedente (arr[i] = arr[i-1] + i), no.

Thread utente e thread kernel

• Thread utente (user threads): gestiti da una libreria in spazio utente, senza che il kernel lo sappia.
• Thread kernel (kernel threads): gestiti direttamente dal sistema operativo; supportati da tutti i sistemi generali.

La relazione tra i due tipi definisce il modello di multithreading:

Con many-to-many e many-to-one servono dei canali di comunicazione tra kernel e libreria per tenere il numero giusto di thread kernel. Si usa una struttura intermedia, il processo leggero (lightweight process, LWP): un "processore virtuale" su cui la libreria schedula i thread utente, ognuno legato a un thread kernel (scheduler activations).

Librerie principali: Pthreads (POSIX: thread utente o kernel; UNIX, Linux, macOS), Windows threads (kernel, modello one-to-one: ogni thread ha un id, un insieme di registri, due stack, uno utente e uno kernel, e un'area privata; registri, stack e area formano il contesto), e Java threads.

In Linux non si distingue davvero tra processi e thread: sono tutti task. Il thread si crea con la system call clone() e dei flag che dicono cosa condividere con il padre (spazio degli indirizzi CLONE_VM, file system, file aperti, gestori di segnali, CLONE_THREAD). Senza flag clone() equivale a fork().

Pthreads

Pthreads è lo standard POSIX (IEEE 1003.1c) per creare e sincronizzare thread: specifica il comportamento, non l'implementazione. Le funzioni principali:

Si compila collegando la libreria: gcc programma.c -o programma -lpthread. Esempio completo: si divide la somma dei primi $N$ interi in $M$ parti, una per thread (parallelismo sui dati). Ogni thread scrive il proprio risultato parziale in un suo elemento di un array: nessuna variabile è modificata da due thread, quindi non ci sono race condition.

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>

#define N 1000000L            /* sommare 1 + 2 + ... + N */
#define M 4                   /* numero di thread */

struct lavoro {
    long da, a;               /* intervallo [da, a) assegnato al thread */
    long parziale;            /* risultato del thread */
};

static void *somma_parziale(void *arg)
{
    struct lavoro *w = arg;               /* ogni thread riceve il proprio lavoro */
    long s = 0;
    for (long i = w->da; i < w->a; i++)
        s += i + 1;
    w->parziale = s;
    return NULL;                          /* equivale a pthread_exit(NULL) */
}

int main(void)
{
    pthread_t tid[M];
    struct lavoro w[M];                   /* un elemento per thread: niente variabili condivise in scrittura */

    for (int k = 0; k < M; k++) {
        w[k].da = k * (N / M);
        w[k].a  = (k + 1) * (N / M);
        w[k].parziale = 0;
        if (pthread_create(&tid[k], NULL, somma_parziale, &w[k]) != 0) {
            fprintf(stderr, "pthread_create fallita\n");
            return 1;
        }
    }
    long totale = 0;
    for (int k = 0; k < M; k++) {
        pthread_join(tid[k], NULL);       /* aspetta il thread k, poi legge il suo risultato */
        totale += w[k].parziale;
    }
    printf("somma = %ld (attesa %ld)\n", totale, N * (N + 1) / 2);
    return 0;
}

Per $N = 10^6$ e $M = 4$ ogni thread somma 250 000 numeri e il risultato è $N(N+1)/2 = 500\,000\,500\,000$, uguale a quello seriale.

Trappola classica: passare l'indirizzo di una variabile che cambia. In un ciclo for (int i...) pthread_create(&t[i], NULL, f, &i); tutti i thread leggono la stessa i, che il ciclo continua a incrementare: i thread vedono valori sbagliati o ripetuti. Si risolve passando l'indirizzo di un elemento di un array (&w[k] come sopra), o il valore con un cast di intero a puntatore, oppure creando un oggetto per thread.

Quando due thread modificano la stessa variabile (sum++ e sum-- su una globale), nascono le race condition: è il laboratorio 3 (Esercizio - Thread, race condition e parallelismo sui dati (laboratorio 3)).

Threading implicito

Gestire a mano i thread diventa difficile quando sono molti. Con il threading implicito creazione e gestione passano a compilatori e librerie. Metodi:

• fork-join: si "biforcano" più compiti (fork) e si aspetta la loro fine (join); la libreria decide come dividere;
• thread pool: si creano in anticipo $n$ thread che attendono lavoro; servire una richiesta con un thread già pronto è più rapido che crearne uno, il numero di thread resta limitato dalla dimensione del pool, si separa il compito dal meccanismo e si possono pianificare esecuzioni periodiche;
• OpenMP: direttive del compilatore (#pragma omp parallel for) e API per C, C++ e FORTRAN, per la memoria condivisa; il compilatore crea tanti thread quanti sono i core;
• Grand Central Dispatch (Apple): blocchi di codice messi in una coda di dispatch in attesa di un thread libero in un pool;
• Threading Building Blocks (Intel): libreria C++ con costrutti come parallel_for.

Questioni aperte con i thread

Contention scope

Quando la libreria schedula i thread utente su LWP (many-to-one, many-to-many) la competizione per la CPU è dentro il processo: process-contention scope (PCS), di solito con priorità decise dal programmatore. Quando invece i thread kernel sono schedulati direttamente sulla CPU, competono con tutti i thread del sistema: system-contention scope (SCS). L'API Pthreads permette di chiedere PTHREAD_SCOPE_PROCESS (PCS) o PTHREAD_SCOPE_SYSTEM (SCS) alla creazione, ma Linux e macOS accettano solo PTHREAD_SCOPE_SYSTEM: il programma posix-scope.c del laboratorio 3 mostra lo scope predefinito e poi lo imposta a SYSTEM.

Goroutine in Go

Go è un linguaggio con la concorrenza nel linguaggio. Una goroutine è una funzione eseguita in modo concorrente con le altre, avviata con la parola chiave go. È molto più leggera di un thread: parte con uno stack di pochi KB che cresce quando serve, e il runtime di Go le multiplexa su pochi thread del sistema (un modello many-to-many realizzato dal runtime, con un numero di thread kernel regolato da GOMAXPROCS). Si coordinano con sync.WaitGroup (si aspetta la fine di un gruppo) e con i canali (channel), il meccanismo di comunicazione tipizzato: lo stile Go è «non comunicare condividendo la memoria, ma condividere la memoria comunicando».

package main

import (
	"fmt"
	"sync"
)

func main() {
	var wg sync.WaitGroup
	for i := 0; i < 3; i++ {
		wg.Add(1)                // un compito in più da aspettare
		go func(id int) {        // goroutine: id è passato per valore, ogni goroutine ha il suo
			defer wg.Done()      // alla fine segnala di aver terminato
			fmt.Println("goroutine", id)
		}(i)
	}
	wg.Wait()                    // il main aspetta tutte, altrimenti uscirebbe subito
}

Se main ritorna, il programma termina anche se ci sono goroutine in esecuzione: per questo serve wg.Wait(). L'ordine delle tre stampe non è determinato. Si noti che i è passato come argomento id: è lo stesso problema dell'indirizzo condiviso visto in C (nelle versioni di Go precedenti alla 1.22 una closure che usava direttamente la i del ciclo la condivideva).

Lo stesso esempio della somma parallela, con un canale per raccogliere i risultati parziali (parallelismo sui dati, senza variabili condivise):

package main

import "fmt"

func sommaParziale(v []int, ris chan<- int) { // chan<- : canale in cui si può solo inviare
	s := 0
	for _, x := range v {
		s += x
	}
	ris <- s // invio sul canale (bloccante finché qualcuno riceve)
}

func main() {
	a := make([]int, 1000)
	for i := range a {
		a[i] = i + 1 // 1, 2, ..., 1000
	}
	const m = 4
	ris := make(chan int)
	pezzo := len(a) / m
	for k := 0; k < m; k++ {
		go sommaParziale(a[k*pezzo:(k+1)*pezzo], ris) // una goroutine per quarto
	}
	totale := 0
	for k := 0; k < m; k++ {
		totale += <-ris // ricezione: aspetta il risultato di una goroutine
	}
	fmt.Println(totale) // 500500
}

Il canale senza buffer fa da rendez-vous (Processi - stati, PCB, creazione con fork ed execUn processo è un programma in esecuzione (entità attiva) con codice (text), dati globali, heap, stack e lo stato dell'esecuzione; il kernel lo descrive con il PCB (Process Control Block: stato, program counter, registri, informazioni di scheduling, memoria, accounting, file aperti, in Linux la struct task_struct) e passa da un processo all'altro con il context switch (puro overhead); gli stati sono new, ready, running, waiting, terminated, con una ready queue e varie wait queue; in UNIX fork() crea un figlio copia del padre (restituisce 0 al figlio e il pid del figlio al padre), exec() sostituisce il programma del figlio, wait()/waitpid() raccoglie lo stato di uscita: senza di essa un figlio terminato è uno zombie, un figlio il cui padre è morto è un orfano adottato da init/systemd; i processi cooperanti comunicano con memoria condivisa (POSIX shm) o scambio di messaggi (diretto o indiretto, sincrono o asincrono, buffer a capacità zero, limitata, illimitata) e con pipe ordinarie (padre-figlio, unidirezionali) e named pipe (FIFO).Processi - stati, PCB, creazione con fork ed exec →): l'invio aspetta la ricezione. Per i problemi classici (produttore-consumatore, lettori-scrittori, filosofi) con goroutine e canali si veda 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 →. Le data race in Go si individuano con go run -race programma.go.

Esercizi collegati

• Esercizio - Thread, race condition e parallelismo sui dati (laboratorio 3)

Domande d'esame

1. Qual è la differenza tra concorrenza e parallelismo? Un sistema con un solo core può essere concorrente? E parallelo? Traccia. Concorrenza = più compiti che fanno progressi alternandosi (lo scheduler); parallelismo = più compiti eseguiti nello stesso istante, richiede più unità di elaborazione. Con un core si ha concorrenza ma non parallelismo.

2. Un'applicazione è parallelizzabile al 60%. Qual è lo speedup massimo con 4 core e con infiniti core? Traccia. $S = 0{,}4$. Con 4 core: $1/(0{,}4 + 0{,}6/4) = 1/0{,}55 = 1{,}82$. Con infiniti core: $1/S = 2{,}5$.

3. Confrontare i modelli many-to-one, one-to-one e many-to-many. Quale usa Linux? Traccia. Many-to-one: un thread kernel per tutti, se uno si blocca si bloccano tutti, niente parallelismo. One-to-one: un thread kernel per ogni thread utente, più concorrenza ma costo per thread (Linux e Windows). Many-to-many: multiplexing di molti thread utente su alcuni thread kernel, flessibile ma complesso.