Sistemas Operacionais 7 8 9 10 12 RAID 1

Prévia do material em texto

Arquitetura de Sistemas Arquitetura de Sistemas 
OperacionaisOperacionais
Cap. 7 – Sincronização e Comunicação 1
Capítulo 7Capítulo 7
Sincronização e ComunicaçãoSincronização e Comunicação
entre Processosentre Processos
Sumário
• Introdução
• Aplicações concorrentes
• Especificação de concorrência em programas
• Problemas de compartilhamento de recursos
• Exclusão mútua
Cap. 7 – Sincronização e Comunicação 2
• Exclusão mútua
• Sincronização condicional
• Semáforos
• Monitores
• Troca de mensagens
• Deadlock
Introdução
• Surgindo os sistemas multiprogramáveis, 
passou a ser possível uma aplicação ter 
trechos de códigos sendo executado de 
forma concorrente – aplicação concorrente;
• A base é a execução cooperativa de 
processos ou threads em prol de um objetivo 
Cap. 7 – Sincronização e Comunicação 3
processos ou threads em prol de um objetivo 
comum;
• Mesmo em sistemas monoprocessados é 
possível obter ganhos com aplicações 
concorrentes;
• Ao sistema multiprocessados estende as 
vantagens do uso deste tipo de aplicação;
Introdução
• É natural o compartilhamento de 
recursos pelos processos de uma 
aplicação concorrente;
• Este compartilhamento pode gerar 
situações indesejáveis;
• Para evitar estas situações os 
Cap. 7 – Sincronização e Comunicação 4
• Para evitar estas situações os 
processos devem ter a sua execução 
sincronizadas, a partir de mecanismos 
oferecidos pelo S.O.;
• Este capítulo descreve a sincronização 
e comunicação entre processos.
Aplicações Concorrentes
• Muitas vezes, os processos 
concorrentes devem comunicar entre 
si;
• Esta comunicação pode ser 
implementada através de:
Cap. 7 – Sincronização e Comunicação 5
implementada através de:
– Memória compartilha;
– Troca de mensagens.
Aplicações Concorrentes
• Na próxima figura:
– Um processo que lê do buffer;
– Outro processo de grava no buffer;
• Condições:
– O processo só lê se o buffer não tiver 
vazio;
Cap. 7 – Sincronização e Comunicação 6
vazio;
– O processo só grava se o buffer não tiver 
cheio;
• Em ambos os casos, os processos 
deverão esperar o buffer estar pronto 
para a operação;
Aplicações Concorrentes
• Sincronização e comunicação entre 
processos
Sincronização
Cap. 7 – Sincronização e Comunicação 7
Processo
gravador
Processo
leitor
dado
l e i t
u r
a
gravação
Buffer
Aplicações Concorrentes
• Os mecanismos que garantem a 
comunicação e o acesso aos recursos 
compartilhados são chamados de 
mecanismos de sincronização;
• Nesta abordagem tanto subprocessos 
Cap. 7 – Sincronização e Comunicação 8
• Nesta abordagem tanto subprocessos 
como thread tem o mesmo significado 
que processos, para exemplicação das 
aplicações;
Especificação de Concorrência em 
Programas
• Existem várias notações para 
especificar a concorrência em 
programas (partes do programa que 
devam ser executadas 
concorrentemente);
Cap. 7 – Sincronização e Comunicação 9
concorrentemente);
• Conway(1963) e Dennis e Van Horm, 
criaram a primeira notação:
– FORK – cria um outro processo;
– JOIN – sincroniza com outro programa;
Especificação de Concorrência em 
Programas
PROGRAM A
-
-
FORK B;
-
-
JOIN B;
PROGRAM B
-
-
-
END.
• O programa A começa;
• Encontra o comando FORK:
– Começa o programa B em outro 
processo;
• O programa A encontra o 
comando JOIN:
– O programa A espera o término 
Cap. 7 – Sincronização e Comunicação 10
END.– O programa A espera o término 
do programa B;
• Estes comandos são utilizados 
no Unix;
Especificação de Concorrência em 
Programas
• Dijkstra em 1965 propôs o PARABEGIN 
e o PARAEND, uma das 
implementações mais claras;
• Foram chamadas, posteriormente, de 
COBEGIN e COEND;
Cap. 7 – Sincronização e Comunicação 11
COBEGIN e COEND;
• O comando PARABEGIN especifica uma 
seqüência de comandos seja executa 
de forma concorrente em uma ordem 
imprevisível, criando um processo para 
cada comando;
Especificação de Concorrência em 
Programas
• O comando PARAEND define um ponto 
de sincronização, onde o 
processamento só continua quando 
todos os processos tiverem 
terminados;
Cap. 7 – Sincronização e Comunicação 12
terminados;
• Os comandos podem ser simples, como 
atribuições ou chamadas a 
procedimentos;
Especificação de Concorrência 
em Programas
• Concorrência em programas
Processo
principal
Cap. 7 – Sincronização e Comunicação 13
Processo
principal
Processo 1 Processo 2 Processo n
PARBEGIN
 Comando_1;
 Comando_2;
 .
 .
 Comando_n;
