Conceitos de Escalonamento

Modulo 3 · Aula 1 ~15 min de leitura Nivel: Intermediario

Video da aula estara disponivel em breve

O Problema do Escalonamento

Quando ha mais processos prontos do que CPUs disponiveis, o SO precisa decidir: quem roda agora? Essa decisao e feita pelo escalonador (scheduler), e o algoritmo usado tem impacto direto na performance percebida pelo usuario e no throughput do sistema.

O escalonador e invocado quando:

Um processo termina ou bloqueia (I/O)
Um novo processo fica pronto (Ready)
Um timer interrupt ocorre (quantum expirou)
A prioridade de um processo muda

Criterios de Escalonamento

Nao existe um "melhor" algoritmo universal. A escolha depende do que voce quer otimizar:

Metricas de Escalonamento

Metrica              | Definicao                              | Otimizar
---------------------|----------------------------------------|----------
CPU Utilization      | % do tempo que a CPU esta ocupada      | Maximizar
Throughput           | Processos completados por unidade tempo| Maximizar
Turnaround Time      | Tempo total: chegada ate conclusao     | Minimizar
Waiting Time         | Tempo total na fila Ready              | Minimizar
Response Time        | Tempo entre request e primeira resposta| Minimizar
Fairness             | Cada processo recebe CPU justa          | Garantir

Exemplo numerico:
  Processo P chega em t=0, fica na fila ate t=3, roda de t=3 a t=8.
  Turnaround  = 8 - 0 = 8
  Waiting     = 3 - 0 = 3
  Response    = 3 - 0 = 3 (neste caso = waiting, pois nao ha preempcao)

Trade-offs inevitaveis Otimizar throughput geralmente piora response time (e vice-versa). Sistemas batch priorizam throughput. Sistemas interativos priorizam response time. Sistemas de tempo real priorizam previsibilidade (deadline guarantees).

Preemptivo vs. Nao-Preemptivo

A distincao mais fundamental entre escalonadores:

Diagrama — Preemptivo vs Nao-Preemptivo

Nao-Preemptivo (Cooperativo):
  Processo roda ate terminar ou bloquear voluntariamente.
  O SO nao pode tirar a CPU de um processo em execucao.

  CPU: |=====P1=====|===P2===|=======P3=======|===P4===|
       P1 so sai quando termina ou faz I/O

Preemptivo:
  O SO pode interromper um processo e dar a CPU a outro.
  Usa timer interrupt para garantir quantum maximo.

  CPU: |==P1==|==P2==|==P1==|==P3==|==P2==|==P1==|
       quantum de 10ms, processos se alternam

Nao-Preemptivo:                 Preemptivo:
+ Simples de implementar        + Nenhum processo monopoliza CPU
+ Sem race conditions no kernel + Melhor response time
- Um processo pode monopolizar  - Mais complexo (requer timer)
  a CPU indefinidamente         - Requer sincronizacao cuidadosa
- Ruim para sistemas interativos  (dados compartilhados no kernel)

Exemplos:                       Exemplos:
  Windows 3.1                     Linux, Windows NT+, macOS
  Mac OS classico                 Todos os SOs modernos

Todo SO moderno e preemptivo Escalonamento nao-preemptivo e historicamente interessante, mas nenhum SO de uso geral o utiliza mais. Se um processo entra em loop infinito num sistema nao-preemptivo, o sistema inteiro congela. Windows 3.1 era famoso por isso.

CPU-bound vs. I/O-bound

Processos tem perfis de uso de CPU muito diferentes, e um bom escalonador leva isso em conta:

Diagrama — CPU-bound vs I/O-bound

CPU-bound (ex: compilacao, rendering, crypto):
CPU: |============|....|============|....|============|
I/O: |............|====|............|====|............|
     Bursts longos de CPU, I/O curto e raro

I/O-bound (ex: editor de texto, browser, shell):
CPU: |==|.........|=|...........|==|.........|=|
I/O: |..|=========|.|===========|..|=========|.|
     Bursts curtos de CPU, muito tempo esperando I/O

Estrategia ideal:
  - Dar prioridade a processos I/O-bound (usam CPU por pouco tempo)
  - Eles liberam a CPU rapidamente e vao esperar I/O
  - Processos CPU-bound preenchem o tempo restante
  - Resultado: CPU e I/O devices ficam ocupados simultaneamente

Niveis de Escalonamento

Em sistemas complexos, o escalonamento acontece em multiplos niveis:

