PR - DAINF/Departamento Acadêmico de Informá · PDF fileCompile: javac jthread/Main.java Execute: java -cp . jthread/Main ... As linhas em destaque mostram que o semáforo SEM1 e

PROGRAMAÇÃO PARALELA E DISTRIBUÍDAFundamentos

Prof. Cesar Augusto Taclahttp://www.dainf.ct.utfpr.edu.br/~tacla

JAVAProgParSD/0030-ProgParalelaDistribuida.ppt

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁPR

22Programação Paralela e Distribuída - Fundamentos/UTFPR Prof. Cesar Augusto Tacla

Sumário

1. Introduçãoa. Definição de sistemas paralelos e distribuídosb. Conceitos: programa, processo e threadc. Criação de threadsd. Yield, Sleep, Joine. Prioridade entre threadsf. Compartilhamento de memóriag. Máquina de estados de uma thread

2. Problemas de concorrênciaa. Race conditionb. Vivacidade (deadlock, livelock, starvation)c. Soluções (mutex, semáforos, monitor)


REFERÊNCIAS BIBLIOGRÁFICAS

(Coulouris et al., 2003) George Coulouris, Jean Dollimore, Tim Kindberg. Distributed Systems - Concepts and Design, Addison Wesley Publ. Comp., 3a edição, 2003.

(Tanenbaum & Steen, 2002) Andrew S. Tanenbaum, Maarten van Steen. Distributed Systems, Prentice-Hall International, 2002.

(Garg, 2004) Vijay K. Garg. Concurrent and Distributed Computing in Java, Wiley Inter-Science, 2004, 309p.

(LEA, 200) Douglas Lea. Concurrent programming in Java: design principles and patterns, 2nd ed. Reading: Addison-Wesley, c2000. 411 p. (Java series).


Sumário

Definição de sistemas paralelos e distribuídos

1 a


Sistema Paralelo

MemóriaCompartilhada

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

Múltiplos processadores conectados por uma memória compartilhada

barramento


Sistema Distribuído

Rede de Comunicação

Múltiplos processadores conectados por uma rede de comunicação

Troca de mensagens

Segundo (Garg, 2004), são sistemas compostos por múltiplos processadores conectados por uma rede de comunicação, sendo a rede de comunicação uma LAN (Ethernet) ou WAN (Internet). Neste tipo de sistema os processadores se comunicam por troca de mensagens (não por memória compartilhada)


Necessidades

◊ Sistemas paralelos e distribuídos� Necessitam de ferramentas e técnicas� Distintas das utilizadas em software sequencial


Distribuído x Paralelo (1)

◊ Em relação ao hardware,� Se pensarmos em desempenho, é melhor termos sistemas

distribuídos ou paralelos?� R: combinação

� Computadores multiprocessados conectados por uma rede



CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL


CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL



◊ Por que não sistemas completamente paralelos?� Escalabilidade� Modularidade e heterogeneidade� Compartilhamento de dados� Compartilhamento de recursos� Estrutura distribuída por si� Confiabilidade� Baixo custo



◊ Por que não sistemas completamente distribuídos?� Melhor desempenho no processamento local� É mais rápido atualizar uma memória local do que enviar uma

mensagem para outro processador, especialmente quando o valor de uma variável deve ser comunicado para vários processadores



◊ Em relação ao software (API programação),� Pode ser independente do hardware?

◊ Na realidade, reflete a estrutura de hardware� Modelo de objetos distribuídos (ex. RMI) tem-se

� Processos que se comunicam por mensagens

� Processos que podem ter várias threads

� Threads que se comunicam por memória compartilhada



CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL


CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL

CPU

MEMLOCAL


Sumário

Conceitos: programa, processo e thread

1 b


Programa, processo, thread

◊ Programa conjunto de instruções numa linguagem de alto nível ou de máquina

◊ Processo resulta da execução do programa, tem um ambiente de execução autocontido e privado.

� O que o usuário enxerga como aplicação ou sistema, normalmente é composto por vários processos

� Sequencial = 1 processo

� Concorrente = vários processos

programaexecução

Processo 1

Processo 2

Processo n



◊ Thread são chamadas de processos peso-pena

◊ Tanto threads como processos provêm um ambiente de execução ou contexto de execução

◊ Toda aplicação possui pelo menos uma thread �� main

◊ Threads compartilham o mesmo "espaço de endereçamento“ (memória)

◊ É mais rápido chavear a execução entre threads do queentre processos.

◊ Threads compartilham recursos do processo: memória e arquivos abertos.

1515

Programa, processo e thread

◊ Uma thread recebe recursos próprios durante a execução:� uma pilha (stack) de execução para poder chamar métodos, passar parâmetros, alocar variáveis locais

� um "Program Counter" � Estes elementos formam o contexto de execução da thread

Programação Paralela e Distribuída - Fundamentos/UTFPR Prof. Cesar Augusto Tacla



PCR

Method area

heap

StackThread 1

Processos que compartilham código e dados são chamados de threads, são também chamados de processos lightweight

StackThread 2

StackThread 3

Compartilhadopelas threads

Stack: armazena o estado de cada invocação de método: variáveis locais, argumentos, retorno e dispatch de exceções. São vários frames empilhados � stack overflow

Heap: armazena instâncias de objetos criadas em tempo de execução. Também armazena arrays � OutOfMemoryError

Method area: informações da classe (nome, modificadores), superclasse, atributos e seus modificadores, atributos estáticos com valores, métodos e seus modificadores, bytecodes

PCR PCR

Program Counter Register

Contexto de execução de uma thread


Exemplos de threads

◊Threads – demos� Links na página do curso� http://www.doc.ic.ac.uk/~jnm/concurrency/classes/ThreadDemo/ThreadDemo.html� http://www.dsc.ufcg.edu.br/~jacques/cursos/map/html/threads/threads1.html

