Monitor

I semafori sono estremamente potenti e flessibili ma presentano alcune difficoltà:

• La sincronizzazione è gestita in modo decentralizzato dai singoli thread. Se il programmatore non organizza bene le funzioni di sincronizzazione la manutenzione del codice può risultare difficoltosa
• La gestione di mutex e sincronizzazione diventa complessa quando i thread devono attendere per condizioni non facilmente codificabili tramite un singolo semaforo. Ad esempio, nei lettori-scrittori abbiamo visto che viene eseguita un’attesa dentro una sezione critica.

I Monitor sono un costrutto linguistico [Tony Hoare ’74] che permette di risolvere i due problemi discussi sopra. Da un lato costringe il programmatore a centralizzare tutta la sincronizzazione in un un unico punto del programma (il monitor); dall’altro permette di gestire in modo molto efficace la mutua esclusione, soprattutto nel caso in cui un thread debba attendere su condizione complesse.

I Monitor ricordano le classi della programmazione ad oggetti, in cui procedure e dati sono incapsulati in un’unità modulare: i thread non possono accedere direttamente ai dati ma devono utilizzare le procedure del Monitor.

I Monitor realizzano i seguenti meccanismi di sincronizzazione:

1. Le procedure del monitor vengono eseguite in mutua esclusione;
2. I Monitor forniscono delle variabili speciali dette condition sulle quali sono possibili due operazioni:
   • wait: il thread si mette in attesa sulla coda relativa alla condition. Il mutex del Monitor viene automaticamente rilasciato in modo da permettere ad altri thread di invocare le procedure del Monitor;
   • signal o notify: riattiva il primo thread in attesa sulla coda relativa alla condition. Se non ci sono thread in attesa non ha nessun effetto. Il thread viene eseguito immediatamente nel caso della signal o viene messo in attesa del mutex nel caso della notify (vedere sotto per una descrizione più approfondita).

NOTA: Le condition sono simili ai semafori ma non c’è un valore: sono come semafori sempre rossi in quanto la wait è sempre bloccante e la signal/notify non fa nulla se non ci sono thread in coda.

Differenza tra signal e notify

Quando viene eseguita una signal o notify e viene sbloccato un thread è necessario gestire la presenza simultanea dei due thread nel Monitor. Ci sono due possibilità:

1. signal: Il thread che viene sbloccato dalla signal va subito in esecuzione nel Monitor mentre il thread che ha eseguito la signal attende, su una coda prioritaria, che il thread sbloccato esca dal Monitor;
2. notify: Il thread che viene sbloccato dalla notify si mette in coda per riaccedere al Monitor mentre il thread che ha eseguito la notify prosegue la sua esecuzione.

La differenza fondamentale è che con la signal siamo sicuri che il thread sbloccato verrà eseguito immediatamente mentre con la notify verrà eseguito in base allo scheduler. Questo significa che, con la notify, tra lo sbloccaggio e l’effettiva esecuzione potrebbero essere eseguiti altri thread cambiando eventualmente lo stato del Monitor. Questo comporta una differenza importante nel modo in cui si programma il Monitor che illustriamo qui sotto.

Produttore-Consumatore

Rivediamo ancora una volta l’esempio classico del produttore-consumatore. Avevamo provato a realizzare la sincronizzazione utilizzando un contatore di celle libere ma questo aveva portato a interferenze che necessitavano una sezione critica. I Monitor ci permettono di risolvere facilmente questo problema consentendo, inoltre, di mettere in attesa i thread evitando la tecnica del busy-waiting.

Per prima cosa dobbiamo riscrivere produttore e consumatore in modo che la sincronizzazione sia centralizzata, in stile object-oriented. Chiamiamo pc il Monitor produttore-consumatore. Tale Monitor ha due procedure scrivi e leggi che scrivono e leggono dal buffer condiviso. Il codice risultante è il seguente:

Produttore() {
  while(1) {
    /* produce un elemento d */
    pc.scrivi(d);
  }
}

Consumatore() {
  while(1) {
    d = pc.leggi();
    /* consuma d */
 }
}

Tutta la sincronizzazione avviene quindi nel Monitor che definiamo come segue:

Monitor pc {
  dato buffer[MAX];
  int contatore=0, inserisci=0, preleva=0;
  condition piene,vuote;

  void scrivi(dato d) {
    if (contatore == MAX)
      vuote.wait(); // buffer pieno attendo

    /* scrivi sul buffer */
    buffer[inserisci] = d;
    inserisci=(inserisci+1)%MAX; // Il buffer è circolare

    contatore++; // aggiorno il contatore
    piene.signal();
  }

  dato leggi() {
    if (contatore == 0)
      piene.wait(); // buffer vuoto attendo

    /* leggi dal buffer */
    d = buffer[preleva];
    preleva=(preleva+1)%MAX; // Il buffer è circolare

    contatore--; // aggiorno il contatore
    vuote.signal();
    return d;
  }
}

Analizziamo la procedura scrivi: Per poter scrivere nel buffer è necessario che ci sia una cella vuota. Quindi l’attesa avviene quando il contatore contiene il valore MAX tramite il seguente codice:

    if (contatore == MAX)
      vuote.wait();

