01 - Gerenciamento de Processos (scheduler, PID)

1. A Ontologia do Processo: A Estrutura task_struct

Na teoria de sistemas operacionais, um programa é uma entidade passiva (bytes repousando em um disco), enquanto um processo é a abstração de sua execução isolada. No âmago do Kernel Linux, a ilusão de concorrência e a materialização dessa entidade ativa dependem de uma única, massiva e complexa estrutura de dados em C chamada task_struct (definida primariamente em <linux/sched.h>).

Cada thread ou processo em execução no sistema possui exatamente uma instância alocada da task_struct na memória do Ring 0. Esta estrutura é formidável em tamanho (frequentemente ultrapassando 8 a 10 Kilobytes em arquiteturas de 64 bits modernas) e atua como o repositório central de todos os metadados vinculados à execução.

A task_struct não contém código de usuário em si, mas encapsula:

• Ponteiros de Memória (mm_struct): O mapa completo do espaço de endereçamento virtual da tarefa (Páginas, VMA - Virtual Memory Areas).

• Credenciais (cred): Estruturas que definem o UID, GID e capabilities (privilégios) do processo sob as leis do sistema de segurança (SELinux/AppArmor).

• Descritores de Arquivos (files_struct): A tabela de arquivos abertos, descritores de sockets e pipes interligados ao VFS.

• Contexto de CPU (thread_struct): Uma subestrutura altamente dependente da arquitetura (ex: x86_64) que armazena os registradores do processador (RSP, RIP, CR3) no exato momento em que a tarefa é removida do processador, permitindo a futura retomada perfeita.

Historicamente, o kernel alocava a task_struct no fundo da própria pilha de execução (kernel stack) da thread. Em designs contemporâneos e com a mitigação de exploits de stack overflow, a task_struct é alocada dinamicamente via Slab Allocator, enquanto apenas uma estrutura mínima (thread_info) permanece na base da pilha do kernel, contendo sinalizadores de preempção de baixo nível.

2. A Dualidade PID/TGID e a Resolução em Espaços de Nomes

O Linux original não possuía o conceito formal de threads em seu núcleo. A filosofia fundamental, introduzida na chamada de sistema clone(), é que uma thread é simplesmente um processo que escolhe compartilhar certas estruturas (como a mm_struct e a files_struct) com o processo que o criou.

No entanto, o padrão POSIX (pthreads) exige que todas as threads de um mesmo programa compartilhem o mesmo Identificador de Processo (PID). Para conciliar a visão do kernel (onde cada entidade executável é única) com o padrão POSIX, o Linux implementou a topologia de Grupo de Threads (Thread Groups).

Na task_struct, existem dois identificadores cruciais:

• pid (Process ID na visão interna): É o identificador exclusivo daquela estrutura de execução na tabela do kernel. Para o espaço do usuário, este valor é conhecido como TID (Thread ID).

• tgid (Thread Group ID): É o PID real retornado por funções POSIX como getpid(). Quando um processo principal invoca fork(), uma tarefa é criada onde pid == tgid. Quando esse processo cria threads secundárias via clone(), as novas task_structs recebem pid exclusivos, mas herdam o tgid do processo líder.

O Abismo dos PID Namespaces

A alocação de PIDs não é mais um vetor global simples de 1 a 32768. Com o advento dos contêineres (LXC, Docker), o kernel introduziu os PID Namespaces. A estrutura real é baseada no sistema Radix Tree / IDR (Integer ID Management).

Quando um processo está aninhado em um contêiner, ele possui múltiplas identidades. Uma estrutura struct pid no kernel mapeia o PID global verdadeiro (ex: 14502 no namespace raiz/host) para o PID virtualizado no namespace isolado (ex: PID 1 dentro do contêiner). As chamadas de sistema do processo traduzem essas identidades de forma transparente no Ring 0.

3. A Máquina de Estados Finita e as Wait Queues

O tempo de CPU é o recurso mais disputado do sistema. Um processo passa a esmagadora maioria de sua vida fora do processador. O kernel gerencia isso através de um campo volátil state na task_struct, governando a máquina de estados através das seguintes constantes fundamentais:

• TASK_RUNNING (R): O único estado elegível para execução. O processo está fisicamente computando na CPU ou aguardando em uma fila de execução (Runqueue) para ser escalonado.

