Programação Concorrente - Provas Antigas (16)

Prévia do material em texto

Computação Concorrente (MAB117) – Prova Suplementar
Prof. Silvana Rossetto – 21 de julho de 2015
1DCC/IM/UFRJ
Questão 1 (2,0 pts) A série abaixo pode ser usada para estimar o valor de π. A função
Serial pi implementa o cálculo dessa série de forma sequencial. (a) Implemente uma
versão concorrente para essa função para dividir a tarefa de estimar o valor de π entre N
threads. Todas as threads deverão executar a mesma função.
π = 4 ∗ [1− 1/3 + 1/5− 1/7 + 1/9− ...]
double Serial_pi(long long n) {
double sum = 0.0; long long i; double factor = 1.0;
for (i = 0; i 0) { wait(); }
17: } catch (InterruptedException e) {}
18: //realiza a escrita de ’str’
19: notify(); //libera outro escritor (caso exista escritor bloqueado)
20: } }
Resp.: (a) Sim, pois os escritores só ficarão bloqueados na variável de condição
quando houver leitores lendo, como o último leitor desbloqueia todos os escritores blo-
queados não há necessidade do notify() na saı́da do método Escrita().
(b) Sim, desde que o notify() da linha 19 seja mantido. Nesse caso, se vários es-
critores ficarem bloqueados na variável de condição porque há leitores lendo, quando o
último leitor sair, ele irá desbloquear apenas um escritor, mas cada escritor irá neces-
sariamente desbloquear outro escritor quando terminar a escrita, garantindo que todos
os escritores bloqueados sejam em algum momento desbloqueados. Isso é possı́vel pois
apenas escritores ficarão bloqueados na fila da variável de condição.
(c)
class LE {
private int leit, escr, escresp;
LE() {
this.leit = 0; //numero de leitores lendo
this.escr = 0; //numero de escritores escrevendo (0 ou 1)
this.escresp = 0; //numero de escritores esperando
}
// Entrada para leitores
public synchronized void EntraLeitor (int id) {
try {
while (this.escr > 0 || this.escresp > 0) {
wait(); //bloqueia se houver escritores esperando ou escrevendo
}
this.leit++;
} catch (InterruptedException e) { }
}
// Saida para leitores
public synchronized void SaiLeitor (int id) {
this.leit--;
if (this.leit == 0)
notifyAll(); //libera os escritores
//(a fila da variavel de condicao pode ter leitores e escritores)
}
// Entrada para escritores
public synchronized void EntraEscritor (int id) {
try {
this.escresp++; //sinaliza que quer escrever
while ((this.leit > 0) || (this.escr > 0)) {
wait(); //bloqueia se houver leitores lendo ou outro escritor escrevendo
}
this.escresp--;
this.escr++;
} catch (InterruptedException e) { }
}
// Saida para escritores
public synchronized void SaiEscritor (int id) {
this.escr--;
notifyAll(); //libera os leitores e outros escritores
}
}
Questão 3 (5,0 pts) Você foi contratado para desenvolver uma aplicação para a Justiça
Federal que, dado o número do CPF de uma pessoa, consulte todos os processos relaciona-
dos a essa pessoa em um banco de dados e gere um arquivo texto com esse levantamento.
Como a busca no banco de dados é muito demorada, já foi definido que a aplicação
deverá ser concorrente, i.e., executar com várias threads para aumentar sua eficiência,
diminuindo o tempo total para processar várias buscas consecutivas. A thread princi-
pal (main) deverá inicialmente criar um número de threads auxiliares igual ao dobro do
número de processadores da máquina. As threads auxiliares deverão realizar a tarefa
principal de, dado um número de CPF, consultar o banco de dados e gerar o arquivo de
saı́da. A thread principal (main), após criar as threads auxiliares, deverá ficar esperando
a entrada de um novo CPF pelo teclado, ou o valor -1 indicando que a aplicação deve
ser encerrada. A cada novo CPF informado, a thread principal deverá acionar uma thread
auxiliar para processá-lo, e logo em seguida voltar a esperar nova entrada do usuário. As
threads auxiliares devem ficar aguardando uma nova tarefa (CPF para consultar), realizar
a tarefa e voltar a aguardar nova tarefa, até que a thread principal avise que a aplicação
deve terminar e não há mais consultas pendentes para realizar (nesse caso a thread auxili-
ar deve finalizar sua execução). Após o usuário solicitar o encerramento da aplicação, as
consultas pendentes devem ser realizadas/finalizadas e novas consultas não serão mais re-
cebidas. A thread principal deve aguardar todas as threads auxiliares terminarem e então
finalizar a aplicação.
Considere que já existe uma função implementada que dado um CPF ela faz a
busca dos processos e gera o arquivo de saı́da. A assinatura dessa função é: void
consultaProcessos(long int cpf).
A função sysconf( SC NPROCESSORS ONLN) pode ser usada para identificar o número
de processadores da máquina.
(a) Usando a linguagem C, implemente uma solução para a aplicação definida
acima (código da thread principal e das threads auxiliares) usando de forma eficiente a
capacidade de processamento da máquina.
(b) Avalie a sua implementação quanto à corretude (atende aos requisitos do prob-
lema, não possui erros de concorrência, como possibilidade de condições de corrida in-
desejáveis, e não pode causar deadlock ou livelock) e à eficiência (usa da melhor forma
possı́vel a capacidade de processamento da máquina). Apresente argumentos objetivos
que justifiquem a sua avaliação.
Resp.: (a)
/*Variaveis globais */
pthread_mutex_t em; //lock par exclusao mutua
pthread_cond_t cond; //variavel de condicao para sincronizacao logica
int NTHREADS = sysconf(_SC_NPROCESSORS_ONLN) * 2;
long int cpf[NTHREADS]; //buffer para guardar CPFs esperando por atendimento
int in=0, out=0, cont=0; //variaveis de controle do buffer
int terminar=0; //variavel para registrar se a aplicacao deve terminar (0:nao, 1:sim)
//insere um novo cliente (CPF) no buffer para ser atendido por uma thread
//funcao executada pela thread main
int insere(long int cliente) {
pthread_mutex_lock(&em);
if(cont==NTHREADS) { //se nao ha espaco no buffer, recusa a solicitacao
pthread_mutex_unlock(&em);
return 0;
}
//insere o novo cliente e atualiza as variaveis de estado do buffer
cpf[in]=cliente;
in=(in+1)%NTHREADS;
cont++;
pthread_mutex_unlock(&em);
return 1;
}
//retira um cliente do buffer para atende-lo
//funcao executada pelas threads auxiliares
//(elas soh executam essa funcao se ja houver uma solicitacao armazenada)
long int retira() {
long int cliente;
cliente=cpf[out];
cpf[out]=0; //slot vazio
out=(out+1)%NTHREADS;
cont--;
return cliente;
}
//funcao principal das threads auxiliares
void *Trabalhador (void *t) {
int my_id = *(int*)t;
long int local_cpf;
while(1) { //permanece ativa ate que o sinal de terminar seja lançado
pthread_mutex_lock(&em);
while((cont==0) && (!terminar)) {
pthread_cond_wait(&cond, &em);
}
if(cont>0) { //ha solicitacao para tratar, pega uma delas e processa
local_cpf=retira();
pthread_mutex_unlock(&em);
fazInteracao(local_cpf); //interacao com o cliente remoto, fora da secao critica
} else { //terminar==1, a thread deve encerrar
pthread_mutex_unlock(&em);
break;
}
}
pthread_exit(NULL);
}
//funcao principal
int main(int argc, char *argv[]) {
int i,res;
long int req;
pthread_t threads[NTHREADS];
int id[NTHREADS];
//inicializa o lock e a variavel de condicao
pthread_mutex_init(&em, NULL);
pthread_cond_init(&cond, NULL);
//cria as threads auxiliares
for(i=0;i