Sistemas Operacionais: Processos e Escalonamento

Prévia do material em texto

T164s Tanenbaum, Andrewa S.
 Sistemas operacionais [recurso eletrônico] : projeto e
 implementação / Andrew S. Tanenbaum, Albert S. Woodhull ;
 tradução João Tortello. – 3. ed. – Dados eletrônicos. – Porto
 Alegre : Bookman, 2008.
 Editado também como livro impresso em 2008.
 ISBN 978-85-7780-285-2
 1. Sistemas operacionais. I. Woodhull, Albert S. II. Título.
 CDU 004.4
Catalogação na publicação: Mônica Ballejo Canto – CRB 10/1023
CAPÍTULO 2 • PROCESSOS 103
em vez de ser admitido imediatamente. Dessa maneira, um escritor precisa esperar o término 
dos leitores que estavam ativos quando ele chegou, mas não precisa esperar os leitores que 
apareceram depois dele. A desvantagem dessa solução é que ela gera menos concorrência e, 
portanto, tem desempenho inferior. Courtois et al. apresentam uma solução que dá prioridade 
aos escritores. Para ver os detalhes, sugerimos a leitura desse artigo.
 2.4 ESCALONAMENTO
Nos exemplos das seções anteriores, com freqüência tivemos situações em que dois ou mais 
processos (por exemplo, produtor e consumidor) eram logicamente executáveis. Quando um 
computador tem suporte a multiprogramação, freqüentemente ele tem vários processos com-
petindo pela CPU ao mesmo tempo. Quando mais de um processo está no estado pronto e 
existe apenas uma CPU disponível, o sistema operacional deve decidir qual deles vai executar 
primeiro. A parte do sistema operacional que faz essa escolha é chamada de escalonador; o 
algoritmo que ele utiliza é chamado de algoritmo de escalonamento.
Muitos problemas de escalonamento se aplicam tanto aos processos como as threads. 
Inicialmente, focalizaremos o escalonamento de processos, mas posteriormente examinare-
mos rapidamente alguns problemas específi cos ao escalonamento de threads.
 2.4.1 Introdução ao escalonamento
Na época dos sistemas de lote, com entrada na forma de uma fi ta magnética, o algoritmo de 
escalonamento era simples: apenas executar o próximo job da fi ta. Nos sistemas com compar-
tilhamento de tempo, o algoritmo de escalonamento se tornou mais complexo, pois geralmen-
te havia vários usuários esperando o serviço. Também pode haver um ou mais fl uxos de lote 
(por exemplo, em uma companhia de seguros, para processar pedidos). Em um computador 
pessoal, você poderia pensar que haveria apenas um processo ativo. Afi nal, é improvável que 
um usuário digitando um documento em um processador de textos esteja simultaneamente 
compilando um programa em segundo plano. Entretanto, freqüentemente existem tarefas de 
segundo plano, como daemons de correio eletrônico enviando ou recebendo e-mail. Você 
também poderia pensar que os computadores fi caram tão mais rápidos com o passar dos anos, 
que a CPU raramente teria falta de recursos. Contudo, os aplicativos novos tendem a exigir 
mais recursos. Exemplo disso é o processamento digital de fotografi as e a exibição de vídeo 
em tempo real.
Comportamento dos processos
Praticamente todos os processos alternam rajadas de computação com requisições de E/S 
(disco), como mostra a Figura 2-22. Normalmente, a CPU executa por algum tempo sem 
parar e, depois, é feita uma chamada de sistema para ler ou escrever em um arquivo. Quando 
a chamada de sistema termina, a CPU computa novamente, até precisar de mais dados ou 
ter de escrever mais dados e assim por diante. Note que algumas atividades de E/S contam 
como computação. Por exemplo, quando a CPU copia dados de uma memória de vídeo para 
atualizar a tela, ela está computando e não fazendo E/S, pois a CPU está sendo usada. Nesse 
sentido, a E/S se dá quando um processo entra no estado bloqueado esperando que um dispo-
sitivo externo conclua seu trabalho.
O importante a notar na Figura 2-22 é que alguns processos, como o que aparece na 
Figura 2-22(a), passam a maior parte de seu tempo computando, enquanto outros, como o 
que aparece na Figura 2-22(b), passam a maior parte de seu tempo esperando por E/S. Os pri-
meiros são chamados de processos limitados por processamento (CPU-bound); os últimos 
104 SISTEMAS OPERACIONAIS
são chamados de processos limitados por E/S (I/O-bound). Os processos limitados por pro-
cessamento normalmente têm longas rajadas de uso de CPU e raramente esperam pela E/S, 
enquanto os processos limitados por E/S têm curtas rajadas de uso de CPU curtas e esperas 
freqüentes por E/S. Note que o principal fator é o comprimento da rajada de uso de CPU e 
não o comprimento da rajada de E/S. Os processos limitados por E/S são classifi cados como 
tal não por terem requisições de E/S particularmente longas, mas sim por não executarem 
muita computação entre elas. O tempo para ler um bloco de disco é sempre o mesmo, inde-
pendente de se gastar muito ou pouco tempo para processar os dados lidos.
Rajada longa de CPU
Rajada curta de CPU
Esperando por E/S
(a) 
(b) 
Tempo
Figura 2-22 As rajadas de utilização de CPU alternam com períodos de espera por E/S. (a) 
Um processo vinculado à CPU. (b) Um processo limitado por E/S.
É interessante notar que, à medida que as CPUs se tornam mais rápidas, os processos 
tendem a fi car limitados por E/S. Esse efeito ocorre porque as CPUs estão evoluindo muito 
mais rapidamente do que os discos. Como conseqüência, o escalonamento de processos limita-
dos por E/S provavelmente se tornará um assunto bem mais importante no futuro. A idéia bási-
ca aqui é que, se um processo limitado por E/S quiser ser executado, deverá ter uma chance de 
fazê-lo rapidamente, para que possa emitir sua requisição ao disco e mantê-lo ocupado.
Quando fazer o escalonamento
Existe uma variedade de situações nas quais o escalonamento pode ocorrer. Primeiramente, o 
escalonamento é absolutamente exigido em duas ocasiões:
 1. Quando um processo termina.
 2. Quando um processo é bloqueado em uma operação de E/S ou em um semáforo.
Em cada um desses casos, o processo que estava em execução se torna não apto a conti-
nuar, de modo que outro processo deva ser escolhido para executar em seguida.
Existem três outras ocasiões em que o escalonamento é normalmente feito, embora, 
logicamente falando, não seja absolutamente necessário nesses momentos:
 1. Quando um novo processo é criado.
 2. Quando ocorre uma interrupção de E/S.
 3. Quando ocorre uma interrupção de relógio.
