Aula 07 Gerenciamento de CPU

Prévia do material em texto

SISTEMAS OPERACIONAIS
 Prof. Gerhard Saboia
Capítulo 6: Escalonamento de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Capítulo 6: Escalonamento de CPU
 Conceitos básicos
 Critérios de Escalonamento
 Algoritmos de Escalonamento
 Escalonamento em Múltiplos Processadores
 Escalonamento em Tempo Real
 Avaliação de Algoritmos
 Modelos de Escalonamento de Processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.1 Conceitos Básicos
 Objetivo da multiprogramação: maximizar uso da CPU
 Diversos processos em memória
 Sempre que um deixa a CPU (em geral por E/S), outro ganha
 O escalonamento (scheduling) é função fundamental
 Praticamente todos recursos são escalonados (não só CPU)‏
 O escalonamento é parte central do projeto de um SO
 Execução de processo composta de:
 Picos de CPU (CPU bursts): execução intensiva de instruções
 Picos de E/S (I/O bursts): aguardo por E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Seqüências de Picos de CPU e E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Histrograma de Picos de CPU
* Maior parte 
dos picos são 
curtos (até 
8ms)‏
* Poucos são 
longos (até 
40ms)‏
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
 Escalonador de CPU (curto prazo)‏
 Seleciona processo na fila (FIFO ou não) da de prontos
 Preempção: interrupção da execução de um processo 
seguida da alocação da CPU a outro processo
 Retira-se o processo da CPU de maneira “forçada”
 Escalonamento pode ser
 Sem preempção: processo resolve deixar a CPU
 Com preempção (preemptivo): processo retirado e trocado
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
 As decisões de escalonamento de CPU podem ocorrer 
quando um processo:
 1. Passa do estado em execução para em espera
 2. Passa do estado em execução para pronto
 3. Passa do estado em espera para pronto
 4. Termina (passa para o estado terminado)‏
 Nos casos 1 e 4 o escalonamento é sem preempção
 Nos casos 2 e 3 o escalonamento é com preempção
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
 Escalonador de CPU sem preempção
 Um processo pode usar a CPU o quanto desejar ou até terminar: 
inviabiliza tempo compartilhado
 Escalonador de CPU com preempção
 Requer hardware especial (timer)‏
 Requer melhor projeto
 Problema: como retirar um processo da CPU se o kernel está tratando 
de suas atividades?
 Pode haver inconsistências, perdas de dados
 Alguns sistemas: só fazem preempção após final de chamada ao sistema 
ou bloco de E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Despachante (Dispatcher)‏
 Despachante
 Módulo que passa o controle da CPU ao processo escolhido pelo 
escalonador
 Realiza 
 Troca do contexto
 Coloca a execução em modo usuário
 Desvia a execução para o local apropriado do processo escolhido para 
iniciá-lo (ou reiniciá-lo)‏
 Latência de despacho: tempo gasto para o despachante operar
 Despachante deve ser rápido: invocado a cada troca de processo 
(tempo compartilhado....)‏
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.2 Critérios de Escalonamento
 Existem diferentes algoritmos de escalonamento
 Para os mesmos ou diferentes propósitos
 Utiliza-se uma série de critérios para compará-los e para 
eleger um bom escalonador
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Critérios de Escalonamento
 Principais critérios considerados:
 Utilização de CPU: pode variar de 0 a 100%, indicando se está ociosa 
ou carregada
 Throughput: número de processos que são executados em unidade 
de tempo (por segundo, hora, etc.)‏
 Tempo de turnaround: tempo que um processo leva, de sua 
submissão até o completamento (inclui E/S, esperas, etc.)‏
 Tempo de espera: tempo total que um processo gasta esperando na 
fila com o estado pronto
 Tempo de resposta: intevalo que leva entre uma solicitação ao 
processo e a primeira resposta do processo
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Critérios de Escalonamento
 Objetivos de um escalonador:
 Maximizar
 Utilização da CPU
 Throughput
 Minimizar
 Tempo de turnaround
 Tempo de espera
 Tempo de resposta
 Deseja-se maximizar ou minimizar não somente um valor 
