13 - Escalonamento

Prévia do material em texto

Fundamentos de Sistemas 
Operacionais
Gerência de processos
Escalonamento de processos
 IES - Osmar da Cunha Filho 2
Escalonamento de processos
● É a base de sistemas operacionais multitarefas
● Torna o computador mais produtivo
● Em sistemas multithread, na verdade são as 
threads que são escalonadas
– Pode-se falar em escalonamento de threads e de 
processos
 IES - Osmar da Cunha Filho 3
Escalonamento de processos
● Considere um sistema monoprocessado
● Apenas um processo é executado por vez
● Os outros processos devem esperar a CPU 
ficar livre para ser reagendado
● Tipicamente, o processo em execução deve 
esperar até que E/S responda a uma requisição
– Tempo de espera é perdido
– Nenhuma outra tarefa tem prosseguimento
 IES - Osmar da Cunha Filho 4
Escalonamento de processos
● Sistemas multitarefas 
tentam utilizar melhor 
esse tempo perdido, 
mantendo diversos 
processos em 
memória
● Enquanto um espera 
resposta, outro pode 
ganhar tempo da 
CPU
 IES - Osmar da Cunha Filho 5
Escalonamento de processos
● Escalonar processos depende de uma 
propriedade da execução dos processos
– Ciclos de execução de CPU
● CPU burst
– Espera de E/S
● I/O burst
● Processos alternam entre esses estados
– Processos começam e terminam com explosões de 
CPU
– Em seguida aguardam explosões de E/S
 IES - Osmar da Cunha Filho 6
Escalonamento de processos
● Quando os processos ficam ociosos o SO deve 
selecionar outro processo que esteja pronto na 
lista para ser executado
● Quem seleciona o próximo processo é o 
escalonador de processos
● O escalonador seleciona um processo da 
memória e aloca a CPU
 IES - Osmar da Cunha Filho 7
Escalonamento de processos
● Não necessariamente é uma fila de processos 
(FIFO)
– First In, First Out
● Pode ser uma fila com prioridades, uma lista 
desordenada
● São apenas processos esperando a execução
 IES - Osmar da Cunha Filho 8
Escalonamento preemptivo
 IES - Osmar da Cunha Filho 9
Escalonamento de processos
Escalonamento preemptivo
● Preemptar
– Retirar recurso de
– Deslocar
– Trocar
 IES - Osmar da Cunha Filho 10
Escalonamento de processos
Escalonamento preemptivo
 IES - Osmar da Cunha Filho 11
Escalonamento preemptivo
● O escalonador atua no momento das transições 
de estados dos processos
– Do estado rodando para o estado em espera
● E/S
– Do estado rodando para o estado pronto
● Interrupção
– Do estado esperando para o estado pronto
● Chegou resposta de uma E/S
– Quando o processo termina
 IES - Osmar da Cunha Filho 12
Escalonamento preemptivo
● Se o escalonador somente atua em
– Do estado rodando para o estado em espera
– Quando o processo termina
● Diz-se que o escalonador é não-preemptivo ou 
cooperativo
● Em outras palavras, o escalonador não retira 
os recursos do processo em execução, 
esperando ele chegar em um estado de espera 
ou ao fim
 IES - Osmar da Cunha Filho 13
Escalonamento preemptivo
● Senão, diz-se que o escalonador é preemptivo
● Em outras palavras, o escalonador retira os 
recursos do processo em execução, passando 
para outro processo
 IES - Osmar da Cunha Filho 14
Escalonamento preemptivo
● Consequências do escalonamento preemptivo 
– Gerar mais condições de corrida
● Processos subsequentes podem querer acessar o 
mesmo dado
– Ao tratar uma chamada de sistema, o processo em 
execução está no modo kernel
– Pode chegar uma interrupção durante o processo
 IES - Osmar da Cunha Filho 15
Critérios de escalonamento
Algoritmo de escalonamento
● Cada algoritmo de escalonamento favorece um 
tipo de problema
– Utilização de CPU
● Manter a CPU em uso o maior tempo possível
– Vazão de processos
● Quantidade de processos completados por unidade de 
tempo
– Turnaround
● Tempo do início ao fim do processo: contabiliza tempo de 
espera de E/S, aguardando na fila para execução, 
acessando a memória
 IES - Osmar da Cunha Filho 16
