Por Dentro do Kernel: O Scheduler 'Completely Fair' do Linux

O seu computador está mentindo para você: ele finge que faz mil coisas ao mesmo tempo, mas na verdade ele só alterna entre elas tão rápido que seu cérebro não percebe. O maestro dessa ilusão é o Scheduler do Linux, a peça de código que decide, em microssegundos, quem merece a CPU agora.

Por 15 anos, um algoritmo chamado CFS governou o mundo digital usando uma elegante árvore matemática para garantir a "justiça" entre os processos. Mas o jogo mudou. Vamos abrir o capô do Linux para entender como essa engrenagem invisível funciona, como ela moldou a internet moderna e por que ela acaba de ser substituída por algo ainda mais inteligente.

Parte 1: A Guerra dos Schedulers (O(1) vs SD)

Antes do CFS (antes de 2007), o Linux usava o O(1) Scheduler, criado por Ingo Molnar. Ele era focado em Big Iron (servidores gigantes). Ele usava filas de prioridade fixas e heurísticas complexas para "adivinhar" se um processo era interativo (como um editor de texto) ou numérico (como uma renderização de vídeo).

• Problema: As heurísticas erravam. Às vezes, o Linux achava que seu mouse era um processo de fundo e a interface travava enquanto compilava código.

Um anestesista australiano e hacker nas horas vagas, Con Kolivas, ficou frustrado com a performance do Linux no desktop. Ele escreveu seu próprio scheduler, o RSDL (Rotating Staircase Deadline), focado em "Fairness" (Justiça) em vez de throughput bruto. Ele argumentava que um usuário humano prefere que uma compilação demore 10% a mais, desde que o mouse não trave.

Isso gerou uma "guerra civil" na lista de e-mails do Kernel. Linus Torvalds foi bombardeado. A resposta de Ingo Molnar foi criar o CFS, inspirado nas ideias de Kolivas, mas implementado de forma modular e limpa. Em 62 horas, Ingo escreveu o código que governaria o mundo pelos próximos 15 anos.

Parte 2: A Matemática da Justiça (vruntime)

A filosofia do CFS é simples: Modelar uma "CPU Ideal e Perfeita". Em uma CPU Ideal (hardware infinitamente paralelo) com 2 processos, cada processo receberia 50% de força física o tempo todo, em paralelo perfeito. Como CPUs reais não funcionam assim (elas precisam alternar no tempo), o CFS mede o Erro entre a realidade e o ideal.

O Conceito de vruntime (Virtual Runtime)

Para cada processo (chamado de task_struct), o kernel mantém um contador chamado vruntime.

• O vruntime é o tempo físico (nanossegundos) que o processo passou rodando na CPU, normalizado pelo número de processos totais e seu peso.
• Se um processo roda, seu vruntime aumenta.
• Se um processo espera, seu vruntime fica parado.

A regra de ouro do CFS é: "A tarefa com o MENOR vruntime é a que sofreu a maior injustiça. Ela merece a CPU agora."

O objetivo do Kernel é manter o vruntime de todas as tarefas igual, em uma linha reta perfeita.

/*
 * Representação Abstrata da Lógica
 */
update_curr(cfs_rq) {
    time_elapsed = now() - curr_task.start_time;
    // O vruntime cresce mais devagar para tarefas importantes
    curr_task.vruntime += time_elapsed * (NICE_0_LOAD / curr_task.load.weight);
}

Parte 3: A Estrutura de Dados (Red-Black Tree)

Como encontrar a tarefa com o menor vruntime eficientemente entre 10.000 tarefas? Uma lista encadeada ordená-la seria lenta (O(N)). O CFS usa uma Árvore Binária de Busca Balanceada (Red-Black Tree), ordenada pelo vruntime.

• Esquerda da Árvore: Tarefas "famintas" (baixo vruntime). Precisam de CPU.
• Direita da Árvore: Tarefas "cheias" (alto vruntime). Já rodaram bastante.

Operação pick_next_task(): O scheduler não precisa procurar. Ele simplesmente pega o nó mais à esquerda da árvore (rb_leftmost). Essa operação é quase instantânea (O(1) com cache do ponteiro leftmost).

Operação put_prev_task(): Quando a tarefa atual esgota seu tempo (time slice), o scheduler:

1. Atualiza seu vruntime (somando o tempo que rodou).
2. Remove ela da posição atual na árvore.
3. Reinsere ela na árvore na nova posição (provavelmente mais à direita, já que o vruntime cresceu).
4. Pega a nova tarefa mais à esquerda.

Parte 4: O Peso das Prioridades (Nice Values)

O Unix tem o conceito de "Nice" (gentileza).

• Nice 0: Padrão.
• Nice -20: Alta prioridade (pouco gentil com os outros).
• Nice +19: Baixa prioridade (muito gentil).

No CFS, o "Nice" não dá mais tempo de CPU magicamente. Ele altera a velocidade do relógio vruntime.

• Para um processo de Alta Prioridade (-20), o vruntime passa em câmera lenta. Ele pode rodar 10ms físicos, mas o scheduler conta apenas 5ms virtuais. Isso faz com que ele avance pouco na árvore (ficando à esquerda) e seja escolhido de novo mais rápido.
• Para um processo de Baixa Prioridade (+19), o vruntime é acelerado. 1ms físico conta como 10ms virtuais. Ele é jogado para o fundo da árvore (direita) rapidamente.

Isso é genial porque o algoritmo de escolha (pegar o mais à esquerda) nunca muda. Apenas a métrica de tempo é distorcida pela prioridade.

Parte 5: Latência vs Throughput (O Dilema)

A grande configuração do CFS é o sched_latency_ns. Digamos que seja 24ms (milissegundos). O CFS promete que todo processo rodará pelo menos uma vez dentro dessa janela de 24ms.

• Se tens 2 processos: Cada um roda 12ms.
• Se tens 4 processos: Cada um roda 6ms.

Mas e se tiveres 100 processos? 24ms / 100 = 0.24ms. Trocar de contexto (Context Switch) a cada 0.24ms é ineficiente. A CPU passaria mais tempo trocando caches do que rodando código. Por isso existe o sched_min_granularity_ns (ex: 3ms). O scheduler diz: "Desculpe, não vou cortar fatias menores que 3ms, senão o computador para". Nesse caso, a latência alvo de 24ms é estourada.

Parte 6: O Futuro (EEVDF)

Em 2023/2024, a comunidade do Kernel começou a substituir o CFS por um novo algoritmo: EEVDF (Earliest Eligible Virtual Deadline First). Anunciado por Peter Zijlstra, o EEVDF resolve um problema que o CFS tinha com aplicações sensíveis a latência (como jogos e áudio).

O CFS focava em "Justiça Média" ao longo do tempo. Mas às vezes, um processo precisa de "Injustiça Agora" (preciso rodar AGORA senão o áudio falha) e promete devolver o tempo depois. O CFS era ruim nisso. Pessoas usavam truques sujos (chrt) para contornar o CFS.

O EEVDF introduz o conceito de deadline virtual. O processo diz: "eu preciso de 5ms de CPU e tenho que receber isso até o tempo T+20". O scheduler agora tenta honrar esses prazos explícitos, eliminando a necessidade de heurísticas complexas de latência. O Kernel 6.6 já trouxe essa mudança, marcando o fim da era CFS.

Apêndice Técnico A: Glossário do Escalonamento

Para tunar seu servidor, você precisa falar a língua do Kernel.

Apêndice Técnico B: Guia de Tuning (sysctl)

Você pode alterar o comportamento do scheduler em tempo real escrevendo em /proc/sys/kernel/sched_.

Comando para ver seus valores:

sysctl kernel.sched_latency_ns
sysctl kernel.sched_min_granularity_ns

Apêndice Técnico C: A Estrutura de Dados Real

Para os programadores C, é assim que o sched_entity se parece no código fonte (include/linux/sched.h). Note como ele é embutido dentro da task_struct.

struct sched_entity {
    /* For load-balancing: */
    struct load_weight		load;
    unsigned long			runnable_weight;
    
    /* Red-Black Tree node: */
    struct rb_node			run_node;
    
