Programação Concorrente - Provas Antigas (5)

Prévia do material em texto

Computação Concorrente (MAB117) – Gabarito da Primeira Prova
Prof. Silvana Rossetto – 27 de março de 2014
1DCC/IM/UFRJ
Questão 1 (2.0pts) Uma aplicação sequencial pode ser dividida em três etapas: entrada
de dados, processamento e saı́da de dados. A entrada de dados consome 1/5 do tempo
total de execução, o processamento 3/5 e a saı́da de dados 1/5. (a) Qual será o ganho
máximo de desempenho (em termos de redução do tempo total de execução) da aplicação
se a etapa de processamento for paralelizada e a aplicação for executada em uma máquina
com 2 processadores? (b) Se a aplicação paralelizada for executada em uma máquina
com um único processador, será possı́vel ter algum ganho de desempenho? Ou o tempo
total será necessariamente maior que o tempo da versão sequencial executada na mesma
máquina? Justifique suas respostas.
Resp.: (a) O ganho máximo de desempenho será a razão entre o tempo de execução
da versão sequencial e o tempo de execução da versão paralelizada, considerando uma
máquina com dois processadores. Seja Ts o tempo de execução da versão sequencial
e Tp o tempo de execução da versão paralela, o ganho máximo de desempenho será a
razão Ts/Tp.
Ts = 5/5 = 1
Tp = 2/5 + (3/5)/2, onde 2 é o número de processadores.
Então Ts/Tp = 10/7 = 1, 42.
(b) Dependerá do tipo de aplicação. Se for uma aplicação cujo processamento
requer muitas operações de entrada e saı́da (IO-bound) e o código paralelo implemen-
tado garantir que enquanto uma thread espera por I/O a outra thread está pronta para
executar, é possı́vel ter ganho de desempenho mesmo executando em uma máquina mono-
processador. Ao contrário, se for uma aplicação cujo processamento requer apenas
operações na CPU (CPU-bound), a versão paralela terá desempenho um pouco pior
pois o custo de gerência das threads não será compensado.
Questão 2 (3.0pts) Uma aplicação dispara duas threads (T1 e T2) para execução (códigos
mostrados abaixo). (a) Quais são os possı́veis valores esperados na saı́da do programa
(impressos na linha 10)? (b) Pode ocorrer da thread T2 ficar executando indefinidamente
(i.e., não chegar a executar a linha 11)? Justifique. (c) Aponte os trechos de código que
são seção crı́tica. (d) Usando locks, altere o código das threads de forma a eliminar as
condições de corrida que podem gerar resultados incorretos. (e) Implemente uma thread
adicional (T3) para necessariamente imprimir o valor da variável item sempre que x
chegar a um valor múltiplo de 5. Justifique suas respostas.
int x=0; float item; //variaveis globais
(1) void *T1 (void *) {
(2) for(int i=1; irequisitos do problema: O acesso à
bandeija está sendo feito com exclusão mútua entre todas as threads, via semáforo
mutex; o processamento para produção (produtores) e consumo (consumidores) de um
item está fora da seção crı́tica; produtores são bloqueados quando a bandeija está
cheia (linhas 6 a 9) e desbloqueados quando um slot é esvaziado (linhas 31 e 32); consum-
idores são bloqueados quando a bandeija está vazia (linhas 23 a 26) e desbloqueados
quando um slot é preenchido (linhas 15 e 16); os itens são consumidos na mesma ordem
em que são inseridos.
(b) Qual é a finalidade das linhas 9 e 26? Linha 9: bloquear um produtor caso
não exista slot vazio para inserir o item produzido. Linha 26: bloquear um consumidor
caso não exista item para ser consumido.
(c) As linhas 8, 10, 25 e 27 poderiam ser excluı́das? Não. Elas são necessárias
para liberar a exclusão mútua antes de um produtor ou consumidor se bloquear no
caso de não ter condição lógica para continuar executando naquele instante. Assim,
uma thread de outro tipo conseguirá entrar na seção crı́tica permitindo que a aplicação
evolua.
(d) Que tipo de erro poderia ocorrer se alterássemos a linha 15 para if(cont==1)?
O semáforo vazio poderia acumular sinais indevidamente. Por exemplo, a seguinte
sequência poderia ocorrer: um produtor insere o primeiro elemento e executa as linhas
15 (alterada) e 16, deixando um sinal acumulado no semáforo vazio quando não há
nenhum consumidor bloqueado ainda. No futuro, se ocorrer da bandeija ficar vazia e
um consumidor tentar consumir, ao invés de ficar imediatamente bloqueado na linha 26,
ele seguirá em frente. O loop while fará ele testar a condição novamente e só então o
consumidor ficará bloqueado.
Outra situação que poderia ocorrer é consumidores bloqueados quando há ele-
mentos na bandeija para consumir. Por exemplo, a seguinte sequência poderia ocorrer:
todos (ou parte) os consumidores tentam consumir antes dos produtores inserirem algum
elemento, ficando bloqueados no semáforo vazio. Em seguida os produtores inserem
uma sequência de elementos, liberando apenas um dos consumidores. Os demais ficarão
bloqueados desnecessariamente.
\begin{quote}\small
\begin{verbatim}
sem_t mutex; //inicia com 1
sem_t cheio, vazio; //ambos iniciam com 0
int bandeija[N], in=0, out=0, cont=0, prodEsperando=0, consEsperando=0;
(1) void *produtor(void * arg) {
(2) int item;
(3) while(1) {
(4) item = produzItem();
(5) sem_wait(&mutex);
(6) while(cont==N) {
(7) prodEsperando++;
(8) sem_post(&mutex);
(9) sem_wait(&cheio);
(10) sem_wait(&mutex);
(11) prodEsperando--;
(12) }
(13) cont++;
(14) bandeija[in%N] = item; in++;
(15) if(consEsperando>0)
(16) sem_post(&vazio);
(17) sem_post(&mutex);
(18) } }
(19) void *consumidor(void * arg) {
(20) int item;
(21) while(1) {
(22) sem_wait(&mutex);
(23) while(cont==0) {
(24) consEsperando++;
(25) sem_post(&mutex);
(26) sem_wait(&vazio);
(27) sem_wait(&mutex);
(28) consEsperando--;
(29) }
(30) cont--; item = bandeija[out%N]; out++;
(31) if(prodEsperando>0)
(32) sem_post(&cheio);
(33) sem_post(&mutex);
(34) consomeItem(item);
(35) } }