PPA+ +2019 01+ +parte+04

Prévia do material em texto

Programação Paralela
4ª parte
Prof. Jobson Massollar
jobson.silva@uva.br
Programação Paralela2
Threads
➢ Quando executamos um programa, o SO enxerga esse programa como
um processo.
➢ Cada processo tem um ID, memória para código e dados, pilha de
execução, permissões, descritores de arquivos, registradores, etc.
➢ Todo processo possui pelo menos uma thread, que é chamada de
thread principal.
➢ A thread principal pode iniciar outras threads, ou seja, um processo
pode ter várias threads.
➢ Cada thread tem sua própria memória local, mas pode acessar a
memória global do processo.
Programação Paralela3
Threads
➢ Para explorar o paralelismo com threads, um programa deve ser
projetado como um conjunto discreto de tarefas independentes que
podem ser executadas em paralelo (concorrentemente).
➢ Cada tarefa será executada em uma thread.
➢ Cada tarefa pode:
 Manipular um conjunto de dados distintos.
 Manipular um conjunto de dados compartilhados com outras
tarefas.
➢ É importante notar que os programadores são responsáveis por:
 Sincronizar a execução das tarefas (threads).
 Garantir a integridade dos dados compartilhados.
Programação Paralela4
Threads
➢ Apesar de estarem associadas a um mesmo processo, as threads
podem ser escalonadas e executadas pelo SO de forma independente.
➢ Cada thread terá acesso à CPU de acordo com:
✓ Cotas de tempo
✓ Prioridades
dependendo do Sistema Operacional.
Programação Paralela5
Threads em Java
➢ Temos duas formas de criar threads em Java:
1. Estendendo a classe Thread
✓Crie um nova classe que estende a classe Thread e sobrescreva
o método void run().
2. Implementando a interface Runnable
✓Crie um nova classe que estende a interface Runnable e
implemente o método void run().
Programação Paralela6
Threads em Java
1. Estendendo a classe Thread:
public class ExemploThread extends Thread {
private int repeticoes;
public ExemploThread(int repeticoes) {
this.repeticoes = repeticoes;
}
@Override
public void run() {
for (int i = 1; i <= repeticoes; i++)
System.out.printf("Linha %d\n", i);
}
}
Programação Paralela7
Threads em Java
2. Implementando a interface Runnable:
public class ExemploRunnable implements Runnable {
private int repeticoes;
public ExemploRunnable(int repeticoes) {
this.repeticoes = repeticoes;
}
@Override
public void run() {
for (int i = 1; i <= repeticoes; i++)
System.out.printf("Linha %d\n", i);
}
}
Programação Paralela8
Threads em Java
➢ Para executar a thread, precisamos criar o objeto e chamar o método
start().
1. Caso a thread estenda a classe Thread, executamos da seguinte
forma:
public static void main(String[] args) {
Thread t = new ExemploThread(100);
System.out.println("Inicio");
t.start();
System.out.println("Fim");
}
Programação Paralela9
Threads em Java
➢ Para executar a thread, precisamos criar o objeto e chamar o método
start().
2. Caso a thread implemente a interface Runnable, executamos da
seguinte forma:
public static void main(String[] args) {
Runnable r = new ExemploRunnable(100);
Thread t = new Thread(r);
System.out.println("Inicio");
t.start();
System.out.println("Fim");
}
Programação Paralela10
Exercícios
➢ Exercício 1: Altere a thread do exemplo anterior e acrescente um
nome para ela. O nome da thread deve ser impresso junto com o
número no método run(). Em seguida, dispare duas threads, cada
uma com um nome diferente.
Programação Paralela11
Classe Thread
➢ A classe Thread implementa vários métodos úteis:
✓ public void start(): faz a JVM chamar o método run() da thread.
✓ public static Thread currentThread(): retorna uma referência para a thread
que está executando no momento.
✓ public static void sleep(long tempo): faz com que a thread atual pare por 
tempo milissegundos. Após esse tempo, a thread volta para a fila de 
execução. 
✓ public static void yield(): para a execução da thread e a coloca na fila de 
execução. Isso faz com que outras threads da fila possam entrar em 
execução.
✓ Atenção: esse método não garante que a thread vai realmente parar porque 
ela pode ir para a fila de execução e ser selecionada novamente pelo SO, ou 
seja, a thread para e em seguida ganha novamente a CPU.
✓ public void join(): aguarda a thread terminar.
✓ public boolean isAlive(): verifica se a thread está viva.
Programação Paralela12
Classe Thread
➢ A classe Thread implementa vários métodos úteis:
✓ public String getName(): retorna o nome da thread.
✓ public void setName(String nome): altera o nome da thread.
✓ public void setPriority(int prioridade): altera a prioridade da thread. O 
valor de prioridade varia de 1 a 10. Existem 3 constantes pré-definidas: 
Thread.MIN_PRIORITY, Thread.MAX_PRIORITY e 
Thread.NORM_PRIORITY.
✓ public int getPriority(): retorna a prioridade da thread.
Programação Paralela13
Ciclo de Vida das Threads
fim do sleep
pronto
nascimento
executando
adormecido morto bloqueadoesperando
inicia E/S
completosleep
wait
notify ou
notifyAll
conclusão de 
E/S
despachar
(alocar um
processador)
start
yield ou expiração 
do quantum
1. Uma thread pode estar no estado executável (pronto em uma fila), executando e não-executável
(esperando, bloqueado, adormecido).
2. A thread entra no estado executável com start(), o que causa o início do método run(), e passa
para o estado morto quando o método run() chega ao fim.
Programação Paralela14
Exercícios
➢ Exercício 2: altere o exercício 1 e acrescente a chamada ao método
sleep(), após a impressão da mensagem. Crie mais um atributo na
classe para armazenar o tempo do sleep.
➢ Exercício 3: altere o exercício 1 e acrescente a chamada ao método
yield(), a cada N mensagens impressas. N deve ser um atributo da
thread.
➢ Exercício 4: crie um programa que simule trabalhadores que fabricam
produtos de couro simultaneamente. O programa deve perguntar o
nome, o produto e o tempo de descanso de cada trabalhador, antes
de iniciar a simulação. Durante a simulação, cada trabalhador deve
informar seu nome, o produto e a quantidade produzida e, ao final,
avisar que terminou a tarefa. Dica: use uma lista ou vetor de threads.
Programação Paralela15
Sincronização de Threads
➢ Em diversas situações precisamos sincronizar a execução de duas ou
mais threads, ou seja, só é possível executar determinado código
quando duas ou mais threads terminam as suas tarefas.
➢ Exemplo: para somar os números inteiros no intervalo de a..b
podemos quebrar esse intervalo em diversos subintervalos distintos e
executar a soma de cada subintervalo em uma thread.
Programação Paralela16
Sincronização de Threads
➢ Exemplo:
public class Soma extends Thread {
private long a;
private long b; 
private long soma; 
public Soma(long a, long b) {
this.a = a;
this.b = b;
}
public long getSoma() {
return soma;
}
@Override
public void run() {
soma = 0;
for (long i = a; i <= b; i++)
soma += i;
}
}
Programação Paralela17
Sincronização de Threads
➢ Exemplo:
public class Somatorio {
public static void main(String[] args) {
Soma s1 = new Soma(1, 10000);
Soma s2 = new Soma(10001, 20000);
long total;
s1.start();
s2.start();
total = s1.getSoma() + s2.getSoma();
System.out.printf("Total = %d\n, total); 
}
}
O que está errado nessa 
implementação ?
Programação Paralela18
Sincronização de Threads
➢ Exemplo:
public class Somatorio {
public static void main(String[] args) {
Soma s1 = new Soma(1, 10000);
Soma s2 = new Soma(10001, 20000);
long total;
s1.start();
s2.start();
total = s1.getSoma() + s2.getSoma();
System.out.printf("Total= %d\n, total); 
}
}
Só podemos pegar o 
valor da soma de s1 e s2 
depois que as threads
terminarem!
Programação Paralela19
Método join()
➢ Usamos o método join() quando precisamos aguardar uma ou mais
threads terminarem.
➢ Ao executar o método join() em uma thread, esse método só retorna
quando a thread entra no estado de morto (ou seja, terminou).
➢ Assim, o join() serve para sincronizar a execução de alguns trechos de
código, pois temos certeza que a(s) thread(s) terminou (aram).
➢ Para corrigir o exemplo anterior devemos garantir que todas as
threads que somam os subintervalos terminaram de executar.
Programação Paralela20
Método join()
➢ Exemplo:
public class Somatorio {
public static void main(String[] args) {
Soma s1 = new Soma(1, 100);
Soma s2 = new Soma(101, 200);
long total;
s1.start();
s2.start();
try {
s1.join();
s2.join();
} catch(InterruptedException e) {}
total = s1.getSoma() + s2.getSoma();
System.out.printf("Total = %d\n", total); 
}
}
O método join() pode gerar 
uma InterruptedException. 
Por isso precisamos do 
try..catch.
Programação Paralela21
Exercícios
➢ Exercício 5: crie um programa para calcular o fatorial de um número
(25, por exemplo) e meça o tempo do cálculo. Em seguida, crie uma
thread que recebe dois números, que formam um intervalo, e calcule a
multiplicação dos números desse intervalo. Por exemplo:
✓ 1 a 10: multiplica os números de 1 a 10
✓ 15 a 30: multiplica os números de 15 a 30.
Em seguida, use essas threads para calcular o fatorial novamente,
dividindo o número. Por exemplo: para calcular o fatorial de 25, pode
dividir em duas threads de 1 a 12 e 13 a 25, e depois multiplicar o
resultado de cada thread.
Dicas:
✓ Use o método join() para sincronizar as threads.
✓ Use a classe BigDecimal para armazenar o fatorial.
✓ Use o método System.nanoTime() para medir o tempo.
✓ Experimente executar o cálculo com 1, 2, 4 e 8 threads e meça os tempos.
Programação Paralela22
Race Conditions
➢ Quando múltiplas threads tentam acessar o mesmo recurso podem
ocorrer race conditions (condições de corrida).
➢ O recurso pode ser:
 Uma variável;
 Um objeto (no caso de linguagens OO);
 Um arquivo;
 Uma conexão de rede;
 etc.
➢ O termo race conditions é usado para essa situação porque várias
threads correm umas contra as outras para terminar a execução.
Programação Paralela23
Race Conditions
➢ Exemplo 1:
 Duas threads tentam acessar a mesma variável para realizar
alterações.
 Não é possível definir em que ordem essas alterações serão feitas,
uma vez que o SO pode escalonar a execução das threads em
qualquer ordem.
Thread 1
x = x / 2
x++;
Thread 2
x = x * 2
x -= 2;
x
10 → 9
Thread 1
x = x / 2
x++;
Thread 2
x = x * 2
x -= 2;
x
10 → 10
Programação Paralela24
Race Conditions
➢ Exemplo 2:
 Classe ContaCorrente com métodos para sacar e depositar.
public ContaCorrente {
private float saldo = 0;
public void depositar(float valor) { saldo = saldo + valor; }
public void sacar(float valor) { saldo = saldo - valor;}
}
Programação Paralela25
Race Conditions
➢ Exemplo 2:
 Classe ContaCorrente com métodos para sacar e depositar.
 Threads distintas executam operações de depósito e saque no
mesmo objeto.
public Thread1 extends Thread {
private ContaCorrente conta;
public Thread1(ContaCorrente conta) {
this.conta = conta;
}
public void run() {
conta.depositar(100);
conta.depositar(200);
}
}
public Thread2 extends Thread {
private ContaCorrente conta;
public Thread2(ContaCorrente conta) {
this.conta = conta;
}
public void run() {
conta.sacar(50);
}
}
Programação Paralela26
Race Conditions
Thread 1 Thread 2 Saldo
conta.depositar(100) - 0
saldo + valor → (0 + 100) - 0
saldo ← 100 - 100
conta.depositar(200) - 100
saldo + valor → (100 + 200) - 100
- conta.sacar(50) 100
- saldo – valor → (100 - 50) 100
- saldo ← 50 50
saldo ← 300 300
O valor 
deveria ser 
250!
public ContaCorrente {
private float saldo = 0;
public void depositar(float valor) { saldo = saldo + valor; }
public void sacar(float valor) { saldo = saldo - valor;}
}
Programação Paralela27
Blocos Síncronos
➢ Nesses exemplos percebemos que existem partes de um programa,
denominadas regiões críticas, que podem gerar dados inconsistentes.
➢ O problema está no fato desses trechos de programa poderem ter a
sua execução interrompida pelo SO.
➢ Para evitar esta situação, o acesso a essas regiões críticas deve ser
sincronizado.
➢ Os blocos síncronos são os recursos do Java para sincronizar o acesso
a determinadas partes do código e, com isso, evitar as situações de
race condition.
Programação Paralela28
Blocos Síncronos
➢ Um bloco síncrono delimita um trecho de código e está sempre
associado a um objeto.
➢ Ao iniciar um bloco síncrono é realizado um lock no objeto associado
ao mesmo.
➢ Estando o objeto bloqueado, nenhuma outra thread pode acessá-lo
até que ele seja desbloqueado.
➢ O objeto é automaticamente desbloqueado assim que o bloco síncrono
termina de executar.
➢ Cada objeto tem seu próprio lock.
Programação Paralela29
Blocos Síncronos
➢ Um bloco síncrono é definido com o uso da palavra synchronized.
➢ Um bloco síncrono pode ser:
1. Apenas um trecho de código
synchronized (objeto que será bloqueado) {
comandos
}
2. Um método inteiro
public syncronized tipo nome_método(parâmetros) {
comandos
}
Programação Paralela30
Blocos Síncronos
public ContaCorrente {
private float saldo = 0;
public synchronized void depositar(float valor) { saldo = saldo + valor; }
public synchronized void sacar(float valor) { saldo = saldo - valor;}
}
public Thread1 extends Thread {
private ContaCorrente conta;
public Thread1(ContaCorrente conta) {
this.conta = conta;
}
public void run() {
conta.depositar(100);
conta.depositar(200);
}
}
Quando um método synchronized
de um objeto é executado isso 
significa que NENHUM outro 
método pode ser executado para 
esse objeto até esse método 
terminar.
Programação Paralela31
Blocos Síncronos
Thread 1 Thread 2 Saldo
conta.depositar(100) - 0
saldo + valor → (0 + 100) - 0
saldo ← 100 - 100
conta.depositar(200) - 100
saldo + valor → (100 + 200) - 100
saldo ← 300 - 300
- conta.sacar(50) 300
- saldo – valor → (300 - 50) 300
- saldo ← 250 250
public ContaCorrente {
private float saldo = 0;
public synchronized void depositar(float valor) { saldo = saldo + valor; }
public synchronized void sacar(float valor) { saldo = saldo - valor;}
}
Programação Paralela32
Blocos Síncronos
public ContaCorrente {
private float saldo = 0;
public void depositar(float valor) { saldo = saldo + valor; }
public void sacar(float valor) { saldo = saldo + valor;}
}
public Thread1 extends Thread {
private ContaCorrente conta;
public Thread1(ContaCorrente conta) {
this.conta = conta;
}
public void run() {
synchronized (conta) {
conta.depositar(100);
conta.depositar(200);
}
}
}
public Thread2 extends Thread {
private ContaCorrente conta;
public Thread2(ContaCorrente conta) {
this.conta = conta;
}
public void run() {
synchronized (conta) {
conta.sacar(50);
}
}
}
Programação Paralela33
Exercícios
➢ Exercício 6: Em uma empresa, existem 5 telefonistas que atendem de
50 a 100 clientes por dia. O atendimento de cada cliente dura cerca
de 3 a 5 minutos. Pra cada atendimento, deverá ser gerado um
número único de protocolo, iniciando em 1 e incrementado de 1 em 1.
Use threads, números aleatórios e métodos synchronizedpara simular
esse cenário. Imprima, para cada atendente, o seu nome, o número
do cliente e o número do protocolo.
➢ Dicas:
 Use o gerador de números aleatórios para definir quantidade de clientes
de cada atendente.
 Também use o gerador de números aleatório para gerar o tempo de
atendimento de cada cliente (100 milissegundos = 1 minuto)
 Use um método synchronized para gerar o número único de protocolo
para todas as atendentes.
Programação Paralela34
Exercícios
➢ Exercício 7: Calcule e imprima todos os números primos entre 1 e N,
onde N e um valor fornecido pelo usuário. Permita também que o
usuário defina o número de threads a serem executadas. Adote a
mesma estratégia do exercício 5. Por exemplo, para calcular os primos
entre 1 e 10000 com 4 threads, calcule:
✓ Primos de 1 a 2500
✓ Primos de 2501 a 5000
✓ Primos de 5001 a 7500
✓ Primos de 7501 a 10000
Guarde os resultados em uma lista e, ao final, exiba a lista ordenada.
Programação Paralela35
Comunicação entre Threads
➢ O mecanismo de sincronização é suficiente para evitar que as threads
interfiram umas com as outras, mas pode ocorrer a necessidade de as
threads se comunicarem.
➢ Os métodos a seguir têm o propósito de permitir a comunicação entre
as threads:
 public void wait(): faz com que a thread fique em estado de espera
até que determinada condição seja satisfeita.
 public void notify(): informa a uma thread em estado de espera
(escolhida arbitrariamente) que algo mudou e pode ser que a
condição de espera seja satisfeita.
 public void notifyAll(): informa a todas as threads em estado de
espera que algo mudou e pode ser que a condição de espera seja
satisfeita.
Programação Paralela36
Comunicação entre Threads
➢ Para uso do wait(), notify() e notifyAll(), alguns detalhes são
importantes:
 O teste da condição do wait() deve estar sempre em loop. Nunca
podemos assumir que a notificação implica que a condição
esperada foi satisfeita. Assim, devemos sempre usar um comando
de loop (while ou for) e nunca um if.
 O método ou bloco que testa a condição do wait() precisa ser
synchronized, pois não há como garantir que após o teste da
condição, esta não seja novamente alterada por outra thread.
 O wait() suspende a execução da thread e desbloqueia o objeto.
Quando a thread é reiniciada, o objeto é bloqueado novamente.
 O método ou bloco que chama os métodos notify() e notifyAll()
também precisa ser synchronized.
Programação Paralela37
Comunicação entre Threads
➢ Vamos voltar ao exemplos dos trabalhadores que produzem produtos
de couro. Para criar o produto, o trabalhador precisa de uma peça de
couro devidamente preparada. Imagine que haja somente 1 produtor
de peças de couro para N trabalhadores que vão consumir essas
peças. Cada peça que o produtor produz ele coloca em uma esteira.
Nesse caso, os trabalhadores tem que esperar que exista uma peça
disponível nessa esteira para trabalharem. Toda vez que o produtor
colocar uma peça na esteira ele irá notificar os trabalhadores.
Programação Paralela38
Exercícios
➢ Exercício 8: alterar o exercício anterior para incluir o produtor de
peças de couro. Para implementar esse cenário:
 A quantidade de peças de couro a serem produzidas é a quantidade total
de produtos a serem produzidos pelos N trabalhadores.
 Assim como os trabalhadores, o produtor de peças de couro também terá
um tempo de descanso entre a produção de cada peça.
 Deverá haver uma classe Esteira, que usará uma fila para simular uma
esteira de peças de couro. Nessa classe deverá haver métodos para retirar
e colocar uma peça de couro da esteira.
 Cada peça de couro produzida terá um código numérico.
 Cada trabalhador deverá informar o número da peça de couro usada para
produzir seu produto.
Programação Paralela39
Classe Random
➢ Para geração de números aleatórios usamos a classe Random e os
seguintes métodos:
 public Random(): construtor que cria o gerador de números aleatórios.
 public int nextInt(): retorna um número aleatório inteiro. Pode ser
qualquer número no intervalo de inteiros do Java.
 public long nextLong(): retorna um número aleatório longo. Pode ser
qualquer número no intervalo de longos do Java.
 public int nextInt(int n): retorna um número aleatório inteiro no intervalo
de 0 a n-1.
 public float nextFloat(): retorna um número aleatório float no intervalo de
0 (incluído) a 1 (excluído).
 public double nextDouble(): retorna um número aleatório double no
intervalo de 0 (incluído) a 1 (excluído).
Programação Paralela40
Classe Random
➢ Exemplo:
public static void main(String[] args) {
Random gerador = new Random(); // cria o gerador aleatório
int a = gerador.nextInt(); // int
long b = gerador.nextLong(); // long
int c = gerador.nextInt(11); // int de 0 a 10
int d = gerador.nextInt(51) + 50; // int de 50 a 100
float e = gerador.nextFloat(); // float de [0, 1[
double f = gerador.nextDouble(); // double de [0, 1[
float g = gerador.nextFloat() * 10; // float de [0, 10[
}