� observar como uma applet é incorporada a uma página WEB<applet codebase="Sort/" code="SortItem.class" width="300" height="300">


Sumário

Criação de Processos/Threads

1 c


UNIX, C++

◊ Criação de processos

pid = fork();if (pid == 0) {

cout << “processo filho”;else

cout << “processo pai”;







Processo pai

Processo filho

programa


Criação de threads em Java

◊ Há 2 métodos� Extends Thread Implements Runnable

MinhaThread

+run():void

Thread

MinhaThread

+run():void

Runnable

<<realizes>>

Possibilita estender outra classe



◊ Exemplo de criação de Thread por extends

public class Main {

public static void main(String[] args) {

MinhaThread t = new MinhaThread();

t.start();

}

}

public class MinhaThread extends Thread {

public void run() {

System.out.println(“Ola!!!!”);

}

}

:Main

:MinhaThreadnew

start()

run()

Diagrama de sequência em UML



◊ Exemplo de criação de Thread por implements

public class Main {


MinhaThread t = new MinhaThread();

Thread t2 = new Thread(t);

t2.start();

}

}

public class MinhaThread implements Runnable {

public void run() {

System.out.println(“Ola!!!!”);

}

}

:Main

:MinhaThreadnew

start()

run()



◊ Exemplo básico: threads contadoras

Código fonte e .jar disponível emhttp://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JThreadContadoras

JAVARepositorio\JThreads\JThreadContadoras

Duas threads são criadas, cada uma conta até 1.000. Os resultados podem aparecer intercalados.

Para compilar e executar Ir ao subdiretório src/jthreadSalvar o arquivo em Main.java <dir>/jthread/Lance o shell: executar � cmd Posicione no diretório <dir>Compile: javac jthread/Main.javaExecute: java -cp . jthread/Main

Para executar somenteIr ao subdiretório distSalve o arquivo .jar em <dir>Lance o shell: executar � cmd Posicione no diretório <dir>Execute: java -jar JThreadContadoras.jar


Criação de Threads em Java

class MinhaThread implements Runnable {

public void run() {

// a interface Runnable exige a implementação do método run

String name = Thread.currentThread().getName();

System.out.println(name + " rodando");

for (int i=0;i < 1000; i++) {

System.out.println(name + ": " + i);

}

System.out.println(name + " FIM ***");

}

}

public class Main {


System.out.println("INICIO DA THREAD MAIN ***");

Thread t1 = new Thread(new MinhaThread(), "thread 1");

Thread t2 = new Thread(new MinhaThread(), "\t\tthread 2");

t1.start();

t2.start();

}

}

◊Exemplo básico: threads contadoras


Criação de Threads em Java

◊Exemplo básico: threads contadoras

Quem faz o chaveamento de contexto?



◊ Exercício 1: modifique o programa das threads contadoras de forma a criá-las estendendo a classe Thread

◊ Exercício 2: criar várias threads (> 4) e observar o chaveamento de contexto.


....


Sumário

Yield, Sleep e Join

1 d


Java THREADS: YIELD

◊ YIELD� suspende a execução da thread atual

e permite que outra ocupe o processador.

:Main

t1:MinhaThreadnew

start()

Início do run()

t2:MinhaThreadnew

start()

yield()

yield()

swapInício do run()

swap

As flechas pontilhadas indicam swap. O label das flechas indicam omotivo do swap: Swap: escalonador do SO; yield(): a chamada ao método causou a mudança.


Java THREADS: YIELD

◊ Exemplo de utilização de yield


public void run() {

// a interface Runnable exige a implementação do método run

String name = Thread.currentThread().getName();

System.out.println(name + " rodando");

for (int i=0;i < 1000; i++) {

System.out.println(name + ": " + i);

// eh possivel passar o controle para outra thread implicitamente

Thread.yield();

}

System.out.println(name + " FIM ***");

}

}

public class Main {





t1.start();

t2.start();

}

}


Java THREADS: YIELD

◊ Exercício: no exemplo das threads contadoras, habilite o yield fazendo: java –jar JThreadContadoras.jar YIELD

3131

Java Threads: SLEEP

◊ Sleep: suspende a execução da thread por um período� Libera o processador para outras threads

� Faz a thread dormir por milisegundos ou nanosegundos

� Tempo de sleep não é preciso, depende do SO

