10
Concorrência
 Por que concorrência?.
 Programas e processos.
 Problemas com a concorrência.
 Interações de processos.
 Primitivas de concorrência
 Abstrações para controle da concorrência
7-1
Por que concorrência? (1)
 A
concorrência
foi
inicialmente
introduzida
nos
computadores com o objetivo de melhorar o desempenho
• Realização de E/S e operações da CPU em simultâneo, que
acarretou o surgimento da programação concorrente
 A programação concorrente ficou muito complexa para o
programador de aplicações
• Restringiu-se basicamente aos sistemas operacionais, que seriam os
arquétipos dos programas concorrentes
7-2
Por que concorrência? (2)
 Os sistemas de multiprogramação objetivam maximizar o
uso dos recursos através da execução de dois ou mais jobs
concorrentemente
 Sistemas de multiacesso ou servidores estendem a
multiprogramação, permitindo que vários jobs executem,
cada um em benefício de um usuário remoto
 Sistemas de multiprocessador estão presentes em
computadores que várias CPUs operando simultaneamente
na execução de jobs que compartilham uma memória
principal
7-3
Por que concorrência? (3)
 Sistemas distribuídos consistem de vários computadores
que não apenas operam independentemente, mas que
também se intercomunicam eficientemente
 A medida que a velocidade das CPU atingem limites
tecnológicos, ganhos futuros em desempenho dependem de
uma melhor exploração da concorrência
 A concorrência em linguagem de programação é necessária
para permitir a modelagem mais precisa dos aspectos
concorrentes do mundo real
 Desenvolvimento de arquiteturas de computadores novas e
7-4
altamente concorrentes
Programas e Processos (1)
 Um processo seqüencial é um conjunto totalmente ordenado
de passos, cada passo sendo uma mudança de estado em
algum componente de um sistema de computação
 Um programa seqüencial especifica as possíveis mudanças
de estado de um processo seqüencial, as quais ocorrem numa
ordem determinada pelas estruturas de controle do programa
 Um programa concorrente especifica as possíveis
mudanças de estados de dois ou mais processos seqüenciais
• Nenhuma ordem é naturalmente definida entre as mudanças de
estados de um processo em relação a mudanças de estados de
quaisquer outros processos
• Dizemos que estes processos são executados concorrentemente,
7-5
podendo até mesmo serem executados simultaneamente
Programas e Processos (2)
 O exemplo de um processo seqüencial é a execução de um
programa numa linguagem como Pascal ou C
• Os eventos de um processo como este correspondem à atualização das
variáveis do programa
• Tais eventos são totalmente ordenados pelas regras de seqüenciamento da
linguagem, que definem como o controle é transferido de um comando
para outro
 Por causa da total ordenação dos eventos, pode-se associar à
passagem do tempo físico as mudanças de estado de um
programa seqüencial
• Mudanças de estado de baixo nível podem não ser totalmente ordenadas
no tempo, porém como não são observáveis pelo programador e como
não afetam o resultado final, não são consideradas relevantes
7-6
Problemas com a concorrência (1)
 O que faz os programas concorrentes serem diferentes dos
programas seqüenciais?
 Não-determinismo (1)
• Um programa determinístico é aquele que segue uma seqüência de
passos que pode ser prevista caso saibamos seus dados de entrada
– Programas seqüenciais corretos são sempre determinísticos
– Logo, seu comportamento pode ser completamente reproduzido, tornando
praticável a verificação de programas por meio de testes
• Existem construções que introduzem alguma imprevisibilidade em
programas seqüenciais como:
– Comandos colaterais
– Comandos condicionais não determinísticos
– Avaliação colateral de subexpressões, onde uma destas subexpressões pode
provocar efeitos colaterais em outra
7-7
Problemas com a concorrência (2)
 Não-determinismo (2)
• Em cada um destes casos
– O processador da linguagem é livre para escolher a ordem de
execução
– O comportamento do programa poderá ser diferente com
processadores distintos, mas certamente será o mesmo num
processador de linguagem específico
– Logo o comportamento do programa poderá ser reproduzido
• Um programa concorrente, por outro lado, é verdadeiramente nãodeterminístico
– A ordem de execução dos passos é imprevisível, assim como o
resultado final, mesmo num processador de linguagem específico
• Em geral, deseja-se escrever programas efetivamente
determinísticos, isto é, um programa cujo resultado global seja
previsível
7-8
Problemas com a concorrência (3)
 Não-determinismo (3)
• Entretanto, um programa concorrente incorreto pode se comportar
como previsto a maior parte do tempo, mas pode desviar de seu
comportamento previsto de modo intermitente e irreproduzível
– Erros de programação concorrente são dos mais difíceis de se
diagnosticar
– A pesquisa de meios para preveni-los é uma grande motivação na área
de programação concorrente
7-9
Problemas com a concorrência (4)
 Dependência de Velocidade (1)
