Concorrência
Paradigmas de Linguagem de Programação
Prof. Dr. Alysson F. Milanez
alysson.milanez@maisunifacisa.com.br
Semáforos
2
Semáforos
Um semáforo é um mecanismo simples que pode ser usado para fornecer sincronização de tarefas
3
Semáforos
Dijkstra projetou os semáforos em 1965
podem ser usados para sincronização de competição e de cooperação
4
Semáforos
Um semáforo é uma estrutura de dados que tem um inteiro e tem uma fila que armazena descritores de tarefas
Um descritor de tarefa é uma estrutura de dados que armazena todas as informações relevantes acerca do estado de execução de uma tarefa
5
Semáforos
Para fornecer acesso limitado a uma estrutura de dados, guardas são colocadas ao redor do código que acessa a estrutura
6
Semáforos
Uma guarda é um dispositivo linguístico que permite ao código guardado ser executado apenas quando uma condição específica é verdadeira
7
Semáforos
Uma guarda pode ser usada para permitir que apenas uma tarefa acesse uma estrutura de dados compartilhada em um dado momento
Um semáforo é uma implementação de uma guarda
8
Semáforos
Uma parte integral de um mecanismo de guarda é um procedimento para garantir que todas as execuções tentadas do código de guarda ocorram em algum momento do tempo
As duas operações fornecidas pelos semáforos são wait e release
9
Semáforos
Cooperação
10
Semáforos - cooperação
Um buffer compartilhado
O buffer deve gravar tanto o número de posições vazias quanto o de preenchidas
O componente de contagem de uma variável de semáforo pode ser usado para esse propósito
11
Semáforos - cooperação
Uma variável de semáforo – emptyspots – para armazenar o número de posições vazias em um buffer compartilhado, e outra – fullspots – para armazenar o número de posições preenchidas no buffer
12
Semáforos - cooperação
As filas desses semáforos armazenam os descritores de tarefas forçadas a esperar pelo acesso ao buffer
A fila emptyspots armazenará tarefas à espera por posições disponíveis no buffer; a fila fullspots armazenará tarefas que estão aguardando os valores serem colocados no buffer
13
Semáforos - cooperação
DEPOSIT - subprograma para entrada de dados
FETCH - subprograma de saída do buffer
14
Semáforos - cooperação
DEPOSIT precisa apenas verificar o semáforo emptyspots para ver se existe alguma posição vazia
Se existir ao menos uma, ele pode continuar com DEPOSIT, que deve incluir o decremento do contador de emptyspots
15
Semáforos - cooperação
Se o buffer estiver cheio, o chamador de DEPOSIT deve esperar na fila de emptyspots até que uma posição vaga seja disponibilizada
16
Semáforos - cooperação
Quando DEPOSIT tiver completado sua tarefa, o subprograma DEPOSIT incrementa o contador do semáforo fullspots para indicar que existe mais uma posição preenchida no buffer
17
Semáforos - cooperação
FETCH tem a sequência oposta de DEPOSIT
Ele verifica o semáforo fullspot para ver se o buffer contém ao menos um item
18
Semáforos - cooperação
Se contém, um item é removido e o semáforo emptyspots tem seu contador incrementado em 1
Se o buffer estiver vazio, o processo chamador é colocado na fila de fullspots para esperar até que um item apareça
19
Semáforos - cooperação
Quando FETCH terminar, ele precisa incrementar o contador de emptyspots
20
Semáforos - cooperação
As operações em semáforos são feitas pelos subprogramas wait e release
A operação DEPOSIT descrita anteriormente é, na verdade, realizada em parte por chamadas a wait e a release
21
Semáforos - cooperação
wait é usado para testar o contador de uma variável semáforo
Se o valor for maior do que zero, o chamador pode continuar sua operação
22
Semáforos - cooperação
Nesse caso, o valor do contador da variável semáforo é decrementado para a existência agora de um item a menos daquilo que o semáforo estiver contando
Se o valor do contador é zero, o chamador deve ser colocado na fila de espera da variável semáforo, e deve ser dada ao processador alguma outra tarefa pronta
23
Semáforos - cooperação
release é usado por uma tarefa para permitir a alguma outra ter um item do contador da variável de semáforo especificado, independentemente do item que tal variável estiver contando
24
Semáforos - cooperação
Se a fila da variável semáforo especificada estiver vazia, ou seja, nenhuma tarefa está esperando, release incrementa seu contador
25
Semáforos - cooperação
Se uma ou mais tarefas estão esperando, release move uma delas da fila do semáforo para a fila de tarefas prontas
26
Semáforos - cooperação
wait(umSemaforo)
if contador de umSemaforo > 0 then
decrementar o contador de umSemaforo
else
colocar o chamador na fila de umSemaforo
tentar transferir o controle para alguma outra tarefa
(se a fila de tarefas prontas estiver vazia, ocorre um impasse)
end if
27
Semáforos - cooperação
release(umSemaforo)
if a fila de umSemaforo estiver vazia (nenhuma tarefa está esperando) then
incrementa o contador de umSemaforo
else
coloca a tarefa chamadora na fila de tarefas prontas
transfere o controle para uma tarefa da fila de umSemaforo
end
28
Semáforos - cooperação
semaphore fullspots, emptyspots;
fullspots.count = 0;
emptyspots.count = BUFLEN;
task producer;
loop
-- Produz VALUE --
wait(emptyspots); { espera por um espaço }
DEPOSIT(VALUE);
release(fullspots); { aumenta os espaços preenchidos }
end loop;
end producer;
29
Semáforos - cooperação
task consumer;
loop
wait(fullspots); { certifica-se de que não está vazio }
FETCH(VALUE);
release(emptyspots); { aumenta os espaços vazios }
-- Consome VALUE --
end loop;
end consumer;
30
Semáforos
Competição
31
Semáforos - competição
Um semáforo que requer apenas um contador de valor binário - semáforo binário
32
Semáforos - competição
O pseudocódigo a seguir ilustra o uso de semáforos para fornecer tanto sincronização de competição quanto de cooperação para um buffer compartilhado acessado concorrentemente
33
Semáforos - competição
O semáforo access é usado para garantir acesso mutuamente exclusivo ao buffer
34
Semáforos - competição
semaphore access, fullspots, emptyspots;
access.count = 1;
fullspots.count = 0;
emptyspots.count = BUFLEN;
35
Semáforos - competição
task producer;
loop
-- produzir VALUE --
wait(emptyspots); { esperar por um espaço }
wait(access); { esperar por acesso }
DEPOSIT(VALUE);
release(access); { liberar acesso }
release(fullspots); { aumentar espaços preenchidos }
end loop;
end producer;
36
Semáforos - competição
task consumer;
loop
wait(fullspots); { garantir que não esteja vazio }
wait(access); { esperar por acesso }
FETCH(VALUE);
release(access); { liberar acesso }
release(emptyspots); { aumentar espaços vagos }
-- consumir VALUE --
end loop;
end consumer;
37
Semáforos - competição
Um semáforo é um objeto de dados compartilhado, logo as operações nos semáforos também são suscetíveis a problema
É essencial que as operações de semáforo não possam ser interrompidas
38
Semáforos - competição
Muitos computadores têm instruções não interrompíveis projetadas especificamente para operações de semáforos
Se tais instruções não estão disponíveis, usar semáforos para fornecer sincronização de competição é um problema sério sem uma solução simples
39
Semáforos - Avaliação
"O semáforo é uma ferramenta de sincronização elegante para um programador ideal que nunca comete erros"
Per Brinch Hansen (1973)
40
Monitores
41
Monitores
Uma solução para alguns dos problemas dos semáforos em um ambiente concorrente é encapsular as estruturas de dados compartilhadas com suas operações e ocultar suas representações
42
Monitores
A primeira linguagem de programação a incorporar monitores foi o Pascal Concorrente.
Modula, CSP/k e Mesa também fornecem monitores
Dentre as linguagens contemporâneas, eles são suportados por Ada, Java e C#
43
Monitores - competição
Um dos recursos mais importantes dos monitores é que os dados compartilhados são residentes no monitor, em vez de em uma das unidades clientes
44
Monitores - competição
O programador não sincroniza o acesso mutuamente exclusivo aos dados compartilhados pelo uso de semáforos ou de outros mecanismos
45
Monitores - competição
Como os mecanismos de acesso fazem parte do monitor, a implementação de um pode ser feita de forma a garantir acesso sincronizado, permitindo apenas um acesso de cada vez
46
Monitores
Chamadas a procedimentos do monitor são implicitamente enfileiradas se ele estiver ocupado no momento da chamada
47
Monitores - cooperação
Apesar de o acesso mutuamente exclusivo aos dados compartilhados ser intrínseco com um monitor, a cooperação entre processos ainda é tarefa do programador
48
Monitores - cooperação
Em particular, o programador deve garantir que um buffer compartilhado não sofra de transbordamentos positivos ou negativos
49
Monitores - cooperação
Diferentes linguagens fornecem diferentes maneiras de programar a sincronização de cooperação, onde todas são relacionadas aos semáforos
50
Monitores - Avaliação
Monitores são uma forma melhor de fornecer sincronização de competição do que os semáforos
Semáforos e monitores são igualmente poderosos para expressar o controle de concorrência
51
Passagem de Mensagens
52
Passagem de Mensagens
A passagem de mensagens pode ser síncrona ou assíncrona
53
Passagem de Mensagens
O conceito básico da passagem síncrona de mensagens é que as tarefas estão normalmente ocupadas e não podem ser interrompidas por outras unidades
54
Passagem de Mensagens
Suponha que as tarefas A e B estejam em execução, e que A deseja enviar uma mensagem para B. Se B estiver ocupada, não é desejável permitir que outra tarefa a interrompa, impedindo o processamento atual de B
55
Passagem de Mensagens
Desse modo, fornecemos um mecanismo linguístico capaz de permitir a uma tarefa especificar para outras quando ela está pronta para receber mensagens
56
Passagem de Mensagens
Uma tarefa pode ser projetada de forma a suspender sua execução em um determinado momento, seja porque está desocupada ou porque precisa de informações de outra unidade antes de poder continuar
57
Passagem de Mensagens
Em alguns casos, não existe nada a fazer, além de esperar
Entretanto, se uma tarefa A está esperando por uma mensagem no momento em que B a envia, a mensagem pode ser transmitida
58
Passagem de Mensagens
Essa transmissão real da mensagem é chamada de um rendezvous
Note que um rendezvous pode ocorrer apenas se tanto o remetente quanto o destinatário quiserem que ele aconteça
59
Passagem de Mensagens
Durante um rendezvous, a informação da mensagem pode ser transmitida em qualquer das direções (ou em ambas)
60
Referências
61
Referências
SEBESTA, R. Conceitos de Linguagem de Programação.
Capítulo 13
TUCKER, A. B.; NOONAN, R. E. Linguagens de Programação: Princípios e Paradigmas.
Capítulo 17
GOETZ, B. Java Concurrency in Practice.
62
Concorrência
Paradigmas de Linguagem de Programação
Prof. Dr. Alysson F. Milanez
alysson.milanez@maisunifacisa.com.br