Domande d'orale

Dà lo speedup massimo ottenibile con N processori quando solo una frazione P del programma (tra 0 e 1) è parallelizzabile: S = 1 / ((1 − P) + P/N), dove lo speedup si misura come T1/TN.

Con P = 0 non c'è nulla da parallelizzare e S = 1 per ogni N; con P = 1 si ha S = N, lo speedup lineare. Per P intermedi S sta tra 1 e N, e quando N cresce tende al tetto 1/(1 − P): la parte sequenziale limita il guadagno qualunque sia il numero di processori. Lo speedup va quindi da 1 a N, non da 0 a 1, che è semmai l'intervallo tipico dell'efficienza.

→ Cap. 1, §7 · Misurare le prestazioni: speedup, Amdahl, efficienza

È la struttura introdotta da Dijkstra con cui si risolve quasi ogni problema di mutua esclusione e di sincronizzazione a memoria condivisa. Ha due campi: S.V, un intero ≥ 0, e S.L, l'insieme dei processi bloccati su S; si usa solo con due operazioni atomiche.

wait(S): se S.V > 0 lo decrementa, altrimenti il processo si blocca in S.L. signal(S): se S.L è vuoto incrementa S.V, altrimenti sveglia un processo di S.L e lascia S.V invariato, perché il permesso passa direttamente al risvegliato. Ne discende l'invariante S.V = k + #signal − #wait, con k valore iniziale.

→ Cap. 5, §1 · Che cos'è un semaforo

Tre usi, che differiscono per valore iniziale: binario o mutex (1, fa da lock e lo stesso processo fa wait e signal attorno alla sezione critica), generale o counting (N, i permessi o le risorse disponibili) ed evento (0: chi aspetta fa wait, chi fa accadere l'evento fa signal, mai lo stesso processo). I primi due servono alla competizione, il terzo alla cooperazione.

Per le garanzie di liveness si distinguono poi i semafori deboli (S.L è un insieme e signal sveglia un processo qualsiasi), forti (S.L è una coda FIFO: niente starvation) e busy-wait (niente S.L, si ritesta il valore).

→ Cap. 5, §2 · Tre usi, una sola struttura → Cap. 5, §3 · Chi viene svegliato? Semafori forti, deboli e busy-wait

Su un multiprocessore, quando chi aspetta ha un processore tutto suo e non toglie CPU ad altri calcoli, e con poca contesa, cioè con attese brevi: girare per pochi istanti costa meno che sospendere il thread e cambiare contesto, e non coinvolge il sistema operativo. Si usano negli algoritmi paralleli. Il prezzo è che non garantiscono l'assenza di starvation, nemmeno con due soli processi.

→ Cap. 5, §3 · Chi viene svegliato? Semafori forti, deboli e busy-wait

L'evento da aspettare è «a1 eseguita»: si crea un semaforo evento a1Done inizializzato a 0, perché l'evento non è ancora accaduto. Chi aspetta fa wait subito prima dell'azione vincolata, chi fa accadere l'evento fa signal subito dopo:

semaphore a1Done := (0, {})

p1                        p2
a1                        b1
signal(a1Done)            wait(a1Done)
a2                        b2
                          b3

Funziona in entrambi gli ordini: se p1 segnala per primo a1Done vale 1 e la wait di p2 passa senza bloccarsi; se p2 arriva prima alla wait, si blocca finché p1 non segnala.

→ Cap. 5, §5 · Ordinare le azioni: il semaforo evento

Prima i due processi, ciascuno da solo: una catena posto → transizione → posto con un token nel posto iniziale, una transizione per azione (a1, a2 per p1; b1, b2, b3 per p2). Poi la «colla»: il semaforo diventa un posto a1Done senza token, che è il suo valore iniziale.

La transizione a1 ha a1Done come secondo posto di uscita (la signal) e b2 lo ha come secondo posto di ingresso (la wait), quindi b2 scatta solo quando p2 ha eseguito b1 e a1 ha messo un token in a1Done. L'errore tipico è collegare il posto dopo a1 sia ad a2 sia a b2: un posto con due transizioni in uscita è una scelta, e l'unico token andrebbe all'una o all'altra.

→ Cap. 9, §4 · Sincronizzazione, mutua esclusione, semafori → Cap. 5, §5 · Ordinare le azioni: il semaforo evento

Un semaforo binario inizializzato a 1 usato come lock: wait(S) prima della sezione critica e signal(S) dopo, con lo stesso codice per qualsiasi numero di processi, che garantisce mutua esclusione e assenza di deadlock.

Il problema da evitare è la starvation: con un semaforo debole la signal può svegliare sempre gli stessi processi, e uno di loro non entra mai. Serve quindi un semaforo forte, con coda FIFO (in Java new Semaphore(1, true)).

→ Cap. 5, §4 · La sezione critica con un semaforo

I produttori creano dati e li inviano, i consumatori li ricevono e li elaborano: è un problema d'ordine di esecuzione. Nell'approccio sincrono non c'è buffer e i due si incontrano, e chi arriva prima aspetta; in quello asincrono un buffer condiviso li disaccoppia e assorbe le differenze di velocità.

I problemi sono di sincronizzazione, non di velocità da correggere con lo scheduling: il consumatore non deve prelevare da un buffer vuoto, il produttore non deve inserire in un buffer pieno, e con più processi le operazioni sul buffer sono sezioni critiche. Si risolvono con i semafori divisi availItems (0) e availPlaces (N) più un mutex, preso dopo la wait di sincronizzazione per non andare in deadlock, oppure con un monitor o una ArrayBlockingQueue.

→ Cap. 5, §6 · Produttori e consumatori

Una situazione in cui due o più processi aspettano ciascuno un evento (il rilascio di una risorsa, un segnale, un messaggio) che solo un altro del gruppo potrebbe produrre: un'attesa circolare da cui nessuno esce. Il caso tipico è l'abbraccio mortale: A tiene il lock L e chiede M, B tiene M e chiede L.

Può verificarsi solo se valgono insieme le quattro condizioni di Coffman (mutua esclusione, possesso e attesa, nessuna prelazione, attesa circolare), quindi per prevenirlo basta romperne una, di solito acquisendo i lock sempre nello stesso ordine.

→ Cap. 6, §1 · Deadlock, starvation, livelock → Cap. 6, §3 · Quando può esserci un deadlock: le condizioni di Coffman

Perché waitC deve rilasciare il lock del monitor nello stesso passo atomico in cui sospende il processo. Se non lo rilasciasse, chi aspetta terrebbe il monitor occupato e nessuno potrebbe entrare a rendere vera la condizione: deadlock. Se lo rilasciasse in un passo separato, una signalC arrivata nell'intervallo troverebbe la coda vuota e andrebbe persa.

Per questo in Java una Condition si ottiene dal proprio lock con lock.newCondition(), e wait() si chiama solo tenendo il lock dell'oggetto.

→ Cap. 7, §2 · Aspettare una condizione: le variabili condizione

No. Se la lettura fosse una procedura del monitor, la mutua esclusione implicita impedirebbe a due lettori di leggere insieme, e il monitor resterebbe occupato per tutta la durata di letture e scritture: si tornerebbe alla soluzione sovravincolata.

Il monitor offre invece operazioni che aprono e chiudono l'accesso (request_read/release_read, request_write/release_write): gestisce solo i permessi, contati da nr e nw, come un allocatore di risorse. La lettura e la scrittura vere avvengono fuori, tra le due chiamate.

→ Cap. 7, §4 · Buffer e lettori-scrittori come monitor

È la regola per i task CPU-bound: N_cpu processori raggiungono di solito l'utilizzo ottimo con N_cpu + 1 thread. Il thread in più serve perché anche un thread di solo calcolo ogni tanto si ferma, per esempio per un page fault, quando la pagina che gli serve non è in memoria e il sistema operativo lo sospende per caricarla: in quel momento il thread in più tiene occupato il core.

Più thread di così aggiungono solo costi di cambio di contesto. Con 16 core, 17 thread; il numero si ricava a run time con Runtime.getRuntime().availableProcessors(), non si scrive nel codice.

→ Cap. 10, §8 · Quanti thread: prestazioni e dimensionamento del pool

Sì. Se i task si bloccano sull'I/O, in ogni istante una parte dei thread non può usare la CPU, quindi servono più thread dei core per tenerli occupati. La formula è N_threads = N_cpu · U_cpu · (1 + W/C), con U_cpu l'utilizzo di CPU voluto e W/C il rapporto tra tempo di attesa e tempo di calcolo di un task: con 8 core, U_cpu = 1 e W/C = 3 servono 32 thread.

Con W/C = 0 la formula torna a N_cpu, e il «+1» è il margine empirico del caso CPU-bound. In pratica il valore si conferma misurando l'utilizzo della CPU con pool di dimensioni diverse.

→ Cap. 10, §8 · Quanti thread: prestazioni e dimensionamento del pool

Perché execute e submit non aspettano il task: lo consegnano all'executor e ritornano subito. Il task viene eseguito più tardi, da un thread del pool, in modo asincrono rispetto a chi l'ha sottomesso, che raccoglie il risultato dopo tramite la Future restituita da submit. Le chiamate asincrone si riconoscono proprio da questo: restituiscono una Future, o nulla.

→ Cap. 10, §5 · Perché ragionare per task: executor e thread pool

Quattro «a», in un ordine qualsiasi, e poi nulla. I 4 thread prendono i primi 4 task, stampano a e si sospendono sulla barriera, che aspetta 100 arrivi; gli altri 96 task restano in coda senza un thread libero: nessuna b, nessuna eccezione, e il programma non termina. Un task che aspetta sospende il thread del pool che lo esegue: nell'Executor framework i task devono essere indipendenti.

Un pool di 100 thread lo «risolve», ma è barare: il numero di thread torna a dipendere dal problema. La correzione è togliere l'attesa dai task e lasciarla al master:

List<Future<?>> phaseA = new ArrayList<>();
for (int i = 0; i < 100; i++) { int id = i; phaseA.add(exec.submit(() -> System.out.println("a" + id))); }
for (Future<?> f : phaseA) f.get();      // l'attesa è nel master, fuori dal pool
for (int i = 0; i < 100; i++) { int id = i; exec.execute(() -> System.out.println("b" + id)); }

→ Cap. 10, §7 · Perché un task non deve aspettare un altro task

Java PathFinder è il model checker per Java nato alla NASA: una Java Virtual Machine scritta in Java che esegue il bytecode lungo tutti gli interleaving possibili, memorizzando gli stati, tornando indietro (backtracking) e riconoscendo quelli già visti. Non serve scrivere un modello a parte.

Di base cerca deadlock ed eccezioni non catturate, compresi gli assert falliti; con il listener PreciseRaceDetector trova anche le race condition. Non accetta formule LTL: le proprietà specifiche si scrivono con assert. Su un programma vero si verifica un modello ridotto (monitor e 2–3 thread, niente GUI né I/O), e «no errors detected» conta solo se la ricerca è stata completa.

→ Cap. 11, §4 · Java PathFinder

È una domanda sul proprio codice, e si risponde con l'architettura consegnata. Da preparare: quali sono i componenti attivi e quelli passivi, le fasi del lavoro e quali sono parallele, le due versioni richieste (platform thread con monitor scritti da voi, e task sull'Executor Framework) e perché differiscono, come le fasi si sincronizzano.

La scheda di preparazione ricostruisce tutto questo per il Poool: il frame come pipeline di sei passi, i monitor Buffer, Barrier e RenderSynch nella v1, invokeAll al posto del Barrier nella v2.

→ Assignment 1, §1 · Cosa ho costruito → Assignment 1, §2 · Scelte concorrenti

La regola generale è N_cpu + 1 per i task CPU-bound e N_threads = N_cpu · U_cpu · (1 + W/C) quando i task aspettano. Il Poool è CPU-bound (W/C ≈ 0), quindi circa un thread per core, N_cpu + 1.

