Concorrência STRD
Roteiro
 Sistemas de Tempo Real
 Sistemas de Tempo Real Distribuidos
 Processos X Threads
 Concorrência
 Problemas
Sistemas de Tempo Real
 Trabalham sobre restrições temporais.
 Subsistemas de controle (computadores) e
subsistemas controlados (ambiente).
 Interação



Tirar amostras
Processar
Responder
 Respeitando restrições de tempo.
Sistemas de Tempo Real
 Hard Real Time
 Conseqüências catastróficas
 Ex.: Sistemas de controle de avião
 Soft Real Time
 Sem maiores conseqüências
 Ex.: Ar-condicionado
Sistemas de Tempo Real Distribuídos
 Sistemas distribuídos com restrições temporais.
 Processos distintos em diferentes processadores
trabalhando nos mesmos requisitos.
 Benefícios


Concorrência
Degradação
Sistemas de Tempo Real Distribuídos
 Finalidade
 Melhorar tempo de resposta
 Aumentar confiabilidade
 Aumento de complexidade
 Particionamento de tarefas
 Comunicação entre processos
Sistemas de Tempo Real Distribuídos
 Características
 Operação contínua
 Restrições de tempo severas
 Interação assíncrona entre processos
 Atrasos de comunicação e race conditions
 Resultados não deterministicos
 Estado global
 Múltiplas thread de interação de processos
Processos vs Threads
 Processos
 -Um processo é uma forma abstrata de encarar um
programa em execução.
 Threads
 -Linhas de execução dentro de um processo
Processos vs Threads
 Diferenças
Processos
Threads
Pode conter uma ou mais threads
Tem um único processo como dono
Cara comunicação entre
processos(Troca de contexto)
Comunicação barata, usa memória do
processo.
Seguro, não podem corromper outros
processos
Não é seguro, pois outras threads
podem usam a mesma memória do
processo.
Exclusão Mútua
 Técnica usada para evitar que dois processos ou
threads tenham acesso simultaneamente a um
recurso compartilhado
 Atende:
 Único processo em região crítica
 Todo processo deve eventualmente conseguir entrar em
sua região crítica
Busy waiting
 É o método de controle de sincronização onde uma
variável compartilhada cujo valor pode ser
manipulado (modificado e testado/test-and-set)
através de uma primitiva indivisível, cria-se um
modo simples para a sincronização de processos
concorrentes
Busy waiting
Busy waiting
 Busy-waiting possui várias desvantagens, como por
exemplo, o gasto supérfluo de CPU.
 Programas utilizando tais primitivas são difíceis de
entender, depurar e provar que estão corretos, em
virtude de serem implementados em baixo nível.
Semáforos
 Semáforos são estruturas de dados usadas para resolver
problemas de sincronização de tarefas.
 Foi inventado por Edsger Dijkstra.
 Tem como função o controle de acesso a recursos
compartilhados num ambiente multitarefa.
Semáforos
 Um semáforo S é uma variável inteiro positiva sobre a qual os
processos podem fazer duas operações P(S) e V(S).
 Operações de P e V são atômicas e indivisíveis.
 Uso de fila para manter processos que esperam no semáforo.
Semáforos
 Inicialização: Recebe um valor inteiro indicando a quantidade
de processos que podem acessar um determinado recurso.
 Operação P(S): Decrementa o valor do semáforo. Se o
semáforo está com valor zerado, o processo é posto para
dormir.
 Operação V(S): Se o semáforo estiver com o valor zerado e
existir algum processo adormecido, um processo será acordado.
Caso contrário, o valor do semáforo é incrementado.
Tipos de Semáforos
 Semáforos Binários
Valor inicial é 1.
 Usado para criar exclusão mútua no acesso a recursos .

 Semáforos de Contagem
Valor inicial é normalmente maior do que 1.
 Utilizados para sincronização e controle de alocação de
recursos
 Valor inicial do semáforo é igual ao número de unidades do
recurso

Monitores
 Monitor é um alto nível de construção para sincronização




em programação concorrente
Encapsula estados - Um monitor pode ser visto como uma
classe que pode ser usada em programas concorrentes
Como uma classe, um monitor tem métodos e atributos
para manipular dados
Várias threads podem acessar um monitor ao mesmo
tempo, logo ele possui suporte a métodos que garantem a
exclusão mútua
Todo monitor tem uma fila associada com threads
aguardando para entrar
Monitores
 Monitores possuem variáveis de condição
 Um variável de condição possui duas operações:
wait e notify
 Para uma variável de condição x, qualquer thread,
t1, que faça chamada para x.wait() é bloqueada e
colocada em uma fila associada com x
 Quando outra thread, t2, fizer uma chamada
x.notify(), se a fila associada com x não estiver
vazia, uma thread é removida da fila e inserida na
fila de threads que estão eleitas para executar
Sincronização de Processos
Processo
Processo
Recursos do Sistema
Processo
Processo
Corrupção de Dados
Procedure echo();
Var out, in: character;
begin
input (in, keyboard);
out := in;
output (out, display)
end.
Starvartion
P1
Recursos do Sistema
P2
P3
Deadlock
P1
R1
R2
P2
Soluções
 Exclusão Mútua
 Busy Wait
 Semáforo
Selective Waiting
 Se o programa “guardado” for um operador de
mensagem (receive, send) então chama-mos a
declaração de selective waiting(introduzido em
CSP).
Selective Waiting
 Passagem de mensagem: o receptor deve esperar
até que o processo ou canal entregue a
comunicação.
 Problema: a ordem de chegada das mensagens é
desconhecida para servidor
Selective Waiting
 Djikstra’s guarded commands
 Executado quando a guarda é verdadeira
 Determinismo
Uso de guardas: Não-determinística (Choice)
 Uso de declarações definidas: Escolha determinística (if)

Selective Waiting

Validação da guarda:
Mais de uma verdadeira: escolha arbitrária.
 Nenhuma verdadeira: erro de condição => declaração abortada.

Utilização de Recursos
 Controle dos recursos
 dispositivos externos, arquivos, dados compartilhados, etc
 Podem ser requisitados por vários processos que
estão rodando concorrentemente
 Evitar deadlocks e inconsistências
Gerenciamento e utilização desses Recursos
• Processos:
– Servers: Processos que controla o acesso e encapsula recursos
do sistema
– Clients: Processos que irão utilizar os recursos
• Conditional Wait
• Avoidance
• Utilização:
– Shared
– Exclusive
Deadlock
 Situação no sistema onde dois ou mais processos
ficam impedidos de continuar suas execuções
 Condições para que ocorra um deadlock:




Condição de não-preempção
Condição de espera circular
Condição de exclusão mútua
Condição de posse-e-espera
Deadlock
• A prevenção pode ser feita garantindo que pelo
menos uma das condições citadas nunca ocorra
• Pode ser evitado fazendo com o que o sistema
verifique as consequências da alocação de um
recurso
• Recuperação do sistema:
–
–
–
Desabilitando a exclusão mútua de algum recurso
Abortando um ou mais processos
Preempção de alguns recursos de um ou mais processos que
estão em deadlock
Referências
 Burns, Allan and Wellings, Andy. Real Time System
and Their Programming Languages.
 Tsai, Jeffrey and Yang, Steve. Monitoring and
Debugging of Distributed Real Time Systems.