Aula 06 ESCALONAMENTO DE CPU

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
SISTEMAS OPERACIONAIS
Prof. Gerhard Saboia
Capítulo 6: Escalonamento de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Capítulo 6: Escalonamento de CPU
Conceitos básicos
Critérios de Escalonamento
Algoritmos de Escalonamento
Escalonamento em Múltiplos Processadores
Escalonamento em Tempo Real
Avaliação de Algoritmos
Modelos de Escalonamento de Processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.1 Conceitos Básicos
Objetivo da multiprogramação: maximizar uso da CPU
Diversos processos em memória
Sempre que um deixa a CPU (em geral por E/S), outro ganha
O escalonamento (scheduling) é função fundamental
Praticamente todos recursos são escalonados (não só CPU)‏
O escalonamento é parte central do projeto de um SO
Execução de processo composta de:
Picos de CPU (CPU bursts): execução intensiva de instruções
Picos de E/S (I/O bursts): aguardo por E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Seqüências de Picos de CPU e E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Histrograma de Picos de CPU
* Maior parte dos picos são curtos (até 8ms)‏
* Poucos são longos (até 40ms)‏
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
Escalonador de CPU (curto prazo)‏
Seleciona processo na fila (FIFO ou não) da de prontos
Preempção: interrupção da execução de um processo seguida da alocação da CPU a outro processo
Retira-se o processo da CPU de maneira “forçada”
Escalonamento pode ser
Sem preempção: processo resolve deixar a CPU
Com preempção (preemptivo): processo retirado e trocado
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
As decisões de escalonamento de CPU podem ocorrer quando um processo:
1. Passa do estado em execução para em espera
2. Passa do estado em execução para pronto
3. Passa do estado em espera para pronto
4. Termina (passa para o estado terminado)‏
Nos casos 1 e 4 o escalonamento é sem preempção
Nos casos 2 e 3 o escalonamento é com preempção
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonador de CPU
Escalonador de CPU sem preempção
Um processo pode usar a CPU o quanto desejar ou até terminar: inviabiliza tempo compartilhado
Escalonador de CPU com preempção
Requer hardware especial (timer)‏
Requer melhor projeto
Problema: como retirar um processo da CPU se o kernel está tratando 	de suas atividades?
Pode haver inconsistências, perdas de dados
Alguns sistemas: só fazem preempção após final de chamada ao sistema ou bloco de E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Despachante (Dispatcher)‏
Despachante
Módulo que passa o controle da CPU ao processo escolhido pelo escalonador
Realiza 
Troca do contexto
Coloca a execução em modo usuário
Desvia a execução para o local apropriado do processo escolhido para iniciá-lo (ou reiniciá-lo)‏
Latência de despacho: tempo gasto para o despachante operar
Despachante deve ser rápido: invocado a cada troca de processo (tempo compartilhado....)‏
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.2 Critérios de Escalonamento
Existem diferentes algoritmos de escalonamento
Para os mesmos ou diferentes propósitos
Utiliza-se uma série de critérios para compará-los e para eleger um bom escalonador
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Critérios de Escalonamento
Principais critérios considerados:
Utilização de CPU: pode variar de 0 a 100%, indicando se está ociosa ou carregada
Throughput: número de processos que são executados em unidade de tempo (por segundo, hora, etc.)‏
Tempo de turnaround: tempo que um processo leva, de sua submissão até o completamento (inclui E/S, esperas, etc.)‏
Tempo de espera: tempo total que um processo gasta esperando na fila com o estado pronto
Tempo de resposta: intevalo que leva entre uma solicitação ao processo e a primeira resposta do processo
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Critérios de Escalonamento
Objetivos de um escalonador:
Maximizar
Utilização da CPU
Throughput
Minimizar
Tempo de turnaround
Tempo de espera
Tempo de resposta
Deseja-se maximizar ou minimizar não somente um valor específico, mas, em geral, a média dos valores dos processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
6.3 Algoritmos de Escalonamento
Principais algoritmos
FCFS (First Come, First Served)‏
SJF (Shortest Job First)‏
RR (Round-robin)‏
Filas Multiníveis
Filas Multiníveis com Retroalimentação 
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” (FCFS)‏
FCFS
Algoritmo de escalonamento mais simples
Primeiro processo a requisitar CPU é o primeiro a ganhar
Sem preempção
Se um processo ganha a CPU, só sai se terminar ou fazer E/S
Não adequado para sistemas de tempo compartilhado
Implementação simples
Através de fila de prontos FIFO
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” (FCFS)‏
Processo Tempo de pico
P1 24ms
P2 3ms
P3 3ms
Ordem de chegada: P1 , P2 , P3. O diagrama de Gantt (etapas de execução) para o escalonamento será:
Tempo de espera para P1 = 0; P2 = 24; P3 = 27
Tempo de espera médio: (0 + 24 + 27)/3 = 17ms
Tradução de Operating Systems Concepts de Silberschatz,
Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “First-Come, First-Served” (FCFS)‏
Se ordem de chegada for: P2 , P3 , P1. O diagrama de Gantt para o escalonamento será:
Tempo de espera para P1 = 6; P2 = 0; P3 = 3
Tempo de espera médio: (6 + 0 + 3)/3 = 3ms
Muito melhor do que no caso anterior
Efeito comboio: 1 processo CPU-bound + n I/O-bound
n processos fazem E/S e têm que aguardar o CPU-bound
Isso se repete durante toda a execução
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento “Shortest Job First” (SJF)‏
Escalonador possui informação sobre tamanho do próximo pico de CPU de cada processo
Essa informação é usada para escolher processo com tempo mais curto 
Dois esquemas:
Sem preemção
Com preempção: se um outro processo chegar pico de CPU menor do que o restante do processo atual, há preempção. Esse esquema é conhecido como “Shortest Remaining Time First” (SRTF).
SJF é ótimo
Sempre provê o menor tempo de espera médio para um determinado conjunto de processos
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de SJF sem Preempção
 Processo Tempo do próximo pico
