（计算机应用技术专业论文）基于ootcpn模型的嵌入式系统设计方法研究.pdf

西华大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任 学位论文作者签名：乃锄 日期： ) 。ij 毋7 指导教师签名蕊 嗍加卜6 夕 西华大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，在校 ，攻读学位期间论文工作的知识产权属于西华大学，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，西 华大学可以将本论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复印手段保存和汇编本学位论文。( 保密的论文在解 密后遵守此规定) 学位论文作者签名：马翻 日期： 多口i i 7 指导教师签名：触 日期翩f f 7 西华大学硕士学位论文 摘要 嵌入式系统，作为计算机技术中的一项重要研究方向，已经被广泛地应用到各个领 域。随着嵌入式产品在不同领域的应用，用户需求的不断增加，嵌入式系统功能越来越 强大，设计难度也越来越大，导致传统的设计方法难以满足复杂嵌入式系统的设计需求， 因此研究系统级的设计方法己成为嵌入式系统设计的主要研究方向。 本文通过对现有嵌入式系统建模方法研究的基础上，引出形式化建模是嵌入式 系统建模研究的主要方向。针对基本p e t r i 网在嵌入式系统建模中处理数据能力弱、 没有考虑时间因素和没有层次结构的问题：通过引入面向对象技术、时延网和有 色网，扩展了基本p e t r i 网，给出了面向对象的时延有色p e t r i 网( o o t c p n ) 模型的 形式化定义。与其他模型相比，本文模型在数据描述能力、实时性、层次性等方 面有了较大的提高，适合复杂的嵌入式系统建模。 在模型验证方面，通过对基本p e t r i 网模型的验证技术研究，分别阐述了仿真 分析和模型检验方法的原理和特点，探讨了p e t r i 网模型的电路仿真分析方法，给 出了利用硬件描述语言描述o o t c p n 模型的方法，并通过实例说明。与传统的p e t r i 网仿真分析软件相比，此方法适用范围更广，可移植性强，使用灵活，便于向底 层设计转换。 最后通过对电梯系统建立系统模型，并对模型进行仿真分析，仿真结果表明了 基于o o t c p n 模型的嵌入式系统建模方法的可行性和正确性。 关键词：嵌入式系统设计方法；建模方法；o o t c p n ；模型验证；硬件描述语言 基于o ( w c p i n 模型的嵌入式系统设计方法研究 a b s t r a c t e m b e d d e ds y s t e m ，a s 雒i m p o r t a n tr e s e a r c hd i r e c t i o no fc o m p u t e rt e c h n o l o g y , h a sb e e n w i d e l ya p p l i e dt ov a r i o u sf i e l d s ih a sb e e nw i d e l yu s e di ne v e r yf i e l di nm o d e r nt i m e w i t ht h e p r e v a l e n ta p p l i c a t i o no fe r a b e d d e dp r o d u c ti ne v e r yf i e l d ，a n dw i t ht h ei n c r e a s i n go fu s e r r e q u r i e m e n t , t h ef u n c t i o no fe m b e d d e ds y s t e mh a sb e c o m em o r ea n dm o r ec o m p l i c a t e d ，t h e c o m p l e x i t yo fe m b e d d e ds y s t e md e s i g ni si n c r e a s i n g t h et r a d i t i o n a ld e s i g nm e t h o d sc a n n o t m e e tt h er e q u i r e m e n t so f t h ec o m p l i c a t e ds y s t e md e s i g na n ym o r e ，t h e r e f o r ed e s i g nm e t h o d s o ff u r t h e rg r a d e sa r et h en e wc h a l l e n g e sw h a tt h ec u r r e n td e s i g n e r sa r ef a c i n g a c c o r d i n gt ot h es t u d yo nt h ed e s i g nm e t h o d so ft h ee x i s t i n ge m b e d d e ds y s t e mm o d e l s ， t h i sp a p e rd r a wt h ei m p o r t a n c ea n da d v a n t a g e so ft h ef o r m a l i z e dm o d e l si ne m b e d d e ds y s t e m a i m e da tl i m i t a t i o n so ft h eb a s i cp e t r in e ti ne m b e d d e ds y s t e m ，s u c ha s ，w i t h o u tt i m ee l e m e n t s a n dh i e r a r c h i c a ls t r u c t t t r e s ，a n dw e a k n e s si np r o c e s s i n gd a t a , t h i sp a p e rf o c u s e si t ss t u d yo nt h e o b j e c to r i e n t e dt i m e c o l o rp e t r in e t ( o o t c p n ) m o d e la n df o r m a l i z e dd e f i n i t i o n sa r eg i v e no u t c o m p a r e d 晰也o t h e rm o d e l s ，t h i sm o d e ld e s c r i b e st h ea b m t yo ft h ed a t a , r e a l - t i m e ，l e v e l ，e r e h a sb e e ne n h a n c e df o rm o d e l i n go fc o m p l e xe m b e d d e ds y s t e m s i nm o d e lv e r i f i c a t i o nr e j e c t ，t h i sp a p e rr e s p e c t i v e l yd e s c r i b e dt h et h e o r ya n d c h a r a c t e r i s t i c so f t h es i m u l a t i o na n a l y s i sm e t h o d sa n dm o d e lc h e c k i n gm e t h o d s ，u g ht h e r e s e a r c ho ft h eb a s i cp e t r in e tm o d e lv e r i f i c a t i o nt e c h n o l o g y i tf o c u s e si t ss t u d yo nt h e d e s c r i p t i o no f t h ev e r i f i c a t i o nm e t h o da n dt e c h n o l o g yo ft h eo o t c p nm o d e lb a s e do nt h e h a r d w a r ed e s c r i p t i o nl a n g u a g e , a n de x a m p l e sa r ei l l u s t r a t e dt op r o v et h a t c o m p a r e dw i t ht h e t r a d i t i o n a lp e t r in e ts i m u l a t i o ns o r w a r e ，t h i sm e t h o daw i d e rs c o p eo f a p p l i c a t i o n ，p o r t a b i l i t y , f l e x i b l e ，e a s yt oc o n v e r tt ot h eu n d e r l y i n gd e s i g n f i n a l l y , i th a sc r e a t e das y s t e mm o d e lo ft h ee l e v a t o rs y s t e m ，a n dt h em o d e lh a s s i m u l a t e d ，s i i n u l a t i o nr e s u l t sh a v es h o w nt h a tt h ee m b e d d e ds y s t e mm o d e l i n gw a st h e f e a s i b i l i t ya n dc o r r e c t n e s sb a s e do no o t c p nm o d e l k e yw o r d s ：e m b e d d e ds y s t e md e s i g nm e t h o d ；m o d e l i n gm e t h o d ；o o t c p n ； m o d e l i n gv e r i f i c a t i o n ；h a r d w a r ed e s c r i p t i o nl a n g u a g e i i 西华大学硕士学位论文 。 目录 摘要i a b s t r a c t i i 1绪论1 1 1 研究的目的和意义。1 1 2 研究的背景及国内外现状：2 1 3 本文研究的主要内容及章节安排3 2 嵌入式系统设计方法：4 2 1 嵌入式系统基本理论4 2 1 1 嵌入式系统的定义。4 ，2 1 2 嵌入式系统的特点4 2 2 嵌入式系统的设计流程：j 5 2 3常用的嵌入式系统建模方法8 2 3 1 面向状态的模型8 2 3 2 面向活动的模型。1 0 2 3 3 面向结构的模型11 2 3 4 面向数据的模型。1 1 2 3 5 异构模型：1 2 3 基于o o t c p n 模型的建模方法1 4 3 1p e t f i 网基本理论1 4 3 1 1 p e t r i 网的基本定义：1 4 3 1 2p e l r i 网的变迁规则1 5 3 1 3 p e t r i 网的基本性质1 6 3 2 时延有色p e t r i 网1 7 3 2 1 有色p c t r i 网1 7 3 2 2 时延p e t r i 网1 9 3 2 3时延有色p e t d 网。2 0 3 3 面向对象的t c p n ：2 3 4 模型验证技术3 0 4 1 引言3 0 4 2p v t r i 网的仿真分析技术3 0 4 2 1 仿真分析方法概述。3 0 1 1 1 基于o o t c p n 模型的嵌入式系统设计方法研究 4 2 2 库所，变迁网的电路模拟3 3 4 2 3t c p n 的硬件实现3 5 4 3 模型检验技术4 1 4 3 1 计算树逻辑4 1 4 3 2 线性时态逻辑4 2 4 3 3 验证方法4 3 4 4小结4 4 5 应用系统的设计举例4 6 5 1电梯控制系统结构。4 6 5 2电梯控制系统模型建立4 7 5 2 1基本o o t c p n 模型的建立4 7 5 2 2 输入系统模型4 8 5 2 3 控制系统4 9 5 2 4 电机系统5 1 5 2 5 存储系统5 2 5 2 7电梯控制系统的o o t c p n 模型5 3 5 2 8电梯控制模型仿真分析5 5 结论5 7 参考文献：5 8 攻读硕士学位期间发表的论文及科研成果6 1 致谢6 2 西华大学硕士学位论文 1 绪论 1 1研究的目的和意义 。随着微电子技术和超大规模集成电路的高速发展，嵌入式技术已经广泛地应用到当 今各个领域，与人们的生活息息相关，小到掌上的数字产品，大到汽车、航天飞机。据 美国g a r t n e rg r o u p 公司在2 0 0 8 年调查后作出估计，到2 0 11 年前全世界投入使用的嵌 入式系统约有6 0 0 0 亿个，而且这个数字还不断在成倍增长【l 】。有学者甚至断言，以嵌入 式系统为代表的后p c 时代即将到来。 随着用户需求不断增加，对嵌入式系统的功能要求越来越强，导致嵌入式系统的规 模也越来越大，系统也越来越复杂，设计难度大大增加【2 捌。早期的嵌入式系统功能比较 简单，涉及到的技术比较单一，涉及的领域也比较少，+ 开发难度比较小。目前，随着嵌 入式产品的在不同领域的应用，用户需求的不断增加，嵌入式系统功能越来越强大，设 计难度也越来越大。复杂的嵌入式系统开发设计过程涉及到硬件技术、软件技术、信号 处理技术和微处理器技术等多个方面。同时，不同应用领域对嵌入式系统设计要求也不 相同，加大了设计工作的难度，大大增加了开发风险。传统的嵌入式系统设计方法已经 不能适应新的发展要求，研究探索适合嵌入式系统设计的方法和技术是人们面临的新挑 战。 在传统的设计方法中，设计者将关注的重点放在系统开发后期，也就是系统的具体 实现上。由于早期的嵌入式系统应用领域相对较小，功能简单，在开发初期设计者就能 够很容易对系统功能进行描述，所以开发后期系统的具体实现工作所占比重最大，是系 统开发的重点所在。近几十年来，随着各种c a d 工具出现和e d a 工具的出现，使得 r t l 级、模块级的设计实现变得越来越容易，后期设计风险也越来越小。另一方面，由 于嵌入式系统应用领域越来越广，功能越来越来强大，开发初期对系统功能的正确描述 显得越来越重要了，而不正确的描述很可能造成嵌入式系统设计的失败。 为了满足适应新形式下嵌入式系统设计的要求，工程师们的关注的重点应转向前期 设计，即关注的重点是如何正确的描述系统行为特性。本文旨在利用模型的思想，描述 系统的行为特性，在设计前期规避风险，从而提高嵌入式系统设计的可靠性。 基于模型的设计思路是利用一些形式化和非形式化的高层建模方法建立嵌入式系 统的抽象模型，支持边构造边校正，并通过仿真来验证系统设计的正确性，然后按这些 形式化的高层次模型自动生成可执行的代码框架，以实现模型的校验。这种基于高层次 抽象模型的设计过程可以大大减少系统的设计时间，并通过仿真验证和代码生成，大大 缺乏精确语义定义，难以对所建立的模型进行形式化的分析和验证，是的半形式化模型。 第二种是以p c t r i 网为代表的具有严格语法和语义的形式化建模方法，能够对系统模型 进行形式化的分析和验证。但是，形式化的建模不能描述客观事物的所有方面。特别是 对嵌入式系统建模中还存在很多问题，如实时性，层次性，数据处理能力等方面还存在 着不足。因此，研究适合嵌入式系统建模的p c t r i 网，成为形式化建模方法的研究热点【8 】。 在模型验证方面，主要包括有两种方法：模型检验和仿真分析。模型检验技术优点 是理论知识比较完善，技术比较成熟，自动化程度比较高，不足之处特别是对于庞大的 系统来说，模型检验往往只是理论上的验证。仿真分析方法的优点是理论知识比较容易 2 西华大学硕士学位论文 掌握，仿真工具比较容易获得，技术也比较成熟，具体应用涉及的工作量相对要小，不 足之处是对于每一次仿真分析只能验证特定用例的功能，而不能对所有的用例进行验 证，是一种有穷验证技术。两种方法都有优缺点，利用何种方法才能更好的验证模型， 是本文的研究重点。 1 3 本文研究的主要内容及章节安排 本文主要研究嵌入式系统设计方法，主要包括建模方法和模型验证。重点研 究基于扩展p e t r i 网的嵌入式系统建模方法和验证技术，给出实例验证建模方法的 正确性和可行性。具体研究的主要内容如下： ( 1 ) 对现有的嵌入式系统建模方法的研究，分析其特点和不足，指出形式化 建模在嵌入式系统建模中重要性和优势。 ( 2 ) 针对基本p c t r i 网在嵌入式系统建模中的不足，如没有时间因素、没有 层次结构、处理数据能力弱等，通过引入面向对象技术、时间网和有色 网，提出一种面向对象的时延有色p e t r i 网( o o t c p n ) 模型，给出模 型的形式化定义。 ( 3 ) 研究基本p e t r i 网模型的模型验证技术，分别阐述仿真分析和模型检验 方法的原理和特点。讨论基本p e t r i 网模型的电路仿真分析技术，提出 一种利用硬件描述语言描述o o t c p n 模型的方法，并给出实例说明。 ( 4 ) 通过对电梯系统建立系统模型，并对模型进行模型验证，验证本文建模 方法的可行性和正确性。 第一章：绪论 介绍本文的研究目的和意义以及研究背景和国内外现状。 第二章：嵌入式系统设计方法 介绍嵌入式系统的相关概念和常用设计方法的分析比较。 第三章：基于o o t c p n 模型的嵌入式系统建模方法 介绍嵌入式系统的p e t r i 网建模方法。 第四章：模型验证技术研究 介绍p e t r i 网的模型验证技术。 第五章：应用系统的设计举例 结合实例，验证本文建模方法的正确性和可行性。 3 基于o o t c p n 模型的嵌入式系统设计方法研究 嵌入式系统设计方法 嵌入式系统基本理论 1 嵌入式系统的定义 嵌入式系统已经广泛地应用到当今各个领域，并且与人们的生活息息相关。但是， 嵌入式系统的到目前为止还没有统一的标准。i e e e 协会给出的定义：嵌入式系统 于控制、监视或者辅助操作机器和设备的装置【9 】。而国内从事嵌入式系统的技术人 遍认同的定义：以应用为中心，以计算机技术为基础，软硬件可裁剪，适应对功能、 性、体积、实时性、可靠性、成本、功耗等方面严格要求的专用计算机系统。 可以从广义和狭义的角度来看嵌入式系统的定义。从广义上讲，只要是带有微处理 专用软硬件系统都可以称为嵌入式系统，如单片机。从狭义上讲，嵌入式系统仅仅 使用3 2 位以上微处理器、具有嵌入式操作系统并且具有特定功能的系统，那么单 就不算嵌入式系统。事实上，也正是由于3 2 位微处理器崛起，才出现嵌入式系统 名词，并渐渐应用到各个领域。 嵌入式系统之所以没有统一的标准，是因为其应用领域非常广泛，小到r a p 3 、手机、 相机，大到汽车电子设备、智能机器人、航空航天等，无法给出精确的定义。但是， 入式系统的定义可以看出，嵌入式系统实质上是实现特定功能的计算机应用系统。 2 嵌入式系统的特点 根据嵌入式系统的定义，可以看出，嵌入式系统是由硬件和软件相结合组成的具有 特定功能、用于特定场合的独立系统。其硬件主要由嵌入式微处理器、外围硬件设备组 成；其软件主要包括底层系统软件和用户应用软件组成。嵌入式系统与通用计算机系统 相比，有如下一些特点： ( 1 ) 专用性。由于嵌入式系统通常是面向某个领域具有特定功能应用的，所以 嵌入式系统具有专一性。 ( 2 ) 实时性。目前，嵌入式系统已广泛应用于工业控制、实时监测、通信等场 合，所以都对嵌入式系统有实时性的要求。对设计者和用户来说，实时性 是设计嵌入式系统重点考虑的一个重要指标。 ( 3 ) 可裁剪性。嵌入式系统开发工程师可以根据实际应用需要来量体裁衣，去 除冗余，从而使系统在满足应用要求的前提下达到最精简的配置。可裁剪 性也体现了嵌入式系统专用性。 4 西华大学硕士学位论文 ( 4 ) 可靠性高。可靠性是嵌入式系统设计的最重要的指标。小到m p 3 、手机， 大到汽车电子、航空航天都要求很高可靠性，且后者的可靠性要求极高。 ( 5 ) 功耗低。有很多嵌入式产品，例如p d a 、m p 3 、飞机、舰船、数码相机 等，这些设各不可能配各容量较大的电源，低功耗一直是嵌入式系统追求 的目标。 2 2 嵌入式系统的设计流程 由于早期的嵌入式系统功能简单，嵌入式系统的开发周期短，设计流程没有严格的 规范，随意性比较大，抽象级别比较低，设计的重点主要集中在后期的具体实现上。当 前，嵌入式系统规模越来越大，系统也越来越复杂，设计的难度也越来越大，开发风险 也大大增加，传统的设计方法无法规避设计风险。为此，人们在设计方法上引入了软件 工程的思想，并将整个系统设计过程划分为几个阶段，每一个阶段都有相应的设计任务 和设计目标，以及相应的开发工具和设计方法，其优点是将复杂的设计过程分解成几个 阶段，制定每个阶段的设计任务，明确相应的设计目标，降低设计过程的复杂性，从而 降低设计开发风险，提高系统开发的效率。 嵌入式系统的设计流程主要包括5 个阶段，如图2 1 所示，采用从上到下的方法， 从需求分析开始，到系统集成和测试完成整个设计过程。整个设计过程是从上到下，抽 象级别也是从高到低，对系统的描述也是越来越具体。也可以采用从下到上的设计方法， 从构件设计开始，实现各个构件的功能设计。一般情况下，复杂的系统设计过程都是采 用两种方法相结合的设计方法，本文只介绍从上到下的设计方法。 l 需求分析 j l 设计目标 j l 技术方案 i l 构件设计 j l 糸统集成和 测试 图2 1 设计流程 f i g 2 1d e s i g nf l o w t a b 2 2 d e s i g no b j e c t i v et a b l eo fa dc o l l e c t o r 名称a d 采集器 通道数双通道 最高采样率 2 5 0 k s p s 电压5 v - 5 v 实现双通道采集，最高采样率2 5 0 k s p s ， 功能 并设计成a d i p 核形式 6 西华大学硕士学位论文 ( 3 ) 技术方案阶段 技术方案是系统设计中的重要部分之一，它直接决定着整个系统的性能和生产成 本，是开发人员在实施开发任务之前必须做的，因此，这就要求开发人员依据经验和现 有的技术手段，给出一个可行的技术方案。 技术方案阶段是在设计目标的基础上，给出更加详细的技术指标和方案，如器件的 选型、软硬件划分问题。如表所示，显示了一个数据采集系统中的存储部分的技术方案 表。 表2 3n a nf l a s h 的技术方案表 f i g 2 3 t e c h n i c a lp r o p o s a lt a b l eo f n a n df l a s h 存储器 n a nf l a s h 器件名称 k 9 g 8 g 0 8 u o m p c b o 厂家 s a m s u n g 容量 1 g b “ 工作电压 2 7 v 3 6 v 封装t s o p ( 4 ) 构件设计阶段 构件设计是系统的具体实现，是系统实现的最重要的部分。构件设计主要包括 硬件设计和软件设计，在技术方案的基础上，通过软硬件设计协同设计，可以缩 短系统的开发周期。 在构件设计中有些构件是不用设计的，它们有标准构件可以直接使用，也有 一些是第三方提供的构件，如硬件中c p u 、存储器等；软件中的操作系统、驱动 程序、软件算法、l p 核等。除了现成的构件不需要设计，其他构件都需要在技术 方案的指导下，利用开发工具设计开发。 ( 5 ) 系统集成和测试阶段 系统集成和测试是整个系统设计最后一部分，也是验证系统是否到达设计目 标的关键阶段。 根据当前状态和输入来得到输出。 如图2 2 所示，显示了一个状态机的例子。s 1 ，s 2 ，s 3 表示三个状态，图中清晰地显 示了各个状态之间的转换关系。有限状态机的缺点是随着系统的规模越来越强大，状态 数也随之增加，导致状态空间爆炸问题。 西华大学硕士学位论文 图2 2 一个有限状态机的例子 f i g 2 2 a n e x a m p l eo ft h ef i n i t es t a t em a c h i n e p e t r i 网模型是由位置( p l a c e ) 集、迁移( t r a n t i o n ) 集和标记( t o k e n ) 集构成。其形式化 的定义如下： 其中，p = p 。，p 2 ，p 。) 是位置集合，t = 辑，t 2 ，乙) 是迁移集合；输入函数i ： 丁一尸+ ，定义了输入弧集合，输出函数o ：丁一p ，定义了输出弧集合；标记函数u ：定 义了每个位置中的托肯个数。 如图2 3 所示，显示了一个处理器的p e t r i 网模型。当p 1 和p 4 都有托肯时，t 1 就 会触发，运行后的结果如图2 3 ( b ) 所示。 图2 3 处理器的p n 模型 f i g 2 3 t h ep nm o d e lo f p r o c e s s o r 经过多年的发展，p e t r i 网已经成为一个易于理解、功能强大的建模语言，可以描述 系统的并发、异步、同步等操作特性。而且随着p e t r i 网理论的不断发展，各种相关的 仿真工具也开发出来了。 9 基于o o t c p n 模型的嵌入式系统设计方法研究 虽然p c t r i 网在建模和分析并发系统方面有着许多的优势，但是它也存在着许多不 比如缺少时间、层次概念以及对数据描述不足。 2 面向活动的模型 面向活动的模型主要有两种模型：数据流图和流程图。 数据流图是由结点集和边集组成。数据流图主要应用在数据处理占主的系统中建 比如在数字信号处理领域。通常，在数据流图表示中，矩形表示输入或输出结点， 表示活动结点。如图2 4 所示，显示了一个数据流图的例子。 图2 4 数据流图 f i g 2 4 d a t af l o wg r a p h s 控制流图是由结点集合和弧的集合组成。在数据图中弧用来表示数据流，而在控制 中表示顺序性或者控制流。通常，在控制流程图表示中，圆角矩形来表示起始结点 束结点，用矩形表示计算结点，用菱形表示决策结点。如图2 5 所示，给出了一个 图的例子。 图2 5 控制流图 f i g 2 5 c o n t r o lf l o wg r a p h 1 0 西华大学硕士学位论文 2 3 3 面向结构的模型 面向结构的模型主要是组件连接图( c c d ) 。数据流图或控制流图表示由数据或者控 制相关性连接的系统活动，而c c d 表示系统组件以及它们的互联关系，也就是说c c d 主要描述的系统的物理结构而不是功能性。如图2 6 所示，显示了一个面向结构的建模 例子。 系 图2 6 面向结构模型 f i g 2 6o b j e c ta r c h i t e c t u r em o d e l 2 3 4 面向数据的模型 面向数据的模型主要有两种：实体关系图和j a c k s o n 图。 面向数据的模型和面向活动的模型有着很大的不同，前者重点描述数据不是处理数 据的行为特性。面向数据的模型主要用于信息系统。 实体关系图( e i m ) 【2 0 】是面向数据的模型一种重要表示方法，它将系统定义为实体以 及实体之间的不同关系。在e r d 中，实体用矩形方框表示，关系用菱形方框表示。e r d 的优点是能够描述整个的各个数据之间的关系，主要用于数据结构复杂的系统中，缺点 是不能描述系统的时序特性。 如图2 7 所示，显示了一个实体关系例子。 基于o o t c p n 模型的嵌入式系统设计方法研究 图2 7 实体关系模型 f i g 2 7 e n t i t y - r e l a t i o nm o d e l j a c k s o n 图是另一种面向数据的模型【2 1 1 。e r d 是重点描述数据的属性和其相互关系， 合于有着复杂关系数据的系统；而j a c k s o n s 是利用数据的结构，把数据分解成子数据， 数据进行建模，适合于有着复合结构数据的系统。 3 5 异构模型 常见的异构模型主要有控制数据流图、结构图、程序状态机、面向对象等模型。 控n 数据流图【2 2 】是结合了数据流程图和控制流程图的优点，换句话说，控制数据 图既可以表示数据的相关性，又可以表示系统的控制顺序。如图2 8 所示，显示了一 控n 流程图的例子。 结构图用于描述系统的数据、活动和控制访问。同控n 流程图一样，它既可以表示 制信息又可以表示数据信息。不同的是结构图没有完全说明执行顺序。因此，结构图 要用于设计顺序执行的预备阶段。 程序状态机是结合了层次化并发有限状态机和程序设计语言的优点。它既可以描述 统的并发性、层次性，又可以用文本语言描述系统。 西华大学硕士学位论文 图2 8 控制数据流图 f i g 2 8 c o n 竹o f d a mf l o wg r a p h 面向对象的模型是将系统看成一组对象，每个对象是由数据和操作组成的。面向对 象的模型有很多优点，如可封装、重用性、继承性等特点。 如图2 9 所示，显示了一个面向对象的模型系统，系统除了对象以外，还包含 一组转换，用于定义变化的系统行为。由于面向对象的模型具有封装性，也就意 味着当一个对象改变其他对象的数据时，前者必须请求后者的操作。 尽管面向对象的模型有很多优点，但是对于需要复杂转换函数的系统来说，还是有 很多不足。在以后的设计中，要逐步解决这些不足。 对象 对象 图2 9 面向对象模型 f i g 2 9o b j e c t - o r i e n t e dm o d e l ( 2 ) t 是变迁集合，并和p 不相交； ( 3 ) f 是流关系，f 冬( p x r ) u ( r p ) ，即连接弧集合。 如果p 和t 都是有限集，则网v 就称为有限的网。 由定义3 1 可知，网包含了三个要素：p ( 库所) 、t ( 变迁) 、f ( 弧) ，其中f 又可 以细分为i ( 输入弧集合) 和o ( 输出弧集合) ，这些要素都只描述了系统结构特征，而 没有描述出系统的状态。为此，加入系统的状态元素：m a r k i n g ( 标识) 和t o k e n ( 令牌) ， 进而得出了基本p e t r i 网的定义。 定义3 2 设p n = ( p ，t ，i ，o ，m 0 ) ，其中 ( 1 ) p 是库所的集合； ( 2 ) t 是变迁集合，并和p 不相交； ( 3 ) i 是输入函数，定义从p 到t 的有向弧集合； ( 4 ) o 是输出函数，定义从t 到p 的有向弧集合； ( 5 ) m 0 是网络的初始标识，是一个向量，其中该向量的第i 维表示库所的 p i 中t o k e n 的个数。 西华大学硕士学位论文 由定义3 2 可知，p e t r i 网中有两大要素：p ( 库所，状态元素) 和t ( 变迁，变迁 元素) ，它们组成的集合是不相交的。利用p e t r i 网建立模型时，p 表示资源、发生条 件、地点、信道、等待队列、任务等元素，而t 表示事件、消息的发送接收、变 迁、动作等元素。如图3 1 所示，显示了一个简单的p e t r i 网的例子。 图3 1 f i g 3 1 由图3 1 可知，在p e t d 网中p ( 库所) 用小圆圈表示，t ( 变迁) 用矩形表示， t o k e n ( 托肯) 用小圆点或数字表示表示，如图3 1 所示，在p 1 中有2 个托肯，就有 2 个小圆点，也可用2 表示。 3 1 2p e t ri 网的变迁规则 p e t r i 网不仅能够描述系统的静态特性，还可以通过触发变迁描述系统的动态 特性。如图3 2 所示，描述了p e t r i 网的变迁规则。 性质如下： ( 1 ) 有界性，刻画状态空间的有限性； ( 2 ) 活性，刻画从任何可达标识开始，每一个变迁都至少发生一次； ( 3 ) 可逆性，刻画从任何可达标识到初始标识的可恢复性： ( 4 ) 互斥性，刻画变迁不能并发的特征或子标识不能同时满足的特征。 分析图3 3 ( a ) ，假设变迁t 1 发生，导致p 2 得到一个托肯。接下来对于t 3 来 说，触发条件不满足，系统进入死锁状态。所以此系统不具有活性，也不具有可 逆性。假设变迁t 2 发生，m = p 3 + 风。接下来变迁t 3 发生，得到m = p l + 岛。变迁 西华大学硕士学位论文 t 2 、t 3 重复发生n 次后，得到的标识m = p ，+ u p , 。在这里由于p 3 的标识能任意大， 库所p 3 是无界的。但是在实际应用中，库所p 3 代表的物理元素时，容量是有限的，所 以系统本身是无界的。假设变迁t 1 和t 2 同时满足触发，库所p 1 中至少有两个托肯， 而此时p 1 中只有一个托肯，所以不能满足假设条件，即t 1 和t 2 不能并发具有互斥性， 因而，系统是一个无界的、可死锁的且不可逆的。而图3 3 c o ) q = 的系统就是一个有界 的、活的且可逆的系统。 3 2 时延有色p e t ri 网 图3 3网系统 f i g 3 3 n e ts y s t e m 3 2 1有色p e t ri 网 在介绍有色网之前，先给出库所变迁系统的定义如下所示： 定义3 3 一个p t 系统是一个五元组n = ( p ，t ，p r e ，p o s t ，m o ) ，其中 ( 1 ) p 是一个有穷集合( 库所集合) ； ( 2 ) t 是一个有穷集合( 变迁集合) ，并且和p 不相交； ( 3 ) p r e ，p o s t i n l 9 刖是矩阵( 网n 的向前和向后关联矩阵) 。c = p o s t p r e 称为网n 的 关联矩阵； ( 4 ) m 。是初始标识。 c d ( p ) = 如，c ) 。 西华大学硕士学位论文 图3 4 有色网变迁规则 f i g 3 4t r i g g e rr u l eo ft r a n s i t i o no fc o l o rn e t 3 2 2 时延p e t ri 网 由于经典的p e t r i 网缺乏时间观念，而在嵌入式系统中，实时性是非常重要的一个 因素。随着p e t r i 网的发展，出现两类基于时间的p e t r i 网模型。一类是由r a r n c h a n d a m i 提出的时延p e l r i 网，规定每个变迁都有时延过程，一旦变迁使能就立即触发。另一类 是由m e r l i 提出的时间p e t r i 网模型，规定每个变迁都有时间区间( a b ) ，任何变迁在触发 前，必须连续使能( a b ) 个时间单元。基于上述所述，结合嵌入式系统的特点，给出时延 p e t r i 网的形式化定义。 定义3 5 一个时延p e t r i 网( t p n ) 是一个七元组n = ( p ，t ，p r e ，p o s t ，m o ，d i ) ，其中 ( 1 ) p 是一个有穷集合( 库所集合) ； ( 2 ) t 是一个有穷集合( 变迁集合) ，并且和p 不相交； ( 3 ) p r e ，p o s t i n i 卟1 1 1 是矩阵( 网n 的向前和向后关联矩阵) 。c = p o s t p r e 称为网n 的 关联矩阵； ( 4 ) m 。是初始标识； ( 5 ) d ；是变迁的延时响应时间集。 如图3 5 所示，显示了一个时序p e t r i 网的例子。对于变迁t 1 来说，它要延迟 2 个时间单位才能响应，对于t 2 来说，它要延迟1 个时间单位才能响应。虽然t 1 和t 2 是并发的、冲突的，但是，通过引入了时间因素以后，就很好的解决了这个 问题。通过例子可以看出，加入了时间因素以后，不仅解决p e t r i 网缺点问题，而 1 9 定义3 6 一个时延有色p e t r i 网( t c p n ) 是一个八元组 n = ( p ，t ，p r e ，p o s t ，c ，c d ，d i ，m o ) ，其中 p 是一个有穷集合( 库所集合) ； t 是一个有穷集合( 变迁集合) ，并且和p 不相交； c 是颜色类的集合； c d ：p u t c 颜色域的映射： p r e ，p o s t i n l 9 州是矩阵( 网n 的向前和向后关联矩阵) ，使得对于每一对 q ，t ) pxt ，p r e p ，t ：c d ( t ) 一b a g ( e a ( p ) ) 和p o s t p ，t 】：c d ( t ) _ b a g ( c d ( p ) ) 是映射。 d ；是变迁的延时响应时间集。 m 。是初始标识； 由定义可知，t c p n 是有色网和时延p e t r i 网的结合，也是对基本p e t r i 网的形 式化的扩展。具体的扩展有以下几个方面： 西华大学硕士学位论文 托肯扩展：不同颜色，代表不同的资源或数据。适合嵌入式系统对数据的 处理。 变迁扩展：变迁触发，加入时间延迟，能够更好的模拟实时系统，并处理 并发问题，同时也加入变迁颜色，表示不同的数据类型。 库所扩展：库所中不再是一种资源，而是加入了颜色集，能够在同一个库 所中表示各种资源或数据类型。 弧扩展：加入了颜色集，不同的颜色可以表示不同的数据类型，同时，权 值以变量或常量的形式表示。 通过上述分析，可以看出来p e t r i 网在不同方面都有了扩展，增强了处理数据 的能力，同时对实时系统的模拟起到重要的作用。尽管t c p n 在数据处理、实时 性方面都了很大提高，但是在描述复杂系统的时候，还是遇到状态空间爆炸的情 况，且模型不易理解。通过分析研究，层次化的结构可以解决这一问题，具体实 现在下一节详述。 ( 2 ) 图形表示 p c t r i 网的图形表示有利于分析和理解网的特性。t c p n 采用有向、加权、时 间三分图来表示，图形元素包括库所、变迁、弧。托肯颜色集可以分为几种类型， 而把类型称为颜色，因此可以把颜色看成数据类型。库所用圆圈表示，变迁用矩 形表示，弧上的权值可以用变量或表达式表示，也可以用常量表示变迁的延迟时间 标在变迁上。库所中可以用不同的颜色代表不同的对象。变迁中可以用不同颜色 代表不同的触发方式。如图3 6 所示，显示了一个总线结构的两个功能单元之间循 环运作的网。图中颜色集：t o k e nm o d e s = a ，b ) ，弧上的权值用常量表示。 tt ( 3 ) 变迁规则 颜色集：t o k e n m o d e s = a ，b ) 常量：a