A comparative analysis of scheduling algorithms in the linux kernel

Abstract

O escalonador de processos é um componente fundamental do kernel Linux, ditando diretamente a responsividade do sistema e a vazão global ao arbitrar o acesso à CPU entre processos concorrentes. Os escalonadores modernos enfrentam o desafio cen tral de equilibrar as demandas conflitantes de tarefas interativas sensíveis à latência e processos em lote orientados à vazão, um compromisso tornado mais complexo pela onipresença de arquiteturas multicore. Esta tese aborda esse desafio com o obje tivo de responder à seguinte pergunta: Qual é o impacto no desempenho do sistema ao executar cargas de trabalho idênticas sob diferentes políticas de escalonamento de tarefas do Linux? Este estudo vai além da discussão teórica ao conduzir uma série de benchmarks controlados em um único sistema de hardware. Um kernel Linux base é sistematicamente modificado para implementar e isolar diferentes algoritmos de escalonamento, incluindo o consolidado Completely Fair Scheduler (CFS) e o novo escalonador Earliest Eligible Virtual Deadline First (EEVDF). Uma suíte diversificada de cargas de trabalho, abrangendo cenários intensivos em CPU, intensivos em E/S e de uso misto, é executada em cada configuração de kernel. Indicadores-chave de de sempenho, como latência de tarefas, vazão total, justiça (fairness) e utilização da CPU, são meticulosamente medidos. O objetivo é fornecer evidências quantitativas e repro dutíveis dos compromissos de desempenho inerentes ao design de cada escalonador. Os resultados visam oferecer insights claros e baseados em dados sobre os pontos fortes e fracos práticos de cada política, fornecendo orientação para administradores de sistemas e desenvolvedores de kernel na seleção e ajuste de escalonadores para casos de uso específicos e reais.

The process scheduler is a fundamental component of the Linux kernel, directly dictat ing system responsiveness and overall throughput by arbitrating CPU access among competing processes. Modern schedulers face the core challenge of balancing the con flicting demands of latency-sensitive interactive tasks and throughput-oriented batch processes, a trade-off made more complex by the ubiquity of multi-core architectures. This thesis addresses this challenge through a direct, empirical analysis aimed at an swering the question: What is the impact on system performance when running iden tical workloads under different Linux task scheduling policies? This study moves be yond theoretical discussion by conducting a series of controlled benchmarks on a sin gle hardware system. A baseline Linux kernel is modified through systemic patching to implement and isolate different scheduling algorithms, including the long-standing Completely Fair Scheduler (CFS) and the recently introduced Earliest Eligible Virtual Deadline First (EEVDF) scheduler. A diverse suite of workloads, encompassing CPU bound, I/O-bound, and mixed-use scenarios, is executed on each kernel configuration. Key performance indicators such as task latency, total throughput, fairness, and CPU utilization are meticulously measured. The objective is to provide quantitative, repro ducible evidence of the performance trade-offs inherent to each scheduler’s design. The findings aim to offer clear, data-driven insights into the practical strengths and weaknesses of each policy, providing guidance for system administrators and kernel developers when selecting and tuning schedulers for specific, real-world use cases.