Aula07_Sincronismo_de_Processos

Prévia do material em texto

Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Aula 7 
Capítulo 7 – Sincronismo de processos 
• 7.1 Fundamento 
• 7.2 O problema da seção crítica 
• 7.3 Solução de Peterson 
• 7.4 Hardware de sincronismo 
• 7.5 Semáforos 
• 7.6 Problemas clássicos de sincronismo 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.1 Fundamento 
• Processo Cooperativo: pode afetar ou ser afetado 
pelos outros processos que estão em execução no 
sistema. 
• Esses processos podem compartilhar um mesmo 
espaço de endereçamento lógico (código e dados) ou 
ter permissão para compartilhar dados apenas através 
de arquivos. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.1 Fundamento 
• Acesso concorrente aos dados compartilhados podem 
resultar em inconsistência de dados. 
• Manter a consistência dos dados exige mecanismos 
para garantir a correta execução dos processos 
cooperativos. 
• A sincronização entre os processos garante a 
execução adequada para que dados inconsistentes 
não sejam gerados, dos processos em cooperação 
que compartilham um determinado espaço de 
endereçamento. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.1 Fundamento 
• Exemplo: Produtor-Consumidor 
• Processo Produtor – produz informação para o 
processo consumidor. 
• Processo Consumidor – consume a informação 
produzido pelo processo produtor. 
• Produtor-Consumidor devem estar sincronizados, de 
modo que o consumidor não tente consumir um item 
que ainda não tenha sido produzido. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.1 Fundamento 
• Em processos sequenciais isso não teria nenhum 
problema, mas quando falamos de diversos 
processos que manipulam dados concorrentes, 
isso lembra de uma corrida entre processos. 
• Para isso é necessário um mecanismo de 
sincronização entre os processos. 
• Ex.: Criamos uma variável count para armazenar um 
valor, que será utilizado pelo produtor e pelo 
consumidor para saber tantas posições temos de 
memória. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.1 Fundamento 
• count = count + 1 => quando um novo item é 
adicionado na área de armazenamento. 
• count = count - 1 => quando item é removido dessa 
área. 
• Mas mesmo assim teríamos problemas se 
permitíssemos que ambos processos manipulassem o 
valor armazenado em count simultaneamente. 
• A seguir vamos aprender como solucionar esse 
problema. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.2 O Problema da Seção Crítica 
• Como primeiro método de controle de acesso a 
recurso compartilhado, declaramos uma seção do 
código como crítica; depois regulamos o acesso a 
essa seção. 
• Considere um sistema consistindo em n threads {T0, 
T1, ..., Tn-1}. 
• Cada thread possui um segmento de código, 
chamado seção crítica, em que a thread pode alterar 
variáveis comuns, atualizando uma tabela, gravando 
um arquivo e assim por diante. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.2 O Problema da Seção Crítica 
• Característica mais importante desse sistema: 
– Quando uma thread está executando em sua seção crítica, 
nenhuma outra thread pode ter permissão para executar em 
sua seção crítica. 
– Assim a execução de seções críticas pelas threads é 
mutuamente exclusiva no tempo. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.2 O Problema da Seção Crítica 
• O desafio da seção crítica é criar um protocolo que as 
threads possam utilizar para a cooperação. 
• Uma solução para o problema da seção crítica precisa 
satisfazer os três requisitos a seguir: 
– Exclusão mútua 
– Progresso 
– Espera limitada 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.2 O Problema da Seção Crítica 
– Exclusão mútua – Se uma thread está executando em sua 
seção crítica, então nenhuma outra thread poderá executar 
em suas seções críticas. 
– Progresso – Se nenhuma thread estiver executando em sua 
seção crítica e algumas threads quiserem entrar em suas 
seções críticas, então somente as threads que não estão 
executando em suas seções não críticas poderão participar 
na decisão sobre qual entrará em sua seção crítica em 
seguida, e essa seleção não pode ser adiada 
indefinidamente. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.2 O Problema da Seção Crítica 
– Espera limitada – existe um limite no nº de vezes que outras 
threads têm permissão para entrar em suas seções críticas 
após uma thread ter feito uma requisição para entrar em sua 
seção crítica e antes de essa requisição ser atendida. 
• Esse limite impede starvation de qualquer processo isolado. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.3 Solução de Peterson 
• É uma solução clássica baseada em software para o 
problema da região crítica. 
• Apesar de não haver garantias para as arquiteturas 
modernas que realizam as instruções básicas em 
linguagem de máquina load e store. 
• É uma boa descrição algorítmica da solução do 
problema da região crítica. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.3 Solução de Peterson 
• A solução de Peterson é restrita a dois processos que 
alternam a execução entre suas seções críticas e as 
seções restantes. 
• Os processos são numerados como P0 e P1, ou seja, 
Pi indica um processo e Pj indica o outro processo, j = 
i – 1. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.3 Solução de Peterson 
Veja o algoritmo: 
 
