Sincronismo e
Comunicação entre
Processos
Profa. Priscila Facciolli
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.
• Evitando 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
sim
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.
• Os mecanismos que garantes a comunicação entre
processos concorrentes e o acesso aos recursos são
chamados de Mecanismos de Sincronização.
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.
• 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 impede que outros
processos entrem em suas próprias Regiões Críticas.
Isto ocorre ao recurso estar livre mas ainda alocado a um
processo, impedindo que os demais o utilizem.
Sistemas Operacionais
7
Soluções para a Exclusão Mútua
No Hardware:
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
Sincronização de processos vinculada a uma condição de acesso.
a
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 / Consumidos 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 pro
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
É uma variável inteira, não negativa, que só pode ser manipulada pro
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
12
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
13
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 ficará aguardando a sua vez em uma fila de entrada.
•
Encarrega-se de garantir
procedimentos definidos.
a
Exclusão
Sistemas Operacionais
Mútua
entre
os
14
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
15
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 na comunicação
tenham suas execuções sincronizadas.
Sistemas Operacionais
16
Troca de Mensagens
Transmissão de
mensagem
Processo
transmissor
Processo
receptor
Canal de comunicação
SEND
RECEIVE
Sistemas Operacionais
17
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
18
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.
•
Nela, vários processos podem estar associados a MAILBOX.
•
Também possuem suas execuções sincronizadas em função do fluxo de
mensagens. Um processo não pode tratar uma mensagem até que ela tenha sido
enviada ou receber a mesma mensagem mais de uma vez.
Processo A
Processo B
Mailbox
ou Port
Sistemas Operacionais
19
Deadlock
É a situação onde o processo aguarda pro um recurso que nunca
estará disponível ou um evento que não ocorrerá. É consequencia
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
20
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
21
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 é solucionada 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
22
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
23
Prevenção de Deadlocks
3- Negando a condição “Não Preempção”:
Para vários recursos, como uma impressora, não é interessante que um
processo perca seus dados 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
24
Detecção e Recuperação
•
Alguns sistemas verificam se existe a possibilidade de surgir um
Deadlock quer periodicamente ou caso certos eventos ocorram.
•
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.
•
Surge devido a um Deadlock que impedem 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, que
resulta no desbloqueio dos recursos. Essa é a estratégia mais
utilizada para tratamento de Deadlock.
Sistemas Operacionais
25
Gerenciamento Manual de
Deadlock
Muitos os sistemas atuais deixam para o usuário a função
de detectar um Deadlock, que através da utilização
rotineira, o usuário percebe que o tempo para que o
processo seja executado já foi ultrapassado, ficando a
critério do usuário achar que os processos entraram em
Deadlock e com isso podem resolver a situação através
das ferramentas dos sistemas, como por exemplo sua
reinicialização.
Sistemas Operacionais
26
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
27