No caso de um novo processo, faz sentido reavaliar as prioridades nesse momento. Em 
alguns casos, o processo pai pode solicitar uma prioridade diferente para o processo fi lho.
CAPÍTULO 2 • PROCESSOS 105
No caso de uma interrupção de E/S, isso normalmente signifi ca que um dispositivo de 
E/S acabou de concluir seu trabalho. Assim, algum processo que estava bloqueado, esperando 
pela E/S, poderá agora estar pronto (ou apto) para executar.
No caso de uma interrupção de relógio, essa é uma oportunidade para decidir se o pro-
cesso que está correntemente em execução já está executando por um tempo demasiado. Os 
algoritmos de escalonamento podem ser divididos em duas categorias, com relação ao modo 
como tratam das interrupções de relógio. Um algoritmo de escalonamento não-preemptivo 
seleciona um processo para executar e, em seguida, permite que ele seja executado até ser 
bloqueado (ou no caso de uma E/S ou na espera por outro processo) ou até que libere a CPU 
voluntariamente. Em contraste, um algoritmo de escalonamento preemptivo seleciona um 
processo e permite que ele seja executado por algum tempo fi xo máximo. Se o processo 
ainda estiver em execução no fi nal do intervalo de tempo, ele será suspenso e o escalonador 
selecionará outro processo para executar (se houver um disponível). O escalonamento pre-
emptivo exige a ocorrência de uma interrupção de relógio no fi nal do intervalo de tempo, para 
devolver o controle da CPU para o escalonador. Se não houver nenhum relógio disponível, a 
escalonamento não-preemptivo será a única opção.
Categorias de algoritmos de escalonamento
Evidentemente, em diferentes ambientes, são necessários diferentes algoritmos de escalo-
namento. Essa situação surge porque as diferentesáreas de aplicação (e diferentes tipos de 
sistemas operacionais) têm objetivos diversos. Em outras palavras, o que o escalonador deve 
otimizar não é a mesma coisa em todos os sistemas. É importante distinguir três ambientes:
 1. Lote
 2. Interativo
 3. Tempo real
Nos sistemas de lote, não há usuários esperando impacientemente uma resposta rápida 
em seus terminais. Conseqüentemente, com freqüência são aceitáveis algoritmos não-pre-
emptivos ou algoritmos preemptivos com longos períodos de tempo para cada processo. Essa 
estratégia reduz as trocas de processo e, assim, melhora o desempenho.
Em um ambiente com usuários interativos, a preempção é fundamental para impedir 
que um processo aproprie-se de todo o tempo de CPU e negue serviço para os outros. Mes-
mo que nenhum processo seja executado para sempre intencionalmente devido a um erro 
de programa, um único processo poderia barrar os outros indefi nidamente. A preempção é 
necessária para evitar esse comportamento.
Nos sistemas com restrições de tempo real, às vezes, a preempção é, estranhamente, 
desnecessária, pois os processos sabem que não podem ser executados por longos períodos de 
tempo e normalmente fazem seu trabalho e são rapidamente bloqueados. A diferença com os 
sistemas interativos é que os sistemas de tempo real executam apenas os programas necessá-
rios a uma aplicação em particular. Já os sistemas interativos são de propósito geral e podem 
executar qualquer tipo de programa, inclusive os que são mal-intencionados.
Objetivos dos algoritmos de escalonamento
Para projetar um algoritmo de escalonamento, é necessário ter alguma idéia do que um bom 
algoritmo deve fazer. Alguns objetivos dependem do ambiente (lote, interativo ou tempo 
real), mas também existem outros que são desejáveis para todos os casos. Alguns objetivos 
estão listados na Figura 2-23. A seguir, os discutiremos cada um deles.
106 SISTEMAS OPERACIONAIS
Todos os sistemas
Imparcialidade – dar a cada processo o mesmo tempo de uso de CPU
Imposição da política – garantir que a política declarada é executada
Balanceamento de carga – manter todas as partes do sistema ocupadas
Sistemas de lote
Taxa de saída – maximizar o número de jobs por hora
Tempo de retorno – minimizar o tempo entre envio e término
Utilização da CPU – manter a CPU ocupada o máximo de tempo possível
Sistemas interativos
Tempo de resposta – atender rapidamente as requisições
Proporcionalidade —satisfazer às expectativas dos usuários
Sistemas de tempo real
Cumprir os prazos fi nais – evitar a perda de dados
Previsibilidade – evitar degradação da qualidade em sistemas multimídia
Figura 2-23 Alguns objetivos dos algoritmos de escalonamento sob diferentes circuns-
tâncias.
Sob todas as circunstâncias, a imparcialidade é importante. Processos comparáveis de-
vem receber serviço comparável. Dar para um processo muito mais tempo de CPU do que 
para outro equivalente não é justo. Naturalmente, diferentes categorias de processos podem 
ser tratadas de formas diferentes. Pense no controle de segurança e no processamento da fo-
lha de pagamento do centro de computação de um reator nuclear.
Um tanto relacionada com a imparcialidade é a imposição das políticas do sistema. Se 
a política local diz que os processos de controle de segurança devem ser executados quando 
quiserem, mesmo que isso signifi que que a folha de pagamento seja atrasada em 30 segundos, 
o escalonador precisa garantir que essa política seja imposta.
Outro objetivo geral é manter todas as partes do sistema ocupadas, quando possível. 
Se a CPU e todos os dispositivos de E/S puderem ser mantidos ocupados o tempo todo, será 
feito, por segundo, mais trabalho do que se alguns dos componentes estiverem ociosos. Em 
um sistema de lote, por exemplo, o escalonador tem controle sobre quais tarefas são levadas à 
memória para execução. Ter alguns processos vinculados à CPU e alguns processos limitados 
por E/S em memória é uma idéia melhor do que primeiro carregar e executar todas as tarefas 
vinculadas à CPU e, depois, quando elas tiverem terminado, carregar e executar todas as ta-
refas vinculadas à E/S. Se esta última estratégia for usada, quando os processos vinculados à 
CPU estiverem em execução, eles lutarão pela CPU e o disco estará ocioso. Posteriormente, 
quando as tarefas vinculadas à E/S entrarem em ação, elas disputarão o disco e a CPU estará 
ociosa. É melhor manter o sistema todo em funcionamento simultaneamente, por meio de 
uma mistura cuidadosa de processos.
Os gerentes dos centros de computação corporativos que executam muitas tarefas de 
lote (por exemplo, processamento de pedidos de companhias de seguro), normalmente exa-
minam três métricas para avaliarem o desempenho de seus sistemas: taxa de saída (throu-
ghput), tempo de retorno (turnaround) e utilização da CPU. A taxa de saída é o número de 
jobs por segundo que o sistema conclui. Considerando tudo os fatores, concluir 50 jobs por 
segundo é melhor do que concluir 40 jobs por segundo. Tempo de retorno é o tempo médio 
desde o momento em que um job do lote é submetido até o momento em que ele é concluído. 
Ele mede o tempo que o usuário médio precisa esperar pela saída. Aqui, a regra é: quanto 
menor, melhor.
CAPÍTULO 2 • PROCESSOS 107
Um algoritmo de escalonamento que maximiza a taxa de saída pode não necessaria-
mente minimizar o tempo de retorno. Por exemplo, dada uma mistura de jobs curtos e longos, 
um escalonador que sempre executasse os jobs curtos e nunca os jobs longos poderia obter 
uma taxa de saída excelente (muitos jobs curtos por segundo), mas à custa de um tempo de 
retorno terrível para os jobs longos. Se jobs curtos continuassem chegando constantemente, 
os jobs longos poderiam nunca ser executados, tornando o tempo de retorno médio infi nito, 
embora obtivesse uma taxa de saída alta.
A utilização da CPU também é um problema nos sistemas de lote porque, nos compu-
tadores de grande porte, onde os sistemas de lote são executados, a CPU ainda tem um custo 
alto. Assim, os gerentes dos centros de computação se sentem culpados quando ela não está 
executando o tempo todo. Na verdade, contudo, essa não é uma boa métrica. O que realmente 
importa é quantos jobs por segundo saem do sistema (taxa de saída) e quanto tempo demora 
para retornar um job (tempo de retorno). Usar a utilização da CPU como métrica é como 
classifi car carros tendo por base o giro do motor por segundo.
Para sistemas interativos, especialmente sistemas de compartilhamento de tempo e ser-
vidores, diferentes objetivos se aplicam. O mais importante é minimizar o tempo de respos-
ta, que é o tempo entre a execução de um comando e o recebimento de seu resultado. Em um 
computador pessoal, onde está sendo executado um processo de segundo plano (por exemplo, 
lendo e armazenando e-mail na rede), o pedido de um usuário para iniciar um programa ou 
abrir um arquivo deve ter precedência sobre o trabalho de segundo plano. O fato de ter todos 
os pedidos interativos atendidos primeiro será percebido como um bom serviço.
Um problema relacionado é o que poderia ser chamado de proporcionalidade. Os 
usuários têm uma idéia básica (mas freqüentemente incorreta) do tempo que as coisas devem 
demorar. Quando um pedido que é percebido como complexo demora um longo tempo, os 
usuários aceitam isso, mas quando um pedido que é percebido como simples demora um 
longo tempo, os usuários fi cam irritados. Por exemplo, se clicar em um ícone que ativa um 
provedor de Internet usando um modem analógico demorar 45 segundos para estabelecer a 
conexão, o usuário provavelmente aceitará isso como um fato normal. Por outro lado, se cli-
car em um ícone para desfazer uma conexão demorar 45 segundos, o usuário provavelmente 
estará dizendo palavrões na marca dos 30 segundos e, decorridos 45 segundos, já estará espu-
mando de raiva. Esse comportamento é devido à percepção comum do usuário de que fazer 
uma ligação telefônica e estabelecer uma conexão provavelmente demora muito mais do que 
apenas desligar.Em alguns casos (como neste), o escalonador não pode fazer nada a respeito 
do tempo de resposta, mas em outros casos, ele pode, especialmente quando o atraso é devido 
a uma escolha malfeita na ordem dos processos.
Os sistemas de tempo real têm propriedades diferentes dos sistemas interativos e, as-
sim, diferentes objetivos de escalonamento. Eles são caracterizados por terem prazos fi nais 
que devem ou pelo menos deveriam ser cumpridos. Por exemplo, se um computador está 
controlando um dispositivo que produz dados a uma velocidade regular, o fato de deixar de 
executar o processo de coleta de dados pontualmente pode resultar na sua perda. Assim, a 
principal necessidade em um sistema de tempo real é cumprir todos os prazos fi nais (ou a 
maioria deles).
Em alguns sistemas de tempo real, especialmente aqueles que envolvem multimídia, a 
previsibilidade é importante. Perder um prazo fi nal ocasional não é fatal, mas se o processo 
de áudio for executado muito irregularmente, a qualidade do som se deteriorará rapidamente. 
O vídeo também é um problema, mas os ouvidos são muito mais sensíveis à fl utuação de fase 
do que os olhos. Para evitar esse problema, a escalonamento dos processos deve ser altamente 
previsível e regular.
108 SISTEMAS OPERACIONAIS
 2.4.2 Escalonamento em sistemas de lote
