本文分为概述、历史、el7.2代码架构图解三部分。

解决的问题：

　　a.Kernel调度发展过程；

　　b.以架构图的方式，详解el7.2具体调度实现、内核线程模型、调度时间片计算，以及探究整个Kernel实际运行过程。

 

1.概述

    现代操作系统，通过虚拟化CPU及内存，来达到最大化硬件能力的目的

        a.内存虚拟化：

            每个task都有自己独立的虚拟内存地址空间，然后映射到physical memory；实际内存总量是一定的，为了使多个程序同时、正常的运行起来，每个task虚拟内存都从0x0000开始，当程序被载入内存中时，才在物理内存管理表中，建立虚拟内存和物理内存的关系，task运行时实际是CPU在物理内存上进行指令运算、存取。

            好比桌子上有一堆huge水果，但是你只有一个small篮子，为了让每个huge水果被食用时，都是通过篮子装载的，只有在食用时，才从桌子上把huge水果放到篮子的固定位置，提供给你食用。

        b.CPU虚拟化：

            每个task并不是一直独占CPU，而是将CPU按照时钟频率进行划分，通常HZ为1000，每个获取执行权限的task执行一个时序，而从在秒级层面看来，本时间段中，有多个task获得执行，达到模拟并行的效果。

            这个过程和现实中人做事情一样，每一个固定时间段，精力集中在一件事上，但是一整天，咱并行做了很多任务。

    CPU调度的难点在于必须使高、低优先级的task都得到执行，并且交互式task必须在50-150ms中得到执行。

 

2.历史

   a.0.01版

        最初的调度系统中，只有一个处理队列，并且循环不断的从其中取出要执行的task。

        在那个年代，最多能执行的task总数为NR_TASKS=32；并且从那时起就引入了执行task状态RUNNING、INTERRUPTIBLE、UNINTERRUPTIBLE的概念；同时，提出了按照优先级和时间片来决定next exec task，这一schedule核心的思想，贯穿了整个Kernel的发展。

    

    b.O(n) Scheduler in Version 2.4

        简单粗暴的将系统的一段时间划分给系统上所有task，以保证在这段时间（lifetime生命周期）内所有进程得到执行；

        在这段时间末尾，有些task的timeslice未用完，则将其值的一半加到下一个时间段中

        其显著缺点是耗费太多时间在选择要执行的task上，并且对real-time task支持不好

 

    c.O(1) in early versionf of 2.6 kernel

        由于其显著的选择goodness task速度及对real-time的支持，很快便取代了O(n) Scheduler

        i.从全局进行priority规划，0-139共140个等级，数字越小，优先级越高；同时，对real-time和normal task的等级区间进行了规划，即0-99作为real-time task专用区间，100-139作为normal task区间；

        ii.CPU抢占思想的提出，当有task进入TASK_RUNNING时，并根据其与当前task优先级大小（current——调度系统中指向当前执行进程的宏，非常重要），决定是否调用schedule()——调用此方法，会重新选择执行task，以达到高优先级抢占低优先级task CPU的目的；

        iii.根据task的交互程度动态调整task优先级；

        iv.为real-time设计了静态优先级。

        

        设计：

        i.为避免每次选择执行task时，遍历所有task，这里使用两个数组来装载task——active and expired array（list），从active array中取出task进行执行，task耗尽分配的时间后，放入expired array。

        ii.将active及expired array按照140个优先级进行划分，这样每个active或expired数组都是二维数组——含有140个元素，每个元素都是一个list；并且持有一个bitmap，用来标识140个list中，哪个list有task

        经此设计，每次schedule()先查bitmap，从低位开始，从有task的list中取出task来执行，而优先级一致的task按序执行即可，从而实现了O(1)的调度速度。

        iii.使用task's sleep time来标记交互式task，active array根据sleep time进行排序，这块非常复杂，且容易异常情况态度，会导致各种各样问题。

 

    d.内核调度分支——The Staircase Scheduler

        核心思想是在c的基础上，高优先级task执行一次后，其优先级减1，并放入对应array中，等待下次执行。

 

    e.Default Scheduler CFS——Completely Fair Scheduler For Normal Task

        提出了根据不同类型task使用不同的调度策略的思想，real-time task使用“kernel-3.10.0-327.el7/linux-3.10.0-327.el7.centos.x86_64/kernel/sched/rt.c”进行调度，而normal task则使用fair.c进行调度；fair.c即是CFS的实现，针对的是normal task的调度，其思想是"根据one normal task's weight占total normal task weight总和百分比来决定CPU使用率，达到了理想的高度精确的多任务调度：

        i.重新设计的优先级，引入nice的概念，范围为[-20,19]，值越小，获得CPU使用率越大；

        ii.理想的按nice数值控制的CPU使用率，即nice每上升1，则少获取10%CPU；为达到精确控制，设计了prio_to_weight数组（见下图），只有两个nice为0的进程为，每个进程CPU使用率占比都为1024/(1024+1024)；只有一个nice为0与1的进程是，nice为0进程CPU使用率为1024/(1024+820)=0.55，nice为1进程CPU使用率为0.45，两者的CPU使用率相差10%，

        iii.使用Red-Black Tree来存取task，每次调度时间复杂度为O(lgN)

        iv.内核层面的优先级仍然为0-140，0-99为real-time task，100-139为normal task，向上兼容real-time task的调度，通过将nice值加上120（120=real-time task优先级个数100+nice值个数40的一半）得到priority，而priority减去120得到nice

        v.同时引入按组调度的概念，整体CPU使用率按组进行划分（如只有GroupA与B时，GroupA与B各占50%使用率）

 

3.el7.2代码图解(入口为红色五角星)

 

 

 

 

4.参考资料：

　　http://www.linuxjournal.com/magazine/real-time-linux-kernel-scheduler?page=0,0

　　start_kernel():https://danielmaker.github.io/blog/linux/start_kernel.html

   　http://blog.csdn.net/hlchou/article/details/7425416

　　http://blog.csdn.net/gatieme/article/details/52067748系列

　　[个人博客Linux kernel部分调度]