[MUD-Dev] C&C and Event Rescheduling
clawrenc at cup.hp.com
clawrenc at cup.hp.com
Mon Aug 11 16:58:22 New Zealand Standard Time 1997
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
>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
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
Event X is executing.
References Object A.
Is A in X's working set?
Is A's inheritance tree up to date?
No -- rebuild inheritance tree.
Yes -- continue.
Yes -- continue.
Add A to X's working set.
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?
-- on each interation select a random rescheduling time from a
range whose total size doubles?
-- 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
Event X fails at time T.
X will be rescheduled at a time S.
S will be T + (N * Q) + rand(M * N)
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
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
>> 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
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...
More information about the MUD-Dev