Sistemas Operacionais aula 07

Prévia do material em texto

CCT0011 – Sistemas Operacionais 
Aula 07 – Gerência do Processador 
Professor Ricardo Bernardo 
Sistemas Operacionais 
Conteúdo da Aula 
Breve Revisão Última Aula 
 
Fundamentos 
Critérios de Escalonamento 
FCFS 
Prioridade 
SJF 
Round Robin 
Sumário 
• Introdução 
• Funções Básicas 
• Critérios de escalonamento 
• Escalonamentos não-preemptivos e 
preemptivos 
• Escalonamento FIFO 
• Escalonamento SJF 
• Escalonamento cooperativo 
• Escalonamento circular 
• Escalonamento por prioridades 
• Escalonamento circular com prioridades 
• Escalonamento por múltiplas filas 
• Escalonamento por múltiplas filas com 
realimentação 
• Política de Escalonamento em Sistemas de 
Tempo Compartilhado 
• Política de Escalonamento em Sistemas de 
Tempo Real 
Sistemas Operacionais 
Introdução 
 Nos sistemas multiprogramáveis, múltiplos processos podem permanecer na 
memória principal compartilhando o uso da CPU. Neste modelo a gerência do 
processador tornou-se uma das atividades mais importantes em um sistema 
operacional. 
 
 Diversos processos podem estar no estado de pronto, desta forma, critérios devem 
ser estabelecidos para determinar qual processo será o escolhido para fazer uso do 
processador. 
 
 Os critérios utilizados para esta seleção compõem a chamada política de 
escalonamento, que é a base da gerência do processador e da multiprogramação em 
um sistema operacional. 
 
Sistemas Operacionais 
Introdução 
Estado de
Espera
Estado de
Execução
Estado de
Pronto
Escalonam
ento Funções básicas do escalonamento 
 
• Manter a CPU ocupada a maior parte do tempo 
• Balancear o uso da CPU entre processos 
• Privilegiar a execução de aplicações críticas 
• Maximizar o throughput do sistema 
• Oferecer tempos de resposta razoáveis para usuários interativos 
 
Sistemas Operacionais 
Funções Básicas 
 Cada SO possui sua política de escalonamento adequada ao seu propósito e às suas características. 
 
Escalonador (scheduler) Rotina do sistema operacional responsável por implementar os critérios de 
escalonamento. 
O escalonador é a entidade do sistema operacional responsável por selecionar um processo apto a 
executar no processador e dividir o tempo do processador de forma justa entre os processos que estão 
aptos. 
 
Dispatcher 
Responsável pela troca de contexto dos processos após o escalonador determinar qual processo deve 
fazer uso do processador. 
 
Sistemas Operacionais 
Funções Básicas 
Ambientes que implementam apenas processos: 
• O escalonamento é realizado com base nos processos prontos para execução. 
 
Em ambientes que implementam threads: 
• O escalonamento é realizado considerando os threads em estado de pronto, independentemente do 
processo. 
• Processos – unidades de alocação de recursos 
• Threads – unidades de escalonamento 
Sistemas Operacionais 
Objetivos do Escalonamento 
 Maximizar a utilização do processador ; 
 
 Privilegiar aplicações que são críticas; 
 
 Maximizar a produção do sistema ,com o maior número de processos executados por unidade de 
tempo; 
 
 Minimizar o tempo de execução, ou seja, o tempo que um processo gasta desde a sua criação até seu 
 término; 
 
 Minimizar o tempo de espera, ou seja, o tempo que um processo permanece na lista de prontos ; 
 
 Minimizar o tempo de resposta, ou seja, o tempo decorrido entre uma requisição e a sua realização. 
 
 
 
Sistemas Operacionais 
Critérios de Escalonamento 
 Critérios que devem ser considerados em uma politica de escalonamento: 
 
 Utilização do Processador: 30% carga baixa, 90 % sistema carregado; 
 Throughput: Número de processos executados em um determinado intervalo de tempo; 
 Tempo de Processador/Tempo de CPU: Tempo que um processo leva em estado de execução durante 
o seu processamento; 
 Tempo de Espera: Tempo total que um processo permanece na fila de espera; 
 Tempo de Turnaround: Tempo desde a criação até o término de um processo (tempo total); 
 Tempo de Resposta: Tempo decorrido entre uma requisição ao sistema ou à aplicação e o instante 
em que a resposta é exibida; 
Sistemas Operacionais 
Considerações 
 A política de escalonamento varia de acordo com o propósito do sistema operacional (Sistemas de 
Tempo Real x Sistemas de Tempo Compartilhado x Sistemas Batch); 
 
