Introduzione alla Programmazione Concorrente e Programmazione Asincrona

1. Presentazione del corso

Il Prof. Alessandro Ricci apre il corso di Programmazione Concorrente e Distribuita (PCD) presso l'Universita' di Bologna, sede di Cesena. Il corso e' integrato con un'altra disciplina: le due parti sono indipendenti ma complementari. Il voto finale sara' la media dei voti ottenuti nelle due parti.

Modalita' d'esame

L'esame si compone di due macro-parti:

Gli assignments non hanno deadline: lo studente organizza autonomamente i tempi. Non sono esami parziali, ma strumenti per consolidare l'apprendimento. Il professore sottolinea che questa flessibilita' e' una novita' rispetto agli anni passati.

Struttura del corso

1. Parte 1 — Programmazione multi-threaded (Java, meccanismi di sincronizzazione)
2. Parte 2 — Programmazione concorrente basata su messaggi (attori, Erlang, Go)
3. Parte 3 — Programmazione distribuita: comunicazione su rete

2. Concetti fondamentali

Concorrenza: definizione generale

La concorrenza e' una proprieta' dei sistemi in cui piu' processi computazionali sono in esecuzione contemporaneamente e potenzialmente interagiscono tra loro. E' un concetto che attraversa molti domini: sistemi operativi, programmi multi-thread, sistemi distribuiti, sistemi di controllo, sistemi real-time.

Programmazione concorrente

La programmazione concorrente e' l'arte di costruire programmi in cui molteplici attivita' computazionali si sovrappongono nel tempo e tipicamente interagiscono in qualche modo. Un programma concorrente e' un insieme finito di programmi sequenziali che possono essere eseguiti in parallelo.

Ogni programma sequenziale in esecuzione viene chiamato processo: un singolo thread di controllo, una sequenza di istruzioni che opera come un gruppo. Il termine e' astratto e non va confuso con il processo del sistema operativo.

Proprieta' fondamentali dei processi

Esempio concreto: sistemi operativi

Il professor Ricci fa l'esempio dei sistemi operativi: in un sistema moderno, decine o centinaia di processi convivono. Il sistema operativo e' un esempio classico di sistema concorrente, dove la concorrenza emerge dalla gestione di eventi asincroni (interrupt), scheduler, e interazioni tra processi.

3. Concorrente, parallelo, distribuito

E' fondamentale distinguere tre concetti spesso confusi:

Il punto di Rob Pike

Il professor Ricci cita Rob Pike (co-creatore di Go): la concorrenza e' un modo di strutturare il software, di comporre computazioni indipendenti. Il parallelismo e' un aspetto algoritmico, legato alle performance. La concorrenza abilita il parallelismo, ma non e' parallelismo.

4. Evoluzione hardware: il "Free Lunch is Over"

Herb Sutter ha coniato l'espressione "The Free Lunch is Over": per decenni i programmatori hanno beneficiato dell'aumento automatico delle prestazioni grazie all'incremento della frequenza dei processori. Questa era e' finita. Oggi le prestazioni si migliorano aggiungendo core, non aumentando la frequenza.

Architetture multi-core

I processori moderni integrano multi-core sullo stesso chip, condividendo RAM e talvolta livelli di cache. Esempi: Intel Core i7, AMD Ryzen Threadripper (fino a 64 core).

Architetture ibride (P-core + E-core)

Le architetture recenti sono ibride, combinando core di dimensioni diverse:

Esempio: Intel Core i9-14th Gen — 24 core (8 P-core + 16 E-core). Anche AMD con l'architettura Zen 5 adotta un approccio simile, con chiplet design che collega piccole unita' (Core Complex Dies) tramite un'interconnessione ad alta velocita'.

Architetture eterogenee e many-core

I chip moderni integrano processori specializzati: GPU, NPU (Neural Processing Unit), ISP (Image Signal Processor), FPGA. Esempio: Apple Silicon M5 — System-on-Chip con CPU (P-core + E-core), GPU, NPU per machine learning, e vari coprocessori.

Supercomputer e cluster

I supercomputer (es. Fugaku del RIKEN Center) hanno milioni di core connessi da reti ad-hoc. I cluster usano componenti commodity (computer standard) connessi da reti standard (Gigabit Ethernet, InfiniBand). Il cloud computing (AWS EC2, Azure, Google App Engine) offre risorse come servizio su rete pubblica.

5. Tassonomia di Flynn