específico, mas, em geral, a média dos valores dos 
processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.3 Algoritmos de Escalonamento
 Principais algoritmos
 FCFS (First Come, First Served)‏
 SJF (Shortest Job First)‏
 RR (Round-robin)‏
 Filas Multiníveis
 Filas Multiníveis com Retroalimentação 
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” 
(FCFS)‏
 FCFS
 Algoritmo de escalonamento mais simples
 Primeiro processo a requisitar CPU é o primeiro a ganhar
 Sem preempção
 Se um processo ganha a CPU, só sai se terminar ou fazer E/S
 Não adequado para sistemas de tempo compartilhado
 Implementação simples
 Através de fila de prontos FIFO
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” 
(FCFS)‏
Processo Tempo de pico
P1 24ms
P2 3ms
P3 3ms
 Ordem de chegada: P1 , P2 , P3. O diagrama de Gantt (etapas de 
execução) para o escalonamento será:
 Tempo de espera para P1 = 0; P2 = 24; P3 = 27
 Tempo de espera médio: (0 + 24 + 27)/3 = 17ms
P1 P2 P3
24 27 300
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” 
(FCFS)‏
 Se ordem de chegada for: P2 , P3 , P1. O diagrama de Gantt 
para o escalonamento será:
 Tempo de espera para P1 = 6; P2 = 0; P3 = 3
 Tempo de espera médio: (6 + 0 + 3)/3 = 3ms
 Muito melhor do que no caso anterior
 Efeito comboio: 1 processo CPU-bound + n I/O-bound
 n processos fazem E/S e têm que aguardar o CPU-bound
 Isso se repete durante toda a execução
P1P3P2
63 300
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “Shortest Job First” (SJF)‏
 Escalonador possui informação sobre tamanho do próximo pico de CPU 
de cada processo
 Essa informação é usada para escolher processo com tempo mais 
curto 
 Dois esquemas:
 Sem preemção
 Com preempção: se um outro processo chegar pico de CPU menor do que o 
restante do processo atual, há preempção. Esse esquema é conhecido como 
“Shortest Remaining Time First” (SRTF).
 SJF é ótimo
 Sempre provê o menor tempo de espera médio para um determinado 
conjunto de processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de SJF sem Preempção
Processo Tempo do próximo pico
P1 6ms
P2 8ms
P3 7ms
P4 3ms
 Escalonamento:
 Tempo de espera para P1 = 3; P2 = 16; P3 = 9; P4 = 0
 Tempo de espera médio: (3+16+9+0)/4 = 7ms
0
P1 P3 P2
3
P4
9 16 24
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de SJF com Preempção (SRTF)
Processo Chegada Pico
P1 0 8
P2 1 4
P3 2 9
P43 5
 Escalonamento:
 Tempo de espera médio = [(10 -1)+(1-1)+(17-2)+(5-3)]/4 = 6,5 ms
0
P2 P4 P3
1
P1
5 10 26
P1
17
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Dificuldades com SJF
 Como determinar os tempos dos próximos picos de CPU?
 Usuário informa: em escalonadores de longo prazo
 Não há forma automática de saber exatamente o tempo do próximo pico
 Pode-se estimar: utilizando como base tempos dos picos anteriores
 Embora SJF seja ótimo, não pode ser usado como escalonador de CPU (curto prazo)
 Pode apenas estimar o tempo
 Estimação do próximo pico através de uma média exponencial:
 n+1 = duração estimada do próximo pico de CPU
 n = história dos picos passados
 tn = duração real do enésimo burst de CPU
 Define-se: n+1 =  tn + (1 - ) n , onde 0 ≤  ≤ 1
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Estimação do próximo pico de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplos de Média Exponencial
  =0
 n+1 = n
 O histórico recente não conta.
  =1
 n+1 = tn
 Apenas o último surto de CPU real tem efeito.
 Se expandirmos a fórmula, obtemos:
n+1 =  tn+(1 - )  tn -1 + …
+(1 -  )j  tn -1 + …
+(1 -  )n=1 tn 0
 Como  e (1 - ) são menores ou iguais a 1, cada termo sucessivo 
possui peso menor do que seu.
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
 Um número de prioridade (inteiro) é associado a cada 
processo
 A CPU é alocada para o processo com a prioridade mais alta
 Processos de igual prioridade são executados na ordem FCFS
 SJF é um caso particular do escalonamento por prioridade
 A prioridade é o inverso do próximo pico de CPU
 Neste livro
 Números menores: prioridades mais altas
 Números maiores: prioridades mais baixas
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
Tempo de chegada: 0 para todos os processos
Processo Pico de CPU Prioridade
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
 Escalonamento:
 Tempo de espera médio = 8,2 ms
