Faculdade de Filosofia Ciências e Letras de CaruaruLuiz Filipe de Sousa Pinto – 3° Período ADSSistemas Operacionais – Douglas Brito Damalio

Escalonamento

Definição:

O escalonamento é a chave da multiprogramação, por que determina que processo deverá usar o processador em um determinado momento. A forma com que se dá o escalonamento é, em grande parte, responsável pela produtividade e eficiência de um sistema computacional. Mais que um simples mecanismo, o escalonamento deve representar uma política de tratamento dos processos que permita obter os melhores resultados possíveis num sistema.

Técnicas de Escalonamento:

1) Nível de escalonamento:

Existem três níveis distintos de escalonamento em um sistema computacional quando se considera a frequência e a complexidade das operações envolvidas:

Escalonamento de Alto Nível: corresponde a admissão de processos, isto é, a determinação de quais tarefas passarão a competir pelos recursos do sistema. Uma vez admitidas as tarefas se transformam em processos. Correspondem as rotinas de alto nível oferecidas pelas APIs do sistema operacional.

Escalonamento de Nível Intermediário: corresponde a determinação de quais processos existentes competirão pelo uso da CPU (processos ativos). Este nível de escalonamento é responsável por administrar a carga do sistema, utilizando-se de primitivas de suspensão (suspend) e ativação (resume ou activate). Correspondem a rotinas internas do sistema operacional.

Escalonamento de Baixo Nível: rotinas que determinam qual processo, dentre os processos ativos, será o próximo processo que efetivamente utilizará a CPU. Essas tarefas são executadas são dispatcher, usualmente uma rotina escrita diretamente em linguagem de máquina que se encontra permanentemente na memória principal.

2) Escalonamento Preemptivo e Não-Preemptivo:

Não-Preemptivo é o algoritmo de escalonamento que quando temos um processador designado para um certo processo não pode ser retiradoaté que o processo seja finalizado (conpletion), algoritmos não-preemptivos são simples e adequados para processamentos não interativos.

Preemptivo é o algoritmo de escalonamento que quando uma CPU está designada para um processo pode ser retirada deste em favor de outro processo,

isso sem prejuízo. São mais adequados para sistemas em que múltiplos processos requerem atenção do sistema.

3) Algoritmos de Escalonamento:

Escalonamento FIFO (Firt In Firt Out) – è a forma mais simples de escalonamento, os processos prontos são colocados numa fila organizada por ordem de chegada. Na sua vez, cada processo recebe o uso da CPU até que seja completado. O FIFO é um algoritmo não-preemptivos.

Escalonamento RR (Round-Robin) – os processos também são organizados em filas por ordem de chagada e então despachados para execução. Porém, ao invés de ser executado até o fim, cada processo recebe um pequeno intervalo de tempo (time-slice ou quantum). Caso o processo não seja finalizado neste intervalo de tempo será substituído pelo próximo processo da lista de processos ativos, e colocado no fim da fila. Isso significa que ao final de seu intervalo de tempo ocorre a preempção do processador, ou seja, o processador é designado a outro processo, sendo salvo o contexto do processo interrompido para permitir a continuidade da execução quando sua vez chegar novamente.

Escalonamento SJF (Shortest Job Firt) – é uma variante do FIFO onde os processos prontos são organizados numa fila segundo seu tempo de execução, sendo colocados a frentes os menores jobs. Mesmo sendo não-preemptivo, oferece a vantagem de proporcionar tempos médios de esperas menores que os oferecidos no esquema FIFO.

Escalonamento SRF (Shortest Remaining Firt) – é a variante preemptiva do escalonamento SJF. De forma semelhante ao SJF a fila de processos a serem processados é organizada conforme o tempo estimado de execução, sendo processados primeiro os menores Jobs. Na entrada de um novo processo, o algoritmo de escalonamento avalia seu tempo de execução incluindo job em execução, caso a estimativa de seu tempo de execução seja menor que a do processo concorrentemente em execução, ocorre a substituição do processo em execução pelo recém-chegado, de duração mais curta, ou seja, ocorre a preeempção do processo em execução. O processo suspenso deverá ser colocado na fila numa posição correspondente ao tempo de execução restante e não mais pelo tempo de execução total, tornando-se necessário registrar os tempos decorridos de execução de cada processo.

Escalonamento Highest Response-Ratio Next – para corrigir algumas deficiências do escalonamento SJF, Hansen (1971) propôs um balanceamento entre a duração do processo e o tempo de espera, de forma a compensar a espera excessiva de processos de maior duração. Para tanto idealizou a organização da fila de processos dinamicamente através do cálculo de suas razões de resposta (response ratio) ou prioridades:

tespera + tserviçoprioridade =

tserviço

Como o tempo de serviço aparece no denominados, os jobs de curta duração são favorecidos, mas como o tempo de espera aparece no denominador acontece o equilíbrio em relação a espera dos jobs maiores. Uma vez encaminhados a CPU, os jobs são processados até sua finalização, sendo assim, este é um algoritmo

não-preemptivo de escalonamento, apesar da firma dinâmica com que a fila de processos em espera é administrada.

Escalonamento MQF (Multilevel Feedback Queues) – é um interessante sistema de escalonamento baseado em várias filas encadeadas. Todos os novos processos são colocados inicialmente na fila de nível 1, que tem um comportamento FIFO, ou seja, o processo aguarda sua vez pela ordem de chegada. Ao utilizar a CPU podem ocorrer três situações:

1) o processo é finalizado e então retirado das filas,2) o processo solicita o uso de dispositivos de E/S, sendo bloqueado até

que o pedido de E/S seja atendido, voltando para a mesma fila até que seu quantum de tempo esgote e

3) tendo esgotado seu quantum inicial de tempo, o processo é colocado no final da fila de nível 2.

Nas filas seguintes o mecanismo é o mesmo, embora os processos só utilizem a CPU na sua vez e na ausência de processos nas filas de nível superior. Quando novos processos aparecem em filas superiores, ocorre a preempção dos processos nas filas de nível inferior, de forma a atender os processos existentes nas filas superiores. A última fila apresenta um comportamento um pouco diferente: ela não é uma FIFO e sim uma fila circular, ou seja, de escalonamento Round-Robin, onde os processos permanecem até que sejam finalizados