Linux应用程序内存管理的活性分析技术和运行时环境

面向Linux应用程序内存管理的活性分析技术和运行时环境引用此版本：本杰明·多芬实时应用程序内存管理的活性分析技术和运行时环境嵌入式系统巴黎综合理工学院，2021年。英语NNT：2021IPPAT004。电话：03682675HAL Id：tel-03682675https://theses.hal.science/tel-036826752022年5月31日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire626数据流应用程序内存管理的活性分析技术和运行环境巴黎综合理工学院博士论文巴黎电信筹备巴黎综合理工学院（ED IP Paris）博士专业：网络、信息和通信Thèse présentée et soutenue à Sophia Antipolis，le 16 mars 2021，par评审团组成：LaurePetrucci本杰明·多芬巴黎第十三大学校长罗伯特·德西蒙尼INRIA研究主任Sophia Antipolis特别报告员让-弗朗索瓦·内藏INSA Rennes大学校长特别报告员塞缪尔·蒂博法国波尔多-斯特凡·曼奇尼Grenoble Alpes大学硕士安德里亚·恩里奇诺基亚贝尔实验室法国研究工程师雷诺·帕卡莱特Directeur卢多维奇·阿普夫里列巴黎电信局局长NNT：2021IPPAT0042回忆录我对所有可能的人都很仁慈。首先是雷诺·帕卡莱导演，卢多维奇·阿普夫里尔导演，还有安德里亚·恩里奇和拉贝亚·阿梅-布利法。你的想法，你的变化，你的兴趣和你的后续工作ont façonné ce'il est devenu aujourd'hui。谢谢你的陪伴。我希望陪审团成员都能接受。Robert de Simone和Jean-François Nezan的演讲者在重新演讲这首歌时已经过去，我们的改变也允许他们改进。我也感谢劳雷·佩特鲁奇、萨穆埃尔·蒂博和斯特凡·曼奇尼为我的工作和J’adresse现在，我为我的家人感到遗憾，因为他们都是我的亲人，我也从来没有听说过他们3简历Cette thèse a été effectuée à Télécom Paris et a été financé par Nokia Bell LabsFrance.贝尔实验室与在这方面，他们对不同的技术进行了研究，包括对集团间的管理和对系统中记忆能力的饱和。这一工作的动机是在十年后信息系统体系结构的复杂化，特别是在异构体系结构和非均匀存储器访问（NUMA）的通用化方面这一演变在各种类型的信息系统中不断发展，主要体现在多处理器片上系统（MPSoC）和分布式系统的高性能Nous nousintéressons en particulier au problème de la saturation des capacités memoiresdans les systèmes em- barqués utilisés pour le treitement numérique du signal（数字信号处理）.Nos contributions peuvent toutefois être utilisées pour d'autres typesd'applications et de platformes.这是三个人的贡献。第三章中提出的这一主题的主要贡献包括一种防止块间干扰的技术，该技术基于对一种类型的图--记忆排除图（MEG）中的集团的研究Ces graphes représen- tent lesbuffers alloués en mmoire et appropossibilité对构成缓冲区整体的集团的研究不允许分配资源，这使资源记录饱和，以便在调整不同工作费用之间的优先约束时，能够检测到内部冲突和难民情况。 Ces constraintes de précédences sont ajoutées en- tre leconsommateur d'un buffer de la clique et le producteur d'un autre buffer de cettemême clique. L’ajout de la contrainte de précédence entraine une mise à jour du该过程是由一个对应于MEG中存在的饱和度记忆的小集团负责的，以保证不可能饱和。在最大限度地减少对工作费用执行期间的约束的影响的目标中，4contrainte sont sélectionnées en fonadium de deletate在第四章中，我们提出了第二个贡献，这是对由于对记忆资源的管理不善而造成的各集团之间的冲突的另一种看法。IlNous definissons un type我们认为，对这些国家的总体分析足以确保不存在集团间的相互影响，而不需要根据常规分析的规定进行精确的分析这是一个这两项贡献在第5章中的艺术国家问题上具有可比性。第6章详细介绍了我们的三个贡献，对应于第二个贡献的一个实用性分析，即利用最佳生存分析结果开发区块间的一种技术。Cette technique最后，第七章回顾了各种贡献、局限性和改进的可能性。我们建议在对这一问题作出贡献的基础上，在今后的工作中增加更多的途径。5内容目录5图8表10一.背景.111导言. 131.1现代计算平台131.2Deadlocks171.3问题陈述181.4论文贡献201.5概要和大纲212相关工作232.1一.导言. 232.2计算模型242.3排序问题的形式化342.4活动和死锁3862.5数据流应用程序的运行时环境2.6结论48二.捐款513使用内存排除图的533.1导言. 533.2目标平台543.3应用程序和数据库553.4内存短缺593.5结论和限制684有效的活性分析714.1一、导言. 714.2系统模型和设计假设4.3调度自动机754.4控制自动机814.5自动机82的活性分析4.6调度和控制自动机分析4.7数学形式化874.8结论.965实验评估975.1一、导言. 975.2实施细节985.3实验装置995.4最小支持内存1005.5宽容1015.6计算时间1025.7讨论1046运行时环境10776.1导言. 1076.2运行时环境的功能1086.3集成死锁处理策略1106.4运行时环境的架构1126.5结论1297结论1317.1论文的贡献1317.2限制和改进1327.3未来的工作和前景133三.背景材料137缩略语139参考书目1438图目录1.15G解码链（接收端）141.2示例存储器架构162.1同步数据流（SDF）图及其对应的非循环均匀同步数据流（AHSDF）图的应用示例。......................................................................................................................... 252.2参数化接口同步数据应用示例Flow（π SDF）图。S是配置动作者，B是分层动作者........................................282.3一个例子的Petri网，之前和之后发射的一个过渡。............................................. 292.4图2.3中的例子Petri网的可达性图。........................................................................302.5不同类别的Petri网实例用于研究顺序资源分配系统（RAS）. ...........................313.1目标平台的示例逻辑架构......................................................................................... 543.2示例应用程序3.3示例工作负载由4G应用的一次迭代组成，5G应用56的两个并发迭代3.4两个普通期间的应用程序扩展示例......................................................................... 573.5示例AHSDF及其对应的记忆排除图（MEG）。613.6示例应用，其并发执行可能导致存储器短缺643.7更新的应用程序，没有内存短缺654.1活性分析的步骤734.2目标架构744.3单个应用程序的AHSDF示例，带有映射7594.4图4.3中的调度自动机示例4.5图4.3的控制自动机815.1我们实验中使用的两个示例应用程序。边上的数字表示缓冲区大小.....................996.1示例应用和映射1126.2软件架构1136.3作业状态的有限状态机1186.4缓冲区状态的有限状态机1206.5服务器的体系结构。带圆圈的数字对应于示例运行中发送事件的步骤。........12110表的列表1.1RAS192.1死锁处理工具和方法2.2基于任务和基于任务的应用程序。484.1 3种工作负载类型875.1近似方法的最小支持内存大小，与贡献2101的5.2按近似方法计算的允许进度表数量，比较至贡献2102的理论最大值5.3五种方法的计算时间：来自memDAG的三种算法，以及我们对第一和第二贡献的情况10311第一背景13第1介绍1.1现代计算平台当今现场可编程门阵列（FPGA））。这些平台用于多个领域中对处理能力要求较高的实时低功耗应用：从无线通信中的数字信号处理（DSP）到自动驾驶中的图像或视频分析。这些应用受到非常大的存储器带宽和短的存储器延迟的限制，这通常引导设计者采用具有非均匀存储器访问（NUMA）架构的平台，在该架构中，存储器资源分布在多个大小受限的物理存储器上。一方面，这些NUMA体系结构为设计人员提供了满足内存带宽和延迟限制的能力另一方面，存储器在大小上是有限的，并且计算节点通常可以访问物理存储器的有限子集。这使得搜索实时可编程应用程序的有效执行顺序（调度）变得复杂，因为它引入了新的死锁源。本文是巴黎电信和法国诺基亚贝尔实验室合作的一部分因此，本论文的工作主要集中在数字信号处理的嵌入式系统上。 这篇论文的贡献可以理想地放在O-RAN软件的上下文中[3]。14来自RF/ADC14个OFDM符号RX传输块解扰检查并删除CRC码块级联LDPC解码器64QAM解调m点IDFT子载波解映射n点DFT删除循环前缀（CP）1.1.1应用41个代码块图1.1：5G解码链（接收端）数据流应用程序由一组代表不同计算的任务组成任务表示为依赖图的顶点，其中边表示任务之间的优先约束和通信。例如，图1.1显示了5G解码链，其中解扰任务将在64 QAM解调任务之后执行，因为后者产生前者使用的输入数据具有多个迭代的应用程序可以作为独立的应用程序进行分析还可以同时分析多个迭代，当应用程序图中存在（或可以添加）某些依赖性约束时，这很例如，如果迭代n+1中的任务t不应该在迭代n中的t之前完成，则与将两个迭代视为独立的相比，同时分析多个迭代降低了复杂度。1.1.2计算系统体系结构的演变在过去的几十年中，应用程序的复杂性及其性能要求的稳步增长导致了随着它们变得越来越复杂，现代计算系统也变得越来越难以编程。从同质到异质第一个计算平台的体系结构，如ENIAC和EDVAC，只有一个计算单元，只允许在一个计算机中执行程序。15完全顺序的方式。在一个平台上使用多个计算单元很快成为一种明显的提高计算性能的方法，它允许多个计算并行进行。这导致了同构体系结构的兴起，在同构体系结构中，所有计算单元（或处理元件（PE））具有相同的能力，即，任何任务都可以在任何PE上运行。同构架构可能具有不同计算速度的PE，例如一个PE的速度是另一个PE的两倍。但是同构架构也有其局限性，随着对计算能力需求的不断增长，这些局限性受到了挑战。例如，不可能无限地增加通用CPU的速度，诸如能量消耗和散热的物理约束阻止将频率增加到阈值以上。因此，多年来，计算系统的设计者已 经 诉 诸 于 使 用 越 来 越 多 的 异 构 体系 结 构。 例如 ， 称为 片 上 多 处理 器 系 统（MPSoC）的异构嵌入式系统在同一芯片上具有各种类型的处理器。MPSoC的PE提供不同的能力，通常以一些通用CPU以及专用PE（GPU、硬件加速器等）为特征。这意味着并非所有任务都可以在所有PE上运行，而且当任务能够在不同类型的PE上运行时，它们的性能可能会以非线性的方式急剧变化。Marvell OCTEONFusion CNF95xx系列[2]是为4G和5G基站设计的异构平台的一个例子。对于智能手机和平板电脑平台，我们可以引用三星Exynos和高通Snapdragon系列。Xilinx ZynqUltraScale+[72]系列的片上系统（SoC）是为基于FPGA的数字信号处理领域设计的示例异构平台。存储器架构计算系统的存储器架构取决于目标平台，并且可以分为不同的类别。在具有统一存储器访问（UMA）的平台中，每个存储器单元可以由所有PE访问，并且对于每个PE，对单元的访问速度是相同的。图- ure1.2a示出了具有多个存储器单元的UMA图1.2b显示了一个带有多个内存单元的NUMA平台示例。在NUMA体系结构中，PE和内存单元之间的访问时间取决于16(a) 示例统一存储器AC-cess平台（b）示例非均匀存储器访问平台图1.2：示例内存架构在所考虑的PE/单元对上。一些PE甚至可以使其存储器访问仅限于存储器单元的一个或子集。一个典型的例子是硬件加速器PE与其工作存储器紧密耦合，并且不能访问系统中的任何其他存储器另一个参与者，例如直接存储器访问（DMA）引擎，然后用于将数据移入和移出PE1.1.3现代MPSoC随着现代MPSoC架构的复杂性增加，其制造商开始提供称为软件设计工具包（SDK）的开发工具。SDK是一组工具，如库，编译器，运行时环境等，旨在简化平 台 的 开 发 。 示 例 商 业 SDK 包 括 Xilinx[71] 、 Intel[5] 或 数 据 平 面 开 发 工 具 包（DPDK）[1]等提供的SDK。平台SDK的质量尽管如此，大多数用于现代MPSoC的SDK不提供针对死锁处理的功能。因此，软件开发人员需要确保系统处于安全状态或可以从不安全状态恢复官方SDK中缺乏死锁处理工具，这使得为这些平台开发的任务更加困难一17本论文的目的之一是通过提供设计时和/或运行时的工具，为MPSoC提供死锁处理，以解决SDK中缺乏死锁处理策略的问题。1.2死锁死锁是一种情况，其中一组进程每个都等待另一个进程采取行动，以便能够继续执行，因此没有进程能够继续。这些过程可以表示算法计算，但也可以表示例如平台内部的数据通信。当不同的进程占用资源（内存缓冲区、通信节点等）时，就会发生死锁。在这种情况下，任何进程都无法访问完成其任务所需的所有资源。多年来，已经开发了许多技术来解决死锁问题。这些技术通常分为三种主要类型。第一，死锁预防技术，旨在确保在设计时，一旦系统运行，死锁不会发生。这些技术集中在固定约束方面，可以静态分析其优点在于没有运行时机制。它们的主要缺点是执行分析的高静态成本，或者过度保守导致运行时灵活性降低。死锁预防用于资源有限的系统，如嵌入式系统，由于其运行时间开销低，以及安全关键领域，如航空电子设备，医疗设备等，其中应不惜一切代价避免死锁的发生。其次，死锁检测和恢复技术的重点是让系统自由运行，并定期检查是否发生死锁。当监视器检测到死锁时，系统将回滚到安全状态，例如通过将系统恢复到先前的状态，或通过丢弃某些计算结果（必须重新执行）。死锁检测和恢复的一个重要优点是在运行时执行操作的灵活性。恢复机制仅在需要时使用，因此不会约束执行。死锁检测和恢复由于需要监视而具有一些运行时开销此外，恢复机制可能是昂贵的18或者需要再次执行一些昂贵的计算，其结果在过程中丢失。因此，死锁检测和恢复被用于具有足够资源来处理运行时开销的系统中，并且对于该系统，死锁的发生对于恢复的成本是可接受的是足够罕见的例如，在用于大数据的一些高性能计算（HPC）第三，死锁避免技术，它指导系统的执行，以确保在运行时不采取导致死锁的决策至于死锁预防，与死锁检测和恢复相反，它们的目标是确保没有死锁发生。区别在于死锁避免使用系统执行的运行时控制.这些技术通常比死锁预防更灵活，但确实会产生一些运行时开销。在死锁检测和恢复成本太高的情况下，如果系统具有完全的运行时灵活性，则死锁的相对频率，或者由于缺乏可用于执行恢复的资源而完全不可能。解决死锁问题的这三种主要策略，以及每种策略的现有方法的选择，将在下一章中详细介绍1.3问题陈述本文的工作主要是针对计算机系统中由于内存不足而产生的死锁问题，设计并实现了解决死锁的方法。本论文不涉及通信引起的死锁问题，也不旨在解决在不同类型的系统，如分布式系统，高性能计算（HPC）等中发生的死锁。我们的目标是嵌入式系统，如MPSoC，我们表示为资源分配系统（RAS）。简单地说，RAS旨在表示进程对一组资源的使用，每个资源具有固定的容量，每个进程需要分配给给定数量的资源来执行。RAS将在下一章中详细介绍。在本论文的工作中，我们考虑了三种资源：PE、通信单元和存储单元。每一个人-19存储器端口被认为是单独的通信资源，并且存储器仅根据其容量（存储器空间）来引用。PE和通信单元的容量是1，存储单元的容量是它们的大小。Coffman等人[19]确定了死锁发生的四个充分必要条件.• 互斥：任务需要独占使用资源，每个资源要么分配给单个任务，要么可用。• Hold-and-wait：一个任务在请求额外资源的同时至少持有一个资源。• 无抢占：在持有资源的任务结束之前，不能挂起或取消资源所有权。• 循环等待：存在一组任务{t1，t2，. . . .在我们的RAS中，这些情况的发生率总结见表1.1。条件处理通信存储器存储器表1.1：RAS中死锁的发生率在我们的RAS中，互斥不会发生在（纯理论）有限内存的情况在内存单元中可能会出现保持和等待的情况，因为一些输入缓冲区可能已经被分配，而其他输入缓冲区尚未被分配。我们假设处理节点上的任务没有抢占，这是高端数据中非常常见的情况接种（无限） （有限）互斥真真假真保持等待假假真真没有优先权真真真真循环等待假真假真死锁风险没有没有没有是的