SIE_02 Modelling of Distributed Real-Time Systems.pdf
Document Details
Uploaded by ForemostHeliotrope2447
Tags
Full Transcript
Modelling of Embedded Real-Time Systems Prof. Dr. Roman Obermaisser 2 Model Construction Focus on the essential properties – eliminate the unnecessary detail (viewpoint important). The eleme...
Modelling of Embedded Real-Time Systems Prof. Dr. Roman Obermaisser 2 Model Construction Focus on the essential properties – eliminate the unnecessary detail (viewpoint important). The elements of the model and the relationships between the elements must be well specified. Understandability of the structure and the functions of the model. Formal notation to describe the properties of the model should be introduced to increase the precision. Model assumptions must be stated explicitly. Embedded Systems Modelling 3 Assumption Coverage Every model/design is based on a set of assumptions about the behavior of the components and the environment. Assumption coverage: The probability that the assumptions cover the real-world scenario. The dependability of a perfect design is limited by the assumption coverage Assumption coverage also limits the utility of formal verification Specification of the assumptions is a system engineering task. Embedded Systems Modelling 4 Load and Fault Hypothesis Two important assumptions that must be contained in the requirements specification: Load Hypothesis: Specification of the peak load that a system must handle. Fault Hypothesis: Specification of the number and types of faults that a fault-tolerant system must tolerate. The fault hypothesis partitions the fault space into two domains: those faults that must be tolerated and those faults that are outside the fault-tolerance mechanisms. Outside Fault Hypothesis: NGU (Never-give-up) Strategy Embedded Systems Modelling 5 Elements of a RT System Model Essential: Representation of Real-Time Semantic Properties of Data Transformations Durations of the executions Unnecessary Detail: Representation of information within a system (this is only important at the interfaces -- specified by architectural style). Detailed characteristics of Data Transformations Time Granularity that is finer than the application requirement Embedded Systems Modelling 6 Structure Overview Real-time System: Computer System + Controlled Object + Operator Cluster: A subsystem of the RT-system with high inner connectivity Node: A hardware software unit of specified functionality Process: The execution of a program within a node Man-Machine Instrumentation Interface Interface Real-Time Controlled Operator Computer Object (Environment System (Environment Cluster) (Computational Cluster) Cluster) Embedded Systems Modelling 7 Process Process is the execution of a program Starting with reading the input data Terminating with the production of the output data Simple (S) Process No synchronization points within a S-Processes S-Processes can have an internal state, i.e., memory between successive activations. Stateless S-Processes are called functional. Complex (C) Process: Processes with at least one internal synchronization point, e.g. a “wait on condition” (P) statement. If we use the word “Process” without further specification, we refer to an S-Process. Embedded Systems Modelling 8 Model of a S-Process: Action h-state compu- Input Output tation Start End Granularity of action: Time Interval between Start and End Embedded Systems Modelling 9 Node A node is a hardware-software unit that consists of: Hardware: CPU, memory, real-time clock, process I/O, communication interface Operating System: CPU Management, I/O support, communication support, error manager i-state(initialization state): static data structure, i.e., application program code, initialization data (can be put into ROM) h-state (history state): dynamic data structure that contains information about the current and past computations (has to be put into RAM) g-state (ground state): minimal h-state when all processes are inactive and all channels are flushed--reintegration point. Embedded Systems Modelling 11 History State (h-state) The h-state comprises all information that is required to start an “empty” node (or process) at a given point in time: Size of the h-state depends on the point in time chosen relative minimum immediately after a computation (an atomic action) has been completed. System in ground state: no messages in transit and no activity occurring. shall be small at reintegration points. If no h-state has to be stored between successive activations of the node, the node is called “stateless” (at the chosen level of abstraction!). Embedded Systems Modelling 12 Size of H-State During an Atomic Action h-state Real-Time Start Termination Embedded Systems Modelling 13 Size of h-state at the End of an Atomic Action Size of h-state The size of the h-state in bits decreases with the increasing granularity of actions! Select a reintegration point with minimal h-state! Granularity of Atomic Action Embedded Systems Modelling 14 Ground State (g-state) Process A Process B active Process C Real Time Process A Process B active Process C Ground State at Real Time Reintegration Point Ground State (g-state): Minimal h-state of a subsystem (node) where all processes are inactive and all channels are flushed. Needed for reintegration of nodes. Embedded Systems Modelling 15 Example of a Cluster I/O Body Electronics Network Driver Assistant Gateway Node Controller Host Interface System Body Interface (CHI) CC CC CC CC CC CC CC Brake Engine Steering Suspen- Manager Control Manager sion I/O I/O I/O I/O CC: Communication Controller Embedded Systems Modelling 17 Interface The interface between two subsystems (cluster, node, etc.) is characterized by Its data properties, i.e., the structure and semantics of the data items crossing the interface Its temporal properties, i.e., the temporal conditions that have to be satisfied by the interface: control and temporal data validity. The functional intent, i.e., the assumptions about the functions of the interfacing partner In a non-real-time computer system, there is little concern about the temporal properties. Embedded Systems Modelling 18 Message Passing and Shared Memory Shared memory prevalent in multi-processor architectures Parallel processing based on multiple threads of control executing at the same time with access to shared data Synchronization mechanisms like semaphores Message-passing with distributed-memory systems provides better scalability Network N N N N N N N N Network Embedded Systems Node Modelling 19 Message Passing in Distributed Real-Time Systems Unidirectional message passing is the basic interaction mechanism among nodes in distributed real-time systems Every message has one sender and one or more receivers (multicasting supported) Messages are used for the exchange of data and can be used for the synchronization Shared memory (e.g., transactional memory) can be realized at a higher level on top of a basic message passing service Message passing facilitates encapsulation and recovery. Embedded Systems Modelling 20 Interfaces of a Node – Messages Diagnostic and management Interface (e.g., boundary scan in HW design) Sporadic access Requires knowledge about internal structure of node No real-time requirements Linking Interface / LIF Local Periodic in control applications Interfaces Real-time observations Application Real-time requirements Software Relevant for composability Configuration Planning Interface Sporadic access Installation of node in new configuration No real-time requirements Embedded Systems Modelling 21 LIF is Important for Composability For the temporal composability, only the LIF interface is relevant. A LIF (e.g., a control algorithm) must specify: At what point in time the input information is delivered to a module (temporal pre-conditions) At what point in time the output information must be produced by the module (temporal post-conditions). The properties of the intended information transformation provided by the module (a proper model) Focus on Message Based Interfaces! Embedded Systems Modelling 22 Local Interfaces versus Linking Interfaces Node with message-based linking interface and local interfaces acts as an information transducer Node hides physical interface of the real-world devices from standardized information representation within a given cluster Viewed from a higher level of abstraction, differences in information representation are of no concern, as long as the semantic contents and temporal properties are maintained across the interface Information representation is relevant at the low level, but not within a properly designed cluster, where an information representation standard is chosen Embedded Systems Modelling 23 Example: Man-Machine Interface Important Incoming Message Input Message Generalized Man-Machine Interface Reaction Message Specific Man-Machine Interface (View, Sound) (concrete World Interface) Embedded Systems Modelling 24 World vs Message Interfaces Local Controlled LIF Interface Node Object Real- Time Bus Local Interface LIF Operator Node Another LIF LIF Computer Node Cluster Embedded Systems Modelling 25 Message Classification Attribute Explanation Antonym valid A message is valid if its checksum and contents are in invalid agreement. checked A message is checked at source (or, in short, checked) not checked if it passes the output assertion. permitted A message is permitted with respect to a receiver if it not permitted passes the input assertion of that receiver. timely A message is timely if it is in agreement with the untimely temporal specification value- A message is value-correct if it is in agreement with not value- correct the value specification correct correct A message is correct if it is both timely and value- incorrect correct. insidious A message is insidious if it is permitted but incorrect not insidious Embedded Systems Modelling 26 The LIF Specification hides the Implementation Node Operating System Middleware Programming Language WCET Scheduling Memory Management Etc. Embedded Systems Modelling 27 Interface Specification Operational Specification Data Domain: Specification of syntactic units contained in a message, e.g., by an IDL. Bridges the gap between the logical level and the information level Temporal Domain: Specify the instants, the rate, the order, the phase relationship between messages Meta-level Specification Assign meaning to the syntactic units generated by the operational specification by referring to a LIF service model. Bridges the gap between the information level and the user level Embedded Systems Modelling 28 Interface Specification (ii) Operational Specification: Operational Input Interface Specification Syntactic Specification Temporal Specification Input Assertion Operational Output Interface Specification Syntactic Specification Temporal Specification Output Assertion Interface State Meta-level Specification: Meaning of the data elements: Means-and-ends model Embedded Systems Modelling 29 Example: Text to Speech Input Interface: Event-triggered acceptance of text according to the client- server paradigm ET interface is composite Output Interface: Time-triggered output of a bit-stream that is encoding the sound. Temporal firewall interface. TT interface is elementary Embedded Systems Modelling 30 Interface State Machine: Text-to-Speech Input compu- Message tation I ET Input Interface state I Interface Compu- tation Interface state II compu- Output tation II Message TT Output Interface Embedded Systems Modelling 32 Property Mismatches at Interfaces Property Example Physical, Electrical Line interface, plugs, … Communication protocol CAN versus Ethernet Syntactic Endianness of data Flow control Implicit or explicit, Information push or pull Incoherence in naming Same name for different entities Data representation Different styles for data representation Different formats for date Temporal Different time bases Inconsistent time-outs Dependability Different failure mode assumptions Semantics Differences in the meaning of the data Embedded Systems Modelling 33 Boundary Line versus Interface System (IS) BL Subsystem Subsystem A B BL BL nz Subsystem Interface Subsystem A System (IS) B Sch Embedded Systems Modelling 34 Elementary vs. Composite Interface Consider a unidirectional data flow between two subsystems (e.g., data flow from sensor node to processing node). We distinguish between: Control Elementary Example: Interface: A B state message Data in a DPRAM Control Composite Queue of Interface: A B event messages Data Elementary interfaces are inherently simpler than composite interfaces Embedded Systems Modelling 35 Information Push vs. Information Pull Information Push Interface: Information producer pushes information on information consumer (e.g., telephone, interrupt) Information Pull Interfaces: Information consumer requests information when required (e.g., email). What is better in real-time systems?--For whom? Embedded Systems Modelling 36 Time-Triggered Architecture Embedded Systems Modelling 37 RT Entities, RT Images and RT Objects Operator Distributed Computer Control Object A R B T L C A C N RT Entity RT Image RT Object A: Measured Value of Flow B: Setpoint for Flow C: Intended Valve Position Embedded Systems Modelling 38 Real Time (RT) Entity A Real-Time (RT) Entity is a state variable of interest for the given purpose that changes its state as a function of real-time. We distinguish between: Continuous RT Entities Discrete RT Entities Examples of RT Entities: Flow in a Pipe (Continuous) Position of a Switch (Discrete) Setpoint selected by an Operator Intended Position of an Actuator Embedded Systems Modelling 39 Attributes of RT-Entities Static attributes of RT-Entity: Name Type Value Domain Maximum Rate of Change Dynamic Attributes: Value set at a particular point in time Embedded Systems Modelling 40 Sphere of Control Every RT-Entity is in the Sphere of Control (SOC) of a subsystem that has the authority to set the value of the RT-entity: Setpoint is in the SOC of the operator Actual Flow is in the SOC of the control object Intended Valve Position is in the SOC of the Computer Outside its SOC a RT-entity can only be observed, but not modified. At this level of abstraction, changes in the representation of a RT-entity are not significant. Embedded Systems Modelling 41 Observation Information about the state of a RT-entity at a particular point in time is captured in an observation. An observation is an atomic triple Observation = consisting of: The name of the RT-entity The point in real-time when the observation has been made The values of the RT-entity Observations are transported in messages. Embedded Systems Modelling 42 Observation of Events A state corresponds to a section of the timeline while an events occurs at the cut of the timeline. Every change of state is an event. An event cannot be observed--only the new state can be observed. Event Occurrence Point of Observation of the Event Occurrence Embedded Systems Modelling 43 State and Event Observation State observation, Value of the observation contains the full or partial state of the RT-entity. The time of a state observation denotes the point in time when the RT-entity was sampled. Event observation Value of the observation contains the difference between the “old state” (the last observed state) and the “new state”. The time of the event information denotes the point in time of the L-event of the “new state”. Embedded Systems Modelling 44 RT Images A RT-Image is a picture of a RT Entity. A RT image is valid at a given point in time, if it is an accurate representation, both in the domains of value and time, of the corresponding RT Entity. RT-Images are only valid during a specified interval of real-time. can be based on an observation or on a state estimation. can be stored in data objects, either inside a computer (RT object) or outside in an actuator. Embedded Systems Modelling 45 RT Object A RT-object is a “container” for a RT-Image or a RT-Entity in the Computer System. A RT-object k has an associated real-time clock which ticks with a granularity tk. This granularity must be in agreement with the dynamics of the RT-entity this object is to represent. Activates an object procedure if the time reaches a preset value. If there is no other way to activate an object procedure than by the periodic clock tick, we call the RT-object a synchronous RT object. Embedded Systems Modelling 46 Distributed RT-Object A distributed RT-object is a set of replicated RT-objects located at different sites. Every local instance of a distributed RT-object provides a specified service to its local site. The quality of service of a distributed RT-object must be in conformance with some specified consistency constraint. Examples: Clock synchronization within a specified precision Membership service with a specified delay Embedded Systems Modelling 47 Temporal Accuracy of Real-Time Information How long is the RT image, based on the observation: RT entity “The traffic light is green” temporally accurate ? RT image in the car Embedded Systems Modelling 49 Temporal Accuracy of RT Objects Value Accuracy Interval RT Entity RT Image Real-Time If a RT-object is updated by observations, then there will always be a delay between the state of the RT entity and that of the RT object Embedded Systems Modelling 50 Point of Ignition The point in time of ignition is a function of the following parameters: Parameter Recent History Accuracy(sec) crank position 10−6 h-state 10−3 gas pedal position 10−2 load 1 temperature 10+1 There are seven orders of magnitude difference in the required temporal accuracy of the parameters. There are five parameter, but only one can serve as control! Embedded Systems Modelling 51 Synchronized Actions Point of Observation Sending Process WCETsend Communication WCCOM Point of Use Receiving Process WCETrec Real-Time Embedded Systems Modelling 52 Parametric Real-Time Image We call a data element parametric (or phase insensitive) if (dupdate +WCETsend+WCCOM+WCETrec) < dacc dupdate is the update interval of the data element. It is assumed that there is no laxity at the sending node. If there is a situation where (WCETsend+WCCOM+WCETrec) < dacc ≤ (dupdate +WCETsend+WCCOM+WCETrec) the data element is called phase sensitive. Embedded Systems Modelling 53 State Estimation A good accuracy of a RT-object can be obtained either by frequent sampling of the RT-entity or by state estimation In state estimation, an estimation of the current state of the RT-entity is periodically calculated within a RT-object based on a computational model of the dynamics of the RT entity. There is often the possibility for a tradeoff between computational and communication resources. Embedded Systems Modelling 54 Timing Requirements for State Estimation A state estimation program needs the time of observation of a RT-entity and the planned time of actuation to be able to compensate for the delay. Quality of state estimation depends on the Precision of the clock synchronization Size of latency and quality of latency measurement Quality of state estimation model Point of Observation Output Action at Node A at Node B Communication and Processing determines required latency Real-Time Embedded Systems Modelling 55 State Estimation of Sensor Observations Node A Start of control Node B algorithm by the control node Node C Real Time Observation of the RT entity Channel access interval Interval used for state estimation Embedded Systems Modelling 56 Latency Guarantee The composability of a distributed TT architecture can be improved, if the sender guarantees the latency between the point of sampling and the point of transmission. Then the receiver can correct this known latency in his state estimation model. Alternatively, the sender can send “timed” messages that contain the interval between observation and transmission observation transmission use Latency at sender Real Time Embedded Systems Modelling 57 Hidden Channel (red) Control Valve Alarm Monitor A MDA C Hidden Channel MBA Comm. System Pressure Sensor Operator B MBC D Vessel Embedded Systems Modelling 58 Hidden Channel (2) 1 Sending of MBC 1 2 hidden channel Sending of MBA 1 5 2 Arrival of MBC 3 4 6 dmax 3 Sending of MDA interval of 4 Arrival of MDA dmin Real Time incorrect alarm 5 Arrival of MBA dmax 6 Permanence of MDA Embedded Systems Modelling 59 Permanence Permanence is a relation between a given message Mi that has arrived at a RT-object O and all messages Mi-1, Mi-2,... that have been sent to this object before (in the temporal order) message Mi. The message Mi becomes permanent at object O as soon as all previously sent messages have arrived at O. If actions are taken on non-permanent messages, then an inconsistent behavior may result. The action delay is the interval between the point in time when a message is sent by the sender and the point in time when the receiver knows that the message is permanent. How long does it take until a message becomes permanent? Embedded Systems Modelling 60 Action Delay In distributed RT systems without a global time base the maximum action delay is 𝑑𝑚𝑎𝑥 + 𝜀 = 2 𝑑𝑚𝑎𝑥 − 𝑑𝑚𝑖𝑛 but the consistent order problem is not yet solved! In systems with a global time the maximum action delay: 𝑑𝑚𝑎𝑥 + 2𝑔 In distributed real time system the maximum protocol execution time and not the “median” protocol execution time determines the responsiveness. Embedded Systems Modelling 61 Accuracy versus Action Delay In a properly designed RT system 𝐴𝑐𝑡𝑖𝑜𝑛 𝐷𝑒𝑙𝑎𝑦 < 𝑑𝑎𝑐𝑐 The accuracy is an application specific parameter, while the action delay is an implementation specific parameter. What happens if this condition is violated? Then we need state estimation! Embedded Systems Modelling 62 Idempotence Idempotence is a relation between a set of messages. A set of messages is idempotent, if the effect of receiving more than one messages of this set is the same as the effect of receiving a single message. Duplicated state messages are idempotent. Duplicated event messages are not idempotent. If the idempotence of a set of redundant messages is given, then the design of fault-tolerant systems is simplified. Embedded Systems Modelling 63 Replica Determinism Replica Determinism is a desired relation between replicated RT objects. A set of replicated RT objects is replica determinate if all objects of this set visit the same state within a specified interval of real time. In a Time-Triggered System, this time interval is determined by the precision of the clock synchronization. Replica determinism is needed for consistent distributed actions the implementation of fault tolerance by active redundancy Embedded Systems Modelling 64 Example: Airplane on Takeoff Consider an airplane with a three channel flight control system taking off from a runway: Kanal 1 Take off Accelerate Engine Kanal 2 Abort Stop Engine Kanal 3 Take off Stop Engine (Fault) Majority Take off Embedded Systems Modelling 65 Why do we need “Replica Determinism”? Replica Determinism is needed for two main reasons: To improve the testability of systems--tests are only reproducible if the replicas are deterministic To facilitate the implementation of fault-tolerance by active replication. Replica Determinism helps to make systems more intelligible! Embedded Systems Modelling 66 What destroys replica determinism? Replica determinism can be destroyed by: Inconsistent inputs Inconsistent order Non-deterministic program constructs Explicit synchronization statements (e.g., Wait) Uncontrolled access to the global time and timeouts Dynamic preemptive scheduling decisions Consistent comparison problem (software diversity) This list is not complete! Embedded Systems Modelling 67 Consistent Comparison Problem Occurs whenever a real valued quantity is mapped into a discrete representation and this representation serves as an input to a binary decision. Examples: Time Sensor Input Different Software versions operating on real numbers in different order (different truncation!) Embedded Systems Modelling 68 Major Decision Point How can we make sure, that both replicas take the same decision at this major decision point? Embedded Systems Modelling 69 Summary and Key Takeaways Model construction and assumption coverage Structure of a distributed real-time system Notion of state and ground state Interfaces (elementary/composite, push/pull, message/shared memory, property mismatches) Message classification Real-time entities, images and objects State and event observations Temporal accuracy Hidden channels, permanence and actional delay Idempotence Replica determinism Embedded Systems Modelling
