Modulo 02 - Escalonamento da CPU v6

Prévia do material em texto

SOA
1
Silberschatz, Galvin, and GagneSistemas Operacionais
Módulo 6: Escalonamento de CPU
• Conceitos Básicos
• Critério de Escalonamento
• Algoritmos de Escalonamento
Silberschatz, Galvin, and GagneSistemas Operacionais
Era uma vez...
• Os computadores faziam uma coisa por vez.
DECK de 
cartões 
perfurados
Listagem 
com 
resultados
Silberschatz, Galvin, and GagneSistemas Operacionais
Pessoas
Segundos-Depois do almoço…
Era uma vez...
• Os computadores faziam uma coisa por vez.
• Há uma grande diferença entre a velocidade do 
processador e a velocidade do mundo externo.
Periféricos
Micro-Milissegundos
Processadores
Nano-segundos
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de CPU
• O escalonador de CPU define a sequência de “ações” que 
determinam o interleave (intercalação) das threads.
– Programas utilizam sincronização a fim de prevenir 
“ações nocivas”.
– …entretanto as escolhas do escalonamento aparentam 
(para o programa) ser não-determinísticas.
• As ações do escalonador são ditadas por uma política de 
escalonamento.
Fila de jobs 
prontos
Acordou ou
Pronto para
executar
Seleciona próximo 
a ser executado()
Chaveia
processo()
Silberschatz, Galvin, and GagneSistemas Operacionais
Objetivos do Escalonador
– Tempo de resposta ou latência
 Quanto tempo o programa demorará para fazer o que eu 
quero?
– Throughput (vazão)
 Quantas operações são completadas por unidade de tempo ? 
 Utilização: que porcentagem de tempo a CPU (e cada 
dispositivo) consome fazendo algo útil ? 
– Justiça
 O que significa ? Dividir a torta em partes iguais ? Garantir 
baixa variação nos tempos de resposta ? Livre de starvation
(ou inanição) ?
 Cumprir com os tempos e garantir repetibilidade de tasks
(tarefas) periódicas
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonadores de Processos
Fila Prontos
Solicitação de I/O
Expira Time Slice
Cria proc. Filho
Aguarda por uma 
Interrupção
Filho Executa
Interrupção Ocorre
I/O Fila de I/O
CPU
Escalonador 
de longo 
prazo injeta 
jobs
Processo Parcialmente Executado
que sofreu Swap
SOA
2
Silberschatz, Galvin, and GagneSistemas Operacionais
Process Control Block (PCB ou BCP)
Número do Processo
Program Counter
Inf. Estado de I/O
Ponteiro
Registradores
Limites de Memória
Informações Contábeis
Estado do 
Processo
Inf. Escalonamento
O Bloco de Controle do Processo é uma estrutura de dados no núcleo do 
sistema operacional que serve para armazenar a informação necessária 
para tratar um determinado processo. É utilizado para representar 
um processo dentro do sistema operacional
Silberschatz, Galvin, and GagneSistemas Operacionais
Process Control Block
enum state_type {new, ready, running, waiting, 
halted};
typedef struct _control_block 
{
struct control_block *next_pcb;
enum state_type state;
int pid;
address PC;
int reg_file[NumRegs];
int priority;
address page_table;
...
} control_block;
Silberschatz, Galvin, and GagneSistemas Operacionais
Prioridade
• Alguns objetivos podem ser atingidos incorporando a noção de 
prioridade numa metodologia de escalonamento básica.
 Cada job da fila de processos prontos tem associado um 
valor de prioridade, que o favorece em relação aos processos 
de menor prioridade.
• Valores de prioridade externos :
– Impostos ao sistema pelo usuário, administrador, ou 
projetista;
– Refletem as preferências externas para um particular usuário 
ou tasks:
 “Todos os jobs são iguais, mas alguns jobs são mais 
iguais que outros.”
Exemplo: System Call nice do Unix, para diminuir a 
prioridade de uma task.
Exemplo: Tasks urgentes de um sistema de controle em 
tempo real.
Silberschatz, Galvin, and GagneSistemas Operacionais
Prioridade Interna 
• Prioridade Interna: O sistema ajusta os valores de prioridade 
internamente por meio de uma técnica de implementação
incorporada ao escalonador. 
 Melhora a igualdade, utilização de recursos, diminui o perigo de 
starvation (ou inanição);
– Abaixa a prioridade de jobs consumindo mais que eles 
compartilham; 
– Aumenta a prioridade de jobs que estão prendendo recursos que 
estão em falta:
 Ex.: primitiva do interna Unix sleep
– Incentiva jobs que estiveram em starvation num passado recente;
– Proporcionam um reajuste contínuo e dinâmico em resposta às 
condições e eventos observados:
 Pode ser visível e controlável por outras partes do sistema
Silberschatz, Galvin, and GagneSistemas Operacionais
Preempção
• As políticas do Scheduler (ou escalonador) podem ser 
preemptivas ou não-preemptivas.
– Preemptiva: o scheduler pode unilateralmente forçar 
uma task (tarefa ou processo) a liberar o processador 
antes que a task bloqueie, suspenda, ou finalize.
– Timeslicing impede os jobs de monopolizarem a CPU
Escalonador escolhe um job e o processa por um 
quantum do tempo de CPU.
Um job executando por mais tempo que seu quantum 
é forçado a interromper seu processamento por meio 
de código de tratamento de interrupção de relógio no 
scheduler.
– Utiliza-se preempção para honrar a prioridade:
Preempta (retira da CPU) um job se um outro de 
maior prioridade passar ao estado pronto
Silberschatz, Galvin, and Gagne
Conceito de Escalonamento
 Escalonamento consiste em determinar, dentre os processos 
prontos, qual o próximo processo a ser executado;
 Realizado por um componente do sistema operacional 
denominado escalonador;
Principais objetivos:
 Maximizar a utilização do processador;
 Maximizar o número de processos completados por 
