Sistemas Operacionais:

Escalonamento de

processos

Escalonamento

Critrios de escalonamento

Algoritmos de escalonamento

Escalonamento em multiprocessadores

Escalonamento tempo real

Caractersticas de processos

Multiprogramao possibilita a mxima

utilizao da CPU

Processo:utilizao da CPU e E/S

Distribuio da utilizao da CPU

Algoritmo de escalonamento

Seleciona entre os processos prontos e na memria, qual ir ganhar a CPU

O escalonamento pode ocorrer: 1. Um processo passa do estado executando para o estado espera (p.

exemplo, o processo solicita uma operao de E/S)

2. Um processo passa do estado executando para o estado pronto

3. Um processo passo do estado espera para pronto

4. Um processo finalizado

Escalonamento nas alternativas 1 e 4 denominado no-preemptivo (nonpreemptive)

As outras opes so denominadas preemptivo (preemptive)

Critrios para o escalonamento

Utilizao da CPU utilizar o mximo da CPU

Throughput nmero de processos finalizados em

um dado intervalo de tempo

Tempo de execuo tempo para finalizar a

execuo de um determinado processo no sistema

Tempo de espera quantidade de tempo que o

processo ficou na fila de prontos

Tempo de resposta tempo entre a requisio e a

sada do primeiro resultado (sistemas interativos)

Otimizaes

Utilizao mxima da CPU

Throughput mximo

Tempo de execuo mnimo

Tempo de espera mnimo

Tempo de resposta mnimo

FCFS (First-come, first-served)

Primeiro a chegar, primeiro a ser servido (sistemas no preeemptivos)

Process Burst Time

P1 24

P2 3

P3 3

A ordem de chegada dos processos P1, P2, P3. O grfico de

Gantt para esse algoritmo :

Tempo de espera P1 = 0; P2 = 24; P3 = 27

Tempo mdio de espera: (0 + 24 + 27)/3 = 17

P1 P2 P3

24 27 30 0

FCFS(2)

Considerando a ordem de chegada P2, P3, P1

O grfico de Gantt

Tempo de espera P1 = 6; P2 = 0; P3 = 3

Tempo mdio de espera: (6 + 0 + 3)/3 = 3

Melhor desempenho que o caso anterior

Efeito comboio: todos os processos menores ficam esperando pelo processo maior utilizar a CPU

P1 P3 P2

6 3 30 0

SJF (Shortest Job First)

Menor tarefa primeiro

Cada processo associado com o tempo de utilizao da CPU (normalmente derivado das execues anteriores)

Dois esquemas: No preeemptivo quando um processo ganha a CPU ele

executado at o fim do perodo de utilizao da CPU

Preemptivo se um processo chega com o tempo de durao da CPU menor que o tempo restante que do processo em execuo, o escalomanento realizado. Shortest-Remaining-Time-First (SRTF)

SJF fornece o menor tempo mdio de espera para um dado conjunto de processos (soluo tima)

SJF no preemptivo

Process Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4

Tempo mdio de espera = (0 + 6 + 3 + 7)/4 = 4

P1 P3 P2

7 3 16 0

P4

8 12

SJF preemptivo

Process Arrival Time Burst Time

P1 0.0 7

P2 2.0 4

P3 4.0 1

P4 5.0 4

Tempo mdio de espera= (9 + 1 + 0 +2)/4 = 3

P1 P3 P2

4 2 11 0

P4

5 7

P2 P1

16

Determinando o tempo de uso da

CPU de um processo Estimativas

Normalmente baseadas nos ciclos de execuo anteriores, utilizando a mdia exponencial

= controla o peso da ltima execuo sobre as execues passadas

:Define 4.

10 , 3.

burst CPU next the for value predicted 2.

burst CPU of length actual 1.

1n

thn nt

.1 1 nnn t

Predio do tempo de execuo

Utilizando a mdia exponencial

=0 n+1 = n A histria recente no considerada

