38
+ Programação Concorrente Benito Fernandes Fernando Castor João Paulo Oliveira Weslley Torres XV Jornada de Cursos CITi Aula 1

Programação Concorrente - Aula 1

Embed Size (px)

DESCRIPTION

Ensino de programação concorrente, ideal para quem começa a estudar computação e ou programação.

Citation preview

  • +

    Programao Concorrente

    Benito FernandesFernando CastorJoo Paulo OliveiraWeslley Torres

    XV Jornada de Cursos CITi

    Aula 1

  • +Suposies bsicas

    Conhecimento bsico sobre Programao Orientada a Objetos

    Experincia de pelo menos um semestre com Java, C# ou C++

    Conhecimento sobre os componentes fundamentais deum computador (processador, memria RAM, cache, etc.)

  • http://en.wikipedia.org/wiki/File:Gigabyte_NVIDIA_GeForce_9500_GT.JPGhttp://upload.wikimedia.org/wikipedia/en/a/af/E6750bs8.jpghttp://media.bestofmicro.com/I/S/8452/3/8452.jpghttp://www.cs.uaf.edu/2009/fall/cs441/proj1/bob/Pics/cell.jpghttp://en.wikipedia.org/wiki/File:Athlon64x2-6400plus.jpg

    Fontes:

    AMD Athlon X2 6400+

    NVIDIA GeForce 9500 GT

    Intel Core 2 Duo

    IBM Cell

    Sun Ultrasparc 2

  • +

    O que todos esses processadores tm em

    comum?

    Todos eles so multicore(ou multi-ncleo)

  • +Processadores multi-ncleo

    Incluem vrios nclos em uma nica pastilha

    Nmero de instrues simultneas = nmero de ncleos

    Cache compatilhada ou no

    Memria compartilhada ou passagem de mensagens

    Fonte: http://en.wikipedia.org/wiki/File:Dual_Core_Generic.svg

  • +Descobrindo o nmero de ncleos

    Instrues de emergncia

    Salvar em um arquivo chamado C.java e, em seguida:

  • +Por que multi-ncleo?

    Antigamente, apenas aumentar o nmero de

    transistores era suficiente

    Juntamente com o aumentos de cache

    E aumento da frequncia de clock

    Hoje em dia, no mais o caso

    Nmero de transistores continua crescendo

    Mas a frequncia de clock est estagnada

    Consumo de energia e aquecimento so os fatores

    limitantes

  • +

    Fonte: http://www.gotw.ca/publications/concurrency-ddj.htm

  • +Por que multi-ncleo (cont.)?

    Novas abordagens tornaram-se necessrias

    Soluo encontrada: paralelismo

    Diversos ncleos em uma mesma pastilha

    Memria nica

    Reaproveitamento de outros componentes

    Localidade propicia melhor desempenho

    Alternativa: diversos processadores Supercomputadores usam essa abordagem

    Mais cara

  • +Paralelismo funciona!

    Compile e execute o programa abaixo.

  • +Agora este:

  • +Paralelismo: O Bom, o Mau e o Feio

    Processadores multi-ncleo podem propiciar grandes aumentos de desempenho

    Melhor caso: aplicaes N vezes mais rpidas, onde N o nmero de ncleos

    Entretanto, o aumento costuma ser menor que isso

    Lei de Amdahl

    Aumento de desempenho limitado pela poro no-paralelizvel da aplicao

  • +

    Fonte: http://en.wikipedia.org/wiki/Amdahl%27s_law

  • +

    Qual a percentagem de cada aplicao que vocs desenvolvem que

    paralelizvel?

  • +

    Faltou o Feio:

    Responder a pergunta do slide anterior no o suficiente

    necessrio saber tornar paralela a aplicao

    Criar aplicaes paralelas difcil

    Exige tcnicas especficas

    Pois tem problemas especficos

    Alguns tipos de aplicao se prestam melhor paralelizao do que outros

    Paralelismo: O Bom, o Mau e o Feio (cont.)

  • +O objetivo deste curso :

    Apresentar algumas das tcnicas usadas para se construir aplicaes paralelas

    Usando a linguagem java, j que esta muito popular*

    E seu modelo de programao paralela tambm

    Vrias das ideias so aplicveis a programas em C# e C++

    * http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html

  • +

    Pera... mas este no um curso de Programao CONCORRENTE?

  • +Sistemas concorrentes

    Caso a quantidade de requisies seja muito alta a aplicao no quebra

    Execuo particionada em unidades de computao

    Independentes ou inter-dependentes

    Executadas simultaneamente ou sequencialmente

    Iluso de simultaneidade

    Exemplos:

    Sistemas operacionais, servidores (web, de aplicao, de DNS, etc.), simuladores

    Fonte: http://www.cs.cuw.edu/museum/images/vectra386.jpg

  • +Sistemas paralelos

    Sistemas concorrentes desenvolvidos para ser executados em hardware paralelo Supercomputadores

    Mquinas multi-ncleo

    Aglomerados (clusters)

    Tcnicas para construir sistemas concorrentes frequentemente aplicam-se aos paralelos Exceto quando a alocao de processos

    de software aos elementos de hardware importante

    Fonte: http://parasatria.files.wordpress.com/2008/09/supercomputeribm.jpg

  • +Sistemas paralelos

    Sistemas concorrentes desenvolvidos para ser executados em hardware paralelo Supercomputadores

    Mquinas multi-ncleo

    Aglomerados (clusters)

    Tcnicas para construir sistemas concorrentes frequentemente aplicam-se aos paralelos Exceto quando a alocao de processos

    de software aos elementos de hardware importante

    Fonte: http://parasatria.files.wordpress.com/2008/09/supercomputeribm.jpg

    Aspecto no coberto neste curso. Importante em dois contextos:

    - Supercomputao (problemas especficos)- Mquinas multi-ncleo (tema de pesquisas recentes!)

  • +Sistemas distribudos

    Sistemas paralelos executados em uma rede de processadores autnomos que no compartilham memria

    Normalmente dispersos geograficamente

    Redes no to rpidas

    E no to confiveis

    Tcnicas mais especficas so necessrias

    Fonte: http://www.worldofwarcraft.com/wrath/

  • +

    The biggest sea change in software development since the OO revolution is knocking at the door, and its name is Concurrency.

    Herb Sutter

  • +Em que os sistemas concorrentes so diferentes?

    No-determinismo

    Interao entre processos (ou processadores ou threads ou atores ou tarefas ...)

    Comunicao

    Sincronizao

    Controle de acesso a recursos compartilhados

    E os sistemas paralelos?

    Alocao de elementos de processamento a unidades de hardware

    Infraestrutura de execuo frequentemente cuida disso

  • +No-determinismo

    Programas sequenciais produzem as mesmas sadas quando executados com as mesmas entradas

    Dado que no realizam escolhas aleatrias

    Esta caracterstica os torna determinsticos

    Um programa no-determinstico pode produzir sadas diferentes para uma mesma entrada

    Em execues subsequentes

  • +

    Programas paralelos e concorrentes so intrinsecamente no-determinsticos

    So necessrias tcnicas para torn-los determinsticos

    Dependendo de quais aes so relevantes

    Fontes possveis:

    Escalonamento

    Interao com o usurio

    Acesso a recursos

    No-determinismo (cont.)

  • +

    Compile e execute o programa abaixo.

    Um programa determinstico...

  • +... e um no-determinstico...

  • +Programas no-determinsticos podem passar a iluso de determinismo

  • +

    s=s+i s=s+i s=s+i

    s=s+i s=s+i s=s+i

    Processo 1

    Processo 2

    Sada padro

    System.out.println(i)

    Entrelaamento (interleaving) de execues

  • +Alguns problemas comuns em programas concorrentes

    Erros de consistncia de memria

    Deadlock (impasse)

    Starvation

    Depurao e teste

    (entre outros...)

  • +

    i = i + 1

    Memria

    int i = 1

    i = i - 1

    Processo 2

    Escrita(i == 0)

    Escrita(i == 2)

    Leitura(i == 1)

    Leitura(i == 1)

    Processo 1

    Erros de consistncia de memria

  • +Evitando erros de consistncia de memria

    necessrio sincronizar o acesso varivel i

    Acessos a i devem funcionar como se fossem sequenciais regio crticaSGBDs funcionam assim

    Duas possveis abordagens:Permitir apenas leituras concorrentes

    Escritas serializadas

    S permitir que uma tarefa tenha acesso a i de cada vez excluso mtua

    E se uma tarefa precisar usar diversas variveis?

  • +Deadlocks (impasses)

    Situao onde um sistema no pode progredir

    Dependncia circular entre processos que precisam reservar certos recursos

  • +

    Memria

    Processo 2

    Reserva avarivel i

    Processo 1

    Reserva avarivel j

    Tentar reservara varivel j

    Tentar reservara varivel i

    Nenhum dos dois

    progridePode ocorrer em diversas situaes em sistemas reais!!!

    Deadlocks (cont.)

  • +Starvation

    Decorre de polticas injustas de escalonamento

    Consequncia: alguns processos nunca tm acesso aos recursos desejados

    Fonte: http://www.roadfood.com/photos/3310.JPG

  • +Testes e depurao

    Automao de testes torna-se muito difcilConsequncia do no-determinismo

    Tanto para testes funcionais quanto para testes de caminhos

    O que significa execuo passo-a-passo quando vrios passos so simultneos?Como garantir que certa sequncia executada?

  • +

    No restante do curso, alguns desses problemas sero

    examinados com mais calma...

    e algumas solues sero apresentadas.