unidade de tempo;
 Garantir que todos os processos recebam o processador;
 Minimizar o tempo de resposta para o usuário.
 Dois tipos de escalonadores:
 Longo prazo;
 Curto prazo.
SOA
3
Silberschatz, Galvin, and Gagne
Escalonadores
• Escalonador ou Scheduler
– Seleciona um processo de um conjunto.
• Escalonador de Longo Prazo (ou escalonador de job): 
seleciona qual processo deve ser colocado na fila de 
processos prontos
• É invocado com pouca frequência (segundos, minutes)  (pode ser lento)
• Controla o grau de multiprogramação.
• Escalonador de Curto Prazo (ou escalonador de CPU): 
seleciona qual processo vai ser o próximo a ser 
executado e aloca a CPU
– É invocado frequentemente (milissegundos)  (necessita ser rápido)
– Por exemplo, após uma solicitação de I/O ou Interrupção
– Às vezes é o único escalonador de um sistema.
Silberschatz, Galvin, and Gagne
Lista de PCBs dos Estados de Pronto e Espera
........
........
........
........
........
Lista de
processos
em estado
de pronto
PCB# 5
PCB# 9
PCB# 1
PCB# 2 PCB# 4
Lista de
processos
em estado
de espera
Silberschatz, Galvin, and Gagne
Conceito de Escalonamento
 Uma visão dos escalonadores do sistema operacional
Longo-Prazo
Fila de Prontos
Fila
Espera
I/O
CPU
Curto-Prazo
FIM
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento Não-Preemptivo
Fila Prontos
Solicitação de I/O
Expirou Time Slice
Cria proc. Filho
Aguarda por uma 
Interrupção
Filho Executa
Interrupção Ocorre
I/O Fila de I/O
CPU
Escalonador 
de longo 
prazo injeta 
jobs Processo tem o controle da CPU
ate que ele abandone-a voluntariamente
Processo tem o controle da CPU
ate que ele abandone-a voluntariamente
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento Preemptivo
Fila Prontos
Solicitação de I/O
Expirou Time Slice
Cria proc. Filho
Aguarda por uma 
Interrupção
Filho Executa
Interrupção Ocorre
I/O Fila de I/O
CPU
Escalonador 
de longo 
prazo injeta 
jobs Processos podem ser 
forçados a abandonar a CPU.
Processos podem ser 
forçados a abandonar a CPU.
Escalonador 
de curto 
prazo
Silberschatz, Galvin, and GagneSistemas Operacionais
Conceitos Básicos
• Utilização máxima da CPU é obtida com multiprogramação;
• CPU–I/O Burst Cycle – Execução do processo consiste de 
um ciclo de: execução de CPU e espera de E/S;
• Distribuição CPU burst (Picos de CPU);
•Burst Cycle (ciclo de surto) - Tempo que a CPU está em 
efetivo atendimento (processando) a um processo.
SOA
4
Silberschatz, Galvin, and GagneSistemas Operacionais
Alternância de surto (burst) de CPU e de E/S
Silberschatz, Galvin, and GagneSistemas Operacionais
CPU-I/O Burst Cycle (ou Ciclo de CPU e ciclo de E/S)
Executa
Aguarda por I/O
CPU
Bound
I/O
Bound
Silberschatz, Galvin, and GagneSistemas Operacionais
Diagrama de estados de um processo
Novo
Waiting
Pronto
Encerrado
Executando
criação
interrupção
fim
aguardando I/O 
ou evento
conclusão de I/O 
ou evento
Escolhido
pelo 
escalonador
Silberschatz, Galvin, and Gagne
Ativação do Escalonador
• Um novo processo é criado e passa para estado de pronto;
• Um processo terminou sua execução e um processo 
pronto deve ser executado;
• Um processo é bloqueado (dependência de E/S)=> outro 
deve ser executado;
• Quando ocorre uma interrupção de E/S, o escalonador 
deve decidir por:
– Executar o processo que estava esperando esse 
evento;
– Continuar executando o processo que já estava sendo 
executado.
Sistemas Operacionais
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de CPU
• Seleciona dentre os processos na memória, aqueles que estão 
prontos para executar e aloca a CPU para um deles. 
• As decisões de escalonamento da CPU são realizadas quando o 
processo:
1. Troca do estado de execução para o de espera
2. Troca do estado de execução para o de pronto para executar
3. Troca do estado de espera para o de pronto para executar
4. Termina
• Escalonamento para 1 e 4 é não-preemptivo. Processo libera a 
CPU voluntariamente.
• Todo os outros escalonamentos são preemptivos.
Silberschatz, Galvin, and Gagne
Mudança de Contexto de Processo
Carrega registradores do
Processo B
Carrega registradores do
Processo A
Sistema Operacional
Salva registradores do
Processo A
executando
executando
executando
Salva registradores do
Processo B
Processo A Processo B
SOA
5
Silberschatz, Galvin, and GagneSistemas Operacionais
Dispatcher - Despachador
• O módulo Dispatcher dá o controle da CPU para o processo 
selecionado pelo escalonamento de curto-prazo (short-
term). Isto consiste de:
– troca de contexto;
– alterar para modo usuário (já que o dispatcher roda no 
modo supervisor );
– pula para o lugar (endereço) adequado do programa do 
usuário, para dar inicio a sua execução;
• Dispatch latency (ou tempo de latência do despachante) –
tempo que leva para o dispatcher parar um processo e 
iniciar outro.
Silberschatz, Galvin, and GagneSistemas Operacionais
Critério de escalonamento
• Utilização da CPU – Manter a CPU ocupada o maior tempo possível
• Throughput (Razão de finalização)– número de processos que 
completam sua execução por unidade de tempo
• Tempo de espera – Tempo que um processo permanece em espera 
na fila de prontos
• Turnaround time (Tempo de tempo de retorno ou tempo de 
permanência ou tempo de circulação)– Tempo necessário para 
executar um processo em particular. É dado pela soma do soma do 
tempo de espera com o tempo de execução.
• Tempo de resposta – Tempo que leva entre uma requisição ser 
submetida até a primeira resposta ser produzida, não é a saída 
completa do processo (para ambientes de tempo compartilhado)
Silberschatz, Galvin, and GagneSistemas Operacionais
Critério de Otimização
•Utilização máxima da CPU
•Maximizar throughput (vazão)
•Minimizar turnaround time 
•Minimizar Tempo de espera
•Minimizar Tempo de resposta
•Ou seja: A otimização é atingida com o 
equilíbrio dessas prioridades.
Silberschatz, Galvin, and Gagne
Ex.: Processo P2
Instante 
de 
submissão
P1 P2 P3
24 27 300
Tempo
De 
Espera
Tempo de 
Turnaround
(tempo de espera + 
tempo de execução) 
Tempo de 
Resposta
do P2 
Silberschatz, Galvin, and Gagne
• Ferramenta de escalonamento visual ;
• Trata-se de um método gráfico ( um tipo de 
gráfico de barras horizontal) baseado numa 
escala de tempo, mostrando o 
escalonamento ao longo do tempo das 
várias atividades que compõem uma tarefa;
• Mostra as dependências entre atividades, 
pessoas e outros recursos na sua alocação;
• Possibilita o traceamento até a finalização.
Gantt Chart
Silberschatz, Galvin, and Gagne
• Iniciado em 1916 por Henry Laurence Gantt, um engenheiro 
americano, para gerenciar o desempenho dos equipamentos;
• Faça os eixos um gráfico com escala de tempo na 
horizontal, e desenhe um bloco para representar cada 
atividade a partir do seu instante de inicio até o seu 
término.
• Considerando que serão executados três processos 
segundo a ordem, P1, P2 e P3, com duração de 24, 3 e 4 
unidades e tempo, o gráfico de Gantt será:
Gantt Chart (cont.)
P1 P2 P3
24 27 300
SOA
6
Silberschatz, Galvin, and GagneSistemas Operacionais
Algoritmos de Escalonamento
•O escalonamento de CPU lida com o 
problema de decidir a quais processos na 
fila de processos prontos, a CPU deverá 
ser alocada;
•Existem muitos algoritmos diferentes de 
escalonamento de CPU.
Silberschatz, Galvin, and Gagne
Objetivos gerais do escalonamento
• Sistemas não interativos (em lote ou batch):
– Maximizar o número de tarefas por unidade de tempo (vazão ou 
throughput);
– Minimizar o tempo entre submissão e término (tempo de retorno ou 
turnaround);
– Minimizar o tempo no estado apto (tempo de espera ou waiting time);
– Manter a CPU ocupada a maior parte do tempo.
• Sistemas interativos:
– Responder rapidamente as requisições (tempo de resposta ou response
time);
– Satisfazer as expectativas dos usuários (proporcionalidade, ou seja, 
tempo esperado para executar uma tarefa).
• Sistemas de tempo real:
– Cumprir prazos no atendimento de eventos;
– Previsibilidade ou determinismo.
Sistemas Operacionais
Ainda: Justiça 
Respeitar 
políticas locais 
Equilíbrio.
Silberschatz, Galvin, and Gagne
 Ou Primeiro a Chegar, Primeiro a Ser Atendido; 
 Ou First-In-First-Out (FIFO);
 Não preemptivo por definição;
 Primeiro processo da fila é o primeiro a ser 