=1 n+1 = tn Somente a ltima execuo considerada

Expandindo a formula: n+1 = tn+(1 - ) tn -1 +

+(1 - )j tn -j +

+(1 - )n +1 0

Desde que E (1 - ) so menores que 1, cada item um peso menor que o seu predecessor

Escalonamento por prioridades

Cada processo tem uma prioridade associada (valor inteiro)

Ganha a CPU o processo com maior prioridade (normalmente,

menor valor = maior prioridade)

Preemptivo

No preemptivo

SJF um algoritmo baseado em prioridades, onde a prioridade

do processo a estimativa do tempo de uso da CPU

Problema Starvation (abandono de processos)processos de

baixa prioridade podem no ganhar a CPU

Soluo Aging (envelhecimento) durante a execuo do

sistema, processos vo ganhando maior prioridade

Round Robin (RR)

Alocao circular

Cada processo ganha um pequeno tempo de CPU (na ordem de milissegundos) denominado quantum

Cada processo ganha uma quantidade q de utilizao da CPU

q grande: FCFS (todos os processos executam at o FIM)

q pequeno: haver desperdcio devido ao tempo necessrio para a troca de contexto

Simulao do escalonamento RR

Process Burst Time

P1 53

P2 17

P3 68

P4 24

Grfico de Gantt:

Normalmente, o throughput menor, porm com um melhor tempo de resposta

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

0 20 37 57 77 97 117 121 134 154 162

Exerccio

Calcular o tempo mdio de processamento

para os seguintes processos utilizando a

poltica de alocao circular (RR), para q =1,

2, 3, 4, 5, 6

Processo Tempo

P1 6

P2 3

P3 1

P4 7

Escalonamento com mltiplas filas

A fila de prontos separada em vrias filas:

fila para processos interativos

fila para processos em lote

Cada fila tem sua poltica de escalonamento

RR para processos interativos

FCFS para processos em lote

Deve haver um escalonamento entre as filas

Prioridade: primeiro a fila de processos interativos

(possibilidade de abandono de processos (starvation)

Fatia de tempo para cada fila

Mltiplas filas e transferncia entre

filas Processos podem ser transferidos de fila

Envelhecimento (aging): processo vai ganhando prioridade com o tempo

Escalonador com mltiplas filas pode ser definido atravs dos seguintes parmetros:

Nmero de filas

Algoritmos de escalonamento para cada fila

Mtodo utilizado para aumentar a prioridade do processo

Mtodo utilizado para diminuir a prioridade do processo

Mtodo utilizado para determinar qual fila o processo ficar quanto o mesmo solicita um servio

Escalonamento com mltiplas filas

Escalonamento em

multiprocesadores Escolher qual processo pronto vai executar em

qual CPU

Simtrico

Todas as estruturas de dados so acessadas por

todos os processadores

Assimtrico

Somente um processador tem acesso a estrutura de

dados do ncleo

Escalonamento no Linux (at 2.6)

Dois algoritmos: tempo compartilhado e tempo real

Tempo compartilhado Baseado em prioridades(crditos) o processo com mais

crdito escalonado

O crdito subtrado quando um interrupo ocorre

Quando crdito= 0, outro processo escolhido

Quando todos os processos tem crdito= 0, um novo clculo dos crditos realizado

Baseado em fatores como prioridade e histrico

Tempo real Soft real-time

Duas classes de algoritmos FCFS e RR

O processo de mais alta prioridade sempre executa

Escalonamento no Linux (a partir

2.6) CFS: Completely Fair Scheduler

Modela uma CPU ideal (todos os processos

ganham a quantidade de tempo que precisam para

executar)

Wait_runtime: tempo em que o processo esperou

para ganhar a CPU. Idealmente 0

Os processos so organizados em uma rvore

rubro-negra

Ordenados pela tempo que elas devem ganhar a CPU

Resoluo em nanosegundos