Exclusão Mútua (Mutex) e Sincronização de Processos

Exclusão Mútua (Mutex)

Exclusão mútua (mutex) é uma técnica usada em programação concorrente para evitar que dois processos ou threads tenham acesso simultâneo a um recurso compartilhado, acesso esse denominado região crítica.

Soluções de Hardware

• Desabilitação de interrupções:
  • Desabilitar interrupções externas ao entrar numa região crítica e habilitá-las ao sair.
  • Se o processo não habilitar as interrupções ao sair da região crítica, o sistema pode ficar comprometido.
• Instrução Test-and-Set:
  • Instrução especial que permite ler uma variável, armazenar seu conteúdo em outra área e atribuir um novo valor à variável.
  • Executa sem interrupção.
  • É uma instrução atômica (invisível ao programador).
  • Assim, dois processos não podem manipular uma variável compartilhada ao mesmo tempo (exclusão mútua).

Soluções de Software

Algoritmos

• Primeiro algoritmo
  Problema: Você define quem começa! Existe uma variável que controla a 'vez'.
• Segundo algoritmo
  Problema: Os dois podem ser executados simultaneamente; a variável é setada dentro do loop e nenhum dos processos pode progredir.
• Terceiro algoritmo
  Problema: Situação semelhante ao segundo; ambos podem entrar em execução continuamente (loop infinito).
• Quarto algoritmo
• Algoritmo de Dekker
• Algoritmo de Peterson
• Algoritmo para exclusão mútua entre N processos

Espera Ocupada (Busy Wait)

• Conhecido como busy wait.
• Faz o processador ficar em loop, consumindo tempo de CPU desnecessariamente.
• Uma solução é a implementação de monitores e semáforos para evitar espera ocupada.

Problemas de Compartilhamento de Recursos

• Devem existir mecanismos de controle para evitar problemas.
• Exemplos:
  • Atualização simultânea de arquivos compartilhados.
  • Cálculos concorrentes com as mesmas variáveis.

Solução para os Problemas de Compartilhamento

• Exclusão múltua (solução mais simples): impedir que dois ou mais processos acessem um mesmo recurso no mesmo instante; um deve esperar que o outro termine.
• Região crítica: parte do código onde é feito o acesso ao recurso compartilhado.
• Usa-se geralmente um protocolo ao entrar e ao sair de uma região crítica.

Problemas de Sincronização

• Problemas introduzidos pela exclusão múltua.
• Velocidade de execução dos processos:
  • Diferenças de velocidade ou tempos de processamento distintos entre processos podem causar efeitos indesejados.
• Starvation:
  • Situação em que um processo nunca consegue executar sua região crítica e acessar o recurso compartilhado.
  • Ocorre quando dois ou mais processos esperam por um mesmo recurso alocado; se o sistema escolher aleatoriamente o processo ao liberar o recurso, um processo pode nunca ser escolhido.
  • Quando um processo tem baixa prioridade também pode nunca ser escolhido.
  • Filas FIFO eliminam esse problema.
• Sincronização condicional:
  • Quando um recurso não está pronto para uso, o processo deve ser colocado em espera até a liberação do recurso.
  • Exemplo produtor/consumidor: um processo tenta gravar num buffer enquanto outro tenta ler; um não deve ler de um buffer vazio nem escrever em um buffer cheio.

Semáforos

• Solução geral e simples de implementar.
• Variável inteira, não negativa, que só pode ser manipulada por duas operações: DOWN e UP.
• Mutexes (mutual exclusion semaphores):
  • Semáforos aplicados ao problema da exclusão múltua.
  • Nas exclusões múltiplas, as operações DOWN e UP funcionam como protocolos de entrada e saída: valor > 0 — recurso liberado; valor = 0 — acesso impedido.
  • O processo entra na região crítica executando DOWN, impedindo outros do acesso.
  • Ao sair da região crítica, o processo executa UP, liberando o acesso para outros processos.
  • Normalmente, UP e DOWN são chamadas de sistema (system calls).
• Semáforos para sincronização condicional:
  • Quando um processo deve ser notificado sobre um evento e outro pode detectar sua ocorrência, pode-se utilizar um semáforo associado ao evento para sincronizá-los.
  • Semáforos contadores: úteis na alocação de recursos do mesmo tipo (pools).

Monitores

• Mecanismos de sincronização de alto nível que facilitam o desenvolvimento e a correção de programas concorrentes.
• Conjunto de procedimentos, variáveis e estruturas de dados definidos dentro de um módulo.
• Somente um processo pode executar um dos procedimentos do monitor em um determinado instante.
• A implementação da exclusão mútua nos monitores é realizada pelo compilador.
• WAIT — faz um processo entrar em estado de espera quando uma variável de condição (estrutura de dados do tipo fila) está impedindo a liberação para outros processos.