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