 |
AppletTalk.com
Java discussions newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Thyme
Guest
|
 Posted: Fri Nov 21, 2003 8:19 pm Post subject: Thread question - multi-threaded behavior |
 |
|
Here's a java problem I'm trying to work through.
I wrote a program that solves a game a friend of mine calls the
"Cracker Barrel Game" because he remembers it from restaraunts of
that genre. There are 15 holes in a triangle with 14 pegs, as below.
0
p p
p p p
p p p p
p p p p p
You play by jumping over a peg and removing it, trying to get to just
one peg.
I implemented this with threads as follows:
I wrote a class "game" implementing runnable and - in the run method
- the object checks whether there is a valid move.
If there is, it checks for all valid moves, starting another thread
running game for each possible move.
If not, it checks whether this sequence of moves is better than the
last stored sequence of moves.
To keep track of things, every time an instance of game is
initialized, it increments a static variable and prints that out.
When it's done, the program prints out the answer it came up with.
The order in which the threads run is not gaurunteed. Since the
program regards any result with just 1 peg as a perfect game, I
expect it to get one of 15 acceptable answers.
What I didn't expect was that the number of threads run is different
every time - something like 15000 to 25000 threads.
The approach I've described should create the same number of threads
each time. It doesn't try to save cycles by making use of results
from one thread in another thread. Whether it creates a thread or not
does not depend on any other thread's result.
So, now I'm scratching my head. Here's where I need some ideas. Here's
some places where things might have gone wrong.
1. Maybe it does run the same number of threads, but not all of them
are printing out their numbers. The code isn't thread safe - although
I can't see how one thread affects another.
2. Maybe some of the threads are dying. If even one thread died -
without a trace - or didn't run to completion, it would have a huge
effect on the number of threads, since branches of the tree would be
lost.
Of course, it would have to happen for reasons non-deterministic with
respect to the code. Does the JVM ever drop a thread without an
exception?
3. I can't think of a number 3, but if you can, that would help.
I'm thinking of trying several things:
- Make a single threaded version. The point of the program, by the
way, is for me to do some threaded programming because, well, I have
too much time on my hands. If I get a single threaded version to run,
I would know what the multithreaded version was trying to do.
- Put a sleep in the code, right before starting each new thread. This
would make the number of threads running at once smaller and rule out
problems from massive multitasking (althought I thought Java wouldn't
have these problems.)
- Work through the game code to see if there's a mistake in
implementing moves. Maybe I screwed up and let the state of another
thread leak in (can't see how, but maybe it's there.)
Any other suggestions or information would be appreciated.
Tim Sherer
|
|
| Back to top |
|
 |
