Work/Task Stealing ThreadPoolExecutor

Question

In my project I am building a Java execution framework that receives work requests from a client. The work (varying size) is broken down in to a set of tasks and then queued up for processing. There are separate queues to process each type of task and each queue is associated with a ThreadPool. The ThreadPools are configured in a way such that the overall performance of the engine is optimal.

This design helps us load balance the requests effectively and large requests don't end up hogging the system resources. However at times the solution becomes ineffective when some of the queues are empty and their respective thread pools sitting idle.

To make this better I was thinking of implementing a work/task stealing technique so that the heavily loaded queue can get help from the other ThreadPools. However this may require implementing my own Executor as Java doesn't allow multiple queues to be associated with a ThreadPool and doesn't support the work stealing concept.

Read about Fork/Join but that doesn't seem like a fit for my needs. Any suggestions or alternative way to build this solution could be very helpful.

Thanks Andy

Answer 1

Executors.newWorkStealingPool

Java 8 has factory and utility methods for that in the Executors class: Executors.newWorkStealingPool

That is an implementation of a work-stealing thread pool, I believe, is exactly what you want.

Answer 2

Have you considered the ForkJoinPool? The fork-join framework was implemented in a nice modular fashion so you can just use the work-stealing thread pool.

Answer 3

you could implement a custom BlockingQueue implementation (i think you mainly need to implement the offer() and take() methods) which is backed by a "primary" queue and 0 or more secondary queues. take would always take from the primary backing queue if non-empty, otherwise it can pull from the secondary queues.

in fact, it may be better to have 1 pool where all workers have access to all the queues, but "prefer" a specific queue. you can come up with your optimal work ratio by assigning different priorities to different workers. in a fully loaded system, your workers should be working at the optimal ratio. in an underloaded system, your workers should be able to help out with other queues.