Thread pool configurations problems

Question

Note that I'm not talking about any specific implementation in any specific language.

Lets say I have a thread pool and a task queue. When a thread runs it pops a task from the task queue and handles it - that thread might add additional tasks into the task queue, as a result. The time the thread has to handle a certain task is unlimited - meaning the thread works until the task is finished and never terminates before that.

What kind of problems (e.g. deadlocks) each the following thread pool configurations are susceptible to?

Possible thread pool configurations I'm concerned with:
1) Unbounded task queue with bounded num. of threads
2) Bounded task queue with unbounded num. of threads
3) Bounded task queue with bounded num. of threads.
4) Unbounded task queue with unbounded num. of threads

Also - say that now the thread has a limited time to handle each task, and is forcibly terminated if it doesn't finish the task in the time frame that was given. How does that change things?

Answer 1

If you have a bounded number of threads then you can experience deadlocks if a task running on a pool thread submits a new task to the queue and then waits for that task --- if there is no free thread then the new task will not be run, and the original task will block, holding up the pool thread until the new task can run. If you end up with enough of these blocked tasks then the whole pool can deadlock.

This isn't really helped by bounding the number of tasks, unless the bound is the same as the number of threads --- once each thread is doing something then you can no longer submit new tasks.

What does help is either (a) adding new threads when a thread becomes blocked like this, or (b) if a pool thread task is waiting for another task from the same pool then that thread switches to running the task being waited for.

If you have an unbounded number of threads then you have to watch out for oversubscription --- if I have a quad-core machine, but submit 1000 tasks, and run 1000 threads then these will compete with each other and slow everything down.

In practice, the number of threads is bounded to some large number by the OS either due to a hard-coded number, or due to memory constraints --- each thread needs a new stack, so you can only have as many threads as you've got memory for their stacks.

You can always get a deadlock with 2 tasks if they wait for each other, regardless of any scheme you use, unless you start forcibly terminating tasks after a time limit.

The problem with forcibly terminating tasks is twofold. Firstly, you need to communicate to any code that was waiting for that task that the task was terminated forcibly rather than finished normally. Secondly (and this is the bigger issue) you don't know what state the task was in. It might have owned a lock, or any other resources, and forcibly terminating the task will leak those resources, and potentially leave the application in a bad state.