Programação concorrente:
Problemas, comunicação e
sincronização de processo
Referências:
- Capítulo 2, Modern Operating Systems, A. Tanenbaum
- Capítulo 5, Operating Systems: Internals and Design Principles, Willian Stallings
- Capítulo 6, Operating System Concepts, Silberschatz & Galvin
- http://www.cne.gmu.edu/modules/ipc/
- Apostila
*baseado no material do Prof. Orlando Loques - IC/UFF
1
Conceito de processo
• Um sistema operacional executa uma variedade de programas de
forma “simultânea”
• Livros usam os termos job e processo quase que
indeterminadamente.
• Processo – um programa em execução; execução do processo
deve progredir de maneira seqüencial.
• Tecnicamente um processo é criado quando um outro
processo faz uma chamada ao sistema de criação de
processos
- Fork  clone identico ao processo que o chamou
• Inicialização de processos em segundo plano pelo
2
- Daemons
Estados do processo
• Durante a execução de um processo, ele
altera seu estado
–Novo (new): O processo está sendo criado.
–Executando (running): instruções estão sendo
executadas.
–Esperando (waiting): O processo está esperando
algum evento acontecer.
–Pronto (ready): O processo está esperando ser
associado a um procesador.
–Terminado (terminated): O processo terminou
sua execução.
3
Diagrama de estados do processo
4
Tipos de Processamento Concorrente
• Multiprogramação: vários processos em um sistema
monoprocessador
• Multiprocessamento: vários processos em um sistema
multiprocessador (memória comum - acesso
compartilhado)
• Processamento Distribuído: vários processos
executando em vários (multi) processadores distribuídos
(memória privada - acesso exclusivo)
5
Programação Concorrente
• Conceitos e mecanismos para expressar paralelismo potencial
• Facilita a solução de problemas inerentes associados ao
compartilhamento de recursos, à sincronização e à comunicação
de processos
• Provê as abstrações de programação para o tratamento de
situações comuns, existentes no mundo real
• sistemas operacionais
• sistemas de comunicação
• sistemas de controle de processos (embutidos)
• Pode ser suportada através do compartilhamento de um único
processador ou por vários processadores operando em paralelo
• Leva a sistemas eficientes, modulares e bem estruturados
6
Concorrência: utilizações
• Compartilhamento de recursos
• Sincronização de processos
• Comunicação entre processos
7
Exemplo de Compartilhamento
Atualização de uma variável compartilhada, exemplo: saldo bancário
var V:integer; // valor do saldo
...
processo T_1;
begin
.
.
|
V = V +1;
<---------------|
.
|
.
end;
processo T_2;
begin
.
.
V = V +1;
.
.
end;
{ sequência de instruções }
load V
add 1
store v
load V
|
<---------------| add 1
store v
|
8
Sequência de Execução
tempo
Processo
Ação
Valor de V
1
load V
4
2
load V
4
1
add 1
-
2
add1
-
1
store V
5
2
storeV
5
9
Outro Exemplo
procedure echo;
var out, in: character;
begin
input(in, keyboard);
out := in;
output(out, display)
end.
Programa simplesmente lê um valor e o imprime
10
P1, P2 executando em processadores separados
Cada processo tem uma linha de código executada por vez de forma alternada...
Entrada: “xy”
Process P1
--- echo
Process P2
--- echo
•
out := in
output(out,display)
•
•
•
•
input(in,keyboard) ”y”
out := in
•
output(out,display)
•
P1 e P2 concorrentes
Saídas: “yy” ou “xx” ?!
P1 e P2 exclusivos
Saída: “xy” ok!
•
input(in,keyboard) “x”
11
Condições de corrida (Race Conditions)
• Processos trocam dados, as vezes, através de
memória
–Principal, arquivo...
• Região/seção crítica
–Porção de programa que pode levar a condição
de disputa
• Tipo de memória não altera o problema
–Alguma forma de garantir que apenas 1 esteja na
região crítica
12
Condições de corrida (Race Conditions)
• Condições de Corrida:
–Situações onde dois ou mais processos
estão acessando dados compartilhados.
–O resultado final pode variar de acordo
com a ordem de execução.
• Mecanismo de Sincronização.
–Garante o compartilhamento de recursos e
a comunicação entre os processos.
–Garante a integridade e a confiabilidade
dos dados compartilhados.
13
Condições de corrida (Race Conditions)
• Exemplo 1:
2
1
7
7
Processo
A
3
7+1
Processo
B 4
7-1
7
5
8
6
6
14
Condições de corrida (Race Conditions)
2
Processo
A
• Exemplo 2:
8
suspenso
recebe CPU
10
Y
5
6
1
9
7
8
4
próxima
entrada
3
7
6
X
–Valor armazenado pelo
processo B é perdido.
4
5
7
8
Processo
B
3
7
recebe CPU
suspenso
15
Condições de corrida (Race Conditions)
• Região Crítica:
–Parte do código onde é feito acesso a recursos
compartilhados, e que podem levar a condições
de corrida.
• Ex: Processo A.
–Código normal
–Início da Seção Crítica (Protocolo de Entrada)
–
Seção Crítica
–Término da Seção Crítica (Protocolo de Saída)
–Código normal
16
Condições de corrida (Race Conditions)
• Enquanto um processo estiver usando um
recurso, os outros devem aguardar até que
o recurso esteja liberado.
• Exclusão Mútua.
–Exclusividade no acesso a um determinado
recurso.
• A exclusão mútua deve afetar os processos
concorrentes quando um deles estiver em
uma região crítica.
17
Regiões críticas
• Como evitar condições de disputa?
–Implementar exclusão mútua
–Um por vez junto à região
• Garantir que dois ou mais processos estarão
sincronizados, e só um dentro da região
crítica
–Operando sobre dados compartilhados
18
Regiões críticas
• Quatro requisitos básicos para os algoritmos
solucionarem o problema de região crítica
–Dois ou mais processos NUNCA podem estar
simultaneamente na região crítica
–Não considerar velocidade relativas dos
processos
–Quem estiver fora da região não pode bloquear
quem quer entrar
–Tem que entrar em algum momento!
19
Regiões críticas
20
Dois tipos de bloqueios
• Dois tipos de bloqueio são considerados
básicos:
– bloquear até que um recurso se torne
disponível;
– bloquear até que chegue um sinal de outro
processo.
21
Locks
Conceito e Implementações
22
Locks - Funcionamento
Um processo só entra num trecho delimitado pelo par
lock/unlock se nenhum outro processo está executando em um
outro trecho delimitado dessa maneira.
Isto é, o primeiro processo que executa o comando lock
passa e tranca a passagem (chaveia a fechadura) para os
demais.
O comando unlock deixa passar (desbloqueia) o primeiro
processo da fila de processos que estão bloqueados por terem
executado um lock (enquanto a fechadura estava trancada).
Se a fila está vazia, a fechadura é destrancada (isto é, é
23
deixada aberta).
Solução: Locks (i)
Definição:
Lock L = valor binário
L = 0  lock aberto; o processo prossegue
L = 1  lock fechado; o processo espera
Tentativa de Implementação
• Lock (L) ::= while L=1 do nothing;
L:= 1;
• UnLock (L) ::= L := 0;
Espera ocupada
o processo esperando em
um lock fica em loop,
usando inutilmente
o processador.
Isso pode degradar
o desempenho do sistema
24
Solução: Locks
•Encapsulamento Lock/Unlock garante a Exclusão Mútua
– Permite acesso seguro a variáveis compartilhadas
Thread_T;
begin
...
Lock (L);
- - seção crítica
UnLock (L);
...
end;
25
Implementação de Locks
• Hardware: Inibição de Interrupção
Lock ::= < desabilita interrupção >
Unlock ::= < habilita interrupção >
desligar_interrupções
zona crítica
ligar_interrupções
• A perda da capacidade de entremear a execução de programas
pode afetar o desempenho
• A capacidade de resposta rápida a eventos (associados a
interrupções) é também afetada
• Em multiprocessadores, mais que um processo pode estar
executando ao mesmo tempo: bloquear interrupções não
26
garante a exclusão mútua
Locks: Falha de TSL
TSL = Test and Set Lock
• Mecanismo implementado a nível de hardware
• É atômico
27
A instrução TSL pode falhar se o acesso ao barramento não for bloqueado
Sleep / Wakeup
28
Funcionamento
• Quando um processo P executa o comando sleep,
ele se bloqueia até que um outro processo execute
o comando wakeup(P).
• Este último comando acorda (desbloqueia) o
processo especificado por P.
• Se wakeup(P) é executado antes, o processo P não
se bloqueia ao executar o sleep.
• Não formam uma estrutura sintática (isto é, não
precisam estar casados, como se fossem um abre e
fecha parênteses), eles são comandos
independentes
29
Semáforo
Dijkstra 1965
30
Semáforos
• Em 1965 Dijkstra propôs usar uma variável inteira
para contar o número de sinais de acordar e salválos para uso futuro. Esta variável recebeu o nome
de semáforo e é usada para sincronizar processos.
• Seu objetivo é coordenar o acesso a uma região
crítica e evitar os problemas que levam a
condições de corrida.
• O Semáforo guarda a quantidade de wakeups
feito!!!
– valor 0 (indicando que nenhum sinal de acordar foi
salvo) ou outro valor positivo caso 1 ou mais sinais de
acordar estejam pendentes.
31
Semáforos
• Um semáforo S tem associado a ele:
- Um valor inteiro
- Uma fila de processos bloqueados
- Duas operações: P ou Wait & V ou Signal
Em holandes
P = Probeer ('Try')
V = Verhoog ('Increment', 'Increase by one').
32
Semáforos
• Para ser indivisível as operações P e V são implementadas
como chamadas de sistema. Com isso, por um pequeno
instante as interrupções são desabilitadas, mas não geram
nenhum problema.
• Semáforos Binários: apenas tomam valores 0 e 1. São
habitualmente usados para garantir exclusão mútua no acesso
a zonas críticas, e designam-se por mutexes.
33
Mutex
Mutual Exclusion
34
Mutex
• Mutex é uma versão simplificada dos semáforos que
serve para controlar o acesso a RC e que pode estar
somente em dois estados distintos: impedido ou
desempedido. Portanto, apenas um bit é necessário
para armazenar esta informação.
• Existe 2 procedimentos para usar o esquema de
mutex:
– 1. mutex_lock: se o mutex estiver desempedido (RC livre)
o processo ganha acesso a RC. Caso o mutex estiver
impedido o processo será bloqueado.
– 2. mutex_unlock: procedimento chamado pelo processo
que deixa a RC para liberar o acesso aos demais processos.
35
Mutex
36
Monitor
Hoare 74 / Brinch Hansen 73
37
Monitor: Conceito
• Mecanismo de sincronização de alto nível proposto
por Hoare (1974) e Brinch Hansen (1975);
• Conjunto de procedimentos e funções de alto nível
agrupadas em um módulo
– Similar a uma classe, na OO
• Característica mais importante é a implementação
automática da exclusão mútua:
–Somente um processo pode estar ativo dentro um
monitor em um determinado instante de tempo.
– Somente um procedimento sendo executado, até a completude, por
vez
– Programador livre de especificar as restrições
38
Monitor: Conceito
monitor example;
... declarações locais do monitor
… variáveis de condição
procedure entry proc_declaration_1;
:
begin
:
:
end;
procedure entry proc_declaration_2;
:
begin
:
:
end;
: // mais procedimentos ... //
begin
:
... iniciação do monitor
:
end example.
• entry:
assegura exclusão mútua na
execução do procedimento
• Java
entry = synchronized
• variáveis de condição:
• associadas a filas de espera
• definidas por expressões lógicas
• primitivas:
• wait (condição)
• signal (condição)
39
Monitor: Sistema
T_1
T_2
T_3
M_1
M_2
B_Dados
Display
T_4
40
Mensagens
41
Troca de mensagens
• Primitivas de SEND/RECEIVE
–Enviar para e receber de
–Recepção bloqueante
• Novos problemas
–Perda de mensagens
• ACK, NACK
–Recebimento duplicado
• Controle de seqüência
–Segurança...
42
Troca de mensagens
• Produtor/consumidor
Consumidor
enviar N msg vazias
while (TRUE) {
receive (produtor, &m);
extrai_item();
send (produtor, &m);
consome_item();
}
Produtor
while (TRUE) {
produz_item();
receive (consumidor, &m);
constroi_msg();
send (consumidor, &m);
}
43
Endereçamento indireto: caixa postal
Q1
P1
Pn
send ( mailbox , msg )
mailbox
Qn
receive ( mailbox , msg )
dilema em sistemas distribuídos: onde fica a caixa postal ?
44
Outras Técnicas
45
• Rendezvous
– Uma chamada coloca um processo
para dormir até que uma segunda
chamada rendezvous ocorra
• Eventos
– Processos subscrevem / manifestam interesse
por eventos
• RPC (Remote Procede Call)
• Distributed Shared Memory (DSM)
• Sincronização por barreira
– Processos inteiros esperam até que uma
“barreira” seja alcançada
46