Long-term (job scheduler): decide quais processos entram no sistema (New → Ready). Controla o grau de multiprogramacao. Presente em sistemas batch.
Medium-term (swapper): decide quais processos sao temporariamente removidos da memoria (swap out) para liberar recursos. Presente em sistemas com memoria virtual.
Short-term (CPU scheduler): decide qual processo pronto (Ready) recebe a CPU. Executado a cada interrupcao de timer. Este e o escalonador que estudaremos em detalhe.

Diagrama — Niveis de Escalonamento

                    Long-term           Short-term
Jobs na fila ------> [New] ----------> [Ready] ------> [Running]
                       |                 ^   |            |
                       |    Medium-term  |   |            |
                       |    (swap in)    |   v            |
                       |         +-------+  [Waiting]     |
                       |         |                        |
                       +------[Swapped out]               |
                              (em disco)                  v
                                                    [Terminated]

Dispatcher

O dispatcher e o modulo que efetivamente realiza a troca de contexto decidida pelo escalonador. Suas funcoes:

Context switch (salvar/restaurar registradores)
Trocar para user mode
Saltar para o endereco correto no programa do usuario

O tempo que o dispatcher leva para parar um processo e iniciar outro e o dispatch latency. Em sistemas de tempo real, minimizar essa latencia e critico.

No harness.os

O escalonamento no harness.os e o problema de decidir qual agente executa qual tarefa, quando, e com quais recursos:

Diagrama — Token Economy como Resource Allocation

Recursos escassos no SO:           Recursos escassos no harness.os:
========================           =================================
CPU time (cycles)                  Token budget (API calls)
RAM (bytes)                        Context window (tokens)
I/O bandwidth                     MCP tool calls (DB queries)
Network bandwidth                 Agent slots (concurrent sessions)

Criterios de escalonamento SO:     Criterios harness.os:
  CPU utilization ->                 Token efficiency (output/token)
  Throughput      ->                 Tasks completed per session
  Waiting time    ->                 Time-to-first-response
  Fairness        ->                 All projects get attention

Preemptivo:                        Compaction:
  Timer interrupt forca              Token limit forca "preempcao"
  context switch                     do contexto — dados antigos
                                     sao resumidos para liberar espaco

Python — Escalonador de requests no harness.os

class RequestScheduler:
    """Decide qual request da fila processar primeiro."""

    def schedule(self, ready_queue):
        # Criterios (como um escalonador de CPU):
        # 1. Prioridade: bugs > features > docs
        # 2. Waiting time: requests antigos sobem prioridade
        # 3. Estimated burst: tasks curtas primeiro (SJF)
        # 4. Fairness: nenhum projeto fica sem atencao

        return sorted(ready_queue, key=lambda r: (
            -r.priority,           # maior prioridade primeiro
            -r.waiting_time,       # aging: previne starvation
            r.estimated_tokens,    # jobs curtos primeiro (SJF)
        ))[0]

Assim como o SO precisa equilibrar throughput e response time, o harness.os equilibra token efficiency (completar mais trabalho por token) com fairness (todos os projetos recebem atencao). E exatamente o mesmo trade-off, apenas com recursos diferentes.

Homework

Classifique estes programas como CPU-bound ou I/O-bound: (a) compilador gcc, (b) servidor web nginx, (c) mineracao de crypto, (d) cliente de email, (e) treinamento de ML.
No harness.os, o orchestrator decide qual agente executar. Descreva um cenario onde a "starvation" acontece (um projeto nunca e atendido) e como preveni-la com aging.
Calcule turnaround, waiting, e response time para estes processos num sistema FIFO: P1(burst=5), P2(burst=3), P3(burst=8), chegando todos em t=0 nessa ordem.

Resumo

Escalonador decide quem usa a CPU quando ha mais processos que cores
Metricas: CPU utilization, throughput, turnaround, waiting, response time
Preemptivo (SO pode interromper) vs nao-preemptivo (processo decide quando sai)
Processos CPU-bound e I/O-bound tem necessidades diferentes
3 niveis: long-term (admissao), medium-term (swap), short-term (CPU)

Verifique seu entendimento

Um processo I/O-bound deveria receber prioridade maior ou menor que um CPU-bound? Por que?

Maior prioridade: I/O-bound usa CPU por pouco tempo e a libera rapidamente, melhorando response time geral
Menor prioridade: I/O-bound nao precisa de CPU, entao pode esperar mais
Mesma prioridade: tratar todos igualmente garante fairness
Depende exclusivamente do usuario: o SO nao deve interferir em prioridades

Aula anterior 2.3 Threads: Conceitos e Modelos Proxima aula 3.2 Algoritmos de Escalonamento