Re: SDL-News: transition atomicity in SDL

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


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.



----- Begin Included Message -----

>From Thu Apr 10 10:59 MET 1997

Date: Thu, 10 Apr 1997 10:58:57 +0200

From: (Bernd Grahlmann)


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




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 Included Message -----

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