Il valore va confermato misurando: variando i thread lo speedup cresce fino al numero di core e poi si ferma, con il tetto fissato dalla parte seriale (Amdahl). All'orale portate i numeri del vostro benchmark e il valore scelto.

→ Cap. 10, §8 · Quanti thread: prestazioni e dimensionamento del pool → Assignment 1, §3 · Domande probabili

Si risponde nominando i propri componenti. Il principio: gli agenti (thread) non si chiamano tra loro, interagiscono solo attraverso componenti passivi, i monitor. Per un lavoro a fasi lo schema tipico è un master-workers ripetuto: il master distribuisce il lavoro di una fase, aspetta che tutti abbiano finito (barriera, latch, Future) e solo dopo passa alla fase successiva.

Nella scheda del Poool il main loop distribuisce il lavoro con un Buffer per worker e attende il rendezvous su un Barrier (v1), oppure consegna i task con invokeAll (v2).

→ Cap. 8, §2 · Componenti attivi e passivi → Cap. 8, §6 · Come si capisce che il lavoro è finito → Assignment 1, §3 · Domande probabili

Dipende dal proprio codice, ma la scelta va motivata. Un buffer limitato blocca il produttore quando è pieno e frena chi produce più di quanto si smaltisce; uno illimitato non lo blocca mai, ma può crescere senza limite.

Nella scheda del Poool il Buffer dell'input è unbounded: i produttori (tastiera e bot) sono lenti, il game loop svuota tutto con poll() a ogni frame, e un buffer limitato bloccherebbe la EDT congelando l'interfaccia.

→ Assignment 1, §3 · Domande probabili → Cap. 5, §6 · Produttori e consumatori

Si descrivono le proprie. Il caso tipico è un model checking con JPF di un modello ridotto: i monitor con 2–3 thread, senza GUI né I/O, le proprietà scritte come assert e il deadlock controllato da JPF, più una versione volutamente sbagliata per mostrare che la verifica trova davvero l'errore.

Vanno aggiunti i test sul risultato, sapendo che cosa un test non può dimostrare. La scheda del Poool descrive StrategyEquivalence (stesso risultato della versione sequenziale) e la verifica JPF del Barrier.

→ Cap. 11, §4 · Java PathFinder → Assignment 1, §3 · Domande probabili

Vanno classificate una per una con un criterio: se una violazione si mostra con un'esecuzione finita (uno stato cattivo raggiungibile) è safety; se serve un'esecuzione infinita in cui la cosa buona non arriva mai è liveness.

Mutua esclusione, limiti del buffer, rete limitata, invarianti di posto e «nessuna marcatura morta raggiungibile» sono safety; «chi chiede la sezione critica prima o poi entra», «il programma termina», «ogni elemento prodotto viene consumato» sono liveness. Attenzione ad «assenza di deadlock», che può indicare l'una o l'altra: dite quale intendete.

→ Cap. 11, §2 · Safety o liveness: che cosa si verifica e come → Assignment 1, §3 · Domande probabili

Dipende da come nascono i task. Se il loro numero è noto quando li si sottomette si contano i completamenti: un monitor che attende N risultati, un latch inizializzato a N, le Future (get su ciascuna o invokeAll), oppure shutdown più awaitTermination. Se i task ne generano altri un bag vuoto non basta: serve un contatore dei task pendenti, e il lavoro è finito quando arriva a zero.

Nella scheda del Poool il numero di task di una fase è noto: il Barrier conta i report dei worker (v1), invokeAll ritorna quando tutte le Future sono complete (v2).

→ Cap. 8, §6 · Come si capisce che il lavoro è finito → Assignment 1, §3 · Domande probabili

Si racconta il proprio setup. JPF esplora tutti gli interleaving, quindi si verifica un modello ridotto: i monitor e i thread che li usano, 2–3 thread e pochi cicli, file e GUI sostituiti da dati in memoria, le proprietà come assert e il deadlock lasciato al controllo di JPF.

Conviene verificare anche una versione volutamente rotta, per mostrare che la verifica trova l'errore, e leggere «no errors detected» insieme alle statistiche. Nella scheda del Poool: TestBarrier con 2 parti e 2 round, e UnsafeBarrier, a cui manca un synchronized.

→ Cap. 11, §4 · Java PathFinder → Assignment 1, §3 · Domande probabili

x = 0                          // L1
asynctask(x, (res) => {
  x = x + res                  // L2
});
x = x + 1                      // L3

Sì: L1, L3, L2, sempre. L1, la chiamata ad asynctask e L3 appartengono allo stesso handler, che l'event loop esegue per intero; asynctask affida il lavoro a un thread in background e registra L2 come handler del completamento, eseguito in un ciclo successivo del loop. L2 potrebbe anche non essere mai eseguita, se il task fallisce o non termina.

→ Cap. 12, §3 · Callback e continuation-passing style

Perché non c'è preemption: il worker che ha finito può solo accodare l'evento di completamento, e l'event loop guarda la coda solo quando l'handler corrente è terminato. La callback la esegue l'event loop, non il worker: per questo non ci sono race su x, che viene scritta sempre dallo stesso thread.

→ Cap. 12, §3 · Callback e continuation-passing style

x = 0;                                   // L1
const p = asyncTask(x);                  // restituisce subito una promise pending
p.then((res) => { x = x + res; });       // L2: registrata, non eseguita
x = x + 1;                               // L3

asyncTask non riceve più la callback: restituisce subito una promise, e then registra la reazione, che l'event loop eseguirà dopo il codice corrente. L'ordine resta L1, L3, L2: cambia la forma del codice, non il motore.

→ Cap. 12, §5 · Promise

async function f() {
  const res = await asyncTask(x);
  x = x + res;               // L2
}
x = 0;                       // L1
f();
x = x + 1;                   // L3

f() parte subito, chiama asyncTask(x) con x = 0 e si sospende all'await, restituendo il controllo al chiamante, che esegue L3. L2 arriva quando la promise si risolve: l'ordine resta L1, L3, L2. await sospende la funzione, non il thread.

→ Cap. 12, §7 · async/await

x = 0
asynctask1(x, (res1) => {
  asynctask2(x + res1, (res2) => {
    console.log(res2);
  });
});
x = x + 1

Con le promise:

x = 0;
asyncTask1(x)
  .then((res1) => asyncTask2(x + res1))   // restituire la promise appiattisce
  .then((res2) => console.log(res2));
x = x + 1;

Il segreto è che then restituisce una nuova promise che segue l'esito del valore restituito dalla callback: la prima callback restituisce la promise di asyncTask2, il secondo then si aggancia a quella e l'annidamento sparisce. Nota che x + res1 si valuta quando la callback viene eseguita, cioè dopo x = x + 1: in entrambe le versioni lì x vale già 1.

→ Cap. 12, §5 · Promise

async function run() {
  const res1 = await asyncTask1(x);
  const res2 = await asyncTask2(x + res1);
  console.log(res2);
}
x = 0;
run();
x = x + 1;

run() parte subito e si sospende al primo await; il chiamante esegue x = x + 1. Quando le promise si risolvono l'event loop riprende run, e x + res1 si valuta con x già a 1. È cambiata la forma del codice, non il motore.

→ Cap. 12, §7 · async/await

Continuation-passing style (Sussman e Steele, 1975): invece di restituire un valore, la funzione riceve come argomento in più una continuazione, il resto del calcolo, e la chiama con il risultato. In stile diretto int sum(a, b) restituisce a + b; in CPS void sum(a, b, k) chiama k(a + b), e il chiamante passa ciò che vuole fare dopo.

Poiché non si torna mai indietro lo stack non serve: il CPS è programmazione stackless. Nella programmazione asincrona la continuazione è la callback, e non la esegue il thread che ha svolto il lavoro: la esegue l'event loop quando arriva l'evento di completamento.

→ Cap. 12, §3 · Callback e continuation-passing style

Dopo x = 1; y = x + 1; x = 2, in un linguaggio imperativo y vale 2: l'assegnamento dà un nome al valore di x + 1 in quel momento, e i cambiamenti successivi di x non lo toccano. In un linguaggio reattivo y vale 3: l'assegnamento dichiara una relazione, come l'uguale della matematica, e y deve valere x + 1 in ogni istante.

La variabile reattiva è quindi un valore che varia nel tempo, un flusso: il sistema mantiene il grafo delle dipendenze e ricalcola y a ogni cambiamento di x.

→ Cap. 13, §1 · Dall'assegnamento alla relazione

È una domanda sul proprio codice: si indicano classi e operatori della versione Rx. Da preparare: come i file diventano un flusso (una sorgente cold, flatMap per la ricorsione sulle sottodirectory, operatori di aggregazione per il conteggio e le bande), dove stanno subscribeOn e observeOn, se serve la backpressure (Flowable e quale strategia) e come funzionano stop e aggiornamenti live (dispose, scan).

La scheda avverte che nel repository del corso la soluzione non c'è: rileggete la vostra prima dell'orale.

→ Assignment 2, §2 · Scelte concorrenti → Assignment 2, §3 · Domande probabili → Cap. 13, §7 · Su quali thread: gli scheduler

Si descrive la versione a event loop consegnata, con i punti che la scheda elenca: getFSReport restituisce subito una Future/Promise; nessuna chiamata bloccante sull'event loop (API asincrona del file system, oppure executeBlocking); come si capisce che la scansione ricorsiva è finita (Future dei figli composte ricorsivamente, o un contatore di operazioni pendenti gestito dal solo event loop).

Va detto anche perché le statistiche non richiedono lock: tutte le callback girano sull'unico thread dell'event loop.

→ Assignment 2, §2 · Scelte concorrenti → Assignment 2, §3 · Domande probabili → Cap. 12, §9 · L'event loop in Java: Vert.x

Va indicato nel proprio codice: dove un metodo asincrono crea una Promise, restituisce subito la sua future() e la completa (complete o fail) a lavoro finito; dove le operazioni si concatenano con compose invece di annidare callback; dove Future.all aspetta i risultati delle sottodirectory.

Bisogna saper spiegare che la catena resta piatta solo se la lambda di compose restituisce la nuova future: fare la chiamata dentro onSuccess riporta la piramide.

→ Cap. 12, §9 · L'event loop in Java: Vert.x → Assignment 2, §3 · Domande probabili

Nel sincrono il canale non ha buffer: la send si blocca finché il messaggio non è ricevuto e la receive finché qualcuno non invia, quindi il trasferimento è un punto d'incontro, un'azione atomica comune ai due processi. Nell'asincrono il canale ha una coda FIFO: la send ha successo appena il messaggio è accodato e si blocca solo la receive, a coda vuota.

Il sincrono dà una sincronizzazione gratuita ma porta facilmente al deadlock; l'asincrono disaccoppia ed è la scelta di quasi tutti i sistemi moderni. La send sincrona aspetta la ricezione, non una risposta: quella è il rendez-vous.

→ Cap. 14, §2 · Sincrono o asincrono?

Go: i canali creati senza buffer (make(chan T)) sono sincroni, e send e receive si aspettano a vicenda; con make(chan T, k) il canale ha invece un buffer di capacità k. Altri esempi sono Occam, derivato dal CSP di Hoare, e Ada con il rendez-vous.

→ Cap. 14, §2 · Sincrono o asincrono? → Cap. 14, §8 · Go: goroutine, canali e select

Un modello di concorrenza in cui tutto è un attore: un'entità con un indirizzo, una mailbox, uno stato privato e un comportamento, che non condivide memoria e interagisce solo con messaggi asincroni. Un attore agisce solo quando riceve un messaggio, e lo elabora per intero prima del successivo (macro-step): sul suo stato non ci sono race né lock, ma un handler non deve mai bloccarsi.

Il modello è di Hewitt (1973), formulato da Agha (1986); nel corso si usa Apache Pekko, e ne sono esempi anche Erlang e ActorFoundry.

