Gerência de Processador e Escalonamento

Prévia do material em texto

GERÊNCIA DE PROCESSADOR 
Considerada a parte principal de um Sistema operacional. É nela que são definidos os critérios para 
mudar os estados dos diversos processos que estão aguardando execução em uma máquina. O 
procedimento de seleção de qual processo passa a qual estado, dentre os possíveis processos que 
esperam nas diversas filas é chamado escalonamento. 
CONCEITOS BÁSICOS 
• Multiprogramação: vários processos estão na memória ao mesmo tempo. Quando um 
processo espera, o sistema operacional. coloca outro processo para executar. 
• Burst ciclo (CPU – E/S): a execução do processo consiste de um ciclo de execução de 
instruções pela CPU e espera por E/S. A execução começa com um CPU burst, seguido de um 
E/S burst e novamente um CPU burst. 
Exemplo: 
 
Load 
Store CPU 
Add burst 
Read from file 
Wait por E/S E/S burst 
Store 
increment CPU burst 
write to file 
wait por E/S E/S burst 
 
 
Escalonamento preemptivo: o escalonamento da CPU é preemptivo quando o sistema operacional 
pode interromper um processo em execução para que outro processo utilize o processador. 
Naturalmente a interrupção depende de hardware especial (um relógio externo, por exemplo). 
Despachador (Dispatcher) ou escalador de curto prazo: é uma rotina encarregada de escolher qual 
dos processos no estado de pronto para rodar deve receber a CPU, de acordo com suas prioridades. 
Ele se utiliza de algumas estruturas de dados que implementam filas de processos, através da 
manipulação de seus BCPs. São elas: 
1 - A FILA DE PRONTOS ou Fila da CPU: que é uma lista ordenada, de acordo com as prioridades de 
cada processo, de BCPs dos processos no estado de Pronto. 
2 - A FILA DE CONDIÇÃO: Dos BCPs de processos suspensos (ou BLOQUEADOS), esperando por 
alguma condição. Por exemplo, a espera de uma operação de E/S, a espera de memória, etc. 
Além de manipular essas filas, ele também opera com o relógio de intervalos, estabelecendo, a cada 
novo intervalo de tempo, qual o valor da fatia de tempo destinada ao processo escolhido para ganhar a 
CPU. A transferência do controle da CPU ao processo escolhido é feita através da reposição do 
contexto desse processo via seu BCP e uma instrução do tipo IRET. 
As rotinas de tratamento de interrupções realizam a segunda função do núcleo, sendo implementadas 
uma para cada tipo de interrupção que possa ocorrer no sistema. 
O módulo de sincronização implementa um par de rotinas do tipo WAIT e SIGNAL e é utilizado para 
estabelecer o sincronismo de processos no acesso aos recursos do sistema. Esse módulo também 
manipula filas de processos. 
 
São as seguintes as operações realizadas sobre os processos pelo sistema operacional. para cada 
uma das principais ocorrências: 
➢ INTERRUPÇÃO de FIM DE I/O: 
- salva contexto do processo EXECUTANDO; 
- se entrada: transfere dado para endereço adequado; 
- retira o primeiro BCP da fila de condição do dispositivo e o insere na fila de prontos; 
- faz estado do dispositivo = LIVRE; e 
- chama DESPACHADOR. 
➢ INTERRUPÇÃO de RELÓGIO: 
- salva contexto do processo EXECUTANDO; 
- retira BCP do topo da fila dos PRONTOS; 
- insere BCP no final da fila; e 
- chama DESPACHADOR. 
➢ INTERRUPÇÃO de ERRO DE PROGRAMA (TRAP): 
- remove BCP do topo da fila de PRONTOS; 
- insere-o na fila dos ACABADOS; e 
- dispara rotina de Fim de Processo. 
➢ INTERRUPÇÃO POR ERRO DE HARDWARE: 
- depende do erro, se for localizado e recuperável, aborta o processo corrente e chama o processo de 
recuperação, chama o despachador senão, Halt (para o processador). 
➢ DESPACHADOR: 
- zera registro de intervalo de tempo; 
- busca o primeiro BCP da fila dos PRONTOS; 
- coloca-o como EXECUTANDO; 
- restabelece registrador de intervalo de tempo; 
- restabelece contexto do processo; 
- restabelece interrupções; 
- restabelece CI; e 
- faz um IRET (salta para o processo). 
CRITÉRIOS DE ESCALONAMENTO 
Alguns critérios devem ser observados na avaliação dos algoritmos de escalonamento: 
• Utilização da CPU: mede o percentual de utilização da CPU, que deve ser o maior possível. 
• Throughput: numero de processos que foram completados por unidade de tempo 
• Tempo turnaround: é a soma dos tempos gastos pelo processo esperando para obter a CPU 
(fila de prontos), esperando por memória, executando na CPU e esperando por E/S. 
• Tempo de espera: soma dos períodos de tempo gastos esperando na fila de prontos. 
• Tempo de resposta: tempo decorrido entre a submissão de um processo até que a primeira 
resposta seja obtida. Não é considerado o tempo gasto com a efetiva saída do pedido, uma 
vez que este depende da velocidade do dispositivo de saída. 
 
 
POLÍTICAS DE ESCALONAMENTO 
ESCALONAMENTO FIRST COME FIRST SERVED 
É implementado com uma fila FIFO, onde o primeiro que chega é o primeiro a ser executado. 
Exemplo: 
 
