Algoritmos de escalonamento · PDF fileEscalonamento de Processos Algoritmos de escalonamento podem ser divididos em duas categorias dependendo de como essa interrupção de clock

Algoritmos de escalonamento

Escalonamento de Processos

Sistemas Interativos

Algoritmos para Sistemas Interativos:

First-Come-First-Served (FIFO)

Round-Robin;

Prioridade;

Múltiplas Filas;

Utilizam escalonamento em dois níveis (escalonador da CPU e

memória);

2


Algoritmos de escalonamento podem ser divididos em duas categorias dependendo de como essa interrupção de clock é tratada:

Preemptivo: estratégia de suspender o processo sendo executado;

Não-preemptivo: estratégia de permitir que o processo sendo executado continue sendo executado até ser bloqueado por alguma razão (semáforos, operações de E/S-interrupção);

3


Categorias de Ambientes:

Sistemas em Batch: usuários não esperam por respostas rápidas; algoritmos preemptivos ou não-preemptivos;

Sistemas Interativos: interação constante do usuário; algoritmos preemptivos; Processo interativo espera comando e executa comando;

Sistemas em Tempo Real: processos são executados mais rapidamente; tempo é crucial sistemas críticos;

4

5


Características de algoritmos de escalonamento:

Sistemas em Batch:

Taxa de execução (throughput): máximo número de jobs

executados por hora;

Turnaround time: tempo no qual o processo espera sua resposta

(para ser executado);

Eficiência: CPU deve estar 100% do tempo ocupada;

Sistemas Interativos:

Tempo de resposta : tempo esperando respostas;

Satisfação do usuários;

6


Características de algoritmos de escalonamento:

Sistemas em Tempo Real:

Prevenir perda de dados;

Previsibilidade: prevenir perda da qualidade dos serviços

oferecidos;

7


Escalonamento Three-Level (três níveis)

Normalmente todos os processos estão na memória

principal

Suponha:

processos na memória principal + processos no disco

Chaveamento de processos que estão no disco requer

mais tempo 1 ou 2 ordens de grandeza

Utilizado em Sistemas em Batch;

8


Escalonamento Three-Level

Subconjunto dos processos Memória Principal (MP);

Escalonador se restringe a esses processos;

Periodicamente um escalonador da CPU é acionado para

remover processos da MP;

9



RAM

Escalonador da CPU *

Disco

Fila de entrada

Novo processo

Escalonador

Da Memória

Escalonador

de Admissão

CPU

10



Escalonador de admissão: processos menores primeiro; processos com menor tempo de acesso à CPU e maior tempo de interação com dispositivos de E/S;

Escalonador da Memória: decisões sobre quais processos vão para a MP:

A quanto tempo o processo está esperando?

Quanto tempo da CPU o processo utilizou?

Qual o tamanho do processo?

Qual a importância do processo?

Escalonador da CPU: seleciona qual o próximo processo a ser executado;


Não preemptivo por definição

Primeiro processo da fila é o primeiro a ser executado

Processos usam a CPU até terminar todo

processamento

Mesmo com alguma intercalação, processos com menor prioridade podem prejudicar processos com maior prioridade

Desvantagem:

Ineficiente quando se tem processos que demoram na sua execução

11


First In First Out (FIFO)

Constitui-se no esquema mais simples de escalonamento

em que os processos são executados do início até o fim,

na ordem de chegada.

12


Interrupção qualquer

(semáforo, E/S)

CPU

0Fila de entrada

23 1


CPU

1Fila de entrada

30 2


Shortest Job First – Processo mais curto primeiro

Processos menores são executados primeiro.

Processos curtos são favorecidos.

Processo maiores são prejudicados.

Pouco utilizado na prática.

Pode ser preemptiva ou não-preemptiva

Cada processo é associado ao seu tempo de uso do processador

Escalonado o processo com o menor tempo de CPU

privilegiam processos menores

reduzem o tempo médio de espera na fila de prontos

Problema:

Como determinar quanto tempo de CPU será necessário?


Shortest Job First – Processo mais curto primeiro

Exemplo:Processo Tempo de Uso da CPU em ms

(milissegundos)

Chegada