Latência do dispatcher: tempo gasto para a troca de processos; 
 
Em ambientes multithread, a unidade escalonada é a thread (somente as que estiverem no estado 
“pronto”); 
 
 
Sistemas Operacionais 
Tipos de Escalonadores 
Escalonamentos 
 
 Não preemptivo  Escalonadores que permitem que os processos rodem até o fim de sua 
execução sem serem interrompidos por eventos externos; 
 
 
 Preemptivo  Escalonadores que são capazes de suspender processos que poderiam continuar 
executando. 
 
 
Sistemas Operacionais 
Tipos de Escalonadores 
Os processos poderão utilizar a CPU até os seguintes casos ocorrem: 
 
Não preemptivo 
1. Término de execução do processo; 
2. Execução de uma requisição de entrada/saída ou sincronização; 
3. Liberação voluntária do processador a outro processo. 
 
Preemptivo 
1. Término de execução do processo; 
2. Execução de uma requisição de entrada/saída ou sincronização; 
3. Liberação voluntária do processador a outro processo; 
4. Interrupção de relógio; 
5. Processo de mais alta prioridade esteja pronto para executar. 
 
Sistemas Operacionais 
Algoritmos de Escalonamento 
 
 Diversos mecanismos (algoritmos) foram sendo desenvolvidos ao longo dos anos. 
 
 Cada um possui uma vantagem ou desvantagem, mas os escolhidos são aqueles que 
oferecem um bom desempenho, ou seja, evitam ao máximo o tempo de espera e 
mantém os recursos ocupados em ambientes de processos heterogêneos 
 
Sistemas Operacionais 
Algoritmos de Escalonamento 
Alguns algoritmos de escalonamento: 
 
Algoritmos não preemptivos: 
1. FIFO 
2. SJF 
3. Cooperativo 
 
Algoritmos preemptivos: 
1. Round Robin (circular) 
2. Múltiplas filas (e suas variações ) 
Sistemas Operacionais 
Algoritmo de Escalonamento FIFO 
 
 O algoritmo FIFO (First In First Out) mais simples de implementar, onde o processador possui uma fila 
associada para armazenar os processos que estão prontos a executar. 
 
Funcionamento: 
 Processos que se tornam aptos são inseridos no final da fila; 
 Processo que está no início da fila é o próximo a executar; 
 Processo executa até que: 
 
• Libere explicitamente o processador 
• Realize uma chamada de sistema (bloqueado) 
• Termine sua execução. 
Sistemas Operacionais 
Algoritmo de Escalonamento FIFO 
Escalonamento FIFO também conhecido como First Come First Served (FCFS) 
 
 
 
 
 
 
 
 
 
Não se preocupa em melhorar o tempo médio de espera dos processos. 
Não há preempção. 
UCP
Estado de
Criação
Estado de
Espera
Fila dos processos no estado de Pronto
Estado de
Término
Sistemas Operacionais 
Algoritmo de Escalonamento FIFO 
Processo A
Processo B
Processo C
10 14 17
Processo A
Processo B
Processo C
4 7 17
u.t.
u.t.
Processo
Tempo de
processador
(u.t.)
A
B
C
10
4
3
Processos CPU-Bound levam vantagens 
 
 
Processos A, B e C na fila de prontos. 
 
Tempo médio de espera dos três 
processos: 
 
a) (0 + 10 + 14) / 3 = 8u.t 
 
b) (7 + 0 + 4) / 3 = 3,7 u.t. 
Sistemas Operacionais 
A
rq
u
it
et
u
ra
 d
e 
S
is
te
m
as
 O
p
er
ac
io
n
ai
s 
–
 M
ac
h
ad
o
/Mai
a 
Algoritmo de Escalonamento SJF 
Processo A
Processo B
Processo C
3 7 17 u.t.
 Shortest Job First (SJF) também conhecido como 
Shortest Process Next (SPN). 
 Seleciona o processo que tiver o menor tempo 
de processador ainda por executar. 
 
 Para utilizar este algoritmo o tempo de 
execução de cada processo precisar ser 
previamente conhecido. 
 Toda vez que um processo na fila de estado 
de pronto tem um tempo de processador 
estimado menor do que o processo em 
execução, ocorre uma preempção. 
 
Tempo médio de espera dos três processos. 
(7 + 3 + 0) / 3 = 3.3 u.t. 
Sistemas Operacionais 
Algoritmo de Escalonamento SJF 
Sua vantagem sobre o escalonamento FIFO está na redução do tempo médio de turnaround dos 
processos. 
 