Agora é hora de examinarmos os problemas gerais de algoritmos de escalonamento especí-
fi cos. Nesta seção, veremos os algoritmos usados nos sistemas de lote. Nas seguintes, exa-
minaremos os sistemas interativos e de tempo real. Vale notar que alguns algoritmos são 
usados tanto em sistemas de lote como em sistemas interativos. Vamos estudar estes últimos 
posteriormente. Aqui, focalizaremos os algoritmos que são convenientes apenas nos sistemas 
de lote.
O primeiro a chegar é o primeiro a ser atendido
Provavelmente, o mais simples de todos os algoritmos de escalonamento é o não-preemptivo 
primeiro a chegar é o primeiro a ser atendido* (First-come First-served FCFS). Nesse 
algoritmo, os processos recebem tempo de CPU na ordem em que solicitam. Basicamente, 
existe uma única fi la de processos prontos (aptos a executar). Quando, de manhã, o primeiro 
job entra no sistema, ele é iniciado imediatamente e pode ser executado durante o tempo que 
quiser. Quando outros jobs chegam, eles são colocados no fi nal da fi la. Quando o proces-
so que está em execução é bloqueado, o primeiro processo da fi la é executado em seguida. 
Quando um processo bloqueado se torna pronto, assim como um job recém-chegado, é colo-
cado no fi nal da fi la.
A maior vantagem desse algoritmo é que ele é fácil de ser entendido e igualmente fácil 
de programar. Ele também é imparcial, da mesma forma que é justo vender entradas para 
jogos ou concertos muito concorridos para as pessoas que estejam dispostas a fi car na fi la às 
2 da manhã. Com esse algoritmo, uma lista encadeada simples mantém todos os processos 
prontos. Selecionar um processo para executar exige apenas remover um do início da fi la. 
Adicionar uma nova tarefa ou um processo que acaba de ser desbloqueado exige apenas inse-
ri-lo no fi nal da fi la. O que poderia ser mais simples?
Infelizmente, o algoritmo do primeiro a chegar é o primeiro a ser atendido também 
tem uma grande desvantagem. Suponha que exista um único processo limitado por proces-
samento que seja executado por 1 segundo a cada vez e muitos processos limitados por E/S 
que utilizam pouco tempo da CPU, mas cada um tendo que realizar 1000 leituras de disco 
para terminar. O processo limitado por processamento é executado por 1 segundo e, em se-
guida, lê um bloco de disco. Agora, todos os processos de E/S são executados e começam as 
leituras de disco. Quando o processo limitado por processamento recebe seu bloco de disco, 
é executado por mais 1 segundo, seguido de todos os processos limitados por E/S, em uma 
rápida sucessão.
O resultado fi nal é que cada processo limitado por E/S lê 1 bloco por segundo e demora 
1000 segundos para terminar. Se fosse usado um algoritmo de escalonamento que fi zesse a 
preempção do processo limitado por processamento a cada 10 ms, os processos limitados por 
E/S terminariam em 10 segundos, em vez de 1000 segundos, e sem diminuir muito a veloci-
dade do processo limitado por processamento.
Tarefa mais curta primeiro
Examinemos agora outro algoritmo não-preemptivo para sistemas de lote que presume que 
os tempos de execução são conhecidos antecipadamente. Em uma companhia de seguros, por 
exemplo, as pessoas podem prever precisamente quanto tempo levará para executar um lote 
de 1.000 pedidos, pois um trabalho semelhante é feito todos os dias. Quando várias tarefas 
 * N. de R.T.: Esse algoritmo também é denominado de primeiro a chegar, primeiro a sair (First-In, First-Out ou, simplesmente, 
FIFO).
CAPÍTULO 2 • PROCESSOS 109
igualmente importantes estão na fi la de entrada esperando para serem iniciadas, o escalona-
dor seleciona a tarefa mais curta primeiro (Shortest Job First - SJF). Veja a Figura 2-24. 
Aqui, encontramos quatro jobs A, B, C e D, com tempos de execução de 8, 4, 4 e 4 minutos, 
respectivamente. Executando-as nessa ordem, o tempo de retorno para A é de 8 minutos, para 
B é de 12 minutos, para C é de 16 minutos e para D é de 20 minutos, dando uma média de 14 
minutos.
(a)
8
A
4
B
4
C
4
D
(b)
8
A
4
B
4
C
4
D
Figura 2-24 Um exemplo de escalonamento com a tarefa mais curta primeiro. (a) Executan-
do quatro jobs na ordem original. (b) Executando-as na ordem do job mais curto primeiro.
Agora, consideremos a execução desses quatro jobs utilizando o algoritmo da tarefa 
mais curta primeiro, como mostrado na Figura 2-24(b). Os tempos de retorno agora são de 4, 
8, 12 e 20 minutos, para uma média de 11 minutos. O algoritmo da tarefa mais curta primeiro 
provavelmente é ótimo. Considere o caso de quatro jobs, com tempos de execução de a, b, c e 
d, respectivamente. O primeiro job acaba no tempo a, o segundo no tempo a + b e assim por 
diante. O tempo de retorno médio é (4a + 3b + 2c + d)/4. É claro que a contribui mais para 
a média do que os outros tempos; portanto, ele deve ser o job mais curto, com b vindo em 
seguida, depois c e, fi nalmente, d como a mais longo, pois ele afeta apenas seu próprio tempo 
de retorno. O mesmo argumento aplica-se igualmente bem a qualquer número de jobs.
É interessante notar que o algoritmo da tarefa mais curta primeiro é ótimo apenas quan-
do todos os jobs estão disponíveis simultaneamente. Como um contra-exemplo, considere 
cinco jobs, de A a E, com tempos de execução de 2, 4, 1, 1 e 1, respectivamente. Seus tempos 
de chegada são 0, 0, 3, 3 e 3. Inicialmente, apenas A ou B podem ser escolhidos, pois os ou-
tros três jobs ainda não chegaram. Usando o algoritmo da tarefa mais curta primeiro, executa-
remos os jobs na ordem A, B, C, D, E, para uma espera média de 4,6. Entretanto, executá-los 
na ordem B, C, D, E, A corresponde a uma espera média de 4,4.
Menor tempo de execução restante
Uma versão preemptiva do algoritmo da tarefa mais curta primeiro é o algoritmo do Me-
nor tempo de execução restante (Shortest Remaining Time Next – SRT). Nesse algoritmo, 
o escalonador sempre escolhe o processo (ou job) cujo tempo de execução restante é o 
mais curto. Aqui, novamente, o tempo de execução precisa ser conhecido antecipadamente. 
Quando chega um novo job, seu tempo total é comparado com o tempo restante do processo 
corrente. Se o novo job precisar de menos tempo para terminar do que o processo corrente, 
este será suspenso e a novo job será iniciado. Este esquema permite que os novos jobs curtos 
recebam um bom serviço.
Escalonamento em três níveis
Sob certo aspecto, os sistemas de lote permitem escalonar processos em três níveis diferentes, 
conforme ilustrado na Figura 2-25. Quando os jobs chegam no sistema, eles são colocados 
inicialmente em uma fi la de entrada armazenada em disco. O escalonador de admissão deci-
de quais jobs ingressarão no sistema. Os outros são mantidos na fi la de entradaaté que sejam 
selecionados. Um algoritmo de controle de admissão típico poderia procurar uma mistura de 
110 SISTEMAS OPERACIONAIS
jobs limitados por processamento e jobs limitados por E/S. Como alternativa, os jobs curtos 
poderiam ser admitidos rapidamente, enquanto os jobs mais longos teriam de esperar. O es-
calonador de admissão está livre para manter alguns jobs na fi la de entrada e admitir jobs que 
cheguem depois, se optar por isso.
CPU
Escalonador
da memória
Job
chegando
Fila de
entrada
Escalonador
de admissão
Memória
principal
Disco
Escalonamento da CPU
Figura 2-25 Escalonamento em três níveis.
Quando um job for admitido no sistema, um processo poderá ser criado para ele e 
poderá competir pela CPU. Entretanto, poderia ser que o número de processos fosse tão 
grande que não haveria espaço sufi ciente para todos eles em memória. Nesse caso, alguns 
dos processos teriam que ser postos no disco. O segundo nível de escalonamento é decidir 
quais processos devem ser mantidos em memória e quais devem ser mantidos no disco. Isso 
é chamado de escalonador da memória, pois ele determina quais processos são mantidos na 
memória e quais são mantidos no disco.
Essa decisão precisa ser freqüentemente revista para permitir que os processos que es-
tão no disco recebam algum serviço. Entretanto, como trazer um processo do disco é dispen-
dioso, essa revisão não deve acontecer mais do que uma vez por segundo, talvez com menos 
freqüência ainda. Se o conteúdo da memória principal é trocado com muita freqüência com 
o do disco, isso implica em um consumo de uma grande quantidade de largura de banda de 
disco, diminuindo a velocidade da E/S de arquivos. Essa alternância entre estar em memória 
principal e estar armazenado no disco é denominado de swapping.
Para otimizar o desempenho do sistema como um todo, o escalonador da memória tal-
vez queira decidir cuidadosamente quantos processos deseja ter na memória (o que é chama-
do de grau de multiprogramação) e quais tipos de processos. Se ele tiver informações sobre 
quais processos são limitados por processamento e quais são limitados por E/S, poderá tentar 
manter uma mistura desses tipos de processo na memória. Como uma aproximação muito 
grosseira, se determinada classe de processos computa cerca de 20% do tempo, deixar cinco 
deles juntos é aproximadamente o número certo para manter a CPU ocupada.
Para tomar suas decisões, o escalonador da memória revê periodicamente cada processo 
no disco para decidir se vai levá-lo para a memória ou não. Dentre os critérios que ele pode 
usar para tomar sua decisão estão os seguintes:
 1. Quanto tempo passou desde que o processo sofreu swap (entrou ou saiu)?
 2. Quanto tempo de CPU o processo recebeu recentemente?