• TASK_INTERRUPTIBLE (S - Sleeping): O processo está inerte, dormindo de forma superficial. Ele aguarda por um evento (entrada de dados de um socket, clique de mouse, ou um timer). Ele pode ser acordado prematuramente pela chegada de um sinal do sistema (ex: SIGINT).

• TASK_UNINTERRUPTIBLE (D): O estado de suspensão profunda e blindada. Ocorre quando a tarefa emite um pedido I/O crítico de hardware (ex: ler uma página direta do disco). Para evitar corrupção das estruturas de dados do VFS, a tarefa entra em estado D e não responderá a nenhum sinal, nem mesmo ao implacável SIGKILL. Processos "presos" em estado D aumentam o Load Average do sistema e, se bloqueados indefinidamente por hardware defeituoso, exigem reinicialização forçada.

• EXIT_ZOMBIE (Z): O processo encerrou sua execução voluntariamente (via exit()) ou morreu por uma exceção (Segfault). A memória (mm_struct), arquivos e recursos foram destruídos e devolvidos ao sistema. A única coisa que resta no kernel é o "esqueleto" da task_struct contendo o código de saída (Exit Status), aguardando que o processo pai realize a chamada de sistema wait() ou waitpid() para coletar os dados e expurgar a estrutura da tabela do kernel.

A transição para os estados de suspensão ocorre de forma determinística: o processo altera seu próprio state, insere um ponteiro de si mesmo em uma estrutura chamada Wait Queue associada ao recurso desejado (ex: o disco) e chama voluntariamente a função schedule() para abdicar do controle da CPU.

4. O Custo Físico da Preempção: A Comutação de Contexto (Context Switch)

Quando o timer tick do hardware interrompe a CPU ou quando uma tarefa bloqueia voluntariamente, o escalonador invoca a função macroarquitetural __schedule(), que eventualmente culmina em context_switch().

A troca de contexto é uma das operações de núcleo mais caras e agressivas na computação. É dividida em duas grandes fases sistêmicas:

1. A Comutação de Espaço Virtual (switch_mm): O kernel deve trocar a ilusão de memória. Ele lê o ponteiro do diretório de páginas do novo processo e o carrega no registrador de gerenciamento de memória do processador (CR3 em x86_64).

   • O Gargalo da TLB: Mudar o CR3 invalida historicamente toda a Translation Lookaside Buffer (TLB), o cache ultrarrápido do processador que traduz endereços virtuais para físicos. Para mitigar esse custo devastador, o Linux moderno utiliza o recurso de hardware PCID (Process-Context Identifiers), que etiqueta as entradas da TLB com o ID do processo, permitindo que a CPU evite o flush total da TLB durante o context switch.

2. A Comutação de Estado da CPU (switch_to): Esta fase ocorre em Assembly puro de nível abissal. O kernel salva o valor atual do ponteiro de pilha (RSP) do kernel, do ponteiro de instrução (RIP) e dos registradores de uso geral na estrutura thread_struct do processo que está saindo. Em seguida, injeta os valores salvos anteriormente do processo que está entrando nos registradores físicos da CPU. Ao finalizar a instrução ret (return), a CPU retoma a execução exatamente de onde o novo processo havia parado na última vez, ignorante ao fato de que outro código esteve rodando naquele mesmo núcleo de silício.

5. A Matemática da Justiça: O Escalonador (CFS e EEVDF)

O módulo que decide qual tarefa ocupará a CPU no próximo microssegundo não é um simples algoritmo Round-Robin. O código responsável pelo agendamento evoluiu drasticamente das tabelas O(n) nos anos 1990 para o lendário O(1) Scheduler (Linux 2.6) e depois para o padrão de fato da computação moderna em nuvem: O Completely Fair Scheduler (CFS).

A Mecânica do CFS (Completely Fair Scheduler)

O princípio algorítmico do CFS não é a alocação de "fatias de tempo" estáticas (timeslices). Em vez disso, ele tenta modelar uma "CPU ideal e infinitamente paralela".

Cada processo sob o domínio do CFS (classe SCHED_NORMAL) acumula uma métrica interna chamada vruntime (Virtual Runtime). O vruntime é o tempo real que o processo passou executando no processador, ponderado inversamente pela sua prioridade (o valor Nice).

• Se o processo A tem prioridade normal e roda por 10ms, seu vruntime aumenta em 10ms.

