Programação Concorrente - Provas Antigas (21)

Prévia do material em texto

Computação Concorrente (MAB117) – 2016/2 – Gabarito Prova de Segunda Chamada
Profa. Silvana Rossetto – 15 de dezembro de 2016
1DCC/IM/UFRJ
Questão 1 (2,5 pts) Considere um recurso compartilhado com as seguintes caracterı́sticas: (i) en-
quanto o número de threads usando o recurso é menor que três, novas threads podem usar o recurso
imediatamente; (ii) uma vez que há três threads usando o recurso, todos as três devem liberar o recurso
antes de qualquer outro processo poder usá-lo. O código abaixo implementa uma solução para esse
problema. Ocorreu que em uma determinada execução desse código o recurso foi acessado por mais
de três threads ao mesmo tempo e a aplicação entrou em deadlock. Em outra execução, a aplicação
terminou sem deadlock mas também houve erro de acesso ao recurso, e por fim em outras tentativas a
aplicação atendeu à lógica de acesso ao recurso mas entrou em deadlock. (a) Identifique o(s) erro(s)
no código. (b) Mostre como corrigı́-lo(s).
1: pthread_mutex_t mutex; //inicializado na main()
2: pthread_cond_t cond; //inicializado na main()
3: //variaveis de estado
4: int deve_esperar = 0;
5: int esperando = 0;
6: int ativas = 0;
7: //funcao executada pelas threads
8: void *recurso (void *tid) {
9: pthread_mutex_lock(&mutex);
10: if(deve_esperar) {
11: esperando++;
12: pthread_cond_wait(&cond, &mutex);
13: esperando--;
14: }
15: ativas++;;
16: deve_esperar = (ativas==3);
17: if(esperando>0 && !deve_esperar)
18: { pthread_cond_signal(&cond); }
19: pthread_mutex_unlock(&mutex);
20: /* usa o recurso */
21: pthread_mutex_lock(&mutex);
22: ativas--;
23: pthread_mutex_unlock(&mutex);
24: pthread_exit(NULL);
25:}
Resp.: (a) Após ser desbloqueada a thread não está checando novamente se a condição de
uso do recurso continua favorável. Outras threads podem ter começado a usar o recurso antes dela
retornar completamente do bloqueio e, se isso ocorrer e já houver 3 threads acessando o recurso,
poderemos ter mais de 3 threads acessando o recurso ao mesmo tempo. Com relação ao deadlock,
ele está ocorrendo porque quando uma thread termina de usar o recurso ela não está atualizando a
variável deve esperar e também não está verificando se é necessário desbloquear outras threads que
estão esperando pela condição lógica da aplicação.
(b) Na linha 10, o if deve ser substituı́do por while para que a thread cheque se o estado
da aplicação continua válido para acessar o recurso após ela ser desbloqueada. Além disso, entre
as linhas 22 e 23 é necessário atualizar a variável deve esperar e desbloquear possı́veis threads
bloqueadas, caso a condição de uso do recurso tenha sido liberada. Código correto:
1: pthread_mutex_t mutex; //inicializado na main()
2: pthread_cond_t cond; //inicializado na main()
3: //variaveis de estado
4: int deve_esperar = 0;
5: int esperando = 0;
6: int ativas = 0;
7: //funcao executada pelas threads
8: void *recurso (void *tid) {
9: pthread_mutex_lock(&mutex);
10: while(deve_esperar) {
11: esperando++;
12: pthread_cond_wait(&cond, &mutex);
13: esperando--;
14: }
15: ativas++;;
16: deve_esperar = (ativas==3);
17: if(esperando>0 && !deve_esperar)
18: { pthread_cond_signal(&cond); }
19: pthread_mutex_unlock(&mutex);
20: /* usa o recurso */
21: pthread_mutex_lock(&mutex);
22: ativas--;
23: if(ativas==0) { deve_esperar=0; }
24: if(esperando>0 && !deve_esperar)
25: { pthread_cond_signal(&cond); }
26: pthread_mutex_unlock(&mutex);
27: pthread_exit(NULL);
28:}
Questão 2 (2,5 pts) Considere um tipo de dado opaco ITEM e a função int processaItem
(ITEM item) que processa um elemento desse tipo e retorna um valor inteiro. Sabe-se que o
tempo de processamento dessa função pode variar consideravelmente, dependendo do argumento
passado como entrada. (a) Escreva um programa concorrente em C com M threads para processar
os elementos de um vetor de ITEM de tamanho N, usando a função processaItem(). Con-
sidere que o vetor de itens ITEM itens[N] está definido como variável global e já foi inicializado.
Implemente a função executada pelas threads e na função main() tudo o que for necessário para
inicializar as variáveis, disparar as threads e aguardar pelo seu término. A carga de trabalho deverá
ser dividida igualmente entre as threads e os trechos de código com exclusão mútua deverão ser os
menores possı́veis. Todas as threads deverão executar a mesma tarefa. Comente seu código.
#define N 10000000
#define M 10
//variaveis globais
pthread_mutex_t bastao; //lock para exclusão mutua
int resultados[N]; //vetor de resultados
void * tarefa(void * args) {
//indice do proximo elemento do vetor de ITEM a ser processado
static long int i_global=0;
//indice local do elemento do vetor de ITEM a ser processado
//pela thread
long int i_local;
//pega um indice do vetor para processar
pthread_mutex_lock(&bastao);
i_local = i_global; i_global++;
pthread_mutex_unlock(&bastao);
while(i_localos recursos e sempre ao menos uma das threads vizinhas
está usando o recurso.
A possibilidade de ocorrer starvation é minimizada pelo fato da thread que libera um recurso
necessariamente disparar o procedimento que verifica se há condição no momento de uma thread
vizinha que já manifestou interesse em usar os recursos fazê-lo, antes que a mesma thread requisite
os recursos novamente.
Questão 4 (2,5 pts) Implemente uma classe em Java para resolver o problema dos leitores/escritores
garantindo ausência de starvation. Condições do problema: uma área de dados (ex., arquivo, bloco
da memória, tabela de uma banco de dados) é compartilhada entre diferentes threads; a leitura dos
dados pode ser feita por mais de uma thread ao mesmo tempo; a alteração/escrita de dados só pode ser
feita por uma thread de cada vez; enquanto uma alteração/escrita está sendo realizada não é permitido
leituras.
class Cluster {
private int leitE, escrE, vezLeit, leitU, escrU;
private boolean vezEscr;
// Construtor
Cluster() {
this.leitE = 0; //numero de leitores esperando
this.escrE = 0; //numero de escritores esperando
this.leitU = 0; //numero de leitores lendo
this.escrU = 0; //numero de escritores escrevendo (maximo 1)
this.vezLeit = 0; //sinaliza vez dos leitores esperando
this.vezEscr = false; //sinaliza vez dos escritores esperando
}
// Entrada para leitores
public synchronized void EntraLeit () {
try { while ((this.escrU > 0) || (this.escrE > 0)) {
this.leitE++;
wait(); //bloqueia pela condicao logica da aplicacao
this.leitE--;
if(this.vezLeit > 0) { //permite que os leitores esperando leiam
this.vezLeit--; break;
}
}
this.leitU++;
} catch (InterruptedException e) { }
}
// Saida para leitores
public synchronized void SaiLeit () {
this.leitU--;
if (this.leitU == 0) {
vezLeit = 0; //encerra o intervalo de acesso para os leitores
if(escrE > 0) { //passa a vez para os escritores esperando
vezEscr = true;
notifyAll(); //desbloqueia os escritores esperando
}
}
}
// Entrada para escritores
public synchronized void EntraEscr () {
try { while ((this.escrU > 0) || (this.leitU > 0) || (this.leitE > 0)) {
this.escrE++;
wait(); //bloqueia pela condicao logica da aplicacao
this.escrE--;
if(this.vezEscr) {
this.vezEscr=false; break;
}
}
this.escrU++;
} catch (InterruptedException e) { }
}
// Saida para escritores
public synchronized void SaiEscr () {
this.escrU--;
if(leitE > 0) {
vezLeit = leitE;
vezEscr = false;
notifyAll(); //desbloqueia leitores esperando
} else if (escrE > 0)
vezEscr = true;
notifyAll(); //desbloqueia escritores esperando
}
}
}