P1 6ms
P2 8ms
P3 7ms
P4 3ms
Escalonamento:
Tempo de espera para P1 = 3; P2 = 16; P3 = 9; P4 = 0
Tempo de espera médio: (3+16+9+0)/4 = 7ms
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de SJF com Preempção (SRTF)
Processo Chegada Pico
				 P1 0 8
				 P2 1 4
				 P3 2 9
				 P4 3 5
Escalonamento:
Tempo de espera médio = [(10 -1)+(1-1)+(17-2)+(5-3)]/4 = 6,5 ms
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Dificuldades com SJF
Como determinar os tempos dos próximos picos de CPU?
Usuário informa: em escalonadores de longo prazo
Não há forma automática de saber exatamente o tempo do próximo pico
Pode-se estimar: utilizando como base tempos dos picos anteriores
Embora SJF seja ótimo, não pode ser usado como escalonador de CPU (curto prazo)
Pode apenas estimar o tempo
Estimação do próximo pico através de uma média exponencial:
n+1 = duração estimada do próximo pico de CPU
n = história dos picos passados
tn = duração real do enésimo burst de CPU
Define-se: n+1 =  tn + (1 - ) n , onde 0 ≤  ≤ 1
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Estimação do próximo pico de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplos de Média Exponencial
 =0
n+1 = n
O histórico recente não conta.
 =1
 n+1 = tn
Apenas o último surto de CPU real tem efeito.
Se expandirmos a fórmula, obtemos:
n+1 =  tn+(1 - )  tn -1 + …
 +(1 -  )j  tn -1 + …
 +(1 -  )n=1 tn 0
Como  e (1 - ) são menores ou iguais a 1, cada termo sucessivo possui peso menor do que seu.
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
Um número de prioridade (inteiro) é associado a cada processo
A CPU é alocada para o processo com a prioridade mais alta
Processos de igual prioridade são executados na ordem FCFS
SJF é um caso particular do escalonamento por prioridade
A prioridade é o inverso do próximo pico de CPU
Neste livro
Números menores: prioridades mais altas
Números maiores: prioridades mais baixas
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
Tempo de chegada: 0 para todos os processos
Processo Pico de CPU Prioridade
				 P1 10 3
				 P2 1 1
				 P3 2 4
				 P4 1 5
							 P5 5 2
