Programação ConcorrenteAula 01

Prof: André Luis Meneses Silva

Conteúdo

• O que é• Motivação• Conceitos• Processos• Threads• Propriedades• Safety• Liveness

Programação Concorrente[ O que é ]

• “Um programa concorrente é um conjunto de programas seqüenciais comuns que são executados em um paralelismo abstrato” (M.Bem-Ari)

Programação Concorrente[ O que é ]

• “Um programa concorrente especifica 2 ou mais processos que cooperam para realizar uma tarefa. Processos cooperam através de comunicação; utilizam variáveis compartilhadas ou troca de mensagens“(G. R. Andrews)

Programação Concorrente[ Motivação ]

• Aproveitar hardware com múltiplos processadores

• Atender a vários usuários simultaneamente• Melhorar o desempenho das aplicações• Aumentar a disponibilidade para o usuário• Objetos ativos e controle de atividades• Programas paralelos

Programação Concorrente[ Conceitos ]

• Paralelismo– Processamento simultâneo físico

• Concorrência– Processamento simultâneo lógico (aparente)– Requer entrelaçamento (interleaving) de ações

• Processo– Execução de um programa

• Programa Concorrente– Vários processos que cooperam para a realização de uma tarefa

Programação Concorrente[ Conceitos ]

• Comunicação– Variáveis compartilhadas– Passagem de mensagens

• Sincronização– Exclusão mútua de seções críticas– Sincronização por condição

• Estado de um programa concorrente– Consiste dos valores das variáveis (explícitas e implícitas)– A execução de um comando muda o estado

• Ações atômicas– Transformação indivisível de estado

Programação Concorrente[ Processos ]

• Um processo é um programa que está em algum estado de execução

• Tem espaço de endereçamento próprio, que é mapeado pelo S.O. para memória física

• Possui um fluxo de controle ou thread único• Mantém um contador de programa (PC) que indica o

endereço da próxima instrução• A MMU (Memory Management Unit) traduz os

endereços lógicos em endereços físicos, que normalmente não são contíguos (Memória Virtual)

Programação Concorrente[ Processos ]

• Espaço de Endereçamento Lógico

Instruções

Dados Globais

Espaço de Endereçamento

Lógico de um Processo

Pilha

Heap

Programação Concorrente[ Processos ]

• Tabela de Processos– Estado do processo– Valores dos registradores– Arquivos abertos– Alocação de memória– PID (Process ID)– UID (User ID)– GID (Owner’s Group ID)

Programação Concorrente[ Processos ]

• Estados de um processo– Executando (Running): Utilizando a CPU– Executável ou Pronto (Runnable ou Ready):

Esperando para ser escalonado para usar a CPU– Suspenso (Suspended): Recebeu um sinal para ser

suspenso– Bloqueado (Blocked): Esperando pela conclusão

de algum serviço solicitado ao S.O.

Programação Concorrente[ Processos ]

Executando

Suspenso

Executável

Bloqueado

EncerradoIniciado

Ativo

Programação Concorrente[ Threads ]

• Um processo pode ter mais de uma Thread (Linha)

• Cada Thread possui contador de programa e pilha próprios

• Quando um processo é escalonado para ser executado, uma das Threads entra em execução

• As Threads compartilham as variáveis globais do processo

Programação Concorrente[ Threads ]

Espaço de Endereçamento de um Processo

Instruções

Variáveis Globais

Pilha

Heap

Pilha

Contadorde Programa

Thread 1

Pilha

Contadorde Programa

Thread 2

Pilha

Contadorde Programa

Thread n

Programação Concorrente[ Threads ]

• Vantagens sobre processos compartilhando memória– São muito mais leves de serem criadas– A troca de contexto é mais suave pois compartilha

instruções, heap e variáveis globais– Facilitam o compartilhamento de memória

Threads[ Ciclo de Vida ]

Criada

Pronta Executando

Esperando

Dormindo

Encerrada

Bloqueada

Operaçãode E/Siniciada

Término

sleep

waitnotifynotityAll

Operaçãode E/Sconcluída

start

Intervalo de tempo expirou

escalonada

interrompida

Threads[ Sincronização ]

• Sincronizando Threads– Programação com múltiplas Threads requer

bastante cuidado:• Acesso / Atualização de variáveis compartilhadas• Starvation• Deadlock• Acesso a estados inválidos de outros objetos

Threads[ Sincronização ]

• Problema de acesso a variáveis compartilhadas– Várias Threads (representando os depósitos dos clientes)

querendo atualizar (depositar um valor) uma mesma conta– Quando uma está lendo o saldo atual, uma outra Thread pode

já ter lido esse valor e calculado o novo saldo, mas ainda não ter gravado o novo valor

– Se nesse momento a primeira Thread gravar o valor, o saldo final será igual ao calculado pela Thread que gravar o novo valor por último (desconsiderando assim o depósito da Thread que encerrou primeiro).

– O ideal é impedir que uma operação de depósito seja iniciada antes da outra encerrar

Threads[ Sincronização ]

• A sincronização baseia-se na idéia de que para acessar um método sincronizado ou um entrar em um bloco sincronizado, é preciso obter (ou já ter) o lock desse objeto.

• A Thread que conseguir esse lock é a única autorizada a acessar os recursos protegidos através de sincronização.

Programação Concorrente[ Propriedades ]

• Safety: O programa nunca entra em um estado inconsistente)

• Liveness: Em algum momento o programa entra em um estado consistente