→ Cap. 15, §1 · Che cos'è un attore

Tre: send, l'invio asincrono di un messaggio, dopo il quale il mittente prosegue subito; create, che crea un nuovo attore con un comportamento iniziale; become, che fissa comportamento e stato per il prossimo messaggio.

In Pekko typed sono tell, ctx.spawn e il Behavior restituito dall'handler; in Erlang !, spawn e la chiamata ricorsiva con il nuovo stato.

→ Cap. 15, §1 · Che cos'è un attore

Si risponde sul proprio codice: l'elenco degli attori e dei loro ruoli (tastierino, sensori, centralina, sirena), il protocollo dei messaggi come interfaccia sigillata di record immutabili, un Behavior per ciascuno dei cinque stati dell'allarme, i timer per exit ed entry delay (da cancellare se il PIN arriva prima), lo stash o lo scarto per i messaggi fuori stato.

La scheda propone una topologia a stella con la centralina al centro, e avverte che nel repository il codice consegnato non c'è: va recuperato e riletto.

→ Assignment 3, §2 · Scelte concorrenti → Assignment 3, §3 · Domande probabili → Cap. 16, §1 · Timer: un attore che agisce da solo

Due esercizi con due modelli di message passing: il sistema d'allarme ad attori in Pekko (asincrono: tell su mailbox, un messaggio alla volta) e il torneo pari-e-dispari in Go con goroutine e canali (sincrono sui canali senza buffer, solo message passing, nessuna memoria condivisa).

Per il secondo la scheda propone una goroutine per giocatore, un arbitro per partita che riceve le due mosse, i canali dei vincitori come ingressi del round successivo e la terminazione senza busy-wait. La risposta va data sulla propria soluzione.

→ Assignment 3, §1 · Cosa ho costruito → Assignment 3, §2 · Scelte concorrenti

La relazione happened-before di Lamport, e1 → e2, la più piccola che soddisfa tre regole: e1 ed e2 sono nello stesso processo ed e1 viene prima; e1 è l'invio di un messaggio ed e2 la ricezione di quello stesso messaggio; esiste un evento g con e1 → g e g → e2 (transitività). Se non vale né e1 → e2 né e2 → e1, gli eventi sono concorrenti.

È un ordine parziale, non un tempo fisico. Non va confusa con la sua implementazione: gli orologi logici e vettoriali sono i meccanismi che la realizzano.

→ Cap. 17, §5 · Happened-before: l'ordine che si può ricostruire

Con l'algoritmo di Ricart–Agrawala. Chi vuole entrare invia a tutti gli altri una richiesta marcata (timestamp logico, id) ed entra dopo aver ricevuto N − 1 OK. Chi riceve una richiesta risponde subito OK, a meno che sia in sezione critica o stia a sua volta chiedendo con una coppia minore: in quei casi accoda il richiedente e gli manda l'OK all'uscita.

Costa 2(N − 1) messaggi per ingresso e non richiede canali FIFO, ma ogni processo deve conoscere tutti gli altri e il guasto di uno blocca chi aspetta il suo OK. L'alternativa è l'algoritmo con un coordinatore che custodisce un token (n. 200).

→ Cap. 18, §3 · Ricart–Agrawala: mutua esclusione senza coordinatore

Si descrive il proprio tris. Lo schema che la scheda propone: una lobby remota pubblicata sul registry per creare una partita o unirsi a una esistente per nome; un oggetto remoto partita progettato come monitor, perché il runtime RMI esegue le chiamate su più thread; listener remoti per notificare le mosse senza polling; RemoteException gestita come parte del contratto.

Il confronto: con gli attori il flusso di controllo sta nell'attore, l'interazione è asincrona e la mailbox serializza i messaggi, quindi niente lock; con RMI si torna a oggetti passivi e chiamate sincrone, lo stato va protetto e le notifiche vanno costruite con callback remote. Il «come vi siete trovati» è personale: va detto con esempi dal proprio codice.

→ Assignment 4, §2 · Scelte concorrenti → Assignment 4, §3 · Domande probabili → Cap. 19, §3 · Java RMI

Passivi: gli oggetti remoti, cioè lobby e partita sul server e i listener sul client. Non hanno un flusso di controllo proprio: i loro metodi li eseguono i thread del runtime RMI. Attivi: i client (il thread della UI o del main, che invoca e resta bloccato fino alla risposta) e, sul server, i thread del runtime RMI.

Le conseguenze da dire: l'oggetto partita è condiviso tra più thread e va fatto monitor; la callback verso il client gira su un thread RMI del client, quindi l'aggiornamento della GUI passa alla EDT con SwingUtilities.invokeLater. La risposta finale va data sulle classi della propria soluzione.

→ Assignment 4, §3 · Domande probabili → Cap. 19, §3 · Java RMI

