Escalonamento de tarefas - Teoria de Sistemas Operacionais

Os algoritmos de escalonamento por prioridades (PRIO) e Shortest Job First (SJF) podem gerar starvation (inanição).

Um editor de texto não é um tipo de tarefa CPU-bound. CPU-bound são tarefas que requerem muito processamento de CPU. O editor de texto não demanda de muito processamento e interage muito com o usuário. Ele está em grande parte do tempo aguardando uma requisição do usuário para processar e gerar uma saída. Sendo assim, ele pode ser considerado uma tarefa IO-bound.

No escalonamento cooperativo, a tarefa libera o processador quando ela termina, solicita uma entrada/saída, indo para o estado suspensa ou quando libera explicitamente a CPU por meio de uma chamada de sistema. No escalonamento cooperativo não existe um limite de tempo para tarefa permanecer no processador. As tarefas devem cooperar entre si para utilizarem o processador. Se não houver cooperação, o uso do processador pode ser injusto (ou seja, uma tarefa pode dominar o processador enquanto outras estão aguardando no estado de Pronta).

Starvation (inanição) significa que uma tarefa está no estado de pronta mas nunca recebe o processador para executar. Algoritmos de escalonamento que permitem que uma tarefa que chegou recentemente na fila de prontos passe na frente de outras tarefas mais antigas podem gerar inanição. Para resolver este problema, pode-se utilizar a técnica de envelhecimento (aging).

Para otimizar a operação do Sistema Operacional, o despachante (dispatcher) precisa de executar a cada troca de contexto pois é ele quem efetivamente faz a troca. A troca é feita com base na fila definida pelo escalonador.

Os algoritmos de escalonamento por prioridades (PRIO) e Shortest Job First (SJF) podem gerar starvation (inanição). Como o algoritmo PRIO escolhe a tarefa com maior prioridade para ser executada, uma tarefa de baixa prioridade pode esperar indefinidamente pelo processador. O mesmo raciocínio ocorre para o SJF pois ele escolhe sempre a menor tarefa (em termos de tempo) para ser executada. Caso tarefas pequenas cheguem continuamente no sistema, uma tarefa que demanda mais tempo nunca ganhará o processador.

A métrica “Tempo de Vida”, utilizada para avaliar escalonadores, diz respeito ao tempo entre a criação da tarefa e o seu encerramento.

 A métrica “Tempo de Espera”, utilizada para avaliar escalonadores, diz respeito ao tempo gasto pela tarefa na fila de prontos. O tempo de espera é o tempo que a tarefa poderia estar no processador, mas deve ficar aguardando no estado de pronta.

Para otimizar a operação do Sistema Operacional, o escalonador não precisa ser executado a cada troca de contexto. O escalonador pode definir uma fila de tarefas que serão executadas pelos próximos N milissegundos e, a cada troca de contexto, o despachante utiliza essa lista para executar a troca.

São tipos de métricas para avaliar diferentes escalonadores:

• Tempo de vida
• Tempo de espera
• Tempo de resposta

O tempo do processo no estado executando não é uma métrica para avaliar o algoritmo de escalonamento. Essa medida pode ser utilizada para avaliar um determinado algoritmo (por exemplo, um algoritmo de busca), mas não a efetividade do algoritmo de escalonamento.

No escalonamento preemptivo, uma troca de contexto pode ocorrer a cada interrupção, exceção ou chamada de sistema. Uma troca de contexto pode ocorrer quando: i) uma interrupção (que pode ser uma interrupção indicando que tempo da tarefa no processador terminou) ou ii) uma exceção (que pode ser um acesso a uma posição de memória indevida) ou iii) uma chamada de sistema (que pode ser uma write ou read). Vale destacar que, quando a tarefa executa uma chamada de sistema, ela irá para o estado de suspensa até que a execução da chamada seja encerrada.

O escalonador de CPU define a ordem de execução das tarefas que estão no estado Prontas. O escalonador define quem será a próxima tarefa que será executada e o despachante realiza a troca das tarefas na CPU. A ordem de execução das tarefas deve considerar apenas as tarefas prontas para ganharem o processador. Não faz sentido escalonar tarefas que estão aguardando algum evento (I/O, por exemplo).

São tipos algoritmos de escalonamento:

• First Come, First Served
• Round robin
• Shortest job first

Caso o Sistema Operacional utilize o algoritmo de escalonamento por prioridades (PRIO), a técnica de Envelhecimento (aging) pode ser utilizada para resolver o problema de starvation. Tarefas que estão aguardando muito tempo na fila de prontas (ou seja, tarefas que “envelhecem” na fila de prontas) podem ter sua prioridade aumentada de tal forma que possam ser executadas. Essa técnica pode utilizar uma função linear, ou seja, a prioridade aumenta linearmente com o tempo em que a tarefa está aguardando na fila de prontas. Lembrando que, após ganhar o processador, a tarefa volta a ter sua prioridade original. Os algoritmo de escalonamento que alteram a prioridade da tarefa são chamados de algoritmos por prioridades dinâmicas.