• Um programa seqüencial é independente de velocidade porque
sua correção não depende da velocidade com que é executado
• Um programa concorrente, em geral, é dependente de velocidade,
visto que suas saídas podem depender da velocidade relativa de
execução dos processos que o compõem
– Como conseqüência, pequenas flutuações na velocidade dos
processadores e dos dispositivos de E/S podem levar ao nãodeterminismo
– Quando velocidades absolutas devem ser levadas em conta, tem-se
um programa em tempo real
– Quando o resultado é dependente de velocidade, diz-se que existe
uma condição de corrida (race condition)
7-10
Problemas com a concorrência (5)
 Dependência de Velocidade (2)
• Exemplo: condição de corrida
– Suponha que dois processos P e Q atualizam a mesma variável
tipo String
s
do
 In P: s := "ABCD";
In Q: s := "EFGH";
– Se P completa a atribuição antes de Q começar a atribuição, o valor
final de s é "EFGH"
– Se Q completa a atribuição antes de P começar a atribuição, o valor
final de s é "ABCD"
– Mas, supondo que P e Q atualizam s um caractere por vez, o valor
final de s pode ser um dentre 60 valores, ou seja, pode haver um
7-11
resultado diferente cada vez que P corre com Q
Problemas com a concorrência (6)
 Dependência de Velocidade (2)
• Imagine-se caos do problema anterior com múltiplos processos e
variáveis
– Um dos objetivos da programação concorrente é prevenir este pesadelo
 Uso de variáveis atômicas – aquelas que só podem ser inspecionadas ou
atualizadas como um todo
» Em Java, referência a objetos e variáveis de tipos primitivos diferentes de long
e double são sempre atômicas
» Em Ada, qualquer variável pode ser declarada atômica com a cláusula
pragma atomic(v);, embora o compilador seja livre para rejeitá-la
– Entretanto, tais medidas estão longe de ser uma solução completa
7-12
Problemas com a concorrência (7)
 Deadlock (1)
• Deadlock é o bloqueio permanente de um conjunto de processos que, ou
estão competindo por recursos, ou estão competindo para se comunicar uns
com os outros
• O deadlock pode ocorrer num sistema de processos e recursos, se e
somente se, as seguintes condições existirem todas juntas
– Exclusão mútua: os processos podem ter acesso exclusivo aos recursos
– Aquisição incremental: os processos continuam a prender recursos
previamente alocados, enquanto esperam que a requisição de um novo recurso
seja atendida
– Não preempção: recursos não podem ser removidos de um processo até que ele
voluntariamente o libere
– Espera circular: pode existir um ciclo de recursos e processos no qual cada
processo está esperando por um recurso que está preso pelo próximo processo
no ciclo
7-13
Problemas com a concorrência (8)
 Deadlock (2)
• Vários enfoques podem ser empregados para solucionar o problema do
deadlock
– Ignorar o deadlock e caso ele aconteça, resolver o problema manualmente pela
interferência do operador do sistema, destruindo alguns processos ou
reinicializando todo o sistema
– Outra opção é detectar o deadlock e então recuperar-se dele automaticamente,
de modo que o sistema como um todo possa continuar funcionando
– Prevenir o deadlock pela eliminação de uma ou mais condições necessárias à
sua ocorrência
 Eliminação da aquisição incremental de processos – ou tudo ou nada
 Eliminação da espera circular – imposição de uma ordem de aquisição de recursos
– Fazer com que os escalonadores do sistema evitem ativamente o deadlock pela
determinação antecipada dos processos que se pretende alocar
 Algoritmo do banqueiro
7-14
Problemas com a concorrência (9)
 Starvation (1)
• Um sistema concorrente tem a propriedade de avanço finito se
houver a garantia de que todo processo avançará em algum período
suficientemente grande de tempo (mas finito)
– Para atender a esta condição o sistema deve
 Ser livre de deadlock
 Ter um escalonamento justo
» Escalonamento é a alocação de recursos para processos no tempo, tendo por
meta algum objetivo, como um tempo de resposta adequado ou a alta utilização
da CPU
» O escalonamento justo assegura que nenhum processo necessitando de um
recurso vai ficar esperando indefinidamente para obter o recurso por causa da
demanda de outros processos
7-15
Problemas com a concorrência (10)
 Starvation (2)
• Usa-se o termo starvation quando um processo fica esperando
indefinidamente para executar por causa de um escalonamento
injusto
– Uma situação de starvation pode ocorrer quando o acesso a CPU é
dado preferencialmente aos processos de alta prioridade
 Neste caso, deste que se tenha um sempre um processo de alta prioridade
na vez para usar a CPU, um processo de baixa prioridade pode ficar
esperando indefinidamente a sua vez para executar
7-16
Interações de Processos (1)
 A notação C; K especifica a composição seqüencial dos
comandos C e K
 A notação C, K especifica a composição colateral dos
comandos C e K
 A diferença entre os dois é que na composição seqüencial
