[MUD-Dev] [TECH] Event Queue System

[J C Lawrence]

On Thu, 14 Feb 2002 17:02:32 -0600 
the sage <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.

  An event is an external state change whose detection prompts and
  requires some form of reaction by the system, typically in the
  form of an internal state change or internal process execution.

    Translation: Something happened outside the system and the
    system noticed and reacted in some way.  The thing that was
    noticed was an "event".

This is why things like key presses, network packets, interrupts,
mouse movements etc are typically termed "events".  What you are
calling events above and below are really just scheduled processes,
very akin to cron jobs, not events.

> 2) Can anyone give me more information on it than what I am about
> to present?

You may want to search the list archives.  There have been several
systems for handling scheduled processes discussed on the list,
usually tightly bound to the transaction and data flow model of the
author's server design (eg my dispatchor/executor/thread pool
model).

> 3) Is the way I'm going to present it totally wrong?

No.

> An event queue system is a system which uses scheduled events to
> execute, rather than looping through millions of lists per second
> to check that no characters have moved, picked something up, said
> something over a channel, no mob has moved, tried to kill another
> mob, no room has changed it's description through OLC, no object
> has been enchanted, etc., etc.  It, literally, just loops through
> one list, and one list only. Now, 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.

Correction:

  You have a number of processes that you want executed at known
  times in the future.  The problem is how to efficiently track,
  represent, and execute those processes within your transaction
  model, thread model, and data flow model.

Most text MUDs have used one of a few structures:

  1) Iterating across the entire object base on each heartbeat
  querying each object and executing any required functions as
  indicated.  Typically this is done by broadcasting a hearbeat
  event to all objects and then acting on any reactions to that
  event.  This has obvious poor scalability and performance curves.

  2) Maintaining a distinct list of "active objects" and then
  iterating across that set on each heartbeat making the same checks
  etc.  Typically this is done by broadcasting a heartbeat event as
  above.  This has the same scalability and performance problems as
  the last, but does do a bit better as the processed set is
  smaller.

  3) Maintaining a sorted list of predictively scheduled processes
  and on each heartbeat popping ripe items off the top of the list
  and executing them.  This performs reasonably well as it reduces
  the working set on each cycle, but retains the problems of
  hearbeat driven systems, as well as the questions of predictively
  defining all scheduled processes.

  4) Maintaining a sorted list of predictively scheduled processes
  and as each comes ripe (often as determined by an internal time_t
  via SIGALARM) popping ripe items off the top of the list
  and executing them.  

  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.

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.

> For more graphical people (why are you playing MUDs? :P) ...

Not all MUDs are textual.

--
J C Lawrence                
---------(*)                Satan, oscillate my metallic sonatas. 
claw at kanga.nu               He lived as a devil, eh?		  
http://www.kanga.nu/~claw/  Evil is a name of a foeman, as I live.
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev