[MUD-Dev] Re: atomic functions

J C Lawrence claw at under.engr.sgi.com
Tue May 5 17:21:27 New Zealand Standard Time 1998


On Thu, 30 Apr 1998 16:18:44 -0400 
Shawn Halpenny<malachai at iname.com> wrote:

> I'm not sure I understand how this alone will impose an execution
> order.  If I have threads (I could even substitute "events")
> executing in parallel, normally whichever is able to C&C first,
> wins.  Any order I impose on executing events depends on sequence
> numbers associated with the events themselves.  Design details about
> the sequencing are still muddy, since I'm re-examining my approach.

This is an area that I'm still not happy with in my own design.  The
specific area I'm not happy with is the handling of an event which has 
failed C&C sufficiently to exhaust its rescheduling opportunities.
Details of the ugliness follow:

My basic model is simple:

  An event may execute, and may define one or more events to be logged 
if an when it itself succeeds at C&C.

This itself is fairly simple stuff.  Each event of course only exists
as of when it passes C&C, and so can only logically cause things to
exist if it succeeds at C&C.  

Complexity enters in two areas:

  1) An event executes which logs two or more subsequent events with
the intention that some N event will finally be executed after all the 
intervening events have successfully C&C'ed.

  2) An event logs an event to follow it, and C&C's.  That next event
similarly logs a follow-up event, C&C's and so on, daisy chain style.
(This is an extremely common construct).  Eventually one of these
subsequent chained events is unable to C&C (exhausts its rescheduling
opportunities), and fails.  The chain dies.



#1 may seem a bit complex.  Diagrammed:

         +--EventB--+
        /            \
  EventA              EventD
        \            /
         +--EventC--+

Execution proceeds from left to right.  EventB and EventC are executed 
in parallel with their relative C&C order being inconsequential.  More 
complex scenarios are easily crafted, such as:

                   +--EventD--+
                  /            \
         +--EventB----EventE----+--EventH--+---+--EventJ
        /         \                       /   /
  EventA           +--EventF--+--EventG--+   /
        \                    /              /
         +--EventC----------+              /
                             \            /
                              +--EventI--+

ie EventJ executed only after EventH, EventG, and EventI have all
successfully C&C'ed, with each of those events having signficantly
different parentages.  You can also get much nastier patterns where
the dependancies are on the prior C&C of events logged from utterly
seperate parentages.  

Yes, this is nasty stuff.  Happily I don't find it happens often.
Unhappily it always happens when I'm doing otherwise tricky stuff and
would *really* appreciate having a simple set of machinics to work
with.

My solution for the first (simple case) is that I allow the predicate
on an event to define that it can only run when all of its parent's
direct children (ie daisy-chain children) have C&C'ed.  This is an
ugly solution. and I doin't like it one bit.

For the more complext cases I have an object heirarchy whose instances
act as semaphore objects.  Its ugly.  It effectively creates global
variables in the guise of first class objects, whose state is
protected by the C&C mechanism.  Watchers and spoofs are then used to
effect synchronisation in the updates to the sempahore object states
such that the appropriate events are logged when the right time comes.
Ugly ugly ugly ugly.  Wish I had something better.

Faint idea for a decent model which would allow solution of the entire 
problem space in a reasonably elegant manner:

  Expose the entire executing-events space as first class objects
which can be spoofed, watched etc.  

  For an event that fails C&C, no watches etc are triggered (after
all, it didn't exist), however the same watchers and spoofs are
installed on the next instance of that event when it comes back thru
the rescheduler.

  Events can then install watchers on their own children, and then use
those watchers to effect coordination.

<shrug>  Needs thought but could very well work.



#2 is the one that has a whole lot of my attention.  The problem is
in handling the error condition.  Sure, if the subject event is the
result of attempting to process a "go north" command, the final C&C
failure is not critical.  The problem really occurs in the non-trivial 
cases, especially when it is deep in an event daisy-chain.

Consider the case:

  > l
  You are in Panama.
  > dig canal
  You start digging the panama canal.

Now what actually happens is that the "dig canal" command starts a
very long event daisy chain.  Each event digs a bit, and then logs a
new dig event for a little bit further in the future.  Now lets say
that the 53rd such daisy-chained event ultimately fails its C&C (and
all attempted reschedules).  What to do?

What if this event daisy chain didn't start from a user command, but
was generated by a mobile attempting its normal business of wandering
the land?  If the event chain dies with that failed event the mobile
itself "dies" -- there are no more events to "animate" it.

My only solution has been to remove the possibility of an event
failing out fo the rescheduler.  Every event must now eventually
succeed at C&C.  The only variation is how hard the rescheduler tries
to get it to pass C&C early on in the reschedule process.

I can't see a logical course about this one.  I actively suspect that
there isn't one, but am not prepared to invest the effort (now) to
prove it.

--
J C Lawrence                               Internet: claw at null.net
(Contractor)                               Internet: coder at ibm.net
---------(*)                     Internet: claw at under.engr.sgi.com
...Honourary Member of Clan McFud -- Teamer's Avenging Monolith...

--
MUD-Dev: Advancing an unrealised future.



More information about the MUD-Dev mailing list