if (i%3==0) {

try {

thread.sleep(2000); // dorme 2 seg

catch (InterruptedException e) {}

}

No exemplo das threads contadoras, cada thread

dorme 2s a cada 3 contagens. Execute-o fazendo:

java –jar JThreadContadoras.jar NO 2000

3232

Java THREADS: SLEEP

◊ SLEEP� suspende a execução da thread atual por pelo menos x

milisegundos e permite que outra ocupe o processador.

:Main

t1:MinhaThreadnew

start()

Início do run()

t2:MinhaThreadnew

start()

Início do run()

sleep(2000)

Timedwaiting

swap

swap

swap

3333

Java Threads: SLEEP

◊ Exercício [JAVA]: faça a simulação de um cruzamento controlado por dois semáforos utilizando apenas sleep para controlar os tempos de verde, amarelo e vermelho. Observe que o sleep fará sinaleiros não sincronizados. Para simplesmente executá-lo, ver próximo slide.

Sol. JAVARepositorio\JThreads\JCruzamento-v1

3434

Java Threads: SLEEP

◊ Para executar o cruzamento fazer:

◊ Baixar o .jar dehttp://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JCruzamento-v1/dist/

>java -jar JCruzamento.jar

Estado SEM1:VERMELHO

Estado SEM2:VERDE

Estado SEM1:VERDE

Estado SEM2:AMARELO

Estado SEM2:VERMELHO

Estado SEM1:AMARELO

Estado SEM2:VERDE

...

As linhas em destaque mostram que o semáforo SEM1e o SEM2 ficaram verde ao mesmo tempo!!!

3535

Java Threads: JOIN

◊ Thread.join(): permite que uma thread espere pelo término de duas ou mais threads

:Main

t1:MinhaThreadnew

start()

Início do run()

t2:MinhaThreadnew

start()

Início do run()

fim t1waiting

fim t2

swap

swap

join (t1, t2)

Fim join (t1, t2)

A thread main fica a espera de t1 e t2

3636

Java Threads: JOIN

public static void main (String[] args) {




t1.start();

t2.start();

try {

t1.join(); // a thread main aguarda o término de t1

t2.join(); // a thread main aguarda o término de t2

} catch (InterruptedException e) {

System.out.println(“interrupcao");

}

System.out.println("*** As duas threads encerraram a

contagem ***");

// outras coisas da thread main

}

3737

Java Threads: JOIN

◊ JOIN: “une” as execuções das threads

No exemplo das threads contadoras, para testar o JOIN, faça:java –jar JThreadContadoras.jar NO 2000 JOIN

3838

Sumário

Prioridade entre threads

1 e

3939


◊ Qual thread é escolhida para rodar?

◊ Depende...� da implementação da JVM (Java Virtual Machine);

� da prioridade da thread

� da política/algoritmo de escalonamento do sistema operacional (ex. round-robin = rodízio por fatia de tempo = quantum)

4040


◊ Exemplo: escalonamento no Linux[fonte http://www.inf.pucrs.br/~celso/SchedulerLinuxWindows.pdf]

� Cada processo possui uma prioridade, recalculada dinamicamente.� O escalonador dá a CPU ao processo de maior prioridade� O escalonador é preemptivo� Para processos interativos (I/O bound) -> round-robin� Para processos tempo-real -> FCFS (first come, first served)

4141

Prioridade entre Threads

◊ Windows (2000/NT/XP) – ESCALONAMENTO[fonte http://www.inf.pucrs.br/~celso/SchedulerLinuxWindows.pdf]

� No Windows 2000/XP o escalonador utiliza múltiplas filas e as threads interativos (I/O bound) possuem prioridade sobre os CPU bound.

� O escalonamento é baseado em prioridades. Cada thread possui uma prioridade, que varia de 0 a 31 (0 é a menor e 31 a maior).

� A prioridade 0 é atribuída a uma thread especial, chamada zero thread, que é responsável por zerar as páginas livres no sistema. Somente esta thread pode receber a prioridade 0.

� As prioridades definem três classes de threads:� Real time: prioridades de 16 a 31;� Normal: prioridades de 0 a 15.� Existe ainda uma classe especial chamada idle, a de mais baixa

prioridade. Threads nesta classe somente executam quando não existem outras threads aptas (portanto, threads dessa classe não interferem na performance – não causam overhead).

4242

Prioridade entre Threads

◊ Windows (2000/NT/XP) – ESCALONAMENTO� O escalonador escolhe sempre a thread de maior prioridade.� As threads da classe real time executam até terminar ou se bloquear

(FCFS).� As threads com prioridade normal (0 a 15) recebem fatias de tempo (RR).

� no Windows 2000 professional, a fatia de tempo é de 20 ms (para favorecer a interatividade).

� no Windows 2000 Server, a fatia é de 120 ms (para gerar menos trocas de contexto).

� Cada thread recebe uma prioridade base ao ser criada. Para os processos de tempo real (prioridade entre 16 e 31) esta prioridade não se altera. Além disso, uma thread tem uma prioridade inicial que indica sua prioridade relativa dentro do processo.

� Threads com prioridade entre 0 e 15 têm a prioridade ajustada em tempo de execução:� Preemptadas por operações de I/0 recebem um bônus de aumento,

que depende do periférico (ex. 1 para disco e 6 para teclado).� Preemptadas por esgotar o quantum: prioridade reduzida.

4343


◊ Mapeamento de threads

� Há de se considerar o mapeamento das threads da JVM para threads nativas do

sistema operacional. Por exemplo, a JavaHotSpot VM na Solaris mapeia uma thread

Java em uma thread nativa.

� Maiores detalhes em http://java.sun.com/j2se/1.5.0/docs/guide/vm/thread-priorities.html

◊ As prioridades das Threads setadas no código Java são lógicas e dependem

da implementação da JVM:

� public final void setPriority(int newPriority)

� public final int getPriority()

� MAX_PRIORITY = 10 constante inteira

� MIN_PRIORITY = 1 constante inteira

� NORM_PRIORITY = 5 prioridade atribuída por default

4444


◊ Exercício: modificar a prioridade das threads contadoras e observar efeito na execução. Os dois últimos parâmetros modificam respectivamente as prioridades da thread 1 e 2. Recorda-se que a prioridade deve estar no intervalo [1, 10]

Código fonte e jar disponíveis emhttp://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JThreadContadoras/

No exemplo das threads contadoras, para testar o a prioridade, faça:java –jar JThreadContadoras.jar OFF 0 OFF 1 10

Prioridade thread 1

Prioridade thread 2

4545


◊ Exercício: considere um simulador de corridas de fórmula 1 que simula uma disputa entre dois pilotos: Schumacker e Barrichelo.� Cada carro funciona de forma independente

� O tempo de cada volta é dado por um valor randômico. O programa deve esperar por este tempo sem fazer nada para então iniciar a próxima volta

� Ao final da corrida (quando os dois carros completam 5 voltas), o simulador mostra o tempo acumulado para cada um dos pilotos e aponta o vencedor ou empate.

◊ Responda� Que comandos da linguagem Java você utilizaria para resolver cada um dos itens acima?

JAVARepositorio\JThreads\JCarrosCorrida

4646


◊ O código abaixo é uma solução do problema anterior. [JAVA] Altere o programa atribuindo maior prioridade a uma das threads (Schumacker ou Barrichelo). [TELEINFO] Execute o .jar for fun!

* No exemplo seguinte, simulamos dois carros de corrida: Schumacker e Barrichelo.* Cada carro funciona de forma independente na sua thread e demora x milisegundos* para percorrer um determinado trecho da pista (x é um valor aleatório).* Para simular este tempo, utilizamos o método Sleep. Na thread Main aguardamos que* os dois carros terminem a prova para encerrar a corrida. Isto é feito através do join.** * Rodar a partir da linha de comando* ===================================* 1. Salve este arquivo em <dir>/jcarroscorrida/* 2. Lance o shell: executar -> cmd* 3. posicione no diretório <dir>* 4. compile: javac jcarroscorrida/Main.java* 5. execute: java -cp . jcarroscorrida/Main*/

Código fonte e .jar disponíveis emhttp://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JCarrosCorrida/

JAVARepositorio\JThreads\JCarrosCorrida

4747

Sumário

Compartilhamento de memória

1 f

4848

Compartilhamento de memória

◊ Compartilhamento de memória é um subtópico de comunicação inter-processos (IPC)� fila de mensagens (SO)� pipeline (SO) � proc1 >> proc2 >> proc 3� área de memória compartilhada (SO) � POSIX, threads� envio de mensagens (rede) � CORBA, JRMI, RPC, MPI

◊ Threads se comunicam por compartilhamento de memória� Atributos (membro de classe e de instância)� Objetos compartilhados

4949

Exemplo de compartilhamento de memória

class AreaMem {

static String compartilhada= Thread.currentThread().getName();;

}

class Escritora extends Thread {

public void run() {

AreaMem.compartilhada = Thread.currentThread().getName();

}

}

public class Main {


Escritora E0 = new Escritora();

Escritora E1 = new Escritora();

E0.start();

E1.start();

System.out.println("Compartilhada = " + AreaMem.compartilhada);

}

}

O atributo estático AreaMem.compartilhada é compartilhado entre as threads E0, E1 e main

http://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JCompartMemStaticSimples/

5050

Exercício

◊ Execute várias vezes o código do slide anterior

◊ Anote os valores impressos

◊ Qual a explicação?

5151

Cenários de execução do exemplo

main:Thread

E0:Threadnew

start()

c=“main”

print c

Xrun()

c=“Thread-0”

X

E1:Thread

start()

run()

c=“Thread-1”

X

Um dos cenários possíveis de execução; o valor impresso é “main”

5252

Exemplo por atributo estático

public class Main extends Thread {

static int c = 0; // compartilhado

private int ini, fim; // nao compartilhados

public Main(int ini, int fim) {

this.ini = ini;

this.fim = fim;

}

public void run() {

System.out.println(Thread.currentThread().getName() + " !!! wait ");

while (c >= ini && c <= fim) {

System.out.println(Thread.currentThread().getName() + " antes " + c);

c = (int)(Math.random()*10);

System.out.println(Thread.currentThread().getName() + " depois " + c);

}

System.out.println(Thread.currentThread().getName() + " !!! fim ");

}


new Main(0, 4).start();

new Main(5, 10).start();

}

}

JAVARepositorio\JThreads\JCompartMemStatic

5353

Cenário de execução do exemplo

main:Main

Thread-0:Main<<create>>

start()

X

Thread-1:Main

run()0 ≤≤≤≤ c ≤≤≤≤ 4c:=20 ≤≤≤≤ c ≤≤≤≤ 4c:=5

start()

Xswap

5 ≤≤≤≤ c ≤≤≤≤ 10c:=65 ≤≤≤≤ c ≤≤≤≤ 10c:=2

X

swap

O atributo estático cé compartilhado pelasthreadas

5454

Exercício

main:Main

Thread-0:Main<<create>>

start()

X

run()5 ≤≤≤≤ c ≤≤≤≤ 10

Thread-1:Main

run()0 ≤≤≤≤ c ≤≤≤≤ 4c:=2

start()

swap

swap

0 ≤≤≤≤ c ≤≤≤≤ 4c:=5

Xswap

5 ≤≤≤≤ c ≤≤≤≤ 10c:=65 ≤≤≤≤ c ≤≤≤≤ 10c:=2

X

swap

Explique porque a seguinte sequência de mensagens não é possível

5555

Exercício

◊ Para a classe abaixoclass Schedule

static int x = 0;static int y = 0;public static int op1() {

x = 1;return y;

}public static int op2() {

y = 2;return 3*x;

}

Se uma thread chama op1 e outra, op2, que resultados podem ser retornados pelos métodos op1 e op2?

(Vijay K. Garg, 2004, p. 15)

Objetivo: entender o compartilhamento de memória por atributos estáticos

5656

Exemplo por objeto compartilhado

class Conta {

int saldo = 0;

}

class Deposito extends Thread {

private Conta c;

public Deposito(Conta c) {

this.c = c;

}

public void run() {

int vlrs[] = {40, 50, 60, 10, 20, 30};

for (int i=0; i <vlrs.length; i++)

c.saldo += vlrs[i];

}

}

class Retirada extends Thread {

private Conta c;

public Retirada(Conta c) {

this.c = c;

}

public void run() {

int vlrs[] = {10, 20, 30, 40, 50, 60};

for (int i=0; i <vlrs.length; i++)

c.saldo -= vlrs[i];

}

}

public class Main {


Conta c = new Conta();

Thread d = new Deposito(c);

Thread r = new Retirada(c);

d.start();

r.start();

try {

d.join();

r.join();

} catch (InterruptedException e) { }

System.out.println("Saldo=" + c.saldo);

}

}

Objeto compartilhado

http://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JCompartMemObjetoCC/

5757

Exercício

◊ Faça uma classe Java que faça busca paralela num array de inteiros. A classe deve implementar o método:

public static int busca(int x, int[] A, int nThreads)

� O método cria nThreads� Estas threads devem compartilhar o objeto A.� Cada thread busca pelo inteiro x em uma parte de A, por exemplo,

da posição 0 até a 10, outra da 11 a 20, ...

� Se uma das threads encontra x, então retorna-se o índice i, tal que A[i] = x

� Caso contrário, o método retorna -1� Quando uma das threads encontra o número x, as outras devem

parar a busca!

sol. JAVARepositorio\JThreads\JBuscaParalela

5858

Sumário

Máquina de estados de uma thread

1 g

5959

Estados de uma thread

NEW BLOCKED

WAITING

TIMED WAITING

TERMINATED

new()

start()

Synchronized(obj)

Obteu lock

Object.wait()

Thread.join()

Object.notify()

Object.notifyAll()

Object.wait(timeout)

Thread.join(timeout)

Thread.sleep(delay)Object.notify()

Object.notifyAll()

join thread termina

fim do sleep

Fim do método run()

http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.State.html

RUNNING

Escolhida pelo

scheduler Thread.yield()

swap do scheduler

As transições observadas até o momento estão em destaque

RUNNABLE

join threads terminam

6060

Estado de uma thread: detalhe do runnable

Em runnable, a thread pode ser escolhida pelo schedulerpara entrar em execução. Uma vez em execução, pode liberar o processador por yield ou por swap do scheduler.

RUNNABLE

RUNNING

Escolhida pelo scheduler Thread.yield()

swap do scheduler

6161

Sumário

PROBLEMAS DE CONCORRÊNCIA

2

6262

Sumário

Problemas de Concorrência

2 a

6363

Problemas de concorrência

◊ Processos compartilham dados

◊ Sincronizar acesso aos dados é necessário

◊ Exemplo� x é uma variável compartilhada (inicialmente zero)� Thread T0 faz x := x + 1� Thread T1 faz x := x + 1� x deve ser 2 ao final

◊ Porém, se x := x + 1 não for uma operação atômica...

6464

RACE CONDITION: atualização perdida

◊ x = x + 1 em código de máquina (inicial x=0)� LD R, x load registrador R com x� INC R incrementar R� ST R, x store R em x

◊ A execução de T0 e T1 é intercalada

P0: LD R, x

P0: INC R

P1: LD R, x

P1: INC R

P0: ST R, x

P1: ST R, x

Resultado final: x = 1 �� problema da atualização perdida

R = 0

R =1

R = 0

R =1

x =1

x =1

Registrador R

0

0Variável x

11

0101

6565

Problemas de concorrência

◊ x := x + 1 deve ser executada atomicamente

◊ Região/Seção crítica �� necessida atomicidade

◊ Para garantir atomicidade, exclusão mútua

processos querem o recurso,mas só um pode utilizá-lo, casocontrário o recurso pode ficar num estado inconsistente

Processo 2Processo 1

Recursocompartilhado

Quem ganha a disputa?

6666


CC = Conta correnteSaldo: R$ 100,00

Transação T2:crédito de 10% de juros

Transação T1:crédito de R$5,00

Situação desejada:1) Aplica-se o juros2) credita-se R$ 5,00

