INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES E SISTEMAS OPERACIONAIS VIVIANE LUCY Sistemas Operacionais Sincronismo e Comunicação entre processos WebDesign

INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES E SISTEMAS OPERACIONAIS

VIVIANE LUCY

Sistemas OperacionaisSincronismo e Comunicação

entre processos

WebDesign Redes de Computadores

Aula 12


VIVIANE LUCY

Semáforos• Apesar dos algoritmos apresentados até então

resolverem as questões de sincronização condicional e exclusão mútua, o problema da espera ocupada se faz presente.

• Espera Ocupada ocorre quando os processos que estão esperando a liberação de uma região crítica continuam ocupando o processador, mesmo estando num while que não faz nada.


VIVIANE LUCY

Semáforos• O semáforo é um mecanismo de sincronização que

permite implementar, de forma simples, a exclusão mútua e a sincronização condicional entre processos.

• Um semáforo é uma variável inteira, não negativa, que só pode ser manipulada por duas instruções:

• UP e DOWN


VIVIANE LUCY

Semáforos• A instrução UP incrementa uma unidade ao valor do

semáforo.

• A instrução DOWN decrementa uma unidade ao valor do semáforo.

• Se um semáforo tiver valor 0 e uma instrução DOWN for executada no mesmo, o processo entra em estado de espera.


VIVIANE LUCY

Semáforos• Os semáforos podem ser classificados como:

• Binários (também chamados de mutex) – podem receber valores 0 ou 1.

• Contadores – Podem assumir qualquer valor inteiro positivo, além do 0.


VIVIANE LUCY

Exclusão mútua com semáforos

• A exclusão mútua pode ser implementada através de um semáforo binário associado a um recurso compartilhado.

• As instruções UP e DOWN funcionam como protocolos de entrada e saída.

• Sempre que um processo deseja entrar na região crítica, um processo executa uma instrução DOWN.


VIVIANE LUCY


• Se o semáforo for igual a 1, esse valor é decrementado e o processo que solicitou a operação pode executar as instruções da região crítica.

• Se o semáforo for igual a 0, o processo fica impedido do acesso permanecendo em estado de espera. E consequentemente, não ocupando o processador.


VIVIANE LUCY


• O processo que está acessando o recurso, ao sair da região crítica, executa uma instrução UP, incrementando o valor do semáforo e liberando o acesso ao recurso.

• Se um ou mais processos estiverem esperando pela liberação do recurso, o sistema selecionará um processo na fila de espera, associada ao recurso e alterará o seu estado para pronto.


VIVIANE LUCY

Exclusão mútua com semáforosProcesso deseja entrar

na região crítica

Processo acessa aregião crítica

Fila de espera de processos

DOWN (S

= 1) DOWN (S = 0)

UP (S) – processo sai da região crítica

Libera processo da fila de espera


VIVIANE LUCY

void process_A(void){while(1){ DOWN(s); Regiao_Critica_A; UP(s); }}void process_B(void){while(1){ DOWN(s); Regiao_Critica_B; UP(s); }}void main(void){semaforo s = 1; while(1){ process_A(); process_B();}}

Processo Instrução S Espera

A While 1 *

B While 1 *

A DOWN(S) 0 *

A Regiao_Critica 0 *

B DOWN(S) 0 Processo_B

A UP(S) 1 *

B DOWN(S) 0 *

B Regiao_Critica_B

0 *


VIVIANE LUCY

Sincronização• Windows XP

• Em um sistema monoprocessado quando o kernel do Windows XP acessa um recurso global, ele mascara as interrupções para todos os tratadores de interruções que podem acessar o recurso.

• Em um sistema multiprocessado o Windows XP protege o acesso aos recursos globais usando semáforos.


VIVIANE LUCY

Sincronização• Linux

• No modo kernel, para regiões críticas consistindo em seções curtas de código, o Linux desativa interrupções.

• Para regiões críticas mais longas o Linux utiliza semáforos para bloquear dados do kernel.