0
P5 P3
1
P2
6 19
P1
16
P4
18
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
 Escalonamento pode ser
 Preemptivo: se chega um de prioridade mais alta, o escalonador troca de 
processo
 Não-preemptivo
 Problema
 Possibilidade de estagnação/inanição/starvation
 Um processo de baixa prioridade podem nunca ser executado!
 Solução: envelhecimento (aging)
 Conforme o tempo passa, aumenta a prioridade dos processos que estão 
em espera há muito tempo
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento Round-Robin (RR)‏
 Projetado para sistemas de tempo compartilhado
 Semelhante FCFS
 Preemptivo: comutação entre processos
 Definição de quantum: unidade de tempo (ex.: 10 ou 100ms)
 Escalonamento RR
 Fila de prontos é uma fila FIFO circular
 Escalonador percorre fila alocando, para cada processo, até 1 
quantum 
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento Round-Robin
 Se processo não deixar a CPU dentro do quantum, é preemptado
 Se houverem n processos e o quantum for q, cada processo possui 1/n 
tempo de CPU, executado em porções de tempo de tamanho até q
 Nenhum processo espera mais do que (n-1)q para utilizar CPU
 Não ocorre starvation (estagnação)
 Desempenho
 Quantum muito grande: execução FCFS (FIFO)
 Quantum muito pequeno: muitas trocas de contexto
 Alto custo
 Quantum deve ser pequeno suficiente para garantir o tempo compartilhado
 Quantum deve ser grande bastante para compensar trocas de contexto
 Bom desempenho: 80% dos picos de CPU devem ser menores que quantum
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de RR com quantum 4ms
Processo Pico de CPU
P1 24
P2 3
P3 3
 Tempo de chegada: 0 para todos processos
 A execução será:
 Tempo de espera médio: (6 + 4 + 7)/3 = 5,66ms
0
P3
4
P2
10 30
P1
14 26
P1 P1 P1 P1 P1
7 18 22
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exercício
 Cinco jobs A, B, C, D e E, em batch, chegam ao computador com 1 segundo de 
intervalo entre eles. Seus tempos de processamento são estimados em 10, 7, 3, 
4 e 5 segundos de CPU, respectivamente. Sendo round-robin a política de 
escalonamento utilizada, com um quantum de 1 segundo.
 O tempo médio de turnaround desses processos (ignorando overheads de troca 
de contexto e interrupções e assumindo que um job recém-chegado é colocado 
no início da fila, ou seja, na frente dos outros) é: 
 a) 25,5 s b) 13,1 s c) 10,0 s d) 19,6 s e) 29,0 s
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Quantum de Tempo e Tempo de Troca de 
Contexto
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Turnaround varia conforme o quantum
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis
 Fila de prontos é dividida em várias filas
 Ex.: 2 filas
 Processos em primeiro plano (interativos/foreground)‏
 Processos em segundo plano (background/batch)‏
 Cada fila possui seu próprio algoritmo de escalonamento:
 Ex.:
 Processos em primeiro plano: RR (para manter tempo compartilhado)
 Processos em background: FCFS
 É necessário haver escalonamento entre as filas:
 Para escolher o processo de qual fila será executado
 Se usar algoritmo de prioridade fixa de uma fila sobre outra: starvation
 Outra opção: dividir o tempo de execução entre as filas
 Foreground fica com 80% e background com 20% do tempo de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis e 
prioridade fixa
d
Discriminação?
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis com 
Retroalimentação
 Sem retroalimentação: processo nunca é trocado de fila
 Com retroalimentação: processo pode ser trocado de fila
 Permite separar processos com características de picos de CPU 
semelhantes
 Um processo que usa muito tempo de CPU é movido para fila de mais 
baixa prioridade
 Dessa forma: processos IO-bound e interativos (dependem da interação 
do usuário) ficam nas filas com mais prioridade
 Processos que ficam aguardando muito tempo por CPU podem ser 
movidos para filas de mais alta prioridade: evita starvation (inanição)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis com 
Retroalimentação
 Escalonador é definido pelos seguintes parâmetros:
 número de filas
 algoritmos de escalonamento para cada fila
 método usado para determinar quando elevar um processo
 método usado para determinar quando rebaixar um processo
 método usado para determinar em que fila um processo entrará 