Funcionamento das transações

1) s:=CC.getSaldo()2) Crédito na variável s3) CC.setSaldo(s)

Saldo da conta deve ser:(R$100,00 * 1,1) + 5,00 = R$ 115,00

Problemas:Leitura sujaAtualização perdida

6767


Quando uma transação sobrescreve valores produzidos por outra

TRANSAÇÃO T1

Creditar R$ 5,00

S:= CC.getSaldo() // R$100

S:= S + 5 // S = 105

CC.setSaldo(S) // R$105

TRANSAÇÃO T2

Juros de 10%

S = CC.getSaldo( ); // R$100

S = S * 1,10; // R$ 110,00CC.setSaldo(S); // R$ 110,00

Sobrescreve o valor produzido por T2Saldo final = R$ 105,00

6868

RACE CONDITION: leitura suja

Quando uma transação lê valores intermediários de outro transação - atributos que estão sendo modificados em outra transação

TRANSAÇÃO T1

A.retirar(100)

B.depositar(100)

TRANSAÇÃO T2

total = A.saldo( ); // R$100total = total + B.saldo( ); // R$300Mostrar total = R$ 400,00

Transfere R$100,00 daConta A para a conta B

Relatório com o saldo total dasagências

Saldo A = R$ 200,00Saldo B = R$ 300,00TOTAL = R$ 500,00