    /* List head for when not on RB-Tree: */
    struct list_head		group_node;
    
    /* Current state: */
    unsigned int			on_rq;
    
    /* The Magic Numbers: */
    u64						exec_start;
    u64						sum_exec_runtime;
    u64						vruntime;    // <--- O REI
    u64						prev_sum_exec_runtime;

    u64						nr_migrations;

#ifdef CONFIG_FAIR_GROUP_SCHED
    int						depth;
    struct sched_entity		*parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq			*cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq			*my_q;
#endif
    // ...
};

Apêndice Histórico: Cronologia dos Schedulers

• Linux 1.2 (1995): Scheduler circular simples. Ineficiente para muitos processos.
• Linux 2.4 (2001): O(N) Scheduler. Percorria a lista toda para achar o melhor. Lento em servidores grandes.
• Linux 2.6.0 (2003): O(1) Scheduler (Ingo Molnar). Rápido, mas complexo e injusto em desktops.
• Linux 2.6.23 (2007): CFS (Completely Fair Scheduler). Introdução da Red-Black Tree.
• Linux 3.14 (2014): Deadline Scheduler (sched_dl) adicionado para tarefas de tempo real rígido.
• Linux 6.6 (2023): EEVDF começa a substituir o CFS. A era do vruntime simples termina, entra a era do Deadline Virtual.

Perguntas Frequentes (FAQ)

Q: Qual a diferença para o Scheduler do Windows? R: O Windows NT usa um scheduler baseado em prioridades dinâmicas e Multilevel Feedback Queues. Se um processo usa muita CPU, sua prioridade cai. Se ele espera muito I/O (mouse), sua prioridade sobe (Quantum Boosting). O Windows favorece explicitamente a "responsividade da GUI" em detrimento da justiça matemática pura. O CFS é mais "científico", o Windows é mais "pragmático para desktop".

Q: O que é kernel -rt (Real Time)? R: Existe um patch chamado PREEMPT_RT que transforma o Linux em um Sistema de Tempo Real (Hard Real-Time). Ele muda travas (spinlocks) para mutexes preemptíveis e força as interrupções a rodarem como threads. Isso garante que, se um robô industrial precisa mover um braço em exatos 1ms, o Linux vai obedecer, parando tudo o resto. O CFS padrão não garante isso (Soft Real-Time).

Q: Mudar o "Nice" do meu jogo faz ele rodar mais rápido? R: Depende. Se sua CPU está 100% ocupada (Gargalo de CPU), sim. Dar nice -10 vai fazer o CFS dar mais prioridade de tempo para o jogo em detrimento do Chrome ou Discord. Se sua CPU está sobrando (Gargalo de GPU), o nice não faz nada, pois o scheduler já estaria dando todo o tempo que o jogo pede de qualquer forma.

Q: Por que Árvore Vermelho-Preta e não AVL? R: Árvores AVL são mais rigidamente balanceadas, o que torna a busca rápida, mas a inserção/remoção mais lenta (mais rotações). No kernel, processos acordam e dormem o tempo todo (muitas inserções/remoções). A RB-Tree é um compromisso melhor: um pouco menos balanceada, mas muito mais rápida para alterar.

Conclusão

Sistemas Operacionais são a arte de gerenciar escassez. Nunca haverá CPU suficiente para todos. O CFS nos ensinou que a melhor maneira de gerenciar essa escassez não é com regras rígidas feitas à mão ("dê prioridade ao vídeo"), mas com modelos matemáticos elegantes que buscam a justiça ideal. Ele serviu bem por 15 anos, mas como tudo na tecnologia, sua hora chegou. O EEVDF é a próxima fronteira.

Referências Bibliográficas

1. Robert Love. "Linux Kernel Development, 3rd Edition".
2. Kernel.org Documentation. "CFS Scheduler Design".
3. LWN.net. "The EEVDF Scheduler". Artigos técnicos detalhados sobre a transição.
4. Tanenbaum. "Modern Operating Systems". Teoria clássica de escalonamento.

Este artigo foi expandido em Dezembro de 2025 para incluir a transição histórica para o EEVDF.