Linux3.0:futex-ロックデッドロックバグ？

Question

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch)
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch)
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters

struct Lock
{
Lock() : x(1) {}

void lock()
{
    while (true)
    {
        if (SubFetch(x, 1) == 0)
            return;

        x = -1;

        CompareWait(x, -1);
    }
}

void unlock()
{
    if (AddFetch(x, 1) == 1)
        return;

    x = 1;

    Wake(x, 1);
}

private:
    int x;
};

Linux3.0では、以下のようなシステムコールが提供されている。 フテックス, これには、最近のpthread_mutex実装を含む多くの並行性ユーティリティが基づいています。コードを書くときはいつでも、既存の実装を使用するか、自分で書くかがプロジェクトにとってより良い選択であるかどうかを常に検討する必要が

上記は、futexとセマンティクスの記述に基づいたロック(mutex,1permit counting semaphore)の実装である。 マンフューテックス(7)

複数のスレッドが数千回ロックとロック解除を試みた後、スレッドはx==-1の状態になり、すべてのスレッドがCompareWaitでスタックしますが、誰もロックを保持していないというデッドロックのバグが含まれているようです。

誰でもバグがどこにあるか見ることができますか？

更新: 私はfutex（7）/セマンティクスが非常に壊れていることに少し驚いています。私は完全に次のようにロックを書き直しました。..これは今正しいですか？

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false;

struct Lock
{
Lock() : x(0) {}

void lock()
{
    while (!CompareAssign(x, 0, 1))
        if (x == 2 || CompareAssign(x, 1, 2))
            CompareWait(x, 2);
}

void unlock()
{
    if (SubFetch(x, 1) == 0)
        return;

    x = 0;

    Wake(x, 1);
}

private:
int x;
};

ここでの考え方は、xには次の3つの状態があるということです:

0: unlocked
1: locked & no waiters
2: locked & waiters

Answer 1

問題は、あなたが明示的に-1に割り当てることです x の場合は、 SubFetch ロックの取得に失敗します。これはロック解除と競争します。

1. スレッド1はロックを取得します。 x==0.
2. スレッド2はロックを取得しようとします。ザ- SubFetch セット x -1にし、スレッド2が中断されます。
3. スレッド1はロックを解除します。ザ- AddFetch セット x 0にすると、コードは明示的に設定されます x へ1と通話 Wake.
4. スレッド2 x -1にしてから呼び出します CompareWait.

スレッド2は現在、待機して立ち往生しています,と x -1に設定しますが、スレッド1がすでにロックを解放しているため、それをウェイクする人はいません。

Answer 2

Ulrich Dropperの論文「Futexesはトリッキーな」に記載されている布団ベースのミューテックスの適切な実装が記載されています。

http://people.redhat.com/drepper/futex.pdf

コードだけでなく、正しい理由の詳細な説明も含まれています。紙からのコード：

class mutex
{
 public:
 mutex () : val (0) { }
 void lock () {
   int c;
   if ((c = cmpxchg (val, 0, 1)) != 0)
     do {
       if (c == 2 || cmpxchg (val, 1, 2) != 0)
         futex_wait (&val, 2);
     } while ((c = cmpxchg (val, 0, 2)) != 0);
 }
 void unlock () {
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch !
   if (atomic_dec (val) != 1) {
     val = 0;
     futex_wake (&val, 1);
   }
 }
 private:
   int val;
};

.

紙のコードとコードを比較すると、差分を見つけます

あなたはを持っています

if（x== 2 || CompareAssign（x、1,2））

Futexの値を直接使用するのに対し、Drepperは前のcompareAssign（）から戻り値を使用します。その違いはおそらくパフォーマンスのみに影響を与えるでしょう。

あなたのロック解除コードも異なりますが、意味的に同等のようです。

いずれにせよ、私はDeropperのコードを手紙に従うようにあなたに強く助言します。その紙は時間のテストに立っており、たくさんのピアレビューを受けました。あなたはあなた自身の転がりから何も得られません。

Answer 3

このシナリオでは、A、B、Cの3つのスレッドを使用してください。

このシナリオの初期状態は次のとおりです:

• ロックを保持しているaに糸を通します
• スレッドBはまだロックのために競合していません
• スレッドCで CompareWait()
• x == -1 Cがロックの取得に失敗したときから

        A                  B                C
    ==============   ================  ===============
     AddFetch()
     (so x == 0)
                       SubFetch()
                       (so x == -1)

     x = 1

                       x = -1

     Wake()

この時点で、BまたはCがブロック解除されているかどうかにかかわらず、それらは結果を取得しません 0 彼らが SubFetch().