Re: SDL-News: transition atomicity in SDL


Subject: Re: SDL-News: transition atomicity in SDL
munhoz#cpqd.br
Date: Tue Apr 22 1997 - 13:19:26 GMT


The originator of this message is responsible for its content.

-----From munhoz#cpqd.br (Flavia Andrea Munhoz V. da Silva) to sdlnews
-----

Bernd Grahlmann wrote:

-----From bernd#informatik.uni-hildesheim.de (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.

Cheers,

  Bernd

*********************************************************************

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

bernd#informatik.uni-hildesheim.de

*********************************************************************

-----End text from bernd#informatik.uni-hildesheim.de (Bernd Grahlmann) to
sdlnews -----

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

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

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

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
the

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

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

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
registration.

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
would

be much closer to their system reality.

Kind regards,

Flavia

********************************************************************

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

Phone: (+55) 019-789-6622

Fax: (+55) 019-789-6331

munhoz#cpqd.br

http://www.cpqd.br

*********************************************************************

-----End text from munhoz#cpqd.br (Flavia Andrea Munhoz V. da Silva) to
sdlnews -----

For help, email "majordomo#sdl-forum.org" with the body of your email as:

    help

or (iff this does not answer your question) email:
owner-sdlnews#sdl-forum.org



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