关于任务调度的数据结构问题

lxy572535121

我们知道linux内核中是以task_struct来存储每一个进程的相关信息的
在CFS（completely fair schedule）调度中是以红黑树的形式来连接每一个进程的task_struct的
但是同时每一个task_struct又通过list_head以双向循环链表的形式来连接
我想问的就是既然有了红黑树，为何还要以双向循环链表的形式来连接每个task_struct
求解答

blake326

回复 1# lxy572535121

ｒｂｔｒｅｅ给ｃｆｓ　ｓｃｈｅｄｕｌｅ使用，取ｌｅｆｔｍｏｓｔ，ｉｎｓｅｒｔ,delete都很快。

list其他场景使用，比如for_each_task

pqy330

回复 2# blake326

啥？ｃｆｓ　ｓｃｈｅｄｕｌｅ不是也要同时更新两种数据结构吗？不然rb tree 跟list就不同步了啊

blake326

回复 3# pqy330

只有ｒｕｎｎｉｎｇ状态（等待ｃｐｕ执行）的ｔａｓｋ才会再ｒｂｔｒｅｅ上。
更精确一点，　正在cpu上执行的ｔａｓｋ是不在ｒｂｔｒｅｅ上的，但是on_rq, on_cpu都是等于１的。