[MUD-Dev] [TECH] Event Queues in MUDs

[Christian Loth]

On Wed, Dec 19, 2001 at 01:03:19PM -0000,
Daniel.Harman at barclayscapital.com wrote:
 
> Still progressing slowly with my game, and started work on
> implementing an event queue/scheduler class. Does anyone have any
> particularly good priority queue algorithms for this type of
> thing?
 
> I want to make a fairly generic scheduler, so I'm thinking along
> the lines of multiple lists of events categorised by time until
> the event. This would speed up insertion sorting as I would expect
> to have a lot of events ticking fairly frequently along with
> things on a period of several hours/days. In fact they don't have
> to be multiple queues, I just need multiple pointers into one to
> simulate this.

What I did was the following. My scheduler works with a
priority_queue, where the sorting criteria is a 64bit unsigned
integer. The lower the number, the higher in the priority queue it
is.

This 64bit integer is split into two parts: The first 32 bit is the
timeslice, at which the event wants to be executed. The second 32
bit is the event's running number, to actually address the event
object.

With these presumption, the scheduling algorithm I use is fairly
easy (pseudo code follows)

  void schedule_events() {
  
    // If there are events waiting for execution...
  
    while (!priority_queue_empty()) {
  
      // First get the priority which is currently on top of the queue.
      priority = pop_top_of_priority_queue();
  
      // Then get the event adressed by the second 32 bits of the priority
      event = get_event_by_running_number(low32bits(priority));
  
      // Then check if execution is due for this priority, i.e. compare
      // the first 32 bits with the current time slice.
      if (high32bits(priority) <= current_time_slice) {
  
        // If execution is due, execute
        execute_event(event);
  
        // Is the event finished yet with its work? If so, remove the 
        // event object. Otherwise calculate a new priority from the
        // event's running number, and the timeslice when it should
        // execute next. Insert the new priority into the priority
        // queue.
    
        if (not_yet_finished(event)) {
          priority = recalculate_priority(new_time_slice, 
                                          event.running_number);
          insert_in_priority_queue(priority);
        } else {
          remove_from_event_list(event);
        }
  
      } else {
    
        // We can assert the following: if the top of the execution 
        // queue is not due for execution, the rest won't be as well.
  
        insert_in_priority_queue(priority);
        break;
   
    }
  }
  
This sort of algorithm might not be optimal, but it was what I could
come up with, plus it works for me as of now.

This scheduling is btw running in its own dedicated thread. The
timeslices I use are 25ms which is enough for my needs.

Hope this answers your question and helps somehow,

- Chris

--
Christian Loth
Coder of 'Project Gidayu'
Computer Science Student, University of Dortmund
chris at gidayu.mud.de - http://gidayu.mud.de
_______________________________________________
MUD-Dev mailing list
MUD-Dev at kanga.nu
https://www.kanga.nu/lists/listinfo/mud-dev