首页
学习
活动
专区
圈层
工具
发布

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.8K20

编译到底做了什么(***.c -> ***.o的过程)

编译器做了什么?   从最直观的角度来说,编译器就是将高级语言翻译成机器语言的一个工具。   以 C语言为例,解释一下 ***.c -> ***.o 的过程。...编译器所能分析的语义是静态语义。(动态语义不能被分析)   静态语义:在编译阶段可以确定的语义,通常包括声明和类型的匹配,类型的转换。  ...若用把目标代码用汇编器编译成真正能在机器上执行的指令,这两个地址从何而来呢。 若index和array定义在跟上面的源代码同一个编译单元里,那么编译器可以为它们分配空间,确定它们的地址。...附在那本书的一些话:(助于理解) (1).现代的编译器可以将一个源代码文件编译成一个未链接的目标文件,然后由链接器最终将这些目标文件链接起来形成可执行文件。...(4).经过预编译、编译和汇编直接输出目标文件(Object File)。 参考文献《程序员的自我修养--链接、装载与库》 P41-P48 (其实就是摘抄整理了一下,哈哈)

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

    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)中加了需要时间的判断,各种情况的考虑,导致代码的阅读性很差,读起来很费劲。

    3.3K21

    谈谈调度 - 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 的身影。

    2.1K80

    初识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(

    38310

    【Linux 内核】编译 Linux 内核 ⑤ ( 查看 .config 编译配置文件 | 正式编译内核 )

    文章目录 一、查看 .config 编译配置文件 二、正式编译内核 一、查看 .config 编译配置文件 ---- 在上一篇博客 【Linux 内核】编译 Linux 内核 ④ ( 打开 Linux...内核编译 菜单配置 |菜单配置中的光标移动与选中状态 | 保存配置 | 配置项帮助文档 ) 中 , 已经将编译配置保存到了 .config 文件中 ; 查看 .config 编译配置文件 , 在 linux...内核源码根目录中 , 执行 gedit .config 命令 , 查看 .config 编译配置文件 : ( 也可以使用 vi , vim 等文本编辑器查看 ) 在 .config 配置中 , #...等号右侧的 y 表示同意该操作 ; .config 文件内容示例 : 配置文件很多 , 这里只贴出一部分 ; # # Automatically generated file; DO NOT EDIT. # Linux...---- 在 Linux 内核源码根目录 , 执行 sudo make j4 开始编译 Linux 内核 ;

    15.1K40

    怎么编译Linux内核?

    /bin STM32MP157全功能版 kernel的编译过程如下(编译内核前需要先配置好工具链等一些环境变量): book@100ask:~/100ask_stm32mp157_pro-sdk/Linux...LOADADDR=0xC2000040 book@100ask:~/100ask_stm32mp157_pro-sdk/Linux-5.4$ make dtbs 编译步骤参考如下,编译完成 uImage...后才可编译设备树文件,如果你觉得编译速度很慢可以加 -j来使用并行任务编译,如下图加 -j8 参数使用 8 个并行任务来编译内核,编译速度视性能而言,i7 9700F 主频 3Ghz 四核...STM32MP157全功能版 进入内核源码目录后,就可以编译内核模块了: book@100ask:~/100ask_stm32mp157_pro-sdk/Linux-5.4$ make ARCH=arm...CROSS_COMPILE=arm-buildroot-linux-gnueabihf- modules -j8 内核模块编译命令执行截图示例 4.

    11.6K20
    领券