21

並列実行スレッドから読み取り専用でSTL ベースのコンテナーにアクセスしたい。ユーザーが実装したロックを使用しない場合。次のコードのベースは、標準が適切に実装された C++11 です。

http://gcc.gnu.org/onlinedocs/libstdc++/manual/using_concurrency.html
http://www.sgi.com/tech/stl/thread_safety.html
http://www.hpl.hp.com/personal/ Hans_Boehm/c++mm/threadsintro.html
http://www.open-std.org/jtc1/sc22/wg21/ (現在のドラフトまたはN3337、これは基本的に C++11 であり、軽微なエラーとタイプミスが修正されています)

23.2.2 コンテナのデータ競合 [container.requirements.dataraces]

データ競合 (17.6.5.9) を回避する目的で、実装は次の関数を const と見なす必要があります: begin、end、rbegin、rend、front、back、data、find、lower_bound、upper_bound、equal_range、at and、連想を除くまたは順序付けられていない連想コンテナー、operator[]。

(17.6.5.9)にもかかわらず、vector<bool> を除く同じシーケンス内の異なる要素に含まれるオブジェクトのコンテンツが同時に変更される場合、実装はデータ競合を回避する必要があります。

[注: サイズが 1 より大きい vector<int> x の場合、x[1] = 5 および *x.begin() = 10 はデータ競合なしで同時に実行できますが、x[0] = 5 および * x.begin() = 10 を同時に実行すると、データ競合が発生する可能性があります。一般的なルールの例外として、vector<bool> y の場合、y[0] = true は y[1] = true と競合する可能性があります。— 終了注記]

と

17.6.5.9 データ競合の回避 [res.on.data.races] 1 このセクションでは、実装がデータ競合 (1.10) を防止するために満たさなければならない要件を指定します。特に指定のない限り、すべての標準ライブラリ関数は各要件を満たす必要があります。以下に指定されている場合以外の場合、実装によってデータ競合が防止される場合があります。

2 C++ 標準ライブラリ関数は、現在のスレッド以外のスレッドによってアクセス可能なオブジェクト (1.10) に直接または間接的にアクセスしてはなりません。

3 C++ 標準ライブラリ関数は、現在のスレッド以外のスレッドによってアクセス可能なオブジェクト (1.10) を直接的または間接的に変更してはなりません (これを含む、関数の非 const 引数を介して直接的または間接的にオブジェクトにアクセスする場合を除く)。

4 [注: これは、たとえば、スレッド間でオブジェクトを明示的に共有しないプログラムでもデータ競合が発生する可能性があるため、同期なしでは実装が内部目的で静的オブジェクトを使用できないことを意味します。— 終了注記]

5 C++ 標準ライブラリ関数は、その引数またはそのコンテナー引数の要素を介して間接的にアクセス可能なオブジェクトにアクセスしてはなりません。

6 標準ライブラリ コンテナーまたは文字列メンバー関数を呼び出すことによって取得された反復子に対する操作は
、基になるコンテナーにアクセスできますが、それを変更してはなりません。[ 注: 特に、イテレーターを無効にするコンテナー操作は、そのコンテナーに関連付けられたイテレーターの操作と競合します。— 終了注記]

7 オブジェクトがユーザーに表示されず、データ競合から保護されている場合、実装はスレッド間で独自の内部オブジェクトを共有できます。

8 別段の指定がない限り、C++ 標準ライブラリ関数は、それらの操作がユーザーに見える効果 (1.10) を持っている場合、現在のスレッド内でのみすべての操作を実行するものとします。

9 [ 注: これにより、目に見える副作用がなければ、実装で操作を並列化できます。— 終了注記]

結論
コンテナーはスレッドセーフではありません! ただし、複数の並列スレッドからコンテナーでconst 関数を呼び出すことは安全です。そのため、ロックせずに並列スレッドから読み取り専用操作を行うことができます。私は正しいですか？

私は、それらに欠陥のある実装は存在せず、C++11 標準のすべての実装が正しいふりをします。

サンプル：

// concurrent thread access to a stl container
// g++ -std=gnu++11 -o p_read p_read.cpp -pthread -Wall -pedantic && ./p_read
#include <iostream>
#include <iomanip>
#include <string>
#include <unistd.h>

#include <thread>
#include <mutex>

#include <map>

#include <cstdlib>
#include <ctime>
using namespace std;

// new in C++11
using str_map = map<string, string>;

