可调度性分析

摘要： 针对多核系统中并行实时任务调度,提出并行实时任务调度(Parallel Real-Time Tasks,PRTT)策略.PRTT调度策略分为两级调度,第一级将任务池中就绪实时任务调度到处理器核,第二级调度在处理器核上调度.允许任务抢占优先级低任务运行的核,动态提高要访问内存的任务的优先级,高于不访问存储器的所有任务.当任务读取的数据在高速缓存中时,将该任务的优先级提升到最高优先级,抢占没有访问存储器任务的核.研究结果表明:PRTT调度策略在核利用率、 任务可调度率等方面都有较好的性能.

摘要： 操作系统调度算法是现代操作系统实现多任务功能的核心.本文针对嵌入式操作系统实时性的要求,研究了几种经典的实时调度算法,分析了各个算法的具体原理和优缺点.在嵌入式Linux系统原有调度算法基础上,采用移植LSF算法的方式来提高其系统的调度性能,并且给出了相关其他调度算法移植到嵌入式Linux系统的具体步骤,为算法的移植提供了模板.通过实验发现,移植后的系统可调度性得到了提高,系统的任务截止时间错失率降低了10％.

摘要： 针对时间约束下工作流可调度性验证和修正策略不完善的问题,提出一种基于时间约束着色Petri网的任务关键系统(MCS)可调度性分析方法.根据系统中任务的性质将其划分为关键任务和非关键任务.对工作流中的活动进行可调度性验证,结合任务类别和时间约束修正不可调度的活动.实例分析结果表明,该方法具有较好的修正性能和运行效果,对时间约束下MCS的描述和建模具有一定应用价值.

摘要： 偶发实时任务最早截止期优先(earliest deadline first,简称EDF)可调度分析是实时系统领域经典的NP困难问题.现有的伪多项式时间判定算法(pseudo-polynomail time decision algorithm,简称PTDA)均局限于利用率U严格小于1的同步任务系统.对于U≤1的同步系统或更加困难的异步系统,现有PTDA则不再适用.针对以上问题,为同步和异步两类实时系统建立了统一的整数规划模型,其规模并不依赖于利用率U的取值.基于多面体理论证明了模型维数和极大诱导不等式,进而提出了同屏步系统上EDF可调度性分析问题统一的多项式时间线性松弛求解方法.实验结果表明,该方法能够获得较紧的问题解下界,在异步和同步系统中,线性松弛解与最优解之间的平均百分界差gap分别为0.78％和1.27％.另外,随机生成了大量同步和异步系统的算例,用于该算法和传统算法进行性能比较.对于同步算例,实验结果表明,在U＞0.99时,该算法能够对70％的算例给出判定结果,算法性能与QPA算法相比有指数级提升.对于异步算例,实验结果表明,该算法能够对近96％的算例给出可调度性判定.与传统算法相比,该方法将不能判定可调度性的算例比例平均降低了29.27％.对于剩余的4％的算例,该算法将可调度上界的值平均降低了近104倍.

摘要： Network-on-Chip (NoC) based conventional wormhole cut-through switching (Con-WCTS)cannot employ the priority based arbitration logic directly,so it is not suitable for the multiprocessor system-on-chip with high real-time requirements.By utilizing the virtual channel technique,this paper constructs a shared priority wormhole cut-through switching (SP-WCTS) network and proposes a method to calculate the worst-case traversing time for the traffic-flow of the SP-WCTS NoC.Furthermore,some experiments are made for comparing the schedulability of Con-WCT,shared priority wormhole switching (SP-WS),SP-WCTS and round robin wormhole switching (RR-WS) NoCs and analyzing the effect of the number of VCs and the total network utilization on the schedulability of these different NoCs.It is shown that the SP-WCTS NoCs can achieves the best schedulability and the number of VCs has a greater effect on the schedulability of the SP-WS than SP-WCTS NoCs.%基于传统虫孔直通交换(Conventional Wormhole Cut-Through Switching,Con-WCTS)的片上网络系统(Network-on-Chip,NoC)无法直接实现基于优先级的仲裁逻辑,不适用于对信息传输实时性要求较高的多核片上系统.引入虚拟通道技术,提出了共享优先级虫孔直通交换(Shared Priority Wormhole Cut-Through Switching,SP-WCTS)的网络结构,并给出了该网络信息最坏传输时间的计算方法.通过实验对比了Con-WCT网络、共享优先级虫孔交换(Shared Priority Wormhole Switching,SP-WS)网络、SP-WCTS网络以及轮询虫孔交换(Round Robin Wormhole Switching,RR-WS)网络的可调度性,并探究了虚拟通道数量和总网络利用率对网络可调度性的影响.实验结果表明:SP-WCTS的可调度性要明显优于另外3种网络;虚拟通道数量和总网络利用率对SP-WS网络可调度性的影响大于共享优先级SP-WCTS网络.

