futures, deadlocking and mutual recursion.
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.
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%20av... K -- http://www.kirit.com/
Achilleas Margaritis:
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:
It doesn't, unless the future<int> contains a magic per-object mutex. It would be a deadlock if A is changed as follows: class A { int data; mutable mutex mx; public: int getData() const { scoped_lock lock( mx ); return data; } void someAction(B *b) { scoped_lock lock( mx ); future<int> i = bind(b, &B::someAction, this); data = i.wait() + 1; } }; which is broken. A mutex lock should never encompass a blocking call. class A { int data; mutable mutex mx; public: int getData() const { scoped_lock lock( mx ); return data; } void setData( int v ) { scoped_lock lock( mx ); data = v; } void someAction(B *b) { future<int> i = bind(b, &B::someAction, this); setData( i.wait() + 1 ); } };
O/H Peter Dimov έγραψε:
Achilleas Margaritis:
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:
It doesn't, unless the future<int> contains a magic per-object mutex. It would be a deadlock if A is changed as follows:
class A { int data; mutable mutex mx;
public: int getData() const { scoped_lock lock( mx ); return data; }
void someAction(B *b) { scoped_lock lock( mx ); future<int> i = bind(b, &B::someAction, this); data = i.wait() + 1; } };
which is broken. A mutex lock should never encompass a blocking call.
class A { int data; mutable mutex mx;
public: int getData() const { scoped_lock lock( mx ); return data; }
void setData( int v ) { scoped_lock lock( mx ); data = v; }
void someAction(B *b) { future<int> i = bind(b, &B::someAction, this); setData( i.wait() + 1 ); } };
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Aaaah yes, it's because each future is a different thread. But it would be a deadlock in the Actor model, where B's thread would wait A's thread and A's thread would wait for B's thread.
participants (3)
-
Achilleas Margaritis -
Kirit Sælensminde -
Peter Dimov