51
Silberschatz, Galvin and Gagne ©2009 perating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

Embed Size (px)

Citation preview

Page 1: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Capítulo 5: Escalonamento de CPU

Page 2: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.2 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Conceitos básicos

Utilização máxima da CPU obtida com a multiprogramação

Execução de processos consiste de ciclos contendo rajadas de requisições a CPU e tempo de espera por I/O

Page 3: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.3 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Ciclo de uso da CPU

Page 4: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.4 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Histograma do tempo da rajada de requisições para a CPU

Page 5: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.5 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU

O escalonador escolhe um processo na fila ready e aloca a CPU para ele

A fila pode ser ordenada de acordo com diferentes critérios

Fila de prontos (ready): Novos processos que ainda não acessaram a CPU, processos em execução que foram retirados da CPU devido a uma interrupção e processos que estavam esperando uma resposta de I/O e receberam essa resposta

Page 6: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.6 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU

Decisões de escalonamento de CPU são tomadas quando um processo:

1. Sai do estado de execução (running) para o estado de espera (waiting)

Ocorre quando existe uma solicitação de I/O

2. Sai do estado de execução (running) para o estado de pronto (ready)

Ocorre quando acontece uma interrupção de clock

3. Sai do estado de espera (waiting) para o estado de pronto (ready)

Ocorre quando acontece uma interrupção avisando o fim de uma operação de I/O

4. Termina

O escalonamento nas condições 1 e 4 é não preemptivo ou colaborativo

O escalonamento nas condições 2 e 3 é preemptivo

Page 7: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.7 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU

Preempção

Interrupção de clock

Interrupção de I/O

Troca de contexto irá depender do escalonador

Page 8: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.8 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU – Acesso a dados compartilhados

Processo 1

Variável A compartilhada

Leia do disco

Escreve resultado em A

Processo 2

Variável A compartilhada

Leia variável A

Escreve resultado na tela

Execução

• SO escolhe P1

• P1 lê do disco e começa a escrever o resultado em A

• SO para P1 e dá a vez a P2

• P2 lê valor inconsistente em A

• P2 escreve valor inconsistente (1 0 1 1 x x x x) na tela

• P2 termina e passa a vez a P1

• P1 acaba de escrever resultado em A

1 0 1 x x

x x x x x

x

x

1 0 1 0 0 0

...

...

...

Page 9: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.9 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU – Preempção no modo kernel

Se o sistema operacional aplicasse preempção sobre o seu próprio funcionamento durante chamadas de sistema:

Processo 1

Leia do disco

Escreve resultado em A

Processo 2

Leia do disco

Escreve resultado na tela

Chamadas de sistema

Controle passa para o kernel

Page 10: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.10 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonador de CPU – Preempção no modo kernel

Se o sistema operacional aplicasse preempção sobre o seu próprio funcionamento durante chamadas de sistema:

Execução

• SO escolhe P1

• P1 faz chamada de sistema para leitura de disco

• Passagem para o modo kernel e inicio da atualização do ponteiro de leitura de disco

• SO para P1 e dá a vez a P2

• P2 faz chamada de sistema para leitura de disco

• Passagem para o modo kernel e inicio da atualização do ponteiro de leitura de disco, sobrescrevendo dados de P1

• SO para P2 e dá a vez a P1

• Fim da atualização do ponteiro para P1

• (...)

Valor inconsistente no ponteiro

Em geral, SOs não fazem troca de contexto durante chamadas de sistema!

Page 11: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.11 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Despachante

O despachante dá ao processo selecionado pelo escalonador o acesso a CPU. Para tanto, ele realiza:

Troca de contexto

Comutação para o modo usuário

Direcionamento para a parte adequada do programa do usuário para reiniciar o programa

Latência de despacho– tempo que o despachante gasta entre parar um processo e iniciar outro

Page 12: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.12 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Critérios de Escalonamento

Utilização de CPU

Manter a CPU utilizada pelo maior tempo possível

Vazão

Aumentar o número de processos que são terminados por unidade de tempo

Tempo de Turnaround

Diminuir o tempo para executar um certo processo (tempo de execução + tempo em filas)

Tempo de espera

Diminuir o tempo que o processo espera na fila de prontos (ready) (tempo em filas)

Tempo de resposta

Diminuir o tempo entre a submissão de um pedido e a obtenção da primeira resposta (não necessariamente a saída do processo) (tempo de execução até primeira resposta + tempo em filas)

Page 13: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.13 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Algoritmos de escalonamento