executado;
 Processos usam a CPU até terminar todo 
processamento;
 Mesmo com alguma intercalação, processos com 
menor prioridade podem prejudicar os processos 
com maior prioridade;
 Inversão de prioridade;
 Starvation ou inanição;
Escalonamento First-Come, First-Served (FCFS)
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento First-Come, First-Served (FCFS), ou 
First-In-First-Out (FIFO)
• Exemplo: Processo Burst Time
P1 24
P2 3
P3 3
• Suponha que os processos chegaram na ordem: P1 , P2 , P3 
O Gantt Chart (Gráfico de Gantt) para esse escalonamento é:
•
• Tempo de espera para: P1 = 0; P2 = 24; P3 = 27
• Tempo de espera médio: (0 + 24 + 27)/3 = 17
P1 P2 P3
24 27 300
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento FCFS (Cont.)
Agora, suponha que os processos chegaram na ordem
P2 , P3 , P1 .
• O Gantt Chart para o escalonamento passa a ser:
• Tempo de espera para P1 = 6; P2 = 0 ; P3 = 3
• Tempo de espera médio: (6 + 0 + 3)/3 = 3
• Muito melhor que o caso anterior.
• Efeito de conjunto: processo pequeno (em tempo de execução) 
após um processo longo. 
P1P3P2
63 300
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo FCFS
Processo
(Ordem)
Burst Time
Instante cheg.
P1 P2 P3
20 3 3
0 0 0
P1 P2 P3
0 20 23 26
Tempo médio de espera = 
(0 + 20 + 23) / 3 = 14,3
Processo
(Ordem)
Burst Time
Instante cheg.
P3 P2 P1
3 3 20
0 1 2
P1P3 P2
0 3 6 26
Tempo médio de espera = 
(0 + 2 + 4) / 3 = 2
Exemplo 2
SOA
7
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento FCFS (Cont.)
• Facilmente implementado por uma fila FIFO;
– Quando um processo entra na fila de processos 
prontos, seu PCB é ligado ao final da fila;
– Quando a CPU é liberada, ela é alocada ao processo 
cujo PCB encontra-se no início da fila;
• O algoritmo de escalonamento FCFS é não-preemptivo. 
Assim que a CPU tiver sido alocada a um processo, esse 
processo mantém a CPU até liberá-la, querseja por ter 
sido concluído, quer seja por ter de atender a um pedido de 
I/O;
• Esse algoritmo não é indicado para sistemas de tempo 
compartilhado, onde é importante que o usuário tenha 
acesso a CPU em intervalos regulares.
• Proporciona baixa utilização da CPU.
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento Shortest-Job-First (SJF)
• Ou “Menor Job Primeiro “
• Associa a cada processo o próximo tempo de CPU (CPU burst). Usa 
esse valor para escalonar os processos com o menor tempo
• Dois esquemas: 
– Não-preemptivo – Uma vez que a CPU foi dada a um processo, 
ela não pode lhe ser tomada até que complete seu tempo de CPU.
– Preemptivo – Se um novo processo chega e possui menor tempo 
de CPU que o restante de tempo do processo corrente, a CPU lhe é 
tomada. Este esquema é conhecido como Shortest-Remaining-
Time-First (SRTF).
• SJF é o ótimo – Proporciona o menor tempo médio de espera para 
um dado conjunto de processos.
Silberschatz, Galvin, and Gagne
Processo Burst Time
P1 6
P2 8
P3 7
P4 3
• SJF ( gráfico de Gantt)
• Tempo médio de espera = (3 + 16 + 9 + 0)/4 = 7 
P4 P1 P3
3 9 16 24
P2
Exemplo: SJF Não Preemptivo
Silberschatz, Galvin, and GagneSistemas Operacionais
Processo Tempo de Chegada Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4
• SJF (não-preemptivo)
• Tempo de espera médio = (0 + 6 + 3 + 7)/4 = 4
Exemplo: SJF Não Preemptivo
P1 P3 P2
7 160
P4
8 12
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo de SJF Preemptivo
Processo Tempo de Chegada Burst Time
P1 0.0 7
P2 2.0 4 
P3 4.0 1
P4 5.0 4 
• SJF (Preemptivo)
• Te p1 = 0+(11-2) = 9 , Te p2 = 0+(5-4) = 1 , Te p3 = (4-4) =0 e Te p4 = (7-5) =2 
• Tempo de espera médio = (9 + 1 + 0 +2)/4 = 3
P1 P3P2
42 110
P4
5 7
P2 P1
16
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplos SJF não Preemptivo
Processo
(Ordem)
Burst Time
Instante
P1 P2 P3
6 8 7
0 0 0
P4
3
0
Tempo médio de espera = (0 + 3 + 9 + 16) / 4 = 7
P4
0 3
P1 P3 P2
9 16 24
SJF
Tempo médio de espera = (0 + 6 + 14 + 21) / 4 = 10.25
P4
0 6
P1 P3P2
14 21 24
FCFS, mesmo exemplo:
SOA
8
Silberschatz, Galvin, and GagneSistemas Operacionais
Shortest Remaining Time (SRT)
• Versão preemptiva do SJF;
• Política:
– Escolher o processo com o menor tempo de CPU burst, 
e executar esse processo preemptivamente até que:
Ocorra sua finalização ou bloqueie, ou
Um outro processo entre na fila de processos 
prontos
– Nesse momento, escolher um outro processo para 
executar, caso ele tenha um tempo restante de CPU 
Burst inferior ao do processo que está correntemente 
sendo executado.
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo de SRT
Processo
(Ordem)
Burst Time
Ordem chegada
P1 P2 P3
8 4 9
0 1 2
P4
5
3
Tempo médio de espera = (0 + (8–1) + (12–3) + (17–2)) / 4 = 7.75
P4
0 8
P1 P3P2
12 17 26
ordem P2 P3 P4
SJF
P1 P2 P3 P4
Tempo médio de espera = ((0+(10–1)) + (1–1) + (17–2) + (5–3)) / 4 = 6.5
0 5 10 17 26
P4P2 P1 P3P1
ordem P2 P3 P4
P1 P2 P3 P4
SRT ou Shortest-Remaining-Time-First
Silberschatz, Galvin, and GagneSistemas Operacionais
Determinando o tamanho do próximo tempo de 
CPU
• Utilizados em ambientes interativos
• Pode-se somente estimar o próximo tempo de CPU
• Pode ser feito usando o tempo anterior de CPU e 
usando média exponencial através da estimativa:
tn = tempo de CPU no n-ésimo ciclo de CPU 
τn+1 = valor estimado para o próximo ciclo de CPU
α , constante tal que 0 < α < 1
Define-se:
ττττn+1 = αααα tn + (1 - αααα ) ττττn 
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplos de média exponencial 
• α =0
– τn+1 = τn
– histórias recentes não contam (transitórias)
• α =1
– τn+1 = tn
– Só o último CPU burst conta ( histórico irrelevante)
• Se expandirmos a fórmula, teremos:
τn+1 = α tn+(1 - α) α tn -1 + …
+(1 - α )j α tn -1 + …
+(1 - α )n=1 tn τ0
• Desde que ambos α e (1 - α) sejam menores ou iguais a 
1, cada termo sucessivo tem menor peso que seu 
antecessor
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo
• Para α =1/2, t0 = 6 e τ0 =10 teremos as 
seguintes estimativas:
Tempos 0 1 2 3 4 5 6 7 ......
ti 6 4 6 4 13 13 13 ...... 
surto
τi 10 8 6 6 5 9 11 12 ...... 
previsão
ti tempo efetivo de gasto de CPU no i-ésimo tempo
τi tempo estimado de CPU no i-ésimo tempo
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento por prioridade
• Uma prioridade (valor inteiro) é associado a cada 
processo
• A CPU é alocada para o processo que tiver a maior 
prioridade (menor inteiro ≡ prioridade maior).
– Preemptivo
– Não-preemptivo
• SJF é um escalonamento por prioridade, onde a 
prioridade é definida pelo tempo de CPU
• Problema ≡ Starvation (inanição) – processos de baixa 
prioridade podem nunca executar
• Solução ≡ Aging (envelhecimento) – com o passar do 
tempo incrementar a prioridade dos processos.
SOA
9
Silberschatz, Galvin, and Gagne
Prioridade
 Atribuição de prioridades 
 Estática: o processo tem uma prioridade 
