Linux CFS Scheduler Optimization for Android Systems: Weight, Fairness, and Group Scheduling Challenges

This article explores Linux kernel thread scheduling mechanisms with a focus on Android system requirements. It explains fundamental scheduling concepts including sched class (CFS and RT scheduling classes), runqueue management using red-black trees for CFS threads, sched latency (thread waiting time), and sched slice (execution time per invocation).

The core of CFS scheduling revolves around weight-based fairness. Each thread has a nice value that maps to a weight, determining both time slice allocation and virtual runtime (vruntime) growth. The weight calculation formula is: weight = 1024 / (1.25 ^ nice) . Higher weight threads get larger time slices and slower vruntime accumulation, enabling wakeup preemption when the difference exceeds a granularity threshold.

Despite CFS's fair scheduling design, Android still faces challenges: long-running threads accumulate vruntime making them vulnerable to preemption, and time slices are limited within each scheduling period. Android optimizes critical threads by assigning them to real-time scheduling class (surfaceflinger, hw-composer) or lower nice values (-16 for audio, -10 for UI/Render, -2 to -4 for system_server locks).

With GKI (Generic Kernel Image) enabling group scheduling ( CONFIG_FAIR_GROUP_SCHED ), Android organizes threads into groups: root, top-app, foreground, background. This creates a hierarchical structure where time slices are allocated top-down. However, group scheduling introduces problems: vruntime compensation for individual tasks becomes ineffective since the scheduler must first select the group at the top-level cfs_rq; nice values have different effects across hierarchy levels; and threads in the same group share the group's share value, causing key threads' time slices to be affected by unrelated threads in the same group.

Experimental results demonstrate these issues: with all threads at nice=0, root group threads receive double the time slice of tmp group threads (6.7ms vs 3.3ms); even when setting top_0 to nice=-10 (high priority), it only gets 4.7ms compared to root_0's 5.3ms, showing that priority adjustments within groups are severely limited.