Behavioral Design

Topics in Behavioral Design

Based on Material in [Rosenblum94][Budgen94] [Ghezzi91] [Harel88]

Software Design (Behavioral) © SERG

 Behavioral Design Topics
• State Transition Diagrams
• Petri Nets
• Higraphs and Statecharts

Software Design (Behavioral) © SERG

State Transition Diagrams

Software Design (Behavioral) © SERG

State Transition Diagrams (STD)
• Systems exist in a finite set of possible
states. External events are triggers that lead
to transitions between the states.
• Since most systems have many states, a
partial model of the system may be a good
compromise.
• STDs are the cornerstone of more powerful
diagrams for specifying system behavior,
such as Petri Nets and State Charts.
Software Design (Behavioral) © SERG
 Partial Unix vi STD
o
i
l
Command Text
Mode Insertion
Mode
ZZ ESC
return
:
/

Line
Command

Software Design (Behavioral) © SERG

Formal Definition of an STD
STD = (Q, , q0 ,  , F ), where :
Q is a set of states
 is an input alphabet
q0  Q is the start state
 is a transitio n function
 :Q   Q
F  Q is the set of final states
Software Design (Behavioral) © SERG
 Combination Safe STD

1L 3R 2L Safe
Safe Locked 1/3 Unlocked 2/3 Unlocked
Unlocked

any other dial

any other dial
any other dial movement
movement
movement

Sound Alarm

Software Design (Behavioral) © SERG

 stop
Compiling run IDE STD
Compiled
error events

Start
stop
success finished
stop

pause
Running Pausing
resume

hiccup events
no events events

Executing

Software Design (Behavioral) © SERG

 Petri Nets

Software Design (Behavioral) © SERG

 A Simple Petri Net
P1 t1 P2 t2

t3 P3 P4

Software Design (Behavioral) © SERG

 A Marked Petri Net
P1 t1 P2 t2

t3 P3 P4

Software Design (Behavioral) © SERG

 A Marked Petri Net
After Firing t1
P1 t1 P2 t2

t3 P3 P4

Software Design (Behavioral) © SERG

 Definition of a Petri Net
• PNet = (P, T, A, M0)
– P is a finite set of places (labeled circles),
where a place holds tokens.
– T is a finite set of transitions (bars), where a
transition represents an activity.
– A is a finite set of directed arcs, where an arc
connects a place and a transition.
– M0 is the initial marking of PNet, where a
marking is an arrangement of tokens in places
representing state.
Software Design (Behavioral) © SERG
 Petri Net Execution Model
• Input Place: Place P is an input place for
transition T if there is an arc from P to T.
• Output Place: Place P is an output place
for transition T if there is an arc from T to P.
• Enabled Transition: A transition is
enabled if there is at least one token at each
of its input places.

Software Design (Behavioral) © SERG

 Petri Net
Execution Model (Cont’d)
• Firing a Transition: An enabled transition
is non deterministically selected and fired
by removing one token from each of its
input places and depositing one token at
each of its output places.
• Firing Sequence: A firing sequence
<t0,t1, …, tn> such that t0 is enabled and
fired in M0, t1 is enabled and fired in M1, ...

Software Design (Behavioral) © SERG

Petri Net Firing

Software Design (Behavioral) © SERG

 A Petri Net Describing an ATM
Valid Card
Machine Card
Ready Accepted
Notes in
Dispenser
Valid
Request
Correct
Pin

Sufficient
Funds

Card in
Slot
Sufficient
ATM Cash

Software Design (Behavioral) © SERG

 A Marked Petri Net Semaphore
IN1 IN2

IN = Input of Process
OUT = Output of Process
CR = Critical Region
SEM = Semaphore

CR1 SEM CR2

OUT1 OUT2

Software Design (Behavioral) © SERG

 Enabled Transitions
IN1 IN2

CR1 SEM CR2

OUT1 OUT2

Software Design (Behavioral) © SERG

After Non-Deterministic Firing
IN1 IN2

CR1 SEM CR2

OUT1 OUT2

Software Design (Behavioral) © SERG

 Enabled Transition
IN1 IN2

CR1 SEM CR2

OUT1 OUT2

Software Design (Behavioral) © SERG

 After Firing
IN1 IN2

CR1 SEM CR2

OUT1 OUT2

Software Design (Behavioral) © SERG

 Petri Net Static Analysis
