软件设计方法

1、第4讲 实时软件设计方法 主讲: 黎忠文,2020/6/22,2,内容提要 本讲首先讲述了RSTAD的一些相关概念，并以行驶监控系统案例介绍了其应用步骤和方法。 介绍了DARTS的相关知识，并以行驶监控系统案例介绍其使用步骤和方法。 对本讲中介绍的各种并发和实时软件设计方法进行比较。 最后概述了使用性能模型和应用实时调度理论进行软件设计性能分析的过程。,2020/6/22,3,目 录 4.1 实时系统的结构化分析与设计 4.2 实时系统设计方法 4.3 并发和实时软件设计方法的比较 4.4 并发与实时系统软件设计性能分析,2020/6/22,4,转换可以是数据转换或控制转换。 在设计过程中，功

2、能被映射为模块。 以状态转换图形时表示的有限状态机用于定义系统的行为特征。 控制转换表示的是状态转换图的执行过程。 实体关系（ER）模型用于显示系统中数据存储之间的关系模型。 模块内聚在模块分解过程中作为一种标准来使用，用于确定模块内部的强度或统一性。 模块耦合在模块分解过程中作为一种标准来使用，用于判断模块间连接性的程度。,4.1 实时系统的结构化分析与设计,4.1.1 基本概念,2020/6/22,5,4.1.2 表示法,4.1 实时系统的结构化分析与设计,实时结构化分析中使用了数据流/控制流图。图4-1中显示的是用于数据流/控制流图的Ward/Mellor表示法。,状态转换图是有限状态机

3、的图形表示法。 实体关系图是E-R模型的图形表示法。 结构图用于显示程序分解为模块的方式，还用于显示模块间的接口。,图4-1 实时结构化分析表示法,2020/6/22,6,4.1.3 使用方法的步骤,实时结构化分析 在实时结构化分析阶段，将会发生以下活动: 开发系统环境图。 实现数据流/控制流的分解系统要分解为多个功能并且要以数据流或控制流的形式定义功能间的接口。 开发控制转换（Ward/Mellor）或控制规范（Boeing/Hatley）对结构化分析主要的实时扩展是引入了对控制问题的考虑，以定义系统的行为特征。 定义小说明（mini-specifications,或过程规范）通常使用的是结

4、构化的英语。 开发数据字典数据字典用于定义所有的数据流、事件流、数据存储。,4.1 实时系统的结构化分析与设计,2020/6/22,7,实时设计 在RTSA阶段之后，Boeing/Hatley方法使用了系统构架图。Ward/Mellor方法则继续采用以下步骤： f) 将转换分配到各个处理器中。 g) 将转换分配到各个任务中每个处理器的转换都被分配到并发任务中。 h) 结构化设计指定任务中的转换使用结构化设计分解为多个模块。 转换分析是用于将数据流图映射为结构图的一种策略，其重要的流程是输入-处理-输出流。 在模块分解过程中，功能内聚和信息内聚被认为是最强的内聚形式。数据耦合是耦合的最低形式。,

5、4.1 实时系统的结构化分析与设计,2020/6/22,8,4.1.4 设计过程的成果,实时结构化分析应用RTSA所产生的规范包括以下内容： 系统环境图； 数据流/控制流图的层次集合； 数据字典； 小说明。 定义每种控制转换或控制规范的状态转换图。 结构化设计对于每个程序来说，都有一个结构图来显示将其分解为模块的方式。,4.1 实时系统的结构化分析与设计,2020/6/22,9,4.1.5 行驶监控系统案例研究,实时结构化分析 实时结构化分析规范包括系统环境图、数据流/控制流图的层次集合以及状态转换图。如图4-24-11所示。这个方案使用了Ward/Mellor表示法。 开发系统环境图,4.1

6、 实时系统的结构化分析与设计,图4-2显示的是系统环境图，每个外部实体由一个终端表示。,图4-2 行使控制系统环境图,2020/6/22,10,分解系统环境图 图4-3为顶级数据流/控制流图，其中系统环境图分解为两个主要功能行驶控制功能和监视功能。,4.1 实时系统的结构化分析与设计,图4-3 分解为子系统,2020/6/22,11,实现汽车行驶控制 实现汽车行驶控制（图4-3）分解为图4-4所示的数据流图。有3个数据转换在监视汽车的传感器。,4.1 实时系统的结构化分析与设计,图4-4 实现汽车行驶控制,2020/6/22,12,行驶控制状态转换图 控制速度数据转换（图4-4）分解为数据流/

