在C++ 11中使用期货,异步和线程实现搜索

Question

我想以多线程方式实现分支定界搜索.特别是,我想用来async包装每个分支的搜索调用,然后等到某个线程得到答案,然后退出.(理想情况下,我想取消其他线程,但线程取消不在标准中).这是一些简化的代码:

#include <iostream>
#include <random>
#include <future>
#include <thread>

using namespace std;

mt19937 rng;
uniform_int_distribution<unsigned> random_binary(0, 1);

bool search() {
  return static_cast<bool>(random_binary(rng));
}

#define N 10000

int main()
{
  rng.seed(42);

  std::vector<future<bool>> tasks;

  for (unsigned i=0; i<N; ++i)
    tasks.push_back(async(launch::async, search));

  // Don't want to wait sequentially here.
  for (unsigned i=0; i<N; ++i) {
    tasks[i].wait();
    if (tasks[i].get()) {
      cout << "i = " << i << "\n";
      break;
    }
  }
  return 0;
}

search()是搜索功能.它根据是否找到答案返回true/false.我回答一个随机的答案来说明.但问题的关键在于调用的for循环tasks[i].wait().现在,我正在等待任务完成.相反,我想做这样的事情:

auto x = wait_for_any(tasks.begin(), tasks.end());
x.get();
// cancel other threads.
// Profit?

实现这一目标的好方法是什么？

Answer 1

std::future提供了一个valid()函数,可以让您检查结果是否可用而不会阻塞,因此您可以使用它,例如在忙等待循环中:

std::future<bool>* res_future = 0;
for(size_t i = 0; ; i==tasks.size()?i=0:++i){
  // could add a timeout period to not completely busy-wait the CPU
  if(tasks[i].wait_for(std::chrono::seconds(0)) == std::future_status::ready){
    res = &tasks[i];
    break;
  }
}

bool res = res_future->get();

std::future为了使这样的任务更容易,建议添加一种.then(func_obj)方法,该方法异步调用func_obj结果可用的时间,您可以在其中设置标志或其他内容.

遗憾的是,我不知道可能wait_for_any以上述任何其他方式实施的方法.:/

template<class FwdIt>
std::future<bool> wait_for_any(FwdIt first, FwdIt last)
{
  return std::async([=]{
    for(FwdIt cur(first); ; cur==last?cur=first:++cur){
    // could add a timeout period to not completely busy-wait the CPU
    if(cur->wait_for(std::chrono::seconds(0)) == std::future_status::ready)
      return cur->get();
  });
}

线程破坏通常通过协作取消来完成.

PS:如果结果不可用,std::future<T>::get()将自动进行wait().

Answer 2

安排所有的任务有机会获得同样的condition_variable,mutex和bool.这可以通过创建这些全局变量或每个任务运行成员函数的成员数据来完成,或者您可以通过std::ref任务创建函数中的参数传递它们.

在开始任何任务之前初始化boolto not_found.然后主线程启动任务并等待condition_variable.搜索者的任务然后搜索.当他们搜索时,他们偶尔会检查bool(可能带有原子载荷)以查看它是否已被设置为found.如果有,则搜索器线程立即返回.

当一个线程找到结果时,它会设置bool为found并发出信号condition_variable.这将唤醒主线程并有效地取消其余的搜索器任务.然后,主线程可以与所有搜索器任务一起加入,分离,放弃等等.如果您没有主要明确加入搜索者任务,那么最好在主要退出之前安排所有搜索者任务结束.

没有民意调查.无需等待死胡同搜索.唯一的特殊部分是确定搜索者检查任务的方式和频率bool.我建议对这部分进行性能测试.