Lista 4 2010 2

Prévia do material em texto

4ª Lista de Exercícios de Paradigmas de Linguagens Computacionais
Professor: Fernando Castor
Monitores:
Paulo Barros <pbsf>,
Leonardo Brayner <lbs2>,
Cleivson Siqueira de Arruda <cleivson.tb@gmail.com>,
Irineu Moura <imlm2>,
Caio Sabino Silva <ccss2>
CIn-UFPE – 2010.2
Disponível desde: 29/11/2010
Entrega: 10/12/2010
A lista deverá ser respondida em dupla . A falha em entregar a lista até a data estipulada implicará na perda 
de 0,30 ponto na média da disciplina para os membros da dupla. Considera-se que uma lista na qual 
menos que 30,00% (menos que três) das respostas estão corretas não foi entregue. A entrega da lista com 
pelo menos 80,00% (oito ou mais) das questões corretamente respondidas implica em um acréscimo de 
0,15 ponto na média da disciplina para os membros da dupla. Se qualquer situação de cópia de 
respostas for identificada, os membros de todas as duplas envolvidas perderão 0,6 ponto na média da 
disciplina. O mesmo vale para respostas obtidas a partir da Internet. As respostas deverão ser entregues 
exclusivamente em formato texto ASCII (nada de .pdf, .doc, .docx ou .odt) e deverão ser enviadas para o 
monitor responsável por sua dupla, sem cópia para o professor. Tanto podem ser organizadas em arquivos 
separados, um por questão (e, neste caso, deverão ser zipadas), quanto em um único arquivo texto onde a 
resposta de cada questão está devidamente identificada e é auto-contida (uma
 parte da resposta de uma questão que seja útil para responder uma outra deve estar duplicada neste 
última).
Obs. Para resolver as questões desta lista, é explicitamente permitido empregar a biblioteca 
java.util.concurrent, exceto nas questões onde é dito que a resposta deve ser escrita na linguagem 
Haskell.
1º) Implemente, usando filas bloqueantes (BlockingQueue's), uma solução em Java para uma variação do 
problema do Produtor e do Consumidor onde há vários (dois ou mais, conforme definido pelo usuário) 
produtores e cada um tem seu próprio buffer (um por produtor). Os buffers de todos os produtores têm a 
mesma capacidade. Além disso, o sistema tem vários consumidores (mesma quantidade que a de 
produtores). Cada produtor coloca itens produzidos apenas em seu buffer particular mas consumidores 
podem consumir itens de qualquer buffer. Fora isso, as mesmas regras do Produtor-Consumidor básico 
valem: consumidores não podem consumir de um buffer vazio, embora possam tentar consumir de outro 
buffer, produtores não podem produzir além da capacidade de seus buffers e o sistema nunca pode entrar 
em deadlock. Não é permitido usar a implementação do buffer da sétima questão da Lista 3 para resolver 
esta.
2º) Reimplemente a solução para a primeira questão da Lista 3 usando ThreadPool's, ou seja, sem criar 
explicitamente as threads. Compare o desempenho dessa solução com a da primeira questão da Lista 3. 
Inclua essa comparação como um arquivo texto junto com sua resposta.
3º) Para cada um dos itens abaixo, faça o que se pede:
(a)
public class Conta {
 private double saldo = 0;
 public void debitar(double valor) {
 if (valor <= saldo) { saldo = saldo - valor;
 } else System.out.println("Saldo Insuficiente.");
 }
 public void creditar(double valor) { saldo = saldo + valor; }
 public static void main(String args[]) {
 final Conta c1 = new Conta();
 final Conta c2 = new Conta();
 long t = System.currentTimeMillis();
 c1.creditar(60000000.0); 
 Thread t1 = new Thread(new Trans(c1,c2)); Thread t2 = new Thread(new Trans(c1,c2));
 Thread t3 = new Thread(new Trans(c1,c2)); Thread t4 = new Thread(new Trans(c1,c2));
 Thread t5 = new Thread(new Trans(c1,c2)); Thread t6 = new Thread(new Trans(c1,c2));
 t1.start(); t2.start(); t3.start(); t4.start(); t5.start(); t6.start();
 try { t1.join(); t2.join(); t3.join(); t4.join(); t5.join(); t6.join(); 
 } catch(InterruptedException e) {}
 System.out.println("C1: " + c1.saldo + " C2: " + c2.saldo);
 System.out.println("Tempo: " + (System.currentTimeMillis() - t));
 }
}
class Trans implements Runnable {
 private Conta c1; private Conta c2;
 Trans(Conta c1, Conta c2) { this.c1 = c1; this.c2 = c2; } 
 public void run() {
 for(long i = 0; i < 1000000; i++) { c1.debitar(10); c2.creditar(10); }
 }
}
Modifique as implementações das duas classes de modo que, ao final da execução, c1 tenha saldo 0,0 e c2 
tenha saldo 60000000,0. É proibido modificar a classe Conta e é proibido usar synchronized e travas 
explícitas; 
(b)
public class AgenteConta implements Runnable {
 private double saldo = 1000000.0;
 private AgenteConta[] contas = new AgenteConta[3]; 
 public AgenteConta() {};
 public AgenteConta(AgenteConta c1, AgenteConta c2, AgenteConta c3) {
 contas[0] = c1; contas[1] = c2; contas[2] = c3;
 }
 public void debitar(double valor) {
 if (valor <= saldo) { saldo = saldo - valor;
 } else System.out.println("Saldo Insuficiente.");
 }
 public void creditar(double valor) { saldo = saldo + valor; }
 public void transferir(AgenteConta c, double quantia) { 
 c.saldo = c.saldo - quantia; this.saldo = this.saldo + quantia; }
 public void run() {
 for(long i = 0; i < 100000; i++) {
 contas[0].debitar(1); contas[1].debitar(1); contas[2].debitar(1);
 this.creditar(3);
 this.transferir(contas[0],1);this.transferir(contas[1],1);this.transferir(contas[2],1);
 }
 }
 public static void main(String args[]) {
 long t = System.currentTimeMillis();
 AgenteConta c1 = new AgenteConta(); AgenteConta c2 = new AgenteConta(); 
 AgenteConta c3 = new AgenteConta(); AgenteConta c4 = new AgenteConta(c1,c2,c3);
 c1.contas = new AgenteConta[] { c2, c3, c4 };
 c2.contas = new AgenteConta[] { c1, c3, c4 };
 c3.contas = new AgenteConta[] { c1, c2, c4 };
 Thread t1 = new Thread(c1); Thread t2 = new Thread(c2);
 Thread t3 = new Thread(c3); Thread t4 = new Thread(c4);
 t1.start(); t2.start(); t3.start(); t4.start(); 
 try { t1.join(); t2.join(); t3.join(); t4.join(); 
 } catch(InterruptedException e) {}
 System.out.println("C1: "+c1.saldo+" C2: "+c2.saldo+" C3: "+c1.saldo+" C4: "+c2.saldo);
 System.out.println("Tempo: " + (System.currentTimeMillis() - t));
 }
}
Modifique a implementação da classe AgenteConta de modo que, ao final da execução, suas quatro 
instâncias sempre tenham o mesmo saldo (1.000.000,00). É proibido modificar o método main() e é 
proibido também usar travas ou monitores, globais ou locais. Também é proibido mudar a lógica da 
aplicação (i.e., cada instância de AgenteConta deve continuar debitando das três outras contas, creditando 
para si e, em seguida, transferindo uma unidade para cada uma das outras contas) e a sequência de 
operações realizadas no método run().
4º) Implemente em Java uma versão sequencial do algoritmo MergeSort de ordenação capaz de ordenar 
arrays de números inteiros (tipo long). Crie também um método main() que gera um array com 
10.000.000 de posições e a mesma quantidade de números aleatórios e solicita que sua implementação do 
MergeSort os ordene. Agora torne paralela a sua implementação e mostre que sua implementação paralela 
é mais rápida que a sequencial e funcionalmente equivalente (produz os mesmos resultados para as 
mesmas entradas). Se necessário, aumente o tamanhodo heap da JVM para reduzir a quantidade de colta 
de lixo que ela realiza (para isso, é recomendável usar uma máquina com uma grande quantidade de 
memória RAM).
5º) Reimplemente a solução da questão anterior sem usar synchronized ou locks explícitos. Compare o 
desempenhodessa versão com a produzida para a questão 4.
6º) Construa um programa em Haskell que, dado um número N muito grande, determina pelo método da 
força bruta se ele é primo ou não e, também, a quantidade de divisores inteiros maiores que 1 que o maior 
número não-primo menor ou igual a N tem. Construa uma versão alternativa desse programa que usa 
paralelismo semi-explícito e que seja mais eficiente que a versão original. Mostre que o desempenho é, de 
fato, melhor.
7º) Considere a implementação abaixo do algoritmo MergeSort em Haskell: 
--Fonte: http://en.literateprograms.org/Merge_sort_(Haskell)?oldid=5460
split :: [a] -> ([a],[a])
split xs = splitrec xs xs []
splitrec :: [a] -> [a] -> [a] -> ([a],[a])
splitrec [] ys zs = (reverse zs, ys)
splitrec [x] ys zs = (reverse zs, ys)
splitrec (x1:x2:xs) (y:ys) zs = splitrec xs ys (y:zs) 
merge :: (a -> a -> Bool) -> [a] -> [a] -> [a]
merge pred xs [] = xs
merge pred [] ys = ys
merge pred (x:xs) (y:ys) =
 case pred x y of
 True -> x: merge pred xs (y:ys)
 False -> y: merge pred (x:xs) ys
