そのような驚くべきセマフォ

翻訳者から： Jeff Preshingはカナダのソフトウェア開発者であり、過去12年間Ubisoft Montrealに在籍しています。 彼はRainbow Six、Child of Light、Assassin's Creedなどの有名なフランチャイズの作成に携わっていました。 彼のブログでは、特にGame Devに関して、並列プログラミングの興味深い側面について頻繁に書いています。 今日、私はジェフの記事の一つの翻訳を公開したいと思います。

ストリームは待機する必要があります。 リソースに排他的にアクセスできるようになるまで、または実行するタスクが表示されるまで待ちます。 スレッドがOSカーネルスケジューラによって実行されない待機メカニズムの1つは、 セマフォを使用して実装されます。

セマフォは古くなっていると思っていました。 1960年代、マルチスレッドプログラムやその他のプログラムを書いた人はほとんどいなかったため、Edsger Dijkstraは新しい同期メカニズム-セマフォのアイデアを提案しました。 セマフォの助けを借りて、利用可能なリソースの数を追跡したり、ミューテックスのぎこちない類似物を作成したりできることは知っていましたが、これは、私が考えたように、範囲が限られています。

セマフォとアトミック操作のみを使用して、他のすべての同期プリミティブを作成できることに気付いたとき、私の意見は変わりました。

1. 軽量ミューテックス
2. 軽量の条件変数
3. 軽量な読み取り/書き込みロック
4. 食事哲学者の問題を解決するためのプリミティブ
5. 軽量セマフォ

これらのプリミティブはすべて、ユーザー空間で完全に実行されるという意味で軽量であり、オペレーティングシステムからスレッドロックを要求する前に（これはオプションの条件です）ループ内で回転できます（例はGitHubで利用可能です）。私のプリミティブライブラリは、Windows、MacOS、iOS、Linux、およびその他のPOSIX互換OSのシステムセマフォのラッパーであるSemaphoreクラスを実装しています。 これらのプリミティブをプロジェクトに簡単に追加できます。

バウンサーセマフォ

トレンディなナイトクラブの前の列のように、たくさんのスレッドが実行を待っていると想像してください。 セマフォは、入り口の前にある警備員です。 彼は、適切な指示が与えられた場合にのみ、クラブの中に入ることができます。



各スレッドは、このキューに入るタイミングを決定します。 ダイクストラはこの操作をPと呼びましたが、これはおそらくおかしなオランダ語の用語への参照でしたが、現代のセマフォの実装では、 待機操作のみを見つける可能性があります。 本質的に、スレッドがwaitメソッドを呼び出すと、キューになります。

バウンサー、つまり セマフォは、1つの操作のみを実行できる必要があります。 ダイクストラはこの操作をVと呼びました。 これまで、この操作に名前を付ける方法については合意がありません。 原則として、 post 、 release、またはsignal関数に出くわすことができます。 私は信号を好む。 このメソッドが呼び出されると、セマフォは待機中のスレッドの1つをキューから「解放」します。 （他の前に待機を呼び出したスレッドと同じである必要はありません。）

しかし、キューにスレッドがないときに誰かがシグナルを呼び出すとどうなりますか？ 問題ありません：スレッドのいずれかがwaitを呼び出すと、セマフォはブロックせずにそのスレッドをすぐにスキップします。 さらに、キューが空の状態でシグナルが 3回連続して呼び出されると、セマフォは、 待機を引き起こした次の3つのスレッドが待機せずにキューをバイパスできるようにします。



言うまでもなく、セマフォはキューが空のときにシグナル呼び出しの数をカウントする必要があります。 したがって、各セマフォには内部カウンタが装備されており、その値はシグナルが呼び出されると増加し、 待機が呼び出されると減少します。

このアプローチの利点は、 待機とシグナルが呼び出される順序に関係なく、結果が常に同じになることです：セマフォは、実行のために常に同じ数のスレッドをスキップし、同じ数の待機中のスレッドが常にキューに残ります。

