Win a copy of Murach's Python Programming this week in the Jython/Python forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Problem with hanging and more  RSS feed

 
Victor Bechev
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
First of all - hello to everyone.
I hope I don't write a very stupid first post but, you see, I've got this problem with threads...
I'm involved in a project that requires realization of BFS algorithm with multiple threads. Unfortunately I obviously did something wrong (or did not do something) and my program hangs one out of two times for bigger graphs (Fun fact: it either hangs on thread one or on thread three). The approach I adopted is making threads, each of which do a bfs and... well, I'll just show you and if you have any questions I'll elaborate.




As I said my program hangs and my theory is that either something with the tread management (workingThreads, threadMax) goes wrong or something concerning priority (for example if the main thread "eats up" all the processor time and doesn't let the thread I created do it's job and decrease the workingThreads counter. In the end I could just try with java.lang.Thread.activeThreads() but there is still the problem about efficiency. There is none. Yes, I do not gain any acceleration (bad choice of words, but it's late and English is not my mother tongue) when switching to >1 threads.
I hope this question and my code don't come out as stupid, but I'm not good at all with threads (and overall Java for now, but I'm trying ), sorry if they do.
Thanks in advance, even if just for baring with me.
 
Andrey Kozhanov
Ranch Hand
Posts: 79
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Victor, welcome to ranch!

I see two possible causes of hanging.

1. Did your bfs() method hang in one-theaded run? If yes, it's your problem;

2. Every changes to objects, visible to all threads, could be the cause of hanging, so try synchronizing access to such objects. So, your BFSThread.run() method should look like this:
 
Victor Bechev
Greenhorn
Posts: 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank you Andrey, synchronized helped with the hanging problem.
Stupid of me not to consider that.

Now if I could just deal with the efficiency problem, but I guess that's a more complex task.
For example, for a graph with 10000 nodes I get average execution times of around:
3.94s - single thread.
3.05s - 2 threads.
2.73s - 3 threads.
2.70s - 4 threads.
I think that the while in the main thread is taking too much processor time and I should use a mechanism of some sort to make the main thread rest while workingThreads==threadMax and only start when new threads are needed. But of course, that also depends of the implementation of my BFS algorithm and I won't bother you with that, but I'd appreciate any insight or hints on where in my code to look/touch in order to make multi-threading more efficient.

Thanks again.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!