Sistemas Operacionais

Sistemas Operacionais
Capítulo 7
Comunicação entre Processo

7.1 – 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

7.2 – 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.

7.3 – 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.

7.4 – 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.

7.5 – 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.

7.6 – 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
Assim, dois processos não podem manipular uma variável compartilhada ao mesmo tempo (exclusão múltua).

7.7 – 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.

7.7.1 – Semáfaros

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áfaros 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áfaros 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 acossiado ao evento esperado para sincronizar ambos os processos
Semáfaros contadores: úteis quando aplicados na alocação de recursos do mesmo tipo (pool).

7.7.2 – 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.

7.7.3 – 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.

7.8 – 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:

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

7.8.1 – 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.

7.8.2 – 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.

7.8.3 – 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.

[voltar]