01:  sem_t garfo[5] = {1,1,1,1,1};
02:  sem_t copo = 3;
03:
04: F0, F1, F2:                         F3, F4:
05:   while (1) {                         while (1) {   
06:     pensa();                            pensa();
07:     sem_wait(&copo);                    sem_wait(&garfo[i]);
08:     sem_wait(&garfo[i]);                sem_wait(&garfo[(i+1)%N]);
09:     sem_wait(&garfo[(i+1)%N]);          sem_wait(&copo); 
10:     come();                             come();
11:     sem_post(&copo);                    sem_post(&copo);
12:     sem_post(&garfo[i]);                sem_post(&garfo[i]);
13:     sem_post(&garfo[(i+1)%N]);          sem_post(&garfo[(i+1)%N]);
14:   }                                   } 

Erros mais comuns:

• Dizer que o sistema não está sujeito a deadlock.
• Descrição incompleta do cenário de deadlock (por exemplo, dizer apenas que cada filósofo irá pegar um garfo).

volatile int n=0;   /* Variável compartilhada para o contrle do número
                       de execuções da função faz_alguma_coisa() */
#define NMAX 100 

/* Declaração e inicialização de um lock simples para controlar o 
   acesso à variável n. Para adquirir ou liberar o lock, considere as funções: 
      int pthread_mutex_lock(pthread_mutex_t *mutex);
      int pthread_mutex_unlock(pthread_mutex_t *mutex);
*/
pthread_mutex_t lock_n = PTHREAD_MUTEX_INITIALIZER;

/* Função auxiliar que deve ser invocada exatamente uma vez para 
   cada valor de i entre 0 e NMAX-1. */
void faz_alguma_coisa(int i) {
   /* ..... */
}

/* Função a ser executada por um grupo de threads */
void *f_thr(void *v) {
  int i;
  while ((i = proximo()) != NMAX) {
    faz_alguma_coisa(i);
  }
  return NULL;
}

/* Função auxiliar para controle da execução de faz_alguma_coisa() */
int proximo() {
}

int proximo() {
  int retorno;
  pthread_mutex_lock(&lock_n);
  retorno = n;
  if (retorno < NMAX) 
    n++;
  pthread_mutex_unlock(&lock_n);
  return retorno;
}

Erros mais comuns:

• Não retornar o valor zero (fazer o incremento antes de guardar o valor de retorno):

  int proximo() {
    int retorno;
    pthread_mutex_lock(&lock_n);
     if (retorno < NMAX) 
      n++;
    retorno = n;
    pthread_mutex_unlock(&lock_n);
    return retorno;
  }
  

• Não limitar o valor de n:

  int proximo() {
    int retorno;
    pthread_mutex_lock(&lock_n);
    retorno = n++;
    pthread_mutex_unlock(&lock_n);
    return retorno;
  }
  

• Incrementar na região protegida pelo lock, mas retornar valor de n na região desprotegida. Neste caso, não há garantia de valores únicos entre 0..NMAX-1.

  int proximo() {
    pthread_mutex_lock(&lock_n);
    if (n < NMAX) 
      n++;
    pthread_mutex_unlock(&lock_n);
    return n;
  }
  

• Não utilizar corretamente as funções pthread_mutex_lock e pthread_mutex_unlock.

Avalie se esta função garante ou não: (a) exclusão mútua, (b) ausência de deadlock e (c) ausência de starvation.

01: int atomic_inc(int *i);  /* Incrementa *i atomicamente
02:                             retorna o valor de *i depois da operação */    
03: int futex_wait(void *addr, int val1);  /* Bloqueia se *addr == val1 */
04: int futex_wake(void *addr, int n);     /* Acorda até n threads */
05:
06:  typedef struct {  
07:    volatile int senha;
08:    volatile int proxima;
09:  } mutex_t;
10:
11:  void mutex_init(mutex_t *m) {
12:     m->senha = 0;
13:     m-> proxima = 1; 
14:  }
15:
16:  void mutex_lock(mutex_t *m) {
17:    int minha_senha = atomic_inc(m->senha);    
18:    int prox = m->proxima;   
19:      
20:    while (prox != minha_senha) {
21:      futex_wait(&m->proxima, prox);
21.5:    prox = m->proxima;  /* linha adicional sugerida na lousa */ }
22:  }
23:
24: void mutex_unlock(mutex_t *m) {
25:   m->proxima++;
21:   if (m->senha >= m->proxima)
22:     futex_wake(&m->proxima, 1);
23: }

