0

並行スレッドによって増加し続ける（減少しない）カウンターがいくつかあります。各スレッドは1つのカウンターを担当します。場合によっては、スレッドの1つがすべてのカウンターの最小値を見つける必要があります。私はこれをすべてのカウンターでの単純な反復で行い、最小値を選択します。この最小値がどのカウンターよりも大きくならないようにする必要があります。現在、同時実行メカニズムは使用していません。間違った答えが返ってくる可能性はありますか（つまり、カウンターの1つよりも大きい最小値になってしまう）。コードはほとんどの場合機能しますが、場合によっては（0.1％未満の時間）、カウンターの1つよりも大きい最小値を見つけることによってコードが壊れます。私はC++コードを使用していますが、コードは次のようになっています。

unsigned long int counters[NUM_COUNTERS];
void* WorkerThread(void* arg) {
  int i_counter = *((int*) arg);
  // DO some work
  counters[i_counter]++;
  occasionally {
    unsigned long int min = counters[i_counter];
    for (int i = 0; i < NUM_COUNTERS; i++) {
      if (counters[i] < min)
        min = counters[i];
    }
    // The minimum is now stored in min
  }
}

更新：@JerryCoffinによって提案された修正を採用した後、コードは次のようになります

unsigned long int counters[NUM_COUNTERS];
void* WorkerThread(void* arg) {
  int i_counter = *((int*) arg);
  // DO some work
  counters[i_counter]++;
  occasionally {
    unsigned long int min = counters[i_counter];
    for (int i = 0; i < NUM_COUNTERS; i++) {
      unsigned long int counter_i = counters[i];
      if (counter_i < min)
        min = counter_i;
    }
    // The minimum is now stored in min
  }
}
4

1 に答える 1

4

はい、壊れています-競合状態があります。

言い換えると、最小の値を選択すると、間違いなく他のどの値よりも小さくなりますが、比較を行った後に他のスレッドがそれをインクリメントすると、試行するまでに他のカウンターよりも大きくなる可能性がありますそれを使用します。

 if (counters[i] < min)
        // could change between the comparison above and the assignment below
        min = counters[i];

値の比較と保存の間の比較的短い間隔は、得られた答えがほとんどの場合正しい理由を説明します-比較の直後にコンテキストスイッチがあり、他のスレッドが頻繁にカウンターする場合にのみ、問題が発生します制御が切り替わる前に十分であるため、保存されるまでに最小のカウンターではなくなります。

于 2013-03-07T20:06:35.010 に答える