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
*********************************************************************
-----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