7、控制流图。图4-5中的行驶控制状态转换图由图4-6中的【行驶控制】控制转换来执行。,4.1 实时系统的结构化分析与设计,在使用图4-5中的实时 结构化分析约定时，其中的矩形表示状态，带有标签的箭头表示状态转换。在直线的上方是可以引起状态转换的输入事件。在直线的下方是在发生转换时生成的输出事件。输出事件触发（T）、启动（E）或禁止（D）数据转换，然后执行指定操作。,图4-5 行驶控制状态转换图,2020/6/22,13,从行驶控制的角度来看，汽车的不同状态包括： 停机。 开始“非制动” 。 开始“制动”。 加速。 巡行。 巡行关闭非制动。 巡行关闭制动。 恢复巡行。,4.1 实时系统的结构化分析

8、与设计,输出事件如下所示： E1 启动“增加速度” D5 禁止“维持速度” D2 禁止“增加速度” E6 启动“恢复巡行速度” T3 触发“选择所需速度” D7 禁止“恢复巡行速度” E4 启动“维持速度” T8 触发“清除所需速度”,2020/6/22,14,控制速度 经触发的转换是一次性函数。 在整个状态的过程中启动的转换很可能是可以循环的。,4.1 实时系统的结构化分析与设计,在状态转换时，触发、启动或禁止控制速度（图4-6）过程中DFD上的数据转换。,图4-6 控制速度,2020/6/22,15,测量距离和速度 图4-4中的【测量距离和速度】数据转换可以分解为图4-7中的数据流图。,4

9、.1 实时系统的结构化分析与设计,图4-7 测量距离和速度,2020/6/22,16,4.1 实时系统的结构化分析与设计,【控制校准】是使用图4-8所示的状态转换图来定义的。,图4-8 控制校准状态转换图,2020/6/22,17,实现汽车监视 实现汽车监视（图4-3）的过程在图4-9中进行了进一步分解,4.1 实时系统的结构化分析与设计,图4-9 实现汽车监视,2020/6/22,18,监视并显示平均值 图4-9中的【监视并显示平均值】数据转换分解为图4-10中所示的数据流图。,4.1 实时系统的结构化分析与设计,它计算并显示了每加仑汽油可以行驶的平均英里数和每小时行驶的英里数。,图4-10

10、 监视并显示平均值,2020/6/22,19,检查维护需要 图4-9中的【检查维护需要】数据转换分解为图4-11中所示的数据流图。,4.1 实时系统的结构化分析与设计,要定期进行3种维护服务：滤油器、空气过滤器和大修维护。每种服务的提供方式都是类似的。,图4-11 检查维护需要,2020/6/22,20,结构化设计 下一步，RTSA规范要映射到结构化设计中。如图4-124-18所示。,4.1 实时系统的结构化分析与设计,结构图中的模块主要是功能模块，其中也有一些信息隐藏模块。主模块行驶监控系统（图5-12）由一个环形循环，在这个循环中可以判断何时调用下级模块：实现汽车行驶控制和实现汽车监视。,

11、图5-12 行驶监控系统结构图,2020/6/22,21,实现汽车行驶控制 对应于其4个主要功能，实现汽车行驶控制有4个下级模块。在【获得行驶控制输入】模块中，选择的是使用轮询I/O。,4.1 实时系统的结构化分析与设计,图4-13 获得行驶控制输入结构图,2020/6/22,22,轴中断程序还要更新一个内部变量【轴转数】 （ShaftRotation Counter），然后【确定距离】模块（图4-14）要访问这个变量来计算汽车所经过的【累积距离】 。,4.1 实时系统的结构化分析与设计,图4-14 确定距离和速度结构图,2020/6/22,23,无论何时出现新的行驶控制输入， 【实现汽车行驶

