O escalonamento de processos ou agendador de tarefas (em inglês scheduling) é uma atividade organizacional feita pelo escalonador (scheduler) da CPU ou de um sistema distribuído, possibilitando executar os processos mais viáveis e concorrentes, priorizando determinados tipos de processos, como os de I/O Bound e os CPU Bound.
O escalonador de processo é um processo que deve ser executado quando da mudança de contexto (troca de processo), ao passo que ele escolhe o processo que será executado pela CPU, sendo o escalonamento realizado com o auxílio do hardware.
São utilizados algoritmos de escalonamento para determinar qual processo será executado em determinado momento e por quanto tempo.
O escalonador de processos de 2 níveis escolhe o processo que tem mais prioridade e menos tempo e coloca-o na memória principal, ficando os outros alocados em disco; com essa execução o processador evita ficar ocioso.
O escalonador deve ainda se preocupar com a eficiência da CPU, pois o chaveamento de processos é complexo e custoso, uma vez que ele afeta o desempenho do sistema e por sua vez a satisfação do usuário.
Tipos básicos Escalonador de curto prazo Seleciona entre os processos em estado de pronto que estão na memória, para serem executados pelo processador, após a interrupção de um ciclo, uma interrupção de E/S, uma chamada de sistema ou outra forma de sinal. Assim o escalonador de curto prazo faz decisões de escalonamento muito mais frequentemente que os de médio e longo prazo. Uma decisão de escalonamento deve ser feita no mínimo a cada fatia de tempo, e estas são bem curtas.
Escalonador de médio prazo Seleciona entre os processos que estão na memória virtual. Ele temporariamente remove o processo da memória principal e o coloca na memória secundária (swap) fazendo as operações de swapping in e swapping out. O escalonador a médio prazo pode realizar a operação swap out em vários casos, como: um processo que não está mais ativo após um tempo, um processo que tem baixa prioridade, um processo que tem tido falta de página frequentemente, um processo que está ocupando uma larga quantidade de memória que precisa ser removido da memória principal para outros processos serem carregados.
Escalonador de longo prazo Seleciona os processos que estão na memória secundária e que serão levados para a memória principal. Isto é, quando uma tentativa de executar um programa é feita, sua admissão ao conjunto de processos sendo executados é autorizada ou atrasada pelo escalonador de longo prazo. Assim, este escalonador dita quais processos serão executados em um sistema, e o degrau de concorrência do sistema, ou seja quantos processos serão executados em concorrência, e como a divisão entre processos I/O bound(orientado à E/S) e CPU bound(orientados à CPU) deve ser feita. Geralmente este escalonador é responsável pelo Grau de Multiprogramação.
Definição Para que a CPU não fique muito tempo sem executar tarefa alguma, os sistemas operacionais utilizam técnicas para escalonar os processos que estão em execução na máquina.
O escalonamento de processos é uma atividade complicada já que nenhum algoritmo é totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas interativos, como o Microsoft Windows. Nos sistemas interativos a interação com o usuário é fundamental já que quem o utiliza busca respostas rápidas e, a todo o momento, processos são interrompidos pelo usuário.
Escalonamento é muito atuante nos sistemas em tempo real, onde o tempo é um fator extremamente crítico, como: aviões, hospitais, usinas nucleares, bancos, multimídia, etc. Em ambientes como estes, quando um sistema tem respostas com atraso, é tão ruim quanto não obter. Tipos de sistemas em tempo real: Hard Real Time onde atrasos não são tolerados (aviões, usinas nucleares, hospitais); Soft Real Time quando atrasos são tolerados (Bancos, Multimídia).
O escalonador do SO utiliza alguns critérios de escalonamento, como: a taxa de utilização de CPU, que é a fração de tempo durante a qual ela está sendo ocupada; throughput que são números de processos terminados por unidade de tempo; turnaround que é o tempo transcorrido desde o momento em que o software entra e o instante em que termina sua execução; tempo de resposta: intervalo entre a chegada ao sistema e inicio de sua execução; tempo de espera: soma dos períodos em que o processo estava no seu estado pronto.
Os responsáveis por essa tarefa são algoritmos de escalonamento. Os sistemas operacionais utilizam combinações deles para melhor escalonar os processos.
Objetivos do Escalonamento O projeto de um escalonador adequado deve levar em conta uma série de diferentes necessidades, ou seja, o projeto de uma política de escalonamento deve contemplar os seguintes objetivos:
Ser justo: Todos os processos devem ser tratados igualmente, tendo possibilidades idênticas de uso do processador, devendo ser evitado o adiamento indefinido. Maximizar a produtividade (throughput): Procurar maximizar o número de tarefas processadas por unidade de tempo. Ser previsível: Uma tarefa deveria ser sempre executada com aproximadamente o mesmo tempo e custo computacional. Minimizar o tempo de resposta para usuários interativos. Maximizar o número possível de usuário interativos. Minimizar a sobrecarga (overhead): Recursos não devem ser desperdiçados embora algum investimento em termos de recursos para o sistema pode permitir maior eficiência. Favorecer processos "bem comportados": Processos que tenham comportamento adequado poderiam receber um serviço melhor. Balancear o uso de recursos: o escalonador deve manter todos os recursos ocupados, ou seja, processos que usam recursos sub- utilizados deveriam ser favorecidos. Exibir degradação previsível e progressiva em situações de intensa carga de trabalho.
Como pode ser visto facilmente, alguns destes objetivos são contraditórios, pois dado que a quantidade de tempo disponível de processamento (tempo do processador) é finita, assim como os demais recursos computacionais, para que um processo seja favorecido outro deve ser prejudicado.
O maior problema existente no projeto de algoritmos de escalonamento está associado à natureza imprevisível dos processos, pois não é possível prevermos se um dado processo utilizará intensamente o processador, ou se precisará grandes quantidades de memória ou se necessitará numerosos acessos aos dispositivos e E/S.
Quando é necessário o uso do algoritmo de escalonamento? Existem situações nas quais um processo de escalonamento é necessário. Dentre elas estão ocasiões onde um novo processo é criado; quando um processo terminou sua execução e um próximo processo pronto deve ser executado; quando um processo é bloqueado (semáforo, dependência de E/S), resultando que outro processo deve ser executado. Quando uma interrupção de E/S ocorre, o escalonador deve optar por: executar o processo que estava esperando essa interrupção; continuar executando o processo que já estava sendo executado; ou executar um terceiro processo que esteja pronto para ser executado.
Algoritmos de escalonamento thumb|Execução do escalonamento FIFO.|249x249px
Existem os algoritmos preemptivos e os não preemptivos. Os preemptivos são algoritmos que permitem que um processo seja interrompido durante sua execução, que seja por força de uma interrupção de entrada/saída, quer seja em decorrência da politica de escalonamento adotada e aplicada por parte do escalonador de processos ou simplesmente por força do término da execução do processo. Após a interrupção deste processo, ocorre o que se chama de troca de contexto, que consiste em salvar o conteúdo dos registradores e a memória utilizada pelo processo e conceder a outro processo o privilégio de executar na CPU, restaurando assim o contexto deste ultimo processo. Cabe ressaltar que nos algoritmos não preemptivos, por serem utilizados exclusivamente em sistemas monoprocessados, esse fato não ocorre, sendo cada programa executado até o fim.
Exemplos de Algoritmos: miniaturadaimagem|249x249px|Diagrama de Gantt do algoritmo FIFO FIFO (First in, first out) ou FCFS (First come, first served), em português:"primeiro que entra, primeiro que sai": Onde como seu próprio nome já diz, o primeiro que chega será o primeiro a ser executado, não-preemptivo, ou seja, executa o processo como um todo do início ao fim não interrompendo o processo executado até ser finalizado, apenas uma fila, processos que passam para o estado de pronto vão para o final da fila e são escalonados quando chegam no início. Vantagens: o mais simples entre os processos de escalonamento, até mais do que o Round-Robin, todos os processos tendem a serem atendidos. Desvantagens: muito sensível a ordem de chegada, se processos maiores chegarem primeiro aumentarão o tempo médio de espera, não garante um tempo de resposta rápido. SJF (Shortest Job First): Onde o menor processo ganhará a CPU e atrás do mesmo formar uma fila de processos por ordem crescente de tempo de execução, não-preemptivo. Desvantagem: baixo aproveitamento quando se tem poucos processos prontos para serem executados. SRT (Shortest Remaining Time): Neste algoritmo é escolhido o processo que possua o menor tempo restante, mesmo que esse processo chegue à metade de uma operação, se o processo novo for menor ele será executado primeiro, preemptivo. Desvantagem: processos que consomem mais tempo de execução podem demorar muito para serem finalizados se muitos processos com curto tempo de execução chegarem. Algoritmo Loteria: O Sistema Operacional distribui tokens (fichas), numerados entre os processos, para o escalonamento é sorteado um numero aleatório para que o processo ganhe a vez na CPU, processos com mais tokens têm mais chance de receber antes a CPU; Algoritmo de Prioridade: Como o próprio nome já diz, é um algoritmo onde cada processo no estado de pronto recebe uma prioridade, os processos com maiores prioridades são executados primeiro, prioridades que podem ser atribuídas dinâmica ou estaticamente. É um Algoritmo preemptivo.miniaturadaimagem|249x249px|Diagrama de Gantt do algoritmo RR Escalonamento garantido: Este algoritmo busca cumprir promessas de alocação de CPU o mais preciso possível. Uma forma completamente diferente de tratar a questão do escalonamento é fazer certas promessas ao usuário a respeito da performance, e cumpri-las de alguma forma.Uma promessa bem realista e muito fácil de cumprir é a de que se houver N usuários ativos na rede, cada um vai receber em torno de 1/N da capacidade de processamento que um usuário usou para todos os seus processos desde o momento em que tal usuário tornou-se ativo.Como o tempo que cada usuário gastou até o momento é conhecido, é fácil calcular a razão entre o tempo realmente concedido ao usuário e o tempo prometido. A ideia do algoritmo é por para rodar o processo com razões mais baixas, diminuindo, em consequência, as razões mais altas.