int turn; // a variável turn indica de quem é a vez de entrar em seção crítica. 
boolean flag[2]; /* o array flag é usado para indicar se um processo está pronto 
para entrar em sua seção crítica. flag[i] = true implica que o processo Pi está 
pronto.*/ 
 
while (true) { 
 flag[i] = TRUE; 
 turn = j; 
 while (flag[j] && turn == j) 
 seção crítica 
 flag[i] = FALSE; 
 seção restantes 
} 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.4 Hardware de sincronismo 
• Os recursos disponíveis em hardware podem tornar a 
tarefa de programação mais fácil e o sistema mais 
eficiente. 
• Existem algumas instruções simples de hardware que 
estão disponíveis em muitos sistemas e que podem 
ser usadas para resolver o problema das seções 
críticas. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.4 Hardware de sincronismo 
• O problema de seção crítica poderia ser solucionada 
de forma simples em um ambiente monoprocessado 
poderia ser desativado as interrupções. 
– O código atualmente em execução poderia ser executado 
sem preempção. 
• Infelizmente, essa solução não é viável em um 
ambiente multiprocessado. Desabilitar interrupções 
em multiprocessadores pode ser algo demorado, pois 
os comandos para habilitar e desabilitar precisam ser 
passados a todos os processadores. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.4 Hardware de sincronismo 
• Máquinas modernas, oferecem instruções de 
hardware especiais, que nos permitem testar e 
modificar o conteúdo de uma palavra, ou trocar o 
conteúdo de duas palavras, atomicamente - ou seja, 
como uma unidade ininterrupta. 
• Podemos usar essas instruções especiais para 
solucionar o problema da seção crítica de maneirarelativamente simples. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.4 Hardware de sincronismo 
• A instrução get-and-set tem uma característica 
importante, é uma instrução executada de forma 
atômica. 
• Assim, se duas instruções get-and-set forem 
executadas simultaneamente (em CPUs diferentes), 
serão executadas sequencialmente em qualquer 
ordem. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.4 Hardware de sincronismo 
• A instrução swap assim como a instrução get-and-set 
é uma instrução executada de forma atômica. 
• Ela opera sobre o conteúdo de duas palavras. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• As soluções para as seções críticas através do 
hardware não são fáceis de serem adaptadas como 
solução para problemas mais complexos. 
• Para esse tipo de problema mais complexos temos 
uma ferramenta de sincronização chamado 
SEMÁFORO. 
7.5 Semáforos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Semáforo nada mais é do que uma ferramenta de 
sinalização. 
• Um semáforo S é uma variável inteira que, fora a 
inicialização, é acessada apenas por duas operações 
padrão: acquire( ) e release( ). 
• As modificações feitas no valor inteiro do semáforo 
nas operações acquire( ) e release( ) precisam ser 
executadas de modo atômico. Veja a seguir o que 
isso significa. 
7.5 Semáforos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Quando um thread modificar o valor do semáforo, 
nenhuma outra thread poderá modificar esse mesmo 
valor de semáforo concorrentemente. 
7.5 Semáforos 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Semáforos são usados para resolver problemas de 
sincronização entre processos concorrentes, 
principalmente os problemas das seções críticas. 
• Temos dois tipos de semáforos: 
– Semáforo Contador – valor nele armazenado pode ser 
qualquer número inteiro. 
– Semáforo Binário – valor nele armazenado pode variar entre 
0 e 1. E pode ser implementado mais simplesmente. Também 
conhecidos como mutex. 
7.5.1 Utilização 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Semáforos Contadores: 
– podem ser usados para controlar o acesso a determinado 
recurso consistindo em um número finito de instâncias. 
– O semáforo é inicializado para o número de recursos 
disponíveis. 
– Cada thread que deseja usar um recurso realiza uma 
operação acquire( ) sobre o semáforo (decrementando o 
contador). 
– Quando a thread libera um recurso, ela realiza uma operação 
release( ) (incrementando o contador). 
– Quando o contador para o semáforo chega a 0, todos os 
recursos estão sendo usados. 
 
