首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Linux O(n)调度器

前面我们学习了调度器的设计需要关注的几个点,在这里复习下: 吞吐量(对应的是CPU消耗型进程) 响应速度(对应的是IO消耗型进程) 公平性,确保每个进程都可以有机会运行到 移动设备的功耗 Linux中调度器的设计...实时进程采用两种调度策略SCHED_RR或者SCHED_FIFO 普通进程采用nice值进行动态调整普通进程的优先级 经常睡眠的进程尝试增大下优先级,经常长占CPU的适当减少优先级 本节我们先来学习Linux...早期的调度算法的设计,先从最早的调度器算法开始,此调度器时间复杂度是O(n),所以也可以称为O(n)调度算法。...我们选择的内核版本是linux-2.4.19。 O(n)调度器的实现原理 O(n)代表的是寻找一个合适的进程的时间复杂度。...总之O(n)调度器有很多问题,不过有问题肯定要解决的。所以在Linux2.6引入了O(1)的调度器。

3.4K20
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    谈谈调度 - Linux O(1)

    约莫十五年前,当我刚刚开始参加工作时,赶上 Linux 发布划时代的 2.6 内核。在这个大家都翘首期盼的内核版本中,最令人兴奋的便是 O(1) scheduler。本文来谈谈这个算法是如何实现的。...2.4 scheduler 的问题 Linux 2.4 scheduler 支持 SMP(Symmetric Multi-Processing),然而,由于只用一个 global runqueue,各个...谈到搜索,大家第一反应是 hash table 是 O(1) 时间复杂度的。然而,它在最坏情况下是 O(N) 的。除此之外,没有任何算法能在最坏情况下 search 也是 O(1)。...linked list,stack,queue 在平均和最坏情况下都是 O(1),而大家脑海里的 hash table,同样的,虽然平均是 O(1),但最坏情况是 O(N)。...在其刚问世时,很多 linux 发行版就迫不及待将其移植回 2.4 kernel。而程序君整个职业生涯中接触过的一些调度器中,都能见到 bitarray + priority queue 的身影。

    1.9K80

    Linux O(1)调度器

    O(n)调度器的种种问题,linux内核社区则在2.6内核版本引入了O(1)调度器,当然了引入的目的也正是要解决O(n)调度器面临的问题。...我们这片文章以Linux2.6.2版本来学习,在Linux内核文档中有一篇关于O(1)调度器的目的,如何设计的,以及实现有一个详细的介绍:sched-design.txt文档,有兴趣的可以去阅读。...从以上几点来看,可以看出O(1)的算法的改进都是针对O(n)算法存在的问题来修改的。...总结: O(1)调度器的引入主要是为了解决O(n)调度器的不足 O(1)调度器在赏罚机制上比O(n)调度器考虑的因素比较多,不再时像O(1)那样直接考时间片的大小来调度 但是O(n)和O(1)调度算法上核心还是通过判断一个进程的行为...如果去看O(1)调度器的实现,没有O(n)算法那么简单明了,O(1)中加了需要时间的判断,各种情况的考虑,导致代码的阅读性很差,读起来很费劲。

    2.9K21

    初识Linux · O(1)调度算法

    并且,优先级一共就那么几个优先级,实际运行的时候,进程可不止有那么多个,所以优先级并不能真正代替进程是否先运行,并且nice值也是影响进程的运行,这一切,构成了一个新的专题,即Linux中的O(1)调度算法...O(1)调度算法 正式开始之前,我们不妨整理一下,有多少个问题: 1. 随着进程的增多,进程排队的时间是否会越来越多,甚至导致运行不了? 2. 优先级一定是越小就一定会先运行吗?...3. nice值影响优先级的区间为什么只有40个值 这么多问题的切入点只有一个,即Linux源码中的一个结构:runqueue 这是解决问题的关键。...根据上图,array[0]中有一个140个空间的queue,还有一个bitmap[5],因为这两个变量的存在,所以Linux的调度是分时操作的,保证了一定的公平性,还有一种操作是实时操作,实时操作的例子比如出租车...当某个队列中一个进程都没有了,比如active中没有进程了,那么active和expired交换队列,此时acitve指向的即活跃,即原来过期的进程变成了活跃进程,活跃的进程变成了过期的进程,这个过程,就被成为O(

    7010

    ConcurrentHashMap的put方法

    计算key的哈希值for自旋保证put成功如果没有初始化就初始化table有可能多个线程去调用initTable()方法去初始化,用cas加锁就行了,成功一次就行了通过与哈希取模计算数组下标,如果下标节点为...null,就通过cas放进数组当前下标的位置如果当前下标有值,并且发现当前节点正在做扩容迁移操作,就去帮助扩容如果既有值,又没在扩容,就锁住这个数组下标节点,开始进行put操作第一种情况当前节点是一个链表遍历整个链表判断...hash不存在,此时已经遍历到了最后一个节点e,然后把当前的key/value添加到链表e节点的后i面,尾插法第二种情况当前节点是红黑树将节点放入红黑树,具体怎么放的参考我另一篇同系列下的文章之红黑树put

    81010

    Linux进程调度之 - O(1)调度算法

    Linux是一个支持多任务的操作系统,而多个任务之间的切换是通过 调度器 来完成,调度器 使用不同的调度算法会有不同的效果。...Linux2.4版本使用的调度算法的时间复杂度为O(n),其主要原理是通过轮询所有可运行任务列表,然后挑选一个最合适的任务运行,所以其时间复杂度与可运行任务队列的长度成正比。...而Linux2.6开始替换成名为 O(1)调度算法,顾名思义,其时间复杂度为O(1)。...虽然在后面的版本开始使用 CFS调度算法(完全公平调度算法),但了解 O(1)调度算法 对学习Linux调度器还是有很大帮助的,所以本文主要介绍 O(1)调度算法 的原理与实现。...由于在 Linux 内核中,任务和进程是相同的概念,所以在本文混用了任务和进程这两个名词。

    4.9K81

    时间复杂度o(1), o(n), o(logn), o(nlogn)

    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(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。 比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次。...5、时间复杂度为O(nlogn)。 就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。 归并排序就是O(nlogn)的时间复杂度。

    1.4K10

    PUT和POST的区别

    PUT 和 POST 是 HTTP 协议中两种常用的请求方法。它们有些相似之处,但也有一些重要的区别。在本文中,我们将详细介绍 PUT 和 POST 的区别。...PUT 请求 PUT 请求是 HTTP 协议中的一种请求方法,通常用于更新或替换服务器上的资源。使用 PUT 请求时,客户端需要将整个资源的新版本发送到服务器。...PUT 请求的一些特点: 可以更新整个资源。 客户端需要发送完整的资源内容。 如果服务器上不存在该资源,则会创建一个新的资源。 PUT 请求具有幂等性,即执行多次 PUT 请求的结果应该相同。...幂等性不同:PUT 请求具有幂等性,即执行多次 PUT 请求的结果应该相同,而 POST 请求不具有幂等性。...总之,PUT 和 POST 请求有些相似之处,但也有一些其他的区别: 安全性不同:PUT 请求是安全的,即对服务器上的资源的任何操作都不会导致状态的改变。

    2.1K10

    “去O”不如“减O”

    去IOE的话题最近很火,而来自四川电信的客户访问,其中有一段颇有借鉴意义:去“O”不如减“O”。...去O”不如“减O” - 在成功去掉小型机之后,TechTarget记者还向梁天健询问了关于去E(EMC存储)和去O(Oracle数据库)的话题。...再谈到去O,梁天健的态度很明确,从技术层面来讲,目前很多企业连Oracle这样具有高可用、高性能、易用性强的数据库都没有用好,去O根本无从谈起。...梁天健认为答案是否定的:“我们不去O,但是我们可以尝试减O。何谓‘减O’?就是将假设现在的200个独立的Oracle数据库整合到20个更大型的Oracle数据库中去。”...当然,“减O”同样具有风险,实施需谨慎。梁天健认为,以前一个系统出现故障,也就是影响这一个系统,但是整合在一起,一个系统的数据库占用了100%的I/O,会导致其它的系统也同样受到干扰。

    1.8K60
    领券