DEV Community

Alex Volnei Galante
Alex Volnei Galante

Posted on

Kernel Linux para Desenvolvedores Backend - Processos & Threads Parte II

#algorithms #backend #computerscience #linux

Este artigo é a continuação da Parte I, onde abordamos processos, seu ciclo de vida, syscalls e como os runtimes de Python, Go e .NET os utilizam. Se você ainda não leu, recomendo começar por lá:
Kernel Linux para Desenvolvedores Backend — Processos & Threads Parte I

Sumário da Parte II

Escalonamento de Processos

A peça fundamental que realiza toda a máquina de estados com processos no kernel é o escalonador. Vamos começar com uma base teórica sobre os algoritmos de escalonamento, suas categorias e como o Linux implementa isso na prática.

Categorias de Algoritmos de Escalonamento

Os algoritmos de escalonamento são projetados para diferentes tipos de sistemas, cada um com prioridades distintas.

Algoritmos para Batch Systems

Sistemas batch priorizam throughput e turnaround time. Não há usuário interativo esperando resposta.

First-Come, First-Served (FCFS)

Detalhe completo no link https://www.geeksforgeeks.org/dsa/first-come-first-serve-cpu-scheduling-non-preemptive/ — é o algoritmo mais simples, mas pode levar a tempos de espera muito altos para processos curtos (efeito comboio).

Executa os processos na ordem de chegada. O processo que chega primeiro é executado até terminar, depois o próximo, e assim por diante.

  Fila de chegada: P1(24ms) → P2(3ms) → P3(3ms)

  Execução FCFS:
  |────────── P1 (24ms) ──────────|─ P2 (3ms) ─|─ P3 (3ms) ─|
  0                               24            27            30

  Waiting time médio: (0 + 24 + 27) / 3 = 17ms

  Se a ordem fosse P2, P3, P1:
  |─ P2 ─|─ P3 ─|────────── P1 (24ms) ──────────|
  0       3       6                               30

  Waiting time médio: (0 + 3 + 6) / 3 = 3ms  ← 5.7x melhor!
Enter fullscreen mode Exit fullscreen mode

O efeito comboio (convoy effect) é o problema clássico do FCFS: um processo CPU-bound longo bloqueia todos os demais. Isso é análogo a ter uma query SQL pesada bloqueando o único worker disponível.

Shortest Job First (SJF)

Detalhe completo no link https://translate.google.com/translate?u=https://www.geeksforgeeks.org/operating-systems/shortest-job-first-or-sjf-cpu-scheduling/&hl=pt&sl=en&tl=pt&client=srp —

Executa primeiro o processo com menor tempo estimado de CPU. É provadamente ótimo para minimizar o waiting time médio — mas requer conhecimento prévio do tempo de execução, o que raramente é possível.

  Processos: P1(6ms), P2(8ms), P3(7ms), P4(3ms)

  FCFS:  |─ P1(6) ─|── P2(8) ──|─ P3(7) ─|─P4(3)─|
        Waiting médio: (0+6+14+21)/4 = 10.25ms

  SJF:   |P4(3)|─ P1(6) ─|─ P3(7) ─|── P2(8) ──|
        Waiting médio: (0+3+9+16)/4 = 7ms  ← ótimo
Enter fullscreen mode Exit fullscreen mode

Na prática, SJF inspira heurísticas usadas em load balancers e connection schedulers: redirecionar requisições para o worker que deve terminar mais rápido (least-connections, por exemplo).

Algoritmos para Interactive Systems

Sistemas interativos — onde se encaixam a maioria das aplicações backend — priorizam response time e fairness.

Round-Robin (RR)

Detalhe completo no link https://www.geeksforgeeks.org/operating-systems/round-robin-scheduling-in-operating-system/

Cada processo recebe um quantum (timeslice) fixo de CPU. Ao esgotar o quantum, é preemptado e colocado no final da fila.

Quantum = 4ms
Processos: P1(24ms), P2(3ms), P3(3ms)

|─P1(4)─|P2(3)|P3(3)|─P1(4)─|─P1(4)─|─P1(4)─|─P1(4)─|P1(4)|
0        4     7    10      14      18      22      26    30