7.5.1 Utilização 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Semáforo Binário: 
– São usado para controlar o acesso a uma seção crítica para 
um processo ou thread. 
– Cinco threads separadas são criadas, mas somente uma 
pode estar em seção crítica em determinado momento. 
– O semáforo compartilhado por todas as threads, controla a 
acesso a seção crítica. 
– Ele verifica quem (thread) está executando sua seção crítica 
e bloqueia as demais. 
 
 
7.5.1 Utilização 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Essas soluções que acabamos de ver exigem a 
espera ocupada. Enquanto um processo está em sua 
seção crítica, qualquer outro processo que tenta 
entrar em sua seção crítica precisa ficar em loop 
contínuo no código de entrada. 
• Um semáforo que produz esse resultado também é 
chamado de spinlock ou semáforos com espera em 
ciclo. 
• Os semáforos com espera em ciclo são úteis quando 
o tempo de espera para entrada em seções críticas 
for pequeno. 
7.5.2 Implementação 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
Semáforo com espera em ciclo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Semáforo com espera em ciclo (Spinlock) 
– Vantagem: não há necessidade de troca de contexto quando 
um processo precisa esperar em um bloco de operações. 
– Desvantagem: Desperdício de tempo da CPU - processo 
executando sua seção crítica, os demais processos entra em 
um ciclo de espera. Ocupa a CPU com um ciclo repetitivo 
prejudicando outros processos que poderiam estar usando a 
CPU de modo produtivo. 
7.5.2 Implementação 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.5.2 Implementação 
• Para contornar a necessidade de espera ocupada, 
podemos modificar as definições das operações 
acquire( ) e release( ). 
• Quando um processo executa a operação acquire( ) e 
descobre que o valor do semáforo não é positivo, ele 
precisa esperar. Entretanto, em vez de usar a espera 
ocupada, o processo pode se bloquear. 
 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.5.2 Implementação 
