Linux CFS的RB树平衡管理函数是什么？调度器如何维持其有序？

Great question about the inner workings of Linux CFS's RB tree—let's unpack this clearly.

Why update_curr doesn't need to adjust the RB tree position #

Here's the key insight: the currently running task is not actually in the RB tree. The RB tree in CFS holds all tasks waiting to be scheduled (the runqueue's idle tasks and ready-to-run tasks). When a task is selected to run, it's removed from the RB tree first.

The update_curr function only updates the virtual runtime (vruntime) of the currently executing task. Since this task isn't in the RB tree while it's running, there's no need to check or adjust its position in the tree during these updates.

The RB tree order is maintained when the task is reinserted into the queue—this happens when:

• The task's time slice is exhausted
• The task is preempted by a higher-priority (lower vruntime) task
• The task voluntarily sleeps or blocks

At that point, the scheduler calls enqueue_entity, which handles inserting the task back into the RB tree at the correct position based on its updated vruntime. The insertion process automatically ensures the tree stays ordered.

Kernel functions for RB tree balancing in CFS #

Linux uses a set of generic RB tree utility functions to maintain balance, and CFS leverages these directly:

• rb_link_node: This function links the new node into the RB tree at the correct position determined by vruntime comparisons.
• rb_insert_color: After linking the node, this function performs the necessary rotations and color flips to restore RB tree balance properties. You'll find this called right after rb_link_node in CFS's __enqueue_entity helper function.
• rb_erase: When removing a task from the RB tree (like when it's selected to run), this function handles the removal and automatically rebalances the tree if needed.

These are generic kernel-wide RB tree functions, not CFS-specific—they're used across the kernel wherever RB trees are implemented.

内容的提问来源于stack exchange，提问作者Tyrann