Real-Time Embedded Systems
Discrete-event models: part 1 – prerequisites
Dr. Bystrov
School of Engineering Newcastle University
Copyright By PowCoder代写 加微信 powcoder
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Physical processes
Open systems
Reactivity
non-determinism from multiple sources, not controllable or observable by the programmer
causal relations in the environment are hidden. Closed systems
execution non-determinism confined to one source causal relations are easily established
for synthesis – distinguish between input and output events (a degree of “openness”).
Closed Open System System
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Discrete-event systems
Dynamic system
Abrupt occurrence of (physical) events
Possibly irregular time intervals
Time – included or not included
Rates and probability distributions – present or not
Concurrency – present or not
Properties: valid/invalid states, deadlock, liveness, implementability, etc.
Use – refinement of high-level systems
Use – high-level ad-hoc design (controlling agents,
plants, valid and forbidden states and behaviours)
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Before we go further – FSM model
You know what it is – please revisit this topic and find the appropriate reference material (Home Task)
What systems can be implemented with FSMs?
Non-real-time
Control parts (mode selection) Security, etc.
What about concurrency? What is concurrency? The discussion of concurrent models (Petri nets and Reachability Graphs) follows the review of FSM
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Did I mention FSM? – Revision!
Read e.g. Williams, R.: “Real-Time systems Development”, Esevier, 2006
Discrete-event systems
Moore and Mealy types
States, transitions, trigger events and actions Auxiliary variables
Hierarchical State Charts
SW implementation (a separate lecture) – Chapter 6 from R.Williams_2006
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Finite State Diagram
Bare-bone model (logic I/O not included) FSD is a tuple Σ = ⟨S,T,s0⟩
FSD is a directed graph
states S = {s0, …, sk} s0 is the initial state
Transitions T ⊆ (S × S).
Additional components may be introduced:
State labels or encoding
Transitions guards and Auxiliary variables Trigger events and Actions
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Moore and Mealy types
This interpretation is different from the logic synthesis (your examples).
Moore: activities take place either inside the states or on leaving a state
Mealy: activities are evoked on entry to a state Transition
State m event
Entry Trigger action
Exit State n action
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Example of a washing machine
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Traces Context Example
Auxiliary variables
You have seen them in the previous illustration…
In a bare-bone FSM all memories of the past are explicit.
Compression of a diagram by introducing global Aux. variables
Context Equivalence
Think of examples!
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Hierarchical finite state diagrams
It’s Unified Modelling Language (UML), e.g. in Matlab. Weak bisimulation [Milner 1980] and branching bisimulation [van Glabeek 1989] must be preserved when constructing a superstate [Harel 1987].
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
Discrete event systems in general Reactivity
FSM – formal definition, taxonomy FSM + Aux variables
FSM as hierarchical diagrams
Next: concurrency concept and Petri net model
Real-Time Embedded SystemsDiscrete-event models:part 1 – prerequisites
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com