1. Leitores/Escritores Simples
Este slide apresenta uma solução alternativa para o problema dos Leitores/Escritores, diferente da solução analisada e discutida nas teóricas. Estude esta nova 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?
d) Com esta solução pode ocorrer alguma situação de interblocagem (deadlock) ou míngua (starvation)? Compare com a solução discutida nas teóricas (ver livro ou slides das teóricas).
1. Leitores/Escritores com Múltiplos Registos em Array
Obtenha e descomprima o pacote sthreads+logrw (V2) a partir da página do projecto. Na directoria include encontrará os ficheiros block.h e logrw.h.
a) Estude a API definida em cada um desses ficheiros. As funções mencionadas em block.h já se encontram implementadas noutros ficheiros do pacote sthreads+logrw. Encontre e analise também esses ficheiros.
b) Baseando-se na solução do problema leitores/escritores da alínea 1, construa uma solução mais genérica em que existe um conjunto de registos partilhados dos quais se pode ler ou escrever (e não apenas um registo). Trabalhe a partir deste esqueleto do ficheiro, que devera' colocar na directoria logrw. A sua solução deverá oferecer a API definida no ficheiro include/logrw.h. Implemente apenas as funções logrw_read, logrw_write, logrw_init e logrw_free.
c) Teste a sua solução com o programa de teste tests-sthreads-logrw/test-logrw-nodumps.c.
d) Caso tenha usado a API das pthreads para o semáforo e o trinco lógico, substitua essas chamadas por chamadas à API das sthreads, definida em include/sthread.h.
Nota: Como as sthreads fornecidas no pacote base não incluem ainda uma implementação de semáforos, inclua a opção de compilação -DUSE_PTHREADS na sua Makefile. Desta forma, o programa usará o suporte a semáforos e trincos lógicos oferecido pelas pthreads; de igual forma, quando nas próximas semanas o seu grupo completar a biblioteca sthreads com a implementação de semáforos (parte do problema I.B), o seu programa estará já pronto a usar essa implementação (retirando a opção -DUSE_PTHREADS).
2. Leitores/Escritores baseados em Logs (Resolução do Problema I.A do Projecto)
Estude o problema I.A do enunciado do projecto. Com a ajuda do professor do seu laboratório, comece a construir a solução para o mesmo problema, assumindo a API definida em include/logrw.h. Sugerimos a seguinte abordagem:
a) Comece por identificar as estruturas de dados principais.
b) Identifique as restrições principais de sincronização que deverá salvaguardar.
Sugestão: por discussão com os seus colegas de grupo, enumere por extenso um conjunto de condições. Por exemplo, "Condição 1: quando dois escritores tentam concorrentemente reservar um novo bloco no array activo, devem fazê-lo em exclusão mútua". Complete a lista de condições.c) Decida quais os objectos de sincronização deverá usar para assegurar as condições que enumerou acima. Poderá recorrer a trincos lógicos, semáforos e a trincos de leitores/escritores.
d) Em pseudo-código, elabore um primeiro esboço do algoritmo que, usando os objectos de sincronização definidos acima, assegure todas as condições de sincronização que o seu grupo identificou. Com os restantes elementos do grupo e com a ajuda do professor do laboratório, confirme que o programa é correcto.
e) No seu primeiro esboço de algoritmo, tente encontrar oportunidades de paralelismo que o esboço actual do algoritmo esteja a proibir. Tente encontrar variantes do algoritmo que, mantendo a correcção, consigam expor maior paralelismo.Sugestão final: use apenas pseudo-código durante estas iterações (usando papel e lápis, ou um editor de texto). Avance para a implementação apenas quando o grupo tiver uma forte garantia de que a solução esboçada é correcta e eficiente.
1. 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.
2. Leitores/Escritores com monitores
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.
3. 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 travessia 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().
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.
5. 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().
6. Mais...
Exercícios de exame sobre a sincronização