Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Embedded Systems > Specification and Modeling > Flashcards

Specification and Modeling Flashcards

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
    ..
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define “Models of Computation”

A

Components + computation + communication

  1. Components and an execution model for computation for each component (dependence graph)
  2. Communication model for exchange of information between components
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Describe the three steps of StateCharts Simulation Phases. Is this determinate behavior?

A
  1. Effect of external changes on events and conditions evaluated
  2. The set of transitions to be made in current step and right hand sides of assignments are computed
  3. Transitions become effective, variables obtain new values

The seperation into phase 2 and 3 enables determinate (unique) behavior

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Specification and Description Language (SDL):

Definition and Representation

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

SDL Communication

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Is SDL determinate?

A

No, if signals arrive in FIFO at same time the store order is unknown -> different behavior for mutliple runs possible

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

SDL: Pros and cons

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

SDL: timers

A
  • can be declared locally
  • elapsed timer put signal into queue
  • reset removes timer (also from FIFO queue)

SEE V2 p.82

30
Q

SDL: Process interaction diagrams

A
  • special case of block diagram
  • in addition to processes these diagrams contain channels and declaration of local signals

SEE V2 p.80

31
Q

SDL: Representation of FSMs /Processes

A
  • 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
Q

Data Flow Modeling - Definition

A

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
Q

Kahn Process Networks (KPN) - Description

A
  • 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
Q

Data Flow Modeling - Examples (3)

A
  • Kahn Process Networks
  • Synchronous Data Flow
  • Visual Programming Languages
35
Q

Kahn Process Networks - Properties

A
  • 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
Q

Are Kahn Process Networks determinate?

A

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
Q

Kahn Process Networks: Pros and Cons

A

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
Q

Synchronous Data Flow (SDF) - Description (opposed to KPN, naming of nodes etc)

A
  • 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
Q

Homogenous vs inhomogenous SDF?

A

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
Q

Analysis of Buffersize for SDF channels?

A

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
Q

Petri Nets: Usecase, Key Elements?

A
  • 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
Q

Petri Nets: When is N=(C,E,F) called a “net”?

A
  1. C and E are disjoint sets

2. F aus (C x E) u (E x C) is a binary relation (“flow relation”)

43
Q

Petri Nets: When is a net called “pure”?

A

If in the net N = (C,E,F) -> F does not contain any loops

44
Q

Petri Nets: Pre- and Post-Sets?

A

*x is called pre-set of x –> all preconditions leading to x

x* is called post-set of x –> all postconditions after x

45
Q

Petri Nets: When is a net called “simple”?

A

If no two nodes n1 and n2 have the same pre-set and post-set (examples V2 p124)

46
Q

Petri Nets: What are so called “condition/event nets (C/E nets)”?

A

SIMPLE nets with no isolated elements (fully connected graph) meeting some additional restrictions

47
Q

Place/Transition Nets: Definition and (P, T, F, K, W, M0)

A

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
Q

Petri Nets: Determinate?

A

No, the order in which transitions fire is not fixed. Also activated transitions CAN take place or fire but do not have to

49
Q

What are diophantic Equations?

A

Equations with multiple unknowns that must be integers

ILP: integer linear programming - optimization for ie. compiler

50
Q

Name three application areas where petri-nets are used

A
  • 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
Q

Predicate/Transition Nets: Goal and differences to Petri- and C/E-Nets

A

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
Q

Petri-Nets: Pros (3) and Cons (3)

A

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
Q

Discrete Event Models: Semantics (of Basic Discrete Event)

A
  • 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
Q

Discrete Event Models: VHDL meaning

A

Very High Speed Integrated Circuit Hardware Description Language, short: VHDL

55
Q

VHDL: Semantics of Simulation

A
  • 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
Q

VHDL: What is a “Delta Cycle”? Drawbacks?

A

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
Q

VHDL: When are Delta Cycles used?

A
  • 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
Q

VHDL: Determinate?

A
  1. Compute future values
  2. Assign values
    Seperation in two phases (like StateMate Semantics) results in determinate semantics.
59
Q

VHDL: Abstraction of Electrical signals?

A

Distinction between:

  1. the logic level (abstraction of voltage) and
  2. the strength (abstraction of the current drive capability)
60
Q

VHDL: Signal strength meaning

A
  • logic values ‘0’ and ‘1’
  • both same strength
  • encoding binary ‘false’ and ‘true’
61
Q

VHDL: Open Collector? Tri-State Buffer?

A

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
Q

VHDL: signal strength - ‘Z’ and ‘X’?

A

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
Q

VHDL: depletion transistor, what and why?

A
  • 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
Q

VHDL: IEEE 1164? How many signal types and use?

A
  • 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
Q

Imperative Model of Computation: Key features of Von-Neumann Model, Problem for Embedded Design?

A
  • 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
Q

What is a semaphore?

A
  • Used when multiple threads use a shared variable, lines of code can be executed in an atomic fashion (no interrupts) –> mutual exclusion
67
Q

What are the four conditions for a deadlock to happen?

A
  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
Q

Problems with Imperative Languages and Shared Memory

A
  • 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
Q

Communicating Sequential Processes (CSP language), What and how? Name a programming language.

A
  • synchronous message passing between two processes (rendevouz-based communication)
  • no race conditions!

Language: ADA (inherently parallelism)

70
Q

Java: benefits (3) and problems (6)?

A

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

Embedded Systems (7 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions