Comunicação entre Processos

Afluentes: Sistemas Operacionais, Sistemas Distribuídos e Mobile

Introdução

• Compartilhamento de recursos entre processos pode gerar situações indesejáveis.
• Mecanismos de sincronização: garantem a comunicação entre processos concorrentes e o acesso a recursos compartilhados.

Especificação de Concorrência em Programas

• Primeira notação para especificação da concorrência: FORK e JOIN
  • FORK: Inicia a execução de outro programa concorrentemente
  • JOIN: O programa chamador espera o outro programa terminar para continuar o processamento
• Implementação mais simples: PARBEGIN e PAREND
  • PARBEGIN: Inicia lista de programas que serão executados paralela e aleatoriamente.
  • PAREND: Especifica o ponto de sincronização.

Problemas de Compartilhamento de Recursos

Mecanismos de controle devem existir para evitar problemas. Exemplos:

• Atualização de arquivos compartilhados ao mesmo tempo.
• Cálculos com mesmas variáveis ao mesmo tempo.

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 para utilizar.
• Região crítica: parte do código onde é feito o acesso ao recurso compartilhado.
• Usualmente utiliza-se de um protocolo ao entrar em uma região crítica e ao sair dela.

Problemas de Sincronização

• Problemas introduzidos pela exclusão múltua.
• Velocidade de Execução dos Processos:
• Processos com diferenças de velocidade ou maior tempo de processamento.

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. Caso o sistema escolha o processo aleatoriamente quando o recurso é liberado, 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 se encontra pronto para ser utilizado pelos processos, o processo deve ser colocado no estado de espera, até a liberação do recurso.
• Problema de processo produtor/consumidor: exemplo, quando um processo tenta gravar num buffer e outro tenta ler. Um processo não poderia ler de um buffer cheio nem tentar ler de um buffer vazio.

Soluções de Hardware

Desabilitação de Interrupções

• Desabilitar interrupções externas ao entrar numa região critica e habilitar ao sair.
• Se o processo não habilitar as interrupções ao sair da região crítica, o sistema pode estar comprometido.

Instrução Test-and-set

• Instrução especial que permite ler uma variável, armazenar seu conteúdo em uma outra área e atribuir um novo valor a essa variável.
• Executa sem interrupção
• É uma instrução invisível.
• Dois processos não podem manipular uma variável compartilhada ao mesmo tempo (exclusão múltua).

Solução de Software

Fatores para a solução de problemas de sincronização:

• O número de processadores e o tempo de execução dos processos concorrentes devem ser irrelevantes;
• Um processo, fora de sua região crítica, não pode impedir que outros processos entrem em suas próprias regiões críticas;
• Um processo não pode permanecer indefinidamente esperando para entrar em sua região crítica.

Semáforos

• Solução mais geral e simples de ser implementada.
• Variável inteira, não negativa, que só pode ser manipulada por duas instruções: DOWN e UP.

Mutexes (mutual exclusion semaphores)

• Semáforos aplicados ao problema da exclusão múltua
• Na exclusão múltua, as instruções DOWN e UP funcionam como protocolos de entrada e saída. Valor > 0, recurso liberado, Valor = 0, processo impedido do acesso.
• Processo entra na região crítica executa DOWN, impedindo outros processos do acesso.
• Processo sai da região crítica executa UP, liberando o acesso para outros processos.
• Normalmente, UP e DOWN são System Calls.

Semáforos aplicados ao problema de sincronização condicional

• Em geral, se existe um processo que deve ser notificado sobre a ocorrência de um evento e um outro capaz de detectar sua ocorrência, pode-se utilizar um semáfaro associado ao evento esperado para sincronizar ambos os processos
• Semáforos contadores: úteis quando aplicados na alocação de recursos do mesmo tipo (pool).

Monitores

• Mecanismos de sincronização de alto nível que tentam tornar mais fácil o desenvolvimento e correção de programas concorrentes.
• Conjunto de procedimentos, variáveis e estrutura de dados definidos dentro de um módulo.
• Somente um processo pode estar executando um dos procedimentos do monitor em um determinado instante.
• 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 tipo fila) está impedindo a liberação para outros processo.
• SIGNAL: Liberação do recurso pelo processo que o alocou.

Troca de Mensagens

• Mecanismo de comunicação e sincronização entre processos.
• SEND: Envia uma mensagem a um processo receptor.

SEND (Receptor, Mensagem)

• RECEIVE: Recebe uma mensagem de um processo transmissor.

RECEIVE (Emissor, Mensagem)

