First - boost.task is the successor of boost.threadpool and uses the wait- notifications too (but doesn't wait infinit because some co-worker-thread could have produced additonal tasks which could be stolen). Second - I'm finishing boost.task-0.4.0 which replaces this_task::reschedule_until() by this_task::block(). block() suspends the current task without blocking the worker-thread. The blocked task gets rescheduled by the internal scheduler (returning from block()): while ( ! condition) this_task::block(); Version 0.4.0 allows to synchronize or exchange messages between the tasks without deadlocking the threadpool (that means amount of tasks >> worker- threads in pool). regards, Oliver Am Freitag 02 Oktober 2009 14:06:13 schrieb Baxter Jeremy:

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: 01684 894801 email: jwbaxter@QinetiQ.com 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 _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Hi Jeremy, first of all thanks for your insigh comments. ----- Original Message ----- From: "Baxter Jeremy" <JWBAXTER@qinetiq.com> To: <boost@lists.boost.org> Sent: Friday, October 02, 2009 2:06 PM Subject: [boost] [task]

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.

Yes, Boost.Task design do not works well with blocking tasks. At least not yet.

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.

I think that it will not to much complex to provide a function that submit a task that must run on the context of a different thread. Would this kind of submit function help you?

...

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

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. the task is not 're-scheduled' it is actually blocked until whatever task the scheduler next selects is complete.

I agree. The comment "The current task will be rescheduled until the passed predicate becomes true. " should be "The current worker thread will schedule tasks until the predicate is true".

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.

You are right this should be a deadlock problem with the current implementation. I don't think however that having more threads would solve the issue, but just reduce its frequency, as the issue appears when tasks T1 and T2 are handled on the same thread. In order to avoid the issue we need to avoid two blocking tasks to be executed on the same thread. The user sould state blocking task on the submit function. The scheduler will not take a blocking task while in the reschedule_until function. Of course, in order to be able to avoid any deadlock associated to the fact we are using a thread pool, the number of threads must grow, if there is no free worker threads able to handle the new blocking task. The reschedule_until function should throw an exception when the task is not a blocking task. This should solve the issue, but introduce a burden at the user level, i.e. specify if the task can block or not. Jeremy, Oliver, what do you think? Best, Vicente