Processo P1 P2 P3 
Tempo burst 24 3 3 
 
Conside que os processos chegaram na ordem P1, P2, P3 e foram executados em FCFS, temos o 
seguinte Gant Chart: 
 
Tempo de espera por processo: 
Para P1: 0 
Para P2: 24 
Para P3: 27 Média = (0+ 24 + 27) / 3 = 17 unidades de tempo 
Se a ordem fosse P2, P3 e P1, teríamos: 
 
Tempo de espera por processo: 
Para P2: 0 
Para P3: 3 
Para P1: 6 Média = (0+ 3 + 6) / 3 = 3 unidades de tempo 
O algoritmo FCFS não é preemptivo. Uma vez que a CPU seja alocada para um processo, ele fica com 
ela até o final ou até que peça alguma operação de E/S. 
Para sistemas de tempo compartilhado, este algoritmo não se aplica. 
ESCALONAMENTO SHORTEST JOB FIRST 
Este algoritmo associa a cada processo o tamanho do próximo CPU burst (veja bem, não o tamanho 
de todo o processamento). O processo escolhido é o que tem o menor próximo ciclo de CPU burst. Se 
dois processos coincidem, é escolhido o que chegou primeiro. 
Exemplo: 
 
Processo P1 P2 P3 P4 
Tempo burst 6 8 7 3 
Veja o Gant Chart: 
 
Tempo de espera por processo: 
Para P4: 0 
Para P1: 3 
Para P3: 9 
Para P2: 16 Média = (0+ 3 + 9 + 16) / 4 = 7 unidades de tempo 
Pelo algoritmo FCFS o tempo médio seria 10,25. Entretanto, embora este algoritmo seja ótimo, não é 
possível implementá-lo integralmente, já que não existe maneira de conhecer o tamanho do próximo 
ciclo CPU burst. Pode-se apenas estimá-lo. 
ESCALONAMENTO POR PRIORIDADE 
A cada processo é associada uma prioridade e a CPU é alocada para o processo com a mais alta 
prioridade. Processos com prioridades iguais são escalados segundo a política FCFS. 
Exemplo: 
Processo P1 P2 P3 P4 P5 
Tempo burst 10 1 2 1 5 
Prioridade 3 1 3 4 2 
Veja o Gant Chart: 
 
 
Média do tempo de espera: (0 + 1 + 6 + 16 + 18) / 5 = 8,2 unidades de tempo. 
Um método para prevenir “starvation” é o “aging”. Consiste em ir aumentando gradualmente a 
prioridade de um processo, à medida que ele fica esperando. 
Prioridade estática: não muda durante a vida do processo. 
Prioridade dinâmica: prioridade ajustada de acordo com o tipo de processamento e/ou carga do 
sistema. 
ESCALONAMENTO ROUND ROBIN OU CIRCULAR 
Especialmente útil para sistemas de tempo compartilhado. Cada processo ganha um tempo limite para 
sua execução. Após esse tempo ele é interrompido e colocado no fim da fila de prontos. Este tempo é 
atachado de fatia de tempo, “time-slice” ou quantum. Geralmente se situa entre 100 e 300 ms. O tempo 
médio de espera é geralmente longo. O desempenho do algoritmo depende bastante da escolha do 
quantum. Se for grande, se parecerá com a política FCFS. Se for muito pequeno, o Round Robin é 
chamado “Processor Sharing” pois parece, do ponto de vista dos processos, que cada um do N 
processos “possui” uma CPU com velocidade 1/N do processador real. 
Exemplo: 
Processo P1 P2 P3 
Tempo execução 24 3 3RR=4 
Gant Chart: 
P1 P2 P3 P1 P1 P1 P1 P1 
0 4 7 10 14 18 22 26 30 
P1=(0+10+14+18+22+26)/6 =15 
Média do tempo de espera: (15 + 4 + 7 ) / 3 = 8,66 unidades de tempo. 
 