CAPÍTULO 2 • PROCESSOS 111
 3. Qual é o tamanho do processo? (Os pequenos não atrapalham.)
 4. Qual é a importância do processo?
O terceiro nível de escalonamento é a seleção de um dos processos prontos, armazena-
dos na memória principal, para ser executado em seguida. Freqüentemente, ele é chamado de 
escalonador da CPU e é o que as pessoas normalmente querem dizer quando falam sobre 
“escalonador”. Qualquer algoritmo pode ser usado aqui, tanto preemptivo como não-preemp-
tivo. Eles incluem aqueles descritos anteriormente, assim como vários algoritmos que serão 
descritos na próxima seção.
 2.4.3 Escalonamento em sistemas interativos
Veremos agora alguns algoritmos que podem ser usados em sistemas interativos. Todos eles 
também podem ser usados como escalonador da CPU em sistemas de lote. Embora a escalo-
namento de três níveis não seja possível aqui, o escalonamento de dois níveis (escalonador da 
memória e escalonador da CPU) é comum. A seguir, focalizaremos o escalonador da CPU e 
alguns algoritmos de escalonamento mais empregados.
Escalonamento round-robin
Vamos ver agora alguns algoritmos de escalonamento específi cos. Um dos algoritmos mais 
antigos, mais simples e mais amplamente utilizados é feito um rodízio entre os processos 
(escalonamento round-robin – RR). A cada processo é atribuído um intervalo de tempo, cha-
mado de quantum, durante o qual ele pode ser executado. Se o processo estiver em execução 
no fi m do quantum, é feita a preempção da CPU e esta é alocada a outro processo. É claro 
que, se o processo tiver sido bloqueado, ou terminado, antes do quantum ter expirado, a troca 
da CPU será feita neste momento. O round-robin é fácil de implementar. Tudo que o escalo-
nador precisa fazer é manter uma lista de processos executáveis, como mostrado na Figura 
2-26(a). Quando o processo consome seu quantum, ele é colocado no fi m da lista, como se 
vê na Figura 2-26(b)
(a)
Processo
corrente
B F D G A
(b)
Processo
corrente
Próximo
processo
F D G A B
Figura 2-26 Escalonamento round-robin. (a) A lista de processos executáveis. (b) A lista de 
processos executáveis após B consumir seu quantum.
O único problema interessante relacionado ao round-robin é a duração do quantum. 
Trocar de um processo para outro exige certa quantidade de tempo para fazer a administração 
– salvar e carregar registradores e mapas de memória, atualizar várias tabelas e listas, esvaziar 
e recarregar a cache de memória etc. Suponha que esse chaveamento de processo ou chave-
amento de contexto, como às vezes é chamado, demore 1 ms, incluindo a troca de mapas de 
memória, esvaziar e recarregar a cache etc. Suponha também que o quantum seja confi gurado 
como 4 ms. Com esses parâmetros, depois de fazer 4 ms de trabalho útil, a CPU terá de gastar 
1 ms na troca (chaveamento) de processos. 20% do tempo da CPU serão desperdiçados em 
sobrecarga administrativa. Claramente, isso é demais.
112 SISTEMAS OPERACIONAIS
Para melhorar a efi ciência da CPU, poderíamos confi gurar o quantum como, digamos, 
100 ms. Agora, o tempo desperdiçado é de apenas 1%. Mas considere o que acontece em 
um sistema de compartilhamento de tempo, se dez usuários interativos pressionarem a tecla 
enter mais ou menos ao mesmo tempo. Dez processos serão colocados na lista de processos 
prontos. Se a CPU estiver ociosa, o primeiro processo começará imediatamente, o segundo 
poderá começar somente 100 ms depois e assim por diante. O infeliz último da fi la talvez 
tenha de esperar 1 segundo antes de ter uma chance, supondo que todos os outros utilizem 
seus quanta inteiros. A maioria dos usuários achará lenta uma resposta de 1 s para um co-
mando curto.
Outro fator é que, se o quantum for confi gurado com um valor maior do que a rajada 
média de CPU, a preempção raramente acontecerá. Em vez disso, a maioria dos processos 
executará uma operação de bloqueio, antes que o quantum termine, causando a troca de pro-
cesso. Eliminar a preempção melhora o desempenho, pois as trocas de processo só ocorrerão 
quando elas forem logicamente necessárias; isto é, quando um processo for bloqueado e não 
puder continuar porque está logicamente esperando por algo.
A conclusão pode ser formulada como segue: confi gurar o quantum curto demais causa 
muita troca de processo e reduz a efi ciência da CPU, mas confi gurá-lo longo demais pode 
causar um tempo de resposta ruim para pedidos interativos curtos. Um quantum em torno de 
20-50 ms freqüentemente é um compromisso razoável.
Escalonamento por prioridade
O escalonamento round-robin faz a suposição implícita de que todos os processos são igual-
mente importantes. Com freqüência, as pessoas que possuem e operam computadores multiu-
suários têm idéias diferentes sobre esse assunto. Em uma universidade, a ordem da prioridade 
pode ser os diretores primeiro, depois os professores, secretários, inspetores e, fi nalmente, 
os alunos. A necessidade de levar em conta fatores externos conduz ao escalonamento por 
prioridade. A idéia básica é simples: cada processo recebe uma prioridade e o processo pron-
to, com a prioridade mais alta, tem permissão para executar.
Mesmo em um PC com um único proprietário, pode haver múltiplos processos, alguns 
mais importantes do que outros. Por exemplo,um processo daemon que envia uma mensa-
gem de correio eletrônico em segundo plano deve receber uma prioridade mais baixa do que 
a de um processo que exibe um fi lme na tela em tempo real.
Para impedir que os processos de alta prioridade sejam executados indefi nidamente, 
o escalonador pode diminuir a prioridade do processo correntemente em execução em cada 
tique de relógio (isto é, a cada interrupção de relógio). Se essa ação fi zer com que sua prio-
ridade caia abaixo da do próximo processo com maior prioridade, ocorrerá um chaveamento 
de processo. Como alternativa, cada processo pode receber um quantum de tempo máximo 
em que ele pode ser executado. Quando esse quantum esgota, é dada a chance de executar ao 
próximo processo com maior prioridade.
As prioridades podem ser atribuídas aos processos estática ou dinamicamente. No com-
putador de um ambiente militar, os processos iniciados pelos generais poderiam começar 
com prioridade 100, os processos iniciados pelos coronéis, com 90, pelos majores, 80, pe-
los capitães, 70, pelos tenentes, 60 e assim por diante. Como alternativa, em um centro de 
computação comercial, as tarefas de alta prioridade poderiam custar 100 dólares por hora, 
os de prioridade média, 75 dólares por hora, e os de baixa prioridade, 50 dólares por hora. 
O sistema UNIX tem um comando, nice, que permite ao usuário reduzir voluntariamente a 
prioridade de seu processo, para ser gentil com os outros usuários. Ninguém o utiliza.
As prioridades também podem ser atribuídas dinamicamente pelo sistema, para atender 
certos objetivos. Por exemplo, alguns processos são altamente limitados por E/S e gastam a 
CAPÍTULO 2 • PROCESSOS 113
maior parte do seu tempo esperando a E/S terminar. Quando um processo assim quer a CPU, 
deve recebê-la imediatamente para permitir que ele inicie sua próxima requisição de E/S, a 
qual pode então prosseguir em paralelo com outro processo que realmente faz computação. 
Fazer com que o processo limitado por E/S espere um longo tempo pela CPU signifi cará 
apenas que ele ocupará a memória por um tempo desnecessariamente longo. Um algoritmo 
simples para oferecer bom serviço para processos limitados por E/S é confi gurar a priorida-
de como 1/f, onde f é a fração do último quantum utilizado por um processo. Um processo 
que utilizasse apenas 1 ms de seu quantum de 50 ms receberia prioridade 50, enquanto um 
processo que executasse 25 ms antes de bloquear receberia prioridade 2 e um processo que 
utilizou o quantum inteiro receberia prioridade 1.
Muitas vezes é conveniente agrupar processos em classes de prioridade e utilizar esca-
lonamento por prioridade entre as classes, mas escalonamento round-robin dentro de cada 
classe. A Figura 2-27 mostra um sistema com quatro classes de prioridade. O algoritmo de es-
calonamento é o seguinte: enquanto houver processos executáveis na classe de prioridade 4, 
executa cada um apenas por um quantum, no sistema round-robin, e nunca se incomoda com 
as classes de prioridade mais baixa. Se a classe de prioridade 4 estiver vazia, então executa 
os processos de classe 3 no sistema round-robin. Se as classes 4 e 3 estiverem vazias, então 
executa a classe 2 no sistema de round-robin e assim por diante. Se as prioridades não forem 
ajustadas ocasionalmente, as classes de prioridade mais baixa poderão sofrer inanição.
Prioridade 4
Prioridade 3
Prioridade 2
Prioridade 1
Cabeça
da fila
Processos executáveis
(Prioridade mais alta)
(Prioridade mais baixa)
Figura 2-27 Um algoritmo de escalonamento com quatro classes de prioridade.
O MINIX 3 usa um sistema semelhante à Figura 2-27, embora existam 16 classes de 
prioridade na confi guração padrão. No MINIX 3, os componentes do sistema operacional 
são executados como processos. O MINIX 3 coloca as tarefas (drivers de E/S) e servidores 
(gerenciador de memória, sistema de arquivos e rede) nas classes de prioridade mais alta. A 
prioridade inicial de cada tarefa ou serviço é defi nida no momento da compilação; a E/S de 
um dispositivo lento pode receber prioridade mais baixa do que a E/S de um dispositivo mais 
rápido ou mesmo de um servidor. Geralmente, os processos de usuário têm prioridade mais 
baixa do que os componentes de sistema, mas todas as prioridades podem mudar durante a 
execução.
Escalonamento por múltiplas fi las
Um dos primeiros escalonadores por prioridade estava no CTSS (Corbató et al., 1962). O 
CTSS tinha o problema de que o chaveamento de processos era muito lento porque o 7094 
podia armazenar apenas um processo na memória. Cada troca signifi cava enviar o processo 
corrente para o disco e ler um novo processo do disco. Os projetistas do CTSS rapidamente 
perceberam que era mais efi ciente dar um quantum grande para processos limitados por pro-
cessamento, de vez em quando, em vez de freqüentemente dar pequenos quanta (para reduzir 
114 SISTEMAS OPERACIONAIS
as trocas). Por outro lado, dar a todos os processos um quantum grande poderia signifi car 
um péssimo tempo de resposta, como já observamos. A solução foi confi gurar classes de 
prioridade. Os processos de classe mais alta eram executados por um quantum. Os processos 
na classe de prioridade mais alta seguinte eram executados por dois quanta. Os processos na 
próxima classe eram executados por quatro quanta e assim por diante. Quando um processo 
utilizava todos os quanta permitidos, ele era movido uma classe para baixo.
Como exemplo, considere um processo que precisasse computar continuamente por 
100 quanta. Inicialmente, ele receberia um quantum e, então, seria trocado. Da próxima vez, 
ele receberia dois quanta antes de ser trocado. Em sucessivas execuções, ele poderia receber 
4, 8, 16, 32 e 64 quanta, embora tivesse utilizado apenas 37 dos 64 quanta fi nais para com-
pletar seu trabalho. Apenas 7 trocas seriam necessárias (incluindo o carregamento inicial), 
em vez de 100, com um algoritmo round-robin puro. Além disso, à medida que o processo 
se baixasse cada vez mais nas fi las de prioridade, ele seria executado cada vez com menos 
freqüência, poupando a CPU para processos interativos curtos.
A seguinte política foi adotada para impedir que um processo que ao ser iniciado pela 
primeira vez necessitasse ser executado durante um longo tempo, mas se tornasse interativo 
posteriormente, fosse eternamente penalizado. Quando a tecla enter era pressionada em um 
terminal, o processo pertencente a esse terminal era movido para a classe de prioridade mais 
alta, supondo-se que ele estava para tornar-se interativo. Um belo dia, um usuário com um 
processo intensamente vinculado à CPU descobriu que o simples fato de pressionar enter vá-
rias vezes, aleatoriamente, melhorava seu tempo de resposta. Ele contou isso a todos os seus 
amigos. Moral da história: na prática, acertar é muito mais difícil do que na teoria.
Muitos outros algoritmos foram usados para atribuir classes de prioridade aos proces-
sos. Por exemplo, o infl uente sistema XDS 940 (Lampson, 1968), construído em Berkeley, 
tinha quatro classes de prioridade, chamadas terminal, E/S, quantum curto e quantum longo. 
Quando um processo que estava esperando uma entrada de terminal era fi nalmente desper-
tado, ele entrava na classe de maior prioridade (terminal). Quando um processo que estava 
esperando um bloco de disco tornava-se pronto, ele entrava na segunda classe. Quando um 
processo ainda estava em execução quando seu quantum esgotava, ele era inicialmente colo-
cado na terceira classe. Entretanto, se um processo esgotasse seu quantum muitas vezes se-
guidas, sem bloquear para terminal ou para outra operação de E/S, ele era movido para o fi nal 
da fi la. Muitos outros sistemas utilizam algo semelhante para favorecer usuários e processos 
interativos em detrimento dos processos que estão em segundo plano.
Processo mais curto em seguida
Como o algoritmo da tarefa mais curta primeiro (SJF – Shortest Job First) sempre produz 
o menor tempo médio de resposta para sistemas de lote, seria interessante se ele tambémpudesse ser usado para processos interativos. Até certo ponto, ele pode ser usado. Os proces-
sos interativos geralmente seguem o padrão de esperar comando, executar comando, esperar 
comando, executar comando e assim por diante. Se considerássemos a execução de cada co-
mando como uma “tarefa” separada, poderíamos então minimizar o tempo de resposta total, 
executando o processo mais curto primeiro (Shortest Process Next – SPN). O único problema 
é descobrir qual dos processos correntemente executáveis é o mais curto.
Uma estratégia é fazer estimativas com base no comportamento passado e executar 
o processo com o menor tempo de execução estimado. Suponha que o tempo estimado por 
comando para um terminal seja T0. Agora, suponha que sua próxima execução seja medida 
como T1. Poderíamos atualizar nossa estimativa usando uma soma ponderada desses dois 
números; isto é, aT0+ (1-a)T1. Pela escolha de a podemos fazer o processo de estimativa ig-
CAPÍTULO 2 • PROCESSOS 115
norar as execuções antigas rapidamente ou lembrar delas durante muito tempo. Com a = 1/2, 
obtemos sucessivas estimativas de
T0, T0/2 + T1/2, T0/4 + T1/4 + T2/2, T0/8 + T1/8 + T2/4 + T3/2
Após três novas execuções, o peso de T0 na nova estimativa caiu para 1/8.
Às vezes, a técnica de estimar o próximo valor em uma série usando a média ponderada 
do valor corrente medido e a estimativa anterior é chamada de envelhecimento. Ela é apli-
cável a muitas situações onde deve ser feita uma previsão com base em valores anteriores. O 
envelhecimento é particularmente fácil de implementar quando a = 1/2. Basta somar o novo 
valor à estimativa corrente e dividir a soma por 2 (deslocando-o 1 bit para a direita).
Escalonamento garantido
Uma estratégia completamente diferente de escalonamento é fazer promessas realistas aos 
usuários sobre o desempenho e, então, cumpri-las. Uma promessa realista e fácil de cumprir: 
se houver n usuários conectados enquanto você estiver trabalhando, você receberá cerca de 
1/n do poder da CPU. De maneira semelhante, em um sistema monousuário com n processos 
em execução, todas as tarefas sendo iguais, cada uma deve receber 1/n dos ciclos da CPU.
Para cumprir essa promessa, o sistema deve monitorar quanto da CPU cada processo 
recebeu desde a sua criação. Então, ele calcula quanto da CPU é atribuído a cada um; isto é, 
o tempo desde a criação dividido por n. Como a quantidade de tempo da CPU que cada pro-
cesso realmente recebeu também é conhecida, é simples calcular a proporção entre o tempo 
real da CPU consumido e o tempo da CPU atribuído. Uma proporção de 0,5 signifi ca que um 
processo só recebeu metade do que devia ter recebido e uma proporção de 2,0 signifi ca que 
um processo recebeu o dobro do tempo que lhe foi atribuído. O algoritmo, então, é executar o 
processo com a proporção mais baixa até que sua proporção fi que acima do seu concorrente 
mais próximo.
Escalonamento por sorteio
Embora fazer promessas aos usuários e cumpri-las seja uma boa idéia, é difícil implemen-
tá-las. Entretanto, outro algoritmo pode ser utilizado para fornecer resultados previsíveis de 
maneira semelhante, com uma implementação muito mais simples. Ele é chamado de escalo-
namento por sorteio (Waldspurger e Weihl, 1994).
A idéia básica é dar aos processos “bilhetes de loteria” para os vários recursos do sis-
tema, como o tempo de CPU. Quando uma decisão de escalonamento tiver de ser tomada, 
um “bilhete de loteria” é sorteado aleatoriamente e o processo que possui esse bilhete recebe 
o recurso. Quando aplicado ao escalonamento da CPU, o sistema pode realizar sorteios 50 
vezes por segundo, com cada vencedor recebendo como prêmio 20 ms do tempo da CPU.
Parafraseando George Orwell, “todos os processos são iguais, mas alguns são mais 
iguais”. Os processos mais importantes podem receber bilhetes extras, para aumentar suas 
chances de ganhar. Se houver 100 bilhetes concorrendo e um processo tiver 20 deles, ele terá 
20% de chance de ganhar em cada sorteio. A longo prazo, ele receberá aproximadamente 
20% da CPU. Em contraste com um escalonador por prioridade, onde é muito difícil dizer o 
que uma prioridade de 40 signifi ca realmente, aqui a regra é clara: um processo contendo uma 
fração f dos bilhetes receberá cerca de uma fração f do recurso em questão.
O escalonamento por sorteio tem algumas propriedades interessantes. Por exemplo, se 
um novo processo aparece e recebe alguns bilhetes, no próximo sorteio ele terá uma chance 
de ganhar proporcional ao número de bilhetes que possui. Em outras palavras, o escalona-
mento por sorteio é altamente sensível.
116 SISTEMAS OPERACIONAIS
Processos cooperativos podem trocar bilhetes se quiserem. Por exemplo, quando um 
processo cliente envia uma mensagem para um processo servidor e, então, é bloqueado, ele 
pode dar todos os seus bilhetes para o servidor, para aumentar a chance de o servidor ser 
executado em seguida. Quando o servidor tiver terminado, ele devolverá os bilhetes para que 
o cliente possa ser executado novamente. Na verdade, na ausência de clientes, os servidores 
não precisam de nenhum bilhete.
O escalonamento por sorteio pode ser usado para resolver problemas difíceis de lidar 
com outros métodos. Um exemplo é um servidor de vídeo onde vários processos estão en-
viando seqüências de vídeo para seus clientes, mas em diferentes velocidades de projeção. 
Suponha que os processos precisem de velocidades de 10, 20 e 25 quadros/s. Alocando para 
esses processos 10, 20 e 25 bilhetes, respectivamente, eles dividirão a CPU na proporção 
correta automaticamente; isto é, 10:20:25.
Escalonamento com compartilhamento imparcial
Até aqui, supomos que cada processo é programado para executar por conta própria, sem 
considerar quem é seu proprietário. Como resultado, se o usuário 1 inicia 9 processos e o 
usuário 2 inicia 1 processo, com os algoritmos round-robin ou de prioridades iguais, o usuá-
rio 1 receberá 90% da CPU e o usuário 2 receberá apenas 10% dela.
Para evitar essa situação, alguns sistemas levam em conta quem possui um processo, 
antes de escalonar sua execução. Nesse modelo, cada usuário recebe uma fração da CPU e 
o escalonador seleciona os processos de maneira a impor essa fração. Assim, se foram pro-
metidos 50% da CPU a dois usuários, cada um receberá isso, independentemente de quantos 
processos tiverem iniciado.
Como exemplo, considere um sistema com dois usuários, cada um com promessa de 
50% da CPU. O usuário 1 tem quatro processos, A, B, C e D, e o usuário 2 tem apenas 1 pro-
cesso, E. Se for usado o escalonamento round-robin, uma possível seqüência de execução que 
atende todas as restrições é a seguinte:
A E B E C E D E A E B E C E D E ...
Por outro lado, se o usuário 1 recebesse duas vezes o tempo da CPU em relação ao 
usuário 2, poderíamos obter:
A B E C D E A B E C D E ...
É claro que existem muitas outras possibilidades que podem ser exploradas, dependen-
do de qual seja a noção de imparcialidade.
 2.4.4 Escalonamento em sistemas de tempo real
Um sistema de tempo real é aquele em que o tempo desempenha um papel fundamental. 
Normalmente, um ou mais dispositivos físicos externos ao computador geram estímulos e o 
computador deve interagir apropriadamente a eles, dentro de um período de tempo fi xo. Por 
exemplo, o computador em um CD player recebe os bits à medida que eles vêm da unidade 
de disco e precisa convertê-los em música dentro de um intervalo de tempo limitado. Se o cál-
culo demorar muito, a música soará estranha. Outros sistemas de tempo real servem para mo-
nitorar pacientes na unidade de terapia intensiva de um hospital, para piloto automático em 
uma aeronave e para controle de robôs em uma fábrica automatizada. Em todos esses casos, 
receber a resposta certa, mas muito tarde, freqüentemente é tão ruim quanto não recebê-la.
Os sistemas de tempo real geralmente são classifi cados como de tempo real rígido, 
(hard real time) signifi cando que há prazos fi nais absolutos a serem cumpridos, e de tempo 
CAPÍTULO 2 • PROCESSOS117
real relaxado ou não-rígido (soft real time), signifi cando que perder um prazo fi nal ocasio-
nalmente é indesejável, mas tolerável. Em ambos os casos, o comportamento de tempo real 
é obtido dividindo-se o programa em vários processos, cujo comportamento é previsível e 
conhecido antecipadamente. Geralmente, esses processos têm vida curta e podem ser execu-
tados até o fi m em menos de um segundo. Quando um evento externo é detectado, é tarefa 
do escalonador agendar a execução dos processos de tal maneira que todos os prazos fi nais 
sejam cumpridos.
Os eventos a que um sistema de tempo real responde podem ser classifi cados mais espe-
cifi camente como periódicos (ocorrendo em intervalos regulares) ou aperiódicos (ocorrendo 
de maneira imprevisível). Um sistema pode ter de responder a vários fl uxos de evento perió-
dicos. Dependendo de quanto tempo cada evento exigir para processamento, talvez nem seja 
possível tratar de todos eles. Por exemplo, se houver m eventos periódicos e o evento i ocorrer 
com um período Pi e exigir Ci segundos de tempo da CPU para tratar de cada evento, então a 
carga só poderá ser manipulada se
C
P
i
ii
m
≤
=
∑ 1
1
Um sistema tempo real que satisfaz esse critério é conhecido como sistema escalonável.
Como exemplo, considere um sistema de tempo real não-rígido com três eventos perió-
dicos, com períodos de 100, 200 e 500 ms, respectivamente. Se esses eventos exigirem 50, 30 
e 100 ms de tempo de CPU por evento, respectivamente, o sistema será escalonável porque 
0,5 + 0,15 + 0,2 < 1. Se for adicionado um quarto evento, com um período de 1 s, o sistema 
continuará sendo escalonável, desde que esse evento não precise de mais de 150 ms de tempo 
de CPU por ocorrência. Nesse cálculo, está implícita a suposição de que a sobrecarga de cha-
veamento de contexto é tão pequena que pode ser ignorada.
Os algoritmos de escalonamento de tempo real podem ser estáticos ou dinâmicos. O 
primeiro toma suas decisões de escalonamento antes que o sistema comece a executar. O úl-
timo toma suas decisões de escalonamento em tempo de execução. O escalonamento estático 
só funciona quando existem, antecipadamente, informações disponíveis confi áveis sobre o 
trabalho necessário a ser feito e todos os prazos fi nais que precisam ser cumpridos. Os algo-
ritmos de escalonamento dinâmicos não têm essas restrições.
 2.4.5 Política versus mecanismo
