如何修改CFS调度算法为随机调度算法

近来辅导本科生的操作系统实验课程，勾起了我对linux内核的无限兴趣。
其中有一个实验是要求修改Linux的内核调度算法为随机调度算法，当然不要求性能怎么样，只是作为熟悉调度算法的实验而已。
在2.6.22版本的内核之前（包含2.6.22），Linux主调度算法采用的是O(1)调度算法，这个算法修改成为随机调度算法相对简单，我已经在2.6.22内核上实现了。
大致就在linux/kernel/sched.c中的schedule(void)函数中增加一些代码：
asmlinkage void __sched schedule(void)
{
             ......

             idx = sched_find_first_bit(array->bitmap);
        
        /****************增加的代码********************/
        if(idx>=MAX_RT_PRIO)
        {
                int seed=jiffies;
                int mod=MAX_PRIO-MAX_RT_PRIO;
                seed=(seed+7)%mod;
                while(!test_bit(MAX_RT_PRIO+seed,(void *)&array->bitmap)){
                        seed=(seed+7)%mod;
                }
                idx=MAX_RT_PRIO+seed;
        }            /*******************************************/
        
        queue = array->queue + idx;

             ......
}
当然也只是对普通进程实现随机调度，实时进程依然优先调度。
这个重新编译内核，完美运行。

但是在2.6.23及其之后的内核版本，普通进程的调度采用了CFS的调度算法，该算法维护了一棵红黑树来选择下一运行的进程。
初步考虑后决定在linux/kernel/sched_fair.c中修改pick_next_task_fair函数来实现普通进程的随机调度。代码如下：
static struct task_struct *pick_next_task_fair(struct rq *rq)
{
        struct task_struct *p;
        struct cfs_rq *cfs_rq = &rq->cfs;
        struct sched_entity *se;

        if (unlikely(!cfs_rq->nr_running))
                return NULL;
        
            /*修改成随机调度*/
            int seed=jiffies;
        int mod=rb_count(&(cfs_rq->tasks_timeline));
        int idx=(seed+7)%mod;//伪随机数
        struct rb_node *idx_node=rb_first(&(cfs_rq->tasks_timeline));
        int i=0;
        while(i<idx)
        {
                idx_node=rb_next(idx_node);
                i++;
        }
        se=rb_entry(idx_node, struct sched_entity, run_node);
             //暂时忽略组调度
         /*
        do {
                se = pick_next_entity(cfs_rq);
                cfs_rq = group_cfs_rq(se);
        } while (cfs_rq);
             */
       
        p = task_of(se);
        hrtick_start_fair(rq, p);

        return p;
}


其中rb_count函数是在rbtree.c中增加的一个计算红黑树节点数的函数（去除根节点），实现如下（不考虑效率）：
/*
* This function returns the counts of rb_node in the tree.
*/
int rb_count(struct rb_root *root)
{
    if(!(root->rb_node))
return 0;

int count=0;
struct rb_node *first,*last,*node;
first=rb_first(root);
last=rb_last(root);
node=first;
do{
count++;
node=rb_next(node);
}while(node!=last);
return count;
}
EXPORT_SYMBOL(rb_count);
编译没有问题，但是开机引导内核时不成功
然后是：Kernel panic - not syncing: Attempted to kill init! 


望大神指点一下！

5 个解决方案

#1

这张图是开机引导时候的错误提示

#2

为什么是修改不是写一个新的模块加进去……简单算法最适合加进去了，彻底搞懂sched.c是怎么运作的。

#3

引用 2 楼 FancyMouse 的回复:

为什么是修改不是写一个新的模块加进去……简单算法最适合加进去了，彻底搞懂sched.c是怎么运作的。

老大。怎么增加一个算法，需要在task_struct中增加东西吗，刚入门不久，还不是太熟悉

#4

我当年学校里做os课的project是用的2.6.26-5，我们那时候还要求新算法还专门弄个调度组。所以基本上sched.h里面每个struct都给碰过一遍了。基本上做的事情还是比较常规的，每个struct里把新算法需要的数据放在里面，sched_class注册好，然后把sched_class里每个函数实现一遍就可以了。

国内课程实验怎么搞的我不懂，不过我是强烈建议弄个2~3礼拜的project当作业。这个真能学到很多东西。

然后是你的代码。粗看一眼我估计问题应该是这个。rb_count(&(cfs_rq->tasks_timeline))和rb_first(&(cfs_rq->tasks_timeline));这个tasks_timeline是struct rb_node？

#5

引用 4 楼 FancyMouse 的回复:

我当年学校里做os课的project是用的2.6.26-5，我们那时候还要求新算法还专门弄个调度组。所以基本上sched.h里面每个struct都给碰过一遍了。基本上做的事情还是比较常规的，每个struct里把新算法需要的数据放在里面，sched_class注册好，然后把sched_class里每个函数实现一遍就可以了。

国内课程实验怎么搞的我不懂，不过我是强烈建议……

嗯，我也在改变思路，不修改原来的fair调度了，想着添加一个随机调度class，正在慢慢搞，不知道何时有结果。
tasks_timeline在cfs_rq中定义为struct rb_root