3 escalonamento processos

SISTEMAS OPERACIONAISATSLANDS ROCHA

ESCALONAMENTO DE PROCESSOS

2

ESCALONADOR DE CPU Seleciona qual processo da fila de PRONTO vai

ser executado; Dois esquemas de escalonamentos:

Não-preemptivoO processo é alocado pela CPU e depois

passa para o estado de pronto ou é terminado.

PreemptivoInterrompe a execução do processo para que

outro possa executar.

3

ALGORITMOS DE ESCALONAMENTOCARACTERÍSTICAS A seleção de um algoritmo de escalonamento

envolve: 1) Utilização da CPU

A CPU deverá ficar ocupada o máximo possível;

2) Número de processos completados por unidade de tempoSe a CPU estiver ocupada, o trabalho está

sendo feito.

4

ALGORITMOS DE ESCALONAMENTOCARACTERÍSTICAS A seleção de um algoritmo de escalonamento

envolve: 3 ) Tempo de retorno: intervalo entre a submissão do

processo até ele concluir Incluindo o tempo de espera para acessar

memória, execução na CPU e operações de I/O.

4) Tempo de espera: soma dos períodos gastos esperando na fila de prontos.

5) Tempo de resposta: intervalo de submissão do processo até a resposta.

5

ALGORITMOS DE ESCALONAMENTOCARACTERÍSTICAS Com o algoritmo selecionado espera-se:

Maximizar a utilização de CPU; Minimizar o tempo de retorno, espera e resposta

(otimizar a média).

6

ALGORITMO DE ESCALONAMENTOFCFS: FIRST-COME, FIRST SERVED Quem solicita primeiro a CPU, recebe-a primeiro; Gerenciada por uma fila FIFO (primeiro que

entra, primeiro que sai); Algoritmo mais simples; Tempo médio de ESPERA pode ser longo.

7

ALGORITMO DE ESCALONAMENTOFCFS: FIRST-COME, FIRST SERVED

Ex: P1 ->24 ms P2 -> 3 ms P3 -> 3 ms

P1 P2 P3

0 24 27 30

8

ALGORITMO DE ESCALONAMENTOFCFS: FIRST-COME, FIRST SERVED

Tempo de espera: P1 -> 0 ms P2 -> 24ms (0ms + 24ms) P3 -> 27 ms (24ms + 3ms) Tempo de espera médio: 17ms (0 + 24 + 27)/3

P1 P2 P3

0 24 27 30

9

ALGORITMO DE ESCALONAMENTOFCFS: FIRST-COME, FIRST SERVED Pode deixar a CPU e dispositivos I/O ociosos; Não-preemptivo; Problemático em sistemas de tempos

compartilhado, onde deseja-se suprir vários usuários.

10

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO Associa a cada processo a duração de seu próximo

surto de CPU; A CPU é atribuída ao processo que tem o menor

próximo surto de CPU; Surtos iguais, usa-se FCFS para desempate.

11

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO

Ex: P1 -> 6ms P2-> 8ms P3-> 7ms P4-> 3ms

P4 P1 P3 P2

0 3 9 16 24

12

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO

Tempo de espera: P1 -> 3 ms P2 -> 16ms P3 -> 9 ms P4 -> 0 ms Tempo espera médio - 7ms (FCFS seria 10,25 ms)

P4 P1 P3 P2

0 3 9 16 24

13

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO Escalonamento ótimo

Fornece o tempo médio de espera mínimo! Dificuldade: conhecer a duração do próximo surto

(pedido) de CPU!

14

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO Quando um processo chega na fila de prontos e

outro ainda está em execução: SJF Não-preemptivo: permite que o processo em

execução termine seu surto de CPU; SJF Preemptivo: Se o processo tiver o próximo surto

menor do que o resto do processo que está executando, este será interrompido.

15

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO PREEMPTIVO Exemplo:

Processo Instante Chegada Duração Surto P1 0 8 P2 1 4 P3 2 9 P4 3 5

P1 P2 P4 P1

0 1 5 10 17 26

P3

16

ALGORITMO DE ESCALONAMENTOSJF: JOB MAIS CURTO PREEMPTIVO

Tempo de espera médio Preemptivo: 6,5 ms Tempo de espera médio SJF Não-preemptivo seria

7,75 ms

P1 P2 P4 P1

0 1 5 10 17 26

P3

17

ALGORITMO DE ESCALONAMENTOESCALONAMENTO POR PRIORIDADES CPU é alocada ao processo com prioridade mais

alta; Processo com prioridades iguais são escalonadas

