[MUD-Dev] lockless system - foolproof?

[James Wilson]

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. In this case, the compound object
would need to be locked, and all its components locked,  in order to prevent
concurrent accesses from constantly (and perhaps indefinitely) restarting the
event that needs the whole object at  once. Please correct me if I'm wrong...

The simple case is this: we have two objects, A and B, containing reference
fields. The programmer would like to guarantee that, if A points to B, B will
point back to A, and vice versa; that is, there will always be a cycle between
them. A and B could be nodes in a doubly linked list, for instance, where

node->previous->next == node || 0 == node->previous
and
node->next->previous == node || 0 == node->next

should always be true. If thread C grabs A and breaks its link to B, and if
thread D grabs B before C gets a chance to break its link to A, how can be
ensure that the constraint is not broken? 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.

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.

Someone suggested that after several cache invalidations the thread might try a
different tack, explicitly locking the structure it is manipulating and all the
objects underneath it. This brings us right back to what we wanted to avoid,
locking and the concomitant possibility of deadlock.

James