1. 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?
2. 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
.
I.
a) Verifique que esta é uma solução possível para o problema.
b) Qual a função do semáforo
SemBarber
? E do semáforoSemCustomers
?c) Porque razão é necessário o trinco
Mutex
?
II.
a) Verifique que esta pode ser também uma solução para o problema através do emprego de monitores.
b) Explique a função do monitor e das variáveis globais na solução apresentada na alínea anterior.
1. Leitores/Escritores
Considere de novo o problema dos Leitores/Escritores.
a) Escreva uma solução em pseudo-código C para as rotinas:
th_reader()
e,th_writer()
utilizando monitores como ferramenta de sincronização entre as várias tarefas concorrentes.b) Suponha que é permitido o acesso, no máximo, a 2 tarefas escritoras consecutivas. Alterar convenientemente a solução anterior de modo a acomodar esta nova situação.
2. Movimento Portuário
Um porto marítimo de uma cidade pode receber no máximo N navios que entram através de um canal. Pelo canal pode transitar apenas um navio de cada vez. Os navios que saiem do porto têm prioridade na travessaia do canal.
Cada navio é simulado por uma tarefa cujo pseudo-código é o seguinte:
thr_navio() { < Chegada à entrada do canal > pedido_entrada(); < Atravessa o canal > entrada_OK(); < Atraca no porto > pedido_saida(); < Atravessa o canal > saida_OK(); < Parte em viagem para outro porto > }
Utilizando monitores, implemente em pseudo-código C as funções
pedido_entrada()
, entrada_OK()
,
pedido_saida()
e saida_OK()
.
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()
eeast_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()
.
3. Mais...
Exercícios de exame sobre a sincronização