06 Escalonamento

Prévia do material em texto

Sistemas Operacionais
Escalonamento
Prof. Humberto Caetano
Humberto.ccs@gmail.com
2/28
Escalonamento
● Em sistemas multiprogramados existe a figura 
do escalonador.
● Este programa do sistema operacional é 
responsável por escolher quem vai para o 
processador quando um processo recebe uma 
interrupção
● Os algoritmos de escalonamento são as 
ferramentas utilizadas para gerenciar esse 
processo.
3/28
Escalonamento
● Introdução
– Em sistemas em lote antigos o escalonamento era 
muito simples, apenas execute a próxima instrução.
– Com o surgimento da multiprogramação, veio a 
necessidade de “escolhermos” qual o programa 
que irá ser executado quando um que estava no 
processador for suspenso.
4/28
Escalonamento
● Introdução
– Computadores de usuários tem requisições muito 
diferentes. Para um usuário é importante que o 
programa que ele está operando execute com 
fluidez.
– Servires executam várias tarefas ao mesmo tempo 
e tem que atender, ainda, as requisições de 
usuários que estão conectados a ele.
5/28
Comportamento de um 
Processo
● Todos os processos tem momentos em que 
estão usando a CPU e momentos que estão 
fazendo E/S.
● Alguns processos tem maior interesse em 
utilizar a CPU, são processos orientados a 
CPU, enquanto outros passam mais tempo 
trabalhando com E/S, processos orientados a 
E/S.
6/28
Comportamento de um 
Processo
7/28
Quando Escalonar
● Situações nas quais o escalonamento é necessário:
– No momento da criação de um novo processo. Qual será 
executado o pai ou o filho?
– No momento que um processo é encerrado. O 
processador está livre, quem será executado em 
seguida?
– Um processo solicitou uma E/S, ou um semáforo. 
– Um dispositivo de E/S gerou uma interrupção. 
Executamos o processo que estava esperando essa 
informação?
8/28
Quando Escalonar
● Os algoritmos de escalonamento podem ser 
divididos em duas categorias:
– Não preemptivos
● Permite que um processo seja executado até que ele 
seja bloqueado (E/S, outro processo), ou até que ele 
libere voluntariamente a CPU.
– Preemptivos
● Escolhe um processo a ser executado e o deixa em 
execução por um tempo máximo fixado.
9/28
Algoritmos de Escalonamento
● Lote
– São sistemas ainda utilizados para processamento em 
grande escala
● Interativo
– Sistemas muito comuns, estão presentes em nossos 
desktops, celulares, servidores, etc
● Tempo Real
– São sistemas que precisam de uma resposta imediata 
frente a um estímulo, como máquinas de UTI, robôs, etc.
10/28
Objetivos do Algoritmo
11/28
Escalonamento em Sistemas
em Lote
● Primeiro a chegar, primeiro a ser servido 
(FCFS)
– Existe uma fila única de processos. A primeira 
tarefa do dia é executada até que ela termine ou 
que ocorra um bloqueio por E/S. Esse processo 
bloqueado é colocado no fim da fila assim que 
estiver pronto.
12/28
Escalonamento em Sistemas
em Lote
● Tarefa mais curta primeiro (SJF).
– Neste algoritmo sabemos o tempo de execução de 
uma tarefa.
– A tarefa mais rápida é colocada primeiro no 
processador e assim por diante.
– Este algoritmo requer que as tarefas estejam 
disponíveis no processador para que este escolha 
qual será executada.
13/28
Escalonamento em Sistemas
em Lote
● Próximo de menor tempo restante.
– Aqui o escalonador executa a tarefa que tem o 
menor tempo restante de processamento.
– O escalonador verifica se para terminar a tarefa 
atual demora mais que terminar uma outra tarefa, 
ele suspende a tarefa atual e inicia a que está 
próxima de ser encerrada.
14/28
Escalonamento em Sistemas
Interativos
● Escalonamento por chaveamento circular 
(round robin)
– A cada processo é atribuído um intervalo de tempo, 
o quantum do processo.
– Caso o tempo do processo se encerre, ele será 
bloqueado e outro processo será sorteado para seu 
lugar.
15/28
Escalonamento em Sistemas 
Interativos
● Escalonamento por chaveamento circular 
(round robin)
– O chaveamento do processo para outro requer 
tempo e precisamos balancear a execução dos 
processos com o chaveamento.
– Caso o chaveamento dure 1ms, e o quanta seja de 
4ms, o sistema gastará 20% do seu tempo só para 
alternar entre processos.
16/28
Escalonamento em Sistemas 
Interativos
● Escalonamento por chaveamento circular 
(round robin)
– Outra possibilidade é utilizarmos o quanta de 
100ms, assim o chaveamento custaria apenas 1%.
– Mas nesse caso, se tivéssemos 50 processos no 
sistema, um simples comando ls poderia demorar 5 
segundos para ser executado.
– O ideal é tentarmos balancear o quanta entre 20ms 
e 50ms.
17/28
Escalonamento em Sistemas 
Interativos
● Escalonamento por prioridades
– O escalonamento por prioridades tenta resolver o 
problema de executar primeiro o que é mais 
importante.
– As prioridades podem ser atribuídas a um processo 
de forma estática ou dinâmica.
– No Unix existe o comando nice que pode alterar a 
prioridade de um processo.
18/28
Escalonamento em Sistemas 
Interativos
● Próximo processo mais curto.
– Em geral, em sistemas interativos, comandos são 
processos curtos, que são executados pelo 
usuário.
– Pode ser interessante executar esse comando 
logo, pois o usuário estará aguardando a resposta 
do mesmo.
19/28
Escalonamento em Sistemas 
Interativos
● Escalonamento por loteria
– A ideia é fazer um sorteio entre os processos que 
estão aguardando para serem executados, assim, 
em teoria, existirá uma divisão justa de 
processamento para cada processo.
– Caso o sistema trabalhe com prioridades, basta 
gerar um número maior de bilhetes para um 
processo de alta prioridade, assim no sorteio ele 
terá mais chances.
20/28
Escalonamento em Sistemas 
de TR
● Em geral os sistemas de tempo real são 
categorizados em dois tipos:
– Tempo real crítico → prazos absolutos devem ser 
cumpridos.
– Tempo real não crítico → o descumprimento 
ocasional de um prazo é indesejável, mas tolerável.
21/28
Escalonamento em Sistemas 
de TR
● Um sistema de tempo real precisa atender a 
eventos periódicos e não periódicos. 
● Cada evento gera um processo que deve ser 
tratado pela CPU.
● Existe a possibilidade de vários processos 
ocorrerem simultaneamente no sistema.
22/28
Escalonamento em Sistemas 
de TR
● Caso existam m eventos periódicos, e o evento 
i ocorrer em um período Pi e requer Ci 
segundos de CPU para executar, então para 
que o sistema seja escalonável, o somatório 
dos eventos no período deve ficar abaixo de 1.
23/28
Escalonamento em Sistemas 
de TR
● Exemplo:
– Um sistema com três eventos periódicos com 
períodos de 100, 200 e 500ms. 
– Cada evento requer 50, 30 e 100ms de tempo de 
CPU por evento.
– O sistema é escalonável pois 
● 50/100 + 30/200 + 100/500 = 0,85
24/28
O Problema do Jantar dos 
Filósofos
25/28
O Problema do Jantar dos 
Filósofos
26/28
Trabalho 1
● Implemente um conjunto de algoritmos de 
escalonamento de CPU e escreva um programa 
que calcula uma série de estatísticas baseado 
nestes algoritmos:
● Os algoritmos de escalonamento a serem 
implementados são os seguintes:
– FCFS: First-Come, First-Served
– SJF: Shortest Job First
– RR: Round Robin (com quantum = 2)
27/28
Trabalho 1
● O programa deverá ler da entrada padrão uma 
lista de processos com seus respectivos 
tempos de chegada e de duração. Em seguida 
deverá imprimir na saída padrão uma tabela 
contendo os valores para as seguintes 
métricas:
– Tempo de retorno médio 
– Tempo de resposta médio
– Tempo de espera médio
28/28
Trabalho 1
● Descrição da entrada:
– A entrada é composta pares de números inteiros separados por um espaçoem branco 
indicando o tempo de chegada e a duração de cada processo. Exemplo de entrada 1:
● 0 20
● 0 10
● 4 6
● 4 8
● Descrição da saída:
– A saída é composta por linhas contendo a sigla de cada um dos três algoritmos e os 
valores das três métricas solicitadas. Cada linha apresenta os valores médios (com 
uma casa decimal) para tempo de retorno, tempo de resposta e tempo de espera, 
separados por um espaço em branco. Exemplo de saída 1 :
● FCFS 30,5 19,5 19,5
● SJF 21,5 10,5 10,5
● RR 31,5 2,0 20,5
	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