返璞归真的Linux BFS调度器
返璞归真的Linux BFS调度器
自Linux 2.6以来(严格说应该是2.5)，O(n)调度器被人们认为是一种千年之前就应该抛弃的东西被重重的甩开了，此后出现了O(1)，CFS等，再也没人提起O(n)了。说实话，Linux的调度器远比标准Unix的来得复杂，因为Linux被用于不同的场合，从手机一直到大型服务器，跨度如此之大就需要兼各种情况，你既要使网络服务器的吞吐量达到最大，又要使交互体验更佳，然而有时候吞吐量和延迟却是鱼与熊掌的关系...
O(n)被彻底遗忘，某种程度上反映了人们的思维误区，那就是“解决问题的方案随着问题的复杂化而复杂，殊不知方案复杂度的增加很多在于方案本身而不是问题”。走了这么多年，人们已然忘记了一样东西在刚出现时是什么样子了，随着时间的流逝，任何事物都会面目全非，于是人们“站在巨人的肩上”使其越来越复杂，最终崩溃...在路上，或者在崩溃前夕，如果能停下来寻找一下本源，返璞归真的东西也许更好，Con Kolivas研发了BFS调度器，正是循着这样的思路进行的，于是他为自己的调度器起了一个十分具有讽刺意义的名字：Brain Fuck ...
0.小手段
计算机操作系统不是神，它们没有灵魂，然而作为一款通用操作系统，很多设计者都希望其兼顾所有的情况，既要满足桌面交互的低延迟需求，又要满足大吞吐量，同时又要支持N多个处理器，因此就需要做负载均衡...作为一个通用的调度器的设计，为了照顾这么多种情况，你不得不引入一些小巧的手段来专门照顾这些另类的需求。1.调度器回顾
O(n)调度器
Linux的初始版本使用的是O(n)调度器，它采用单一链表，用遍历比较的方式，采用冒泡算法进行pick-next，下课的原因在于：a.O(n)中的n吓倒了很多人，大家都不喜欢这个n，因为它的时间复杂度会随着进程数量的增加而增加
b.单一的队列，进程等待时间可能过长，造成饥饿
c.多处理器的出现，为了避免频繁锁定
d.它太简单了？玩弄高深的人不喜欢简单的东西？
O(1)调度器
2.6内核采用了O(1)调度器，该调度器引入了每CPU的优先级队列组，每组队列包含active和expire两个队列，采用启发式算法动态调整优先级，尽可能的进行时间片补偿和惩罚等动态计算，多CPU之间的优先级队列负载均衡。下课的原因有两点：1.启发式算法，补偿/惩罚机制过于复杂，导致算法本身消耗巨大；2.有了更好的CFS调度器。类“多级反馈队列”调度器
此调度器只以patch的形式存在，在并入mainline之前即被CFS取代。采用类似4.4BSD的传统UNIX调度算法，其优点在于免饥饿以及大吞吐量，这也正是UNIX的特点，缺点在于延迟不稳定，仍然需要一些“小手段”来“玷污”良好的设计。CFS调度器
该调度器于2.6.23被并入，旨在消除一切的“小手段”，采用完全公平的策略进行调度，引入了虚拟时钟的概念，进程的优先级以及性别(IO?Calc?交互性?)完全映射到虚拟时钟的速率上，基于虚拟时钟的补偿性调度。理论很美，然而为了支持SMP以及交互进程要求日益提高，仍然引入了“小手段”-睡眠补偿，调度域负载均衡等。接下来的调度器
一定要以一种彻底的方式消除那些“小手段”，“小手段”的引入完全是“兼顾所有情况”这种“鱼与熊掌可兼得”的思想造成的。如果我们回顾上述的调度器，就会发现从O(1)开始，基本都是拆东墙补西墙的方式，解决一个问题从而引入另一个问题。照此以往，事情会越来越复杂的。如果尝试在O(n)调度器的基础上优化，可能会更好，因为O(n)调度器最纯粹。2.BFS调度器的引入
给出一个图片
前些天突然在网上看到了下面的图片
后来发现该图片是BFS调度器的引子，太具有讽刺意义了。
|
评论暂时关闭