P2 termina em t=7  (vs t=27 no FCFS)
P3 termina em t=10 (vs t=30 no FCFS)
Enter fullscreen mode Exit fullscreen mode

O Round-Robin é a base conceitual sobre a qual o CFS do Linux foi construído — embora o CFS use uma abordagem muito mais sofisticada baseada em virtual runtime.

A escolha do quantum é crítica:

  • Muito pequeno (< 1ms): overhead de context switch domina — a CPU gasta mais tempo trocando de processo do que executando
  • Muito grande (> 100ms): degenera para FCFS — processos interativos sofrem
  • Regra empírica: 80% dos CPU bursts devem ser menores que o quantum

Priority Scheduling

Detalhe completo no link https://www.geeksforgeeks.org/operating-systems/priority-scheduling-in-operating-system/

Cada processo recebe uma prioridade. O processo de maior prioridade executa primeiro.

Prioridades (menor número = maior prioridade):

Prioridade 1: ├── Kernel threads (interrupts, softirqs)
Prioridade 2: ├── Processos real-time (SCHED_FIFO, SCHED_RR)
              │   └── Exemplo: audio processing, controle industrial
Prioridade 3: ├── Processos normais com nice negativo
              │   └── Exemplo: nginx worker com nice -5
Prioridade 4: ├── Processos normais (nice 0)
              │   └── Exemplo: sua API Python/Go/.NET
Prioridade 5: └── Processos de baixa prioridade (nice positivo)
                  └── Exemplo: backup, log rotation
Enter fullscreen mode Exit fullscreen mode

O problema fundamental do priority scheduling é o starvation: processos de baixa prioridade podem nunca executar se processos de alta prioridade estão sempre prontos.

Algoritmos para Real-Time Systems

Sistemas real-time precisam de garantias temporais — deadlines que devem ser cumpridos.

Rate Monotonic Scheduling (RMS)

Atribui prioridade fixa inversamente proporcional ao período da tarefa. Tarefas com períodos menores (mais frequentes) recebem prioridade mais alta.

Earliest Deadline First (EDF)

Prioridade dinâmica: o processo com deadline mais próximo executa primeiro. Teoricamente ótimo — pode atingir 100% de utilização de CPU.

Conexão com o kernel: O Linux suporta escalonamento real-time via SCHED_FIFO, SCHED_RR e, a partir do kernel 3.14, SCHED_DEADLINE (baseado em EDF). Embora a maioria das aplicações backend não precise de real-time, entender essas classes é importante para diagnosticar problemas quando um processo real-time inadvertidamente monopoliza CPU.

Escalonamento Preemptivo vs Não-Preemptivo

A distinção entre escalonamento preemptivo e não-preemptivo é fundamental para entender o comportamento do Linux:

Não-preemptivo (cooperativo): O processo mantém a CPU até voluntariamente liberá-la (terminar, bloquear em I/O, ou ceder via yield()). Simples, mas um processo mal-comportado pode monopolizar a CPU.

Preemptivo: O kernel pode forçar a remoção de um processo da CPU a qualquer momento (tipicamente quando seu timeslice expira ou um processo de maior prioridade fica pronto). Mais complexo, mas garante responsividade.

Não-preemptivo:
P1 (CPU-bound, buggy): |████████████████████████████████████████|
P2 (sua API):          |░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░|  ← nunca executa!

Preemptivo (quantum = 10ms):
P1: |████|    |████|    |████|    |████|    |████|
P2:      |████|    |████|    |████|    |████|
          ↑ kernel preempta P1
Enter fullscreen mode Exit fullscreen mode

O Linux é totalmente preemptivo no userspace — o kernel pode preemptar qualquer processo em modo usuário a qualquer momento. O kernel em si tem diferentes níveis de preempção configuráveis:

Configuração Comportamento Uso típico
PREEMPT_NONE Kernel não-preemptivo Servidores de throughput máximo
PREEMPT_VOLUNTARY Preempção em pontos explícitos Default na maioria das distros server
PREEMPT_FULL Kernel totalmente preemptivo Desktop, baixa latência
PREEMPT_RT Real-time, preempção determinística Sistemas embarcados, áudio profissional