Critérios de escalonamento
Algoritmo de escalonamento
● Tempo de espera
– Tempo esperando na fila para execução (tempo no 
estado pronto)
● Tempo de resposta
– Tempo de uma requisição até receber sua resposta 
(não necessariamente tratá-la)
 IES - Osmar da Cunha Filho 17
Critérios de escalonamento
Algoritmo de escalonamento
● Geralmente tenta-se
– Aumentar a utilização de CPU e a vazão
– Diminuir os tempos de turnaround, de espera e de 
resposta
● Para sistemas interativos
– Melhor minimizar os tempos de resposta
 IES - Osmar da Cunha Filho 18
Critérios de escalonamento
Algoritmo de escalonamento
● Como há diversas formas de equilibrar os 
critérios, há diversos algoritmos para escalonar 
os processos
– First-come, First-served
– Shortest-job-first
– Prioridade
– Round-Robin
– Pilha multinível
 IES - Osmar da Cunha Filho 19
Algoritmos de escalonamento
First-come, first-served (FCFS)
● O mais simples de todos
● O processo que solicitar CPU é atendido 
primeiro
● A implementação é feita por uma fila de 
processos
– Quando um processo muda para o estado pronto, 
vai para o fim da fila
– Quando a CPU fica livre, pega o primeiro da fila
 IES - Osmar da Cunha Filho 20
Algoritmos de escalonamento
First-come, first-served (FCFS)
● Desvantagem é que um processo pode 
demorar muito até um processo liberar a CPU
● Algoritmo não preemptivo
– A CPU uma vez alocada, continua neste processo 
até que ele libere a CPU (terminando ou 
requisitando E/S)
 IES - Osmar da Cunha Filho 21
Algoritmos de escalonamento
Shortest-job-first
● Este algoritmo associa a duração do processo 
com a duração do próximo intervalo de CPU
● Quando a CPU fica livre, é escolhido o 
processo que possui a próxima menor duração 
de CPU
● A dificuldade é medir qual a duração de CPU 
que o processo terá
– Sistemas em batch com tempos previstos
 IES - Osmar da Cunha Filho 22
Algoritmos de escalonamento
Prioridade
● Uma prioridade é associada com cada 
processo
● Quando ficar livre, aloca-se a CPU para o 
processo com maior prioridade
● Prioridades geralmente variam em uma faixa de 
valores fixos
– 7 a 0, 0 a 4095
– Não há consenso se um número menor é mais 
prioritário
– Geralmente esse é o caso: número menor tem 
maior prioridade
 IES - Osmar da Cunha Filho 23
Algoritmos de escalonamento
Prioridade
● A prioridade pode ser definida internamente
– Utilizando critérios do próprio sistema operacional
– Tempos, memória, quantidade de arquivos abertos, 
média de requisições de E/S, média de tempo de 
CPU
● Ou pode ser definida externamente
– Utilizando critério de fora do sistema operacional
– Importância para o usuário, patrocínio, fatores 
políticos
 IES - Osmar da Cunha Filho 24
Algoritmos de escalonamento
Prioridade
● Pode ser preemptivo ou não-preemptivo
● Quando um processo vai para o estado de 
pronto, compara-se sua prioridade com a 
prioridade do processo em execução
– No caso preemptivo: se o processo pronto tiver uma 
prioridade maior, o escalonador pode preemptar a 
CPU para alocar esse processo
– No caso não-preemptivo: coloca-se o processo no 
início da fila de processos prontos
 IES - Osmar da Cunha Filho 25
Algoritmos de escalonamento
Prioridade
● O principal problema é o bloqueio indefinido 
ou inanição
– Os processos de menor prioridade sempre vão para 
o final da fila
– Solução: ir incrementando a prioridade de 
processos mais antigos de tempos em tempos
 IES - Osmar da Cunha Filho 26
