[MUD-Dev] Re: atomic functions

[Felix A. Croes]

Jon A. Lambert <jlsysinc at ix.netcom.com> wrote:
> On  5 May 98 at 1:52, Felix A. Croes wrote:
>[...]
> > Hmm...  what is immediately obvious is that the worst-case behaviour
> > of S&S is a total lock-up, while C&C is guaranteed to be always
> > executing at least one event that will complete (if any events are
> > being executed at all).  This suggests that C&C will perform better
> > if there are many conflicts.  On the other hand, S&S offers the
> > programmer more ways to handle those conflicts.
>
> Oh no, deadlocks/lock-up are impossible because of spin-locking.  That's 
> why I was illustrating the two extremes of standard locking mechanisms.  

Well, spin-locking by itself can prevent simple deadlocks, but not
complex ones.  Take the following worst-case scenario:

    N events are executing concurrently in N different objects.  Each
    event attempts to change, in random order, a property in each of
    the N-1 other objects.  In between every two property changes by
    an event is an interval of fixed duration T, of such length that
    the entire event is of maximum duration.

Using spin-locking in this scenario, events may be wrangling over
resources without <any> of them succeeding.  Since all of them are
equally unsuccesful, increasing the priority of failing events will
not help.  Until the system starts executing events single-threadedly,
or decreases the amount of events executed concurrently to such a
degree that it becomes likely that one of them will succeed, none of
the events will complete at all.


> I don't see how any threads are guaranteed execution in C&C, unless they 
> are evntually escalated to single-threading as per your earlier 
> reference.  How does atomic prevent another thread from accessing and 
> updating objects, unless you single thread/task it?

What I wrote is wrong -- if N events are executing and the first
one to complete succeeds, then the ones that complete after that
may all fail, so after completion of the first event, none of
the events executing at that moment will succeed.  But in C&C,
an event that is itself doomed cannot block the progress of
another event.  Since an event can only be doomed by another
event that already completed successfully, progress is guaranteed
in the system as a whole.  In the worst case scenario above, one
event would immediately complete successfully.

Felix Croes

--
MUD-Dev: Advancing an unrealised future.