• Invariants are properties of a Petri net that
hold (are true) in all markings.
• For example, the sum of all tokens in CR1,
CR2, and SEM are equal to 1 in all
reachable markings. That is,
|CR1| + |CR2| + |SEM| = 1

Software Design (Behavioral) © SERG

 Deadlock and Starvation
• A Petri Net with a given marking is in
deadlock iff no transition is enabled in that
marking.
• A Petri Net with a given marking is in
starvation iff one or more transitions have
been permanently disabled.
• A Petri Net is live if every transition can
eventually be fired.

Software Design (Behavioral) © SERG

A Deadlocked Petri Net

Software Design (Behavioral) © SERG

A Petri Net that can Enter a
Deadlocked State

Software Design (Behavioral) © SERG

A Deadlocked Petri Net

Software Design (Behavioral) © SERG

Modification into a
Live Petri Net

Software Design (Behavioral) © SERG

 A Petri Net that
can go into Starvation

t1 t2

t3 t4

Software Design (Behavioral) © SERG

Starving Transitions t2 and t4

t1 t2

t3 t4

Software Design (Behavioral) © SERG

 Shortcoming of Basic Petri Nets
• The Simplicity of building blocks leads to
complexity in nets.
• For example, a semaphore of N processes
requires 2N transitions and 3N+1 places.
• Would like:
– Enable and fire as computations.
– Tokens as data, not just control.
– Ability to reduce high-level Petri nets to basic
Petri nets for analysis.
Software Design (Behavioral) © SERG
Higher-Level Net Semaphore
19
p
71

s
s > 0
transition s-1
predicate p token
value
3

p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 Enabled Transition
19
p
71

s
s > 0
transition s-1
predicate p token
value
3

p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 After Firing
19
p
s
s > 0
transition s-1
predicate p token
value
71 2

p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 Enabled Transitions
19
p
s
s > 0
transition s-1
predicate p token
value
71 2

p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 After Firing
p
s
s > 0
transition s-1
predicate p token
value
19
1
71
p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 Enabled Transition
p
s
s > 0
transition s-1
predicate p token
value
19
1
71
p s
arc
true s+1 expression
p

Software Design (Behavioral) © SERG

 After Firing
p
s
s > 0
transition s-1
predicate p token
value
2
71
p s
arc
true s+1 expression
19 p

Software Design (Behavioral) © SERG

 A Software Change Process
New MRs Approved MRs
19 33
true
7 8 (MR)
11 (Developer)

(MR) (MR, Developer)

(Developer) Olga
Tom Tony
true Maria
(MR,
Developer) (MR, (MR,
Developer) Developer)
true
Assigned MRs Completed MRs
Software Design (Behavioral) © SERG
After Firing (New Assigned MR)
New MRs Approved MRs
19 33
true
8 (MR)
11 (Developer)

(MR) (MR, Developer)

(Developer) Olga
Tony
true Maria
(MR,
Developer) (MR, (MR,
Developer) Developer)
7,Tom true
Assigned MRs Completed MRs
Software Design (Behavioral) © SERG
After Firing (New Assigned MR)
New MRs Approved MRs
19 33
true
(MR)
11 (Developer)

(MR) (MR, Developer)

(Developer)
Tony
true Maria
(MR,
Developer) (MR, (MR,
8,Olga Developer)
Developer)
7,Tom true
Assigned MRs Completed MRs
Software Design (Behavioral) © SERG
 After Firing
(New Completed MR)
New MRs Approved MRs
19 33
true
(MR)
11 (Developer)

(MR) (MR, Developer)

(Developer)
Tony
true Maria
(MR,
Developer) (MR, (MR,
Developer) Developer)
7,Tom true 8,Olga

Assigned MRs Completed MRs

Software Design (Behavioral) © SERG
 After Firing (New Assigned MR)
New MRs Approved MRs
19 33
true
(MR)
(Developer)

(MR) (MR, Developer)

(Developer)

true Maria
(MR,
Developer) (MR, (MR,
11,Tony Developer)
Developer)
7,Tom true 8,Olga

Assigned MRs Completed MRs

Software Design (Behavioral) © SERG
After Firing (New Approved MR)
New MRs Approved MRs
19 33
true 8
(MR)
(Developer)

(MR) (MR, Developer)

(Developer) Olga