• Em sistemas multiprocessados o Linux também utiliza semáforos como mecanismo de proteção.


VIVIANE LUCY

Troca de mensagens• Troca de mensagens é um mecanismo de

comunicação e sincronização entre processos.

• O sistema operacional possui um subsistema de mensagem que suporta esse mecanismo sem que haja necessidade do uso de variáveis compartilhadas.


VIVIANE LUCY

Troca de mensagens• Os processos cooperativos podem fazer uso de um

buffer para trocar mensagens através de duas rotinas:

• SEND ( receptor, mensagem)

• Permite o envio de uma mensagem para o processo receptor.

• RECEIVE ( transmissor, mensagem)

• Possibilita o recebimento de uma mensagem enviada por um transmissor.


VIVIANE LUCY

Troca de mensagens• A troca de mensagens pode ser implementada de

duas maneiras distintas:

• Comunicação Direta – ao enviar ou receber uma mensagem, o processo especifica explicitamente o nome do processo receptor ou transmissor.

• Comunicação Indireta – Utiliza uma área compartilhada onde as mensagens podem ser colocadas pelo processo transmissor e retiradas pelo processo receptor.


VIVIANE LUCY

Troca de mensagens• Na comunicação indireta, o buffer de comunicação é

conhecido como mailbox ou port.

• As características do buffer (mailbox ou port), como identificação e capacidade de armazenamento, são definidos no momento de sua criação.

• Podemos ter vários processos associados ao mailbox, os parâmetros dos procedimentos SEND e RECEIVE passam a ser os nomes de mailbox, e não nome de processos.


VIVIANE LUCY

Troca de mensagens• Processos que trocam mensagens devem ter suas

execuções sincronizadas em função do fluxo de mensagem.

• O primeiro esquema de sincronização é garantir:

• que um processo, ao enviar uma mensagem, permaneça esperando até que o processo receptor a leia.

• Um processo ao tentar receber uma mensagem ainda não enviada, deve permanecer aguardando até que o processo transmissor faça o envio.


VIVIANE LUCY

Troca de mensagens• O problema desta implementação é que a execução

dos processos fica limitada ao tempo de processamento no tratamento das mensagens.

• Um variação desse esquema é permitir que o processo transmissor não fique bloqueado aguardando a leitura da mensagem pelo receptor.

• Um terceiro esquema implementa uma forma assíncrona de comunicação, onde nem o transmissor nem o receptor permaneçam aguardando o envio e o recebimento de mensagens.


VIVIANE LUCY

Troca de mensagens• No terceiro esquema de comunicação, deve haver

outros mecanismos de sincronização que permitam que o processo identifique se uma mensagem já foi enviada ou recebida.

• Esse mecanismo aumenta a eficiência das aplicações concorrentes.


VIVIANE LUCY

Deadlock• Deadlock é uma situação em que o processo

aguarda por um recurso que nunca estará disponível ou um evento que não ocorrerá.

• Essa situação é conseqüência do compartilhamento de recursos (arquivos, registros, dispositivos) entre processos concorrentes em que a exclusão mútua é exigida.


VIVIANE LUCY

Deadlock

Recurso 2 Recurso 1

Processo A

Processo Asolicita o Recurso 2

Recurso 1alocado aoProcesso A

Processo Bsolicita o Recurso 1Recurso 2

alocado aoProcesso B Processo B


VIVIANE LUCY

Deadlock• A figura anterior ilustra o problema do deadlock entre

os processos A e B, quando utilizam os recursos 1 e 2.

• Inicialmente o processo A tem acesso exclusivo ao recurso 1. E o processo B tem acesso ao recurso 2.

• Durante o processamento, o processo A necessita do recurso 2 para prosseguir. Como o recurso 2 está alocado ao processo B, o processo A ficará aguardando o recurso ser liberado.


VIVIANE LUCY

Deadlock• Em seguida, o processo B necessita utilizar R1, e

ficará aguardando até que o processo A libere o recurso.

• Como cada processo está esperando que o outro libere o recurso alocado, é estabelecida uma condição conhecida como espera circular.


