Antes de começarmos, como é a primeira vez que falo sobre Kernel aqui, é importante explicar o que é um Kernel. O kernel é, em poucas palavras, o software que realiza a comunicação entre o hardware e o sistema operacional (SO), e é ele quem nos fornece uma camada de abstração para a comunicação com o hardware. Imagine o seguinte: você escreveu um programa simples na sua linguagem de programação favorita, e a única coisa que este programa faz é imprimir na tela “Hello World!”. Na maior parte das linguagens de programação isso gastaria algumas poucas linhas de código, o que para nós seres humanos, tem uma carga cognitiva minúscula. Mas o que está acontecendo por baixo dos panos é bem mais complexo do que isso, e é justamente o Kernel quem abstrai toda essa complexidade. Para você imprimir uma simples frase na tela, várias coisas precisam acontecer. Além da etapa de compilação que já falamos um pouco no último artigo, quando seu programa é executado, é criado um processo para ele. Através desse processo, ele entra em uma fila para ser executado (exatamente aqui que entra o scheduler, ele é o responsável por gerenciar o uso de CPU pelos processos abertos). Quando ele é escolhido para a execução, o endereço de memória da primeira instrução do seu programa é gravado no Program Counter do seu processador, a CPU executa a instrução neste endereço de memória e segue executando as instruções do seu programa até chegar na instrução para imprimir a mensagem na tela. Considerando que no seu programa você fez algo como printf("Hello World!"), o texto da frase ficou gravado no binário do programa na seção .rodata. Então para imprimir a CPU lê estes dados, envia para o barramento de dados para ser lido pela sua GPU, escreve isso em um framebuffer alocado na VRAM, o monitor lê esse framebuffer e finalmente desenha isso na tela.

Se isso pareceu um pouco mais complicado, é porque ainda sim eu abstrai do texto as particularidades do hardware. Como vimos no último artigo, todo hardware tem uma datasheet, que é um documento técnico que descreve os circuitos internos, com informações de cada componente como tensão elétrica, indutância, capacitância, resistência elétrica etc. Além disso, a datasheet nos informa também quais os terminais do hardware recebem e enviam quais tipos de informação. E pensando em kernel e firmwares no geral, o mais importante, nos informa quais endereços de memória devem ser usados para cada ação. Não adianta a CPU pegar os dados da frase a ser imprimida na tela, jogar no barramento de dados e seguir a vida. Essa informação deve ser escrita para um endereço específico para que essa ação aconteça corretamente. E isso vale para qualquer hardware e qualquer ação, não só o nosso monitor hipotético. Um “simples” printf() parece bem mais complexo agora, certo?

Quando falamos que o kernel é o software que faz a ponte entre o hardware e o sistema operacional, muitas vezes a complexidade do que ele faz fica muito implícita, como o que podemos ver nesse exemplo que eu trouxe, e ainda sim nem mesmo arranhamos a superfície desse tópico, que seriam necessários alguns livros inteiros para abordá-lo com profundidade. De qualquer forma, fiz uma introdução bem longa sobre o que é um kernel, e já podemos agora discutir o tema principal, o Scheduler.

Como disse, o kernel é responsável pela comunicação entre hardware e SO, e uma das partes mais importantes dele (a mais importante na minha opinião, por motivos que ficarão evidentes ao longo desse artigo), é o scheduler. Mas bem, o que é o scheduler? Para responder essa pergunta vou ilustrar um problema, assim como fiz nos parágrafos anteriores. Como disse antes, toda vez que você executa um software no seu computador, o kernel atribui a este software um process ID (PID). Todos os softwares rodando no espaço de usuário, ou ring 3 (entrarei mais em detalhes sobre arquitetura de rings em artigos futuros), possuem seu próprio PID. Isso independe se estes softwares foram executados por você, automaticamente ao inicializar a máquina ou executados por um terceiro software. E isso é necessário por uma razão simples: uma CPU antigamente conseguia executar uma única instrução de cada vez, apenas uma por ciclo, e embora CPUs modernas possuam recursos Simultaneous Multi-Threading como o hyper Threading dos processadores Intel, um computador mesmo que em stand-by possui centenas de processos ativos. Quando pensamos nisso, é natural nos perguntarmos algo como: então como é possível ter, no meu computador, diversos softwares sendo executados ao mesmo tempo? É exatamente aqui que o scheduler entra: o scheduler é, em poucas palavras, o software responsável por administrar o uso de CPU por cada processo, gerenciando com latência de microsegundos o uso do tempo de CPU por centenas de processos simultaneamente, garantindo que todos os processos ativos consigam utilizar a CPU de acordo com a prioridade e minimizando o impacto da troca de contextos na performance. Conforme discutido por Arpaci-Dusseau & Arpaci-Dusseau1 nos capítulos sobre escalonamento, o custo de um context switch envolve o salvamento e restauração do estado da CPU, incluindo registradores, program counter e TLB, podendo impactar significativamente a performance em sistemas com alta carga.

Ao compreendermos a função do scheduler conseguimos de imediato compreender como um computador consegue executar vários softwares “ao mesmo tempo”. A verdade é que ele está executando apenas um (ou alguns poucos, considerando tecnologias de SMT que citadas anteriormente), porém como o scheduler é capaz de alternar o uso de CPU entre milhares de processos em uma fração de segundos, temos a sensação de que são executados simultaneamente.

Agora que essa questão foi esclarecida, é natural que novas perguntas surjam. A mais importante é: mas como o scheduler organiza os processos e decide quem deve e quem não deve utilizar a CPU em um determinado momento?