todas as ações de C devem ser encerradas antes que qualquer
ação de K comece; enquanto na composição colateral as ações
de C e K podem ser intercaladas arbitrariamente
 Nenhuma das notações admite a possibilidade dos comandos
C e K serem executados simultaneamente
7-17
Interações de Processos (2)
 Para isto, usa-se o comando paralelo B || C, que é a
composição concorrente dos comandos B e C
• Especifica que dois ou mais comandos podem ser executados
concorrentemente
• B || C não requer a execução simultânea dos comandos B e C, mas
permite isto
• B || C também permite a execução colateral e a execução seqüencial
dos comandos B e C como casos particulares de concorrência
 Programas concorrentes se distinguem dos seqüenciais não
apenas pela presença da composição concorrente, mas
também pela presença de operações que causam interações
entre processos, que pode ser de vários tipos
7-18
Interações de Processos (3)
 Processos independentes (1)
• Os comandos B e C são independentes se nenhum passo de B pode
afetar o comportamento de qualquer passo de C e vice-versa
– Se B e C são independentes, segue que a composição seqüencial B; C é
equivalente a composição seqüencial C; B
– Também pode-se concluir que B; C, C; B e C, K são equivalentes a
C || K quando C e K são independentes
– Logo, segue que a composição concorrente de processos independentes é
determinística
• Este é um resultado importante porque
– Prover a base para sistemas servidores de multiacesso, que podem
executar muitos jobs pela multiprogramação de um ou mais processadores
– Sendo os jobs independentes, os usuários não precisam tomar precauções
especiais por conta da concorrência
7-19
Interações de Processos (4)
 Processos independentes (2)
• Infelizmente, não é decidível, em geral, se os comandos B e C são
realmente independentes
– Entretanto, uma condição suficiente para independência é que nenhum
comando possa atualizar uma variável que outro comando inspeciona
ou atualiza
 Embora possa ser verificado, em princípio, em tempo de compilação,
deve-se empregar uma definição abrangente de variável, como qualquer
componente do sistema cujo estado possa ser alterado
7-20
Interações de Processos (5)
 Processos competidores (1)
• Os comandos B e C competem se cada um precisa ganhar acesso
exclusivo ao mesmo recurso r para executar alguns de seus passos
• Seja B a seqüência B1;B2;B3 e C a seqüência C1;C2;C3
– Os subcomandos B1, B3, C1 e C3 são independentes , ou seja, nenhuma deles
usa o recurso r
– B2 e C2 requerem acesso exclusivo ao recurso r e não devem executar
simultaneamente nem sua execução se sobrepor no tempo
 B2 e C2 são chamados de seções críticas com respeito ao recurso r
7-21
Interações de Processos (6)
 Processos competidores (2)
– B || C deveria ser executado numa das seguintes maneiras
 ...; B2; ...; C2; ...
 ...; C2; ...; B2; ...
mas não como
 ...; B2 || C; ...
– Então, B || C tem dois possíveis resultados, que são exatamente os
resultados das seqüências B; C e C; B, respectivamente
 Qual destes resultados realmente ocorre dependerá das velocidades relativas
com que B e C são executados e isto não é previsível em geral
 Caso o efeito de uma seção crítica dependa do estado do recurso quando ele é
adquirido e se a seção muda o estado do recurso, então o sistema B || C é nãodeterminístico em geral
• Um programa concorrente possui a propriedade de safety (segurança)
se suas seções críticas nunca se sobrepõem no tempo
– É seguro no sentido de que todos os comando que ele aplica sobre um
7-22
recurso terá o seu efeito seqüencial normal
Interações de Processos (7)
 Processos competidores (3)
• Exemplo: Não determinismo apesar da exclusão mútua
– Suponha que dois processos P e Q atualizam a variável
atômica e com valor inicial 0
i
do tipo
Integer,
– Os comandos de atribuição de P e Q estão em exclusão mútua, um em
relação ao outro
 In P: i := i + 1;
In Q: i := 2 * i;
– Existe corrida (race) entre P e Q, mas os dois únicos possíveis resultados
em i são 1 (Q executa a atribuição antes de P) ou 2 (P executa a atribuição
antes de Q)
 É que se chama de não determinismo delimitado: o resultado não é previsível,
mas pertence a um conjunto conhecido e fixo de saídas, todas igualmente
aceitáveis
7-23
Interações de Processos (8)
 Processos comunicantes (1)
• Sejam os comandos B e C como vistos anteriormente
– Existe comunicação de B para C caso B2 produza dados que C2 consuma,
de modo que B2 termine antes de C2 começar
 Neste caso, B || C tem o mesmo resultado que B; C
 Um pipeline ocorre quando existe uma encadeamento de processos, cada um
consumindo a saída do processo anterior e produzindo a entrada do processo
seguinte
» Exemplo: comandos pipeline do UNIX – "B | C"
• Os processos B e C se intercomunicam caso exista comunicação em
ambas as direções
– Isto torna os possíveis resultados de B || C muito mais numerosos e
– Força a impor uma severa disciplina nas formas de intercomunicação
permitidas, caso se deseje preservar o gerência intelectual dos programas
7-24
Primitivas de Concorrência (1)
 Conjunto de operações de baixo nível que afeta a
