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

[James Wilson]

On Sun, 30 Aug 1998, Chris Gray wrote:
>[James Wilson:]
>
> >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.

>I certainly don't want to speak for JC, but here's my understanding...

[snip]

>There could be lots of retries needed on busy objects. I believe some of the
>suggested solutions involved the scheduling of events, with the final
>attempt that of running the contentious (hah!) event all by itself,
>with nothing else running.

yes, contentious is a good word for it. the last clause would of course result
in complete system-wide stoppage while the contentious event is processed. 
This is much stronger than is actually needed; all that is required for
correctness is that events which would collide are not run concurrently. 

Suppose that I have constrained my user scripts so they can only access
some finite set of persistent objects within a given event, and that set can
be determined before the event is actually invoked . For instance, if an
event requires access to at most ten persistent objects, those ten
can be locked before the event is invoked. One could also distinguish 
between read-only and read-write access to allow shared access 
where appropriate.

Leaving aside for a moment the question of whether or not such a set
can be determined automatically (or what mud language structures would 
be required to support that sort of analysis), would it help? 

In the case of the nodes A and B which mutually reference one another, the
event which breaks the cycle would be flagged as needing two objects, A
and B, and would lock both of them. If other events are already manipulating
A or B, the event will be stalled until they're done. Similarly, events that
need to access A or B stall until the cycle-breaker is done. 

If events can nest (i.e. event 1 starts event 2 and does not complete until
event 2 completes) then this system would be subject to deadlock, as 
event E could lock A, event F could lock B,  and each could then nest by
invoking one another. So the above is incompatible with nested events. 
One would be forced to make all events asynchronous, so event E's 
spawning of  event F would not result in the execution of F *within* E, but
rather the execution of F sometime after its spawning. This is a significant 
restriction.

Another problem has to do with obtaining the set of objects a given event
wants to operate upon. If these are fixed (event E always operates on object A)
there is no problem, but presumably one would like to allocate new objects
at runtime and invoke events which manipulate them. In this case, there 
could be some computation done before an event is invoked which determines
the 'working set'. Consider the case where an event is to manipulate a linked
list, where each node in the list must be locked while the event is in
progress. There must be a point at which the linked list is traversed and the
objects in question locked; thus, one must protect THIS segment from deadlock
as well! Otherwise two threads could start at different ends of the list and
try to lock each node in it; they could each get halfway and freeze, waiting
for the other to relinquish the locks on the half they don't have... Mutexing
the procedure which obtains the locks could be a solution, so only one thread
is locking objects at any given time, but this could be a serious bottleneck
(as waiting for a previously locked object would block the invocation of new
events).

Alternatively, the set of objects accessible to the event could be passed when
the event is pushed on the event stack. Thus if event E has access to object A
which points to objects B and C, E can push a new event F which will manipulate 
B and C simultaneously. Manipulating an entire list could be accomplished by
an event E obtaining access to A, spawning F which has access to A and B, 
spawning G which has access to A, B, and C, etc... unwieldy indeed. 

James