Disciplina: Sistemas Operacionais - CAFW-UFSM
Professor: Roberto Franciscatto
Introdução
• O escalonamento de CPU é a base
dos sistemas operacionais
multiprogramados.
• A partir da resdistribuição da CPU
entre os processos, o sistema
operacional pode tornar o
computador mais produtivo
Conceitos Básicos
• O objetivo da multiprogramação é
contar sempre com algum processo
em execução para maximizar a
utilização da CPU.
• Em um sistema com um único
processador, somente um processo
pode ser executado de cada vez.
• Quaisquer outros processos devem
esperar até que a CPU esteja livre e
possa ser redistribuída.
Conceitos Básicos
• A ideia da multiprogramação é
Com a multiprogramação
tentamos utilizar este tempo de
forma produtiva.
precise aguardar, na maioria dos
casos , pelo término de alguma
solicitação de I/O.
Diversos processos são
mantidos na memória ao
mesmo tempo.
• Em um sistema de computação
Quando um processo em
execução tiver que entrar em
espera, o SO libera a CPU,
alocando-a a um outro processo.
relativamente simples:
• Um processo é executado até que
simples, a CPU permanece ociosa.
• Todo esse processo de espera é
desperdiçado
Conceitos Básicos
• O escalonamento é uma função
fundamental do SO.
• Quase todos os recursos do
computador são submetidos a um
processo de escalonamento antes
do uso.
• A CPU é naturalmente um dos
recursos primordiais do computador.
• Assim, seu escalonamento é
central para o projeto do SO.
Ciclos de Picos CPU - I/O
• O sucesso do escalonamento da
Segue-se um pico de I/O, então
outro pico de CPU, depois outro
pico de I/O e assim por diante
Em dado momento, o último
pico de CPU irá chegar ao fim
com uma solicitação do sistema
para encerrar a execução
e não com outro pico de I/O
CPU depende das seguintes
propriedades dos processos:
• A execução do processo consiste
em um ciclo de execução da CPU e
de espera de I/O.
• Os processos se alternam entre
estes dois estados.
• A execução do processo dá início a
um pico de CPU
Ciclos de Picos CPU - I/O
• As durações destes picos da CPU
tem sido extensivamente
mensuradas
• Variam bastante por processo e por
computador (medidas em
milisegundos)
• Dependendo se um processo faz
mais uso de CPU ou de I/O pode-se
selecionar um algoritmo de
escalonamento da CPU apropriado.
Escalonamento da CPU
• Sempre que a CPU se torna
ociosa, o SO deve solicitar um dos
processos existentes na fila pronta
para que seja executado.
A fila pronta não é
necessariamente uma fila firstin-first-out
Uma fila pronta por sua vez,
• A seleção é executada pelo
pode ser implementada como:
scheduler de curto prazo (ou
scheduler da CPU).
Uma fila FIFO
Uma fila de prioridades
• O scheduler escolhe dentre os
Uma árvore
processos na memória que estão
prontos para execução, e aloca a
CPU a um deles
ou simplemente uma lista
encadeada
Escalonamento com Preempção
• Conceito:
• Corresponde à
interrupção de um
processo que está em
execução, seguida da
alocação da CPU a um
outro processo, em
ambiente de
multiprogramação
Escalonamento com Preempção
• As decisões de escalonamento da
CPU podem ocorrer sob as quatro
seguintes circunstâncias:
Quando um processo
comuta do estado de
execução para o estado
de espera (ex.: requisição
de I/O)
Quando um processo
comuta do estado de
execução para o estado
de pronto (ex.: quando
ocorre uma interrupção)
Quando um processo
comuta do estado de
espera para o estado de
pronto (ex.: conclusão de
I/O)
Quando um processo
termina
Escalonamento com Preempção
• Nas circunstâncias 1 e 4, não há
Quando o scheduling ocorre
somente nas circunstâncias 1 e
4, dizemos que o esquema de
escalonamento é sem
preempção
Nos outros casos, o
escalonamento é com
preempção.
escolha em termos de
escalonamento.
• Um novo processo (se existir um na
fila pronta) deve ser selecionado
para execução
• Entretanto existe uma escolha, nas
circustâncias 2 e 3.
Escalonamento com Preempção
• Em caso do Scheduling, sem
preempção, uma vez que a CPU
tenha sido alocada a um processo,
este toma conta da CPU até liberá-la
• Ou porque chegou ao
término
• Ou porque comutou
para o estado de espera
• Este método de escalonamento é
utilizado pelos SO Windows e Apple.
Despachante
• Um outro componente envolvido
na função de escalonamento da CPU
é o despachante.
•
Esta função envolve:
• Comutação de contexto
• Comutação para modalidade
• O despachante é o módulo que
passa o controle da CPU ao processo
selecionado pelo escalonador de
curto prazo
de usuário
• Desvio para a localização
própria no programa do
usuário de modo a reiniciá-lo
Critérios de Escalonamento
• Ao escolher qual algoritmo usar
em uma situação particular,
devemos considerar as propriedades
dos diversos algoritmos.
Os critérios dizem respeito ao
seguinte:
Utilização da CPU: o intuito
é manter a CPU tão ocupada
quanto possível.
• Muitos critérios tem sido sugeridos
para comparar algoritmos de
escalonamento de CPU.
A utilização da CPU pode
variar de 0 a 100%.
Em um sistema real, ela pode
variar de 40% a 90%
Critérios de Escalonamento
• Throughput: número de
processos que se completam por
unidade de tempo.
• Para processos longos, esta taxa
pode ser de 1 processo por hora;
• Para transações curtas, o
throughput pode ser 10 processos
por segundo
Tempo de turnaround:
corresponde ao intervalo entre o
momento em que um processo é
submetido e o momento em que
ele completa toda a sua
execução.
Isso corresponde a soma dos
períodos de tempo gastos em
espera para ocupar memória,
em espera na fila pronta,
executando na CPU e realizando
I/O.
Critérios de Escalonamento
• Tempo de Espera: o algortimo de
escalonamento da CPU não afeta o
período de tempo durante o qual um
processo ocupa a CPU ou realiza I/O.
• ele influi somente no montante de
tempo que um processo gasta
esperando na fila pronta.
• O tempo de espera é a soma dos
períodos gastos esperando na fila
pronta.
Tempo de Resposta: intervalo
de tempo entre a submissão de
uma solicitação e o momento
em que a primeira resposta é
produzida.
Algoritmos de Escalonamento
• O escalonamento da CPU trata do
problema de decidir qual dos
processos na fila pronta deve ser
alocado a CPU.
• Para isso existem diversos
algoritmos de escalonamento.
Escalonamento FirstFirst-Come First
First--Served
• O algoritmo de escalonamento
First-Come First-Served (Primeiro
que chega, primeiro atendido) é o
mais simples .
Quando um processo entra na
fila pronta, seu PCB é conectado
à cauda da fila
Quando a CPU fica livre, ela é
• Com este esquema, o processo
que primeiro requisita a CPU é o
primeiro a ser alocado a CPU.
alocada ao processo na cabeça
da fila
O processo em execução é então
• A implementação da política de
FCFS é facilmente gerenciada com
uma fila FIFO.
removido da fila
Escalonamento MenorMenor-Job
Job--Primeiro
• Este algoritmo associa a cada
processo a duração do próximo pico
da CPU do último processo
• Quando a CPU está disponível, ela
é designada para o processo com o
menor próximo pico de CPU
• Se dois processos têm o mesmo
tempo de duração do próximo pico
de CPU, o escalonamento FCFS é
usado para resolver o impasse.
Um termo mais apropriado seria
o próximo pico de CPU mais
curto, porque o escalonamento
é realizado examinando-se o
tempo de duração do próximo
pico de CPU de um processo, e
não o seu tempo de duração
total.
Escalonamento por prioridades
• Uma prioridade é associada a cada
Quanto maior o pico da CPU,
processo e a CPU é alocada ao
processo com prioridade mais alta
menor a prioridade, e vice-versa.
Um problema significativo com
• Processos com igual prioridade são
algoritmos de escalonamento
por prioridades é o bloqueio
indefinido (ou inanição).
agendados para execução em ordem
FCFS
• Um algoritmo por prioridades ,
baseia-se na ideia onde a prioridade
é o inverso do próximo pico da CPU.
Um processo que esteja pronto
para executar mas não tenha a
posse da CPU pode ser
considerado bloqueado – em
espera pela CPU
Escalonamento por prioridades
• Um algoritmo de escalonamento
por prioridades pode deixar alguns
processos de baixa prioridade
esperando indefinidamente pela
CPU.
• Já em um sistema de computação
muito carregado, um fluxo estável
de processos com prioridades mais
altas pode levar a que um processo
de baixa prioridade jamais consiga
ocupar a CPU.
Geralmente uma das duas coisas
pode ocorrer.
Escalonamento RoundRound-Robin
• O algoritmo de escalonamneto
round-robin (RR) é projetado
especialmente para sistemas de
tempo compartilhado
Um quantum de tempo fica em
geral entre 10 ou 100
milisegundos.
A fila pronta é tratada como
• É semelhante ao escalonamento
FCFS, mas leva em conta a
preempção para realizar a
comutação de processos
• Uma unidade de tempo pequena
chamada quantum de tempo (ou
porção de tempo) é definida.
uma fila circular.
O escalonador da CPU circula a
fila pronta alocando a CPU a
cada processo, por um intervalo
de tempo de até 1 quantum de
tempo.
Como o SO gerencia o processador ?
• Em um sistema com duas ou mais
•
Os sistemas operacionais
assimétricos utilizam uma CPU
para suas próprias necessidades
e dividem os processos dos
aplicativos entre as outras CPUs.
•
Os sistemas operacionais
simétricos compartilham as
várias CPUs e equacionam a
demanda e a disponibilidade da
CPU, mesmo quando o sistema
operacional é o único aplicativo
em execução.
CPUs, o trabalho é dividido entre os
processadores.
• O sistema operacional deve
equacionar a demanda de cada
processo para as diferentes CPUs.
• Os sistemas operacionais neste
caso, classificam-se em dois tipos:
simétricos e assimétricos .
Como o SO gerencia o processador ?
• A CPU não é o único recurso
requisitado mesmo quando somente
o sistema operacional está sendo
executado.
• O gerenciamento da memória é um
passo crucial para que todos os
processos sejam executados de
maneira tranqüila.
Como o SO gerencia o processador ?
• Sistema Operacional Assimétrico
Sistema Operacional Simétrico
Exercícios
• Descreva cinco tipos diferentes de
processadores de última geração e
também:
• Velocidade
• Performance
• Como funcionam
• Como opera junto ao SO ?
Enviar por e-mail para:
[email protected]