ESCALONAMENTO POR MÚLTIPLAS FILAS 
Implementa diversas filas de processos no estado de pronto, uma para cada prioridade. Os processos 
devem ser classificados previamente em função do tipo de escalonamento para poderem ser 
corretamente alocados. Cada fila separada tem seu próprio algoritmo de escalonamento,. 
Ex: fila de forground (interativos) usa escalonamento Round Robin, enquanto os processos da fila de 
background (batch) utilizam algoritmo FCFS. 
 
Processos do sistema 
Processos interativos 
Processos batch 
 
ESCALONAMENTO POR MÚLTIPLAS FILAS COM REALIMENTAÇÃO 
No caso de processos que alterem seu comportamento no decorrer do tempo, o esquema anterior é 
falho, porque não permite a movimentação do processo entre as filas. Este escalonamento permite a 
troca entre as filas. 
O sistema tenta identificar dinamicamente o comportamento de cada processo, ajustando suas 
prioridades de execução e mecanismos de escalonamento. Este esquema é dito mecanismo 
adaptativo. Exemplo: 
 
 
 
 
 
Quando o processo é criado, é posto na fila 1 (de mais alta prioridade). Se ele esgota seu quantum, é 
posto uma fila abaixo e recebe um novo quantum (maior). Se também esgota esse quantum, vai 
descendo sucessivamente de fila, até atingir a de menor prioridade, onde o escalonamento é circular. 
Neste esquema, os processos “I/O bound” ficam por mais tempo nas filas de alta prioridade, enquanto 
os “CPU bound” gastam seu tempo e passam para filas de menor prioridade. Ou seja, os processos 
evoluem bem, independentemente da sua natureza (I/O bound ou CPU bound). 
ESCALONAMENTO COM MÚLTIPLOS PROCESSADORES 
Este escalonamento é usado quando existem vários processadores. 
Compartilhamento de carga: fornece uma fila separada para cada processador. 
 Problema: um processador pode estar ocioso enquanto o outro está sobrecarregado 
 Solução: colocar uma só fila de prontos e deixar o despachador decidir na hora da execução. 
Uma maneira de escalonar é o processador ser auto escalonável, ou seja, cada processador vai à fila e 
seleciona um processo. Cuidados a serem tomados: não permitir que um processo seja escolhido por 
mais de um processador; não permitir que um processo não seja escolhido por nenhum processador 
Prioridade 
: 
Outra maneira é usar um processador como escalonador de processos para os outros processadores, 
criando uma estrutura mestre-escravo. 
Outra maneira ainda é o multiprocessamento assimétrico, onde um processador é responsável por 
todas as decisões de escalonamento, processamento de E/S, etc. Os demais processadores só 
executam código do usuário. 
ESCALONAMENTO DE TEMPO REAL 
Para sistemas de tempo real, é importante definir alguns conceitos que são críticos: 
Tempo de chaveamento: é o tempo gasto pelo sistema para chavear o processamento entre dois 
processos independentes, ativos e de prioridade igual. Ocorre, por exemplo, no chaveamento por “time 
slice”. 
Tempo de preempção: é o tempo que um processo de maior prioridade leva para tomar o controle de 
um de menor prioridade por ocasião da ocorrência de um determinado evento externo de interrupção. 
Tempo de latência de interrupção: é o tempo entre o recebimento de um pedido de interrupção pela 
CPU e a execução da primeira instrução da rotina de serviço da interrupção. 
Vamos analisar primeiramente as soluções para sistemas de tempo real “hard”. Nestes sistemas, como 
as tarefas têm que terminar em tempos definidos, o sistema operacional. tem que admitir o processo 
somente quando ele poderá terminar na hora certa. Caso contrário, o sistema operacional. deve rejeitar 
o pedido como impossível. Isto é conhecido como “Reserva de recurso”. Para ter tempos garantidos, 
recursos tais como memória virtual e armazenamento em disco, estão descartados. Normalmente este 
tipo de sistema possui hardware específico. 
Para sistema de tempo real soft: neste tipo de sistema, os processos de tempo real devem ter a mais 
alta prioridade. Essa prioridade não deve ser degradada com o tempo. Para esses processos não deve 
haver time sharing. O tempo de latência deve ser pequeno para que o processo possa começar a 
executar o mais rapidamente possível. 
Em todos os casos, o tempo de chaveamento e de latência devem ser pequenos, o tempo de 
preempção deve ser adequado aos propósitos do sistema e em alguns casos podem existir primitivas 
de bloqueio da preempção, 
 
Siglas 
BCP ou bloco de controle --- Cada processo é representado por um descritor (BCP), que é uma área 
de memória contendo todas as informações relevantes do processo. O descritor contém a identificação 
do processo e uma indicação do estado corrente do processo (em execução; pronto para ser 
executado; bloqueado). 
IRET - Instruções do tipo IRET retornam o sistema ao estado Usuário, restabelecendo o contexto do 
programa que pediu o SVC, ou chamando o módulo escalador de processos do Núcleo.