12、控制】模块都要调用【控制速度】模块（图4-15）,4.1 实时系统的结构化分析与设计,图4-15 控制速度的结构图,2020/6/22,24,时间问题 每次循环中，【实现汽车行驶控制】模块都会调用【获得行驶控制输入】模块判断是否有新的输入。 然后它会调用【确定距离和速度】模块来更新累积距离并计算当前速度。 下一步就是调用【控制速度】模块来处理下一次的行驶控制事件和/或实现任何状态依赖功能。 最后，该模会会调用【进行校准】 （图4-16）来检查是否发生了校准事件,4.1 实时系统的结构化分析与设计,图4-16 实现校准结构化图,2020/6/22,25,实现汽车监视 【实现汽车监视】模块调用【获

13、得复位输入】（图4-12）模块，用于确定是否某个里程或维护复位按钮被按下。,4.1 实时系统的结构化分析与设计,例如，如果按下了MPH复位按钮，【实现汽车监视】模块就会调用【监视并显示平均值】模块（图4-17）。,图4-17 监视和显示平均值结构图,2020/6/22,26,如果按下了其中某个维护按钮，【实现汽车监视】模块就会调用【检查维护需要】模块（图4-18）。,4.1 实时系统的结构化分析与设计,图4-18 检查维护需要结构图,2020/6/22,27,4.1.6 方法评估,优点包括： 结构化分析及其实时扩展在项目中得到了广泛应用。 有大量的CASE工具可以支持RTSA； 使用数据流图和

14、控制流图有助于对系统的理解和评审。 强调了使用状态转换图/表的重要性。 缺点包括： 对于如何实现系统分解并没有提供足够的指导。 与NRL需求规范方法不同的是，RTSA并没有将系统作为黑盒来开发。这样就模糊了需求与设计之间的界限。 结构化设计主要用于分解功能模块的程序设计方法，而不能用于解决将系统分解为并发任务的问题。 在信息隐藏的应用中，结构化设计方法落后于NRL方法和面向对象的设计方法。,4.1 实时系统的结构化分析与设计,2020/6/22,28,4.1.7 扩展与变化,ESML（Extended System Modeling Language）是将Ward/Mellor方法与Boein

15、g/Hatley方法结合在一起用于实时结构化分析的一种尝试。 在开发状态转换图方面，Ward/Mellor方法支持事件，但不支持条件，而Boeing/Hatley方法支持条件却不支持事件。 在ESML和COBRA中解决了所有这些限制,既支持事件又支持条件，这一点与NRL方法和状态图表示法是相同的。,4.1 实时系统的结构化分析与设计,2020/6/22,29,4.2.1 基本概念 任务结构化标准可以为设计人员将实时系统分解为并发任务的时候提供帮助。 任务接口可以采用的形式有消息通信、事件同步或信息隐藏模块（IHM）。 消息隐藏作为封装数据存储的标准来使用。 采用状态转换图形式的有限状态机用于定

16、义系统的行为特征。 使用事件顺序识别系统子集，来协助演化原型法和增量式开发。这些图确定了用于处理外部事件的任务和模块的执行顺序。,4.2 实时系统设计方法,2020/6/22,30,4.2.2 表示法,在RTSA中使用了数据流/控制流图。这些图是对数据流图的扩展，包括事件流和控制转换。 状态转换图是有限状态机的图形表示，其中的节点代表状态，弧线代表状态转换。,4.2 实时系统设计方法,DARTS设计方法使用任务构架图来显示系统分解为并发任务的过程。如图4-19所示。 起源于结构化设计的结构图在DARTS中用于显示如何将一个任务分解为多个模块。,图4-19 任务构架图表示法,2020/6/22,

17、31,4.2.3 使用方法的步骤,方法中所使用的步骤如下： 使用实时结构化分析方法开发系统规范。 将系统划分为多个并发任务。 定义任务接口。 设计每个任务。 4.2.4 设计过程的成果 设计过程的3个成果是： RTSA规范； 任务结构规范。 任务分解。,4.2 实时系统设计方法,2020/6/22,32,4.2.5 行驶监控系统案例研究,实时结构化分析 应用DARTS的第一个步骤是开发RTSA规范。 任务结构化,4.2 实时系统设计方法,在开发了RTSA规范之后，DARTS使用了任务结构化标准，用于确定系统中的并发任务。 图4-20显示的是用于行驶监控子系统的任务构架图。,图4-20 行驶控制

