[MUD-Dev] [TECH] Event Queue System

[Phillip Lenhardt]

On Fri, Feb 15, 2002 at 02:50:38AM -0800, J C Lawrence wrote:
> On Thu, 14 Feb 2002 17:02:32 -0600 the_sage2000 at juno.com> wrote:

>> 1) Has anyone implemented an event queue system and can give me
>> advise on doing it?

> Note: This is an abuse of the definition of "event".
> Unfortunately its an abuse I popularised in the early days of this
> list, and it doesn't seem willing to die.  It should die.

> What you are calling events above and below are really just
> scheduled processes, very akin to cron jobs, not events.

A common and accepted term for the things you put on a schedule to
be executed is "task".

I have implemented task schedulers in Python several times and I
have partial C and Scheme implementations as well.

>> this event list can have many fields, but, unless I've forgotten
>> a key field, all that is really needed is the event the MUD
>> should execute, at what time, and who's wanting to do the event.

That's the typical minimal task structure that I've seen as well.
But you can get a lot more exotic than that.  For one, needing a
"who's wanting to do the event" field is a very object-oriented
approach.  In a logic programming language (eg Prolog) you could
have a schedule composed of nothing but constraints to be unified.
In a pure functional language each task could be just a (possibly
curried) function that takes a monad.  In a procedural language, you
could have a schedule composed of inputs to a finite state machine.
In a Lispish language each task could be a closure/continuation.
I'm sure there are other possibilities as well.

When it comes to the time field, there are a lot of options there
too.  You can store an absolute time (eg "1100:00:00 GMT") or you
could store an offset from some fixed time (eg "300 seconds from
now/startup").  Or you could make execution time implicit by
splitting the list into buckets where each bucket is executed in a
particular timeslice.

And if you stick to an object-oriented "who's wanting to do the
event" structure you could do away with the task name field and have
each object keep an internal task list (eg the schedule always calls
object.do_task() and leaves it to the object to decide what task it
needs to do).

In my work I've also noticed that it is good to keep the schedule as
minimal as possible, since that speeds up inserts/deletes and helps
ensure that parts of it don't get paged out.  Also, the smaller the
schedule, the easier it is to write to disk for persistance and the
easier it is to regenerate it if it gets corrupted.  The structure
used for the schedule itself also bears some consideration: list? 
heap? priority queue? something else?

> Most text MUDs have used one of a few structures:

... 

>   5) Maintaining a sorted list of predictively scheduled processes
>   that involve objects which are likely to be visible to or affect
>   the current player base (in their current positions/activities).
>   As the players move about and act in the world nodes are removed
>   from the set as they pass out of range/notice and new nodes are
>   added as additional active systems come into the range of
>   awareness of the players.  Items are popped off the list and
>   executed as applicable.  This effectively surrounds each player
>   with a nimbus of "active objects" with the rest of the world
>   lieing fallow until they are activated by a player coming into
>   range.  For items which require the apparency of extensed state
>   change operations (eg a lake draining thru a smashed dam), while
>   out of player range nothing is done, upon a player coming into
>   range the then current state of the lake etc is inferentially
>   computed and scheduled processes are inserted from there to
>   render the apparency of the lake having been continuously
>   animated.

I have heard this talked about, but I've never seen an
implementation.  And it seems so complicated I doubt it really works
that well anyway.

> They all share the base problem of attempting to define future
> activities on the basis of current state -- which frequently
> causes problems when current state at the time of execution not
> longer matches the state at the time of prediction.

I find that this is less of a problem when the schedule just keeps
track of object references and when to call object.do_task().  The
schedule doesn't know why the object wanted to be called at time T,
it just knows that a some point in the past the object thought that
it might have work to do at time T.  This lets the object modify (or
possibly nullify) a task at any time between when it was scheduled
and when it ripened. (as an aside, locality of reference is also
better, since all the state associated with the task is stored in
the object, which needs to be loaded anyway to do a task, instead of
in the schedule, which doesn't do anything with the task state
besides provide it to the object.)
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev