Sincronismo e
Comunicação entre
Processos
Sistemas Operacionais
1
Conteúdo
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Introdução;
Aplicações Concorrentes;
Problemas no Compartilhamento de Recursos;
Exclusão Mútua;
Soluções de Exclusão Mútua;
Sincronização Condicional;
Semáforos;
Monitores;
Troca de Mensagens;
Deadlock;
Prevenção de Deadlocks;
Detecção e Recuperação;
Gerenciamento Manual de Deadlocks;
Exercícios.
Sistemas Operacionais
2
Introdução
• Com os sistemas multiprogramáveis, é possível que partes
diferentes do código do programa possam ser executadas
concorrentemente. É denominada de Aplicação Concorrente e
baseia-se na execução cooperativa de múltiplos processos, que
trabalham em uma mesma tarefa na busca de um resultado comum.
• Estes processos compartilham recursos e isso pode ocasionar
situações indesejáveis, podendo comprometer a execução das
aplicações.
• Para evitar isso, os Processos Concorrentes possuem suas
execuções sincronizadas, com o objetivo de garantir o
processamento correto dos programas.
Sistemas Operacionais
3
Aplicações Concorrentes
• Em uma aplicação concorrente é necessário que processos
comuniquem-se
entre
si
através
de
variáveis
compartilhadas na Memória Principal ou troca de
mensagens.
• Nessa situação os processos devem ter sua execução
sincronizadas pelo SO.
• São os Mecanismos de Sincronização que garantem a
comunicação entre processos concorrentes e o acesso aos
recursos.
Sistemas Operacionais
4
Problemas no Compartilhamento
de Recursos
•
Problemas podem ocorrer devido a falha de Sincronização entre processos
concorrentes.
•
Exemplo: Situação onde dois processos (A e B) executam um comando de
atribuição.
O processo A soma 1 na variável X e o processo B diminui 1 da mesma
variável que está compartilhada. Inicialmente X=2.
•
Seria razoável que o resultado de X continuasse 2, porém isso nem sempre
será verdade.
•
Qualquer situação onde dois ou mais processos compartilham um mesmo
recurso, deve existir um mecanismo de controle para evitar problema
similar ao exemplo acima e esse controle é conhecido como RACE
CONDITIONS, ou Condições de Corrida.
Sistemas Operacionais
5
Exclusão Mútua
• Impede que dois ou mais processos acessem um mesmo
recurso simultaneamente. Exclusividade de acesso.
• Enquanto um processo estiver acessando um recurso, os demais
que queiram acessá-lo deverão esperar pelo término de sua
utilização.
• A parte do código do programa onde é feito o recurso de
compartilhamento é a REGIÃO CRÍTICA. Se for possível
evitar que dois processos entrem em Região Crítica ao
mesmo tempo, os problemas de compartilhamento estarão
evitados.
• Tanto para executar uma instruções na Região Crítica quanto
para sair dela, executa-se um protocolo que garante a
Exclusão Mútua da Região Crítica do programa.
Sistemas Operacionais
6
Exclusão Mútua
O acesso sincronizado, além da Exclusão Mútua evita duas
situações indesejáveis:
• STARVATION ou Espera Indefinida: É a situação em que um
processo nunca consegue executar sua Região Crítica,
acessando o recurso compartilhado. Quando o processo é
liberado, é o SO que seleciona qual processo fará parte do
recurso.
O critério de Escolha é baseado pela prioridade do processo. A
solução é a implementação de uma fila FIFO.
•
Um processo fora de sua Região Crítica impeça que outros
processos entrem em suas próprias Regiões Críticas.
Isto ocorre ao recurso estar livre, não está sendo utilizado, mas
ainda alocado a um processo, impedindo que os demais o
utilizem.
Sistemas Operacionais
7
Soluções para a Exclusão Mútua
Desabilitação de Interrupções:
Faz com que o processo desabilite todas as interrupções antes
de entrar na Região Crítica e as reabilite após deixar a Região
Crítica.
Instruções de Test – and – Set:
Permite ler uma variável, armazenar seu conteúdo em outra
área e atribuir um novo valor a mesma variável, através de uma
única instrução de máquina. Com isso torna-se impossível que
dois processos manipulem uma variável compartilhada ao mesmo
tempo.
Sistemas Operacionais
8
Sincronização Condicional
Situação onde o acesso ao recurso compartilhado exige a
Sincronização de processos vinculada a uma condição de
acesso.
Ex.: Comunicação entre dois processos através de operações de
leitura e gravação em buffer, onde os processos que geram
informações (processos produtores) são utilizados por outros
processos (consumidores).
Enquanto um processo grava os dados em um buffer, o outro lê os
dados concorrentemente. Esse problema de sincronização é
conhecido como Produtor / Consumidor ou Buffer Limitado
Sistemas Operacionais
9
Sincronização Condicional
Sincronização e comunicação entre processos
Sincronização
gr
Processo
gravador
av
aç
ão
i tu
le
ra
Processo
leitor
dado
Buffer
Sistemas Operacionais
10
Semáforo
É uma variável inteira, não negativa, que só pode ser manipulada
por duas instruções DOWN E UP, chamadas também de P
(Proberen, teste em holandês) e V (Verhogen, incremento em
holandês).
São instruções que não podem ser interrompidas e são classificadas
em:
Binários: Chamados de Mutexes (Mutual Exclusion Semaphores), só
podem assumir valores de O e 1.
Semáforos Contadores: Podem assumir qualquer valor inteiro
positivo além do O.
Sistemas Operacionais
11
Semáforo
Semáforo binário na exclusão mútua
Processo deseja entrar
na região crítica
W
0)
DO
N
=
(S
0)
O
D
N
W
>
(S
UP (S) - processo sai
da região crítica
Libera processo
da fila de espera
Processo acessa
a região crítica
Fila de espera
de processos
Sistemas Operacionais
12
Monitores
•
São implementados pelo compilador, possibilitando o
desenvolvimento de programas concorrentes com chances de
menos erros.
•
É formado por procedimentos e variáveis encapsulados
dentro de um módulo, implementando de forma automática a
Exclusão Mútua entre os procedimentos declarados.
•
Toda vez que algum processo faz uma chamada a um
procedimento, o Monitor verifica se já existe outro processo
executando algum procedimento no monitor. Caso exista, o
processo fica aguardando a sua vez em uma fila de entrada.
•
Encarrega-se de garantir
procedimentos definidos.
a
Exclusão
Sistemas Operacionais
Mútua
entre
os
13
Monitores
Estrutura do monitor
Declaração de
variáveis globais
Procedimentos
Monitor
Proc. 1
Proc. 2
Fila de entrada
Proc. n
Inicialização
de variáveis
Sistemas Operacionais
14
Troca de Mensagens
•
Esse tipo de mecanismo de comunicação e sincronização de
processos, o SO possui um subsistema de mensagens onde
não há necessidade do uso de variáveis compartilhadas. É
necessário que exista um buffer ou um link de uma rede de
computadores como canal de comunicação.
•
Os processos cooperativos que podem utilizar o buffer
através de duas rotinas: SEND e RECEIVE.
•
A rotina SEND envia uma mensagem para o processo receptor,
enquanto a RECEIVE recebe a mensagem enviada por um
processo transmissor.
•
Com isso exige que os processos envolvidos
comunicação tenham suas execuções sincronizadas.
Sistemas Operacionais
na
15
Troca de Mensagens
Transmissão de
mensagem
Processo
transmissor
Processo
receptor
Canal de comunicação
SEND
RECEIVE
Sistemas Operacionais
16
Troca de Mensagens
A Troca de Mensagens pode ser implementada de duas maneiras:
COMUNICAÇÃO DIRETA: Exige que tanto ao enviar ou receber
uma mensagem, enderece o nome do processo Receptor ou
Transmissor. Só permite a troca de mensagens entre dois
processos.
Processo A
Processo B
Sistemas Operacionais
17
Troca de Mensagens
COMUNICAÇÃO INDIRETA:
•
•
•
Utiliza uma área compartilhada onde as mensagens podem ser
colocadas pelo processo transmissor e retiradas pelo receptor. Esse
buffer é conhecido como MAILBOX e suas características, como
identificação e capacidade de armazenamento de mensagens, são
definidas no momento de criação.
Vários processos podem estar associados a MAILBOX.
Também possuem suas execuções sincronizadas em função do fluxo de
mensagens.
Processo A
Processo B
Mailbox
ou Port
Sistemas Operacionais
18
Deadlock
É a situação onde o processo aguarda por um recurso que
nunca estará disponível ou um evento que não ocorrerá. É
conseqüência do compartilhamento de recursos entre processos
onde a Exclusão Mútua é exigida.
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 um determinado instante;
2- Espera por Recursos: Um processo, além dos recursos já
alocados, ainda aguarda por outros recursos;
3- Não-Preempçã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 que esperar por um
recurso alocado a outro processo e vice-versa.
Sistemas Operacionais
19
Deadlock
Espera circular
Processo A
Processo A
solicita o
Recurso 2
Recurso 1
alocado ao
Processo A
Recurso 2
Recurso 1
Processo B
Recurso 2
alocado ao
Processo B
Processo B
solicita o
Recurso 1
Sistemas Operacionais
20
Prevenção de Deadlocks
Para que um Deadlock ocorra, todas as quatro condições devem
ocorrer simultaneamente. Se garantirmos que uma delas não
ocorra, prevenirmos a ocorrência de Deadlocks em um
determinado sistema. Examinaremos as quatro condições
separadamente:
1- Negando a condição “Exclusão Mútua”:
• Essa condição não deve ser negada, pois dois processos
acessando um recurso simultaneamente poderia causar caos
no sistema.
Ex.: Dois processos acessando uma impressora ao mesmo tempo.
Utilizando o sistema de spool é solucionado esse problema pois
um único processo de spool acessa a impressora
diretamente e não acessa outro recurso, com isso deadlocks não
podem ocorrer, porém nem todos os recursos utilizam o spool.
Sistemas Operacionais
21
Prevenção de Deadlocks
2- Negando a condição “Esperar por Recurso”:
• Requer que todos os recursos que um processo precise devem ser
requisitados de uma só vez.
• O sistema deve liberar os recursos segundo uma política de tudo
ou nada.
• Se todos os recursos que o processo solicitou estão disponíveis, então o
sistema pode alocá-los todos ao mesmo processo de uma vez.
• Caso contrário, ele deverá esperar até que todos estejam
disponíveis, porém nessa espera, não deve deter nenhum
recurso. Assim a condição é negada e Deadlocks não podem ocorrer.
Desvantagens:
• Desperdício de Recursos: O recurso que será executado por último
fica alocado ao processo antes de ser efetivamente utilizado.
•
Possibilidade de um processo ficar indefinidamente esperando, se
outros processos estiverem usando os recursos que ele deseja com
freqüência.
Sistemas Operacionais
22
Prevenção de Deadlocks
3- Negando a condição “Não Preempção”:
Negar a condição de “não-preempção” é uma estratégia ainda pior do que a anterior.
Para vários recursos, não é interessante que um processo perca
seus dados, porque foi interrompido durante seu uso.
4- Negando a condição “Espera Circular”:
1ª Maneira: Estabelecer regra que um processo só pode alocar um
único recurso em um dado momento. Se ele precisa de um 2º
recurso, deve liberar o primeiro;
2ª Maneira: Todos os recursos devem ser numerados em ordem
crescente, assim processos podem requisitar recursos sempre.
Sistemas Operacionais
23
Detecção e Recuperação
•
Alguns sistemas verificam se existe a possibilidade de
surgir um Deadlock. (periodicamente ou certos eventos)
•
Caso esse algoritmo de detecção for executado muitas
vezes, tornará o sistema lento, mas se não for executado
vezes suficientes, os processos em Deadlock e os recursos do
sistema ficam entrelaçados até que o sistema seja recuperado.
•
Problema acima surge devido a um Deadlock que impede de
executar algum evento que dispare o algoritmo de execução.
•
Na estratégia do algoritmo de detecção, ele primeiramente
detecta se ocorre a situação de Deadlock e depois
recupera, desbloqueiando os recursos. Essa é a estratégia
mais utilizada para tratamento de Deadlock.
Sistemas Operacionais
24
Exercícios
1) Defina o que é uma aplicação concorrente e dê um exemplo de sua
utilização?
2) O que é Exclusão Mútua e como é implementada?
3) Explique o que é sincronização condicional e dê um exemplo de sua
utilização.
4) Diferencie Semáforos e Monitores.
5) Quais são os tipos possíveis de Semáforos?
6) O que é Deadlock, qual a condição para obtê-lo e quais as soluções
possíveis?
7) O que é mecanismo de troca de mensagens e como pode ser
implementado?
8) O que é Região Crítica em um programa?
9) Liste uma solução para a Exclusão Mútua explicando-a.
10) " Independente do mecanismo de comunicação adotado, processos que
estão trocando mensagens devem ter suas execuções
sincronizadas".Esta afirmação está correta? Justifique
Sistemas Operacionais
25