Module 5: CPU Scheduling
•
•
•
•
•
•
Conceitos básicos
Crirtérios de Scheduling
Algoritmos de Scheduling
Multiple-Processor Scheduling
Real-Time Scheduling
Avaliação de Algoritmos
Operating System Concepts
5.1
Silberschatz and Galvin1999
Conceitos básicos
•
•
•
Maximizar o uso da CPU explorando multiprogramming
Ciclo de rachadas CPU–entrada/saída – Execução de um
processo consiste em ciclos de uso da CPU e epera por
entrada/saída.
Distribuição das rajadas de uso da CPU
Operating System Concepts
5.2
Silberschatz and Galvin1999
Alternating Sequence of CPU And I/O Bursts
Operating System Concepts
5.3
Silberschatz and Galvin1999
Histogram of CPU-burst Times
Operating System Concepts
5.4
Silberschatz and Galvin1999
CPU Scheduler
•
•
•
•
Seleciona um entre os processos prontos a aloca a CPU para
ele.
Decisões de CPU scheduling podem acontecer quando um
processo:
1. passa do estado “rodando” para o estado “waiting”,
2. passa de “rodando” para pronto”,
3. passa de “esperando” para “pronto”,
4. termina.
Scheduling em 1 e 4 é nonpreemptive.
outro scheduling é preemptive.
Operating System Concepts
5.5
Silberschatz and Galvin1999
Despachante (Dispatcher)
•
•
O dispatcher dá o controle da CPU ao processo selecionado
pelo scheduler de curto prazo. Isto envolve:
– troca de contexto
– troca para privilégio de aplicativo (user mode)
– pular para o endereço adequado do aplicativo para
continuar o programa
Latência de despachante – tempo necessário para que o
despachante pare um processo para começar a rodar outro.
Operating System Concepts
5.6
Silberschatz and Galvin1999
Critérios de Scheduling
•
•
Utilização da CPU– manter a CPU o mais ocupada possível
Vazão – número de processos que terminam sua execução
dentro de uma unidade de tempo
•
tempo de turnaround – tempo gasto para executar um processo
em particular
•
tempo de espera –tempo que um processo gastou de na fila de
prontos
•
tempo de resposta – tempo gasto entre a submissão de uma
requisição até que uma primeira reação é realizada, não o
resultado de saída. (aplicável para sistemas de
compartilhamento de tempo (time-sharing))
Operating System Concepts
5.7
Silberschatz and Galvin1999
Optimization Criteria
•
•
•
•
•
Max CPU utilization
Max throughput
Min turnaround time
Min waiting time
Min response time
Operating System Concepts
5.8
Silberschatz and Galvin1999
First-Come, First-Served (FCFS) Scheduling
•
•
Exemplo:
Processo
Tempo de rajada
P1
24
P2
3
P3
3
Suponha que os processos chegam na ordem: P1 , P2 , P3
O mapa de Gantt para este scheduling é:
P1
P2
0
•
•
24
P3
27
30
Tempo de espera para P1 = 0; P2 = 24; P3 = 27
Tempo de espera médio: (0 + 24 + 27)/3 = 17
Operating System Concepts
5.9
Silberschatz and Galvin1999
FCFS Scheduling (Cont.)
Suponha que os processos chegam na ordem
P2 , P3 , P1 .
•
O mapa de Gantt é:
P2
0
•
•
•
•
P3
3
P1
6
30
Tempo de espera P1 = 6; P2 = 0; P3 = 3
Tempo de espera médio: (6 + 0 + 3)/3 = 3
Muito melhor que o caso anterior.
Efeito de comboio - processos rápidos atrás de processos longos
Operating System Concepts
5.10
Silberschatz and Galvin1999
Shortest-Job-First (SJR) Scheduling
•
•
•
Associe a cada processo o tempo da próxima rajada. Escolhe
primeiro o processo de menor tempo.
Duas abordagens:
– nonpreemptive – uma vez que um processo recebe a CPU
ele não pode ser interrompido até completar a sua rajada
de CPU.
– Preemptive – se chega um outro processo com rajada de
CPU menor que o tempo de execução restante do processo
que está rodando, tire-o: Shortest-Remaining-Time-First
(SRTF).
SJF é ótimo - resulta em um tempo de espera médio mínimo
para um dado conjunto de processos.
Operating System Concepts
5.11
Silberschatz and Galvin1999
Example of Non-Preemptive SJF
Processo Tempo de chegada Tempo de rajada
•
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
SJF (non-preemptive)
P1
0
•
3
P3
7
P2
8
P4
12
16
Tempo de espera médio = (0 + 6 + 3 + 7)/4 - 4
Operating System Concepts
5.12
Silberschatz and Galvin1999
Example of Preemptive SJF
•
Tempo chegada
Tempo rajada
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
SJF (preemptive)
P1
0
•
Processo
P2
2
P3
4
P2
5
P4
7
P1
11
16
Tempo de espera médio = (9 + 1 + 0 +2)/4 = 3
Operating System Concepts
5.13
Silberschatz and Galvin1999
Determinar o tempo de duração da próxima
rajada
•
•
Somente estimação
usando as durações de rajadas passadas, por exemplo através
de média exponencial.
1. t n  duração da n
ta
rajada de CPU
2.  n  1  valor de predição da próxima
rajada
3.  , 0    1
4. Define :
 n 1   t n  1    n .
Operating System Concepts
5.14
Silberschatz and Galvin1999
Exemplos de média exponencial
•
 =0