Saldo A = R$ 100,00Saldo B = R$ 400,00TOTAL = R$ 500,00

Após transferência

6969

CONCORRÊNCIA

◊ Exemplo de leitura suja/atualização perdida: executar o código abaixo e observar que o número apontado pelo contador central difere da soma dos contadores locais devido aos problemas de leitura suja e atualização perdida.

Códigos fonte e .jar disponíveis emhttp://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JRaceConditionRoletas/

Roleta e contador local

Contador central

Atualizado pelas duas roletas de forma concorrente

40.000.000

160.000.000

120.000.000

7070

Sumário

Vivacidade: deadlock, livelock e starvation

2 b

7171

Vivacidade

◊ VIVACIDADE: um pedido de uma thread para entrar/acessar uma seção crítica será atendido mais cedo ou mais tarde

� DEADLOCK: uma thread t1 bloqueia a espera de uma seção crítica ocupada por t2 que, por sua vez, está bloqueada a espera da seção crítica ocupada por t1 �� grafo wait-for cíclico

� STARVATION: quando uma thread solicita entrada numa seção crítica e nunca é atendida (ex. porque as outras tem maior prioridade)

� LIVELOCK: duas threads não conseguem avançar porque uma muda seu estado em resposta à mudança de estado da outra (ex. duas pessoas no corredor que sempre escolhem o mesmo lado para desviarem).

7272