VIVIANE LUCY

Deadlock• Para que ocorra a situação de deadlock, quatro

condições são necessárias simultaneamente:

• 1. Exclusão mútua – cada recurso só pode estar alocado a um único processo em determinado instante.

• 2. Espera por recurso – um processo, além dos recursos alocados, pode estar esperando por outros recursos.


VIVIANE LUCY

Deadlock• 3. Não-preempção – um recurso não deve ser

liberado por 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.


VIVIANE LUCY

Métodos para tratamento de deadlock

• Podemos lidar com o problema do deadlock de três maneiras:

• Podemos usar um protocolo para prevenir ou evitar deadlocks, garantindo que o sistema nunca entrará em deadlock.

• Podemos permitir que o sistema entre em deadlock, detectá-lo e recuperá-lo.

• Podemos ignorar o problema e fingir que os deadlocks nunca ocorrem no sistema.


VIVIANE LUCY

Prevenção do Deadlock• Para prevenir a ocorrência de deadlocks, devemos

garantir que uma das quatro condições apresentadas nunca se satisfaça.

• A ausência da primeira condição (exclusão mútua) acaba com o problema do deadlock, pois nenhum processo precisará esperar para ter acesso a um recurso

• Para evitar a segunda condição (espera por recurso) – processos que já possuem recursos garantidos não devem requisitar outros recursos.


VIVIANE LUCY

Prevenção do Deadlock• Uma maneira de implementar esse mecanismo de

prevenção é que, antes do início da execução um processo deve pré-alocar todos os recursos necessários.

• Todos os recursos necessários à execução do processo devem estar disponíveis para o início da execução, caso contrário nenhum recurso será alocado e o processo permanecerá aguardando.


VIVIANE LUCY

Prevenção do Deadlock• Esse mecanismo produz desperdício de recursos, pois

um recurso pode estar alocado por um grande período de tempo, sendo utilizado apenas por um breve momento.

• A terceira condição (não–preempção) – pode ser evitada quando é permitido que o recurso seja retirado de um processo no caso de outro processo necessitar do mesmo recurso.


VIVIANE LUCY

Prevenção do Deadlock• A liberação de recursos já disponíveis a um processo

pode causar sérios problemas, podendo impedir a continuidade da execução do processo.

• A última maneira de evitar o deadlock é exluir a possibilidade da quarta condição (espera - circular) – uma forma de implementar esse mecanismo é forçar o processo a ter apenas um recurso por vez.

• Caso o processo necessite de outro recurso, o recurso já alocado deve ser liberado. Esta condição restringiria muito o grau de compartilhamento e o processamento do programa.


VIVIANE LUCY

Detecção correção de Deadlock• A detecção do deadlock é o mecanismo que determina

a existência da situação de deadlock, permitindo identificar os recursos e processos envolvidos no problema.

• Para detectar deadlocks, os sistemas operacionais devem manter estruturas de dados capazes de identificar cada recurso do sistema, o processo que o está alocando e os processo que estão à espera da liberação do recurso.


VIVIANE LUCY

Detecção e correção de Deadlock• Toda vez que o recurso é alocado ou liberado, a

estrutura de dados é atualizada.

• Os algoritmos que implementam esses mecanismos de detecção de deadlock verificam a existência de espera circular, percorrendo toda a estrutura sempre que um processo solicita o recurso e ele não pode ser imediatamente garantido.


VIVIANE LUCY

Detecção e correção de Deadlock• Após identificar o deadlock o sistema operacional

deverá de alguma forma corrigir o problema.

• O S.O. pode eliminar um ou mais processos envolvidos no deadlock.

• O S.O. pode também suspender um processo, liberar o recurso e, após a resolver o problema retornar a execução do processo.

Documents

INTRODUÇÃO À ORGANIZAÇÃO DE COMPUTADORES E SISTEMAS OPERACIONAIS VIVIANE LUCY Sistemas Operacionais Sincronismo e Comunicação entre processos WebDesign