• Correção Parcial: Se o programa terminar, o resultado está correto. Caso contrário, nunca pode dar o resultado correto

• Término: O programa termina eventualmente• Ausência de Deadlock: Nunca todos os processos

estarão bloqueados• Correção Total: O programa sempre termina e produz o

resultado correto

Safety [ Introdução ]

• Objetos interagindo em múltiplas Threads normalmente provocam interferência

• Programas concorrentes devem possuir 2 propriedades:– Safety: Nada de mau acontecerá durante a

execução do programa.– Liveness: Algo de bom acontecerá durante a

execução do programa.

Safety [ Introdução ]

• Em geral há mais atenção sobre Safety na engenharia– É melhor que o programa não faça nada a ter um

comportamento aleatório ou até perigoso• Liveness está relacionada ao progresso do programa• Em alguns casos é melhor obter uma informação

imprecisa a não receber– Sistemas de Suporte a Decisão, Data Warehouse e Simulação de

Trânsito• Melhorar a Liveness pode implicar em reduzir a Safety

Safety [ Objetos Seguros ]

• Em programa OO, o controle de interferência é implementado de classe a classe

• Objetos/variáveis podem entrar temporariamente em um estado inconsistente

• Um objeto/variável é considerado seguro quando:– Seu estado consistente é sempre consistente– Operações não são realizadas enquanto está em

um estado inconsistente

Safety [ Objetos Seguros ]

• Há 3 estratégias conservadoras para projetar objetos/variáveis seguros:– Imutabilidade: evitar mudanças de estado– Sincronização: garantir acesso exclusivo

dinamicamente– Contenção: garantir acesso exclusivo

estruturalmente

Safety [ Imutabilidade ]

• Variáveis de instância constantes (final em Java)

• Encapsulamento• Não requer sincronização• Classes sem estado (stateless)– Como não há estado, não há interferência

Safety [ Sincronização ]

• Um Objeto/variável sempre está pronto para sofrer modificações, mesmo quando ainda está no meio do processamento de alguma

• Acesso a estados inconsistentes devem ser evitados:– Conflitos de leitura/escrita: vários lêem enquanto

um escreve– Conflitos de escrita/escrita: vários lêem e

escrevem ao mesmo tempo

Safety [ Sincronização ]

• No contexto de OO, podemos ter:– Sincronização Total• Objetos totalmente sincronizados. Podem fazer apenas

uma operações por vez

– Sincronização Parcial• Parte do objeto é sincronizado. Somente métodos

sincronizados são travados

Safety [ Contenção ]

• Baseia-se na idéia de manter referências únicas para objetos internos isolados dos demais.

• São acessados apenas através de métodos sincronizados do objeto no qual estão contidos, estando, portanto, protegidos.

externo1

interno1

interno2

subinterno1

Safety [ Contenção ]

• Recursos Exclusivos– Garante que somente um objeto por vez é

“proprietário” do recurso exclusivo. Porém, a propriedade de um recurso pode mudar

– Semelhanças com objetos físicos:• Se você tem um, então pode usá-lo• Se você tem um, ninguém mais pode tê-lo• Se você da um para alguém, então deixa de tê-lo• Se você destrói um, ninguém nunca mais o terá

Safety [ Contenção ]

– É preciso definir um protocolo que garanta a exclusividade do recurso

serviço 2serviço 0

serviço 3

serviço 1vizinho

vizinho vizinho

vizinho

null

null

null

Recurso

Liveness [ Introdução ]

• Projetos baseados em combinações de Imutabilidade, Sincronização e Contenção são abordagens simples, rápidas e de fácil entendimento para o desenvolvimento de programas concorrentes OO

• Porém, essas técnicas nem sempre são a melhor solução

• Utilização de Sincronização pode provocar problemas de Liveness (eficiência)

Liveness [ Falhas de Liveness ]

• São tão sérias quanto falhas de Safety• São mais difíceis de identificar e evitar

durante o projeto• Tipos de falhas– Contenção: uma thread, apesar de estar pronta

para executar, não executa porque outra tomou recursos (também conhecida como starvation ou adiamento infinito)

Liveness [ Falhas de Liveness ]

– Dormência: uma thread não pronta falha ao tentar passar para esse estado.

– Deadlock: duas ou mais threads bloqueiam-se em um ciclo vicioso enquanto tentam acessar travas sincronizadas necessárias para continuar suas atividades

– Término prematuro: uma thread é parada ou encerrada prematuramente

Liveness[ Análise de Variáveis de Instância ]

• Através de análise de variáveis e métodos, é possível identificar oportunidades para reduzir a sincronização

• Muitas vezes, a proteção implementada é exagerada

Liveness[ Análise de Variáveis de Instância ]

• Acesso– Métodos de acesso podem deixar de ser

sincronizados para permitir leitura durante a escrita

– Condições para remover a sincronização:• A variável não pode assumir valores ilegais durante a

execução dos métodos• Atribuição atômica

Liveness[ Análise de Variáveis de Instância ]

• Atualização– Métodos de atualização podem abdicar da

sincronização quando satisfaz, além das condições para acesso:• Valor da variável permanece consistente em todas as

possíveis situações (Ex: atributo temperatura sendo atualizado constantemente por múltiplas threads)• Não requer ações especiais sincronizadas para certos

valores assumidos pelas variáveis (Ex: reconstruir uma estrutura de dados após atingir um tamanho)

Referências

• Concurrent Programming - Hartley (capítulo 1)• Concurrent Programming in Java - Lea

(capítulo 1, 2 e 3)