Boost logo

Boost :

Subject: [boost] [threadpool] sub_tasks and active waiting
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-09-12 02:17:55


How can I define pool so the following code do not deadlocks?

???? pool;

int fib_seq(int n) {
    if (n <= 1) return n;
    else return fib_seq(n−1) + fib_seq(n−2);
void fib_par(int n) {
    if (n <= 5) // granularity ctl
        return fib_seq(n);
    else {
        tp::task<int> t1(pool.submit(bind(fib_par, n-1));
        tp::task<int> t2(pool.submit(bind(fib_par, n-2));
        return t1.get_future().get() + t2.get_future().get();

int main() {

    return fib_par(10);

Well, we can see that the number worker threads depends on the fib_par
parameter. As soon as the fib_par function waits on its sub_tasks t1 and t2,
the worker thread cannot handle other tasks, so we need a thread available
for fib_par(9) and fib_par(8). When this worker thread call fib_par(9) after
launching fib_par(8) and fib_par(7) will be blocked to manage other task,
... Evidently this do not scale very well, so we can not use the threadpool
library to address this kind of problems, in which the tasks is split on
sub-task launched to be run in parallel, and the the parennt task waits on
its child sub-task to do somthing.

IMO, what we need is that instead of creating a task we create a subtask.
When the function will wait until the results of its subtasks are ready, we
don't need to block the worker thread, instead we can implement replace the
pasive wait by an active one, which will check if the waited task is ready
and if this is not the case it will do a scheduling step on the associated
thread pool and check again.

void fib_par(int n) {
    if (n <= 5) // granularity ctl
        return fib_seq(n);
    else {
        tp::sub_task<int> t1(pool.submit_subtask(bind(fib_par, n-1));
        tp::sub_task<int> t2(pool.submit_subtask(bind(fib_par, n-2));
        return t1.get() + t2.get();

The submison of a sub_task can be done differently of a task, because there
is a parent task that will be waiting for the end of the sub_task, so maybe
we can add it on LIFO order.

Do you think that this is an interesting feature for your library? could it
be integrated in your library without disruption?

Vicente Juan Botet Escribá

Boost list run by bdawes at, gregod at, cpdaniel at, john at