Até agora, admitimos tacitamente que todos os processos no sistema pertencem a usuários 
diferentes e assim estão competindo pela CPU. Embora isso freqüentemente seja verdadeiro, 
às vezes acontece de um processo ter muitos fi lhos executando sob seu controle. Por exemplo, 
um processo de sistema de gerenciamento de banco de dados pode criar muitos fi lhos. Cada 
fi lho pode estar trabalhando em um pedido diferente ou cada um pode ter alguma função 
específi ca para executar (análise de consulta, acesso a disco etc.). É plenamente possível que 
o processo principal tenha uma excelente noção de quais de seus fi lhos são os mais impor-
tantes (ou os mais críticos quanto ao tempo) e quais são menos importantes. Infelizmente, 
nenhum dos escalonadores discutidos anteriormente aceita qualquer informação de processos 
de usuário sobre decisões de escalonamento. Como resultado, o escalonador raramente faz a 
melhor escolha.
A solução para esse problema é separar o mecanismo de escalonamento da políti-
ca de escalonamento. Isso signifi ca que o algoritmo de escalonamento é parametrizado 
de alguma maneira, mas os parâmetros podem ser fornecidos pelos processos de usuário. 
118 SISTEMAS OPERACIONAIS
Consideremos novamente o exemplo do banco de dados. Suponha que o núcleo utilize um 
algoritmo de escalonamento por prioridade, mas forneça uma chamada de sistema por meio 
da qual um processo pode confi gurar (e alterar) as prioridades de seus fi lhos. Assim, o pai 
pode controlar com detalhes como seus fi lhos são postos em execução, mesmo que não faça 
a escalonamento em si. Aqui, o mecanismo está no núcleo, mas a política é confi gurada por 
um processo de usuário.
 2.4.6 Escalonamento de threads
