4

私は並行プログラミングが初めてなので、よろしくお願いします。基本的なシーケンシャル プログラム (宿題用) があり、それをマルチスレッド プログラムに変換しようとしています。2 番目の共有変数にロックが必要かどうかわかりません。スレッドは私の変数を変更する必要がありますが、それらを読み取ることはありません。唯一の時間カウントを読み取る必要があるのは、すべてのスレッドを生成するループがキーの配布を終了した後です。

#define ARRAYSIZE 50000

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h> 

void binary_search(int *array, int key, int min, int max); 

int count = 0; // count of intersections
int l_array[ARRAYSIZE * 2]; //array to check for intersection

int main(void)
{
    int r_array[ARRAYSIZE]; //array of keys
    int ix = 0;

    struct timeval start, stop;
    double elapsed;

    for(ix = 0; ix < ARRAYSIZE; ix++)
    {
        r_array[ix] = ix;
    }
    for(ix = 0; ix < ARRAYSIZE * 2; ix++)
    {
        l_array[ix] = ix + 500;
    }

    gettimeofday(&start, NULL);

    for(ix = 0; ix < ARRAYSIZE; ix++)
    {
        //this is where I will spawn off separate threads
        binary_search(l_array, r_array[ix], 0, ARRAYSIZE * 2);
    }

    //wait for all threads to finish computation, then proceed.

    fprintf(stderr, "%d\n", count);

    gettimeofday(&stop, NULL);
    elapsed = ((stop.tv_sec - start.tv_sec) * 1000000+(stop.tv_usec-start.tv_usec))/1000000.0;
    printf("time taken is %f seconds\n", elapsed);
    return 0;
}

void binary_search(int *array, int key, int min, int max)
{
    int mid = 0;
    if (max < min) return;
    else
    {
      mid = (min + max) / 2;
      if (array[mid] > key) return binary_search(array, key, min, mid - 1);
      else if (array[mid] < key) return binary_search(array, key, mid + 1, max);
      else 
      {
          //this is where I'm not sure if I need a lock or not
          count++;
          return;
      }
    }
}
4

3 に答える 3

6

ご想像のとおり、count++;同期が必要です。これは、実際には、やらないで「逃げる」ようにすべきことではありません。遅かれ早かれ、最初のスレッドがカウントを読み取った後、カウントをインクリメントする前に、2 番目のスレッドがカウントを読み取ります。その後、カウントを逃します。どのくらいの頻度で発生するかを予測することは不可能です。ブルームーンに 1 回、または 1 秒間に何千回も発生する可能性があります。

于 2012-10-27T02:20:09.437 に答える
5

実際、あなたが書いたコードは、変数の読み取りと変更の両方を行います。次のような行に対して生成されるマシンコードを見ると、

count++

あなたはそれが次のようなもので構成されていることがわかります

fetch count into register
increment register
store count

そうです、そこでミューテックスを使用する必要があります。（そして、そうしなくても逃げることができたとしても、練習する機会をとってみませんか？）

于 2012-10-27T02:03:01.253 に答える
4

複数のスレッド間で正確なインクリメントが必要な場合count、これらのタイプの単一値の更新は、まさにインターロックされたメモリ バリア関数の目的です。

これには、gcc を使用している場合は__sync_add_and_fetchを使用します。実行できるさまざまな連動操作が多数ありますが、そのほとんどはプラットフォーム固有のものなので、ドキュメントを確認してください。ただし、このようなカウンターの更新では、手間を大幅に省くことができます。その他のサンプルには、Windows のInterlockedIncrement、OS X のOSAtomicIncrement32などがあります。

于 2012-10-27T02:15:30.410 に答える