Transcript Document

Some general properties of languages
1. Synchronous vs. asynchronous languages
Description of several processes in many languages nondeterministic:
The order in which executable tasks are executed is not
specified (may affect result).
Synchronous languages: based on automata models.
“Synchronous languages aim at providing high level,
modular constructs, to make the design of such an
automaton easier” [Halbwachs].
Synchronous languages describe concurrently operating
automata... “when automata are composed in parallel, a
transition of the product is made of the "simultaneous"
transitions of all of them“.
Embedded Systems - SDL
-
1
-
Some general properties of languages
1. Synchronous vs. asynchronous languages
Synchronous languages implicitly assume the presence of a
(global) clock. Each clock tick, all inputs are considered,
new outputs and states are calculated and then the
transitions are made.
This requires a broadcast mechanism for all parts of the
model.
Idealistic view of concurrency.
Has the advantage of guaranteeing deterministic behavior.
 StateCharts is a synchronous language.
Embedded Systems - SDL
-
2
-
Some general properties of languages
2. Properties of processes
•
Number of processes
static; dynamic (dynamically changed hardware
architecture?)
• Nested declaration of processes
or all declared at the same level
• Different techniques for process creation
Elaboration in the source code,
explicit fork and join,
process creation calls
 StateCharts comprises a static number of processes,
nested declaration of processes, and process
creation through elaboration in the source code.
Embedded Systems - SDL
-
3
-
Some general properties of languages
3. Communication paradigms
• 1. Message passing:
– Non-blocking communication
Sender does not have to wait until message has
arrived; potential problem: buffer overflow
– Blocking communication, rendez-vous-based
communication
Sender will wait until receiver has received message
– Extended rendez-vous
Explicit acknowledge from receiver required. Receiver
can do checking before sending acknowledgement.
Embedded Systems - SDL
-
4
-
Some general properties of languages
3. Communication paradigms
• 2. Shared memory
Variables accessible to several tasks
– Critical sections = sections at which exclusive access
to some resource r must be guaranteed.
 StateCharts uses shared memory for communication
between processes.
Embedded Systems - SDL
-
5
-
Some general properties of languages
4. Specifying timing
4 types of timing specs required [Burns, 1990]:
• Measure elapsed time
Check, how much time has elapsed since last call
• Means for delaying processes
• Possibility to specify timeouts
We would like to be in a certain state only a certain
maximum amount of time.
• Methods for specifying deadlines
With current languages not available or specified in
separate control file.
 StateCharts comprises a mechanism for specifying
timeouts. Other types of timing specs are not
supported.
Embedded Systems - SDL
-
6
-
Properties of specification languages
5. Using non-standard I/O devices -
Direct access to switches, displays etc;
No protection required; OS can be much faster than for
operating system with protection.
 No support in standard StateCharts.
 No particular OS support anyhow.
Embedded Systems - SDL
-
7
-
Specification and Description Language (SDL)
Language designed for specification of distributed systems.
• Dates back to early 70s,
• Formal semantics defined in the late 80s,
• Defined by ITU (International Telecommunication Union):
Z.100 recommendation in 1980
Updates in 1984, 1988, 1992, 1996 and 1999
Embedded Systems - SDL
-
8
-
SDL
• Designed for distributed applications, based on
asynchronous message passing.
• Provides textual and graphical formats to please all users
(graphical and textual formats).
• Just like StateCharts, it is based on the CFSM model of
computation; each FSM is called a process,
• However, it uses message passing instead of shared
memory for communications,
• SDL supports operations on data.
Embedded Systems - SDL
-
9
-
SDL-representation of FSMs/processes
state
input
output
Embedded Systems - SDL
-
10
-
Operations on data
Variables can be declared locally for processes.
Their type can be predefined or defined in SDL itself.
SDL supports abstract data types (ADTs). Examples:
Embedded Systems - SDL
-
11
-
Communication among SDL-FSMs
Communication between FSMs (or “processes”) is based on
asynchronous message-passing, assuming a potentially
indefinitely large FIFO-queue.
• Each process
fetches next entry
from FIFO,
• checks if input
enables transition,
• if yes: transition
takes place,
• if no: input is ignored
(exception: SAVEmechanism).
Embedded Systems - SDL
-
12
-
Process interaction diagrams
Interaction between processes can be described in process
interaction diagrams (special case of block diagrams).
In addition to processes, these diagrams contain channels
and declarations of local signals.
Example:
,
Embedded Systems - SDL
(channel)
-
13
-
Designation of signal recipients
1. Through process
identifiers:
Example: OFFSPRING
represents identifiers of
processes generated
dynamically.
2. Explicitly:
By including the
channel name.
3. Implicitly:
If signal names imply
channel names (B 
Sw1)
Embedded Systems - SDL
Counter
TO OFFSPRING
Counter
Via Sw1
-
14
-
Hierarchy in SDL
Process interaction diagrams can be included in blocks.
The root block is called system.
Processes cannot contain other
processes, unlike in StateCharts.
Embedded Systems - SDL
-
15
-
Timers
Timers can be declared locally. Elapsed timers put signal
into queue (not necessarily processed immediately).
RESET also removes timer signal from queue.
Embedded Systems - SDL
-
16
-
Additional language elements
SDL includes a number of additional language elements, like
• procedures
• creation and termination of processes
• advanced description of data
Embedded Systems - SDL
-
17
-
Example: vending machine
Machine° selling pretzels, (potato) chips,
cookies, and doughnuts:
accepts nickels, dime, quarters, and halfdollar coins.
Not a distributed application.
° [J.M. Bergé, O. Levia, J. Roullard: High-Level System Modeling, Kluwer
Academic Publishers, 1995]
Embedded Systems - SDL
-
18
-
Overall view of vending machine
Embedded Systems - SDL
-
19
-
Decode
Requests
p
ChipHandler
Embedded Systems - SDL
-
21
-