Salta al contenuto
Note per Studenti Esercizio - concorrenza sulle copie di un libro con monitor e attesa limitata (progetto originale)

Esercizio - concorrenza sulle copie di un libro con monitor e attesa limitata (progetto originale)

Esercizio originale, nello stile del progetto d'esame (un problema di concorrenza, con il codice). Teoria: Concorrenza in Java - thread, sincronizzazione e poolIn Java un thread si crea con Thread e Runnable e si avvia con start() (run() chiamato direttamente non crea nessun thread); i thread che modificano dati condivisi producono race condition (aggiornamenti persi) se la sequenza lettura-modifica-scrittura non è atomica, e si protegge con synchronized (monitor dell'oggetto, rientrante), con classi atomiche o con lock; wait/notifyAll dentro un synchronized, sempre in un ciclo while, realizzano l'attesa di una condizione (pool di risorse, produttore-consumatore); l'ordine opposto di acquisizione di due lock provoca stallo (deadlock) e si evita con un ordine globale; i thread pool (ExecutorService, Callable, Future) riusano pochi thread per molti compiti; i pattern concorrenti ricorrenti sono monitor, produttore-consumatore, thread pool, Singleton thread-safe, oggetti immutabili, future.Concorrenza in Java - thread, sincronizzazione e pool →. Il codice è stato compilato ed eseguito con JDK 21; nelle uscite i valori che dipendono dallo scheduler sono indicati come tali.

Testo

Di un libro esiste una sola copia. Dieci iscritti, ciascuno nel proprio thread, la chiedono nello stesso istante. La prima versione del metodo prendi() è:

java
boolean prendi() {
    if (disponibili > 0) {        // controllo
        disponibili--;            // modifica
        return true;
    }
    return false;
}

Si richiede di: 1) dimostrare con un programma che questa versione assegna più copie di quelle che esistono (e spiegare perché, mostrando l'intreccio); 2) correggerla con synchronized; 3) aggiungere la possibilità di attendere una copia per un tempo massimo (prendi(attesaMs)), con restituisci() che sveglia chi aspetta; 4) dimostrare l'attesa con un thread che restituisce la copia dopo 50 ms mentre un altro attende fino a 1 s.

Soluzione

1. Il difetto: check-then-act

Il metodo fa due passi separati: controllo (disponibili > 0) e modifica (disponibili--). Se due thread eseguono il controllo prima che uno dei due decrementi, entrambi vedono 1 e entrambi decrementano:

passo thread A thread B disponibili
1 legge 1, controllo vero 1
2 legge 1, controllo vero 1
3 decrementa 0
4 decrementa -1
5 restituisce true restituisce true -1

Due iscritti ottengono la stessa copia e il contatore va sotto zero. Per rendere l'intreccio certo il programma inserisce uno sleep(5) tra controllo e modifica (nel caso reale la finestra è di pochi nanosecondi, e l'errore si manifesta raramente e in modo non riproducibile: è il motivo per cui è pericoloso). I dieci thread partono insieme grazie a un CountDownLatch.

2. La correzione

Controllo e modifica devono essere un'unica sezione critica: il metodo diventa synchronized (il monitor dell'oggetto CopieSicure). In questo modo un solo thread alla volta esegue il blocco, e chi arriva dopo trova disponibili == 0.

3. L'attesa limitata

Un iscritto può voler aspettare una copia per un certo tempo: serve wait con un tempo massimo. Regole applicate (vedi la teoria): wait dentro synchronized, in un while perché dopo il risveglio la condizione può essere di nuovo falsa (un altro thread può aver preso la copia) o il risveglio può essere spurio, e il tempo residuo va ricalcolato a ogni giro: wait(resto) aspetta al massimo resto millisecondi. restituisci() incrementa e fa notifyAll().

4. Codice

java
import java.util.concurrent.CountDownLatch;

/** Versione ingenua: controlla e poi modifica in due passi separati (check-then-act). */
class CopieIngenue {
    private int disponibili;
    CopieIngenue(int n) { disponibili = n; }

    boolean prendi() {
        if (disponibili > 0) {                                 // 1) controllo
            try { Thread.sleep(5); } catch (InterruptedException e) { }   // un altro thread puo' entrare qui
            disponibili--;                                     // 2) modifica
            return true;
        }
        return false;
    }
    int disponibili() { return disponibili; }
}

/** Versione corretta: controllo e modifica sono un'unica sezione critica; chi non trova copie attende un tempo massimo. */
class CopieSicure {
    private int disponibili;
    CopieSicure(int n) { disponibili = n; }

    synchronized boolean prendi(long attesaMs) throws InterruptedException {
        long fine = System.currentTimeMillis() + attesaMs;
        while (disponibili == 0) {
            long resto = fine - System.currentTimeMillis();
            if (resto <= 0) return false;                      // scaduta l'attesa
            wait(resto);                                       // rilascia il monitor mentre aspetta
        }
        disponibili--;
        return true;
    }

    synchronized void restituisci() { disponibili++; notifyAll(); }
    synchronized int disponibili() { return disponibili; }
}

