Escalonamento de processos

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

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ção. 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.

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.

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

Existem vários critérios que permitem a avaliação da qualidade do serviço oferecido por um algoritmo de escalonamento. São eles: uso do processador, tempo de resposta e tempo de permanência.

O tempo de permanência, tempo de retorno ou turnaround time, é um critério simples dado pela soma do tempo de espera com o tempo de serviço ou tempo de execução. Em geral deseja- se que o tempo de permanência seja o menor possível.

Uma outra forma de avaliar a qualidade do escalonamento é utilizando-se do tempo de permanência normalizado, ou seja, a razão entre o tempo de permanência e o tempo de serviço.

Algoritmos escalonadores[editar | editar código-fonte]

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 à 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:

  • FIFO (First in, first out) ou FCFS (First come, first served): Onde como seu próprio nome já diz, o primeiro que chega será o primeiro a ser executado;
  • 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;
  • 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;
  • 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.
  • RR (Round-Robin): 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. Com exceção do algoritmo RR e escalonamento garantido, todos os outros sofrem do problema de Inanição (starvation).
  • Múltiplas Filas: 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.

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

Ainda existem vários

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]

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.