mergesort :: (a -> a -> Bool) -> [a] -> [a]
mergesort pred [] = []
mergesort pred [x] = [x]
mergesort pred xs = merge pred (mergesort pred xs1) (mergesort pred xs2)
 where
 (xs1,xs2) = split xs
Desenvolva, usando paralelismo semi-explícito, uma versão paralela do MergeSort usando como base a 
implementação acima. Mostre que sua versão paralela tem um desempenho pelo menos tão bom quanto a 
versão original, para entradas grandes (1.000.000 ou mais elementos).
8º) Implemente uma solução em Haskell para uma variação do problema do Produtor e do Consumidor 
onde há vários (dois ou mais, conforme definido pelo usuário) produtores e cada um tem seu próprio buffer 
(um por produtor). Os buffers de todos os produtores têm a mesma capacidade (pelo menos 10 posições). 
Além disso, o sistema tem vários consumidores (mesma quantidade que a de produtores). Cada produtor 
coloca itens produzidos apenas em seu buffer particular mas consumidores podem consumir itens de 
qualquer buffer. Fora isso, as mesmas regras do Produtor-Consumidor básico valem: consumidores não 
podem consumir de um buffer vazio, embora possam tentar consumir de outro buffer, e produtores não 
podem produzir além da capacidade de seus buffers. Além disso, o sistema nunca pode entrar em deadlock.
9º) Reimplemente a solução para o item anterior usando memória transacional. Avalie o desempenho das 
duas soluções, considerando que os produtores produzem, cada um, pelo menos 1.000.000 de itens (e não 
esperam para cada item produzido, antes de produzir o próximo).
10º) Implemente uma versão paralela do algoritmo QuickSort em Haskell usando threads criadas 
explicitamente. Otimize essa versão paralela do QuickSort e mostre empiricamente que seu desempenho é 
melhor que o do QuickSort sequencial em Haskell.