Problemi Classici della Programmazione Concorrente

Il Problema

Due thread condividono un buffer limitato (array di N celle): il Produttore inserisce elementi, il Consumatore li preleva. Senza sincronizzazione possono verificarsi due problemi:

Buffer pieno — il produttore inserisce su una cella già occupata, sovrascrivendo dati non ancora letti.

Buffer vuoto — il consumatore preleva da una cella vuota, leggendo dati non validi.

Soluzione con tre semafori

Per il buffer limitato servono tre semafori, ognuno con uno scopo preciso:

empty = N Conta i posti liberi. Il produttore fa acquire() prima di inserire: se è 0 (buffer pieno) si blocca.

full = 0 Conta gli elementi presenti. Il consumatore fa acquire() prima di prelevare: se è 0 (buffer vuoto) si blocca.

mutex = 1 Esclusione mutua sull'accesso al buffer. Impedisce che produttore e consumatore tocchino il buffer contemporaneamente.

// Produttore
empty.acquire();  // c'è posto?
mutex.acquire();  // accesso esclusivo
inserisce nel buffer;
mutex.release();
full.release();   // segnala elemento disponibile
// Consumatore
full.acquire();   // c'è qualcosa?
mutex.acquire();  // accesso esclusivo
preleva dal buffer;
mutex.release();
empty.release();  // segnala posto liberato

Premi Avanti → per iniziare la simulazione Produttore/Consumatore.

0 / 18

Buffer (capacità 5) + Processi

Produttore

in attesa

Buffer condiviso

empty=5 full=0 mutex=1

Consumatore

in attesa

Log

Soluzione in Java — buffer limitato con tre semafori

// ProduttoreConsumatore.java
import java.util.concurrent.Semaphore;

public class ProduttoreConsumatore {
  static final int N = 5;
  static int[] buffer = new int[N];
  static int in = 0, out = 0;

  static Semaphore empty = new Semaphore(N); // posti liberi
  static Semaphore full  = new Semaphore(0); // elementi presenti
  static Semaphore mutex = new Semaphore(1); // accesso esclusivo al buffer

  static class Produttore extends Thread {
    public void run() {
      for (int i = 0; i < 10; i++) {
        try {
          empty.acquire(); // c'è posto? se 0 → si blocca
          mutex.acquire(); // accesso esclusivo al buffer
          buffer[in] = i;
          in = (in + 1) % N;
          System.out.println("Prodotto: " + i);
          mutex.release();
          full.release();  // segnala: elemento disponibile
        } catch (InterruptedException e) {}
      }
    }
  }

  static class Consumatore extends Thread {
    public void run() {
      for (int i = 0; i < 10; i++) {
        try {
          full.acquire();  // c'è qualcosa? se 0 → si blocca
          mutex.acquire(); // accesso esclusivo al buffer
          int item = buffer[out];
          out = (out + 1) % N;
          System.out.println("Consumato: " + item);
          mutex.release();
          empty.release(); // segnala: posto liberato
        } catch (InterruptedException e) {}
      }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread p = new Produttore();
    Thread c = new Consumatore();
    p.start();
    c.start();
    p.join();
    c.join();
  }
}

Il Problema

Una risorsa condivisa (es. un database, un file) viene acceduta da N lettori e M scrittori. Le regole fondamentali sono:

✓ Più lettori possono leggere contemporaneamente — la lettura non modifica i dati.

✗ Lo scrittore deve avere accesso esclusivo — nessun altro lettore o scrittore può operare mentre lui scrive.

! Starvation: se arrivano lettori in continuazione, lo scrittore potrebbe non ottenere mai accesso. Le varianti del problema bilanciano questa priorità.

Varianti e Soluzione

Priorità ai Lettori

I lettori non aspettano se la risorsa è già letta. Rischio: gli scrittori vanno in starvation.

Priorità agli Scrittori

Se uno scrittore aspetta, i nuovi lettori vengono bloccati. Rischio: i lettori vanno in starvation.

Variabili usate: read_count (numero di lettori attivi), mutex (protegge read_count), wrt (esclusione scrittore). Il primo lettore che arriva acquisisce wrt; l'ultimo che esce la rilascia.

Premi Avanti → per simulare l'accesso concorrente al database.

0 / 9

Database condiviso + Processi

Lettori

📦 DB

libero

read_count=0 wrt=1

Scrittori

Log

Soluzione in Java — priorità ai lettori

// LettoriScrittori.java
import java.util.concurrent.Semaphore;

public class LettoriScrittori {
  static int readCount = 0;
  // mutex: protegge la variabile readCount
  static Semaphore mutex = new Semaphore(1);
  // wrt: accesso esclusivo allo scrittore
  static Semaphore wrt   = new Semaphore(1);

