Aula de Exercícios - 23/03/99

Considere o problema dos macacos (um clássico de SC1), apresentado no livro texto. O problema trata de um grupo de macacos que utiliza uma corda para atravessar um precipício. Vários macacos podem atravessar simultaneamente, desde que eles estejam cruzando na mesma direção. Se um macaco cruzando para o leste encontra uma macaco cruzando para oeste no meio da corda, ocorre deadlock, porque um não consegue cruzar com o outro e nem andar para trás.

Abaixo são apresentadas quatro soluções para o problema, onde o comportamento dos macacos é modelado com o uso de semáforos.

1. Em cada uma delas
   1. Faça uma análise explicando se a solução permite que os macacos atravessem o precipício sem ocorrência de deadlock.
   2. Caso a resposta no item anterior seja afirmativa, discuta as desvantagens apresentadas pela solução (por exemplo, possibilidade de starvation).

   1. #define FALSE 0
      #define TRUE 1
      sem mutex; mutex.valor = 1; 
      int cruzandoOeste = FALSE; int cruzandoLeste = FALSE;
      
      CruzaOeste()                    CruzaLeste()
      {                               /* simetrico a CruzaOeste() */
        int consegui = FALSE;
        repeat
          P(mutex)
          if (!cruzandoLeste){
            cruzandoOeste = TRUE;
            consegui = TRUE;
          }
          V(mutex);
        until (consegui);
        Cruza();
        P(mutex);
        cruzandoOeste = FALSE;
        V(mutex);
      }

   2.   sem oeste; oeste.valor = 0; 
        sem leste; leste.valor = 1;
        
        CruzaOeste()         CruzaLeste()
        {                    {
          P(oeste);            P(leste)
          Cruza();             Cruza();
          V(leste);            V(oeste);
        }                    }

   3. int cruzandoLeste = 0; int queremLeste = 0;
      int cruzandoOeste = 0; int queremOeste = 0;
      sem oeste; oeste.valor = 0; 
      sem leste; leste.valor = 0; 
      sem mutex; mutex.valor = 1;
      
      CruzaOeste() {                          CruzaLeste() {
      
        P(mutex);                               P(mutex);   
        cruzandoOeste++;                        cruzandoLeste++;
        if (!cruzandoLeste)                     if (!cruzandoOeste)
          V(oeste);                               V(leste);
        else                                    else
          queremOeste++;                          queremLeste++;
        V(mutex);                               V(mutex);
        P(oeste);                               P(leste);
      
        Cruza();                                Cruza();
      
        P(mutex);                               P(mutex);
        cruzandoOeste--;                        cruzandoLeste--;
        if (!cruzandoOeste && queremLeste)      if (!cruzandoLeste && queremOeste)  
        {                                       {
          queremLeste--;                          queremOeste--;
          V(leste);                               V(oeste);
        }                                       }
        V(mutex);                               V(mutex);
      }                                       }

2. Escolha uma solução que lhe pareça mais próxima da ``ideal'' e tente modificá-la para torná-la correta ou mais justa.