Sincronização Arquivo - Comunidade Aprender Livre

Sincronização de Processos
Sistemas Operacionais
Informática (Técnico)
CEFET
Atualizado em 19/03/2014
Introdução
Processos ou threads de uma aplicação
concorrente compartilham recursos do
sistema
Arquivos
Memória
Dispositivos de E/S
O compartilhamento destes recursos pode
ocasionar situações indesejadas, que
podem comprometer a execução da
aplicação
Introdução
Para evitar esse problema, os
processos e threads devem ter sua
execução sincronizada
O sistema operacional deve oferecer
mecanismos que garantam o
correto funcionamento destes
processos e threads
Exemplo
Concorrência
Existem várias maneiras de
especificar a concorrência entre
programas
A primeira notação de concorrência
em um programa foram os
comandos FORK e JOIN
Conway (1963)
Dennis e Van Horn (1966)
Concorrência – FORK e JOIN
PROGRAM A;
...
FORK B;
...
JOIN B;
...
END;
PROGRAM B;
...
...
...
END;
Concorrência – FORK e JOIN
O FORK faz com que seja criado um outro
processo para a execução do programa B,
concorrentemente ao programa A.
O comando JOIN permite que o programa
A sincronize-se com B.
Ou seja, o programa A irá esperar pelo
término do processamento de B.
Concorrência – PARBEGIN e PAREND
Uma das implementações mais claras e simples
de expressar concorrência foi introduzida por
Dijkstra, em 1965
O comando PARBEGIN especifica que a seqüência
de comandos seja executada numa ordem
imprevisível, através da criação de um processo
(Processo_1, Processo_2, Processo_N) para cada
comando (Comando_1, Comando_2,
Comando_N).
O comando PAREND define um ponto de
sincronização, onde o programa só continuará
quando todos os processos ou threads criados
tiverem terminado suas execuções.
Problema de Compartilhamento
Suponha que um programa principal, P,
possua uma variável X, inteira, e duas
threads, A e B.
Quando executada, a thread A soma 1 a
X.
Quando executada, a thread B diminui 1
em X.
Ao executar as threads concorrentemente
qual será o valor de X ?
Problema de Compartilhamento
Um comando de atribuição em uma
linguagem de alto nível pode ser
decomposto em mais comandos em
linguagem Assembly.
Logo, podemos pensar que, para o
processador, um comando em
linguagem de alto nível pode ainda
significar diversos comandos a
serem processados.
Problema de Compartilhamento
Thread A:
Thread B:
LOAD X, Ra
ADD 1, Ra
STORE Ra, X
LOAD X, Rb
SUB 1, Rb
STORE Rb, X
Problema de Compartilhamento
Imagine que A execute:
LOAD X, Ra
ADD 1, Ra
E neste momento A sofra preempção* por
tempo e B entre em execução:
LOAD X, Rb
SUB 1, Rb
Neste momento B sofre preempção e A
volta a ser processado:
STORE Ra, X
Finalmente, B retorna a execução:
STORE Rb, X
X ficará zero (0) !
Preempção: é o direito a preferência
Problema de Compartilhamento
Recaptulando o exemplo, sendo X = 1:
Thread
A
A
B
B
A
B
Instrução
LOAD X, Ra
ADD 1, Ra
LOAD X, Rb
SUB 1, Rb
STORE Ra, X
STORE Rb, X
X
1
1
1
1
2
0
Ra
1
2
2
2
2
2
Rb
?
?
1
0
0
0
Conclusão
Em qualquer situação onde dois ou mais
processos ou threads compartilhem um
mesmo recurso, devem existir
mecanismos de controle para evitar este
tipo de problema.
Este problema é conhecido como
Condição de Corrida (Race Condition).
Exclusão Mútua
A solução mais simples para evitar o
acesso simultâneo a um recurso é impedílo.
Enquanto um processo estiver acessando
um recurso, os demais processos devem
esperar até que o acesso termine.
Essa idéia de exclusividade é chamada de
Exclusão Mútua (ou “mutex”).
Deve afetar apenas os processos
concorrentes somente quando os mesmos
acessarem um recurso compartilhado.
Exclusão Mútua – Região Crítica
A parte do código onde é feito o acesso a
um recurso compartilhado é chamado de
Região Crítica.
A idéia é que o código dentro de uma
Região Crítica seja executado de forma
exclusiva, ou seja, por somente um
processo por vez.
No código é preciso sinalizar o início e o
término da região crítica.
Soluções de Hardware
A exclusão mútua pode ser
implementada através de
mecanismos de hardware:
Desabilitação de Interrupções
Test-And-Set
Soluções de Hardware – Desabilitação
de Interrupções
Ao entrar em uma região crítica,
todas as interrupções são
desabilitadas
Como a preempção é realizada
através de uma interrupção, o
processo que as desabilitou terá
acesso exclusivo garantido.
Não haverá preempção !
Soluções de Hardware – Desabilitação
de Interrupções
Essa solução é simples, mas tem algumas
limitações:
A multiprogramação pode ficar comprometida, já
que a concorrência tem como base o uso de
interrupções (preempção).
Em sistemas com múltiplos processadores, a
solução pode ser ineficiente por causa do tempo de
propagação da sinalização
(desabilitação/habilitação) para todas as CPUs (caso
contrário, outra CPU poderia acessar).
Interfere no mecanismo de clock (sinal que
coordena as ações de circuitos eletrônicos) do
sistema, que é implementado através de
interrupções. Logo, deve ser usada com cuidado.
Logo, é indicada para o kernel do Sistema
Operacional, mas não para processos do usuário.
Soluções de Hardware – Test and Set
Lock (TSL)
É uma instrução especial que permite
carregar uma variável booleana (1 bit)
compartilhada (global) armazenando seu
valor num registrador (LOAD) e atribuindo
o valor (STORE) 1 à mesma, num só
passo.
TSL Ra, flag
Copia flag para Ra e faz flag igual a 1
de forma exclusiva.
Soluções de Hardware – Test and Set
Lock (TSL)
Servirá para simularmos uma região
crítica.
Enquanto o flag for 1, estamos na região
crítica.
Quando atribuirmos 0 (zero), saímos da
região crítica.
Como flag é global, todos sabem que
enquanto seu valor for 1, todos devem
esperar.
Soluções de Hardware – Test and Set
Lock (TSL)
O uso da instrução especial TSL
oferece vantagens, como:
Simplicidade de implementação da
exclusão mútua em múltiplas regiões
críticas
Pode ser usada em arquiteturas com
múltiplos processadores
A principal desvantagem é a
possibilidade de haver starvation.
Primitivas de Exclusão Mútua
As soluções de software iniciais
usavam as primitivas
EnterCriticalSession e
LeaveCriticalSession.
A maioria era feita pensando na
utilização de um único processador.
Primitivas de Exclusão Mútua
Enquanto uma thread não estiver em
sua sessão crítica, outras threads
podem entrar em sua própria sessão
crítica.
Se uma sessão crítica de uma thread
não for codificada adequadamente,
pode comportar-se mal, levando ao
adiamente indefinido de outras
threads, ou até ao deadlock*.
*Deadlocks serão vistos adiante
Sleep e WakeUp
São primitivas de comunicação
interprocessos que bloqueiam ao invés
de gastar tempo de CPU.
Sleep é uma chamada ao sistema que faz
com que quem a chama fique suspenso
até que um outro processo o desperte.
WakeUp desperta um processo desejado,
passado por parâmetro.
Semáforo
Conceito criado por Edsger Dijkstra,
em 1965.
É uma forma de gerar Exclusão
Mútua.
Pode ser visto como uma variável
num programa que controla o
acesso a um determinado recurso.
Semáforo
Se é controlado se um recurso está
disponível ou ocupado, dizemos que
é um semáforo binário (0 ou 1).
Se é controlado a quantidade
disponível de um determinado
recurso, dizemos que é um
semáforo de contagem (0..n).
Exemplo com Semáforo Binário
Suponha que, num sítio, 5 crianças queiram
andar de bicicleta, mas haja apenas 1 bicicleta
disponível.
Para evitar disputas, cada criança deve solicitar a
bicicleta ao caseiro.
Enquanto a bicicleta está sendo usada por uma
criança, as outras esperam.
Quando uma criança entrega a bicicleta ao
caseiro, ele a libera para uma outra criança poder
usá-la.
Pense na bicicleta como o recurso, nas crianças
como os processos e o caseiro como o semáforo,
que indica se a bicicleta (recurso) está disponível
ou não quando a criança (processo a requisita).
Exemplo com Semáforo de Contagem
Suponha que, num sítio, 30 crianças queiram andar de
bicicleta, e hajam 12 bicicletas idênticas disponíveis.
Para evitar disputas, cada criança deve solicitar a bicicleta ao
caseiro.
O caseiro verifica, em sua prancheta, quantas bicicletas estão
disponíveis (não importam quais, já que são idênticas).
Quando o caseiro cede à uma criança alguma bicicleta, ele
diminui a quantidade de bicicletas disponíveis em sua
prancheta.
Se a quantidade de bicicletas disponíveis chegar a zero, as
demais crianças terão de esperar pela liberação de alguma
bicicleta.
Quando uma criança entrega a bicicleta ao caseiro, ele
aumenta a quantidade de bicicletas disponíveis para uso.
Pense na bicicleta como o recurso, nas crianças como os
processos e o caseiro como o semáforo, que controla se há
bicicletas (recursos) disponíveis para uso.
Semáforo
O uso de semáforos foi adotado em
diversos sistemas operacionais para tratar
problemas de concorrência (condição de
corrida).
Apesar de funcionar bem para muitos
casos, há a possibilidade de haver
bloqueio perpétuo (deadlock), quando
ocorrem determinadas seqüências de
eventos.
Deadlock
É um bloqueio perpétuo causado
por um impasse.
Exemplo: Linhas de Trem
Deadlock
Um processo está em deadlock
quando espera por um evento
particular que jamais ocorrerá.
Um sistema está em deadlock
quando um ou mais processos estão
nesta situação.
Exemplo
Uma cadeia sucessiva de solicitações de
recursos que culminam num arranjo
circular.
Um processo A, que detém um recurso
R1, solicita um recurso R2 alocado para
um processo B.
B por sua vez está solicitando o recurso
R1, em uso por A.
Como nenhum processo dispõe a,
voluntariamente, liberar o recurso que
aloca, configura-se uma situação de
bloqueio perpétuo.
Exemplo
A
R1
R2
B
Maneiras de Resolver
1.
2.
3.
4.
Ignorar o problema e conviver com
ele
Detectar e se recuperar
Prevenção dinâmica (por análise)
Prevenção estrutural (exclusão
mútua, etc.)
Questões
1.
2.
3.
4.
5.
Por que devemos efetuar a
sincronização do acesso a recursos
feitos por threads?
O que é uma Condição de Corrida?
Dê um exemplo de uma situação
onde há uma Condição de Corrida.
O que é Exclusão Mútua?
O que é uma Região Crítica?
Questões
6.
Como funciona a implementação
de Exclusão Mútua por hardware
através da Desabilitação de
Interrupções? Quais as suas
vantagens e desvantagens?
7.
Como funciona a implementação
de Exclusão Mútua por hardware
através da instrução TSL ?
Questões
Qual é a idéia por trás dos
algoritmos propostos por Dekker e
Peterson? Qual é a desvantagem
desses algoritmos?
9. Para que servem as primitivas
Sleep e WakeUp?
10. Qual a idéia dos Semáforos,
introduzidos por Dijkstra,
aproveitando o uso das primitivas
Sleep e WakeUp?
8.
Questões
11.
O que é Deadlock? Dê o exemplo
de uma situação, no contexto de
processos e threads, em que ele
ocorre.