true Maria
(MR,
Developer) (MR, (MR,
11,Tony Developer)
Developer)
7,Tom true
Assigned MRs Completed MRs
Software Design (Behavioral) © SERG
Higraphs and Statecharts

Software Design (Behavioral) © SERG

 Higraphs
• Higraphs are based on:
– Euler graphs
– hypergraphs
– Venn diagrams
Graph Hypergraph

Q Q^R R
P^Q^R

P^Q P^R

Software Design (Behavioral) © SERG

 Higraphs Supports
Cartesian Products.
A
B
D

C F
G

J H
P
K I
O Q
S
L
T R N
M

E
Software Design (Behavioral) © SERG
Formal Definition of a Higraph
H = (B, , , E), where

B is a finite set of elements (blobs)

 is the sub - blob function  : B  2 B

 is the partitioni ng function

 : B  2 BB
BB
(2 = 2  ...  2 )
B B

E is the set of edges E  B  B

Software Design (Behavioral) © SERG
 Specialized Higraphs:
State Charts
• State Charts are a higraph-based extension
of standard state-transition diagrams, where
blobs represent states and arrows represent
transitions.
• State Charts = state diagrams + depth +
orthogonality + broadcast communication

Software Design (Behavioral) © SERG

 Depth of State Charts
• e, f, g, h: events that
D
trigger the transitions
A A •g(c): is the transition by
e e
event g when condition c
f is true.
g(c) f •Being in state D means
g(c) B B being in one of states A
f or C.
h
•The f arrow leaving D
h
C C applies to both A and C.
•A is the default state.
•C is the default state
when in D.
Software Design (Behavioral) © SERG
 Orthogonality of State Charts
Y k
B,F h
A D
B E k B,E g B,G
e
f e
e [in{G}] g h F e f
g
C,E C,G
C G e m k h
n C,F e p e
n p
e I
H H p
I

Software Design (Behavioral) © SERG

Broadcasting of State Charts
Y
A D
k
B E

e f/g F
n g

C G e

H m/e
I J
n/f

Software Design (Behavioral) © SERG

 State Chart Describing ATC
in flight
take off
cruising on ground

parked
stacked

landing taxiing
approach

touch down
Software Design (Behavioral) © SERG
 State Chart Describing a
Computer
Computer
CPU Main Memory

Fetching
Instruction Waiting
for Request
instr. instr.
cmpl. avail. Put
Addr. Data Data Get
Written Read Addr.
Execution
Instruction
Memory Memory
Write Cycle Read Cycle
getAddr putAddr
Software Design (Behavioral) © SERG
Display State of Digital Watch
displays
update
date
hour min b
c d
c d
c
sec c time
date c a
a
a alarm
stopwatch
b c
up-alarm
c
hour sec
2-min min
[not in(stopwatch)] c c

Software Design (Behavioral) © SERG

Stopwatch State of Digital Watch
time
a

stopwatch
d zero
[in(off)]
b b
disp run

reg on
d
d b b
[in(on)]

lap off

Software Design (Behavioral) © SERG

High-Level Description of
Digital Watch
dead

alive
main power

displays weak strong

bt-weak
light
b

on off
b-up
alarm-state
beep-rt t-hits-tm d[in(alarm)]
[in(enable)]
beep enable disable
d[in(alarm)]

Software Design (Behavioral) © SERG

State Chart of Digital Watch
dead bat-rn
bat-in
alive
main
2-min power
[not in(stopwatch)]
displays

update weak strong

date
hour min b
c d bt-weak
c
c d
sec
c time light
date
c b
a

on off
stopwatch
zero a alarm
d
b b b c b-up
disp run
reg on up-alarm
d d b b hour c sec
alarm-state d[in(alarm)]
lap off
c min c
enable disable
t-hits-tm
beep-rt beep
[in(enable)] d[in(alarm)]

Software Design (Behavioral) © SERG

 References
• [Rosenblum94] D. Rosenblum, A. L. Wolf, Formal
Software Engineering, Tutorial SIGSOFT’94 FSE, New
Orleans, Dec., 1994.
• [Budgen94] D. Budgen, Software Design, Addison-
Wesley, 1994.
• [Ghezzi91] C. Ghezzi, M. Jazayeri, D. Mandrioli,
Fundamentals of Software Engineering, Prentice-Hall,
1991.
• [Harel88] D. Harel, On Visual Formalisms, CACM, Vol.
31, No. 5, 1988.

Software Design (Behavioral) © SERG