The Linux kernel's scheduler uses various algorithms to determine how processes share the CPU. The two most well-known approaches are CFS (Completely Fair Scheduler) and the older O(1) scheduler. How do these algorithms make decisions, and what factors (e.g., priority, load, interactivity) do they consider? Additionally, how are extra policies integrated for real-time tasks? How is performance impact measured across different workload scenarios? In your opinion, which is more flexible and sustainable?
How do scheduling algorithms work in the Linux kernel and what are the selection criteria?
👁️ 239 views💬 2 replies❤️ 0 likes
2 Replies
In real-world projects, I primarily control the response time of interactive processes by tuning CFS's `sched_latency_ns`, `sched_min_granularity_ns`, and weights. For tasks requiring strict latency, I directly enable the real-time scheduling class (SCHED_FIFO / SCHED_RR) and configure bandwidth limits in `rt_runtime_us` and `rt_period_us` to prevent RT tasks from monopolizing all CPUs. The core of CFS is the red-black tree (vruntime), which accumulates the virtual runtime of each process and prioritizes scheduling the process with the smallest vruntime—this is essentially a "fairness" cost function. In contrast, the O(1) scheduler uses a radix-heap to assign processes to fixed priority queues, offering O(1) scheduling overhead but lacking adaptability for long-running workloads.
During actual testing, I use `schedtool -R` / `taskset` to pin workloads to specific CPUs, then combine `perf`, `rtla` (Real-Time Latency Analyzer), or `kernelshark` to capture scheduling latency and context switch counts. I compare the average scheduling latency and throughput of the same workload under CFS and O(1) (switched via kernel compile options). Empirical results show that CFS performs more smoothly in multi-core and mixed I/O/CPU workloads, automatically adjusting the proportion of interactive processes. O(1) has a slight edge in extreme low-latency scenarios (e.g., kernel-level network forwarding), but requires manual tuning and struggles to adapt to evolving workloads.
Overall, unless your system has strict millisecond-level hard real-time constraints, I recommend sticking with the default CFS and using real-time scheduling classes for lightweight RT partitioning. This approach preserves the scheduler's adaptive capabilities while providing hard real-time guarantees when necessary.
In CFS, how exactly is the virtual runtime (vruntime) calculated based on a process's weight and actual runtime? And when real-time scheduling classes (like SCHED_FIFO, SCHED_RR) coexist with CFS, how does the kernel decide the switching strategy?