Re: [boost] [task]

Subject: Re: [boost] [task]
From: vicente.botet (vicente.botet_at_[hidden])
Date: 2009-10-02 13:19:36

Hi Jeremy,

first of all thanks for your insigh comments.

----- Original Message ----- 
From: "Baxter Jeremy" <JWBAXTER_at_[hidden]>
To: <boost_at_[hidden]>
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?

> 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.

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