摘要： 针对混合关键性系统的多重认证需求,研究多核处理器平台中全局调度算法fixed-priority and Earliest Deadline First by Virtual Deadline (fpEDF-VD)的可调度性分析问题.fpEDF-VD结合处理器利用率和虚拟截止期两个方面来计算任务优先级,系统可调度性取决于是否存在可行的虚拟截止期调整参数.考虑到现有可调度分析方法仅测试有限数量的调整参数候选值,不能有效地判定系统可调度性,故提出了一种改进的判定方法.该方法基于传统(非混合关键)任务调度算法fpEDF的可调度利用率约束条件,利用函数图像分析研究不同关键性级别的系统可调度性需求,并在此基础上给出有效虚拟截止期调整参数的确切范围.通过实例分析及与现有判定方法的比较,验证了该方法的正确性和高效性.与理论分析一致,基于随机生成任务集的仿真实验结果表明改进后的方法具有更优越的可调度性能,能显著地提高任务集的可调度接受率.

摘要： 针对航天嵌入式系统中存在多级中断情况下的时间分析问题,提出了中断与任务混合的响应时间计算模型.该模型中断与任务使用统一的优先级定义,将多级中断嵌套的响应时间分析与任务嵌套的响应时间分析相结合,推导出了混合模型下响应时间计算公式.并进一步比较了中断与任务的异同,阐述了公式中关键参数的含义与计算方法.最后利用开源的LEON3平台和Modelsim软件对所述方法进行了仿真验证,结果表明,任务最差响应时间过估小于5％,可以得到准确的分析结果,有较高的工程应用价值.

摘要： A schedulability analysis approach of timing constraint workflows is proposed. According to the deficiency of Timing Constraint Petri Nets(TCPN for short)which is ordinary Petri net that can’t be used to model multiple resources, extended Timing Constraint Petri Nets(w-TCPN for short) is defined. Then, based on the topological structure of w-TCPN, from the two levels of model and case, the verification method for the schedulability of w-TCPN is presented in the form of theorems. In the end, the adjustment strategy of timing constraint is proposed. The research of w-TCPN makes the modeling and schedulability analysis of timing constraint workflows more reasonable.%提出一种时间约束工作流的可调度性分析方法。针对时间约束Petri网（Timing Constraint Petri Nets， TCPN）为普通Petri网无法建模多参与资源的不足，给出了扩展的时间约束Petri网（w-TCPN）的定义；结合w-TCPN的拓扑结构，从模型和实例两个层次，给出了w-TCPN变迁可调度的判定定理；提出了时间约束的调整策略。w-TCPN的研究使得时间约束工作流的建模和可调度性分析更加合理。

摘要： 带时间约束的实时任务图(TCDRT)模型具有接近于时间自动机的丰富表达性,但是其关联的可调度性分析(SA)问题却是强NP困难的.目前的研究仅关注一类约束个数为常数K的易解模型:K-TCDRT,且局限于SA问题的图转换求解方法.这种间接求法使得问题的计算复杂度随约束宽度呈指数倍增长.该文研究TCDRT模型上可调度性分析问题的直接求解方法,为两个核心子问题给出新的理论结果:第一,针对需求上界函数(DBF)的计算问题,提出了考虑时间约束的路径需求结构,并据此设计了新的动态规划算法,其时间复杂度与约束宽度无关;第二,对于可调度分析上界T的限定问题,从理论上证明了该问题是伪多项式时间可解的,且计算复杂度不再与K指数相关,这使得文中算法性能较已有结果有指数级提升.更进一步地,该文方法还蕴含着一类新的TCDRT易解模型.该类模型突破了约束个数必须为常数的局限,其分析难度也较K-TCDRT有指数倍地下降.

