Concorrência_Assíncrona

Prévia do material em texto

EXECUÇÃO ASSÍNCRONA Sistemas Operacionais
OBJETIVOS
Programação concorrente - conceitos
Desafios de sincronizar processos e threads concorrentes
Seções críticas e a necessidade de exclusão mútua
Implementar primivitas de exclusão mútua em software
Primitivas de exclusão mútua em hardware
Utilização e implementação de semáforos
2
PROGRAMAÇÃO CONCORRENTE
Se exite mais de uma thread em um sistema ao mesmo tempo, diz-se que as threads 
são concorrentes
Programação concorrente é o paradigma para a construção de programas para a 
execução concorrente (simultânea) de várias tarefas computacionais interativas.
Estes programas podem ser implementadas separadamente ou como um conjunto de 
processos (threads) criadas por um único programa. 
3
PROGRAMAÇÃO CONCORRENTE
Essas tarefas podem ser executadas por um único processador, vários processadores
em um único equipamento ou processadores distibuídos por uma rede. 
A interação e a comunicação correta entre as diferentes tarefas, além da 
coordenação do acesso concorrente aos recursos computacionais são as principais
questões discutidas durante o desenvolvimento de sistemas concorrentes.
4
EXECUÇÃO SÍNCRONA E ASSÍNCRONA
Duas threads concorrentes podem executar independentemente uma da outra ou
cooperativamente.
Quando threads operam independentes uma da outra diz-se que estão executando
de maneira assíncrona.
Mesmo independentes ocasionalmente elas podem precisar se comunicar e se 
sincronizar para executar tarefas cooperativas.
5
EXCLUSÃO MÚTUA
Considere um servidor de correio eletrônico que processa emails para uma
organização.
Suponha que o sistema monitore continuamente o número total de emails enviados
desde o início do dia.
6
EXCLUSÃO MÚTUA
Suponha também que o recebimento de um email seja tratado por uma das várias
threads concorrentes.
Cada vez que uma destas threads receber um email, aumentará em 1 o valor de 
mailCount.
7
EXCLUSÃO MÚTUA
O que acontece se 2 threads tentarem incrementar mailCount simultaneamente, 
sabendo que esta é uma variável compartilhada? Suponha o seguinte código:
LOAD mailCount
ADD 1
STORE mailCount
LOAD copia o valor de mailCount da memória para um registrador
ADD adiciona a constante imediata 1 para o registrador
STORE copia o valor do registrador para a memória
8
EXCLUSÃO MÚTUA
Considere que o valor corrente de mailCount é 21687
A primeira thread executa LOAD e ADD deixando mailCount = 21688 (no 
registrador)
Então a primeira thread perde o processador devido a uma expiração no quantum, 
e o contexto é chaveado para uma segunda thread
9
EXCLUSÃO MÚTUA
A segunda executa todo o código deixando mailCount = 21688 (na memória)
Esta thread perde o processador e o contexto é chaveado para a primeira thread
10
EXCLUSÃO MÚTUA
A primeira thread executa a instrução STORE, mailCount = 21688
Devido ao acesso não controlado à variável mailCount o sistema perdeu um dos 
emails, mailCount deveria ser 21689
Como podemos fazer para evitar isso?
11
EXCLUSÃO MÚTUA
Um erro destes ocorrendo em uma aplicação de missão crítica, como controle de 
tráfego aéreo, pode custar vidas.
Para resolver o problema basta conceder a cada thread acesso exclusivo a 
mailCount.
12
EXCLUSÃO MÚTUA
Enquanto uma thread incrementa a variável compartilhada, todas as outras que
querem fazer o mesmo esperam.
Quando a thread que está executando terminar de acessar a variável compartilhada, 
o sistema permitirá que um dos processos à espera prossiga - serialização do acesso a 
variável compartilhada.
13
EXCLUSÃO MÚTUA
Assim threads não poderão acessar dados compartilhados simultaneamente.
Enquanto cada thread estiver atualizando a variável compartilhada, todas as outras
será impedidas, o que é denominado de exclusão mútua.
14
ESTUDO DE CASO - PRODUTOR/CONSUMIDOR
Em um relacionamento produtor/consumidor, a parte da aplicação referente ao
produtor gera dados e os armazena em um objeto compartilhado.
A parte do consumidor lê dados do objeto compartilhado e os consome.
Exemplos:
 Spooling de impressão: processador de texto passa os dados para um buffer, que são consumidos
pela impressora
 Uma aplicação que copia dados para CDs: coloca dados em um buffer de tamanho fixo que é 