public class Copie {
    static int provaIngenua() throws InterruptedException {
        CopieIngenue c = new CopieIngenue(1);                 // UNA sola copia, 10 utenti insieme
        int[] ottenute = {0};
        CountDownLatch via = new CountDownLatch(1);
        Thread[] t = new Thread[10];
        for (int i = 0; i < t.length; i++) {
            t[i] = new Thread(() -> {
                try { via.await(); } catch (InterruptedException e) { }
                if (c.prendi()) synchronized (ottenute) { ottenute[0]++; }
            });
            t[i].start();
        }
        via.countDown();
        for (Thread x : t) x.join();
        return ottenute[0];
    }

    public static void main(String[] args) throws Exception {
        System.out.println("versione ingenua: copie assegnate = " + provaIngenua() + " (ne esisteva una)");

        CopieSicure c = new CopieSicure(1);
        int[] ottenute = {0};
        Thread[] t = new Thread[10];
        for (int i = 0; i < t.length; i++) {
            t[i] = new Thread(() -> {
                try { if (c.prendi(200)) synchronized (ottenute) { ottenute[0]++; } }
                catch (InterruptedException e) { Thread.currentThread().interrupt(); }
            });
            t[i].start();
        }
        for (Thread x : t) x.join();
        System.out.println("versione sicura:  copie assegnate = " + ottenute[0] + ", disponibili = " + c.disponibili());

        // attesa che si risolve: un lettore restituisce la copia mentre un altro aspetta
        CopieSicure d = new CopieSicure(0);
        Thread restituisce = new Thread(() -> {
            try { Thread.sleep(50); } catch (InterruptedException e) { }
            d.restituisci();
        });
        restituisce.start();
        System.out.println("prenotato con attesa di 1 s: " + d.prendi(1000));
        restituisce.join();
    }
}

Uscita:

versione ingenua: copie assegnate = 10 (ne esisteva una)
versione sicura:  copie assegnate = 1, disponibili = 0
prenotato con attesa di 1 s: true

Lettura dell'uscita (il primo numero dipende dallo scheduler ma è in pratica maggiore di 1; gli altri due sono deterministici):

  • versione ingenua: le copie assegnate superano quella esistente (qui tutte e 10 le richieste hanno avuto la copia), il difetto è dimostrato;
  • versione sicura: esattamente 1 copia assegnata, 0 disponibili: gli altri nove attendono 200 ms e poi rinunciano (false);
  • attesa: il thread che restituisce dopo 50 ms sveglia il richiedente, che ottiene la copia prima del limite di 1 s (true).

Perché non basta volatile né un AtomicInteger

volatile int disponibili garantisce la visibilità ma non rende atomico "controlla e decrementa". Con un AtomicInteger si potrebbe usare compareAndSet in un ciclo (controllo e decremento insieme), ma per l'attesa serve comunque un monitor (o una Condition/semaforo): per questo nel monitor si usano wait e notifyAll. Una soluzione alternativa è java.util.concurrent.Semaphore(1) con tryAcquire(attesa, MILLISECONDS).

Versione ripasso

  • Difetto: check-then-act: controllo (disponibili > 0) e modifica (disponibili--) separati; due thread vedono 1 e decrementano entrambi →\to contatore -1, la stessa copia assegnata due volte. Nel programma: sleep(5) fra i due passi e CountDownLatch per far partire i 10 thread insieme.
  • Correzione: controllo e modifica in un'unica sezione critica: metodo synchronized.
  • Attesa limitata: wait dentro synchronized, in un while, con tempo residuo ricalcolato a ogni giro; restituisci() fa notifyAll().
java
synchronized boolean prendi(long attesaMs) throws InterruptedException {
    long fine = System.currentTimeMillis() + attesaMs;
    while (disponibili == 0) {
        long resto = fine - System.currentTimeMillis();
        if (resto <= 0) return false;                  // attesa scaduta
        wait(resto);                                    // rilascia il monitor mentre aspetta
    }
    disponibili--;
    return true;
}
synchronized void restituisci() { disponibili++; notifyAll(); }

  • Uscita: versione ingenua: copie assegnate oltre una (qui 10 su 10; varia); versione sicura: copie assegnate = 1, disponibili = 0; attesa: prenotato con attesa di 1 s: true (la copia è restituita dopo 50 ms).

    passo thread A thread B disponibili
    1 controllo vero (legge 1) 1
    2 controllo vero (legge 1) 1
    3 decrementa 0
    4 decrementa -1

  • Come si dimostra: sleep(5) tra controllo e modifica rende certo l'intreccio; CountDownLatch fa partire 10 thread insieme; in condizioni reali la finestra è di nanosecondi e l'errore appare raramente e non è riproducibile, per questo è pericoloso.

  • Versione sicura con attesa: i 10 thread chiedono con attesa di 200 ms: una copia assegnata, gli altri nove rinunciano (false); d.prendi(1000) con una restituzione dopo 50 ms →\to true.

  • Alternative: volatile non basta (visibilità, non atomicità del controlla-e-decrementa); AtomicInteger.compareAndSet risolve il decremento ma non l'attesa; Semaphore(1) con tryAcquire(attesa, MILLISECONDS).

  • Errori tipici: controllo e modifica separati; if al posto di while; non ricalcolare il tempo residuo (l'attesa totale supera il massimo); non usare notifyAll dopo restituisci; ingoiare InterruptedException.

Teoria collegata