Eric Sosman
Guest
|
| Posted: Fri Nov 21, 2003 9:17 pm Post subject: Re: Thread question - multi-threaded behavior |
|
|
Thyme wrote:
| Quote: |
Here's a java problem I'm trying to work through.
I wrote a program that solves a game a friend of mine calls the
"Cracker Barrel Game" because he remembers it from restaraunts of
that genre. There are 15 holes in a triangle with 14 pegs, as below.
0
p p
p p p
p p p p
p p p p p
You play by jumping over a peg and removing it, trying to get to just
one peg.
I implemented this with threads as follows:
I wrote a class "game" implementing runnable and - in the run method
- the object checks whether there is a valid move.
If there is, it checks for all valid moves, starting another thread
running game for each possible move.
|
Oooogh. If one man can dig a posthole in five minutes,
three hundred can do the job in one second flat, right? I
hereby christen this approach "The Death Of A Thousand Cuts."
| Quote: | If not, it checks whether this sequence of moves is better than the
last stored sequence of moves.
To keep track of things, every time an instance of game is
initialized, it increments a static variable and prints that out.
When it's done, the program prints out the answer it came up with.
|
Is access to this static counter synchronized? If not,
you may be losing some of the increments:
Thread 1: fetch old value (42, say)
Thread 2: fetch old value (still 42)
Thread 2: store new value (43)
Thread 1: store new value (43)
Two attempted incrementations advance the counter only once.
Also, is the printing synchronized so that each thread
really prints its own value, and no other thread has an
opportunity to get in and change the value first?
| Quote: | The order in which the threads run is not gaurunteed. Since the
program regards any result with just 1 peg as a perfect game, I
expect it to get one of 15 acceptable answers.
|
When a thread achieves a perfect game, does it by any chance
call System.exit()? That would stop all the other threads in
their tracks, preventing them from creating additional sub-threads.
And it's indeterminate which thread might find a solution first.
| Quote: | What I didn't expect was that the number of threads run is different
every time - something like 15000 to 25000 threads.
The approach I've described should create the same number of threads
each time. It doesn't try to save cycles by making use of results
from one thread in another thread. Whether it creates a thread or not
does not depend on any other thread's result.
|
Is access to "the last stored sequence of moves" (see above)
synchronized?
| Quote: | So, now I'm scratching my head. Here's where I need some ideas. Here's
some places where things might have gone wrong.
1. Maybe it does run the same number of threads, but not all of them
are printing out their numbers. The code isn't thread safe - although
I can't see how one thread affects another.
|
The counter is one point of conflict, and perhaps the "stored
sequence" and/or the System.exit() call are others.
| Quote: | 2. Maybe some of the threads are dying. If even one thread died -
without a trace - or didn't run to completion, it would have a huge
effect on the number of threads, since branches of the tree would be
lost.
Of course, it would have to happen for reasons non-deterministic with
respect to the code. Does the JVM ever drop a thread without an
exception?
|
Yes, if the thread returns from its run() method. Or if
you call System.exit(). Or if you pull out the power cord ...
| Quote: | 3. I can't think of a number 3, but if you can, that would help.
I'm thinking of trying several things:
- Make a single threaded version. The point of the program, by the
way, is for me to do some threaded programming because, well, I have
too much time on my hands. If I get a single threaded version to run,
I would know what the multithreaded version was trying to do.
- Put a sleep in the code, right before starting each new thread. This
would make the number of threads running at once smaller and rule out
problems from massive multitasking (althought I thought Java wouldn't
have these problems.)
|
Java is a lot of things, but it isn't magic snake oil. If
massive parallelism and resource contention are inherent in your
program design, uttering the mystic word "Java" will not make
them disappear.
"Resource contention? But my threads hardly interact at
all!" Perhaps not explicitly, but your 25000 threads need
memory for 25000 thread stacks, and once they get it and start
running all 25000 of them contend for a presumably smaller set
of CPUs. The Java Virtual Machine runs on an Actual Physical
Machine, after all.
| Quote: | - Work through the game code to see if there's a mistake in
implementing moves. Maybe I screwed up and let the state of another
thread leak in (can't see how, but maybe it's there.)
|
Checking for bugs is a good idea in any case. Besides which,
you've already mentioned one definite inter-thread "leak" and at
least two others might be present.
| Quote: | Any other suggestions or information would be appreciated.
Tim Sherer
|
--
[email]Eric.Sosman (AT) sun (DOT) com[/email]
|
|
| Back to top |
|
|
Chris Smith
Guest
|
| Posted: Fri Nov 21, 2003 11:06 pm Post subject: Re: Thread question - multi-threaded behavior |
|
|
Hi Tim,
Thyme wrote:
| Quote: | 1. Maybe it does run the same number of threads, but not all of them
are printing out their numbers. The code isn't thread safe - although
I can't see how one thread affects another.
|
You just said that every new game instance created increments a static
variable. If you aren't protecting that static variable with
synchronization, then you are going to get unpredictable results.
| Quote: | 2. Maybe some of the threads are dying. If even one thread died -
without a trace - or didn't run to completion, it would have a huge
effect on the number of threads, since branches of the tree would be
lost.
|
Unless you're catching exceptions and ignoring them, you'd know if a
thread did not complete normally, because you'd see an exception stack
trace. Threads don't just disappear, except when you use System.exit,
but then you're not there to observe them disappearing either.
| Quote: | 3. I can't think of a number 3, but if you can, that would help.
|
Possibly you are inadvertently sharing some data structure, and the
threads are interfering with each other in random ways.
| Quote: | - Put a sleep in the code, right before starting each new thread. This
would make the number of threads running at once smaller and rule out
problems from massive multitasking (althought I thought Java wouldn't
have these problems.)
|
Given the combinatorial nature of the problem, this only seems like a
good idea if you have a few spare centuries to solve it. Nevertheless,
yes Java *does* have problems if you have too many threads and don't
properly synchronize their shared data. Java (actually, your operating
system, which Java relies upon) could also have a problem with so many
concurrent threads at all, but in that case I'd expect to see an
exception of some kind, such as java.lang.OutOfMemoryError.
| Quote: | Any other suggestions or information would be appreciated.
|
If you post the code, it will be easier for the rest of us to diagnose
the problem.
--
www.designacourse.com
The Easiest Way to Train Anyone... Anywhere.
Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
|
|
| Back to top |
|
|
Thyme
Guest
|
| Posted: Sat Nov 22, 2003 7:38 am Post subject: Re: Thread question - multi-threaded behavior |
|
|
Eric Sosman <Eric.Sosman (AT) sun (DOT) com> wrote
<SNIP>
| Quote: | To keep track of things, every time an instance of game is
initialized, it increments a static variable and prints that out.
When it's done, the program prints out the answer it came up with.
Is access to this static counter synchronized? If not,
you may be losing some of the increments:
Thread 1: fetch old value (42, say)
Thread 2: fetch old value (still 42)
Thread 2: store new value (43)
Thread 1: store new value (43)
Two attempted incrementations advance the counter only once.
Also, is the printing synchronized so that each thread
really prints its own value, and no other thread has an
opportunity to get in and change the value first?
|
This could be it - I can't find any duplicate numbers in the output -
and if this is the problem, the threads should be printing duplicate
numbers, since every game object prints a number - whatever value
the counter currently has.
I'll come up with a way to be sure there are no duplicates.
| Quote: |
The order in which the threads run is not gaurunteed. Since the
program regards any result with just 1 peg as a perfect game, I
expect it to get one of 15 acceptable answers.
When a thread achieves a perfect game, does it by any chance
call System.exit()? That would stop all the other threads in
their tracks, preventing them from creating additional sub-threads.
And it's indeterminate which thread might find a solution first.
|
No, there's no easy out. There is no System.exit(). If there's a
thread that can exist, I'm going to create it. If it's too big, I'll
find a smaller
problem to learn on.
| Quote: | "Resource contention? But my threads hardly interact at
all!" Perhaps not explicitly, but your 25000 threads need
memory for 25000 thread stacks, and once they get it and start
running all 25000 of them contend for a presumably smaller set
of CPUs. The Java Virtual Machine runs on an Actual Physical
Machine, after all.
|
I guess this what I'm really after.
No more than about 100 threads run at once (it prints out an
activeCount).
I'm expecting that, once a thread and all the threads spawning it and
spawned by it have run out, it will be garbage-collected away.
(Although,
I'm not sure how GC deals with multiple threads - I'll check into
that.)
If the JVM is overwhelmed by this design, no problem - as long as it
reacts
in a predictable manner, like a nice, clean error.
Because if there's no error, I have to assume the problem is in my
code -
which is a possibility.
Thanks - TS
|
|
| Back to top |
|
|
Thyme
Guest
|
| Posted: Sat Nov 22, 2003 7:40 am Post subject: Re: Thread question - multi-threaded behavior |
|
|
| Quote: | You just said that every new game instance created increments a static
variable. If you aren't protecting that static variable with
synchronization, then you are going to get unpredictable results.
|
This might be it - although the value of the static values does nto
affect how many threads are created, it could affect the output,
leading me to think fewer threads were created.
| Quote: | Unless you're catching exceptions and ignoring them, you'd know if a
thread did not complete normally, because you'd see an exception stack
trace. Threads don't just disappear, except when you use System.exit,
but then you're not there to observe them disappearing either.
That's why I'm puzzled. I'm not catching exceptions and they're nto showing |
at runtime. There's no exit.
| Quote: | - Put a sleep in the code, right before starting each new thread. This
would make the number of threads running at once smaller and rule out
problems from massive multitasking (althought I thought Java wouldn't
have these problems.)
Given the combinatorial nature of the problem, this only seems like a
good idea if you have a few spare centuries to solve it. Nevertheless,
|
yeah, that's why I came to the newsgroups before trying it.
| Quote: | If you post the code, it will be easier for the rest of us to diagnose
the problem.
|
No, I wouldn't put you though that. The game implementation code is pretty
klugey. The thread code is straight forward, but I don't understand threads
as well as I should.
Thanks for your help.
TS
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
