系统建模

发表于 | 分类于
字数统计: 3,216

概念

CPS系统与实时系统的区别？

实时系统（Real-Time Systems）
  • 定义：系统的正确性不仅取决于计算的逻辑结果，还取决于产生结果的时间，在计算和操作上具有性能最后期限。 实时系统通常是嵌入式的，意味着计算系统存在于一个更大的系统内部，目的是帮助系统实现其整体职责。
  • 时间定义：
    • 时间约束（Timing constraint）：对执行时间行为的约束（包括硬实时和软实时）
    • 发布时间（Release Time）：作业变成为可执行的时间。如果所有的工作在系统开始执行时被释放，那么就认为没有释放时间
    • 截止时间（Deadline）：工作被要求执行完成的时间。如果截止时间是无限的，那么工作就没有最后期限。绝对截止时间等于发布时间加上相对截止时间
    • 响应时间（Response time）：作业从发布到执行完成的时间长度

  • 特征

    • 及时性：行为的及时性与时间约束有关，如截止时间。最后期限可能很硬或很软。时效性的重要建模问题是建模执行时间，截止时间，到达模式，同步模式和时间源。

    • 并发性：

      ​ 多个操作顺序链的同时执行。围绕并发系统执行的问题与此有关：

      ​ a.并发线程的调度特性——线程调度

      ​ b.即将到来的事件的到来模式

      ​ c.线程必须同步时使用的集合点模式

      ​ d.控制对共享资源访问的方法

    • 可预测性

    • 正确性： 正确性表明一个系统总是运行正确。

    • 鲁棒性：鲁棒性表明系统即使在遇到新的情况（不在计划中）下也是可靠的。因此必须警惕死锁，竞争以及其他异常情况

实时操作系统

实时性能定量指标包括

  • 任务上下文切换时间 ：中断延迟，响应，恢复时间，任务响应时间
  • 最大中断禁止时间：反映内核对外界停止中断响应的最长时间

提高内核实时性的方法：任务互斥、同步

资源有限等待：任务没能获得需要的资源会被阻塞。如果资源不是任务继续运行必备的，任务可选择有限等待该资源

优先级反转问题解决：抢占式任务调度中的资源竞争，输入输出时间不一致导致抖动，优先级本身的不确定性导致可预测性下降。多任务内核应允许动态改变任务的优先级以避免发生优先级反转现象。为防止发生优先级反转,内核能自动变换任务的优先级,这叫做优先级继承(Priority inheritance)。

CPS系统(建模对象)

​ Cyber（信息技术）: 计算，通信，控制（3C技术,computation,communication, control )，并且离散，逻辑，交换的系统；

​ Physical（物理系统）： 自然的和人造的系统受物理定律的支配，并持续运行；如嵌入式、传感系统

​ Cyber-Physical Systems（信息物理融合系统）: 网络和物理系统紧密结合在一起的系统。

CPS系统的特点

  • 信息-物理的耦合由新的需求和应用驱动
    • 网络工作在多个和极端的规模下，每个物理组件中的网络性能，大规模的有线和无线网络
  • 系统的系统
  • 新的时空约束
    • 多个时间和空间尺度上的复杂性，动态重组/重新配置，非传统的计算和物理基板
  • 通信/计算/控制 之间的新型交互
    • 自动化程度高，控制回路必须在所有尺度上关闭，控制回路中有大量非技术型的精明用户

  • 无处不在的安全和隐私需求，操作必须可靠

    Notice：不是桌面计算；不是传统的，事后嵌入式/实时系统；不是今天的传感器网络.

其研究目标是物理和网络（计算，通信，控制）设计深度集成；未来工程和监控物理系统的新学科

CPS是基于实时操作系统开发的，但是由于各种结构可能是异构的，所以要进行融合。

※MDA(模型选择/建模方法)

MDA定义的三种模型—— 逐步求精

  • 计算独立模型（CIM，Computation-Independent Model）——功能需求：描述系统的需求和将在其中使用系统的业务上下文。此模型通常描述系统将用于做什么，而不描述如何实现系统。CIM 通常用业务语言或领域特定语言来表示。
  • 平台独立模型（PIM，Platform-Independent Model）—— 操作系统：描述如何构造系统，而不涉及到用于实现模型的技术。此模型不描述用于为特定平台构建解决方案的机制。PIM 在由特定平台实现时可能是适当的，或者可能适合于多种平台上的实现。
  • 平台特定模型 （PSM，Platform-Specific Model）—— 硬件：从特定平台的角度描述解决方案。其中包括如何实现 CIM 和如何在特定平台上完成该实现的细节。

MARTE与UML的区别？

MARTE(modeling and analysis of real time and embedded systems)是UML在嵌入式实时系统领域的建模规范，取代原有的UML-SPT（UML profile for Schedulability , Performance and Time），支持对嵌入式实时系统的非功能属性建模。弥补了UML在嵌入式实时领域非功能属性表达能力的不足。

实践

实时调度算法

可调度性：表示实时系统（一组实时任务）是否能够按期完成的属性

对于周期任务（p，e），任务周期性的重复。（注意任务的描述符号表示，调度算法部分会用到）
周期 p = inter - release time；p>0
执行时间 e = maximum execution time (0 < e < p)
利用率 U = e/p

响应时间：任务从释放时间到结束时间

RM算法和EDF算法都属于抢占式算法

RM算法(单调速率，Rate Monotonic)