Algoritmos de escalonamento
Round-Robin
● É similar ao FCFS, mas tem preempção para 
trocar os processos
● Uma pequena unidade de tempo é definida
– Quantum, fatia
– Duração de 10, 100, 200 ms
● A fila de processos prontos é tratada de forma 
circular (após o último, volta para o primeiro)
● Aloca-se uma fatia de tempo (1 quantum) para 
cada processo
 IES - Osmar da Cunha Filho 27
Algoritmos de escalonamento
Round-Robin
● O processo tem 1 quantum de CPU para 
executar suas instruções (explosão de CPU)
● Se o timer estourar e o processo precisar de 
mais de 1 quantum para completar sua tarefa, o 
escalonadorarmazena os dados desse 
processo e faz uma troca de contexto para o 
próximo processo
 IES - Osmar da Cunha Filho 28
Algoritmos de escalonamento
Pilha multinível
● Algoritmo criado quando há grupos/classes de 
processos
– Foreground (interativos)
– Background
● Como esses grupos tem tempos de resposta 
distintos, podem ser escalonados 
diferentemente
 IES - Osmar da Cunha Filho 29
Algoritmos de escalonamento
Pilha multinível
● Divisão em níveis
– Processos de sistema
– Processos interativos
– Processos de lote (batch)
● Para a execução do nível seguinte, deve-se 
tratar todos os processos do nível anterior
 IES - Osmar da Cunha Filho 30
Escalonamento em múltiplos processadores
 IES - Osmar da Cunha Filho 31
Escalonamento em múltiplos 
processadores
● Em sistemas com múltiplos processadores, 
pode-se compartilhar a carga
– Dividir a execução dos processos
● Concentrar em sistemas de processadores 
idênticos
 IES - Osmar da Cunha Filho 32
Escalonamento em múltiplos 
processadores – Assimétrico
● Multiprocessamento assimétrico
– Todas as decisões do escalonador, operações de 
E/S e atividades do sistema são feitas por um 
processador
– Os outros processador executam apenas código do 
usuário
● Chama-se assimétrico porque apenas um 
processador acessa dados do sistema, 
reduzindo a necessidade de compartilhamento 
de dados
 IES - Osmar da Cunha Filho 33
Escalonamento em múltiplos 
processadores – Simétrico
● Multiprocessamento simétrico (SMP)
– Cada processador escalona
– Todos os processos prontos ficam em uma fila 
(acessíveis ou não a todos os processadores)
– Cada processador escolhe uma desses processos e 
o executa
● O escalonador deve tomar cuidado ao acessar 
essa fila compartilhada
– Dois processadores não podem escolher o mesmo 
processo
 IES - Osmar da Cunha Filho 34
Escalonamento em múltiplos 
processadores – Afinidade
● Considerando um processo em execução em 
um processador
● Os acesso à memória ficam na cache deste 
processador
 IES - Osmar da Cunha Filho 35
Escalonamento em múltiplos 
processadores – Afinidade
● Se este processo passa a ser executado em 
outro processador, os dados não estão mais na 
cache e os acessos à memória aumentam
● Devido ao custo de ter que consultar a 
memória, tende-se que um processo fique 
sempre no mesmo processador
● Isto é a afinidade do processador
 IES - Osmar da Cunha Filho 36
Escalonamento em múltiplos 
processadores – Balanceamento
● Em sistemas de processamento simétrico é 
importante que a carga de trabalho seja dividida 
em todos os processadores
● Então o balanceamento de carga tenta 
distribuir os processos nos processadores
– Em sistemas com uma fila de processos acessível a 
todos os processadores isto é desnecessário, pois 
cada processador pega o próximo processo pronto
 IES - Osmar da Cunha Filho 37
Escalonamento em múltiplos 
processadores – Balanceamento
● O balanceamento de carga pode seguir duas 
linhas
– Migração puxada (Pull migration)
● Funciona quando um processador puxa um processo em 
espera de outro processador
– Migração empurrada (Push migration)
● Uma tarefa de sistema verifica os processadores mais 
ocupados e empurra os processos de um processador 
mais ocupado para um processador mais livre
 IES - Osmar da Cunha Filho 38
Referências
● SILBERSCHATZ. Sistemas operacionais (9 ed.)
– Capítulo 6
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38