concorrência através de sua criação, controle e destruição
• Fundamental para entender as construções de alto nível das
linguagens de programação concorrente
 Tipos de processos (1)
• Processos convencionais – havyweight: é a execução de um programa
para o qual o sistema operacional prover um espaço de
endereçamento, a alocação de memória principal e também o
compartilhamento da CPU e de outros recursos
– Sobrecarga substancial para criação de processos e também na troca de
contexto de um processo para o outro pelo sistema operacional
7-25
Primitivas de Concorrência (2)
 Tipos de processos (2)
• Processos thread – lightweight: é um fluxo de controle através de um
programa, mas que não possui recursos computacionais
independentes
– Uma thread existe dentro de um processo e depende dos recursos do
processo
 A troca de contexto de thread para thread de um processo pode ser
implementada de forma simples e eficiente
» Java usa o termo thread
» Ada usa o termo tarefa (task)
• No livro-texto, termo processo será usado com neutralidade,
independente de ser havyweight ou lightweight
7-26
Primitivas de Concorrência (3)
 Criação e controle de processos (1)
• As operações primitivas relativas processos são as seguintes
– create um processo filho novo e inativo
– load o código de programa a ser executado por um processo
– start a execução de um processo
– suspend a execução de um processo (temporariamente)
– resume a execução de um processo (suspenso)
– permitir que um processo stop ele mesmo ao fim de sua execução
– permitir que seu criador wait por pelo processo para parar
– destroy um processo parado, liberando quaisquer recursos alocado
para ele
7-27
Primitivas de Concorrência (4)
 Criação e controle de processos (2)
• É sempre conveniente combinar as operações create, load e start
numa única operação, em geral chamada fork e combinar wait e
destroy numa única operação chamada join
– fork é sempre definido de modo que o programa do processo filho é
uma cópia exata do programa do processo pai
– No sistema operacional UNIX, a operação fork é uma função sem
parâmetros que retorna um inteiro
 No processo pai este inteiro é a identificação do novo processo filho criado,
enquanto no processo filho, este inteiro é zero
• As primitivas são bem gerais, permitindo a criação de quaisquer
sistemas de processos concorrentes ativos
– Têm a desvantagem de não revelar com clareza o fluxo do controle do
programa, que se desenvolve dinamicamente
7-28
Primitivas de Concorrência (5)
 Criação e controle de processos (3)
• Exemplo: forking um novo processo no UNIX
– child_id := fork;
if child_id = 0 then
programa filho
else
continua programa pai
– O UNIX não tem operação join. Um processo é destruído
automaticamente quando termina
• Além de operações para criação e terminação de processos, é preciso
operações que permitam uma comunicação e competição pacífica
entre os mesmos
7-29
Primitivas de Concorrência (6)
 Criação e controle de processos (4)
• Para permitir que as seções críticas de processos competidores sejam
disjuntas no tempo, as operações primitivas acquire(r) e relinquish(r)
são usadas para obter e liberar, respectivamente, o acesso exclusivo ao
recurso r
– Caso r já esteja alocado, acquire(r) bloqueia o processo que a executou
– Quando relinquish(r) é executado pelo processo que no momento detém
o recurso r, r se torna livre para ser realocado e os processos que estão
esperando por r são reescalonados
 Um desses processos pega r exclusivamente, completando sua operação
acquire(r)
7-30
Primitivas de Concorrência (7)
 Criação e controle de processos (5)
• Um par de operações similares suportam a comunicação entre
processos:
– Um processo transmissor chama a operação transmit(c), que envia uma
mensagem notificando a ocorrência de um condição c
 c pode ser, por exemplo, "operação de E/S terminada" ou "CPU 2 foi
reiniciada"
– O processo receptor chama a operação receive(c), que o bloqueia até que
a condição c ocorra
– A operação transmit pode se comunicar com um processo receptor
específico ou ser na forma de difusão (broadcast), tornando a
transmissão disponível a qualquer receptor interesado
– Caso não haja um receptor apto no momento da transmissão, ela pode se
perder ou pode ser armazenada – o projeto das primitivas determina o
7-31
tipo de comportamento
Primitivas de Concorrência (8)
 Interrupções
– Uma interrupção é, na prática, uma chamada de procedimento invisível
inserido aleatoriamente em algum ponto do programa!
• Usadas em operações de entrada e saída, para indicar que uma
operação autônoma de E/S terminou
• Se o dispositivo de E/S for visto como um processo externo, a
interrupção pode tratada como um mecanismo para comunicação entre
processos
– Estendendo este conceito, pode-se permitir que um processo (interno)
interrompa outro – comando kill no UNIX
• Trocas de contextos, em geral, são implementadas com interrupções
– Combina níveis de prioridade e possibilidade de inabilitação de
interrupções
7-32
Primitivas de Concorrência (9)
 Algoritmos spin locks e espera-livre (1)