Respostas esperadas As respostas podiam considerar que sempre havia um uso correto das funções mutex_lock e mutex_unlock (por exemplo, nenhuma thread chamaria mutex_unlock sem primeiro ter executado mutex_lock).

• Código com a alteração sugerida
  • (a) Há garantia de exclusão mútua visto que as senhas são obtidas via incremento atômico e o while da linha 20 garante o bloqueio de threads com senhas maiores do que a que pode entrar na região crítica.
  • (b) Existe a possibilidade de deadlock. Considere que T0 está com o lock, T1 pegou uma senha x e T2 pegou x+1. Se T2 executar futex_wait antes de T1, na hora que T2 for acordada ela verá que não é ainda a vez dela e voltará a dormir. A thread T1 não será acordada e o sistema entrará em deadlock. No caso de overflow da senha, a thread com o lock pode avaliar m->senha >= m->proxima como falso quando, na verdade, há threads na fila do futex.
  • (c) Como a entrada na região crítica depende da senha, não há risco que uma thread seja sempre desfavorecida enquanto outras conseguem entrar na região crítica.
• Código sem a alteração sugerida
  • (a) como no item (a) da versão alterada.
  • (b) Existe a possibilidade de deadlock. Considere que T0 está com o lock, T1 pegou uma senha e está dormindo na linha 21. Quando T0 enviar o sinal de futex_wake, T1 não conseguirá sair do while pois não atualiza o valor de prox. Nenhuma outra thread irá conseguir entrar na região crítica.
  • (c) como no item (c) da versão alterada.
  Erros mais comuns
  • Dizer que não garante exclusão mútua, garante ausência de deadlock ou não garante ausência de starvation.
  • Confundir os conceitos de starvation e deadlock.
  • Não considerar a possibilidade de overflow.

01: typedef struct {
02: int c, tamanho;
03: sem_t sem_barreira; 
04: } barrier_t;
05:
06: /* tamanho: número de threads que devem se sincronizar via barrier_wait() */
07: void barrier_init(barrier_t b, int tamanho) {
08:  b->c = 0;
09:  b->tamanho = tamanho;
10:  sem_init(&b->sem_barreira, 0);
11: }
12: 
13: void barrier_wait(barrier_t *b) {
14:   atomic_inc(&b->c);
15:   if (b->c == b->tamanho)
16:     sem_post(&b->sem_barreira);
17:   sem_wait(&b->sem_barreira);
18:   sem_post(&b->sem_barreira);
19:   atomic_dec(&b->c);
20:   if (b->c == 0)
21:     sem_wait(&b->sem_barreira);
22: }

Resposta esperada: Considere que apenas uma thread avaliou b->c == b->tamanho como verdadeiro na linha 15 e, portanto, houve um único incremento extra do semáforo na linha 16. Considere que duas threads avaliaram b->c == 0 como verdadeiro na linha 20. A segunda irá thread irá ficar presa no comando sem_wait da linha 21.

Erros mais comuns:

• Dizer que não existe cenário em que uma thread fica presa.
• Dizer que existe cenário em que uma thread fica presa, mas descrever um cenário em que isso na verdade não acontece. Por exemplo, dizer que uma thread sempre fica presa na linha 21, sem comentar sobre o número de threads que executam as linhas 16 e 21.
• Considerar que a entrada de um número maior de threads do que o tamanho da barreira levaria automaticamente à condição de erro. Novamente, o mais relevante é o número de threads que executam as linhas 16 e 21.

01: void trata_SIGALRM(int signum) {
02:   printf("Ai que sono! Queria dormir mais...\n");
03: } 
04:
05: int main() {
06:
07:   if ((pid = fork()) != 0) { 
08:       signal(SIGALRM, trata_SIGALRM); /* Instalação do tratador de sinal */ 
09:   pause();  /* Pai espera ser acordado pelo filho */
10:   }
11:   else  {
12:     faz_alguma_coisa();
13:     kill (getppid(), SIGALRM); /* Filho envia sinal para acordar o pai */
14:   }
15:   return 0;  
16: }

Resposta esperada: Dois dos seguintes problemas:

• Se o pai receber o sinal antes de instalar o tratador, o comportamento padrão do SIGALRM será realizado (processo pai morrerá) e a mensagem não será exibida.
• Se o pai receber o sinal depois de instalar o tratador, mas antes de executar o comando pause, a mensagem será exibida e o pai dormirá eternamente (ou até receber algum outro sinal).
• Se o processo filho morrer por algum motivo antes de enviar o sinal o pai dormirá eternamente (ou até receber algum outro sinal).