Faculdade de Ciências e Tecnologia Mater Christi
Sistemas de informação
Exclusão mútua
Bruna Rafaella da Costa Moura
Silvana dos Santos Lima
Introdução
Problema
Seções críticas
Exclusão mútua
Algoritmos centralizados
Algoritmos distribuídos
Algoritmos anel
Conclusão
Introdução
 Iremos discutir o problema de garantir
exclusividade de execução para um processo,
em um sistema de processos concorrentes.
Assim como os sistemas centralizados, os
sistemas distribuídos enfrentam o problema de
gerenciar recursos compartilhados sem
comprometer a sua consistência.
Problema
 As instruções envolvidas no acesso a recursos globais
compartilhados são intercaladas pelo escalonador fora
do controle do programador.
 Recursos que não podem ser usados simultaneamente
por diversos processos.
Seção crítica
 Trecho de código de um programa onde as instruções
não podem ser intercaladas com a de outro programa,
onde os dados compartilhados são acessados.
 É o trecho de um programa que deve ser executado
sobre exclusão mútua.
Estrutura típica de um processo
Repeat
entrada da seção crítica;
seção crítica;
saída da seção crítica;
resto do processo;
Until false;
Exclusão mútua
 É uma técnica usada em programação concorrente
para evitar que dois processos ou threads tenham
acesso simultaneamente a um recurso compartilhado,
acesso esse, denominado por seção crítica.
Um algoritmo que implementa exclusão
mútua deve satisfazer os seguintes critérios:
 Exclusão mútua: dado um recurso compartilhado que
pode ser acessado por diversos processos ao mesmo
tempo, somente um processo pode acessar aquele
recurso a qualquer momento.
 Starvation: cada processo que requisita o recurso deve
recebê-lo em algum momento.
Algoritmo centralizado
 Um processo é escolhido para ser o coordenador;
 Cada processo tem que pedir autorização ao coordenador
para entrar na SC;
 Se não existe processo acessando a SC, então o
coordenador pode imediatamente garantir acesso ao
processo que fez a requisição;
 Se mais de um pede acesso à SC, então só um ganha
acesso;
 Após termino de uso, próximo informa coordenador;
 Coordenador então pode liberar SC para outro processo (se
existir)
Algoritmo centralizado
Desvantagens
 Baixa tolerância a falhas, se o coordenador falhar,
possivelmente, todo o sistema falhará.
 O coordenador pode se tornar um gargalo do sistema.
 Processo 1 solicita ao coordenador permissão para
entrar na RC.
 Processo 2 solicita ao coordenador permissão para
entrar na mesma RC. Permissão negada.
 Quando o processo 1 sai da RC, ele avisa ao
coordenador que libera o processo 2.
Algoritmo distribuído
 Se o processo deseja acessar SC, então ele envia uma mensagem
para todos os outros processos
 Mensagem contém:
Identificador do processo
nome da SC que ele deseja acessar
um timestamp único gerado pelo processo que enviou a
mensagem
 Ao receber mensagem processo:
Responde ao processo que enviou mensagem e garante acesso a SC se:
não quer acessar a SC
quer acessar a SC, mas seu timestamp é maior que o timestamp do
processo que enviou a mensagem
Não responde se:
processo que recebeu mensagem está executando na SC
processo está esperando para acessar SC e seu timestamp é menor que
o timestamp do processo que enviou a mensagem
Algoritmo distribuído
Desvantagens
 O único ponto de falha foi substituído por n pontos de
falha;
 O tráfego gerado na rede é muito maior;
 Em sistemas muito grandes todos os processos se tornam
possíveis gargalos;
Algoritmo de token
 Neste método, exclusão mútua é conseguida pelo uso de um token único
que circula entre os processos do sistema
 Um token é uma mensagem especial que dá ao detentor da mensagem
direito de acesso a SC
 Para que o algoritmo seja justo, os processos são organizados em um anel
 O token circula entre os processos no anel sempre na mesma direção
Algoritmo de token
Desvantagens
 Se o token se perder há a necessidade de se criar um novo
 É difícil detectar a perda to token;
 Se algum processo falhar, seu vizinho deve identificar a falha e
removê-lo do anel;
Conclusão