Deferring thread pool tasks until later

[JC2]

I have a thread pool that is constantly executing tasks from a work
queue. There is a finite number of threads in the pool.

Some of the tasks compete for certain resources (e.g. some tasks might
be database lookup tasks where there are only a small finite number of
database connections available, etc.), and therefore might not be able
to execute if there are not enough resources available.

Right now, what happens is some of the worker threads end up blocking
waiting for resources to become available when they actually could be
executing other tasks in the queue that are actually runnable instead.

I'd like the thread pool to be able to run tasks that *can* run while
waiting for tasks that can't run to become runnable, rather than
idling and doing nothing.

Low task latency is more important than throughput; the tasks produce
visible output in response to some real time input and must be
completed as soon as possible.

I'm having trouble getting my head around the work queue
implementation to support this. The first thing that came to mind was
simply putting non-runnable tasks back on the end of the queue. The
problem with this is I don't want these tasks to be at the end of the
queue -- I want them to be executed ASAP and if the queue is large,
this adds a lot of unwanted latency (and also for tasks competing for
the same resources, it really should be first come first serve).

Now I'm thinking maybe I can put the tasks on a second "deferred task"
queue, and if there's anything on that queue, execute it before
looking at the main queue. Instead of popping tasks off the front
immediately, in this deferred queue, just search for the first
runnable task and run and remove that. Does this seem reasonable?
Tasks that are deferred should be in the minority, relatively rare, so
performance penalties for searching through this queue (in the case
that there's a lot of tasks at the head that are not runnable for a
long period of time) shouldn't matter too much, since for the most
part, tasks won't be in this queue anyways. I think. I don't know;
what's the normal way to handle situations like this?

Thanks,
J

[David Schwartz]

One way that's often very simple is simply to create one thread for
each the limited resources. That thread then pulls a job from a
specific queue that holds only jobs that require that resource. That's
not always appropriate, as it may give too much priority to jobs that
require specific resources over ones that don't.

Another possibility is to have a "deferred" queue. A thread operates
as follows:

1) Is the "deferred" queue empty? If not, can we do the head job of
the deferred queue now? If so, do it.

2) Take the head job from the normal queue. If we can do it now, do
it. Otherwise put it on the tail of the deferred queue.

3) Go to step 2.

This may require more than one "deferred" queue for different
resources.

DS