• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

calling submit from a thread pool in the same pool it belongs to

 
Ranch Hand
Posts: 113
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

I have an ExecutorService which I'm using to solve a recursive problem. Initially I call submit on this pool passing to it the entire task it has to solve. The task class implements Callable and its method call
makes some calculations and them breaks the problem into two pieces, which I want to solve using other threads on the same pool. So in the task constructor I pass a reference to the same pool so its call method
can call submit on the same pool so the two pieces can be solved by threads on the pool as well. My problem is that I want to call "get" to wait for the results. Obviously, if I have just one thread on the pool, for example,
it will call submit on the pool and then get, but it will wait forever since there are no other threads to run that task it submitted.
So, the bigger my problem is, the more I'll need threads in my pool. I have "solved" the problem by using a CachedThreadPool, which gave me another problem: it creates threads on demand which is not what I want either.
I want a pool with a fixed number of threads. Can you give a suggestion?
 
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, you can't do this.

Let's take a merge-sort as a typical example of this problem. Here's an implementation that looks reasonable, but is broken:
Since sorting the two halves of the array are disjoint problems, it stands to reason we can sort them concurrently; the first half as a new task for the thread pool, the second half by the current thread. When the current thread is done sorting, it waits for the thread pool to finish sorting the first half, and then it merges the two halves.

There's a problem with this approach though. Since the sorting is done recursively, each call will submit half of its part of the array to the thread pool. Sorting an array of length 8 means submitting 7 tasks to the thread pool. If the pool never has more than 6 threads available, it's likely the program will deadlock because threads in the pool will wait for deeper tasks to complete, which will never complete because there are no threads in the pool available to execute them.

Instead, you should tell the method the maximum amount of tasks it may submit, and halve the number for each recursive call. If a method call may not submit any more tasks to the thread pool, it should sort both halves in the current thread. Another solution is to communicate with the thread pool in a synchronized way to find out if there are idle threads that can execute a new task, but this may actually end up slowing down the entire process.
Disclaimer: I didn't compile or test any of the code in this post, so there may be loads of errors.
 
Stephan van Hulst
Bartender
Posts: 15737
368
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is some tested code that performs merge-sort using multiple threads. You specify a file, and optionally the number of threads and an insertion-sort threshold.

The program breaks the file up in tokens, sorts them and determines how long it took. You can specify the minimum size that sub-arrays need to be in order to use merge-sort, else insertion-sort is used; a threshold of 1 means a pure merge-sort.

On my system, using 8 threads and an insertion threshold of 16, it takes around 250 ms to sort about a million strings. This is almost twice as fast as using Arrays.sort() to sort the same tokens.
 
Ranch Hand
Posts: 291
Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What a lot of work, but it's already been done.

If you're using Java7, then look at the Fork/Join framework therein.

If you're not using Java7 or you want a superior product then look at the Fork/Join product:
TymeacDSE
 
Those cherries would go best on cherry cheesecake. Don't put those cherries on this tiny ad:
Smokeless wood heat with a rocket mass heater
https://woodheat.net
reply
    Bookmark Topic Watch Topic
  • New Topic