多核操作系统中的线程调度与性能优化

0计算机科学博士论文0多核操作系统中的线程调度0如何理解、改进和修复您的调度程序0Redha GOUICEM0巴黎第六大学计算机实验室InriaWhisper团队0博士答辩：2020年10月23日，法国巴黎0评审委员会成员：0Pascal Felber先生，纳沙泰尔大学终身教授，评审人 VivienQuéma先生，格勒诺布尔国立理工学院（ENSIMAG）终身教授，评审人 RachidGuerraoui先生，洛桑联邦理工学院终身教授，考官 KarineHeydemann女士，巴黎第六大学副教授，考官 Etienne Rivière先生，鲁汶大学终身教授，考官 GillesMuller先生，Inria高级研究科学家，指导老师 Julien Sopena先生，巴黎第六大学副教授，指导老师0摘要0在这篇论文中，我们从几个角度解决了多核架构的调度程序问题：设计（简单性和正确性）、性能改进以及开发特定应用程序的调度程序。所提出的贡献总结如下：0•Ipanema，一种专门用于多核架构的线程调度器的领域特定语言。我们还在Linux内核中实现了一种新的抽象，可以动态添加用Ipanema编写的调度程序。0•一系列性能和错误跟踪工具。借助这些工具，我们表明Linux调度程序CFS在现代处理器上存在与频率管理相关的问题。我们提出了一个解决方案，以补丁的形式提交给社区。这个补丁可以显著提高许多应用程序的性能。0•一个以“特性树”形式建模调度程序。我们独立实现这些功能，以提供全新的模块化调度程序。这种模块化调度程序使我们能够全面研究不同功能的组合，从而为特定应用程序的调度程序开发铺平道路。0iiiDans cette thèse, nous traitons du problème des ordonnanceurs pourarchitectures multi-coeur en l’abordant sous plusieurs angles: celuide la conception (simplicité et correction), celui de l’amélioration desperformances et enfin celui du développement d’ordonnanceurs surmesure pour une application. En résumé, les contributions présentéessont les suivantes:• une série d’outils de recherche de bogues de performance. Grâceà ces outils, nous montrons que l’ordonnanceur de Linux, CFS,souffre d’un problème lié à la gestion de la fréquence sur lesprocesseurs modernes. Nous proposons une solution à ce prob-lème sous la forme d’un patch soumis à la communauté. Cepatch permet d’améliorer significativement les performances denombreuses applications.v0摘要0•Ipanema，一种专门用于多核处理器线程调度器的领域特定语言。我们还在Linux内核中实现了一种新的抽象，可以动态添加用Ipanema编写的调度程序。0•一个以“特性树”形式建模调度程序。我们独立实现这些功能，以提供全新的模块化调度程序。这种模块化调度程序使我们能够全面研究不同功能的组合，从而为特定应用程序的调度程序开发铺平道路。0致谢0尽管这篇论文以我的名字命名，但它是四年来与其他研究人员、同事、朋友和家人合作、讨论和支持的结果。研究不是孤立个体的工作，而是在自己的书桌上进行的协作企业，也发生在咖啡休息时间或家庭晚餐时。话不多说，让我们感谢参与这项工作的每个人。0首先，我要感谢审稿人Pascal Felber和VivienQuéma，他们花时间仔细阅读和评估这篇论文。我还要感谢考官RachidGuerraoui，Karine Heydemann和EtienneRivière，他们同意成为评审委员会的一部分。0没有Gilles Muller和JulienSopena的指导和监督，这篇论文是不可能完成的。Gilles，你在撰写论文和汇聚合适的人才方面的专业知识让这篇论文比原本更容易。我会努力保持从你那里学到的清晰表达观点的严谨性。尽管过去两年的环境非常困难，但每当我需要帮助时，你总是在那里并且乐意提供帮助。Julien，你是激发我对系统和研究兴趣的人之一。每天与你一起工作都是一种愉快，充满了各种想法，每一个都比前一个更疯狂，但总是相关的。我永远感激你在科学家和人类方面教给我的一切。非常感谢你们两位让我度过了这四年的兴奋时光。你们两位教会了我如何进行良好的系统研究，我希望能达到你们的期望。我还要特别感谢JuliaLawall，她虽然不是我的官方导师，但在这四年里她对我提高写作和批判性思维方面帮助很大。另外特别感谢我的合著者们Baptiste Lepers，Jean-PierreLozi和NicolasPalix，他们陪伴我一起完成了这项工作。和你们每一个人一起工作并分享所有这些富有成效的讨论，提高了我的工作质量，这真是太棒了。0博士生活可能会很紧张，让你想要放弃。当这些时刻到来时，身边有一群团结的人是至关重要的。这种团结精神在LIP6特别强大，尤其是在我花了大部分时间的三个团队Whisper，Delys和MoVe中。0viiAnd last, but not least, I would like to thank my family for theirunwavering support since always. Mom, Dad, I will never be ableto repay you for all you did for me. You always pushed me to workhard and I am glad I listened to you. To my brothers Djelloul, Hichem,Mourad, and my sister Amel, thank you for helping me become theman I am now and supporting me all these years.These acknowledgments have proved to be longer and more seriousthan I initially intended before starting writing. For once, I have triednot to make jokes for more than five minutes straight, and that isa challenge I would probably not have been able to overcome fouryears ago. Again, thanks to each and every one of you, and if I forgotanyone, please forgive me, it was probably unintentional.viii0当我开始我的博士学位时，我受到了一群非凡的人的欢迎，他们让我的融入变得容易。我真的很想感谢Antoine，Gauthier和Damien，他们对我和许多其他学生都是导师。我希望我对新生的教导能像你们对我的那样好。我还要感谢所有其他博士生和实习生，我有幸与他们共度美好时光：Alexandre，Arnaud，Bastien，Cédric，Célia，Daniel，Darius，Denis，Dimitrios，Florent，Francis，Gabriel，Guillaume，Hakan，Ilyas，Jonathan，Laurent，Lucas，Ludovic，Lyes，Marjorie，Maxime，Pierre，Saalik，Vincent，Yoann。为了不冒犯任何人，名单按字母顺序排列 :)0我也特别感谢高年级研究人员和学生之间的良好氛围。我要感谢他们所有人作为老师和/或同事传授给我的知识。对Jonathan，Luciana，Marc，Pierre，Pierre-Évariste和Swan，谢谢一切。特别感谢KarineHeydemann，在我有些迷茫时帮助我选择申请哪个硕士课程。我仍然记得将近7年前的那次讨论，对此我心存感激。0除了实验室的所有朋友，我还要感谢那些完全不了解计算机科学研究意味着什么但仍然支持我的人。Liazid，Manil，Sami，除了开心的笑声，我知道如果我在任何事情上需要帮助，你们会是第一个答应帮助我的人，我为此感激不尽。感谢LSCHandball的所有队友，我们保持了强烈的团队精神，无论是胜利还是失败。没有你们，我可能有时会变得有点疯狂。特别感谢Ilyas和Maxime，感谢你们带给我的欢乐和计算机科学的时刻。很高兴自从我们在大学的长凳上相识以来，能把你们算作我的朋友。TA B L E O F C O N T E N T S1introduction11.1Scheduler Development . . . . . . . . . . . . . . . . . .21.2Performance Enhancement. . . . . . . . . . . . . . . .31.3Application-Specific Schedulers . . . . . . . . . . . . . .31.4Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . .42thread scheduling52.1Execution Entities . . . . . . . . . . . . . . . . . . . . . .52.2Hardware Resources . . . . . . . . . . . . . . . . . . . .62.3Thread Scheduling . . . . . . . . . . . . . . . . . . . . .102.4Scheduling in the Linux Kernel . . . . . . . . . . . . . .182.5General-Purpose Operating System Schedulers . . . . .242.6User-Level Schedulers. . . . . . . . . . . . . . . . . . .362.7Hypervisor Schedulers . . . . . . . . . . . . . . . . . . .392.8Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .413writing schedulers with ipanema433.1The Ipanema Tool Chain . . . . . . . . . . . . . . . . . .443.2The Domain-Specific Language Approach . . . . . . . .453.3The Ipanema DSL Through Policies. . . . . . . . . . .503.4Scheduler as a Kernel Module . . . . . . . . . . . . . . .543.5Property Verification . . . . . . . . . . . . . . . . . . . .593.6Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . .623.7Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .674frequency-informed scheduling decisions694.1Example of a Performance Bug in CFS . . . . . . . . . .694.2Monitoring and Visualization Tools. . . . . . . . . . .704.3Investigating the Performance Bug . . . . . . . . . . . .744.4Dynamic Frequency Scaling . . . . . . . . . . . . . . . .784.5Handling Frequency Inversions in CFS. . . . . . . . .864.6Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . .884.7Discussion . . . . . . . . . . . . . . . . . . . . . . . . . .1024.8Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .1035feature-oriented scheduler analysis1055.1Feature Analysis of CFS . . . . . . . . . . . . . . . . . .1065.2Feature Model of a Scheduler . . . . . . . . . . . . . . .1105.3Feature Evaluation. . . . . . . . . . . . . . . . . . . . .1155.4Finding the Best Scheduler for an Application . . . . .1285.5Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . .129ixxtable of contents06 结论13106.1调度器开发13106.2性能增强13206.3特定应用程序的调度器1330出版物 1350生成的软件1360参考文献 1390索引1610首字母缩略词 162110介绍01951年，Ferranti Mark1和UNIVAC计算机发布。这两台机器是第一批商用的图灵完备机器，能够以打孔纸带的形式执行任意程序。由于价格昂贵，这样的机器只有政府机构、大学和大公司购买。20世纪50年代最流行的计算机IBM 650的成本为50万美元（2020年相当于476万美元）。0它们执行了大量不同的程序，从科学计算到会计和国家普查。这些机器由人类操作员操作，将代码和数据加载到机器中，等待计算完成并检索结果。这些操作员在它们的正常运行中起着基础作用，因为他们确保程序的执行顺序。这是调度的第一种形式。随着计算机处理能力的增加，人工操作的成本与计算时间相比变得重要。为了最小化这一成本，计算机设计者试图将调度器作为计算机的一部分，并取代人工操作员。随着1955年操作系统（OSs）的引入，第一个软件调度器作为计算机资源管理的中心组件出现。从那时起，开发了大量的调度算法。它们针对不同的工作负载和性能目标。一些服务器应用程序需要最小化其请求的延迟，而批处理应用程序需要最大化吞吐量。对于个人计算机和智能手机，用户的交互性至关重要。另一方面，嵌入式设备在服务质量和遵守截止日期方面可能有严格的要求。调度器还受到了计算机底层硬件组件的发展的影响，无论是中央处理单元（CPU）、内存还是输入/输出（I/O）设备。多核处理器的出现扩展了调度器的工作。除了管理程序应该何时执行外，它还必须选择在哪个核心上执行。非均匀存储访问（NUMA）架构、异构处理器和存储器层次结构进一步复杂化了正确分配计算资源的问题。02 介绍0工作负载和用户需求的多样化以及硬件的惊人发展一直是调度器发展的推动力。将硬件复杂性和软件要求结合起来，极大地加大了调度器的决策过程，并增加了其设计的复杂性。0在这篇博士论文中，我们研究了线程调度以及它对应用程序性能的影响。我们旨在为调度器开发人员提供新的工具，帮助他们进行工作。我们的工作可以分为三个方面：调度器开发，性能增强和特定应用程序的调度器。01.1调度器开发0第一个轴，调度器开发，旨在简化在操作系统中开发新调度器的过程，同时保持高水平的安全性。开发调度器很困难，因为它涉及多个专业领域：调度理论、低级内核开发和硬件架构。这大大增加了开发过程中出现错误的可能性。调度算法中的错误可能导致重要属性在开发者不知情的情况下被违反。由于在操作系统内核中进行开发的困难，实现错误经常发生，并可能导致系统崩溃。最后，对硬件架构了解不足可能导致由于诸如内存延迟或异构计算单元等因素而导致调度策略低效。我们的目标是通过提供易于学习的高级领域特定语言（DSL）来消除对内核开发专业知识的需求，该语言将被编译为可在Linux中使用的C代码。我们的编译器通过禁止非法操作并自动生成诸如锁管理之类的代码，有助于提高代码的安全性。DSL的抽象还将包括硬件拓扑，以帮助开发人员考虑这一点。我们还希望通过允许通过我们的DSL进行调度属性的形式验证来避免算法错误。此外，我们还为Linux提供了一个新功能，即作为内核模块的调度器或SaaKM。有了这个功能，我们可以在运行时插入新的调度策略。然后每个应用程序可以决定使用哪种策略。我们的Ipanema编译器生成的C代码与SaaKM兼容。借助SaaKM和我们的DSL，我们开发和测试了多个调度器，例如Linux调度器的简化版本，在我们评估的应用程序集上的性能与原始版本相似。1.2 performance enhancement3develop a version of this scheduler proven to be work-conserving thatoutperforms the original on some applications.1.2performance enhancementThe second axis, performance enhancement, aims at helping sched-uler developers finding performance bugs. These bugs do not causecrashes but silently eat away at performance. They are therefore hardto notice and solve. There are two ways of detecting such bugs: pro-ducing a better scheduler that does not suffer from this bug, or usingprofiling tools that highlight the bug.We design monitoring tools to efficiently profile the behavior ofschedulers, and visualization tools to easily track performance bugsand identify their origin. These tools enable us to record schedulingevents at run time without disturbing application behavior and with ahigh resolution. They also allow us to visualize specific data such asthe CPU usage of each core, their frequency or all scheduling events.With these tools, we detect a new problem, frequency inversion,that stems from modern per-core dynamic frequency scaling and thescheduler unawareness of CPU frequency in its thread placementdecisions. This problem triggers situations where high frequency coresare idle while low frequency cores are busy. After finding the rootcause of this problem, we propose two solutions for Linux to solve theproblem and thoroughly evaluate them. The best solution has beensubmitted to the Linux community for review.In addition, we also provide a detailed analysis of the behavior ofthe frequency scaling algorithm on multiple CPUs. This analysis waspossible thanks to our monitoring tools and further strengthens ourbelief that schedulers must account for the frequency of cores.1.3application-specific schedulersThe third and last axis, application-specific schedulers, aims at help-ing software developers use the best possible scheduler for their appli-cation instead of always using the default scheduler of the OS. Eventhough general-purpose schedulers try to be generic and offer goodperformance for most workloads, they are not able to always offerthe best performance. This is mainly due to two major problems: thestructure and size of their code, and the necessary configuration.The structure and size problem is prominent in general-purposeschedulers such as Linux’s CFS. They tend to be large, with a consid-erable number of features. These features also tend to be intertwined,be it in terms of code or impact. This increases the likelihood of safetyor performance bugs, and hardens the maintenance of the code.The choice to be generic also creates a fundamental problem: sincethe expectations of users differ and are sometimes conflicting, it is4introductionimpossible to always satisfy everyone. To overcome this problem, mostgeneral-purpose schedulers are configurable through static configura-tions at compile time or dynamically at run time. Due to the difficultyof finding the correct configuration for a given workload, most usersjust use the default values provided by their OS. For more advancedusers, there also exist a multitude of user-provided configurations andtips on system administrator forums on the internet.We propose to start building an actual modular scheduler fromscratch. To do so, we develop a feature model of a scheduler whereeach feature is implemented independently, making it easy to extend.This model also allows for an evaluation of each feature separatelyfrom the others. With such an evaluation, we propose methodologiesto find the most adapted features for a given workload. Finally, wepropose methodologies to build application-specific schedulers fromthis data.1.4outlineThe remaining of this document is organized in five chapters. Chap-ter 2 presents the technical background and the state-of-the-art onthread scheduling. It lays off the needed knowledge to understandour contributions. Chapter 3 presents our first contribution, Ipanema,a DSL for schedulers. We present the design of the language, its toolchain and an evaluation of multiple policies we implement in Ipanema.Chapter 4 presents our second contribution, the identification of anew problem, frequency inversion, and strategies to solve it. Thisproblem stems from modern implementations of frequency scalingon CPUs and current general-purpose schedulers’ behavior duringthread placement. We present the problem through a detailed casestudy and propose two strategies to solve this problem in Linux thatwe extensively evaluate on multiple machines. Chapter 5 presents ourlast contribution, a feature model of a thread scheduler. This modelis designed with the objective of evaluating scheduler features indi-vidually in order to design application-specific schedulers. We presentvarious methodologies that help finding the best suited scheduler fora given application. Finally, Chapter 6 concludes this thesis with asummary of our work and contributions, and discusses future workand perspectives.250线程调度0本章旨在定义贯穿本论文的线程调度的基本概念，并为读者提供必要的技术背景，以理解我们的贡献。线程调度器是系统中管理计算资源分配的组件。在本章中，我们首先定义了线程调度器管理的硬件和软件资源。然后我们详细描述了线程调度器是什么以及它们如何操作。最后，我们描述了线程调度在各种系统中的实现，重点关注Linux。02 . 1 执行实体0在操作系统理论中，有多个概念描述软件以及它应该如何执行：线程、进程、任务等。计算机科学家倾向于混合使用这些术语，通常在其上下文中没有丢失意义。然而，在这篇关于调度的论文中，使用一个术语而不是另一个术语将是一个错误，并导致误解。本论文将使用以下定义，以避免这种误解。图 2 . 1总结了每个描述的实体之间的层次关系。0线程。线程是执行指令的实体，也是线程调度器操作的最小实体。它通常表示为指令指针（IP）、堆栈指针（SP）和寄存器。当线程调度器分配计算资源时，线程执行其IP指向的指令。线程可以在内核级或用户级进行处理。内核线程由操作系统的内核管理，而用户线程由用户级程序（如语言运行时或库）操作。最终，用户级线程被映射到内核线程，以便由操作系统的内核进行调度。在本论文中，除非另有说明，否则术语“线程”将用于内核线程。0进程。进程表示一组资源，包括内存映射、文件描述符、套接字等。一个进程至少被一个线程使用。如果多个线程共享一个进程，则需要进行通信。06 线程调度0程序0进程线程0进程0线程 线程0图 2 . 1：具有多线程进程的程序示例。0通过共享资源简化了通信。另一方面，在进程之间进行通信更加繁重，并依赖于操作系统提供的进程间通信机制的使用。0程序。程序，或应用程序，是一组一个或多个进程，包含一个或多个线程，它们合作以实现共同的目标。例如，一个为每个标签生成一个进程的网络浏览器仍然被视为单个程序。0任务。术语“任务”根据上下文有不同的含义。在Linux中，它被用作线程或进程的同义词。在Java语言中，它既是线程的同义词（使用Thread类时），也是可以由任何线程执行的工作单元（使用Executor接口时）。由于这种歧义，在本论文中将不使用术语“任务”。02 . 2 硬件资源0线程调度器是管理系统中计算单元的软件组件。自计算机诞生以来，这些计算单元已经发生了巨大的变化。图 2 . 2显示了现代计算机的硬件拓扑结构。在这种拓扑结构中，有执行单元（核心）、内存加速器（缓存）和主内存。其中一些组件是共享的，而其他组件是独占的。所有这些交互使得计算资源的分配对于调度器来说是一项复杂的工作。我们将介绍不同的硬件组件，它们可能的相互作用以及对线程调度器的影响。02.2.1核心：执行单元0核心，也称为硬件线程，是处理器芯片中找到的最小计算单元。它执行单个线程的指令02.2硬件资源70核心核心0φ核心0核心核心0φ核心0核心核心0φ核心0核心核心0φ核心0L10L10L10L10L20L20L20L20L3 RAM0图2.2：单节点8核机器，每个物理核心（ϕ核心）有两个线程和三级缓存。0一次执行的线程。这是线程调度器管理的实际资源，将其分配给特定时间段的软件线程。核心通常由一组寄存器和计算单元组成。寄存器存储正在运行的线程使用的数据，以及用于管理线程的元数据，如其指令指针或堆栈指针。计算单元执行各种计算，如算术运算（算术逻辑单元（ALU））、浮点运算（浮点运算单元（FPU））或地址计算（地址生成单元（AGU））。0芯片级多处理。自1950年代以来，计算机体系结构方面的大量创新提高了核心的个体性能。指令级并行技术，如指令流水线，推测执行[19]或乱序执行[80]等，从调度的角度来看并没有影响，除了更有效地执行指令。然而，线程级并行技术改变了线程调度器的运行方式，允许多个线程同时运行。芯片级多处理（CMP）通过将多个核心集成到单个芯片中来实现线程级并行。每个核心都是相同的，因此可以独立执行不同的线程。有了CMP，调度器现在可以选择同时运行多个线程。0核心寄存器APU FPUAGU0芯片0核心寄存APU FPUAGU0芯片核心寄存器APU FPU AGU0核心寄存0APU FPUAGU0芯片核心寄存器0单核0CMP0SMT0图2.3：线程级并行实现。0同时多线程。早期，计算机架构师注意到所有计算单元并非同时使用，导致计算资源的浪费。为了解决这个问题，他们引入了同时多线程（SMT）[160]。SMT的思想是在同一个物理核心上运行多个线程，通过复制部分硬件，主要是寄存器。这些副本被称为逻辑核心。例如，英特尔®最常见的SMT实现Hyper-Threading[85]允许每个核心运行两个线程，即对于n个物理核心，有2n个逻辑核心可用。在本论文中，我们将使用术语“核心”来指代逻辑核心，因为调度器会将线程放置在逻辑核心上。08线程调度0在这种核心上。SMT对线程调度产生影响，因为一些操作将无法同时由共享相同计算单元的两个核心执行。图2.3总结了CMP和SMT之间的区别。0非对称架构。一些处理器芯片还具有具有不同功能的核心。这种非对称架构3可以有专门用于某种类型计算的核心3也称为异构架构，如视频或音频解码[71，86，145]。这种架构的另一个用途是嵌入式设备上的能量管理。例如，ARM®big.LITTLE架构[11]有一组低功耗和低性能核心（LITTLE）和一组更强大且耗电量更大的核心（big）。使用其中一组核心对性能和能耗有很大影响。动态电压和频率调节的实现0（DVFS）技术也可以看作是一种不对称性。实际上，如果每个核心可以以不同的频率运行，它们都具有不同的处理能力。这将在第4章中更详细地讨论。02.2.2 缓存：内存访问加速器0当核心执行计算时，它们通常使用主内存中可用的数据。访问这