P1 7 0

P2 4 2

P3 1 4

P4 4 5

Shortest-Job-First

A política SJF é ótima, minimizando o tempo médio

de espera de um conjunto de processos

Dificuldade: determinar antecipadamente o tempo de

processador de cada processo

Na prática, o tempo é estimado, é utilizada uma

aproximação

Shortest-Job-First: não preemptivo

Processo Tempo de chegada Duração da rajada

P1 0.0 7

P2 2.0 1

P3 4.0 4

P4 5.0 4

SJF (não preemptivo)

73 160 8 12

P1 P2 P3 P4

18

Shortest-Job-First: preemptivo


P1 0.0 7

SJF (preemptivo)

P2 2.0 4

P3 4.0 1 terminado

P4 5.0 4

terminado

0

P1

2

P2

5

P3

4 7

P2

11

P4

terminado

16

P1

terminado

19

Shortest-Job-First: preemptivo

?


P1 0.0 7

0

P1

SJF (preemptivo)

2

P2

P2 2.0 4

tempo restante: 5

? 5

P3 4.0 1

P3

4

tempo restante: 2

terminado

P4 5.0 4

7

P2

terminado

11

P4

terminado

16

P1

terminado

20

Prioridade

A cada processo é atribuída uma prioridade

O processo com maior prioridade é atribuído ao

processador

Pode ser não-preemptiva ou preemptiva

não-preemptiva: o processo libera

espontaneamente o processador

preemptiva : o processo executando é

interrompido caso chegue à fila de prontos um

processo com maior prioridade

21

Prioridade

Atribuição de prioridades

estática: o processo tem uma prioridade

fixa durante o seu tempo de vida

dinâmica: prioridade muda ao longo do

tempo de vida do processo, de acordo com

o seu comportamento

22

Prioridade

Atribuição de prioridades normalmente é feita pelo SO

pode ser configurada pelo superusuário

processos de usuário recebem uma prioridade máxima de usuário

usuário pode diminuir a prioridade de seus processos

ex.: comando renice do Unix

Dinâmica

pode ser ajustada de acordo com

tipo de processamento realizado

a carga do SO

quando o processo passa do estado de espera para o estado executando ele é penalizado e sua prioridade é reduzida, processos

CPU bound terão suas prioridades reduzidas a cada passagem para o estado executando

I/O bound ficam em estado de espera com freqüência, processos CPU bound não serão prejudicados

23

Prioridade






Dinâmica



a carga do SO




Estática

é atribuída quando o processo é iniciado

não é alterada durante a existência do processo

pode oferecer tempos de resposta aceitáveis 24

Prioridade






Dinâmica



a carga do SO




Estática

é atribuída quando o processo é iniciado

não é alterada durante a existência do processo

pode oferecer tempos de resposta aceitáveis

Observação

SO pode associar à alta prioridade um número escalar pequeno

0 significa a maior prioridade25

Prioridade

Processo A

Processo B

tempo4 8 10 13 16 18 23 26 27

1u.t.

4 u.t.

B solicita

I/Opreempção

por B

4 u.t.

B solicita

I/O

2 u.t.

A solicita

I/O

3 u.t.

2 u.t.

B solicita

I/O

5 u.t.

preempção

por B

3 u.t.

B solicita

I/O

Tempo de CPU (u.t.) Característica do Processo Prioridade

Processo A 13 CPU bound 1 menor

Processo B 11 I/O bound 0 maior

26

Prioridade

Vantagens

é possível fazer diferenciação entre processos

adaptabilidade (prioridades dinâmicas)

Desvantagem

starvation: um processo com baixa prioridade

pode nunca ser atribuído ao processador

solução: aumentando, em intervalos regulares, a

prioridade dos processos que estão há muito tempo

esperando

27


Round Robin – Alternância Circular

Processos são executados na ordem FIFO, mas com um

intervalo chamado quantum.

Ao final de seu quantum, se o processo ainda estiver

em execução, é interrompido (preempção) e voltará

para o estado de pronto (final da fila) e o próximo

processo da fila será alocado para ocupar a CPU.

Se o processo terminar antes de finalizar o seu

quantum, a CPU será liberada.


