Programmazione con i Monitor

Semafori con i Monitor

Vediamo come realizzare un semaforo contatore tramite Monitor. Consideriamo il problema dei filosofi a cena in cui vogliamo limitare il numero di filosofi a tavola a 4. Con i semafori è sufficiente inizializzare un semaforo al valore 4 e eseguire una P(S) prima di raccogliere le bacchette e una V(S) dopo che le bacchette sono state depositate.

Estendiamo il Monitor tavola con due nuove procedure siediti e alzati che vengono invocate come segue:

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

    tavola.siediti(); // attende una delle 4 sedie disponibili
    tavola.raccogli(i);

    < mangia >
    
    tavola.deposita(i);
    tavola.alzati(); // libera la sedia
  }
}

Per realizzare tali procedure è sufficiente un contatore per il numero di sedie libere e una condition per la coda di attesa:

Monitor tavola {
  int sedie=4;
  condition sedia;
  ...
  void siediti() {
    while(sedie==0)
      sedia.wait(); // attende una sedia libera
    
    // occupa una sedia
    sedie--;
  }

  void alzati() {
    sedie++; // libera una sedia
    sedia.notify(); // sblocca un thread in attesa di un sedia
  }
}

La procedura siediti può essere invocata 4 volte prima di diventare bloccante. La procedura alzati incrementa il contatore e sblocca un thread in coda. Di fatto siediti e alzati si comportano come P e V su un semaforo inizializzato a 4.

Notare che con questa soluzione non è più necessario che le bacchette vengano raccolte in maniera atomica in quanto lo stallo viene evitato.

Esercizio: Provare a scrivere la soluzione in cui le bacchette vengono raccolte singolarmente utilizzando le procedure alzati e siediti per prevenire lo stallo.

Lettori e scrittori: la notifyAll

Rivediamo il problema dei lettori e scrittori che avevamo risolto tramite semafori.

Abbiamo due tipologie di thread:

Lettore {
  while(1) {
    ...
    rw.ini_leggi();

    < legge i dati >

    rw.end_leggi();
    ...
  }
}

Scrittore {
  while(1) {
    ...
    rw.ini_scrivi();

    < modifica i dati >

    rw.end_scrivi();
    ...
  }
}

Dobbiamo realizzare il Monitor rw in modo che sia garantito l’accesso a un numero arbitrario di lettori oppure a un solo scrittore.

È importante capire quale informazione è necessaria per realizzare la sincronizzazione. In questo caso specifico dobbiamo sapere se c’è uno scrittore in sezione critica oppure il numero esatto di lettori in sezione critica. I lettori entrano se non c’è uno scrittore, lo scrittore entra se non c’è nessuno in sezione critica.

Monitor rw {
  int n_lettori=0; // n. lettori in sezione critica
  boolean scrittore=false; // scrittore in sezione critica
  condition c; // coda di attesa

  void ini_leggi() {
    while(scrittore)
      c.wait(); // attende se c'è uno scrittore
    n_lettori++; // il lettore entra
  }

  void end_leggi() {
    n_lettori--; // il lettore esce
    if (n_lettori==0)
      c.notify(); // l'ultimo lettore sblocca eventuali scrittori in attesa
  }

  void ini_scrivi() {
    while(scrittore || n_lettori > 0)
      c.wait(); // attende se c'è uno scrittore o qualche lettore
    scrittore=true; // lo scrittore entra
  }

  void end_scrivi() {
    scrittore=false; // lo scrittore esce
    c.notifyAll(); // lo scrittore sblocca tutti i thread in attesa
  }
}

Come vediamo sopra, i monitor permettono di programmare la sincronizzazione tramite variabili senza preoccuparsi della mutua esclusione che viene garantita automaticamente.

In end_scrivi() notiamo l’uso di notifyAll() sulla condition c. Questa operazione sblocca tutti i thread in coda. In questo caso specifico è necessario sbloccare tutti i thread perché eventuali lettori in attesa riescano ad entrare tutti in sezione critica. Notare che grazie al ciclo while che racchiude le wait tutti i thread riverificheranno la condizione di attesa prima di proseguire.

La notifyAll() ha anche la particolarità di affidare allo scheduler di sistema la scelta del prossimo thread che entrerà in sezione critica. Generalmente questo evita starvation grazie ai meccanismi anti-starvation presenti negli scheduler di tutti i moderni sistemi operativi.

Monitor rw {
  ...
  queue q;

  void ini_leggi(id) {
    q.add(id); // si accoda
    // attende se non e' il primo della coda o se c'è uno scrittore
    while(q.top()!=id || scrittore)
      c.wait(); 
    q.remove(); // si toglie dalla coda (e' il primo!)
    n_lettori++; // il lettore entra
    c.notifyAll(); // notifica eventuali altri lettori in attesa
  }

  void end_leggi(id) {
    n_lettori--; // il lettore esce
    if (n_lettori==0)
      c.notifyAll(); // l'ultimo lettore sblocca tutti i thread
  }

  void ini_scrivi(id) {
    q.add(id); // si accoda
    // attende se non e' il primo della coda o se c'è uno scrittore o qualche lettore
    while(q.top()!=id || scrittore || n_lettori > 0)
      c.wait(); 
    q.remove(); // si toglie dalla coda (e' il primo!)
    scrittore=true; // lo scrittore entra
  }

  void end_scrivi(id) {
    scrittore=false; // lo scrittore esce
    c.notifyAll(); // lo scrittore sblocca tutti i thread in attesa
  }
}