• Um spin lock é um loop de espera ocupada no qual um processo espera
para acessar (exclusivamente) um recurso compartilhado através de
repetidos testes num flag que indica se o recurso está livre
• A primeira pessoa a conseguir este feito (um algoritmo que
implementasse exclusão mútua) foi o matemático Dekker em 1968 num
trabalho apresentado por E. Dijkstra
– O trabalho apresenta uma série de tentativas incorretas de implementação,
que ilustram as dificuldades encontradas pelo programador para lidar com
acesso exclusivo a variáveis compartilhadas
– Assume a serialização justa nas operações de acesso à memória realizadas
concorrentemente pela CPU/interface de memória
7-33
Primitivas de Concorrência (10)
 Algoritmos spin locks e espera-livre (2)
• Série de tentativas que culminaram no algoritmo de Dekker (1)
– Assume-se a existência de dois processos 1 e 2, cada um executando um
programa com a seguinte forma (self sendo 1 ou 2)
– repeat
código não crítico para processo self;
acquire(r);
seção crítica para processo self;
relinquish(r);
exit when processo self estiver finalizado;
until processo self ser terminado
com um padrão cíclico de acesso ao recurso protegido r
7-34
Primitivas de Concorrência (11)
 Algoritmos spin locks e espera-livre (3)
• Série de tentativas que culminaram no algoritmo de Dekker (2)
– A primeira é usar uma variável turn, inicializada com 1 ou 2, que indica
quais dos dois processos tem permissão para entrar na sua seção crítica.
Cada processo self implementa as primitivas de exclusão como segue
– acquire(r):
while turn = other loop null; end loop;
relinquish(r):
turn := other
– Isto certamente garante que apenas um dos processos entre por vez na sua
seção crítica. Entretanto, é uma solução é muito rígida uma vez que impõe
uma ordem alternada de entrada dos processos na seção crítica
7-35
Primitivas de Concorrência (12)
 Algoritmos spin locks e espera-livre (4)
• Série de tentativas que culminaram no algoritmo de Dekker (3)
– Uma segunda tentativa usa um array claimed, com um valor booleano para
cada processo, indicando se este processo reclamou o direito de entrar na sua
seção crítica. Ambos os componentes de claimed são inicializados com false
– acquire(r):
while claimed(other) loop null; end loop;
claimed(self) := true
relinquish(r):
claimed(self) := false
– O algoritmo falha se o processo 1 (digamos) está num ponto após ter
encontrado claimed[other] = false e antes de fazer claimed[self] = true.
Neste momento específico abre-se uma brecha para que o processo 2 entre no
seu loop e descubra que claimed[self] ainda é = false. No caso, ambos os
processos fariam claimed[self] igual true e poderiam entrar nas suas seções
críticas concorrentemente. Logo, a exclusão mútua não está garantida 7-36
Primitivas de Concorrência (13)
 Algoritmos spin locks e espera-livre (5)
• Série de tentativas que culminaram no algoritmo de Dekker (4)
– Uma maneira de consertar tal problema seria modificar a operação acquire(r)
como segue
– acquire(r):
claimed(self) := true;
while claimed(other) loop null; end loop;
– Mas, nesta situação, um problema surge caso o processo 1 (digamos) esteja
num ponto após fazer claimed[self] = true e antes de entrar no loop. Isso
permite que o processo 2 faça o mesmo, ficando ambos os processos
reclamando uso do recurso compartilhado indefinidamente e nunca mais
conseguirão entrar na sua seção crítica
7-37
Primitivas de Concorrência (14)
 Algoritmos spin locks e espera-livre (6)
• Série de tentativas que culminaram no algoritmo de Dekker (5)
– Corrige-se essa falha permitindo que cada processo retire sua reclamação
temporariamente durante o loop, dando a oportunidade ao outro processo para
prosseguir
– acquire(r):
claimed(self) := true;
while claimed(other) loop
claimed(self) := false;
while claimed(other) loop null; end loop;
claimed(self) := true
end
– Esta solução funciona com sucesso na maior parte das situações, mas tem um
falha fatal. Caso os dois processos executem exatamente a uma mesma
velocidade e em perfeita fase, pode acontecer que nenhum dos processos
descubra que o outro está oferecendo uma chance para ele continuar.
7-38 Esta
solução falha porque é dependente de velocidade
Primitivas de Concorrência (15)
 Algoritmos spin locks e espera-livre (7)
• Algoritmo de Dekker para exclusão mútua
– Combina as melhores características das tentativas anteriores. Usa as variáveis
turn e claimed, como inicializadas anteriormente, do seguinte modo
– acquire(r):
claimed(self) := true;
while claimed[other] loop
if turn = other then
claimed(self) := false;
while turn = other loop null; end loop;
claimed(self) := true
end if;
end loop;
relinquish(r):
turn := other;
claimed(self) := false
– O algoritmo de Dekker é bastante complexo e difícil de generalizar para mais
de dois processos preservando a justiça. O algoritmo de Peterson, descoberto
7-39
em 1981 está livre destes problemas
Primitivas de Concorrência (16)
 Algoritmos spin locks e espera-livre (7)