摘要： 考虑有滞留时间约束的单臂集束型装备调度模型和可调度性问题,建立了包括单臂机械手和加工模块时序约束关系的混合整数规划模型,并从理论上证明了并行模块等价加工时间的合理性。在此模型基础上,分析了单臂机械手和加工模块的周期性加工和搬运晶圆过程,证明了集束型装备可调度性的条件。对模型和可调度性条件进行了仿真实验分析,结果表明模型有效且可行。

摘要： 在分析FlexRay协议结构和特点的基础上,对动态段进行基于最坏响应时间的可调度性分析。并采用动态规划的调度算法,通过多阶段决策,逐一决定每一个动态报文的取舍,从而得到最优的调度方案。该算法可以显鞒提高FlexRay动态段的带宽利用率,充分发挥FTDMA的优势。

摘要： 本发明公开一种基于多处理器的AADL模型的可调度性分析方法，包括以下步骤：提取AADL系统架构中各分区的相关信息以及各分区与处理器构件的绑定关系；分析各分区与处理器构件的绑定关系，将每个分区中的每个线程构件与唯一的处理器构件绑定；确定各分区中线程构件的执行时序，计算每个线程构件的响应时间；根据各线程构件的响应时间及截止时间，计算系统中相应各线程构件的可调度性；根据各线程构件的可调度性，得到系统可调度性。通过上述步骤对基于多处理器的AADL模型的可调度性分析计算，得到系统模型的可调度性分析结果，为多处理器的AADL模型的可调度性分析方法提供一种较为精确的可调度性评价方法。

摘要： 本发明公开了一种带抢占点实时任务的可调度性分析方法，包括：根据实时任务的相对截止期进行排序，得到实时任务表；遍历实时任务表，获取分析任务，得到实时任务的最大干扰非抢占域集合；根据实时任务的最大干扰非抢占域集合，得到实时任务集中每项实时任务的最坏情况响应时间；将每项实时任务的最坏情况响应时间和每项实时任务的相对截止期进行比较，如果存在最坏情况响应时间大于相对截止期的实时任务，判定实时任务集不可调度；否则，判定时任务集可调度。本发明利用率高、运行速度快、执行效率高。

摘要： 本发明公开了一种片上网络中实时通信的可调度性分析方法，包括：在未分析的流中取最高优先级的流为目标流；搜索直接干扰流，在目标流的路由路径上共享链路资源的高优先级流为直接干扰流；搜索间接干扰流和其中的下游间接干扰流，在目标流的直接干扰流路径上与直接干扰流共享链路资源，且不与目标流共享链路资源的高优先级流为间接干扰流，根据间接干扰流与直接干扰流共享链路资源的相对位置划分为上游和下游间接干扰流；计算最大间接干扰和下游间接干扰；计算目标流的最大延时。本发明在分析计算目标流最大延时时，区分上游和下游间接干扰流对目标流产生的不同作用，从而确保了片上网络中实时通信的可调度性分析的正确性。

摘要： 本发明属于实时系统的实时调度和模型检测领域，具体涉及一种基于需求上界函数的任务自动机可调度性分析方法。该方法为：建立任务自动机系统模型；对任务自动机系统的每个任务自动机生成其对应的状态迁移系统；通过建立线性规划模型I和线性规划模型II，求解动态规划迭代带次数的上界Tbound；将任务自动机的状态空间全部划分为等效空间RPzone；利用动态规划的算法结构实现求解需求上界函数DBF(t)，将任务自动机的可调度性分析问题转化为需求上界函数的问题；计算任务自动机系统的DBF(t)，进行可调度性分析。通过等效划分，避免穷尽搜索所有的状态空间，只遍历边界状态进行可调度性分析，降低可调度性分析的复杂度。

摘要： 本发明涉及一种多处理器系统的AADL模型可调度性分析与验证方法，属于嵌入式软件可信属性验证领域。该方法综合考虑了节点内线程的并发关系、节点间线程的同步关系以及通信时消息的响应时间对线程调度的影响，通过分析AADL模型线程构件与处理器的绑定关系以及绑定在不同处理器上线程构件的交互关系，得到各线程的节点内干扰集和节点间干扰集，通过计算各线程受到节点内线程干扰时的响应时间以及受节点间线程干扰时的干扰时间，进而计算出各线程的最坏响应时间，并将线程的最坏响应时间与其截止期间进行比较，最终根据可调度性判定规则来对多处理器系统AADL模型可调度性进行分析。

摘要： 本发明公开了一种基于缓存抢占延迟约束下AADL模型的可调度性分析方法，用于解决现有可调度性分析方法实时性差的技术问题。技术方案是根据可执行构件分配的存储资源大小初始化构件缓存利用率，并在特定调度算法下获取任务集在一次调度过程中的抢占序列，结合可执行构件的缓存利用率提出了基于抢占序列的CRPD计算方法。由于本发明方法是通过AADL线程构件存储资源预估值计算CRPD，因此在没有具体程序也可以对构件的缓存抢占延迟进行计算，故而可以普适地应用在AADL模型可调度性验证。特定调度策略下抢占序列刻画了调度过程中任务之间抢占行为，基于抢占序列的CRPD计算方法较UCB‑Union方法更为准确。

摘要： 本发明提供了一种基于最差响应时间的混合关键系统任务可调度性分析方法，本发明首先给出混合双安全关键(DM)任务模型，并对系统行为重新定义；结合系统安全关键级转换时任务周期、优先级的变化，给出混合关键任务最差响应时间推导过程及任务集可调度性定理。最后，实例对比分析表明本发明的有效性。安全关键级提升时，本发明提出的最差响应时间分析方法能够在保证HC任务可调度性的前提下，为LC任务提供更好的服务；本发明的分析过程更加简化，更短的任务平均响应时间、更高的CUP资源利用率，能够保持更高、更稳定的系统吞吐量。

摘要： 本发明公开了一种带抢占点实时任务的可调度性分析方法，包括：根据实时任务的相对截止期进行排序，得到实时任务表；遍历实时任务表，获取分析任务，得到实时任务的最大干扰非抢占域集合；根据实时任务的最大干扰非抢占域集合，得到实时任务集中每项实时任务的最坏情况响应时间；将每项实时任务的最坏情况响应时间和每项实时任务的相对截止期进行比较，如果存在最坏情况响应时间大于相对截止期的实时任务，判定实时任务集不可调度；否则，判定时任务集可调度。本发明利用率高、运行速度快、执行效率高。

摘要： 本发明公开一种基于多处理器的AADL模型的可调度性分析方法，包括以下步骤：提取AADL系统架构中各分区的相关信息以及各分区与处理器构件的绑定关系；分析各分区与处理器构件的绑定关系，将每个分区中的每个线程构件与唯一的处理器构件绑定；确定各分区中线程构件的执行时序，计算每个线程构件的响应时间；根据各线程构件的响应时间及截止时间，计算系统中相应各线程构件的可调度性；根据各线程构件的可调度性，得到系统可调度性。通过上述步骤对基于多处理器的AADL模型的可调度性分析计算，得到系统模型的可调度性分析结果，为多处理器的AADL模型的可调度性分析方法提供一种较为精确的可调度性评价方法。

摘要： 本发明公开了一种片上网络中实时通信的可调度性分析方法，包括：在未分析的流中取最高优先级的流为目标流；搜索直接干扰流，在目标流的路由路径上共享链路资源的高优先级流为直接干扰流；搜索间接干扰流和其中的下游间接干扰流，在目标流的直接干扰流路径上与直接干扰流共享链路资源，且不与目标流共享链路资源的高优先级流为间接干扰流，根据间接干扰流与直接干扰流共享链路资源的相对位置划分为上游和下游间接干扰流；计算最大间接干扰和下游间接干扰；计算目标流的最大延时。本发明在分析计算目标流最大延时时，区分上游和下游间接干扰流对目标流产生的不同作用，从而确保了片上网络中实时通信的可调度性分析的正确性。