18、子系统的任务构架图,2020/6/22,33,图4-21显示的是监视子系统任务构架图,4.2 实时系统设计方法,图4-21监视子系统任务构架图,2020/6/22,34,任务接口 这些任务通过消息或IHM进行通信。 由多个任务访问的数据存储要映射到IHM中。因此，在行驶控制子系统中，【当前速度】、【所需速度】、【累积距离】、【轴转数】和【校准常数】数据存储都要映射到信息隐藏模块中。在监视子系统中，3个任务之间的接口要通过数据存储映射到IHM中。 到行驶控制任务的接口是松散耦合先进先出队列。,4.2 实时系统设计方法,2020/6/22,35,结构化设计 一旦设计完任务并定义了任务间的接口之后，

19、下一步就要通过使用结构化设计方法，将任务分解为多个模块。这些模块主要是功能模块，有些是IH。,4.2 实时系统设计方法,在结构化设计中，通常位于层次结构的最低层。 图4-22显示了行驶控制任务的结构。,图4-22 行驶控制任务结构图,2020/6/22,36,图4-23显示的是【汽车速度控制】任务的结构。,4.2 实时系统设计方法,这个任务通过调用【接受速度命令】模块并等待消息来接收速度命令。 【汽车速度控制】模块的设计是事务分析的一个例子。,图4-23 汽车速度控制任务结构图,2020/6/22,37,图4-24所示为【实现校准】模块的结构图。该模块调用了【读取校准】输入模块来接收输入。,4

20、.2 实时系统设计方法,图4-24 实现校准任务结构图,2020/6/22,38,4.2.6 方法评估,这种方法优点包括： 将系统分解为多个并发任务，并提供了用于确定任务的标准。 对于定义任务间接口的方式，该方法提供了详细的指导。 主要使用了状态转换图，这在实时控制系统的设计中是非常重要的。 该方法提供了从RTSA规范到实施设计的转换。 这种方法的缺点包括： 虽然DARTS使用了信息隐藏技术来封装数据存储，但使用的广泛性并没有达到使用NRL和OOD方法的程度。 使用DARTS的潜在问题是：如果RTSA阶段的工作完成得不好，那么任务的结构化工作就会更加困难。,4.2 实时系统设计方法,2020/

21、6/22,39,4.2.7 扩展与变化,将系统分解为子系统的方法之一是称为DART/DA的方法，它是对DARTS方法的扩展，可以支持分布式实时应用程序。 DARTS在信息隐藏中的缺点通过ADARTS方法和CODARTS方法得到了解决。 ADARTS和CODARTS的设计可以使用类似于Buhr图的图形化表示法来描述。 在CODARTS方法中，使用RTSA的潜在问题通过使用COBRA分析和建模方法得到了解决，而并非使用RTSA方法。,4.2 实时系统设计方法,2020/6/22,40,4.3.1 并发任务比较,虽然所有的方法都在某种程度上解决了并发的问题，但是它们的侧重点各有不同。对DARTS和J

22、SD这两种方法来说，并发任务比较重要。NRL方法和OOD方法不侧重于任务结构化。 Ward/Mellor版本的RTSAD方法，可以将系统分解为多个并发任务，但对此提供的指导却很少。结构化设计（SD）是一种程序设计方法，而不能解决任务结构化的问题。而结构化设计可以用于设计单个任务，与使用DARTS方法的作用相同。 在行驶控制问题中，结构化设计方案解决了一个内在的并发问题，并将其转换为顺序性方案。 DARTS在任务结构化领域解决了RTSAD的缺点。,4.3并发和实时软件设计方法的比较,2020/6/22,41,与SD方法不同，DARTS方法并没有使用循环指令来控制整个系统，而是更具有独立性。 JS

23、D模型任务类似于DARTS中的控制任务。 在映射任务时和把功能分组的过程中，NRL方法没有使用DARTS方法中的任务内聚或JSD方法中任务转换的概念。 与DARTS方法和NRL方法不同，OOD方法认为可以使用相同的对象结构化标准来确定任务（主动对象）和信息隐藏模块（被动对象）。 面向对象的设计方法没有用于优化设计的策略，而DARTS提供了任务内聚标准，JSD提供了任务转换方法。,4.3 并发和实时软件设计方法的比较,2020/6/22,42,4.3.2 信息隐藏和对象比较,在NRL方法和OOD方法中，信息隐藏是非常重要的基本原则。DARTS方法和RTSAD方法也使用了这种概念，但是JSD方法没

