Upload
phamnguyet
View
214
Download
0
Embed Size (px)
Citation preview
1
Sistemas Operativos I
Escalonamento Luis Lino Ferreira / Maria João ViamonteFevereiro de 2006
05/06 2Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Sumário
Conceitos básicosCritérios de escalonamento Algoritmos de escalonamentoEscalonamento multi-processadorEscalonamento em tempo real
2
05/06 3Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Conceitos Básicos
Objectivos do escalonamentoOptimizar a performance do sistema de acordo com um critério
Dividir a capacidade de processamento da UCP entre vários processosDiminuir o tempo de resposta (sistemas de Tempo-Real)
Como? Alguns exemplos:
Quando um processo está à espera (por ex: de uma operação de I/O ou de um sinal), outro processo pode entrar em funcionamentoPeriodicamente é retirado um processo e substituído pelo próximo na fila de ready
05/06 4Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Caracterização de um programa
Ciclo de um programaExecução na UCP (CPU Burst) seguido de espera atéà finalização de um operação de I/O (I/O Burst)
3
05/06 5Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Notação Gráfica UtilizadaChegada de um processo ao sistema
Processo em execução (estado de running)
Processo à espera (estado de waiting)
Finalização de um processo
Exemplo:
P2
3 110 6 9 15 t
P2
05/06 6Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Histograma dos CPU BurstsA duração dos CPU Burst têm tendência a ter uma curva de frequência exponencial, com muitos CPU Burst de curta duração e poucos CPU Burstde longa duração
Um programa I/O-bound tem muitos CPU Burst de curta duração Um programa CPU-bound
tem poucos CPU Burst, mas estes são de longa duração
4
05/06 7Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonador da UCPO escalonador selecciona entre os processos na fila de Ready,aqueles que devem entrar em execução de seguidaA decisão de escalonamento pode ser feita nas seguintes circunstâncias:
1. O processo comuta do estado Running para o estado Waiting (pedido de I/O, evocação da função wait())
2. O processo comuta do estado Running para o estado Ready(ocorrência de uma interrupção)
3. O processo comuta do estado Waiting para o estado Ready(termina um pedido de I/O)
4. O processo termina
05/06 8Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Diagrama de Estados
1
2
3
4
ReadyReady RunningRunning
WaitingWaiting
TerminatedTerminatedInterrupção
I/O ou espera evento
Exit
EscalonadorI/O fim ouchegada evento
5
05/06 9Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Tipos de Escalonamento
Escalonamento não preemptivo: o escalonador apenas pode efectuar a comutação entre processos quando o processo termina ou passa para o estado de WaitingCasos 1 e 4*Exemplo: Windows 3.1 e AppleMacintosh OS
05/06 10Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Tipos de Escalonamento
Escalonamento preemptivo: o escalonador pode interromper a execução de um processo antes que este tenha terminado
Casos 2 e 3* * do slide anterior
6
05/06 11Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento preemptivoAlguns problemas
2 Processos partilham dadosUm dos processo está a actualizar os dados, a UCP decide efectuar a comutação para outro processoO segundo processo vai ter acesso a dados potencialmente inconsistentes
Mecanismos para protecção no acesso a dados partilhados (Capítulos seguintes)
05/06 12Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
DispatcherOutro componente envolvido na função de escalonamento é o Dispatcher :
É o módulo que atribui a UCP ao processo seleccionado pelo escalonador de curto-prazo
Dispatcher executa as seguintes operações:comutação de contextocomutação para o modo de utilizadorsalto para o endereço adequado de memória do programa por forma a continuar ou iniciar a sua execução
O tempo de execução do Dispatcher deverá ser minimizado
7
05/06 13Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Estrutura de um Escalonador
Selecciona processo
Coloca processo em funcionamento
Escalonador Dispatcher UCP
05/06 14Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Tipos de Escalonamento
NewNew
ReadyReady RunningRunning
WaitingWaiting
TerminatedTerminatedSuspended
ReadySuspended
Ready
SuspendedBlocked
SuspendedBlocked
Escalonamento a médio prazo
Escalonamento a longo prazo
Escalonamento a curto prazo
8
05/06 15Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de EscalonamentoCritérios orientados ao utilizador (performance)
Turnaround timeTempo que decorre entre o instante em que um processo ésubmetido e o instante em que é concluídoÉ a soma do tempo de espera para ir para a memória, tempo de espera na fila dos ready, tempo em execução na UCP e o tempo de espera por recursos
Tempo de respostaTempo que decorre entre a submissão de um pedido e o início da resposta este critério é adequado para sistemas interactivosObjectivos: baixo tempo de resposta maximizando o número de utilizadores com tempos de resposta aceitáveis
05/06 16Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de EscalonamentoCritérios orientados ao utilizador (performance)
DeadlineDeadline, ponto no tempo no qual um determinado resultado de computação deve estar disponível
Sempre que forem especificadas deadlines, o critério de escalonamento deve garantir que as deadlines são cumpridas, caso não seja possível deve garantir que o mínimo número de deadlines é ultrapassado
9
05/06 17Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de EscalonamentoCritérios orientados ao utilizador (outros)
Predictabilidadeum determinado processo, independentemente da carga do processador deve correr aproximadamente no mesmo tempoExemplos:
um jogo de computador do tipo “Arcade” deve correr à mesma velocidade independentemente da máquina em que está funcionar e da respectiva cargaum programa de descodificação de vídeo deve ser capaz de processar 30 frames por segundo independentemente da máquina e respectiva carga
05/06 18Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de Escalonamento
Critérios orientados ao sistema (performance)Utilização da UCP
Utilização: razão entre o tempo durante o qual a UCP éutilizada e o tempo total de execuçãoO objectivo é maximizar a utilização da UCP
Débito (Throughput)Número de processo executados por unidade de tempoMaximizar o número de processos concluídos por unidade de tempoO valor óptimo depende dos processos
10
05/06 19Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de EscalonamentoCritérios orientados ao sistema (outros)
FairnessNa ausência de qualquer critério por parte do utilizador os processo devem ser tratados de forma idêntica pela UCP
PrioridadesCada processo é associado a uma determinada prioridade que lhe garante um tratamento diferenciado por parte da UCP em relação aos outros processo do sistema, podendo ser beneficiado ou prejudicado
05/06 20Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Critérios de EscalonamentoCritérios orientados ao sistema (outros)
Balanceamento de recursosUtilizado em conjunto com políticas de escalonamento de médio e longo prazo, permite escalonar preferencialmente processos que sub-utilizem determinados recursos, que se encontrem sobrecarregados
Tempo de esperaÉ a soma dos períodos dispendidos pelo processo no estado de Ready
11
05/06 21Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Algoritmos de Escalonamento
Fisrt-Came, Fisrt-Served (FCFS)Shortest-Job-First (SJF)Escalonamento por PrioridadesRound-Robin (RR)Multi-nível por FilasMulti-nível com realimentação por filas
05/06 22Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)O processo que chega à fila de ready em primeiro lugar étambém o primeiro processo a ser executadoSimples e fácil de implementarNão preemptivo
um processo apenas liberta a UCP quando termina ou quando requer uma operação de I/O
ProblemasEfeito de comboio, resultando em baixa utilização da UCPFavorece processos CPU Bound, dado que os processo I/O Bound têm que esperar pelo fim dos processos CPU Bound
12
05/06 23Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)
Exemplo:Processo Burst Time
P1 24P2 3P3 3Ordem de chegada: {P1, P2, P3}
05/06 24Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)
Tempo de espera: P1=0, P2=24, P3=27Tempo médio de espera: (0+24+27)/3 =17
P1 P2 P3
24 27 300
P1, P2, P3
13
05/06 25Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)Ordem de chegada: {P2, P3, P1}
Tempo de espera: P2=0, P3 = 3, P1=6Tempo médio de espera: (0+3+6)/3=3O Efeito de Comboio deve-se aos processo mais curtos terem que esperar por processos de maior duração
P1P3P2
63 300
P2, P3, P1
05/06 26Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)
Exemplo com processos I/O Bound e CPU BoundPerfil de execução P1 (I/O Bound)
Perfil de execução de P2 (CPU Bound)
P1
30 6 9 15 t
P1
P2
0 6 15 t
P2
14
05/06 27Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)
ResultadoOrdem de chegada {P1, P2}
Os processo CPU Bound tem tendência para serem executados primeiro
P1
3 110 6 9 19 t
P2,P1
P2 P1 P2 P1 P1
21 27
05/06 28Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
First-Come, First-Served (FCFS)
Favorecimento de processos CPU-boundOs processos I/O bound libertam a UCP sempre que requerem uma operação de I/OPassam para a fila de waitingQuando terminam a operação de I/O, voltam a entrar na fila de ready na última posiçãoEsperam até que os processo à sua frente terminem ou libertem a UCP
15
05/06 29Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)O escalonador selecciona o processo na fila de readyque tiver menor tempo de execução
Não preemptivo: se chegar à fila de ready um processo com um tempo de execução menor que o processo em execução, este não é comutadoPreemptivo: o processo em execução é comutado pelo processo novo se o tempo restante de execução for maior que o tempo de execução do processo novo (Shortest-Remaining-Time-First(SRTF))
05/06 30Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)
SJF - Não PreemptivoProcesso Chegada Burst
P1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4
P1 P3 P2
73 160
P4
8 12
P1 P2 P3 P4
16
05/06 31Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)SJF - Preemptivo
Processo Chegada BurstP1 0.0 7P2 2.0 4P3 4.0 1P4 5.0 4
P1 P3P2
42 110
P4
5 7
P2 P1
16
P1 P2 P3 P4
Chegada de um processo
05/06 32Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)Características
É considerado como um algoritmo óptimo* para minimização do tempo médio de esperaUsado essencialmente para escalonamento a longo prazo
ProblemasÉ necessário conhecer e avaliar o tempo de execução do processo Não é possível saber apenas é possível estimar
Pode-se utilizar como tempo de execução o tempo limite especificado pelo utilizador
Em casos de carga elevada os processos mais longos são prejudicados (i.e. são os últimos a ser executados)Pouco adequado ao escalonamento de curto prazo devido àdificuldade de prever a duração do próximo CPU Burst
* Não foi ainda provado
17
05/06 33Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)
SJF no escalonamento a curto prazoPode ser utilizada uma estimativa da duração do próximo CPU Burst (τn+1) com base nos anterioresA duração do próximo CPU Burst é uma média exponencial da duração dos anteriores CPU Burstτn+1=α.tn + (1- α).tn - média exponencial para um valor de α
α: controla o peso relativo da historia passada e recente, 0≤α≤1tn: duração do último CPU Burstτn+1: valor previsto para o próximo CPU Burst
05/06 34Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Shortest-Job-First (SJF)
α= 0.5t0=10
18
05/06 35Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento por Prioridades
Cada processo tem uma prioridade associadaA UCP é alocada ao processo com maior prioridadeProcessos de igual prioridade podem ser escalonados através de FCFSPode ser preemptivo ou não preemptivoA prioridade é representada por um número inteiro positivo (nesta disciplina adoptou-se que 0 representa a maior prioridade)
05/06 36Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento por Prioridades
Escalonamento não preemptivo Processo Burst Prioridade
P1 3 3P2 2 1P3 2 4P4 2 5P5 5 2
Chegada simultânea no tempo 0
P5 P1P2
73 140
P3
10
P4
P1,P2, P3, P4, P5
19
05/06 37Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
P2,P3
Escalonamento por Prioridades
Escalonamento preemptivoProcesso Burst Prioridade Tempo de chegada
P1 3 3 0P2 2 1 2P3 2 4 2P4 2 5 5P5 5 2 7
P2P1
72 140
P1
12
P4P5
P1 P4 P5
P3
05/06 38Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento por PrioridadesCaracterísticas
Em situações de sobrecarga os processos de menor prioridade podem nunca ser executados
Uma das soluções para este problema é aumentar a prioridade do processo com o tempo
As prioridades podem ser definidas:em função das propriedades do processo
Duração dos CPU Bursts, deadlines, importância do processo, etc
politicamenteEm função do pagamento do utilizador, o departamento a quem pertence o processo, etc
20
05/06 39Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Round-Robin (RR)Especialmente adaptado para Sistemas Partilhados Multi-utilizadorAlgoritmo:
Cada processo obtém uma pequena unidade de tempo da UCP, timequantum ou time slice, vulgarmente 10 -100msNo fim de cada time quantum (q) o processo é comutado e adicionado à cauda da fila readyCaso o processo termine a sua execução ou passe para o estado de waiting durante time quantum atribuído, o escalonador selecciona o processo seguinte para execuçãoO escalonador necessita de um timer de modo a que seja periodicamente interrompido após cada time quantum
05/06 40Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Round-Robin (RR)
Processo BurstP1 53P2 17P3 68P4 24
time quantum = 20
P1 P2 P3 P4 P1 P3 P4 P1 P3 P3
0 20 37 57 77 97 117 121 134154 162
P2 termina sua execução
P4 termina sua execução
P1 termina sua execução
P3 termina sua execução
P1,P2, P3, P4
21
05/06 41Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Round-Robin (RR)Características
Melhor tempo de resposta do que SJFO escalonamento em RR pode ser visto como dividir a capacidade de processamento da UCP pelo vários processos
ProblemasSe o time quantum for pequeno o overhead do algoritmo pode ser grande (FCFS)Favorece processo CPU bound
Os processos I/O bound usam a UCP durante um tempo inferior ao time quantum e após o que passam para a fila de waitingOs processo CPU bound usam o seu time quantum na totalidade e voltam para a fila de ready
05/06 42Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Round-Robin (RR)
Turnaround timetempo que decorre entre o instante em que um processo ésubmetido e o instante em que é concluídoTurnaround time também estádependente do valor do timequantum
22
05/06 43Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Round-Robin (RR)
Algumas questões:E se quisermos dar maior importância a um processo?
Que alterações devem ser feitas ao algoritmo RR?
Se reduzirmos o time quantum para um valor muito pequeno.
Que problemas ocorrem?
05/06 44Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
Este tipo de escalonamento é usado quando é fácil classificar os processos em classes distintas, por ex.:
Processos interactivosProcessos batchAplicações multimédia
A fila ready é dividida em várias filas, uma por cada classe de processos
23
05/06 45Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
Cada fila pode ter o seu próprio algoritmo de escalonamento, por ex.:
Processos interactivos: RRProcessos batch: FCFSProcesso do sistema: prioridades
Cada fila tem prioridade absoluta sobre a outra
i.e. um processo da fila de batch apenas corre quando não existirem processos na fila dos processos interactivos
05/06 46Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
24
05/06 47Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
Também é necessário efectuar o escalonamento entre as filas:
Prioridades fixasEm casos de carga elevada os processos atribuídos às filas de menor prioridade são preteridos
Round-Robincada fila obtém uma certa quantidade de tempo da UCP que pode ser escalonado pelos seus processos
80% para processos foreground em RR20% para processos background em FCFS
05/06 48Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por FilasExemplo: 2 processos do sistema: P1 e P2
2 processos interactivos: P3 e P4
1 processo batch: P5
Perfis de execução
P1
30 5t
P2
20 t
P3
30 4 t
P4
30 4 t
P5
30 5t
25
05/06 49Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
Exemplo (cont.)Algoritmos de escalonamento
Processos interactivos: RR com time quantum igual a 2Processos batch: FCFS Processos do sistema: prioridades (P1 = 2, P2 = 0)
Chegadas dos processosP1 – 0P2 – 4P3 – 0P4 – 0P5 – 1
05/06 50Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível por Filas
Exemplo (resultado)
P1P1
5 150 10 17 t
P1,P3, P4
P3 P2 P4 P3
P5P2
P5P4
26
05/06 51Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Permite que um processo se mova entre filasA passagem para um fila de prioridade inferior éfeita quando o processo utiliza mais tempo da UCP do que aquele que lhe estava destinado, por exemplo se o processo exceder o respectivo timequantumIgualmente um processo que espere demasiado tempo numa fila de prioridade inferior pode ser passado para um fila de prioridade superior
05/06 52Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
27
05/06 53Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Três filas: Q0 – RR com time quantum de 8 msQ1 – RR com time quantum de 16 msQ2 – FCFS
EscalonamentoUm novo processo entra na fila Q0, a qual segue uma política RR. Quando ganha a UCP, o processo recebe 8 ms; se não terminar em 8 ms, o processo é passado para a fila Q1Em Q1, o processo é servido novamente por uma política de escalonamento RR e recebe 16 ms adicionais;se mesmo assim não termina, o processo é passado para a fila Q2 com uma política FCFS
05/06 54Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Exemplo:Perfis de execução
P1
30 4 t
P2
30 t
P3
30 4 t
P4
30 4 t
P5
30 5t
28
05/06 55Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Exemplo (cont.)Algoritmos de escalonamento
Q0 RR com time quantum igual a 2Q1 RR com time quantum igual a 3Q2 FCFS
Chegadas dos processosP1 – 0P2 – 0P3 – 0P4 – 0P5 – 0
05/06 56Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Exemplo (resultado)
P3P1
5 150 10 t
P3P2 P4 P1
P1-5
P5
P2 passa para a fila Q1
P5 corre até ao fim dado que as outras filas estão vazias
P4P2 P5
P5 passa para a fila Q1
Dado que a fila Q0 estávazia o escalonador passa a escalonar processos da
fila Q1
29
05/06 57Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Exemplo2RR com time quantum (q) variável por fila, igual a 2(i-1)
Permite que o turnaround time de processos mais longos seja menor
28P5
56P4
44P3
62P2
30P1
Burst timeTempo de chegada
Processo
05/06 58Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Exemplo2 (resultado)
30
05/06 59Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Multi-nível com Realimentação por Filas
Caracterizado por:Número de filasAlgoritmos de escalonamento de cada filaMétodo utilizado para passar um processo para uma fila de mais alta ou mais baixa importânciaMétodo utilizado para decidir em que fila o processo é colocado, após a sua entrada no sistema
05/06 60Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Multi-processador
O problema do escalonamento torna-se ainda mais complexo para sistemas multi-processadorTipos de sistemas
Processadores homogéneos: todos os processadores são idênticos em termos de funcionalidadesProcessadores não homogéneos: alguns dos processadores tem características diferentes. Por ex.: acesso a certo dispositivos de I/O, arquitectura do processador diferente, performance
Objectivos do escalonamentoPartilhar a carga entre processadores
31
05/06 61Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Multiprocessador
Multi-processamento assimétricoSó um processador acede às estruturas de dados do sistema, aliviando a necessidade de partilha de dadosÉ usada uma única fila Ready, e não uma fila por processador, para evitar que haja algum processador inactivo enquanto outros têm processos nas suas filas Ready à espera
05/06 62Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Tempo-Real
Tipos de aplicaçõesIndustriaisAvionicsAutomóveisMultimédia
Tipos de sistemas tempo realSistemas críticos (Hard Real-Time)Sistemas não críticos (Soft Real-Time)
32
05/06 63Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Tempo-Real
Sistemas críticos (Hard Real-Time)É necessário garantir que a(s) tarefa(s) consideradas críticas terminem antes de um determinado tempo (deadline), caso contrário o seu não cumprimento pode resultar em graves danos para o sistemaExemplos:
Aplicações aeroespaciaisABS de um carroSistema de automação
05/06 64Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Tempo-Real
Sistemas não críticos (Soft Real-Time)O funcionamento do sistema é apenas ligeiramente afectado caso não seja possível cumprir um determinada deadline.Exemplos:
Aplicações multimédiaJogos de computador
33
05/06 65Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonamento Tempo-Real
Os métodos de escalonamento devem garantir àpriori que o sistema cumpre as suas metas temporaisÉ normalmente necessário conhecer o tempo de execução das tarefas
Periódicas (por ex. para aquisição de dados)Esporádicas (por ex. para o tratamento de alarmes)
O sistema é muito pouco dinâmicoEscalonamento por prioridadesEscalonamento utilizando o algoritmo Earliest DeadlineFirst (EDF)
05/06 66Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Exemplos de Escalonadores
34
05/06 67Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Exemplos de Escalonadores
Solaris
Windows 2000
Linux
05/06 68Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris
35
05/06 69Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2
Usa um processo de escalonamento baseado nas prioridadesDefine 4 classes de escalonamento:
Real-TimeSystemTime sharingInteractive
Cada classe tem diferentes prioridades e diferentes algoritmos de escalonamento (as duas últimas que usam o mesmo)Por defeito um processo criado é atribuído àclasse de Time Sharing
05/06 70Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2
36
05/06 71Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2
Real-TimeMaior prioridade, prioridade (100-159)*Tempo de resposta garantidoEstes processos correm antes que qualquer outro processo de outra classe (normalmente existem poucos)
SystemProcessos relacionados com o kernel
Processos de utilizadores a correr em Kernel mode não são adicionados a esta classe
Prioridade fixa (60-99)Cada processo corre até bloquear ou ser preemptado por outro processo mais prioritário
* Para o SO Solaris a maior prioridade é 159
05/06 72Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2Time Sharing
Prioridade (0-59)Escalonamento multi-nível com realimentação por filas
Prioridades dinâmicasTime quantums diferentes para cada nível de prioridade (maior prioridade, menor time quantum)Movimentação dos processo entre filas de prioridades diferentes
InteractiveProcesso interactivos são escalonados na classe Time Sharing, mas tipicamente é lhes atribuída maior prioridade e permanecem nessas filas
Bons tempos de resposta para processos interactivosBom débito (throughput, número de processo executados por unidade de tempo) para processos CPU-bound que ficam com baixa prioridade mas com um Time quantum maior
37
05/06 73Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2O escalonador converte a prioridade do processo para as prioridade global e escolhe sempre para entrar em execução o processo com maior prioridadeProcessos com a mesma prioridade são escolhidos por um algoritmo de RR O processo corre na UCP até que:
fique bloqueadoutilize o time quantum que lhe estava atribuído (se não for um processo da classe system, ou seja se for um processo da classe Interactive ou Time-sharing)ou preemptado por um processo de maior prioridade
05/06 74Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Solaris 2Escalonamento de processos Time Sharingou Interactive
Inicialmente aos processo é lhes atribuída a prioridade 29 Caso o processo não utilize todo os seu timeslice:
a sua prioridade é aumentada (até 59)O time slice é diminuindoFavorece processos I/O-bound
Caso o processo utilize todo os seu time slice:a sua prioridade é diminuídao time slice aumentaFavorece processos CPU-bound
38
05/06 75Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Windows
05/06 76Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
WindowsAlgoritmo de escalonamento preemptivo por prioridadesSão definidos 32 níveis de prioridade divididos por 6 classes:
REALTIME_PRIORITY_CLASS (24)HIGH_PRIORITY_CLASS (13)ABOVE_NORMAL_PRIORITY_CLASS (10)NORMAL_PRIORITY_CLASS (8)BELOW_NORMAL_PRIORITY_CLASS (6)IDLE_PRIORITY_CLASS (4)
Os processos com prioridades de 1 a 15 podem ver a sua prioridade alterada dinamicamenteOs processos com prioridades de 16 a 32 têm prioridade fixa
39
05/06 77Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Windows 2000O escalonador gere uma fila para cada nível de prioridade e escolhe para entrar em execução o processo com prioridade mais alta (da fila)Um processo corre até:
Um outro processo de prioridade mais alta entrar para a fila de readyUm processo terminarUm processo terminar o seu time quantumUm processo entrar no estado waiting
Para as classes de prioridade variável o escalonador modifica as prioridades quando:
O Time-quantum do processo expira, sendo a prioridade diminuída de 1Um processo passa de background para foreground (só para a classe NORMAL_PRIORITY_CLASS)Uma janela recebe um evento, por ex. um timer ou recebe mensagens do ratoO processo passa do estado de waiting para ready, a prioridade é aumentada
05/06 78Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Windows 2000Para conseguir níveis de desempenho adequados em programas interactivos, o sistema usa uma regra de escalonamento especial nos processos da classe NORMAL_PRIORITY_CLASS:
Distingue entre nos processos em foreground (quando a janela correspondente está seleccionada) e nos processos em background(quando a janela correspondente não está seleccionada)Quando um processo passa para foreground, aumenta-se a sua prioridade de modo a que esta seja maior ou igual que a prioridade do processo de mais alta prioridade em backgroundQuando do processo passa para backgroud, diminui-se a sua prioridade para a sua prioridade original
Processos de tempo-real têm acesso preferencial à UCP; mas o SO não garante que um processo de tempo real comece a ser executado dentro de um limite temporal pré-definido (o Windows 2000 é do tipo soft real-time)
40
05/06 79Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Windows 2000
A estratégia de prioridades tem alguns aspectos a realçar
Tende a dar óptimos tempos de resposta para processos interactivos que usem o rato e janelasPermite que processos I/O-bound mantenham os dispositivos em funcionamento (sem pausas)Os processos CPU-bound ficam com as sobras da UCP
05/06 80Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Linux
41
05/06 81Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
LinuxEm Linux, o escalonamento também inclui a execução das tarefas do kernelEstas tarefas do kernel incluem as tarefas requisitadas por processos em execução e as tarefas internas ligadas aos device driversA execução em modo kernel pode ocorrer de 3 formas:
Um programa em execução requisita explicitamente um serviço do SO através de uma chamada ao sistema Implicitamente quando a gestão de memória virtual gera uma “falha de página”Um device driver gera uma interrupção que leva a UCP a iniciar uma rotina do kernel para atendimento da interrupção
05/06 82Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
LinuxO Linux usa duas técnicas para proteger a execução de processos:
O código normal do kernel não pode ser interrompidoQuando uma interrupção surge durante a execução em modo kernel, uma flag é activada de modo a que o escalonador possa correr logo que a função de sistema termine e o controlo volte para o modo de utilizador
Para secções críticas de código pertencentes a rotinas de serviço usa-se outra técnica
Desactivando as interrupções por hardware durante as secções críticas, o kernel garante que pode prosseguir sem o risco de acesso simultâneo a dados partilhados do SO (e sem possibilidade de se adulterar o sistema)
42
05/06 83Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
LinuxO Linux usa 3 métodos de escalonamento de processos:
Um algoritmo de tempo partilhado para escalonamento de processos “convencionais”Dois algoritmos de tempo-real para processos em que a previsibilidade dos parâmetros temporais (por ex. período e deadline) do processo são importantes para a sua execução correcta
Por ex. uma tarefa responsável por descodificar um filme deve mostrar um fotograma 30 vezes por segundo
05/06 84Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Linux
É a classe de escalonamento de cada processo que determina qual o algoritmo a usar:
SCHED_FIFO: First-in-first-out tempo realSCHED_RR: Round-Robin tempo realSCHED_OTHER: Escalonamento hierarquicocom realimentação
43
05/06 85Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Linux
O escalonador escolhe para entrar em execução o processo com maior prioridade (0-139) presente na fila de ready
0-99 prioridades estáticas para os processo de tempo-real100-139 prioridades dinâmicas para processos convencionais
Notas:As prioridades estáticas são sempre superiores às dinâmicasOs processos de tempo-real tem sempre prioridade relativamente aos processo convencionais
05/06 86Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Linux
Para processo convencionaisO tempo da UCP é dividido em epochs(épocas)No início de cada epoch o escalonador calcula os time quantums de cada processoUm processo é substituído por outro quando:
utiliza o seu time quantumpassa para o estado de waitingé lançado um processo mais prioritário
O epoch termina quando todos os processo na fila de ready, tiverem esgotado o seu timequantum
44
05/06 87Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
LinuxPara processos convencionais, o Linux usa um algoritmo para calcular o time quantum baseado em créditos e prioridades
A regra de creditação
Os créditos são transformados em tempoa regra leva em conta a história do processo e a sua prioridadeEste sistema de creditação automaticamente dá mais prioridade a processos interactivos ou I/O-bound em detrimento de processos CPU-bound
priority2
credits : credits +=
05/06 88Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
LinuxO Linux implementa as classes de escalonamento de tempo-real FIFO (ou FCFS) e Round-Robin; em ambos os casos, cada processo tem uma prioridade e uma classe de escalonamento próprios
O escalonador executa o processo com a prioridade mais alta; em caso de empate, executa o processo que tem mais tempo de esperaOs processos FCFS executam até terminar ou bloquearOs processos Round-Robin são interrompidos ao fim do seu time quantum e colocados no fim da fila de ready, por forma a garantir equidade no tratamento (entre eles)
45
Sistemas Operativos I
Escalonamento Luis Lino Ferreira / Maria João ViamonteFevereiro de 2006
05/06 90Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Escalonador da UCPO escalonador selecciona entre os processos na fila de Ready, aqueles que devem entrar em execução de seguidaA decisão de escalonamento pode ser feita de acordo com as transições de estado de um processo:
1. Comuta do estado Running para o estado Waiting2. Comuta do estado Running para o estado Ready3. Comuta do estado Waiting para o estado Ready4. Termina5. Quando um processo entra pela 1ª vez para a fila de
Ready
46
05/06 91Sistemas Operativos ILuis Lino Ferreira / Maria João Viamonte
Windows 2000
Threads são a unidade de execução manipulada pelo escalonador do kernelUma Thread pode estar num de 6 estados:
ReadyStandbyRunningWaitingTransitionTerminated