5

JLSから2つの結論があります。

  • C1：プログラムにデータ競合がない場合、プログラムのすべての実行は逐次一貫性があるように見えます。data-race-free => sequentially consistent
  • C2：プログラムが正しく同期されている場合、プログラムのすべての実行は順次一貫しているように見えます。correctly synchronized => sequentially consistent

C1の逆が真である場合、次のように結論付けることができます。

  • C3：プログラムが正しく同期されている場合、データの競合は発生しません。correctly synchronized => data-race-free

しかし、残念ながら、JLSにはそのようなステートメントがないため、4番目の結論に到達します。

  • C4：プログラムは正しく同期され、データの競合が発生する可能性があります。

しかし、私はこのアプローチに満足しておらず、非公式な方法でもサンプル的な方法でも、この結論が正しい（または間違っている）という証拠を入手したいと思います。

まず、データ競合を含むマルチスレッドプログラムの逐次一貫性のある実行を示すコードセグメントは、この問題を理解して解決するのに役立つと思います。

真剣に検討した結果、まだ適切なサンプルが見つかりません。では、そのようなコードセグメントを教えていただけませんか。

4

3 に答える 3

5

良い例は、Stringのハッシュコードです。

private int hash; // Default to 0

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

ハッシュはさまざまなスレッドで書き込みおよび読み取りが可能であり、発生前の関係（同期なし）がないため、ここではデータの競合が発生します。

ただし、スレッドが文字列の実際のハッシュコードではないハッシュコードを確認することは不可能であるため、プログラムは順次一貫性があります（スレッドがハッシュコードメソッドを実行すると、0を確認して値を再計算できますが、これは決定論的です。有効な値が表示されます）。これは、int書き込みがアトミックであるために機能します。

編集

この（ほぼ）同じコードは壊れており、0のハッシュコードを返す可能性があります。

public int hashCode() {
    if (hash == 0 && count > 0) { //(1)
        int h = hash;
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return hash; //(2)
}

（1）と（2）を並べ替えることができるため、（1）はnull以外の値を読み取ることができ、（2）は0を読み取ることができます。最初の例では、ローカル変数で計算が行われ、戻り値が返されるため、これは発生しません。値はそのローカル変数でもあり、定義上、スレッドセーフです。

編集2

あなたの提案C4に関しては、私はそれが可能ではないと思います：

プログラムは、すべての逐次一貫性のある実行にデータ競合がない場合にのみ、正しく同期されます。

プログラムが正しく同期されている場合、プログラムのすべての実行は逐次一貫性があるように見えます（§17.4.3）。

したがって、プログラムが正しく同期されている場合：

  • すべての実行は順次一貫しているように見えます。
  • 逐次一貫性のあるすべての実行には、データの競合がありません。

したがって、すべての実行にはデータ競合がなく、したがってプログラムにはデータ競合がないと結論付けることができます。

于 2012-08-17T15:00:43.507 に答える
1

競合状態とは、プログラムの出力を、特定の時点で誰が最初に取得するかに依存させることを意味します。たとえば、T1とT2の2つのスレッドがある場合、T1がプログラムのポイントPに最初に到達した場合にプログラム出力がXであり、T2が最初にポイントPに到達した場合にプログラムの出力がYである場合、競合状態になります。

擬似コードの場合：

 Global variable i initialized to 6;
 Thread 1: 
       aquire(lock l)
             increment global variable i, i.e. i++;


 Thread 2: 
       aquire(lock l)
             double the value of global var i, i.e.: i*=2;

T1がロックlfirtsを取得し、T2秒の場合、iの値は14になります。T2がlock l firtsを取得し、T1秒の場合、iの値は13になります。

于 2012-08-17T13:31:02.020 に答える
0

http://rsim.cs.illinois.edu/Pubs/popl05.pdf

証明は次のようになります。

正しく同期されたプログラムの実行にデータ競合が含まれているとすると、「正しく同期されたプログラム」の定義に違反する、データ競合を含む順次実行を見つけることができます[C1]

したがって、実行にデータ競合を含めることはできません。[C3]そこから、実行は逐次一貫性があることが証明できます。[C2]

したがって、C3は真であり、C2を証明するために使用されます。

于 2012-08-24T00:43:22.363 に答える