24、有使用。 NRL方法和OOD方法都侧重于将系统分解为信息隐藏模块（对象）。 在NRL方法中有一类模块不能使用OOD方法直接确定。 与NRL方法相比，在OOD方法的对象结构化过程中，并没有限制让每个对象/模块只能隐藏一个设计决策。 RTSAD方法在信息隐藏的领域并无长处可言。在这种方法的应用中，结构化设计方法要落后于NRL方法和OOD方法。 DARTS使用信息隐藏概念的程度比不上NRL方法和OOD方法。,4.3 并发和实时软件设计方法的比较,2020/6/22,43,4.3.3 有限状态机比较,RTSAD、DARTS、NRL将有限状态机的使用作为主要问题来考虑。在OOD中它是一个次要问题。在JS

25、D中采用的是使用实体结构图来描绘时间顺序的方法。 Ward/Mellor版本的RTSA方法只允许在状态转换中出现事件，而不允许出现条件。Boeing/Hatley方法允许出现条件而不允许出现事件。NRL方法既支持事件也支持条件，而且还可以使用更为简明的状态转换表。 在结构化设计中没有很好解决的状态依赖问题在DARTS中得到了解决。 在OOD方法中，可以通过封装在对象中的有限状态机来定义对象。 在JSD方法中，所使用的常规表达式表示法在数学上等价于有限状态机表示法。,4.3 并发和实时软件设计方法的比较,2020/6/22,44,4.3.4 时间约束,这里介绍的每种方法都在一定程度上解决了时间约

26、束的问题。 RTSAD方法在分析和设计阶段解决了时间约束的问题。 DARTS使用RTSA时间规范将时间预算分配到每个任务上。 在NRL方法中，要在需求阶段对那些生成系统输出的定期功能和请求功能指定时间约束。 在JSD方法中，使用网络图可以确定单个任务的时间约束。 在OOD方法中，时间图可以用于显示对象之间的时间依赖关系。 总之，时间约束问题在实时系统中很重要，它是大多数用于实时系统的软件设计方法的特征之一。,4.3 并发和实时软件设计方法的比较,4.4.1 性能模型,4.4 并发与实时系统软件设计性能分析,概念 计算机系统的性能模型是对真实计算机系统行为的抽象。可以是数学模型或模拟模型。可以是

27、静态的，也可是动态的。 队列模型 是计算机系统的解析模型，用于分析系统中对有限资源的竞争和预测系统性能，是计算机系统性能的高级模型。 模拟模型 是确定设计是否完善且符合时间要求的有效方式。 计算机系统建模中的问题 开发模型时考虑的主要因素包括开发模型的开销、模型的详细程度、完成模型的速度及其精确度。,本节概述了实用性能模型和应用实时调度理论进行软件设计性能分析的过程。,2020/6/22,46,4.4 并发与实时系统软件设计性能分析,4.4.2 Petri网 由于有限状态机的严格顺序性，因此不能用于对平行关系进行建模。 Petri网可以直接对并发系统进行建模，是更为有利的工具。有限状态机是其串

28、行子集。 Petri网使用有向图表示，支持的两种节点称为库所。其执行由令牌来控制。 Petri网既可以作为分析工具也可以作为建模工具使用，功能非常强大。,2020/6/22,47,4.4 并发与实时系统软件设计性能分析,4.4.3 实时调度理论 介绍 实时调度理论解决了具有硬性最后期限的并发任务，基于优先级进行调度的问题。 调度定期任务 定期任务具有周期T，它是任务执行时的频率，还有执行时间C,表示在周期中所需的CPU时间。CPU的使用率U为C/T。如果任务没有超出所有的最后期限，就可以调度。 对于一组独立的定期任务来说，速率单调算法可以根据任务周期为每个任务指定一个固定优先级，任务周期越短，

