1

そのリソースのロックを使用せずに、複数のスレッドで（オブジェクトの）共有された初期化されたcスタイルの配列に要素を同時に追加するための既知の動作するコードはありますか？つまり、要素がポインタによってリンクされていない連続メモリブロックに。

つまり、ライブラリなどではなく、アルゴリズムです。たとえば、ロックなしで20スレッドの要素で配列を埋めたい、または埋めるスレッドの配列範囲を指定する必要があります（ロックフリーリンクリストのように）。

slackware 13.37 64ビット、pthreads、Intel c ++コンパイラ、tcmallocアロケータを使用しています。

更新：皆さんの回答に感謝します。皆さんは皆さんのアイデアに役立っています。できれば、すべてのアイデアを回答としてマークします。しかし、私はまだ私のコードに苦労しています。だから、後で別のスレッドにコードを入れて、私のコードで何が起こっているのかを正確に確認して、人々が本当に集中できるようにします。

4

3 に答える 3

2

たぶん私はその考えを正しく理解していませんでしたが、明らかな解決策はstd::atomic現在の配列インデックスに増分を使用することです。整数型のアトミックは通常、ロックフリーとして実装されます。

ただし、これが当てはまらない場合、またはコンパイラがC ++ 11をサポートしていない場合はInterlockedIncrement、VSや__sync_fetch_and_addGCCなどのコンパイラ固有のロックフリー関数に置き換えることができます。

IntelC++コンパイラC++ 11 atomicsの場合はサポートされています。_InterlockedIncrement64また、ヘッダーファイルから使用することもできます。ia64intrin.hの147ページを参照してくださいIntel(R) C++ Intrinsics Reference。

サンプルコード（ここで機能することの証明）

#include <atomic>
#include <thread>
#include <iostream>

const uint max_count = 100;

std::atomic_uint count;
std::string data[max_count];

void thread_func(const char* str)
{
   while(true)
   {
      const uint index = count++;
      if(index >= max_count) break;
      // Use += to see defect if data was already initialized by other thread
      data[index] += str;
      std::this_thread::sleep_for(std::chrono::milliseconds(1));
    }
 }

 int main()
 {
    std::cout << "Atomic counter is lock-free: " << 
       (count.is_lock_free() ? "Yes!" : "No!") << std::endl;

    std::thread t1(thread_func, "Thread 1");
    std::thread t2(thread_func, "Thread 2");
    std::thread t3(thread_func, "Thread 3");

    t1.join();
    t2.join();
    t3.join();

    for(uint i = 0; i < max_count; ++i)
    {
       std::cout<< i << ": " << data[i] << std::endl;
    }

    return 0;
 }
于 2012-10-23T10:40:44.303 に答える
0

配列内のオブジェクトを読み書きするだけの場合は、インターロック スタイル命令を使用してデータを読み書きするだけで済みます。例えば：

Foo* data[10];
// some more code
Foo *value=interlocked_read(&data[2]);

interlocked_write(&data[3], new Foo);

インターロックにより、有効なポインターをアトミックに読み取ることが保証され、配列にアクセスするときにメモリの一貫したビューがあることが保証されます。Windows を使用している場合は、同期に関するドキュメントのさまざまな InterlockedXXX 関数を参照してください。

配列からオブジェクトを読み取り、それを変更してから書き戻す場合は、ロックを回避し、別のスレッドが変更される可能性を回避したい場合は、比較と交換のアプローチ (CAS とも呼ばれます) を使用する必要があります。あなたと同時に更新しているオブジェクト。

于 2012-10-23T09:41:32.687 に答える
0

各スレッドがチャックを取得するように配列を分割できます。たとえば、次の場合:

static int array[100];

次に、各スレッドはその一部で機能します。

int size = 100 / amount_of_threads;
int* partition = array + thread_id * size;

thread_idは連続的で、0 から始まると見なされます。

于 2012-10-23T09:37:17.680 に答える