前提假设

  • 所有的任务是相互独立的（它们不相互作用，不相互依赖）
  • 所有任务都是周期的，且运行时间不变
  • 没有任何任务因等待外部事件而阻塞。
  • 所有任务共享一个共同的释放时间（临界时刻，critical instant）
  • 所有的任务的截止时间等于它们的周期，即任务必须在下一个作业释放之前完成。

算法描述

  • 最佳的静态优先级调度
  • 根据周期分配优先权
  • 周期较短的任务具有较高的优先级

  • 以最短的时间执行一项工作

    使用限制：$∑U_i <= n*(2^{(1/n)}-1)$ 满足以上式子时才能用RM算法进行调度

EDF算法（最早截止时间优先，Earliest Deadline First）

算法描述

  • 最佳的动态优先级调度

  • 具有较早截止时间的任务具有较高的优先级

  • 以最早的截止时间执行任务

    注意：当一个任务在执行时，这时有一个新的任务到了，即使优先级更高，当前任务还是会继续执行(类似于磁盘电梯算法)

使用限制：$∑U_i <= 1$

UML(建模工具)

UML (Unified Modeling Language)为面向对象软件设计提供统一的、标准的、可视化的建模语言。适用于描述以用例为驱动，以体系结构为中心的软件设计的全过程。

过程: 分析 -> 设计 -> 实现 -> 测试 -> 分析…

  • 用例图：描述用户所看到的系统的功能行为，用例图从用户的角度来表示系统的功能，用例是系统中的一个功能单元（静态视图）

    录音机用例图

  • 类图：描述系统的静态结构（对象，属性，联系），类图表示系统的结构

  • 序列图：描述系统对象之间的动态行为，序列图将系统的行为表示为不同对象之间的消息交互。当执行一个用例行为时，顺序图中的每条消息对应了一个类操作或引起状态转换的触发事件 。综合考虑用例图中参与者和类图中对象的关系

  • 状态图：描述单个对象的动态行为，一个类对象所可能经历的所有历程的模型图。状态图由对象的各个状态和连接这些状态的转换组成

  • 活动图：状态图的一个变体，用来描述执行算法的工作流程中涉及的活动，活动图描述了一组顺序的或并发的活动

UML的主要特征是支持有限状态机。状态图的两个基本概念是状态和转换。

状态图

​ UML中定义了四种事件：

  • SignalEvent：与信号相关的事件。

​ Signal是一个异步通信的规范，所以SignalEvent是一个与异步接收信号相关的事件。

  • CallEvent：与调用相关联的事件。

​ Call是一个同步通信的规范，所以CallEvent允许一个对象直接调用其中一个方法来影响另一个对象的状态。

  • TimeEvent：与时间流逝相关的事件，通常用tm（\）或after（\）表示。

    几乎所有的TimeEvents都是相对的时间。也就是说，它们指定事件将在对象处于指定状态至少\时间单位后发生。

    如果对象在超时之前离开该状态，则与该持续时间关联的逻辑计时器将消失，而不会创建超时事件

  • ChangeEvent：与属性的值更改关联的事件。

    它很少用在软件应用程序中。然而，当一个状态属性被内存映射到一个硬件上时，它可以用来指示内存地址改变的值

状态的特点：

​ 可以在状态图上捕获行为的对象被认为是被动的。

​ 这样一个对象的行为空间被分解为存在的不相交和不相交的条件，称为状态。

​ 转换是对导致状态改变的事件的响应。该对象可以在接收到事件（尽管不进行转换）或者进行转换时执行动作，进入或退出状态。

转换（transition）

​ 转换是从起始状态开始并在目标状态结束的弧。

​ 转换通常具有命名的事件触发器，可选地随后是执行转换时执行的动作（即可执行语句或操作）。

​ 过渡事件签名的格式为：

​ event-name ‘(‘ parameter-list ‘)’ ‘[‘ guard-expression ‘]’ ‘/‘ action-list

​ 注：事件可以指定形式参数列表，这意味着事件可以携带实际的参数。

​ digit(key: keyType)/ show(key)

​ 约束（Guard）和行为执行顺序（Execution Order）：

​ guard表达式是一个布尔表达式，包含在方括号中，必须计算为true或false。

​ 行动的执行顺序很重要，基本规则是退出->转换->进入（exit-transition-entry）。

​ 也就是说，先行状态的退出动作首先执行，然后是转换动作，随后是后续状态的进入动作。

序列图

含 Alternatives, Branches, Options, and Loops

时间自动机（Timed automata 建模与验证）

​ 时间自动机是实时系统建模与验证的理论。 具有相同目的的其他形式的例子还有时间Petri网（timed Petri Nets），

​ 时间过程代数（timed process algebras）和实时逻辑（real time logics）

​ 公平地说，以时间自动机作为输入语言的核心开发的几种模型检查器是理论应用和发展的动力。

时间自动机本质上是一个用实值变量（时间系统）进行扩展的有限自动机（包含一组有限节点和一组有限带有标记的边的图）

  • 变量（variables）对系统中的逻辑时钟进行建模，在系统启动时用零初始化，然后以相同的速率同步增加
  • 时钟约束（clock constraints），即边上用于限制自动机行为的约束（Guard）
  • 当时钟值满足在边上标记约束（Guard）时，边表示的转换（transition）就可以发生。 当进行转换时，时钟可能被重置为零。

实验

时间自动机工具UPPAAL

  • 同步通信（synchronous）通过使用输入输出行为的握手同步（hand-shake synchronization）来实现
  • 异步通信（asynchronous）使用共享变量（shared variables）来实现

​ 为了对握手同步进行建模，字母 ∑ 定义为包括：输入动作 a？，输出动作a！，内部行为 ‘T’

三次实验内容回顾