final 2014 2 Maria Luiza Menezes Vieira

Prévia do material em texto

Prova Final de PLC (IF686)
Data: 26 de fevereiro de 2015. Tempo dispon´ıvel:
2h00m.
Prof.: Fernando Castor
1. (4,8 ptos., com cada acerto valendo 0,6 pto.) Considere
o programa Java em a seguir.
1 public class Conta {
2 double saldo;
3 String nome;
4 public Conta(String nm ,double amnt ) {
5 saldo=amnt;
6 nome=nm;
7 }
8 void depositar(double money){
9 saldo+= money;
10 }
11 void sacar(double money){
12 saldo -=money;
13 }
14 void transferir(Conta ac,double mn){
15 saldo -=mn;
16 ac.saldo +=mn;
17 }
18
19 public static void main(String args []) {
20 Conta c1 = new Conta("Vinculus", 100.00);
21 Conta c2 = new Conta("Stephen Black", 100.00);
22 Conta c3 = new Conta("Arabella", 100.00);
23 Conta c4 = new Conta("John Childermass", 100.00);
24 GerContas g1 = new GerContas(new Conta []{c1,c2,c3 ,c4});
25 GerContas g2 = new GerContas(new Conta []{c4,c3,c2 ,c1});
26 g1.start (); g2.start ();
27 try { g1.join(); g2.join();
28 } catch(InterruptedException e) {}
29 for(int i=0; i <= 3; i++) {
30 System.out.println(g1.contas[i]. saldo); }
31 for(int i=0; i <= 3; i++) {
32 System.out.println(g2.contas[i]. saldo); }
33
34 }
35 }
36 class GerContas extends Thread {
37 Conta[] contas=null;
38 public GerContas(Conta [] accs) {
39 contas = accs;
40 }
41 public void run(){
42 contas [0]. depositar (100);
43 contas [1]. transferir(contas [2] ,75);
44 contas [3]. sacar (50);
45 contas [0]. transferir(contas [3] ,100);
46 }
47 }
Marque verdadeiro (V) ou falso (F) em sua folha de respos-
tas para as proposic¸o˜es a seguir. E´ importante enfatizar que
a pontuac¸a˜o ma´xima desta questa˜o e´ de 4,8 pontos. Ale´m
disso, cada dois erros anulam um acerto. Isso significa que e´
poss´ıvel errar um dos itens e, ainda assim, obter nota ma´xima
na questa˜o. Tambe´m e´ poss´ıvel deixar duas das alternativas
em branco e, ainda assim, obter nota ma´xima na questa˜o.
Obs.1: nas proposic¸o˜es abaixo, sempre que e´ dito que o programa “pro-
duziria a mesma sa´ıda que produziria se fosse estritamente sequencial”,
isso significa que para todas as suas poss´ıveis execuc¸o˜es, o resultado sera´
sempre o mesmo e o programa na˜o entra em deadlock. Nesta questa˜o,
consideramos que os resultados produzidos pelo programa sa˜o
aqueles que ele imprime.
Obs.2: nas proposic¸o˜es abaixo, sempre que e´ dito que o programa “po-
deria entrar em deadlock”, isso significa que esse evento pode acontecer
em algumas das suas execuc¸o˜es (na˜o necessariamente todas).
(a) O programa, como esta´, nunca entra em deadlock.
(b) Se o modificador synchronized for adicionado aos
me´todos sacar(), transferir() e depositar(), o pro-
grama produzira´ a mesma sa´ıda que produziria se fosse
estritamente sequencial.
(c) Se as linhas 42-45 fossem substitu´ıdas por
synchronized (contas[0]) {
synchronized (contas[3]) {
... // conteudo das linhas 42-45
}
}
o programa produziria a mesma sa´ıda que produziria se
fosse sequencial.
(d) Se as linhas 42-45 fossem substitu´ıdas por
synchronized (contas[2]) {
... // conteudo das linhas 42-45
}
o programa na˜o entra em deadlock.
(e) Se Java tivesse uma classe chamada AtomicFloat,
ana´loga a AtomicInteger e AtomicLong, so´ que para
dados do tipo float, e o atributo saldo fosse do tipo
AtomicFloat (com operac¸o˜es como soma e subtrac¸a˜o
sendo implementadas usando os me´todos corresponden-
tes definidos por esta classe), o programa produziria a a
mesma sa´ıda que produziria se fosse sequencial.
(f) Considerando o cena´rio descrito no item anterior (com
saldo passando a ser do tipo AtomicFloat), se subs-
titu´ıssemos as linhas 42-45 por
synchronized (nome) {
... // conteudo das linhas 42-45
}
o programa pode entrar em deadlock.
(g) Se a classe GerContas armazenasse os objetos do tipo
Conta em um ConcurrentHashMap, ao inve´s de um vetor,
o programa na˜o poderia entrar em deadlock.
(h) Suponha que foi inclu´ıdo no programa o atributo
private static Lock[] locks = new Lock[3];
Cada posic¸a˜o de locks e´ inicializada no me´todo main()
com um objeto do tipo ReentrantLock. Ale´m disso, su-
ponha que as linhas 42-45 foram substitu´ıda pelas se-
guintes linhas:
locks[0].lock();
contas[0].depositar(100);
locks[1].lock();
contas[1].transferir(contas[2],75);
contas[3].sacar(50);
locks[1].unlock();
locks[2].unlock();
contas[0].transferir(contas[3],100);
locks[2].unlock();
locks[0].unlock();
Se fossem removidas a primeira e a segunda chamadas a
lock() (e as chamadas a unlock relativas aos mesmos
locks) o programa na˜o produziria a mesma sa´ıda que
produziria se fosse sequencial.
(i) Considerando o cena´rio do item anterior (a inclusa˜o do
atributo locks e etc.), se fossem removidas a segunda e
a terceira chamadas a lock() (e as chamadas a unlock
relativas aos mesmos locks) o programa na˜o produziria
a mesma sa´ıda que produziria se fosse sequencial.
(j) Se fossem removidas as linhas 27 e 28 do programa e os
me´todos da classe Conta fossem modificados de modo que
condic¸o˜es de corrida nunca ocorressem, este produziria
o mesmo resultado que produziria se fosse estritamente
sequencial.
2. (1,7 ptos) Determine o tipo da expressa˜o
map.(\x y z -> foldr y x z) func
onde func :: STM a -> IO a.
Dica: pense primeiro sobre a ordem de avaliac¸a˜o das sub-
expresso˜es, em outras palavras, onde ficariam os pareˆnteses.
3. (3,5 ptos) Implemente em Haskell uma func¸a˜o
mergeSort :: [Int] -> [Int]
que implementa o algoritmo mergesort.
Dica: o algoritmo mergesort funciona em duas etapas: split e
merge.