Subject: Re: SDL-News: transition atomicity in SDL
bernd#informatik.uni-hildesheim.de
Date: Tue Apr 15 1997 - 13:19:07 GMT
Hi,
Last week I sent the following e-mail to the SDL list, but
it hasn't appeared in the list so far. I'm not sure whether
it was lost or ...
Anyhow, it would be nice if you could distribute it.
Thanks,
Bernd
----- Begin Included Message -----
>From bernd#informatik.uni-hildesheim.de Thu Apr 10 10:59 MET 1997
Date: Thu, 10 Apr 1997 10:58:57 +0200
From: bernd#informatik.uni-hildesheim.de (Bernd Grahlmann)
To: sdlnews#sdl-forum.org
Subject: Re: SDL-news: transition atomicity in SDL
Dear SDL user or SDL tool-builder!
After reading all the comments and statements to this topic,
I'm pretty sure that the notions of `atomicity', `interleaving',
`transition' and `task' are not as clear as they should be ;-)
In SDL a transition may consist of different parts
(let's say part1_1, part1_2, ..., part1_n for process 1 and
part2_1, part2_2, ..., part2_n for process 2) some of these parts
may be tasks (e.g. t:=t-1).
If you have a look in the Z100. You can find things like:
`The created process then executes asynchronously and in parallel
with other processes.'
This means, that for the two transitions of the two processes
given above you may have different interleavings
(e.g. part1_1, part2_1, part2_2, part2_3, part1_2, ...).
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.
Transitions or parts of different transitions may be completely independent
(note that using different variables is absolutely not sufficient). This is
a completely different notion (in comparison to atomicity).
Furthermore, atomicity of tasks is different from atomicity of
transitions. Atomicity of tasks is commonly used in the area of
concurrent programming, ...
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 Included Message -----
This archive was generated by hypermail 2a23 : Sun Jun 16 2013 - 10:41:39 GMT