Correct Clean-Up of Parent and Children with Callbacks (C++)

Question

This design problem pops up again and again and I still don't have a nice solution for it. It might turn out to be a design pattern ;) Only, it seems to be very C++ specific (lack of garbage collection). Anyhow, here's the problem:

We have a parent object that keeps references to child objects. The parent's state depends on (some aggregate of) its children's states. In order to be notified of state changes in its children, it passes them a reference to itself. (In another variation it passes them a callback that the children can invoke to notify the parent. This callback is a closure that keeps a reference to the parent.) The application is heavily multi-threaded. Now, this setup is a whole hornet's nest of potential race conditions and dead locks. To understand why, here's a naive implementation:

class Parent {
 public:
   Parent() {
     children_["apple"].reset(new Child("apple", this));
     children_["peach"].reset(new Child("peach", this));
   }

   ~Parent() {
   }

   void ChildDone(const string& child) {
     cout << "Child is DONE: " << child << endl;
   }

  private:
   map<string, linked_ptr<Child> > children;
}; 

class Child {
  public:
   Child(const string& name, Parent* parent) 
       : name_(name), parent_(parent), done_(false) {}

   Foo(int guess) {
     if (guess == 42) done_ = true;
     parent->ChildDone(name_);
   }

  private:
   const string name_;
   Parent* parent_;
   bool done_; 
};

Potential issues:

During destruction of the parent, it must be on the lookout for ongoing callbacks from its children. Especially if those callbacks are fired off in a separate thread. If it is not, it might be gone by the time the callback is invoked.

If there are locks in both the parent and the children (very likely in a multi-threaded non-trivial application), locking order becomes an issue: the parent invokes a method on the child, which in turn experiences a state transition and tries to notify the parent: dead-lock.

Adding/Removing children outside the constructor can be an issue if the child tries to notify the parent from its destructor. The parent must be holding a lock in order to modify the map of children, yet the child is attempting a callback on the parent.

I only scratched the surface, but one can think of other potential issues.

What I'm looking for is some advice on how to handle clean destruction of the parent in the face of threads, locks, and dynamic addition/removal of children. If anybody has come up with an elegant solution that is robust under multi-threaded deployment, please share. The keyword here is robust: it's easy to design a structure that comes with some huge caveats (child never calls parent, parent never calls child, no separate thread for callbacks, etc.), the challenge is to put as few restrictions on the programmer as possible.

Answer 1

Often a big part of the problem with multithreading is the failure to properly separate processing (the worker thread i.e. Child) and state. Locking should be done via thread safe data structures not the threads themselves. Message queues, state machines and other such tools are intended to allow you to manage such data in a controlled way that is independent of the processes used to update them. You can almost always rework such a lifetime management problem so that it becomes a (thread safe) data management problem. The parent can be thought of as the owner of the state and the all threads update the state itself. Reference counting to manage lifetime of objects is a common paradigm also.

Answer 2

If there are locks in both the parent and the children (very likely in a multi-threaded non-trivial application), locking order becomes an issue: the parent invokes a method on the child, which in turn experiences a state transition and tries to notify the parent: dead-lock.

It's not clear to me why notifying the parent would cause a deadlock unless

1. the parent lock is held in thread A
2. thread A is waiting for the child to return a signal via some means
3. the child is signalling the parent in thread B
4. the parent when it receives the signal from the child in (3) attempts to obtain its lock

That's a lot of ifs. And it's a naturally problematic design: one thread (A) is holding a lock, and waiting for another thread (B) to do something.

There's no magic solution to avoid this problem - you just have to avoid it. The best answer is probably to not signal back to the parent from a separate thread; or, to distinguish between signals which will or will not be called with the parent lock already held.

During destruction of the parent, it must be on the lookout for ongoing callbacks from its children. Especially if those callbacks are fired off in a separate thread. If it is not, it might be gone by the time the callback is invoked.

The trick here is probably that the children should have a method (perhaps the destructor) which gaurentees that, after it returns, the child will make no further callbacks. When the parent is being destroyed it calls that method for each of its children.

I know you asked for "as few restrictions as possible" but realistically, when working in a multi-threaded environment, you have to have rules to prevent deadlocks and races.