• O operação de bloqueio coloca um processo em uma 
fila de espera associada ao semáforo, e o estado do 
processo é passado para o estado esperando. 
• Em seguida, o controle é transferido para o 
escalonador da CPU, que seleciona outro processo 
para ser executado. 
• Um processo bloqueado, esperando por um semáforo, 
deve ser reiniciado quando algum outro processo 
executar uma operação release( ). 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.5.3 Deadlocks e Starvation 
• A implementação de um semáforo com uma fila de 
espera pode resultar em uma situação em que dois ou 
mais processos aguardam indefinidamente por um 
evento que só poderá ser causado por um dos 
processos aguardando. 
• Quando esse estado é alcançado, considera-se que 
esses processos estão em um deadlock. 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Impasse (deadlock) é uma paralisação que pode 
ocorrer quando dois ou mais processos estão cada 
um esperando por alguma coisa que somente o outro 
pode fornecer. 
• Resumindo, os processos estão esperando por um 
evento que nunca ocorrerá (abandono de processos). 
7.5.3 Deadlocks e Starvation 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Outro problema relacionado com deadlock é o 
bloqueio indefinido ou starvation (estagnação) – 
uma situação na qual os processos esperam 
indefinidamente no semáforo. 
7.5.3 Deadlocks e Starvation 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Esses problemas são utilizados para testar novas 
propostas de mecanismos de sincronização. 
• São eles: 
– O problema do buffer limitado 
– O problema dos leitores-escritores 
– O problema dos filósofos na mesa de jantar 
7.6 Problemas clássicos de sincronismo 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Vamos falar novamente sobre o produtor e o 
consumidor. 
• O consumidor não pode consumir mais do que o 
produtor produziu, ou seja o consumidor não pode ler 
um espaço vazio. 
• O produtor não pode produzir dados se não tiver 
espaço para armazenar. 
• Esse é o problema do buffer limitado. 
7.6.1 O problema do buffer limitado 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Situação-problema: 
– Um banco de dados dever ser compartilhado entre diversas 
threads concorrentes. 
– Algumas dessas threads podem querer apenas ler o banco 
de dados, enquanto outras podem querer atualizar o banco 
de dados (ouseja, ler e escrever nele). 
7.6.2 O problema dos leitores-escritores 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Leitores: são threads (processos) que somente lê 
valores armazenados. 
• Escritores: são threads (processos) que podem ler e 
modificar valores armazenados. 
• Se dois leitores acessarem os dados compartilhados 
concorrentemente, não teremos qualquer efeito 
adverso. 
7.6.2 O problema dos leitores-escritores 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• O problema está se um escritor está utilizando um 
objeto compartilhado, e um leitor ou escritor quiser 
usar simultaneamente. 
• Para garantir que essas dificuldades não surjam, é 
preciso que os escritores tenham acesso exclusivo ao 
objeto compartilhado. 
• Esse requisito leva ao problema de leitores-escritores. 
• Esse problema tem sido usado para testar quase toda 
nova primitiva de sincronismo. 
7.6.2 O problema dos leitores-escritores 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Imagine 5 filósofos que gastam suas vidas pensando 
e comendo. 
• Os filósofos compartilham uma mesa redonda comum, 
cercada por cinco cadeiras, cada uma pertencendo a 
um filósofo. 
• No centro da mesa existe uma tigela de arroz, e a 
mesa está disposta com 5 hashi1. 
 
 
 
• 1 O hashi ou fachi, chamados ainda popularmente de pauzinhos ou palitinhos, também conhecidos como são 
as varetas utilizadas como talheres em boa parte dos países do Extremo Oriente, como a China, o Japão, o 
Vietnã e a Coréia. http://pt.wikipedia.org/wiki/Hashi 
 
7.6.3 O problema dos filósofos na mesa de 
jantar 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
7.6.3 O problema dos filósofos na mesa de 
jantar 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Quando um filósofo pensa, ele não interage com os 
colegas. 
• De vez em quando, um filósofo tem fome e tenta 
pegar os dois pauzinhos próximos a ele (os pauzinhos 
estão entre ele e seus vizinhos da esquerda e da 
direita). 
• Um filósofo só pode pegar um pauzinho de cada vez. 
Obviamente, ele não pode pegar um pauzinho que já 
esteja na mão de um vizinho. 
7.6.3 O problema dos filósofos na mesa de 
jantar 
Sistemas Operacionais com Java 
Silberschatz, Galvin e Gagne (c) 2003 
• Quando um filósofo com fome tem dois pauzinhos ao 
mesmo tempo, ele come sem largar os pauzinhos. 
• Quando termina de comer, ele coloca os dois 
pauzinhos na mesa e recomeça a pensar. 
• O problema dos filósofos na mesa de jantar é 
considerado um problema clássico de sincronismo, 
pois é um exemplo de uma grande classe de 
problemas de controle de concorrência. 
7.6.3 O problema dos filósofos na mesa de 
jantar 
Sistemas Operacionais com Java 
Referências 
• Capítulo 7 da referência abaixo: 
– SILBERSCHATZ, ABRAHAM; GAGNE, GREG; 
GALVIN, PETER BAES. Sistemas operacionais: 
com java. . Rio de Janeiro: Elsevier, 2004. 
 
Silberschatz, Galvin e Gagne (c) 2003