• Algoritmo de Peterson para exclusão mútua
– acquire(r):
claimed(self) := true;
turn := other;
while claimed(other) and (turn = other)
loop null; end loop;
relinquish(r):
claimed(self) := false
7-40
Primitivas de Concorrência (17)
 Algoritmos spin locks e espera-livre (8)
• O código baseado em spin locks pode apresentar problemas
– A otimização de loops pode pré-alocar variáveis em registradores, de tal forma
que a sua atualização num processo não é percebida pelos outros
 Pode-se prevenir isto em C, C++ e Java declarando a variável com o modificador
volatile
»
Em Java, variáveis long e double declaradas voláteis passam a ser também atômicas, assim como as
demais variáveis de tipos primitivos, porém, não há como garantir a volatilidade dos elementos de um
array em Java!
 Em Ada, uma variável declarada como atômica é automaticamente volátil, que
também pode ser declarada volátil explicitamente
» pragma volatile(v);
» pragma volatile_componentes(a);
7-41
Primitivas de Concorrência (18)
 Algoritmos spin locks e espera-livre (9)
• Spin locks são onerosos em tempo de CPU
– A sobrecarga à CPU limita o desempenho de um sistema altamente concorrente
– Os algoritmos de espera-livre conseguem reduzir a sobrecarga, mesmo sem
aplicar funções de bloqueio – que fazem um processo suspender a si mesmo
 Funções de bloqueio podem provocar uma regressão infinita se chamadas pelo
escalonador do sistema operacional para implementação da exclusão mútua à suas
próprias variáveis
 Tais algoritmos podem precisar de instruções especiais que permitem a atualização
atômica de mais de uma posição de memória
» A memória cache pode ser um problemas em sistemas multiprocessados!
 O algoritmo de Simpson, de 1990, é um desses algoritmos de espera-livre,7-42
e não usa
bloqueios ou spin locks
Primitivas de Concorrência (19)
 Eventos (1)
• Um evento representa uma categoria de mudanças de estados, cuja
ocorrência deve ser comunicada para um conjunto de processos
– Implementado pelas operações event-wait(e) e event-signal(e), com e sendo
um valor de um tipo abstrato de dado
 Quando um processo executa event-wait(e), ele fica bloqueado, esperando pela
próxima ocorrência de um evento de categoria e
 A operação event-signal(e) faz com que todos os processos que estão bloqueados
por e fiquem prontos para executar novamente
7-43
Primitivas de Concorrência (20)
 Eventos (2)
• Exemplo: spin lock com bloqueio
– Implementação de uma versão com bloqueio da operação acquire(r), com
cada recurso r associado a um evento r-freed que é sinalizado periodicamente
– Usando o algoritmo de Peterson, tem-se
– acquire(r):
claimed(self) := true;
turn := other;
while claimed[other] and (turn = other) loop
event-wait(r-freed);
end loop;
7-44
Primitivas de Concorrência (21)
 Eventos (3)
• Considerado como primitivas de comunicação, eventos têm desvantagens
– As operações wait e signal não são comutativas, sendo sujeitas a dependência
de velocidade
– A operação
event-signal(e)
desperta todos os processos bloqueados no
evento e, de modo que esta implementação de transmit é interpretada como
broadcasting (difusão)
– Eventos não são úteis para exclusão mútua, devendo-se ter um suporte em
separado para isto (como spin locks ou interrupções)
 Apesar das desvantagens, o uso de eventos combinados com interrupções proveu a
base original para bem sucedida gerência de processos na família de sistemas
operacionais UNIX
7-45
Primitivas de Concorrência (22)
 Semáforos (1)
• Um semáforo é uma variável S do tipo inteiro e um grupo associado de
processos esperando para executar, sobre a qual apenas duas operações
atômicas podem ser realizadas, além de uma operação de incialização
– P(S): if S  1 then
S := S  1
else o processo em execução se coloca no grupo de processos associados a S que estão
esperando para executar e libera a CPU
end if;
– V(S): if fila de processos de S é não vazia then
remova um processo que está esperando e o coloque disponível para executar
else
S := S + 1
end if;
7-46
Primitivas de Concorrência (23)
 Semáforos (2)
• Exemplo: implementação de exclusão mútua

Shared Variable
var S: semaphore := 1;
Process i
Process j
loop
...
P(S);
Acessa seção crítica
V(S);
...
end loop;
loop
...
P(S);
Acessa seção crítica
V(S);
...
end loop;
7-47
Primitivas de Concorrência (24)
 Semáforos (3)
• Semáforos são comutativos, sendo adequados para implementação de
sincronização – exemplo para o problema produtor/consumidor

