Programação Concorrente
Aula 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
Pilha
Espaço de
Endereçamento
Lógico de um
Processo
Heap
Dados Globais
Instruções
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 ]
Ativo
Bloqueado
Executável
Executando
Encerrado
Iniciado
Suspenso
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
Pilha
Thread 1
Thread 2
Thread n
Pilha
Pilha
Pilha
Contador
de Programa
Contador
de Programa
Contador
de Programa
Heap
Variáveis Globais
Instruções
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 ]
Intervalo de tempo expirou
sleep
Dormindo
Encerrada
escalonada
Criada
start
Término
Pronta
Executando
interrompida
Operação
de E/S
concluída
wait
notify
notityAll
Operação
de E/S
iniciada
Esperando
Bloqueada
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.
interno1
externo1
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
null
null
serviço 1
vizinho
vizinho
serviço 0
serviço 2
vizinho
vizinho
serviço 3
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)