lista 3 2012 1

Prévia do material em texto

3ª Lista de Exercícios de Paradigmas de Linguagens Computacionais
Professores: Fernando Castor e Márcio Cornélio
Monitores:
Ciência da computação: Alberto Costa Jr. (arcj), David Hulak (dbh), Glauco dos 
Santos (grps), Jessica Barbalho (jcb), Renato Oliveira (rso), Luís Gabriel Lima (lgnfl), 
Vanessa Gomes (vgl), Walter Lima Filho (wflf)
Engenharia da Computação: Alan Gomes (aga), Álvaro Silvino (ajsss), Felipe 
Araújo (fsa2), Gabriel Avelar (gafm), Larissa Paz (lorp), Lívia Vilaça (lcjbv), Lucas 
Inojosa (licf), Pedro Araujo (pam2).
CIn-UFPE – 2012.1
Disponível desde: 10/05/2012
Entrega: 31/05/2012
A lista deverá ser respondida em dupla. A falha em entregar a lista até a data 
estipulada implicará na perda de 0,25 ponto na média da disciplina para os membros 
da dupla. Considera-se que uma lista na qual menos que 4 das respostas estão 
corretas não foi entregue. A entrega da lista com pelo menos 7 das questões 
corretamente respondidas implica em um acréscimo de 0,125 ponto na média da 
disciplina para os membros da dupla. A questão 5 é obrigatória e não respondê-la é 
equivalente a não entregar nenhuma resposta. Se qualquer situação de cópia 
de respostas for identificada, os membros de todas as duplas envolvidas 
perderão 0,5 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. Devem ser 
organizadas em arquivos separados, um por questão, entregues em um único formato 
compactado, ou seja, um único arquivo zipado contendo as respostas para todas as 
questões. 
1) Está acontecendo uma competição de programação (para programadores extrema-
mente rápidos e que nunca erram), em que N (>=2) times devem resolver uma quanti-
dade Y (>0) de questões. Considere as seguintes informações:
- Cada time é composto por três membros.
- Só é fornecido um computador para cada time (logo os membros terão que se re-
vezar no computador).
- A resolução de uma questão é feita individualmente por cada membro do time em 
duas etapas: Leitura/entendimento e Programação 
- Cada membro do time lê/entende uma questão no tempo entre 1000ms e 1500ms 
e depois vai programa-la caso o computador esteja livre, caso contrário espera até 
que o computador esteja livre.
- Cada membro do time quando estiver ocupando o computador, programa a ques-
tão que foi lida/entendida no tempo entre 500ms e 2000ms, ao final ele vai ler outra 
questão liberando o computador para outro membro do time.
– Assim que um time resolver as Y questões a competição será interrompida. Im-
prima o ranking dos times em ordem decrescente do número de questões que cada 
um resolveu.
–
2) P pessoas querem se inscrever em um curso de uma instituição. Há B balcões com 
B atendentes para inscrever essas P pessoas. A cada balcão é designada uma fila de 
pessoas com no máximo 10 pessoas por fila. Cada pessoa tem uma identificação (um 
número natural chamado de ID). Quando uma pessoa chega para se inscrever em um 
curso, ela precisa entrar em uma fila de um balcão. O número do balcão escolhido para 
uma determinada pessoa é ID%B. 
 Cada pessoa só pode ser inscrita uma vez (logo, só pode entrar em uma fila de 
um balcão uma vez). A ordem em que cada pessoa chega à instituição deve ser 
aleatória (sugestão: utilize Collection.shuffle() para criar uma lista de pessoas 
desordenada). Se uma pessoa entra na instituição e a fila na qual deve entrar está 
cheia, esta pessoa deve esperar que um espaço seja liberado na fila. Se um atendente 
não tem ninguém para atender, ele vai dormir por 1 milissegundo.
Cada balcão atende pessoas concorrentemente. Considere que a instituição 
possui 5 entradas e que as pessoas entram aleatoriamente (utilize Math.random()) por 
elas e de modo concorrente. Cada pessoa entra por uma determinada entrada a cada 1 
segundo. Se a fila desse balcão estiver cheia quando a pessoa tentar entrar, ela espera 
pacientemente até que uma vaga seja aberta na fila e a entrada fica bloqueada por esta 
pessoa esperando. O seu programa deve terminar quando todas as pessoas forem 
inscritas no curso ou quando o programa rodar por T segundos. 
Coloque T, P e B como constantes estáticas na mesma classe que contém a 
função main. As pessoas escolhidas serão armazenadas em uma 
LinkedBlockingQueue, cada fila deve ser uma ArrayBlockingQueue de capacidade 10 e 
cada balcão deve ser armazenado em um ConcurrentHashMap de tamanho B. Ou seja, 
cada chave do map é ID%B e cada valor é o balcão correspondente (cada balcão 
contendo seu ArrayBlockingQueue).
Seu programa deve realizar as seguintes impressões (seguidas de uma quebra 
de linha) em um arquivo de texto, quando o evento em questão ocorrer:
- “A pessoa i entrou pela porta p”, em que p é o número da porta (de 0 a 4) e i é o ID 
da pessoa (de 0 a P-1).
- Quando um atendente terminar de atender uma pessoa (ou seja, colocou-a na fila), 
deve ser impresso “O atendente b terminou de atender a pessoa p”, em que b é o 
número do balcão (de 0 até B-1).
- “A pessoa p entrou na fila do balcão b”.
- Ao término do programa devem ser impressos os ID’s das pessoas escolhidas, na 
ordem em que forem escolhidas, separados por um espaço em branco.
3)O programa abaixo representa uma cafeteria onde existem N banheiros e C 
consumidores. Esses consumidores bebem café e usam o banheiro. Para usar o 
banheiro o consumidor precisa pegar a chave do banheiro, e assim que terminar de 
usar o banheiro o consumidor coloca a chave no quadro de chaves dos banheiros. 
Logo, o consumidor só pode usar um banheiro se houver chaves disponíveis no 
quadro.
Nesta questão você deverá modificar o programa abaixo para que deixe de utilizar 
escopos sincronizados e passe a utilizar exclusivamente tipos de dados atômicos 
(aqueles que existem no pacote java.util.concurrent.atomic). O programa 
resultante de suas modificações deve se comportar exatamente da mesma forma que o 
programa abaixo e nunca deve entrar em deadlock ou apresentar condições de corrida.
import java.util.Scanner;
class Consumidor extends Thread{
int loop;
int passo = 1;
int nome;
boolean continua = true;
public Consumidor(int qtdLoop, int n){
this.loop = qtdLoop;
this.nome = n;
}
@Override
public void run() {
System.out.println("Consumidor"+this.nome+"entrou!");
while(this.continua){
/**
 * Consumidor entra na cafeteria e por K vezes
 * 
 * Bebe café
 * Pega uma chave
 * Usa o banheiro
 * Devolve a chave
 * 
 * Sai da cafeteria
 * 
 * */
//Bebe café
if(this.passo == 1){
System.out.println("Consumidor"+this.nome+"está bebendo café!");
int tempo = (int)((Math.random()*3000) + 8000);
try {
sleep(tempo);
} catch (InterruptedException e) {
e.printStackTrace();
}
this.passo = 2;
}
// Pega chave
if(this.passo == 2){
if(Cafeteria.decrementaQuadro()){
this.passo = 3;
}
}
//Usa o banheiro
if(this.passo == 3){
System.out.println("Consumidor"+this.nome+"está usando o banheiro!");
int tempo = (int)((Math.random()*3000) + 8000);
try {
sleep(tempo);
} catch (InterruptedException e) {
e.printStackTrace();
}
this.passo = 4;
}
//Devolve a chave
if(this.passo == 4){
if(Cafeteria.incrementaQuadro()){
this.loop--;
this.passo = 1;
}
}
if(this.loop == 0){
this.continua = false;
}
}
System.out.println("Consumidor " + this.nome + " saiu da cafeteria!");
}
}
public class Cafeteria {
static int quadro;
static int chave;
public Cafeteria(int n, int consumidores, int loop) {
quadro = n;
chave = n;
for (int i = 1; i <= consumidores; i++) {
Consumidorconsu = new Consumidor(loop, i);
consu.start();
}
}
public static synchronized boolean incrementaQuadro(){
if(quadro < chave){
quadro++;
return true;
}else{
return false;
}
}
public static synchronized boolean decrementaQuadro(){
if (quadro > 0){
quadro--;
return true;
}else{
return false;
}
}
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.println("Quantos banheiros existem na Cafeteria? ");
int banheiros = console.nextInt();
System.out.println("Quantos consumidores estão na cafeteria? ");
int consumidores = console.nextInt();
System.out.println("Quantes idas ao banheiro? ");
int k = console.nextInt();
Cafeteria cafe = new Cafeteria(banheiros, consumidores, k);
}
}
4) Imagine que exista um mapa, representado por um array bidimensional de inteiros, 
onde duas formigas possam andar sobre ele. A cada instante, cada formiga escolhe 
aleatoriamente uma posição ao seu redor para se mover, mas, se a posição escolhida já 
estiver ocupada por outra formiga, aguarda até que esse espaço seja liberado. Leia o 
código java abaixo, identifique o que está causando o deadlock e encontre uma solução 
simples para resolver o problema que não resulte em outros problemas, como 
condições de corrida e starvation.
public class Ant {
private int[][] mapa;
public Ant(){
//Bidimensional map
mapa = new int[3][3];
Formiga f1 = new Formiga("Philip Fry", mapa, 0, 0);
mapa[0][0] = 1;
Formiga f2 = new Formiga("Bender Rodriguez", mapa, 1, 1); 
mapa[1][1] = 1;
f1.start(); f2.start();
}
public static void main(String[] args){
new Ant();
}
}
class Formiga extends Thread {
private int[][] mapa;
private int posicaoX;
private int posicaoY;
private String nome;
public Formiga(String nome, int[][] mapa, int posicaoX, int posi-
caoY){
this.nome = nome;
this.mapa = mapa;
this.posicaoX = posicaoX;
this.posicaoY = posicaoY;
}
private void printMap(){
for (int i = 0; i < mapa.length; i++){
for (int j = 0; j < mapa[i].length; j++){
System.out.print(mapa[i][j] + " ");
}
System.out.println();
}
}
public void run(){
while (true){
andar();
}
}
public synchronized void andar(){
int novoX = posicaoX;
int novoY = posicaoY;
//Choosing new place to go
while (novoX == posicaoX && novoY == posicaoY){
//Randomizing new position
novoX = (int) ((posicaoX - 1) + (Math.round(Math.ran-
dom()*2)));
novoY = (int) ((posicaoY - 1) + (Math.round(Math.ran-
dom()*2)));
//Keeping new position inside array bounds
if (novoX < 0) novoX = 0;
if (novoY < 0) novoY = 0;
if (novoX >= mapa.length) novoX = mapa.length - 1;
if (novoY >= mapa[novoX].length) novoY = 
mapa[novoX].length - 1;
}
System.out.println("[" + nome + "] Anterior: (" + posicaoX 
+ "," + posicaoY + "); Nova posição: (" + novoX + "," + novoY + ")");
while (mapa[novoX][novoY] == 1){
//Wait before new position is free
}
//Performing movement
mapa[posicaoX][posicaoY] = 0;
mapa[novoX][novoY] = 1;
posicaoX = novoX;
posicaoY = novoY;
System.out.println(nome + " andou");printMap();
//Rest a little
try {
sleep((long) (25 + Math.random() * 50));
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
5) Considere que uma galinha pode ser modelada por 4 Threads. Cada thread 
representa a função de uma parte do corpo.
Os olhos procuram por comida e informam ao cérebro sempre que alguma 
comida for detectada. Uma vez que a comida é localizada, o cérebro avisa aos pés para 
se moverem certa distância com o objetivo de alcançar a comida. Uma vez que os pés 
tiverem movido a distância indicada, eles informam ao cérebro, e esse, por sua vez, 
avisa a boca para começar a comer.
Essas galinhas não tem memória, a qualquer momento os olhos podem 
identificar outra comida. Isso vai acarretar em: o cérebro avisar aos pés para parar 
qualquer caminhada e a boca parar de comer, os pés começarem a se mover em 
direção a nova comida, e em seguida comê-la.
Escreva um programa que simula o comportamento dessa galinha. As threads 
devem se comportar como descrito abaixo:
- Olhos: procuram por comida a cada tempo t ms (t está entre 1000 e 2000), 
achando comida 50% das vezes. Cada vez que os olhos buscam por comida a string 
"procurando..." é impressa.
- Cérebro: recebe sinal dos olhos indicando que foi encontrado comida. Uma vez 
informado, a string "comida!" é impressa e em seguida informa a boca para parar de 
comer, aos pés para pararem qualquer movimentação e se moverem em direção à nova 
comida encontrada. Uma vez que os pés indicam que o destino foi alcançado a string 
"yes!" é impressa e a boca é avisada para começar a comilança.
- Pés: recebem sinal do cérebro indicando nova comida. Uma vez avisados, 
param qualquer movimento que esteja sendo feito, e movem-se um número randômico 
de passos (entre 5 e 10) en direção à nova comida. São gastos 400ms por passo. 
Depois de cada passo deve-se imprimir a string "passo". Uma vez que uma sequência 
de passos tenha sido finalizada, o cérebro deve ser avisado que o destino já foi 
alcançado.
- Boca: aguarda por um sinal do cérebro para começar a comer. Fica comendo 
até que seja informada para parar. Cada bocanhada leva 400ms e para cada uma deve 
ser impresso uma string "comendo".
A simulação só deve terminar quando o usuário matar o processo. Sua 
implementação não pode empregar travamento explícito ou monitores (nada de locks, 
synchronized, wait, notify, signal, await, etc.).
6) Considere a Classe ProdutorConsumidor abaixo:
import java.util.Stack;
public class ProdutorConsumidor {
public static Stack<Integer> buffer = new Stack<Integer>();
public static void main(String[] args) {
Runnable produtor = new Runnable() {
public void run() {
for(int i = 0; i < 100000; i++){
buffer.push(i);
}
}
};
Runnable cons = new Runnable() {
public void run() {
for(int i = 0; i < 100000; i++){
System.out.println(buffer.pop());
}
}
};
new Thread(produtor).start();
new Thread(cons).start();
}
}
Edite a classe ProdutorConsumidor para que, utilizando apenas o conceito de monitores 
e comunicação entre threads, ela funcione como funcionaria se fosse sequencial, exce-
to pela ordem em que as operaçõs push() e pop() são chamadas, em todas as situa-
ções. (não utilize locks explícitas, nem o método sleep()). Considere que a pilha pode 
ter no máximo 200 itens e certifique-se de que não é possível incluir itens nela quando 
ela já alcançou esse limite nem remover itens quando está vazia.
7) Barracas de tiro ao alvo são muito comuns em festividades juninas. Uma barraca 
possui 4 caixas que vendem os tiros. Existem pacotes de compras diferentes (De 3 tiros 
por vez até 20 tiros por vez - pacotes de tiros), e por isso, cada vez que o cliente com-
pra "a vez", ele pode pagar preços diferentes. A barraca tem estrutura pra funcionar 
para pelo menos 400 clientes, e a quantidade de clientes, o nome, o preço de cada pa-
cote de tiros devem ser definidos num arquivo à parte - na definição do arquivo, gere a 
quantidade de tiros de cada cliente aleatoriamente. Um cliente pode querer dar mais ti-
ros do que estão disponíveis no pacote máximo de 20 tiros. Neste caso, ele compra ti-
ros, espera um tempo (durante o qual ele está dando os tiros) e depois volta para a bar-
raca. O preço dos tiros é único. (Você pode muito bem nomear os clientes como C1, C2, 
C3, etc.)
Modele cada cliente e cada barraca como uma thread diferente. Além disso, vo-
cênão precisa modelar explicitamente o momento em que o cliente vai atirar (a thread 
apenas espera por um período de 1s), apenas aquele em que ele compra os tiros. 
Como dito, considere que existem de 3 a 20 tipos de pacotes de tiro diferentes e que a 
escolha do pacote que será vendido é feita aleatoriamente. Os clientescompram paco-
tes de tiros em intervalos aleatórios. Imprima na tela, para cada cliente, o nome, a quan-
tidade de tiros comprada e o total gasto. Considere que por noite de trabalho, a barraca 
vende pelo menos 10000 tiros.
8) Crie um semáforo de trânsito um pouco mais inteligente que os semáforos 
existentes atualmente. Imagine um cruzamento onde há um semáforo de dois tempos, 
um tempo controla se os carros da vertical devem seguir ou parar e o outro tempo 
controla se os carros da horizontal devem seguir ou parar. Os carros não podem dobrar, 
eles só podem seguir em frente no cruzamento. Cada tempo deve ficar aberto durante 
um intervalo X de segundos que deverá ser determinado pelo usuário. Contudo há duas 
situações onde esse intervalo pode ser desrespeitado: se em X/4 segundos nenhum 
carro passar no cruzamento, em nenhum dos sentidos, o sinal fecha e seu oposto abre; 
se alguma fila da direção oposta atingir um número Y de carros, definido pelo usuário, o 
tempo para esta direção é aberto (consequentemente seu oposto é fechado).
Considere que cada carro leva 2 segundos para cruzar o semáforo, uma vez que 
ele esteja na primeira posição, se ele estiver na segunda posição ele leva o tempo do 
primeiro carro, mas o tempo dele mesmo, ou seja 4 segundos e por aí vai.
Em cada uma das 4 filas os carros aparecem em intervalos randômicos que podem vari-
ar de X/50 segundos a X/10 segundos e cada fila é independente da outra. O carro que 
aparecer ocupa a próxima posição disponível da fila.
Ambos os tempos nunca devem ficar abertos no mesmo momento, nem fecha-
dos no mesmo momento. Evite acidentes, mas não cause engarrafamento.
Obs: Sentido e direção são coisas diferentes. Neste caso direção é horizontal ou verti-
cal, cada uma com dois sentidos.
9) A cidade de GrayVille está em guerra! Devido aos recentes avanços da tecnologia 
local os ferreiros da cidade desenvolveram um tipo de canhão que é carregado com 3 
munições. Cada tiro demora 500ms e cada canhão demora 3 segundos para ser 
recarregado. Porém, devido a guerra, só existe na cidade uma pessoa capaz de 
recarregar os canhões. Considere que a cidade possui 5 canhões e quando um está 
sendo carregado e outro fica sem munição, ele entra em uma fila para aguardar sua 
vez. Considere também que existe uma quantidade finita de munição na cidade, quando 
acabar a munição imprima quantas balas cada canhão atirou.
Implemente o problema da cidade de GrayVille com locks explícitos e 
travamento não-bloqueante e considere cada canhão como uma thread.