Programação Concorrente - Provas Antigas (15)

Prévia do material em texto

Computação Concorrente (MAB117) – Gabarito da Prova
Suplementar
Prof. Silvana Rossetto – 05 de junho de 2014
1DCC/IM/UFRJ
Questão 1 (2.5pts) Uma aplicação possui threads do tipo bar e do tipo foo (códigos
mostrados abaixo). A saı́da da aplicação consiste na impressão na tela dos valores finais
das variáveis globais cont e aux, acessadas exclusivamente dentro do código das threads.
Na primeira versão da aplicação foram criadas uma thread bar e uma thread foo. (a)
Quais são os possı́veis valores finais de cont, aux e p para uma execução dessa versão da
aplicação? (b) O código dessa versão da aplicação possui condição de corrida? Por que?
Se sim, altere o código para eliminar esse problema. Na segunda versão da aplicação
foram criadas 2 threads foo e uma thread bar. (c) Nesse caso, a aplicação possui condição
de corrida? Por que? Se sim, altere o código para eliminar esse problema.
int volatile cont=0, aux=0;
void *bar(void * arg) {
int p=0;
while(aux==0) p++;
//faz algo
cont--;
}
void *foo(void * arg) {
aux++;
//faz algo
cont++;
}
Resp.: (a) cont: 0, -1 ou 1; aux: 1; p: 0 ou qualquer valor positivo
(b) Sim, por conta do acesso compartilhado à variável ’cont’ (a resposta do item
anterior demonstra que apenas o valor final de ’cont’ depende da ordem de execução das
threads). A variável ’aux’ também é compartilhada pelas threads ’foo’ e ’bar’, mas como
apenas uma thread ’foo’ escreve nessa variável (a thread ’bar’ depende do seu valor mas
apenas para incrementar uma variável local que não afeta o estado final da aplicação),
ela não causa condição de corrida nessa versão da aplicação. Para corrigir o código é
preciso definir uma variável global de lock, como mostrado abaixo:
int volatile cont=0, aux=0;
pthread_mutex_t me_cont; // lock para exclusao mutua entre as threads
void *bar(void * arg) {
int p=0;
while(aux==0) p++;
//faz algo
pthread_mutex_lock(&me_cont); //entrada na secao critica
cont--;
pthread_mutex_lock(&me_cont); //sai da secao critica
}
void *foo(void * arg) {
aux++;
//faz algo
pthread_mutex_lock(&me_cont); //entrada na secao critica
cont++;
pthread_mutex_lock(&me_cont); //sai da secao critica
}
(c) Sim, agora por conta do acesso compartilhado à variável ’cont’ e ’aux’. Com
duas threads ’foo’, o incremento da variável ’aux’ gera condição de corrida. Para corri-
gir o código é preciso definir uma variável global de lock, como mostrado abaixo:
int volatile cont=0, aux=0;
pthread_mutex_t me_cont, me_aux; //locks para exclusao mutua entre as threads
void *bar(void * arg) {
int p=0;
while(aux==0) p++;
//faz algo
pthread_mutex_lock(&me_cont); //entrada na secao critica
cont--;
pthread_mutex_lock(&me_cont); //sai da secao critica
}
void *foo(void * arg) {
pthread_mutex_lock(&me_aux); //entrada na secao critica
aux++;
pthread_mutex_lock(&me_aux); //sai da secao critica
//faz algo
pthread_mutex_lock(&me_cont); //entrada na secao critica
cont++;
pthread_mutex_lock(&me_cont); //sai da secao critica
}
Questão 2 (2.5pts) Usando semáforos, construa um canal de comunicação do tipo mail-
box assı́ncrono limitado capaz de manter até M mensagens. Implemente as primitivas
send (não-bloqueante) e receive (bloqueante) para esse canal.
public class AMailbox {
private final int M = 100;
private Object message[] = new Object[M]; //buffer do canal
private final Semaphore msgDisponivel = new Semaphore(0);
private final Semaphore slotDisponivel = new Semaphore(M);
//objeto para sincronização entre emissores
private final Object sender = new Object();
//objeto para sincronização entre receptores
private final Object receiver = new Object();
private int in=0, out=0; //proximas posicoes de inserção/remoção
//envia uma mensagem
public void send(Object msg) {
slotDisponivel.wait(); //bloqueia se mailbox cheio
synchronized (sender) {
message[in] = msg; //armazena a mensagem no buffer
in=(in+1)%M;
}
msgDisponivel.post(); //sinaliza nova mensagem
}
//recebe uma mensagem
public Object receive() {
Object receivedMsg = null;
msgDisponivel.wait(); //espera nova mensagem
synchronized(receiver) {
receivedMsg = message[out]; //recebe a mensagem
out=(out+1)%M;
}
slotDisponivel.post(); //sinaliza um slot vazio
return receivedMsg;
}
}
Questão 3 (2.5pts) Uma aplicação consome grande parte do seu tempo total de proces-
samento executando o trecho de código abaixo. O vetor vet foi definido como variável
global com M inteiros. Implemente uma versão concorrente para esse trecho de código
de forma a obter o máximo de aproveitameto possı́vel (redução do tempo total de proces-
samento da aplicação) em uma máquina com P processadores. Comente seu código.
for (int t=0; t0) || (esperandoB>0)) {
esperandoA++; wait(); esperandoA--;
} usandoA++;
}
public synchronized void SaidaA () {
usandoA--;
if((usandoA == 0) && (esperandoB > 0))
notifyAll();
}
public synchronized void EntradaB ()
while((usandoA>0) || (esperandoA>0)) {
esperandoB++; wait(); esperandoB--;
} usandoB++;
}
public synchronized void SaidaB () {
usandoB--;
if((usandoB==0) && (esperandoA>0))
notifyAll();
} }
Resp.:
class Recurso {
int esperandoA=0, esperandoB=0; //qtde threads A e B esperando pelo recurso
int usandoA=0, usandoB=0; //qtde threads A e B usando o recurso
int vezA, vezB; //sinaliza a vez de cada tipo de thread usar o recurso
Recurso() {//construtor}
public synchronized void EntradaA () {
while((usandoB>0) || (esperandoB>0)) {
esperandoA++; wait(); esperandoA--;
if(vezA > 0) { //permite que as threads A usem o recurso
vezA--; break;
}
} usandoA++;
}
public synchronized void SaidaA () {
usandoA--;
if(usandoA == 0) {
vezA=0;
if (esperandoB > 0)) {
vezB = esperandoB;
notifyAll();
}}
}
public synchronized void EntradaB ()
while((usandoA>0) || (esperandoA>0)) {
esperandoB++; wait(); esperandoB--;
if(vezB > 0) { //permite que as threads B usem o recurso
vezB--; break;
}
} usandoB++;
}
public synchronized void SaidaB () {
usandoB--;
if(usandoB == 0) {
vezB=0;
if (esperandoA > 0)) {
vezA = esperandoA;notifyAll();
}}
}
}