View
3.101
Download
3
Category
Preview:
DESCRIPTION
Uma das coisas que mais me chamou atenção na epoca que fiz esta matéria foi exatamente este captulo. Nele vemos diversas meios que são super validos hoje para trabalhar a programação concorrente, resolvi postar este conteudo por que eu acho que se trata um importante assunto que muitos dos meus amigos no qual eu questiono e eles não tiveram a oportunidade de ver isto.
Citation preview
1
Concorrência
Débora Pereira Coura
Linguagem de Programação
2
Introdução
O mundo real funciona concorrentemente: várias atividades podem ser executadas em paralelo. Exemplo: uma pessoa pode estar
respirando, e, falando, e escrevendo, e lendo, etc.
Computadores também operam concorrentemente. Exemplo: um computador pode estar
compilando um programa, e recebendo uma mensagem, e, imprimindo um arquivo, e, tocando música, etc.
3
Objetivos
Reduzir o tempo total de processamento múltiplos processadores
Aumentar confiabilidade e disponibilidade processadores distribuídos
4
Atividades
Cada atividade possui uma seqüência própria de operações
Programas independentes podem se encarregar de Compilador: compilar um programa Navegador: receber uma mensagem e exibir animação Subsistema de e/s: imprimir um arquivo Subsistema de áudio: tocar música
Multiprogramação: vários programas executam sob controle do sistema operacional
5
Programação concorrente
Uma unidade concorrente é um componente de um programa que não exige a execução seqüencial, ou seja, que sua execução seja realizada antes ou após a execução de outros componentes do programa
O termo programação concorrente é usado no sentido abrangente, para designar a programação paralela e a programação distribuída
Concorrência relaciona-se com fluxo de controle: em um programa, existe mais de um fluxo de controle ativo.
6
Fluxo de execução
Execução seqüencial Comandos de controle de
fluxo de execução Seqüencial Condicional Iterativo
Requisição de execução de unidades explícita:chamada de
métodos implícita: ativação de
exceções Programa controla a ordem
de execução
Execução concorrente Cada tarefa é uma unidade de
execução autônoma (um thread) Tarefas podem ser totalmente
independentes Exemplo: execução de um
mesmo método sobre dois objetos (da mesma classe)
Tarefas podem necessitar comunicação
Programa não controla a ordem de execução
7
Motivos para se estudar
Método para conceber soluções de programa para problemas. Muitos domínios são naturalmente concorrentes.
O grande uso de computadores de múltiplos processadores.
8
Nível de instrução: executa 2 ou mais instruções de máquina.
Nível de comando: executa 2 ou mais comandos.
Nível de unidade: executa 2 ou mais unidades de sub-programas.
Nível de programa: executa 2 ou mais programas.
Concorrência
9
A execução concorrente de unidades de programa pode ocorrer fisicamente em processadores separados ou logicamente usando alguma forma de tempo fatiado em um sistema de computador de um único processador.
Concorrência
10
Para o programador e para o projetista da linguagem as duas concorrências são a mesma coisa.
O implementador da linguagem é que deve fazer a correspondência da lógica com o hardware subjacente.
Categorias
11
Execução concorrente, também conhecida como execução paralela, não significa execução simultânea
A execução de unidades concorrentes admite as seguintes possibilidades:
Pseudo-paralela: Execução em um único processador; Paralela: Execução em vários processadores que compartilham
uma memória; Distribuída: Execução em vários processadores independentes, sem
compartilhamento de memória. O programa geralmente não possui controle sobre a ordem e
o tempo de execução das unidades concorrentes
Execução concorrente
12
Os mecanismos para programação concorrente compreendem as construções que as linguagens usam para: indicar quais unidades são concorrentes ativar e controlar um fluxo de execução concorrente possibilitar a interação entre unidades concorrentes
Unidades concorrentes em programas (níveis) Unidades que possuem várias tarefas ou processos
concorrentes Procedimentos/funções, objetos Comandos
Mecanismos de programação concorrente
13
Concorrência de procedimentos/funções podem ser tarefas de uma mesma unidade podem ser ativadas de forma implícita/explícita Em ADA, a palavra Task identifica unidade concorrente,
como por exemplo: Procedure M; Task t1; Task t2; ----- end M;
A ativação das tarefas concorrentes é implícita: quando o procedimento M é chamado, as unidades t1 e t2 iniciam automaticamente sua execução concorrente
Precaução contra tarefas/processos órfãos
Unidades concorrentes
MT1 T2
14
A LP pode adotar um dos seguintes esquemas para explicitar processos:
Uma construção que indica que aquela unidade é um processo. Exemplo, Process MP< ….>
Uma construção que instancia uma unidade concorrente. Por exemplo: New Process ...(<args>).
Ambos os esquemas acima Modelo de objetos: herança de comportamento concorrente
Exemplo em Java: class Thread {... void run()...} class Concorre extends Thread{ ... }Concorre oc=new Concorre(); Thread oc = new Thread();
Unidades concorrentes: processos
15
public class M extends Thread{public static int n=10;public void t1(){System.out.println("Entrada T1: " + n);for (int i=1; i>=50000;i++); //consome tempon=n+1;}public void t2(){System.out.println("Entrada T2: " + n);for (int i=1; i>=50000;i++); //consome tempon=n+2;}public void run(){t1();t2();}
}
Exemplo em Java
inicia execução
16
A LP deve oferecer recursos para: controlar a execução das unidades concorrentes estabelecer prioridades e restrições temporais permitir a comunicação entre unidades
Processos podem ser: centralizados (ambiente local) ou distribuídos (ambiente global) Questões: comunicação entre os processos
Unidades concorrentes: mecanismos
17
procedure M; O ciclo de atualização da global N é decomposto: n: integer; task t1; t1: |___ fetch N ___|___n:=n+1___|___store n__| n:= n+1; task t2; t2: |___ fetch N ___|___n:=n+2___|___store n__| n:= n+2; begin n:= 10; resultado: cobegin n= 13, se Fetch N for feito após a sua atualização; t1;t2; n= 12 ou 11, se Fetch N for feito por t1 e t2, com coend; acesso simultâneo, antes de um Store N. write(n); end.
Exemplo de concorrência de instruções
18
Tarefa: unidade de um programa que pode estar em execução concorrente com outras unidades do mesmo programa. Pode oferecer um thread. Pode ser iniciada implicitamente A tarefa não precisa terminar para a unidade continuar
executando. O controle pode ou não retornar à unidade que iniciou essa
execução. Pode se comunicar pelas variáveis não-locais
compartilhadas, pela passagem de mensagens ou pelos parâmetros.
Concorrência no Nível de Subprograma
19
Tarefa disjunta: não se comunica ou não afeta a execução de qualquer outra tarefa.
Sincronização: mecanismo que controla a ordem de execução das tarefas. Cooperação: quando uma tarefa A precisa
aguardar que a B termine alguma atividade para que ela possa continuar a sua execução. Ex. produtor-consumidor.
Competição: quando duas tarefas precisam usar algum recurso e o seu uso não pode ser simultâneo. Ex. semáforos, monitores
Concorrência no Nível de Subprograma
20
Scheduler : gerencia o compartilhamento dos processadores entre as tarefas.
Deadlock : Situação na qual duas ou mais unidades concorrentes não conseguem prosseguir a execução por que cada uma está aguardando que alguma das outras faça alguma coisa
Livelock : Situação na qual uma unidade concorrente não consegue terminar a execução ou entrar em uma seção crítica por excesso de trabalho ou falta de velocidade. Difere de deadlock por estar ativa e não bloqueada ou
aguardando algo
Concorrência no Nível de Subprograma
21
Tarefas são unidades ( grupos de comandos, objetos, processos) de execução concorrente com as seguintes características: Uma tarefa pode ser implicitamente iniciada Quando uma unidade de programa inicia a execução de
uma tarefa, poderá ou não prosseguir a sua execução Quando a execução de uma tarefa é completada o controle
pode não retornar o ponto de invocação Tarefas podem exigir comunicação para fins de:
cooperação: T1 necessita um serviço de T2 para prosseguir execução (aguarda serviço)
competição: T1 precisa um recurso que T2 está usando (aguarda recurso)
Tarefas x subprogramas
22
A comunicação entre tarefas pode ser feita através de: Variáveis não locais compartilhadas Parâmetros Passagem de mensagem
Recursos compartilhados devem ser protegidos contra acessos simultâneos
Comunicação entre tarefas
Tarefa1
Tarefa2
Tarefa3
recurso compartilhadorecurso compartilhado
23
Duas unidades concorrentes fazem operações sobre variáveis a e b, através de métodos de uma mesma classe
Problema: inconsistência de dados
Solução: garantir atomicidade de execução das operações
Variáveis compartilhadas
thread 1ab()
thread 2ba()
ab(){a = a-b; } ba(){b = b-a; }
a = 100 ; b = 200
24
class DoisMetodos {static int a = 100, b = 200;static void ab() { exibeDados(); a = a-b; exibeDados(); }static void ba() { exibeDados(); b =b-a; exibeDados(); }static void exibeDados(){ System.out.println(" a =" + a +"\t" +" b =" + b +"\t" +
Thread.currentThread().getName());} }
Sem sincronismo: exemplo
ChamaAB oab= new ChamaAB();ChamaBA oba = new ChamaBA();oab.start();oba.start();
25
/* um resultado a =100 b =200 Thread-1 a =100 b =200 Thread-2 a = -100 b =200 Thread-1 a = -100 b =300 Thread-2 *//* outro resultado: a =100 b =200 Thread-1 a = -100 b =200 Thread-1 a = -100 b =200 Thread-2 a = -100 b =300 Thread-2*/ /* mais um resultado a =100 b =200 Thread-2 a =100 b =100 Thread-2 a =100 b =100 Thread-1 a =0 b =100 Thread-1 */
Inconsistência de dados
threadsintercaladas
OK! thread2 após thread1
OK! thread1 após thread2
26
Como é feito o sincronismo de cooperação? Exemplo: mecanismo de espera, no qual uma tarefa
aguarda que outra atinja um determinado ponto de execução para estabelecer comunicação.
Como é feito o sincronismo de competição? Exemplo: bloqueio de código de acesso a recursos
compartilhados (exclusão mútua) Como e quando as tarefas iniciam a terminam sua
execução? Exemplo: tarefas são explicitamente iniciadas e podem
terminar normalmente ou por interrupção explícita
LP concorrentes: projeto
27
Semáforos (Dijkstra) Exigem memória compartilhada Podem ser usados para cooperação e competição
Monitores (Brinch-Hansen) Exigem memória compartilhada Baseados em tipos abstrados de dados
Passagem de mensagens Podem ser usados para programação distribuída
Mecanismos de sincronização
28
Exemplo: produtor x consumidor
Produtor- produz item- coloca item no buffer,se não estiver cheio
Consumidor:- busca item no buffer, se não estiver vazio- consome item
BUFFER de ITENS
aguarda se cheio aguarda se vazio
29
Um semáforo é uma estrutura de dados que consiste de um contador e uma fila de tarefas
Possuem apenas duas operações: Aguarda / Bloqueia ( primitiva P) Continua / Libera (primitiva V)
Semáforos podem ser usados para implementar guardas no código de acesso a dados compartilhados
Semáforos
30
Aguarda / Bloqueia: P(semáforo S)se S.contador > 0 ( fila do semáforo S não vazia)então decrementa S.contadorsenão coloca a tarefa na S.fila, tenta transferir o controle para
alguma tarefa apta; se não existir tarefa apta, ocorre deadlock
Continua / Libera: V (semáforo S)se fila do semáforo S estiver vaziaentão incrementa S.contadorsenão coloca a tarefa como apta e transfere o controle para
uma tarefa da S.fila
Semáforos: primitivas
31
Semáforos: produtor x consumidor
Process Produtor; Process Consumidor;Var i: integer; Var i: integer;begin begin loop loop produz(i); P(ocupados); P(vazios); P(exclusão); P(exclusão); retira(i); coloca(i); V(exclusão); V(exclusão); V(vazios); V(ocupados); consome(i); end loop; end loop;end; end;
código crítico
exclusão
vazios
ocupados
32
Semáforos: deadlock
Process Produtor; Process Consumidor;Var i: integer; Var i: integer;begin begin loop loop produz(i); P(exclusão); P(vazios); P(ocupados); P(exclusão); retira(i); coloca(i); V(exclusão); V(exclusão); V(vazios); V(ocupados); consome(i); end loop; end loop;end; end;
exemplo: inverter ordem
33
A idéia: encapsular os dados compartilhados e suas operações para restringir o acesso
Um monitor é um TAD para dados compartilhados Fornece sincronização de competição sem semáforos Transfere a responsabilidade da sincronização ao sistema em
tempo de execução.
Monitores
BUFFER de ITENS
operaçãocoloca
operaçãoretira
produtor consumidor
34
type buffer= monitor var conteudo : array[...] of integer; origem, destino: fila; {...} procedure entry coloca (item:integer); begin if buffercheio then delay(origem); { coloca item no buffer } continue(destino); end; procedure entry retira(var item:integer); begin if buffervazio then delay(destino); { retira elemento do buffer} continue(origem); end; begin {corpo do monitor}end;
Monitores: buffer
35
Monitores: buffer
Delay(fila): colocar o processo que a chama na fila especificada e retirar seus direitos de acesso exclusivo a estruturas de dados do monitor. Execução suspensa.
Continue(fila): desconectar o processo que a chama do monitor, liberando-o de ser acessado por outros processos. Examina a fila especificada, se contiver processo, ele será removido e sua execução reiniciada.
36
Monitores: produtor x consumidor
{type}Produtor= process (area: buffer); var dado: integer; begin cycle produz(dado); area.coloca(dado);end; end;
{type}
Consumidor=
process (area=buffer);
var dado: integer;
begin cycle area.retira(dado); consome(dado); end;
end;
37
Os tipos de dados declarados Buffer(monitor), Produtor (process) e Consumidor(process) devem ser : instanciados inicializados através de um comando init
init provoca a execução cíclica do Produtor e do Consumidor , que usam o monitor Buffer
O monitor Buffer garante a exclusão mútua das operações coloca e retira
Monitores: produtor x consumidor
38
Definição básica: “ Fluxo de controle seqüencial isolado dentro de um programa.”
Programas multithreaded: Múltiplos threads concorrentes de execução num único programa, realizando várias tarefas “ao mesmo” tempo.
Exemplo: programa do usuário + coleta de lixo
Diferentes threads podem executar em diferentes processadores, se disponíveis, ou compartilhar um processador único
Diferentes threads no mesmo programa compartilham um ambiente global (memória, processador, registradores, etc.)
Threads: o que são?
39
Programação Reativa : aplicação responde a eventos de entrada. Exemplo: interfaces com o usuário, onde cada evento
corresponde a uma ação
Programação Interativa: uma tarefa para fazer alguma interação com o usuário, outra para exibir mensagens, outra para fazer animação, etc..
Paralelismo físico/ distribuição: para tirar vantagem de múltiplas CPUs centralizadas ou distribuídas
Algumas aplicações multithreaded
40
Criação de threads em Java
Criar uma subclasse da classe Thread
public class MyClass extends Thread { ... }
Implementar a interface Runnable;
public class MyClass extends Applet implements Runnable { ... }
class Thread
class MyClassclass Applet
interface Runnable
class MyClass
41
Segurança: como sincronizar threads para que elas não interfiram com uma outra
Longevidade: como evitar situações de deadlock ou livelock para garantir que todos os threads farão progresso
Desempenho: a mudança de contexto dos diversos threads provoca queda de desempenho (overhead)
Questões importantes em Multithreading
42
Instanciação de objetos concorrentes
Métodos
Estruturas de dados
classe
Dados do Objeto2
Dados doObjeto1
Execução concorrente do mesmo código
RA2RA1
43
Execução de threads
Cada thread possui um método run() que define a atividade concorrente Exemplo: public void run( ) {
for (int count=0; count<1000; count++)
System.out.println(nome); }
A atividade concorrente inicia quando é invocado o método start() sobre um objeto. Exemplo: public static void main(String[] arg) {....
um.start( );
dois.start( ); ......}
O que?
Quando?
44
Classe Thread
Usada quando a classe a ser executada concorrentemente não deriva de outra classe
Contém métodos para controlar a execução Criação e execução:
Declarar uma nova classe que seja subclasse da classe Thread
Sobrescrever o método run() com o código que será executado pela thread
Instanciar a nova classe Invocar seu método start(); o método rodará em seu
próprio thread de controle
45
Contexto da classe Thread
java.lang.Object
java.lang.Thread
public class Threadextends Objectimplements Runnable
Alguns métodos da classe Thread start(): inicia a execução do Thread; sleep(): suspende a execução por um determinado tempo
(especificado em milisegundos) e automaticamente recomeça a execução;
destroy():destrói esta thread. Demais métodos: jdk1.2.1/docs/api/java/lang/Thread.html
46
Exemplo de extensão Thread
class Piloto extends Thread{ private String nome; public Piloto(String str){ nome = str; } public void run(){ System.out.println("****LARGADA ****"); System.out.println(”Primeira volta: " + nome);
for(int cont=0; cont<10000; cont++){};System.out.println(nome + " -> Terminou a Corrida !!!");
}}
47
Exemplo de execução
public class CorridaT{public static void main(String[] args){
Piloto um = new Piloto("Rubinho"); Piloto dois = new Piloto("Schumacher"); Piloto tres = new Piloto(”Raikonnen"); um.start(); dois.start(); tres.start(); }}
CorridaT
um dois tres
Quem terminará antes?
48
Resultado de uma execução
*** LARGADA ****** LARGADA ****** LARGADA *** Primeira volta:Rubinho Primeira volta:Schumacher Primeira volta: RaikonnenRubinho -> Terminou a Corrida !!!Raikonnen -> Terminou a Corrida !!!Schumacher -> Terminou a Corrida !!!
CorridaT
um dois tres
49
Resultado de outra execução*** LARGADA *** Primeira volta:RubinhoRubinho -> Terminou a Corrida !!!*** LARGADA *** Primeira volta:Schumacher*** LARGADA ***Schumacher -> Terminou a Corrida !!! Primeira volta: RaikonnenRaikonnen -> Terminou a Corrida !!!
CorridaT
um dois tres
50
Interface Runnable
Usada quando não se pode herdar da classe Thread, pois há necessidade de herança de alguma outra classe possui apenas o método run()
Cria-se um objeto da classe base Thread, porém o código a ser executado está descrito na classe do usuário(derivada + ancestrais).
Criação e execução: Declarar uma nova classe que implementa a
interface Runnable Sobrescrever o método run() Criar um objeto da classe Thread. Exemplo: Thread um = new Thread(this);
51
Exemplo de implementação Runnnable (1)
class PilotoR implements Runnable{ private String nome; public PilotoR(String str){ nome = str; } public void run(){ System.out.println("*** LARGADA ***"); System.out.println(" Primeira volta:" + nome); for(int cont=0; cont<10000; cont++) {}; System.out.println(nome + " -> Terminou a Corrida !!!"); }}
52
Exemplo de implementação Runnnable (2)
public class CorridaR{
public static void main(String[] args){
PilotoR um = new PilotoR("Rubinho");
PilotoR dois = new PilotoR("Schumacher");
PilotoR tres = new PilotoR(" Raikonnen ");
new Thread(um).start();
new Thread(dois).start();
new Thread(tres).start();
}
}
53
Estados de Threads
newblocked
running
dead
start
Sleep
done sleeping
wait
sleep Waiting I/O
I/O done
destroy
No decorrer da execução, threads podem alterar seu estado:
- ativo
- inativo
- encerrado
54
Exemplo de sleep
class PrintThread extends Thread {private int sleepTime;public PrintThread (String name) { // construtorsuper(nome); // nome do thread: construtor de TreadsleepTime=(int)(Math.random() * 5000); // 0-5 secSystem.out.println(“Name: “+ getName() + “; sleep “ + sleepTime);public void run ( ){try{System.out.println(getName() + “going to sleep”);Thread.sleep (sleepTime) ;}catch ( InterruptedException exception) {System.out.println(exception.toString()); }
55
Exceção: sleep
try {
System.out.println(getName() + “going to sleep”);
Thread.sleep (sleepTime) ;
}
catch ( InterruptedException exception)
{
System.out.println(exception.toString());
}
método sleep pode disparar exceção*
nome da exceção
* se outro thread chama o método interrupt durante sleep
56
Prioridades
Cada thread possui uma prioridade (entre 1 e 10)
Default: prioridade = 5 Prioridade transmitida por
herança Threads de igual prioridade
cedem processador por: chamada de yield time-slicing
Thread de mais alta prioridade apta a executar: faz com que o thread de
menor prioridade ceda o processador
seja executada até que termine a sua execução, ou,
tenha a sua execução suspensa (sleep/wait...)
57
Resumo de estados de threads
A execução do thread depende do ambiente de execução (sistema operacional)
New threads: thread criado com new mas ainda não está rodando
Runnable threads: Depois de chamado o método start(), o thread está apto a ser executada (depende da disponibilidade do sistema)
Blocked threads: um thread entra no estado bloqueado quando ocorre chamada aos métodos sleep(), suspend() ou wait() espera por I/O
Dead threads: execução encerrada ( o objeto thread é destruído)
Recommended