[MUD-Dev] C&C and Event Rescheduling

[clawrenc at cup.hp.com]

In <199707261742.TAA00453 at regoc.srce.hr>, on 07/26/97 
   at 10:53 AM, silovic at srce.hr (Miroslav Silovic) said:

>> Jon A. Lambert wrote:
>> > 
>> > > From: clawrenc at cup.hp.com
>> > > Subject: [MUD-Dev]  C&C and Event Rescheduling
>> > >
>> > >   Re: #5.  How do you determine that the object has changed during the
>> > > execution of the event?  I do this by always keeping an original copy
>> > > of the object to compare to the copy current in the DB and then do a
>> > > bit-wise comparison of the two objects.  The original copy is the
>> > > second copy made above for a modification.

>I already specced the commit procedure for Cold, however, I went for
>locking instead of copying. When you read an object, you obtain a
>read lock on it. On write, the original is copied (in case of the
>rollback), however, if any other task has a read lock on the object,
>writer gets a rollback. If write suceeds, the object gets a write
>lock - attempt to read a write-locked object causes rollback (these
>are the basic rules, of course). Temporary copies are kept in a hash
>table (hashed by object IDs), and thrown away on commit (along with
>write locks). Advantage of this method is that things are not copied
>unnecessarily (actually piling the copy in the hashtable is a simple
>reference tweaking, and not actual tree-copying). 'Object' here
>actually means object attribute, object method, object header (i.e.
>objname and parents/children lists), file buffers and networking
>buffers. Of course, none of this has been implemented yet. :)

Ignoring the lock semantics, in actual runtime effect this is almost
identical to what I'm doing.  However the net effect of the write lock
behaviour (Okay, dipping slightly into lock sematics) is to signal a
failed contention when the attempted access occurs rather than at
commit as I do.  This could allow a failed event to die and reschedule
much sooner than if it had to wait for the other contender to commit

Hurm.

It also changes the character fo the DB accesses.  In the lockless
model events compete to C&C successfully.  Events with smaller
workings have an advantage at C&C time, as do events with shorter run
times.  Its a question of who is in and out first.  Neither of those
points are true for your model.  For you, more or less, the first to
reach the base has it, holds it, and is guaranteed to commit
successfully (ignoring questions of needing to access an object which
another already has locked, which is not a safe assumption as below). 


Another potential problem is that your locking model opens itself to
infinite loops about the Dining Philosophers problem.  Without some
very interesting deadlock detection it is quite possible to have (say)
a minimal set of 3 events each of which attempts to lock various
objects and all of which get killed/rolled back because one of the
other two events already has the requested resource.  Consider:

  Objects A, B and C,

  Events X, Y and Z.

  X locks A.

  Y locks B.
  
  Z locks C

  X attempts to lock B and dies.

  Y attempts to lock C and dies.
  
  X restarts and locks A.

  Z attempts to lock A and dies.

  Y restarts and locks B.

  X attempts to lock B and dies.

  Z restarts and locks C.

  Y attempts to lock C and dies.

  ...etc.

This is a very simplistic case.  Add many more events, and have each
event attempt to access more than one object (5?  10?) and it becomes
almost probable.

Aside: Its not distributable, well, not in any sane manner, whereas
the lockless model rolls out there pretty easily, especially if you
allow objects to migrate between DB servers.

--
J C Lawrence                           Internet: claw at null.net
(Contractor)                           Internet: coder at ibm.net
---------------(*)               Internet: clawrenc at cup.hp.com
...Honorary Member Clan McFUD -- Teamer's Avenging Monolith...