`
liudaoru
  • 浏览: 1586185 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Linux 调度器内幕[z]

阅读更多
Linux® 内核继续不断发展并采用新技术,在可靠性、可伸缩性和性能方面获得了长足的发展。2.6 版本的内核最重要的特性之一是由 Ingo Molnar 实现的调度器。这个调度器是动态的,可以支持负载均衡,并以恒定的速度进行操作 —— O(1)。本文将介绍 Linux 2.6 调度器的这些属性以及更多内容。

本文将回顾一下 Linux 2.6 的任务调度器及其最重要的一些属性。在深入介绍调度器的详细信息之前,让我们先来理解一下调度器的基本目标。

什么是调度器?

通常来说,操作系统是应用程序和可用资源之间的媒介。典型的资源有内存和物理设备。但是 CPU 也可以认为是一个资源,调度器可以临时分配一个任务在上面执行(单位是时间片)。调度器使得我们同时执行多个程序成为可能,因此可以与具有各种需求的用户共享 CPU。

调度器的一个重要目标是有效地分配 CPU 时间片,同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标,例如既要为关键实时任务最小化响应时间,又要最大限度地提高 CPU 的总体利用率。下面我们来看一下 Linux 2.6 调度程序是如何实现这些目标的,并与以前的调度器进行比较。





回页首


早期 Linux 调度器的问题

O-notation 的重要性
O-notation 可以告诉我们一个算法会占用多少时间。一个 O(n) 算法所需要的时间依赖于输入的多少(与 n 是线性关系),而 O(n^2) 则是输入数量的平方。O(1) 与输入无关,可以在固定的时间内完成操作。

在 2.6 版本的内核之前,当很多任务都处于活动状态时,调度器有很明显的限制。这是由于调度器是使用一个复杂度为 O(n) 的算法实现的。在这种调度器中,调度任务所花费的时间是一个系统中任务个数的函数。换而言之,活动的任务越多,调度任务所花费的时间越长。在任务负载非常重时,处理器会因调度消耗掉大量的时间,用于任务本身的时间就非常少了。因此,这个算法缺乏可伸缩性。

在对称多处理系统(SMP)中,2.6 版本之前的调度器对所有的处理器都使用一个运行队列。这意味着一个任务可以在任何处理器上进行调度 —— 这对于负载均衡来说是好事,但是对于内存缓存来说却是个灾难。例如,假设一个任务正在 CPU-1 上执行,其数据在这个处理器的缓存中。如果这个任务被调度到 CPU-2 上执行,那么数据就需要先在 CPU-1 使其无效,并将其放到 CPU-2 的缓存中。

以前的调度器还使用了一个运行队列锁;因此在 SMP 系统中,选择一个任务执行就会阻碍其他处理器操作这个运行队列。结果是空闲处理器只能等待这个处理器释放出运行队列锁,这样会造成效率的降低。

最后,在早期的内核中,抢占是不可能的;这意味着如果有一个低优先级的任务在执行,高优先级的任务只能等待它完成。





回页首


Linux 2.6 调度器简介

2.6 版本的调度器是由 Ingo Molnar 设计并实现的。Ingo 从 1995 年开始就一直参与 Linux 内核的开发。他编写这个新调度器的动机是为唤醒、上下文切换和定时器中断开销建立一个完全 O(1) 的调度器。触发对新调度器的需求的一个问题是 Java™ 虚拟机(JVM)的使用。Java 编程模型使用了很多执行线程,在 O(n) 调度器中这会产生很多调度负载。O(1) 调度器在这种高负载的情况下并不会受到太多影响,因此 JVM 可以有效地执行。

2.6 版本的调度器解决了以前调度器中发现的 3 个主要问题(O(n) 和 SMP 可伸缩性的问题),还解决了其他一些问题。现在我们将开始探索一下 2.6 版本的调度器的基本设计。

主要的调度结构

首先我们来回顾一下 2.6 版本的调度器结构。每个 CPU 都有一个运行队列,其中包含了 140 个优先级列表,它们是按照先进先出的顺序进行服务的。被调度执行的任务都会被添加到各自运行队列优先级列表的末尾。每个任务都有一个时间片,这取决于系统允许执行这个任务多长时间。运行队列的前 100 个优先级列表保留给实时任务使用,后 40 个用于用户任务(参见图 1)。我们稍后将来看一下为什么这种区别非常重要。


图 1. Linux 2.6 调度器的运行队列结构
Linux 2.6 调度器的运行队列结构

除了 CPU 的运行队列(称为活动运行队列(active runqueue))之外,还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后,它就被移动到过期运行队列(expired runqueue) 中。在移动过程中,会对其时间片重新进行计算(因此会体现其优先级的作用;稍后会更详细地介绍)。如果活动运行队列中已经没有某个给定优先级的任务了,那么指向活动运行队列和过期运行队列的指针就会交换,这样就可以让过期优先级列表变成活动优先级的列表。

调度器的工作非常简单:它在优先级最高的队列中选择一个任务来执行。为了使这个过程的效率更高,内核使用了一个位图来定义给定优先级列表上何时存在任务。因此,在大部分体系架构上,会使用一条 find-first-bit-set 指令在 5 个 32 位的字(140 个优先级)中哪一位的优先级最高。查找一个任务来执行所需要的时间并不依赖于活动任务的个数,而是依赖于优先级的数量。这使得 2.6 版本的调度器成为一个复杂度为 O(1) 的过程,因为调度时间既是固定的,而且也不会受到活动任务个数的影响。

更好地支持 SMP 系统

那么什么是 SMP 呢?SMP 是一种体系架构,其中多个 CPU 可以用来同时执行各个任务,它与传统的非对称处理系统不同,后者使用一个 CPU 来执行所有的任务。SMP 体系架构对多线程的应用程序非常有益。

尽管优先级调度在 SMP 系统上也可以工作,但是它这种大锁体系架构意味着当一个 CPU 选择一个任务进行分发调度时,运行队列会被这个 CPU 加锁,其他 CPU 只能等待。2.6 版本的调度器不是使用一个锁进行调度;相反,它对每个运行队列都有一个锁。这样允许所有的 CPU 都可以对任务进行调度,而不会与其他 CPU 产生竞争。

另外,由于每个处理器都有一个运行队列,因此任务通常都是与 CPU 密切相关的,可以更好地利用 CPU 的热缓存。

任务抢占

Linux 2.6 版本调度器的另外一个优点是它允许抢占。这意味着当高优先级的任务准备运行时低优先级的任务就不能执行了。调度器会抢占低优先级的进程,并将这个进程放回其优先级列表中,然后重新进行调度。





回页首


但是请等一下,还有更多功能呢!

似乎 2.6 版本调度器的 O(1) 特性和抢占特性还不够,这个调度器还提供了动态任务优先级和 SMP 负载均衡功能。下面就让我们来讨论一下这些功能都是什么,以及它们分别提供了哪些优点。

动态任务优先级

为了防止任务独占 CPU 从而会饿死其他需要访问 CPU 的任务,Linux 2.6 版本的调度器可以动态修改任务的优先级。这是通过惩罚 CPU 绑定的任务而奖励 I/O 绑定的任务实现的。I/O 绑定的任务通常使用 CPU 来设置 I/O,然后就睡眠等待 I/O 操作完成。这种行为为其他任务提供了 CPU 的访问能力。

用户响应能力更好
与用户进行通信的任务都是交互型的,因此其响应能力应该比非交互式任务更好。由于与用户的通信(不管是向标准输出上发送数据,还是通过标准输入等待输入数据)都是 I/O 绑定型的,因此提高这些任务的优先级可以获得更好的交互式响应能力。

由于 I/O 绑定型的任务对于 CPU 访问来说是无私的,因此其优先级减少(奖励)最多 5 个优先级。CPU 绑定的任务会通过将其优先级增加最多 5 个优先级进行惩罚。

任务到底是 I/O 绑定的还是 CPU 绑定的,这是根据交互性 原则确定的。任务的交互性指标是根据任务执行所花费的时间与睡眠所花费的时间的对比程度进行计算的。注意,由于 I/O 任务先对 I/O 进行调度,然后再进行睡眠,因此 I/O 绑定的任务会在睡眠和等待 I/O 操作完成上面花费更多的时间。这会提高其交互性指标。

有一点值得注意,优先级的调整只会对用户任务进行,对于实时任务来说并不会对其优先级进行调整。

SMP 负载均衡

在 SMP 系统中创建任务时,这些任务都被放到一个给定的 CPU 运行队列中。通常来说,我们无法知道一个任务何时是短期存在的,何时需要长期运行。因此,最初任务到 CPU 的分配可能并不理想。

为了在 CPU 之间维护任务负载的均衡,任务可以重新进行分发:将任务从负载重的 CPU 上移动到负载轻的 CPU 上。Linux 2.6 版本的调度器使用负载均衡(load balancing) 提供了这种功能。每隔 200ms,处理器都会检查 CPU 的负载是否不均衡;如果不均衡,处理器就会在 CPU 之间进行一次任务均衡操作。

这个过程的一点负面影响是新 CPU 的缓存对于迁移过来的任务来说是冷的(需要将数据读入缓存中)。

记住 CPU 缓存是一个本地(片上)内存,提供了比系统内存更快的访问能力。如果一个任务是在某个 CPU 上执行的,与这个任务有关的数据都会被放到这个 CPU 的本地缓存中,这就称为热的。如果对于某个任务来说,CPU 的本地缓存中没有任何数据,那么这个缓存就称为冷的

不幸的是,保持 CPU 繁忙会出现 CPU 缓存对于迁移过来的任务为冷的情况。





回页首


挖掘更多潜能

2.6 版本调度器的源代码都很好地封装到了 /usr/src/linux/kernel/sched.c 文件中。我们在表 1 中对在这个文件中可以找到的一些有用的函数进行了总结。

表 1. Linux 2.6 调度器的功能 函数名 函数说明
schedule 调度器主函数。调度优先级最高的任务执行。
load_balance 检查 CPU,查看是否存在不均衡的情况,如果不均衡,就试图迁移任务。
effective_prio 返回任务的有效优先级(基于静态策略,但是可以包含任何奖励和惩罚)。
recalc_task_prio 根据任务的空闲时间确定对任务的奖励或惩罚。
source_load 适当地计算源 CPU(任务从中迁移出的 CPU)的负载。
target_load 公平地计算目标 CPU(任务可能迁移到的 CPU)的负载。
migration_thread 在 CPU 之间迁移任务的高优先级的系统线程。

运行队列的结构也可以在 /usr/src/linux/kernel/sched.c 文件中找到。2.6 版本的调度器还可以提供一些统计信息(如果启用了 CONFIG_SCHEDSTATS)。这些统计信息可以从 /proc 文件系统中的 /proc/schedstat 看到,它为系统中的每个 CPU 都提供了很多数据,包括负载均衡和进程迁移的统计信息。





回页首


展望

Linux 2.6 调度器从早先的 Linux 调度器已经跨越了一大步。它极大地改善了最大化利用 CPU 的能力,同时还为用户提供了很好的响应体验。抢占和对多处理器体系架构的更好支持使整个系统更接近于多桌面和实时系统都非常有用的操作系统。Linux 2.8 版本的内核现在谈论还为时尚早,但是从 2.6 版本的变化中,我们可以期望会有更多的好东西。



参考资料

学习

获得产品和技术
  • Linux Kernel Archives 上,查找最新的 Linux 内核。

  • 订购免费的 SEK for Linux,这有两张 DVD,包括最新的 IBM for Linux 的试用软件,包括 DB2®、Lotus®、Rational®、Tivoli® 和 WebSphere®。

  • 在您的下一个开发项目中采用 IBM 试用软件,这可以从 developerWorks 上直接下载。


讨论


关于作者

M. Tim Jones

Tim Jones 是一名嵌入式软件工程师,他是 GNU/Linux Application ProgrammingAI Application Programming 以及 BSD Sockets Programming from a Multilanguage Perspective 等书的作者

分享到:
评论

相关推荐

    Linux操作系统的内核编译内幕详解

    Linux操作系统的内核是整个系统的核心,它管理着进程调度、内存管理、设备驱动、文件系统和网络协议,直接影响到系统的性能和稳定性。Linux的一大特色就是它的开源性,内核源代码可在/usr/src/linux目录下找到,这...

    若干源程序资料12.rar

    2012-06-11 21:44 6,947,979 Linux内核完全注释V3.0书签版(带源码).rar 2012-06-11 21:31 11,599 MATLAB仿真程序OFDM程序.txt 2012-06-11 21:37 14,584,477 msdn for vb6.0简体中文版.zip 2012-06-11 21:02 12,288 ...

    刘嘉怡.中期检查.doc

    刘嘉怡.中期检查.doc

    COMSOL热电效应模型:基于MATLAB API的热电转换仿真与优化

    内容概要:本文详细介绍了如何使用COMSOL Multiphysics进行热电效应仿真的全过程。首先解释了热电效应的基本概念及其应用场景,如手机充电发烫、吹风机温度升高等。接着,通过具体实例展示了如何在COMSOL中建立热电模型,包括选择合适的物理场(焦耳热和热电效应)、设定材料属性(电导率、导热系数、塞贝克系数)、绘制几何形状以及设置边界条件。文中还提供了详细的MATLAB代码片段用于自动化建模流程,涵盖求解器配置、网格划分、后处理等方面的技术细节。此外,作者分享了一些常见问题的解决方案,如求解器不收敛、网格畸变等。 适合人群:对热电效应感兴趣的科研人员、工程技术人员及高校学生,尤其适用于有一定COMSOL和MATLAB基础的学习者。 使用场景及目标:帮助读者掌握热电效应的基本原理和COMSOL仿真技能,能够独立完成从模型构建到结果分析的完整流程。目标是提高热电转换系统的效率,优化设计参数,探索新材料的应用潜力。 其他说明:文章不仅提供了理论指导,还包括大量实战经验和技术技巧,有助于解决实际建模过程中遇到的问题。

    汽车内外饰模具设计规范详解:分型面、斜顶滑块及模架顶出系统的技术要点

    内容概要:本文深入探讨了汽车内外饰模具设计的关键要素,涵盖分型面设计、斜顶和滑块的应用、模架选择以及顶出系统的配置。针对每个部分,不仅提供了理论指导,还辅以Python、MATLAB等编程语言的实际代码示例,帮助理解和实施具体设计方案。例如,分型面设计强调了如何根据产品结构和外观要求确定最佳分型面位置;斜顶和滑块部分讨论了不同类型及其应用场景;模架和顶出系统则关注于结构稳定性和顶出效果的优化。 适合人群:从事汽车模具设计的专业人士,尤其是希望深入了解内外饰模具设计细节的新手设计师和技术人员。 使用场景及目标:适用于汽车内外饰模具设计项目,旨在提高模具设计的精度和效率,减少试错成本,确保产品质量。通过学习本文提供的技术和实践经验,能够更好地应对实际工作中遇到的各种挑战。 其他说明:文中提到的代码示例和经验公式均来源于实际工程案例,具有较高的参考价值。同时,作者还分享了许多宝贵的行业经验和技巧,有助于读者快速掌握模具设计的核心技能。

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    python3.10以上 可安装pyside6(类似pyqt),具体安装操作步骤

    【人工智能领域】DeepSeek AI深度探索平台的优势解析:多模态处理、低成本训练与广泛应用场景综述

    内容概要:DeepSeek AI是由杭州深度求索人工智能基础技术研究有限公司于2025年1月20日发布的深度探索AI技术。它具有多模态能力、多语言支持、长上下文理解、领域垂直优化、开源特性等多项技术突破,支

    IIS配置phpweb服务器所需VC-redist.x64.rar

    IIS配置phpweb服务器所需VC_redist.x64.rar

    云南移动5G-A网业战略发展探讨 -创新领航,千帆竞发,共同迈入5G-A新时代.pptx

    云南移动5G-A网业战略发展探讨 -创新领航,千帆竞发,共同迈入5G-A新时代.pptx

    C#学习之OpenCv实现模版匹配案例

    本文描述了如何使用C#基于OpenCvSharpe实现模版匹配功能,其中实现了下功能: 1、图像加载; 2、模版加载、绘制、保存功能; 3、模版匹配功能。

    【软件工程与数据分析】数据结构求职面试问题汇总:涵盖链表、树结构及算法复杂度分析的实战题目解析

    内容概要:本文档汇集了CSci 235软件设计与分析II课程中关于数据结构的面试题,由Stewart Weiss教授整理。文档涵盖了广泛的数据结构主题,包括但不限于链表(如单链表、双向链表、循环链表)、二叉树(如二叉搜索树、最小高度二叉搜索树)、栈、队列等。每个问题都旨在考察求职者对不同数据结构的理解及其应用场景。例如,选择合适的数据结构实现手机通讯录功能,或设计支持撤销功能的文本编辑器。此外,文档还探讨了复杂度分析(Big-O表示法),以及如何优化特定操作的时间复杂度。最后,文档提供了额外的学习资源链接,帮助求职者进一步准备面试。 适合人群:计算机科学专业的学生或有志于从事软件开发工作的求职者,特别是那些希望在技术面试中表现优异的人士。 使用场景及目标:①理解并掌握常见数据结构的基本概念和特性;②学会根据不同场景选择最合适的数据结构;③掌握常见数据结构操作的时间复杂度分析;④为技术面试做充分准备,提高面试成功率。 其他说明:文档中的问题不仅限于理论知识,还包括实际编码练习,建议读者在学习过程中动手实践,以加深理解和记忆。同时,文档提供的额外资源链接可以作为扩展阅读材料,帮助读者更全面地掌握相关知识。

    【路径规划】基于matlab A_Star融合灰狼算法GWO求解多仓库机器人送货路径规划【含Matlab源码 13134期】.zip

    Matlab领域上传的视频是由对应的完整代码运行得来的,完整代码皆可运行,亲测可用,适合小白; 1、从视频里可见完整代码的内容 主函数:main.m; 调用函数:其他m文件;无需运行 运行结果效果图; 2、代码运行版本 Matlab 2019b;若运行有误,根据提示修改;若不会,私信博主; 3、运行操作步骤 步骤一:将所有文件放到Matlab的当前文件夹中; 步骤二:双击打开main.m文件; 步骤三:点击运行,等程序运行完得到结果; 4、仿真咨询 如需其他服务,可私信博主; 4.1 博客或资源的完整代码提供 4.2 期刊或参考文献复现 4.3 Matlab程序定制 4.4 科研合作

    帆软本地打印插件FinePrint 8.0版本

    帆软本地打印插件FinePrint 8.0版本,适用于FineReport8

    【嵌入式控制系统】基于EECS461课程的嵌入式控制技术在汽车领域的应用与发展:从基础概念到未来挑战了文档的主要内容

    内容概要:本文介绍了密歇根大学EECS 461课程——嵌入式控制系统的核心内容及其发展背景。课程旨在教授学生嵌入式控制系统的理论与实践,包括传感器和执行器接口、实时性能和安全要求、混合行为系统、分布式控制网络等方面的知识。文中特别强调了现代汽车作为嵌入式控制系统的典型应用,从1977年到2019年间,汽车技术经历了从模拟控制到微处理器控制的巨大变革,如今的汽车具备了更高效、更环保、更安全的特点。课程还涵盖了S32K144微控制器的开发环境、实验室练习(如数字I/O、PWM信号生成、虚拟墙模拟等)以及自动代码生成工具的使用。 适合人群:具备一定编程基础,特别是对嵌入式系统感兴趣的本科生和研究生,尤其是电气工程、计算机科学专业的高年级学生或硕士生。 使用场景及目标:①了解嵌入式控制系统的基本概念和发展历程;②掌握嵌入式控制系统的设计方法和技术手段,如实时操作系统、中断处理、网络通信协议(CAN)等;③通过实际项目操作,熟悉嵌入式硬件平台和开发工具链的应用。 其他说明:随着汽车行业向智能化、自动化方向发展,对于能够开发复杂嵌入式软件的人才需求日益增长。EECS 461不仅为学生提供了扎实的技术训练,也为他们未来的职业发展打下了坚实的基础。此外,课程还反映了跨学科教育的重要性,鼓励学生打破传统学术界限,培养解决实际问题的能力。

    C#与Halcon联合编程实现高效视觉几何定位与测量框架

    内容概要:本文详细介绍了如何利用C#与Halcon联合编程构建高效的视觉几何定位与测量框架。主要内容涵盖模板创建与匹配、圆测量、数据持久化以及图像采集等方面的技术细节。首先,通过创建形状模板并进行匹配,实现了工件的精确定位。接着,针对圆形物体的测量,提出了动态ROI绘制、亚像素边缘提取和稳健圆拟合的方法。此外,还讨论了模板管理和图像采集的最佳实践,确保系统的稳定性和高效性。最后,强调了Halcon对象的内存管理和错误处理机制,提供了实用的优化建议。 适合人群:具备一定编程基础,尤其是对C#和Halcon有一定了解的研发人员和技术爱好者。 使用场景及目标:适用于工业生产线上的自动化检测设备开发,旨在提高工件定位和尺寸测量的精度与效率。主要目标是帮助开发者掌握C#与Halcon联合编程的具体实现方法,从而构建稳定可靠的视觉检测系统。 其他说明:文中提供了大量实战代码片段和调试技巧,有助于读者快速理解和应用相关技术。同时,作者分享了许多实际项目中的经验和教训,使读者能够避开常见陷阱,提升开发效率。

    【人工智能领域】DeepSeek AI核心技术优势及广泛应用场景:推动全球AI创新与产业变革

    内容概要:本文深入探讨了DeepSeek AI的独特优势及其在全球AI领域的影响力。DeepSeek由中国深度求索公司开发,自2025年1月20日发布以来,凭借其卓越的性能和独特优势迅速吸引了全球关注。其核心优势包括:1) 极致成本效率,如低成本训练和高效推理;2) 强大的推理能力,涵盖多领域表现优异

    php连接sqlserver之VC-redist.x64.exe

    php连接sqlserver之VC_redist.x64.exe

    基于Matlab/Simulink的异步电动机恒压频比与转差频率控制仿真及其实现

    内容概要:本文详细介绍了利用Matlab/Simulink进行异步电动机交流调速系统的仿真实验,主要探讨了两种控制方式:恒压频比(V/F)开环控制和转差频率闭环控制。文中不仅提供了具体的数学模型和代码片段,还展示了不同控制方式下的仿真结果对比,包括转速响应、电流波形和谐波含量等方面的表现。此外,文章深入讲解了SVPWM(空间矢量脉宽调制)的应用,强调了其相对于传统SPWM的优势,并给出了详细的参数调整技巧和注意事项。 适合人群:从事电机控制系统设计的研究人员和技术人员,尤其是对Matlab/Simulink有一定基础并希望深入了解异步电动机调速系统的人群。 使用场景及目标:适用于需要进行电机控制算法开发和优化的场合,旨在帮助读者掌握异步电动机调速的基本原理和具体实现方法,提高仿真的准确性和效率。 其他说明:文章通过丰富的实例和图表,生动地展示了各种控制策略的特点和效果,有助于读者更好地理解和应用相关理论。同时,文中提供的调试技巧对于解决实际工程中的常见问题非常有帮助。

    电动汽车等速工况续驶里程仿真及Matlab实现详解

    内容概要:本文详细介绍了如何利用Matlab进行电动汽车等速工况续驶里程的仿真。首先解释了等速工况的概念及其重要性,接着展示了具体的参数设定,如车辆质量、风阻系数、电池容量等。然后深入探讨了核心算法,包括阻力计算、功率需求、能量消耗以及SOC(剩余电量)的变化过程。文中特别强调了一些常见的陷阱和注意事项,如单位换算错误、电机效率的动态变化等。最后,通过可视化工具展示了仿真结果,并讨论了可能的改进方向,如引入NEDC工况循环和其他动态因素。 适合人群:新能源汽车专业的学生、研究人员以及对电动汽车仿真感兴趣的工程师。 使用场景及目标:①帮助理解和掌握电动汽车等速工况续驶里程仿真的原理和方法;②提供详细的代码实现和注释,便于学习和修改;③用于课程设计、毕业设计或其他研究项目。 其他说明:本文不仅提供了完整的Matlab代码,还包括详细的参数说明和常见问题解析,确保使用者能够顺利运行并理解整个仿真过程。同时,作者还分享了许多实践经验,有助于提高仿真的准确性和实用性。

    【定稿】桂林电子科技大学第七届大学生思政课社会实践优秀成果展示活动实施方案 (1).zip

    【定稿】桂林电子科技大学第七届大学生思政课社会实践优秀成果展示活动实施方案 (1).zip

Global site tag (gtag.js) - Google Analytics