Exemplo de deadlock

◊ DEADLOCK: filósofos podem bloquear-se.

Applet demo disponível emhttp://www.doc.ic.ac.uk/~jnm/concurrency/classes/Diners/Diners.html /

?

?

7373

Exemplo de starvation

◊ STARVATION: um dos filósofos nunca come porque o outro tem maior prioridade.

Prioridade porser o mais sábio

7474

Exemplo de livelock

◊ LIVELOCK: filósofos podem bloquear-se porque mudam de estado continuament em função do outro.

7575

Problema dos filósofos

Pauzinho 1

Pauzinho 2

Filósofo 1termina de

comer

Filósofo 2termina

de comer

P1 c/ F1

P2 c/ F1

P1 c/ F21

P2 c/ F2

F1decidecomer

F2decidecomer

F1 e F2pensam

F2pega

2 pauzinhos

F1pega

2 pauzinhos

1. Só um dos filósofos decide comer2. Os dois decidem comer ao mesmo tempo, cada um pega um pauzinho

7676


◊ Solução para o problema dos filósofos: coordenar as ações

� Um dos filósofos devem solicitar os recursos na ordem inversa dos outros

� Ex. todos pegam o objeto da esquerda e depois o da direita.� Facilmente visível com dois filósofos

7777


◊ SOLUÇÃO: coordenar as ações. Inverter a ordem.

WAIT

7878

Solução para filósofos

Pauzinho 1

Pauzinho 2

Filósofo 1termina de

comer

Filósofo 2termina

de comer

P1 c/ F1

P1 e P2C/ F1

P1 c/ F21

P1 E P2c/ F2

F1decidecomer

F2decidecomer

F1 e F2pensam

Primeiro o p1 depois o p2 Se os dois decidem comer ao mesmo tempo, somente um deles conseguirá pegar o pauzinho 1

7979


◊ Exercício� Verificar se a solução apresentada funciona para 4 filósofos sendo o f2

aquele que pega na ordem invertida. Represente em um diagrama de seqüência a situação na qual todos tentam pegar os pauzinhos ao mesmo tempo.

f1

f3

f2f4

p1

p2p3

p4

8080

Sumário

Soluções aos problemas de concorrência

2 c

8181

SOLUÇÕES PARA CONCORRÊNCIA

Como resolver os problemas de acesso à seção crítica?

◊ Exclusão mútua por hardware� Desabilitar interrupções� instruções de máquina atômicas de mais alto-nível

◊ Primitivas de sincronização� Semáforos� Monitores

monitor

8282

MUTEX por HARDWARE

◊ Que soluções existem em hardware para o problema de exclusão mútua (MUTEX)?

� Desabilitar interrupções: antes de entrar na SC, o processo desabilita as interruções� Em máquinas monoprocessador pode funcionar com alguns

incovenientes...� interrupções do clock (time-slice) ficam desabilitadas� mas, em máquinas multiprocessadores? É possível desabilitar

interrupções em todos os processadores?

� Instruções atômicas mais abstratas fornecidas pelo hardware� Test and set� Swap

8383

SEMÁFOROS

◊ SEMÁFORO (Dijkstra): é uma primitiva de sincronização de acesso à seção crítica que soluciona o problema de busy-wait.

◊ API do sistema operacional (SO) � Disponível na API do S.O.� Java não oferece semáforos

◊ Dois tipos de semáforos� Binário

� contador

8484

SEMÁFORO BINÁRIO

◊ Semáforo binário: � Valor inicial: verdadeiro

� Fila de processos em wait: vazia

◊ Operações básicas� P() wait� V() signal (notify)

8585

Semáforo binário

T1:thread T2:threadS:SemaforoBinario

true

P( )

falseP( )

waitV( )

true

notify( )

Na seçãocrítica

Na seçãocrítica

V( )

false

true

8686

SEMÁFOROS

◊ Semáforo contador: � Valor inicial: valor inteiro = número de processos permitidos na SC

◊ Operações básicas� P() wait decrementa um contador� V() signal (notify) incrementa contador

Ver código

8787

Semáforo contador

T1:thread T2:threadS:SemaforoContador

2

P( )

1P( )

wait

V( )

V( )

Na seçãocrítica

0

T3:thread

1

P( )

notify( )

0

1

Há dois recursos, neste caso osemáforo é inicializado com 2

8888

PRODUTOR-CONSUMIDOR

◊ Problema do Produtor-Consumidor� Solução utilizando semáforos

PRODUTOR CONSUMIDOR

K=5

BUFFER COMPARTILHADO

8989

PRODUTOR-CONSUMIDOR

◊ PRODUTOR-CONSUMIDOR Solução utilizando semáforos

0

1

2

34

5

...

TAM -1

saída

entrada

9090

PRODUTOR-CONSUMIDOR

◊ Problemas � Exclusão mútua no acesso ao buffer

(ou o produtor ou o consumidor)

� Consumidor não deve buscar itens quando o buffer está vazio� Produtor não pode produzir se buffer estiver cheio

� SINCRONIZAÇÃO CONDICIONAL: Um processo aguarda que uma condição se torne verdadeira antes de continuar suas operações.

� Exemplos:

� Consumidor aguarda a existência de um item� Produtor aguarda espaço no buffer para produzir

9191

PRODUTOR-CONSUMIDOR

◊ Exercício (solução utilizando semáforos)� Baixe o código fonte� Faça o diagrama de sequência para o cenário seguinte:

� O produtor produz um item (double)� O consumidor consome.� O consumidor tenta consumir um item que não existe.

Código fonte e .jar disponível emJAVARepositorio/JThreads/JProdutorConsumidorSemaforos

9292

SEMÁFOROS

◊ Outros problemas bem-conhecidos� Leitor-escritor em banco de dados

� Não acessam o BD concorrentemente� Leitor e escritor� Dois escritores

