CODEWITHSUNDEEP
c++multithreadingrecursion
0xbaadf00d
0xbaadf00d

Reputation: 2643

Multithreaded Recursive task synchronization

void Node::recursiveThing()
{
  for(auto iter = m_children.begin();
  iter != m_children.end();
  iter++)
  {
    s_threadPool->addTask(std::bind(&Node::recursiveThing, (*iter));
  }
}

int main()
{
  Node * hugeThree = makeHugeTreeMethod();
  std::future allIterationsDone = s_threadPool->addTask(std::bind(&Node::recursiveThing, hugeTree));
  allIterationsDone.wait(); // I want to somehow block here until all spawned child tasks are done.
}

Yeah.

So my problem is that I'd like to spawn child tasks from a task, which in turn spawn even more child tasks. This works, but how can I know that all spawned child tasks have been completed? Maybe I need to make a thread safe list where they are all appended?

I read somewhere that this might be possible in c++17, but I'd need something now, any ideas?

Upvotes: 2

Views: 414

Answers (1)

David Haim
David Haim

Reputation: 26526

hmmm...
yes, C++17 std::when_all could have being very helpfull here.

one solution I can think about (psudo code only!):

struct TreeTasks
   vector<child*> busyNodes
   mutex vectorLock
   condition_variable vectorCV
   thread taskChecker 

BeforeAll
 lock busyNodes
 add root-node's *this* to busyNodes
 unlock busyNodes
 launch taskChecker with taskChecker Routine

OnNodeTaskFinish
 lock vectorLock
 add child nodes pointers to busyNodes if exist
 remove *this* from busyNodes
 unlock busyNodes
 notify vectorCV

taskChecker Routine
  lock vectorLock
  wait on vectorCV(vectorLock) on predicate -> busyNodes.isEmpty()
  return done

this is very similiar on a thread-pool algorithm on how to split the tasks.
we have a vector which containes the node that are being worken on,
a thread which most of the time just sleeps and wakes up when a size-change occures on the vector.

when a task finishes to work on a node, it may or may not append the children into the vector, but anyway removes itself from it. the checker thread wakes up - if the vector is empty - all the tasks are done.

Upvotes: 1

Related Questions