Quando vários processos têm múltiplas threads cada um, temos dois níveis de paralelismo 
presentes: processos e threads. O escalonamento em tais sistemas difere substancialmente, 
dependendo se as threads são suportadas em nível de usuário ou em nível de núcleo (ou 
ambos).
Vamos considerar primeiro as threads em nível de usuário. Como o núcleo não tem co-
nhecimento da existência de threads, ele funciona normalmente, selecionando um processo, 
digamos, A, e dando a esse processo o controle de seu quantum. Dentro do processo A existe 
um escalonador de threads que seleciona qual thread vai executar, digamos, A1. Como não 
existem interrupções de relógio para multiprogramar as threads, essa thread pode continuar 
executando o quanto quiser. Se ela consumir o quantum inteiro do processo, o núcleo selecio-
nará outro processo para executar.
Quando o processo A fi nalmente for executado outra vez, a thread A1 retomará sua 
execução. Ela continuará a consumir todo o tempo de A, até que termine. Entretanto, seu 
comportamento anti-social não afetará outros processos. Eles receberão o que o escalonador 
considerar como sua fatia apropriada, independente do que estiver acontecendo dentro do 
processo A.
Agora, considere o caso em que as threads de A têm relativamente pouco trabalho a 
fazer por rajada de CPU, por exemplo, 5 ms de trabalho, dentro de um quantum de 50 ms. 
Conseqüentemente, cada uma deles é executada por um pouco de tempo e, então, devolve a 
CPU para o escalonador de threads. Isso poder levar à seqüência A1, A2, A3, A1, A2, A3, A1, 
A2, A3, A1, antes do núcleo comutar para o processo B. Essa situação está ilustrada na Figura 
2-28(a).
Processo A Processo B Processo BProcesso A
1. O núcleo seleciona
 um processo
1. O núcleo seleciona
 uma thread
Possível: A1, A2, A3, A1, A2, A3
Também possível: A1, B1, A2, B2, A3, B3
Possível: A1, A2, A3, A1, A2, A3
Impossível: A1, B1, A2, B2, A3, B3
(a) (b)
Ordem em
que as threads 
são executadas
2. O escalo-
nador em 
nível de
usuário
(runtime)
seleciona
uma thread
1 2 3 1 3 2
Figura 2-28 (a) Possível escalonamento de threads em nível de usuário com um quantum 
de processo de 50 ms e threads executando 5 ms por rajada de CPU. (b) Possível escalona-
mento de threads em nível de núcleo com as mesmas características de (a).