c.进程调度的pick-next在BFS中,首先要调度的是抢占的进程,如果有进程抢占其它正在运行的进程,那么将它投入运行:
static inline struct task_struct *earliest_deadline_task(struct rq *rq, struct task_struct *idle) { unsigned long long_deadline, shortest_deadline; struct task_struct *edt, *p; unsigned int cpu = rq->cpu; struct list_head *queue; int idx = 0; if (rq->preempt_next) { //rq->preempt_next在try_preempt中设置 if (likely(task_queued(rq->preempt_next) && cpu_isset(cpu, rq->preempt_next->cpus_allowed))) { edt = rq->preempt_next; goto out_take; } } retry: idx = find_next_bit(grq.prio_bitmap, PRIO_LIMIT, idx); queue = &grq.queue[idx]; if (idx < MAX_RT_PRIO) { /* We found rt tasks */ list_for_each_entry(p, queue, run_list) { if (cpu_isset(cpu, p->cpus_allowed)) { edt = p; goto out_take; } } /* More rt tasks, we couldn't take the lower prio ones */ ++idx; goto retry; } /* No rt tasks, find earliest deadline task */ edt = idle; if (unlikely(idx >= PRIO_LIMIT)) { /* All rt tasks but none suitable for this cpu */ goto out; } long_deadline = shortest_deadline = longest_deadline() * 2 + 1; list_for_each_entry(p, queue, run_list) { unsigned long deadline_diff; /* Make sure cpu affinity is ok */ if (!cpu_isset(cpu, p->cpus_allowed)) continue; deadline_diff = p->deadline - jiffies; /* Normalise all old deadlines and cope with jiffy wrap. */ if (deadline_diff > long_deadline) deadline_diff = 0; /* Select the earliest deadline task now */ //简单的冒泡比较 if (edt == idle || deadline_diff < shortest_deadline) { shortest_deadline = deadline_diff; edt = p; } } if (edt == idle) { if (idx < IDLE_PRIO) { /* Haven't checked for SCHED_IDLEPRIO tasks yet */ idx++; goto retry; } goto out; } out_take: take_task(rq, edt); out: return edt; }
d.时间片用尽略......自己的体验费了九牛二虎之力,编译好了带有BFS的内核(实际上只是在2.6.32内核上打上了一个patch,然后重新编译内核而已,然而这个工作量不小,你可以试试...),基于Debian的桌面版本,硬件是在垃圾场淘的巨老无比的P4,效果十分可观,起码和Mac OS一样了,由此我再也不把RedHat的桌面看作可有可无的部分了。以前我总是编辑/etc/inittab文件将其启动到level 3,然后用ssh登录操作之,现在我也可以直接进level 5了,这就是BFS的效果。顺带说一句,如果你使用很高档或者比较高档的硬件,那么这个效果就不明显了,学子们注意了,别较真儿
听说Android使用了该调度器,我还没有尝试,因为我没有预算买设备。
3.更多的寓意写这篇文章的目的在于引出一些寓意,而不是介绍BFS调度器本身。该寓意在于,历史得看问题或许会更好。埋没在历史深处的事务并不一定是过时的,它可能是最能反映问题本质的,不要将其置之不顾,时不时地回头看一眼,有的时候,它会给你更多的思路。
所谓的操作系统进程调度就是为了让所有的CPU都动起来,这是一门艺术而不仅仅是一门技术。你既不能让CPU空闲,又不能让某些进程排队等待时间过长,这是一个CPU利用率和对待进程公平性的游戏。这才是问题的本质,而这个问题的本质在不同的硬件配置以及使用场景下又有不同的表现,因此调度器为了迎合这种差异巨大的不同的表现不可能做成一个统一的,只有具体问题具体分析才能得到良好的表现