Boost logo

Boost :

From: vicente.botet (vicente.botet_at_[hidden])
Date: 2008-06-09 14:52:21


----- Original Message -----
From: "Kowalke Oliver (QD IT PA AS)" <Oliver.Kowalke_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, June 09, 2008 1:53 PM
Subject: Re: [boost] [thread-pool/futures] Explicit yielding

> For what would be 'task-stealing' be usefull?
> Wouldn't be one task-queue on which worker threads are waiting be
> sufficient?

It may be sufficient, but it can be ineficient.

> Polling of one thread in task-queues of other threads seams to be
> expensive.

You are right, the main raison this is expensive is that we need to
synchronize the access to this shared resource. But this is already the case
when we have only one task-queue.

I think that the quiz is that we need to manage the root-task (without
parent) and the sub-task (with a parent task) differently. root-task must be
handle in fifo order, but sub-tasks are needed to complete other tasks, so
they need to be handled in lifo order.

So a worker thread will take a root-task at a time in fifo order. If the
task needs to wait for the result of another task, the worker thread will
handle the tasks in the task-stack in lifo order, checking if the future is
ready. When there are no more tasks in the task-stack and the future is not
ready, the worker thread can either wait explicitly on the future or try to
execute other tasks. We can either take a new root-task or a sub-task of
another worker thread. But what we can do when there are no new root-tasks?
we can take a sub-task of the other worker threads. Even if this is
expensive this avoid to let a working thread in a waiting state. Only when
there are no more task to do the working thread will wait on the future. In
addition some optimizations can be applied becuase the owner of the
task-stack use it on lifo order but the others use it on fifo order (so it
needs to be a dequeue).

I hope this will help you to understand for what would 'task-stealing' be
Anyway a reading of the FJTask article, or the tasks in Threading
Building Blocks (TBB) will be worthwhile.

Vicente Juan Botet Escriba

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