Monitor e variabili condizione

1. Oltre i semafori: i monitor

I semafori sono potenti ma di basso livello: il professore sottolinea che sono espressivi e permettono di risolvere qualsiasi problema di interazione, ma il loro uso non e banale perche sono un meccanismo comunque di basso livello, facile da sbagliare — programmi soggetti a errori, difficili da usare in programmi concorrenti complessi. Da qui nasce l'esigenza di costrutti di piu alto livello: i Monitor, introdotti da Brinch Hansen (1973) e generalizzati da Tony Hoare (1974).

Un Monitor e un'astrazione di dati per la programmazione concorrente che incapsula in un'unica entita:

• Lo stato (variabili permanenti, private all'interno del monitor)
• Le operazioni (procedure pubbliche che costituiscono l'interfaccia)
• La politica di concorrenza (mutua esclusione implicita + sincronizzazione esplicita)

monitor MonitorName {
    // variabili permanenti (stato privato)
    // codice di inizializzazione
    procedure (o entry) NomeOp(params) {
        // corpo
    }
}

Proprieta fondamentali

• Mutua esclusione implicita: le procedure del monitor si eseguono automaticamente in mutua esclusione — al piu un processo alla volta puo eseguire una procedura del monitor. Non serve alcun meccanismo esplicito come wait/signal per la mutua esclusione. I processi che trovano il monitor occupato vengono sospesi.
• Incapsulamento: solo le procedure (l'interfaccia) sono visibili all'esterno; le variabili permanenti sono accessibili solo dall'interno.
• Nessuna coda esplicita: non c'e una coda associata alle procedure del monitor — la politica di scheduling e lasciata all'implementazione. Questo puo portare a starvation.
• Sincronizzazione esplicita: tramite variabili condizione, usate per ritardare un processo che non puo continuare fino a quando lo stato del monitor non soddisfa una certa condizione booleana.

Il professore nota che il monitor e una generalizzazione del concetto di kernel dei sistemi operativi: invece di avere un unico kernel centralizzato che gestisce tutte le sezioni critiche, ogni monitor e un "mini-kernel" decentralizzato specializzato per un dato condiviso. E anche una generalizzazione del concetto di oggetto nella OOP: come un modulo OOP che incapsula dati + operazioni + politica di sincronizzazione/mutua esclusione, includendo il costrutto di base per garantire la correttezza dell'accesso concorrente.

L'esempio piu semplice e un contatore thread-safe:

monitor Counter {
    int count;

    procedure inc() {
        count := count + 1
    }

    procedure getValue(): int {
        return count
    }
}

L'esempio del contatore mostra la potenza dell'astrazione: non c'e alcun wait/signal esplicito per la mutua esclusione. Se due processi chiamano inc() contemporaneamente, il monitor garantisce l'atomicita: due thread non eseguiranno mai inc() nello stesso momento. Il docente sottolinea che la mutua esclusione e implicita, fornita dall'implementazione del monitor: le operazioni sono eseguite atomicamente le une rispetto alle altre, senza che il programmatore usi semafori o altri meccanismi.

2. Variabili condizione: operazioni e semantica

La sola mutua esclusione non basta: serve anche la sincronizzazione. Le variabili condizione (condition variables) sono un tipo di dato primitivo che i monitor mettono a disposizione per la sincronizzazione esplicita: permettono di sospendere (waitC) e risvegliare (signalC) processi all'interno di un monitor, rappresentando condizioni (eventi) sullo stato del monitor in attesa di essere soddisfatte. Ogni variabile condizione e associata a una coda FIFO di processi bloccati su quella condizione.

Operazioni

Formalmente, le due operazioni fondamentali si definiscono cosi:

waitC(cond) = < append p to cond.queue
                p.state := blocked
                monitor.lock := release >

signalC(cond) = < if cond.queue != empty
                    q := remove head of cond.queue
                    q.state := ready >

Esempio: SynchCell (cella sincronizzata)

Una cella che permette a un processo di depositare un valore e a un altro di prelevarlo, con sincronizzazione automatica:

monitor SynchCell {
    int value;
    boolean available := false;
    cond isAvail;

    procedure set(int v) {
        value := v
        available := true
        signalC(isAvail)
    }

    procedure get(): int {
        if (!available)
            waitC(isAvail)
        return value
    }
}

Un processo chiama get() ma se il valore non e ancora disponibile (available = false), si sospende su isAvail. Quando un altro processo chiama set(), imposta il valore e segnala isAvail, risvegliando il processo in attesa. Il professore sottolinea che il waitC rilascia automaticamente il lock del monitor, permettendo cosi ad altri processi di chiamare set() per fornire il dato.

Il professore fa anche notare: se piu processi sono in waitC su isAvail, un singolo signalC ne sveglia solo uno. Per svegliarli tutti, si usa signalAllC — utile quando non si sa quanti processi stanno aspettando.

3. Discipline di segnalazione

Quando un processo esegue una signalC, sia il signaller che il signalled potrebbero essere pronti a proseguire nel monitor, ma solo uno puo avere accesso esclusivo: si pone il problema di chi debba continuare, il processo che segnala o quello che viene risvegliato? Le tre discipline classiche differiscono per l'ordine di priorita tra signaller (S), waiting (W — processi in attesa sulla condizione) ed external processes (E — processi bloccati sull'entry del monitor):

In forma tabellare compatta:

Legenda: S = segnalante, W = processi in waitC, E = processi bloccati sull'entry del monitor.

Conseguenza pratica: if vs while

A seconda della disciplina di segnalazione, il test sulla condizione dopo un waitC puo essere un if o un while: l'uso del while e sempre sicuro ed e necessario con Signal and Continue, perche la condizione potrebbe essere cambiata da un altro processo tra il risveglio e la riacquisizione del lock. Il professore nota che la scelta della disciplina ha implicazioni pratiche: con Signal & Continue, dopo un waitC(cond) e consigliabile usare while (!condizione) invece di if (!condizione) per gestire possibili risvegli spuri (il signalled potrebbe trovare la condizione ancora falsa perche un altro processo l'ha cambiata nel frattempo).

// Con Signal and Wait (preemptive): if basta (ma while e sempre sicuro)
if (!B) waitC(cond)

// Con Signal and Continue: while necessario!
while (!B) waitC(cond)

4. Producer-Consumer con monitor

Ecco l'implementazione del bounded buffer come monitor, che incapsula automaticamente la mutua esclusione sull'accesso al buffer e la sincronizzazione tramite variabili condizione. Il buffer e implementato come array circolare:

monitor BoundedBuffer {
    int[] elems := new int[MAX_ELEMS]
    int first := 0, last := 0
    cond notFull, notEmpty

    procedure put(int elem) {
        if ((last + 1) % MAX_ELEMS = first)
            waitC(notFull)
        elems[last] := elem
        last := (last + 1) % MAX_ELEMS
        signalC(notEmpty)
    }

    procedure take(): int {
        if (first = last)
            waitC(notEmpty)
        int elem := elems[first]
        first := (first + 1) % MAX_ELEMS
        signalC(notFull)
        return elem
    }
}

// Producer                    // Consumer
loop                          loop
    ElemType el := produce        ElemType el := BoundedBuffer.take()
    BoundedBuffer.put(el)         consume(el)

Il codice produttore e consumatore diventa estremamente semplice: chiamano rispettivamente put e take sul monitor, senza preoccuparsi di lock espliciti o semafori. La variabile condizione notFull blocca il produttore se il buffer e pieno; notEmpty blocca il consumatore se il buffer e vuoto. Quando un produttore aggiunge un elemento, segnala notEmpty per sbloccare un eventuale consumatore in attesa; quando un consumatore preleva, segnala notFull per sbloccare un eventuale produttore.

Il professore commenta: "Questa soluzione e molto piu semplice e chiara rispetto a quella con semafori. Il monitor gestisce automaticamente la mutua esclusione sul buffer, e le variabili condizione notFull/notEmpty gestiscono la sincronizzazione."

5. Readers-and-Writers con monitor

L'implementazione del RWLock come monitor mostra la potenza delle variabili condizione per gestire politiche di sincronizzazione complesse: la politica di sincronizzazione viene incapsulata nella struttura dati stessa, usando due variabili di condizione (okToRead, okToWrite). Ecco la versione con disciplina Signal & Continue:

// Invariant: (nr == 0 or nw == 0) and (nw <= 1)
monitor RWLock {
    int nr, nw := 0
    cond okToRead, okToWrite

    procedure request_read() {
        while (nw > 0)
            waitC(okToRead)
        nr := nr + 1
    }

    procedure release_read() {
        nr := nr - 1
        if nr = 0
            signalC(okToWrite)
    }

    procedure request_write() {
        while (nr > 0 or nw > 0)
            waitC(okToWrite)
        nw := nw + 1
    }

    procedure release_write() {
        nw := nw - 1
        signalC(okToWrite)
        signalAllC(okToRead)
    }
}

L'invariante fondamentale: (nr == 0 or nw == 0) and (nw <= 1) — o ci sono solo reader, o solo un writer (o nessuno). Questa soluzione garantisce che i lettori non si escludano tra loro ma escludano gli scrittori, e viceversa. release_write() fa due segnalazioni: signalC(okToWrite) per sbloccare un writer in attesa (se c'e), e signalAllC(okToRead) per risvegliare tutti i reader in attesa.