Round Robin – Alternância Circular

Exemplo: quantum de 20 ms Processo Tempo de Uso da CPU em

ms (milissegundos)

P1 50

P2 14

P3 65

P4 21

Round-Robin

Bom para tempo compartilhado

Similar a FIFO + tempo limite para execução (time-slice ou quantum)

terminado o quantum, o processo é devolvido (preempção) para o final da fila de prontos

processos não monopolizam a CPU

quantum entre 100 a 300 ms

30

Round-Robin

Processo A

Processo B

tempo5 9 11 13 16 21 23 26 27

Tempo de CPU (u.t.) Característica do Processo

Processo A 15 CPU bound

Processo B 8 I/O bound

5 u.t.

termina

quantum

de A

4 u.t.

B solicita

I/O

A solicita

I/O

2 u.t.

B solicita

I/O

2 u.t.

5 u.t.

termina

quantum

de A

2 u.t.

B solicita

I/O

3 u.t.

A solicita

I/O

31

Round-Robin

Vantagem do escalonamento Robin Round

simplicidade

Tamanho da fatia de tempo é crucial no escalonamento circular

pequena: tempo de troca de contexto torna-se significativo

grande: aumenta o tempo de resposta dos processos no final da fila de prontos

32

Round-Robin

Se existem n processos na fila de prontos

Se quantum = q

cada processo tem 1/n do tempo de CPU em fatias de no máximo q unidades de tempo cada

Nenhum processo espera por mais de (n-1) qunidades de tempo para ser atendido

33

Round-Robin

Desempenho

quantum = muito grande

FIFO

quantum = muito pequeno

q deve ser grande comparado a

mudança de contexto, caso contrário, o

overhead é muito elevado34

Round-Robin

Processo Tempo de execução

P1 53

P2 17

P3 68

P4 24

Diagrama de Gantt (quantum = 20 u.t.)

Tipicamente, temos turnaround time médio maior que

na SJF, mais em compensação melhor resposta

0 20 37 57 77 97 117 121 134 154 162

P1 P2 P3 P4 P1 P3 P4 P1 P3 P3

35

Como um pequeno quantum de tempo aumenta as mudanças de

contexto

tamanho do processo: 10 u.t. quantum mudanças

de contexto

0 10

12 0

0 6 10

6 1

0 1 2 3 4 5 6 107 8 9

1 9

36

Múltiplas Filas

Política do tipo preemptiva

Prioridades são atribuídas às classes de processos

Processos das classes de maior prioridade recebem o

processador

Processos podem migrar entre classes de acordo com

seu comportamento

Vantagem: adaptabilidade de acordo com o

comportamento do processo

37

Múltiplas Filas

Processos são classificados em função do tipo de

processamento

Cada grupo formado fila associada

Fila de prontos associada a cada grupo permite

aplicação de tipos de escalonamento

diferentes

38

Múltiplas Filas

Cada fila possui uma prioridade

SO só vai escalonar processos em uma fila se

todos os processos das filas de maior prioridade

estiverem vazias

39

Múltiplas Filas

p = 3

p = 2

p = 0

p = 1

processos interativos

processos em batch

40

Fila de Processos do Sistema

Fila de Processos Batch

Fila de Processos Interativos

Maior Prioridade

Menor Prioridade

sistema

mais prioritário

algoritmo de escalonamento por prioridades

interativo

prioridade intermediária

escalonamento Round-Robin

batch

menor prioridade

usa Round-Robin ou FCFS

Exemplo

41

Múltiplas Filas com Realimentação

Escalonamento anterior a classificação dos processos era estática

Se processo alterar seu comportamento, o esquema pode falhar (não existe reclassificação)

Seria interessante que o SO

reconhecesse a alteração de comportamento de um processo

ajustasse dinamicamente o seu tipo de escalonamento

42

Múltiplas Filas com Realimentação

No escalonamento por múltiplas filas com realimentação (multi-level feed-bak queues)

é permitido que os processos sejam movimentados

entre as filas

ajuste dinâmico (mecanismo adaptativo)

processo é direcionado para uma das filas em função de seu comportamento

43

Múltiplas Filas com Realimentação:

Funcionamento

Criação do processo

prioridade mais alta e quantum mais baixo

Cada fila pode implementar uma política de

escalonamento diferente para chegar a CPU:

FIFO com quantum

SJF

RR

44


Funcionamento

Processo é reescalonado dentro da mesma fila

quando

processo volta ao estado de pronto

sofre preempção por outro processo de uma fila

mais prioritária

Processo é direcionado para fila de menor

prioridade e maior quantum quando

processo esgota o seu quantum (sofrendo

preempção)45


Funcionamento

Quanto maior a prioridade menor o quantum

Escalonamento de uma fila só acontece depois

que todas as outras filas de prioridade mais alta

estão vazias

Fila de menor prioridade Round-Robin

46


Características

Atende as necessidades de escalonamento de

diversos tipos de processos

Processos I/O bound

bom tempo de resposta: maior prioridade

permanecem a maior parte do tempo nas

filas de alta prioridade

usa pouco a CPU

47


Características

Processos CPU bound

com o transcorrer do processamento sua

prioridade vai sendo reduzida

É um mecanismo complexo e gera

overhead, mas os resultados são

satisfatórios

48


Exemplo 1

Fila 1 (escalonamento FIFO)


Fila m (Round-Robin)

Maior Prioridade

Menor Prioridade Maior quantum

Menor quantum


preempção por término de quantum

preempção por término de quantum

...preempção por término de quantum

49


Exemplo 2

quantum = 8

quantum = 16

FCFS

50

Concorrência

Os processo concorrem pelos recursos do sistema.

Exemplo: fila de impressão

Deadlock

Acontece quando dois ou mais processos estão disputando recursos e nenhum deles consegue seguir a execução porque ambos estão bloqueando uns aos outros.

Exemplo:

Dois processos querem gravar um CD.

Processo P1 aloca o Gravador.

Processo P2 aloca o HD.

P1 espera P2 terminar de usar o HD.

P2 espera P1 terminar de usar o gravador.

Exclusão Mútua

Evitar que mais de um processo utilize um recurso

compartilhado.

Condições para exclusão mútua:

1. Dois processos não podem estar dentro de suas regiões críticas

ao mesmo tempo, compartilhando o mesmo recurso.

2. A exclusão mútua dos processos deve ser independente da

velocidade dos processos ou o número de CPUs.

3. Um processo executado fora da região crítica não pode

bloquear outros processos.

4. Nenhum processo esperará para sempre para entrar em sua

região crítica.

Exclusão mútua com espera ocupada

Se um processo está acessando uma região crítica, ou seja, esta em execução, todos os outros processos que precisarem acessar esta região deverão entrar em estado de espera ocupada.

Esta espera se refere apenas à região crítica.

Desabilitar interrupções.

Variável Lock.

Variável Turn.

Peterson.

Instrução TSL.

Desabilitar interrupções

Desabilitar todas as interrupções, inclusive as do

sistema operacional, quando uma região crítica

está sendo acessada, garantindo que o processo

em execução termine de executar a região crítica

sem a intervenção de outros processos.

Variável Lock

Esta solução utiliza um algoritmo em que cada

recurso compartilhado possui uma variável global

chamada lock, com valor inicial igual a 0.

O algoritmo controla o acesso à região crítica por

meio da variável lock. Ao consultar, se o seu valor

for 0, o processo executará a região crítica; e se

for 1, o processo aguardará até que a variável

lock se torne 0.

Variável Turn

Se a variável turn for igual a i, o processo de

número i executará a região crítica até terminar.

Ao sair, o processo altera o valor de turn para i+1

para que o próximo processo, ao executar, tenha

acesso à região crítica.

Solução de Peterson

Combina as variáveis lock e turn solucionando os

problemas individuais de cada uma delas.

Instrução TSL

É uma instrução utilizada em muitos processadores

que permite a implementação de variáveis lock.

A vantagem é que nem mesmo uma interrupção de

hardware pode interromper a execução.

Documents

Algoritmos de escalonamento · PDF fileEscalonamento de Processos Algoritmos de escalonamento podem ser divididos em duas categorias dependendo de como essa interrupção de clock