セマフォのコンセンサス番号は何ですか？

Question

（私はそう思う） コンセンサス番号 Mutexの場合は2です。

セマフォのコンセンサス番号は何ですか（pthread_sem_*のように）？

条件変数のコンセンサス番号は何ですか（PTHREAD_COND_*のように）？

Answer 1

ミューテックスのコンセンサス番号は1です。ミューテックスが単一のスレッドに対して待機しないことがわずかに明確です。その定義から、ミューテックスが2つのスレッドに対してももう待機していないことも明らかです。したがって、コンセンサス番号は> = 1および<2であるため、1でなければなりません。

同様に、1つのスレッドを別のスレッドに有利に止めることで機能する他の同期メカニズムもコンセンサス番号1を持ち、したがって2つのスレッドで共有される待機オブジェクトを構築するために使用することはできません。

Answer 2

答えは、MutexまたはSemaphoreでサポートされている操作に依存します。ブロックロックのみがサポートされている場合、コンセンサス数は1です。スレッドが待機せずにミューテックスをロックしようとすることができる場合、コンセンサス番号は2です。これは、2つのスレッドがある場合、両方ともMutexをロックしようとすることができるためです。どちらがそれを手に入れたのか同意するので、コンセンサスがあります。ミューテックスがさらにロックしたスレッドの任意のスレッドについてさらに決定できる場合、コンセンサス数は無限です。セマフォの状況は似ていると思います。ミューテックスは、カウンター1のセマフォに相当します。コンセンサスには、より大きなカウンターだけではコンセンサスに到達できるとは思いませんが、それでも同じ操作になります。 Pthreadsは、クエリではなくブロッキングロック以外のロックをサポートしているため、答えは2になります。

条件変数を信号することは、スレッドがそれを待っていない場合、何もしないため、コンセンサス番号1があります。

Answer 3

確かに？しかし、彼らは自由に待っていません。

おそらく私は誤解しています。ミューテックスのコンセンサス数は2の2つです - そのためのあなたの情報源は何ですか？ブロッキングのトレードオフとともに、任意の数のスレッドがリソースを共有できるように設計されています。

原子 テストアンドセット コンセンサス数は2ですが、ブロックしません。

---

明確にするために：セマフォ、ミューテックスなどは、（正しく行う限り）安全にするために共有されたリソースを単純に包むことができるプリミティブです。彼らはブロックするかもしれませんが、彼らはあなたのデータが安全であることを保証します。

あなたが引用する論文は、データを保護するために必要なプリミティブについてです ブロックせずに, 、それです 難しい. 。同じプリミティブはロックにも役立つかもしれませんが、それはただの素晴らしいエクストラです。

Answer 4

この記事だけでは、セマフォには2以下のコンセンサス数が必要である必要があると結論付けることができます。なぜ次の理由は次のとおりです。

記事の3番目のページでは、「フェッチ＆追加操作は非常に柔軟です。セマフォに使用できます...」。 Fetch＆Addのコンセンサス数は2に等しいことがわかっているため、その論文の定理1を使用して、セマフォが2以下のコンセンサス数を持たなければならないことを示すことができます。証明は次のようになります。

証拠

Fetch＆Addによるセマフォの待機中の実装が存在すると仮定します。さらに、セマフォのコンセンサス数は2を超えていると仮定します。Fetch＆Addのコンセンサス数は2です。定理1から、2つ以上のプロセスのシステムにSemaphoreの待機中の実装は存在しないと結論付けることができます。 。これは、Fetch＆Addによる実装が存在するという仮定と矛盾しています。したがって、セマフォには2以下のコンセンサス数が必要です。

QED