[Home] [Downloads] [Search] [Help/forum]

Gammon Software Solutions forum

See www.mushclient.com/spam for dealing with forum spam. Please read the MUSHclient FAQ!

[Folder]  Entire forum
-> [Folder]  SMAUG
. -> [Folder]  SMAUG coding
. . -> [Subject]  Who knows windows threads (or any threads)
Home  |  Users  |  Search  |  FAQ
Username:
Register forum user name
Password:
Forgotten password?
(New message)
Subject: Who knows windows threads (or any threads)
Name:
Your forum user name.
Register forum user name
Password:
Your forum password.
Forgotten password?
Message:
Message to be posted (in English, please).
Forum codes:
Check this if your message uses 'forum codes' or templates (auto-detected for new posts).
Forum codes Templates

Save this message ...

Subject review (reverse sequence)

Pages: 1 2  

Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Mon 12 Nov 2007 09:51 PM (UTC)  [ quote  ]
Message
Quote:

Always (always!) take locks in the same order.


I agree that to solve deadly embrace situations, you won't get them if you take locks in sequence. That is, if each possible lock is numbered, and you can only lock a higher number than you currently hold. That way, lock 1 can take lock 2, but lock 2 can't take lock 1.

However this can be easier said than done, and also relies on discipline by the programmer, I don't think it can be enforced in any useful way.

Quote:

Ideally if the lua thread wanted the network thread to do something, it would dispatch a message to the thread and then give up the lua lock and block until it had received a response.


If the Lua lock is on the whole Lua script engine, it isn't really meaningful to talk about a Lua script giving up the Lua lock - either the Lua script engine is locked or it isn't.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by ThomasWatts   USA  (66 posts)  [Biography] bio
Date Mon 12 Nov 2007 09:34 PM (UTC)  [ quote  ]
Message
Yeah, this is why I asked for some help. You all know quite a bit more about thread theory then I do. Thanks.
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Mon 12 Nov 2007 10:45 AM (UTC)  [ quote  ]
Message
I'm not sure why the is/like distinction is really that important, but I chose to use the word "like" and not "is" because it is a concrete instantiation of the problem illustrated by the dining philosophers. But anyhow, I don't think we're talking about the same thing... Some deadlocks cannot be solved by taking locks in the right order. Sometimes the fundamental design of the system is just wrong.

Thread 1:
Holds lock 1. Sends a message to Thread 2. Waits for response.

Thread 2:
Notices message. Grabs lock 1. Oops.

The problem here is that t1 is keeping its lock while waiting for t2 to do its thing, and t2 needs t1's lock. No amount of choosing locks in the right order will solve this. You'd need t1 to release its lock while letting t2 do its thing.

Besides, occasionally you need to hold two locks at once, so it's not always an option to have a strict protocol of only holding one lock at a time and acquiring them in a specific order. (Of course, that often helps. It's just not a solve-all solution.)

And yes, the message solution is as I suggested a better way of designing the system.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Isthiriel   (111 posts)  [Biography] bio
Date Mon 12 Nov 2007 08:49 AM (UTC)  [ quote  ]

Amended on Mon 12 Nov 2007 08:58 AM (UTC) by Isthiriel

Message
Quote:
David Haley wrote:
I believe he was describing a situation where the Lua thread needs to lock on the networking thread, and then the networking thread needs to lock on the Lua thread. Poof, deadlock. So no, it can't be solved by reentrant locks. It's a classic deadlock problem, like dining philosophers.

I just remembered why I've never had this problem before :P (and it's not like dining philosophers, it is dining philosophers, with two philosophers and two chopsticks)

Always (always!) take locks in the same order.

The same advice applies for semaphores, mutexes &c..