fixa durante o seu tempo de vida;
 Dinâmica: prioridade muda ao longo do 
tempo de vida do processo, de acordo com 
o seu comportamento .
Silberschatz, Galvin, and Gagne
Prioridade
 Atribuição de prioridades
 normalmente é feita pelo SO
 pode ser configurada pelo superusuário
 processos de usuário recebem uma prioridade 
máxima de usuário
 usuário pode diminuir a prioridade de seus 
processos
 ex.: comando renice do Unix
serão prejudicados.
 Dinâmica:
 Pode ser ajustada de acordo com:
 Tipo de processamento realizado
 A carga do SO
 quando o processo passa do estado de 
espera para o estado executando ele é 
penalizado e sua prioridade é reduzida, 
processos
  CPU bound terão suas prioridades 
reduzidas a cada passagem para o estado 
executando
  I/O bound ficam em estado de espera 
com freqüência, processos CPU bound não 
serão prejudicados.
 Estática:
 É atribuída quando o processo é iniciado
 Não é alterada durante a existência do processo
 pode oferecer tempos de resposta aceitáveis Observação
 SO pode associar à alta prioridade um 
número escalar pequeno; 
  0 significa a maior prioridade.
Silberschatz, Galvin, and Gagne
Prioridade
Processo A
Processo B
tempo4 8 10 13 16 18 23 26 27
1u.t.
4 u.t.
B solicita 
I/O
preempção
por B
4 u.t.
B solicita 
I/O
2 u.t.
A solicita 
I/O
3 u.t.
2 u.t.
B solicita 
I/O
5 u.t.
preempção
por B
3 u.t.
B solicita 
I/O
Tempo de CPU (u.t.) Característica do Processo Prioridade
Processo A 13 CPU bound 1 menor
Processo B 11 I/O bound 0 maior 
Silberschatz, Galvin, and Gagne
Prioridade
 Vantagens:
 é possível fazer diferenciação entre processos;
 adaptabilidade (prioridades dinâmicas).
 Desvantagem
 Starvation: um processo com baixa prioridade 
