本文转载自微信公众号《人人都是极客》，作者布道者Peter。转载本文请联系大家是极客公众号。调度发展历史领域版本O(n)schedulerlinux0.11-2.4O(1)schedulerlinux2.6CFSschedulerlinux2.6tonowO(n)scheduler是kernel2.4及更早版本使用的一种算法，其调度算法为非常简单直接。就绪队列是一个全局列表，从就绪队列中搜索下一个最佳任务。由于每次都需要遍历系统中的所有任务（全局列表）寻找下一个任务，所以称为是O(n)调度器（时间复杂度）。Kernel2.6使用O(1)调度程序，允许每个CPU维护自己的就绪队列，从而减少锁竞争。就绪队列由两个优先级数组组成，活跃优先级数组和过期优先级数组。每个优先级数组包含140个优先级队列，即每个优先级对应一个队列，其中前100个对应实时进程，后40个对应普通进程。如下图所示：这种设计的好处，调度器选择下一个被调度任务变得更加高效和简单，只需要在activepriority数组中选择一个高优先级，且队列中有可运行的任务即可。这里用一个位图来定义队列中是否有可运行的任务，如果有，则将位图中对应的位设置为1。这样，选择下一个被调用任务的时间就变成了查询任务的操作位图。但是，上述算法存在一个问题。高优先级的多线程应用程序将比低优先级的单线程应用程序获得更多的资源。这将导致低优先级应用程序在调度周期内无响应。直到高优先级应用程序结束。CFS调度器从一视同仁的角度解决了这个问题，保证每个任务在一个调度周期内都有机会执行，执行时间的长短取决于任务的权重。下面我们来详细了解一下CFS调度器是如何动态调整任务运行时间来实现公平调度的。实际运行时间CFS是CompletelyFairScheduler的缩写，即完全公平调度器。CFS调度器与以往调度器的区别在于没有时间片的概念，而是公平分配CPU使用的时间。例如：2个相同优先级的进程运行在一个cpu上，那么每个进程将分配50%的cpu运行时间。这就是要达到的公平。但在现实中，一定有的进程的优先级高，有的进程的优先级低。CFS调度器引入了权重的概念，权重代表进程的优先级，每个进程根据权重比例分配CPU时间。例如：2个进程A和B，A的权重为1024，B的权重为2048，则A获得cpu的时间比例为1024/(1024+2048)=33.3%。进程B获得的CPU时间比例为2048/(1024+2048)=66.7%。引入权重后，分配给进程的时间计算公式为：实际运行时间=调度周期*进程权重/所有进程权重之和。CFS调度器使用nice值来表示优先级，取值范围为[-20,19]，nice与权重是一一对应的关系。值越小，优先级越高，权重值越大。nice值与权重的换算关系：constantsched_prio_to_weight[40]={/*-20*/88761,71755,56483,46273,36291,/*-15*/29154,23254,18705,14949,11916,/*-10*/9548,7620,6100,4904,3906,/*-5*/3121,2501,1991,1586,1277,/*0*/1024,820,655,526,423,/*5*/335,272,215,172,137,/*10*/110,87,70,56,45,/*15*/36,29,23,18,15,};数组值计算公式是的：weight=1024/1.25nice。公式中1.25的值是基于这样一个事实，即进程每将nice值减少一个，它就会多获得10%的CPU时间。公式是根据1024的权重计算的。1024的权重对应nice值0，它的权重叫做NICE_0_LOAD。默认情况下，大部分进程的权重基本都是NICE_0_LOAD。Virtualruntime根据上面的理解，这里举个例子。如果一个CPU的调度周期为6ms，进程A和B的权重分别为1024和820（nice值为0和1），那么进程A得到的运行时间为6x1024/(1024+820)=3.3ms，而进程B得到的执行时间为6x820/(1024+820)=2.7ms。进程A的cpu使用率为3.3/6x100%=55%，进程B的cpu使用率为2.7/6x100%=45%。（符合上面所说的“每个进程减少nice值，都会多获得10%的CPU时间”）显然，两个进程的实际执行时间是不相等的，但是CFS要保证的运行时间每个过程都是平等的。所以CFS引入了虚时间的概念，就是说上面的2.7ms和3.3ms可以通过公式换算得到相同的值，这个换算后的值就叫做虚时间。这种情况下，CFS只需要保证各个进程运行的虚拟时间相等即可。虚拟时间vriture_runtime与实际时间（walltime）的换算公式如下：虚拟运行时间=实际运行时间*NICE_0_LOAD/进程权重=（调度周期*进程权重/所有进程权重之和）*NICE_0_LOAD/进程权重=调度周期*1024/所有进程的总权重从公式可以看出，在一个调度周期内，所有进程的虚拟运行时间是相同的。因此，在进程调度时，只需要找到虚拟运行时间最小的进程进行调度运行即可。为了快速找到虚拟运行时间最小的进程，Linux内核使用红黑树来保存可运行进程。CFS跟踪调度实体sched_entity的虚拟运行时间vruntime，通过enqueue_entity()和dequeue_entity()将sched_entity出列到红黑树中。vruntime较少的调度实体sched_entity安排在红黑树的左侧。如上图所示，红黑树的左节点比父节点小，而右节点比父节点大。所以在寻找最小节点的时候，只需要得到红黑树最左边的节点即可。相关步骤如下：在每个sched_latency周期内，根据每个任务的权重值，可以计算出运行时间runtime；运行时runtime可以转换为虚拟运行时vruntime；根据虚拟运行时间的大小，插入到CFS红黑树中，虚拟运行时间少的调度实体放在左边；调度下一个任务时，选择虚拟运行时间少的调度实体运行（pick_next_task从就绪队列中选择最合适的调度实体，即虚拟时间最小的调度实体）；CFS数据结构task_struct：task描述符，里面包含了很多进程相关的信息，比如优先级、进程状态、调度实体等。structtask_struct{...structsched_entityse;...}cfs_rq：跟踪就绪队列信息和管理就绪状态调度实体，维护一个按虚拟时间排序的红黑树。tasks_timeline->rb_root是红黑树的根，tasks_timeline->rb_leftmost指向红黑树中最左边的调度实体，即虚拟时间最小的调度实体。strucctcfs_rq{...structrb_root_cachedtasks_timeline...};sched_entity：可被内核调度的实体。每个就绪状态调度实体sched_entity包含插入红黑树的节点rb_node，vruntime成员记录已经运行的虚拟时间。structsched_entity{...structrb_noderun_node;...u64vruntime;...};这些数据结构之间的关系如下图所示：CFS算法实现1.时钟中断scheduler_tick更新虚拟运行时间，检查是否需要抢占。更新运行时的各种统计信息，如vruntime、运行时间、负载值、权重值等。检查是否需要抢占，主要是比较运行时间是否耗尽，vruntime的差值是否大于运行时间.2、任务出队入队当任务进入可运行状态时，使用enqueue_task_fair将调度实体放入红黑树中，完成入队操作；当任务退出可运行状态时，使用dequeue_task_fair将调度实体从红黑树队列中移除，完成出队操作；团队运作。调用__enqueue_entity函数后，可以将进程调度实体插入到运行队列的红黑树中。同时，红黑树的最左节点会缓存在运行队列的rb_leftmost字段中，以快速获取下一个可运行进程。从cfs_rq中获取下一个可运行任务每当进程任务切换时，即执行schedule函数时，调度器需要选择下一个要执行的任务。在CFS调度器中，是由pick_next_task_fair函数完成的，其本质是从就绪队列中选择最合适的调度实体（虚拟时间最小的调度实体）。