Possibilidade de ocorrer starvation para processos com tempo de processamento muito longo ou 
processos do tipo CPU-bound. 
 
Uma implementação do escalonamento SJF com preempção é conhecida como escalonamento Shortest 
Remaining Time (SRT). 
Nesta política, toda vez que um processo no estado de pronto tem um tempo de processador estimado 
menor do que o processo em execução, o sistema realiza a preempção. 
Sistemas Operacionais 
Escalonamento Cooperativo 
 
 
 Implementação que busca aumentar o grau de multiprogramação em políticas de escalonamento que 
não possuem mecanismos de preempção, como FIFO e SJF não preemptivo. 
 
 A principal característica do escalonamento cooperativo está no fato de a liberação do processador 
ser uma tarefa realizada exclusivamente pelo processo em execução, que de uma maneira cooperativa 
libera a CPU para outro processo. 
Sistemas Operacionais 
Escalonamento Cooperativo 
 
 
Processo em execução pode liberar voluntariamente a CPU, retornando para à fila de pronto; 
 
• Uma forma de implementar este modelo é criando uma “fila ou caixa de mensagens”, onde informações 
sobre os eventos ocorridos são postadas. 
• Verifica a fila de mensagens periodicamente 
• Podem ocorrer problemas 
 
Exemplo: primeiros sistemas MS-Windows 
Sistemas Operacionais 
Preempção por tempo
UCP
Estado de
Criação
Estado de
Espera
Fila dos processos no estado de Pronto
Estado de
Término
Escalonamento Circular 
 Quando um processo passa para o estado de execução existe um tempo-limite para o uso contínuo 
do processador (round robin) 
 Em sistemas de time-sharing o tempo de CPU deve ser compartilhado, sendo dada uma parcela de 
tempo a cada programa (time-slice). Denominamos de quantum este intervalo de tempo. 
 Esse tipo de escalonamento é também conhecido como preempção circular. 
Sistemas Operacionais 
Escalonamento Circular 
 Esse algoritmo é bastante semelhante ao 
FIFO. 
 
 O valor da fatia de tempo depende da 
arquitetura de cada sistema operacional e, em 
geral varia entre 10 e 100 milissegundos. 
 
 Processos CPU-Bound levam vantagens, pois 
tendem a utilizar por completo a fatia de tempo. 
 
 
Processo A
Processo B
Processo C
2 4 17 u.t.6 8 10 11
Sistemas Operacionais 
Escalonamento Circular Virtual 
 Os processos que saem da fila auxiliar possuem preferência no escalonamento em relação à fila de 
pronto, e o escalonador só seleciona a fila de pronto quando a fila auxiliar estiver vazia. 
 Quando um processo é selecionado a partir da fila auxiliar sua fatia de tempo é calculada como sendo 
o valor da fatia de tempo do sistema menos o tempo de processador que o processo utilizou da última 
vez em que foi escalonado. Preempção por tempo
UCP
Estado de
Criação
Fila dos processos no estado de Pronto
Estado de
Término
Estado de
Espera
Fila auxiliar
Sistemas Operacionais 
Escalonamento Circular Virtual 
Problema 1: 
Dimensionar o quantum: 
 Compromisso entre overhead e tempo de resposta em função do número de usuários; 
 Compromisso entre tempo de chaveamento e tempo do ciclo de processador (quantum); 
 
 Exemplo: Para cada 20 ms de processamento útil que seja necessário gastar 5 ms com tarefas de 
troca de contexto, 20% do tempo de processador está sendo gasto com overheads. 
 
Problema 2: 
Processos I/O-bound são prejudicados : 
 Esperam da mesma forma que processos CPU-bound porém muito provavelmente não utilizam 
todo o seu quantum; 
 Solução: Estabelecer prioridades para os processos. 
. 
 
Sistemas Operacionais 
Escalonamento por Prioridade 
 
 Este algoritmo é recomendado para sistemas de processamento em tempo real, onde determinadas 
atividades ou processos tem prioridade sobre os demais e devem ser tratados no momento em que 
ocorrem. 
 
 O processo com maior prioridade no estado de pronto é sempre escolhido para execução. 
 
 Um problema que surge é o dos processos com menor prioridade não serem nunca processados se 
existirem processos de maior prioridade. Neste caso, o processo “morre de fome” (starvation). 
 
 Em alguns casos o Sistema Operacional pode mudar a prioridade dos processos, minimizando este 