pode nunca ser atribuído ao processador;
 Solução: aumentando, em intervalos regulares, 
a prioridade dos processos que estão há muito 
tempo esperando.
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo de Escalonamento por Prioridade
Processo Burst Time Prioridade
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
P5 P3
6 190
P4
161
P1
18
P2
Considerando 1 como sendo a prioridade máxima, o 
Tempo Médio de Espera é = 8.2
Silberschatz, Galvin, and Gagne
Processos Burst time Prioridade
P1 10 3
P2 1 1
P3 2 4
P4 1 5 
P5 5 2
•Considerando a prioridade 1, como sendo a 
mais elevada, o tempo médio de espera 
resulta em: (6+0+16+18+1)/5=8.2
Exercício de Escalonamento por Prioridade - 1
SOA
10
Silberschatz, Galvin, and Gagne
Processos Bursttime Prioridade Instante de chegada
P1 10 3 0.0
P2 1 1 1.0
P3 2 4 2.0
P4 1 5 3.0
P5 5 2 4.0
•Faça o gráfico de Gantt para o escalonamento 
preemptivo e não preemptivo e calcule o tempo 
médio de espera
Exercício de Escalonamento por Prioridade - 2
Silberschatz, Galvin, and Gagne
 Atribuição de prioridades
 normalmente é feita pelo SO
 pode ser configurada pelo superusuário
 processos de usuário recebem uma prioridade 
máxima de usuário
 usuário pode diminuir a prioridade de seus 
processos
 ex.: comando renice do Unix
 Dinâmica:
 pode ser ajustada de acordo com:
 Tipo de processamento realizado;
 A carga do SO.
 Quando o processo passa do estado de 
espera para o estado executando ele é 
penalizado e sua prioridade é reduzida. 
Assim os processos:
  CPU bound terão suas prioridades 
reduzidas a cada passagem para o 
estado executando;
  I/O bound ficam em estado de espera 
com frequência, processos CPU bound
não serão prejudicados.
 Observação:
 O SO pode associar à alta prioridade um 
número escalar pequeno. Nesse caso: 
  0 significa a maior prioridade
 Estática:
 É atribuída quando o processo é 
iniciado;
 Não é alterada durante a existência 
do processo;
 Pode oferecer tempos de resposta 
aceitáveis.
Prioridades dos Processos
Silberschatz, Galvin, and Gagne
Prioridade
Processo A
Processo B
tempo4 8 10 13 16 18 23 26 27
1u.t.
4 u.t.
B solicita 
I/O
preempção
por B
4 u.t.
B solicita 
I/O
2 u.t.
A solicita 
I/O
3 u.t.
2 u.t.
B solicita 
I/O
5 u.t.
preempção
por B
3 u.t.
B solicita 
I/O
Tempo de CPU (u.t.) Característica do Processo Prioridade
Processo A 13 CPU bound 1 (menor)
Processo B 11 I/O bound 0 (maior) 
Silberschatz, Galvin, and Gagne
Prioridade
 Vantagens:
 É possível fazer diferenciação entre processos;
 Adaptabilidade (prioridades dinâmicas).
 Desvantagens:
 Starvation: Um processo com baixa prioridade 
pode nunca ser atribuído ao processador;
 Solução: Aumentando, em intervalos regulares, 