Shared Variable
var X: semaphore := 1;
F,E: semaphore := 0,1;
buffer: Char;
Process Producer
var nextChar: Char;
Process Consumer
var nextChar: Char;
loop
GetChar(nextChar);
P(E);
P(X);
buffer := nextChar;
V(X);
V(F);
end loop;
loop
P(F);
P(X);
nextChar := buffer;
V(X);
V(E);
PutChar(nextChar);
end loop;
7-48
Primitivas de Concorrência (25)
 Semáforos (5)
• No exemplo anterior, a sincronização é feita pelos semáforos F e E que
indicam se o buffer está cheio ou vazio, respectivamente. Já a exclusão
mútua é realizada com o semáforo X
• Caso vários processos estejam esperando num mesmo semáforo, não está
definido qual deles será reativado pela operação V(S)
– Isto permite uma liberdade que o projetista pode usar para incluir um critério
de escalonamento mais adequado para sua aplicação. O único requisito é que
este critério seja justo
• Ao contrário de eventos, as operações com semáforos são comutativas,
tornando os programas menos suscetíveis a dependência de velocidade
induzidas por erros de programação
7-49
Primitivas de Concorrência (26)
 Semáforos (6)
• Semáforos, assim como eventos e todas as primitivas de baixo nível, têm
uma séria desvantagem
– A conexão entre um recurso qualquer (ou condição) a uma operação de
semáforo é apenas uma convenção
– O esquecimento da chamada a uma destas primitivas pode ser desastroso
• Uma vantagem é que semáforos podem ser usados para implementar
exclusão mútua e comunicação
• Em algumas arquiteturas, os semáforos são implementados como instruções
de máquina dado ao seu baixo nível de abstração
7-50
Primitivas de Concorrência (27)
 Mensagens (1)
• Spin Locks, eventos e semáforos não são apropriados para sistemas
distribuídos nos quais os processos executam em rede, sem
compartilhamento de memória
– A rede provê um serviço de comunicação que suporta a interação entre
processos por meio da troca de mensagens
 A troca de mensagens também pode ser usada como a base para interação entre
processos num sistema de memória compartilhada
» Tem a desvantagem de possuir uma sobrecarga maior, quando comparado com outras
primitivas, como os semáforos
– O envio de mensagens pressupõe um canal que pode levar uma mensagens de
um processo para outro
 O canal pode ser identificado por uma fila de mensagens (buffer) e dever permitir a
comunicação entre um número arbitrário de transmissores e receptores
7-51
Primitivas de Concorrência (28)
 Mensagens (2)
– Quando um canal é implícito, suporta apenas a comunicação um-para-um, com
o transmissor devendo saber a identificação do receptor
– Este canal pode suportar a
 Comunicação em apenas uma direção (simplex)
 Comunicação em ambas as direções (duplex)
– As operações primitivas sobre canais incluem:
 connect um processo a um canal
 disconnect um processo de um canal
 send uma mensagem através de um canal
 receive uma mensagem de um canal ou espera por sua chegada
 test pela existência de uma mensagem de entrada num canal
– Uma mensagem pode ser formada por cópia dos dados do transmissor (mais
usados em sistemas distribuídos) ou por uma referência a dados compartilhados
(mais usados em sistemas de memória compartilhada)
7-52
Primitivas de Concorrência (29)
 Chamada remota de procedimentos – RPC
• Numa RPC (Remote Procedure Call), o ambiente em tempo de execução
determina o site onde o procedimento chamado está e se comunica
sincronamente com o site para chamá-lo
– Oferece uma abstração para comunicação via mensagens, facilitando a
programação e o entendimento do código
• O site que tem este procedimento pode, quando do recebimento da
chamada remota, criar um processo para executá-la
• Alternativamente, um processo servidor no site pode receber todas as
chamadas remotas e atendê-las
• Esta escolha é feita com base no custo relativo da criação do processo em
relação a comunicação e também pelo grau de concorrência desejado
7-53
Abstrações para controle da concorrência (1)
 Objetivam organizar os programas concorrentes assim como
outras
abstrações
já
estudadas
organizam
os
programas
seqüenciais
• Regiões Críticas Condicionais
• Monitores
• Rendezvous
 Construções de alto nível que simplificam o desenvolvimento e o
entendimento de programas concorrentes
7-54
Abstrações para controle da concorrência (2)
 Regiões críticas condicionais (1)
• Uma região crítica condicional é um comando composto que provê, tanto
exclusão mútua, quanto comunicação
– A idéia chave é que cada variável a ser compartilhada entre processos seja
declarada como tal
– Pseudo código em Ada
– region
v
v é a variável compartilhada
do
C
end region;
O subcomando C é a seção crítica relativa à
variável v, que só pode ser acessada dentro de uma
seção crítica condicional – ou seja – o acesso
exclusivo a ela fica assegurado automaticamente
7-55
Abstrações para controle da concorrência (3)
 Regiões críticas condicionais (2)
