LEIC/LERC 2010/11

Sistemas Operativos

Aula 4

Exercícios de Sincronização I

Objectivo

Resolução de problemas de sincronização aplicando primitivas de sincronização (trincos e semáforos):
- Exclusão mútua
- Produtores/Consumidores

Introdução

1. Exclusão Mútua

Observando o programa, responda às questões seguintes:

a) Identifique a secção crítica. Justifique.

b) Resolva o problema de sincronização existente utilizando um trinco ou um semáforo.

2. Produtores/Consumidores

Relembre uma solução possível do problema clássico Produtores/Consumidores.

a) É um problema de competição, de cooperação ou ambos?

b) Qual a função dos semáforos?

Material de Apoio

Funcionamento do trinco (slide).

Funcionamento do semáforo (slide).

Exercícios

1. Exclusão mútua
A
int A = 1;
        
thr_func_1() {
   int b = 10;
           
   while (b > 0) {
      if(A + b % 2 == 0) {
         A++;
      }
      else
         b++;
   }
}

// Lançar 5 tarefas thr_func_1
B
int X = 0;
        
void *thr_func_A(int id) {
   while (true) {
      if (X % id == 0) {
         return NULL ;
      }
      printf("X=%d is not divisible by %d\n",X++, id);

   }
}
        
void *thr_func_B() {
   int a = 0;
   for(;;) {
      X += a;
      if (X == 1000) {
         break;
      }
      a++;	
   }
return NULL;
}

//Lançar 1 tarefa thr_func_A e N tarefas thr_func_B
Os programas A e B, implementados em pseudo-código C, são executados por tarefas. Compreenda o que fazem as tarefas e responda às seguintes questões:

a) Identifique as secções críticas.

b) Proteja as secções críticas com trincos, permitindo que o paralelismo entre as tarefas seja máximo.

2. Exclusão mútua
A
int X = 1;
        
thr_func_1() {
   trinco Mutex;
   fechar(Mutex);
   while (true) {
      X++;
      if (X == 5) {
         return;
      }
      abrir(Mutex);
   }
}

// Lançar 10 tarefas thr_func_1
B
int Y = 0;
semaforo Sem = 0;
trinco Mutex;
        
thr_func_1(int id) {
   fechar(Mutex);
   esperar(Sem);
   Y = 1;
   printf("Y=%d",Y);

   abrir(Mutex);
}
        
thr_func_2() {
   fechar(Mutex);
   Y++;
   printf("Y=2 (check %d)",Y);
   assinalar(Sem);
   abrir(Mutex);
}

//Lançar 1 tarefa thr_func_1 e 1 tarefa thr_func_2
Os programas A e B apresentam problemas de sincronização. Compreenda o código das tarefas e responda às questões seguintes:

a) Identifique cada um dos problemas.

b) Desenhe soluções correctas e eficientes para os problemas encontrados.

3. A Molécula de Água

Um sistema é composto por duas tarefas concorrentes: A tarefa thr_Hidrogenio() gera átomos de hidrogénio e a tarefa thr_Oxigenio() gera átomos de oxigénio. Cada tarefa periodicamente produz um átomo e invoca uma função de impressão. Pretende-se que a actividades de ambas as tarefas estejam sincronizadas de modo a que os inputs fornecidos à função de impressão Imprime() estejam ordenados no seguinte modo: HHOHHOHHOHH...
                thr_Hidrogenio () { 

	                for(;;) {
	                    
	                    Imprime("H");
	                }

                }   

                thr_Oxigenio () { 

                	for(;;) {
                	   
                	   Imprime("O");
                	}

                }   
        
Usando semáforos, implemente a correcta sincronização das tarefas thr_Hidrogenio() e thr_Oxigenio().

4. Produtores/Consumidores

Modifique a solução do problema dos Produtores/Consumidores considerando as seguintes alterações:

existe apenas um produtor;

quando o buffer está vazio, os consumidores não devem ficar bloqueados, mas devem imprimir uma mensagem de erro.

Exercício Suplementar

O Coffee-Break

Num coffee-break os participantes servem-se de bolos de nata retirando-os, um de cada vez, de um tabuleiro capaz de conter M unidades. Quando um participante deseja comer um bolo de nata e apercebe-se que o tabuleiro está vazio, avisa imediatamente o empregado de serviço que de seguida coloca B bolos de nata no referido tabuleiro. O sistema é composto por um empregado de serviço e N participantes no coffee-break.

Utilizando semáforos, implemente em pseudo-código C as tarefas thr_participante() e thr_empregado().