Escalonamento de processos
Processos
Escalonamento
M. Sc. Luiz Alberto
[email protected]
• Quando um ou mais processos estão prontos para serem
executados, o sistema operacional deve decidir qual deles vai
ser executado primeiro.
• A parte do sistema operacional responsável por essa decisão
é chamada escalonador, e o algoritmo usado para tal é
chamado de algoritmo de escalonamento.
• O escalonamento de processo visa a alternância do uso da
CPU entre os processos buscando uma maior produtividade e
um uso mais efetivo do hardware do computador.
Aula - SO – Processos - Escalonamento
Estados do Processo
–1–
Prof. Luiz Alberto -
Tipos de Tarefas (temporal)
• Tarefas de tempo real
– Previsibilidade em seus tempos de respostas
• Tarefas interativas
– Eventos externos solicitados por usuários (desktop)
• Tarefas em lote (batch)
– Sem intervenção do usuário (processo de backup)
1 - Processo bloqueado para entrada
2 - Gerenciador desativa um processo
3 - Gerenciador ativa outro processo
4 - Entrada se torna disponível
Aula - SO – Processos - Escalonamento
–2–
Prof. Luiz Alberto -
Aula - SO – Processos - Escalonamento
–3–
Prof. Luiz Alberto -
Tipos de Tarefas (processador)
• Tarefas orientadas a processamento (CPU-bound
tasks)
– Uso intensivo do processador
– Passam a maior parte do tempo esperando respostas
dos dispositivos de entrada/saída
–4–
• Maximizar a utilização do processador.
• Maximizar a produção do sistema (throughput).
– Número de processos executados por unidade de tempo.
• Minimizar o tempo de execução (turnaround).
• Tarefas orientadas a entrada/saída (IO-bound
tasks)
Aula - SO – Processos - Escalonamento
Objetivos
Prof. Luiz Alberto -
Critérios de Escalonamento
– Tempo total para executar um determinado processo.
• Minimizar o tempo de espera.
– Tempo que um processo permanece na lista de aptos.
• Minimizar o tempo de resposta.
– Tempo decorrido entre uma requisição e a sua realização.
Aula - SO – Processos - Escalonamento
–5–
Prof. Luiz Alberto -
Critérios de Escalonamento
• Utilização de CPU
• Justiça
– fazer com que cada processo ganhe seu tempo justo
de CPU;
• Eficiência
– manter a CPU ocupado o máximo de tempo possível;
• Vazão (throughput)
– refere-se ao número de processos concluídos por unidade de tempo;
• Tempo de Retorno (turnaround)
– manter a CPU ocupada 100% do tempo (se houver
demanda);
– é o intervalo desde o momento da submissão do processo até o
momento do término do mesmo;
• Tempo de Espera
– é a soma dos períodos gastos aguardando na fila de espera;
• Tempo de Resposta
– tempo desde a submissão de uma requisição até a primeira resposta
ser produzida.
Aula - SO – Processos - Escalonamento
–6–
Prof. Luiz Alberto -
Aula - SO – Processos - Escalonamento
–7–
Prof. Luiz Alberto -
Tipos de Escalonadores de Processos
Tipos de Escalonadores de Processos
• Não-Preemptivos
• Preemptivos
– A tarefa em execução permanece no processador enquanto
tiver condições de executar
– Uma vez escalonado, o processo utiliza o processador até
que:
• Termine a sua execução
• Execute uma requisição de E/S ou Sincronização
• Libere voluntariamente o processador para outro processo
Aula - SO – Processos - Escalonamento
–8–
Prof. Luiz Alberto -
Algoritmos de Escalonamento
• Seleciona qual processo deve executar em um
determinado instante de tempo.
• Os algoritmos de escalonamento buscam:
– Obter bons tempos médios ao invés de maximizar ou
minimizar um determinado critério.
– Privilegiar a variância em relação a tempos médios.
Aula - SO – Processos - Escalonamento
– 10 –
Prof. Luiz Alberto -
– Nestes sistemas uma tarefa pode perder o
processador
– Uma vez escalonado, o processo utiliza o processador
até que:
•
•
•
•
•
Termine a sua execução
Execute uma requisição de E/S ou sincronização
Libere voluntariamente o processador para outro processo (yield)
Interrupção de relógio
Um processo de mais alta prioridade esteja pronto a executar
Aula - SO – Processos - Escalonamento
–9–
Prof. Luiz Alberto -
Algoritmos de Escalonamento
• Uma complicação que os escalonadores devem levar
em consideração é que cada processo é único e
imprevisível.
• Para que um processo não execute tempo demais,
praticamente todos os computadores possuem um
mecanismo de relógio (clock) que causa uma
interrupção periodicamente.
Aula - SO – Processos - Escalonamento
– 11 –
Prof. Luiz Alberto -
Exemplos de Algoritmos de Escalonamento
• FIFO (First-In First-Out) ou FCFS (First-Come
• First-Served).
• SJF (Shortest Job First) ou SPN (Shortest Process
Next).
• SRTF (Shortest Remaining Time First).
• HRRN (Highest Response Rate Next);
• Round-Robin.
• Priority.
• Multiple queue
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
– 12 –
First-Come, First-Served (FCFS)
• Exempo
Processo
– Ordem de execução: P1, P2 e P3
– Tempo médio de espera:
• tm = (0+24+27)/3 = 17 ms.
Aula - SO – Processos - Escalonamento
– 14 –
Tempo de
Execução
P1
24
P2
3
P3
3
Prof. Luiz Alberto -
First-Come, First-Served (FCFS)
• First-Come, First-Served (FCFS) – Primeiro a chegar,
primeiro a ser atendido
• Algoritmo de escalonamento do tipo não-preemptivo.
• O FCFS é facilmente implementado através de uma
FIFO.
• Processos que se tornam aptos são inseridos no final da
fila.
• O processo que está no início da fila é o próximo a
executar.
• Prejudica processos I/O-Bound.
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
– 13 –
First-Come, First-Served (FCFS)
• Exempo
– Ordem de execução: P2, P3 e P1
– Tempo médio de espera:
Processo
Tempo de
Execução
P1
24
P2
3
P3
3
• tm = (0 + 3 + 6) / 3 = 3 ms.
Aula - SO – Processos - Escalonamento
– 15 –
Prof. Luiz Alberto -
Shortest-Job-First (SJF)
Shortest-Job-First (SJF)
• Shortest-Job-First (SJF) – menor tarefa primeiro
• Escalonamento do tipo não-preemptivo.
• Originário do fato que o menor tempo médio é obtido quando se
executa primeiro os processos de menor ciclo de processador (I/OBound)
• Algoritmo ótimo, isso é, fornece o menor tempo médio de espera para
um conjunto de processos.
• Processos I/O-Bound são favorecidos.
• Dificuldade é determinar o tempo do próximo ciclo de CPU de cada
processo, porém
– pode ser empregado em processos batch (long term scheduler)
– Prever o futuro com base no passado
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
– 16 –
• Exempo
Aula - SO – Processos - Escalonamento
– 18 –
P1
6
P2
8
P3
7
P4
3
• tm = (0 + 3 + 9 +16) / 4 = 7 ms.
Aula - SO – Processos - Escalonamento
– 17 –
Prof. Luiz Alberto -
Round-Robin (RR)
• O algoritmo SJF em sua versão preemptiva é chamado de
SRTF (Shortest Remaining Time First) – menor tempo
restante primeiro.
Processo Tempo de Tempo de
Execução Chegada
• Exemplo:
• tm = ((10 - 1) +(1 - 1) + (17 - 2) + (5 - 3)) / 4 = 6,5 ms.
Tempo de
Execução
– Ordem de execução:P4 , P1 , P3 e P2
– Tempo médio de espera:
Shortest-Job-First (SJF)
– Ordem de execução:P1 , P2 , P4 , P1 , P3
– Tempo médio de espera:
Processo
P1
0
8
P2
1
4
P3
2
9
P4
3
5
Prof. Luiz Alberto -
•
•
•
•
•
•
•
Round-Robin (RR) – revezamento/alternância circular
Escalonamento do tipo preemptivo.
Algoritmo de escalonamento similar ao FCFS.
Uma unidade de tempo é definida (quantum/time slice).
Um quantum geralmente é definido entre 10 a 100 ms.
A fila de processos prontos é tratada como uma fila circular.
Ao serem executados, os processo que necessitam de mais
tempo que o quantum definido são colocados novamente na
fila de prontos.
Aula - SO – Processos - Escalonamento
– 19 –
Prof. Luiz Alberto -
Round-Robin (RR)
• Exempo
– Quantum de 4 ms.
– Ordem de execução:P1 , P2 , e P3
– Tempo médio de espera:
• tm = (0 + 4 + 7 + 6) / 3 = 5,66 ms.
Aula - SO – Processos - Escalonamento
– 20 –
Round-Robin (RR)
Processo
Tempo de
Execução
P1
24
P2
3
P3
3
Prof. Luiz Alberto -
Escalonamento Baseado em Prioridades
• Uma prioridade é associada a cada processo.
• A CPU é alocada ao processo de mais alta prioridade.
• Processos com prioridade iguais são escalonados em
ordem FCFS.
• O escalonamento baseado em prioridades pode ser
preemptivo ou não-preemptivo.
Aula - SO – Processos - Escalonamento
– 22 –
Prof. Luiz Alberto -
• Configurar um Quantum curto demais causa muita troaca de
processo e reduz a eficiência da CPU
• Configurá-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
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
– 21 –
Escalonamento Baseado em Prioridades
• O algoritmo SJF em sua versão preemptiva é chamado de
SRTF (Shortest Remaining Time First) – menor tempo
restante primeiro.
Processo
Tempo de Prioridade
Execução
• Exemplo:
– Ordem de execução:P2 , P5 , P1 , P3 e P4
– Tempo médio de espera:
• tm = (0 + 1 + 6 + 16 + 18) / 5 = 8,2 ms.
Aula - SO – Processos - Escalonamento
– 23 –
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2
Prof. Luiz Alberto -
Escalonamento Baseado em Prioridades
• Prioridade Estática
– A prioridade é mantida durante todo o tempo de vida do
processo.
• Prioridade Dinâmica
– A prioridade do processo é ajustada conforme o estado de
execução do processo e/ou do sistema (aging).
– Ajustar a prioridade em função da fração do quantum que foi
realmente utilizada pelo processo.
Aula - SO – Processos - Escalonamento
– 24 –
Prof. Luiz Alberto -
Múltiplas Filas
• Se as prioridades não forem ajustadas de tempos
em tempos, os processos nas classes de
prioridades mais baixas podem sofrer o fenômeno
que chamamos starvation (o processo nunca recebe
o processador, pois sua vez nunca chega).
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
Múltiplas Filas
• Os processo são classificados em diferentes grupos.
• Particiona a fila de processos prontos em várias filas
separadas.
• Um processo é associado permanentemente a uma
fila geralmente baseado em alguma propriedade.
• Cada fila tem seu próprio algoritmo de
escalonamento.
Aula - SO – Processos - Escalonamento
Problemas com prioridades
Prof. Luiz Alberto -
• Os processo são classificados em diferentes grupos.
• Particiona a fila de processos prontos em várias filas
separadas.
• Um processo é associado permanentemente a uma
fila geralmente baseado em alguma propriedade.
• Cada fila tem seu próprio algoritmo de
escalonamento.
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
Múltiplas Filas
Nível 1
(FIFO)
Dúvidas?
Usa a
CPU
Término
Usa a
CPU
Término
Usa a
CPU
Término
Preempção
Nível 2
(FIFO)
Preempção
Nível n
(round robin)
Preempção
Aula - SO – Processos - Escalonamento
Prof. Luiz Alberto -
Aula - SO – Processos - Escalonamento
– 29 –
Prof. Luiz Alberto -