problema. 
Sistemas Operacionais 
UCP
Estado de
Término
Filas dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Prioridade Pn
Estado de
Criação
Estado de
Espera
Preempção por prioridade
Escalonamento por Prioridade 
 Neste escalonamento não existe o conceito de 
fatia de tempo. 
 Quando um processo de maior prioridade entra 
na fila, ele passa na frente. 
 A princípio só existe preempção por prioridade. 
 
Sistemas Operacionais 
Escalonamento por Prioridade 
Exemplo 
Este tipo de escalonamento é muito útil em sistemas de tempo real. 
 
Processo A
Processo B
Processo C
3 13 17 u.t.
Processo
Tempo de
processador
(u.t.)
A
B
C
10
4
3
Prioridade
2
1
3
Sistemas Operacionais 
Escalonamento por Prioridade 
 Prioridade estática versus dinâmica 
 
 Prioridade estática: Um processo é criado com uma determinada prioridade e esta prioridade é 
mantida durante todo o tempo de vida do processo; 
 
 Prioridade dinâmica: A prioridade do processo é ajustada de acordo com o estado de execução do 
processo e/ou do sistema. 
 
Exemplo: Ajustar a prioridade em função da fração do quantum que foi realmente utilizada pelo 
processo q = 100 ms. 
Processo A utilizou 2ms !nova prioridade = 1/0.02 = 50 
Processo B utilizou 50ms !nova prioridade = 1/0.5 = 2 
 
Sistemas Operacionais UCP
Estado de
Término
Fila dos processos no estado de Pronto
Prioridade P1
Prioridade P2
Prioridade Pn
Estado de
Criação
Estado de
Espera
Preempção por tempo ou prioridade
Escalonamento Circular com Prioridade 
 
 Implementa o conceito de fatia de tempo e de 
prioridade de execução associada a cada processo. 
 
 
 
 Neste tipo de escalonamento, um processo 
permanece no estado de execução até que termine 
seu processamento, voluntariamente passe o estado 
de espera ou sofra preempção por tempo ou 
prioridade. 
 
 Principal vantagem é o melhor balanceamento 
no uso da CPU. 
Sistemas Operacionais 
UCP
Fila de processos do sistema
Fila de processos interativos
Fila de processos batch
Maior
prioridade
Menor
prioridade
Escalonamento por Múltiplas Filas 
 Existem diversas filas no estado de pronto, cada qual com uma prioridade específica. 
 Os processos são associados às filas em função de características próprias, como importância para a 
aplicação, tipo de processamento ou área de memória necessária. 
 A principal vantagem de múltiplas filas é a possibilidade da convivência de mecanismos de 
escalonamento distintos em um mesmo sistema operacional. 
 Neste mecanismo, o processo não 
possui prioridade, ficando esta 
característica associada à fila.O sistema operacional só pode 
escalonar processo de uma 
determinada fila caso todas as outras 
filas de maior prioridade estejam 
vazias. 
Sistemas Operacionais 
UCP
Fila 1 (FIFO Adaptado)
Preempção por tempo
Fila 2 (FIFO Adaptado)
Preempção por tempo
Fila 3 (FIFO Adaptado)
Preempção por tempo
Fila n (Circular)
Preempção por tempo
M
en
o
r
Pr
io
ri
d
a
d
e
M
a
io
r
Pr
io
ri
d
a
d
e
M
a
io
r 
fa
ti
a
d
e 
te
m
p
o
M
en
o
r 
fa
ti
a
d
e
 t
em
p
o
Escalonamento por Múltiplas Filas com Realimentação 
 É semelhante ao escalonamento por múltiplas 
filas, porém os processos podem trocar de fila 
durante seu processamento. 
 
 Sua vantagem é permitir ao sistema operacional 
identificar dinamicamente o comportamento de 
cada processo, direcionando-o para fila com 
prioridade de execução e mecanismo de 
escalonamento mais adequado ao longo de seu 
processamento. 
Sistemas Operacionais 
Políticas em Sistemas de Tempo Compartilhado 
 Em geral caracterizam-se pelo processamento interativo , onde usuários interagem 
com as aplicações exigindo tempos de resposta baixos. 
 A escolha de uma política para atingir este propósito deve levar em consideração o 
compartilhamento dos recursos de forma equitativa para possibilitar o uso balanceado 
da CPU entre processos. 
Sistemas Operacionais 
Políticas em Sistemas de Tempo Real 
 
 
• Tempos de respostas rígidos 
• Aplicações de controle de processos 
• Utiliza prioridades estáticas 
• Não utiliza fatias de tempo 
 
Sistemas Operacionais 
Dúvidas