Implicação prática: Distros server como Ubuntu Server e RHEL usam PREEMPT_VOLUNTARY por default. Se sua aplicação precisa de latência ultra-baixa (ex: trading), pode ser benéfico usar um kernel com PREEMPT_FULL ou PREEMPT_RT.

Implicação prática: Imagens docker que utilizam o kernel do host herdam a configuração de preempção do host. Portanto, mesmo dentro de um container, o comportamento de escalonamento é ditado pelo kernel do host.

Problema da Inversão de Prioridade

A inversão de prioridade ocorre quando um processo de alta prioridade é indiretamente bloqueado por um de baixa prioridade, violando a política de escalonamento.

Cenário clássico (Mars Pathfinder, 1997):

Prioridade Alta (H):   Task meteorológica (deadline crítico)
Prioridade Média (M):  Task de comunicação (longa)
Prioridade Baixa (L):  Task de coleta de dados

Sequência do problema:
1. L adquire mutex M₁
2. L é preemptado por H
3. H tenta adquirir M₁ → bloqueado (L detém M₁)
4. M fica pronto e executa (maior prioridade que L)
5. M executa por tempo arbitrário
6. H continua bloqueado — inversão de prioridade!

Timeline:
L:  |██|      |░░░░░░░░░░░░░░░░|██|──unlock──|
M:  |  |      |████████████████|  |           |
H:  |  |██|→blocked            |  |           |██████|
         ↑                                     ↑
    tenta lock                            finalmente executa
Enter fullscreen mode Exit fullscreen mode

Soluções:

  • Priority Inheritance: Quando H bloqueia em um lock detido por L, L temporariamente "herda" a prioridade de H, impedindo que M execute no meio. O kernel Linux implementa isso para rt_mutex.
  • Priority Ceiling: O mutex recebe a prioridade do processo de maior prioridade que pode usá-lo. Qualquer processo que adquire o mutex tem sua prioridade elevada ao ceiling.

Implicação prática: Em Go, a inversão de prioridade pode ocorrer entre goroutines quando uma goroutine de alta prioridade (tratando request HTTP) bloqueia em um sync.Mutex detido por uma goroutine de baixa prioridade (fazendo log assíncrono), enquanto goroutines de prioridade média consomem os threads do runtime. O scheduler do Go não implementa priority inheritance — é responsabilidade do desenvolvedor minimizar a contenção de locks.

Starvation e Aging

Starvation ocorre quando um processo nunca recebe CPU porque processos de maior prioridade estão sempre prontos. Em sistemas com priority scheduling puro, processos de baixa prioridade podem ser indefinidamente postergados.

Starvation:
Tempo →  0    10    20    30    40    50    60    70    80
Prio 1:  |████|████|████|████|████|████|████|████|████|
Prio 2:  |░░░░|░░░░|░░░░|░░░░|░░░░|░░░░|░░░░|░░░░|░░░░|  ← nunca executa!
Enter fullscreen mode Exit fullscreen mode

Aging é a solução clássica: a prioridade de um processo aumenta gradualmente quanto mais tempo ele espera na ready queue. Eventualmente, mesmo o processo de menor prioridade terá prioridade suficiente para executar.

Aging:
Tempo →  0    10    20    30    40    50    60
Prio P2: 10   11    12    13    14    15    16  ← agora compete com Prio 1!
                                          |████| P2 finalmente executa
Enter fullscreen mode Exit fullscreen mode

O CFS do Linux implementa uma forma sofisticada de aging através do virtual runtime: processos que receberam menos CPU têm vruntime menor e são naturalmente favorecidos pelo escalonador. Isso torna starvation virtualmente impossível no CFS.

Como o Linux Implementa Escalonamento: Visão Geral

O escalonador do Linux organiza os algoritmos em scheduling classes, cada uma implementando uma política diferente:

Hierarquia de Scheduling Classes (maior → menor prioridade):

    ┌─────────────────────────────────────────────┐
    │  stop_sched_class                           │ ← Migration threads (interno)
    ├─────────────────────────────────────────────┤
    │  dl_sched_class (SCHED_DEADLINE)            │ ← EDF: deadline-based
    ├─────────────────────────────────────────────┤
    │  rt_sched_class (SCHED_FIFO,SCHED_RR)       │ ← Real-time: prioridade fixa
    ├─────────────────────────────────────────────┤
    │  fair_sched_class (SCHED_NORMAL,SCHED_BATCH)│ ← CFS: a maioria dos processos
    ├─────────────────────────────────────────────┤
    │  idle_sched_class (SCHED_IDLE)              │ ← Executa apenas quando nada mais
    └─────────────────────────────────────────────┘

