Tipos de comutação de processos :

    • Nonpreemptive - comutação pelos processos

    Comutação inexistente : Run to completion

    Comutação voluntária : Friendly Turn Over

    • Preemptive - comutação pelo sistema operativo

    Comutação forçada : Run while allowed

Comutador de processos

Scheduler

O scheduler é quem tem a função de comutar os processos, ou seja, implementar o pseudo-paralelismo.

De um ponto de vista superior, existe paralelismo.

     CPU bound :

    Processos de processamento intensivo

    Denominados de processos batch

    Processos de input/output intensivo

    Denominados de processos interactivos

Quando existem vários processos prontos para "correr", o scheduler deve decidir qual vai ser escolhido, para tal pode contemplar um ou  vários dos seguintes critérios :

    • justiça, cada processo leva a sua parte de cpu

    • eficiência, manter o cpu ocupado 100%

    • tempo de resposta, minimizar o tempo de resposta (acção/reacção) para       os utilizadores interactivos

    • tempo de volta (tempo de execução), minimizar o tempo em                      execução dos processo batch (ponto de vista de um processo)

    • taxa de saída, maximizar o número de processos terminados por hora

Princípios de Scheduling

Os algoritmos de scheduling baseiam-se principalmente nos  seguintes factores :

    • Tempo de execução do processo

    dão prioridade à igualdade de execução

    • Prioridade associada os processo

    dão prioridade à importância do processo

Este mecanismo baseia-se na existência de :

   • Clock do sistema, clock tick

  • Quantum, n.º de clock ticks que um processo pode ocupar o cpu

Um processo quando é seleccionado para execução, pode ocupar o cpu por um intervalo de tempo (quantum), por tal este mecanismo é designado de "fatias de tempo" (TIME_SLICE )

Este mecanismo baseia-se nas seguintes premissas :

        • cada processo tem uma determinada prioridade

    • o processo em execução é o processo disponível mais prioritário

Este mecanismo faz distinção entre os vários processos, utilizando o valor de prioridade de cada um (based on priorities).

-Round Robin

Round Robin - mecanismo (T.S.) em que a atribuição do  processador é feita por atendimento do tipo fifo.Quando um processo é retirado de execução, ele é  recolocado no fifo.

Tempo de mudança de processo corrente (context switch ou process switch) de 5ms :

        Com Quantum de 20ms, gasta-se 25% do tempo

        Com Quantum de 500ms, gasta-se 1% do tempo

        Com Quantum de 20ms, 180ms

       Com Quantum de 500ms, 4.5s

Que é também o tempo máximo que um utilizador pode esperar por uma resposta do sistema.

Quantum grande : menos comutações, maior tempo de resposta

Quantum pequeno : mais comutações, menor tempo de resposta

Um sistema Round Robin com quantum idêntico para todos os processos, pode ser justo mas não é eficiente. Pois existem :

    processos interactivos => quantum pequeno

    processos batch => quantum grande

Solução : Round Robin com quantum variável

• Quando um processo esgota o seu quantum, este é aumentado
• Quando um processo não esgota o seu quantum, este é reduzido

No Scheduling com múltiplas queues cada conjunto de processos com características semelhantes partilha uma queue.

Exemplo :

    Queue para processos interactivos

        Queue para processos batch

Existem agora, duas formas de scheduling :

    Scheduling dentro de cada queue

     Scheduling entre queues

• Scheduling dentro de cada queue :

       Cada queue como agrega processos com características semelhantes,

           pode ter um critério próprio ( o que seja mais eficiente para as suas

           características ).

• Scheduling entre queues :

           Baseado em prioridades, enquanto existir processos na queue mais

            prioritária, os processos das outras queues não são executados.

            Baseado em tempo, o tempo do cpu é partilhado pelas várias queues,

            por exemplo : queue "interactiva" 80%, queue "batch" 20%

O mecanismo anterior apresenta as seguintes fraquezas :

       • Será difícil classificar préviamente o comportamento de todos

            os processos

           • Um processo pode não ter um comportamento constante em termos

             de cpu

Solução :            

                  Transição dinâmica entre as várias queues

Neste caso tem que se definir o critério de passagem entre queues

Os processos do utilizador entram para a queue de processos interactivos.

Entre queues o atendimento é exclusivamente prioritário.

O processos do sistema não são preemptíveis ( Fists-Come, First-Served ).

Cada vez que um processo :

• esgotar o quantum, transita para uma queue de menor prioridade.

• não esgotar o quantum, "sobe" de queue.

Short Job First

Short job first - algoritmo em que o processo escolhido para execução é o que necessitará de menor tempo de cpu. Este algoritmo optimiza o tempo médio de execução dos vários processos.

Exemplo : p1/5, p2/4, p3/10, p4/7 Tempo médio total

Execução pela ordem de declaração : (5+9+19+26)/4 = 14.75

Execução SJF : (4+9+16+26)/4 = 13.75

Execução LONG JF : (10+17+22+26)/4 = 18.75

Podemos considerar:

• o tempo de execução do processo (nonpreemptive).

• o tempo da próxima execução (preemptive).

No scheduling baseado em prioridades (como já visto) o processo em execução é o processo mais prioritário no sistema.

Nota : máxima prioridade é a prioridade de valor zero

O SJF é um caso destes com : prio = k* Texec (k>0)

Pode acontecer que os processos de menor prioridade raramente

tenham oportunidade de correr, neste caso diz-se que existe

STARVATION ( nonopólio da utilização de um recurso)

De forma a permitir uma utilização coerente do cpu, o sistema pode alterar as prioridades dos processos no sentido de ajustar os diferentes comportamentos dos processos.

Uma das formas consiste em baixar a prioridade de um processo em função do consumo de cpu, como já visto no SJF :

            prio = Baseprio + k*TLexec

• estática : definida pelo utilizador ou pelo sistema (baseprio)

• dinâmica : definida pelo sistema (TLexec)

Um sistema de tempo real tem que assegurar os tempos de execução de alguns dos seus serviços.

    • a tempo de comutação deve ser o mínimo possível

    • baseado em prioridade, as tarefas mais críticas têm mais prioridade

    • as prioridades não podem ser diminuídas com o tempo

    • os serviços têm tempo de execução definido

Como satisfazer o pedido de um processo prioritário por um recurso

possuído por um processo menos prioritário ?

Priority inversion - o processo menos prioritário assume a prioridade do

outro processo, de forma a libertar o recurso o mais rápidamente possível.

Retornando depois à sua antiga prioridade.