Il professor Ricci apre la lezione introducendo il concetto fondamentale del design task-oriented: quando progettiamo un sistema concorrente, dobbiamo iniziare dall'analisi del problema per identificare i task — unita di lavoro ben definite, con un inizio e una fine — che compongono il sistema. Questa analisi puo partire dai dati (data-driven) o dalle funzionalita (function-driven).
Un task non e un thread. Un task e un'unita di lavoro logica, astratta, indipendente. Il thread e il veicolo che esegue il task. Separare i due concetti e il primo passo verso un buon design concorrente.
L'analisi procede rispondendo a tre domande fondamentali:
Il professore sottolinea l'importanza di adottare un approccio limpido e lineare: esplicitare le cose, non nasconderle dietro astrazioni troppo sofisticate. La semplicita nel design paga sempre, soprattutto nei sistemi concorrenti dove la complessita intrinseca e gia elevata.
Sull'Assignment 1: il docente sara disponibile come "coach". Non si tratta di ricevere soluzioni prefabbricate, ma di discutere insieme l'approccio. Se un gruppo arriva dicendo "non riesco a capire come fare una certa cosa", si puo discutere. Il vero obiettivo dell'Assignment e fare qualcosa di concreto, non banale, che permetta di discutere insieme durante il colloquio orale.
Il pattern Division of Labor, noto anche come strategia del divide-et-impera, consiste nel:
Il risultato di una buona analisi task-oriented e un'organizzazione del programma piu semplice, che facilita il recovery da errori (i task sono confini naturali per le transazioni) e promuove naturalmente la concorrenza.
Il professor Ricci introduce il Executor Framework di Java (java.util.concurrent, JDK 5.0) come l'astrazione principale per il task-oriented programming. Il framework disaccoppia la sottomissione di un task dalla sua esecuzione.
public interface Executor {
void execute(Runnable task);
}Questa interfaccia semplice e il cuore del framework. Invece di creare un thread per ogni task (one-thread-per-task), si sottomette il task a un executor che decide quando, dove e come eseguirlo secondo una specifica execution policy.
Una execution policy specifica:
La classe factory Executors fornisce diverse implementazioni pronte:
| Metodo factory | Comportamento |
|---|---|
newFixedThreadPool(n) | Pool di dimensione fissa: mantiene n thread, li riusa per i task successivi |
newCachedThreadPool() | Pool flessibile: thread inattivi vengono terminati dopo 60s, se ne creano di nuovi se serve |
newSingleThreadExecutor() | Un singolo worker thread, task in coda FIFO |
newScheduledThreadPool(n) | Pool per task con ritardo o periodici |
Il docente mostra un esempio concreto di web server che usa un fixed thread pool al posto del pattern one-thread-per-task:
class TaskExecutionWebServer {
private static final int NTHREADS
= Runtime.getRuntime().availableProcessors() + 1;
private static final Executor exec =
Executors.newFixedThreadPool(NTHREADS);
public static void main(String[] args) throws IOException {
ServerSocket socket = new ServerSocket(80);
while (true) {
Socket connection = socket.accept();
exec.execute(() -> {
handleRequest(connection);
});
}
}
}Il docente sottolinea: "Eseguire i task in modo sequenziale e come il SingleThreadWebServer: poor performance, poor responsiveness, poor resource usage. Con un thread per task si migliora tutto, ma si crea il problema della stabilita sotto carico pesante." Il thread pool e il punto di equilibrio.
Rispetto alla creazione esplicita di thread per ogni task (one-thread-per-task), l'approccio pool-based offre:
Il professore sottolinea anche un avvertimento importante: nel framework Executor, i task devono essere indipendenti. Un task non dovrebbe aspettare un altro task, perche bloccando un task si blocca anche il thread fisico che lo esegue, aprendo la possibilita a deadlock.
I task nell'Executor Framework sono unita di lavoro ben definite che iniziano e terminano. Non sono loop infiniti (come potrebbero essere thread, agenti o processi). Questa differenza e cruciale: un task compute-area termina; un thread server no.
Non tutti i task sono di tipo fire-and-forget (Runnable). Spesso un task deve restituire un risultato. Per questo l'Executor Framework introduce due interfacce complementari: Callable<V> e Future<V>.
Simile a Runnable ma con due differenze fondamentali: il metodo si chiama call() invece di run(), e puo restituire un valore oltre a poter lanciare eccezioni.
public interface Callable<V> {
V call() throws Exception;
}Un Future<V> rappresenta il risultato di un calcolo asincrono. Il professore spiega che e un contenitore che sara valorizzato nel tempo, una sorta di promessa di un risultato futuro.
public interface Future<V> {
boolean cancel(boolean mayInterruptIfRunning);
boolean isCancelled();
boolean isDone();
V get() throws InterruptedException, ExecutionException,
CancellationException();
V get(long timeout, TimeUnit unit) throws ...;
}Il docente accenna a un dibattito interessante: tecnicamente le Future non sono "funzionali" perche introducono tempo e non-determinismo. Un collega (Viroli) sostiene che con le monadi si possa conciliare il tutto, ma il professore preferisce rimanere su una spiegazione pragmatica.
La differenza tra execute(Runnable) e submit(Callable) e la seguente:
// Esegue un task senza risultato
executor.execute(runnableTask);
// Sottomette un task con risultato e restituisce un Future
Future<Integer> future = executor.submit(callableTask);
Integer result = future.get(); // bloccante finche il task non completafuture.get() e bloccante: il thread chiamante si sospende finche il task non ha prodotto il risultato. Questo e il punto in cui la concorrenza si riconcilia con la sequenzialita.
Il professore presenta il classico problema del calcolo di un integrale definito per approssimazione trapezoidale:
// ComputeAreaTask: calcola l'area di un singolo trapezio
class ComputeAreaTask implements Callable<Double> {
private final double x0, delta;
private final Function<Double,Double> f;
// costruttore...
public Double call() {
return (f.apply(x0) + f.apply(x0 + delta)) * delta / 2.0;
}
}
// Master: scompone l'intervallo e colleziona i risultati
List<Future<Double>> futures = new ArrayList<>();
for (double x = a; x < b; x += delta) {
futures.add(executor.submit(new ComputeAreaTask(x, delta, f)));
}
double totale = 0.0;
for (Future<Double> f : futures) {
totale += f.get(); // si blocca finche il task non e pronto
}Il docente sottolinea che il master non si sospende subito: sottomette tutti i task, colleziona i future, e solo dopo chiama get() su ciascuno. In questo modo i task possono essere eseguiti concorrentemente mentre il master continua a preparare i task successivi.
L'esempio del PrimeGenerator mostra come implementare la cancellazione cooperativa usando un flag volatile:
public class PrimeGenerator implements Runnable {
private final List<BigInteger> primes = new ArrayList<>();
private volatile boolean cancelled;
public void run() {
BigInteger p = BigInteger.ONE;
while (!cancelled) {
p = p.nextProbablePrime();
synchronized (this) { primes.add(p); }
}
}
public void cancel() { cancelled = true; }
public synchronized List<BigInteger> get() {
return new ArrayList<>(primes);
}
}
// Uso: genera numeri primi per 1 secondo
List<BigInteger> aSecondOfPrimes() throws InterruptedException {
PrimeGenerator gen = new PrimeGenerator();
new Thread(gen).start();
try { SECONDS.sleep(1); } finally { gen.cancel(); }
return gen.get();
}Il docente avverte: la cancellazione cooperativa (con flag) non funziona se il thread e bloccato su una put bloccante di un buffer pieno. In quel caso serve l'interruption.
class PrimeProducer extends Thread {
private BlockingQueue<BigInteger> queue;
// costruttore...
public void run() {
BigInteger p = BigInteger.ONE;
try {
while (!Thread.currentThread().isInterrupted()) {
queue.put(p.nextProbablePrime());
}
} catch (InterruptedException ex) {
// allow thread to exit
}
}
public void cancel() { interrupt(); }
}Il professor Ricci passa a un esempio pratico e doloroso: un cronometro implementato con pattern Model-View-Controller, ma con due bug classici della programmazione concorrente in GUI Java.
Il programma si chiama CronoMVCNotReactivePlusRace ed e l'esempio di come NON si fa. L'idea e semplice: un cronometro con pulsanti Start, Stop e Reset che conta i secondi in un text field.
Questa versione ha due problemi fondamentali:
1. Non e reattiva (non responsive) — premere Start blocca completamente l'interfaccia
2. Race condition — viola la mutua esclusione sullo stato del modello
Il bug principale e nel controller: l'azione di start viene eseguita direttamente sull'Event Dispatch Thread (EDT), il thread di Swing che gestisce tutti gli eventi della GUI. Cosa succede?
// VERSIONE BUGGY: il controller esegue il loop sull'EDT!
buttonStart.addActionListener(e -> {
started = true;
while (started) {
model.updateState();
display.setText(String.valueOf(model.getValue()));
// ^^^^^ setText accoda un task all'EDT...
// ma l'EDT e gia occupato qui nel loop!
Thread.sleep(100); // blocca tutto
}
});Il problema e duplice:
setText() su un componente Swing non aggiorna immediatamente il display: accoda un task nella coda eventi dell'EDT.while(started) del controller. Quindi non puo servire la coda eventi. Il display non si aggiorna mai e l'interfaccia e completamente bloccata.L'EDT e un thread a event loop: deve stare sempre in attesa sulla coda eventi, eseguire rapidamente un handler, e tornare ad aspettare. Se lo "imbragliamo" in un loop che non compete a lui, il sistema si blocca.
La versione corretta si chiama CronoMVCReactiveNonRaces. La regola fondamentale e: l'EDT si occupa solo della business logic che riguarda la view, non il model, non il controller.
Separare il flusso di controllo: la reazione agli eventi (notifyStarted, notifyStopped) appartiene al controller, ma l'esecuzione del loop di conteggio deve avvenire su un thread separato, non sull'EDT.
// VERSIONE CORRETTA: il controller delega a un thread separato
class Controller {
private final Model model;
private final View view;
private Thread countingThread; // thread separato per il conteggio
public void notifyStarted() {
countingThread = new Thread(() -> {
while (isRunning()) {
model.updateState(); // aggiorno il modello
SwingUtilities.invokeLater(() -> {
view.updateDisplay( // aggiorno la view sull'EDT
model.getValue());
});
Thread.sleep(100);
}
});
countingThread.start();
}
public void notifyStopped() {
stopRunning(); // flag per fermare il loop
}
}SwingUtilities.invokeLater() accoda un task nella coda dell'EDT e torna immediatamente. Il thread di conteggio puo continuare a eseguire senza bloccare l'interfaccia. In questo modo l'EDT rimane libero di servire eventi (pulsanti, aggiornamenti) e il cronometro funziona correttamente.
Il docente sottolinea che invokeAndWait() e un'alternativa sincrona: il chiamante si blocca finche l'EDT non ha completato il task. Utile per sincronizzarsi, ma per l'aggiornamento del display e preferibile invokeLater().
Ricorda: invokeLater e invokeAndWait — entrambi accodano un task nella Event Queue dell'EDT. La differenza e che invokeAndWait e sincrono: il chiamante attende il completamento. invokeLater e asincrono: accoda e ritorna immediatamente.
Il secondo esempio pratico e Sketch2, un programma GUI che illustra come gestire input asincrono da tastiera all'interno di un'architettura Model-View-Controller.
L'applicazione mostra un conteggio che viene aggiornato sia automaticamente (da un componente attivo che incrementa il valore periodicamente) sia manualmente (premendo il tasto I sulla tastiera). Il tasto R resetta il conteggio.
La sfida: la tastiera genera eventi in modo asincrono, indipendentemente dal ciclo di vita del programma. Come li integriamo nel MVC?
// Gestione dell'input da tastiera in Java con MVC
public class Sketch2 {
public static void main(String[] args) {
Model model = new Model();
View view = new View(model);
Controller controller = new Controller(model, view);
// Il controller registra listener per gli eventi di tastiera
view.addKeyListener(new KeyAdapter() {
public void keyPressed(KeyEvent e) {
if (e.getKeyCode() == KeyEvent.VK_I) {
controller.notifyIncrementRequest();
} else if (e.getKeyCode() == KeyEvent.VK_R) {
controller.notifyResetRequest();
}
}
});
}
}Il professore spiega che la gestione e concettualmente identica a quella del cronometro: il controller reagisce agli eventi, modifica il modello su un thread separato (non l'EDT), e usa SwingUtilities.invokeLater() per aggiornare la vista. In questo modo l'interfaccia rimane reattiva anche durante computazioni lunghe.
Sketch2 rappresenta un pattern generale per la gestione di input asincrono in GUI concorrenti: gli eventi esterni (tastiera, mouse, rete) vengono catturati da listener che notificano il controller, il quale orchestra le modifiche al modello su thread separati.
L'esercizio delle palle che rimbalzano e un caso studio di simulazione fisica concorrente. Il professore presenta un modello in cui delle palline si muovono in uno spazio bidimensionale, con:
friction factor)Ecco la logica di aggiornamento del modello fisico:
class Particle {
double x, y; // posizione
double vx, vy; // velocita
void update(double dt) {
// Applica attrito (decelerazione costante)
double friction = 0.98; // coefficiente
vx *= friction;
vy *= friction;
// Se la velocita e molto bassa, ferma del tutto
if (Math.abs(vx) < 0.01) vx = 0;
if (Math.abs(vy) < 0.01) vy = 0;
// Aggiorna posizione (cinematica)
x += vx * dt;
y += vy * dt;
// Boundary check: rimbalzo sui bordi
if (x < 0 || x > maxX) { vx = -vx; x = clamp(x, 0, maxX); }
if (y < 0 || y > maxY) { vy = -vy; y = clamp(y, 0, maxY); }
}
}Il professore sottolinea la separazione netta: le coordinate del modello sono logiche, non pixel. Sara la view a mappare le coordinate logiche nello spazio visivo (viewport). Questo e il pattern MVC applicato alla simulazione fisica.
Il professor Ricci introduce il Fork-Join Framework (Java SE 7) come evoluzione del pattern Executor per algoritmi che non hanno una topologia dei dati conosciuta a priori (es. strutture a grafo o ad albero).
Il problema: con un executor tradizionale, se un task Callable aspetta il risultato di un altro Callable, il thread che lo esegue rimane in attesa sprecando una risorsa. Fork-Join risolve questo con l'algoritmo di work-stealing.
// Esempio: somma degli elementi di un array (divide & conquer)
class SumTask extends RecursiveTask<Long> {
static final int THRESHOLD = 1000;
private final int[] array;
private final int lo, hi;
SumTask(int[] a, int lo, int hi) { this.array = a; this.lo = lo; this.hi = hi; }
protected Long compute() {
if (hi - lo < THRESHOLD) {
long sum = 0;
for (int i = lo; i < hi; i++) sum += array[i];
return sum;
}
int mid = (lo + hi) / 2;
SumTask left = new SumTask(array, lo, mid);
SumTask right = new SumTask(array, mid, hi);
left.fork(); // fork: avvia il task in parallelo
long rightResult = right.compute(); // compute: esegui direttamente
long leftResult = left.join(); // join: attendi il risultato
return leftResult + rightResult;
}
}
// Uso con ForkJoinPool
ForkJoinPool pool = new ForkJoinPool();
long total = pool.invoke(new SumTask(array, 0, array.length));Il work-stealing e il trucco: quando un thread si blocca in attesa del risultato di un fork, invece di rimanere idle, ruba (steal) un altro task dalla coda di un altro thread. Questo mantiene tutti i thread occupati e migliora il throughput complessivo.
Fork-Join realizza il pattern Map-Reduce (o divide-et-impera):
Il Fork-Join Framework e particolarmente efficace per algoritmi su strutture ricorsive come alberi, grafi, e per elaborazione di grandi volumi di dati con pattern map/reduce.
Il professore accenna, nelle slide, al concetto di Structured Concurrency introdotto in JDK 20 (incubating). L'idea e semplice ma potente: se un task si divide in subtask concorrenti, tutti i subtask devono tornare allo stesso punto — il blocco di codice del task padre.
La classe StructuredTaskScope permette di strutturare un task come una famiglia di subtask concorrenti, coordinati come unita:
// Esempio: fetch parallelo di due sorgenti
Response handle() throws ExecutionException, InterruptedException {
try (var scope = new StructuredTaskScope.ShutdownOnFailure()) {
Future<String> user = scope.fork(() -> findUser());
Future<Integer> order = scope.fork(() -> fetchOrder());
scope.join(); // attendi entrambi i fork
scope.throwIfFailed(); // propaga errori
// Entrambi completati con successo
return new Response(user.resultNow(), order.resultNow());
} // scope si chiude: tutti i fork sono completati
}Il vantaggio: il ciclo di vita dei subtask e confinato al blocco try-with-resources. Non ci sono thread o task "orfani" che continuano dopo che il parent e terminato. La leggibilita e la manutenibilita sono simili al codice sequenziale.
Il professore introduce i semafori, il costrutto fondamentale per la coordinazione tra processi, introdotto da Dijkstra nel 1968. Un semaforo e un tipo di dato astratto fornito dalla macchina concorrente.
Un semaforo S e un tipo di dato composto con due campi:
S.V — un intero ≥ 0 (il valore del semaforo)S.L — un insieme di identificatori di processo (la coda dei processi bloccati)Viene inizializzato con S = (k, {}) dove k ≥ 0 e il valore iniziale di V. Fornisce due operazioni atomiche:
wait(S) = < if (S.V > 0)
S.V := S.V - 1
else
S.L := S.L + {p}
p.state := blocked >
signal(S) = < if (S.L = {})
S.V := S.V + 1
else
let q := arbitrary element of S.L
S.L := S.L - {q}
q.state := ready >
Il docente presenta l'invariante che ogni semaforo soddisfa:
S.V >= 0 S.V = k + #signal(S) - #wait(S)
dove k e il valore iniziale, #signal(S) e il numero di signal completati, e #wait(S) e il numero di wait completati con successo (esclusi i processi bloccati).
Il professore distingue tre tipi principali:
Semafori il cui valore intero puo assumere solo i valori 0 e 1. Si usano tipicamente per implementare la mutua esclusione (da qui il nome "mutex"). Inizializzati con S = (1, {}).
Semafori il cui valore intero puo assumere qualsiasi valore ≥ 0. Usati per gestire risorse condivise con piu istanze disponibili (es. pool di connessioni). Il valore rappresenta il numero di risorse disponibili. Inizializzati con S = (N, {}) dove N e il numero di risorse.
Semafori inizializzati con 0, usati esclusivamente per la sincronizzazione (signalling) tra processi. Un processo esegue wait(S) per attendere un segnale; un altro esegue signal(S) per inviarlo. Inizializzati con S = (0, {}).
Il professore distingue anche tra semafori forti (S.L e una coda FIFO) e deboli (S.L e un insieme). La differenza cruciale: i semafori forti garantiscono l'assenza di starvation per qualsiasi numero N di processi. I semafori deboli no.
Esistono anche i busy-wait semaphores, senza lista S.L: il wait e un ciclo attivo che testa S.V > 0. Sono appropriati in sistemi multiprocessore con bassa contesa, dove il processo in attesa ha un proprio processore e non spreca cicli utili ad altri.
// Busy-wait semaphore (no S.L) wait(S) = < await(S.V > 0); S.V := S.V - 1 > signal(S) = < S.V := S.V + 1 >
Il problema della sezione critica (CS) viene risolto in modo elegante e semplice con i semafori. Per due processi P e Q:
// Semaforo binario inizializzato a (1, {})
S := (1, {})
// Processo P // Processo Q
loop forever loop forever
NCS NCS
wait(S) wait(S)
CS CS
signal(S) signal(S)Il professore dimostra la correttezza costruendo il diagramma di stato ridotto. Il semaforo garantisce:
La soluzione con semaforo debole per N processi NON e immune da starvation. Il docente lo sottolinea: per N processi, se la lista S.L e un insieme, un processo potrebbe essere saltato indefinitamente.
Il problema del Producer-Consumer e un classico esempio di coordinazione tra processi. Il professore presenta tre varianti con complessita crescente.
Con un buffer infinito, serve sincronizzare solo il consumatore: non deve prelevare da un buffer vuoto.
UnboundedQueue<Item> buffer := empty queue
semaphore availItems := (0, {})
// Producer // Consumer
loop forever loop forever
Item el := produce wait(availItems)
append(buffer, el) Item el := take(buffer)
signal(availItems) consume(el)Con un buffer di capacita N, serve anche sincronizzare il produttore: non deve inserire in un buffer pieno. I due semafori availItems e availPlaces sono un esempio di split semaphores.
L'invariante dei due semafori divisi: availItems.V + availPlaces.V = N. Quando il produttore wait(availPlaces), riduce i posti liberi e automaticamente aumenta la probabilita che il consumatore possa lavorare, e viceversa.
Se le operazioni sul buffer non sono atomiche (append/take), serve anche un semaforo mutex per la mutua esclusione:
BoundedQueue<Item> buffer := empty queue
semaphore availItems := (0, {})
semaphore availPlaces := (N, {})
binary semaphore mutex := (1, {})
// Producer // Consumer
loop forever loop forever
Item el := produce wait(availItems)
wait(availPlaces) wait(mutex)
wait(mutex) Item el := take(buffer)
append(buffer, el) signal(mutex)
signal(mutex) signal(availPlaces)
signal(availItems) consume(el)Il professor Ricci presenta il classico problema dei Filosofi a Cena, introdotto da Dijkstra nel 1971 (originariamente come problema di 5 computer che competono per 5 drive a nastro) e divulgato da Tony Hoare.
Cinque filosofi siedono a un tavolo con 5 piatti e 5 forchette. Ogni filosofo alternativamente pensa e mangia. Per mangiare, un filosofo ha bisogno di due forchette (la sinistra e la destra). Il problema e progettare i protocolli di pre- e post- per garantire:
Il primo tentativo modella ogni forchetta come un semaforo binario:
semaphore array[0..4] fork := [1, 1, 1, 1, 1]
// Filosofo i (0..4)
loop forever
think
wait(fork[i]) // prendi forchetta sinistra
wait(fork[(i+1) % N]) // prendi forchetta destra
eat
signal(fork[i]) // rilascia sinistra
signal(fork[(i+1) % N]) // rilascia destraQuesto tentativo deadlocka! Sotto un interleaving in cui tutti i filosofi prendono la forchetta sinistra prima che qualcuno provi a prendere la destra, ognuno tiene una forchetta aspettando l'altra: si crea un ciclo di attesa circolare.
semaphore array[0..4] fork := [1, 1, 1, 1, 1]
semaphore ticket := (4, {}) // al massimo 4 filosofi in sala
loop forever
think
wait(ticket) // entra in sala
wait(fork[i])
wait(fork[(i+1) % N])
eat
signal(fork[i])
signal(fork[(i+1) % N])
signal(ticket) // esce dalla salaLimitando a N-1 il numero di filosofi che possono mangiare contemporaneamente, si evita il deadlock. Con 5 filosofi e 4 ticket, almeno un filosofo non puo iniziare a mangiare, rompendo il ciclo.
semaphore array[0..4] fork := [1, 1, 1, 1, 1]
integer first = min(i, (i+1) % N)
integer second = max(i, (i+1) % N)
loop forever
think
wait(fork[first]) // prendi forchetta con indice minore
wait(fork[second]) // prendi forchetta con indice maggiore
eat
signal(fork[first])
signal(fork[second])L'ultimo filosofo (indice 4) prendera prima la forchetta 0 (destra) e poi la 4 (sinistra), rompendo il ciclo di attesa circolare. Regola generale: assegnare un ordine totale ai lock e acquisirli sempre nello stesso ordine.
Il problema Readers-Writers (Courtois, Heymans, Parnas, 1971) e un'astrazione dell'accesso concorrente a un database. I reader possono leggere concorrentemente. I writer richiedono mutua esclusione totale.
Invarianti da rispettare:
nR >= 0 nW = 0 || nW = 1 (nR > 0 → nW = 0) ∧ (nW = 1 → nR = 0)
Un primo tentativo con un singolo semaforo lock serializza tutti gli accessi, anche quelli dei reader. Inutile: serve permettere ai reader di lavorare in parallelo.
La soluzione usa un semaforo per i writer (rw) e un mutex per i reader che aggiornano il contatore nr:
binary semaphore mutexR := (1, {})
int nr := 0
binary semaphore rw := (1, {})
DataBase dbase;
// Reader // Writer
loop forever loop forever
wait(mutexR) wait(rw)
if nr == 0 Item el := create_record
wait(rw) write(dbase, el)
nr := nr + 1 signal(rw)
signal(mutexR)
Item el := read(dbase)
wait(mutexR)
nr := nr - 1
if nr == 0
signal(rw)
signal(mutexR)Il primo reader acquisisce il lock rw (bloccando i writer), ma gli altri reader possono entrare liberamente. L'ultimo reader rilascia rw, permettendo ai writer di procedere.
Il professore introduce i monitor, un costrutto di alto livello introdotto da Brinch Hansen (1973) e generalizzato da Hoare (1974). I monitor nascono dalla constatazione che i semafori, pur potenti, sono troppo low-level e error-prone per programmi complessi.
Un monitor e un data type astratto che incapsula stato, operazioni e politica di sincronizzazione. E come un modulo (o un oggetto) che fornisce intrinsecamente mutua esclusione su tutti i suoi metodi.
monitor MonitorName {
// variabili permanenti (stato privato)
// codice di inizializzazione
procedure (o entry) NomeOp(params) {
// corpo
}
}Un esempio semplice: un contatore thread-safe.
monitor Counter {
int count;
procedure inc() {
count := count + 1
}
procedure getValue(): int {
return count
}
}Il docente sottolinea: la mutua esclusione e implicita. Il programmatore non deve usare wait/signal. Se due processi chiamano inc() contemporaneamente, il monitor garantisce l'atomicita.
La sola mutua esclusione non basta: serve anche la sincronizzazione. I monitor forniscono le variabili condizione (condition variables) per questo scopo.
Una variabile condizione e un tipo di dato primitivo che permette di sospendere (waitC) e risvegliare (signalC) processi all'interno di un monitor. Ogni variabile condizione ha associata una coda FIFO di processi bloccati.
waitC(cond) = < append p to cond.queue
p.state := blocked
monitor.lock := release >
signalC(cond) = < if cond.queue != empty
q := remove head of cond.queue
q.state := ready >
waitC rilascia il lock del monitor (altrimenti nessun altro processo potrebbe entrare per cambiare lo stato e risvegliarlo). signalC risveglia il processo in testa alla coda (semaforo forte).
| Semaforo | Condition Variable (Monitor) |
|---|---|
| wait puo non bloccare (se S.V > 0) | waitC blocca sempre |
| signal ha sempre effetto | signalC non ha effetto se la coda e vuota |
| signal sblocca un processo arbitrario | signalC sblocca il processo in testa alla coda |
| Il processo sbloccato puo proseguire subito | Il processo sbloccato deve riacquisire il lock del monitor |
Non-preemptive: il signaler continua l'esecuzione; il processo risvegliato eseguira in un momento successivo. PrioritA: E < W < S (E = processi bloccati sull'entry, W = processi in wait, S = signaler).
Preemptive: il processo risvegliato esegue subito; il signaler aspetta. PrioritA: E = S < W.
La soluzione classica (Hoare). Come Signal & Wait, ma il signaler ha priorita rispetto ai processi in attesa sull'entry lock quando puo riprendere. PrioritA: E < S < W.
monitor SynchCell {
int value;
boolean available := false;
cond isAvail;
procedure set(int v) {
value := v
available := true
signalC(isAvail)
}
procedure get(): int {
if (!available)
waitC(isAvail)
return value
}
}Il professore fa notare: se piu processi sono in waitC su isAvail, un singolo signalC ne sveglia solo uno. Per svegliarli tutti, si usa signalAllC — utile quando non si sa quanti processi stanno aspettando.
Il professore mostra come i monitor semplificano la soluzione dei classici problemi di coordinazione, incapsulando la politica di sincronizzazione nella struttura dati stessa.
monitor BoundedBuffer {
int[] elems := new int[MAX_ELEMS]
int first := 0, last := 0
cond notFull, notEmpty
procedure put(int elem) {
if ((last + 1) % MAX_ELEMS = first)
waitC(notFull)
elems[last] := elem
last := (last + 1) % MAX_ELEMS
signalC(notEmpty)
}
procedure take(): int {
if (first = last)
waitC(notEmpty)
int elem := elems[first]
first := (first + 1) % MAX_ELEMS
signalC(notFull)
return elem
}
}
// Producer // Consumer
loop loop
ElemType el := produce ElemType el := BoundedBuffer.take()
BoundedBuffer.put(el) consume(el)Il buffer e implementato come array circolare. Le condition variables notFull e notEmpty gestiscono la sincronizzazione. La mutua esclusione e implicita nel monitor.
// Invariant: (nr == 0 or nw == 0) and (nw <= 1)
monitor RWLock {
int nr, nw := 0
cond okToRead, okToWrite
procedure request_read() {
while (nw > 0)
waitC(okToRead)
nr := nr + 1
}
procedure release_read() {
nr := nr - 1
if nr = 0
signalC(okToWrite)
}
procedure request_write() {
while (nr > 0 or nw > 0)
waitC(okToWrite)
nw := nw + 1
}
procedure release_write() {
nw := nw - 1
signalC(okToWrite)
signalAllC(okToRead)
}
}Il docente sottolinea l'uso di while invece di if nella condizione di wait — pattern fondamentale per gestire la riapertura della condizione dopo signal (soprattutto con semantica Signal & Continue).
Con Signal & Continue, dopo esser stati risvegliati, i processi devono ricontrollare la condizione. Un while loop e obbligatorio, non opzionale. Questo e un errore comune che porta a bug sottili.
Il professore chiude la lezione con una panoramica sulla verifica formale dei programmi concorrenti. Perche la verifica tradizionale (testing) non basta?
Il testing rivela la presenza di errori, non la loro assenza. Nei programmi concorrenti, lo stesso input puo dare output diversi in scenari diversi.
— Prof. Ricci
| Proprieta | Descrizione | Esempio |
|---|---|---|
| Safety | "Le cose brutte non accadono mai" — sempre vera in ogni stato | Mutua esclusione: ¬(p3 ∧ q3) |
| Liveness | "Le cose buone accadono prima o poi" — vera in qualche stato futuro | Assenza starvation: p2 → ⋄ p3 |
| Fairness | "Ogni processo ottiene il suo turno infinite volte" | Scheduling: ogni azione eligible viene eseguita |
LTL aggiunge operatori temporali alla logica proposizionale per esprimere proprieta delle computazioni:
□p (always p) — p e vera in tutti gli stati futuri ◆p (eventually p) — p diventa vera prima o poi ○p (next p) — p e vera nello stato successivo p U q (p until q) — p resta vera finche q non diventa vera
LTL permette di esprimere proprieta come: □(p2 → ◆p3) — "ogni volta che un processo e pronto per entrare in CS, prima o poi ci entrera". Oppure il bounded overtaking: tryp → (¬CSq) W (CSq W ((¬CSq) W CSp)) — al massimo un sorpasso.
Il model checking e la tecnica piu importante per la verifica automatica di sistemi concorrenti. Esplora esaustivamente lo spazio degli stati e verifica che le proprieta (espresse in LTL o simili) siano soddisfatte.
# Esempio: file di configurazione JPF
# target = pcd.lab03.jpf.TestSequential
# classpath = ${jpf-core}/build:target/classesTLA+ (Temporal Logic of Actions) e un linguaggio di specifica formale introdotto da Leslie Lamport, usato per descrivere insiemi di comportamenti legali di un sistema. PlusCal (ex +CAL) e un linguaggio algoritmico basato su TLA+, piu vicino a un vero linguaggio di programmazione.
Il professore mostra un esempio di Peterson in PlusCal:
--algorithm Peterson {
variables flag = [i \in {0,1} |-> false], turn = 0;
process (proc \in {0,1}) {
a0: while (true) {
a1: flag[self] := true;
a2: turn := Not(self);
a3a: if (flag[Not(self)]) { goto a3b } else { goto cs };
a3b: if (turn = Not(self)) { goto a3a } else { goto cs };
cs: skip; \* critical section
a4: flag[self] := false;
}
}
}Lo stato dell'arte nella verifica: per sistemi piccoli, SPIN o JPF possono esplorare esaustivamente tutti gli stati. Per sistemi grandi si usa il model checking simbolico o la dimostrazione induttiva di invarianti. TLA+ combina entrambi gli approcci.
Un task e un'unita di lavoro logica, astratta, con inizio e fine. Un thread e il veicolo fisico che esegue il task. Il task-oriented programming separa i due concetti: il programmatore definisce i task; l'executor decide come e quando eseguirli su thread.
Perche il loop di conteggio viene eseguito direttamente sull'Event Dispatch Thread (EDT). L'EDT rimane bloccato nel loop, non puo servire altri eventi (pulsanti, aggiornamenti), e setText() sulla GUI accoda un task nella coda eventi che non viene mai eseguito. Risultato: interfaccia bloccata e display non aggiornato.
Accoda un task nella coda degli eventi dell'EDT e ritorna immediatamente (asincrono). Il task verra eseguito dall'EDT quando sara il suo turno. E il meccanismo standard per aggiornare la GUI da un thread diverso dall'EDT.
Due invarianti: S.V >= 0 e S.V = k + #signal(S) - #wait(S), dove k e il valore iniziale, #signal(S) e il numero di signal completati, #wait(S) e il numero di wait completati (esclusi i processi bloccati).
1. Mutua esclusione — una risorsa non condivisibile
2. Hold and wait — processi tengono risorse mentre ne richiedono altre
3. No preemption — le risorse non possono essere revocate
4. Circular wait — esiste un ciclo di attesa tra processi
Se una qualsiasi delle quattro e assente, il deadlock e impossibile.
Tre differenze chiave: (1) wait sul semaforo puo non bloccare se S.V > 0; waitC blocca sempre. (2) signal sul semaforo ha sempre effetto (incrementa S.V); signalC non ha effetto se la coda e vuota. (3) signal sblocca un processo arbitrario; signalC sblocca il processo in testa alla coda (FIFO).
Con la semantica Signal & Continue (usata da Java), il thread risvegliato non ha garanzia che la condizione sia ancora vera: un altro thread potrebbe averla invalidata prima che il risvegliato riacquisisca il lock. Il while ricontrolla la condizione, garantendo la correttezza.
Il testing verifica che una proprieta valga per alcuni scenari selezionati. Il model checking verifica che la proprieta valga per tutti gli scenari possibili, esplorando esaustivamente lo spazio degli stati. Il testing rivela la presenza di errori; il model checking puo provare l'assenza.
Dal momento in cui un processo P cerca di entrare in CS, un altro processo Q puo entrare al massimo k volte prima che P riesca ad entrare. In LTL: tryp → (¬CSq) W (CSq W ((¬CSq) W CSp)) per 1-bounded overtaking.