实时系统端到端约束的概率研究

实时系统端到端约束的概率研究克里斯蒂安·马克西姆引用此版本：克里斯蒂安·马克西姆实时系统中端到端约束的概率研究。系统与控制[cs.SY]。皮埃尔和玛丽居里大学-巴黎第六，2017年。英语NNT：2017PA066479。电话：02003251HAL Id：tel-02003251https://theses.hal.science/tel-020032512019年2月1日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire医生的声音l’UNIVERSIT皮埃尔与玛丽-居里我很高兴Informatique信息、通信和电子（巴黎）学院克里斯蒂安·马克辛为了获得等级E '大学博士皮埃尔与玛丽-居里Sujetdelat`ese：在时间系统中训练出b的概率研究soutenuele11dec'embre2017devantlejurycompos'ede：夫人LilianaCUCU-GROSJEANM. Benoit TRIQUET Coordinateur IndustrielChristineROCHANGE特别报告员M. Thomas NOLTE特别报告员夫人阿里克斯·弹药检查官M. Victor JEGU考官M. George LIMAM. Sascha UHRIG考官内容目录iii1介绍11.1概述。 . . . . . . . . . . . . . . . . . . . . . . . . . .11.1嵌入式系统 . . . . . . . . . . . . . . . . . . . . . . .21.1.2实时域。. . . . . . . . . . . . . . . . . . . . . . .41.1.3航空电子工业。 . . . . . . . . . . . . . . . . . . . . . . . .91.2背景 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .141.2.1表演赛 . . . . . . . . . . . . . . . . . . . . . . . .151.2.2执行时间 . . . . . . . . . . . . . . . . . . . . . . . . . .171.2.3概率和统计。 . . . . . . . . . . . . . . . . . . .211.3论文动机. . . . . . . . . . . . . . . . . . . . . . . . . . . .221.4模型. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .241.4.1概率论中的有用概念。 . . . . . . . . . .241.4.2概率实时系统。 . . . . . . . . . . . . . . . . .262现有技术292.1概率实时系统的时间分析 . . . . . . . . . . .312.2概率方法. . . . . . . . . . . . . . . . . . . . . . . . . .382.3基于测量的概率分析. . . . . . . . . . . . . . .412.4随机化架构 . . . . . . . . . . . . . . . . . . . . . . . .492.5航空电子行业中的时序分析 . . . . . . . . . . . . . . . . . .512.5.1综合模块化航空电子设备（IMA） . . . . . . . . . . . . . .522.5.2航空电子应用的时间分析 . . . . . . . . . . . . .542.5.3混合临界系统。. . . . . . . . . . . . . . . . . . .56我二.目录3EVT在实时领域593.1系统一致性603.1.1输入613.1.2软件623.1.3平台633.2相同的分布式数据643.3独立663.4基于测量的方法 693.4.1WCET估算方法713.4.2测量协议的再现性723.4.3测量协议的代表性723.4.4再现性、代表性和收敛性之间的关系743.5结论764pWCET估计方法774.1广义极值分布4.2广义帕累托分布834.3统计结果的确认4.4根据相关执行时间944.5小变异性数据4.6结论.975实验结果995.1多处理器体系结构基准测试分析995.2航空电子应用分析1055.2.1应用介绍1075.2.2平台特性1145.2.3时间分析结果1275.3结论1566一般性结论1576.1捐款1576.2今后的工作158目录iiiA统计检验161A.1 运行测试161A.2 Kolmogorov-Smirnov检验162A.3 Anderson-Darling检验163图169表171女177参考书目196第1介绍1.1一般性介绍21世纪的人类生活被技术所包围.从家庭到交通，从教育到爱好，从安全到体育，信息学在日常活动中发挥着重要作用。社会互动、教育和保健只是技术快速发展对生活质量产生重大积极影响的几个领域的例子。企业越来越依赖嵌入式系统来提高生产力、效率和价值。在工厂中，机器人的精确性往往会取代人类的多功能性。尽管无人机、智能手表或智能家居等联网设备在过去几年变得越来越流行，但在处理用户安全的行业中，这种技术已经使用了很多年。自1972年生产第一架A300飞机以来，航空电子行业一直在使用计算机进行产品，并在1976年开发第一架协和式飞机时取得了惊人的进步，这被认为是技术的奇迹从协和式飞机上获得的大量创新和知识仍然用于最近的型号，如A380或A350。在航天或汽车行业可以看到技术进化的缓慢开始，但随着OneWeb项目的开始[OneWeb，2015]和自动驾驶汽车的引入，这些领域已经遇到了加速阶段，似乎不会很快休息。在本节中，我们将概述上述行业中使用的技术，重点是12第1章 介绍作为实时领域的一个重要组成部分，关键实时嵌入式系统（CRTES）。1.1.1嵌入式系统在我们这个时代，我们被技术所包围，这些技术旨在改善我们的生活，确保其安全性，或编程以实现不同的功能并尊重一系列限制。我们认为它们是嵌入式系统，或者通常是网络物理系统的一部分。嵌入式系统是一种基于微处理器的系统，用于控制一项功能或一系列功能，而不是像PC那样由最终用户编程[Heath，2002]。用户可以选择有关功能，但不能通过添加或替换软件来修改系统的功能。嵌入式系统由微控制器或数字信号处理器（DSP）、现场可编程门阵列（FPGA）、专用集成电路（ASIC）和门阵列形式的单个或多个处理核心管理这些处理组件与专用于处理电气和/或机械接口的组件集成。嵌入式系统例如，路由器和交换机系统是嵌入式系统，而通用计算机使用适当的OS来实现路由功能。然而，嵌入式路由器在路由功能方面比基于操作系统的计算机更有效商用嵌入式系统的范围从数字手表和MP3播放器到巨型路由器和交换机。复杂性从单个处理器芯片到具有多个处理芯片的高级单元不等。与强调计算元素的嵌入式系统相比，信息物理系统是计算与物理过程的集成[Lee和Seshia，2011]。大多数网络物理系统都包含至少一个嵌入式系统。网络物理系统的术语非常广泛，涵盖了从软件和建模到系统，网络和计算机科学与工程控制的各种研究主题。这些系统的详细概念图见图1.1[Cyber，2010]。这种分类法是一种不断发展的分类法，新的域以连续的方式添加实时系统是任何信息处理系统，它必须在有限和指定的时间内响应外部产生的输入刺激[Burns和1.1.一般性介绍3图1.1：信息物理系统-概念图图片由Edward A. Lee在S. Shyam Sunder [Lee，Edward Ashford，2012].Wellings，2001年]。在这种类型的系统中，正确性不仅取决于逻辑结果，还取决于它被交付的时间没有回应和错误的回应一样糟糕实时系统可以在航空、航天、汽车或铁路等行业中找到，也可以在传感器网络、图像处理、多媒体应用、医疗技术、机器人、通信、计算机游戏或家用系统中找到。根据其截止日期错过重要性，实时系统可以分为以下几类：• 硬实时系统- 在这种情况下，绝对必须在规定的截止日期内做出响应对于这些系统，响应时间的超时 因此，许多这些系统被认为是安全关键的。 如果错过最后期限会危及非常昂贵的过程，则可以将系统视为任务关键型，但不一定是安全关键型。这样的示例4第1章 介绍是空间飞行任务，预算非常高，如果发生事故，即使没有生命危险，财政损失也是相当大的。• 软实时系统- 最后期限很重要，但即使偶尔错过最后期限也能正常这些系统通常与服务质量有关，并且能够容忍最后期限错过，即使它们是不希望的。• 硬实时系统- -软实时系统，但不能从延迟交付服务中获益。对于这些系统，如果响应不及时给出，则计算是过时的。预测系统是这方面的相关例子。• 弱硬实时系统-其中必须满足m个截止日期中的k个（k m）。这些系统会因为太多的最后期限错过而变得不稳定。作为一个例子，我们可以提到反馈控制系统。所有这些系统都有一个与之相关的成本函数。图1.2是这些成本函数的抽象表示。在实时系统和嵌入式系统之间存在着一种包容的关系，因为所有的实时系统同时也是嵌入式系统，但并不是所有的嵌入式系统都有时间约束。另一方面，嵌入式系统和网络物理系统之间没有直接的关系大多数网络物理系统包含一个或多个嵌入式系统作为组成部分，但由于复杂性的差异，它们的名称不能互换。在这篇论文中，我们专注于实时嵌入式系统，为了便于标记，我们简单地将它们命名为实时系统。如果是这样的话，我们可能会提到网络物理1.1.2实时域实时系统的原理首先由Stankovic在[Stankovic，1988]中定义，从那时起，这个概念就成为航空电子、汽车或航空航天等主要行业的重要组成部分。Liu和Layland引入的基本模型[Liu和Layland，1973]考虑了一组任务Γ的存在性，n个任务τi=（Oi，Ci，Pi，Di），其中i = 1. n，其特征在于偏移Oi，最差1.1.一般性介绍5图1.2实时系统案例执行时间Ci、周期Pi和截止日期Di。为了保证这种系统的可行性，所有的任务必须在截止日期之前完成随着时间的推移，这种模式产生了新的相关概念。以下是一些常见的任务的最坏情况执行时间（Worst Case Execution Time，WCET）表示任务执行所需的最大时间。WCET是在分析之后获得的，并且大多数时候它不能通过用尽所有可能的执行来准确地确定。这就是为什么在工业中，测量仅在可能的场景的子集上进行（将生成最高执行时间的场景），并且通过将安全裕度添加到最大观察时间来估计执行时间界限。在相反的方面，我们遇到了最佳情况执行时间（BECT）的概念，它表示任务可以执行的最小时间长度关于WCET概念的详细报告由Wilhelm等人在[Wilhelm等人， 2008年]。任务的偏移量是任务应该开始的确切时间6第1章 介绍i=1而抖动是其周期性的偏差。虽然偏移在任务的生命周期中一次发生，但抖动可以在任务的多个偏移可以由系统或编程器定义，但抖动是由于架构组件而发生的不期望的效应[Leung和Merrill，1980]和[Pellizzoni和Lipari，2005]对含有补偿的系统进行了研究，[ Goossens和Devillers，1997 ]和[ Goossens，2003 ]对无补偿的系统进行了研究。在Audsley等人提出的调度分析中考虑了抖动。 [Audsley等人，1993年]。Marti等人 [Marti等人， 2001]已经确定了在分布式实时系统中可能发生的抖动类型，而Nilsson等人。 [Nilsson等人， 1998年，他将其用于随机分析。周期性实时系统- 由以周期性方式释放其实例（作业）的任务描述因此，任务τi的第j个作业将在时间Oi+jPi被释放。偶发的实时系统- 是不同的，从周期的事实，组成任务释放作业的时间间隔等于或大于周期Pi。任务τi的利用率由公式Ui=Ci/Pi描述，其中系统的利用率为U = n C i /P i。同时等待一个资源的作业的执行顺序由它们的优先级给出。优先级可以在任务级或作业级上给出，并且可以是固定的或动态的。如果一个具有较高优先级的任务能够中断一个较低优先级的任务的执行，我们称这个任务为抢占，实现它的算法是抢占式的。表示实时系统是否能满足其最后期限的属性称为可调度性。调度用于确定任务执行的顺序。在文献中，有多种调度算法能够调度由先前提到的概念的不同组合描述的模型的任务Liu和Leyland [Liuand Layland，1973]定义了速率单调算法，该算法为周期较小的任务提供更高的优先级Leung和Whitehead在[LeungandWhitehead，1982]中提出了一种只考虑截止期而不考虑周期的算法，称为截止期单调算法最早截止日期优先（EDF）算法[Liu和Layland，1973]是一种调度算法，其允许任何预1.1.一般性介绍7利用率小于或等于1的空任务集，通过给予具有最早截止期的作业最高优先级并允许其首先执行来调度。Audsley等人[Audsley等人， 1993年]和Bini和Buttazo在[Bini和Buttazo，2004年]。 作为非抢占式系统的抢占开销和低可扩展性之间的折衷，在像[Burns，1993]、[Baruah，2005]和[Yao等人， 2011年]。存在关于实时调度的更大和更详细的调查，从中我们提到[Audsley等人，1995]和[Sha等人，#20004;，结构完整、？随着应用复杂性的增加，实时系统面临着资源共享的问题。当两个或多个任务应该使用相同的资源时，就会出现这个问题，并且可能会通过优先级反转或死锁等现象导致任务响应时间大幅增加为了解决这些问题，Sha等人[Sha等人，1990]提出了优先级反转协议，Baker [Baker，1991]引入了堆栈资源策略。混合临界系统是实时领域的研究热点。它似乎是对应用程序复杂性不断增加的一种回答，这种复杂性导致低效的系统像对待高关键任务一样对待低关键任务。混合临界系统的第一个模型由Vestal在[Vestal，2007]中介绍，并在[Baruah等人， 2011]，[Baruah等人， 2012]和[Ekberg和Yi，2014]。时间分析是实时系统中的一个关键概念，它为任务或程序片段的WCET分配一个上界。该分配可以通过静态分析[Ferdinand等人，2001]或通过基于测量的分析[Bernat等人， 2002年]，[Wenzel，2006年]。 图1.3[Wilhelm等人，[2008]Wilhelm et al. 描述了实时属性，以便更好地理解时序分析。虽然在程序片段执行时间的组合中使用类似的方法，但这些估计的获得方式是根本不同的。静态分析使用目标硬件的抽象模型，并计算程序从所有可能的初始状态开始可以达到的所有可能执行状态的完整范围基于这些状态，8第1章 介绍图1.3：时序分析的基本概念 下面的曲线表示测量的执行的子集。它的最小值和最大值是最小观测执行时间和最大观测执行时间。较暗的曲线是前者的包络线，代表所有处决的时间它的最小值和最大值是最佳情况和最坏情况的执行时间，缩写为BCET和WCET。可以导出执行时间。基于测量的分析是非常直接的，包括用可能的初始状态和输入的子集执行每个程序片段通常选择被认为对系统压力最大的输入和状态，但测量的最大执行时间通常低估了WCET（见图1.3）。静态分析估计的正确性取决于抽象模型的正确性，并且这些模型的创建是容易出错且费力的过程，特别是在没有硬件的精确规格可用的情况下。这种情况经常发生在使用商用现货（COTS）硬件的今天，这可能会使静态分析成为一个昂贵的过程。这些情况可能会给静态分析带来优势，因为它们可能更适合于新的架构，因为它不依赖于架构的这种抽象模型。另一方面，基于测量的方法的可靠性难以保证。如果所有的初始状态和输入都被覆盖，那么测量将是微不足道的由于数量庞大，这通常是不可行的。相反，在测量中只能考虑初始状态和输入的子集1.1.一般性介绍9静态和基于测量的方法，在其确定性的方法，往往是非常悲观的。不幸的是，不是所有的实时系统都能承受这种悲观主义和随之而来的过度配置，对于这些情况，应该考虑其他方法一种这样的方法是在时间分析或描述分析模型中使用概率我们在本论文的以下部分详细介绍了这一主题的现有结果1.1.3航电产业在实时系统的所有分支中，关键实时嵌入式系统（CRTES）领域扮演着重要的角色CRTES广泛应用于汽车、航空电子、铁路、医疗保健等领域CRTES的性能分析不仅从他们的正确性的角度来看，而且从时间的角度来看。在航空电子工业中，这样的系统必须经历严格的分析过程，以满足认证机构（欧洲的欧洲航空安全局（EASA）或美国的联邦航空管理局（FAA））所要求的一系列认证标准。对于航空电子工业来说，这是由现有功能系统的任何改变都会带来的高成本所推动的。软件或硬件的任何更改都必须经过一个认证过程，这将花费制造商的金钱，时间和资源。尽管飞机制造商有保守的倾向，但他们不能对技术的不断变化无动于衷令人好奇的是，在世界上飞行的飞机上发现的大多数微处理器的计算能力都比现代家用PC小。他们的芯片组是专门为嵌入式应用设计的，其特点是低功耗，可预测性和许多I/O外设。到目前为止，大多数记录在案的飞机事故都是由于人为错误造成的，尽管如此，还是有一些事故是由一个或多个软件问题引起的[Wong等人， 2009年]。例如，法航447航班（2009年5月31日，一架空客A330-200）报告说，在飞机消失之前，系统发送了几条关于指示空速读数差异的信息10第1章 介绍尽管这起事故被归类为人为错误，但空中客车公司向所有空中客车机型的运营商发出了事故信息电传，提醒飞行员在空速指示不可靠的情况下应采取的建议的异常和紧急程序1994年12月 20日坠毁的原因被描述为飞行员的失误，但很大一部分责任在于软件系统的设计不当。简而言之，飞行员没有选择正确的无线电培根必要正确计算飞机的轨迹和错误迫使飞机做一个大半圆转向东。当发现错误时，飞机正朝着一座3000米的山峰笔直前进 关于这些错误和其他灾难性事故的更详细的报告，其中软件发挥了重要作用，可以在[Wong等人， 2009年]。最近，一架空客A400M在西班牙进行试飞时在起飞时坠毁，造成4人死亡。调查显示，在生产过程中，发动机控制软件的安装错误可能导致四分之三的发动机停止响应油门指令，从而导致事故[A400M，2015]。为了避免此类事故或大幅降低其出现的概率，所有安全关键系统都必须经过认证过程。这一过程由独立的机构执行，飞行认证的飞机软件认证所有民用飞机在投入使用前都要进行全面检查。该审查由独立的法律机构通过特定的行业标准进行为了允许搭载平民，飞机必须通过标准中提到的一系列目标获得认证根据系统的关键程度，每个组件可能需要通过不同数量的目标。关键性是系统组件所需的故障保证级别的指定换句话说，每个系统根据其故障可能产生的后果而获得不同级别的认证作为飞机开发参考的认证标准• ARP-4754 [SAE，2010]涉及系统开发1.1.一般性介绍11• DO-254 [RTCA，2015]是硬件开发生命周期的标准• DO-178 C [RTCA，2015]给出了软件开发生命周期的标准每个组件都有一套不同的要求，并置于其相应的安全完整性等级（SIL）或设计保证等级（DAL）。在航空电子工业中，有五个DAL，从A（最高临界度）到E（最低临界度）。每个DAL的描述见ARP-4761 [SAE，1996]，我们从中提取了表1.1。水平普罗巴严重程度失效条件效应DAL-A 10−9/h灾难性的所有故障条件，防止连续安全飞行和着陆DAL-B10−7/h危险安全裕度或功能能力大幅降低;工作量增加或身体不适，导致无法依靠机组人员准确执行任务，或完全;对居住者的不利影响DAL-C10−5/h主要安全裕度或功能能力显著降低;船员工作量显著增加或损害船员效率的条件;对操作人员的内裤DAL-D10−3/h轻微安全裕度略有降低;船员工作量略有增加;一些不便给住户。DAL-EN/A没有影响没有。表1.1：ARP-4761 [SAE，1996]中的设计保证水平描述。航空电子系统中的临界性概念不同于文献中混合临界性系统中的临界性理论概念虽然混合临界性被视为进一步详情12第1章 介绍关于这两种情况的差异，将在最新技术水平章节中介绍（见2.5.3）。软件开发是飞机开发的一个组成部分，它经历了一个持续的发展过程。对于空中客车机队，定期增加新技术，以提高安全性、燃油消耗、成本节约和可靠性。在过去的20年里，飞机驾驶舱发生了巨大的变化，许多驾驶设施也被引入。例如，在2011年至2016年期间，空中客车A330飞机引入了空中交通态势感知（ATSAW）、交通防撞系统解决方案咨询（TCAS RA）、自动驾驶仪/飞行指挥交通防撞系统（AP/FD TCAS）、机载机场导航系统（OANS）、GBAS着陆系统（GLS）、飞行管理着陆系统（FLS）、连续下降进场（CDA）和跑道超限保护系统（ROPS）等功能。所有这些功能增加了板计算机必须执行的指令总数与此同时，系统的计算需求增加，因此增加了机载计算机的数量以及飞机的重量为了避免上述问题，飞机制造商引入了集成模块化航空电子（IMA）的概念，其允许多个软件系统部件托管在同一执行目标上。这是对传统航空电子设备的一种回答，在传统航空电子设备中，对于给定的系统，每个负责开发一个或多个功能的供应商都提供一台计算机。IMA概念的精确描述可参见最新技术水平章节（见2.5.1）。WCET认证过程在同一硬件上集成多个系统意味着在认证过程中进行严格的验证和确认DO-178 C的一些限制不仅改变了开发过程，而且改变了整个系统的实际设计例如，DO-178C要求申请人计算软件程序的最坏情况执行时间在现代处理器上计算非对于定制处理器，这可以以较低的难度实现，但对于COTS硬件，生产商更关注性能和平均执行时间，而不是安全性和WCET，这项任务似乎很麻烦，如果不是不可能的话。新的计时1.1.一般性介绍13近年来，人们已经考虑了一些分析方法，其中概率分析方法将在本文中进一步介绍WCET相关的约束在DO-178 B/C标准的第6.3.4节中找到。软件要获得认证，其目标是“准确性和一致性”。在这个背景下，它被设想（在1992年的DO-178B），当大多数代码是用汇编程序编写的，这个目标是一个相关的。但是在我们这个时代，当软件开发在不同的提供商之间高度划分时，每个提供商都提出了自己的编写语言，技术和工具，准确性和一致性的验证可能不是那么明显。在同一节（6.3）的导言中，有一个短语表明，仅凭评论和分析不能完全处理某些主题（例如WCET和堆栈分析）。指出这一点的案文如下：“在有些情况下，本节所述的核查目标可能无法仅通过审查和分析完全实现。 在这种情况下，这些验证目标可以通过软件产品的附加测试来满足。例如，可以开发审查、分析和测试的组合，以确定最坏情况下的执行时间或堆栈使用的验证。随着技术的快速发展，航空电子行业正面临着跟上步伐的压力，软件或硬件的每一个变化都要经过新的认证过程该标准要求生产商评估WCET对编译器、链接器或硬件的任何修改的影响可以注意到，目标不是确定真实的WCET或精确的上限，而是简单地验证最大执行时间与分配的时间一致，并且验证开发过程识别的文档化时间约束（即需求）。通常，高级时序要求被表示为用于对外部事件作出反应的处理顺序性或端到端延迟在动态设计阶段，这些要求通常通过将系统功能分配给周期性任务来回答。最常见的情况是，特别是在控制-命令功能中，系统要求不能容忍定时超限.因此，软件任务被设计为在观察到最后期限错过时检测并应用一些制裁。一般来说，制裁是杀死（可能重新启动）失败-