Aula10-Gerencia-do-processador

Prévia do material em texto

Sistemas Operacionais 
 
GERÊNCIA DO PROCESSADOR 
MACHADO/MAIA: CAPÍTULO 08 
Prof. Pedro Luís Antonelli 
Anhanguera Educacional 
Gerenciamento do Processador 
A gerência do processador pode ser considerada a atividade mais 
importante de um Sistema Operacional. 
 
Geralmente temos 2 ou mais processos aptos a utilizar o 
processador para serem executados. 
 
Nesse instante, o sistema operacional deve decidir qual dos 
processos aptos, armazenados em uma fila, será escolhido para 
rodar primeiro. 
 
 
Gerenciamento do Processador 
Essa tarefa e a tomada de decisão é feita pelo escalonador de 
processos (parte do sistema operacional) através da implementação 
de alguns algoritmos de seleção, denominados algoritmos de 
escalonamento. 
 
 
Escalonador de processos 
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. 
 
Em outras palavras, o objetivo dos escalonadores é implementar 
uma política de escalonamento de processos. 
 
Escalonador de processos 
O sistema operacional possui um módulo responsável por efetuar a 
troca de contexto entre a execução de processos distintos, chamado 
de Dispatcher ( expeditor). 
 
Já o escalonador está relacionado com a implementação e aplicação 
das políticas de seleção adotadas. 
Objetivos do escalonamento 
1. Maximizar a utilização do processador ; 
 
2. Privilegiar aplicações que são críticas; 
 
3. Maximizar a produção do sistema ,com o maior número de 
processos executados por unidade de tempo; 
 
4. Minimizar o tempo de execução, ou seja, o tempo que um 
processo gasta desde a sua criação até seu término; 
 
Objetivos do escalonamento 
5. Minimizar o tempo de espera, ou seja, o tempo que um processo 
permance na lista de aptos ; 
 
6. Minimizar o tempo de resposta, ou seja, o tempo decorrido entre 
uma requisição e a sua realização. 
Tipos de escalonadores 
Existem 2 tipos de escalonadores: 
 
1. Não-preemptivo: escalonadores que permitem que os 
processos rodem até o fim de sua execução sem ser 
interrompidos por eventos externos; 
 
2. Preemptivo: escalonadores que são capazes de suspender 
processos que poderiam continuar executando. 
Tipos de escalonadores 
Para cada um desses tipos, os processos poderão utilizar o 
processador até que: 
 
- No caso do tipo 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. 
Tipos de escalonadores 
- No caso do tipo 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. 
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 
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 ) 
 
Algoritmo 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 aptos a executar. 
 
Funcionamento: 
 
1. Processos que se tornam aptos são inseridos no final da fila; 
 
2. Processo que está no início da fila é o próximo a executar; 
 
3. Processo executa até que: 
 
 a. Libere explicitamente o processador 
 b. Realize uma chamada de sistema (bloqueado) 
 c. Termine sua execução. 
Algoritmo escalonamento FIFO 
Não há preempção, ou seja, o próximo da fila só é atendido 
quando o atual tiver encerrado todas as suas operações. 
 
Algoritmo escalonamento FIFO 
Desvantagem:O tempo médio de espera na fila de execução 
depende a ordem: 
Ex. 
 a. Ordem A-B-C-D = (0 + 12 + 20 + 35 ) / 4 = 16.75 u.t. 
 
 b. Ordem D-A-B-C = (0 + 5 + 17 + 25 ) / 4 = 11.7 u.t. 
Algoritmo escalonamento SJF 
No algoritmo anterior (FIFO) os processos que levam menos tempo 
podem ser prejudicados se ficarem atrás dos que levam mais tempo. 
 
Neste caso, o tempo médio que um processo espera para processar 
pode ser muito grande. 
 
O algoritmo pode ser modificado de forma que estes (os menores) 
sejam processados antes, e com isto, o tempo de espera médio 
diminui. 
 
O Shortest Job First ou algoritmo do “Menor Processo Primeiro” 
busca resolver este problema. 
Algoritmo escalonamento SJF 
Para usar este algoritmo precisamos conhecer antecipadamente o 
tempo de execução de cada processo, o que é difícil. 
 
A idéia é alocar o processador para o menor job da fila. 
 
O fato é que o menor tempo médio é obtido quando se executa 
primeiro os processos de menor ciclo de processador (I/O bound). 
Algoritmo escalonamento Cooperativo 
Nos algoritmos anteriores, os processos não podiam ser 
preemptados por tempo máximo de processamento (timesharing). 
 
Com a evolução, os computadores passaram a ser multi-usuário ou 
multitarefa. Neste caso, uma maior interação com o usuário e uma 
melhor utilização da CPU pelos programas tornou-se necessária. 
 
O método cooperativo é uma forma de tornar isso possível. 
 
Neste caso, os processos cooperam uns com os outros, passando a 
CPU a um outro caso este seja necessário. 
 
Algoritmo escalonamento Cooperativo 
Uma forma de implementar este modelo é criando uma “fila ou caixa 
de mensagens”, onde informações sobre os eventos ocorridos são 
postadas. 
Os processos verificam continuamente a caixa de mensagens, 
retirando e processando as que são endereçadas a eles. 
Os processos ou eventos do sistema geram novas mensagens, que 
são colocadas no final da fila. 
 
Algoritmo escalonamento Cooperativo 
Se o processo perceber uma mensagem que não seja para ele, 
chama o programa adequado, passando assim a CPU ao próximo. 
 
