Help with a task scheduling algorithm

Question

I am working on an application in which thousands of tasks associated with hundreds of devices, each task requiring, < 5ms to begin execution, and taking on average 100ms to complete.

The conditions are as such:

1. Each device can only process a single task at a time, e.g., one task must finish running on its assigned device prior to subsequent task's being processeed.
2. The scheduler should be efficient. Currently, processing a given device's work queue takes longer than the sum of it's tasks.

Here is basic description of the current implementation:

Each device contains a work queue which is filled with tasks associated with that device.

When a task is enqueued, that device's work queue is placed into a global run queue (a queue of queue's). The global run queue is consumed by a worker thread which dequeue's the device's task objects, processes one, then places the device queue at the back of the global run queue. When that given device has been dequeued again, the worker thread checks to see if the task has completed, if so, the next task is executed. This process continues, until all device queues have been depleted of tasks in the global runqueue.

Any suggestions for improvements? Have I stated this clearly? If not, please let me know, and I'll do my best to clarify.

Thanks for taking the time to look this over. Regards.

Answer 1

How about something like the ExecutorCompletionService together with a ThreadPoolExecutor. This gives you callback on completion, which you can use to submit subsequent jobs, and a managed threadpool of executors, which you can tweak to improve throughput.

I suggest you run your code through a profiler to see which threads are currently blocking (sounds like it will be your producer device threads). I can recommend YourKit Java Profiler, however its not free.

Answer 2

The problem with your design is that only one task is run at a time, which means that any device is idle while any other device is in use.

Since there are hundreds of devices, it would probably not be a good idea to assign a thread to each of these devices, but a thread pool could very well be used.