[MUD-Dev] C&C and Event Rescheduling

[clawrenc at cup.hp.com]

In <199708012349.BAA04053 at petra.zesoi.fer.hr>, on 08/01/97 
   at 05:03 PM, Miroslav Silovic <silovic at petra.zesoi.fer.hr> said:

>> >I consider this a good thing. Remember, you have change_parents
>> >function in Cold. When you call it, it guarantees that the database
>> >will be consistant after termination. 
>> 
>> FWLIW I have a similar call, but I don't guarantee consistancy. 
>> Instead I rebuild the inheritance tree when an outdated object is
>> detected.  This doesn't change the workload much -- it just spreads it
>> out over time.

>No, the problem we deal with is this: Suppose you have a helpnode,
>and some moron decides to reparent it to room. Now this is almost
>surely and admin mistake, but this is what then happens: helpnode is
>tracked by help indices, and rooms are tracked by their realms. Now
>if you /only/ change the inheritance, you have a room in a help index
>and a room without its realm. This, of course, is a Bad Thing,
>because you have also broken the help index.

>The idea, then, is to call destructor method that destroys the
>helpnode part of the help node (indidentally removing it from its
>index) and calls constructor that does the housecleaning needed to
>add a consistant room.

>Now do this to a helpnode with 2000 descendants. Each of them is a
>helpnode and, well, needs to be cleared.

>Of course, this is not very realistic example, but adding parents to
>user object may well be very desirable, and if the parent require
>some internal state (suppose you're adding combat stats object to
>user), Cold will guarantee that the entire hierarchy is properly
>initialized.

>This has *huge* working set, but the alternative of /not/ doing it
>caused incredible number of problems in the past (it's utterly
>annoying to have, for example, invalid objects in the player
>database).

I don't see the problem IF you have a fail safe method of determining
that an object's inheritance tree is outdated.  For me the procedure
is:

  Event X is executing.
    References Object A.
    Is A in X's working set?
      No --
      Is A's inheritance tree up to date?
        No -- rebuild inheritance tree.
        Yes -- continue.
      Yes -- continue.
    Add A to X's working set.
    Continue.

Then you never need concern yourself if an object is out of date, as
any access to an object guarantees that it is up to date.

>> >Actually I intend to reschedule the tasks with random delays,
>> >precisely because of this (I believe this solution is standard).
>> >Deadlock is improbable, then, because sooner or later things will
>> >schedule in the right order, with proper pause between each.
>> 
>> Random rescheduling is a standard approach, however I wouldn't label
>> it a solution.  You might like to do a simulation here.  I suspect
>> you'll be surprised by the results.  The problem of this approach is
>> that its incredibly sensitive to both the load and to range of the
>> random number generated.  
>> 
>> Specific case:  If the random generation varies by a value which is
>> generally far smaller than the specific contending events in question,
>> then they'll continue to contend for a long while.  There are other
>> nasty cases (a simulation should show you most of the nasty ones).  

>I actually intended to double the random delay on each reschedule.
>This should take care of most of the problems. But you're quite
>right, this will take some experimenting. Mind you, we don't even
>have OS-level threading in place (or even in progress) yet. :)

There's some definitional fall out here:

  Is this a 

    -- select a random value, and then interatively double that
earlier value on each rescheduling?

or
    -- on each interation select a random rescheduling time from a
range whose total size doubles?

or

  -- on each interation select a random rescheduling time from a fixed
length range which is then appended to a time block whose length
doubles on each iteration?

I'm certain there are studies on this area, but I don't have time to
investigate.  My temptation however would be to have the rescheduling
time follow:

  Event X fails at time T.
  X will be rescheduled at a time S.
  S will be T + (N * Q) + rand(M * N)

  where:

    N is the number of times this event has been rescheduled.  

    Q is a fixed unit of time equal to 1/2 (this fraction requires
tuning) the runtime length of an average event.

    M is a fixed unit of time equal to the shortest common runtime of
an event.
    
It could also be profitable to make S:

  S will be T + rand(Q * N)
 
Testing would tell.

>I'm actually interested on your opinion on doubling the delays each
>time (well, doubling value 'x', then getting the delay as random(x),
>to be more precise).

Ahh, you've answered the above question.  I *think* this would work
pretty well.  I'd really want to program up a little simulator that
ran say a test bed of 50 or 100 (P) simultaneous events which compeat
for a limited set of N resources (N == P, N>P, N<P, N>>P etc).  Let
the thing run for a few hours/day, vary the various weighting factors
and see what the results look like.  

It should take about a day or less to design, write, and debug,  Then
play with it for a week or so and see what sort of numbers and
performances you get out of it.

Note: You may also want to play with your random() algorithm, as well
as making the selection of seed on each call/thread be reset.  many
random() implementation area really NOT random for strict sequential
calls.

>> Unter originally took the replication model.  Latter design
>> discussions that I've heard of spoke of doing RPC until a threshhold
>> value (balance of local calls to remote calls from specific target) at
>> which point the object would be moved to the preferential server.

>I like this, but i'd have to do some thinking to figure how to do it
>(well, of course, I'll not be the only one to do the thinking).

It is what I'd like to do, but I have yet to come up with a really
decent design for it.  *ponders*  Something to chew on for those late
nights.

--
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...