基于着色时间Petri网的实时嵌入式软件形式化综合方法研究

140《理论计算机科学电子札记》65卷第6期（2002）网址：http://www.elsevier.nl/locate/entcs/volume65.html20页基于着色时间Petri网时间记忆调度的实时嵌入式软件形式化综合？。熊宝安1号及高泉厚国立中正大学计算机科学与信息工程系摘要随着大多数日常生活中的人类设施（如家用电器）的计算机化，实时嵌入式系统中的软件现在占系统设计的70%一方面，软件的增加使得嵌入式系统更易于访问和使用，而另一方面，它也需要进一步研究如何自动和正确地设计复杂的，实时的嵌入式软件。加强这项研究的最新进展，我们提出了一个时间记忆调度（TMS）的方法，正式合成和自动生成代码的实时嵌入式软件，使用着色时间Petri网模型。我们的方法在三个方面扩展了以前的工作：（1）通过允许在系统描述中指定时间约束来建模软件的实时行为，（2）通过允许在系统描述中指定彩色标记来建模不同数据类型的内存使用，以及（3）通过提出一个扩展算法来调度增强的系统模型并生成静态代码。一个实时嵌入式软件，这是指定的一组CTPN，调度使用TMS，使调度满足有限的嵌入式存储器的要求和所有的实时和任务优先级约束。最后，一个可移植的嵌入式软件程序生成的C编程语言使用有效的TMS的时间表。所提出的方法是在Java中实现的，以便它可以安装在设计原型的在线代码更改，以满足用户的动态需求通过ATM虚拟专用网服务器上的一个实例，说明了TMS方法用于嵌入式实时软件综合的可行性和优越性。关键词：实时嵌入式软件，着色时间Petri网，准静态调度，代码生成？ 本研究得到国家科学委员会NSC-90-2215-E-194-009研究计划的部分资助。1 电子邮件：hpa@computer.org和URL：http://www.cs.ccu.edu.tw/pahiung/c 2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。熊和高1411介绍随着电子技术的进步，现在可以将微处理器嵌入因此，人们在日常生活中遇到的嵌入式系统的数量从过去的几十个急剧增加到最近几年的数百个。此外，一旦嵌入式系统与人交互，就存在对其行为的时间期望，这可能是软约束（例如多媒体服务器）或硬约束（例如车辆中的制动系统）。现在，大多数嵌入式系统也是实时系统，因此它们的设计也必须满足所有的实时要求。基于这种动机，我们提出了一种时间-内存调度方法来形式化地综合和自动生成实时嵌入式系统的代码。实时嵌入式系统是一个计算单元，安装在一个称为环境的更大的系统中，这样它就可以帮助环境完成一些具有时间和空间约束的专用任务集。一般来说，嵌入式系统有硬件和软件两部分。硬件被制造为一个或多个ASIC、ASIP或PLD。软件在一个或多个微处理器上执行，有或没有操作系统。实时嵌入式软件（RTES）是一段程序代码，必须：（1）满足实时约束，如响应时间，截止日期和周期，（2）在指定大小的内存空间内执行。RTES通过接口或直接连接与嵌入式硬件进行通信.根据上述定义，在设计RTES时有两个主要问题有限内存执行：处理器不能有无限数量的存储空间用于执行任何软件进程。这一事实在嵌入式系统中更加突出，嵌入式系统通常只安装了几百个字节的内存实时约束：一个处理器可能必须执行多个并发具有优先级和时间约束的任务。因此，一个RTES通常是由几个并发的，实时的，计算任务。为了解决上述两个问题，RTES的综合方法必须生成可以在有限的存储器中执行的程序代码，同时满足所有给定的实时约束。建议的解决方案包括以下两个步骤：时间-内存调度：计算部分可达性树，以便从树中修剪所有违反时间或空间约束的计算。所得到的树保证，对于非确定性数据相关执行选择中的所有可能结果，用于计算的存储器总是在限制内，并且软件的执行是周期性的，也就是说，它总是在其最后期限约束内返回到其初始状态。熊和高142代码生成：TMS之后获得的树表示系统的可行计算，并且可以通过直接映射转换为调度生成代码本文提出了一种基于有色时间Petri网（CTPN）的形式化综合方法，该方法采用时间-内存调度（TMS）来满足有限的嵌入式内存限制和硬实时约束。然后根据TMS计划生成软件代码。软件代码中的任务数量被最小化以提高效率和代码大小。最后通过一个应用实例说明了该方法的可行性和优越性.本文的结构如下。第2节给出了一些以前的工作相关的RTES综合。第3节制定，建模，并解决了RTES综合问题。第4节通过一个应用实例说明了所提出的问题解决方案第五部分总结了本文的工作，并提出了今后的工作方向。2以前的工作目前，软件综合是嵌入式系统软硬件协同设计领域的研究热点[10]。以前，大量的工作是针对硬件综合和相对较少的注意力支付给软件综合。部分软件综合主要针对通信协议[18]、工厂控制器[17]和实时调度器[1]进行，因为它们通常表现出规则的行为。直到最近才有一些关于自动生成嵌入式系统软件代码的工作[2，16，20，22]。除了Honeywell的MetaH之外，没有其他自动软件合成方法可用于并发嵌入式实时软件。在下文中，我们将简要地调查现有的非实时软件的综合工作，我们的工作是基于。Lin [16]提出了一种通过中间Petri网表示从并发过程规范生成软件程序的算法。这种方法基于Petri网是安全的假设，即缓冲器最多可以存储一个数据单元，这意味着它总是可扩展的。所提出的方法将准静态调度应用于一组安全Petri网以产生一组对应的状态机，然后将其按语法映射到最终的软件代码。后来，Zhu和Lin [22]提出了一种合成方法的组合版本，该方法减少了生成的代码大小，因此更有效。Sgroi等人提出了一种准静态调度算法，用于一类称为自由选择Petri网（FCPN）的Petri网[20]。给出了FCPN可解的一个充要条件。首先检查FCPN的可扩展性，然后通过将FCPN分解为一组无故障（CF）组件生成有效的调度，然后单独静态调度这些组件。代码最终从有效的计划生成。基于FCPN，Hsiung提出了一种扩展的调度方法，熊和高143时间限制到合成过程中，这样就可以为硬实时嵌入式系统生成代码[14]。它后来被修改为软实时嵌入式系统的合成代码这两种方法仍然受到系统描述模型上的自由选择约束的限制。Cortadella等人[7]提出了一类更一般的Petri网的可达图算法输入由FlowC源组成，输出是预定的嵌入式软件代码。在所提出的算法中没有考虑时间约束。Balarin等人[2]提出了一个反应式嵌入式系统的软件综合过程中的协同设计有限状态机（CFSM）[3]框架与POLIS软硬件协同设计工具[3]。这项工作不容易扩展到其他更一般的框架。除了软件综合之外，最近还有一些关于嵌入式系统中软件验证的工作，例如调度-验证-映射方法[11]，线性混合自动机技术[9，12]和映射策略[8]。最近，软件合成也考虑了系统参数[13]。在上述相关的软件综合工作中，要么他们在嵌入式软件综合的系统模型中没有考虑实时相比之下，我们的工作重点是如何预定的程序代码可以生成实时嵌入式软件没有任何模型的限制。3实时嵌入式软件综合本文提出了一种实时嵌入式软件的形式化综合方法。它的基本特点是，所提出的综合方法产生的软件代码执行在有限的内存中，并满足所有用户给定的实时约束。在详细介绍这种方法之前，首先介绍了系统模型和相关术语。实时嵌入式软件被指定为一组着色时间Petri网（CTPN），它是着色Petri网（CPN）[19]和时间Petri网（TPN）[4，5]的组合如第2节所述，Petri网（PN）的几种变体被用于嵌入式软件的综合[7，16，20]，但不知何故，这些模型既不允许内存使用的建模，也不允许时序约束的建模因此，我们建议使用CTPN，它允许内存使用和时序约束的显式建模。在本节的其余部分中，我们首先定义了CTPN，给出了系统模型，它的语义和它的调度。然后，我们制定我们的目标问题。最后，我们描述了我们提出的合成算法，以及代码生成。熊和高144的t0[3、6]p0t2第1页[7，7]t3p3t5p4[1，]t1{(3，grey）}[1、5]第2 页[1，2]t4[2、5]{（2，black），（1，grey）}Fig. 1. 着色时间Petri网3.1系统模型实时嵌入式系统被建模为一组着色时间Petri网（CTPN），其定义如下。3.1有色时间Petri网（CTPN）着色时间Petri网是一个6元组（P; T; C;;M0;），其中：P是一个有限的位置集合，T是一个有限的转移集 P[ T6=;，且 P\ T=;，C是一组颜色，这是与每个标记相关联的属性，：（PT）[（TP）！ 是由弧表示的地点和过渡之间的加权流动关系，使得每个弧与整数颜色对f（k; c）j k 2N;c 2 C g的集合相关联，其中N是非负整数的集合，M 0：P！ 2是初始标记（将彩色标记分配给位置），NC和T！ N（N[1]），即， （t）=（t），其中t2T是最早点火时间（EFT），并且是最晚点火时间（LFT）。 我们将使用缩写（t）和（t）分别表示EFT和LFT。K从图形上看，CTPN可以如图所示进行描绘1，其中圆圈表示地点，垂直条表示过渡，箭头表示弧，点表示图，点的不同阴影表示不同的颜色，并且标记在弧上的整数颜色对的集合表示由定义的权重。这里，（x; y）6=;意味着有一个从x到y的弧，其权重为（x; y），其中x和y可以是一个位置或一个过渡。CTPN中允许冲突和混淆 当在具有多于一个传出弧的位置中存在令牌时，发生冲突，使得只有一个启用的转换可以激发，从而消耗令牌并禁用所有其他转换。 例如，ft2;t3g和ft3;t4g是图1中的一对冲突跃迁. 1.一、混淆是并发和熊和高145K在同一个过渡期发生冲突例如，在图2中的转变t2和t3处存在混淆1.一、从语义上讲，CTPN的行为由一系列标记给出，其中标记是将彩色标记分配给位置。从初始标记M0开始，CTPN可以通过触发启用的转换和令牌的重新分配来转换到另一个标记当转换的所有输入位置在所需的时间量内具有所需数量的彩色标记时，转换被称为被启用，其中所需数量的彩色标记是由流关系定义的权重，并且所需的时间量是由定义的最早激发时间。启用的转换不一定需要触发。但是在触发时，所需数量的标记从所有输入位置中移除，并且指定数量的标记被放置在输出位置中，其中指定数量的彩色标记是由来自转换的输出弧上的流关系指定的。启用的转换不能在其最后触发时间之后触发。为了用符号形式化上述语义描述，我们给出以下基本定义。整数颜色对的集合被定义为f（n; c）jn2N;c2C g，其中N是非负整数的集合，C是颜色的集合。如果NC和NC是两组整数颜色对，NCiff k0 k对于所有的（k 0; c）2NC 0，（k; c）2NC，且k 0>0.直观地说，这意味着对于每种颜色，NC 0中该颜色的标记数不大于NC中的标记数。此外，对于NC 0 NC，我们还可以将它们的差NCNC 0定义为整数颜色对f（k0 0;c）j k00=kk0;8（k;c）2NC;（k0;c）2NC 0，且k 0 k g的集合NC 0 0. 类似地，也可以为两组整数颜色对定义sum形式上，标记是向量M= hNC 1;N C 2;：;NCjPji，其中N C iNC是整数颜色对的集合，表示颜色的非负数。在位置pi2P中的或令牌。与每个标记M相关联，存在两个属性：（1）时间戳（M），以及（2）存储器使用（M）。时间戳（M）定义为CTPN从初始标记M0变为标记M所经过的时间。这里，（M0）= 0。内存使用量（M）定义为CTPN在标记M中时使用的内存量。转换t被称为在具有时间戳的标记M（M）如果下列条件成立：（1）（p k; t）N C K，对于所有 （p k;t）6=;和k2f1，jPjg，和（2）（M）（t）。当在某个标记M中触发转换t时，CTPN的状态改变为新的标记M0= hNC0;N C0;：：：;1 20jPj i，其中NC0=NCk（pk;t）+（t;pk）对于所有k2f1; ：;jPjg. 的在具有时间戳（M）的标记M中，在时间t处触发转换t被称为如果满足以下两个属性，则为有效触发过渡期限：（t）（男）（t），以及内存约束：（M0）max，其中M0是通过在M中触发t获得的标记，max是用户指定的实时嵌入式系统中可用的最大内存量Petri网（PN）的一些性质可以定义如下。可达性：NC熊和高146如果存在点火序列，则标记M0可从标记M从标记M开始并在M0结束。有界性：一个PN被称为k-有界的，如果在可达标记的每一个地方的标记的数量不超过一个有限数k。安全PN是1-有界的。无死锁：如果每个可达标记中至少有一个启用的转换，则PN是无死锁的活性：PN是活的，如果对于每个可达标记和每个转换t，有可能到达使能t的标记。3.2问题公式化用户通过一组CTPN和内存使用的上限来指定实时嵌入式软件的设计要求，其可以正式定义如下。定义3.2实时嵌入式软件（RTES）实时嵌入式软无线系统S被定义为一组CTPN，其中A i=（Pi;Ti; C; i; M 0 i;i），以及表示系统中可用存储器的最大量的整数max。我们在这里试图解决的问题是找到一种构造方法，通过该方法，一组CTPN可以作为软件代码执行，在给定的有限内存空间下运行，并满足所有给定的实时约束，例如每次转换的最早和最晚触发时间，系统周期和系统截止日期。以下是RTES合成问题的正式定义。定义3.3 RTES合成给定由一组CTPNfA1;A2; ：;Ang建模的实时嵌入式软件系统S的规范，其中Ai=（Pi;Ti;C;i;M0i;i），以及存储器使用的上限最大值，并且给定一组实时约束，(1)它可以在单个处理器上执行，（2）它使用小于或等于上限max的存储器，以及（3）它满足所有转换EFT和LFT以及实时约束集。3.3合成算法在进入合成算法的细节之前，需要一些基本概念和定义，并描述如下。给定一个CTPN，我们定义选择集和排除集，以确保在一个最终的可行的时间表的完整的CTPN的所有过渡的完全覆盖。定义3.4选择集Giv enaCTPNAi=（Pi;Ti;C;i;M0i;i），一组转换H=ft0;t1; ：;tmg称Ti为选择集，如果存在一个位置 p2 Pi，使得有弧连通熊和高147将p与H中的每一个跃迁连接，而与T中的任何一个都不连接。名义上，9p2Pi，（p;tk）6=;对所有k2f0;1; ： ：;mg和（p;t0）=;对所有t02TinH.3.1节中提到的冲突变迁是选择集的一个特例，因为冲突变迁的集合是不相交的。然而，选择集不一定是例如，两个位置之间的同步转换，每个位置都有一组多个传出转换，属于两个选择集。当我们将所有不相交的选择集合并为一个转换集时，它被称为排除集，其正式定义如下。定义3.5排除集Giv enaCTPNAi=（Pi;Ti;C;i;M0i;i），一组转换H=ft0;t1; ：;tmg如果存在一个转移序列，使得每个相邻的转移对都有一个公共的输入位置，则Ti被称为排除集从上面的定义中，我们可以观察到选择集是排除集的一个特例，排除集总是连通的，两个或多个排除集是不相交的。直观地说，排除集表示在特定系统状态（CTPN标记）下依赖计算（行为）的所有可能选择。因此，在本节稍后介绍的调度算法中，我们强制执行这样一个事实，即在我们接受标记作为系统调度的可行状态之前，排除集应该在标记处排除集的部分启用最终将导致部分系统计划。现在，我们介绍源转换和独立任务的概念。一个变迁t称为源变迁，如果（p;t）=;对于所有的位置p2P，也就是说，它没有输入位置。从物理上讲，源转换代表来自环境的不可控输入事件。如果两个源转换在某个共同的可达转换处同步，则称它们是依赖的，其中如果从t的触发到t 0的启用存在一系列有效转换触发，则称转换t是从另一转换t0可 达 的。如果一组源跃迁由相互依赖的所有源跃迁组成，并且CTPN中没有其他源跃迁依赖于该组中的任何跃迁，则该组源跃迁被定义为最大例如，在图1中，源转换t0和t1是相关的，因为它们对应的计算运行最终在t3同步。此外，一组转换构成一个独立的任务，如果他们都是从一些最大的依赖源转换集可达。在图1中，整个CTPN构成一个独立的任务。给出CTPN模型的上述基本定义和概念，我们现在将正式介绍我们的合成算法。如第1节所介绍的和定义3.3中的公式，RTES综合算法有两个目标本文提出的算法以时间-记忆调度策略的形式熊和高148给定一组CTPN S = fA ij A i=（P i; T i; C; i; M 0 i; i）;i = 1; 2;：; ng，存储器max的最大界限，一组周期E =fiji2N;i = 1; 2;：; n g，其中i是Ai的周期，一组期限D = fd ij d i2 N;i = 1; 2;：; n g，其中di是Ai的期限，在以下两个阶段之后生成软件代码：时间存储器调度（TMS）和代码生成。3.3.1时间记忆调度在时间记忆调度（TMS）中，通过为每个独立的任务创建一个进程来为实时嵌入式系统生成有效的软件调度，该任务由一个或多个相关的源转换组成。每个过程都是通过创建可达性树生成的顺序调度，可达性树以标记为节点，以有效的转换触发为边。在创建可达性树时考虑了几个因素，例如最大可用内存的界限，独立任务所属的CTPN的周期以及相应的截止日期。每个任务都可以分配一个优先级，例如执行频率，因此我们不允许在执行任务时抢占任务。这确保了根据过程的顺序时间表遵守过渡点火间隔。我们提出的TMS算法的细节在表1中给出。首先将给定的CTPN集划分为独立的任务，如前所述（步骤1）。每个独立的任务都包含在一个CTPN中，而一个CTPN可以由多个独立的任务组成。然后，通过以初始标记为根节点开始，为每个独立任务生成可达性树。这里，根节点实际上是CTPN初始标记在独立任务上的投影（步骤2、3、4）。可达性树的每个节点表示独立任务的标记，并且每个树边缘表示启用的转换的有效激发。首先，为根节点（步骤6中的Spawn Child其次，选择根节点的一个子节点进行遍历，其中选择基于对内存和时间使用的评估（步骤7中的Select Child（）），如稍后所述。最后，迭代地生成可达性树（步骤8在可达性树的生成中，标记的节点指示从由该节点表示的标记开始，存在有效的调度。对于所考虑的每个当前节点（CNode），它或者是完整的调度或者不是（步骤24）。 如果是，则简单地标记它（步骤25），并考虑其父节点 作为当前节点（步骤26）。如果它不是一个完整的计划，则为它的每个1步后继标记创建一个子节点（步骤27中的Spawn Child（）），它满足所有约束，包括：转换截止日期：（M 0）（M）+（t）（t），其中假定t是在时间戳（M）处从由CNode表示的标记M开始启用的转变，并且t被连续启用直到到达具有时间戳（M0）的另一标记M0熊和高149表1时间记忆调度算法TM计划（S;max; E; D）S =f A ij A i=（Pi; Ti; C;i; M0 i;i）;i = 1;2;：; n g;integermax;//最大内存E =fiji2N;i= 1;2;：; ng;//周期D=fdijdi2N;i= 1;2;：; ng;//期限fT=独立任务（S）;（1）对于每个任务2Tf//假设任务2Ai，对于某些i2f1; ：;ng（2）RTree =创建新到达树（t）;（3）RTree.root =项目标记（M0 i; t）;（4）CNode = RTree.root;// CNode：当前节点（5）Spawn Child（CNode，max，i，di）;（6）CNode =Select Child（CNode）;（7）while（RTree.size！=0）f（8）如果（CNode==RTree.root CNode.HasChild&&CNode.AllChildMarked）生成TMS代码（RTree）;（9）如果（CNode.Spawned）f（10）if（CNode.HasChild）f（11）删除不完整的ExSet（CNode）;（12）if（Marked（CNode.HasCompleteExSet））f（13）删除其他子节点（CNode）;（14）（15）Strings;CNode = CNode.Parent;g（16）else if（Marked（CNode.HasNonExSet））f（17）删除其他子节点（CNode）;（18）int n（int n）;（19）CNode = CNode.Parent;g（20）else CNode =Select Child（CNode）;g（21） elsefDelete（CNode）;（22）CNode = CNode.Parent;gg（23）elsef if（CNode.Is Complete Schedule）f（24）（25）Strings;CNode = CNode.Parent;g（26）else生成子节点（CNode，max，i，di）;（27）ggggCTPN Deadline：（M0）+（ t）di，其中di是当前任务所属的CTPN的截熊和高150止日期。内存使用：（M 00）max，其中M 00是击发后达到的新标记从M 0开始。如果CNode有一些子节点（步骤11），则表示标记的所有子节点熊和高151删除不完整的排除集（步骤12）。这里的直觉是，排除集的部分启用最终将导致部分调度，这是不可接受的。如果存在具有完整排除集的某个子节点并且也被标记（步骤13），则删除所有其他子节点（步骤14），标记CNode（步骤 15）并且将其父节点视为当前节点（步骤16）。对于不属于任何排除集的单个标记的子节点也执行相同的操作（步骤17如果没有标记的子节点，则选择其中一个子节点作为当前节点（步骤21中的Select Child（））。如果不能为CNode生成子节点，则将其删除（步骤22），并将其父节点视为当前节点（步骤23）。TMS算法在可达树调度中选择子节点（Select Child（））作为可行的下一个标记，采用最早截止日期优先（EDF）方法，即在所有可能的标记中，选择截止日期最早的标记作为生成调度中的下一个标记。如果两个或多个标记具有相等的最早期限，则选择具有最大执行时间的标记。如果两个或多个标记具有相等的最早截止时间以及相等的执行时间，则选择具有最少内存使用的标记这里，时序约束的满足被给予优先于存储器约束的满足，因为时间在计算运行上累积，而存储器使用是计算运行中所有标记的存储器使用的最大值应用上述方法后，将为每个独立任务创建可达性树。然后，这些任务可以根据它们的优先级以非抢占式的方式进行调度。在调度期间，对每个新标记进行内存使用的估计，并且通过观察估计的内存空间是否不超过界限来检查内存界限的满足。程序使用的内存空间在功能上可以分为以下几类：全局内存：全局变量和数据驻留在全局内存中，它们的生命周期是程序执行的整个持续时间。这个空间被假设在程序执行的最开始就被分配，因此它是恒定的大小，并且可以静态地确定。这个恒定的空间大小必须被添加到每个内存空间的估计中。本地内存：用户指定的代码用于转换的本地变量驻留在本地内存中。该空间大小对于每个转换都不同，并且必须通过代码分析来先验地所有转换使用的本地内存空间的最大大小，其触发导致标记，必须添加到内存大小估计。缓冲存储器：从一个转换的代码传递到另一个转换的代码的中间变量或数据驻留在缓冲存储器中。由于CTPN具有带有来自集合C的颜色的着色令牌，如果由C中的某个颜色c占用的存储器的量被表示为C（c），则我们可以估计缓冲器熊和高152表2码生成算法Gen TMS代码（RT ree套件）RT ree Set：可达树的集合F对于RT ree中的每个RT ree，SetfProcessCode =Extract（RTree.root）;Output（ProcessCode）;Greturn（）;（一）（标记使用的存储器M= h NC1;：;N CjPji如下：（一）B（M）=X0X（nC（c））11ijPj@（n;c）2NCiA这里假设释放的内存空间的垃圾收集是由每个转换执行（在消耗输入彩色令牌时），或者由诸如Java虚拟机之类的系统执行。程序代码使用的最大内存空间量可以估计如下：（2）（S）=maxG（R）+maxhmax（L（t））+B（M）i其中G（R）是使用可达性树R调度的独立任务的全局存储器大小，maxxt！M（L（t））是其触发导致标记M的转换t所使用的本地存储器空间L（t）的最大量，并且B（M）如等式（1）中所定义。3.3.2代码生成在时间存储器调度之后，通过如表2所示的代码生成过程Gen TMS Code（）将从CTPN集合获得的调度集合（可达性树）映射到软件程序中。为系统中的每个独立任务（可达性树）创建实时进程（步骤1这种代码生成方法最大限度地减少了系统中的任务数量，因为系统中的并发程度等于独立触发转换的数量[20]，这与独立任务的数量相同。在代码生成算法（表2）中，Extract（）过程用于从根节点开始递归地提取可达性树的代码。程序详情见表3。如果当前节点CNode是叶节点（步骤1），则提取该节点的相应用户给定代码并将其连接到Code变量，表示该过程的最终代码（步骤2）。因为叶节点表示调度的结束，所以追加了一个return;语句（步骤3）。对于单个子节点（步骤4），对应的用户-R2SM2Rt！M熊和高153表3提取代码程序提取该节点的给定代码（步骤5），并递归地调用Extract（）与CNode的唯一子节点（步骤6）。对于具有多个子节点的节点，将创建一个分支结构，并递归地为每个子节点提取代码（步骤73.3.3执行提出的TMS算法和代码生成程序在Java编程语言中实现，生成C代码。由于Java的可移植性，我们的小合成程序可以安装在不同类型的嵌入式系统和原型，使用户可以根据自己的需要动态改变嵌入式应用软件的功能生成C代码的理由下一节将给出一个ATM服务器上的例子，它的代码是通过执行我们的合成程序来合成和生成的。4ATM虚拟专用网服务器示例为了说明我们的实时嵌入式软件综合方法的可行性和优点，我们已经将其应用到一个真实的系统：一个ATM服务器的虚拟专用网（VPN）[6]。ATM服务器驻留在通过ATM骨干网互连局域网的ATM交换节点ATM服务器临时存储来自虚拟信道连接（VCC）的输入信元，并根据信元报头信息和VCC的内部状态表将它们转发到虚拟路径连接VPC是一组统计复用的VCC，它们共享固定的提取（CNode）CNode：可达性树Fif（CNode is leaf）fCode += getCode（CNode）; Code +=Gelse if（Nchild（CNode）== 1）fCode += getCode（CNode）;Extract（CNode.child）;G否则fCode += getBranchCode（CNode）;对于每个子节点CNode。Ci提取（CNode. ci）;（一）（四）（五）（六）熊和高154细胞提取物加权公平调度消息选择丢弃VCC单元CID/PTI推插入蜱流行图二、ATM虚拟专用网服务器带宽量ATM服务器的功能如图2所示，其中CID和PTI是携带报头信息的中断，并且在非空信元进入服务器时不规则地发生，TICK是周期性事件，在N次发生之后，它使能选择下一个要发送的信元的算法（信元提取）[21]。根据规范，CID/PTI和TICK没有固定的采样率比，因此可以独立点火。因此，我们有两个独立的任务调度（可达树建设）和代码生成。此外，在ATM服务器中存在如下两种算法一种消息选择性丢弃（MSD）算法，通过丢弃选定的传入信元来避免缓冲区溢出。通过使用阈值机制来保持消息（单元组）的完整性一种加权公平队列（WFQ）调度算法，为每个队列分配输出链路带宽的固定部分。每个传入的信元都被分配了一个时间戳，在这个时间戳上它必须被发出，这样每个连接就可以保证不超过它的带宽。图3中给出了一个着色时间Petri网模型，它对MSD算法进行了建模。该模型共有24个位置和27个过渡。它是在[21]中找到的修改版本。我们的模型是一个更紧凑的模型。如图3所示，每当接收到CID和PTI中断（在t1同步）时，MSD算法就开始执行它首先从内部表（READ STATE VCC和READ OUT QUID）检查输入信元的VCC状态和信元要转发的逻辑队列然后，根据VCC状态处理输入信元在位置p9处，变量st的值指示VCC的状态，其可以是以下中的任一个IDLE（st= 0）：这里，队列长度与缓冲器阈值进行比较（在状态p20中）。如果队列长度小于阈值（t11），则信元被推入队列（PUSH），如果队列为空则调用WFQ调度（SCHEDUPLWFQ），并且VCC状态被更新为ACCEPT（UPDATE STATE ACC）。如果队列长度大于阈值，则丢弃它（UP-1）。计数器熊和高155CID READ_STATE_VCC UPDATE_STATE_INITMSD p1p3 t1 p5p7 t2Yp10Np2 p4 p6 p8PTI = 1/3？PTIREAD_OUT_QUIDt6Q长度= 0？NT12[1、16]READ_MAX_QLENGTHt9p21t3p11P15t7Qlength

下载后可阅读完整内容，剩余1页未读，立即下载