Chinaunix

标题: 关于任务调度的数据结构问题 [打印本页]

作者: lxy572535121 时间: 2018-03-31 19:45
标题: 关于任务调度的数据结构问题
我们知道linux内核中是以task_struct来存储每一个进程的相关信息的
在CFS（completely fair schedule）调度中是以红黑树的形式来连接每一个进程的task_struct的
但是同时每一个task_struct又通过list_head以双向循环链表的形式来连接
我想问的就是既然有了红黑树，为何还要以双向循环链表的形式来连接每个task_struct
求解答

作者: blake326 时间: 2018-04-02 10:27
回复 1# lxy572535121

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

list其他场景使用，比如for_each_task

作者: pqy330 时间: 2018-04-02 12:58
回复 2# blake326

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

作者: blake326 时间: 2018-04-02 16:34
回复 3# pqy330

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

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)