[MUD-Dev] Re: lockless system - foolproof?

[James Wilson]

On Sun, 30 Aug 1998, J C Lawrence wrote:
>On Sat, 29 Aug 1998 19:42:17 -0400 
>James Wilson<jwilson at rochester.rr.com> wrote:
>
>> In order to avoid the problems inherent in thread synchronization,
>> (I think) JC has suggested a lockless system based on (what I call)
>> per-object "cache invalidation", that is, writes to objects a thread
>> is examining invalidate that thread's cache and hook a restart of
>> the event being processed.  This is fine for single-object locking,
>> but (as far as I understand it) does not address the case where an
>> event must deal with multiple objects atomically without those
>> objects mutating under it. 
>
>No, you are missing a key point:  The only time that an "invalidation"
>(as you term it) occurs is when an object successfully C&C's.  ie For
>any event to be rescheduled there must have been a prior event which
>successfully compleated (this ignores the minor question of internal
>event failures and time-outs).

*shrug* I guess I wasn't clear enough. What you describe is exactly what I
meant.

[snip]

>> one solution could be: C doesn't save its change to A to the
>> database until it has also changed B. When it does save changes, it
>> will then need an atomic operation to save A and B simultaneously.
>
>Bingo.
>
>> Assuming this solution (please let me know if there are any other
>> solutions), the possibility arises of having to collect a large
>> number of such database commits due to some operation on a complex
>> compound object, where guaranteeing the atomicity of access to
>> subobjects is not sufficient. Then a thread which tries to grab all
>> the objects in question, operate upon them in such a way that the
>> overall constraints are satisfied, and save the changes, would be
>> vulnerable to frequent, possibly endless restarts as one or another
>> of the many objects it is trying to keep coherent is changed.
>
>True.  

[example snipped]

>The easiest and perhaps the simplest way of attacking this is thru
>approaching the level of parallelism in your execution model.  Again,
>taking the pessimal case, if the execution model degrades until only
>one event is executing at a time, then X is guaranteed to successfully
>C&C when its turn comes as there is no competition.
>
>This is the approach I take.  Events enter the Executor with a
>"priority" value.  As events fail C&C they accumulate priority.  The
>executor's execution model then adapts dynamically per the highest
>priority event on its list.  At one end its the normal unrestrained
>competition between events, and t the other it degrades to
>single-tasking with everal stages in between.

Are your events guaranteed to complete in bounded time? You mentioned that you
are designing with user scripting in mind. If one of those contentious events 
ends up getting a monopoly on cpu time, *and* it's of long/indefinite duration
(which would seem to correlate nicely with the propensity for contentiousness),
everything would freeze waiting for it.

While some might say it seems a bad idea to allow users to write long-running
functions, a scripting system would seem to me to be most useful to builders
wanting to add new functionality to the world without having to muck about in
the source code. In this case, putting bounds on running time would be a serious
constraint on builder creativity. Ideally, bounding runtimes should be a
matter of policy rather than forced by the implementation. 

James