LEIC/LERC 2008/09

Sistemas Operativos

Aula 4

Exercícios de Sincronização

Objectivo

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

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?

3. Leitores/Escritores

Este slide apresenta uma solução alternativa para o problema dos Leitores/Escritores. Estude a solução e responda às questões seguintes:

a) De que forma é assegurada a exclusão mútua entre escritores? E entre um escritor e um leitor?

b) Se um escritor está a escrever, o que impede todos os leitores de aceder aos dados?

c) Se um escritor acaba de escrever, o que permite a todos os leitores bloqueados de aceder aos dados?

4. Barbeiro

Numa barbearia existe uma cadeira onde o barbeiro corta cabelo e N cadeiras para os clientes que estão à espera. Se não existem clientes, o barbeiro senta-se na cadeira e adormece. Quando um cliente chega, ele tem que acordar o barbeiro dorminhoco para lhe cortar o cabelo. Se entretanto chegarem mais clientes enquanto o barbeiro estiver a cortar o cabelo ao primeiro, ou esperam numa cadeira livre ou vão-se embora se já não houver mais cadeiras livres. Considere que o barbeiro e os clientes são implementados, respectivamente, pelas tarefas thr_barber e thr_customer.

a) Verifique que esta é uma solução possível para o problema.

b) Qual a função do semáforo SemBarber? E do semáforo SemCustomers?

c) Porque razão é necessário o trinco Mutex?

Material de Apoio

• Funcionamento do trinco (slide).
• Funcionamento do semáforo (slide).

Exercícios

1. Exclusão mútua

int A = 1;
        
thr_func_1() {
   int b = 10;
           
   while (b > 0) {
      if(A + b % 2 == 0) {
         A++;
      }
      b = b - 1;
   }
}

// Lançar 10 tarefas thr_func_1

int B = 0;
        
thr_func_1(int id) {
   while (true) {
      if (B % id == 0) {
         printf("B=%d divisible by %d\n",B, id);
      }
   }
}
        
thr_func_2() {
   while (true) {
      B++;
      if (B == 1000) {
         break;
      }
   }
}

//Lançar N tarefas thr_func_1 e 1 tarefa thr_func_2

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. Produtores/Consumidores

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

• existe apenas um consumidor;
• quando o buffer está cheio, os produtores não devem ficar bloqueados, mas devem imprimir uma mensagem de erro.

3. Leitores/Escritores

Considere uma ponte com uma única via por onde passam carros em ambos os sentidos Este-Oeste. Um carro só não pode atravessar a ponte se esta se encontrar ocupada por carros que a atravessam no sentido oposto pelo que deve aguardar até que a ponte esteja desimpedida ou que haja carros a atravessar a ponte no seu sentido.

Cada carro é simulado por uma tarefa. O pseudo-código da implementação das viaturas seria:

        thr_west_car() {      thr_east_car() {
           west_enter();         east_enter();
           // cross bridge       // cross bridge
           west_leave();         east_leave
        }                     }

Um carro que se aproxima de Oeste, executa a rotina west_enter para ter acesso e executa a rotina west_leave quando sai da ponte. Para os carros provenientes de este o procedimento é simultâneo mas invocam as rotinas east_enter para ter acesso e executa a rotina east_leave, respectivamente.

a) Escreva o código das rotinas: west_enter(), west_leave(), east_enter() e east_leave(). Sugestão: o algoritmo dos Leitores/Escritores pode ser adaptado se
considerarmos os carros de oeste, incompatíveis com os carros de este, tal como os leitores são incompatíveis como os escritores.

b) Considere agora que não podem existir mais do que 5 carros na ponte em simultâneo (senão ela cai). Reescreva o código.

4. Exclusão mútua

int X = 1;
        
thr_func_1() {
   trinco Mutex;
   
   while (true) {
      X++;
      fechar(Mutex);
      if (X == 5) {
         return;
      }
      abrir(Mutex);
   }
}

// Lançar 5 tarefas thr_func_1

int Y = 0;
semaforo Sem = 0;
trinco Mutex;
        
thr_func_1(int id) {
   fechar(Mutex);
   Y = 1;
   printf("Y=%d",Y);
   assinalar(Sem);
   abrir(Mutex);
}
        
thr_func_2() {
   fechar(Mutex);
   esperar(Sem);
   Y++;
   printf("Y=2 (check %d)",Y);
   abrir(Mutex);
}

//Lançar 1 tarefa thr_func_1 e 1 tarefa thr_func_2

Os programas A e B padecem de 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.

Exercício Suplementar

Parque de Estacionamento

Considere um parque de estacionamento com capacidade máxima para MAX viaturas. Existem três tipos de utilizadores deste parque: docentes, funcionários e alunos. Enquanto há lugares livres no parque, a ordem de entrada é por ordem de chegada. A partir do momento em que o parque fica cheio, a entrada de viaturas fica condicionada à saída de outras, devendo ser dada prioridade às viaturas dos docentes, funcionários e alunos (por esta ordem).

Cada carro é simulado por uma tarefa. O pseudo-código C das tarefas seria:

        thr_car() {
           enter_park();
           // the car is parked
           leave_park();
        }    

Utilizando semáforos, implemente em pseudo-código C as funções enter_park(int tipo) e leave_park().

Exercícios de Exame

1. 1º Teste 2002/03

Considere que existe um serviço com 3 guichets de atendimento (três processos servidores) a que chegam clientes (processos clientes). O sistema deve funcionar do seguinte modo:

• Se existirem processos servidor livres o processo cliente deve ser atendido de imediato.
• Se não existirem processos à espera de ser atendidos os processos servidores devem ficar bloqueados.
• O número máximo de clientes em espera é de K. Para além deste limite o serviço é recusado.

for (;;){ 
    If(NovoCliente()) { 

        Servico(); 

    } else .... 

}

for (;;){

    RequisitarServico();

    Atendimento();

}

Programe as funções que os processos devem invocar: RequisitarServico() e NovoCliente().

Utilize semáforos para sincronizar os processos. Programe em C ou pseudocódigo e defina as variáveis que necessitar. Não se preocupe com o procedimento Atendimento() e Serviço(); apenas se sabe que é um procedimento executado por ambos os processos e que termina ao fim de um intervalo de tempo finito.

2. 1º Teste 2001/02

Pretende-se construir uma aplicação em que processos Produtores enviam mensagens para um processo Consumidor. As mensagens são colocadas em 4 filas cada uma associada a um nível de prioridade (podíamos considerar mensagens com quatro níveis de urgência). As mensagens são todas do mesmo tamanho. As filas de mensagens têm espaço para 3 mensagens.

Quando um produtor pretende escrever a mensagem e a fila está cheia, fica bloqueado. O processo consumidor retira a mensagem da fila mais prioritária. Se não houver mensagem deve ficar bloqueado. Programe as 2 rotinas que permitem inserir e retirar mensagens:

      void inserir(int Prioridade, struct mens m)

      struct mens retirar()

Utilize semáforos para sincronizar os processos. Para simplificar considere as seguintes estruturas:

struct mens - para representar as mensagens.

struct mens [NIVEL] [TAMANHO] buffer - para representar as filas de mensagem NÍVEL corresponde ao nível de prioridade e TAMANHO ao número máximo de mensagens por fila.