LEIC/LERC 2009/10

Sistemas Operativos

Exercícios de Sincronização Suplementares

1. 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.

2. 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.