Re: SDL-News: transition atomicity in SDL

Subject: Re: SDL-News: transition atomicity in SDL
Date: Tue Apr 22 1997 - 13:19:26 GMT

The originator of this message is responsible for its content.

-----From (Flavia Andrea Munhoz V. da Silva) to sdlnews

Bernd Grahlmann wrote:

-----From (Bernd Grahlmann) to sdlnews

Dear SDL user or SDL tool-builder!

This is the theory. In practice, if you would like to build a tool

which offers verification, you run into problems, because you have to

consider all possible interleavings. This causes the well

known `state explosion problem'. Therefore some tool builders

have there own interpretation. They use an explicite and completely

deterministic scheduler. Thus, for them a transition is atomic.

By using this approach they may not consider some possible runs

of the system and therefore may not exhibit some possible states

of the system. (Note that the same holds true if a ready queue instead of a

ready set is used) As long as the user knows about this restrictions

and as long as the possibly produced executable code behaves in the

same way, everything is fine. Verification and simulation is faster :-)

But you should be aware, that it may not be consistent with the (general)

SDL specification.




Bernd Grahlmann Universit"at Hildesheim

Dipl. Inform. Institut f"ur Informatik


Telefon (+49) 05121 / 883 -760 /-740 Samelsonplatz 1

Telefax (+49) 05121 / 860 475 D-31141 Hildesheim


-----End text from (Bernd Grahlmann) to
sdlnews -----

This is all very very interesting. I always wondered how tool builders got

do verification / simulation tools in the sense of how they were able to

the situations to discover if a problem was conveniently fixed or not. The

was that they build a deterministic scheduler - of course the easiest way
to get

it work. The problem is: how much the non-deterinistic behavior influences

goal system in practice ? Considering this, how seriously could one accept

verification/simulation tools results ? Strictly speaking it seems to me

these tools should advice the user about this situation - putting them
aware of

this fact. I had just read the article "Structural Testing of Concurrent
Programs" [IEEE Transactions on Software Engeneering, vol 18, n 3, march
1992] where

some related considerations are being done. The authors propose that the

scheduler could register its walk through the concurrent processes, in
order to be albe to repeat them, or it could

be included a monitoring task to make this scheduler activities

Surely this would give much more confident results if aplicable to
verification /

simulation tools because they would act more realistically. Actually, some

performance problems might still be uncovered using these solutions - and
the authors

also refer to that - but it would be much more acceptable for users, they

be much closer to their system reality.

Kind regards,



Flavia Andrea M. V. da Silva - TELEBRAS R&D Center

Phone: (+55) 019-789-6622

Fax: (+55) 019-789-6331


-----End text from (Flavia Andrea Munhoz V. da Silva) to
sdlnews -----

For help, email "" with the body of your email as:


or (iff this does not answer your question) email:

This archive was generated by hypermail 2a23 : Sun Jun 16 2013 - 10:41:39 GMT