  static class Lettore extends Thread {
    int id;
    Lettore(int id) { this.id = id; }

    public void run() {
      try {
        mutex.acquire();
        readCount++;
        if (readCount == 1)    // primo lettore: blocca scrittori
          wrt.acquire();
        mutex.release();

        System.out.println("Lettore " + id + " legge"); // lettura

        mutex.acquire();
        readCount--;
        if (readCount == 0)    // ultimo lettore: sblocca scrittori
          wrt.release();
        mutex.release();
      } catch (InterruptedException e) { e.printStackTrace(); }
    }
  }

  static class Scrittore extends Thread {
    int id;
    Scrittore(int id) { this.id = id; }

    public void run() {
      try {
        wrt.acquire();          // accesso esclusivo
        System.out.println("Scrittore " + id + " scrive");
        wrt.release();
      } catch (InterruptedException e) { e.printStackTrace(); }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread[] threads = {
      new Lettore(1), new Lettore(2), new Lettore(3),
      new Scrittore(1)
    };
    for (Thread t : threads) t.start();
    for (Thread t : threads) t.join();
  }
}

Il Problema (Dijkstra, 1965)

5 filosofi siedono a un tavolo rotondo. Tra ogni coppia di filosofi c'è una sola forchetta (5 in totale). Per mangiare un filosofo deve prendere entrambe le forchette (sinistra e destra). Quando non mangia, pensa. Il problema modella la contesa su risorse condivise.

💀

Deadlock: se tutti i filosofi prendono la forchetta sinistra contemporaneamente, nessuno può prendere la destra. Tutti aspettano per sempre.

😵

Starvation: un filosofo potrebbe non riuscire mai a ottenere entrambe le forchette se i vicini mangiano in continuazione.

Soluzioni al Deadlock

Filosofo asimmetrico: i filosofi con indice pari prendono prima la forchetta sinistra, quelli dispari prima la destra. Rompe la simmetria che causa il deadlock.

Al massimo N-1 filosofi a tavola: con un semaforo che limita a 4 il numero di filosofi che provano a mangiare contemporaneamente, almeno uno riesce sempre.

Prendere entrambe le forchette insieme: un filosofo prende le forchette solo se entrambe sono disponibili (sezione critica atomica con mutex).

Premi Avanti → per simulare i filosofi. Vedremo come nasce il deadlock e come evitarlo.

0 / 13

Tavola rotonda

Tavolo
🍝

Stato filosofi

Forchette

Log

Soluzione in Java — filosofo asimmetrico

// Filosofi.java — soluzione asimmetrica (no deadlock)
import java.util.concurrent.Semaphore;

public class Filosofi {
  static final int N = 5;
  // un semaforo per ogni forchetta, inizializzato a 1 (disponibile)
  static Semaphore[] forchette = new Semaphore[N];

  static { for (int i=0; i<N; i++) forchette[i] = new Semaphore(1); }

  static class Filosofo extends Thread {
    int id;
    Filosofo(int id) { this.id = id; }

    void pensa() throws InterruptedException {
      System.out.println("F"+id+": penso...");
      Thread.sleep((long)(Math.random()*1000));
    }
    void mangia() throws InterruptedException {
      System.out.println("F"+id+": MANGIO 🍝");
      Thread.sleep((long)(Math.random()*1000));
    }

    public void run() {
      try {
        while (true) {
          pensa();

          if (id % 2 == 0) {          // filosofo PARI
            forchette[id].acquire();          // sinistra prima
            forchette[(id+1)%N].acquire();   // poi destra
          } else {                     // filosofo DISPARI
            forchette[(id+1)%N].acquire();   // destra prima
            forchette[id].acquire();          // poi sinistra
          }

          mangia();

          forchette[id].release();
          forchette[(id+1)%N].release();
        }
      } catch (InterruptedException e) { e.printStackTrace(); }
    }
  }

  public static void main(String[] args) throws InterruptedException {
    Thread[] f = new Thread[N];
    for (int i=0; i<N; i++) { f[i] = new Filosofo(i); f[i].start(); }
    for (Thread t : f) t.join();
  }
}

Codice SBAGLIATO — causa deadlock

// SENZA asimmetria: tutti prendono sinistra → nessuno prende destra → DEADLOCK
forchette[id].acquire();         // tutti acquisiscono sinistra
forchette[(id+1)%N].acquire();  // nessuno riesce ad acquisire destra
// ← tutti i thread bloccati qui per sempre