[boost] [task]

Subject: [boost] [task]
From: Baxter Jeremy (JWBAXTER_at_[hidden])
Date: 2009-10-02 08:06:13

I have been looking at the boost task library from the vault and
comparing it with the threadpools library
http://threadpool.sourceforge.net and have a few comments.
Firstly I should say that I'm interested in tasks / thread pools for a
situation rather different from the one for which they are designed.
Namely the case in which threads (tasks) are being used to monitor some
internal or external activities and so may block for significant periods
of time waiting for the result of a complex planning algorithm or for
some condition being met.
I'm therefore worried about blocking all the available threads. I think
what I need is to be able to dynamically add new threads to the thread
pool, or just not use a pool at all and create and destroy a thread for
every subtask.
However during my review I came across a helper function which I though
might allow re-use of the same thread but I'm concerned could actually
lead to deadlock:
reschedule_until
<file:///D:\Boost\boost.task-0.3.0\doc\html\boost_task\utilities.html>  
In the function boost::this_task::reschedule_until( Pred const&) allows
to synchronize the task with other asynchronous events without blocking
the worker-threads (bool Pred::operator()() must not block). The current
task will be rescheduled until the passed predicate becomes true. 
Looking at the code I don't think this is an accurate description and
gives the potential to introduce deadlocks in tasks which otherwise
would operate normally. 
>From the code what reschedule_until does is repeatedly call the process_
function to look for new tasks, testing once each task has finished to
see if the predicate has been met. This is not quite as described since
the task is not 're-scheduled' it is actually blocked until whatever
task the scheduler next selects is complete.
This introduces problems if multiple tasks on the queue use
reschedule_until. If there are three tasks T1 T2 and T3 on the queue
doing the following:

T1
{
...
Reschedule_until(A)
B.setTrue()
...
}

T2
{
...
Reschedule_until(B)
...
}

T3
{
...
A.setTrue()
}

What we would like to happen, and what will happen if they are run in
different threads (or a different order on the one thread) is that T1
does some work, waits for T3 then terminates. T2 does some work, waits
for T1, then does some more work. T3 independently does its work and
finishes by signalling that T1 can continue.

Unfortunately if they are scheduled in the order T1 T2 T3 then T1 runs,
reschedules and T2 gets to run until it reschedules and T3 gets to run.
When T3 finishes T1 is in a position when it can run, however it will
not get the chance to because in order for condition A to be checked T2
has to have finished, and it can't do that until B is set true.
Therefore although progression should be possible as the condition T1 is
waiting for has been met it will never notice and T1 and T2 will never
complete.

I'm not sure that there is a general solution to this problem without
using more threads so that any potentially runnable task will get a
chance.

A second comment.

Comparing the task and thread pool libraries they use different waiting
mechanisms. Thread pool uses a wait-notify construct on the queue to
block worker threads if the queue is empty. Task uses active polling,
trying to get items from the queue and then sleeping for a short period
if nothing can be found on the queue. I wondered why the difference is
there. Wait - notify would look like it should perform better in the
case where there are fewer tasks than threads is polling better in the
case where there are many more tasks than threads and so threads will
never sit idle polling for long?

Jeremy

Jeremy Baxter
Lead Researcher, UAVs & Autonomy 
Tel: [phone]
email:  jwbaxter_at_[hidden]
www.QinetiQ.com
QinetiQ - Delivering customer focused solutions 

Please consider the environment before printing this email.

The information contained in this E-Mail and any subsequent 
correspondence is private and is intended solely for the intended 
recipient(s).  The information in this communication may be 
confidential and/or legally privileged.  Nothing in this e-mail is 
intended to conclude a contract on behalf of QinetiQ or make QinetiQ 
subject to any other legally binding commitments, unless the e-mail 
contains an express statement to the contrary or incorporates a formal Purchase Order.

For those other than the recipient any disclosure, copying, 
distribution, or any action taken or omitted to be taken in reliance 
on such information is prohibited and may be unlawful.

Emails and other electronic communication with QinetiQ may be 
monitored and recorded for business purposes including security, audit 
and archival purposes.  Any response to this email indicates consent 
to this.

Telephone calls to QinetiQ may be monitored or recorded for quality 
control, security and other business purposes.

QinetiQ Limited
Registered in England & Wales: Company Number:3796233
Registered office: 85 Buckingham Gate, London SW1E 6PD, United Kingdom
Trading address: Cody Technology Park, Cody Building, Ively Road, Farnborough, Hampshire, GU14 0LX, United Kingdom 
http://www.qinetiq.com/home/notices/legal.html