[MUD-Dev] Question about threads.

[J C Lawrence]

On Wed, 13 Feb 2002 13:05:05 -0600 
David Anderson <Anderson> wrote:

> I joined the list a day ago or so, and ended up reading the last
> few quarters of e-mails just because they were so interesting.

Welcome.

> I was wondering about what the purpose of using threads would be,
> since currently I'm in a single loop like Rom, where I process
> every user in turn, and cycle through that over and over.

In essence there are three uses for threads:

  1) Minimising blocking operations
  2) Easier/more deterministic in-game state transitions 
  3) Scalability 

The typical first case for #1 is gethostby{addr|name}() which has a
long timeout associated with it which can't be trivially worked
around.  If you don't do (reverse) lookups this is not a problem.

The more simple case for #1 also impacts #2: keeping your internal
game state logically consistent.  The base problem is time
management.  In a typical text mud setup you have a heartbeat loop
that does a sweep of the active objects on each beat and invokes the
appropriate code for any state changes needed.  While horribly
inefficient, this works for small systems and light weight state
changes.  The problem enters when either:

  a) The number of state changes to perform on a given sweep becomes
  large such that the total time required for the sweep grows and
  becomes unpleasantly noticeable by the users.

  b) One of the component state change functions executed during a
  sweep runs excessively long (which leads back into #a).

The typical/first approach to this is to implement internal
application level threads (cf MOO), or which some fields call
"fibers".  Simply, this means that on each sweep only some portion
of each state change function is executed before processing moves on
to the next one.  Any incompleat state changes functions are picked
up in their incompleat state and executed for another slice on the
next sweep along with any other new state change functions for that
sweep.

This has two obvious problems:

  1) It doesn't handle the problem of the list of state change
  functions to be called growing, and in fact makes it worse more
  rapidly (continued functions are added to the load on the next
  pass, making the number of items to be processed in that sweep and
  this the time needed even longer).

  2) Determining and maintaining logical state guarantees becomes
  increasingly complex.  Consider: 

    What if a state change function on one pass starts manipulating
    objects Q and R, but that function doesn't finish.  

    On the same pass another state change function attempts to
    manipulate objects T, V and W based on the internal states of Q
    and R, and also doesn't finish.  Note: that this second function
    has few guarantees that the internal state of Q & R are
    logically consistent either with each other or with the state of
    W.

    On the next sweep both incompleat fragments start up again, and
    a new state change function is added to the list which also
    processes objects Q, T and W before being interrupted.  This
    function has the same problems as the others: It has few if any
    guarantees as to the internal or relative state of the objects
    it references.

  Its quite a mess.  Is the door open or closed?  If closing or
  opening the door also changes the state of the wind object, when
  the process door operation is interrupted and the flutter flag
  operation starts, is the wind blowing or not?  That's a rather
  trite and insignificant example -- I'll leave you to come up with
  more critical and player-confusing examples (its not hard).

Note that this sort of logical inconsistency can prevented and
handled thru careful data handling/sequencing, process design, and
hinting of interruption/yield state change functions (eg make the
scheduler cooperative instead of pre-emptive (the arguments for and
against cooperative scheduling are distinct and for another post)).
The main problems on this approach are that:

  i) As the number of state changes per sweep increases the whole
  game slows (sweeps take longer and longer and the number of
  incompleat changes per pass grows).

  ii) It requires the developers of state change code to be
  intimately familiar with the internal logics and data handling of
  the current game, the relative processing time and expense of
  their code and the code it calls, and how to correctly handle
  access and lock sequencing to shared data.  Unfortunately the last
  couple are (seemingly) uncommon skills.

A threaded approach can be taken where state change functions are
executed by distinct threads at some level of parallelism.  The
fundamental change from the fibre model is that the scheduler is
pre-emptive.

  The question of whether scheduling is handled in-application or by
  the OS is largely moot as it doesn't change (outside of hinting)
  the base problems.  The real gain that moving to an external
  scheduler gives you (outside of code simplicity) is that you can
  now take advantage of multi-processor systems (and possibly
  distributed systems as well).

However the big gain from threading is scalability.  The single
threaded approach dictates that all the state change functions for a
given sweep be executed sequentially.  Outside of hardware
contraints the processing of player commands (for instance) need not
wait on and need not be paced by the processing and execution of
state change functions and the relative processing of state change
functions can be balanced such that some degree of fairness is
achieved between fast and slow state change functions while also
maintaining a good user experience.

Please note that threading is not a magic bullet.  Its not.  Its a
tool that brings its own problems with it with the primary problem
being data access sequencing and lock management.  Both can easily
and rapidly become non-trivial problems (do some searches on ACID
(in the DB context) and deadlock detection and prevention for
details.

  Also note that in many cases moving to a multi-processing model
  instead of a multi-threaded model can be just as effective and far
  simpler.  The main reason NOT to move to a multi-processing model
  is if state change operations need to share and operate on
  considerable shared state as under a multi-processing model that
  tends to mean a significant message passing expense.

> I haven't found sockets to ever deadlock me, as long as I set the
> sotimeout (socket timeout) to 200 miliseconds.

While I can't comment on the Java model/limits, in the general case
you do not have control over all sockets used by your application.
Some socket operations are hidden under library APIs (eg
gethostbyname()) and are not trivially changed.

Which is also rather beside the point that socket handling is rather
the tiny part of the problem.

> ...if I should use threads, what would be their purpose? One
> thread per user? One thread for users, one for game updates, one
> for mob updates, etc?

That's a very domain and platform specific set of questions.  It
really depends on what you are trying to do and your data sequencing
model.  

  However as a small note in the general case very large numbers of
  thread are a Bad Idea.  Most systems handle very large numbers of
  threads poorly if at all.

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