Escalonamento:
Tempo de espera médio = 8,2 ms
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento por Prioridades
Escalonamento pode ser
Preemptivo: se chega um de prioridade mais alta, o escalonador troca de processo
Não-preemptivo
Problema
Possibilidade de estagnação/inanição/starvation
Um processo de baixa prioridade podem nunca ser executado!
Solução: envelhecimento (aging)
Conforme o tempo passa, aumenta a prioridade dos processos que estão em espera há muito tempo
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento Round-Robin (RR)‏
Projetado para sistemas de tempo compartilhado
Semelhante FCFS
Preemptivo: comutação entre processos
Definição de quantum: unidade de tempo (ex.: 10 ou 100ms)
Escalonamento RR
Fila de prontos é uma fila FIFO circular
Escalonador percorre fila alocando, para cada processo, até 1 quantum 
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento Round-Robin
Se processo não deixar a CPU dentro do quantum, é preemptado
Se houverem n processos e o quantum for q, cada processo possui 1/n tempo de CPU, executado em porções de tempo de tamanho até q
Nenhum processo espera mais do que (n-1)q para utilizar CPU
Não ocorre starvation (estagnação)
Desempenho
Quantum muito grande: execução FCFS (FIFO)
Quantum muito pequeno: muitas trocas de contexto
Alto custo
Quantum deve ser pequeno suficiente para garantir o tempo compartilhado
Quantum deve ser grande bastante para compensar trocas de contexto
Bom desempenho: 80% dos picos de CPU devem ser menores que quantum
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne
(c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de RR com quantum 4ms
Processo Pico de CPU
P1 24
P2 3
P3 3
Tempo de chegada: 0 para todos processos
A execução será:
Tempo de espera médio: (6 + 4 + 7)/3 = 5,66ms
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exercício
Cinco jobs A, B, C, D e E, em batch, chegam ao computador com 1 segundo de intervalo entre eles. Seus tempos de processamento são estimados em 10, 7, 3, 4 e 5 segundos de CPU, respectivamente. Sendo round-robin a política de escalonamento utilizada, com um quantum de 1 segundo.
 O tempo médio de turnaround desses processos (ignorando overheads de troca de contexto e interrupções e assumindo que um job recém-chegado é colocado no início da fila, ou seja, na frente dos outros) é: 
a)	25,5 s	b)	13,1 s	c)	10,0 s	d)	19,6 s	e)	29,0 s
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Quantum de Tempo e Tempo de Troca de Contexto
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Turnaround varia conforme o quantum
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis
Fila de prontos é dividida em várias filas
Ex.: 2 filas
Processos em primeiro plano (interativos/foreground)‏
Processos em segundo plano (background/batch)‏
Cada fila possui seu próprio algoritmo de escalonamento:
Ex.:
Processos em primeiro plano: RR (para manter tempo compartilhado)
Processos em background: FCFS
É necessário haver escalonamento entre as filas:
Para escolher o processo de qual fila será executado
Se usar algoritmo de prioridade fixa de uma fila sobre outra: starvation
Outra opção: dividir o tempo de execução entre as filas
Foreground fica com 80% e background com 20% do tempo de CPU
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis e prioridade fixa
d
Discriminação?
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis com Retroalimentação
Sem retroalimentação: processo nunca é trocado de fila
Com retroalimentação: processo pode ser trocado de fila
Permite separar processos com características de picos de CPU semelhantes
Um processo que usa muito tempo de CPU é movido para fila de mais baixa prioridade
Dessa forma: processos IO-bound e interativos (dependem da interação do usuário) ficam nas filas com mais prioridade
Processos que ficam aguardando muito tempo por CPU podem ser movidos para filas de mais alta prioridade: evita starvation (inanição)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Filas Multiníveis com Retroalimentação
Escalonador é definido pelos seguintes parâmetros:
número de filas
algoritmos de escalonamento para cada fila
método usado para determinar quando elevar um processo
método usado para determinar quando rebaixar um processo
método usado para determinar em que fila um processo entrará quando esse processo precisar de atendimento
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de escalonamento com retroalimentação
Três filas (com prioridade fixa):
Q0 – quantum de tempo 8 milissegundos
Q1 – quantum de tempo 16 milissegundos
Q2 – FCFS
Escalonamento
Uma nova tarefa entra na fila Q0 , que é atendida com base no RR. Quando ganha a CPU, a tarefa recebe 8 milissegundos. Se não terminar nesse tempo, a tarefa é movida para a fila Q1.
Em Q1, a tarefa é atendida novamente com base no RR e recebe 16 milissegundos adicionais. Se ainda não estiver completa, a tarefa é apropriada e movida para a fila Q2.
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Exemplo de escalonamento com retroalimentação
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Múltiplos Processadores
Escalonamento da CPU é muito mais complexo quando várias CPUs estão disponíveis
Processadores idêndicos: simplificação
Compartilhamento de carga: várias CPUs cooperando
Idéia 1: usar fila de prontos separada para cada processador
Enquanto uma CPU fica sobrecarregada outra pode ficar ociosa
Idéia 2: usar fila de prontos comum
Faz um melhor balanceamento da carga
Problemas: CPUs diferentes podem escolher mesmo processo, pode haver outras inconsistências devido ao paralelismo
Multiprocessamento assimétrico (mestre/escravo): mais simples
Só 1 CPU acessa as estruturas de dados do SO (mestre), demais executam
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
Sistemas de tempo real rígido: tarefas devem ser completadas dentro do tempo exigido
Praticamente impossível em um sistema de propósito geral com memória secundária ou memória virtual
Sistemas de tempo real flexível (maleável): tarefas críticas têm maior prioridade sobre as demais
Permite sistemas gráficos/mutimídia executarem de forma adequada (em detrimento de outros processos): aceitável
Latência de despacho deve ser pequena: diminui o tempo para um processo tempo real pronto entrar em execução
Problema: SOs não realizam preempção no meio de chamada ao sistema o bloco de E/S
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
Para reduzir tempo de despacho
Algumas chamadas ao sistema (demoradas) tornam-se interceptáveis
Possuem pontos de interceptacao: locais que verificam se há processos de tempo real para serem executados
Chamadas ao sistema podem ser interrompidas nesses pontos e retomadas futuramente (após execução do processo em tempo real)
Pontos de interceptação devem estar em “áreas seguras” do kernel
Não pode haver possibilidade de inconsistências
Solaris 2: todo o kernel é interceptável (mecanismos de sincronização)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Escalonamento em Tempo Real
Inversão de prioridade
Processo de alta prioridade necessita aguardar recursos que estão sendo atualizados por processo de baixa prioridade: ineficiência
Protocolo de herança de prioridade: processos que estão acessando recursos necessários a um processo de alta prioridade herdam essa prioridade até liberação do recurso
Melhor desempenho
Prioridades voltam ao original após liberar recurso
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Latência de despacho em tempo real
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação de Algoritmos
Modelagem determinística
Considera uma carga de trabalho particular (pré-determinada)
Define (calcula) o desempenho de cada algoritmo para a carga
Utilização de CPU, throughput, tempo de espera, tempo de turnarorund, etc.
Modelos de enfileiramento
Formulação matemática e estatística envolvendo
Distribuição de picos de CPU e E/S, probabilidade de ocorrência de picos particulares, etc.
Permite comparar matematicamente algoritmos de forma tratável
Comparação pode ser irrealística em função de premissas imprecisas
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação de Algoritmos
Avaliação por simulação
Método mais preciso
Utiliza um modelo de sistema de computação
Informações (processos, picos de CPU, chegadas, E/S, términos, etc.) podem ser geradas aleatoriamente
De acordo com distribuições probabilísticas
Resultados são usados para verificar o que ocorre na realidade e adota-se a distribuição adequada
Avaliação por implementação
Mais realista
Alto custo: necessário implementar no kernel e testar sob as diversas situações reais (usuários são prejudicados pelas modificações)
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Avaliação dos Escalonadores de CPU
por Simulação
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
Modelos de escalonamento de processos
Solaris 2
Windows 2000
Linux
Tradução de Operating Systems Concepts de Silberschatz, Galvin e Gagne (c) 2002
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*