• Dentro da região crítica condicional, o await command
await
E;
bloqueia o processo até que a condição E (que acessa a variável v) resulte
em true
– Enquanto espera bloqueado, o processo libera o uso exclusivo da
variável
compartilhada,
mas
quando
retoma
a
execução,
exclusividade é assegurada
7-56
a
Abstrações para controle da concorrência (4)
 Regiões críticas condicionais (3)
• Exemplo: implementação de buffer limitado
– type Message_Buffer is
shared record
size : Integer range 0 .. capacity;
front, rear : Integer range 1 .. capacity;
items : array (1 .. capacity) of Message;
end record;
procedure send_message (item : in Message;
procedure receive_message (item : out Message;
buffer : in out Message_Buffer) is
begin
buffer : in out Message_Buffer) is
begin
region buffer do
region buffer do
await buffer.size < capacity;
await buffer.size > 0;
buffer.size := buffer.size + 1;
buffer.size := buffer.size - 1;
buffer.rear := buffer.rear mod
item := buffer.items(buffer.front);
capacity + 1;
buffer.front := buffer.front mod
buffer.items(buffer.rear) := item;
end region;
end send_message;
capacity + 1;
end region;
end receive_message;
7-57
Abstrações para controle da concorrência (5)
 Regiões críticas condicionais (4)
• Regiões críticas condicionais descrevem as interações entre os processos
com bastante clareza e simplicidade
– Exclusão mútua e comunicação sem variáveis auxiliares
– Exclusão mútua garantida em tempo de compilação
– Transmissão de condições é automática e implícita
– Recepção é simples e comuta com a transmissão
• Aumentam a clareza dos programas concorrentes, embora o comando
await
E seja bastante custoso, já que é implementado em termos de um
loop que repetidamente testa E
7-58
Abstrações para controle da concorrência (6)
 Monitores (1)
• Um monitor é um tipo de pacote que combina encapsulação com exclusão
mútua e sincronização
– Pascal concorrente (Brinch Hansen, 1977) e Módula (Wirth, 1977)
influenciaram linguagens baseadas em Pascal, que passaram a usar
monitores para estruturar a concorrência
• Os monitores de Módula asseguram a exclusão mútua para as operações de
um tipo abstrato de dados
– Diferente das regiões críticas condicionais, os monitores não suportam
sinalização automática
– Um tipo signal predefinido é fornecido com as operações send e wait
7-59
Abstrações para controle da concorrência (7)
 Monitores (2)
– Cada variável signal declarada é na realidade uma fila de processos esperando
uma permissão para continuar a execução dentro do monitor
– A operação
wait
bloqueia um processo e coloca-o na fila de processos
correspondente da variável signal
– Enquanto fica esperando pelo
signal,
o processo libera o uso exclusivo do
monitor
– A operação
send
desbloqueia o processo na frente da fila de processos
esperando da variável signal correspondente
– Quando retoma a execução da operação, ganha o uso exclusivo do monitor
7-60
Abstrações para controle da concorrência (8)
 Monitores (3)
• Exemplo: implementação de buffer limitado em Módula
–
INTERFACE MODULE BufferMonitor;
DEFINE sendMessage, receiveMessage; (* public *)
TYPE MessageBuffer =
RECORD
size : 0.. capacity;
front, rear : 1 .. capacity;
items : ARRAY 1 .. capacity OF Message
END;
VAR buffer : MessageBuffer; nonfull, nonempty : signal;
PROCEDURE sendMessage (item : Message);
PROCEDURE receive Message(VAR item : Message);
BEGIN
BEGIN
IF buffer.size = capacity THEN
IF buffer.size = 0 THEN
wait(nonempty);
wait(nonfull);
buffer.size := buffer.size + 1;
buffer.size := buffer.size - 1;
buffer.rear := buffer.rear MOD
item := buffer.items[buffer.front];
capacity + 1;
buffer.front := buffer.front MOD
capacity + 1;
buffer.items[buffer.rear] := item;
send(nonempty)
END;
send(nonfull)
END;
7-61
Abstrações para controle da concorrência (9)
 Monitores (4)
• Como semáforos e eventos, o
signal
de monitores é associado a condições
apenas por uma convenção que deve ser respeitada na lógica do monitor
– Mais eficiente que
await,
embora menos simples e legível, exigindo mais
trabalho para o programador e mais oportunidades de erros
7-62
Abstrações para controle da
concorrência (10)
 Rendezvous – encontro – (1)
• Baseia-se na interação entre processos apenas através de comunicação
síncrona não bufferizada – o rendezvous
– Cada processo executa um comando indicando o desejo de se comunicar com o
outro
– Cada processo fica bloqueado até que o outro alcance o ponto de rendezvous
– Quando ambos estão prontos, uma mensagem é copiada de emissor para o
receptor, então, ambos são desbloqueados e continuam sua execução
independentemente
– Baseia-se
na
notação
CSP
(Communicating
Sequential
Processes),
desenvolvida por Hoare (1978)
7-63
Abstrações para controle da
concorrência (11)
 Rendezvous (2)
7-64