na ordem FCFS.

18

ALGORITMO DE ESCALONAMENTOESCALONAMENTO POR PRIORIDADES

Exemplo: P1 -> 10ms com Pri = 3 P2 -> 1 ms com Pri = 1 P3 -> 2 ms com Pri = 4 P4 -> 1ms com Pri = 5 P5 -> 5 ms com Pri = 2

*0 é a maior prioridade!

P2 P5 P1 P3

0 1 6 16 18 19

P4

19

ALGORITMO DE ESCALONAMENTOESCALONAMENTO POR PRIORIDADES

Tempo de espera médio - 8,2 ms

P2 P5 P1 P3

0 1 6 16 18 19

P4

20

ALGORITMO DE ESCALONAMENTOESCALONAMENTO POR PRIORIDADES Preemptivo ou Não-preemptivo

Quando um processo chega na fila de prontos, sua prioridade é comparada com a do processo em execução;

Não-Preemptivo: Coloca o processo no topo da fila de pronto;

Preemptivo: Se a prioridade for maior, o algoritmo interrompe o processo atual.

21

ALGORITMO DE ESCALONAMENTOESCALONAMENTO POR PRIORIDADES Problema: Bloqueio por tempo indefinido

Alguns processos de baixa prioridade podem esperar indefinidamente pela CPU.Ou ele pode ser executado às “2h da manhã

de domingo” ou é perdido em eventuais falhas do sistema.

Solução: Envelhecimento Exemplo: A cada 15min os processos em espera

sobem 1 ponto na prioridade.

22

ALGORITMO DE ESCALONAMENTOROUND-ROBIN (RR) Semelhante ao FCFS, mas é PREEMPTIVO; Utilização de quantum (fatia de tempo); Geralmente, o tempo de espera médio é longo; Revezamento circular

A fila de prontos é tratada como uma fila circular!

23

ALGORITMO DE ESCALONAMENTOROUND-ROBIN (RR) A fila de prontos é FIFO (First In, First Out); Escalonador percorre a fila de pronto e aloca a

CPU a cada processo por um quantum Surto de CPU do processo > quantum

Tempo esgota e causa-se uma interrupção. Há troca de contexto e um novo processo executa

Surto de CPU do processo < quantumCPU é liberada e o próximo da fila executa

24

ALGORITMO DE ESCALONAMENTOROUND-ROBIN (RR)

Ex: P1-> 24 ms P2-> 3 ms P3-> 3 ms Quantum = 4 ms

P1 P2 P3 P1

0 4 7 10 14 18 22 26 30

P1 P1 P1 P1

25


Tempo médio de espera: 5,66 Nenhum processo recebe quantas* consecutivos (a não ser

que seja o único processo pronto)

* Quantas = plural de quantum

P1 P2 P3 P1

0 4 7 10 14 18 22 26 30

P1 P1 P1 P1

26

ALGORITMO DE ESCALONAMENTOROUND-ROBIN (RR) DEPENDE do tamanho do quantum

Se for muito grande, será como o FCFS; Se for muito pequeno (Ex: 1 μs), terá muitas trocas de

contextos (desperdício de recursos); Regra geral: 80% dos surtos de CPU dos processos deve

ser menor que o quantum.

27


0 1 2 3 4 5 6 7 8 9 10

P5 P1

0 6 10

0 10

Quantum = 12 Troca Contexto =0

Quantum = 6 Troca Contexto =1

Quantum = 1 Troca Contexto = 9

ALGORITMO DE ESCALONAMENTOAPLICAÇÕES Sistemas em Lote

Job mais curto primeiro. Sistemas Interativos

Round Robin; Classes de prioridades.(?!)

29

ALGORITMO DE ESCALONAMENTO Há outra classe de algoritmos para processos

agrupados Exemplo de grupos:

Processos de primeiro plano (interativos) e de segundo plano (batch).

Os grupos têm diferentes requisitos de tempo de resposta e prioridades e podem ter necessidades diferentes de escalonamento.

30ALGORITMOS DE ESCALONAMENTOESCALONAMENTO POR MÚLTIPLAS FILAS Divide a fila de processos PRONTOS em várias

filas separadas; Os processos são atribuídos a uma fila com base

em um filtro (tamanho da memória, prioridade, tipo, etc);

Os processos não passam de uma fila para outra Vantagem: baixo custo de escalonamento; Desvantagem: Inflexível.

31ALGORITMOS DE ESCALONAMENTOESCALONAMENTO POR MÚLTIPLAS FILAS Cada fila tem seu próprio algoritmo de