O kernel percorre as classes de cima para baixo.
Se uma classe de maior prioridade tem um processo pronto, ele executa.
Enter fullscreen mode Exit fullscreen mode

Para a vasta maioria das aplicações backend, os processos rodam na classe fair_sched_class com política SCHED_NORMAL. É aqui que o CFS (Completely Fair Scheduler) — e seu sucessor EEVDF no kernel 6.6+ — opera.

Prioridades e Nice Values

O Linux mapeia o conceito de prioridade em dois espaços numéricos:

Nice values (userspace):     -20 ────────── 0 ────────── +19
                              ↑ maior prio   normal      ↑ menor prio

Static priority (kernel):     100 ─────────120─────────── 139
                              ↑ nice -20   nice 0        ↑ nice +19

Real-time priorities:         0 ──────────────────────── 99
                              ↑ menor prio rt            ↑ maior prio rt
Enter fullscreen mode Exit fullscreen mode 
# Executando um processo com prioridade alterada
$ nice -n -5 python3 app.py          # maior prioridade (precisa de root para nice < 0)
$ nice -n 10 python3 batch_job.py    # menor prioridade

# Alterando prioridade de processo em execução
$ renice -n -5 -p 1350               # aumenta prioridade do PID 1350

# Verificando nice value
$ ps -eo pid,ni,comm | grep python
1350  -5 python3
1400  10 python3
Enter fullscreen mode Exit fullscreen mode

Dica prática: Em um servidor que roda tanto APIs quanto batch jobs, use nice para dar menor prioridade aos batch jobs. Isso garante que suas APIs mantêm boa responsividade mesmo durante processamento pesado em background.

Métricas de Escalonamento na Prática

Para avaliar como o escalonamento afeta sua aplicação, monitore estas métricas:

# Context switches do sistema (total)
$ vmstat 1
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 3  0      0 245612  45632 1234567    0    0     5    12  256 4521 15  3 80  2  0
                                                           ↑    ↑
                                                     interrupts  context switches

# Context switches por processo
$ cat /proc/<pid>/status | grep ctxt
voluntary_ctxt_switches:    15230
nonvoluntary_ctxt_switches: 892

# Run queue length (processos aguardando CPU)
$ cat /proc/loadavg
2.15 1.80 1.45 3/412 28503
↑    ↑    ↑    ↑
1m   5m   15m  running/total

# Latência de escalonamento com perf
$ perf sched latency
-------------------------------------------------
  Task                  |   Runtime ms  | Switches | Avg delay ms |
-------------------------------------------------
  python3:1350          |    1052.340   |    15230 |    0.045     |
  dotnet:950            |     876.230   |     8920 |    0.032     |
  nginx:601             |     234.120   |    42310 |    0.012     |
Enter fullscreen mode Exit fullscreen mode

A coluna Avg delay ms no perf sched latency mostra quanto tempo, em média, o processo esperou na ready queue antes de ser escalonado. Valores altos indicam contenção de CPU.

# Visualizando scheduling events em tempo real
$ perf sched record -- sleep 10    # grava 10 segundos
$ perf sched map                   # mapa visual de scheduling

# Exemplo de saída:
#           *A0          . .  .  .  .  .  .    846.275762 secs A0 => python3:1350
#            A0          *B0 .  .  .  .  .     846.275800 secs B0 => nginx:601
#            A0           B0 *C0 .  .  .  .    846.275845 secs C0 => postgres:1500
#           *A0           B0  C0 .  .  .  .    846.275900 secs
#            A0          *B0  C0 .  .  .  .    846.275950 secs
Enter fullscreen mode Exit fullscreen mode

Continua nos próximos capítulos... :D
Conteudo parcialmente gerado com auxilio de IA generativa (eu organizei o conteudo e ela me ajudou com lero lero, novos tempos kkkk)

Referencias Bibliográficas

Top comments (0)