Please enable JavaScript.
Coggle requires JavaScript to display documents.
Escalonamento da CPU - Coggle Diagram
Escalonamento da CPU
Escalonamento para
Multiprocessadores
Escalonamento de CPU mais complexa quando múltiplas CPUs estão disponíveis
Com múltiplas CPUs é possível fazer o compartilhamento de carga
O termo multiprocessador pode se aplicar a
Processadores Multicore
vários núcleos de CPU num único processador
Núcleos Multithread
cada núcleo de CPU consegue operar com 2 ou mais threads “simultaneamente”
Sistemas NUMA
(Múltiplos processadores, cada um com sua própria memória local
Multiprocessamento Heterogêneo
vários núcleos que rodam as mesmas
instruções
mas tem poder de processamento e consumo energético diferentes
Abordagens
Multiprocessamento Assimétrico
modelo mais simples onde todas as decisões de escalonamento, processamento de E/S
Multiprocessamento Simétrico (SMP)
cada processador é auto-escalonado
Duas estratégias possíveis
Todas as threads podem estar em uma única fila de prontos (comum ao sistema)
Cada processador pode ter sua própria fila de threads
Processadores Multicore
vários núcleos de processamento num
único chip
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, caso possua capacidade de fazer Simultaneous Multithreading
Processadores multicore tem escalonamento mais complexo por diversas razões
Todos os núcleos vão disputar o acesso a memória principal
Cada núcleo tem seu próprio cache local (L1 e L2, geralmente)
Visto existirem esses problemas
núcleos podem ter de
ficar vários ciclos esperando pela memória e isso diminui o desempenho
Balanceamento de carga
Objetivo
Tentar manter a carga de trabalho distribuída
uniformemente entre todos os processadores num sistema SMP
Necessária apenas quando cada processador tem sua própria fila de processos elegíveis
Tipos
Migração push
Uma tarefa específica verifica periodicamente
a carga de cada processador e eventualmente redistribui a carga
Migração pull
Um processador ocioso puxa uma tarefa
esperando de um processador ocupado
Afinidade de processador
Problema: Inconsistência de cache
Evitando o problema
afinidade de processador
Tipos
Afinidade flexível/leve
o sistema operacional tenta manter o
processo em um único processador
mas é possível que um processo migre entre processadores
Afinidade rígida
permite que um processo especifique um
subconjunto de processadores em que ele pode ser executado
Escalonamento de thread
Threads em nível de kernel é que são
escalonadas pelo SO e não os processos
As threads em nível de usuário são
gerenciadas pela biblioteca de threads
e o kernel não as conhece
Para executar numa CPU
as threads no nível de usuário precisam ser mapeadas a uma thread no nível do kernel
utilizando um LWP
(processo leve)
Algoritmos de Escalonamento
First Come, First Served (FCFS)
Algoritmo de baixa complexidade
Exemplo de abordagem não-preemptiva
Processos que se tornam aptos para execução são inseridos no final da fila de prontos
O primeiro processo da fila é selecionado para execução
O processo executa até que
Termina a sua execução
Realiza uma chamada ao sistema
Processos pequenos podem ter que esperar por muito tempoaté que possam ser executados
Favorece processos CPU-bound
Algoritmo particularmente problemático para
sistemas de tempo compartilhado
onde os usuários precisam da CPU a intervalos regulares
Shortest Job First (SJF)
“Menor-Job-Primeiro”
Dois esquemas
Não preemptivo
Preemptivo
Privilegiando processos pequenos o tempo
médio de espera decresce
SJF é ideal
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
SJF real é impossível de ser implementado
Mas é possível aproximá-lo
usando uma previsão do próximo burst de CPU
Previsão é baseada em histórico
Por prioridade
Um número de prioridade (inteiro) é associado a cada processo
A CPU é alocada ao processo com a maior prioridade
(menor inteiro = maior prioridade)
Preemptivo
Não preemptivo
SJF é um escalonamento por prioridade
onde a prioridade é
o próximo tempo de burst de CPU previsto
Estratégia usada em S.O. de tempo real
Problema = Estagnação (starvation)
processos com baixa prioridade podem nunca ser executados
Solução = Envelhecimento (aging)
à medida que o tempo passa, aumenta a prioridade do processo
Round-Robin (RR)
Algoritmo típico de sistemas operacionais de
tempo compartilhado
Cada processo recebe uma pequena unidade
de tempo de CPU
Depois que esse tempo tiver passado, o
processo é interrompido (“preemptado”)
e acrescentado ao final da fila de prontos
Desempenho
q grande → FIFO
q pequeno → q deve ser grande com relação à troca de contexto
ou então o overhead é muito
alto (muitas trocas de contexto)
Multilevel Queue (Fila Multinível)
Fila de pronto está particionada em duas filas separadas
primeiro plano (interativo)
segundo plano (batch)
Cada fila tem seu próprio algoritmo de escalonamento
Primeiro plano – RR
Segundo plano – FCFS
O escalonamento precisa ser feito entre as filas
Escalonamento com prioridade fixa
serve tudo em primeiro plano, depois em segundo plano
Possibilidade de estagnação
Fatia de tempo
cada fila recebe uma certa quantidade de
tempo de CPU
80% para primeiro plano no RR
20% para segundo plano no FCFS
Multilevel Feedback-Queue (Fila Multinível com Feedback)
Um processo pode mover entre as diversas filas
Escalonador de fila de feedback multinível definido pelos seguintes parâmetros
Número de filas
Algoritmos de escalonamento para cada fila
Método usado para determinar quando fazer o upgrade de um processo
Método usado para determinar quando rebaixar um processo
Método usado para determinar em qual fila um processo entrará quando esse processo precisar de serviço
Conceitos Básicos
Objetivo principal da multiprogramação
ter sempre algum processo em execução
Escalonamento (scheduling)
Quando um processo precisa esperar
SO atribui a CPU a um outro
processo
Quase todos os recursos do computador são
escalonados antes do uso
A CPU é o principal deles
Ciclo de Picos CPU-E/S
Execução de um processo =
ciclo de execução + espera por
E/S.
SO deve observar e armazenar
essas estatísticas a respeito da execução dos processos
a fim de manter a CPU ocupada
Escalonador de CPU
Seleciona dentre os processos na memória que estejam prontos para executar
e aloca a CPU a um deles
Decisões de escalonamento de CPU
podem ocorrer quando um
processo
1.Passa do estado executando para esperando
não há alternativa no que diz respeito ao
escalonamento
2.Passa do estado executando para pronto
Há uma alternativa
Escalonamento preemptivo
já que o processo libera a CPU por decisão do SO
3.Passa de esperando para pronto
4.Termina
não há alternativa no que diz respeito ao
escalonamento
Exemplos de SO’s
Escalonamento não-preemptivo ou cooperativo
Windows 3.1
macOS antes da versão 10
Escalonamento preemptivo
Windows 95 e posteriores
macOS
Unix e Linux
Escalonamento preemptivo
potencial problema
com acesso a dados compartilhados
Despachante
Módulo despachante (dispatcher)
dá o controle da CPU ao processo selecionado
pelo escalonamento de curto prazo
isso envolve
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 e inicie outro
Exemplo de Sistema Operacional:
Windows
Escalonamento baseado em prioridade, preemptivo
Thread de maior prioridade sempre será executada
O despachante seleciona uma thread e ela será executada até
ser interrompida por uma thread de maior prioridade
terminar
seu quantum de tempo terminar ou
até invocar uma chamada de sistema bloqueante (como uma E/S)
O esquema de prioridade usa 32 níveis
divididos
em duas classes
Classe variável: prioridades de 1 a 15
Classe de tempo real: prioridades de 16 a 31
(prioridade 0: gerenciador de memória)
Deixando mais claro alguns
termos importantes do capítulo
Arquitetura homogênea x heterogênea
arquitetura homogênea
todos os componentes de hardware são idênticos e têm a mesma função
arquitetura heterogênea
os componentes de hardware são
diferentes em termos de arquitetura, função...
Multiprocessamento homogêneo x heterogêneo
multiprocessamento homogêneo
todos os processadores são idênticos
multiprocessamento heterogêneo
os processadores são diferentes e combinados para melhorar o desempenho e a eficiência do sistema
Multiprocessamento simétrico (SMP) x Assimétrico (ASMP)
SMP
todos os processadores têm acesso igualitário aos recursos do sistema
ASMP
processadores têm diferentes funções e
capacidades
Critérios de Escalonamento
Existem diversos algoritmos de escalonamento
Qual é o “melhor” algoritmo?
Principais critérios
Utilização de CPU
Mantenha a CPU tão ocupada quanto possível
entre 40 e 90%
MAXimizar
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
é o tempo
total
MINimizar
Tempo de Espera
Tempo em que um processo esteve esperando na fila de prontos
Tempo de Resposta
Tempo desde quando uma solicitação foi submetida até a primeira reposta ser produzida
não a saída