对于基于任务的程序，如何避免递归任务列表遍历？

Question

我有一个带有虚拟方法的类ITask：

class ITask
{
  public:
      virtual void Execute() = 0;
};

我做了一个系统，在不同的线程上分配任务，让它们并行执行。问题是，我需要一些任务在某些其他任务完成之前无法执行。一个任务可能依赖于多个父任务，所以我不能这样做：

void Task::Execute()
{
//do stuff
//finished

    for(int i = 0; i < children.size(); i++)
    {
     ThreadingSystem::QueuedTasks.push_back(children[i]);
    }
}

所以我做了这样的事情：

class Task : public ITask
{
    public:
     void Execute();

     unsigned int dependency;

     vector<Task*> children;
};

void Task:：Execute（）{//do stuff//finished

for(int i = 0; i < children.size(); i++)
{
    children[i]->dependency--;
}

}

所以基本上，只有依赖于0U的任务才能自由执行，所以任务需要等待所有父级完成才能执行。现在的问题是，这个系统变得非常混乱，例如：

    for(int i = 0; i < children.size(); i++)
    {
        if(children[i]->dependency == 0U)
        {
           ThreadingSystem::QueuedTasks.push_back(children[i]);
           //either remove added task from children or set a flag in it to mark as "queued"
        }
    }

我必须基本上称之为不间断，直到所有的孩子都离开向量。第一次迭代可能只向多线程队列发送2个任务，第二次迭代可能再发送3个，第三次迭代可能再发送7个，等等。这是完全不可预测的，涉及很多分支和循环。也许关于依赖整数的整个想法都不好？

Answer 1

可以基于要执行的原始任务构建依赖关系树。假设您想要执行TaskA，这取决于TaskB和TaskC。TaskC本身依赖于TaskD。

让您的任务保存他们的孩子，这是他们的依赖！

class Task : public ITask
{
    public:
     void Execute();

     vector<Task*> children;
};

对于TaskA，向量子项将由TaskB和TaskC组成。TaskB没有其他子任务。TaskC让孩子承担任务。

ThreadingSystem中的线程将解析任务树（从TaskA开始）并搜索叶子，即没有子任务的任务。如果一个线程找到一个叶子，它将确保没有其他线程可以同时运行该任务。一面旗帜可能有用。

执行后，将从树中删除该叶子，并搜索另一片叶子。

如果当前没有可用的叶，线程必须等待一个叶可用。只要一片叶子被处决，你就可以叫醒他们。

ThreadingSystem在没有剩余任务时执行，即TaskA从树中移除时执行。你可以发送一个事件，或者取消对呼叫者的阻止，或者其他什么。

正如你评论一个答案，你这样做是为了教育目的。尝试实现一个树，如果你完成了，你可以尝试实现一个（定向）图。或执行周期检测。尝试加快查找/缓存树叶等的性能。

或使用现有的框架

Answer 2

• 使用getter/setter，而不是直接访问依赖项。
  • 比如child-

  不过，如果您可以找到一个已经调试过的基于任务的线程池库，您应该考虑一下。