escalonamento Ex: Uma fila pode ser escalonada por um algoritmo

RR e outra por FCFS. Há escalonamento entre as filas

Geralmente há escalonamento preemptivo de prioridade fixa.Ex: A fila de primeiro plano tem prioridade

absoluta sobre a fila de segundo plano.

32ALGORITMOS DE ESCALONAMENTOESCALONAMENTO POR MÚLTIPLAS FILAS

Processos interativos

Processos de edição interativa

Processos em batch

Processos secundários

Processos do sistema

Prioridade mais alta

Prioridade mais baixa

33ALGORITMOS DE ESCALONAMENTOESCALONAMENTO POR MÚLTIPLAS FILAS Exemplo:

Nenhum processo da fila de edição interativa pode executar a menos que as filas de processos do sistema e processos interativos estejam vazias;

Se um processo de interativo entrasse na fila de prontos enquanto um processo de edição interativa estiver executando, este é interrompido.

34ALGORITMOS DE ESCALONAMENTOESCALONAMENTO POR MÚLTIPLAS FILAS Há a possibilidade de dividir o tempo entre as

filas Cada fila obtém uma parte do tempo de CPU, que

pode ser escalonado entre os vários processos da fila.Ex: A fila de primeiro plano pode receber

80% da CPU para escalonamento RR entre seus processos e a fila de segundo plano recebe 20% para escalonamento FCFS.

35ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO Processo pode se mover entre as filas; Mais complexo; Separa-se os processos com diferentes

características de surto de CPU; Se um processo usar tempo de CPU excessivo, é

movido para uma fila de menor prioridade.

36ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO Assim, processos de E/S e interativos ficam nas

filas de prioridades mais altas; Um processo que espera demais em uma fila de

baixa prioridade pode ser passado para um fila de maior prioridade;

Forma de envelhecimento que evita estagnação.

37ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO

Quantum = 16

FCFS

Quantum = 8

38ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO Exemplo:

Um processo entra na fila de prontos e é colocado na fila 0 (quantum = 8);

Se não terminar dentro de 8 ms, ele é colocado na fila 1 (quantum = 16);

Se não completar em 16 ms, é colocado na fila 2; A fila 2 funciona de modo FCFS, quando as filas 1 e 2

estiverem vazias.

39ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO Exemplo (cont.):

Assim, processos de surto de 8 ms (ou menos) têm prioridades mais altas;

Processos de surto entre 9 e 24 ms também são atendidos rapidamente (com menor prioridade dos de 8 ms ou menos);

Processos mais longos caem para fila 2 (FCFS).

40ALGORITMOS DE ESCALONAMENTOMÚLTIPLAS FILAS COM REALIMENTAÇÃO Geralmente definido pelos parâmetros:

Número de filas; Algoritmo de escalonamento para cada fila; Método para promover um processo para outra fila; Método para rebaixar um processo para outra fila; Método para selecionar uma fila para um processo.

41

ALGORITMOS DE ESCALONAMENTOMÚLTIPLOS PROCESSADORES Várias CPUs disponíveis, o problema do

escalonamento é mais complexo; Utilização de processadores idênticos em termos

de funcionalidade; Qualquer processador disponível pode executar

qualquer processo pronto; Se for usado uma fila para cada processador, um

processador pode estar ocioso, enquanto outro está sobrecarregado.

42

ALGORITMOS DE ESCALONAMENTOMÚLTIPLOS PROCESSADORES Solução: Somente uma fila de prontos para todos

os processadores. Processos escalonados para qualquer processador

disponível. Duas abordagens:

Multiprocessamento simétrico; Multiprocessamento assimétrico.

43

ALGORITMOS DE ESCALONAMENTOMÚLTIPLOS PROCESSADORES Multiprocessamento simétrico

Cada processador tem seu escalonamento (seleciona o processo para executar);

Deve haver garantia que os processadores não escolherão o mesmo processo;

Não deve haver perda de processos na fila.

44

ALGORITMOS DE ESCALONAMENTOMÚLTIPLOS PROCESSADORES Multiprocessamento assimétrico

Todas as decisões de escalonamento e processamento de I/O são tratadas por um processador mestre;

Mais simples.

45

ALGORITMOS DE ESCALONAMENTO Escalonamento de tempo real (não-crítico)

Tempo real não-crítico: processos devem receber prioridades mais altas que outros processos;

A prioridade de processos de tempo real não deve “envelhecer”;

Desvantagem: Pode causar alocação injusta de recursos ou resultar na paralisação de outros processos.

DÚVIDAS?!

Technology

3 escalonamento processos