� Múltiplos leitores acessam concorrentemente

� Filósofos

9393

MONITOR LOCK

◊ MONITOR: mais alto nível e mais fácil de utilizar que semáforo

◊ Java só trabalha com monitores

◊ Todo objeto em Java é um monitor

9494

MONITOR LOCK

◊ Quando uma thread executa um bloco de código sincronizado, ela fecha o acesso às demais. Outra thread que tentar acessar a seção crítica (o bloco de código) não conseguirá até que a primeira libere o acesso.

◊ Em java, o bloqueio é feito no objeto e não no método.

◊ Isto é útil quando duas ou mais threads devem atualizar a mesma área de mémória (atributo compartilhado).

9595

EXEMPLO MONITOR LOCK

T1:thread T2:threadobj:Compartilhado

Lock livre

método sincronizado( )

Lock ocupado

método sincronizado( )

waitingfim método

notify( )

Na seçãocrítica

Na seçãocrítica

fim método

Lock livre

9696

Exemplo em JAVA

◊ Problema das roletas e contador central

/**

* Contador é um objeto compartilhado pelas threads roleta 1 e roleta 2.

*/

class ContadorCentral {

protected int numPessoas=0;

/**

* O código que faz a atualização da variável numPessoas é uma seção crítica.

* Somente um processo (ou thread) pode executá-lo por vez. Para impedir que

* mais de uma thread atualize numPessoas, utiliza-se a palavra-chave

* synchronized.

**/

protected synchronized void somarNumPessoas(int n) throws InterruptedException

{

numPessoas += n;

}

}

JAVARepositorio\JThreads\JRaceConditionRoletasSol

Ao executar somarNumPessoas de uma certa instância de ContadorCentral o lock fica retido. Qualquer outro método (se houvesse) da instância não poderia ser executado enquanto o somarNumPessoas não terminasse (lock liberado).

9797

Exemplo em JAVA: outra forma

◊ Problema das roletas e contador central (equivale ao anterior, só muda a sintaxe)

/**

* Contador é um objeto compartilhado pelas threads roleta 1 e roleta 2.

*/

class ContadorCentral {

protected int numPessoas=0;

/**

* O código que faz a atualização da variável numPessoas é uma seção crítica.

* Somente um processo (ou thread) pode executá-lo por vez. Para impedir que

* mais de uma thread atualize numPessoas, utiliza-se a palavra-chave

* synchronized.

**/

protected void somarNumPessoas(int n) throws InterruptedException {

synchronized (this) {

numPessoas += n;

}

}

}

JAVARepositorio\JThreads\JRaceConditionRoletasSol

9898

SINTAXE PARA SYNCHRONIZED

public synchronized void metodo() {

….

….

….

}

public void metodo() {

synchronized (this) {

….

….

….

}

}Métodos estáticos podem ser sincronizados – equivale

a um lock de classe

São construções equivalentes

9999

MONITOR LOCK: SEMÂNTICA

◊ Semântica

enterMonitor():

se obtém o lock entra no monitor

se não aguarda;

exitMonitor():

libera o lock e notifica processosbloqueados

synchronized (object) {

….

….

….

}

como

uma

seção

crítica

A thread deve obter o lock deste objeto para entrar na SC

Lock é para objeto(não para o bloco decódigo ou método)

100100

EXERCÍCIO

◊ Baixar o programa JRaceConditionRoletas do repositório e corrigir o problema de condição de corrida na atualização do contador central utilizando bloco de código synchronized.

◊ Idem para o programa que atualiza saldo da conta corrente

Código fonte disponível emJAVARepositorio/JThreads/JRaceConditionRoletas/

Solução em RepositorioJAVA/JThreads/JRaceConditionRoletasSol

FIM

Código fonte disponível emJAVARepositorio/JThreads/JCompartMemObjetoCC/

101101

MONITOR LOCK: WAIT/NOTIFY

◊ Há situações onde, duas threads devem executar de forma concorrente dois blocos de código sincronizados do mesmo objeto.

◊ Mas foi dito que uma vez que uma thread pega o lock de um objeto ela só o libera ao final do método!!!

◊ Foi uma meia verdade... ;-)

102102


Pedestal

põe tiraTHREAD 1 THREAD 2

WAIT pedestal vazioPõe peçaNotifica que colocou

WAIT pedestal ≠ vazioTira peçaNotifica que tirou

Objeto compartilhado

103103


class RoboProdutor implements Runnable {

Pedestal p;

RoboProdutor(Pedestal p) {

this.p = p;

}

public void run() {

while (true) {

synchronized (p) {

while (!p.livre) {

p.wait();

}

println("Peça colocada");

p.livre=false;

p.notifyAll();

}

}

}

}

JAVARepositorio\JThreads\JExemploWaitNotifyPedestal

Catch e try foram omitidosWait libera o lock; Notify não libera o lock

class RoboConsumidor implements Runnable {

Pedestal p;

RoboConsumidor(Pedestal p) {

this.p = p;

}

public void run() {

while (true) {

synchronized (p) {

while (p.livre) {

p.wait();

}

println("Peça retirada");

p.livre=true;

p.notifyAll();

}

}

}

}

class Pedestal {

boolean livre = true;

}

104104

EXEMPLO MONITOR LOCK

Produtor:Runnable Consumidor:Runnablep:Pedestal

Lock

synchronized(p)

Lock

waiting pelo locknotifyAll( )

“Peça Colocada”

p.livre = false

Livre=false

Início do run()

Início do run()

Obtém o lock de psynchronized(p)

fim bloco sync: libera o lock

Lock

Obtém o lock

Obtém o lock de p

wait p.livre

synchronized(p)

“Peça Retirada”p.livre = true

Livre=true

Lock

Lock

105105

EXERCÍCIO

◊ Baixe o código fonte dos robôs e pedestal

