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 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 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.