Re: [boost] futures, deadlocking and mutual recursion.

From: Kirit Sælensminde (kirit.saelensminde_at_[hidden])
Date: 2007-12-02 05:38:51

Achilleas Margaritis wrote:
> Isn't there a deadlock issue with futures? suppose I have the following 
> code:
> 
> class A {
>      int data;
> 
> public:
>      int getData() const {
>          return data;
>      }
> 
>      void someAction(B *b) {
>          future<int> i = bind(b, &B::someAction, this);
>          data = i.wait() + 1;
>      }
> };
> 
> class B {
>      int data;
> 
> public:
>      int someAction(A *a) {
>          future<int> j = bind(a, &A::getData);
>          return j.wait() + 1;
>      }
> };
> 
> int main() {
>       A *a = new A;
>       B *b = new B;
>       a->someAction(b);
> }
> 
> The above contains a deadlock:
> 
> class A builds a future 'i' in function 'someAction' over class B, then 
> it waits for B's method 'someAction' to wait.
> 
> class B, when its method 'someAction' is invoked, builds a future 'j' 
> over method 'getData' of A...then it tries to evaluate 'j'.
> 
> At this point, the instance of A is blocked waiting for B to finish its 
> processing, and B waits for A to finish its processing, thus deadlocking 
> the program.
> 
> My question is: is this a real problem, and if so, how is it handled by 
> boost::futures?
> 
> Another way to introduce the deadlock is by mutual recursion using futures.

In order for futures to not deadlock you have to have an acyclic 
dependency graph - only those dependencies where there is a blocking 
wait on the result in the future count though. If you have a cycle in 
the graph then you have the potential for deadlock.

If you need something provably deadlock free then you need to examine 
your call structure. You can break the deadlock potential by throwing 
away the future and using a callback instead.

On my web site you can Mahlee which is a JavaScript host (Windows only 
I'm afraid) that uses futures for multi threading (it is built on 
Boost.Thread). There is an example of how to write a deadlock free work 
manager using futures here http://www.kirit.com/News:/1720815 Note that 
the manager just passes the futures on to other threads, it never 
examines them so doesn't block on them.

For this style of concurrency programming you want to read up on CSP 
(Communicating Serial Processes). Erlang uses this style exclusively.

Although this is all JavaScript, the deadlock issues are identical to 
those you're discussing and you may find it easier to experiment with as 
the syntax for the messages is much simpler in JavaScript (they look 
identical to normal function calls).

You can find Mahlee here: 
http://www.kirit.com/Categories:/Mahlee%E2%84%A2 and a download link 
here: 
http://www.kirit.com/Blog:/2007-09-25/Mahlee%E2%84%A2%20alpha%20release%20available%20for%20download

K

-- 
http://www.kirit.com/