Escalonamento de processos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book.svg
Esta página ou secção não cita fontes confiáveis e independentes, o que compromete sua credibilidade (desde dezembro de 2013). Por favor, adicione referências e insira-as corretamente no texto ou no rodapé. Conteúdo sem fontes poderá ser removido.
Encontre fontes: Google (notícias, livros e acadêmico)

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

Tipos básicos[editar | editar código-fonte]

Escalonador de curto prazo[editar | editar código-fonte]

Seleciona entre os processos em estado de pronto que estão na memória, para serem executados pelo processador. O escalonador de curto prazo faz decisões de escalonamento muito mais frequentemente que os de médio e longo prazo.

Escalonador de médio prazo[editar | editar código-fonte]

Seleciona entre os processos que estão na memória virtual, reduz o grau de multiprogramações. 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.

Escalonador de longo prazo[editar | editar código-fonte]

Seleciona entre os processos novos, os que são limitados por entrada/saída e os que são limitados por CPU, dando prioridade aqueles limitados por I/O, já que utilizam menos tempo o processador. Este escalonador é o responsável pelo grau de multiprocessamento, ou seja a quantidade de processos que o sistema irá trabalhar.

Definição[editar | editar código-fonte]

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 ao mesmo tempo na maquina.

O escalonamento de processos é uma tarefa complicada, pois nenhum algoritmo é totalmente eficiente e a prova de falhas, principalmente em se tratando de sistemas interativos, como o Windows, pois a interação com o usuário é fundamental para este sistema onde quem o utiliza procura respostas rápidas e a todo o momento processos são interrompidos pelo usuário.

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 programa estava no seu estado pronto.

Responsáveis por essa tarefa são algoritmos que são entendidos mais facilmente, estudados separadamente, mas na pratica os sistemas operacionais utilizam combinações deles para melhor escalonar os processos.

Objetivos do Escalonamento[editar | editar código-fonte]

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[carece de fontes?]:

  • 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 proceso 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[editar | editar código-fonte]

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[editar | editar código-fonte]

Execução do escalonamento FIFO.

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, quer 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 memoria 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:

