Concorrência_Assíncorna_continuação

Prévia do material em texto

EXECUÇÃO ASSÍNCRONA CONCORRENTE Eng. Eduardo Juliano Alberti
SEÇÕES CRÍTICAS
Vimos que quando temos threads concorrentes, ao modificarem dados, podem
ocorrer erros devido aos diversos acessos e a preempção de sua execução.
Para evitar a ocorrência desses problemas, faz-se o que chamamos de exclusão 
mútua, onde limitamos o acesso a uma variável compartilhada. Dessa forma, sua 
modificação só será permitida após o termino de uma operação em andamento.
2
SEÇÕES CRÍTICAS
Porém se for observada a situação na qual threads concorrentes apenas leem o
valor de uma variável compartilhada, acaba-se por notar que os threads podem
prosseguir sem conflitos.
Portanto, existem duas situações para threads concorrentes, situações de conflito e
situações não conflitantes.
3
SEÇÕES CRÍTICAS
As situações nas quais existem conflitos entre threads concorrentes são chamadas de
seções críticas.
As seções críticas protegem e asseguram a execução de operações de um thread.
Quando um thread está em uma região crítica, outro thread que deseja utilizá-la
deverá esperar até que a primeira libere a seção, enquanto o thread que não
necessita da seção crítica poderá executar livremente.
4
SEÇÕES CRÍTICAS
Observamos o uso de exclusão mútua para resolução deste problema, porém o mau
uso da exclusão mútua pode causar ainda mais problemas.
Qual seria este problema?
5
SEÇÕES CRÍTICAS
O sistema que impõe a exclusão mútua deve controlar o acesso e a execução em
seções críticas.
Imagine uma situação na qual um thread solicite acesso a uma área do disco que
representa o local de acesso aos arquivos do usuário. O thread utiliza
indefinidamente esta área. Isso impede o acesso de outros threads e desta forma, o
recurso pode ficar indisponível por muito tempo.
6
SEÇÕES CRÍTICAS
O thread, portanto, deve ao, voluntária ou involuntariamente, deixar a região crítica,
limpar a seção e liberar a exclusão mútua.
O sistema Operacional deve ainda supervisionar para que as ações sejam
executadas, evitando alocação indefinida de recursos.
7
PRIMITIVAS DE EXCLUSÃO MÚTUA
Chama-se de primitivas de exclusão mútua as operações fundamentais inerentes à
exclusão mútua.
Quando a máquina não possui primitivas de exclusão mútua via hardware, estas
devem ser implementadas via software.
8
PRIMITIVAS DE EXCLUSÃO MÚTUA
Algumas propriedades devem ser observadas ao desenvolver primitivas de exclusão
mútua via software:
1. Instruções em linguagem de máquina são indivisíveis, ao serem iniciadas não
podem ser interrompidas.
2. Não deve-se supor velocidades dos threads. Um thread pode executar de modo
inconstante e imprevisível. Um thread deve supor sua interrupção a qualquer
momento.
3. Threads fora da região crítica não podem evitar que outros entrem em sua seção
crítica.
4. Um thread não deve impedir de modo indefinido a entrada de outros threads em
sua região crítica.
9
PRIMITIVAS DE EXCLUSÃO MÚTUA
Algumas propriedades devem ser observadas ao desenvolver primitivas de exclusão
mútua via software:
1. Instruções em linguagem de máquina são indivisíveis, ao serem iniciadas não
podem ser interrompidas.
2. Não deve-se supor velocidades dos threads. Um thread pode executar de modo
inconstante e imprevisível. Um thread deve supor sua interrupção a qualquer
momento.
3. Threads fora da região crítica não podem evitar que outros entrem em sua seção
crítica.
4. Um thread não deve impedir de modo indefinido a entrada de outros threads em
sua região crítica.
10
O ALGORITMO DE DEKKER
O algoritmo de Dekker possui diversas versões, que aperfeiçoaram algumas
condições de versões anteriores.
Neste algoritmo Dekker proprõe que dois threads mantenham uma variável de
controle para a realização da exclusão mútua, sendo que cada um dos threads só
irá executar quando a variável assumir seu número de execução.
11
O ALGORITMO DE DEKKER
12
O ALGORITMO DE DEKKER
Nesta implementação, porém, enquanto não puder acessar sua seção crítica um
thread irá repetidamente consultar a variável threadNumber, o que significa a
realização de um trabalho não essencial (espera ociosa).
Com a espera ociosa a implementação em uniprocessadores é totalmente ineficaz,
além de causar a sobrecarga do processador, e a perda de desempenho.
Outro problema desta implementação é que a exclusão mútua causa o problema de
sincronização de intertravamento, o que significa que os threads mais rápidos serão
obrigados a trabalhar na velocidade dos mais lentos caso estes entrem
constantemente em sua região crítica.
13
O ALGORITMO DE DEKKER
O mais preocupante é que esta técnica de espera ociosa fere um princípio de
implementação de primitivas de exclusão mútua.
Lembra-se qual?
14
O ALGORITMO DE DEKKER
Uma nova implementação prevê então a introdução de uma nova variável para
evitar o sincronismo por intertravamento.
Nessa segunda implementação portanto, cada thread poderá executar livremente e
entrar em sua região crítica tantas vezes for necessário enquanto não houver uso da
mesma.
15
O ALGORITMO DE DEKKER
16
O ALGORITMO DE DEKKER
O problema é que nesta situação não há garantia de exclusão mútua, considere a
situação na qual:
T1 e T2 estão falsos
Ao entrar na seção crítica, T1 sofre preempção antes de alterar o estado de T2
T2 entra na seção crítica e sofre preempção, T1 volta a execução e entra na seção
crítica.
Nesta situação ambos threads terão acessado simultaneamente a seção crítica.
17
O ALGORITMO DE DEKKER
Na resolução anterior, o problema da exclusão mútua não garantida surgiu porque a
verificação do while não previu a preempção, ou seja, um erro de primitiva.
Para resolver esse problema, pode-se verificar a vontade de acessar uma seção
crítica.
18
O ALGORITMO DE DEKKER
19
O ALGORITMO DE DEKKER
Porém, nesta situação, a preempção dos threads antes da verificação dos whiles,
poderia incorrer em um deadlock entre os processos. Neste caso, os dois threads
esperariam indefinidamente por um recurso que nunca seria liberado.
20
O ALGORITMO DE DEKKER
Uma implementação adequada do algoritmo de Dekker prevê a utilização de flags
para sinalização do desejo de entrar na seção crítica, incorpora ainda um condição
de favorecimento para solucionar problemas de disputas por região crítica em
acessos simultâneos.
21
22
O ALGORITMO DE LAMPORT
Todas as implementações anteriores resolviam problemas de acesso a regiões críticas
tendo por base a concorrência entre apenas dois threads.
Porém em prática, podem existir n threads solicitando acesso a um recurso ou seção
crítica.
23
O ALGORITMO DE LAMPORT
O algoritmo de Lamport propõe o uso de uma fila de atendimento para solicitações
a requisições de acesso a regiões críticas. Assim como em uma padaria.
Porém em uma padaria os clientes são atendidos de forma individual e recebem uma
senha única, o que pode não acontecer no algoritmo de Lamport.
24
O ALGORITMO DE LAMPORT
25
SEMÁFOROS
26
Os semáforos são formas de implementação de um sistema de exclusão mútua.
Os semáforos possuem uma variável protegida que pode ser alterada por suas 
operações
 P – proberen – testar
 V – Verhogen – Incrementar
Um thread chama a função P (Wait ou Esperar) quando quer entrar na seção crítica, 
e quando quer sair da seção crítica, chama a função V (Sign ou Sinalizar).
SEMÁFOROS
27
A variável protegida pelo semáforo guarda referências para os threads que 
desejam entrar na seção crítica.
As operações P e V são apenas abstrações para algoritmos mais inteligentes que 
causam o controle das operações.
SEMÁFOROS
28
SEMÁFOROS
29
A implementação de semáforos em java é relativamente simples:
A instância do semáforo recebe o númerode permissões que serão distribuídas:
 Semaphore s = new Semaphore(3);
O semáforo irá controlar uma seção crítica, que para ser acessada deve ser 
requisitada e devolvida.
 S.acquire();
 S.release();