quando esse processo precisar de atendimento
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de escalonamento com 
retroalimentação
 Três filas (com prioridade fixa):
 Q0 – quantum de tempo 8 milissegundos
 Q1 – quantum detempo 16 milissegundos
 Q2 – FCFS
 Escalonamento
 Uma nova tarefa entra na fila Q0 , que é atendida com base no RR. 
Quando ganha a CPU, a tarefa recebe 8 milissegundos. Se não 
terminar nesse tempo, a tarefa é movida para a fila Q1.
 Em Q1, a tarefa é atendida novamente com base no RR e recebe 16 
milissegundos adicionais. Se ainda não estiver completa, a tarefa é 
apropriada e movida para a fila Q2.
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de escalonamento com 
retroalimentação
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Múltiplos 
Processadores
 Escalonamento da CPU é muito mais complexo quando várias CPUs estão 
disponíveis
 Processadores idêndicos: simplificação
 Compartilhamento de carga: várias CPUs cooperando
 Idéia 1: usar fila de prontos separada para cada processador
 Enquanto uma CPU fica sobrecarregada outra pode ficar ociosa
 Idéia 2: usar fila de prontos comum
 Faz um melhor balanceamento da carga
 Problemas: CPUs diferentes podem escolher mesmo processo, pode haver outras 
inconsistências devido ao paralelismo
 Multiprocessamento assimétrico (mestre/escravo): mais simples
 Só 1 CPU acessa as estruturas de dados do SO (mestre), demais executam
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
 Sistemas de tempo real rígido: tarefas devem ser completadas dentro do 
tempo exigido
 Praticamente impossível em um sistema de propósito geral com memória 
secundária ou memória virtual
 Sistemas de tempo real flexível (maleável): tarefas críticas têm maior 
prioridade sobre as demais
 Permite sistemas gráficos/mutimídia executarem de forma adequada (em 
detrimento de outros processos): aceitável
 Latência de despacho deve ser pequena: diminui o tempo para um processo 
tempo real pronto entrar em execução
 Problema: SOs não realizam preempção no meio de chamada ao sistema o bloco 
de E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
 Para reduzir tempo de despacho
 Algumas chamadas ao sistema (demoradas) tornam-se 
interceptáveis
 Possuem pontos de interceptacao: locais que verificam se há processos 
de tempo real para serem executados
 Chamadas ao sistema podem ser interrompidas nesses pontos e 
retomadas futuramente (após execução do processo em tempo real)
 Pontos de interceptação devem estar em “áreas seguras” do kernel
 Não pode haver possibilidade de inconsistências
 Solaris 2: todo o kernel é interceptável (mecanismos de 
sincronização)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
 Inversão de prioridade
 Processo de alta prioridade necessita aguardar recursos que estão 
sendo atualizados por processo de baixa prioridade: ineficiência
 Protocolo de herança de prioridade: processos que estão acessando 
recursos necessários a um processo de alta prioridade herdam essa 
prioridade até liberação do recurso
 Melhor desempenho
 Prioridades voltam ao original após liberar recurso
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Latência de despacho em tempo real
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação de Algoritmos
 Modelagem determinística
 Considera uma carga de trabalho particular (pré-determinada)
 Define (calcula) o desempenho de cada algoritmo para a carga
 Utilização de CPU, throughput, tempo de espera, tempo de turnarorund, etc.
 Modelos de enfileiramento
 Formulação matemática e estatística envolvendo
 Distribuição de picos de CPU e E/S, probabilidade de ocorrência de picos 
particulares, etc.
 Permite comparar matematicamente algoritmos de forma tratável
 Comparação pode ser irrealística em função de premissas imprecisas
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação de Algoritmos
 Avaliação por simulação
 Método mais preciso
 Utiliza um modelo de sistema de computação
 Informações (processos, picos de CPU, chegadas, E/S, términos, etc.) podem 
ser geradas aleatoriamente
 De acordo com distribuições probabilísticas
 Resultados são usados para verificar o que ocorre na realidade e adota-se a 
distribuição adequada
 Avaliação por implementação
 Mais realista
 Alto custo: necessário implementar no kernel e testar sob as diversas 
situações reais (usuários são prejudicados pelas modificações)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação dos Escalonadores de CPU
por Simulação
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Modelos de escalonamento de processos
 Solaris 2
 Windows 2000
 Linux