返璞归真的Linux BFS调度器

自Linux 2.6以来(严格说应该是2.5)，O(n)调度器被人们认为是一种千年之前就应该抛弃的东西被重重的甩开了，此后出现了O(1)，CFS等，再也没人提起O(n)了。说实话，Linux的调度器远比标准Unix的来得复杂，因为Linux被用于不同的场合，从手机一直到大型服务器，跨度如此之大就需要兼各种情况，你既要使网络服务器的吞吐量达到最大，又要使交互体验更佳，然而有时候吞吐量和延迟却是鱼与熊掌的关系…

 O(n)被彻底遗忘，某种程度上反映了人们的思维误区，那就是“解决问题的方案随着问题的复杂化而复杂，殊不知方案复杂度的增加很多在于方案本身而不是问题”。走了这么多年，人们已然忘记了一样东西在刚出现时是什么样子了，随着时间的流逝，任何事物都会面目全非，于是人们“站在巨人的肩上”使其越来越复杂，最终崩溃…在路上，或者在崩溃前夕，如果能停下来寻找一下本源，返璞归真的东西也许更好，Con Kolivas研发了BFS调度器，正是循着这样的思路进行的，于是他为自己的调度器起了一个十分具有讽刺意义的名字：Brain Fuck …

1. static inline void enqueue_task(struct task_struct *p)  


2. {  


3.     if (idleprio_task(p) && !rt_task(p)) {  


4.         if (idleprio_suitable(p))  


5.             p->prio = p->normal_prio;  


6.         else  


7.             p->prio = NORMAL_PRIO;  


8.     }  


9.     if (iso_task(p) && !rt_task(p)) {  


10.         if (isoprio_suitable())  


11.             p->prio = p->normal_prio;  


12.         else  


13.         p->prio = NORMAL_PRIO;  


14.     }  


15.     __set_bit(p->prio, grq.prio_bitmap);  


16.     list_add_tail(&p->run_list, grq.queue + p->prio);  


17.     sched_info_queued(p);  


18. }  

1. static int try_to_wake_up(struct task_struct *p, unsigned int state)  


2. {  


3.     unsigned long flags;  


4.     int success = 0;  


5.     long old_state;  


6.     struct rq *rq;  


7.     rq = time_task_grq_lock(p, &flags);  


8.     old_state = p->state;  


9.     if (!(old_state & state))  


10.         goto out_unlock;  


11.     if (queued_or_running(p))  


12.         goto out_running;  


13.     activate_task(p, rq);  //调用enqueue_task  


14.     try_preempt(p, rq); //这里有一个O(m)时间复杂度的计算，m为cpu的个数  


15.     success = 1;  


16. out_running:  


17.     trace_sched_wakeup(rq, p, success);  


18.     p->state = TASK_RUNNING;  


19. out_unlock:  


20.     task_grq_unlock(&flags);  


21.     return success;  


22. }  

1. static inline struct  


2. task_struct *earliest_deadline_task(struct rq *rq, struct task_struct *idle)  


3. {  


4.     unsigned long long_deadline, shortest_deadline;  


5.     struct task_struct *edt, *p;  


6.     unsigned int cpu = rq->cpu;  


7.     struct list_head *queue;  


8.     int idx = 0;  


9.   


10.     if (rq->preempt_next) {  


11.         //rq->preempt_next在try_preempt中设置  


12.         if (likely(task_queued(rq->preempt_next) &&  


13.             cpu_isset(cpu, rq->preempt_next->cpus_allowed))) {  


14.                 edt = rq->preempt_next;  


15.                 goto out_take;  


16.         }  


17.     }  


18. retry:  


19.     idx = find_next_bit(grq.prio_bitmap, PRIO_LIMIT, idx);  


20.     queue = &grq.queue[idx];  


21.     if (idx < MAX_RT_PRIO) {  


22.         /* We found rt tasks */  


23.         list_for_each_entry(p, queue, run_list) {  


24.             if (cpu_isset(cpu, p->cpus_allowed)) {  


25.                 edt = p;  


26.                 goto out_take;  


27.             }  


28.         }  


29.         /* More rt tasks, we couldn’t take the lower prio ones */  


30.         ++idx;  


31.         goto retry;  


32.     }  


33.   


34.     /* No rt tasks, find earliest deadline task */  


35.     edt = idle;  


36.     if (unlikely(idx >= PRIO_LIMIT)) {  


37.         /* All rt tasks but none suitable for this cpu */  


38.         goto out;  


39.     }  


40.   


41.     long_deadline = shortest_deadline = longest_deadline() * 2 + 1;  


42.     list_for_each_entry(p, queue, run_list) {  


43.         unsigned long deadline_diff;  


44.         /* Make sure cpu affinity is ok */  


45.         if (!cpu_isset(cpu, p->cpus_allowed))  


46.             continue;  


47.   


48.         deadline_diff = p->deadline – jiffies;  


49.   


50.         /* Normalise all old deadlines and cope with jiffy wrap. */  


51.         if (deadline_diff > long_deadline)  


52.             deadline_diff = 0;  


53.   


54.         /* Select the earliest deadline task now */  


55.         //简单的冒泡比较  


56.         if (edt == idle || deadline_diff < shortest_deadline) {  


57.             shortest_deadline = deadline_diff;  


58.             edt = p;  


59.         }  


60.     }  


61.     if (edt == idle) {  


62.         if (idx < IDLE_PRIO) {  


63.             /* Haven’t checked for SCHED_IDLEPRIO tasks yet */  


64.             idx++;  


65.             goto retry;  


66.         }  


67.         goto out;  


68.     }  


69. out_take:  


70.     take_task(rq, edt);  


71. out:  


72.     return edt;  


73. }