a prioridade dos processos que estão há muito 
tempo esperando.
Silberschatz, Galvin, and GagneSistemas Operacionais
Filas por Prioridade
Processador
Evento
ocorre
Fila de Bloqueados
Aguarda Evento
Preempção
Entrada 
Pn
P1
P0
Dispatch
Saída
.
.
.
Silberschatz, Galvin, and Gagne
Prioridade no MS Windows 7/8/10
• Os Threads do MS Windows 7/8/10 são escalonadas para serem executadas 
segundo sua prioridade de escalonamento:
– Ao ser criada, cada thread recebe uma prioridade de escalonamento;
– Os níveis de prioridade vão de zero a 31, sendo zero a menor de todas, 
e 31 a prioridade máxima;
– Somente o mecanismo de controle de paginação de memória pode ter 
prioridade zero. A prioridade máxima (31) é reservada aos processos 
de tempo real. 
• O escalonador trata todos os threads de mesma prioridade de maneira igual;
• Primeiramente o sistema atribui time slices do algoritmo RR a todos os 
threads de maior prioridade;
• Caso nenhuma dessas threads esteja pronta, o sistema atribuirá time slices às 
threads de prioridade imediatamente inferior e assim sucessivamente, até a 
tarefa idle. 
• Caso uma thread de prioridade mais elevada passar ao estado pronto, o 
sistema irá preemptar o processamento da thread de menor prioridade e 
atribuir um time slice para essa thread mais importante 
Sistemas Operacionais
SOA
11
Silberschatz, Galvin, and Gagne
Prioridade no MS Windows 7/8/10
Sistemas Operacionais
Obs: zero corresponde à menor prioridade, e 31 a prioridade máxima;
Silberschatz, Galvin, and Gagne
Alterando a Prioridade no MS Windows
Sistemas Operacionais
Silberschatz, Galvin, and Gagne
Prioridade no MS Windows 7/8/10
Sistemas Operacionais Silberschatz, Galvin, and Gagne
Prioridade de processos em Linux
Silberschatz, Galvin, and GagneSistemas Operacionais
Round Robin (RR) ou Revezamento Circular
• Indicado para sistemas de tempo compartilhado;
• Cada processo ganha uma pequena unidade de tempo da CPU (quantum), 
normalmente 5-100 milissegundos. 
– Após esse tempo, o processo é interrompido, a CPU lhe é tomada, sendo 
então adicionado no fim da fila de processos prontos.
• Se existirem n processos esperando na fila e o quantum de tempo for q, então 
cada processo pega 1/n do tempo da CPU, em bloco de no máximo q unidades 
de tempo, por vez. 
– Nenhum processo espera mais que (n-1)q unidades de tempo.
• Rendimento:
– q grande  FIFO
– q pequeno  q deve ser grande o suficiente para respeitar a mudança de 
contexto, caso contrário haverá grande ineficiência (overhead).
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplo: RR com Quantum de Tempo = 20
Processo Tempo de CPU
P1 53
P2 17
P3 68
P4 24
• O diagrama de Gantt fica: 
• Tipicamente, turnaround é maior que o SRTF, mas a resposta é 
melhor.
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
SOA
12
Silberschatz, Galvin, and GagneSistemas Operacionais
Exemplos RR
Processo
(Ordem Proc.)
Burst Time
Instante
P3 P2 P1
3 3 24
0 0 0
Tempo de espera médio = 
(0 + 3 + 6) / 3 = 3
P3 P2
0 3
P1
30
P1 P1 P1 P1 P1
10 14 18 22 266
Exemplo 2
Tempo de espera médio=
(4 + 7 + (10–4)) / 3 = 5.66
P1 P2 P3 P1 P1 P1 P1 P1
0 4 307 10 14 18 22 26
Processo
(Ordem Proc.)
Burst Time
Instante
P1 P2 P3
24 3 3
0 0 0
time slice = 4
Silberschatz, Galvin, and Gagne
Round-Robin (RR) - Exemplo
Processo Instante de 
Chegada
CPU
1
2
3
4
5
0
2
4
6
8
3
6
4
5
2
Silberschatz, Galvin, and Gagne
Outro Exemplo RR (q = 1)
Silberschatz, Galvin, and Gagne
Outro Exemplo RR e (q = 4)
Silberschatz, Galvin, and GagneA. Frank - P. Weisberg
Exemplo de RR com Quantum = 20
Processo Burst Time
P1 53
P2 17
P3 68
P4 24
• O diagrama de Gantt fica:
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134 154 162
Silberschatz, Galvin, and GagneSistemas Operacionais
Quantum de Tempo menor Aumenta a Troca de Contexto
SOA
13
Silberschatz, Galvin, and GagneSistemas Operacionais
Tempo de Turnaround Varia com o Quantum de Tempo
Silberschatz, Galvin, and GagneSistemas Operacionais
RR - Turnaround x Quantum
Para q = 6, o turnaround médio é:
(6 + 9 + 10 + 17) = 42/4 = 10.5 
Para q=1, o turnaround médio será: (seja 1, 2, 3, 4 os 
processos P1, P2, P3 e P4, então a seqüência de 
execução será)
1............................................................... 17 tempo
1 2 3 4 1 2 4 1 2 4 1 4 1 4 1 4 4
↑ ↑ ↑ ↑
P3 P2 P1 P4 (finalização) 
(3+9+15+17)/4 = 44/4 = 11
Silberschatz, Galvin, and Gagne
O Processo Idle ou "Tempo Ocioso do Sistema”
Sistemas Operacionais
• O que a CPU faz quando não há processos na fila de processos 
prontos, e o algoritmo deseja escolher um processo para ser 
transferido para a CPU que está disponível? 
• Neste caso o sistema operacional escalona um processo idle
("Tempo Ocioso do Sistema”), que é um processo tipicamente 
CPU-bound interno ao sistema operacional; 
• O processo idle recebe a menor prioridade possível, de modo que 
ele nunca será escolhido para ser executado caso haja algum 
processo na fila de processos prontos;
• O processo chamado IDLE representa o tempo em que o 
processador está disponível para processos;
• Quando deixamos um computador parado, sem executar 
comando algum, este processo tende a ocupar 99% do tempo 
total do processador.
Silberschatz, Galvin, and GagneSistemas Operacionais
Processo Idle ou Tempo Ocioso
• O que fazer quando não há nenhum processo na fila de processos prontos?
- Colocar o processador em halt (até que a interrupção chegue):
✔ economiza energia (e diminui aquecimento!);
✔ aumenta o tempode vida do processador;
✘ pode gastar muito tempo entre parar e reiniciar.
- Colocar o escalonador em espera ocupada (busy wait):
✔ Consome ciclos de CPU inutilmente;
✔ Tempo de resposta rápido;
✘ Solução ruim, sem utilidade.
- Inventar um processo chamado idle, que estará sempre apto para rodar:
✔ Proporciona uma estrutura uniforme;
✔ Pode ser utilizado para processar verificações de diagnóstico;
✘ Consome alguma memória;
✘ Pode tornar mais lenta a resposta às interrupções;
 Em geral há um compromisso entre tempo de resposta e utilidade.
Silberschatz, Galvin, and GagneSistemas Operacionais
Múltiplas Filas
• Fila de processos Prontos é particionada em filas separadas:
Foreground (interativa ou primeiro plano)
Background (batch ou segundo plano)
• Cada fila tem seu próprio algoritmo de escalonamento:
Foreground – RR
Background – FCFS
• Escalonamento deve ser feito entre as filas.
– Escalonamento de prioridade fixa; i.e., atende tanto foreground
quanto background. Possibilidade de ocorrência de starvation
(inanição)
– Time slice (Quantum de tempo) – Cada fila “ganha” uma certa 
quantidade de tempo de CPU a qual ela pode escalonar entre 
estes processos; i.e.:
 80% de foreground em RR
 20% de background em FCFS 
Silberschatz, Galvin, and Gagne
Processos Foreground e Background
(a) Processo Foreground
(b) Processo Background
saída
saída
arquivo
de saída
terminalterminal
entrada
entrada
arquivo
de entrada
SOA
14
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de Múltiplas Filas
Silberschatz, Galvin, and GagneSistemas Operacionais
Múltiplas Filas com Realimentação
• Um processo pode se mover entre as várias filas; 
“envelhecimento” (aging) pode ser implementado desta maneira.
• O escalonamento de múltiplas filas com feedback (realimentação) é 
definido pelos seguintes parâmetros:
– Número de filas;
– Algoritmos de escalonamento para cada fila;
– Método usado para determinar quando fazer upgrade de um 
processo;
– Método usado para determinar quando rebaixar um processo;
– Método usado para determinar em qual fila um processo irá 
entrar quando aquele processo precisar de algum serviço.
Silberschatz, Galvin, and GagneSistemas Operacionais
Múltiplas Filas com Realimentação
Silberschatz, Galvin, and GagneSistemas Operacionais
• Três Filas: 
– Q0 – Quantum de tempo de 8 milissegundos
– Q1 – Quantum de tempo de 16 milissegundos
– Q2 – FCFS
• Escalonamento:
– Um novo “job” entra na fila Q0 que é servida por FCFS. Quando 
este ganha a CPU, recebe 8 milissegundos. Se o “job” não 
terminar em 8 milissegundos, é transferido para a fila Q1.
– Em Q1 o trabalho é atendido novamente por FCFS e recebe 16 
milissegundos adicionais. Se ele ainda não se completar, é 
“preemptado” (perde a CPU) e transferido para a fila Q2.
Exemplo de Múltiplas Filas com Realimentação
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento com Múltiplos Processadores
• Escalonamento de CPU é mais complexo quando várias 
CPUs estão disponíveis;
• Processadores homogêneos dentro do multiprocessador 
=> qualquer processador pode processar qualquer 
processo;
• Processadores heterogêneos => cada processador 
compila e processa seus programas
• Compartilhamento de carga (Load Sharing) somente uma 
fila de prontos (quando processadores são homogêneos).
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento em Múltiplos Processadores 
(cont.)
•Multiprocessamento Simétrico (Symmetric 
Multiprocessing -SMP) – cada processador 
faz suas próprias decisões de 
escalonamento.
•Multiprocessamento Assimétrico – apenas 
um processador acessa as estruturas de 
dados do sistema, aliviando a necessidade 
de compartilhamento de dados.
SOA
15
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento em Múltiplos Processadores 
(cont.)
• Multiprocessamento simétrico (SMP)
– Cada processador processa uma mesma cópia do 
sistema operacional.
– Muitos processos podem ser executados ao mesmo 
tempo sem degradação de performance (desempenho).
– Vários sistemas operacionais modernos tem o suporte 
a SMP
• Multiprocessamento assimétrico
– A cada processador é atribuída uma tarefa específica; o 
processador principal (Mestre) escalona e aloca 
trabalho para processadores escravos. 
– Muito comum em sistemas extremamente grandes.
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento em Tempo Real
• Sistemas de Tempo Real Forçado – exige que se complete uma 
tarefa crítica em um intervalo de tempo garantido.
– Software específico em hardware dedicado
• Sistema de Tempo Real Simples – exige que processos críticos 
recebam prioridade maior que outros menos importantes.
• Latência do Dispatcher - Tempo necessário para se completar 
uma mudança de contexto.
– Em sistemas de tempo real o tempo de latência do dispatcher
deve ser o mínimo possível
• Pode ocorrer inversão de prioridade. Um processo de prioridade 
alta necessita modificar um dado que está sendo acessado por um 
processo de baixa prioridade => processo de alta espera processo 
de baixa prioridade. 
– Solução herdar prioridade do processo de alta prioridade para 
finalizar rápido.
Silberschatz, Galvin, and GagneSistemas Operacionais
Latência do Dispatch
Silberschatz, Galvin, and GagneSistemas Operacionais
Silberschatz, Galvin, and GagneSistemas Operacionais
Scheduling em Sistemas de Tempo Real
Um sistema de Tempo Real é Escalonável?
• Considerando:
– m eventos periódicos
– Cada evento i ocorre dentro de um período Pi e 
requer Ci segundos
• Logo a carga computacional somente poderá ser tratada 
se:
1
1
m
i
i i
C
P=
≤
Silberschatz, Galvin, and Gagne
Pipe
entrada do
Processo A
saída do
Processo B
saída do
Processo A
entrada do
Processo B
Processo A Processo B
• Um encadeamento (em inglês: pipeline), nos sistemas operacionais do tipo Unix, 
é um mecanismo implementado com base no conceito original de canalização: 
• Um conjunto de processos encadeados através de seus fluxos padrão, de forma 
que a saída de um processo é utilizada como entrada do processo seguinte.
• O caractere representativo do pipe é o '|'. 
• O pipe pega a saída do comando da esquerda e joga na entrada do comando da 
direita.
SOA
16
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento no UNIX
• As prioridades são recalculadas a cada segundo, ou seja os processos que 
não finalizaram ou foram bloqueados dentro desse tempo são 
preemptados;
• 160 níveis de prioridade divididos em 3 classes de prioridade;
• Um fator de ajuste é utilizado para manter o processo dentro de sua classe;
• O kernel tradicional não é preemptivo
Classe de
Prioridade
Valor 
Global
Seqüência de
escalonamento
Real-time
159
100
primeiro
último
Kernel
99
60
0
59
Time-shared
.
..
.
.
.
.
.
.
.
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de Processos no Linux
2 algoritmos independentes de escalonamento 
de processos:
 Time-Sharing: Baseado em prioridade
Soft-real time: FCFS e RR
 Somente processos no modo usuário podem 
ser preemptados. 
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de Threads
• Thread de usuário
– Escalonamento Local – Escalonamento via biblioteca de 
threads, que decide qual thread irá ser processado por um 
LWP disponível. Escalonamento é local à aplicação.
– Não existe mudança de contexto entre alternância entre os 
threads de usuários. Alternância é tarefa da programação.
• Thread de Kernel
– Escalonamento Global – O sistema decide qual thread 
será o próximo a ganhar controle da CPU. Neste caso é 
tarefa real do SO e existe uma mudança de contexto a ser 
realizada.
Silberschatz, Galvin, and GagneSistemas Operacionais
Programação do Solaris 2
Silberschatz, Galvin, and GagneSistemas Operacionais
Escalonamento de Threads em Java
• JVM usa um algoritmo preemptivo, baseado em 
prioridade. Todo thread em Java possui uma prioridade. 
Um novo thread é escolhido (escalonado) paraassumir a 
CPU, quando:
– O thread corrente termina
– O thread corrente entra em estado de bloqueado, 
esperando por uma E/S
– O método suspend() é chamado
– O método stop() é chamado 
• Filas FIFO são utilizadas se existem múltiplos threads 
com a mesma prioridade.
Silberschatz, Galvin, and GagneSistemas Operacionais
Programação de Threads Java (cont)
JVM programa um thread para ser executado quando:
1.O thread que está executando deixa o estado “em 
execução”.
2.Um thread de alta prioridade entra no estado “em 
execução”.
* Nota – JVM não especifica se os threads são de tempo 
compartilhado (time slice) ou não. 
SOA
17
Silberschatz, Galvin, and GagneSistemas Operacionais
Compartilhamento de Tempo - Java
• Uma vez que o ambiente JVM não garante quantum de 
tempo (time Slice) o método yield() pode ser utilizado:
while (true) {
// Realiza tarefas de CPU intensivas
. . .
Thread.yield();
}
Isto transfere (cede) o controle para outro thread de 
mesma prioridade.
Silberschatz, Galvin, and GagneSistemas Operacionais
Prioridades de Thread - Java
• Prioridades de Thread:
Prioridade Comentário
Thread.MIN_PRIORITY Prioridade mínima
Thread.MAX_PRIORITY Prioridade máxima
Thread.NORM_PRIORITY Prioridade padrão
Prioridade podem ser atribuídas usando-se o método 
setPriority():
setPriority(Thread.NORM_PRIORITY + 2);
Silberschatz, Galvin, and GagneSistemas Operacionais
Avaliação de Algoritmos de Escalonamento
• Avaliação Analítica - utiliza um dado algoritmo e a carga 
do sistema para produzir uma formula ou valor numérico 
que avalia o comportamento do algoritmo para uma dada 
carga.
• Modelagem determinística – tipo de modelagem analítica 
que de posse de uma dada carga pré-determinada do 
sistema (workload), define-se o comportamento de cada 
algoritmo de escalonamento de acordo com esta carga. 
• Exemplo - Para um conjunto de 5 processos, chegando em 
tempo 0, na ordem dada, com os tempos de CPU dados, 
qual algoritmo, entre FCFS, SJF e RR possui o menor 
tempo médio de espera? Dados
P1=10, P2=29, P3=3, P4=7 e P5=12 
Silberschatz, Galvin, and GagneSistemas Operacionais
Avaliação (cont.)
• Modelos de filas - considera o sistema como um rede de 
servidores (CPU, Discos, impressoras, etc). Cada servidor possui 
uma fila associada. Conhecendo a razão de chegada e razão de 
atendimento, podemos computar a utilização, tamanho médio de 
fila, tempo de espera médio, etc. de um servidor.
• Fórmula de Litle n = λ x W
onde n = tamanho médio da fila (excluindo processo sendo 
servido
λ= razão média de chegada na fila (i.e. 3 processos/segundo)
W= tempo médio de espera na fila
• Fórmula de Litle pressupõe sistema em equilíbrio, i.e número de 
processos chegando é igual ao número de processos saindo do 
sistema 
Silberschatz, Galvin, and GagneSistemas Operacionais
Avaliação (cont.)
• Modelo de Simulação - implementar o modelo do 
sistema de computação e processar várias simulações. 
È um método mais acurado para avaliar algoritmos de 
escalonamento, porém é mais caro pois requer várias 
horas de tempo de computação. 
– Quanto mais próximo do sistema real (acurado) for 
o modelo implementado mais preciso é o resultado.
• Simulação: Representar as estruturas mais 
importantes do sistema, representar o relógio por uma 
variável. 
– Variação do relógio (variável) faz o simulador 
modificar os estados do sistema para refletir as 
atividades dos dispositivos. 
Silberschatz, Galvin, and GagneSistemas Operacionais
Avaliação de Escalonamento da CPU por simulação
SOA
18
Silberschatz, Galvin, and Gagne
Evolução dos SOs Time Sharing
Sistemas Operacionais