◊ Inclua mais um robô consumidor

◊ Identifique na mensagem impressa qual robô consumidor que faz a retirada da peça

◊ Verifique se o programa funciona corretamente.

http://www.dainf.ct.utfpr.edu.br/~tacla/JAVARepositorio/JThreads/JExemploWaitNotifyPedestal/

106106

synchronized

(object) {

….

object.wait();

….

object.notify();

….

object.notifyAll(

);

….

}

◊ Cada monitor tem uma fila de processos bloqueados

◊ 3 métodos especiais podem ser usados dentro do monitor

Thread Libera o lock do object e passa ao estado waiting

Se a fila não estiver vazia, pega um processo qualquer da fila e o desbloqueia

Se a fila não estiver vazia, desbloqueia todos os processos da fila que vão disputar o lock – mas só um será escolhido pelo escalonador (ineficiente se houver muitas threads)

MONITOR LOCK: WAIT, NOTIFY

107107

NOTIFY x NOTIFY ALL

◊ Utilizar notify no lugar de notify all somente quando as duas condições abaixo forem verdadeiras:

1. Threads em waiting possuem mesma condição de espera (ex. estahVazio). Todas as threads executam a mesma lógica quando saem do wait.

2. One-in, one-out. A notificação sobre a variável utilizada na condição habilita somente uma thread a prosseguir.

Fonte: Goetz, B. Java Concurrency in Practice, ed. Pearson Education, 2006, seção 14.2.4

108108

Exemplo típico

synchronized(obj) {while(<condição>){

try {wait();

}catch (InterruptedException e) { }}// alguma coisanotifyAll();

}

109109

Métodosde bloco de código sincronizado

Usar somente em blocos de código sincronizado (caso contrário, erro de execução IllegalMonitorStateException)

◊ Object.wait( ) libera o lock◊ Object.wait(<t em ms>) libera o lock◊ Object.notify()◊ Object.notifyAll()

◊ Importante: não manipulam lock� Thread.yield() não libera o lock� Thread.sleep(<t em ms>) não libera o lock� Thread.suspend() não utilizar – deprecated� Thread.resume() não utilizar - deprecated

110110

Tipos de monitores

◊ Há duas implementações clássicas de monitores

� Hoare: o processo que faz a notificação é interrompido

� Estilo Java: o processo que faz a notificação não é necessariamente interrompido

111111

Dois tipos de monitores

Processo 0


….

object.wait();

….

}

Processo 1


….

object.notify();

….

}

Somente um processo pode estar no monitor: 2 possibilidades

Qual processo continua a execução nesse ponto?

112112

TIPO 1: MONITOR DE HOARE

Process 0


….

object.wait();

….

}

Process 1


….

object.notify();

….

}

Processo 0 assume a execução assim que o 1 faz notify

113113

Tipo 1: MONITOR DE HOARE

Process 0


if (x != 1)

object.wait();

assert(x==1); // x é igual a 1

x++;

}

Process 1


x=1;

object.notify();

// x pode ser ≠≠≠≠ 0 neste ponto

}

No monitor HOARE, é possível fazercondição sincronizada com if

A condição de sincronização(x=1) é seguramente verda-deira quando o processoé notificado

O processo que notifica é interrompido

114114

TIPO 2: MONITOR ESTILO JAVA

Process 0


….

object.wait();

….

}

Process 1


….

object.notify();

// código

// código

}

No monitor estilo Java, o Processo 1 continuaa executar após o notify

115115

Tipo 2: MONITOR JAVA

Process 0


if (x != 1)

object.wait();

assert(x==1); // falso

x++;

}

Process 1


x=1;

object.notify();

assert(x == 1); // x must be 1

x++;

}

Processo 1 continua a executar e pode modificar o valor de x. A sincronização condicional com um simples if pode não funcionar.

P0 realiza operações assumindo x=1, sendo que x pode ter outro valor

116116

Tipo 2: MONITOR JAVA

Process 0


while (x != 1)

object.wait();

assert(x==1); // verdadeiro

x++;

}

Process 1


x=1;

object.notify();

assert(x == 1); // x must be 1

x++

}

Para solucionar o problema do slide anterior, é preciso colocar um while (também resolve o caso de interrupções espúrias).

Só sai do while quando x=1

P0 realiza operações assumindo x=1, sendo que x será igual a 1

117117

Dois tipos de monitores

◊ O monitor Java é mais usual� Porém, é prudente verificar o tipo de monitor quando for utilizar

outra linguagem

◊ Código de sincronização é extremamente difícil de debugar� Muitos bugs ficam escondidos durante anos sem que ninguém

perceba� Faça certo da primeira vez!

118118

Resumo

◊ Por que necessitamos de primitivas de sincronização?� Busy waiting desperdiça ciclos de CPU� Primitivas de sincronização necessitam suporte do SO

◊ Semáforo:� Binário, contador� Produtor-consumidor

◊ Monitor:� Mais fácil e mais popular que semáforos� Dois tipos: Hoare e estilo Java

119119

EXERCÍCIO

◊ Problema do barbeiro dorminhoco

� Um barbeiro corta o cabelo de qualquer cliente.� Se não há clientes, o barbeiro tira uma soneca.� Há várias threads, uma para cada cliente.� Um cliente aguarda pelo barbeiro se há ao menos uma cadeira

vazia na barbearia,� Caso contrário, o cliente sai da barbearia imediatamente.� Se há uma cadeira disponível, então o cliente senta.� Se o barbeiro está dormindo, então o cliente acorda-o.� Existem <n> cadeiras na barbearia.

� Faça um programa para a classe BarbeiroDorminhocoutilizando monitor

Documents

PR - DAINF/Departamento Acadêmico de Informá · PDF fileCompile: javac jthread/Main.java Execute: java -cp . jthread/Main ... As linhas em destaque mostram que o semáforo SEM1 e