Il codice seguente scrive nel buffer. Poi viene incrementato il contatore e vengono sbloccati eventuali thread consumatori in attesa tramite il codice:

    contatore++; 
    piene.signal();

La procedura leggi è analoga.

Esempio di esecuzione

Consideriamo un’esecuzione con un consumatore C e due produttori P1 e P2. Il consumatore esegue pc.leggi() e poiché il contatore vale 0 si blocca sulla condition piene. Il mutex viene rilasciato e P1 può invocare pc.scrivi(d). Lo stato è:

- contatore = 0
- C in attesa sulla coda piene
- P1 invoca pc.scrivi(d)
- P2 in attesa sull'invocazione di pc.scrivi

P1 invoca pc.scrivi(d). Poiché il contatore vale 0 il buffer viene scritto, il contatore viene incrementato e viene eseguito piene.signal(). L’effetto è di sbloccare ed eseguire immediatamente il consumatore C in attesa. In questo modo siamo sicuri che ci sono celle da leggere in quanto nessun altro consumatore può aver letto tra la signal e l’esecuzione di C. Lo stato è il seguente:

- contatore = 1
- C nel Monitor subito dopo la piene.wait()
- P1 in attesa sulla piene.signal() dentro pc.scrivi(d)
- P2 in attesa sull'invocazione di pc.scrivi

Il consumatore legge, decrementa il contatore che varrà nuovamente 0 ed esegue vuote.signal() che non fa nulla non essendoci thread in attesa su tale coda. C esce dal Monitor e viene eseguito P1 in quanto in attesa prioritaria rispetto a P2:

- contatore = 0
- C è uscito dal Monitor
- P1 nel Monitor sulla piene.signal() dentro pc.scrivi(d)
- P2 in attesa sull'invocazione di pc.scrivi

P1 di fatto esce immediatamente dal Monitor e viene eseguito P2 che scriverà nel buffer e aggiornerà il contatore:

- contatore = 1
- C è uscito dal Monitor
- P1 è uscito dal Monitor
- P2 è uscito dal Monitor

Produttore-Consumatore con la notify

Lo schema precedente funziona perché i thread sbloccati dalla signal vengono eseguiti immediatamente. Infatti, se così non fosse, sbloccando, as esempio, un consumatore potrebbe accadere che il dato venga consumato da un altro thread consumatore prima che il thread sbloccato vada in esecuzione. Questo può accadere se utilizziamo la notify invece che la signal. In tale caso dobbiamo racchiudere la wait dentro un ciclo while in modo che se lo stato del Monitor si è modificato il thread possa bloccarsi nuovamente. In questo caso il codice diventa:

    while (contatore == MAX)
      vuote.wait();

e

    contatore++; 
    piene.notify();

Filosofi a cena con raccolta atomica

Una delle soluzioni dello stallo nel problema dei filosofi a cena è la raccolta atomica delle bacchette. Se i filosofi raccolgono le due bacchette assieme non può verificarsi una situazione di attesa circolare. Abbiamo visto che realizzare questa soluzione con i semafori è difficoltosa, in quanto dovremmo rilasciare il mutex nel caso una delle bacchette non fosse disponibile. Avevamo detto che avremmo affrontato il problema con i Monitor.

Scriviamo lo schema del filosofo:

Filosofo(i) {
  while(1) {
    < pensa >

    tavola.raccogli(i);

    < mangia >
    
    tavola.deposita(i);
  }
}

Come per il produttore-consumatore la sincronizzazione è centralizzata in un Monitor e abbiamo due procedure raccogli(i) e deposita(i) che raccolgono e depositano entrambe le bacchette del filosofo i-esimo.

Utilizziamo i monitor con notify che vedremo essere convenienti in questo caso.

Monitor tavola {
  boolean bacchetta[5]={true,true,true,true,true}; // presenza bacchette
  condition filosofo[5]; // code di attesa per i filosofi

  void raccogli(int i) {
    while(!bacchetta[i] || !bacchetta[(i+1)%5])
      filosofo[i].wait(); // attende se una delle bacchette non e' disponibile

    // raccoglie le bacchette in modo atomico
    bacchetta[i] = false;
    bacchetta[(i+1)%5] = false;
  }

  void deposita(int i) {
    // deposita le bacchette
    bacchetta[i] = true;
    bacchetta[(i+1)%5] = true;

    // notifica il filosofo a sx e quello a dx
    filosofo[(i+4)%5].notify();
    filosofo[(i+1)%5].notify();
  }
}

I filosofi attendono se una delle bacchette non è disponibile. La wait è racchiusa in un while perché quando il filosofo viene svegliato deve verificare la presenza di entrambe le bacchette prima di proseguire. Infatti, in questo caso l’uso di signal non cambia l’esecuzione perché dobbiamo comunque riverificare la condizione di bloccaggio. Quando un filosofo deposita le bacchette notifica i filosofi a sinistra e a destra.

Esercizio: raccolta atomica con la signal

Per evitare il while è necessario utilizzare la signal al posto della notify ma si deve anche verificare la presenza di entrambe le bacchette prima di eseguire la signal sul filosofo vicino. Provate a scrivere questa soluzione per esercizio.