Il docente sottolinea l'uso di while invece di if nella condizione di wait — pattern fondamentale per gestire la riapertura della condizione dopo signal (soprattutto con semantica Signal & Continue).

Il professore mostra anche una seconda versione, piu compatta, che usa il pattern "cascading signal": dopo startRead(), il primo reader sbloccato chiama a sua volta signalC(okToRead) per risvegliare il successivo, creando una catena. Questa versione elimina il while e torna a usare if per il controllo delle condizioni.

procedure startRead() {
  if writers != 0
    waitC(okToRead);
  readers := readers + 1;
  signalC(okToRead);    { risveglia il prossimo reader in cascata }
}

procedure endWrite() {
  writers := writers - 1;
  if emptyC(okToRead)
    then signalC(okToWrite)   { se nessun reader aspetta, sblocca un writer }
    else signalC(okToRead);   { altrimenti sblocca il primo reader }
}

6. Monitor in Java: synchronized, wait, notify

Java offre due approcci per implementare monitor. Il primo, di piu basso livello, sfrutta i meccanismi nativi della JVM: synchronized, wait, notify, notifyAll.

Quando un metodo e dichiarato synchronized, la JVM genera automaticamente le istruzioni bytecode monitorenter e monitorexit. Ogni oggetto Java ha un intrinsic lock (o monitor lock) associato.

