CFS和老调度算法除了数据结构不同还有什么不同

mordorwww

1 都是基于各线程优先级和各线程已运行时间来选择要运行的进程
2 都支持可抢占调度
3 都是在tick中断里调度


两个调度方法在效果上有什么不同?

好像是cfs计算线程运行时间精确到纳秒，这个如果把老算法的计算线程运行时间精确也调整到纳秒不就OK？

而且这个精度又有什么意义呢？难道因为某个线程比别的线程多跑了一个纳秒就该把她踢下去换别的线程运行？

mordorwww

木有人鸟下，顶

mordorwww

再顶，没人回答这个问题么

Tinnal

回复 3# mordorwww

Linux 2.6 调度器简介(老的O（1）调度）
2.6 版本的调度器是由 Ingo Molnar 设计并实现的。Ingo 从 1995 年开始就一直参与 Linux 内核的开发。他编写这个新调度器的动机是为**、上下文切换和定时器中断开销建立一个完全 O(1) 的调度器。触发对新调度器的需求的一个问题是 Java™ 虚拟机（JVM）的使用。Java 编程模型使用了很多执行线程，在 O(n) 调度器中这会产生很多调度负载。O(1) 调度器在这种高负载的情况下并不会受到太多影响，因此 JVM 可以有效地执行。
2.6 版本的调度器解决了以前调度器中发现的 3 个主要问题（O(n) 和 SMP 可伸缩性的问题），还解决了其他一些问题。现在我们将开始探索一下 2.6 版本的调度器的基本设计。
主要的调度结构
首先我们来回顾一下 2.6 版本的调度器结构。每个 CPU 都有一个运行队列，其中包含了 140 个优先级列表，它们是按照先进先出的顺序进行服务的。被调度执行的任务都会被添加到各自运行队列优先级列表的末尾。每个任务都有一个时间片，这取决于系统允许执行这个任务多长时间。运行队列的前 100 个优先级列表保留给实时任务使用，后 40 个用于用户任务（参见图 1）。我们稍后将来看一下为什么这种区别非常重要。

图 1. Linux 2.6 调度器的运行队列结构

除了 CPU 的运行队列（称为活动运行队列（active runqueue））之外，还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后，它就被移动到过期运行队列（expired runqueue） 中。在移动过程中，会对其时间片重新进行计算（因此会体现其优先级的作用；稍后会更详细地介绍）。如果活动运行队列中已经没有某个给定优先级的任务了，那么指向活动运行队列和过期运行队列的指针就会交换，这样就可以让过期优先级列表变成活动优先级的列表。
调度器的工作非常简单：它在优先级最高的队列中选择一个任务来执行。为了使这个过程的效率更高，内核使用了一个位图来定义给定优先级列表上何时存在任务。因此，在大部分体系架构上，会使用一条 find-first-bit-set 指令在 5 个 32 位的字（140 个优先级）中哪一位的优先级最高。查找一个任务来执行所需要的时间并不依赖于活动任务的个数，而是依赖于优先级的数量。这使得 2.6 版本的调度器成为一个复杂度为 O(1) 的过程，因为调度时间既是固定的，而且也不会受到活动任务个数的影响。
更好地支持 SMP 系统
那么什么是 SMP 呢？SMP 是一种体系架构，其中多个 CPU 可以用来同时执行各个任务，它与传统的非对称处理系统不同，后者使用一个 CPU 来执行所有的任务。SMP 体系架构对多线程的应用程序非常有益。
尽管优先级调度在 SMP 系统上也可以工作，但是它这种大锁体系架构意味着当一个 CPU 选择一个任务进行分发调度时，运行队列会被这个 CPU 加锁，其他 CPU 只能等待。2.6 版本的调度器不是使用一个锁进行调度；相反，它对每个运行队列都有一个锁。这样允许所有的 CPU 都可以对任务进行调度，而不会与其他 CPU 产生竞争。
另外，由于每个处理器都有一个运行队列，因此任务通常都是与 CPU 密切相关的，可以更好地利用 CPU 的热缓存。
任务抢占
Linux 2.6 版本调度器的另外一个优点是它允许抢占。这意味着当高优先级的任务准备运行时低优先级的任务就不能执行了。调度器会抢占低优先级的进程，并将这个进程放回其优先级列表中，然后重新进行调度。


   

Tinnal

回复 3# mordorwww

和O1调度的区别
早期的 2.6 调度器，叫做 O(1) 调度器，它旨在解决 2.4 调度器存在的问题 — 该调度器不需要迭代整个任务列表来确定要调度的下一个任务（因此得名 O(1)，这意味着它效率更高，扩展性更好）。O(1) 调度器跟踪运行队列中可运行的任务（实际上，每个优先级水平有两个运行队列 — 一个用于活动任务，一个用于过期任务）， 这意味着要确定接下来执行的任务，调度器只需按优先级将下一个任务从特定活动的运行队列中取出即可）。 O(1) 调度器扩展性更好而且包含交互性，提供了大量启示用于确定任务是受 I/O 限制还是受处理器限制。 但是 O(1) 调度器在内核中很笨拙。需要大量代码计算启示，难以管理并且对于纯粹主义者而言未能体现算法的本质。

为了解决 O(1) 调度器面临的问题以及应对其他外部压力， 需要改变某些东西。这种改变来自 Con Kolivas 的内核补丁，其中包括他的 Rotating Staircase Deadline Scheduler (RSDL)， 这包含了他在 staircase 调度器方面的早期工作。这些工作的成果就是一个设计简单的调度器，包含了公平性和界限内延迟。 Kolivas 的调度器吸引了很多人（并且很多人呼吁将其包含在目前的 2.6.21 主流内核中），很显然调度器的变革即将发生。 Ingo Molnar，O(1) 调度器的创造者，然后围绕 Kolivas 的一些思想开发了基于 CFS 的调度器。我们来剖析一下 CFS，从较高的层次上看看它是如何运行的。

CFS 概述
CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器。分给某个任务的时间失去平衡时（意味着一个或多个任务相对于其他任务而言未被给予相当数量的时间），应给失去平衡的任务分配时间，让其执行。
要实现平衡，CFS 在叫做虚拟运行时 的地方维持提供给某个任务的时间量。任务的虚拟运行时越小， 意味着任务被允许访问服务器的时间越短 — 其对处理器的需求越高。CFS 还包含睡眠公平概念以便确保那些目前没有运行的 任务（例如，等待 I/O）在其最终需要时获得相当份额的处理器。
但是与之前的 Linux 调度器不同，它没有将任务维护在运行队列中，CFS 维护了一个以时间为顺序的红黑树（参见图 1）。 红黑树 是一个树，具有很多有趣、有用的属性。首先，它是自平衡的，这意味着树上没有路径比任何其他路径长两倍以上。 第二，树上的运行按 O(log n) 时间发生（其中 n 是树中节点的数量）。这意味着您可以快速高效地插入或删除任务。

图 1. 红黑树示例

任务存储在以时间为顺序的红黑树中（由 sched_entity 对象表示），对处理器需求最多的任务 （最低虚拟运行时）存储在树的左侧，处理器需求最少的任务（最高虚拟运行时）存储在树的右侧。 为了公平，调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。任务通过将其运行时间添加到虚拟运行时， 说明其占用 CPU 的时间，然后如果可运行，再插回到树中。这样，树左侧的任务就被给予时间运行了，树的内容从右侧迁移到左侧以保持公平。 因此，每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。


   

Tinnal

回复 1# mordorwww
以上的贴都是拷贝自IBM 网站。
下面这链接有详细的调度策略的变更历史和原因，我就不拷过来了。
http://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/


下面来回答你剩下的两个问题吧。
好像是cfs计算线程运行时间精确到纳秒，这个如果把老算法的计算线程运行时间精确也调整到纳秒不就OK？
从上面的链接你就能看到，调度算法是整个都变了，不是时间精度变化了。变迁的原因写得很清楚。
CFS的切换和精度其实一毛钱关系都没有，CFS要记录时间，而内核里头的时间单位一直是NS。不打开高精度时钟，还按原有的10ms一个tick，CFS也能运行的很好。并且，不打开高精度时钟是服务器Linux的标配（打开高精度时钟是桌面系统的标配）。
高精度时钟，是为了取消周期性时钟，调度精度和调度开销的矛盾而产生的。他不是一个周期性时钟。他是和CFS同时出来的姐妹技术。这样，对于交互程序来于，应用的相应会更加的“实时”。

而且这个精度又有什么意义呢？难道因为某个线程比别的线程多跑了一个纳秒就该把她踢下去换别的线程运行？
它达到的效果是，你要睡眠11ms，就让你睡眠11MS，而不是把TICK设为1MS。这个带来的价值是有好有坏的。这个和CFS没关。在服务器应用来于，业务都是一批一批处理的，吞吐量比相应时间更为重要，打开高精度时钟后，调度得更频繁了，调度开销变大了，因此是一件坏事。但对于桌面应用，响应时间比业务都为重要，你想想，本来你的程序都1ms看看有没有输入，用的是usleep(1000)，但你发现程序延时了10ms，你会不会觉得很郁闷。网上对应用程序的各种延时方法（usleep\select\nonosleep)的精度还写了很多文章，但于到根本，根在于内核的实现呀！！




   

mordorwww

定时器精度和调度精度有什么关系呢。定时器**进程后，进程可以马上抢占执行啊

Tinnal

回复 7# mordorwww

我不已经说了吗，高精度时钟和调度没有址接关系。高精度时钟与高进度定时器有关系，也就可以推导高精度定时器和调度没有直接关系！！
定时器到时了，进程是立马得到一个调度机会（不代表能立马调度运行）。
在低精度定时器是用jiffies来计算定时时间的，因此定时不准。因此，调度的时间就会受到牵连，这是一个间接的关系。


   

mordorwww

按照你上面个说法，那就不光是调度精度的问题了。如果可运行进程太多，cpu资源才那么点，调度精度高也没法保证定时器精度

mordorwww

所以我觉得不要搞太多进程线程。为这个还还刚从一家小屁公司吵架出来了。不知道java为马子要搞那么多线程