esvaziado à medida que o drive de CD grava os dados no CD
15
ESTUDO DE CASO - PRODUTOR/CONSUMIDOR
Considere um relacionamento produtor/consumidor implementado em Java
O thread produtor gera dados e os coloca em um buffer que só pode reter um único
valor
O thread consumidor lê os dados do buffer
Se o produtor que estiver esperando para colocar os dados no buffer determinar
que os dados ainda não foram consumidos, ele deve chamar wait()
Assim o consumidor terá chance de ler os dados antes que outros dados sejam
escritos
16
ESTUDO DE CASO - PRODUTOR/CONSUMIDOR
Quando o consumidor acabar de ler os dados deve chamar notify() para permitir
que o produtor armazene o próximo valor
Notify() faz a transição de uma thread em espera para o estado pronto
17
ESTUDO DE CASO - PRODUTOR/CONSUMIDOR
Se o consumidor encontrar o buffer vazio, seja porque nada foi ainda escrito, ou
descobrir que os dados atuais já foram lidos, ele deve se colocar em espera - wait()
Quando o produtor colocar os próximos dados no buffer deve chamar notify() para 
o consumidor prosseguir
Notify() não tem efeito quando nenhuma das threads estiverem esperando
18
ESTUDO DE CASO - PRODUTOR/CONSUMIDOR
Para mostrar que erros por falta de sincronismo irão ocorrer, considere no exercício
que o consumidor acumula o total de todos os valores que lê. 
Total = 1 + 2 + 3 + 4 = 10
Lembre que o correto seria:
 O consumidor ler cada valor produzido apenas uma vez
 O consumidor não pode ler cada valor até que o produtor o tenha produzido
Se o programa for executado várias vezes o total raramente será 10
19
ESTUDO DE CASO – BUFFER CIRCULAR
No caso produtor/consumidor possuímos uma variável única para armazenamento de 
informações.
Um Buffer único pode produzir problemas de escrita e leitura entre duas threads 
devido ao fato de que uma deve aguardar pela outra – SEMPRE.
20
ESTUDO DE CASO – BUFFER CIRCULAR
Imagine que dois threads, mesmo em mesma velocidade, troquem informações. 
O thread consumidor deverá ler a informação para liberar espaço no buffer para 
que o thread Produtor possa inserir mais informações.
21
ESTUDO DE CASO – BUFFER CIRCULAR
No caso de um buffer circular, pode-se então aumentar a performance da troca de 
dados entre threads.
Imagine que ao contrário de um buffer único, tenha-se um buffer com um número 
limitado n de posições.
22
ESTUDO DE CASO – BUFFER CIRCULAR
O thread produtor poderá gravar n informações, independentemente da velocidade 
de leitura do thread consumidor.
O thread consumidor poderá ler a informação no buffer, independentemente da 
velocidade de gravação do produtor, e liberar o espaço no buffer.
23
ESTUDO DE CASO – BUFFER CIRCULAR
O Thread Produtor, ao observar espaços livres no buffer para a gravação, poderá 
continuar a gravação de dados.
O nome de buffer circular vem do fato de que, ao chegar ao final do buffer, tanto o 
thread produtor quando o consumidor, poderão pular novamente para a posição 
inicial do buffer e, caso livre, continuar a gravação, ou caso não lido, continuar a 
leitura.
24
ESTUDO DE CASO – BUFFER CIRCULAR
Qual o problema desta estrutura?
25
ESTUDO DE CASO – BUFFER CIRCULAR
Apesar de esta estrutura aumentar a velocidade da troca de informações quando
dois threads estão em mesma velocidade, ao envolver threads com velocidades muito
antagonistas esta característica cai por terra.
Imagine a situaçãona qual o thread consumidor realiza a leitura muito mais
rapidamente (de modo consistente) que o thread produtor gera informação.
26
ESTUDO DE CASO – BUFFER CIRCULAR
Nesta situação o thread de leitura deverá entrar em modo de espera até que haja
informação disponível, o que evitaria a leitura duplicada de informações.
Podemos imaginar ainda outra situação, na qual o thread consumidor opere em
velocidade muito mais lenta que o thread produtor (de forma consistente).
Nesta situação o thread consumidor não conseguiria abrir espaço no buffer para que
o thread grave informações, o que implicaria na espera do thread produtor.
27
ESTUDO DE CASO – BUFFER CIRCULAR
Em ambas situações onde os Threads possuem velocidades consistentemente muito
distintas a falta de sincronia acabará por invalidar a proposta de incremento da
velocidade ou performance.
Nestes casos, o gasto de memória é extremamente superior ao caso anterior
(produtor/consumidor) e a velocidade de processamento é a mesma.
28
ESTUDO DE CASO – BUFFER CIRCULAR
Um grande exemplo de aplicação do buffer circular é o sistema de Spooling para
impressão.
É claramente perceptível que a cabeça de impressão não consegue imprimir linhas
com a mesma velocidade da criação dessa informação.
29
ESTUDO DE CASO – BUFFER CIRCULAR
O Buffer Circular é normalmente armazenado em um dispositivo de armazenamento
primário, que possui velocidade de transmissão mais baixa.
O thread gerador de informação, gravador de informações no buffer, é chamado de
spooler e possui velocidade compatível com o sistema de armazenamento.
30
ESTUDO DE CASO – BUFFER CIRCULAR
O Thread que envia as informações para a impressora é chamada de Despooler, que
funciona em velocidade compatível com a impressora.
Como as velocidades dos Threads são incompatíveis seu uso seria inviável.
31
ESTUDO DE CASO – BUFFER CIRCULAR
Para viabilizar o uso do buffer circular mesmo em velocidades diferentes (não muito
distintas) é possível utilizar um buffer com tamanho apropriado para “tirar o atraso”
do sistema.
32