Escalonamento da CPU
scheduling da CPU é a base dos sistemas operacionais multiprogramados
Conceitos Básicos
ter sempre algum processo em execução
Escalonador de CPU
escalonamento de CPU podem ocorrer quando um processo
Passa do estado executando para esperando
Passa do estado executando para pronto
Passa de esperando para pronto
Termina
Despachante
dispatcher dá o controle da CPU ao processo selecionado pelo escalonamento de curto prazo
troca de contexto
troca para o modo usuário
salto para o local apropriado no programa do usuário para reiniciar esse programa
Latência de despacho
tempo para que o despachante termine um processo
Critérios de Escalonamento
Existem diversos algoritmos de escalonamento
principais critérios
Utilização de CPU
Mantenha a CPU tão ocupada quanto possível
Throughput (vazão)
Número de processos que completam sua execução por unidade de tempo
Tempo de Turnaround
tempo de retorno
Quantidade de tempo para executar um processo em particular
Tempo de Espera
Tempo de Resposta
Tempo em que um processo esteve esperando na fila de prontos
Tempo desde quando uma solicitação foi submetida até a primeira reposta ser produzida
Algoritmos de Escalonamento
Por prioridade
Round-Robin (RR)
Shortest Job First (SJF)
Multilevel Queue (Fila Multinível)
First Come, First Served (FCFS)
Multilevel Feedback-Queue
“Primeiro-a-Chegar, Primeiro-a-Ser-Atendido”
abordagem não-preemptiva
Processos que se tornam aptos para execução são inseridos no final da fila de prontos
processo executa até que
Termina a sua execução
Realiza uma chamada ao sistema
Favorece processos CPU-bound.
I/O-bound têm que esperar até que processos CP -bound terminem
“Menor-Job-Primeiro”
privilegiando processos pequenos o tempo médio de espera decresce
Dois esquemas:
Não preemptivo
Preemptivo
uma vez a CPU dada ao processo
gera o menor tempo de espera médio para determinado conjunto de processos
Dificuldade principal
Saber a extensão da próxima requisição de CPU
Um número de prioridade (inteiro) é associado a cada processo
menor inteiro = maior prioridade
Problema
Preemptivo
Não preemptivo
starvation
processos com baixa
prioridade podem nunca ser executados
Solução
aging
à medida que o tempo
passa, aumenta a prioridade do processo
tempo compartilhado
Desempenho
q grande → FIFO
q pequeno → q deve ser grande com relação à troca de contexto
primeiro plano (interativo) e segundo plano (batch)
Primeiro plano – RR
Segundo plano – FCFS
O escalonamento precisa ser feito entre as filas
Escalonamento com prioridade fixa
Fatia de tempo
cada fila recebe uma certa quantidade de tempo de CPU
20% para segundo plano no FCFS
Um processo pode mover entre as diversas filas;
definido pelo seguintes parâmetros
Número de filas
Método usado para determinar quando rebaixa um processo
Algoritmos de escalonamento para cada fila
Método usado para determinar quando fazer o upgrade de um processo
Método usado para determinar em qual fila um processo entrará quando esse processo precisar de serviço
Escalonamento para Multiprocessadores
compartilhamento de carga.
O termo multiprocessador pode se aplicar
Processadores Multicore
Núcleos Multithread
Sistemas NUMA
Multiprocessamento Heterogêneo
Abordagens
Multiprocessamento Assimétrico
modelo mais simples onde
das as decisões de escalonamento, processamento de E/S
outras atividades são tratadas por um processador único
Multiprocessamento Simétrico (SMP)
cada processador é auto- escalonado. Existe um escalonador por processador
Duas estratégias possíveis:
Todas as threads podem estar em uma única fila de prontos
Cada processador pode ter sua própria fila de threads
Processadores Multicore
Balanceamento de carga
vários núcleos de processamento num
único chip (processador multicore)
Cada núcleo é uma “CPU completa”
aparece como um processador lógico separado para o SO
aparece como múltiplos processadores lógicos para o SO
Objetivo:
Tentar manter a carga de trabalho distribuída
uniformemente entre todos os processadores
Tipos:
Migração push
Migração pull
processador ocupado → processador ocioso
Um processador ocioso puxa uma tarefa
esperando de um processador ocupado
Afinidade de processador
Tipos:
Afinidade flexível/leve:
Afinidade rígida:
permite que um processo especifique um subconjunto
o sistema operacional tenta manter o processo em um único processador
Escalonamento de thread
Threads em nível de kernel é que são escalonadas pelo SO e não os processos