当红黑树遇上Linux内核：系统调度的奥秘

点击蓝字  立即关注

当红黑树遇上Linux内核：系统调度的奥秘

“小张，这次用户反馈咱们的服务响应特别慢，CPU使用率也不高，你看看是咋回事？”

“好嘞，我看看…”小张打开系统监控，发现进程调度这块有点问题。这让他想起上周组长说过，Linux系统调度用的是红黑树，当时没太在意，这会儿正好补补这块知识。

红黑树是个啥？

说白了，红黑树就是个不会失衡的二叉搜索树。它通过给树的节点染色（红色或黑色）来保持平衡，就像玩跷跷板一样，两边的重量要差不多才不会一头沉。

咱们写个简单的红黑树节点结构看看：

struct rb_node {
unsigned long rb_parent_color；
struct rb_node *rb_right；
struct rb_node *rb_left；
}；

看着挺简单吧？但这里面藏着个小机灵，rb_parent_color这个变量既保存了父节点指针，又保存了节点颜色。CPU访问内存是要花时间的，这么设计能省下不少时间。

Linux调度器咋用红黑树？

Linux用红黑树来管理进程的优先级。每个进程都有个优先级值，值越小优先级越高，越容易被调度执行。

struct task_struct {
volatile long state； // 进程状态
int prio； // 动态优先级
struct rb_node run_node； // 红黑树节点
// ... 其他字段
}；

温馨提示：Linux里的进程其实都是用task_struct表示的，进程和任务是一个意思。

调度的黑魔法

当一个进程要进入运行队列时，调度器会根据它的优先级，把它插入到红黑树中的合适位置。这个过程有点像排队买奶茶，VIP用户直接去前面排，普通用户只能乖乖排后面。

static void enqueue_task(struct rq *rq， struct task_struct *p， int flags)
{
// 计算优先级
p->prio = normal_prio(p)；
// 插入红黑树
rb_insert_color(&p->run_node， &rq->tasks_timeline)；
}

调度器选择下一个要运行的进程时，就从红黑树最左边的节点开始找。为啥是最左边？因为红黑树是按优先级排序的，最左边的节点优先级最高。

性能有多快？

红黑树的操作时间复杂度都是O(log n)，n是节点数量。打个比方，就算系统里有1000个进程，也只需要动10次左右就能找到该执行哪个。

小张琢磨明白这些，赶紧检查了系统的进程优先级设置，发现有几个关键进程的nice值设置过高，调整之后，服务响应时间一下子就正常了。

“组长，我找到问题了！”小张美滋滋地汇报工作成果，顺便还跟组长说起自己对红黑树和调度器的新认识。

以后再遇到类似的性能问题，小张就知道该从哪些方面入手了：优先级设置、进程状态、调度策略，这些都是值得注意的点。

代码里还有个骚操作：

static inline struct task_struct *rb_entry_task(struct rb_node *node)
{
return container_of(node， struct task_struct， run_node)；
}

这个宏能从红黑树节点找到对应的进程结构体，用的是指针运算，贼快！

Linux内核中类似这样的技巧还有不少，每次看都有新发现。对了，调度器中的红黑树并不是一成不变的，它会随着进程的创建、退出、优先级变化而动态调整，保证系统运行效率。

点赞

分享

在看

留言