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/