– n+1 = n
– histórico não influa.
•
 =1
– n+1 = tn
– somente a última rajada influa.
•
•
Expandindo a exação, obtenmos:
n+1 =  tn+(1 - )  tn -1 + …
+(1 -  )j  tn -1 + …
+(1 -  )n=1 tn 0
Como tanto  como (1 - ) são menor ou igual a 1, cada termo
na seqüência tem menos peso do que o precedente.
Operating System Concepts
5.15
Silberschatz and Galvin1999
Scheduling com prioridade
•
•
•
Um número de prioridade (inteiro) é associado a cada processo.
A CPU é alocado ao processo de maior prioridade (menor inteiro
= maior prioridade).
– Preemptive
– nonpreemptive
SJF pode ser visto como um esquema de scheduling com
prioridade no qual a prioridade é o tempo estimado para a
próxima rajada de CPU.
•
Problema  Starvation (morte de fome) – processos com baixa
prioridade podem eventualmente nunca ser executados.
•
Solução  envelhecimento – com progresso do tempo a
prioridade do processo aumenta.
Operating System Concepts
5.16
Silberschatz and Galvin1999
Round Robin (RR)
•
•
•
Cada processo recebe uma pequena fatia de tempo de CPU
(time quantum), normalmente 10-100 milisegundos. Ao passar
este tempo, o processo é interrompido e colocado ao fim da lista
de prontos.
Se temos n processos na fila de prontos e o time quantum é q,
entào cada processo obtém 1/n do tempo da CPU em pedaços
de no máximo q unidades de tempo por vez. Nenhum processo
espera mais do que (n-1)q unidades de tempo.
Desempenho
– q grande  FIFO
– q pequeno  q overhead de troca de contexto.
Operating System Concepts
5.17
Silberschatz and Galvin1999
Example: RR with Time Quantum = 20
•
Tempo de rajada
P1
53
P2
17
P3
68
P4
24
o mapa de Gantt é:
P1
0
•
Processo
P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
tipicamente tempo de turnaraund médio maior que SJF, mas
melhor tempode resposta.
Operating System Concepts
5.18
Silberschatz and Galvin1999
Como um Quantum de tempo menor
aumenta o número de trocas de contexto
Operating System Concepts
5.19
Silberschatz and Galvin1999
Turnaround Time Varies With The Time Quantum
Operating System Concepts
5.20
Silberschatz and Galvin1999
Fila multinível
•
•
•
Fila de prontos dividida em várias filas:
foreground (interativo)
background (batch)
cada fila tem seu próprio algoritmo de scheduling,
foreground – RR
background – FCFS
Scheduling tem que ser feito entre as filas.
– Scheduling com prioridade fixa, ou seja, atende primeiro
todos os foreground e somente depois passa para
background. Possibilidade de starvation.
– Fatia de tempo – cada fila recebe uma determinada quantia
de tempo que ela pode administrar, por exemplo
80% para foreground em RR
20% para background em FCFS
Operating System Concepts
5.21
Silberschatz and Galvin1999
Multilevel Queue Scheduling
Operating System Concepts
5.22
Silberschatz and Galvin1999
Fila de realimentação multinível
•
•
Um processo pode trocar de fila; envelhecimento pode ser
implementado desta forma.
Um scheduler com fila de realimentação multinível é definido
pelos seguintes parâmetros:
– número de filas
– algoritmo de scheduling para cada fila
– método usado para determinar quando promover um
processo
– método usado para determinar quando desclassificar um
processo
– método usado para determinar em qual fila um processo vai
entrar quando ele solicita a CPU.
Operating System Concepts
5.23
Silberschatz and Galvin1999
Multilevel Feedback Queues
Operating System Concepts
5.24
Silberschatz and Galvin1999
Exemplo de fila de realimentação multinível
•
•
Três filas:
– Q0 – quantum de 8 milisegundos
– Q1 – quantum de 16 milisegundos
– Q2 – FCFS
Scheduling
– Um processo novo entra na fila Q0 que usa FCFS. Quando
ele consegue a CPU, o processo recebe 8 milisegundos. Se
não termina em 8 milisegundos, o processo é removido
para fila Q1.
– Em Q1 o processo é tratado outra vez com FCFS e recebe
outros 16 milisegundos. Se ele ainda não termina ele é
interrompido e passado para fila Q2.
Operating System Concepts
5.25
Silberschatz and Galvin1999
Multiple-Processor Scheduling
•
•
•
•
CPU scheduling more complex when multiple CPUs are
available.
Homogeneous processors within a multiprocessor.
Load sharing
Asymmetric multiprocessing – only one processor accesses the
system data structures, alleviating the need for data sharing.
Operating System Concepts
5.26
Silberschatz and Galvin1999
Real-Time Scheduling
•
Hard real-time systems – required to complete a critical task
within a guaranteed amount of time.
•
Soft real-time computing – requires that critical processes receive
priority over less fortunate ones.
Operating System Concepts
5.27
Silberschatz and Galvin1999
Dispatch Latency
Operating System Concepts
5.28
Silberschatz and Galvin1999
Avaliação de Algoritmos
•
•
•
Modelamento deterministico – usa uma carga de trabalho
predeterminada e determina o desempenho do algoritmo para
esta carga de trabalho.
Modelas de filas (probabilistico)
Implementação
Operating System Concepts
5.29
Silberschatz and Galvin1999
Evaluation of CPU Schedulers by Simulation
Operating System Concepts
5.30
Silberschatz and Galvin1999