29、优先级越高。,2020/6/22,48,使用率限定定理 对于一组定期独立任务，如果每个任务C/T的总和都低于整个CPU使用率的上限，那么这些任务可一直显示为可在各自的周期内完成。 使用率限定定理（定理1） 对于所有的任务阶段，通过速率单调算法调度的一组数目为n的独立定期任务会在周期结束之前完成运行，只要满足以下条件：,4.4 并发与实时系统软件设计性能分析,其中Ci和Ti分别是任务ti的执行时间和周期。 当任务的数量趋向于无穷大时，上限U(n)的值就会趋向于69%。,2020/6/22,49,4.4 并发与实时系统软件设计性能分析,根据定理1，在表4-1中给出了9个任务的使用率界限。这是最坏情

30、况的估计。,表4-1 使用率限定定理（定理1）,速率单调算法所具备的优点是：在瞬时过载的情况下可以保持稳定。,2020/6/22,50,4.4 并发与实时系统软件设计性能分析,完成时间定理 如果一组任务的使用率总和超过了定理1中所规定的上限，那么就可以使用定理2进行检测，它提供了一种准确的判断方法。其可以用于检查每个任务ti是否可以在第一个时间周期之前完成。 完成时间定理（定理2） 对于一组独立的定期任务，在所有任务同时启动的情况下，如果每个任务都可以在第一个时间周期内完成执行，那么启动事件的任意组合都可以使这些任务在各自的周期内完成执行。 定理2可以使用时间图来进行图形化演示。请看下面例子,

31、2020/6/22,51,4.4 并发与实时系统软件设计性能分析,图4-25 所示即为演示这3个任务执行的时间图。,图4-25 时间图,2020/6/22,52,4.4 并发与实时系统软件设计性能分析,完成时间定理的数学函数 定理3 对于所有的任务相位，速率单调算法调度一组n个独立定期任务将会在最后期限之前完成执行，当且仅当满足以下条件：,其中Cj和Tj分别是任务tj的执行时间和周期，并且,公式中，ti表示要检查的任务，tk表示每个会影响任务ti完成时间的高优先级任务。,2020/6/22,53,4.4 并发与实时系统软件设计性能分析,调度定期任务和非定期任务 当处理非定期任务（异步任务）以及

32、定期任务的时候，就要对速度单调理论进行扩展。非定期任务用于处理事件所使用的CPU时间Ca要作为在每个周期Ta中使用的Ca值的票保留起来，如果不能在周期Ta中激活任务，就要将票丢弃。 如果在应用程序中有许多非定期任务，就可用零星服务算法。 使用任务同步进行调度 优先级反向指进入临界区的低优先级任务阻碍试图进入临界区的高优先级任务执行的情况。 优先级顶置协议避免了互斥死锁，并提供了受到限制的优先级反向。至多只能有一个低优先级任务可以阻塞高优先级任务。,2020/6/22,54,4.4 并发与实时系统软件设计性能分析,经过归纳的实时调度理论 需要对基本的速度单调调度理论加以扩展，以便解决速率单调优先

33、级反向的情况。 考虑这样一种情况：任务ti的周期为Ti，在这个周期中，任务要消耗Ci单位的CPU时间。对原理13扩展，明确检查每个任务ti，确定是否满足第一个最后期限，要考虑的问题： 周期小于ti的高优先级任务抢占的时间。这些任务可以抢占任务ti很多次。 任务ti的执行时间。 较长周期的高优先级任务抢占。这些任务都具有非速率单调优先级。 低优先级任务阻塞的时间。这些任务只可以执行一次。,2020/6/22,55,4.4 并发与实时系统软件设计性能分析,因为对于任何给定的任务ti来说，情况a)和情况b)都可以使用定理13来处理，对定理13的归纳要考虑情况c)和情况d)。定理1（使用率限定定理）要进行扩展以解决上面所提出的4种情况：,泛化使用率限定定理在这里称为定理4。Ui是任务ti在周期Ti内的使用率范围。其中有4个概念： 周期比ti短的高优先级任务所抢占的全 部使用率。 任务ti的CPU使用率。 任务ti所经历过的最坏情况阻塞使用率。 周期比ti长的高优先级任务所抢占的全部使用率。,2020/6/22,56,实时调度与设计 在设计阶段或任务实现之后，实时调度理论可以应用到一组并发任务中。 在设计阶段，设计人员有为任务选择指定的优先级的自由。一般来说，所有可能的优先级都应该根据速率单调理论来指定。这种方法容易应用到定期任务中。 应用归纳实施调度理论的例子 有4个任务，其