Nome: Sezione Critica
Contesto: abbiamo una o piu' risorse condivise e l'accesso a tali risorse
 deve avvenire in mutua esclusione
Soluzione:
   Sem M = 1;

   P(M);  // entrare in sezione critica
   ...
   V(M);  // lasciare la sezione critica

Problema:
  A volte e' necessario valutare il valore delle risorse condivise per
  sapere se sia possibile o meno proseguire nella computazione.

Soluzione 1 errata:
   Sem M = 1;
   shared dato;

   if (C(shared) {  // NO! Non sono in sezione critica. Dato alterabile.
     P(M);  // entrare in sezione critica
     ...
     V(M);  // lasciare la sezione critica
   }

Soluzione 2 errata:
   
   Sem M = 1;
   Sem S = 0;  // semaforo di sospensione
   shared dato;

   P(M);  // entrare in sezione critica
     if (C(shared) {
       ...
     } else {
       P(S);  // deadlock: nessun altro entrera' mai piu' in sezione critica
     }
   V(M);  // lasciare la sezione critica

Soluzione 3 (sub-ottimale, alla Java):

   Sem M = 1;
   Sem S = 0;  // semaforo di sospensione
   shared dato;

   P(M);  // entrare in sezione critica
     while (!C(shared) {
       V(M); // lascio la sezione critica
       P(S);
             <-- qua si puo' inserire qualcuno che cambia shared
       P(M);
     }
     ...
   V(M);  // lasciare la sezione critica

   Problemi: starvation, spreco di CPU, no FIFO

Soluzione 4:

   Sem M = 1;
   Sem S = 0;  // semaforo di sospensione
   shared dato;

   P(M);  // entrare in sezione critica
     if (!C(shared) {
       V(M); // lascio la sezione critica
       P(S); // ASSUMIAMO DI ESSERE IN SEZIONE CRITICA AL RISVEGLIO
6*     ...   // QUA SIAMO CERTI CHE C(shared) VALGA!
     }
7*   ...
8* V(M);  // lasciare la sezione critica


  Come?  Tecnica del passaggio del testimone.

  Sia il seguente codice quello eseguito dal processo che risveglia
  il processo precedente.

1 ...
2*P(M); // entra in sezione critica
3*..  // altera i dati condivisi fra cui shared
4*if(C(shared)) {
5*  V(S);  // RISVEGLIA L'ALTRO PROCESSO E PASSA LA SEZIONE CRITICA
6   ....
  } else {
    V(M);
  }
7 ...


Problema ulteriore:
  La soluzione precedenta si basa sull'assunzione che la condizione
  C(shared) sia valutabile esclusivamente a partire dai dati condivisi.
  Questo perche' deve essere valutata da entrambi i processi.
  
  Come fare quando la condizione coinvolge anche dati non condivisi?
    Caso A: i dati sono sensibili e non li vogliamo condividere.
            Soluzione: si torna alla soluzione alla Java. Il processo che
            risveglia il processo sospeso esegue il seguente codice:

 ...
*P(M); // entra in sezione critica
*..    // altera i dati condivisi fra cui shared
*V(S); // nel dubbio risveglio l'altro processo
*....
*V(M);
 ...

    Caso B: i dati non sono sensibili e possono essere condivisi
      Caso B.1:  non mi costa troppo (in spazio) condividere sempre tutti
                 i dati

        Problemi:
           a) spreco di memoria (forse)
           b) aumenta la possibilita' di bug/errori

      Caso B.2:
        Osservazione: al processo che deve risvegliare non servono i dati
          privati di tutti gli altri processi, ma solo quelli del processo
          che si e' sospeso.
        Soluzione: il processo che si sospende subito prima di rilasciare
          la sezione critica condivide i suoi dati privati che servono a
          testare la condizione.

======================================================

Nome: letargo spontaneo
Contesto: un processo vuole decidere autonomamente di sospendersi;
          qualunque altro processo puo' svegliarlo ma solo *dopo* che
          si e' addormentato

Soluzione:

Sem S = 0;  // semaforo di sospensione
bool sleeping = false;
Sem M = 1; // mutex

P {  // che si vuole sospendere autonomamente
   ...
   P(M);
   sleeping = true;
   V(M);
   P(S);   // si sospende perche' S vale sempre 0
   ...
}

Q { // che vuole svegliare P solo se P e' gia' sospeso?

   P(M);
   if(sleeping) {
     sleeping = false;
     V(S);  // scelta possibile: passaggio del testimone o meno
   }
}

======================================================

Soluzione piu' semplice ai filosofi a cena:

Sem S[5] = {0, ...., 0};
Sem M = 1;
bool b[5] = {1, ...., 1};
bool s[5] = {0, ...., 0};

Philo[i] {
    while (1) {
      pensa();
      P(M);
      if(!b[i] || !b[(i+1)%5]) {
          s[i] = 1; // il processo si sospende
          V(M);
          P(S[i]);  // PASSAGGIO DEL TESTIMONE
      }
      b[i] = 0;
      b[(i+1)%5] = 0;
      V(M);
      mangio();
      P(M); 
      b[i] = 1;
      b[(i+1)%5] = 1;
      if (b[(i-1)%5] == 1 && s[(i-1)%5] == 1) {
         V(S[(i-1)%5]); // PASSAGGIO DEL TESTIMONE
         P(M);
         if (b[(i+2)%5] == 1 && s[(i+1)%5) {
           V(S[(i+1)%5]); // PASSAGGIO DEL TESTIMONE
         } else {
           V(M);
         }
      } else if (b[(i+2)%5 == 1 && s[(i+1)%5) {
         V(S[(i+1)%5]); // PASSAGGIO DEL TESTIMONE
         if (b[(i-1)%5] == 1 && s[(i-1)%5) {
           V(S[(i-1)%5]); // PASSAGGIO DEL TESTIMONE
         } else {
           V(M);
         }
      } else {
         V(M);
      }
}


======================================================================
Problema: i processi debbono risvegliarsi in ordine non FIFO
Soluzione:
   invece di usare un unico semaforo S su cui tutti si sospendono,
   ogni processo ha un proprio semaforo S[i], sul quale si sospende
   facendo P(S[i]). Chi lo vuole risvegliare lo fa con V(S[j]).
   Problema: da dove ricava j?
   Idea: quando il processo Pi si sospende prima pubblica il proprio pid()
   i in una qualche struttura dati. Il processo che vuole risvegliare pesca
   da questa struttura dati con una politica != FIFO.

Esempio: coda con priorita' (2)

   Sem M = 1;
   bool libero = 1;
   queue coda[N];  // N e' il numero di priorita'
   Sem S[M]; // M e' il numero di processi nel sistema

   P[i,p] {  // processo di indice i con priorita' p
     P(M);
     if(!libero) {
       queue[p].push(i);
       V(M);
       P(S[i]);
     } else {
       V(M);
     }
     .....  // viene servito
     P(M);
     int k = 0;
     int svegliato = 0;
     while(!svegliato) {
       if(empty(queue[k]))
         k++;
       else {
         j = queue[k].pop();
         svegliato = 1;
         V(S[j]);
       }
     }
     V(M);
  }

Stessa idea di prima: empty(queue[k]) si chiede se c'e' qualcuno di sospeso
prima di riattivarlo.