// thread is new in C++11
// to_string() is new in C++11

mutex m;
const unsigned int MAP_SIZE = 10000;

void fill_map(str_map& store) {
    int key_nr;
    string mapped_value;
    string key;

    while (store.size() < MAP_SIZE) {
        // 0 - 9999
        key_nr = rand() % MAP_SIZE;

        // convert number to string
        mapped_value = to_string(key_nr);
        key = "key_" + mapped_value;

        pair<string, string> value(key, mapped_value);
        store.insert(value);
    }
}

void print_map(const str_map& store) {
    str_map::const_iterator it = store.begin();

    while (it != store.end()) {
        pair<string, string> value = *it;
        cout << left << setw(10) << value.first << right << setw(5) << value.second << "\n";
        it++;   
    }
}

void search_map(const str_map& store, int thread_nr) {
    m.lock();
    cout << "thread(" << thread_nr << ") launched\n";
    m.unlock();

    // use a straight search or poke around random
    bool straight = false;
    if ((thread_nr % 2) == 0) {
        straight = true;
    }

    int key_nr;
    string mapped_value;
    string key;
    str_map::const_iterator it;

    string first;
    string second;

    for (unsigned int i = 0; i < MAP_SIZE; i++) {

        if (straight) {
            key_nr = i;
        } else {
            // 0 - 9999, rand is not thread-safe, nrand48 is an alternative             
            m.lock();
            key_nr = rand() % MAP_SIZE;
            m.unlock();
        }

        // convert number to string
        mapped_value = to_string(key_nr);
        key = "key_" + mapped_value;

        it = store.find(key);

        // check result
        if (it != store.end()) {
            // pair
            first = it->first;
            second = it->second;

            // m.lock();
            // cout << "thread(" << thread_nr << ") " << key << ": "
            //      << right << setw(10) << first << setw(5) << second << "\n"; 
            // m.unlock();

            // check mismatch
            if (key != first || mapped_value != second) {
                m.lock();
                cerr << key << ": " << first << second << "\n"
                     << "Mismatch in thread(" << thread_nr << ")!\n";
                exit(1);

                // never reached
                m.unlock();
            }
        } else {
            m.lock();
            cerr << "Warning: key(" << key << ") not found in thread("
                 << thread_nr << ")\n";
            exit(1);

            // never reached
            m.unlock();
        }
    }
}

int main() {
    clock_t start, end;
    start = clock();

    str_map store;
    srand(0);

    fill_map(store);
    cout << "fill_map finished\n";

    // print_map(store);
    // cout << "print_map finished\n";

    // copy for check
    str_map copy_store = store;

    // launch threads
    thread t[10];
    for (int i = 0; i < 10; i++) {
        t[i] = thread(search_map, store, i);
    }

    // wait for finish
    for (int i = 0; i < 10; i++) {
        t[i].join();
    }
    cout << "search_map threads finished\n";

    if (store == copy_store) {
        cout << "equal\n";
    } else {
        cout << "not equal\n";
    }


    end = clock();
    cout << "CLOCKS_PER_SEC " << CLOCKS_PER_SEC << "\n";
    cout << "CPU-TIME START " << start << "\n";
    cout << "CPU-TIME END " << end << "\n";
    cout << "CPU-TIME END - START " << end - start << "\n";
    cout << "TIME(SEC) " << static_cast<double>(end - start) / CLOCKS_PER_SEC << "\n";

    return 0;
}

このコードはGCC 4.7でコンパイルでき、私のマシンでは正常に動作します。

$ エコー $?
$ 0

4

2 に答える 2

21

セクション 1.10/4 および 1.10/21 の C++11 仕様からのデータ競合には、同じメモリ位置のセットへの非アトミック アクセスを持つ少なくとも 2 つのスレッドが必要です。2 つのスレッドは、アクセスに関して同期されていません。メモリ ロケーションのセット、および少なくとも 1 つのスレッドが、メモリ ロケーションのセット内の要素への書き込みまたは変更を行います。したがって、あなたの場合、スレッドが読み取りのみを行っている場合は問題ありません...定義により、同じメモリ位置のセットに書き込むスレッドがないため、データ競合はありません。スレッド。

于 2012-05-31T12:25:42.040 に答える
4

はい、あなたは正しいです。リーダー スレッドが開始する前に、ベクターを作成するスレッドが完了している限り、安全です。最近似たような質問がありました。

于 2012-05-31T12:26:26.053 に答える