First-Come, First-Served (FCFS) Scheduling

Shortest-Job-First (SJF) Scheduling

Shortest-remaining-time-first

Escalonamento por prioridade

Round Robin (RR)

Filas multiníveis

Filas multiníveis com realimentação

Page 14: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.14 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

First-Come, First-Served (FCFS) Scheduling

Semelhante à fila FIFO, sem preempção

Processo Tempo de Rajada

P1 24

P2 3

P3 3

Assuma que os processos cheguem na ordem: P1 , P2 , P3

Então:

Tempo de espera: P1 = 0; P2 = 24; P3 = 27 Tempo de espera médio: (0 + 24 + 27)/3 = 17

P1 P2 P3

24 27 300

Page 15: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.15 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

FCFS Scheduling (Cont.)

Agora, assuma que os processo chegam na ordem: P2 , P3 , P1

Então:

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

Tempo de espera médio: (6 + 0 + 3)/3 = 3

Muito melhor que no exemplo anterior

Efeito comboio

Processo pequeno após processos longos pode causar uma baixa utilização da CPU

P1P3P2

63 300

Page 16: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.16 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

FCFS

Efeito comboio

Desvantagens

Atrasos grandes

Baixa utilização da CPU

P1 P2 P2 P3 P1 P2 P2 P3Ocioso

Espera por I/O de P1

Espera por I/O de P2

Espera por I/O de P3

Page 17: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.17 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Shortest-Job-First (SJF) Scheduling

Associar cada processo com o comprimento de sua próxima rajada de uso de CPU

O próximo processo a acessar a CPU é aquele que apresentar o menor tempo de uso de CPU

• Não está relacionado ao tamanho do job, mas ao tamanho esperado até o próximo pedido de E/S

• Pode ter ou não preempção

Page 18: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.18 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Shortest-Job-First (SJF) Scheduling

SJF é um algoritmo ótimo para garantir o tempo médio mínimo

Garante um tempo de espera médio mínimo dado um conjunto de processos

Problema

Descobrir qual o tempo da rajada de uso de CPU

Ideal apenas para garantir o tempo médio mínimo. Um processo orientado a CPU em meio a inúmeros processos orientados a I/O pode nunca conseguir o acesso à CPU

Page 19: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.19 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Exemplo de SJF

Tempo de chegada do processoTempo de rajada

P1 0.0 6

P2 2.0 8

P3 4.0 7

P4 5.0 3

Então:

Tempo de espera médio = (3 + 16 + 9 + 0) / 4 = 7

P4 P3P1

3 160 9

P2

24

Page 20: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.20 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Determinando o tempo da próxima rajada de CPU

Pode ser apenas estimado

Portanto, é escolhido o processo com menor tempo previsto

Estimativa pode ser feita utilizando o tempo das rajadas anteriores daquele processo

1. tn = duração da n-ésima rajada de uso de CPU

2. = valor previsto para a próxima rajada de uso de CPU

3. α, 0 ≤ α ≤ 1

4. Defina:

Geralmente, α = ½

1n

1 1 .n n nt

Page 21: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.21 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Predição do comprimento da próxima rajada de CPU

Page 22: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.22 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Shortest-remaining-time-first

Exemplo:

Processo Tempo de chegada Tempo de rajada

P1 0 8

P2 1 4

P3 2 9

P4 3 5

Então:

Tempo de espera médio = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 ms

Sem preempção: Tempo médio = 7,75 ms

P1P1P2

1 170 10

P3

265

P4

Versão do Menor Job Primeiro (SJF) com preempção

Ver no quadro o funcionamento.

Page 23: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.23 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento por Prioridade

Uma prioridade é associada com cada processo

A CPU é alocada ao processo com maior prioridade (menor inteiro maior prioridade)

Preemptivo

Não-preemptivo

O SJF é um escalonamento por prioridade, no qual a prioridade vale o inverso do tempo previsto para a próxima rajada de CPU

Problema Inanição – Processos com baixa prioridade podem não ser executados nunca

Solução Envelhecimento – Prioridade de um processo aumenta com o passar do tempo

Supondo uma prioridade variando de 0 a N, 0 pode representar a mais alta ou a mais baixa prioridade. Daqui para frente, será

usada a notação de 0 como mais alta prioridade.

Page 24: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.24 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Exemplo de escalonamento por prioridade

Processo Tempo de rajada Prioridade

P1 10 3

P2 1 1

P3 2 4

P4 1 5