In un sistema concorrente più attività si sovrappongono nel tempo (una inizia prima che l'altra sia finita) e interagiscono, perché hanno dipendenze. Un programma concorrente è un insieme finito di programmi sequenziali, i processi, eseguiti sovrapposti nel tempo, anche su una sola CPU.

→ Cap. 1, §2 · Che cos'è la concorrenza

Lo stesso programma, con lo stesso input, può produrre esecuzioni e risultati diversi. Nasce dall'indipendenza dalla velocità: non si può fare alcuna ipotesi sulla velocità relativa dei processi, quindi l'ordine in cui le loro azioni si intrecciano cambia da un'esecuzione all'altra.

→ Cap. 1, §2 · Che cos'è la concorrenza

Organizzare un programma come più processi sequenziali che si sovrappongono nel tempo e interagiscono: è un livello logico, un modo di strutturare il software, che esiste anche con una sola CPU. Il linguaggio deve permettere di creare i processi e di farli interagire (sincronizzazione, comunicazione, mutua esclusione).

→ Cap. 1, §3 · Concorrente, parallelo, distribuito → Cap. 1, §8 · Macchine e linguaggi concorrenti

La concorrenza è un modo di strutturare il programma come attività sovrapposte che interagiscono (livello logico); il parallelismo è l'esecuzione simultanea su processori fisici distinti, con l'obiettivo delle prestazioni. Ogni programma parallelo è concorrente, non il contrario: con una CPU i processi sono concorrenti ma non paralleli.

→ Cap. 1, §3 · Concorrente, parallelo, distribuito

In un multi-core ci sono più core general purpose sullo stesso chip, che condividono la RAM e a volte la cache, al più di velocità diverse (P-core ed E-core). In un'architettura eterogenea il processore è affiancato da unità di natura diversa (GPU, NPU, FPGA): una GPU, per esempio, applica lo stesso flusso di istruzioni a molti dati.

→ Cap. 1, §5 · La giungla dell'hardware

Classifica i sistemi per numero di flussi di istruzioni e di flussi di dati: SISD (la macchina di von Neumann), SIMD (la stessa istruzione su più dati: processori vettoriali, GPU), MISD (nessun sistema noto) e MIMD (ogni processore ha istruzioni e dati propri). I programmi del corso sono MIMD.

→ Cap. 1, §6 · La tassonomia di Flynn e la memoria

Tutti i processori vedono un unico spazio di indirizzi e comunicano leggendo e scrivendo variabili condivise. Si distingue in SMP, dove tutti accedono alla memoria con la stessa velocità, e NUMA, dove alcuni blocchi sono fisicamente più vicini ad alcuni processori.

→ Cap. 1, §6 · La tassonomia di Flynn e la memoria

Ogni processore ha il proprio spazio di indirizzi e comunica con gli altri solo inviando e ricevendo messaggi. Ne fanno parte MPP, cluster e grid.

→ Cap. 1, §6 · La tassonomia di Flynn e la memoria

La quantità di lavoro completata nell'unità di tempo, per esempio i task completati al secondo. Aumentarlo sfruttando tutti i core è una delle motivazioni della concorrenza, insieme a reattività e scalabilità.

→ Cap. 1, §4 · Perché programmare in modo concorrente → Cap. 10, §8 · Quanti thread: prestazioni e dimensionamento del pool

È il rapporto S = T1/TN tra il tempo sequenziale e quello con N processori; il valore ideale è N (speedup lineare), e oltre si va solo in casi particolari, per effetto delle cache. Il limite che la parte sequenziale impone allo speedup lo dà la legge di Amdahl (n. 11).

→ Cap. 1, §7 · Misurare le prestazioni: speedup, Amdahl, efficienza

È E = S/N, lo speedup diviso per il numero di processori, e dice quanto bene è stato usato ciascuno. Il valore ideale è 1: uno speedup di 8 su 64 core dà E = 0,125.

→ Cap. 1, §7 · Misurare le prestazioni: speedup, Amdahl, efficienza

Perché i core raggiungono la RAM attraverso un bus su cui passa un'operazione di memoria alla volta, anche quando i thread accedono a indirizzi diversi e non hanno nulla da sincronizzare. Si attenua con le cache (un core che lavora sui dati in cache non usa il bus), con i protocolli di coerenza e con le architetture NUMA.

→ Cap. 1, §7 · Misurare le prestazioni: speedup, Amdahl, efficienza

Perché le prestazioni dipendono da quanto si usano i core: un core fermo mentre c'è lavoro è capacità sprecata. Un thread bloccato sull'I/O libera il suo core, che lavora solo se c'è un altro thread pronto, e per questo i compiti I/O-bound vogliono più thread dei core.

→ Cap. 1, §7 · Misurare le prestazioni: speedup, Amdahl, efficienza

L'esecuzione di un programma sequenziale: un singolo flusso di controllo logico, l'unità di base di un sistema concorrente. Non coincide con il processo del sistema operativo: thread Java, goroutine e attori sono processi in questo senso.

→ Cap. 2, §1 · Processi e interazione

I processi interagiscono quando tra loro c'è una dipendenza: la cooperazione è attesa e voluta (comunicazione e sincronizzazione, come produttori e consumatori con un buffer), la competizione è necessaria ma non voluta (mutua esclusione e sezioni critiche, come più chioschi di check-in sullo stesso database). La terza forma, l'interferenza, non è né attesa né voluta (n. 24).

→ Cap. 2, §1 · Processi e interazione

fork P avvia P in parallelo al chiamante e join P ne attende la fine: è flessibile ma non strutturato, come un goto, e in Java corrisponde a t.start() e t.join(). La fork() di Unix, che duplica un processo del sistema operativo, ne è un caso particolare; il pattern architetturale fork-join, un master-workers ricorsivo, è nel capitolo 8.

→ Cap. 2, §2 · Come si esprime la concorrenza in un linguaggio → Cap. 8, §5 · Le architetture concorrenti

cobegin S1 ‖ S2 ‖ S3 coend (il parbegin/parend di Dijkstra) esegue le istruzioni in parallelo e prosegue quando sono finite tutte. È strutturato, ma il numero di processi è fissato nel testo del programma.

→ Cap. 2, §2 · Come si esprime la concorrenza in un linguaggio

Il linguaggio deve permettere di creare processi e di farli interagire, con tre approcci: linguaggio sequenziale più libreria (C con i Pthreads), linguaggio progettato per la concorrenza con il processo come costrutto di prima classe (Occam, Ada, Erlang, Go), oppure ibrido (Java e Scala: thread di libreria, ma synchronized e un lock in ogni oggetto nel linguaggio).

→ Cap. 2, §2 · Come si esprime la concorrenza in un linguaggio

L'esecuzione atomica di un'istruzione: nel modello a interleaving ogni processo è una sequenza di azioni atomiche, e gli altri ne vedono lo stato di prima o di dopo, mai uno intermedio. Che cosa sia atomico è una scelta di modellazione, che la macchina concorrente deve garantire.

→ Cap. 2, §5 · Il modello a interleaving → Cap. 2, §8 · L'importanza di essere atomici

Una relazione temporale imposta tra azioni di processi diversi: che avvengano insieme o, soprattutto, che una avvenga prima di un'altra (precedenza). Non richiede dati condivisi, e non va confusa con la mutua esclusione (n. 22).

→ Cap. 2, §3 · Sincronizzazione non è mutua esclusione

È la race condition: più processi accedono e aggiornano risorse condivise e il risultato dipende dall'ordine degli accessi. Si elimina rendendo atomica la sequenza «controlla e agisci» o leggi-modifica-scrivi, con la mutua esclusione (lock, semafori, monitor) o con un'istruzione atomica della macchina.

→ Cap. 2, §4 · Race condition e situazioni critiche

La mutua esclusione è la proprietà (al più un processo alla volta accede ai dati condivisi); la sezione critica è il tratto di codice che accede agli oggetti condivisi e deve essere eseguito in mutua esclusione. Il problema della sezione critica chiede i protocolli d'ingresso e d'uscita che la racchiudono.

→ Cap. 2, §3 · Sincronizzazione non è mutua esclusione

Un bug che cambia o sparisce quando lo si osserva: debugger, breakpoint e stampe alterano i tempi di esecuzione e rendono più o meno probabili certi interleaving. È tipico delle interferenze tra processi.

→ Cap. 2, §4 · Race condition e situazioni critiche

Un'interazione tra processi né prevista né voluta: errori tempo-dipendenti che si manifestano solo per certi rapporti tra le velocità. Il caso tipico è la race condition, come due incrementi concorrenti che ne producono uno solo.

→ Cap. 2, §1 · Processi e interazione

Nulla: «corsa critica» è la traduzione italiana di race condition. È la situazione in cui il risultato dell'accesso concorrente a risorse condivise dipende dall'ordine in cui avvengono gli accessi.

→ Cap. 2, §4 · Race condition e situazioni critiche

Con la memoria condivisa i processi leggono e scrivono le stesse variabili: la comunicazione è implicita, ma servono meccanismi espliciti di mutua esclusione e sincronizzazione. Con lo scambio di messaggi ogni processo ha la propria memoria e interagisce solo con send e receive: non ci sono dati da proteggere, e comunicazione e sincronizzazione coincidono.

→ Cap. 2, §1 · Processi e interazione

Il modello a interleaving con i diagrammi di stato per le esecuzioni, la logica temporale (LTL) per le proprietà e i formalismi visuali, reti di Petri e statechart. Per i sistemi distribuiti si aggiungono happened-before e causalità potenziale (capitolo 17).

→ Cap. 2, §5 · Il modello a interleaving

Un'azione è atomica se viene eseguita fino in fondo senza interleaving: gli altri vedono lo stato di prima o quello di dopo. Decide quali scenari esistono: n := n + 1 atomico dà sempre 2 con due processi, spezzato in lettura e scrittura può dare 1 (lost update).

→ Cap. 2, §8 · L'importanza di essere atomici

Sì: un oggetto dati è atomico se le sue operazioni passano da uno stato all'altro atomicamente, e i tipi composti in generale non lo sono, perché attraversano stati interni inconsistenti. In Java letture e scritture di boolean, byte, char, short, int, float e dei riferimenti sono atomiche; per long e double (64 bit) la specifica non lo garantisce, a meno che siano volatile.

→ Cap. 2, §8 · L'importanza di essere atomici → Cap. 2, §9 · Strutture dati non atomiche

Il modello in cui l'esecuzione concorrente è una sequenza che intercala in modo arbitrario le azioni atomiche di tutti i processi, rispettando l'ordine interno di ciascuno, come se le eseguisse un unico processore astratto. Non significa esecuzione simultanea su processori diversi.

→ Cap. 2, §5 · Il modello a interleaving

Che, per l'indipendenza dalla velocità, qualunque intercalamento delle azioni atomiche che rispetti l'ordine di ogni processo è una possibile esecuzione (uno scenario), e il programma deve essere corretto in tutti. Si ignora il tempo: contano solo l'ordine parziale e la scelta di che cosa è atomico.

→ Cap. 2, §5 · Il modello a interleaving

È il grafo degli stati raggiungibili: uno stato è una tupla con l'etichetta della prossima istruzione di ogni processo e il valore di ogni variabile, e una transizione esegue una di quelle istruzioni. Visitandolo si verificano le proprietà: la mutua esclusione è violata se è raggiungibile uno stato che la viola, un deadlock è uno stato senza uscite in cui non tutti hanno finito.

→ Cap. 2, §6 · Stati, transizioni e diagrammi di stato

No: il modello a interleaving non assegna probabilità agli scenari, e basta uno scenario sbagliato perché il programma sia scorretto, perché prima o poi si presenta. Un test può passare mille volte proprio perché nella pratica alcuni scenari sono molto più probabili di altri.

→ Cap. 2, §5 · Il modello a interleaving

La definizione è al n. 33. Se due azioni atomiche avvengono davvero nello stesso istante su due core, il modello le rappresenta come uno dei due ordini possibili, perché per l'atomicità l'effetto è lo stesso e gli accessi alla stessa cella di memoria vengono comunque serializzati dall'hardware: per questo il modello regge anche sui multicore e nei sistemi distribuiti.

→ Cap. 2, §5 · Il modello a interleaving

Un programma concorrente è corretto se le sue proprietà di safety e di liveness valgono in tutti gli scenari possibili, comprese le computazioni infinite. Il testing ne esercita solo alcuni: rivela la presenza di errori, non la loro assenza.

→ Cap. 3, §1 · Perché il testing non basta

«Non succede mai niente di male»: una proprietà vera in ogni stato di ogni computazione, cioè un invariante, come la mutua esclusione. Per falsificarla basta un solo stato raggiungibile che la viola.

→ Cap. 3, §2 · Safety e liveness

«Prima o poi succede qualcosa di buono»: in ogni computazione esiste uno stato in cui la proprietà è vera, come l'assenza di starvation. La falsifica una computazione infinita in cui non diventa mai vera, che nel diagramma di stato è un ciclo.

→ Cap. 3, §2 · Safety e liveness

È la garanzia che un'azione che può essere eseguita prima o poi lo sia, cioè che ogni processo ottenga il suo turno. Sì: è un requisito sulla politica di scheduling, che decide l'interleaving, e lo stesso programma soddisfa o no una liveness a seconda della fairness assunta.

→ Cap. 3, §3 · Fairness

Tre, ciascuno include il precedente: incondizionata (ogni azione incondizionata eleggibile viene prima o poi eseguita), debole (in più, ogni azione condizionata la cui condizione diventa vera e resta vera) e forte (in più, ogni azione condizionata la cui condizione diventa vera infinitamente spesso, anche a intermittenza). Debole e forte differiscono proprio sulle condizioni intermittenti, come await x pari mentre un altro incrementa x.

→ Cap. 3, §3 · Fairness

Il calcolo proposizionale: formule costruite da proposizioni atomiche con ∧, ∨, ¬, → e ↔, vere o false in un singolo stato; nei programmi concorrenti le proposizioni sono variabili booleane o etichette («P è su p4»). Non basta per dire «in ogni stato» o «prima o poi», e per questo servono le logiche temporali.

→ Cap. 3, §4 · La logica temporale lineare

Logiche che aggiungono operatori temporali alla logica proposizionale o dei predicati, per parlare di come evolve il sistema; per i programmi le introdusse Pnueli (1977). Le famiglie sono due: lineare (LTL, il tempo come sequenza di stati) e ramificata (CTL, un albero di futuri).

→ Cap. 3, §4 · La logica temporale lineare

La logica temporale lineare: una formula si valuta su una computazione, e il programma la soddisfa se vale in tutti i suoi scenari. Gli operatori sono □ (always: in ogni stato, per le safety), ◇ (eventually: prima o poi, per le liveness), ○ (next), U (until) e W (weak until, in cui q può non arrivare mai): per esempio □¬(p3 ∧ q3) è la mutua esclusione e □(p2 → ◇p3) l'assenza di starvation.

→ Cap. 3, §4 · La logica temporale lineare → Cap. 3, §5 · Specificare le proprietà in LTL

Un processo che entra in sezione critica al posto di un altro che aspettava; il k-bounded overtaking chiede che, da quando P chiede di entrare, gli altri entrino al più k volte prima di lui, e si esprime con il weak until. Lo limitano protocolli come Peterson (k = 1), il biglietto del fornaio e i semafori forti; un lock con test-and-set non dà alcun limite.

→ Cap. 3, §6 · Overtaking e k-bounded overtaking

Mutua esclusione (mai due processi in CS insieme), assenza di deadlock (se alcuni cercano di entrare, prima o poi uno ci riesce) e assenza di starvation (chi cerca di entrare prima o poi ci riesce). Una versione più forte della terza è l'attesa limitata, il k-bounded overtaking.

→ Cap. 4, §1 · Il problema e le proprietà richieste

È la prima soluzione corretta al problema della sezione critica per due processi con sole letture e scritture atomiche. Ogni processo ha un flag «voglio entrare»: se l'altro non è interessato entra subito, altrimenti la variabile turn assegna il diritto di insistere, e chi non ha il turno abbassa il flag e aspetta.

→ Cap. 4, §3 · Dekker e Peterson

Risolve lo stesso problema con un solo await: ognuno alza il flag, cede il turno all'altro e aspetta finché l'altro non è interessato oppure tocca a lui (await not wantq or turn = 1). Se arrivano insieme perde l'ultimo che ha scritto turn, e nessuno sorpassa l'altro più di una volta (k = 1).

→ Cap. 4, §3 · Dekker e Peterson

Perché dà le stesse garanzie (mutua esclusione, niente deadlock né starvation, con soli load e store atomici) ed è più corto e simmetrico: fonde i due controlli di Dekker in un unico await. È l'algoritmo che il corso riprende in Java, con flag e turn dichiarati volatile.

→ Cap. 4, §3 · Dekker e Peterson

Un'istruzione hardware che in un solo passo atomico legge una variabile e la pone a 1: < r := x; x := 1 >. Con essa la sezione critica per N processi si scrive in tre righe e garantisce mutua esclusione e assenza di deadlock, ma non l'assenza di starvation, e l'attesa è attiva.

→ Cap. 4, §5 · Con l'aiuto dell'hardware: test-and-set e lock

Una soluzione per N processi: chi arriva prende un biglietto numerato e viene servito in ordine di arrivo, e nella versione del corso prendere il biglietto deve essere atomico. Il difetto è l'overflow: i contatori crescono per sempre e con interi finiti prima o poi ripartono da zero.

→ Cap. 4, §4 · N processi: il biglietto del fornaio

Nel modello dei capitoli 3 e 4 sì: await c ritesta di continuo la condizione, ed è la stessa attesa che il semaforo busy-wait fa dentro la wait. Semafori e monitor normali invece sospendono il processo e lo risvegliano con una signal, senza consumare CPU.

→ Cap. 5, §3 · Chi viene svegliato? Semafori forti, deboli e busy-wait

Il merge sort delle slide: due processi ordinano le due metà di un array e fanno ciascuno signal su un proprio semaforo evento, e il processo che fonde aspetta entrambi con due wait prima del merge, invece di fare join sui due processi.

→ Cap. 5, §5 · Ordinare le azioni: il semaforo evento

Un processo aspetta indefinitamente una risorsa che gli viene negata di continuo, mentre gli altri avanzano, senza bisogno di un ciclo di attese (per esempio con un semaforo debole). Il deadlock implica la starvation dei processi coinvolti, non il viceversa.

→ Cap. 6, §1 · Deadlock, starvation, livelock

I processi non sono bloccati, ma cambiano stato di continuo l'uno in risposta all'altro senza progredire, come due persone che in un corridoio si spostano dalla stessa parte all'infinito; è un caso particolare di starvation. Si rompe con un po' di casualità, per esempio un'attesa casuale prima di riprovare.

→ Cap. 6, §1 · Deadlock, starvation, livelock

Cinque filosofi alternano pensare e mangiare attorno a un tavolo con cinque forchette, una tra ogni coppia di vicini, e per mangiare servono le due forchette ai propri lati, prese una alla volta: bisogna garantire mutua esclusione sulle forchette, niente deadlock né starvation ed efficienza senza contesa. Se tutti prendono prima la sinistra si ha un deadlock, che si evita con un ticket per N − 1 filosofi o prendendo le forchette in ordine di indice.

→ Cap. 6, §2 · I filosofi a cena → Cap. 6, §4 · Due soluzioni per i filosofi

Le quattro condizioni di Coffman: mutua esclusione, possesso e attesa (hold and wait), nessuna prelazione e attesa circolare. Sono necessarie, non sufficienti: il deadlock è possibile solo se valgono tutte, quindi per prevenirlo basta romperne una.

→ Cap. 6, §3 · Quando può esserci un deadlock: le condizioni di Coffman

Dare un ordine totale ai lock e acquisirli sempre in quell'ordine. Rende impossibile l'attesa circolare, perché ognuno aspetterebbe un lock di rango maggiore di quello che tiene fino a tornare al primo; è ciò che fa transferMoney prendendo prima il lock del conto con indice minore.

→ Cap. 6, §5 · La regola generale, in Java

In generale sì: i DBMS mantengono il grafo delle attese, vi cercano cicli e abortiscono una transazione vittima, i cui lock vengono rilasciati. La JVM no: non ha rilevamento né recupero automatico, e un deadlock si può solo diagnosticare (thread dump, jstack, ThreadMXBean.findDeadlockedThreads()), quindi in Java va prevenuto.

→ Cap. 6, §6 · Si può rilevare e recuperare un deadlock?

Un'astrazione di dati (Brinch Hansen 1973, Hoare 1974) che incapsula stato, operazioni e politica di sincronizzazione e di mutua esclusione nell'accesso a quei dati. Le procedure si eseguono in mutua esclusione implicita, e per aspettare una condizione sullo stato si usano le variabili condizione.

→ Cap. 7, §1 · Che cos'è un monitor

Hanno la stessa potenza espressiva, ma sono di livello più alto: la mutua esclusione è implicita e non si può dimenticare un rilascio, e la politica di sincronizzazione sta in un solo punto, dentro la risorsa, invece che sparsa nel codice dei processi.

→ Cap. 7, §6 · Monitor e semafori

Dall'esterno sono visibili solo i nomi delle procedure; le istruzioni del monitor non accedono a variabili dichiarate fuori; le variabili permanenti sono inizializzate prima che qualsiasi procedura venga chiamata. A queste si aggiunge la mutua esclusione implicita: al più una procedura attiva alla volta.

→ Cap. 7, §1 · Che cos'è un monitor

Sono le operazioni atomiche di una variabile condizione: waitC sospende il processo nella coda della condizione e rilascia il monitor, signalC risveglia il primo processo in coda e, se la coda è vuota, non fa nulla. In Java sono wait() e notify()/notifyAll() sul lock intrinseco, oppure await() e signal()/signalAll() su una Condition.

→ Cap. 7, §2 · Aspettare una condizione: le variabili condizione → Cap. 7, §5 · Monitor in Java

Può proseguire un solo processo, e lo decide la disciplina di segnalazione: con Signal and Continue (E < W < S) continua chi ha segnalato; con Signal and Wait (E = S < W) esegue subito il risvegliato e il segnalante aspetta alla pari con chi vuole entrare; con Signal and Urgent Wait (E < S < W, quella di Hoare) il segnalante ha la precedenza su chi vuole entrare.

→ Cap. 7, §3 · Chi riparte dopo una signal? Le discipline di segnalazione

Sì: una procedura che chiama un altro monitor tiene il proprio lock per tutta la chiamata, e se un altro thread fa il percorso inverso si ha un deadlock di ordinamento dei lock, come nel pattern Observer. Inoltre, se il monitor interno fa wait, rilascia solo il proprio lock e lascia bloccato quello esterno (nested monitor lockout).

→ Cap. 7, §5 · Monitor in Java

Una variante di Signal and Continue con E = W < S: chi notifica continua e tiene il lock, e il risvegliato compete alla pari con chi vuole entrare, quindi un thread appena arrivato può passargli davanti e cambiare lo stato. notify sveglia un solo thread, scelto arbitrariamente, e per questo le attese si scrivono con while (n. 96).

→ Cap. 7, §5 · Monitor in Java

In due modi da non mescolare: con il lock intrinseco (metodi pubblici synchronized, niente campi pubblici, wait() dentro un while, notifyAll()) oppure con ReentrantLock e una o più Condition (lock/unlock in try-finally, await/signal). Per l'assignment si elencano i propri monitor e il loro ruolo: la scheda del Poool descrive Buffer, Barrier e RenderSynch, costruiti su synchronized, wait e notifyAll.

→ Cap. 7, §5 · Monitor in Java → Assignment 1, §2 · Scelte concorrenti

Una variabile usabile solo dentro il monitor che rappresenta una condizione sullo stato: sospende un processo finché la condizione non diventa vera e lo risveglia quando lo diventa, con una coda FIFO e le operazioni waitC e signalC. Un segnale senza nessuno in attesa va perso, quindi va sempre accompagnata da una condizione esplicita sullo stato.

→ Cap. 7, §2 · Aspettare una condizione: le variabili condizione

Perché Java usa una variante di Signal and Continue: il risvegliato riparte dopo il segnalante e magari dopo thread appena entrati, quando la condizione può essere tornata falsa, e la specifica ammette anche i risvegli spuri. L'if basterebbe solo con la ripresa immediata di Signal and Wait o Signal and Urgent Wait, che Java non offre; il while è corretto con qualsiasi disciplina.

→ Cap. 7, §5 · Monitor in Java → Cap. 7, §3 · Chi riparte dopo una signal? Le discipline di segnalazione

Un gate, o latch, è un componente di coordinazione con due ruoli: chi chiama await aspetta che il cancello si apra, chi passa chiama countDown senza bloccarsi, e dopo N countDown il cancello si apre e resta aperto per sempre. A differenza della barriera, che è simmetrica, il latch aspetta eventi; in Java c'è CountDownLatch.

→ Cap. 7, §7 · Barriere e latch: componenti di coordinazione

Un componente attivo (agente) incapsula un proprio flusso di controllo e si progetta a partire dai suoi compiti: master, worker, produttori, consumatori, attori. Un componente passivo incapsula stato e operazioni con la loro sincronizzazione e agisce solo quando un agente lo chiama: monitor come bounded buffer, bag of tasks, contatori condivisi, latch, barriere.

→ Cap. 8, §2 · Componenti attivi e passivi

È un componente attivo, responsabile di uno o più task di cui incapsula la logica e il controllo: un thread, un event loop o un attore. Non ha metodi pubblici chiamati da altri thread, e interagisce con gli altri agenti solo attraverso componenti passivi.

→ Cap. 8, §2 · Componenti attivi e passivi

Una decomposizione che parte dai task: il problema si scompone in modo naturale in task indipendenti o quasi, e la divisione dei dati segue. Funziona se gestire le dipendenze costa poco rispetto al tempo totale; esempi sono produttori e consumatori o un web server con un task per richiesta.

→ Cap. 8, §3 · L'analisi: decomporre e trovare le dipendenze

Una decomposizione che parte dai dati: si dividono in unità su cui lavorare in modo relativamente indipendente, e i task seguono. Scala bene con il numero di processori, come nel prodotto di matrici con un task per elemento del risultato.

→ Cap. 8, §3 · L'analisi: decomporre e trovare le dipendenze

I vincoli tra task: temporali (un task parte solo dopo che un altro è finito, come il merge dopo gli ordinamenti) o sui dati e sulle risorse (un task usa dati prodotti da un altro, o più task condividono una risorsa). Analizzarle serve a raggruppare e ordinare i task, e dice dove gli agenti dovranno coordinarsi con barriere, latch o monitor.

→ Cap. 8, §3 · L'analisi: decomporre e trovare le dipendenze

Sono le classi di Carriero e Gelernter: result parallelism (si progetta attorno al risultato e se ne calcolano le parti insieme), specialist parallelism (una rete di specialisti, ciascuno con un solo tipo di compito) e agenda parallelism (una lista di attività, con molti generalisti su ogni passo). I confini non sono rigidi, perché un lavoro reale spesso le mescola, ma restano tre modi distinti di pensare il problema.

→ Cap. 8, §4 · Tre modi di pensare il parallelismo

Master-workers (con le varianti dei framework a task e del fork-join), filter-pipeline, shared-space o blackboard, announcer-listeners. In ciascuna gli agenti si coordinano tramite un componente passivo: bag of tasks, pipe, spazio condiviso, servizio di eventi.

→ Cap. 8, §5 · Le architetture concorrenti

Il componente passivo condiviso in cui il master (e nel fork-join anche i worker) inserisce i task e da cui i worker li prelevano, di solito un monitor come un bounded buffer o una blackboard. Disaccoppia il master dai worker, il cui numero dipende dall'hardware e non dai task.

→ Cap. 8, §5 · Le architetture concorrenti

Un'architettura in cui un master scompone il lavoro in sottotask, li mette in una bag of tasks e raccoglie i risultati, mentre i worker prelevano un task, lo eseguono e ne comunicano il risultato. Un executor è un master-workers di cui il programmatore scrive solo il master.

→ Cap. 8, §5 · Le architetture concorrenti

Un modello formale e visuale del flusso di informazione e di controllo, per sistemi di eventi concorrenti con vincoli di precedenza: un grafo bipartito di posti e transizioni con token nei posti. Una transizione è abilitata quando ogni posto di ingresso ha un token, e scattando ne toglie uno da ogni ingresso e ne aggiunge uno a ogni uscita.

→ Cap. 9, §2 · Reti di Petri: posti, transizioni, token

Un posto è un nodo che rappresenta una condizione, lo stato di un processo o una risorsa; un token in un posto dice che la condizione vale, e nel modello dei processi è un flusso di controllo o un permesso. La distribuzione dei token, la marcatura, è lo stato della rete.

→ Cap. 9, §2 · Reti di Petri: posti, transizioni, token → Cap. 9, §3 · Come si modella un sistema di processi

Prende il lock intrinseco di un oggetto all'ingresso di un blocco o di un metodo e lo rilascia all'uscita, anche per eccezione, così al più un thread alla volta esegue codice synchronized sullo stesso oggetto. Il lock è rientrante e dà anche visibilità; indica mutua esclusione, non impone alcun ordine tra i thread.

→ Cap. 10, §2 · Come si protegge lo stato condiviso: synchronized e lock

Ogni lettura di un campo volatile vede l'ultima scrittura, e la scrittura happens-before le letture successive, quindi vieta anche i riordinamenti attorno all'accesso. Dà visibilità e ordinamento, non atomicità: count++ su un volatile perde ancora incrementi, mentre basta per un flag di stop.

→ Cap. 10, §3 · Che cosa garantisce volatile

run contiene il comportamento; start fa nascere un nuovo thread che esegue run e ritorna subito. Chiamare run direttamente è una normale chiamata di metodo, eseguita in sequenza dal thread chiamante, e non crea nessun thread.

→ Cap. 10, §1 · Come si crea e si controlla un thread

Il funzionamento è identico: Runnable o una lambda servono quando la classe deve già estendere un'altra classe. Una classe con un nome è preferibile quando il thread è un concetto del progetto (SortingWorker, MergingWorker), perché rende visibili ruoli e responsabilità che una lambda nasconde.

→ Cap. 10, §1 · Come si crea e si controlla un thread

Sospende il thread chiamante finché quel thread non termina: è la prima forma di sincronizzazione, e l'attesa si interrompe con InterruptedException.

→ Cap. 10, §1 · Come si crea e si controlla un thread

Due thread eseguono un leggi-modifica-scrivi come count++ sulla stessa variabile: leggono entrambi 5, scrivono entrambi 6, e un aggiornamento si perde. Si evita rendendo atomica l'operazione con synchronized, un lock o AtomicInteger.

→ Cap. 10, §2 · Come si protegge lo stato condiviso: synchronized e lock

Una decisione presa su un'osservazione che, al momento dell'azione, può essere già vecchia: «se il file non esiste, crealo», il singleton pigro, if (c.getVal() > 0) c.dec(). Anche se ogni metodo è synchronized la coppia non è atomica, e va resa tale con un blocco sullo stesso lock o con un metodo apposito.

→ Cap. 10, §2 · Come si protegge lo stato condiviso: synchronized e lock

Un lock acquisito per thread e non per invocazione: il thread che lo possiede può riacquisirlo senza bloccarsi, e lo libera dopo un rilascio per ogni acquisizione, così un metodo synchronized può chiamarne un altro sullo stesso oggetto. Non ha a che fare con l'equità, che in ReentrantLock è un'opzione separata del costruttore.

→ Cap. 10, §2 · Come si protegge lo stato condiviso: synchronized e lock

Quando un thread sospeso in un'attesa interrompibile (sleep, wait, join, BlockingQueue.put/take, Future.get, lockInterruptibly, acquire…) riceve interrupt() da un altro thread, o se l'interruzione era già stata chiesta prima dell'attesa; lo stato di interruzione viene azzerato. Non sono interrompibili l'attesa di un blocco synchronized e Lock.lock().

→ Cap. 10, §4 · Come si coordinano i thread: wait/notify e i sincronizzatori

Perché gli eventi li preleva da una coda e li consegna ai listener l'Event Dispatch Thread, l'unico thread che tocca i componenti Swing; il main costruisce la finestra e può anche terminare. L'handler deve quindi ritornare in fretta: un lavoro lungo va a un altro thread, che riconsegna gli aggiornamenti alla GUI con SwingUtilities.invokeLater.

→ Cap. 10, §11 · Chi esegue il codice di una GUI: l'Event Dispatch Thread

actionPerformed(ActionEvent e) di ActionListener, eseguito dall'EDT. Per l'assignment si guarda il proprio codice: nella scheda del Poool l'input da tastiera arriva dalla EDT tramite ViewFrame e passa al game loop attraverso un Buffer.

→ Cap. 10, §11 · Chi esegue il codice di una GUI: l'Event Dispatch Thread → Assignment 1, §1 · Cosa ho costruito

Il framework di java.util.concurrent che separa la sottomissione di un task dalla sua esecuzione: dentro c'è un master-workers con una bag of tasks e un pool di thread. Executor offre execute, ExecutorService aggiunge submit, che restituisce una Future, e il ciclo di vita (shutdown, awaitTermination…).

→ Cap. 10, §5 · Perché ragionare per task: executor e thread pool

Un'unità di lavoro astratta, discreta e indipendente, con un inizio e una fine: non un ciclo infinito e non un thread, che è invece ciò che lo esegue. Separa il livello logico, che viene dal problema, da quello fisico, che dipende dalla macchina.

→ Cap. 10, §5 · Perché ragionare per task: executor e thread pool

Si scrive il task come Callable<V> e lo si sottomette con submit, che restituisce subito una Future<V>; get() blocca finché il risultato è pronto e lo restituisce, o lancia ExecutionException. In alternativa i task depositano i risultati in un monitor che li aggrega.

→ Cap. 10, §6 · Come si ottiene il risultato di un task: Callable e Future

Nel conteggio delle parole con Fork/Join (dove il task di un documento si chiama DocumentSearchTask) non lo crea un master centrale, ma il task della cartella che contiene il documento: il FolderSearchTask fa fork di un task per ogni sottocartella e di uno per ogni documento, poi somma i risultati con join. Espansione e aggregazione sono quindi ricorsive e distribuite.

→ Cap. 10, §10 · Task che generano task: Fork/Join e structured concurrency

Un oggetto restituito subito da submit che rappresenta un risultato non ancora disponibile: permette di controllarne lo stato (isDone), di bloccarsi fino all'arrivo (get, anche con timeout), di cancellare il task e di intercettarne gli errori. È utile perché chi sottomette prosegue e raccoglie i risultati dopo; la Future di Java però è bloccante, a differenza delle promise.

→ Cap. 10, §6 · Come si ottiene il risultato di un task: Callable e Future

Costruire un modello del sistema (con l'interleaving, un sistema di transizioni) ed esplorarne in modo esaustivo tutti gli stati raggiungibili, verificando le proprietà scritte come predicati o in logica temporale; se una è violata si ottiene un controesempio, la traccia che porta all'errore. Il limite è l'esplosione dello spazio degli stati.

→ Cap. 11, §3 · Model checking

Il linguaggio di specifica di Leslie Lamport, basato su matematica discreta semplice (insiemi e predicati) e sulla logica temporale delle azioni: descrive l'insieme dei comportamenti ammessi di un sistema, e il model checker TLC ne verifica le proprietà. Accanto c'è PlusCal, un linguaggio algoritmico che viene tradotto in TLA+.

→ Cap. 11, §5 · SPIN e Promela, TLA+ e PlusCal

Un passo in cui lo stato non cambia: in TLA+ ogni specifica lo ammette per costruzione ([Next]_vars), per confrontare specifiche con livelli di dettaglio diversi. Senza ipotesi di fairness un comportamento può quindi «balbettare» per sempre e smentire le liveness, come la starvation freedom di Peterson.

→ Cap. 11, §5 · SPIN e Promela, TLA+ e PlusCal

Avviare un'operazione senza aspettarne la fine: il chiamante prosegue e il risultato arriva più tardi, come evento gestito da una callback, da una promise o con await. È il modo «a eventi» di fare concorrenza, duale ai thread, in cui un event loop esegue gli handler e le operazioni lente vanno a thread in background.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop → Cap. 12, §2 · La regola del never-blocking

Un programma è una collezione di handler, routine eseguite quando si verifica l'evento a cui sono associate: il flusso di controllo lo decidono gli eventi, non il programmatore. Il modello di esecuzione di riferimento è l'event loop.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop

Un solo flusso di controllo aspetta un evento sulla coda, sceglie l'handler associato e lo esegue fino in fondo, poi torna ad aspettare. Gli eventi che arrivano nel frattempo, dall'ambiente o dai worker in background, restano in coda.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop

Non nello stesso event loop: li esegue un solo thread, uno dopo l'altro, quindi non ci sono race e non servono lock. Un sistema può però avere più event loop, come i verticle di Vert.x, i cui handler girano in parallelo con stato proprio e comunicano generando eventi.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop

È l'event loop come pattern architetturale (Schmidt, POSA 2), che separa il demultiplexing e il dispatching degli eventi dalla logica applicativa: un demultiplexer sincrono attende che un handle (per esempio una socket) sia pronto, e un dispatcher trova l'handler registrato e ne chiama il metodo hook. È l'architettura sotto JavaScript, Node.js, Vert.x e le GUI.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop

Una routine associata a un evento, eseguita dall'event loop quando quell'evento arriva. Può essere registrata anche dinamicamente, come una callback.

→ Cap. 12, §1 · Eventi invece di thread: l'event loop

Viene eseguito fino in fondo senza interruzioni e deve terminare presto; non contiene chiamate bloccanti né attese attive, perché ogni operazione lenta diventa asincrona (never-blocking). Può generare nuovi eventi, che il loop vedrà solo dopo la sua fine, e accede solo allo stato del proprio event loop.

→ Cap. 12, §2 · La regola del never-blocking

Il seguito del calcolo diventa la callback passata come ultimo argomento, asyncTask(p, (r) => { s = r + 1; }): asyncTask ritorna subito, e l'event loop esegue la callback quando r è pronto.

→ Cap. 12, §3 · Callback e continuation-passing style

for (var i = 0; i < 3; i++) {
  setTimeout(() => { console.log(i) }, 0)
}

3, 3, 3. Le tre callback sono task eseguiti dopo la fine del for, e con var esiste un solo binding di i, condiviso dalle tre closure, che a quel punto vale 3.

→ Cap. 12, §6 · Task e microtask

for (let i = 0; i < 3; i++) {
  setTimeout(() => { console.log(i) }, 0)
}

0, 1, 2. Le callback girano comunque dopo il for, ma let crea un binding nuovo a ogni iterazione e ogni closure cattura il proprio, che nessuno modifica più: la differenza la fanno le closure, non l'event loop.

→ Cap. 12, §6 · Task e microtask

Comporre in sequenza operazioni asincrone con le callback significa annidarle: il codice cresce verso destra invece che verso il basso ed è difficile da leggere, riusare ed estendere. Insieme allo spaghetti asincrono forma il callback hell, che promise e async/await appiattiscono.

→ Cap. 12, §4 · Il prezzo delle callback: callback hell

CompletableFuture.supplyAsync(supplier) esegue il Supplier su un thread del ForkJoinPool.commonPool() (o dell'executor passato) e restituisce subito una CompletableFuture a cui attaccare callback, quindi va bene per lanciare calcoli o I/O su un pool di thread. In un framework a eventi non va usata come una promise: le callback non passano dall'event loop ma le esegue il thread che completa lo stadio precedente, e se toccano stato condiviso tornano le race.

→ Cap. 12, §5 · Promise

Una funzione passata a un'operazione asincrona, di solito come ultimo argomento, da eseguire quando il risultato sarà pronto: un handler registrato per l'evento «operazione finita», cioè la continuazione del CPS. Di solito è una closure, quindi vede le variabili del contesto che l'ha creata.

→ Cap. 12, §3 · Callback e continuation-passing style

Una promise rappresenta il risultato non ancora disponibile di un'operazione asincrona e vive nel mondo a eventi: non ha una get bloccante e si configura con then, le cui callback esegue l'event loop, mentre la Future di Java vive nel mondo a thread e ci si blocca con get(). Alcune librerie dividono i due lati: in Vert.x Promise è il lato di chi produce (complete, fail) e Future quello in sola lettura del cliente.

→ Cap. 12, §5 · Promise

Pending alla creazione, fulfilled (o resolved) se l'operazione termina bene, rejected se fallisce. Quando non è più pending si dice settled, e da quel momento stato e valore non cambiano più.

→ Cap. 12, §5 · Promise

I task (I/O, timer, input dell'utente) si servono uno alla volta, ciascuno fino in fondo; i microtask, come le reazioni delle promise, vengono eseguiti tutti appena lo stack si svuota, prima del task successivo. Una catena infinita di microtask blocca quindi l'intera applicazione.

→ Cap. 12, §6 · Task e microtask

Una generalizzazione della subroutine che si può sospendere e riprendere, cedendo il controllo (yield) a un'altra: multitasking cooperativo, con cui si costruiscono task cooperativi, iteratori, event loop e async/await. Molte coroutine possono stare su un solo thread, che ne esegue una alla volta senza context switch del sistema operativo; è un meccanismo di basso livello.

→ Cap. 12, §8 · Coroutine e fibre

Marca una funzione come asincrona: è l'unico posto dove si può usare await, e la funzione restituisce sempre una promise. Chiamarla esegue subito il corpo, nello stesso ciclo, fino al primo await.

→ Cap. 12, §7 · async/await

Si usa dentro una funzione async: await p sospende la funzione (non il thread) e restituisce il controllo al chiamante, e l'event loop la riprende quando p si risolve, con il valore della promise o con un'eccezione se è rigettata. Permette di scrivere codice asincrono in stile sincrono.

→ Cap. 12, §7 · async/await

In Kotlin, una funzione marcata suspend che può sospendersi (per esempio in delay) senza bloccare il thread, che intanto esegue altre coroutine. Si chiama solo da un'altra funzione sospendibile o da un builder come launch, async o runBlocking.

→ Cap. 12, §8 · Coroutine e fibre

Realizza il reactor con più event loop: ogni componente attivo è un verticle con il proprio event loop, l'unico che tocca i suoi campi, e tutte le API sono asincrone e restituiscono una Future di Vert.x, configurata con onSuccess, onFailure e compose. Il codice bloccante va in executeBlocking, e i verticle comunicano solo con l'event bus.

→ Cap. 12, §9 · L'event loop in Java: Vert.x

Un paradigma orientato ai flussi di dati e alla propagazione del cambiamento: si dichiarano le relazioni tra valori che variano nel tempo, e il linguaggio o la libreria aggiorna automaticamente tutto ciò che dipende da un valore quando questo cambia. Il programmatore dice che cosa fare, il sistema decide quando.

→ Cap. 13, §1 · Dall'assegnamento alla relazione

Gli event stream, valori discreti nel tempo come i click del mouse, e i behaviour (o signal), valori continui che hanno un valore in ogni istante, come un timer o una temperatura. Sono valori di prima classe, che si passano ad altre funzioni e si compongono.

→ Cap. 13, §2 · Event stream e behaviour

L'inversione del controllo (il flusso lo decidono eventi in ordine imprevedibile), l'aggiornamento manuale di tutto ciò che dipende da un dato cambiato, la logica frammentata in tanti handler (spaghetti asincrono) e callback che agiscono solo per effetti collaterali; con le callback annidate si aggiunge la pyramid of doom. Promise e async/await ne risolvono una parte, la programmazione reattiva nasce per gli altri.

→ Cap. 13, §1 · Dall'assegnamento alla relazione → Cap. 12, §4 · Il prezzo delle callback: callback hell

In pull chi ha bisogno di un valore lo chiede alla sorgente (demand-driven, naturale nei linguaggi lazy); in push la sorgente, quando ha un dato nuovo, lo spinge a chi ne dipende (data-driven, linguaggi eager). In entrambi i dati vanno dal produttore al consumatore: cambia chi prende l'iniziativa.

→ Cap. 13, §3 · Come si propaga il cambiamento: push, pull, glitch

Un'inconsistenza temporanea della propagazione push: un valore viene ricalcolato prima che siano aggiornate tutte le espressioni da cui dipende, combinando dati nuovi e vecchi, e mostra uno stato mai esistito. Si evita aggiornando i nodi del grafo delle dipendenze in ordine topologico; nei sistemi distribuiti è ancora un problema aperto.

→ Cap. 13, §3 · Come si propaga il cambiamento: push, pull, glitch

La conversione di una variabile o di una funzione normale in una reattiva, che registra la dipendenza nel grafo (come liftB nel timer di Flapjax). Può essere implicito (Bacon.js), esplicito (React.js) o entrambi (Flapjax, esplicito come libreria e implicito come compilatore).

→ Cap. 13, §4 · Lifting e composizione

La componibilità è saper orchestrare più task asincroni usando i risultati dei precedenti come input dei successivi; va di pari passo con la leggibilità, che con molti livelli di callback si perde. Le librerie reattive le ottengono con catene di operatori sui flussi.

→ Cap. 13, §5 · Reactive Extensions: l'Observer fatto bene

Costruire una catena di operatori è solo una configurazione, e nessun dato scorre: la subscribe lega un Publisher a un Subscriber, e la richiesta del Subscriber risale la catena fino alla sorgente e fa partire il flusso. L'eccezione sono i flussi hot, che emettono comunque.

→ Cap. 13, §5 · Reactive Extensions: l'Observer fatto bene

Un controllo di flusso in cui il consumatore dice al produttore quanti elementi è pronto a ricevere (request(n)), trasformando il push in un ibrido push-pull; serve quando uno stadio è più lento del precedente e bloccare non si può. In RxJava c'è solo su Flowable, con strategie di buffer, scarto e campionamento.

→ Cap. 13, §9 · Backpressure

Un flusso cold riparte da capo per ogni subscriber, che riceve tutti gli elementi, ed emette solo se qualcuno è sottoscritto (per esempio range, fromIterable). Un flusso hot emette al proprio ritmo anche senza subscriber, e chi arriva tardi riceve solo gli elementi successivi (sensori, eventi della GUI, dati dalla rete).

→ Cap. 13, §8 · Hot e cold

Nel pattern Observer un subject tiene una lista di osservatori e li notifica con un push quando accade qualcosa. Rx lo estende («l'Observer fatto bene»): un Observable emette una sequenza di valori e ne segnala la fine o l'errore (onNext, onCompleted, onError), le sequenze si compongono con operatori e una sottoscrizione si può annullare.

→ Cap. 13, §5 · Reactive Extensions: l'Observer fatto bene

Un modello in cui i processi non condividono memoria e interagiscono solo inviandosi messaggi su canali: si trasferiscono dati, mai il flusso di controllo. È il modello naturale del distribuito, usato sempre più anche su una sola macchina (Go, attori, Web Worker).

→ Cap. 14, §1 · Che cos'è il message passing

send ch(espressioni) e receive ch(variabili) su un canale con un nome e un tipo di messaggio; l'accesso al canale è atomico, e i messaggi viaggiano per copia. Un canale con buffer è di fatto il bounded buffer del produttore-consumatore.

→ Cap. 14, §1 · Che cos'è il message passing

Le slide ne elencano tre: one-to-one (un canale per coppia, tipico del sincrono), many-to-one (un ricevente e molti mittenti: porte e client-server) e many-to-many (competizione in ricezione e non determinismo). A lezione si aggiunge il one-to-many, in cui più riceventi competono e ogni messaggio va a uno solo.

→ Cap. 14, §3 · Schemi di comunicazione e canali di risposta

Nella comunicazione con guardia di Dijkstra, B; C → S, la guardia è la coppia di un'espressione booleana B sullo stato locale e di un'istruzione di comunicazione C, di solito una receive; S è il blocco da eseguire. Ha successo se B è vera e C può procedere, fallisce se B è falsa, si blocca se B è vera ma C deve aspettare.

→ Cap. 14, §5 · Ricevere da più canali: la comunicazione con guardia

In nessun ordine: se più guardie hanno successo se ne sceglie una in modo non deterministico e si esegue solo quella, mentre gli altri messaggi restano nei loro canali. Nel costrutto do … od la selezione si ripete finché tutte le guardie falliscono.

→ Cap. 14, §5 · Ricevere da più canali: la comunicazione con guardia

Responsabilità distribuite tra processi pari che si coordinano con un protocollo di messaggi, senza un server. Nello scambio dei valori le topologie sono tre: centralizzata (2(n − 1) messaggi, coordinatore collo di bottiglia), simmetrica (n(n − 1) messaggi, massima distribuzione) e ad anello (2n messaggi, concorrenza limitata).

→ Cap. 14, §6 · Peer-to-peer: lo scambio dei valori

Una sincronizzazione estesa: il chiamante (call) aspetta non solo che l'accettante riceva la richiesta (accept), ma anche che esegua il servizio e restituisca il risultato. Ada lo offre nativamente con entry e accept; oggi l'idea sopravvive nelle chiamate di procedura remota e, in forma asincrona, nell'ask degli attori.

→ Cap. 14, §7 · Rendez-vous: call e accept

Solo con gli attori di cui conosce l'indirizzo: quelli che ha creato, quelli che conosceva alla creazione e quelli ricevuti nei messaggi. Poiché gli indirizzi viaggiano nei messaggi, la topologia della comunicazione cambia a run time.

→ Cap. 15, §1 · Che cos'è un attore

Cinque proprietà: reattività pura (lavora solo quando riceve un messaggio), incapsulamento dello stato, semantica a macro-step (un messaggio elaborato per intero prima del successivo), fairness (ogni messaggio prima o poi viene consegnato ed elaborato) e location transparency (per inviare basta l'indirizzo, locale o remoto).

→ Cap. 15, §1 · Che cos'è un attore

Dietro ogni attore c'è un ciclo che aspetta un messaggio, sceglie l'handler e lo esegue fino in fondo. In Pekko e ActorFoundry il ciclo sta nel framework, incapsulato nell'attore, e il programmatore scrive solo gli handler (receive implicita); in Erlang la receive la scrive il programmatore, ed è selettiva.

→ Cap. 15, §2 · Dov'è il ciclo degli eventi

Per il primo esercizio, il sistema d'allarme, Apache Pekko (il fork open source di Akka) con l'API typed, in Java come gli esempi del corso; il secondo esercizio, il torneo pari-e-dispari, si fa in Go con goroutine e canali.

→ Cap. 15, §3 · Tre implementazioni, un'idea → Assignment 3, §1 · Cosa ho costruito

Attivo: incapsula il proprio flusso di controllo e decide lui quando elaborare un messaggio, a differenza di un oggetto o di un monitor, pur restando puramente reattivo.

→ Cap. 15, §1 · Che cos'è un attore

Lo mette da parte nello stash e lo reinserisce in mailbox con unstashAll quando cambia stato (Behaviors.withStash). In ActorFoundry lo stesso effetto si ottiene con i local synchronization constraints.

→ Cap. 15, §5 · Il prezzo del macro-step

Ha un indirizzo, una mailbox con i messaggi non ancora elaborati, uno stato privato e un comportamento; sotto c'è un event loop, esplicito o incapsulato nel framework, che estrae un messaggio ed esegue l'handler fino in fondo.

→ Cap. 15, §1 · Che cos'è un attore → Cap. 15, §2 · Dov'è il ciclo degli eventi

Spezzando il lavoro in passi, ciascuno innescato da un messaggio che l'attore invia a se stesso, così tra un passo e l'altro gli altri messaggi (per esempio uno stop) possono essere elaborati. In Pekko, se il lavoro dipende dal tempo, si usano i timer di Behaviors.withTimers.

→ Cap. 15, §5 · Il prezzo del macro-step → Cap. 16, §1 · Timer: un attore che agisce da solo

Scrivere un programma le cui parti girano su nodi diversi, ciascuno con la propria memoria, e interagiscono solo scambiandosi messaggi in rete. Ogni sistema distribuito è concorrente, e in più non ha memoria né clock condivisi e subisce guasti parziali.

→ Cap. 17, §1 · Che cosa cambia quando il sistema è distribuito

Le tre assenze: niente orologio condiviso (gli eventi di nodi diversi non si ordinano con il tempo fisico), niente memoria condivisa (nessuno conosce lo stato globale) e niente rilevamento accurato dei guasti (senza un limite ai ritardi un processo lento e uno caduto sono indistinguibili).

→ Cap. 17, §2 · Le tre assenze

Un sistema in rete che condivide dati non può garantire insieme consistenza (C), alta disponibilità (A) e tolleranza alle partizioni (P). Poiché le partizioni capitano, il contenuto reale è: durante una partizione si rinuncia a C oppure ad A, scegliendo anche operazione per operazione, mentre senza partizioni si possono avere entrambe.

→ Cap. 17, §3 · Il teorema CAP e la latenza

Il tempo che un messaggio impiega ad arrivare, o una richiesta a ricevere risposta. È legata a CAP: la scelta si presenta durante un timeout, quando bisogna annullare l'operazione (meno disponibilità) o procedere (rischio di inconsistenza).

→ Cap. 17, §3 · Il teorema CAP e la latenza

Per le esecuzioni ci sono tre modelli, dal più concreto al più astratto: interleaving (ordine totale tra tutti gli eventi), happened-before (ordine parziale, totale dentro ogni processo) e causalità potenziale (parziale anche dentro un processo). Per la consegna dei messaggi le garanzie sono FIFO, causale, totale e sincrona.

→ Cap. 17, §4 · Il modello di computazione e l'interleaving → Cap. 18, §5 · Ordinare i messaggi

Un'esecuzione è una coppia (E, →): l'insieme degli eventi e l'ordine parziale happened-before (n. 187), in cui gli eventi di ogni processo sono totalmente ordinati e e → f se nel diagramma c'è un cammino da e a f. È il modello adatto a catturare un'esecuzione reale, dove un ordine totale tra nodi diversi non si può osservare.

→ Cap. 17, §5 · Happened-before: l'ordine che si può ricostruire → Cap. 17, §6 · Causalità potenziale e scelta del modello

Raffina happened-before: dentro un processo non tutti gli eventi sono in rapporto causale, quindi l'ordine locale è solo quello delle dipendenze potenziali (per esempio due ricezioni su porte diverse che aggiornano oggetti diversi). Un diagramma di causalità potenziale equivale all'insieme dei diagrammi happened-before consistenti con esso, ed è il modello adatto al debugging distribuito.

→ Cap. 17, §6 · Causalità potenziale e scelta del modello

Gli orologi di Lamport: ogni processo tiene un contatore, lo incrementa a ogni evento, lo allega ai messaggi e alla ricezione prende il massimo tra il proprio e quello ricevuto, più uno. Garantiscono che a → b implichi C(a) < C(b), ma non il contrario, quindi non riconoscono gli eventi concorrenti.

→ Cap. 17, §7 · Orologi logici di Lamport

Ogni processo tiene un vettore di N contatori, con la propria componente per i propri eventi e le altre per ciò che sa degli altri; i vettori viaggiano nei messaggi e alla ricezione si prende il massimo componente per componente. Vale a → b se e solo se V(a) < V(b), quindi vettori incomparabili indicano eventi concorrenti; il limite è che N deve essere noto.

→ Cap. 17, §8 · Orologi vettoriali

Le tre assenze: niente clock né memoria condivisi, e guasti. Si usano happened-before e orologi logici per ordinare gli eventi; quasi tutti gli algoritmi assumono un sistema asincrono senza guasti, e quando si gestiscono i guasti si assume un sistema sincrono per avere timeout affidabili.

→ Cap. 18, §1 · Come si legge un algoritmo distribuito

Un coordinatore custodisce un token: chi vuole entrare gli manda una richiesta, entra quando riceve il token e uscendo lo restituisce (tre messaggi), e se il token è fuori il coordinatore accoda la richiesta invece di rispondere «no». Per servire le richieste secondo happened-before ogni messaggio porta un vettore delle richieste note, e il coordinatore ritarda una richiesta finché quelle che la precedono causalmente non sono servite.

→ Cap. 18, §2 · Mutua esclusione con un coordinatore

Un processo scelto tra N per un compito particolare, per esempio fare da coordinatore di un algoritmo centralizzato. Poiché può cadere, serve un algoritmo che lo elegga e lo rielegga: di solito si sovrappone alla rete un anello logico, su cui lavora Chang–Roberts (n. 204).

→ Cap. 18, §4 · Elezione del leader: Chang–Roberts

Su un anello ogni processo ha un id unico e vince il massimo: chi avvia invia election(myid) al vicino, chi riceve un id maggiore del proprio lo inoltra, uno minore lo sostituisce con il proprio se non ha ancora partecipato, altrimenti lo scarta. Chi riceve indietro il proprio id è il massimo, si proclama leader e fa girare leader(myid).

→ Cap. 18, §4 · Elezione del leader: Chang–Roberts

I sincronizzatori, che simulano una rete sincrona sopra una asincrona assumendo assenza di guasti o un ritardo massimo noto. Ogni processo ha un contatore, il pulse, tale che i messaggi inviati al pulse i sono ricevuti al pulse i, e il sincronizzatore dice quando si può passare al successivo.

→ Cap. 18, §5 · Ordinare i messaggi

Un algoritmo che cattura uno stato globale consistente verificatosi nel passato: uno stato locale per processo più lo stato dei canali, tale che se contiene la ricezione di un messaggio ne contiene anche l'invio. Serve a rilevare deadlock e terminazione, a osservare predicati globali e a calcolare funzioni globali.

→ Cap. 18, §6 · Lo stato globale: tagli consistenti e Chandy–Lamport

Su canali FIFO, chi avvia salva il proprio stato, diventa rosso e invia un marker su ogni canale in uscita, e un processo bianco che riceve un marker fa lo stesso; lo stato di un canale sono i messaggi ricevuti dopo essere diventati rossi e prima del marker su quel canale. Il FIFO garantisce che nessun processo bianco riceva un messaggio da uno rosso, quindi lo snapshot è consistente senza fermare nessuno.

→ Cap. 18, §6 · Lo stato globale: tagli consistenti e Chandy–Lamport

Mettere d'accordo processi distribuiti su un valore: ognuno propone un valore e alla fine decide in modo irrevocabile. I requisiti sono terminazione (ogni processo corretto decide), accordo (tutti i corretti decidono lo stesso valore) e integrità (se tutti i corretti hanno proposto lo stesso valore, decidono quello).

→ Cap. 18, §7 · Il consenso e il risultato FLP

No, se anche un solo processo può andare in crash: è il risultato FLP (Fischer, Lynch, Paterson, 1985), valido per ogni algoritmo deterministico, perché un processo caduto è indistinguibile da uno lento. Se ne esce cambiando le ipotesi: sincronia, algoritmi randomizzati o sincronia parziale (Paxos, Raft).

→ Cap. 18, §7 · Il consenso e il risultato FLP

Sì: con al più f crash bastano f + 1 round in cui ognuno invia a tutti i valori che conosce e non ha ancora inviato, considerando caduto chi non si fa sentire entro il timeout, e alla fine tutti applicano la stessa funzione di decisione. Con processi bizantini serve di più (n. 211).

→ Cap. 18, §8 · Consenso in un sistema sincrono

Il consenso quando i processi guasti possono comportarsi in modo arbitrario, anche mentendo, raccontato da Lamport, Shostak e Pease (1982) come generali di cui alcuni traditori. Non si risolve se N ≤ 3f: servono almeno 3f + 1 processi, e l'algoritmo del re delle slide, con la soglia N/2 + f, ne richiede N > 4f.

→ Cap. 18, §9 · Guasti bizantini

Perché i thread Java poggiano su quelli del sistema operativo: scheduling, numero massimo di thread e memoria per lo stack dipendono dalla piattaforma. E l'interleaving cambia da una macchina all'altra, quindi una race condition mai vista su un computer può comparire su un altro: la correttezza non può dipendere dalla piattaforma su cui si è provato.

→ Cap. 19, §1 · Middleware e trasparenza → Cap. 10, §1 · Come si crea e si controlla un thread

Un middleware che offre messaggistica: i client inviano e ricevono messaggi tramite code (point-to-point) o topic (publish/subscribe), con persistenza e garanzie di consegna. Rispetto all'RPC rende i messaggi espliciti, l'interazione asincrona e la comunicazione persistente, e disaccoppia i partecipanti; un esempio è RabbitMQ.

→ Cap. 19, §4 · Middleware orientati ai messaggi

Uno strato software tra il sistema operativo e le applicazioni distribuite, con vita propria, che offre servizi come la comunicazione, i nomi per trovare le risorse e la persistenza, così che le parti di un'applicazione interagiscano senza scendere a socket e protocolli. Esempi: RPC, Java RMI, CORBA, i MOM.

→ Cap. 19, §1 · Middleware e trasparenza

Un componente software fornito attraverso un endpoint raggiungibile in rete: un provider lo offre, dei consumer lo usano scambiando messaggi secondo un contratto. È oggi l'approccio principale ai sistemi distribuiti su Internet.

→ Cap. 19, §5 · Servizi e architetture orientate ai servizi

Il contratto (API) è l'insieme di tutti i messaggi che il servizio supporta, esposto a un endpoint; nei big web service lo descrive un WSDL, con le operazioni astratte nel portType e il protocollo concreto nel binding. In una SOA REST si scompone in capability e poggia su un contratto uniforme di tre elementi: URI, metodi HTTP e media type.

→ Cap. 19, §5 · Servizi e architetture orientate ai servizi → Cap. 19, §6 · Web service: SOAP, WSDL e REST

La proprietà per cui la descrizione di un servizio può essere trovata e capita da persone e da altri servizi che potrebbero usarlo. È uno degli otto principi di progetto dei servizi.

→ Cap. 19, §5 · Servizi e architetture orientate ai servizi

Service-Oriented Architecture: uno stile architetturale che scompone la logica di business in servizi più piccoli e autonomi, distribuiti logicamente e fisicamente, che interoperano grazie a contratti e standard condivisi. I suoi componenti sono servizio, contratto, endpoint, messaggio, policy e service consumer.

→ Cap. 19, §5 · Servizi e architetture orientate ai servizi

Un linguaggio XML che definisce l'architettura e il formato dei messaggi dei web service: un Envelope con un Header estensibile (instradamento, qualità del servizio) e un Body con il contenuto. Il contratto invece non lo definisce SOAP ma WSDL.

→ Cap. 19, §6 · Web service: SOAP, WSDL e REST

I microservizi sono uno stile in cui un'applicazione è una suite di piccoli servizi, ciascuno nel proprio processo, organizzati per capacità di business, con protocolli leggeri e deploy e dati indipendenti. I big web service standardizzano invece l'interoperabilità tra sistemi enterprise con uno stack pesante: XML, SOAP, WSDL e gli standard WS-*.

→ Cap. 19, §7 · Microservizi e stili architetturali → Cap. 19, §6 · Web service: SOAP, WSDL e REST

Le slide ne confrontano quattro: a strati, esagonale (la logica al centro, porte e adattatori verso l'esterno), monolitico (un unico eseguibile) e a microservizi (un insieme di servizi, ciascuno con la propria architettura, tipicamente esagonale).

→ Cap. 19, §7 · Microservizi e stili architetturali

Pro: rilascio e scalabilità indipendenti, team autonomi per area di business, libertà di linguaggi e database, confini espliciti, guasti confinati al servizio. Contro: si progetta un sistema distribuito, con latenza su ogni interazione, comunicazione complessa, disponibilità ridotta dalle chiamate sincrone e dati da mantenere consistenti tra servizi.

→ Cap. 19, §7 · Microservizi e stili architetturali

Un cambio di paradigma nell'erogazione dei servizi informatici: calcolo, dati e servizi si spostano off-premise, in un impianto centralizzato e trasparente rispetto alla posizione, e si pagano per l'uso. È una delle scelte principali per le applicazioni distribuite su larga scala.

→ Cap. 19, §8 · Cloud: dall'infrastruttura alle funzioni

CapEx è la spesa in conto capitale, cioè comprare in anticipo l'infrastruttura per il picco di domanda; OpEx è la spesa operativa. Il cloud trasforma la prima nella seconda: si paga l'uso effettivo delle risorse, quindi i costi seguono gli incassi.

→ Cap. 19, §8 · Cloud: dall'infrastruttura alle funzioni

IaaS (infrastruttura di calcolo e memorizzazione, per esempio Amazon EC2), PaaS (una piattaforma per sviluppare applicazioni, per esempio Google App Engine) e SaaS (applicazioni pronte in rete, per esempio Salesforce); salendo, il fornitore gestisce sempre più livelli. A questi si aggiunge il FaaS (n. 223).

→ Cap. 19, §8 · Cloud: dall'infrastruttura alle funzioni

Function as a Service: codice organizzato in funzioni attivate da eventi, eseguite dalla piattaforma senza server da gestire e con scalabilità automatica. Esempi: AWS Lambda, Google Cloud Functions.

→ Cap. 19, §8 · Cloud: dall'infrastruttura alle funzioni

Il modello che generalizza il FaaS, con quattro caratteristiche: nessun server né sistema operativo da gestire, fatturazione per invocazione, scalabilità automatica, disponibilità e tolleranza ai guasti incorporate. Le funzioni sono effimere e senza stato: lo stato sta in un data store.

→ Cap. 19, §8 · Cloud: dall'infrastruttura alle funzioni