[MUD-Dev] Question about multithreaded servers

[Greg Underwood]

It's been a while since I posted, so "howdy" to everyone.  I've been
lurking since I got back from Europe, but this thread (pardon the pun)
caught my eye.

At 08:34 AM 1/18/00 -0600, "Fabian" <lemkef at execpc.com> wrote:
>
>> -----Original Message-----
>> From: Jon A. Lambert [mailto:jlsysinc at ix.netcom.com]
>>
>> Fabian wrote:
>> >
>> > I suppose just by making a simple requirement that
>> > all objects must be secured at the begining of the
>> > script would take care of that.

No, that's not true.  Just because you attempt to lock everything before
you execute the script doesn't mean you avoid deadlocks.  Deadlocks occur
when the following happens:

	Thread 1 - Get Lock 1 - ok
	Thread 2 - Get Lock 2 - ok
	Thread 1 - Get Lock 2 - block
	Thread 2 - Get Lock 1 - block

Both threads block on their second calls to get the locks that the other
thread has.  The reason this occurs is that they both grabbed the locks in
a different order.  Thread 1 attempted to get Lock 1 and then 2, while
Thread 2 attempted to get Lock 2 and then 1.  No matter when this occurs in
your script execution process, you will get a deadlock.  Simply moving the
attempts to get the locks to before the script executes does nothing to
prevent that order of events.  The OS can still preempt any thread at any
time, and grabbing the locks in a different order will open your code to
deadlocks.

The only way to gaurentee you will not get a deadlock is to ALWAYS have
EVERY thread attempt to obtain the same locks in the same order.  In that
case, this is what happens:

	Thread 1 - Get Lock 1 - ok
	Thread 2 - Get Lock 1 - block
	Thread 1 - Get Lock 2 - ok
	Thread 1 - execute required stuff
	Thread 1 - Release Lock 2, release Lock 1
	Thread 2 - Unblocks, having gotten Lock 1
	Thread 2 - Get Lock 2 - ok
	Thread 2 - ...

Thread 2 will never deadlock once it comes out of getting Lock 1 because
any other thread that requires both Lock 1 and Lock 2 will be blocked on
the 'Get Lock 1' call, w/o having Lock 2.  When the OS decides to preempt
has no effect on which locks you can get.

BTW, I had it realease the Locks in reverse order, simply to avoid minor
thrashing.  Assume you release Lock 1 and then 2, but when you release 1,
the OS wakes another thread that is waiting on 1.  This thread then
attempts to get Lock 2, and blocks again.  The OS then has to switch
control back to the original thread to realease Lock 2, and then switch
control back to the second thread again to get Lock 2.  Releasing in
reverse order will prevent those minor, but time consuming context switches.

>>
>> Not a simple requirement though.  How about this sort of script construct:
>>
>> for player in connected
>>    player.message("How about some spam!?!")
>> endfor
>>
>> Do you lock every player object in the connected list?
>> Would the above method be an atomic transaction requiring
>> completion of all events it would generate?
>> Or would you spawn a new event to each player object,
>> and not worry about completion thus making the method
>> above non-atomic?

Good question, but more one of starvation than deadlock.

>> And what about guaranteeing event sequence?
>>
>> for player in connected
>>    player.message("LINE 1")
>>    player.message("LINE 2")
>>    player.message("LINE 3")
>> endfor
>>
>> Perhaps when sending "LINE 1" the lock cannot be achieved and
>> is rescheduled or terminated.  So the Player receives:
>>
>> "LINE 2"
>> "LINE 3"
>> "LINE 1"
>>
>> Just a few things to think about.  :)

This is what grabbing all the locks prior to script execution will get you
(as opposed to a gaurentee of no deadlocks).  Grabbing them all in advance
will insure that you will get the messages in the right order.  However, as
Jon was attempting to point out above, when your script requires that you
grab a zillion locks, you can run into some serious starvation issues.

-Greg




_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev