W3C home > Mailing lists > Public > www-voice@w3.org > January to March 2013

Re: revisiting preemption

From: David Junger <tffy@free.fr>
Date: Mon, 18 Feb 2013 18:46:41 +0100
To: "VBWG Public (www-voice@w3.org)" <www-voice@w3.org>
Message-Id: <2870C437-6F86-4A35-BFD8-96634504D881@free.fr>
Le 18 feb 2013 ŗ 15:58, Jim Barnett a ťcrit :

> 1.       Do we want another definition of preemption?  The obvious candidate is UMLís definition:  two transitions conflict if their exit sets have a non-null intersection. We can tweak the definition based on transition classes/types to have the same semantics, so the real question is:  which definition is easier to understand?

The most intuitive (and shortest to explain) is that optimally-enabled transitions are taken in transition order unless their source has been exited by a previous transition, in which case their are disabled during the exit step. But that's not UML-compatible.

If you want UML-compatible transitions, then, first sort the optimaly-enabled transitions according to this comparator(t1, t2):
	tie if t1 is targetless and t2 is targetless.
	t1 < t2 if t1 is targetless.
	t2 < t1 if t2 is targetless.
	t1 < t2 if t1's LCCA is a descendant of t2's LCCA.
	t2 < t1 if t2's LCCA is a descendant of t1's LCCA.
	tie otherwise.

	use transition order (or document order, which is equivalent at this point) to break ties (though that's unnecessary if you use a stable sort).

Then proceed as before, i.e. optimally-enabled transitions are taken in that order unless their source has been exited by a previous transition, in which case they are disabled during the exit step.

Note that this total ordering of the SC's transitions does not change depending on which transitions are enabled, so it can be compiled.

> 2.       What do we want to do about targetless transitions?  They have an empty exit set, so on the UML definition they donít preempt any transitions and donít preempt any other transitions.  The existing definition (based on transition types/classes) says (in effect) that a targetless transition is preempted by any preceding transition that exits its source state.  This may seem intuitively clear, but it isnít necessary by any means.  The whole point of preemption is to block transition sets that could produce an illegal configuration, and targetless transitions will never do that.   By not preempting targetless transitions, we end up with the largest set of transitions that can be guaranteed not to cause problems.

Agreed, though it might be less intuitive, I don't think it's horribly confusing to say that targetless transitions get priority. But we also have to define the transition's execution order (for determinism). If they can't be preempted then they should be executed before all others.

> 3.       When we discussed this issue in the past, we decided that preemption is so complicated that it should be defined in a separate place, hence we have ĎfilterPreemptedí as a separate function.  On the other hand, the filtering could be folded  back into the selectTransitions functions, particularly if it is based on the intersection of exitSets.   So we could consider getting rid of filterPreempted as a separate function.  However, if we do this, we have to insert the same conflict/preemption-detecting logic in both selectEventlessTransitions and selectTransitions, so it may be better to keep it factored out into a  separate function.

I believe my comparator proposal solves that. You just need a quick test in the exit step to check if the transition's source is still active.

Received on Monday, 18 February 2013 17:47:09 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:07:43 UTC