1
Q
Definition: Model
When is a model minimal?
A
- A model is a simplification of another entity, which can be a physical thing or another model.
- The model contains exactly those characteristics and properties of the modeled entity that are relevant for the task
- a model is called minimal with respect to a task if it does not contain any characteristics which are irrelevant for the task
2
Q
Requ. for Models: Hierachy
A
- Hierachy is a form of abstraction
- Behavioral hierachy: States, processes, procedures
- Structural hierachy: processors, printed circuit boards, racks
3
Q
Requ. for Models: Component-Based Design
A
- System must be designed from components
- behavior must be easy to derive from behavior of subsystems
- concurreny
- synchronization and communication
4
Q
Req. for Models: Timing (examples)
A
- speed of underlying HW platform must be known
- timing behavior (periods, dependences, scenarios)
- Types of timing: elapsed time, delays, timouts, deadlines
5
Q
Req. for Models: Support for reactive Systems
A
- State-oriented behavior (classic automata insufficient)
- event handling (external or internal events)
- exception-oriented behavior (it is not acceptable to describe exception for every state)
6
Q
Name 5-10 Requirements for Models
A
- Presence of programming elements
- Executability (no algebraic specification)
- Support for the design of large systems (object orientated)
- Domain-specific support
- readability
- Portability and flexibility
- Termination
- Support for non-standard I/O devices
- non-functional properties
- Support for the design of dependable systems
..
7
Q
Define “Models of Computation”
A
Components + computation + communication
- Components and an execution model for computation for each component (dependence graph)
- Communication model for exchange of information between components
8
Q
What can/should be contained in a dependance graph?
A
- Nodes (Programms/operations) represented as circles
- Sequence arrows (constraints, conditions)
- timing information (arrival time, deadline i.e. (1,7] )
- I/O information (Kreis mit Punkt in der Mitte als Input)
- shared ressources (i.e. memory)
- periodic schedules (periodic dependance graphs are infinite)
- hierachical Task Graphs (Box around Tasks)
9
Q
Communication Models (examples (pro, cons?))
A
- shared memory
pro: accessable to several components/task
con: model mostly restricted to local systems - Non-blocking/asynchronous message passing
pro: sender does not have to wait until mssge passed
con: buffer overflow may occur - Blocking/Synchronous message passing
- > Sender will wait until receiver has received mssge
pro: no buffer overflow
con: reduced performance
10
Q
Organization of Computation (examples)
A
- finite states machines
- discrete event model
- von Neumann model (sequential execution, program memory etc.)
- differential equations
- data flow (models the flow of data in distribut. system)
- petri nets (models synchronization in distribut. system
11
Q
Name and explain three early design phase modeling approaches.
A
- Plain text:
describing the system under design (SUD)in natural language (english/japanese) - Use cases:
description of possible applications of the SUD; includes in UML (unified modeling language).
This can be created from different points of few (User/Caller/Admin) - Sequence Charts:
explicitly indicates exchange of information (arrows left/right); usually the vertical dimension reflects time, other dim. reflects distribution in space; describes just one case (without timing tolerance)
12
Q
Moore/Mealy automata: Output and Stateequation? For the same programm, does a Moore or a Mealy Machine need more states?
A
Input X, Output Y, internal State Z, next State Z*
Moore: Y=f(Z) and Z=f(X, Z)
Mealy: Y=f(X, Z) and Z=f(X, Z)
Moore and Mealy automata are finite state machines (FSMs). Both are capable of achieving the same programms, whereas Moore (“more”) needs generally more states than a Mealy machine.
13
Q
What is stateCharts and why use it instead of Moore/Mealy
A
StateCharts is a better way of describing communication in finite state machines using hierachy. Moore/Mealy are not useful for complex systems.
14
Q
StateChart Definitions:
- active states
- basic states
- super-states
- OR-super-states
A
- Current states of the FSMs are called active states.
- States which are not composed of other states are
called basic states. - States containing other states are calles super-states
- Super-states S are call OR-super-states if exactly one
of the substates of S is active when ever S is active
15
Q
StateCharts:
- default State
- history mechanism
A
- The default state is no state by itself, only indicating
which substate is entered when entering superstate (filled dot) - History mechanism allows to enter the superstate at the substate it was when left last
- if entered first time the default state mechansim applies
16
Q
How is concurrency realised in StateCharts?
A
- AND-super-states (FSM is in all immediate sub-states of a super state)
- dashed line in super-state box
- when leaving superstate all concurrent states are left
17
Q
StateCharts: Timer
A
timers can be realised by a box with some “zigzag” on top. In this box the amount of waitingtime is specified.
From the timer state more than on arrow can continue depending on the things happening during timer (i.e. timout, lift off phone, closed door etc.)
18
Q
StateCharts: Edge Labels
A
from one state to another the edges are labeled:
event [condition] / reaction
Events: exist only until next evaluation of model (internal or external)
Conditions: refer to values of variables
Reactions: assignment of variable or creation of event
Example: service-off [not in Lproc] / service :=0
19
Q
Describe the three steps of StateCharts Simulation Phases. Is this determinate behavior?
A
- Effect of external changes on events and conditions evaluated
- The set of transitions to be made in current step and right hand sides of assignments are computed
- Transitions become effective, variables obtain new values
The seperation into phase 2 and 3 enables determinate (unique) behavior
20
Q
StateCharts: What is meant by “Broadcast Mechanism”?
A
Values of variables are visible to all parts of the StateChart model!
.. new variables become effective after phase 3 of current step and are obtained by all parts of the model in the next step
21
Q
StateCharts models consist of a sequence of status and step pairs. What is happening in each of them?
A
Status: Values of all variable + set of events + current time
Step: Execution of three phases
22
Q
Name an application where StateCharts is appropriate and not appropriate to use
A
Appropriate: local control systems
Not appropriate: applications for which updating variables take some time
23
Q
Definition: “Determinate System”
A
(Kahn 1974) calls a system determinate if we will always obtain the same result for a fixed set (and timing) of inputs
24
Q
StateCharts: Pros and cons
A
Pros:
- Hierachy allows arbitrary nesting of AND- and OR-super-states
- (StateMate-) Semantics defined in a follow-up paper to original paper
- larger number of commercial simulation tools available
- available “back-ends” translate StateCharts into software or hardwar language, thus enabling their implementation
Cons:
- not useful for distributed applications
- no program constructs
- no description of non-functional behavior
- no object-orientation
- no description of structural hierachy
- generated programs may be inefficient
25
Specification and Description Language (SDL):
| Definition and Representation
- model of computation based on asynchronous message passing communication ( -> appropriate for distributed systems)
- based on Finite State Machines, each FSM is called a process
- provides textual and graphical formats to please all users
26
SDL Communication
- based on message passing of signals (potentially indefinitely large FIFO queue
- each process fetches next signal from FIFO
- checks if signal enables transition (if yes transition otherwise signal ignorred)
27
Is SDL determinate?
No, if signals arrive in FIFO at same time the store order is unknown -> different behavior for mutliple runs possible
28
SDL: Pros and cons
Pros:
- excellent for distributed systems
- commercial tools available
Cons:
- implementation requires bound for maximum length of FIFO -> difficult to compute
- not necessarily determinate
- timer concept adequate just for soft deadlines
- limited way of using hierachies
- limited programming language support
- no description of non-functional properties
29
SDL: timers
- can be declared locally
- elapsed timer put signal into queue
- reset removes timer (also from FIFO queue)
SEE V2 p.82
30
SDL: Process interaction diagrams
- special case of block diagram
- in addition to processes these diagrams contain channels and declaration of local signals
SEE V2 p.80
31
SDL: Representation of FSMs /Processes
- box with all states in one horizontal line
- moving down one line all inputs are listed
- moving down one line all outputs are listed
- moving down to the last line the next states are listed
SEE V2 p.76
32
Data Flow Modeling - Definition
Data flow modeling is ... "the process of identifying, modeling and documenting how data moves around in an information system. Data flow modeling examines:
- processes (activities that transform data from one form to antoher)
- data stores (holding areas for data)
- external entities (inputs/outputs to system)
- data flows (routes by which data can flow). " - Wikipedia
33
Kahn Process Networks (KPN) - Description
- each component is modeled as program/task/process (underlying FSM is inconvenient)
- Communication is by FIFOs: no overflow considered
- only one sender and one receiver (no conflicts like in SDL)
34
Data Flow Modeling - Examples (3)
- Kahn Process Networks
- Synchronous Data Flow
- Visual Programming Languages
35
Kahn Process Networks - Properties
- Communication is only via channels (no shared/global variables), every channel has own FIFO
- mapping of one ore more inputs to one ore more outputs possible (arbitrary numbers)
- channels transmit information (in unpredictable time)
- in general execution time uknown
- asynchronous message passing
36
Are Kahn Process Networks determinate?
Processes have to commit to wait fore data from a particular port and it is not possible to check for available data before reading!
So yes, as the order of reads from the FIFO does not depend on arrival time (but may depend on data) it is therefore determinate
37
Kahn Process Networks: Pros and Cons
Pros:
- KPNs are Turing-complete (anything which can be computed can be computed by a KPN)
- computationally powerful
Cons:
- difficult to analyze (i.e. what is maximum buffer size)
- number of processes is static
38
Synchronous Data Flow (SDF) - Description (opposed to KPN, naming of nodes etc)
- in correlation to KPNs less computational powerful but easier to analyze
- SYNCHRONOUS global clock controlling "firing" of nodes
- again using asynchronous message passing
- nodes are called "actors" and are "ready" if the necessary number of input tokens exist and enough buffer at the output
39
Homogenous vs inhomogenous SDF?
edges have only one (in/output-)token -> homogenous; but can have more than one (inhomogenous), then also buffersize matters more (node can only fire if input and output are possible)
40
Analysis of Buffersize for SDF channels?
In every channel the rate of produced tokens (per iteration) and the consumed tokens (per iteration) should be the same. Tools can be used for buffer memory and deadlock.
41
Petri Nets: Usecase, Key Elements?
- CAUSAL dependencies (what happens if that state does that and another thing does this...)
- no synchronization assumed ( just message passing )
Key Elements: Conditions, Events, Flow Relation (relates cond. and events)
-> it is only allowed to connect cond. with events or an event with cond. (not: cond. -> cond.)
42
Petri Nets: When is N=(C,E,F) called a "net"?
1. C and E are disjoint sets
| 2. F aus (C x E) u (E x C) is a binary relation ("flow relation")
43
Petri Nets: When is a net called "pure"?
If in the net N = (C,E,F) -> F does not contain any loops
44
Petri Nets: Pre- and Post-Sets?
*x is called pre-set of x --> all preconditions leading to x
x* is called post-set of x --> all postconditions after x
45
Petri Nets: When is a net called "simple"?
If no two nodes n1 and n2 have the same pre-set and post-set (examples V2 p124)
46
Petri Nets: What are so called "condition/event nets (C/E nets)"?
SIMPLE nets with no isolated elements (fully connected graph) meeting some additional restrictions
47
Place/Transition Nets: Definition and (P, T, F, K, W, M0)
A six tupel petri net, it is called a place/transition net if:
P = places
T = transitions
K = capacity of place (default: omega (w) equals infinite)
W = weight of graph edges (default: W=1) -> "consumed /produced tokens"
M0 = initial marking of places
48
Petri Nets: Determinate?
No, the order in which transitions fire is not fixed. Also activated transitions CAN take place or fire but do not have to
49
What are diophantic Equations?
Equations with multiple unknowns that must be integers
| ILP: integer linear programming - optimization for ie. compiler
50
Name three application areas where petri-nets are used
- Modeling of resources (ie. how many trains are there?)
- Modeling of mutual exclusion (ie. only one train can be on track)
- Modeling of synchronization
51
Predicate/Transition Nets: Goal and differences to Petri- and C/E-Nets
Goal: Compact representation of complex systems
Key changes:
- tokens become individuals
- transitions are enabled if function at incoming edges true
- individuals generated by firing transitions defindes through functions
52
Petri-Nets: Pros (3) and Cons (3)
Pros:
- appropriate for distribted applications
- well-known theory for formally proving properties
- initially bizarre, now relevant as distributed applications increase in number
Cons:
- problems with modeling timing
- no programming elements
- no hierachy
53
Discrete Event Models: Semantics (of Basic Discrete Event)
- Queue for future actions, sorted by time
- Repeat: Fetch next entry from queue -> perform function as listed in entry (may also include generation of entries)
- repeats until termination criterion fullfilled
54
Discrete Event Models: VHDL meaning
Very High Speed Integrated Circuit Hardware Description Language, short: VHDL
55
VHDL: Semantics of Simulation
- global clock dictates procedure
1. initialization of variables and start of simulation
2. assign new values to signals (Tc - current time)
- > activate all processes sensitive to signal changes
3. evaluate processes
- > future values for signal drivers (Tn - next time)
START AGAIN WITH 2. (loop until end of simulation time)
56
VHDL: What is a "Delta Cycle"? Drawbacks?
Happens if Tn = Tc (Current time = next time).
Delta Cycle is a single assignment without an explicit timing which takes an infinite small delay therefore executed infinite time between two time steps.
-> simulation might never terminate (global clock does not advance), dangerous to work w/o delay
57
VHDL: When are Delta Cycles used?
- when the delay is not known for the hardware which will be used in the end AND
- can be used if there is a "steady state" / the hardware goes passive (for example an RS Flip-Flop)
58
VHDL: Determinate?
1. Compute future values
2. Assign values
Seperation in two phases (like StateMate Semantics) results in determinate semantics.
59
VHDL: Abstraction of Electrical signals?
Distinction between:
1. the logic level (abstraction of voltage) and
2. the strength (abstraction of the current drive capability)
60
VHDL: Signal strength meaning
- logic values '0' and '1'
- both same strength
- encoding binary 'false' and 'true'
61
VHDL: Open Collector? Tri-State Buffer?
Open Collector: Transistor, getting the input at the Gate. The output is connected to the Drain and if Input is '0', the Output is not connected by transistor
Tri-State: acts like switch for hardware at shared bus
Either Output is connected to VDD or to GRD (2 Transistors)
(Abbildungen: V2 p. 163)
62
VHDL: signal strength - 'Z' and 'X'?
this signal denotes to "high impedance"
-> if signal carrying 'Z' is connected with some other signal, always the other signal dominates
'X' is an electrical short (not wanted, highest "strength")
'0' and '1' are between 'X' and 'Z' in signal strength
63
VHDL: depletion transistor, what and why?
- depletion transistor is always conductive, Gate and Source are connected
- as there is some voltage drop across the transistor the signal strength can be lowered just a bit
- resulting in a weak '1' ('H') and weak '0' ('L') for further signal strength abstraction
- from strongest to weakest: ('X' --> '0' and '1' --> 'W' --> 'L' and 'H' --> 'Z'
64
VHDL: IEEE 1164? How many signal types and use?
- in theory all value sets for signals can be used in VHDL --> unpractical
- standard set values of 9 signal types
- {'0' , '1' , 'Z', 'X', 'H', 'L', 'W', 'U', '-'}
- 'U' - uninitialized
- '-' input does not care
65
Imperative Model of Computation: Key features of Von-Neumann Model, Problem for Embedded Design?
- sequential execution of instructions
- possible branches / jumps
Problem: Parallelism and Concurrency not accounted for in the Von-Neumann Model in the first place (but possible to implement)
66
What is a semaphore?
- Used when multiple threads use a shared variable, lines of code can be executed in an atomic fashion (no interrupts) --> mutual exclusion
67
What are the four conditions for a deadlock to happen?
1. Mutual Exclusion
(shared ressource only accessible by 1 thread at a time)
2. Hold and wait
(Thread already holding ressources may request ressources (ie. WLAN, data, USB etc..))
3. No preemption
(Ressource cannot be forcibly removed from threads, they can be released only by holding thread)
4. Circular wait
(key criteria - one process wait for a ressource that the next thread in the chain holds)
68
Problems with Imperative Languages and Shared Memory
- specification of total order is an over-specification (partial order sufficient)
- Preemptions at any time complicate timing analysis
- Access to shared memory leads to anomalies that have to be pruned away by mutexes, semaphores
- potential deadlocks
- Access to shared, protected ressources leads to priority inversion (Chapter 4)
- Undecideable to reason about termination (endless loop?)
- timing can not be specified, guarantees are difficult to give
69
Communicating Sequential Processes (CSP language), What and how? Name a programming language.
- synchronous message passing between two processes (rendevouz-based communication)
- no race conditions!
Language: ADA (inherently parallelism)
70
Java: benefits (3) and problems (6)?
Benefits:
- clean and safe language
- support multi-threading
- platform independent
Problems:
- Size of Java run-time libraries -> memory requ.
- Access to special hardware features
- garbage collection time
- non-deterministic dispatcher (multi-threading)
- performance problems
- checking for real-time constraints
