RE: SDL-News: sub-state machine and persistent state


Subject: RE: SDL-News: sub-state machine and persistent state
From: Scott Shen (Scott.Shen#holleycomm.com)
Date: Thu Feb 13 2003 - 23:38:10 GMT


Hi Rick, Eckhardt, John, Giridhar, Frend Patrick:

Thank you all for your helps. I am so happy that we have a strong and
enthusiastic SDL community.

We have discussed some possible resolutions and I still have questions:

1. resolution ##1. A procedure is NOT a sub-state "machine". you should model
this with SDL services instead of procedures. That would allow you to have a
set of behavioral descriptions that remembers their state.

question: It looks service can address most of my needs except the "disjoint
sets of signals" constraint, but I think it can be worked around in my case.
However, since service is deleted in SDL2000 and replaced by aggregate
composite state, is it difficult to convert my SDL-92 services into SDL-2000
aggregate composite state in the future? There is no way we can do the
conversion automatically, I guess?

2. SDL (SDL-2000) "composite states" and/or "processes within processes"

question: Does anyone know the status of the tools (Tau, Cinderella,
others?)? Are they going to implement/release the features soon?

3. a simple scheduling algorithm within a process allows you to implement
multiple instances of multiple state machines within a single process.
suggested by Frend Patrick.

question: I think this approach also can be workable for me. It looks like a
proprietary approach that can achieve the behaviours similar to services.

Thanks again, and special thank to Rick for the detailed information.
Scott

-----Original Message-----
From: Rick Reed TSE [mailto:rickreed#tseng.co.uk]
Sent: February 13, 2003 1:33 PM
To: Scott Shen; Sdlnews (E-mail)
Subject: Re: SDL-news: sub-state machine and persistent state

Scott Shen at Scott.Shen#holleycomm.com wrote on 12/02/2003 22:01:

> Hi:
>
> Does anyone know how to model sub-state machine in SDL? Is it correct to
say
> that we can define sub-state machines in procedures but whenever the
> procedure is called the sub-state always starts from "start"?
>
> Now I want to have multiple sub-state machines (each is run in a
procedure)
> running concurrently inside a process, therefore every time the process
> leaves and returns to a procedure the revisited procedure should remember
> what was its last sub-state and resume from the same sub-state. Is there
any
> way allow me to do something like that in SDL? Or, is there a better (the
> right way) approach?
>
> Thanks,
>
> Scott Shen

Dear Scott,

You enquiry generated some interesting replies.

> Does anyone know how to model sub-state machine in SDL? Is it correct to
say
> that we can define sub-state machines in procedures but whenever the
> procedure is called the sub-state always starts from "start"?

While it is correct that procedures can have states, as Y Giridhar Appaji
Nag at Giridhar.Nag#ubinetics.co.in answers
> You can do this by using SDL procedures with states.
>
>
> ... You can define states in procedures and also the
> entry point is _always_ the "Procedure Start" symbol (Just like in
> a SDL process the starting point is always the "Process Start".
>
> If your intention is to go into different states within the same
> procedure (on enterin it) based on some condition, you can use a
> decision to decide where to go.

if a process enters a procedure and enters one of the internal procedure
states waiting for an input, it remains in the procedure in this state until
one of the specified inputs arrives.
Note that if there is not a SAVE * for each state in the procedure (most
easily achieved by having a STATE * with a SAVE * in the procedure) then
other unspecified signals may be consumed in implicit transitions.
What states within procedures allow you to do, is to hide in the procedure a
transaction sequence that involves communication with other processes or the
environment. It would make no difference to the behaviour logic of the
process if each procedure call was replaced by the procedure body (with
unique renaming of local variables, joins, states etc to prevent different
expansions interacting).

A procedure is therefore NOT a sub-state "machine". A procedure only allows
actions and states to be abstracted into the procedure from the process
state machine with the advantage the behaviour can be re-used.

Procedures cannot be concurrent in the sense they are in parallel, though it
is true that procedures can call other procedures and can be recursive
(either direct or indirect) so there can be several procedure instances and
more than one instance at any one time. However, (in the absence of services
or aggregate states - see below) in a process only one instance of one
procedure can be waiting in a state at any one time.

john.svensson#telelogic.com at john.svensson#telelogic.com writes

> To me it sounds like you should model this with SDL services instead of
> procedures. That would allow you to have a set of behavioural descriptions
> that remembers their state.

... and this may be exactly what you want. When a service is waiting in a
state, a signal (or remote procedure call) that is handled by another
service is sent to that service which can then handle the signal. Each
service is like a state machine but they share the same input port (or input
queue depending on terminology) and can have shared variables. A process
that is divided into services does not really contain a number of separate
state machines, but actually has a state for each possible combination of
the states of the individual services. For example if service A has states
A1, A2, A3 and A4, Service B has states B1, B2 and B3, and service C has
states C1 and C2, the process which contains these services effectively has
states:

A1B1C1, A1B1C2, A1B2C1, A1B2C2, A1B3C1, A1B3C2,
A2B1C1, A2B1C2, A2B2C1, A2B2C2, A2B3C1, A2B3C2,
A3B1C1, A3B1C2, A3B2C1, A3B2C2, A3B3C1, A3B3C2,
A4B1C1, A4B1C2, A4B2C1, A4B2C2, A4B3C1, A4B3C2

or 4 * 3 * 2 = 24 states, described by the services with only 9 states.

Services can communicate with each other by signals or through shared
variables at the process level.

On the other hand, this may not be what you wanted, because there is no
possibility to "leave" a service to some part of the process behaviour and
later return to the service. Normally services are not turned "on" and "off"
(though this could be achieved by the service design) but are always part of
the process behaviour. Neither are services concurrent. Instead they are
interleaved. When a signal is received that is handled by a service, the
process enters the transition for that signal in that service and no other
service can change state until that service enters a state. When a state is
reached in a service, the process input queue is examined to decide which is
the next service to schedule. A restriction for services is that they handle
disjoint sets of signals (or more strictly stimuli which includes remote
procedure calls).

If a service calls a procedure with internal states, such a procedure has to
be defined within the service. The signals handled by the procedure are part
of the signals handled by the services and must not be handled by any other
service. NOTE: this is not obvious from Z.100(1992) but a procedure defined
at the process level with states would allow two different services to be
waiting instances of the same procedure for the same signal.

The requirement was:
> Now I want to have multiple sub-state machines (each is run in a
procedure)
> running concurrently inside a process, therefore every time the process
> leaves and returns to a procedure the revisited procedure should remember
> what was its last sub-state and resume from the same sub-state. Is there
any
> way allow me to do something like that in SDL? Or, is there a better (the
> right way) approach?

Eckhardt Holz <holz#informatik.hu-berlin.de> is correct writing

> with most recent version of SDL (SDL-2000) sub-states are available in
> SDL. The concept is called composite states, similar to UML you can
> decompose a state into a sub-state machine a shallow and a deep history
> mechanism as well as multiple entry and exit points are available too.
> You may also decompose a state into multiple semi-concurrent state
> machines (alternating execution of transitions).

which allows sub-states that can be re-entered to the last state.

Eckhardt is also correct (as far as I am aware, and currently) no
> SDL tool (e.g. SDT/TAU, Cinderella, etc) implements these new concepts.

The service concept of SDL-92 is replaced by the more powerful aggregate
composite state in SDL-2000, but the essential features remain the same.
Eckhardt called this decomposition of "a state into multiple semi-concurrent
state machines".

There are other features of SDL-2000 such as processes within processes
which may match the requirements, but for the time being lets assume users
are limited to SDL-92 (with 1996 additions and a few SDL-2000 features
supported by tools).

To achieve multiple "sub-state" machines ... running concurrently, these
state machines have to be processes. This would also remove the restriction
that the signals need to be disjoint. Each would have its own input queue
(which may or may not be desirable).

If each process has a LeaveAndReturn procedure that has an internal state
waiting for a "Revisit" response and saves other signals, there can be a
control process that has the task of scheduling the "multiple sub-state
machine" processes. When one of the "sub-state" machines is to be run, the
control process can send the "Revisit" response to the machine. At some
appropriate point (probably just before entering a state), the machine can
call LeaveAndReturn, which should probably notify the control process.

Note: it might be possible to define LeaveAndReturn as a global procedure.

There are no doubt many other schemas that can be used with multiple
processes, but it seems in SDL-92 the choice is limited to either services
(with its limitations) or multiple processes.

--
Rick Reed - rickreed#tseng.co.uk
Tel:+44 15394 88462 Mob.:+44 7970 50 96 50

RE: SDL-News: sub-state machine and persistent state

Hi Rick, Eckhardt, John, Giridhar, Frend Patrick:

Thank you all for your helps. I am so happy that we have a strong and enthusiastic SDL community.

We have discussed some possible resolutions and I still have questions:

1. resolution ##1. A procedure is NOT a sub-state "machine". you should model this with SDL services instead of procedures. That would allow you to have a set of behavioral descriptions that remembers their state.

question: It looks service can address most of my needs except the "disjoint sets of signals" constraint, but I think it can be worked around in my case. However, since service is deleted in SDL2000 and replaced by aggregate composite state, is it difficult to convert my SDL-92 services into SDL-2000 aggregate composite state in the future? There is no way we can do the conversion automatically, I guess?


2. SDL (SDL-2000) "composite states" and/or "processes within processes"

question: Does anyone know the status of the tools (Tau, Cinderella, others?)? Are they going to implement/release the features soon?


3. a simple scheduling algorithm within a process allows you to implement multiple instances of multiple state machines within a single process. suggested by Frend Patrick.

question: I think this approach also can be workable for me. It looks like a proprietary approach that can achieve the behaviours similar to services.


Thanks again, and special thank to Rick for the detailed information.
Scott


-----Original Message-----
From: Rick Reed TSE [mailto:rickreed#tseng.co.uk]
Sent: February 13, 2003 1:33 PM
To: Scott Shen; Sdlnews (E-mail)
Subject: Re: SDL-News: sub-state machine and persistent state


Scott Shen at Scott.Shen#holleycomm.com  wrote on 12/02/2003 22:01:

> Hi:
>
> Does anyone know how to model sub-state machine in SDL? Is it correct to say
> that we can define sub-state machines in procedures but whenever the
> procedure is called the sub-state always starts from "start"?
>
> Now I want to have multiple sub-state machines (each is run in a procedure)
> running concurrently inside a process, therefore every time the process
> leaves and returns to a procedure the revisited procedure should remember
> what was its last sub-state and resume from the same sub-state. Is there any
> way allow me to do something like that in SDL? Or, is there a better (the
> right way) approach?
>
> Thanks,
>
> Scott Shen

Dear Scott,

You enquiry generated some interesting replies.

> Does anyone know how to model sub-state machine in SDL? Is it correct to say
> that we can define sub-state machines in procedures but whenever the
> procedure is called the sub-state always starts from "start"?

While it is correct that procedures can have states, as Y Giridhar Appaji
Nag at Giridhar.Nag#ubinetics.co.in answers
> You can do this by using SDL procedures with states.
>
>
> ... You can define states in procedures and also the
> entry point is _always_ the "Procedure Start" symbol (Just like in
> a SDL process the starting point is always the "Process Start".
>
> If your intention is to go into different states within the same
> procedure (on enterin it) based on some condition, you can use a
> decision to decide where to go.

if a process enters a procedure and enters one of the internal procedure
states waiting for an input, it remains in the procedure in this state until
one of the specified inputs arrives.
Note that if there is not a SAVE * for each state in the procedure (most
easily achieved by having a STATE * with a SAVE * in the procedure) then
other unspecified signals may be consumed in implicit transitions.
What states within procedures allow you to do, is to hide in the procedure a
transaction sequence that involves communication with other processes or the
environment. It would make no difference to the behaviour logic of the
process if each procedure call was replaced by the procedure body (with
unique renaming of local variables, joins, states etc to prevent different
expansions interacting).

A procedure is therefore NOT a sub-state "machine". A procedure only allows
actions and states to be abstracted into the procedure from the process
state machine with the advantage the behaviour can be re-used.

Procedures cannot be concurrent in the sense they are in parallel, though it
is true that procedures can call other procedures and can be recursive
(either direct or indirect) so there can be several procedure instances and
more than one instance at any one time. However, (in the absence of services
or aggregate states - see below) in a process only one instance of one
procedure can be waiting in a state at any one time.

john.svensson#telelogic.com at john.svensson#telelogic.com  writes

> To me it sounds like you should model this with SDL services instead of
> procedures. That would allow you to have a set of behavioural descriptions
> that remembers their state.

... and this may be exactly what you want. When a service is waiting in a
state, a signal (or remote procedure call) that is handled by another
service is sent to that service which can then handle the signal. Each
service is like a state machine but they share the same input port (or input
queue depending on terminology) and can have shared variables. A process
that is divided into services does not really contain a number of separate
state machines, but actually has a state for each possible combination of
the states of the individual services. For example if service A has states
A1, A2, A3 and A4, Service B has states B1, B2 and B3, and service C has
states C1 and C2, the process which contains these services effectively has
states:

A1B1C1, A1B1C2, A1B2C1, A1B2C2, A1B3C1, A1B3C2,
A2B1C1, A2B1C2, A2B2C1, A2B2C2, A2B3C1, A2B3C2,
A3B1C1, A3B1C2, A3B2C1, A3B2C2, A3B3C1, A3B3C2,
A4B1C1, A4B1C2, A4B2C1, A4B2C2, A4B3C1, A4B3C2

or 4 * 3 * 2 = 24 states, described by the services with only 9 states.

Services can communicate with each other by signals or through shared
variables at the process level.

On the other hand, this may not be what you wanted, because there is no
possibility to "leave" a service to some part of the process behaviour and
later return to the service. Normally services are not turned "on" and "off"
(though this could be achieved by the service design) but are always part of
the process behaviour. Neither are services concurrent. Instead they are
interleaved. When a signal is received that is handled by a service, the
process enters the transition for that signal in that service and no other
service can change state until that service enters a state. When a state is
reached in a service, the process input queue is examined to decide which is
the next service to schedule. A restriction for services is that they handle
disjoint sets of signals (or more strictly stimuli which includes remote
procedure calls).

If a service calls a procedure with internal states, such a procedure has to
be defined within the service. The signals handled by the procedure are part
of the signals handled by the services and must not be handled by any other
service. NOTE: this is not obvious from Z.100(1992) but a procedure defined
at the process level with states would allow two different services to be
waiting instances of the same procedure for the same signal.

The requirement was:
> Now I want to have multiple sub-state machines (each is run in a procedure)
> running concurrently inside a process, therefore every time the process
> leaves and returns to a procedure the revisited procedure should remember
> what was its last sub-state and resume from the same sub-state. Is there any
> way allow me to do something like that in SDL? Or, is there a better (the
> right way) approach?

Eckhardt Holz <holz#informatik.hu-berlin.de> is correct  writing

> with most recent version of SDL (SDL-2000) sub-states are available in
> SDL. The concept is called composite states, similar to UML you can
> decompose a state into a sub-state machine a shallow and a deep history
> mechanism as well as multiple entry and exit points are available too.
> You may also decompose a state into multiple semi-concurrent state
> machines (alternating execution of  transitions).

which allows sub-states that can be re-entered to the last state.

Eckhardt is also correct (as far as I am aware, and currently) no
> SDL tool (e.g. SDT/TAU, Cinderella, etc) implements these new concepts.

The service concept of SDL-92 is replaced by the more powerful aggregate
composite state in SDL-2000, but the essential features remain the same.
Eckhardt called this decomposition of "a state into multiple semi-concurrent
state machines".

There are other features of SDL-2000 such as processes within processes
which may match the requirements, but for the time being lets assume users
are limited to SDL-92 (with 1996 additions and a few SDL-2000 features
supported by tools).

To achieve multiple "sub-state" machines ... running concurrently, these
state machines have to be processes. This would also remove the restriction
that the signals need to be disjoint. Each would have its own input queue
(which may or may not be desirable).

If each process has a LeaveAndReturn procedure that has an internal state
waiting for a "Revisit" response and saves other signals, there can be a
control process that has the task of scheduling the "multiple sub-state
machine" processes. When one of the "sub-state" machines is to be run, the
control process can send the "Revisit" response to the machine. At some
appropriate point (probably just before entering a state), the machine can
call LeaveAndReturn, which should probably notify the control process.

Note: it might be possible to define LeaveAndReturn as a global procedure.

There are no doubt many other schemas that can be used with multiple
processes, but it seems in SDL-92 the choice is limited to either services
(with its limitations) or multiple processes.

--
Rick Reed - rickreed#tseng.co.uk
Tel:+44 15394 88462 Mob.:+44 7970 50 96 50

--End text from Scott Shen to sdlnews --- For extra SDL Forum Society benefits join at



This archive was generated by hypermail 2a23 : Thu May 09 2013 - 16:05:49 GMT