• Se o processo B tem alta prioridade (Nice -20), seu tempo conta de forma "mais lenta"; rolar por 10ms físicos pode aumentar seu vruntime em apenas 1ms.

Para rastrear essa métrica em tempo $O(\log N)$ para alocação e $O(1)$ para seleção, o CFS armazena todos os processos do sistema em uma Árvore Rubro-Negra (Red-Black Tree - rb_tree) auto-balanceável em memória, onde a chave de ordenação é o vruntime.

Quando o escalonador é acionado para escolher a próxima tarefa (pick_next_task), ele simplesmente extrai o nó mais à esquerda (leftmost node) da árvore Rubro-Negra. O nó mais à esquerda é sempre, por definição matemática, a tarefa com o menor vruntime (a que foi mais prejudicada/esfomeada de CPU até aquele momento). Quando a tarefa roda, seu vruntime aumenta. Se ela esgotar sua quota dinâmica, é inserida de volta na árvore, que se rebalanceia instantaneamente, deslocando o processo para a direita e permitindo que outra tarefa faminta atinja a posição extrema esquerda.

A Evolução do Estado da Arte: EEVDF

Embora o CFS tenha reinado absoluto desde o Linux 2.6.23, o kernel moderno (a partir do Linux 6.6) está orquestrando a substituição gradual do CFS pelo algoritmo EEVDF (Earliest Eligible Virtual Deadline First).

O EEVDF resolve o "problema da latência" crônico do CFS (onde tarefas que demandavam atenção urgente ocasionalmente sofriam jitter frente a tarefas devoradoras de CPU com baixo vruntime). O EEVDF calcula matematicamente uma "data de validade" (Virtual Deadline) para a necessidade de execução de um processo com base em sua quota contratual (lag/eligible time), fundindo heurísticas de agendamento de tempo real com os princípios de equidade (fairness) do CFS, eliminando parâmetros heurísticos em favor de provas matemáticas estritas.

6. Classes de Escalonamento e a Topologia Multicore (SMP/NUMA)

O escalonador central do Linux é modular, iterando através de Classes de Escalonamento hierárquicas. Antes do CFS sequer ter a chance de escolher um processo normal da árvore Rubro-Negra, o kernel avalia a classe Real-Time (RT).

• Classe RT (SCHED_FIFO e SCHED_RR): Projetada para tarefas críticas de áudio ou maquinário industrial. Tarefas RT possuem uma prioridade absoluta de 0 a 99 (enquanto as tarefas normais do CFS residem na prioridade 100 a 139). Se houver uma única tarefa RT pronta para executar na fila, ela preempciona e silencia todas as tarefas CFS simultaneamente, executando sem limite de quota até bloquear (I/O) ou terminar.

• Classe Deadline (SCHED_DEADLINE): A classe suprema do kernel, superando até mesmo a classe RT. Baseia-se no algoritmo Earliest Deadline First (EDF) e Constant Bandwidth Server (CBS). O processo assina um contrato matemático estrito com o kernel: "Eu preciso de 10ms de tempo de CPU a cada 50ms de tempo real absoluto", garantindo latências microsegundos sem matar o resto do sistema.

Runqueues Per-CPU e Work Stealing

Em sistemas de Multiprocessamento Simétrico (SMP) com dezenas de núcleos, utilizar uma única Árvore Rubro-Negra global destruiria o desempenho devido à contenção massiva de Spinlocks.

O Linux resolve isso implementando uma runqueue (rq) isolada para cada processador lógico (CPU0, CPU1, etc.). Cada núcleo gere sua própria máquina CFS independentemente.

Contudo, se a runqueue do núcleo 0 estiver sobrecarregada com 50 tarefas pesadas, e a runqueue do núcleo 1 estiver ociosa, a simetria de carga é quebrada. Para combater isso, threads especializadas de balanceamento (Load Balancers) despertam periodicamente nos bastidores. Elas analisam os domínios de agendamento (sched_domains), respeitando a arquitetura NUMA (Non-Uniform Memory Access). O balanceador rouba (Work Stealing) as task_structs da fila do núcleo sobrecarregado e as migra para o núcleo ocioso, otimizando o paralelismo do hardware, mas sofrendo a penalidade temporária do resfriamento dos caches L1/L2 na nova CPU.