Diagrama de Gantt do algoritmo FIFO
  • FIFO[1][2][3] (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.
    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 idéia do algoritmo é por para rodar o processo com razões mais baixas, diminuindo, em conseqüência, as razões mais altas.
  • RR[4][5][6] (Round-Robin): Inspirado na história de Robin Hood onde, na procura de justiça, Robin roubava dos ricos para entregar aos pobres, fazendo assim com que todos no seu reino tivesse o mesmo tanto de bens. Uma das mais simples e robustas entre as atuais técnicas utilizadas para problemas de distribuição de carga, nesse escalonamento o sistema operacional possui um timer, chamado de quantum, onde todos os processos ganham o mesmo valor de quantum para rodarem na CPU, depois que o quantum acaba e o processo não terminou, ocorre uma preempção e o processo é inserido no fim da fila. Se o processo termina antes de um quantum, a CPU é liberada para a execução de novos processos. Em ambos os casos, após a liberação da CPU, um novo processo é escolhido na fila. Novos processos são inseridos no fim da fila.Quando um processo é retirado da fila para a CPU, ocorre uma troca de contexto, o que resulta em um tempo adicional na execução do processo.Esta técnica remove a necessidade de criar sistemas para monitoração dinâmica e são obviamente construídas de forma muito mais rápida e prática das que fazem balanceamento através de medições de recursos. Esta técnica foi criada antes mesmo de existirem computadores e é até hoje utilizada em larga escala por inúmeros sistemas com diferentes propósitos. . Com exceção do algoritmo RR, FIFO e escalonamento garantido, todos os outros sofrem do problema de Inanição (starvation), preemptivo;
  • Múltiplas Filas[7][8]: São usadas várias filas de processos prontos para executar, cada processo e colocado em uma fila, e cada fila tem uma política de escalonamento própria e outra entre filas, preemptivo, cada fila tem um determinado nível de prioridade, sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS(Compatible Time-Sharing System - Sistema Compatível de Divisão por Tempo).No algoritmo de Múltiplas Filas, também pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo, o algoritmo RR ou FCFS.

Todos os algoritmos classificam os processos em estados: Iniciando, Pronto, Executando, Entrada/ Saída e Terminado.

Estados de processos[editar | editar código-fonte]

Para o sistema operacional organizar os processos que serão atendidos eles são atribuídos estados para os mesmos.

Diagrama de Estados de Processos[editar | editar código-fonte]

Quem armazena essas informações como os estados de processos e outras como: tempo e execução, por exemplo, é o bloco de controle de processo (PCB - Process Control Block).

Distribuição de Prioridades[editar | editar código-fonte]

Para melhorar essa distribuição da CPU entre os processos, alguns algoritmos utilizam diferentes prioridades. Com intuito de gerenciar melhor as prioridades de processo, o sistema operacional cria filas de processos. Em cada fila existem processos de mesma prioridade, e existe também fila para processos de entrada e saída. Prioridades podem ser mudadas pelo usuário, ou atribuídas automaticamente pelo sistema operacional em questão.

Mesmo com a aplicação de prioridades e algoritmos melhor implementados, alguns processos ainda correm o risco de sofrer starvation (ficar muito tempo sem receber a CPU) por isso em determinando momento pode ocorrer o que chamamos de aging (O aging ocorre quando a prioridade de um processo vai se alterando com o "tempo de vida" do mesmo, controlando o starvation), que muda momentaneamente a prioridade de um processo que não é executado há muito tempo e joga sua prioridade para a mais alta possível para que ele seja atendido, logo após as prioridades voltam ao normal.

Outro caso em que prioridades são alteradas é quando um programa de baixa prioridade começou a fazer uso de algum periférico de entrada e saída antes de outro de prioridade alta. Neste caso processos de alta prioridade são obrigados a esperarem os de baixa terminar sua E/S para poderem usar este periférico.

Alterando prioridades no Windows[editar | editar código-fonte]

Existem ainda sistemas em que quando um processo inicia sua execução, o sistema garante que este processo vai ser terminado, são chamados sistemas garantidos. Nestes sistemas a intervenção do usuário é mínima, ao contrario do que ocorre em sistemas em tempo real como o Windows em que o usuário interrompe processos a todo instante por isso o sistema não garante que um processo vai ser Terminado.

Trocas de contexto[editar | editar código-fonte]

Processos são interrompidos e retomados a todo tempo, para que o sistema operacional possa fazer esse tipo de ação, é necessária a troca de contexto. Para que o sistema operacional possa interromper um processo e retomar ele mais tarde, ele usa a PCB (Process Control Block) para guardar todas as informações que a CPU estava usando naquele momento e possa consulta-la mais tarde para que retome exatamente no ponto em que foi interrompido anteriormente.

Threads[editar | editar código-fonte]

Ver artigo principal: Threads

Processos podem ser divididos em “pedaços” para que eles não deixem de responder por algum motivo externo, como isso poderia atrapalhar a sua execução, ou para agilizar a programação e execução. Quando programas são divididos em threads, podemos ter partes do processo rodando em paralelo, pois as threads também são escalonáveis.

Ligações externas[editar | editar código-fonte]

Ícone de esboço Este artigo sobre Informática é um esboço. Você pode ajudar a Wikipédia expandindo-o.
  1. «A simplicidade e a importância do Round Robin como técnica de balanceamento -». 2014-10-16. Consultado em 2016-08-09. 
  2. «Escalonamento Round-Robin». www.ime.usp.br. Consultado em 2016-08-09. 
  3. «Laboratorio de Sistemas Operacionais». fubica.lsd.ufcg.edu.br. Consultado em 2016-08-09. 
  4. «Laboratorio de Sistemas Operacionais». fubica.lsd.ufcg.edu.br. Consultado em 2016-08-09. 
  5. «A simplicidade e a importância do Round Robin como técnica de balanceamento -». 2014-10-16. Consultado em 2016-08-09. 
  6. «Escalonamento Round-Robin». www.ime.usp.br. Consultado em 2016-08-09. 
  7. «Escalonamento FIFO». prezi.com. Consultado em 2016-08-09. 
  8. «é um tipo de algoritmo de escalonamento, no qual são usadas filas de processos. Cada fila tem um determinado nível de prioridade. Sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - Sistema Compatível de Divisão por Tempo).No algoritmo de Múltiplas Filas, também pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo, o algoritmo RR ou FCFS. : definição de é um tipo de algoritmo de escalonamento, no qual são usadas filas de processos. Cada fila tem um determinado nível de prioridade. Sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - Sistema Compatível de Divisão por Tempo).No algoritmo de Múltiplas Filas, também pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo, o algoritmo RR ou FCFS. e sinónimos de é um tipo de algoritmo de escalonamento, no qual são usadas filas de processos. Cada fila tem um determinado nível de prioridade. Sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - Sistema Compatível de Divisão por Tempo).No algoritmo de Múltiplas Filas, também pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo, o algoritmo RR ou FCFS. (português)». dicionario.sensagent.com. Consultado em 2016-08-09.