La tassonomia di Flynn classifica tutti i sistemi di calcolo in base al numero di flussi di istruzioni e flussi di dati:

Modelli MIMD

La categoria MIMD si suddivide ulteriormente in base all'organizzazione della memoria:

6. Legge di Amdahl e performance

Speedup

Lo speedup misura il miglioramento delle prestazioni quando si usa un algoritmo parallelo rispetto a quello sequenziale:

S = T1 / TN

T1 = tempo di esecuzione con 1 processore
TN = tempo di esecuzione con N processori
N  = numero di processori

Legge di Amdahl

La legge di Amdahl stabilisce un limite teorico allo speedup ottenibile parallelizzando un programma:

S = 1 / ((1 - P) + P/N)

P = proporzione del programma parallelizzabile
1 - P = parte non parallelizzabile (sequenziale)

Efficienza

L'efficienza e' una misura normalizzata dello speedup che indica quanto efficacemente ogni processore viene utilizzato:

E = S / N

S = speedup, N = numero di processori

L'efficienza ideale e' 1 (tutti i processori usati a piena capacita'), ma in pratica e' quasi sempre inferiore.

Il collo di bottiglia della memoria

Oltre alla legge di Amdahl, un altro fattore limitante e' la memoria condivisa e il bus: solo un'operazione di memoria puo' avvenire alla volta. Da qui l'importanza della cache e dei protocolli di coerenza della cache, sempre piu' complessi e sofisticati.

7. Processi e interazione

Interazione tra processi

Qualsiasi programma concorrente non banale si basa su processi che interagiscono. I tipi fondamentali di interazione sono tre:

Sincronizzazione vs mutua esclusione

8. Race conditions e situazioni critiche

Esempio classico: Alice, Bob e il latte

Il professor Ricci presenta il celebre esempio di Alice e Bob per illustrare le difficolta' della sincronizzazione. Alice e Bob vivono insieme e devono comprare il latte quando finisce:

Race condition

Una race condition (o race hazard) si verifica quando due o piu' processi accedono e aggiornano concorrentemente risorse condivise, e il risultato dell'aggiornamento dipende dall'ordine specifico in cui avvengono gli accessi. Si manifesta in due forme principali:

1. Cattiva gestione di interazioni previste
2. Presenza di interazioni spurie non previste nel problema

Situazioni critiche

I problemi nei programmi concorrenti possono portare a tre situazioni critiche:

9. Linguaggi e macchine concorrenti

Macchina concorrente

Una macchina concorrente fornisce il supporto per eseguire programmi concorrenti, mettendo a disposizione tanti processori virtuali quanti sono i processi della computazione concorrente. Fornisce tre meccanismi di base:

1. Multiprogrammazione: creazione e gestione di processori virtuali, scheduling dei processori fisici.
2. Sincronizzazione e comunicazione: due modelli architetturali — memoria condivisa (multi-threaded) e message passing.
3. Controllo d'accesso alle risorse.

Approcci alla progettazione di linguaggi concorrenti

Oltre i thread: scenario ricco

Il panorama della programmazione concorrente va ben oltre i thread tradizionali:

• Framework basati su task (es. Java Executor Framework)
• Programmazione asincrona (event-loop, AsyncTask)
• Attori (OOP concorrente, active objects)
• Message Passing sincrono (processi + scambio di messaggi)
• Programmazione reattiva (Functional Reactive Programming, Rx)
• Calcolo parallelo (GPGPU, Lambda Architecture per Big Data)

10. Programmazione asincrona: event loop e callback

La programmazione asincrona e' uno stile sempre piu' importante, supportato ormai da tutti i principali framework e piattaforme (Java, .NET, iOS, Android, JavaScript/Node.js). Si tratta dell'esecuzione e gestione di computazioni/richieste/processi asincroni, astraendo dai thread.

Panorama attuale dell'async

• Event-driven programming: architetture basate su event loop, Reactor pattern
• Async Functions & CPS: event handler come continuazioni, Promise
• Async/await: meccanismo linguistico che imita lo stile sincrono pur essendo asincrono
• Coroutine-based concurrency: thread leggeri

Event-driven programming

Un programma e' fatto di gestori di eventi (event handler) che vengono chiamati (eseguiti, attivati) quando si verificano eventi. Gli eventi possono essere azioni utente (click, pressioni di tasti), output di sensori, messaggi, risposte ricevute. E' una "programmazione senza call stack": dopo l'esecuzione di ogni handler lo stack e' vuoto.

Modello di esecuzione: Event Loop

L'event loop e' un'architettura di controllo in cui un singolo thread di controllo attende eventi ed esegue gli handler corrispondenti. Una coda degli eventi tiene traccia degli eventi generati dall'ambiente o dagli handler stessi. Gli handler sono eseguiti atomicamente: se un evento si verifica mentre un handler e' in esecuzione, sara' servito solo al termine dell'handler corrente.

loop {
  Event ev = waitForEvent(eventQueue)
  Handler handler = selectHandler(ev)
  execute(handler)
}

Callback e Continuation Passing Style (CPS)

Le richieste asincrone usano il modello callback: una funzione (callback) viene specificata come argomento della chiamata asincrona. La callback viene invocata dall'event loop quando il risultato e' pronto. Questo definisce una continuazione della computazione, da cui Continuation-Passing Style (CPS).

Callback Hell / Pyramid of Doom

La composizione di callback annidate porta a un problema ben noto: callback hell (o "piramide della morte"). La struttura del codice si espande orizzontalmente invece che verticalmente, diventando difficile da leggere, mantenere ed estendere.

step1(function(result1) {
  step2(function(result2) {
    step3(function(result3) {
      // e cosi' via...
    })
  })
})

Esempio concreto discusso dal professore — la funzione loadUserPic in versione sincrona e asincrona:

function loadUserPic(userId) {
  let user = findUserById(userId);
  return loadPic(user.picId);
}

function loadUserPic(userId, ret) {
  findUserById(userId, (user) => {
    loadPic(user.picId, ret);
  });
}
loadUserPic('john', (pic) => {
  ui.show(pic);
});

Nel server Node.js, l'annidamento e' ancora piu' pronunciato:

http.createServer((request, response) => {
  let uri = url.parse(request.url).pathname;
  let filename = path.join(process.cwd(), uri);
  path.exists(filename, (exists) => {
    if(exists) {
      fs.readFile(filename, (err, data) => {
        response.writeHead(200);
        response.end(data);
      });
    } else {
      response.writeHead(404);
      response.end();
    }
  });
}).listen(8080);

11. Promise e chaining

Il problema delle callback

Le callback hanno problemi noti: "asynchronous spaghetti" (frammentazione della computazione), "pyramid of doom" (annidamento), difficolta' di gestione degli errori. Le Promise sono state proposte per risolvere questi problemi.

Cos'e' una Promise?

Una Promise e' un oggetto proxy che rappresenta un risultato non ancora disponibile ma che sara' calcolato in futuro (simile ai futures, proposti nel 1976 da Friedman e Wise). Incapsula azioni asincrone, comportandosi come un valore di ritorno di una computazione, anche se il valore potrebbe non essere ancora disponibile.

Proprietà fondamentali

• Una Promise puo' essere risolta (resolved/fulfilled) o rigettata (rejected) una e una sola volta.
• Una volta risolta, una Promise e' immutabile: stato e valore non cambiano piu'.
• Permette di appiattire l'annidamento delle callback.

API delle Promise in JavaScript

Promise chaining

La caratteristica chiave per appiattire la "piramide della morte": il metodo then ritorna a sua volta una Promise, permettendo il chaining:

let promise = new Promise((resolve, reject) => {
  resolve(1);
});
promise.then((val) => {
  console.log(val); // 1
  return val + 2;
}).then((val) => {
  console.log(val); // 3
});

Composizione di Promise

L'API delle Promise fornisce due metodi fondamentali per la composizione:

// Promise.all - join point per task paralleli
let myProm1 = delayWithRand(1000);
let myProm2 = delayWithRand(2000);
let myTotalProm = Promise.all([myProm1, myProm2]);
myTotalProm.then((values) => {
  console.log(values[0]); // risultato del primo
  console.log(values[1]); // risultato del secondo
});

// Promise.race - chi arriva prima
let myProm1 = delayWithRand(1000);
let myProm2 = delayWithRand(2000);
let myTotalProm = Promise.race([myProm1, myProm2]);
myTotalProm.then((value) => {
  console.log(value); // risultato del piu' veloce
});

Limiti delle Promise

12. Async/await e coroutine

L'evoluzione: async & await

L'estensione async/await e' la soluzione piu' recente e promettente nella programmazione asincrona. L'obiettivo e' fornire uno stile di programmazione sincrono mantenendo un core asincrono. Introdotta in ES2017 (JavaScript), implementata in .NET TAP (C#), Python, DART, Kotlin e molti altri.

L'idea fondamentale:

// Stile async con Promise
let p = asyncFunc(...);
p.then(onCompleteFunc, onErrorFunc)

// Stile async/await - sembra sincrono ma e' asincrono
let p = asyncFunc(...);
let res = await p;
// usa res

await sospende l'esecuzione della funzione finche' la Promise non e' risolta, ma non blocca il thread di controllo: il controllo viene ceduto (yield), salvando lo stato corrente della computazione.

Esempio concreto

Benefici di async/await

• Programmazione asincrona notevolmente semplificata
• Non serve usare esplicitamente Promise/then/chains per sequenze
• Risolti i problemi di eagerness e parametri in then
• Utilizzabile con cicli e iterazioni

Problemi di async/await

Modularita' e incapsulamento

Un esempio discusso dal professore mostra come sia facile sbagliare se non si rispetta la "catena" async:

// Questo NON funziona come ci si aspetterebbe
function g() {
  console.log("started g");
  f(); // f e' async, ma g non la awaita
  console.log("done g");
}

// Versione corretta
async function g() {
  console.log("started g");
  await f();
  console.log("done g");
}

Coroutine

Le coroutine sono una generalizzazione del concetto di subroutine: permettono di sospendere e riprendere l'esecuzione. Sono il meccanismo di basso livello usato per implementare async/await. A differenza delle subroutine tradizionali (che hanno un solo punto di ingresso e terminano sempre), le coroutine possono avere multipli punti di ingresso e uscita tramite yield.

// Esempio: producer-consumer cooperativo con coroutine
var q := new queue

coroutine produce
  loop
    while q is not full
      create some new items
      add the items to q
    yield to consume

coroutine consume
  loop
    while q is not empty
      remove some items from q
      use the items
    yield to produce

Coroutine in Kotlin

Kotlin e' un esempio moderno di linguaggio con supporto nativo alle coroutine. Concetti principali:

Fiber e virtual threads

Le fiber sono thread leggeri che usano cooperative multitasking (a differenza dei thread, che usano preemptive multitasking). Le fiber condividono lo spazio di indirizzi come i thread. Possono essere implementate usando un singolo thread. A livello di astrazione:

• Le coroutine sono un costrutto a livello di linguaggio
• Le fiber sono un costrutto a livello di sistema
• Esempio moderno: Virtual Threads di Java (da JDK 19)

Esempio Kotlin discusso a lezione:

import kotlinx.coroutines.*

fun main(args: Array<String>) = runBlocking {
    println("before async call")
    val result = async {
        println("inside the async call")
        delay(1000)
        println("exiting the async call")
        100
    }
    println("after the async call, before greet")
    greetDelayed(200)
    println("after greet trigger")
    println("${result.await()}")
}

suspend fun greetDelayed(delayMillis: Long) {
    delay(delayMillis)
    println("Hello, World!")
}

Verifica le tue conoscenze

Riferimenti bibliografici

• [SUT-12] Sutter's Mill. Herb Sutter on software, hardware, and concurrency. "Welcome to the Jungle".
• [AND-83] Gregory Andrews and Fred Schneider. "Concepts and Notations for Concurrent Programming", ACM Computing Surveys, Vol. 15, No. 1, March 1983.
• [CLE-96] Rance Cleaveland, Scott Smolka et al. "Strategic Directions in Concurrency Research", ACM Computing Surveys, Vol. 28, No. 4, Dec. 1996.
• [ROS-97] Roscoe, A. W. (1997). The Theory and Practice of Concurrency. Prentice Hall.
• [BUH-05] Peter Buhr and Ashif Harji. "Concurrent Urban Legends". Concurrency and Computation: Practice and Experience. 2005.
• [Con63] Conway, M. E. (July 1963). "Design of a Separable Transition-Diagram Compiler". CACM. 6 (7): 396-408.
• [Mou04] Ana Lucia de Moura; Roberto Ierusalimschy (2004). "Revisiting Coroutines". ACM TOPLAS. 31 (2).
• [Pro18] Aleksandar Prokopec. Theory and Practice of Coroutines with Snapshots. ECOOP 2018.
• [Goe22] Brian Goetz. Virtual Threads: New Foundations for High-Scale Java Applications. InfoQ (Sept. 22).