共有メモリ並行アルゴリズムとmutex/semaphoresの関係

Question

共有メモリベースの並行アルゴリズム（Peterson's/Bakery）とセマフォとmutexの使用の関係を理解し​​ようとしています。

最初のケースでは、OSの介入がないシステムがあり、プロセスは共有メモリとビジー待機を使用して自分自身を同期させることができます。

2番目のケースでは、OSはプロセス/スレッドにブロックする機能を提供し、ビジー待機する必要はありません。

セマフォに加えて共有メモリを使用したい場合（公平性/飢餓状態を確実にするため）、またはこれを行うためのより良い方法がOSにはありますか？

（一般的な概念については疑問がありますが、POSIX/Win32/JAVAスレッド固有の回答もまた興味深い）

ありがとうございます！

Answer 1

実際に欲しいものが忙しいということはまったく考えられません。ビジー待機は、何も達成せずにプロセッサ時間を消費するだけです。 "ビジーウェイト"アルゴリズムは有用ではないと言っているわけではありませんが、 "ビジーウェイト"の部分は目的のプロパティではありません。が必要なのは単なる必要な結果です。です。

PetersonのロックアルゴリズムとLamportのベーカリーアルゴリズムは基本的にmutexの概念の実装です。 OS機能は同じコンセプトの実装を提供しますが、トレードオフは異なります。

ミューテックスの「理想的な」実装では、「ゼロオーバーヘッド」があります---ミューテックスのロックを取得することは、現在所有されていない場合でも時間がかかりません。以前の所有者はロックを解除し、その間に待機中のスレッドはプロセッサ時間を消費しませんでした。

「ビジー待機」または「スピンロック」アルゴリズムは、ウェイクアップ時間を短縮するために待機スレッドによって使用されるプロセッサ時間を交換します。スレッドが現在プロセッサ上でスケジューリングされている場合、ビジーウェイタは、プロセッサがロックを獲得し、スレッドを同期させるのに必要なデータを転送するのと同じくらい速く起きるが、プロセッサ時間の最大割り当てを消費するのを待っている。スレッドの数が使用可能なプロセッサの数を超えている場合、これは現在、mutexを所有しているスレッドから時間がかかるため、待ち時間が長くなる可能性があります。しかし、場合によっては、ロック解除とロックの間の待ち時間が短くてもトレードオフの価値があります。

一方、待機中のスレッドをスリープ状態にするためにOS機能を使用する「ブロッキング」ミューテックスは、トレードオフが異なります。この場合、ミューテックスのロックを解除してからそれを取得する待機中のスレッドのロック解除までの時間はかなり長くなる可能性があり、おそらくビジーウェイトアルゴリズムよりも数百倍も大きくなる可能性があります。利点は、待機中のスレッドが実際に待機中にプロセッサ時間を消費しないため、OSはスレッドが待機している間に他の作業をスケジュールできることです。これにより、潜在的に全体的な待ち時間が短縮され、システム全体のスループットが向上する可能性があります。

一部のミューテックス実装では、ビジー待機とブロッキングの組み合わせを使用しています。ビジー状態のまま短時間待ってから、短時間でロックを取得できない場合はブロッキングに切り替えます。これは、スレッドが待機した直後にロックが解放され、スレッドが長い時間待たなければならない場合にはプロセッサ時間を消費しない場合、高速ウェイクの利点があります。また、短い待ち時間ではプロセッサ使用率が高く、長い待ち時間ではゆっくり目を覚ますという欠点があります。