Pattern del monitor in Java

Regole per implementare il monitor pattern:

1. Tutti i metodi pubblici devono essere synchronized
2. Nessun campo pubblico
3. Il codice del monitor deve accedere solo a oggetti completamente confinati al suo interno
4. E disponibile un'unica variabile di condizione implicita (l'oggetto stesso)

Esempio: SynchCell

Semantica di wait

• Se il thread e stato interrotto, wait lancia InterruptedException
• Altrimenti, il thread viene bloccato e posto nel wait set dell'oggetto
• Il lock di sincronizzazione viene rilasciato (anche se rientrante)
• Al risveglio, il lock viene riacquisito prima di proseguire

Semantica di notify e notifyAll

• notify rimuove un thread arbitrario dal wait set (nessuna garanzia su quale)
• Il thread risvegliato deve riacquisire il lock e si blocca finche il notificante non rilascia il lock
• notifyAll opera su tutti i thread nel wait set (ma riacquisiranno il lock uno alla volta)

Spurious wakeup e il pattern while

La documentazione Java avverte: "A thread can also wake up without being notified, interrupted, or timing out, a so-called spurious wakeup." Per questo il pattern corretto e sempre wrappare wait in un ciclo while che riverifica la condizione:

synchronized void get() {
    while (!available) {    // SEMPRE while, mai if!
        try { wait(); } catch (InterruptedException ex) {}
    }
    return value;
}

Un'altra limitazione del meccanismo di base: piu predicati di condizione diversi devono essere associati alla stessa unica variabile di condizione (l'oggetto). Questo forza l'uso di notifyAll invece di notify, e il ciclo while permette a ogni thread di riverificare la propria condizione specifica al risveglio.

7. Bounded buffer come monitor in Java

Implementiamo il bounded buffer produttori-consumatori usando il monitor pattern in Java, con synchronized/wait/notifyAll.

public class BoundedBuffer<Item> {
    private int first, last, count;
    private Item[] buffer;

    public BoundedBuffer(int size) {
        first = last = count = 0;
        buffer = (Item[]) new Object[size];
    }

    public synchronized void put(Item item) throws InterruptedException {
        while (isFull()) { wait(); }
        last = (last + 1) % buffer.length;
        count++;
        buffer[last] = item;
        notifyAll();
    }

    public synchronized Item get() throws InterruptedException {
        while (isEmpty()) { wait(); }
        first = (first + 1) % buffer.length;
        count--;
        notifyAll();
        return buffer[first];
    }

    public synchronized boolean isEmpty() { return count == 0; }
    public synchronized boolean isFull() { return count == buffer.length; }
}

8. ReentrantLock e Condition: monitor di alto livello

La libreria java.util.concurrent fornisce classi per implementare monitor con variabili di condizione multiple, superando le limitazioni del meccanismo synchronized.

La classe ReentrantLock e un'implementazione rientrante di lock mutex. Da un lock si possono creare multiple Condition, che rappresentano variabili di condizione distinte.

SynchCell con ReentrantLock

public class SynchCell2 {
    private int value;
    private boolean available;
    private Lock mutex;
    private Condition isAvail;

    public SynchCell2() {
        available = false;
        mutex = new ReentrantLock();
        isAvail = mutex.newCondition();
    }

