• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
  • Campbell Ritchie
  • Bear Bibeault
  • Devaka Cooray
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Knute Snortum
  • Junilu Lacar
  • paul wheaton
Saloon Keepers:
  • Ganesh Patekar
  • Frits Walraven
  • Tim Moores
  • Ron McLeod
  • Carey Brown
  • Stephan van Hulst
  • salvin francis
  • Tim Holloway

Problem with hanging and more  RSS feed

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.
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
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.
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!