• Não ocorre exclusão multua.
• Uma mensagem só pode ser lida apos Ter sido enviada.
• Pode ocorrer perda de mensagens
• ACK: (acknowledgement) enviada pelo processo receptor para informar o recebimento da mensagem. Se o emissor não receber um ACK em determinado tempo, reenvia a mensagem.
• Endereçamento direto: só permite a comunicação entre dois processos.
• Endereçamento indireto: utiliza uma área compartilhada (buffer conhecido como mailbox) onde as mensagens podem ser colocadas pelo emissor e retiradas pelo receptor

Comunicação síncrona (rendezvous)

• Um processo envia uma mensagem e fica esperando até que o receptor leia a mensagem.
• Um receptor tenta receber uma mensagem e fica esperando até que o processo transmissor grave alguma mensagem.
• Dispensa necessidade de buffers.
• A necessidade de espera reduz o grau de concorrência.

Comunicação assíncrona

• O transmissor não aguarda o recebimento da mensagem.
• O receptor não aguarda o envio de uma mensagem.
• Necessita de buffers.
• Maior paralelismo na execução dos processos em relação a síncrona.

Deadlock

• Um processo espera por um evento que nunca ocorrerá.
• Conseqüência, em geral, do compartilhamento de recursos do sistema entre vários processos de forma exclusiva.
• Espera circular: quando, por exemplo, um processo A, utilizando um recurso P, necessita de um recurso Q, alocado pelo processo B, para continuar o processamento e o processo B necessita do recurso P para continuar o processamento.
• Deadlocks ocorrem quando 4 condições são verdadeiras:

1. Exclusão mútua: Cada recurso só pode estar alocado a um único processo em um determinado instante.
2. Um processo, além dos recursos já alocados, pode estar esperando por outros recursos.
3. Não-preempsão: Um recurso não pode ser liberado de um processo só porque outros processos desejam o mesmo recurso.
4. Espera circular: Um processo pode Ter de esperar por um recurso alocado a outro processo e vice-versa.

Prevenção de Deadlock

Garantir que uma das quatros condições nunca se satisfaçam:

1a condição

• A ausência da exclusão múltua acaba com o problema.
• Pode causar sérios problemas de consistência.

2a condição

• Alocar todos os recursos necessários para a execução, antes de se executar, caso não disponíveis, fica em espera.
• Pode ocorrer starvation, pois seus recursos podem nunca estarem liberados todos ao mesmo tempo
• Dificuldade de se determinar o número de recursos que um processo deverá alocar antes de sua execução.
• Algum recurso pode demorar a ser liberado.

3a condição

• Evitada quando permitimos que um recurso seja retirado de um processo, no caso de outro processo necessitar do mesmo.
• Pode perder o processamento feito até o momento.
• Pode ocorrer starvation, quando o processo garante alguns recursos e o sistema os libera em seguida.

4a condição

• Forçar ao processo Ter apenas um recurso de cada vez, se precisar de outro recurso, deve liberar o primeiro.

Detecção do Deadlock

• Mecanismo que determina a existência de deadlock, permitindo identificar os recursos e processos envolvidos no sistema
• Existe uma estrutura de dados capaz de identificar cada recurso do sistema.
• Geralmente os algoritmos verificam a existência de espera circular, percorrendo toda a estrutura quando um processo solicita um recurso que não pode ser imediatamente garantindo.

Correção do Deadlock

• Eliminar um ou mais processos envolvidos no deadlock e desalocar os recursos já garantidos por eles, eliminando a espera circular.
• A escolha dos processos é normalmente feita aleatoriamente ou com base em prioridades.
• Pode gerar um elevado overhead ao sistema.
• Rollback:
  • Liberação de apenas uns recursos alocados até o ciclo de espera terminar.
  • O processo retorna seu processamento quando o recurso é devolvido.
  • Difícil de ser implementado devido ser bastante dependente da aplicação.

Lista de Exercícios

Formulário

1. O que são mecanismos de sincronização?
2. Cite um problema que o compartilhamento de recursos pode acarretar em relação à processos concorrentes.
3. Qual a solução para os problemas de compartilhamento e como funciona?
4. Cite e explique os problemas de sincronização.
5. Em relação aos problemas de sincronização, cite e explique resumidamente quais as soluções de Hardwares para resolver esse problema.
6. Em relação aos problemas de sincronização, cite e explique resumidamente quais as soluções de Software para resolver esse problema.
7. O que é Deadlock e quais as condições para que ele aconteça?
8. Como detectar prevenir o Deadlock?
9. Como corrigir o Deadlock?