Please enable JavaScript.
Coggle requires JavaScript to display documents.
Escalonamento da CPU - Coggle Diagram
Escalonamento da CPU
Conceitos
Base em sistemas multiprogramados
Alternar a CPU entre processos
Maior produtividade
Escalonador
Seleciona o próximo processo pronto e aloca a CPU
Atua em 4 situações
A executar para esperando
Não preemptivo
Processo desiste voluntariamente da CPU
SO escolhe o próximo sem interromper o anterior
macOS antes da v. 10, Windows 3.1
A executar para pronto
A esperando para pronto
Preemptivo
SO pode interromper um processo a correr p/ priorizar outro
Windows 95 e posteriores, macOS, Unix e Linux
Risco potencial
Conflito em dados compartilhados
Termina
Funciona através da multiprogramação
CPU nunca ociosa
Processo = 1 ou mais threads
Thread = representa tarefa independente
Kernel decide qual thread será executada
Quase todos os recursos do computador são escalonados
CPU: principal
Ciclo de pico CPU - E/S
Ciclo de execução de um processo
Pico de execução na CPU
Instruções de código
Pico de E/S
Espera de operação interna
SO guarda estatísticas sobre os ciclos
Otimização
Despachante
Transfere a CPU ao processo escolhido pelo escalonador
Envolve...
Troca de contexto
Troca para o modo usuário
Salto no programa
Latência de depacho
Tempo "perdido" da gestão de troca
Algoritmos de Escalonamento
First Come, First Served (FCFS)
Não-preemptivo
Termina sua execução ou realiza uma chamada ao sistema
Baixa complexidade
O primeiro processo que chega à fila de prontos é o primeiro atendido pela CPU
Espera por processos longos
Favorece processos CPU-bound
Inadequado para tempo compartilhado
Efeito comboio
Processos curtos ficam presos a espera de um processo longo
Menos desempenho
Shortest Job First (SJF)
Privilegiar e executar primeiro processos mais curtos
Tempo médio de espera de todos diminui
Associa cada processo ao tempo de burst de CPU
Coloca no topo da fila o menor
Preemptivo
CPU alocada não é preemptada até o fim do burst
Não-preemptivo
Shortest Remaining Time First (SRTF)
Novo processo com burst menor que o restante do atual
Há preempção
SJF real é impossível de ser implementado
São feitas previsões baseadas em histórico
Por prioridade
Cada processo: número inteiro (sua prioridade)
Quanto menor o número inteiro, maior é a prioridade
Preemptivo ou não preemptivo
Problema: starvation
Solução: aging
Round-Robin (RR)
Típico de SOs de
tempo compartilhado
Quantum de tempo p/ processo (10 a 100 ms)
Tempo acabado, processo "preemptado"
N
processos na fila e um quantum
q
Cada um recebe
1/n
da CPU em fatias de até
q
(espera máx:
(n-1)q
)
q
grande -> FIFO
q
pequeno exige
q
alto frente à troca de contexto
Evitar overhead excessivo
Multilevel Queue
Filas de prontos separadas por tipo de processo
Cada fila tem seu algoritmo de escalonamento
Tempo entre as filas
Prioridade fixa
Fatia de tempo
Multilevel Feedback-Queue
Diferença entre a fila multinível estática
Um processo pode se mover entre as diferentes filas
Implementar envelhecimento dinâmico
Escalonador definido por...
N de filas
Algoritmos de cada fila
Critérios para descer ou subir um processo de fila
Fila onde um novo processo entra inicialmente
Critérios de Escalonamento
Utilização de CPU
CPU ocupada o máx. possível
Uso entre 40% e 90%
Throughput (vazão)
Processos concluídos por unidade de tempo
Tempo de Turnaround (tempo de retorno)
Qtd de tempo p/ executar um processo
Tempo de Espera
Tempo do processo esperando na fila de prontos
Tempo de Resposta
Tempo desde a submissão até a primeira resposta