1.軽量ミューテックス

以前の記事の1つで 、独自の軽量ミューテックスを実装する方法について既に説明しました 。 当時、私はこれが共通パターンの適用の一例にすぎないことを知りませんでした。その主なアイデアは、スレッドのブロックに関する意思決定を新しいエンティティ、 興行に委ねることです。 現在のスレッドはインラインで待機する必要がありますか？ 彼は待たずにセマフォを渡す必要がありますか？ 他のスレッドを起動する必要がありますか？



ボックスオフィスは、内部セマフォカウンタの現在の値を知らないのと同様に、キューで待機しているスレッドの数について何も知りません。 代わりに、彼はどういうわけか自分の州の歴史を保持しなければなりません。 軽量ミューテックスの実装について話している場合は、アトミックなインクリメントおよびデクリメント操作を備えた単一のカウンターで履歴を保存できます。 このカウンターをm_contentionと呼びました。 同時にミューテックスをキャプチャしたいスレッド数に関する情報を保存します。

class LightweightMutex { private: std::atomic<int> m_contention; // The "box office" Semaphore m_semaphore; // The "bouncer" 

スレッドがミューテックスをキャプチャする場合、ボックスオフィスを呼び出します。これにより、 m_contention値が増加します。

 public: void lock() { if (m_contention.fetch_add(1, std::memory_order_acquire) > 0) // Visit the box office { m_semaphore.wait(); // Enter the wait queue } } 

カウンタ値がゼロの場合、ミューテックスはマークされていない状態です。 この場合、現在のスレッドは自動的にミューテックスの所有者になり、待機せずにセマフォをバイパスし、ミューテックスによって保護されたコードセクションで引き続き動作します。

ミューテックスが別のスレッドによって既にキャプチャされている場合、カウンター値はゼロより大きくなり、現在のスレッドは、クリティカルセクションに入るまで順番を待つ必要があります。



スレッドがミューテックスを解放すると、ボックスオフィスは内部カウンタの値を1つ減らします。

  void unlock() { if (m_contention.fetch_sub(1, std::memory_order_release) > 1) // Visit the box office { m_semaphore.signal(); // Release a waiting thread from the queue } } 

デクリメント前のカウンタ値が1未満の場合、キューには待機中のスレッドはなく、 m_contention値は0に等しいままです。

カウンター値が1より大きい場合、別のスレッドまたは複数のスレッドがミューテックスをキャプチャしようとしたため、クリティカルセクションに入る順番を待っています。 この場合、セマフォがスレッドの1つを起動し、ミューテックスをキャプチャできるように、 signalを呼び出します。



チケット売り場への各呼び出しはアトミック操作です。 したがって、複数のスレッドがロックとロック解除を並行して呼び出しても、それらは常に連続して興行にアクセスします。 さらに、ミューテックスの動作は、興行収入の内部状態によって完全に決定されます。 興行にアクセスした後、スレッドは任意の順序でセマフォメソッドを呼び出すことができ、これは実行の一貫性に決して違反しません。 （最悪の場合、スレッドはセマフォキューの場所を奪い合います。）

このプリミティブは、スレッドがセマフォに頼らずにミューテックスをキャプチャできるため、「軽量」と呼ばれます。 システムコールを行わずに。 NonRecursiveBenaphoreと呼ばれるGitHubのミューテックスコードを公開しました。同じ場所に軽量のミューテックスの再帰バージョンもあります。 ただし、これらのプリミティブを実際に使用するための前提条件はありません。 とにかく、最もよく知られているミューテックスの実装は軽量です 。 ただし、このコードは、この記事で説明する他のすべてのプリミティブに使用されるアプローチの必要な図として機能します。

2.軽量の条件変数

ご注意 transl .:オリジナルでは、著者はこのプリミティブを自動リセットイベントオブジェクトと名付けましたが、そのようなクエリの検索エンジンはC＃クラスAutoResetEventへのリンクを提供し、その動作はいくつかの仮定でstd :: condition_variableと比較できます。

CppCon 2014で、ゲームエンジンの作成時に条件変数が広く使用されていることを確認しました。ほとんどの場合、あるスレッドに別のスレッド（おそらくスタンバイモード）を通知し、そのための作業があることを通知します（ 注：そのような作業としてグラフィックリソースを展開してGLコンテキストにロードするタスク ）。



つまり、 シグナルメソッドが何回呼び出されても、条件変数の内部カウンターが1より大きくならないようにする必要があります。実際には、 シグナルメソッドを呼び出すたびに、タスクを実行キューに入れることができます。 このアプローチは、 キュー以外のデータ構造を使用してタスクを実行に割り当てる場合でも機能します 。

一部のオペレーティングシステムは、条件変数またはその類似物を整理するためのシステムツールを提供します。 ただし、一度に数千のタスクをキューに追加すると、 signalメソッドの呼び出しがアプリケーション全体のパフォーマンスに大きく影響する可能性があります。

幸いなことに、興行パターンは、 シグナルメソッドの呼び出しに関連するオーバーヘッドを大幅に削減できます。 ロジックは、アトミック操作を使用してボックスオフィスエンティティ内に実装できるため、スレッドが順番を待つ必要がある場合にのみセマフォにアクセスできます。



このプリミティブを実装し、 AutoResetEventと呼びました 。 今回、興行収入は、キューで待機しているスレッドの数を別の方法で会計処理します。 m_statusが負の場合、その絶対値はセマフォで待機しているスレッドの数を示します。

 class AutoResetEvent { private: // m_status == 1: Event object is signaled. // m_status == 0: Event object is reset and no threads are waiting. // m_status == -N: Event object is reset and N threads are waiting. std::atomic<int> m_status; Semaphore m_sema; 

シグナルメソッドでは、 m_status変数の値を1に達するまでアトミックに増やします。

 public: void signal() { int oldStatus = m_status.load(std::memory_order_relaxed); for (;;) // Increment m_status atomically via CAS loop. { assert(oldStatus <= 1); int newStatus = oldStatus < 1 ? oldStatus + 1 : 1; if (m_status.compare_exchange_weak(oldStatus, newStatus, std::memory_order_release, std::memory_order_relaxed)) break; // The compare-exchange failed, likely because another thread changed m_status. // oldStatus has been updated. Retry the CAS loop. } if (oldStatus < 0) m_sema.signal(); // Release one waiting thread. } 

3.軽量の読み取り/書き込みロック

同じ興行パターンを使用して、読み取り/書き込みロックのプリミティブを実装できます。

このプリミティブは、ライターがない場合にスレッドをブロックしません。 さらに、ライターとリーダーの両方で飢vがなく、他のプリミティブと同様に、現在のスレッドの実行をブロックする前に一時的にスピンロックをキャプチャできます。 このプリミティブを実装するには、2つのセマフォが必要です。1つはリーダーを期待するため、もう1つはライターのためです。

4.食事する哲学者の問題

興行収入パターンを使用すると、これまで見たことのないかなり珍しい方法で、哲学者の食事の問題を解決できます。 提案されたソリューションが誰にとっても有用であるとは思わないので、実装の詳細には触れません。 セマフォの普遍性を示すために、このプリミティブの説明を含めました。

そのため、各哲学者（ストリーム）に独自のセマフォを割り当てます。 チケット売り場は、どの哲学者が現在食べているか、どの哲学者が食事を開始するように要求したか、およびこれらの要求のシーケンスを監視します。 この情報は、興行会社がすべての哲学者に最適な方法で取り付けられたセマフォを導くのに十分です。



2つの実装を提案しました。 それらの1つはDiningPhilosophersです 。これは、ミューテックスを使用して興行収入を実装します。 2つ目はLockReducedDiningPhilosophersで 、ボックスオフィスへの各呼び出しはロックフリーアルゴリズムとして実装されます。

5.軽量セマフォ

はい、そうです。興行収入パターンとセマフォの助けを借りて、別のセマフォを実装できます。

なぜこれをしなければならないのですか？ なぜならLightweightSemaphoreを取得するからです。 このようなセマフォには、待機中のスレッドがキューにない場合のシグナル操作が非常に安価です。 さらに、OSが提供するセマフォの実装に依存しません。 シグナルが呼び出されると、興行収入は 、基礎となるセマフォに頼ることなく、独自の内部カウンタの値を増やします。



さらに、ループ内でスレッドをしばらく待機させてから、ブロックすることができます。 このトリックにより、待機時間が事前定義された値よりも短い場合に、システムコールに関連するオーバーヘッドを減らすことができます。

GitHubリポジトリでは、すべてのプリミティブはLightweightSemaphoreに基づいています。 このクラスは、特定のOSによって提供されるセマフォに基づいて実装されているSemaphoreに基づいて実装されています。



Windows PCでLightweightSemaphoreとSemaphoreを使用するときに、提示されたプリミティブの速度を比較するためにいくつかのテストを実行しました。 対応する結果を表に示します。

	軽量セマフォ	セマフォ
testBenaphore	375ミリ秒	5503ミリ秒
testRecursiveBenaphore	393ミリ秒	404ミリ秒
testAutoResetEvent	593ミリ秒	4665ミリ秒
testRWLock	598ミリ秒	7126ミリ秒
testDiningPhilosophers	309ミリ秒	580ミリ秒

ご覧のとおり、動作時間は桁違いに異なる場合があります。 私は言わなければならない、私はすべての環境が同じまたは同様の結果を持つわけではないことを認識しています。 現在の実装では、スレッドはループの10,000回の反復を待ってからセマフォをロックします。 適応アルゴリズムを使用する可能性について簡単に検討しましたが、最良の方法は自明ではないように思われました。 だから私は提案を受け入れています。

セマフォと条件変数の比較

セマフォは、予想よりもはるかに有用なプリミティブであることが判明しました。 では、なぜC ++ 11 STLに欠けているのですか？ Boostに存在しなかったのと同じ理由で、ミューテックスと条件変数が優先されました。 ライブラリ開発者の観点からは、従来のセマフォの使用はしばしばエラーにつながります。

考えてみると、ボックスオフィスパターンは、条件変数のすべての操作がクリティカルセクションの最後で実行される場合の、通常の条件変数の最適化にすぎません。 AutoResetEventクラスを検討してください。 同じ動作でAutoResetEventCondVarクラスを実装しましたが、std：condition_variableを使用しました。 条件変数のすべての操作は、クリティカルセクションの最後に実行されます。

 void AutoResetEventCondVar::signal() { // Increment m_status atomically via critical section. std::unique_lock<std::mutex> lock(m_mutex); int oldStatus = m_status; if (oldStatus == 1) return; // Event object is already signaled. m_status++; if (oldStatus < 0) m_condition.notify_one(); // Release one waiting thread. } 

この方法は、2つの反復で最適化できます。

1. クリティカルセクションから各条件変数を取り出して、セマフォに変換します。 シグナルの独立性-セマフォに対する操作の待機シーケンスにより、この最適化が可能になります。 このステップの後、このメソッドの実装はすでに興行収入パターンの実装に似ています。
2. これで、すべての操作をCASに置き換えてロックフリー方式を実現できるため、システムのスケーラビリティが大幅に向上します。

これら2つの単純な最適化の後、AutoResetEventを取得します。



私のWindows PCでは、AutoResetEventCondVarをAutoResetEventに置き換えるだけで、アルゴリズムの速度が10倍になります。

翻訳者から：私は長い間何も翻訳していないので、訂正と説明に感謝します。