Please enable JavaScript.
Coggle requires JavaScript to display documents.
Escalonamento da CPU - Coggle Diagram
Escalonamento da CPU
Critérios de Escalonamento
Utilização de CPU
Manter a CPU ocupado
Throughput (vazão)
Número de processos que completam sua execução.
Tempo de Turnaround (tempo de retorno)
Quantidade de tempo para executar um processo em particular.
Tempo de Espera
Tempo em que um processo esteve esperando na fila
Tempo de Resposta
Tempo desde quando uma solicitação foi submetida até a primeira reposta
Critério de escalonamento
MAXimizar
Utilização de CPU
Throughput
MINimizar
Tempo de Turnaround (retorno)
Tempo de Espera
Tempo de Resposta
Algoritmos de Escalonamento
First Come, First Served (FCFS)
Algoritmo de baixa complexidade
abordagem não-preemptiva.
Insere processos na fila de prontos
Primeiro da fila é executado
O processo executa até que:
Termina a sua execução;
Realiza uma chamada ao sistema.
Favorece processos CPU-bound
Processos I/O-bound espera processos CPU-bound
Shortest Job First (SJF)
privilegia processos pequenos
Associa a cada processo a extensão de seu próximo burst
usa essas extensões para escalonar o processo
Dois esquemas:
Preemptivo
Shortest
Remaining Time First (SRTF).
Não preemptivo
Processo do pode ser apropriado até que termine seu burst
Difícil Saber a extensão da próxima requisição de CPU.
Utiliza previsão baseado em histórico do próximo burst de CPU
Escalonamento por Prioridade
Um número de prioridade (inteiro) é associado a cada processo
A CPU é alocada ao processo com a maior prioridade
Preemptivo
Não preemptivo
Problema = Estagnação (starvation)
Solução = Envelhecimento (aging)
Prioridade é o próximo tempo de burst de CPU previsto
Round Robin (RR)
Algoritmo típico do SO de tempo compartilhado.
Processo tremptado e adicionado no final da fila de pronto
Desempenho
q grande → FIFO
q pequeno → q deve ser grande com relação à
troca de contexto
Quantum de tempo entre 10-100 milissegundos
Multilevel Queue (Fila Multinível)
Filas particionadas
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
Fatia de tempo
20% para segundo plano no FCFS
Fila Multinível com Feedback
Um processo pode mover entre as diversas filas
Escalonador de fila de feedback multinível
Número de filas
Algoritmos de escalonamento para cada fila
Método para determinar o upgrade de um processo
Método usado para determinar quando rebaixar um processo
Método para determinar em qual fila um processo entrará
Escalonamento para
Multiprocessadores
compartilhamento de carga
Abordagens
Multiprocessamento Assimétrico
Processador único para todos as decisões
um processador acessa as estruturas de dados do sistema
Os outros processadores executam somente o código do usuário
Multiprocessamento Simétrico (SMP)
cada processador é auto-escalonado.
Existe um escalonador por processador
examina a fila de prontos comum e
seleciona um processo para executar.
Duas estratégias possíveis
Cada processador pode ter sua própria fila de threads.
threads podem estar em uma única fila de prontos
Processadores Multicore
Escalonamento mais Complexo
Todos os núcleos vão disputar o acesso a memória principal
Cada núcleo tem seu próprio cache local
núcleos podem ter de ficar vários ciclos esperando pela memória
SO precisa saber quais threads pertencem a núcleos físicos
Balanceamento de carga
cada processador tem sua própria fila de processos elegíveis
Tipos
Migração push
processador ocupado → processador ocioso
Migração pull
processador ocioso puxa tarefa de um processador ocupado
Afinidade de processador
Evita Inconsistência de cache
Tipos
Afinidade flexível/leve
SO tenta manter o processo em um único processador
Afinidade rígida
Permite o processor escolher subconjunto de processadores
Escalonamento de thread
Threads em nível de kernel é que são escalonadas
As threads em nível de usuário são gerenciadas
threads no nível
de usuário precisam ser mapeadas
Conceitos Básicos
Ciclo de Picos CPU-E/S
1 - Carrega e adiciona memória
2 - Lê arquivo
Esperar por I/O
3 - Armazenamento Incremento
4 - Indexa e grava arquivo
Escalonador de CPU
Escalonamento não-preemptivo ou cooperativo.
Escalonamento preemptivo
problema com acesso a dados compartilhados
Despachante
dá o controle da CPU ao processo selecionado
Isso envolve
troca de contexto
troca para o modo usuário
salto para o local apropriado no programa do usuário
Latência de despacho
Tempo para terminar um processo e começar outro
Observações
Arquitetira Homogênea x Arquitetura Heterogênea
Componentes de hardware são idênticos e têm a mesma função
arquitetura heterogênea
Componentes Diferentes para arquitetura, função e etc
melhorar o desempenho e a eficiência do sistema