    public void set(int v) {
        try {
            mutex.lock();
            value = v;
            available = true;
            isAvail.signalAll();
        } finally {
            mutex.unlock();
        }
    }

    public int get() {
        try {
            mutex.lock();
            if (!available) {
                try { isAvail.await(); } catch (InterruptedException ex) {}
            }
            return value;
        } finally {
            mutex.unlock();
        }
    }
}

Note importanti: i metodi non sono synchronized; il lock e gestito esplicitamente con lock()/unlock(); e essenziale il blocco finally per garantire il rilascio anche in caso di eccezioni; Condition offre await(), signal(), signalAll() al posto di wait/notify/notifyAll.

BoundedBuffer con condition variabili multiple

Con ReentrantLock possiamo finalmente avere notFull e notEmpty come variabili di condizione separate, permettendo segnalazioni selettive:

Notate: nel put si fa notEmpty.signal() (sveglia solo consumatori), nel get si fa notFull.signal() (sveglia solo produttori). Nessun overhead di risvegli inutili!

9. Semantica di segnalazione in Java: effetti indesiderati

Il professore ha dedicato una parte significativa della lezione a mostrare un comportamento curioso della semantica di segnalazione in Java. La semantica adottata (Signal-and-Continue con E = W < S) puo portare a ordini di esecuzione controintuitivi.

Scenario dimostrativo: Tre thread competono per un monitor. T1 entra, esegue await() e si sospende. T2 entra, esegue signal() e rilascia. T3 sta aspettando di entrare. Chi ottiene il lock dopo T2?

Con E = W < S, il thread risvegliato (T1) compete ad armi pari con i thread in attesa sul lock (T3). Dipende dall'implementazione della JVM e dallo scheduler del sistema operativo chi entra per primo. Nell'esempio mostrato, T3 e entrato prima di T1.

OUTPUT OSSERVATO:
First thread started.
First thread inside, going to wait
Second thread started.
Second thread inside
Third thread started.
Second thread inside, going to signal
Second thread inside signaled.
Third thread inside.            // <- T3 entra prima di T1!
First thread unblocked.         // <- T1 solo dopo T3

Errore comune: Confondere wait/notify (meccanismi di base su Object) con await/signal (da Condition). Il professore ha mostrato il caso in cui, usando ReentrantLock, si chiama erroneamente wait() invece di await() o notify invece di signal, cosa che causa IllegalMonitorStateException o comportamenti errati.

10. Monitor e semafori: equivalenza espressiva

I monitor possono essere realizzati usando semafori come building blocks di livello piu basso. Per ogni monitor servono:

• Un semaforo mutex (inizializzato a 1) per garantire la mutua esclusione: wait(mutex) in prologo, signal(mutex) in epilogo di ogni operazione
• Per ogni variabile condizione cond, un semaforo condsem e un contatore condcount per tracciare quanti processi sono in attesa

Le due discipline si implementano cosi:

Prologo per ogni operazione:
  wait(mutex)
Epilogo per ogni operazione:
  signal(mutex)

waitC(cond) =
  condcount++;
  signal(mutex);     { rilascia il lock del monitor }
  wait(condsem);     { si blocca sulla condizione }
  wait(mutex);       { quando si risveglia, riacquisisce il lock }

signalC(cond) =
  if (condcount > 0) {
    condcount--;
    signal(condsem); { sblocca un processo in attesa }
  }

Prologo per ogni operazione:
  wait(mutex)
Epilogo per ogni operazione:
  signal(mutex)

waitC(cond) =
  condcount++;
  signal(mutex);
  wait(condsem);     { si blocca — verra sbloccato da signalC }

signalC(cond) =
  if (condcount > 0) {
    condcount--;
    signal(condsem); { sblocca il processo in attesa }
    wait(mutex);     { il signaller si mette in attesa del lock }
  }

Implementare un semaforo con un monitor

Chiudendo il cerchio, si puo anche implementare un semaforo usando un monitor, dimostrando l'equivalenza espressiva dei due costrutti:

monitor Semaphore {
  integer s := <InitValue>
  cond notZero;

  procedure wait() {
    if s = 0
      waitC(notZero);
    s := s - 1;
  }

  procedure signal() {
    s := s + 1;
    signalC(notZero);
  }
}

Il professore mostra anche una versione alternativa che separa il caso in cui s > 0 (decrementa senza bloccare) dal caso s = 0 (si blocca). Entrambe le versioni sono corrette. Potete esplorarla riga per riga qui sotto:

11. Confronto: semafori vs variabili di condizione

Il professore dedica una slide specifica al confronto, che e importante per evitare confusioni:

Verifica le tue conoscenze