PAREND
Especificação de Concorrência 
em Programas
X := SQRT (1024) + (35.4 * 0.23) - (302 / 7)
PROGRAM Expressao;
VAR X, Temp1, Temp2, Temp3 : REAL;
BEGIN
PARBEGIN
Cap. 7 – Sincronização e Comunicação 14
PARBEGIN
Temp1 := SQRT (1024);
Temp2 := 35.4 * 0.23;
Temp3 := 302 / 7;
PAREND;
X := Temp1 + Temp2 - Temp3;
WRITELN ('x = ', X);
END.
Especificação de Concorrência em 
Programas
• O cálculo final de X, só pode ser 
efetuado após terem terminado o 
cálculo de Temp1, Temp2 e Temp3;
Cap. 7 – Sincronização e Comunicação 15
Problema de Compartilhamento 
de Recursos
• Veremos algumas problemas de 
compartilhamento de recursos:
– Compartilhamento de um arquivo em 
disco;
– Compartilhamento de uma variável na 
Cap. 7 – Sincronização e Comunicação 16
– Compartilhamento de uma variável na 
memória principal;
Problema de Compartilhamento 
de Recursos
• Arquivo em disco:
– Atualização de um saldo bancário;
– Lançamento de um débito/crédito;
– Em um arquivo são armazenados todos os 
saldos dos clientes de um banco;
Cap. 7 – Sincronização e Comunicação 17
saldos dos clientes de um banco;
– O programa (próxima transparência):
•Lê o saldo de um cliente;
•Lê o valor da operação;
•Atualiza o saldo;
•Grava o saldo.
Problema de Compartilhamento 
de Recursos
PROGRAM Conta_Corrente;
.
.
READ (Arq_Contas, Reg_Cliente);
READLN (Valor_Dep_Ret);
Reg_Cliente.Saldo := 
Cap. 7 – Sincronização e Comunicação 18
Reg_Cliente.Saldo := 
Reg_Cliente.Saldo + Valor_Dep_Ret;
WRITE (Arq_Contas, Reg_Cliente);
.
.
END.
Problema de Compartilhamento 
de Recursos
• Considerando dois funcionários do banco 
atualizando o mesmo cliente; Certo 1.100
Caixa Comando Arquivo Valor Memória
1 Lê Saldo 1.000 * 1.000
1 Lê valor 1.000 -200 1.000
Cap. 7 – Sincronização e Comunicação 19
1 Lê valor 1.000 -200 1.000
1 Atualiza 1.000 -200 800
2 Lê saldo 1.000 * 1.000
2 Lê valor 1.000 +300 1.000
2 Atualiza 1.000 +300 1.300
1 Grava 800 -200 800
2 Grava 1.300 +300 1.300
Problema de Compartilhamento 
de Recursos
• Variável compartilhada:
– Dois processos (A e B) executam um 
comando de atribuição;
•Processo A soma 1 à X;
•Processo B diminui 1 de X;
Cap. 7 – Sincronização e Comunicação 20
•Processo B diminui 1 de X;
– Se X, inicialmente, é igual a 2 e de se 
esperar que o resultado, após a execução 
dos processos continue igual a 2;
Problema de Compartilhamento 
de Recursos
• Linguagem de alto nível 
Processo A Processo B
X := X + 1; X := X - 1;
Cap. 7 – Sincronização e Comunicação 21
• Linguagem de baixo nível
Processo A Processo B
LOAD x,Ra LOAD x,Rb
ADD 1,Ra SUB 1,Rb
STORE Ra,x STORE Rb,x
Problema de Compartilhamento 
de Recursos
Processo Comando X Ra Rb
A LOAD X, Ra 2 2 *
A ADD 1, Ra 2 3 *
Cap. 7 – Sincronização e Comunicação 22
B LOAD X, Rb 2 * 2
B ADD 1, Rb 2 * 1
A STORE Ra, X 3 3 *
B STORE Rb, X 1 * 1
Problema de Compartilhamento 
de Recursos
• Analisando os exemplos conclui-se que 
em qualquer situação, onde dois ou 
mais processos compartilhamum 
mesmo recurso, devem existir 
mecanismos de controle para evitar 
Cap. 7 – Sincronização e Comunicação 23
mecanismos de controle para evitar 
estes tipos de problemas, conhecidos 
como race conditions (condições de 
corrida);
Exclusão Mútua
• Solução é impedir que dois ou mais 
processos acessem o mesmo recurso 
simultaneamente;
• Portanto, quando um processo estiver 
acessando um recurso, os demais 
Cap. 7 – Sincronização e Comunicação 24
acessando um recurso, os demais 
processos que queiram acessar este 
recurso deverão esperar pelo término 
da utilização deste recurso;
• Esta idéia é chama de exclusão mútua 
(mutual exclusion);
Exclusão Mútua
• A exclusão mútua deve afetar apenas 
os processos concorrentes somente 
quando um deles tiver fazendo acesso 
ao recurso compartilhado;
• A parte do código onde se acessa o 
recurso compartilhado é chamada de 
Cap. 7 – Sincronização e Comunicação 25
recurso compartilhado é chamada de 
região crítica (critical region);
• Para evitar os problemas causados pelo 
compartilhamento basta evitar que 
dois processos entrem na sua região 
crítica simultaneamente;
Exclusão Mútua
Cap. 7 – Sincronização e Comunicação 26
Exclusão Mútua
• Os mecanismos que implementam a exclusão 
mútua utilizam protocolos de acesso à região 
crítica;
• Quando um processo desejar executar 
instruções de sua região crítica, deverá 
executar um protocolo de entrada na região 
Cap. 7 – Sincronização e Comunicação 27
executar um protocolo de entrada na região 
crítica obrigatoriamente;
• Da mesma forma quando sair da região 
crítica deverá executar um protocolo de 
saída;
• Estes protocolos garantem a exclusão mútua 
da região crítica;
Exclusão Mútua
BEGIN
.
.
Entra_Regiao_Critica; (* protocolo de entrada *)
Regiao_Critica;
Sai_Regiao_Critica; (* protocolo de saída)
.
.
Cap. 7 – Sincronização e Comunicação 28
.
END.
Exclusão Mútua
• Para o programa de Conta_Corrente:
– Recurso compartilhado
• Arquivo de contas correntes;
– Solução
• Sempre que o Processo A for atualizar o saldo, 
antes de ler o acesso exclusivo ao arquivo deve 
Cap. 7 – Sincronização e Comunicação 29
antes de ler o acesso exclusivo ao arquivo deve 
ser garantido protocolo de entrada;
• Se conseguir o acesso, significa que outro 
processo não esta utilizando o recurso, podendo 
assim atualizar o saldo
• Quando gravar o saldo atualizado o Processo A 
libera o recurso – saída da região crítica –
permitindo assim que outro processo utiliza o 
recurso (arquivo de conta corrente);
Exclusão Mútua
• Para garantir a implementação da 
exclusão mútua os processos 
envolvidos devem fazer acesso os 
recursos de forma compartilhada;
• Existem diversas soluções para este 
Cap. 7 – Sincronização e Comunicação 30
• Existem diversas soluções para este 
propósito, mas deve-se evitar duas 
situações:
– Espera indefinida (starvation starvation);
– Um processo fora da sua região crítica 
impede que outros processos utilizem o 
recurso compartilhado;
Exclusão Mútua
• Espera indefinida (starvation)
– Ocorre quando um processo nunca 
consegue executar a sua região crítica 
(utilizar o recurso compartilhado);
– Quando um recurso é liberado o S.O. 
Possui um critério para selecionar o 
Cap. 7 – Sincronização e Comunicação 31
Possui um critério para selecionar o 
próximo processo que terá acesso ao 
recurso;
– Dependendo do processo de escolha o 
starvation pode ocorrer;
Exclusão Mútua
• Espera indefinida (starvation)
– Escolha aleatória: não está garantindo que 
em algum momento um processo terá 
acesso ao recurso pois a escola é 
aleatória;
– Por prioridade: a baixa prioridade de um 
Cap. 7 – Sincronização e Comunicação 32
– Por prioridade: a baixa prioridade de um 
processo em relação aos outros pode 
impedir o acesso ao recurso;
– Uma solução simples: criação de filas de 
pedidos para cada recurso, usando FIFO.
Exclusão Mútua
• Um processo fora da sua região crítica 
impede que outros processos utilizem o 
recurso compartilhado;
• Neste caso o recurso estaria livre 
porém alocado a um processo;
Cap. 7 – Sincronização e Comunicação 33
porém alocado a um processo;
• Assim todos os processos que utilizam 
este recurso estariam impedidos de 
entrar nas suas regiões críticas;
Exclusão Mútua
• Soluções de hardware:
– Desabilitação de interrupções;
– Instrução test-and-set.
• Soluções de software
– Primeiro algoritmo;
– Segundo algoritmo;
Cap. 7 – Sincronização e Comunicação 34
– Segundo algoritmo;
– Terceiro algoritmo;
– Quarto algoritmo;
– Algoritmo de Dekker;
– Algoritmo de Peterson;
– Algoritmo para exclusão mútua entre N processos.
Exclusão Mútua
• Desabilitação de interrupções
– Solução mais simples;
– É desabilitado todas as interrupções antes 
de entrar na região crítica;
– É habilitado todas as interrupções após 
Cap. 7 – Sincronização e Comunicação 35
– É habilitado todas as interrupções após 
deixar a região crítica;
– Como a mudança de contexto só pode ser 
executada através de interrupções, fica 
garantindo, assim, o acesso exclusivo;
Exclusão Mútua
• Desabilitação de interrupções
BEGIN
.
Desabilita_Interrupcoes;
Cap. 7 – Sincronização e Comunicação 36
Desabilita_Interrupcoes;
Regiao_Critica;
Habilita_Interrupcoes;
.
END.
Exclusão Mútua
• Desabilitação de interrupções
• Limitações:
– A multiprogramação pode ficar seriamente 
comprometida, já a concorrência tem 
como base o uso de interrupções;
– Se o processo “esquecer” de habilitar as 
Cap. 7 – Sincronização e Comunicação 37
– Se o processo “esquecer” de habilitar as 
interrupções, o sistema ficaria seriamente 
comprometido;
– Em sistemas multiprocessados esta 
solução torna-se ineficiente devido ao 
tempo de propagação de um processador 
para os outros da desabilitação/abilitação 
das interrupções;
Exclusão Mútua
• Desabilitação de interrupções
• Limitações:
– Não esquecer que o mecanismo de clock é 
implementado com o uso de interrupções;
– A seção crítica pode executar E/S que 
Cap. 7 – Sincronização e Comunicação 38
– A seção crítica pode executar E/S que 
dependam de interrupções;
– Apesar das limitações, esta solução pode 
ser útil quando se deseja que partes do 
núcleo do S.O. sem interrupções, 
garantindo que não haverão problemas de 
inconsistências nas estruturas de dados;
Exclusão Mútua
• Instrução test-and-set
– Instrução que:
•Le uma variável;
•Armazena o conteúdo em outro local;
•Atribui um novo valor a mesma variável;
Cap. 7 – Sincronização e Comunicação 39
•Atribui um novo valor a mesma variável;
•É executada sem interrupção, ou seja, é 
uma instrução indivisível;
– Desta forma, é garantindo que dois 
processos não acessem uma variável 
compartilhada ao mesmo tempo – permite 
implementar a exclusão mútua;
Exclusão Mútua
• Instrução test-and-set
– Test-and-Set (X,Y):
• O valor lógico de Y é copiado para X;
• Y recebe o valor lógico verdadeiro.
– Para coordenar o acesso concorrente, é utilizado 
uma variável lógica global chamada de bloqueio:
Cap. 7 – Sincronização e Comunicação 40
uma variável lógica global chamada de bloqueio:
• Quando bloqueio for falso qualquer processo 
poderá alterar o seu valor para verdadeiro e ter 
acesso ao recurso de forma exclusiva;
• Quando terminar de usar o recurso, o processo 
retorna o valor falso para o bloqueio, liberando 
o acesso ao recurso. 
Exclusão Mútua
Program Test_and_Set
var
Bloqueio: boolean;
Procedure Processo_A;
var
P_A : boolean; // pode A
begin
repeat
P_A:= true;
Procedure Processo_B;
var
P_B : boolean; // pode B
begin
repeat
P_B:= true;
while (P_B) do
Test_and_Set(P_B, Bloqueio);
Regiao_Critica_B;
Cap. 7 – Sincronização e Comunicação 41
P_A:= true;
while (P_A) do
Test_and_Set (P_A, Bloqueio);
Regiao_Critica_A;
Bloqueio:= false;
until true;
end;
Regiao_Critica_B;
Bloqueio:= false;
until true;
end;
begin
Bloqueio := false;
PARBEGIN
Processo_A;
Processo_B;
PARAEND
End.
Exclusão Mútua
Processo A Processo B P_A P_B Bloqueio
repeat repeat * * F
P_A:= T P_B:= T T T F
while (P_A) Test_and_set T F T
Test_and_Set Regiao_Critica_B T F T
Cap. 7 – Sincronização e Comunicação 42
T F T
while (P_A) Bloqueio:= F T F F
Test_and_set P_B:= T F T T
Regiao_Critica_A while (P_B) F T T
Exclusão Mútua
• Instrução test-and-set
– Esta solução apresenta algumas 
vantagens:
•Simplicidade de implementação
•Uso em arquitetura com múltiplos 
Cap. 7 – Sincronização e Comunicação 43
•Uso em arquitetura com múltiplos 
processadores;
– Principal desvantagem:
•Possibilidade de starvation, pois a 
escolha do processo para acesso ao 
recurso é aleatória.
Exclusão Mútua
• Soluções de software
– Algoritmo 1
• Uma solução para dois processos;
• Onde a alternância na execução das seções 
críticas;
• Cada procedimento (A e B) é representado por 
Cap. 7 – Sincronização e Comunicação 44
• Cada procedimento (A e B) é representado por 
um loop infinito, onde o recurso é acessado;
• É formado por protocolo de entrada, seção 
crítica e um protocolo de saída;
• A região crítica é representada por uma rotina 
onde o acesso realmente ocorre;
• Após a seção crítica as rotinas executam 
procedimentos individuais.
Exclusão Mútua
• Algoritmo 1
– É utilizada uma variável de bloqueio 
indicando qual processo poderá acessar a 
região crítica;
– Inicialmente possui o valor A indicando 
que o processo A terá acesso;
Cap. 7 – Sincronização e Comunicação 45
que o processo A terá acesso;
– O processo só terá acesso a região crítica, 
quando o processo A atribuir a variável de 
bloqueio o valor ‘B’;
– Assim fica garantindo a exclusão mútua 
dos processos.
Exclusão Mútua
program Algoritmo 1;
var
Vez : char;
procedure Proc_A
begin
repeat
while (vez = ‘B’) do ; /nada
Regiao_Critica_A;
Vez := ‘B’;
procedure Proc_B
begin
repeat
while (vez = ‘A’) do ; /nada
Regiao_Critica_B;
Vez := ‘A’;
Processa_B;
until false;
end;
Cap. 7 – Sincronização e Comunicação 46
Vez := ‘B’;
Processa_A;
until false;
end;
begin
Vez := ‘A’;
PARBEGIN
Proc_A;
Proc_B;
PAREND;
end.
Exclusão Mútua
Proc_A Proc_B Vez
while (Vez = ‘B’) while (Vez = ‘A’) A
Regiao_Critica_A while (Vez = ‘A’) A
Vez:= ‘B’ while (Vez = ‘A’) B
Cap. 7 – Sincronização e Comunicação 47
Vez:= ‘B’ while (Vez = ‘A’) B
Processa_A Regiao_Critica_B B
Processa_A Vez:= ‘A’ A
Processa_A Processa_B A
Processa_A while (Vez = ‘A’) A
Exclusão Mútua
• Algoritmo 1
– Problema 1:
• O acesso ao recurso só pode ser efetuado por 
dois processos e sempre de maneira alternada;
• O processo que utiliza o recurso mais vezes que 
o outro, permanecerá mais vezes bloqueado;
Cap. 7 – Sincronização e Comunicação 48
o outro, permanecerá mais vezes bloqueado;
• Por exemplo, de Proc_A ficar muito tempo no 
Processa_A, é possível que Proc_B queria usar 
o recurso e não o consiga, mesmo Proc_A não 
necessite do recurso.
• Caso um processo tenha o loop mais rápido que 
o outro, a possibilidade de usar o recurso fica 
limitado ao processo de velocidade menor.
Exclusão Mútua
• Algoritmo 1
– Problema 2:
•Se houver um problema com um 
processo de forma que o valor da 
variável de bloqueio não seja alterado, o 
outro processo permanecerá 
Cap. 7 – Sincronização e Comunicação 49
outro processo permanecerá 
indefinidamente bloqueado. 
Exclusão Mútua
• Algoritmo 2
– O problema principal do algoritmo 1 é que 
ambos processos trabalham com a mesma 
variável global, que indica qual processo 
terá acesso a região crítica;
– Para resolver este problema o algoritmo 2 
Cap. 7 – Sincronização e Comunicação 50
– Para resolver este problema o algoritmo 2 
introduz uma variável para cada processo 
(CA e CB), que indica se o processo está 
na região crítica;
– Assim antes de um processo entrar na sua 
região crítica, testa se o outro processo 
está usando o recurso;
Exclusão Mútua
program Algoritmo 2;
var
CA : boolean;
CB : boolean;
procedure Proc_A
begin
repeat
procedure Proc_B
begin
repeat
while (CA) do ; /nada
CB := true;
Regiao_Critica_B;
CB:= false;
Processa_B;
Cap. 7 – Sincronização e Comunicação 51
repeat
while (CB) do ; /nada
CA := true;
Regiao_Critica_A;
CA:= false;
Processa_A;
until false;
end;
Processa_B;
until false;
end;
begin
CA:= false;
CB:= false;
PARBEGIN
Proc_A;
Proc_B;
PAREND;
end.
• Algoritmo 2
– Neste caso o uso do recurso não é 
realizado, necessariamente, alternado;
– Caso um processo tenha um problema fora 
da região crítica não bloqueia o outro 
processo;
Exclusão Mútua
Cap. 7 – Sincronização e Comunicação 52
processo;
– Mas se um processo tiver um problema na 
região crítica ou antes de alterar o valor da 
variável, bloqueará, indefinidamente, o 
outro processo;
– Mas, o mais grave é que este algoritmo 
nem sempre garante a exclusão mútua;
Exclusão Mútua
Proc_A Proc_B CA CB
while(CB) while(CA) F F
Cap. 7 – Sincronização e Comunicação 53
while(CB) while(CA) F F
CA:= true CB:= true T T
Regiao_Critica_A Regiao_Critica_B T T
Exclusão Mútua
• Algoritmo 3
– Este algoritmo tenta solucionar o problema 
do algoritmo 2, colocando a instrução de 
atribuição de CA e CB antes do loop de 
teste;
– Este algoritmo garante a exclusão mútua, 
Cap. 7 – Sincronização e Comunicação 54
– Este algoritmo garante a exclusão mútua, 
mas introduz a possibilidade do bloqueio 
indefinido de ambos os processos;
Exclusão Mútua
program Algoritmo 3;
var
CA : boolean;
CB : boolean;
procedure Proc_A
begin
repeat
procedure Proc_B
begin
repeat
CB := true;
while (CA) do ; /nada
Regiao_Critica_B;
CB:= false;
Processa_B;
Cap. 7 – Sincronização e Comunicação 55
repeat
CA := true;
while (CB) do ; /nada
Regiao_Critica_A;
CA:= false;
Processa_A;
until false;
end;
Processa_B;
until false;
end;
begin
CA:= false;
CB:= false;
PARBEGIN
Proc_A;
Proc_B;
PAREND;
end.
Exclusão Mútua
Proc_A Proc_B CA CB
CA:= true CB:= true T T
Cap. 7 – Sincronização e Comunicação 56
CA:= true CB:= true T T
while(CB) while(CA) T T
Exclusão Mútua
• Algoritmo 4
– No algoritmo 3, cada processo altera o 
estado da sua variável desconhecendo o 
estado do outro processo – este é o 
problema;
– Altera o algoritmo 3 de forma que altera o 
Cap. 7 – Sincronização e Comunicação 57
– Altera o algoritmo 3 de forma que altera o 
estado o estado da variável antes de 
entrar a região crítica (como no algoritmo 
3), porém existe a possibilidade de 
reverter esta alteração;
Exclusão Mútua
program Algoritmo 4;
var
CA : boolean;
CB : boolean;
procedure Proc_A
begin
repeat
CA := true;
while (CB) do 
begin
procedure Proc_B
begin
repeat
CB := true;
while (CA) do 
begin
CB:= false; 
{pequeno intervalo de tempo aleatório}
CB := true;
end;
Regiao_Critica_B;
Cap. 7 – Sincronização e Comunicação 58
begin
CA:= false; 
{pequeno intervalo de tempo aleatório}
CA := true;
end;
Regiao_Critica_A;
CA:= false; 
Processa_A;
until false;
end;
Regiao_Critica_B;
CB:= false; 
Processa_B;
until false;
end;
begin
CA:= false;
CB:= false;
PARBEGIN
Proc_A;
Proc_B;
PAREND;
end.
• Algoritmo 4
– Esta solução garante exclusão mútua e 
não gera bloqueio simultâneo dos 
processos;
– Mas, no casodos tempos aleatórios serem 
próximos e a concorrência gerar uma 
Exclusão Mútua
Cap. 7 – Sincronização e Comunicação 59
próximos e a concorrência gerar uma 
situação onde os processos alterem as 
variáveis CA e CB para falso antes do 
término do loop, nenhum dos processos 
conseguirá executar a sua região crítica, 
mesmo não sendo permanente, esta 
situação pode gerar problemas
Exclusão Mútua
• Algoritmo de Dekker
– Primeira solução de software que garantiu 
a exclusão mútua entre dois processos 
sem problemas foi proposto por T. Dekker;
– Este algoritmo possui uma lógica bastante 
complexa;
Cap. 7 – Sincronização e Comunicação 60
complexa;
– Ver no livro texto as referencias;
Exclusão Mútua
• Algoritmo de Peterson
– Facilmente generalizada para N processos;
– Similar ao algoritmo 3, além das variáveis de 
condição (CA e CB), introduz a variável Vez para 
gerar os conflitos gerados pela concorrência;
– Antes de acessar a região crítica, o processo 
Cap. 7 – Sincronização e Comunicação 61
– Antes de acessar a região crítica, o processo 
sinaliza este desejo (variável de condição), porém 
o processo cede o uso do recurso (variável Vez);
– O processo executa o while (protocolo de 
entrada);
– Assim além de garantir a exclusão mútua, o 
bloqueio indefinido nunca ocorrerá, pelo uso da 
variável Vez;
Exclusão Mútua
program Algoritmo_Peterson;
var
CA : boolean;
CB : boolean;
Vez : char; 
procedure Proc_A
begin
repeat
CA := true;
procedure Proc_B
begin
repeat
CA := true;
Vez := ‘A’;
while (CA and Vez = ‘A’) do ; /nada
Regiao_Critica_B;
CB:= false;
Processa_B;
Cap. 7 – Sincronização e Comunicação 62
CA := true;
Vez := ‘B’;
while (CB and Vez = ‘B’) do ; /nada
Regiao_Critica_A;
CA:= false;
Processa_A;
until false;
end;
Processa_B;
until false;
end;
begin
CA:= false;
CB:= false;
PARBEGIN
Proc_A;
Proc_B;
PAREND;
end.
• Algoritmo para exclusão mútua para N 
processos:
– O algoritmo de Peterson foi generalizado para N 
processos, Hofri (1990);
– O algoritmo do Padeiro (bakey Algorithm) proposto 
por Lamport(1974);
– Problema espera ocupada (busy wait), este caso, 
quando um processo não consegue entrar em sua 
Exclusão Mútua
Cap. 7 – Sincronização e Comunicação 63
quando um processo não consegue entrar em sua 
região crítica, este processo permanece em loop 
testando uma condição, consumino recurso do 
processador;
– A solução para este problema foi a introdução de 
mecanismo de sincronismo que permitem colocar 
um processo em estado de espera, quando estiver 
esperando para entrar na região crítica. 
(semáforos e monitores)
Sincronização Condicional
• Sincronização condicional é quando o 
acesso a um recurso compartilhado 
exige uma sincronização entre os 
processos;
• Exemplo clássico é a comunicação 
entre dois processos através de 
Cap. 7 – Sincronização e Comunicação 64
entre dois processos através de 
operações de gravação e leitura em um 
buffers;
• Os processos devem estar 
sincronizados para que um processo 
não tente ler um buffer vazio nem 
gravar em um buffer cheio;
Sincronização Condicional
• Este problema é conhecido como problema 
do produtor/consumidor ou do buffer 
limitado;
• No algoritmo na próximo slide, o recurso 
compartilhado é um buffer, definido como 
tamanho TamBuf, sendo o acesso controlado 
pela variável Cont;
Cap. 7 – Sincronização e Comunicação 65
pela variável Cont;
• Cont:
– Igual a zero: significa que o buffer está vazio, e o 
processo Consumidor deve esperar;
– Igual a TamBuf: significa que o buffer está cheio, e 
o processo Produtor deve esperar; 
• O algoritmo resolve a questão da 
sincronização condicional, mas apresenta o 
problema da espera ocupada;
Sincronização Condicional
PROGRAM Produtor_Consumidor_1;
CONST TamBuf = ( *Tamanho *);
TYPE Tipo_Dado = (* Tipo *);
VAR Buffer : ARRAY [1..TamBuf]
OF Tipo_Dado;
Dado : Tipo_Dado;
Cont : 0..TamBuf;
BEGIN
Cont := 0;
PARBEGIN
PROCEDURE Produtor;
BEGIN
REPEAT
Produz_Dado (Dado);
WHILE (Cont = TamBuf) DO (*nada*);
Grava_Buffer(Dado, Cont);
UNTIL False;
END;
PROCEDURE Consumidor;
BEGIN
Cap. 7 – Sincronização e Comunicação 66
PARBEGIN
Produtor;
Consumidor;
PAREND;
END.
BEGIN
REPEAT
WHILE (Cont = 0) DO (*nada*);
Le_Buffer (Dado);
Consome_Dado(Dado, Cont);
UNTIL False;
END;
Semáforos
• Proposto por E. W. Dijkstra em 1965;
• Mecanismo de sincronização que 
permite implementar a exclusão mútua 
e a sincronização entre processos de 
forma simples;
• Tornou-se um dos principais 
Cap. 7 – Sincronização e Comunicação 67
• Tornou-se um dos principais 
mecanismos utilizados em projeto de 
S.O. e aplicações concorrentes;
• A maioria das linguagens de 
programação disponibiliza rotinas para 
utilizá-los;
Semáforos
• Semáforos são:
– Uma variável inteira não negativa;
– Manipulados através das seguintes 
operações indivisíveis:
•UP (Proberen – teste): incrementa o 
Cap. 7 – Sincronização e Comunicação 68
•UP (Proberen – teste): incrementa o 
valor da variável;
•DOWN (Verhigen – incremento): 
decrementa o valor da variável;
Semáforos
• Semáforos são:
– A variável não pode ser negativa, assim 
um DOWN em um semáforo com valor 
zero, faz o processo entrar no estado de 
espera;
– Normalmente implementada em hardware;
Cap. 7 – Sincronização e Comunicação 69
– Normalmente implementada em hardware;
Semáforos
• Os semáforos podem ser:
– Binários (mutexes): só podem assumir os 
valores zero e um;
– Contadores: podem assumir qualquer valor 
inteiro positivo e zero;
Cap. 7 – Sincronização e Comunicação 70
Semáforos
• Exclusão mútua:
– Pode ser implementada com o uso de 
semáforos binários associado aos recursos 
compartilhados;
– Principal vantagem: não ocorre a espera 
ocupada;
Cap. 7 – Sincronização e Comunicação 71
ocupada;
– As instruções DOWN e UP funcionam como 
protocolo de entrada e saída;
– Quando o valor é um, indica que o recurso 
está disponível, e se for zero significa que 
algum processo está utilizando o recurso;
Semáforos
• Exclusão mútua:
– Quando for entrar na região crítica, o 
processo executa um DOWN;
– Se o semáforo for igual a um, este valor é 
decrementado e o processo entra na 
região crítica;
Cap. 7 – Sincronização e Comunicação 72
região crítica;
– Se o valor for zero, então o processo 
impedido de entrar na seção crítica, e seu 
estado passa a ser de espera, liberando o 
processador.
Semáforos
• Exclusão mútua:
– O processo ao sair da região crítica, deve 
liberar o recurso compartilhado, para 
tanto, basta executar a instrução UP;
– Caso existam vários processos esperando 
a liberação do recurso, o S.O. selecionará 
Cap. 7 – Sincronização e Comunicação 73
a liberação do recurso, o S.O. selecionará 
um, mudando seu estado de espera para 
pronto – próximo slide;
– Não existe a espera ocupada;
Semáforos
• Semáforo binário na exclusão mútua
Processo deseja entrar
na região crítica
DO
Cap. 7 – Sincronização e Comunicação 74
Fila de espera
de processos
Processo acessa
a região crítica
DOW
N
 (S
= 0)D O
W
N 
( S>
0 )
UP (S) - processo sai
da região crítica
Libera processo
da fila de espera
Semáforos
TYPE Semaforo =record
Valor : integer;
Fila_espera: (*lista dos processos em espera*)
end;
Procedure DOWN (VAR S: Semaforo);
begin
if (S = 0) then Coloca_Processo_na_Fila_de_Espera
Cap. 7 – Sincronização e Comunicação 75
if (S = 0) then Coloca_Processo_na_Fila_de_Espera
else S = S – 1;
End;
Procedure UP (VAR S: Semaforo);
begin
S = S + 1;
If (Processo_Esperando) then Retira_da_Fila_de_Espera.
End;
Semáforos
Program Semaforo_1Var 
S : Semaforo = 1;
Procedure Proc_A;
begin
repeat 
Procedure Proc_B;
begin
repeat 
DOWN(S);
Região_Critica_B;
UP (S);
until false;
Cap. 7 – Sincronização e Comunicação 76
repeat 
DOWN(S);
Região_Critica_A;
UP (S);
until false;
end;
until false;
end;
begin
PARABEGIN
Proc_A;
Proc_B;
PARAEND;
End.
Semáforos
Proc_A Proc_B S Pendente
Repeat Repeat 1 *
Down(s) Repeat 0 *
Cap. 7 – Sincronização e Comunicação 77
Down(s) Repeat 0 *
Regiao_Critica_A Down(s) 0 Proc_B
Up(s) Down(s) 1 Proc_B
repeat Regiao_Critica_B 0 *
Semáforos
• Sincronização condicional:
– Pode-se implementar a sincronização 
condicional;
– Exemplo: solicitação de E/S, o processo 
que solicita a E/S executa um DOWN e fica 
em estado de espera até a operação de 
Cap. 7 – Sincronização e Comunicação 78
em estado de espera até a operação de 
E/S ser completada;
– Quando a operação de E/S finaliza a rotina 
de tratamento de interrupção excuta um 
UP, liberando o processo do estado de 
espera;
Semáforos
Program Semaforo_2;
var 
Evento: Semaforo := 0;
Procedure Solicita_Leitura;
begin
DOWN(Evento)
Begin
PARABEGIN
Solicita_leitura;
Le_Dados;
PARAEND;
End;
Cap. 7 – Sincronização e Comunicação 79
DOWN(Evento)
End;
Procedure Le_Dados;
Begin
UP(Evento)
End;
•Algoritmo para sincronização condicional:
Semáforos
• O problema do produtor/consumidor 
pode ser resolvido com o uso de 
semáforos;
• Para tanto:
– Usa buffer de duas posições;
Cap. 7 – Sincronização e Comunicação 80
– Usa buffer de duas posições;
– Um semáforo binário para garantir a 
exclusão mútua;
– Dois semáforos contadores (Vazio e Cheio) 
para a sincronização condicional;
Semáforos
Program Produtor_consumidor_2
Const TB = 2;
TYPE TDado = (*qualquer*)
VAR
Vazio: semaforo := TB;
Cheio: semaforo := 0;
Mutex: semaforo := 1;
Buffer: array[1..TB] of TDado;
Dado_1: TDado;
Dado_2: TDado;
Procedure consumidor;
begin
repeat
Down(Cheio);
Down(Mutex);
Le_Buffer(Dado_2, buffer);
Up(Mutex);
Up(Vazio);
until false;
End;
Cap. 7 – Sincronização e Comunicação 81
Procedure Produtor
begin
repeat
Produz_Dado (Dado_1);
Down (Vazio);
Down (Mutex);
Grava_Buffer(Dado_1, Buffer);
Up(Mutex);
Up(Cheio);
until false;
end; 
begin
parabegin
Produtor;
Consumidor;
paraend;
end. 
Semáforos
Produtor Consumidor Vazio Cheio Mutex Pendente
* * 2 0 1 *
* Down(Cheio) 2 0 1 Con
Down(Vazio) Down(Cheio) 1 0 1 Con
Down(Mutex) Down(Cheio) 1 0 0 Con
Grava_Buffer Down(Cheio) 1 0 0 Con
UP(Mutex) Down(Cheio) 1 0 1 Con
Cap. 7 – Sincronização e Comunicação 82
UP(Mutex) Down(Cheio) 1 0 1 Con
Up(Cheio) Down(Cheio) 1 1 1 *
Up(Cheio) Down(Cheio) 1 0 1 *
Up(Cheio) Donw(Mutex) 1 0 0 *
Up(Cheio) Le_Dados 1 0 0 *
Up(Cheio) Up(Mutex) 1 0 1 *
Up(Cheio) UP(Vazio) 2 0 1 *
Semáforos
• Semáforos contadores são úteis quando 
existem processos concorrentes alocando 
recursos do mesmo tipo (pool de recursos);
• O semáforo começa com número total de 
recursos do pool;
• Quando necessitar de recurso executa um 
Cap. 7 – Sincronização e Comunicação 83
• Quando necessitar de recurso executa um 
DOWN;
• Quando liberar o recurso executa um UP;
• Caso o semáforo contador seja zero, o 
processo que executar um DOWN ficará em 
estado de espera.
Semáforos
• Problemas
– Problema dos filósofos;
– Problema do barbeiro; 
Cap. 7 – Sincronização e Comunicação 84
Monitores
• Monitores são mecanismos de 
sincronização de alto nível que tornam 
mais simples o desenvolvimento de 
aplicações concorrentes;
• Proposto por Binch Hansen, 1972 e 
Cap. 7 – Sincronização e Comunicação 85
• Proposto por Binch Hansen, 1972 e 
desenvolvido por C.A.R. Hoare em 
1974;
• Mecanismo de sincronização 
estruturado, diferente de semáforos, 
considerados não-estruturados; 
Monitores
• Diferentemente dos semáforos, os 
monitores são implementados pelo 
compilador, menos sujeito a erros;
• Inicialmente implementado em poucas 
linguagens (Concurrent Pascal, Modula-
Cap. 7 – Sincronização e Comunicação 86
linguagens (Concurrent Pascal, Modula-
2, Modula-3) 
• Atualmente, a maioria das linguagens 
disponibiliza este recurso;
Monitores
• O monitor é formado por 
procedimentos e variáveis encapsulado 
dentro de um módulo;
• Sua principal característica é a 
implementação da exclusão mútua 
entre os procedimentos declarados;
Cap. 7 – Sincronização e Comunicação 87
entre os procedimentos declarados;
• Toda vez que é chamado um dos 
procedimentos, o monitor verifica se 
outro procedimento esta sendo 
executado, em caso afirmativo, o 
procedimento que quer ser executado 
fica em espera;
Monitores
• Toda inicialização de variáveis é 
realizada por um bloco de comandos, 
sendo executada apenas uma vez, na 
ativação do programa;
• Um monitor é definido especificando:
Cap. 7 – Sincronização e Comunicação 88
• Um monitor é definido especificando:
– Um nome;
– Declarando:
• variáveis locais;
•Procedimentos;
•Código de inicialização;
Monitores
• Estrutura do monitor
Declaração de
variáveis globais
Procedimentos
Proc. 1
Cap. 7 – Sincronização e Comunicação 89
Fila de entrada
Inicialização
de variáveis
Proc. 1
Proc. 2
Proc. n
M
o
n
i
t
o
r
Monitores
Monitor Exclusao_Mutua;
(* variáveis locais *)
procedure Regiao_Critica_1;
begin
:
End; 
Procedure Regiao_Critica_2;
Begin
Cap. 7 – Sincronização e Comunicação 90
Begin
:
end; 
Procedure Regiao_Critica_3;
begin
:
end; 
begin
(* código de inicialização *)
end.
Monitores
• Exclusão mútua
– A implementação mútua utilizando 
monitores não é realizada diretamente 
pelo programador;
– As regiões críticas são definidas como 
procedimentos no monitor e o compilador 
Cap. 7 – Sincronização e Comunicação 91
procedimentos no monitor e o compilador 
garante a exclusão mútua;
– A comunicação do procedimento e monitor 
é executada através de chamada a 
procedimentos e dos parâmetros 
passados;
– A seguir, um exemplo, onde processos 
somam e subtraem um concorrentemente; 
Monitores
program monitor_1
Monitor Rgião_Critica;
var
X : integer;
procedure Soma;
begin
X := X + 1;
begin
PARABEGIN
Regiao_Critica.Soma;
Regiao_Critica.Susbtrai;
PARAEND;
end;
Cap. 7 – Sincronização e Comunicação 92
X := X + 1;
end;
Procudure Subtrai;
begin
X := X – 1;
end;
begin
X:= 0;
end;
Monitores
• Sincronização condicional:
– A sincronização condicional pode ser 
implementada utilizando-se de monitores 
através de variáveis especiais de 
condição;
– É possível associar a execução de um 
Cap. 7 – Sincronização e Comunicação 93
– É possível associar a execução de um 
procedimento que faz parte do monitor a 
uma determinada condição, garantindo a 
sincronização condicional;
– Esta variáveis são manipuladas através de 
duas instruções:
•WAIT;
•SIGNAL;
Monitores
• Sincronização condicional:
– WAIT coloca o processo no estado de espera, até 
que outro processo envie um SIGNAL, informado 
que a condição de espera foi satisfeita;
– Caso se execute um SIGNAL sem que um processo 
esteja aguardando, nenhum efeito terá;
Cap. 7 – Sincronização e Comunicação 94
– É possível ter vários processos com sua execução 
suspensa, assim, o monitor organiza filas 
associadas as condições de sincronização;
– O SIGNAL libera apenas um único processo da fila 
de espera da condição associada;
– Um processo pode executar um procedimento no 
monitor, mesmo quando um ou mais processos 
estão na fila de espera;
Monitores
• Estrutura do monitor com variáveis de 
condição
Declaração devariáveis globais
Procedimentos
Proc. 1
Condição C1
Cap. 7 – Sincronização e Comunicação 95
Fila de entrada
Inicialização
de variáveis
Proc. 1
Proc. 2
Proc. n
M
o
n
i
t
o
r
Filas de espera
Condição C2
Condição Cn
Monitores
• Sincronização condicional:
– Uma solução para o problema do 
produtor/consumidor usando-se monitor é 
apresentado no próximo slide;
– O monitor condicional é estruturado com 
duas variáveis especiais de condição (cheio 
Cap. 7 – Sincronização e Comunicação 96
duas variáveis especiais de condição (cheio 
e vazio) e dois procedimentos (produz e 
consome)
Monitores
Monitor Condicional;
Var
Cheio : (* variável especial de condição *)
Vazio : (* variável especial de condição *)
procedure Produz;
begin
if (Cont = TamBuf) then WAIT (cheio);
:
if (Cont = 1) then SIGNAL (vazio);
Cap. 7 – Sincronização e Comunicação 97
if (Cont = 1) then SIGNAL (vazio);
end;
procedure Consume;
begin
if (Cont = 0) then WAIT (vazio);
:
if (Cont = Tambuf - 1) then SIGNAL (cheio);
end;
begin
end;
Monitores
• Sempre que o produtor desejar gravar um 
dado, deve chamar o procedimento Produz, 
que testa se existe posições vagas no buffer, 
se não tiver, deve executar um WAIT em 
cheio, suspendendo a execução até que um 
outro processo execute um SIGNAL em 
cheio;
Cap. 7 – Sincronização e Comunicação 98
cheio;
• No caso do consumidor, deve executar o 
procedimento Consume sempre que desejar 
ler um dado do buffer, caso o buffer esteja 
vazio deve suspender a sua execução 
efetuando um WAIT no vazio e esperar um 
SIGNAL no vazio para continuar;
Monitores
• No próximo slide uma solução 
completa para o problema 
Produtor/Consumidor utilizando-se de 
monitor condicional;
• Os procedimentos Produz_Dado e 
Consome_Dado servem para entrada e 
Cap. 7 – Sincronização e Comunicação 99
Consome_Dado servem para entrada e 
saída de dados;
• Os procedimentos Grava_Dado e 
Le_Dado são responsáveis pela 
transferência e recuperação do dado no 
buffer;
Monitores
Program Pro_Con_3;
Const
TamBuf = (* tamanho do buffer *)
Dado : array[1..TamBuf] of (*tipo dado *)
Monitor Condicional;
Var
Cheio : (* variável especial de condição *)
Vazio : (* variável especial de condição *)
Cont : integer;
procedure Produz;
begin
if (Cont = TamBuf) then WAIT (cheio);
procedure Produtor
begin
repeat
Produz_Dado (Dado);
Condicional.Produz;
until false;
end;
Procedure Consumidor;
begin
repeat
Condicional.Consome;
Consome_Dado (Dado);
Cap. 7 – Sincronização e Comunicação 100
if (Cont = TamBuf) then WAIT (cheio);
Grava_Dado (Dado, buffer);
Cont = Cont + 1;
if (Cont = 1) then SIGNAL (vazio);
end;
procedure Consume;
begin
if (Cont = 0) then WAIT (vazio);
Le_Dado (Dado, buffer);
Cont = Cont - 1;
if (Cont = Tambuf-1) then SIGNAL (cheio);
end;
begin
Cont := 0;
end;
Consome_Dado (Dado);
until false;
end;
begin
PARABEGIN
Produtor;
Consumidor;
PARAEND;
end.
Troca de Mensagens
• Troca de mensagens é um mecanismo 
de comunicação e sincronização entre 
processos;
• O S.O. possui um subsistema de troca 
de mensagens, sem que haja 
necessidade do uso de variáveis 
Cap. 7 – Sincronização e Comunicação 101
necessidade do uso de variáveis 
compartilhadas;
• Para a comunicação entre processos 
deve existir um canal de comunicação, 
este podendo ser um buffer ou um 
linke de comunicação;
Troca de Mensagens
• Os processos cooperativos trocam 
mensagens através de duas rotinas:
– SEND(receptor, mensagem);
•Envia uma mensagem para um processo 
receptor;
Cap. 7 – Sincronização e Comunicação 102
receptor;
– RECEIVE (transmissor, mensagem);
•Recebe a mensagem enviada por um 
processo transmissor;
Troca de Mensagens
• Transmissão de mensagem
Processo
transmissor
Processo
receptor
Cap. 7 – Sincronização e Comunicação 103
SEND RECEIVE
Canal de comunicação
Troca de Mensagens
• Este mecanismo exige que os 
processos envolvidos tenham suas 
execuções sincronizadas;
• Isto é necessário, já que a mensagem 
só pode ser tratada após o seu 
Cap. 7 – Sincronização e Comunicação 104
só pode ser tratada após o seu 
recebimento;
• Ou que o envio de uma mensagem 
pode ser condição para a continuação 
da execução do processo;
Troca de Mensagens
• a troca de mensagens pode ser 
implementada de duas formas:
– Comunicação direta; 
– Comunicação indireta;
Cap. 7 – Sincronização e Comunicação 105
Troca de Mensagens
• Comunicação direta
– Exige ao enviar ou receber uma 
mensagem o processo enderece 
explicitamente o nome do processo 
receptor ou transmissor;
– Só permite a troca de mensagens entre 
Cap. 7 – Sincronização e Comunicação 106
– Só permite a troca de mensagens entre 
dois processos;
– O principal problema é a necessidade de 
especificação do nome dos processos 
envolvidos;
– Se mudar a identificação dos processos 
deve-se alterar o código do programa;
Troca de Mensagens
• Comunicação direta
Processo A Processo B
Cap. 7 – Sincronização e Comunicação 107
Troca de Mensagens
• Comunicação indireta;
– Utiliza-se uma área compartilhada, onde 
as mensagens pode ser escritas e lidas;
– Esse tipo de buffer é conhecido como 
mailbox ou port;
Cap. 7 – Sincronização e Comunicação 108
– Suas características (identificação, 
capacidade, etc.) são definidas no 
momento a criação;
– Vários processos podem estar associado a 
um mailbox, e as rotinas SEND e RECEIVE 
passam o nome do mailboxes e não mais o 
nome dos processos;
Troca de Mensagens
• Comunicação indireta
Processo A Processo B
Cap. 7 – Sincronização e Comunicação 109
Mailbox
ou Port
Troca de Mensagens
• Independente do mecanismo de 
comunicação utilizado, os processos 
envolvidos devem ter suas execuções 
sincronizadas em função do fluxo de 
mensagens;
Cap. 7 – Sincronização e Comunicação 110
mensagens;
– Um processo não pode tratar de uma 
mensagem que não recebeu;
– Um processo não pode receber a mesma 
mensagem mais de uma vez;
Troca de Mensagens
• Esquemas para implementar o sincronismo:
– Manter o processo transmissor esperando até a 
confirmação de leitura;
• Um processo ao tentar receber uma mensagem 
ainda não enviada, deve permanecer esperando 
até que o processo transmissor faça o envio;
Cap. 7 – Sincronização e Comunicação 111
• Este esquema implementa uma comunicação 
síncrona, conhecida como rendezvous;
• O problema é que a execução dos processos 
fica limitado ao tempo de processamento da 
mensagens;
– Uma variação mais eficiente de rendezvous, é não 
bloquear o processo transmissor; 
Troca de Mensagens
• Esquemas para implementar o sincronismo:
– No terceiro esquema é implementado uma forma 
assíncrona de comunicação;
• O processo transmissor e receptor não 
permanecem esperado o envio e recebimento 
da mensagem;
Cap. 7 – Sincronização e Comunicação 112
• Além dos buffers para armazenar as mensagens 
devem haver mecanismos para permitir ao 
processo identificar se uma mensagem já foi 
enviada ou recebida;
• A grande vantagem é aumentar a eficiência de 
aplicações concorrentes;
Troca de Mensagens
Program Prod_Con_4
procedure Produtor;
Var
msg : Tipo_Msg;
begin
repeat 
procedure Consumidor;
Var
msg : Tipo_Msg;
begin
repeat 
RECEIVE(Msg);
Consome_Mensagem(Msg);
until false;
Cap. 7 – Sincronização e Comunicação 113
Produz_Mensagem(Msg
);
SEND(Msg);
until false;
end; 
until false;
end;
begin
PARABEGIN
Produtor;
Consumidor;
PARAEND;
End. 
Deadlock
• Deadlock é a situação em que um 
processo aguarda por um recurso que 
nunca estará disponível;
• Normalmente,conseqüência de 
compartilhamento de recursos em 
processos concorrentes onde a 
Cap. 7 – Sincronização e Comunicação 114
processos concorrentes onde a 
exclusão mútua é exigida;
• Torna-se mais freqüente e crítico com 
a evolução dos S.O. implementado o 
paralelismo e alocação dinâmica de 
recursos;
Deadlock
• Próxima figura exemplo de deadlock
conhecido como espera circular;
• Cada processo espera que outro 
processo libere o recurso alocado;
Cap. 7 – Sincronização e Comunicação 115
Deadlock
• Espera circular
Processo A
Processo A
solicita o
Recurso 2
Recurso 1
alocado ao
Processo A
Cap. 7 – Sincronização e Comunicação 116
Recurso 2 Recurso 1
Processo B
Recurso 2
alocado ao
Processo B
Processo B
solicita o
Recurso 1
Deadlock
• Condições necessárias
– Exclusão mútua;
• cada recurso só pode estar alocado a um único 
processo;
– Espera por recurso;
• Um processo pode estar esperando por outros 
recursos
Cap. 7 – Sincronização e Comunicação 117
recursos
– Não-preempção;
• Um recurso não pode ser liberado de um 
processo, só porque outros processos desejam 
o mesmo recurso;
– Espera circular;
• Um processo pode ter de esperar por um 
recurso alocado a outro processo e vice-versa;
Deadlock
• Deadlock existe em qualquer sistema 
multiprogramável;
• As solução implementas devem 
considerar o tipo do sistema e o 
impacto em seu desempenho;
Cap. 7 – Sincronização e Comunicação 118
impacto em seu desempenho;
– usina nuclear x folha de pagamento
Deadlock
• Prevenção
– Para evitar o deadlock evitar que uma das 
condições citadas não ocorra;
– Ausência da primeira condição (exclusão 
mútua), a falta da exclusão mútua gerará 
várias inconsistências já mencionadas;
Cap. 7 – Sincronização e Comunicação 119
várias inconsistências já mencionadas;
Deadlock
• Ausência da segunda condição (espera 
por recurso):
– Processos que já possuam recursos 
garantidos não devem requisitar novos 
recursos;
– Uma forma é pré-alocar todos os recursos 
Cap. 7 – Sincronização e Comunicação 120
– Uma forma é pré-alocar todos os recursos 
necessários a um processo;
– Esta solução pode gerar um grande 
desperdício de recursos;
– É difícil determinar o número de recursos 
que um processo utiliza;
– O mais grave é a possibilidade sofrer 
starvation;
Deadlock
• Ausência da terceira condição (não-
preempção):
– Pode ser evita se permitir que um recurso 
seja retirado do processo no caso de outro 
precisar;
Cap. 7 – Sincronização e Comunicação 121
– A liberação de recursos já garantidos pode 
ocasionar sérios problemas, podendo até 
impedir a continuidade do processo;
– Pode ocorre starvation;
Deadlock
• Ausência da quarta condição (espera 
circular);
– Forçar que o processo só tenha um recurso 
por vez;
– Esta condição restringiria muito o grau de 
Cap. 7 – Sincronização e Comunicação 122
– Esta condição restringiria muito o grau de 
compartilhamento e o processamento de 
programas;
Deadlock
• A prevenção de Deadlock (evitando uma das 
quatro condições) é bastante limitada e não 
é utilizada na prática;
• É possível evitar o deadlock, mesmo com as 
quatro condições presentes;
• A solução mais conhecida é o Algoritmo do 
Cap. 7 – Sincronização e Comunicação 123
• A solução mais conhecida é o Algoritmo do 
Banqueiro (Bank’s Algorithm) proposto por 
Dijkstra(1965);
• Basicamente, este algoritmo exige que os 
processos informem o número máximo de 
cada tipo de recurso necessário a sua 
execução;
Deadlock
• Com estas informações, é possível 
definir o estado de alocação de cada 
recurso, que é a relação entre o 
número de recursos alocados e 
disponíveis e o número máximo de 
Cap. 7 – Sincronização e Comunicação 124
disponíveis e o número máximo de 
processos que necessitam desses 
recursos.
• Com estas informações, o S.O. pode 
alocar os recursos evitando o deadlock 
(Tanenbaum 2001);
Deadlock
• Este algoritmo possui várias limitações, 
a maior é a necessidade de um número 
fixo de processos ativos e de recursos 
disponíveis;
Cap. 7 – Sincronização e Comunicação 125
Deadlock
• Detecção do deadlock
– É necessário mecanismos de detecção de 
deadlock, onde não existam prevenção de 
deadlock;
– Esta detecção identifica a existência de deadlock e 
quais os recursos e processos envolvidos neste 
problema;
Cap. 7 – Sincronização e Comunicação 126
problema;
– Para tanto é necessário ao S.O. manter estruturas 
de dados para identificar cada recurso do sistema, 
o processo que o está alocando e os processos que 
estão a espera para usar o recurso;
– Geralmente os algoritmos que verificam a espera 
circular percorrem esta estrutura sempre que um 
processo solicita um recurso;
Deadlock
• Detecção do deadlock
– Dependendo do S.O. o ciclo de busca de 
deadlock pode variar;
– Em sistema de tempo compartilhado o 
tempo de busca pode ser maior, sem 
comprometer-lo;
Cap. 7 – Sincronização e Comunicação 127
comprometer-lo;
– Sistemas de tempo real devem 
constantemente verificar, porém a maior 
segurança leva a um maior overhead;
Deadlock
• Correção
– Uma solução bastante utilizada é eliminar 
um ou mais processos envolvidos no 
deadlock desalocando recursos, quebrando 
assim a espera circular;
– A eliminação de processos não é simples, 
Cap. 7 – Sincronização e Comunicação 128
– A eliminação de processos não é simples, 
dependendo do tipo de recurso envolvido;
•Por exemplo: impressão e gravação em 
disco;
– Os processos eliminados não tem como ser 
recuperados, mas os outros processos 
envolvidos no deadlock continuarão;
Deadlock
• Correção
– A escolha do processo, normalmente, é feita de 
forma aleatória, ou com base em algum tipo de 
prioridade;
– Este esquema pode consumir tempo considerável 
do processador, aumentando overhead;
Cap. 7 – Sincronização e Comunicação 129
– Uma solução menos drástica envolve a liberação 
de alguns recursos até que o ciclo termine;
– Para esta solução ser eficiente, é necessário que o 
sistema pode suspender um processo, liberar seus 
recursos e após a solução, possa retornar ã 
execução, sem perder o processamento já 
realizado;
Deadlock
• Correção
– Este mecanismo é conhecido com rollback:
•Além do overhead;
•É muito difícil de ser implementado;
•É bastante dependente da aplicação; 
Cap. 7 – Sincronização e Comunicação 130
•É bastante dependente da aplicação; 
Arquitetura de Sistemas Arquitetura de Sistemas 
OperacionaisOperacionais
Cap. 8 – Gerência do Processador 1
Capítulo 8Capítulo 8
Gerência do ProcessadorGerência do Processador
Sumário
• Introdução
• Funções Básicas
• Critérios de escalonamento
• Escalonamentos não-preemptivos e 
preemptivos
Cap. 8 – Gerência do Processador 2
• Escalonamento FIFO
• Escalonamento SJF
• Escalonamento cooperativo
• Escalonamento circular
• Escalonamento por prioridades
• Escalonamento circular com prioridades
Sumário
• Escalonamento por múltiplas filas
• Escalonamento por múltiplas filas com 
realimentação
• Política de Escalonamento em Sistemas de 
Tempo Compartilhado 
• Política de Escalonamento em Sistemas de 
Cap. 8 – Gerência do Processador 3
• Política de Escalonamento em Sistemas de 
Tempo Real
Introdução
• Surgimento de sistemas multiprogramavéis, 
a gerencia do processador passou a ser uma 
das principais atividades do S.O.;
• Como podem existir diversos processos no 
estado de pronto deve-se estabelecer um 
critério para a escolha do processo que 
Cap. 8 – Gerência do Processador 4
critério para a escolha do processo que 
passará ao estado de execução;
• Os critérios da escolha do processocompõem a política de escalonamento, que é 
a base da gerencia do processador no S.O.;
Introdução
• Escalonamento
Estado de
Execução
Escal
Cap. 8 – Gerência do Processador 5
Estado de
Espera
Estado de
Pronto
scalo
na
m
ento
Funções Básicas
• A política de escalonamento possui diversas 
funções básicas:
– Manter a UCP ocupada a maior parte do tempo;
– Balancear o uso da UCP entre processos;
– Privilegiar a execução de aplicações críticas;
– Maximizar o throughput;
Cap. 8 – Gerência do Processador 6
– Maximizar o throughput;
– Oferecer tempos de resposta razoáveis para 
usuários interativos;
• Cada SO possui uma política de 
escalonamento adequada ao seu propósito;
Funções Básicas
• O escalonador (scheduler) é a rotina do SO 
responsável pela implementação dos critérios 
da política de escalonamento;
• Já o dispatcher é a rotina responsável pela 
troca de contexto dos processos;
• O tempo gasto na troca de processos é 
Cap. 8 – Gerência do Processador 7
• O tempo gasto na troca de processos é 
chamado de latência do dispatcher;
• O escalonamento é realizado com base em:
– Processos, ambientes que implementam processos
– Threads, ambientes que implementam threads, 
neste caso:
• Processos – unidades de alocação de recursos;
• Threads – unidades de escalonamento;
Critérios de Escalonamento
• As características do SO determinam 
quais são as principais características 
do escalonador;
• Os principais critérios a serem 
considerados em uma política de 
Cap. 8 – Gerência do Processador 8
considerados em uma política de 
escalonamento são: 
Critérios de Escalonamento
• Utilização do processador;
– É desejável que um processador permaneça ocupado a 
maior parte do tempo;
• 30% - baixa utilização
• 90% - alta utilização, sistema carregado
• Throughput;
Cap. 8 – Gerência do Processador 9
• Throughput;
– Representa o número de processos executados em um
intervalo de tempo;
– A sua maximização é desejada na maioria dos casos;
• Tempo de Processador / Tempo de UCP
– É o tempo que um processo leva no estado execução;
– As políticas de escalonamento não influenciam;
– Este tempo é função do código e dos dados de entrada;
Critérios de Escalonamento
• Tempo de Espera
– É o tempo total que um processo permanece na
fila de pronto;
– A sua redução é desejada pela maioria das
políticas de escalonamento;
• Tempo de Turnaround;
– É o tempo que um processo leva da sua criação
até o seu término;
Cap. 8 – Gerência do Processador 10
– É o tempo que um processo leva da sua criação
até o seu término;
– As políticas de escalonamento buscam minimizá-
lo;
• Tempo de Resposta;
– É o tempo decorrido entre uma requisição e o
instante que a resposta é dada;
– Normalmente este tempo é limitado pela
velocidade dos dispositivos de E/S;
Critérios de Escalonamento
• De forma geral se busca:
– Otimizar a utilização do processador;
– Otimizar o throughput;
– Diminuir os tempos:
•Turnaround;
Cap. 8 – Gerência do Processador 11
•Turnaround;
•Espera;
•Resposta;
• Estas funções podem ser conflitantes;
• O tipo de S.O. determina a importância 
dos critérios;
Escalonamentos 
Não-Preemptivo e Preemptivo
• Preempção – possibilidade do SO 
interromper um processo em execução 
e substituí-lo por outro;
• Para implementar a preempção o SO 
são mais complexos, porém, permitem 
Cap. 8 – Gerência do Processador 12
são mais complexos, porém, permitem 
políticas de escalonamento mais 
flexivéis;
• O escalonamento pode ser:
• Não-preemptivo;
• Preemptivo.
Escalonamentos 
Não-Preemptivo e Preemptivo
• Não-preemptivo;
– Primeiro tipo de escalonamento 
implementado;
– Predomínio do processamento batch;
– Um evento externo pode ocasionar a perda 
Cap. 8 – Gerência do Processador 13
– Um evento externo pode ocasionar a perda 
do processador ;
– O processo só sai do estado de execução 
quando termina, ou executa instruções 
que alterem o seu estado para espera
Escalonamentos 
Não-Preemptivo e Preemptivo
• Preemptivo.
– O sistema pode interronper um processo 
em execução e mudar seu estado para 
pronto;
– É possível ao sistema priorizar a execução 
de processos, como nas aplicações de 
Cap. 8 – Gerência do Processador 14
de processos, como nas aplicações de 
tempo real;
– Permite compartilhar o processador de 
uma maneira mais uniforme, por exemplo 
determinar uma fatia de tempo para ser 
usado pelo processo;
Escalonamento FIFO
• Escalonamento First-In-First-Out, também 
conhecido como first-come-first-served (FCFS 
scheduling);
• O primeiro processo que chegar ao estado 
pronto é o selecionado para a execução;
• É bastante simples de se implementar, 
Cap. 8 – Gerência do Processador 15
• É bastante simples de se implementar, 
necessitando apenas de uma fila;
• Nesta fila os processos que passam para o 
estado pronto entram no final da fila;
• O processo que vai ser executado é o que 
está no início da fila;
Escalonamento FIFO
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Cap. 8 – Gerência do Processador 16
Estado de
Espera
Escalonamento FIFO
• No próximo slide um exemplo de 
escalonamento FIFO;
• Três processos:
– A 10 u.t.
– B 5 u.t.
– C 4 u.t.
Cap. 8 – Gerência do Processador 17
– C 4 u.t.
• Duas situações na fila de pronto:
– A, B, C
• Tempo médio de espera é (0+10+14)/3=8 u.t.;
– B, C, A 
• Tempo médio de espera é (7+0+4)/3=3,7 u.t.;
Escalonamento FIFO
• Exemplo
Processo A
Processo B
Processo C
Cap. 8 – Gerência do Processador 18
10 14 17
Processo A
Processo B
Processo C
4 7 17 u.t.
u.t.
Processo
Tempo de
processador
(u.t.)
A
B
C
10
4
3
Escalonamento FIFO
• Deficiências:
– Impossibilidade de prever quando um 
processo terá sua execução iniciada, já 
dependente do tempo de execução dos 
processos que estão antes na fila;
– Os processos CPU-bound levam vantagem 
Cap. 8 – Gerência do Processador 19
– Os processos CPU-bound levam vantagem 
em relação aos processos I/O bound. Se 
os processos I/O bound forem mais 
importantes não a como privilegiá-los;
– Este escalonamento é do tipo não-
preemptivo;
Escalonamento FIFO
– Inicialmente usado em sistemas 
monoprogramavéis com processamento 
em batch;
– Ineficiente, se for aplicado na forma 
original em sistemas interativos de tempo 
compartilhado;
Cap. 8 – Gerência do Processador 20
compartilhado;
– Atualmente, sistemas de tempo 
compartilhado utilizam deste 
escalonamento com variações, permitindo 
sua implementação parcial.
Escalonamento SJF
• Escalonamento shortest-job-first (SJF), 
também conhecido como shortest-process-
next (SPN scheduling);
• O algoaritmo escolhe o processo que tiver o 
menor tempo de processador a ser 
executado;
Cap. 8 – Gerência do Processador 21
executado;
• O processo, na fila de pronto, que necessitar 
de menor tempo para terminar será 
selecionado;
• Exemplo no próximo slide:
– C, B, A
• Tempo médio de espera é (7+3+0)/3=3,3 u.t.;
Escalonamento SJF 
• Escalonamento Shortest-Job-First
Processo A
Cap. 8 – Gerência do Processador 22
Processo B
Processo C
3 7 17 u.t.
Escalonamento SJF
• Implementação usada nos primeiros S.O. 
com processamento exclusivamente batch;
• Para cada processo é associado um tempo de 
processador;
• Como não é possível precisar este tempo, é 
utilizado uma estimativa;
Cap. 8 – Gerência do Processador 23
utilizado uma estimativa;
• Esta estimativa é obtida de uma análise 
estatística das execuções passadas;
• Caso o tempo informado fosse muito inferior 
ao real, o S.O. poderia interromper aexecução do processo;
Escalonamento SJF
• O principal problema é estimar este tempo 
para os processos interativos;
• Uma forma de implementá-lo em ambientes 
interativos é considerar o comportamento do 
processo neste ambiente;
– Executar poucas instruções e executar uma 
operação de E/S.
Cap. 8 – Gerência do Processador 24
operação de E/S.
– Neste caso utiliza-se o tempo de CPU que será 
utilizado da próxima vez e não o tempo total de 
processamento até o término.
– Mas é difícil ao S.O. calcular o tempo acima;
– Mas pode-se utilizar o seu comportamento no 
passado, o tempo pode ser estimado como a média 
exponencial dos tempos passados: 
Escalonamento SJF
• Onde
– tn = tempo mais recente
– δn = valor historio
– α = alterando o valor da constante α (0 < 
( ) nnn t δααδ −+=+ 11
Cap. 8 – Gerência do Processador 25
– α = alterando o valor da constante α (0 < 
α < 1) é possível ponderar a importância 
do passado
Escalonamento SJF
• Inicialmente, o SJF é não-preemptivo;
• A vantagem em relação ao FIFO esta na 
redução de tempo médio de turnaround;
• Mas pode haver starvation para processos 
com tempo de processador muito longo ou 
do tipo CPU-bound;
Cap. 8 – Gerência do Processador 26
do tipo CPU-bound;
• Uma implementação preemptiva é a shortest 
remain time (SRT sheduling)
– Toda vez que um processo em estado pronto tiver 
um tempo de processador estimado menor que o 
processo em execução, substituí o processo que 
está em execução 
– O risco de starvation permanece. 
Escalonamento Cooperativo
• O escalonamento cooperativo é uma 
implementação que busca aumentar o grau 
de multiprogramação em políticas de 
escalonamento que não possuem 
preempção;
• Nesta implementação, o processo em 
Cap. 8 – Gerência do Processador 27
• Nesta implementação, o processo em 
execução, voluntariamente, libera o 
processo, retornando-o a fila de pronto;
• A liberação do processo é uma tarefa 
executada, exclusivamente, pelo processo 
em execução, que de forma cooperativa 
libera o processador para outro processo; 
Escalonamento Cooperativo
• O processo em execução verifica a fila de 
mensagens para determinar se existem 
processos na fila de pronto;
• Como a interrupção não é responsabilidade 
do S.O., algumas situações indesejadas 
podem ocorrer:
Cap. 8 – Gerência do Processador 28
– Se um processo não verificar a fila de mensagem, 
gerará sérios problemas para a multiprogramação 
cooperativa, já que um programa poderá 
permanecer por um longo período de tempo 
alocando o processador.
• As primeiras versões do Windows usavam 
este escalonamento, sendo conhecido 
multitarefa cooperativa.
Escalonamento Circular
• O escalonamento circular (round robin 
sheduling) é preemptivo;
• Projetado especialmente para sistemas de 
tempo compartilhado;
• Semelhante ao FIFO, porém cada processo 
possui um tempo limite para o uso do 
Cap. 8 – Gerência do Processador 29
possui um tempo limite para o uso do 
processador;
• Este tempo é denominado fatia de tempo 
(time-slice) ou quantum;
• Preempção por tempo é nome mecanismo 
que interrponde o processo em execução 
quando a sua fatia de tempo expira;
Escalonamento Circular
• O próximo slide ilustra o escalonamento 
circular , onde a fila de processos de pronto é 
tratada como uma fila circular;
• O escalonamento é realizado alocando a CPU 
ao primeiro processo da fila de pronto;
• O processo permanece em execução até:
Cap. 8 – Gerência do Processador 30
• O processo permanece em execução até:
– Termine o seu processamento;
– Voluntariamente passe para o estado de espera;
– Que a sua fatia de tempo espire, neste caso, 
sofrendo preempção pelo S.O.;
• Um novo processo é escolhido com base na 
política FIFO;
Escalonamento Circular
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Cap. 8 – Gerência do Processador 31
Preempção por tempo
Estado de
Espera
Escalonamento Circular
• O próximo slide ilustra o 
escalonamento circular dos processos 
A, B, C com a fatia de tempo igual 2 
u.t.;
• Não esta considerado o tempo de 
Cap. 8 – Gerência do Processador 32
• Não esta considerado o tempo de 
latência do dispatcher;
Escalonamento Circular 
• Exemplo
Processo A
Processo B
Cap. 8 – Gerência do Processador 33
Processo B
Processo C
2 4 17 u.t.6 8 10 11
Escalonamento Circular
• O valor da fatia de tempo depende do 
S.O., normalmente varia entre 10 e 
100 milissegundos;
• Este valor afeta diretamente o 
desempenho:
Cap. 8 – Gerência do Processador 34
desempenho:
– Valor muito alto, tenderá ter o mesmo 
comportamento da política FIFO;
– Valor muito baixo, haverá muitas 
preempções, prejudicando o desempenho 
e afetando o turnaround dos processos
Escalonamento Circular
• A principal vantagem do 
escalonamento circular é não permitir 
que um processo monopolize a CPU;
• Este tipo de escalonamento é 
adequado aos sistemas de tempo 
Cap. 8 – Gerência do Processador 35
adequado aos sistemas de tempo 
compartilhado, onde existam muitos 
processos interativos;
Escalonamento Circular
• Um problema nesta política é que 
processos CPU-bound são beneficiados 
em relação aos I/O-bound quando ao 
uso de processador;
• Os CPU-bound tendem a usar toda a 
fatia de tempo e os I/O-bound tem 
Cap. 8 – Gerência do Processador 36
fatia de tempo e os I/O-bound tem 
maior probabilidade de passar para o 
estado de espera antes de sofre a 
preempção;
• Estas características levam a um 
balanceamento desigual no uso do 
processador;
Escalonamento Circular
• Um refinamento para reduzir este problema é o 
escalonamento circular virtual, próximo slide;
• Neste esquema os processos que saem do estado de 
espera vão para uma fila de pronto auxiliar, que possui 
uma prioridade maior que a fila de pronto;
• O escalonador só seleciona um processo da lista de 
pronto de a lista de pronto auxiliar estiver vazia;
• Quando um processo é buscado da lista auxiliar seu 
Cap. 8 – Gerência do Processador 37
• Quando um processo é buscado da lista auxiliar seu 
tempo de execução é calculado como o tempo da fatia 
de tempo menos o tempo de processador utilizado na 
última execução;
• Estudos comprovam o balanceando mais equilibrado no 
uso do processador, apesar da maior complexidade para 
implementar
Escalonamento Circular
• Escalonamento circular virtual
Preempção por tempo
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Cap. 8 – Gerência do Processador 38
Preempção por tempo
Estado de
Espera
Fila auxiliar
Escalonamento por Prioridades
• É um escalonamento do tipo 
preemptivo que considera um valor 
chamado de prioridade de execução;
• O processo com maior prioridade na 
fila de pronto é sempre selecionado 
para a execução;
Cap. 8 – Gerência do Processador 39
para a execução;
• Processos com a mesma prioridade são 
selecionados utilizando-se do FIFO;
• Não existe o conceito de fatia de 
tempo, portanto não existe preempção 
por tempo;
Escalonamento por Prioridades
• A perda do uso do processador ocorre:
– Forma voluntária;
– Quando um processo de maior prioridade passa 
para o estado de pronto;
• Preempção por prioridade é o mecanismo do 
S.O. que interrompe o processo em 
execução, salva seu contexto, coloca-o no 
Cap. 8 – Gerência do Processador 40
execução, salva seu contexto, coloca-o no 
estado de pronto e escalona o processo de 
maior prioridade;
• Esta preempção é implementada através de 
interrupção de clock, permitindo, assim, a 
rotina de escalonamento reavalie as 
prioridades dos processos no estado de 
pronto;
Escalonamentopor Prioridades
• O próximo slide exibe o escalonamento por 
prioridades;
• Para cada prioridade existe uma fila de 
estado pronto que é tratada como uma fila 
circular;
• O escalonamento é realizado alocando o 
Cap. 8 – Gerência do Processador 41
• O escalonamento é realizado alocando o 
processador ao primeiro processo da fila de 
maior prioridade;
• O processo perderá o processador:
– Se terminar o processamento;
– Voluntariamente passar para o estado de espera;
– Se sofrer um preempção por prioridade.
Escalonamento por Prioridades
Estado de
Término
Filas dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Estado de
Criação
Cap. 8 – Gerência do Processador 42
UCP Término
Prioridade Pn
Criação
Estado de
Espera
Preempção por prioridade
Escalonamento por Prioridades
• Exemplo, onde 5 é o valor de maior 
prioridade
Processo A
Processo B
Processo
Tempo de
processador
(u.t.)
A 10
Prioridade
2
Cap. 8 – Gerência do Processador 43
Processo B
Processo C
3 13 17 u.t.
A
B
C
10
4
3
2
1
3
Escalonamento por Prioridades
• Este escalonamento também pode ser 
implementado de forma não-preemptiva;
• Assim, os processos que passam para o 
estado de pronto com prioridade maior que o 
processo em execução, não geram 
preempção por prioridade, são apenas 
Cap. 8 – Gerência do Processador 44
preempção por prioridade, são apenas 
colocados no início da fila de pronto;
• Cada S.O.implementa a sua faixa de valores 
para a prioridade, que podem ser:
– Valores maiores, maior prioridade;
– Valores menores, maior prioridade;
Escalonamento por Prioridades
• Open VMS, a prioridade varia de 0 a 31, 
onde 31 é a maior prioridade;
• No IBM-AIX, a prioridade vária de 0 a 127, 
onde zero é a maior prioridade;
• A prioridade de execução é uma 
característica do contexto de software e pode 
Cap. 8 – Gerência do Processador 45
característica do contexto de software e pode 
ser:
– Estática, seu valor não é alterado durante a 
execução do programa; 
– Dinâmica, seu valor pode ser ajustado de acordo 
com o S.O., permitindo ajustar o critério de 
escalonamento de função do comportamento de 
cada processo no sistema;
Escalonamento por Prioridades
• Um dos principais problema deste 
escalonamento é o starvation;
– Processos de baixa prioridade podem não 
ser escalonados;
– Uma solução para este problema é 
Cap. 8 – Gerência do Processador 46
– Uma solução para este problema é 
incrementar gradualmente a prioridade de 
processos que permanecem muito tempo 
na fila de pronto, esta técnica é chamada 
de aging;
Escalonamento por Prioridades
• Usando este escalonamento é possível 
diferenciar os processos por critérios 
de importância;
• Este tipo de escalonamento é bastante 
útil em sistemas de tempo real e nas 
Cap. 8 – Gerência do Processador 47
útil em sistemas de tempo real e nas 
aplicações de controle de processos e 
também em sistemas de tempo 
compartilhado, quando se precisa 
priorizar o escalonamento de 
determinados processos;
Escalonamento Circular com 
Prioridades
• Este escalonamento implementa o 
conceito de fatia de tempo e de 
prioridade de execução associada a 
cada processo;
• Um processo permanece em estado de 
Cap. 8 – Gerência do Processador 48
• Um processo permanece em estado de 
execução:
– Até o fim do seu processamento;
– Voluntariamente passa ao estado de 
espera;
– Preempção por tempo;
– Preempção por prioridade;
Escalonamento Circular com 
Prioridades
Estado de
Término
Fila dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Estado de
Criação
Cap. 8 – Gerência do Processador 49
UCP Término
Prioridade Pn
Criação
Estado de
Espera
Preempção por tempo ou prioridade
Escalonamento Circular com 
Prioridades
• A principal vantagem é permitir o 
melhor balanceamento, e priorizar os 
processos;
• É utilizando, amplamente, em sistemas 
de tempo compartilhado;
Cap. 8 – Gerência do Processador 50
de tempo compartilhado;
Escalonamento por Múltiplas Filas
• No escalonamento por múltiplas filas 
(multilevel queue scheduling) existem 
diversas filas de processo no estado de 
pronto, cada uma com sua prioridade;
• Os processos são associados as filas 
Cap. 8 – Gerência do Processador 51
• Os processos são associados as filas 
em função de características, como:
– Importância da aplicação;
– Tipo de processamento;
– Área de memória necessária;
Escalonamento por Múltiplas Filas
• Como os processos possuem características 
diferentes é pouco provável que um único 
mecanismo de escalonamento seja adequado 
para todos;
• A sua principal vantagem é a possibilidade da 
convivência de mecanismos de 
Cap. 8 – Gerência do Processador 52
convivência de mecanismos de 
escalonamento distintos em um único S.O.;
• Cada fila possui um escalonador próprio, 
permitindo, por exemplo, que alguns 
processos sejam escalonados pelo FIFO e 
outros pelo circular;
Escalonamento por Múltiplas Filas
• Este mecanismo, o processo não possui 
prioridade, ficando esta característica 
associada a fila;
• O processo em execução sofre preempção 
caso outro processo entre em uma fila de 
maior prioridade;
Cap. 8 – Gerência do Processador 53
maior prioridade;
• Só se pode escalonar um processo de uma 
determina fila caso as filas de maior 
prioridade estejam vazias;
• Uma boa prática é classificar os processos 
em função do tipo de processamento;
Escalonamento por Múltiplas Filas
• Para exemplificar – próximo slide:
– Processos divididos em três grupos, 
listados pela ordem de prioridade:
•Sistema – maior prioridade, escalonador 
baseado em prioridades;
Cap. 8 – Gerência do Processador 54
• Interativo – prioridade intermediária, 
escalonamento circular;
•Bath – menor prioridade, escalonamento 
circurlar (o mesmo do interativo, porém 
de menor prioridade);
Escalonamento por Múltiplas Filas
Fila de processos do sistema
Fila de processos interativos
Maior
prioridade
Cap. 8 – Gerência do Processador 55
UCP
Fila de processos batch
Menor
prioridade
Escalonamento por Múltiplas Filas
• Uma desvantagem com este 
escalonamento, é que se o processo 
mudar o seu comportamento não pode 
mudar de fila;
• A associação do processo com a fila é 
Cap. 8 – Gerência do Processador 56
• A associação do processo com a fila é 
executada na criação do processo, 
permanecendo até o término do seu 
processamento;
Escalonamento por Múltiplas Filas com 
Realimentação
• No escalonamento por múltiplas filas 
com realimentação (multilevel 
feedback queues scheduling) é 
semelhante ao escalonamento por 
múltiplas filas, porém os processos 
podem mudar de fila durante o 
Cap. 8 – Gerência do Processador 57
podem mudar de fila durante o 
processamento;
• Sua grande vantagem é permitir ao 
S.O. identificar o comportamento do 
processo e redirecioná-lo a fila mais 
adequada (considerando a prioridade e 
tipo de escalandor);
Escalonamento por Múltiplas Filas com 
Realimentação
• Este escalonamento permite que os 
processos sejam redirecionados entre 
diversas filas, permitindo ao S.O. 
implementar um mecanismo de ajuste 
dinâmico denominado mecanismo 
Cap. 8 – Gerência do Processador 58
dinâmico denominado mecanismo 
adaptativo; 
• Os processos não são previamente 
associados a fila de pronto, mas 
direcionados para as filas existentes 
com base no seu comportamento;
Escalonamento por Múltiplas Filas com 
Realimentação
• Um mecanismo FIFO adaptado com 
fatia de tempo é usado com 
escalonador em todas as filas, com 
exceção da fila de menor prioridade, 
que utiliza o escalonador