调度策略值得是大家都在ready时，并且CPU已经被调度时，决定谁来运行，谁来被调度。
两者之间有一定矛盾。
响应的优化，意味着高优先级会抢占优先级，会花时间在上下文切换，会影响吞吐。
上下文切换的时间是很短的，几微妙就能搞定。上下文切换本身对吞吐并多大影响， 重要的是，切换后引起的cpu 的 cache miss.
每次切换APP, 数据都要重新load一次。
Linux 会尽可能的在响应与吞吐之间寻找平衡。比如在编译linux的时候，会让你选择 kernal features -> Preemption model.
抢占模型会影响linux的调度算法。
所以 ARM 的架构都是big+LITTLE， 一个很猛CPU+ 多个 性能较差的 CPU, 那么可以把I/O型任务的调度 放在 LITTLE CPU上。需要计算的放在big上。
早期2.6 内核将优先级划分了 0-139 bit的优先级。数值越低，优先级越高。0-99优先级 都是 RT（即时响应）的 ，100-139都是非RT的，即normal。
调度的时候 看哪个bitmap 中的 优先级上有任务ready。可能多个任务哦。
在普通优先级线程调度中，高优先级并不代表对低优先级的绝对优势。会在不同优先级进行轮转。
100 就是比101高，101也会比102高，但100 不会堵着101。
众屌丝进程在轮转时，优先级高的：
初始设置nice值为0，linux 会探测 你是喜欢睡眠，还是干活。越喜欢睡，linux 越奖励你，优先级上升（nice值减少）。越喜欢干活，优先级下降（nice值增加）。所以一个进程在linux中，干着干着 优先级越低，睡着睡着 优先级越高。
后期linux补丁中
红黑树，数据结构， 左边节点小于右边节点
同时兼顾了 CPU/IO 和 nice。
数值代表着 进程运行到目前为止的virtual runtime 时间。
（pyhsical runtime） / weight * 1024(系数)。
优先调度 节点值（vruntime）最小的线程。权重weight 其实有nice 来控制。
一个线程一旦被调度到，则物理运行时间增加，vruntime增加，往左边走。
weight的增加，也导致vruntime减小，往右边走。
总之 CFS让线程 从左滚到右，从右滚到左。即照顾了I/O(喜欢睡，分子小) 也 照顾了 nice值低（分母高）.所以 由喜欢睡，nice值又低的线程，最容易被调度到。
自动调整，无需向nice一样做出奖励惩罚动作，个人理解权重其实相当于nice
但是 此时 来一个 0-99的线程，进行RT调度，都可以瞬间秒杀你！因为人家不是普通的，是RT的!
一个多线程的进程中，每个线程的调度的策略 如 fifo rr normal, 都可以不同。每一个的优先级都可以不一样。
实验举例, 创建2个线程，同时开2个：
运行2次，创建两个进程
sudo renice -n -5(nice -5级别) -g(global)， 会明显看到 一个进程的CPU占用率是另一个的 3倍。
为什么cpu都已经达到200%，为什么系统不觉得卡呢？因为，我们的线程在未设置优先级时，是normal调度模式，且是 CPU消耗型 调度级别其实不高。
利用chrt工具，可以将进程 调整为 50 从normal的调度策略 升为RT （fifo）级别的调度策略，会出现：
chrt , nice renice 的调度策略 都是以线程为单位的，以上 设置的将进程下的所有线程进行设置nice值
线程是调度单位，进程不是，进程是资源封装单位！
两个同样死循环的normal优先级线程，其中一个nice值降低，该线程的CPU 利用率就会比另一个CPU的利用率高。
② 为什么Linux CFS调度器没有带来惊艳的碾压效果| CSDN博文精选
任何领域，革命性的碾压式推陈出新并不是没有，但是概率极低，人们普遍的狂妄在于，总是认为自己所置身的环境正在发生着某种碾压式的变革，但其实，最终大概率不过是一场平庸。
作者 | dog250
责编 | 刘静
出品 | CSDN博客
但凡懂Linux内核的，都知道Linux内核的CFS进程调度算法，无论是从2.6.23将其初引入时的论文，还是各类源码分析，文章，以及Linux内核专门的图书，都给人这样一种感觉，即 CFS调度器是革命性的，它将彻底改变进程调度算法。 预期中，人们期待它会带来令人惊艳的效果。
然而这是错觉。
人们希望CFS速胜，但是分析来分析去， 却只是在某些方面比O(1)调度器稍微好一点点 。甚至在某些方面比不上古老的4.4BSD调度器。可是人们却依然对其趋之若鹜，特别是源码分析，汗牛塞屋！
为什么CFS对别的调度算法没有带来碾压的效果呢？
首先，在真实世界，碾压是不存在的，人与人，事与事既然被放在了同一个重量级梯队比较，其之间的差别没有想象的那么大，根本就不在谁碾压谁。不能被小说电视剧电影蒙蔽了，此外，徐晓冬大摆拳暴打雷雷也不算数，因为他们本就不是一个梯队。
任何领域，革命性的碾压式推陈出新并不是没有，但是概率极低，人们普遍的狂妄在于，总是认为自己所置身的环境正在发生着某种碾压式的变革，但其实，最终大概率不过是一场平庸。
最终就出现了角力，僵持。
其次，我们应该看到，CFS调度器声称它会给交互式进程带来福音，在这方面CFS确实比O(1)做得好，但是惊艳的效果来自于粉丝的认同。Linux系统交互进程本来就不多，Linux更多地被装在服务器，而在服务器看来，吞吐是要比交互响应更加重要的。
那么以交互为主的Android系统呢？我们知道，Android也是采用了CFS调度器，也有一些事BFS，为什么同样没有带来惊艳的效果呢？
我承认，2008年前后出现CFS时还没有Android，等到Android出现时，其采用的Linux内核已经默认了CFS调度器，我们看下Android版本，Linux内核版本以及发行时间的关系：
Linux内核在2.6.23就采用了CFS调度器。所以一个原因就是没有比较。Android系统上，CFS没有机会和O(1)做比较。
另外，即便回移一个O(1)调度器到Android系统去和CFS做AB，在我看来，CFS同样不会惊艳，原因很简单，Android系统几乎都是交互进程，却前台进程永远只有一个，你几乎感受不到进程的切换卡顿，换句话说，即便CFS对待交互式进程比O(1)好太多，你也感受不到，因为对于手机，平板而言，你切换 APP 的时间远远大于进程切换的时间粒度。
那么，CFS到底好在哪里？
简单点说，CFS的意义在于， 在一个混杂着大量计算型进程和IO交互进程的系统中，CFS调度器对待IO交互进程要比O(1)调度器更加友善和公平 。理解这一点至关重要。
其实，CFS调度器的理念非常古老，就说在业界，CFS的思想早就被应用在了磁盘IO调度，数据包调度等领域，甚至最最古老的SRV3以及4.3BSD UNIX系统的进程调度中早就有了CFS的身影，可以说，Linux只是 使用CFS调度器 ，而不是 设计了CFS调度器 ！
就以4.3BSD调度器为例，我们看一下其调度原理。
4.3BSD采用了1秒抢占制，每间隔1秒，会对整个系统进程进行优先级排序，然后找到优先级最高的投入运行，非常简单的一个思想，现在看看它是如何计算优先级的。
首先，每一个进程j均拥有一个CPU滴答的度量值Cj，每一个时钟滴答，当前在运行的进程的CPU度量值C会递增：
当一个1秒的时间区间ii过去之后，Cj被重置，该进程jj的优先级采用下面的公式计算：
可以计算，在一个足够长的时间段内，两个进程运行的总时间比例，将和它们的Base_PrioBase_Prio优先级的比例相等。
4.3BSD的优先级公平调度是CPU滴答驱动的。
现在看Linux的CFS，CFS采用随时抢占制。每一个进程j均携带一个 虚拟时钟VCj ，每一个时钟滴答，当前进程k的VCk会重新计算，同时调度器选择VC最小的进程运行，计算方法非常简单：
可见， Linux的CFS简直就是4.3BSD进程调度的自驱无级变速版本！
如果你想了解CFS的精髓，上面的就是了。换成语言描述，CFS的精髓就是 “ n个进程的系统，任意长的时间周期TT，每一个进程运行T/n的时间！ ”
当然，在现实和实现中，会有80%的代码处理20%的剩余问题，比如如何奖励睡眠太久的进程等等，但是这些都不是精髓。
综上，我们总结了：
所以无论从概念还是从效果，Linux CFS调度器均没有带来令人眼前一亮的哇塞效果。但是还缺点什么。嗯，技术上的解释。
分析和解释任何一个机制之前，必然要先问，这个机制的目标是什么，它要解决什么问题，这样才有意义。而不能仅仅是明白了它是怎么工作的。
那么Linux CFS调度器被采用，它的目标是解决什么问题的呢？它肯定是针对O(1)算法的一个问题而被引入并取代O(1)，该问题也许并非什么臭名昭着，但是确实是一枚钉子，必须拔除。
O(1)调度器的本质问题在于 进程的优先级和进程可运行的时间片进行了强映射！
也就是说，给定一个进程优先级，就会计算出一个时间片与之对应，我们忽略奖惩相关的动态优先级，看一下原始O(1)算法中一个进程时间片的计算：
直观点显示：
针对上述问题，2.6内核的O(1)O(1)引入了双斜率来解决：
直观图示如下：
貌似问题解决了，但是如果单单揪住上图的某一个优先级子区间来看，还是会有问题，这就是相对优先级的问题。我们看到，高优先级的时间片是缓慢增减的，而低优先级的时间片却是陡然增减，同样都是相差同样优先级的进程，其优先级分布影响了它们的时间片分配。
本来是治瘸子，结果腿好了，但是胳臂坏了。
本质上来讲，这都源自于下面两个原因：
固定的优先级映射到固定的时间片。
相对优先级和绝对优先级混杂。
那么这个问题如何解决？
优先级和时间片本来就是两个概念，二者中间还得有个变量沟通才可以。优先级高只是说明该进程能运行的久一些，但是到底久多少，并不是仅仅优先级就能决定的，还要综合考虑，换句话距离来说，如果只有一个进程，那么即便它优先级再低，它也可以永久运行，如果系统中有很多的进程，即便再高优先级的进程也要让出一些时间给其它进程。
所以，考虑到系统中总体的进程情况，将优先级转换为权重，将时间片转换为份额，CFS就是了。最终的坐标系应该是 权重占比/时间片 坐标系而不是 权重(或者优先级)/时间片 。应该是这个平滑的样子：
看来，Linux CFS只是为了解决O(1)O(1)中一个 “静态优先级/时间片映射” 问题的，那么可想而知，它又能带来什么惊艳效果呢？这里还有个“但是”，这个O(1)O(1)调度器的问题其实在计算密集型的守护进程看来，并不是问题，反而是好事，毕竟高优先级进程可以 无条件持续运行很久而不切换 。这对于吞吐率的提高，cache利用都是有好处的。无非也就侵扰了交互进程呗，又有何妨。
当然，使用调优CFS的时候，难免也要遇到IO睡眠奖惩等剩余的事情去设计一些trick算法，这破费精力。
对了，还要设置你的内核为HZ1000哦，这样更能体现CFS的平滑性，就像它宣称的那样。我难以想象，出了Ubuntu，Suse等花哨的桌面发行版之外，还有哪个Linux需要打开HZ1000，服务器用HZ250不挺好吗？
关于调度的话题基本就说完了，但是在进入下一步固有的喷子环节之前，还有两点要强调：
在CPU核数越来越多的时代，人们更应该关心 把进程调度到哪里CPU核上 而不是 某个CPU核要运行哪个进程 。
单核时代一路走过来的Linux，发展迅猛，这无可厚非，但是成就一个操作系统内核的并不单单是技术，还有别的。这些当然程序员们很不爱听，程序员最烦非技术方面的东西了，程序员跟谁都比写代码，程序员特别喜欢喷领导不会写代码云云。
Linux在纯技术方面并不优秀，Linux总体上优秀的原因是因为有一群非代码不明志的程序员在让它变得越来越优秀，另一方面还要归功于开源和社区。Linux的学习门槛极低，如果一个公司能不费吹灰之力招聘到一个Linux程序员的话，那它干嘛还要费劲九牛二虎之力去招聘什么高端的BSD程序员呢？最终的结果就是，Linux用的人极多，想换也换不掉了。
但无论如何也没法弥补Linux内核上的一些原则性错误。
Linux内核还是以原始的主线为base，以讲Linux内核的书为例，经典的Robert Love的《Linux内核设计与实现》，以及《深入理解Linux内核》，在讲进程调度的时候，关于多核负载均衡的笔墨都是少之又少甚至没有，如此经典的着作把很多同好引向了那万劫不复的代码深渊。于是乎，铺天盖地的CFS源码分析纷至沓来。
但其实，抛开这么一个再普通不过的Linux内核，现代操作系统进入了多核时代，其核心正是在cache利用上的革新，带来的转变就是进程调度和内存管理的革新。review一下Linux内核源码，这些改变早就已经表现了出来。
可悲的是，关于Linux内核的经典书籍却再也没有更新，所有的从传统学校出来的喜欢看书学习的，依然是抱着10年前的大部头在啃。
http :// www. ece.ubc.ca/~sasha/papers/eurosys16-final29.pdf
浙江温州皮鞋湿，下雨进水不会胖。
作者：CSDN博主“dog250”，本文首发于作者CSDN博客https://blog.csdn.net/dog250/article/details/957298 30 。
【END】
③ 一文读懂Linux任务间调度原理和整个执行过程
在前文中，我们分析了内核中进程和线程的统一结构体task_struct，并分析进程、线程的创建和派生的过程。在本文中，我们会对任务间调度进行详细剖析，了解其原理和整个执行过程。由此，进程、线程部分的大体框架就算是介绍完了。本节主要分为三个部分：Linux内核中常见的调度策略，调度的基本结构体以及调度发生的整个流程。下面将详细展开说明。
Linux 作为一个多任务操作系统，将每个 CPU 的时间划分为很短的时间片，再通过调度器轮流分配给各个任务使用，因此造成多任务同时运行的错觉。为了维护 CPU 时间，Linux 通过事先定义的节拍率（内核中表示为 HZ），触发时间中断，并使用全局变量 Jiffies 记录了开机以来的节拍数。每发生一次时间中断，Jiffies 的值就加 1。节拍率 HZ 是内核的可配选项，可以设置为 100、250、1000 等。不同的系统可能设置不同的数值，可以通过查询 /boot/config 内核选项来查看它的配置值。
Linux的调度策略主要分为实时任务和普通任务。实时任务需求尽快返回结果，而普通任务则没有较高的要求。在前文中我们提到了task_struct中调度策略相应的变量为policy，调度优先级有prio, static_prio, normal_prio, rt_priority几个。优先级其实就是一个数值，对于实时进程来说，优先级的范围是 0 99；对于普通进程，优先级的范围是 100 139。数值越小，优先级越高。
实时调度策略主要包括以下几种
普通调度策略主要包括以下几种：
首先，我们需要一个结构体去执行调度策略，即sched_class。该类有几种实现方式
普通任务调度实体源码如下，这里面包含了 vruntime 和权重 load_weight，以及对于运行时间的统计。
在调度时，多个任务调度实体会首先区分是实时任务还是普通任务，然后通过以时间为顺序的红黑树结构组合起来，vruntime 最小的在树的左侧，vruntime最多的在树的右侧。以CFS策略为例，则会选择红黑树最左边的叶子节点作为下一个将获得 CPU 的任务。而这颗红黑树，我们称之为运行时队列（run queue），即struct rq。
其中包含结构体cfs_rq，其定义如下，主要是CFS调度相关的结构体，主要有权值相关变量、vruntime相关变量以及红黑树指针，其中结构体rb_root_cached即为红黑树的节点
对结构体dl_rq有类似的定义，运行队列由红黑树结构体构成，并按照deadline策略进行管理
对于实施队列相应的rt_rq则有所不同，并没有用红黑树实现。
下面再看看调度类sched_class，该类以函数指针的形式定义了诸多队列操作，如
调度类分为下面几种：
队列操作中函数指针指向不同策略队列的实际执行函数函数，在linux/kernel/sched/目录下，fair.c、idle.c、rt.c等文件对不同类型的策略实现了不同的函数，如fair.c中定义了
以选择下一个任务为例，CFS对应的是pick_next_task_fair，而rt_rq对应的则是pick_next_task_rt，等等。
由此，我们来总结一下：
有了上述的基本策略和基本调度结构体，我们可以形成大致的骨架，下面就是需要核心的调度流程将其拼凑成一个整体，实现调度系统。调度分为两种，主动调度和抢占式调度。
说到调用，逃不过核心函数schele()。其中sched_submit_work()函数完成当前任务的收尾工作，以避免出现如死锁或者IO中断等情况。之后首先禁止抢占式调度的发生，然后调用__schele()函数完成调度，之后重新打开抢占式调度，如果需要重新调度则会一直重复该过程，否则结束函数。
而__schele()函数则是实际的核心调度函数，该函数主要操作包括选取下一进程和进行上下文切换，而上下文切换又包括用户态空间切换和内核态的切换。具体的解释可以参照英文源码注释以及中文对各个步骤的注释。
其中核心函数是获取下一个任务的pick_next_task()以及上下文切换的context_switch()，下面详细展开剖析。首先看看pick_next_task()，该函数会根据调度策略分类，调用该类对应的调度函数选择下一个任务实体。根据前文分析我们知道，最终是在不同的红黑树上选择最左节点作为下一个任务实体并返回。
下面来看看上下文切换。上下文切换主要干两件事情，一是切换任务空间，也即虚拟内存；二是切换寄存器和 CPU 上下文。关于任务空间的切换放在内存部分的文章中详细介绍，这里先按下不表，通过任务空间切换实际完成了用户态的上下文切换工作。下面我们重点看一下内核态切换，即寄存器和CPU上下文的切换。
switch_to()就是寄存器和栈的切换，它调用到了 __switch_to_asm。这是一段汇编代码，主要用于栈的切换， 其中32位使用esp作为栈顶指针，64位使用rsp，其他部分代码一致。通过该段汇编代码我们完成了栈顶指针的切换，并调用__switch_to完成最终TSS的切换。注意switch_to中其实是有三个变量，分别是prev, next, last，而实际在使用时，我们会对last也赋值为prev。这里的设计意图需要结合一个例子来说明。假设有ABC三个任务，从A调度到B，B到C，最后C回到A，我们假设仅保存prev和next，则流程如下
最终调用__switch_to()函数。该函数中涉及到一个结构体TSS(Task State Segment)，该结构体存放了所有的寄存器。另外还有一个特殊的寄存器TR（Task Register）会指向TSS，我们通过更改TR的值，会触发硬件保存CPU所有寄存器在当前TSS，并从新的TSS读取寄存器的值加载入CPU，从而完成一次硬中断带来的上下文切换工作。系统初始化的时候，会调用 cpu_init()给每一个 CPU 关联一个 TSS，然后将 TR 指向这个 TSS，然后在操作系统的运行过程中，TR 就不切换了，永远指向这个 TSS。当修改TR的值得时候，则为任务调度。
更多Linux内核视频教程文本资料免费领取后台私信【 内核大礼包 】自行获取。
在完成了switch_to()的内核态切换后，还有一个重要的函数finish_task_switch()负责善后清理工作。在前面介绍switch_to三个参数的时候我们已经说明了使用last的重要性。而这里为何让prev和last均赋值为prev，是因为prev在后面没有需要用到，所以节省了一个指针空间来存储last。
至此，我们完成了内核态的切换工作，也完成了整个主动调度的过程。
抢占式调度通常发生在两种情况下。一种是某任务执行时间过长，另一种是当某任务被唤醒的时候。首先看看任务执行时间过长的情况。
该情况需要衡量一个任务的执行时间长短，执行时间过长则发起抢占。在计算机里面有一个时钟，会过一段时间触发一次时钟中断，通知操作系统时间又过去一个时钟周期，通过这种方式可以查看是否是需要抢占的时间点。
时钟中断处理函数会调用scheler_tick()。该函数首先取出当前CPU，并由此获取对应的运行队列rq和当前任务curr。接着调用该任务的调度类sched_class对应的task_tick()函数进行时间事件处理。
以普通任务队列为例，对应的调度类为fair_sched_class，对应的时钟处理函数为task_tick_fair()，该函数会获取当前的调度实体和运行队列，并调用entity_tick()函数更新时间。
在entity_tick()中，首先会调用update_curr()更新当前任务的vruntime，然后调用check_preempt_tick()检测现在是否可以发起抢占。
check_preempt_tick() 先是调用 sched_slice() 函数计算出一个调度周期中该任务运行的实际时间 ideal_runtime。sum_exec_runtime 指任务总共执行的实际时间，prev_sum_exec_runtime 指上次该进程被调度时已经占用的实际时间，所以 sum_exec_runtime - prev_sum_exec_runtime 就是这次调度占用实际时间。如果这个时间大于 ideal_runtime，则应该被抢占了。除了这个条件之外，还会通过 __pick_first_entity 取出红黑树中最小的进程。如果当前进程的 vruntime 大于红黑树中最小的进程的 vruntime，且差值大于 ideal_runtime，也应该被抢占了。
如果确认需要被抢占，则会调用resched_curr()函数，该函数会调用set_tsk_need_resched()标记该任务为_TIF_NEED_RESCHED，即该任务应该被抢占。
某些任务会因为中断而唤醒，如当 I/O 到来的时候，I/O进程往往会被唤醒。在这种时候，如果被唤醒的任务优先级高于 CPU 上的当前任务，就会触发抢占。try_to_wake_up() 调用 ttwu_queue() 将这个唤醒的任务添加到队列当中。ttwu_queue() 再调用 ttwu_do_activate() 激活这个任务。ttwu_do_activate() 调用 ttwu_do_wakeup()。这里面调用了 check_preempt_curr() 检查是否应该发生抢占。如果应该发生抢占，也不是直接踢走当前进程，而是将当前进程标记为应该被抢占。
由前面的分析，我们知道了不论是是当前任务执行时间过长还是新任务唤醒，我们均会对现在的任务标记位_TIF_NEED_RESCUED，下面分析实际抢占的发生。真正的抢占还需要一个特定的时机让正在运行中的进程有机会调用一下 __schele()函数，发起真正的调度。
实际上会调用__schele()函数共有以下几个时机
从系统调用返回用户态：以64位为例，系统调用的链路为do_syscall_64->syscall_return_slowpath->prepare_exit_to_usermode->exit_to_usermode_loop。在exit_to_usermode_loop中，会检测是否为_TIF_NEED_RESCHED，如果是则调用__schele()
内核态启动：内核态的执行中，被抢占的时机一般发生在 preempt_enable() 中。在内核态的执行中，有的操作是不能被中断的，所以在进行这些操作之前，总是先调用 preempt_disable() 关闭抢占，当再次打开的时候，就是一次内核态代码被抢占的机会。preempt_enable() 会调用 preempt_count_dec_and_test()，判断 preempt_count 和 TIF_NEED_RESCHED 是否可以被抢占。如果可以，就调用 preempt_schele->preempt_schele_common->__schele 进行调度。
本文分析了任务调度的策略、结构体以及整个调度流程，其中关于内存上下文切换的部分尚未详细叙述，留待内存部分展开剖析。
1、调度相关结构体及函数实现
2、schele核心函数
④ Linux系统进程调度
主要参考 ：Linux manual page - sched
自从linux内核2.6.23以来，默认的进高哗扮程调度器就被设置为完全公平调度器（CFS，complete fair scheler），取代了之前的O(1)调度器。
每个线程都有一个静态调度优先级，即 sched_priority 字段。
一个线程的调度策略决定了线程会被插入到同级静态优先级的线程队列的位置，以及它在队列中会怎样移动。
所有的调度都是可插入的，如果一个更高静态优先级的线程准备好了，现在运行中的线程就会被插入。而调度策略则仅仅影响了同样静态优先级的线程。
进程（线程）可以通过系芦桥统调用设置自身或者其他进程（线程）的调度策略。
其中 pid 为0时，设置自身的调度策略和参数。结构体 sched_attr 包含以下戚灶字段： size 、 sched_policy （即调度策略，具体会在下一节介绍）、 sched_flags 、 sched_nice 、 sched_runtime 、 sched_deadline 、 sched_period （最后三个为 SCHED_DEADLINE 相关的参数）。当设置成功，系统调用返回0；否则返回-1，并会设置 errno 。
普通进程： SCHED_OTHER / SCHED_BATCH / SCHED_IDLE
实时进程： SCHED_FIFO / SCHED_RR
特殊实时进程： SCHED_DEADLINE
静态优先级：Static_priority：对于普通进程，静态优先级为0；对于实时进程，静态优先级为1-99，99为最高优先级。
动态优先级：Dynamic_priority：仅对普通进程有用，取决于nice和一个动态调整的量（比如进程ready却没被调度，则增加）。