In this case, I think the network lock is less likely to be taken at any given time, so if you want to have both the network lock and the lua lock, you need to take them in that order. If you already have the lua lock (and don't have the network lock), you release the lua lock, take the network lock then retake the lua lock.

You never have a deadlock. You have to be more careful with the state when you release the lua lock (so you can grab the network lock) because you will be preempted at that point by a thread that has the network lock and wants the lua lock.


... and I still contend Nick meant the lua thread would call a network function (send_to_buffer or something) that threw a lua exception (buffer overflow perhaps) without involving the network thread at all, a problem which would be solved by using reentrant locks.


Ideally if the lua thread wanted the network thread to do something, it would dispatch a message to the thread and then give up the lua lock and block until it had received a response. The networking thread (when it woke up) would take the networking lock, check its messages, do what the lua thread wanted (without ever taking the lua lock), dispatch the result back to the lua thread, release the network lock and go back to sleep. The lua thread would then wake up, take the lua lock and merrily go about its business.

... which actually makes both the lua lock and the networking lock redundant since the synchronization is handled by the (implied) message-queue lock, which just goes to show the first rule of inter-thread communication is to minimize the data that needs to be synchronized (in this case going from the network state and the lua state to just the message queue between the two threads).
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Mon 12 Nov 2007 07:25 AM (UTC)  [ quote  ]
Message
Quote:
Isthiriel:
A single-threaded application can occupy, at most, one core. A dual core system will never see the global utilization rise above 50% because one core will always be idle. :P

Well, sure, but that's not a problem unless you often run at full capacity and you can parallelize that task to begin with. :)

Quote:
Isthiriel:
Aim for oodles of commands per second because it's usually harder to fix performance issues after-the-fact when the mud is sitting with a longterm average > 60% utilization and lagging all the players than when you're in the preliminary design/implementation phase.

I'm not sure that's true. On the contrary, having such high utilization lets you run profiling to figure out where you're actually spending your time. Of course, you should be profiling during development, too, but it's hard to simulate "actual load" until you've seen, well, actual load. As the saying goes, premature optimization is the root of all evils.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by Isthiriel   (111 posts)  [Biography] bio
Date Mon 12 Nov 2007 06:39 AM (UTC)  [ quote  ]

Amended on Mon 12 Nov 2007 08:56 AM (UTC) by Isthiriel

Message
Quote:
ThomasWatts wrote:
I was using pathetic boolean checks for locks and a message queue for when the locks were engaged. I tried either/or and a system of both, and neither solved the eventual problem of race conditions. It was alot of hassle that I decided to not deal with at the time.

You need at the absolute minimum an atomic (un-preemptable, no other thread or process can do anything meanwhile) test-and-set function to attempt to implement a lock yourself, if you don't have that then you're just moving the race condition around.

Usually whatever library provides that will also provide higher level constructs, like mutexes, reentrant locks, bounded semaphores ...

EDIT: I just proved myself wrong on this point *sigh*.
While looking for something else I found Wikipedia's explanation of Test-and-Set (http://en.wikipedia.org/wiki/Test-and-set) which has a link to "Peterson's Algorithm" (http://en.wikipedia.org/wiki/Peterson's_algorithm) and while I don't remember it being called that, I do remember being taught it (or at the least the flag/turn bit and the three criteria) at some stage.

Quote:
David Haley wrote:
(In other words, there's no reason to be multi-threaded just because you have several processors.)

A single-threaded application can occupy, at most, one core. A dual core system will never see the global utilization rise above 50% because one core will always be idle. :P

Quote:
David Haley wrote:Still, you would need some kind of synchronization, depending on what exactly is being done.

Just add the UDP listen port to the select() call that waits for player input and process it when it arrives?

Quote:
David Haley wrote:
I suspect that the term "stackless" is something of a misnomer, because each of these "tasklets" (in Python terminology) would have their own stacks, no?

The name "Stackless" is because they removed the underlying C stack, so while Python frames may be part of a Python stack, Python function calls don't add or remove from the C stack.

Quote:
Nick Gammon wrote:
I think there is a slight misunderstanding here. The way you have written that, you are saying the server should handle 1000/commands/sec overall (not per player) to give 5 commands/sec for a single player, if the playerbase is 200.

I don't think you need to design in to handle 1000 commands/sec/player as that seems to me to be abuse of the server. How many genuine players are going to enter 1000 commands in one second?

None, the only way 1000 cmds/sec is useful is as a poor method of benchmarking and/or profiling the server. Having said that, I can't really think of a better way :-/

Aim for oodles of commands per second because it's usually harder to fix performance issues after-the-fact when the mud is sitting with a longterm average > 60% utilization and lagging all the players than when you're in the preliminary design/implementation phase.

(The disadvantage of using 1000 cmd/sec/1 player [or 2 players or 3 players] as a test to see how well the server copes with a large number of commands/sec from a number of players is because a larger number of players is going to be scattered all over the world and have a more varied inventory which affects the performance of processor/memory caching.)
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Mon 12 Nov 2007 05:49 AM (UTC)  [ quote  ]
Message
Quote:

Two threads, one networking, one lua, both calling lua code.


Like I said, I would expect that to fail, without considerable effort put into synchronizing. However, remember you can have multiple Lua states (as I do in my Smaug task system), so if each subsystem called a separate Lua state there would be no problems, or less anyway.
- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Mon 12 Nov 2007 05:43 AM (UTC)  [ quote  ]
Message
Quote:
I believe Lua is supposed to be potentially thread safe, although there may be compile-time considerations.

I think the stuff is there, you just have to turn it on and tell it what functions to call for locking. I think the Lua coroutines are very close to being actual threads. In any case it does require a different compilation of the core, if memory serves.

But yes, Lua is by default not at all thread-safe, and you need to manage the synchronization on your own. But Lua is supposed to be reentrant, in the sense that if you have two threads each running their own Lua states, everything is (supposed to be) ok. Problems only come up when two threads need to talk to the same state.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by ThomasWatts   USA  (66 posts)  [Biography] bio
Date Mon 12 Nov 2007 04:38 AM (UTC)  [ quote  ]
Message
On windows Lua has proven to me to not be thread-safe. Two threads, one networking, one lua, both calling lua code. With no sync both threads would eventually trash each others stack resulting in string constants becoming nils, functions becoming numbers, etc. At least, that's what I experienced.
[Go to top] top
Posted by Nick Gammon   Australia  (18,770 posts)  [Biography] bio   Forum Administrator
Date Mon 12 Nov 2007 04:03 AM (UTC)  [ quote  ]
Message
Quote:

Every command should take some "time" to enact, you might be able to handle 1000 commands/sec/player (and it's something to aim for, since 1000 commands/sec on a playerbase of 1 is only 5 commands/sec on a playerbase of 200) ...


I think there is a slight misunderstanding here. The way you have written that, you are saying the server should handle 1000/commands/sec overall (not per player) to give 5 commands/sec for a single player, if the playerbase is 200.

I don't think you need to design in to handle 1000 commands/sec/player as that seems to me to be abuse of the server. How many genuine players are going to enter 1000 commands in one second?

Quote:

Python has an implementation called "Stackless", I don't know if Lua has something similar?


It is fundamental to Lua that each script coroutine has its own "Lua" stack, I am not sure if this is exactly what you mean.

I believe Lua is supposed to be potentially thread safe, although there may be compile-time considerations. For example, the default I believe is to use malloc and free, and I am not sure if they are thread reentrant.

In any case, depending on your design, if you preempted a Lua script execution, and then did something else with the script state, I would personally expect it to crash. A script is supposed to run until it releases control. Obviously process-level preemption would occur all the time, but at a thread level I would be cautious, if the preempting thread does anything at all with the script state - or indeed, if it alters the execution of a C routine that the script has called.

Here is an example of what I am talking about. Say we have a Lua script like this:


if mob_exists (12345) then
  move_mob (12345, 567)  -- move to different room
end -- if


Now imagine that a thread preemption occurs after the 'if' is successfully tested, but which then deletes the mob. That way the results of the if are incorrect, unknown to the script.

- Nick Gammon

www.gammon.com.au, www.mushclient.com
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Sun 11 Nov 2007 11:46 PM (UTC)  [ quote  ]
Message
Quote:
Isthiriel:
That's what reentrant locks are for.

I believe he was describing a situation where the Lua thread needs to lock on the networking thread, and then the networking thread needs to lock on the Lua thread. Poof, deadlock. So no, it can't be solved by reentrant locks. It's a classic deadlock problem, like dining philosophers.

Quote:
Isthiriel:
Or if you're mud is processor intensive (lots of scripting code, lots of players, mccp, physics?) AND it running on a multi-core (or multi-processor) box.

Ideally, you want 1 thread/processor core.

Well, only if it actually matters. You don't need threads unless you're doing long, blocking operations during which the rest of the program needs to keep on going. Just because you have a bunch of cores doesn't mean you should spawn one thread for each of them. (In other words, there's no reason to be multi-threaded just because you have several processors.)

Quote:
Isthiriel:
Can't that be done asynchronously? Most of the time taken is blocking waiting for a response from the DNS server?

Yes, in fact that's what I believe FUSS 1.8 does. Still, you would need some kind of synchronization, depending on what exactly is being done.

Quote:
Isthiriel:
Python has an implementation called "Stackless", I don't know if Lua has something similar?

Yes, they call them coroutines. But they're not "stackless"; each coroutine still has its own stack. I suspect that the term "stackless" is something of a misnomer, because each of these "tasklets" (in Python terminology) would have their own stacks, no?

Quote:
ThomasWatts:
I was using pathetic boolean checks for locks and a message queue for when the locks were engaged.

Well that's not going to work. :-P You need to use the actual synchronization primitives like semaphores and locks (aka mutexes). Whatever threading library you're using will provide something like that.
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by ThomasWatts   USA  (66 posts)  [Biography] bio
Date Sun 11 Nov 2007 11:13 PM (UTC)  [ quote  ]
Message
That's why I was asking about who knew what about threads and thread control. I know very little about the subject beyond simple thread creation and non-interacting threads. Mainly from when I was taking college classes few too many years ago.
I was using pathetic boolean checks for locks and a message queue for when the locks were engaged. I tried either/or and a system of both, and neither solved the eventual problem of race conditions. It was alot of hassle that I decided to not deal with at the time.
Also about being stackless, lua is not. Each C function has a stack available of at least 20 in size. However, when you are using the same lua state, you use the same lua stack. So when the inevitable happens the C statements end up altering the same stack. So bad st*ff happens.
[Go to top] top
Posted by Isthiriel   (111 posts)  [Biography] bio
Date Sun 11 Nov 2007 11:03 PM (UTC)  [ quote  ]

Amended on Sun 11 Nov 2007 11:06 PM (UTC) by Isthiriel

Message
Quote:
ThomasWatts wrote:
Separated the networking and the lua into two threads. One for the networking, and one for the lua world. Both do things and then sleep, the networking runs at 4 pulses a second, the lua 2.

I don't know why you would want pulses for the networking or the lua.

The big advantage of a thread-driven model is you don't have to have a polling loop. The network code can sleep (select()) until it has input to process and the lua game state should be mostly event driven?

Quote:
Nick Gammon wrote:
For example, if the Lua lock is taken, and then calls the network code (eg. to send a message) and some error condition arises that needs to execute Lua code, then the Lua lock is already taken and the whole process halts.

That's what reentrant locks are for.

Though if you are doing threading the lua code should dispatch an event to the network code, release its locks and sleep until the response is ready? (Or otherwise keep itself occupied doing other stuff rather than blocking until the network code is finished.)

Quote:
David Haley wrote:
I agree though that this adds a lot of complexities and it's worth thinking why exactly you want to break it into threads. In general, you need threads in the following kind of situation:

Or if you're mud is processor intensive (lots of scripting code, lots of players, mccp, physics?) AND it running on a multi-core (or multi-processor) box.

Ideally, you want 1 thread/processor core.

Quote:
David Haley wrote:
Classic example is a GUI application with some processing going on where it needs to remain responsive to e.g. a cancel button being pressed.

The definition of "responsive" varies too, a GUI should respond in less than 1/10 of a second, but a MUD that might have a ping of up to 300ms can be called "responsive" if it takes 2-3 seconds between entering a command and seeing it enacted.

Quote:
David Haley wrote:
In MUD terms, what operations are you running that take a long time? I can only think of one, really: the reverse IP lookup, which sometimes stalls the game for many seconds at a time.

Can't that be done asynchronously? Most of the time taken is blocking waiting for a response from the DNS server?

Quote:
Nick Gammon wrote:
And in fact you could make a case for throttling the server, in the sense that, if you carefully write it to be really really responsive, then it could handle 1000 commands per second spewed out by a client bot, to the disadvantage of "real" players.

Every command should take some "time" to enact, you might be able to handle 1000 commands/sec/player (and it's something to aim for, since 1000 commands/sec on a playerbase of 1 is only 5 commands/sec on a playerbase of 200) but you should only allow a queue of 20 or so commands and each command should take at least 1/16 of a second (for preference changes or other OOG things that translate into a single function call) up to 4 or 5 seconds (for time consuming IG activities... searching, digging, expensive spells, repairing, crafting). Longer than 5 seconds where the game seems unresponsive (because your character is busy) can be problematic :(

Quote:
ThomasWatts wrote:
As it stands I'm just going to see how a single thread goes for now. Input 4 times a second, and the world tick 2 times everything shouldn't get bogged down unless I really write some terrible lua. We shall see in the future.
If anyone else tries for multi-threaded, I'm sure all of us will want to know how it goes.

Python has an implementation called "Stackless", I don't know if Lua has something similar?

Stackless is single threaded BUT provides lots of tools for cooperative multitasking with "microthreads" or "green threads". The idea is that instead of being preempted by the OS scheduler, individual tasklets hand off to each other so you don't need to worry about locks because there is only one thread, and you get all the advantages (except multi-processor use) provided each tasklet hands off the execution when it no longer needs it (or periodically even if it does).
[Go to top] top
Posted by David Haley   USA  (3,881 posts)  [Biography] bio   Moderator
Date Sun 11 Nov 2007 10:34 PM (UTC)  [ quote  ]
Message
Just to double-check, what kind of synchronization were you using with these?
David Haley aka Ksilyan
Head Programmer,
Legends of the Darkstone

http://david.the-haleys.org
[Go to top] top
Posted by ThomasWatts   USA  (66 posts)  [Biography] bio
Date Sun 11 Nov 2007 11:37 AM (UTC)  [ quote  ]
Message
As of this moment, after try number three, it seems too much hassle.
The first try was documented above.
The second try was the message system mentioned in my previous post. The race conditions just moved from lua stack corruption to linked pointer corruption (although it took a lot of alt-tabbing and keyboard mashing for this to happen). I perhaps could have done message passing different, but that's just what I tried.
The third try as of 30 minutes ago was a rather simplistic locking mechanism. The best of the three tries to be sure, but it didn't seem to always work 100%. As with try #2, if I knew more about threads and race conditions, perhaps this could have worked.
As it stands I'm just going to see how a single thread goes for now. Input 4 times a second, and the world tick 2 times everything shouldn't get bogged down unless I really write some terrible lua. We shall see in the future.
If anyone else tries for multi-threaded, I'm sure all of us will want to know how it goes.
[Go to top] top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.

5,982 views.

This is page 1, subject is 2 pages long: 1 2  [Next page]

[Reply to this subject]  Reply to this subject   [New subject]  Start a new subject   [Refresh] Refresh page

Go to topic:           Search the forum

[Go to top] top

[Home]

Written by Nick Gammon - 5K

Comments to: Gammon Software support
[RH click to get RSS URL] Forum RSS feed ( http://www.gammon.com.au/rss/forum.xml )

[Best viewed with any browser - 2K]    [Internet Contents Rating Association (ICRA) - 2K]    [Web site powered by FutureQuest.Net]