P5 5 2

Então:

Tempo de espera médio = 8.2 ms

P2 P3P5

1 180 16

P4

196

P1

Chegada de todos em T0

Definida internamente ou

externamente

Exemplo sem preempção igual ao

mesmo exemplo com preempção, pois todos chegam ao

mesmo tempo

Page 25: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.25 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Round Robin (RR)

Cada processo recebe uma unidade de tempo pequena, chamada de quantum de tempo (q), que usualmente vale entre 10-100 milissegundos.

Após o fim de um quantum, o processo é deixa a CPU por preempção e é adicionado ao final da fila de prontos.

Semelhante ao FCFS com preempção.

P1 P2 P3 P4 ... Pn

Fim do quantum ou espera por E/S

Page 26: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.26 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Exemplo de RR com Quantum = 4

Processo Tempo de rajada

P1 24

P2 3

P3 3

Então:

Tipicamente, apresenta um tempo de turnaround maior que o SJF, mas com melhor tempo de resposta

q deve ser grande, quando comparado ao tempo de troca de contexto (Usualmente, q ~ 10ms a 100ms, troca de contexto < 10 us)

P1 P2 P3 P1 P1 P1 P1 P1

0 4 7 10 14 18 22 26 30

Page 27: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.27 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Round Robin (RR)

Se existem n processos na fila de prontos e o quantum de tempo vale q, então cada processo recebe 1/n do tempo de CPU dividido em intervalos de tempo com q unidades de tempo. Nenhum processo esperará mais do que (n-1)q unidades de tempo.

O temporizador gera uma interrupção a cada quantum para escalonar o próximo processo

Desempenho

q grande FIFO

q pequeno s q não for grande com relação ao tempo de troca de contexto, então a sobrecarga é muito alta

Ex: 5 processos, quantum = 20 ms-Cada processo recebe 20 ms de CPU a cada 5*20=100 ms

Page 28: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.28 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Quantum e troca de contexto

Page 29: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.29 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Variação do tempo de turnaround médio de acordo com o quantum

80% das rajadas de CPU devem ser menores que q

Page 30: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.30 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Filas Multiníveis

Fila de prontos é particionada em diferentes filas. Ex:

foreground (processos interativos)

background (processos em batch)

Processos permanentemente em uma dada fila

Cada fila tem o seu próprio algoritmo de escalonamento:

Ex:

foreground – RR

background – FCFS

O escalonamento precisa ser realizado entre filas:

Escalonamento com prioridade fixa

Ex: Servir a todos os processos de foreground antes de servir os processos de background (Possibilidade de inanição).

Porção de tempo – cada fila obtém uma certa quantidade de tempo de CPU

Exemplo: 80% para foreground em RR e 20% para background em FCFS

Page 31: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.31 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento em filas multiníveis

Page 32: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.32 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Filas multiníveis com realimentação

Um processo pode ser movido entre várias filas

Envelhecimento pode ser implementado dessa forma

Parâmetros do escalonador:

Número de filas

Algoritmo de escalonamento de cada fila

Método para determinar o processo de escalonamento entre filas

Método para rebaixar um processo

Método para determinar a qual fila pertence um novo processo

Page 33: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.33 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Exemplo de Filas multiníveis com realimentação

Três filas:

Q0 – RR com quantum de 8 ms

Q1 – RR com quantum de 16 ms

Q2 – FCFS

Escalonamento

Rebaixamento de jobs

Novos jobs na fila Q0

– Quando o processo chega a CPU, pode ser processado por no máximo 8 ms

– Se precisar de mais tempo de CPU, o job é movido para a fila Q1

Na fila Q1 , o job recebe um máximo de 16 ms de tempo de CPU

– Se não for suficiente para terminar ou fazer um pedido de I/O, ele é posto em Q2

Entre filas: Q2 só é acessada quando não existem jobs em Q1, que por sua vez só é acessada quando não existem jobs em Q0

Page 34: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.34 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Filas multiníveis com realimentação

Sujeito a inanição!

Page 35: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.35 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento de Threads

Distinção entre threads de nível de usuário e de nível de kernel

Usuário – gerenciados por biblioteca, sem interferência do kernel

Biblioteca mapeia os threads de usuário em processos leves

Kernel – gerenciados pelo kernel

Page 36: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.36 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Relembrando... Modelos multithreads

Page 37: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.37 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento de Threads

Distinção entre threads de nível de usuário e de nível de kernel

Usuário – gerenciados por biblioteca, sem interferência do kernel

Biblioteca mapeia os threads de usuário em processos leves

Kernel – gerenciados pelo kernel

Quando o sistema tem suporte a thread, threads são escalonados e não processos

Cada processo é mapeado em um ou mais threads

Page 38: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.38 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Relembrando....Processos e Threads

Page 39: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.39 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento com múltiplos processadores

Escalonamento de CPU é mais complexo quando múltiplas CPUs estão em uso

Multiprocessadores

Homogêneos

Todos os processadores tem capacidades iguais

Heterogêneos

Multiprocessamento

Assimétrico

Simples

– Um processador (mestre) cuida do escalonamento, processamento de I/O e outras atividades do sistema

– Demais processadores executam código de usuários

Simétrico

Cada processador cuida do seu próprio escalonamento

Fila de prontos pode ser única ou por processador

Usado em praticamente

todos os sistemas

operacionais

Page 40: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.40 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento com múltiplos processadores

Afinidade do processador

Processo tem afinidade com o seu processador corrente

Leve

– Processo tende a ficar no mesmo processador, mas eventualmente pode ser trocado

Forte

– Processo especifica que não deve migrar para outros processadores

Melhora a eficiência no uso do cache do processador

Page 41: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.41 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Exemplos de Sistemas Operacionais

Escalonamento no Solaris

Escalonamento no Linux

Page 42: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.42 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Solaris

Escalonamento baseado em prioridade

Seis classes

Tempo compartilhado (padrão)

Interativo

Tempo real

Sistema

Compartilhamento justo

Prioridade fixa

Um thread só pode pertencer a uma classe de cada vez

Cada classe tem seu próprio algoritmo de escalonamento

A classe tempo compartilhado tem uma fila de múltiplos níveis com realimentação

Page 43: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.43 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Tabela de despacho para classes padrão e interativa

Alta prioridade

Próxima prioridade

se quantum de tempo chegar ao

fim

Próxima prioridade

de processos que foram suspensos antes de usarem todo o

quantum (ex: pedido

de I/O)

Baixa prioridade

Page 44: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.44 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento do Solaris

Escalonamento entre filas

Escalonador converte prioridades específicas de cada classe em uma prioridade global por thread

O thread com a maior prioridade é o próximo a ser executado

Threads com mesma prioridade são escolhidos via RR

Thread executa até que:

Seja bloqueado

Use a sua fatia de tempo

Seja movido por preempção por um thread de maior prioridade

Page 45: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.45 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento do Solaris

Page 46: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.46 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento do Linux

Escalonador é executado em tempo constante, independente da carga do sistema Melhora com relação à versão original, herdada do Unix

Preemptivo Baseado em prioridade

Duas classes Tempo compartilhado e tempo real

Quanto menor o valor, maior a prioridade Jobs com prioridade maior ganham maior fatia de tempo

Diferentemente do Solaris

Page 47: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.47 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Prioridades e tamanho da fatia de tempo

Page 48: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.48 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento do Linux

Tarefas organizadas em fila de execução (uma por processador) Organizadas em dois arrays com prioridade (ativo, expirado)

Uma tarefa pode executar enquanto tiver tempo disponível em sua fatia

Ao terminar de usar sua fatia de tempo, a tarefa não pode ser executada até que todas as outras tenham expirado o seu tempo Movida do array de ativos para array de expirados

Quando o array de ativos fica vazio, os arrays são trocados

Page 49: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.49 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Arrays de ativos e expirados

Page 50: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

5.50 Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Escalonamento do Linux

Escalonamento de tempo real de acordo com o POSIX.1b

Tarefas de tempo real tem prioridade estática

Demais tarefas com prioridade dinâmica

Escalonador favorece tarefas interativas

Tarefas interativas tem muito I/O e, consequentemente, grande tempo de suspensão

Atualização de prioridade feita com base no tempo de suspensão (de -5 a +5)

– Tempos de suspensão maiores levam a reduções maiores no valor da prioridade (aumento da prioridade) – Processos limitados por I/O

– Tempos de suspensão menores levam a aumentos maiores no valor da prioridade (redução da prioridade) – Processos limitados por CPU

A atualização da prioridade é feita quando a tarefa expira

Page 51: Silberschatz, Galvin and Gagne ©2009 Operating System Concepts – 8 th Edition Capítulo 5: Escalonamento de CPU

Silberschatz, Galvin and Gagne ©2009Operating System Concepts – 8th Edition

Fim do capítulo 5