Nas primeiras versões do Windows este sistema estava presente, e 
se chamava Multitarefa cooperativa! 
 
Algoritmo escalonamento RR 
O algoritmo anterior, apesar de cooperativo, não garantia a execução 
de todos os programas, já que eles não poderiam ser 
obrigatoriamente parados ( não preemptivos). 
 
Em sistemas de timesharing o tempo de CPU deve ser compartilhado, 
sendo dada uma parcela de tempo a cada programa (time-slice). 
 
Denominamos este intervalo de tempo de quantum. 
 
 
Algoritmo escalonamento RR 
Além disso, este algoritmo é similar ao algoritmo FIFO, pois também 
mantemos uma fila, agora circular, para armazenar os processos. 
 
 
 
 
 
 
 
 
 
 
Para a execução existe a necessidade de um relógio para delimitar as 
fatias de tempo. 
Algoritmo escalonamento RR 
O processo perde o processador quando: 
 
1. Libera explicitamente o processador; 
 
2. Realize uma chamada de sistema (bloqueado); 
 
3. Termina sua execução; 
 
4. Quando sua fatia de tempo é esgotada. 
Algoritmo escalonamento RR 
Problema 1: 
 
Dimensionar o quantum: 
 
1. Compromisso entre overhead e tempo de resposta em função do 
número de usuários; 
 
2. Compromisso entre tempo de chaveamento e tempo do ciclo de 
processador (quantum); 
 
Imagine que a cada 20 ms de processamento útil seja necessário 
gastar 5 ms com tarefas de troca de contexto para rodar processos 
de outro usuário, por exemplo. Com isso, 20% do tempo de 
processador será gasto com estes overheads. 
Algoritmo escalonamento RR 
Problema 1: 
 
Dimensionar o quantum: 
 
1. Compromisso entre overheade tempo de resposta em função do 
número de usuários; 
 
2. Compromisso entre tempo de chaveamento e tempo do ciclo de 
processador (quantum); 
 
Imagine que a cada 20 ms de processamento útil seja necessário 
gastar 5 ms com tarefas de troca de contexto para rodar processos 
de outro usuário, por exemplo. Com isso, 20% do tempo de 
processador será gasto com estes overheads. 
Algoritmo escalonamento RR 
 
Problema 2: 
 
Processos I/O bound são prejudicados 
 
1. Esperam da mesma forma que processos CPU bound porém 
muito provavelmente não utilizam todo o seu quantum; 
 
2. Solução: Estabelecer prioridades para os porcessos. 
Escalonamento por Prioridades 
Neste caso, cada processo tem uma prioridade associada (FIFO por 
prioridade). 
 
Quando um processo de maior prioridade entra na fila, ele passa na 
frente, como num banco, onde os idosos tem a preferência. 
 
A princípio, só existe preempção por prioridade, ou seja, os 
processos não saem da CPU por sua fatia de tempo ter acabado. 
 
Escalonamento por Prioridades 
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. 
 
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. 
Escalonamento por Prioridades 
1. Associar prioridades a processos I/O bound para compensar o 
tempo gasto em estado de espera (apto); 
 
2. Sempre que um processo de maior prioridade que o processo 
atualmente em execução entrar no estado apto deve ocorrer 
uma preempção; 
 
3. Escalonamento com prioridades é inerente a preempção; 
 
4. É possível haver prioridade não-preemptiva; 
 
5. Escalonador deve sempre selecionar o processo de mais alta 
prioridade. 
 
Escalonamento por Prioridades 
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. 
 
Ex.: 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 
Escalonamento por Prioridades 
Problemas com prioridades 
 
1. Com prioridades um processo de baixa prioridade pode não 
executar (starvation); 
 
2. Um processo que durante sua execução troca de comportamento 
(CPU bound a I/O bound) pode ficar mal classificado a nível de 
prioridades e ser penalizado; 
 
3. Solução: Múltiplas filas de prioridades 
Escalonamento por Múltiplas Filas de Prioridades 
Neste modelo temos diversas filas de processos no estado pronto, cada qual com 
prioridades específicas e com sua própria política de escalonamento (FIFO, SJF, RR) 
. 
Escalonamento por Múltiplas Filas de Prioridades 
com Realimentação 
Este modelo é similar ao modelo de múltiplas Filas de Prioridades, porém os 
processos podem trocar de fila durante seu processamento. 
 
Um mecanismo adaptativo é implementado de forma a avaliar o comportamento 
do processo e alterar sua fila. 
 
Por exemplo, toda vez que um processo é “preemptado” por tempo ele muda de 
fila, diminuindo sua prioridade e aumentando sua fatia de tempo (time-slice). 
 
Características: 
 
1. Baseado em prioridades dinâmicas; 
 
2. Em função do tempo de uso da CPU a prioridade do processo aumenta e diminui; 
 
3. Sistema de envelhecimento (aging) evita postergação indefinida. 
Escalonamento por Múltiplas Filas de Prioridades 
com Realimentação 
BIBLIOGRAFIA 
• MACHADO, F. B. & MAIA, L. P., Arquitetura de Sistemas Operacionais, 4 Edição, 
São Paulo, LTC, 2007. 
 
• TANENBAUM, A. S. Sistemas Operacionais Modernos: 2ª edição, São Paulo, 
editora Prentice Hall, 2003. 
 
• SILBERSCHATZ, A. Sistemas Operacionais – Conceitos: São Paulo, editora LTC, 
2004.