3

マルチスレッド方式で分枝限定法を実装したいと思います。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?

これを達成するための良い方法は何ですか？

4

3 に答える 3

8

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()行われます。

于 2012-08-10T22:43:37.220 に答える
6

すべてのタスクが同じ、、、およびにアクセスできるように調整condition_variableしmutexますbool。これは、これらのグローバル、または各タスクがメンバー関数を実行しているメンバーデータを作成することによって行うことができます。またはstd::ref、タスク作成関数の引数としてそれらを渡すことができます。

タスクを開始boolする前に、を初期化します。not_found次に、メインスレッドがタスクを起動し、を待機しますcondition_variable。次に、サーチャータスクが検索します。彼らが検索するとき、彼らは時々bool（おそらく原子負荷で）それがに設定されているかどうかを調べるために検査しfoundます。ある場合、サーチャースレッドはすぐに戻ります。

1つのスレッドが結果を見つけると、にを設定し、boolをfound通知しcondition_variableます。これにより、メインスレッドがウェイクアップし、残りのサーチャータスクが効果的にキャンセルされます。その後、メインスレッドは、すべてのサーチャータスクに参加、切り離し、放棄することができます。mainが明示的にサーチャータスクに参加していない場合は、メインが終了する前にすべてのサーチャータスクを終了するように調整できるとよいでしょう。

ポーリングはありません。行き止まりの検索を待つ必要はありません。唯一のアドホックな部分は、サーチャータスクがを検査する方法と頻度を把握することですbool。この部分のパフォーマンステストをお勧めします。

于 2012-08-10T23:17:29.653 に答える
0

私が採用するアプローチは、メイン関数にを作成させ、std::promiseそれが作業を実行するさまざまなスレッドへの参照として渡されるようにすることです。作業中の各スレッドは、結果が得std::promiseられたら、すべて共有するスレッドを使用して使用しset_value()ます。

動作中のスレッドが最初にそこに到達すると、結果を送信でき、他のスレッドは、使用しようとしたときに例外がスローset_value()され、すでに設定されています。

次のソースコードスケルトンでは、私が使用していますが、何にも使用されないstd::async追加を作成せずに、自律スレッドをスピンオフできれば便利ですstd::promise。

したがって、コードスケルトンは次のようになります。

#include <iostream>
#include <thread>  // std::thread is defined here
#include <future>  // std::future and std::promise defined here

bool search(int args, std::promise<int> &p) {

    // do whatever needs to be done

    try {
        p.set_value(args);
    }
    catch (std::future_error & e) {
        // std::future_errc::promise_already_satisfied
    }
    return true;
}
int main(int argc, char * argv[])
{
    std::promise<int> myProm;    
    auto fut = myProm.get_future();

    for (int i = 1; i < 4; i++) {
        std::async(std::launch::async, search, i, std::ref(myProm));
    }

    auto retVal = fut.get();
    return 0;
}
于 2016-01-23T03:30:01.510 に答える