Nota: As primeiras versões do kernel Linux e do Unix utilizavam algoritmos diferentes dos que são utilizados hoje. O scheduler do Kernel linux passou a utilizar o algoritmo conhecido como Completely Fair Scheduler em 2007, que embora tenha uma complexidade temporal de O(log n) de busca de processos na árvore red-black ele consegue dividir proporcionalmente o tempo de uso de CPU entre todos os processos, diferente do algoritmo anterior que, apesar de ser O(1) na busca de tarefas, utilizava uma janela de tempo baseada em prioridades, priorizando tarefas CPU-bound em detrimento das interativas, o que causava problemas de performance. Como o objetivo deste artigo não é discutir a história do scheduler e sim o que ele é e como funciona, focarei apenas no algoritmo utilizado nas versões modernas do kernel.2

Quando tomamos como exemplo o kernel Linux, o algoritmo utilizado atualmente pelo scheduler é conhecido como Completely Fair Scheduler (CFS). Esse algoritmo foca em distribuir o mais igualmente possível o tempo de uso de CPU entre todos os processos, e para isso ele organiza todos os processos em uma árvore Red-Black (Ou rubro negra, como a literatura brasileira prefere usar) baseando-se no Virtual Runtime (vruntime) de cada processo. O vruntime é, de forma simples, a quantidade de ciclos de CPU que um processo utilizou. Nesta árvore, os processos com menos vruntime são posicionados mais a esquerda, de maneira com que a árvore seja organizada com os processos que utilizaram menos vruntime para os que utilizaram mais, de maneira crescente, da esquerda para a direita. Quando o scheduler irá delegar o uso de CPU para um processo ele procura na árvore pelo processo com menos vruntime, ou seja, o mais a esquerda, e delega o uso de CPU para este processo. Na hora de trocar novamente de contexto ele interrompe este processo e salva seu estado, atualiza o vruntime e rebalanceia a árvore (como o vruntime deste processo agora é maior, ele será registrado na árvore mais a direita do que estava inicialmente) e então o processo é repetido. Um detalhe importante: o vruntime não é a medida de apenas uso de CPU, ele é uma medida ponderada que se baseia na prioridade dos processos. Em sistemas Unix e Unix-like (como o Linux) geralmente as prioridades (ou nice level) variam de -20 a 20, onde -20 é de prioridade crítica e 20 é o menos prioritário.

Figura 1: Representação de uma Red-Black tree com processos gerenciados pelo scheduler. Imagem retirada do portal da IBM. Fonte: https://developer.ibm.com/tutorials/l-completely-fair-scheduler/

cfsimg

Como uma cientista, o que mais me encanta na vida é que quando respondo uma pergunta, geralmente várias outras surgem. A primeira vez que estudei sobre o scheduler e entendi como ele gerenciava os processos, a primeira coisa que me veio a cabeça foi: mas como o algoritmo identifica o que está pronto para consumir CPU? Vamos tomar como exemplo um socket TCP. Imagina que você escreveu um programa que cria um socket TCP escutando na porta 3000, aguarda uma conexão e quando é realizada uma conexão ele escreve uma mensagem para o client, fecha o file descriptor da conexão e encerra a execução. Enquanto o seu software está aguardando uma conexão ele não está consumindo CPU. Na verdade ele não está fazendo nada, e delegar uso de CPU para ele nem mesmo faria sentido. Para lidar com estes casos, o scheduler possui uma tabela de status para os processos. Embora os nomes dos status sejam diferentes em cada kernel a funcionalidade é bem semelhante, então discutiremos aqui a lista de status do scheduler do kernel Linux:

TASK_RUNNING O processo está na runqueue (árvore do CFS) e apto a ser escalonado.
TASK_INTERRUPTIBLE Processo bloqueado (ex: aguardando I/O, socket, read() no disco). Ele é removido da runqueue e colocado em uma wait queue específica. Só acorda com um sinal ou quando o recurso fica disponível.
TASK_UNINTERRUPTIBLE (D-state) A versão “à prova de sinais” do bloqueio. Geralmente usada quando o processo espera I/O de disco diretamente. Um processo nesse estado não pode ser morto nem mesmo com um sinal da tabela de vetores de interrupção, como por exemplo um SIGKILL.
TASK_STOPPED / TASK_TRACED Pausado (ex: pelo debugger gdb).
EXIT_ZOMBIE O processo já terminou, mas o pai ainda não coletou o status (wait()).

Tabela 1: Status possíveis de um processo no scheduler.

Então no nosso exemplo do socket, enquanto o software estivesse aguardando uma conexão ele ficaria com o status TASK_INTERRUPTIBLE, e portanto fora da runqueue do scheduler. A parte mais interessante é que, enquanto na wait queue, este software não acumularia vruntime. Então ao receber uma conexão e voltar para TASK_RUNNING, como seu vruntime ficou congelado, ele estaria bem a esquerda na árvore, e portanto teria uma prioridade maior para uso de CPU.

Obrigada por lerem ate aqui! Neste artigo foi introduzido o CFS, mas ele é apenas uma das classes do scheduler, a SCHED_NORMAL. Existem outras classes como SCHED_FIFO e SCHED_IDLE, que serão abordadas em artigos futuros.

Bibliografia

  1. ARPACI-DUSSEAU, Remzi H.; ARPACI-DUSSEAU, Andrea C. Operating Systems: three easy pieces. [S.l.]: Arpaci-Dusseau Books, 2018. 676 p. ISBN 9781985086593. ↩

  2. Linux: The Completely Fair Scheduler. KernelTrap. 2007-04-19. Disponível em: https://web.archive.org/web/20070416040156/http://kerneltrap.org/. Acesso em: 2 aug 2026. ↩