论文部分内容阅读
摘 要：基于成分分析的层次化调度框架，其中使用到Uppaal，这是一种集成的工具环境，被用来对被转换时间自动机网络模型的实时系统进行建模、校验和验证。它是由瑞典Uppsala大学的信息技术学院和丹麦Aalborg大学的计算科学学院联合开发的。主要讨论了一种可重构的调度框架，表示层次化结构，调度策略，具体任务行为和可共享资源均可重构。
关键词：层次化结构；可重构；调度策略
中图分类号：TP391.41
基于成分分析的层次化调度框架，其中使用到Uppaal，表示层次化结构，调度策略，具体任务行为和可共享资源均可重构。每一阶段的抢占任务的行为被指定为定时动作列表，作为组成该框架的可参数化的自动定时装置的某个输入。构件可能有不同的调度策略，每一个构件使用UPPAAL独立分析。该框架已被应用于某个航空设置系统的调度分析。
该论文的主要贡献为：
—一种组合分析方法，适用于可调度性依赖于它的子系统的递归调度能力的系统。
—一种重构调度框架，适用于可以实例化为不同的配置来满足不同的应用的系统结构。
——具体任务行为模型，适用于需要CPU和资源的定时动作序列
与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全性[1]。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任务调度理论、实时操作系统、实时通信等方面取得了大量成果。
实时任务调度理论是实时处理技术的核心和关键。这是因为，实时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任务的执行都能在其截止期限内完成。如果每个任务的执行都能在其截止期限内完成，则称该调度是可行。可调度性判定就是判定给定的n个实时任务在应用某种调度算法的前提下能否产生一个可行的调度。调度算法的设计要尽可能满足任务可调度性的要求。
事实上，该框架是通过使用可参数化的定时自动装置模型实现。
层次化的可调度系统包括了有限的部件集，一种调度策略和（全局）资源。相应的，每个构件使用有限实体集的并行结构来完成其分配的工作量，此处实体集是指任务集或者是使用同种调度策略的构件，可以看出我们并没有考虑到构件的本地资源。系统任务是带有不同输入参数的定时自动装置的实例，该任务模型的特别参数是定时动作的列表，它给出了给定任务的具体行为。这份列表包括了抽象计算步骤，锁定和解锁资源。正是由于可参数化，该框架可以很容易的使每个明确的层次化调度应用实例化。相似的，每个调度策略可以被分别模拟并使每个构件实例化。
一个层次化调度系统包括了大量的层次化结构的调度系统，可以展示为一个拥有节点的树，这个系统的每一个节点都拥有一个调度器来调度它的孩子构件。
该结构将系统模型作为一系列层次化的构件来架构。相应的，每个构件是实体集以及本地调度器和本地资源的并行结构。一个父亲构件将它每个孩子构件的实时接口作为给定实时接口的单个任务。该构件根据它的孩子的实时接口分配资源。也就是说，每个构件均可以通过时间、预算、调度策略来参数化，其中，预算指出了在父亲层计算机应该提供给该构件的执行时间，调度策略指出了该构件提供给孩子实体的资源分配。对该构件（调度单元）的分析包括根据构件调度策略检查孩子实体在预算内是否可以被调度。一个构件也可以通过作为服务构件本地资源的一系列典型资源参数化。以下为参数符号及概念：
Ti第i个实时任务；n任务集合中任务的数量；ei任务Ti的执行时间；Pi任务Ti的周期；t系统运行的时间，t≥0；ri任务Ti的释放时间；di任务Ti的相对时间限（相对于释放时间）；Di任务Ti的绝对时间限。任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务开始执行的时间。任务的绝对时间限是指任务必须完成的时间。任务的相对时间限是指绝对时间限减去释放时间。
不确定性模型的其实是一个数据源分配模型，它为系统提供执行需要的原始数据。这种基于结构的调度模型是为任务分配数据，因此在任务执行过程中，如何在正确的时间的读入数据，直接影响了程序的执行效率。如果数据的读入在程序的执行过程中总是出现数据漏读的情况，总是在等待数据读入，那么将会极大的降低程序的效率，程序的执行过程中将会有很多垃圾时间。而不确定供应商模型就给了这样一种合理的、动态的分配模型，使得程序在执行过程不会出现断层。
我们现在可以为这个分层实时系统的建模和可调度性分析定义一个组成框架。这个框架可以作为我们运用UPPAAL和UPPAAL SMC来分析时间自动装置的一个可重用的例子。当建立一个分层调度应用模型的时候，这个可重用的模型可以确保具体的工作行为和需要系统工程师来规范的分层结构。这个框架也使得在每个分层的层次中的调度变化及时操作。对比我们基本的建模方法去分析这个建模，我们的框架工作使得我们这个模型更加具有竞争性，也更加的实用。我们已经成功应用我们的组成框架来建立一个航空电子设备系统，而且分析了它的可调度性。在未来的工作中，我们喜剧学习怎么样以一个自动化的方式去判断最佳时间的资源要求。我们也计划考虑多核平台的能量效率问题。
参考文献：
[1]Boudjadar，A.Hierarchical Scheduling Framework Based on Compositional Analysis Using Uppaal，in Formal Aspects of Component Software，J.L.Fiadeiro，Z.Liu，and J.Xue，Editors.Springer International Publishing，2014.
[2]Mikucionis，M.Schedulability Analysis Using Uppaal：Herschel-Planck Case Study，in Leveraging Applications of Formal Methods，Verification，and Validation，Pt Ii，T.Margaria and B. Steffen，Editors，2010：175-190.
[3]Moonzoo Kim，Yunho Kim.Hotae Kim"A Comparative Study of Software Model Checkers as Unit Testing Tools：An Industrial Case Study"，Software Engineering，IEEE Transactions on，2011（02）：146-160.
作者简介：张梦琪，2011级软件工程学生，参加2014年网易“中国合伙人”软件开发大赛进入决赛，并与暑期参与新加坡国立大学计算机学院交流营活动。在校期间连续两年获得“优秀学生”称号，并荣获“优秀毕业生”称号。
作者单位：四川大学软件学院，成都 610000
关键词：层次化结构；可重构；调度策略
中图分类号：TP391.41
基于成分分析的层次化调度框架，其中使用到Uppaal，表示层次化结构，调度策略，具体任务行为和可共享资源均可重构。每一阶段的抢占任务的行为被指定为定时动作列表，作为组成该框架的可参数化的自动定时装置的某个输入。构件可能有不同的调度策略，每一个构件使用UPPAAL独立分析。该框架已被应用于某个航空设置系统的调度分析。
该论文的主要贡献为：
—一种组合分析方法，适用于可调度性依赖于它的子系统的递归调度能力的系统。
—一种重构调度框架，适用于可以实例化为不同的配置来满足不同的应用的系统结构。
——具体任务行为模型，适用于需要CPU和资源的定时动作序列
与非实时系统相比，嵌入式实时系统因其所控制物理过程的动态性，要求运行于其中的单个任务必须满足其时限要求，以确保整个系统的正确性和安全性[1]。在航空航天、电信、制造、国防等领域，对实时系统有着强烈的应用需求。实时处理和实时系统的研究和应用工作已经有了相当长的历史，在实时任务调度理论、实时操作系统、实时通信等方面取得了大量成果。
实时任务调度理论是实时处理技术的核心和关键。这是因为，实时任务具有时限要求，在一个或多个处理器之间调度实时任务，需要判断是否每个任务的执行都能在其截止期限内完成。如果每个任务的执行都能在其截止期限内完成，则称该调度是可行。可调度性判定就是判定给定的n个实时任务在应用某种调度算法的前提下能否产生一个可行的调度。调度算法的设计要尽可能满足任务可调度性的要求。
事实上，该框架是通过使用可参数化的定时自动装置模型实现。
层次化的可调度系统包括了有限的部件集，一种调度策略和（全局）资源。相应的，每个构件使用有限实体集的并行结构来完成其分配的工作量，此处实体集是指任务集或者是使用同种调度策略的构件，可以看出我们并没有考虑到构件的本地资源。系统任务是带有不同输入参数的定时自动装置的实例，该任务模型的特别参数是定时动作的列表，它给出了给定任务的具体行为。这份列表包括了抽象计算步骤，锁定和解锁资源。正是由于可参数化，该框架可以很容易的使每个明确的层次化调度应用实例化。相似的，每个调度策略可以被分别模拟并使每个构件实例化。
一个层次化调度系统包括了大量的层次化结构的调度系统，可以展示为一个拥有节点的树，这个系统的每一个节点都拥有一个调度器来调度它的孩子构件。
该结构将系统模型作为一系列层次化的构件来架构。相应的，每个构件是实体集以及本地调度器和本地资源的并行结构。一个父亲构件将它每个孩子构件的实时接口作为给定实时接口的单个任务。该构件根据它的孩子的实时接口分配资源。也就是说，每个构件均可以通过时间、预算、调度策略来参数化，其中，预算指出了在父亲层计算机应该提供给该构件的执行时间，调度策略指出了该构件提供给孩子实体的资源分配。对该构件（调度单元）的分析包括根据构件调度策略检查孩子实体在预算内是否可以被调度。一个构件也可以通过作为服务构件本地资源的一系列典型资源参数化。以下为参数符号及概念：
Ti第i个实时任务；n任务集合中任务的数量；ei任务Ti的执行时间；Pi任务Ti的周期；t系统运行的时间，t≥0；ri任务Ti的释放时间；di任务Ti的相对时间限（相对于释放时间）；Di任务Ti的绝对时间限。任务的释放时间是指所有用来开始执行任务的资源都可用的时间，即任务开始执行的时间。任务的绝对时间限是指任务必须完成的时间。任务的相对时间限是指绝对时间限减去释放时间。
不确定性模型的其实是一个数据源分配模型，它为系统提供执行需要的原始数据。这种基于结构的调度模型是为任务分配数据，因此在任务执行过程中，如何在正确的时间的读入数据，直接影响了程序的执行效率。如果数据的读入在程序的执行过程中总是出现数据漏读的情况，总是在等待数据读入，那么将会极大的降低程序的效率，程序的执行过程中将会有很多垃圾时间。而不确定供应商模型就给了这样一种合理的、动态的分配模型，使得程序在执行过程不会出现断层。
我们现在可以为这个分层实时系统的建模和可调度性分析定义一个组成框架。这个框架可以作为我们运用UPPAAL和UPPAAL SMC来分析时间自动装置的一个可重用的例子。当建立一个分层调度应用模型的时候，这个可重用的模型可以确保具体的工作行为和需要系统工程师来规范的分层结构。这个框架也使得在每个分层的层次中的调度变化及时操作。对比我们基本的建模方法去分析这个建模，我们的框架工作使得我们这个模型更加具有竞争性，也更加的实用。我们已经成功应用我们的组成框架来建立一个航空电子设备系统，而且分析了它的可调度性。在未来的工作中，我们喜剧学习怎么样以一个自动化的方式去判断最佳时间的资源要求。我们也计划考虑多核平台的能量效率问题。
参考文献：
[1]Boudjadar，A.Hierarchical Scheduling Framework Based on Compositional Analysis Using Uppaal，in Formal Aspects of Component Software，J.L.Fiadeiro，Z.Liu，and J.Xue，Editors.Springer International Publishing，2014.
[2]Mikucionis，M.Schedulability Analysis Using Uppaal：Herschel-Planck Case Study，in Leveraging Applications of Formal Methods，Verification，and Validation，Pt Ii，T.Margaria and B. Steffen，Editors，2010：175-190.
[3]Moonzoo Kim，Yunho Kim.Hotae Kim"A Comparative Study of Software Model Checkers as Unit Testing Tools：An Industrial Case Study"，Software Engineering，IEEE Transactions on，2011（02）：146-160.
作者简介：张梦琪，2011级软件工程学生，参加2014年网易“中国合伙人”软件开发大赛进入决赛，并与暑期参与新加坡国立大学计算机学院交流营活动。在校期间连续两年获得“优秀学生”称号，并荣获“优秀毕业生”称号。
作者单位：四川大学软件学院，成都 610000