O(n)调度器的种种问题，linux内核社区则在2.6内核版本引入了O(1)调度器，当然了引入的目的也正是要解决O(n)调度器面临的问题。...我们这片文章以Linux2.6.2版本来学习，在Linux内核文档中有一篇关于O(1)调度器的目的，如何设计的，以及实现有一个详细的介绍：sched-design.txt文档，有兴趣的可以去阅读。...O(1)调度器的工作原理 ?...总结： O(1)调度器的引入主要是为了解决O(n)调度器的不足 O(1)调度器在赏罚机制上比O(n)调度器考虑的因素比较多，不再时像O(1)那样直接考时间片的大小来调度 但是O(n)和O(1)调度算法上核心还是通过判断一个进程的行为...当然了时代还是要前进的，O(n)和O(1)调度器是为CFS调度器出现地提供了很好的环境。
约莫十五年前，当我刚刚开始参加工作时，赶上 Linux 发布划时代的 2.6 内核。在这个大家都翘首期盼的内核版本中，最令人兴奋的便是 O(1) scheduler。本文来谈谈这个算法是如何实现的。...注意，所有调度系统的难点不在于寻找下一个可执行的 process，这个操作一般都是 O(1)，因为我们只要妥善对 runqueue 排序，使其第一个 process 永远是下次需要调度的 process...满足 O(1) 的数据结构？...linked list，stack，queue 在平均和最坏情况下都是 O(1)，而大家脑海里的 hash table，同样的，虽然平均是 O(1)，但最坏情况是 O(N)。...在其刚问世时，很多 linux 发行版就迫不及待将其移植回 2.4 kernel。而程序君整个职业生涯中接触过的一些调度器中，都能见到 bitarray + priority queue 的身影。
Linux2.4版本使用的调度算法的时间复杂度为O(n)，其主要原理是通过轮询所有可运行任务列表，然后挑选一个最合适的任务运行，所以其时间复杂度与可运行任务队列的长度成正比。...而Linux2.6开始替换成名为 O(1)调度算法，顾名思义，其时间复杂度为O(1)。...虽然在后面的版本开始使用 CFS调度算法（完全公平调度算法），但了解 O(1)调度算法 对学习Linux调度器还是有很大帮助的，所以本文主要介绍 O(1)调度算法 的原理与实现。...O(1)调度算法原理 prio_array 结构 O(1)调度算法 通过优先级来对任务进行分组，可分为140个优先级（0 ~ 139，数值越小优先级越高），每个优先级的任务由一个队列来维护。...1)调度算法实现 接下来我们分析一下 O(1)调度算法 在内核中的实现。
前面我们学习了调度器的设计需要关注的几个点，在这里复习下： 吞吐量（对应的是CPU消耗型进程） 响应速度（对应的是IO消耗型进程） 公平性，确保每个进程都可以有机会运行到 移动设备的功耗 Linux中调度器的设计...经常睡眠的进程尝试增大下优先级，经常长占CPU的适当减少优先级 本节我们先来学习Linux早期的调度算法的设计，先从最早的调度器算法开始，此调度器时间复杂度是O(n)，所以也可以称为O(n)调度算法。...我们选择的内核版本是linux-2.4.19。 O(n)调度器的实现原理 O(n)代表的是寻找一个合适的进程的时间复杂度。...O(n)调度器面临的问题 时间复杂度问题，时间复杂度是O(n),当系统中的进程很少的时候性能还可以，但是当系统中的进程逐渐增多，选择下一个进程的时间则是逐渐增大。...总之O(n)调度器有很多问题，不过有问题肯定要解决的。所以在Linux2.6引入了O(1)的调度器。
1、时间复杂度o(1), o(n), o(logn), o(nlogn)。算法时间复杂度的时候有说o(1), o(n), o(logn), o(nlogn)，这是算法的时空复杂度的表示。...O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。 2、时间复杂度为O(1)。...哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话） 3、时间复杂度为O(n)。 就代表数据量增大几倍，耗时也增大几倍。 比如常见的遍历算法。...二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。 指数函数，一般地，y=a^x函数(a为常数且以a>0，a≠1)叫做指数函数。...对数函数，如果a^x =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。 5、时间复杂度为O(nlogn)。
为了加快代码执行的效率，很多OJ平台都会自动开启O2优化。 在这里我们讲讲到底是怎么优化的。 O0优化 #pragma GCC optimize(0) 1、把变量分配到寄存器。...O1优化 #pragma GCC optimize(1) 包含O0的各种优化功能，并增加了： 1、在变量赋值时，将数值直接赋给变量而不是给出变量的地址。 2、去掉没有用的变量和表达式。...O2优化 #pragma GCC optimize(2) 包含O1的各种优化功能，并增加了： 1、去掉全局通用的子表达式。 2、去掉全局没有用的分配变量和表达式。 3、化解循环。...当只用-O选项时优化器自动进行-O2优化。 O3优化 #pragma GCC optimize(3) 包含O2的各种优化功能，并增加了： 1、去掉未调用的函数。 2、简化返回值未使用的函数。
接下来几篇文章会介绍linux内核是如何调度进程的，在学习内核进程调度之前有必要搞懂这些准备知识！...相信很多开发的同伴们在研究算法、排序的时候经常会碰到O(1)，O(n)，O(logn)，O(nlogn)这些复杂度，看到这里就会有个疑惑，这个O(N)到底代表什么呢？带着好奇开始今天文章。...首先o(1), o(n), o(logn), o(nlogn)是用来表示对应算法的时间复杂度,这是算法的时间复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。...哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标。...index = a; a = b; b = index; //运行一次就可以得到结果 时间复杂度的优劣对比常见的数量级大小：越小表示算法的执行时间频度越短，则越优； O(1)<O(logn)<O(n)<
在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度。这里进行归纳一下它们代表的含义:这是算法的时空复杂度的表示。...O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。 比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。...再比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。...归并排序就是O(nlogn)的时间复杂度。 O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。...哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
平均周转时间为：(10+10+12+9+15)/5=56/5=11.2 4、高优先权优先调度算法: 1、优先级调度的含义 （1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行...基于时间片的轮转调度算法1.png ?...3、时刻2： J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3：J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。...5、时刻4：J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。 6、时刻5：J3经过1个时间片，完成。...7、时刻6：由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。 8、时刻7：J1再经过一个时间片，完成了任务。于是整个调度过程结束。
Linux进程调度 发展历史 Linux从2.5版本开始引入一种名为的调度器，后在2.6版本中将公平的的调度概念引入了调度程序，代替之前的调度器，称为算法（完全公平调度算法）。...策略 I/O消耗型和处理器消耗型 I/O消耗型进程是指那些大部分时间都在等待I/O操作的进程，处理器耗费型的进程则是指把大多数时间用于执行代码的进程，除非被抢占，他们一般都一直在运行。...为了保证交互式应用和桌面系统的性能，一般Linux更倾向于优先调度I/O消耗型进程。 进程优先级 Linux采用了两种不同的优先级范围。 使用nice值：越大的nice值意味着更低的优先级。...Linux调度算法 调度器类 Linux的调度器是以模块的方式提供的，这样使得不同类型的进程按照自己的需要来选择不同的调度算法。...1.等待队列 和可运行队列的复杂结构不同，等待队列在linux中的实现只是一个简单的链表。所有有关等待队列的数据结构被定义在中，具体的实现代码则被定义在中。
I/O 消耗型和 CPU 消耗型 ---- 运行的进程如果大部分来进行 I/O 的请求或者等待的话，这个进程称之为 I/O 消耗型，比如键盘。...没有太多的 I/O 需求，从系统响应的角度上来讲，调度器不应该经常让他们运行。对于处理器消耗型的进程，调度策略往往是降低他们的执行频率，延长运行时间。...Linux 系统为了提升响应的速度，倾向于优先调度 I/O 消耗型。...—— 小结 实时进程优先级：value 越高，优先级越大 普通进程优先级：nice值越高，普通进程的优先级越小 任何实时进程的优先级 > 普通进程 Linux 调度算法 ---- Linux 中有一个总的调度结构...也可以用 pidstat -w 命令查看进程切换的每秒统计值： pidstat -w 1 Linux 3.10.0-229.14.1.el7.x86_64 (bj71s060) 02/01/2018
前者适用SCHED_NORMAL调度策略，后者可选SCHED_FIFO或SCHED_RR调度策略。...1.实时进程的调度 实时进程，只有静态优先级，因为内核不会再根据休眠等因素对其静态优先级做调整，其范围在0~MAX_RT_PRIO-1间。...不同调度策略的实时进程只有在相同优先级时才有可比性： 1. 对于FIFO的进程，意味着只有当前进程执行完毕才会轮到其他进程执行； 2....2.非实时进程的调度 Linux对普通的进程，根据动态优先级进行调度。而动态优先级是由静态优先级（static_prio）调整而来。Linux下，静态优先级是用户不可见的，隐藏在内核中。...Linux2.6 在这方面有了较大的提高。Linux2.6认为，交互式进程可以从平均睡眠时间这样一个measurement进行判断。进程过去的睡眠时间越多，则越有可能属于交互式进程。
调度策略 进程可以分为实时进程和普通进程，对于这两种不同类型的进程肯定有不同的调度策略，task_struct中的policy就用来表示调度策略。...// 调度策略 unsigned int policy; #define SCHED_NORMAL 0 #define SCHED_FIFO 1 #define SCHED_RR 2 #define SCHED_BATCH...fair_sched_class：普通进程的调度策略 CFS调度算法 CFS（completed fair Schedule）完全公平调度，适用于普通进程调度。...vruntime = 实际运行时间 * NICE_0_LOAD / 权重 使用调度算法首先得有包含vruntime的调度实体，task_struct中有如下调度实体的成员变量： struct sched_entity...se; //完全调度实体 struct sched_rt_entity rt; // 实时调度实体 struct sched_dl_entity dl; // deadline调度实体 CFS算法中将
在Linux中，线程是由进程来实现，线程就是轻量级进程（ lightweight process ），因此在Linux中，线程的调度是按照进程的调度方式来进行调度的，也就是说线程是调度单元...和SCHED_RR是实时策略，他们的调度值范围是1到99，数值越大优先级越高，另外实时调度策略的线程总是比前面三种通常的调度策略优先级更高。...下面介绍几种常见的调度策略： SCHED_OTHER：该策略是是默认的Linux分时调度（time-sharing scheduling）策略，它是Linux线程默认的调度策略。...在Linux中，对于SCHED_FIFO和SCHED_RR调度策略其优先级为1到99，其他调度策略优先级为0。注意在不同系统上，这个优先级范围可能不一样。...Linux调度时机主要有: 进程状态转换的时刻：进程终止、进程睡眠（比如I/O阻塞就会导致这种情况），还比如进程调用sleep()或exit()等函数进行状态转换。 当前进程的时间片用完时。
-O 和-O1 对程序做部分编译优化，对于大函数,优化编译占用稍微多的时间和相当大的内存。使用本项优化，编译器会尝试减小生成代码的尺寸，以及缩短执行时间，但并不执行需要占用大量编译时间的优化。...-O2（氧气优化） 是比 O1 更高级的选项，进行更多的优化。Gcc 将执行几乎所有的不包含时间和空间折中的优化。...当设置 O2 选项时，编译器并不进行循环打开（）loop unrolling 以及函数内联。与 O1 比较而言，O2 优化增加了编译时间的基础上，提高了生成代码的执行效率。...O2 打开所有的 O1 选项，并打开以下选项： l -fforce-mem：在做算术操作前，强制将内存数据 copy 到寄存器中以后再执行。...O1 优化会消耗少多的编译时间，它主要对代码的分支，常量以及表达式等进行优化。 O2 会尝试更多的寄存器级的优化以及指令级的优化，它会在编译期间占用更多的内存和编译时间。
O(n)和O(1)调度器 下面介绍Linux的调度策略。最原始的调度策略是按照优先级排列好进程，等到一个进程运行完了再运行优先级较低的一个，但这种策略完全无法发挥多任务系统的优势。...当计算机中有大量进程在运行时，这个调度器的性能将会被大大降低。也就是说，O(n)调度器没有很好的可拓展性。O(n)调度器是Linux 2.6之前使用的进程调度器。...当Java语言逐渐流行后，由于Java虚拟机会创建大量进程，调度器的性能问题变得更加明显。 为了解决O(n)调度器的性能问题，O(1)调度器被发明了出来，并从Linux 2.6内核开始使用。...和O(n)调度器类似，O(1)也是把时间片分配给进程。...完全公平调度器 从2007年发布的Linux 2.6.23版本起，完全公平调度器（CFS，Completely Fair Scheduler）取代了O(1)调度器。
至于CFS调度算法的实现后面后专门写一篇文章，这里只要记住调度时选择一个优先级最高的任务执行 一、调度单位简介 1.1 task_struct 结构体简介 对于Linux内核来说，调度的基本单位是任务，...Linux采用的是每个CPU都有自己的运行队列，这样做的好处： （1）每个CPU在自己的运行队列上选择任务降低了竞争 （2）某个任务位于一个CPU的运行队列上，经过多次调度后，内核趋于选择相同的CPU...在这里我只讨论普通任务的调度，因为linux大部分情况下都是在运行普通任务，普通任务选择的调度器是CFS完全调度。 在调度时，调度器去 CFS 运行队列找是否有任务需要运行。...，如果发生了调度抢占（preempt =1），那么直接跳过，不参与判断，直接调用pick_next_task。...具体请参考：Linux 进程调度通知机制 struct preempt_ops { void (*sched_in)(struct preempt_notifier *notifier, int cpu
一、抢占式调度和主动调度： 前面我们说过，进程的切换总是通过 shedule 函数发生的，而 schedule 函数可以是在系统调用返回、中断返回等时机被调用，也可以进程在驱动程序中主动调用 我们把在系统调用返回等时机调用...schedule 函数的这种非进程自愿情况称为抢占式调度。...把进程在驱动程序中主动调用 schedule 函数来发生进程切换的这种情况称为主动调度 本文将讨论主动调度，抢占式调度将在下一篇文章中讲解： 二、主动调度的发生的情况： 主动调度一般在应用程序读取某个设备时...，设备此时数据还没有准备好，进程就进入睡眠，发生进程调度切换到其它进程运行 例如应用想从网卡读取数据，但是此时网卡没有数据，那么驱动程序就会让进程睡眠，然后发生进程调度。...四、总结: 进程发生切换总是调用 schedule 函数进行的，进程调度分抢占式调度和主动调度，主动调度表示的是进程主动调用 schedule 函数发生进程切换 schedule 函数主要做了两件事，
linux实现公平调度基本上是两种思路： 1、给处于可执行状态的进程分配时间片（按照优先级），用完时间片的进程被放到“过期队列”中。...有兴趣的朋友可以参考下面的链接： 《Linux 调度器发展简述》 《鼠眼看Linux调度器》 《鼠眼再看Linux调度器［1］》 《鼠眼再看Linux调度器［2］》 调度程序的效率 “优先级”明确了哪个进程应该被调度执行...这样就大大提高了调度程序的效率，复杂度为O(1)； 在linux 2.6近期的版本中，可执行状态的进程按照优先级顺序被挂在一个红黑树（可以想象成平衡二叉树）中。...每次调度，调度程序需要从树中找出优先级最高的进程。复杂度为O(logN)。 那么，为什么从linux 2.6早期到近期linux 2.6版本，调度程序选择进程时的复杂度反而增加了呢？...而O(1)的算法是基于一组数目不大的 链表来实现的，按我的理解，这使得优先级的取值范围很小（区分度很低），不能满足公平性的需求。
目录 linux线程调度策略 linux线程调度策略 这是一篇非常好的关于线程调度的资料，翻译自shed 从Linux 2.6.23开始，默认的调度器为CFS，即"完全公平调度器"(Completely...CFS调度器取代了之前的"O(1)"调度器。 CFS的实现细节可以参见sched-design-CFS。cgroup的CPU调度也属于CFS扩展的一部分。...进程调度中使用了2个队列：进程一开始会进入ready队列等待调度；当进程执行中遇到I/O阻塞，等待子进程结束或软中断等原因会进入wait队列，等阻塞结束后会返回到ready队列 SCHED_FIFO:...该参数需要结合sched_rt_period_us使用 Response time 一个阻塞的高优先级的线程(在调度前)等待I/O时会有一个确定的响应时间。...可以通过/proc/$pid/status查看进程上下文切换的情况，如下表示自发(如I/O等待)的上下文切换为1，非自发(如时间片超时会被更高优先级进程抢占)的上下文切换为10。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
