リーダーの効果的な実装–「インターロック変数アクセス」に基づくライターロック

エントリー

私が取り組んでいるプロジェクトの詳細は、一方ではサードパーティライブラリの使用が許可されていないということです（いくつかの例外を除きます）。他方では、非常に深いコードの最適化に重点が置かれています。 そのため、多くの場合、独自の実装の形で車輪を再発明する必要があります。



この出版物の過程で、いわゆるアトミック操作に基づいて、よく知られているリーダーライターロック同期プリミティブを実装するというアイデアを共有したいと思います。 ご存知のように、リーダーライターロックは、同時読み取りと書き込みを回避するように共有リソースへのアクセスを同期する問題を解決するように設計されていますが、同時に任意の多数のスレッドの並列読み取りを許可します。

ソリューションを検索する

当初、私はそのタスクにかなり軽薄に反応しましたが、結局は無駄になりました。 そもそも、利用可能なリソースを見た後、私が望む実装を見つけられませんでした。 判明したように、最大​​の問題は、着信する「リーダー」と「ライター」をブロックして、永久にこの状態のままにならないようにすることでした。 たとえば、 条件変数を使用して待機を整理する場合、着信ストリームをブロックする必要がある状況に陥るのは非常に簡単ですが、ブロックが発生している間、リソースを所有するストリームはその処理を終了し、送信された完了信号は宛先に到達しません。 これにより、「待機」状態への移行が正常に完了し、この実装は失敗します。 問題は実際に追加のロジックを導入することで解決できますが、私の場合、そのような実装は、各着信ストリームの無意味で容赦のないロックよりもさらに遅くなりました。 もちろん、私はこれが絶対的な真実であるというふりをせず、何かを見逃したかもしれませんが、私は他の可能性を探し始めました...この間ずっと、私はより簡単な連動変数アクセスメカニズムを使用して問題を解決できると感じました以前は、 ダブルチェックロックの最適化を非常にエレガントに扱っていました。 だから、私はこの方向に考え始め、結果として次のことが起こりました...

実装

このプロジェクトでは、QNXシステム（製品の実際の指向）とWindows（エミュレーション、デバッグなど）のサポートが必要です。 2番目の方がはるかに人気があるので、C ++の実装を特別に提供します。 しかし、私はPOSIXへの移植の瞬間に専念します。 だから：

クラス空白

class CRwLock { public: CRwLock(); void readLock(); void writeLock(); void readUnlock(); void writeUnlock(); private: static const LONG WRITER_BIT = 1L << (sizeof(LONG) * 8 - 2); LONG mWriterReaders; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

一連の機能を使用すると、すべてが明らかであり、私の意見ではコメントを必要としません。 mWriterReadersクラスの単一フィールドについて話しましょう。

• 最後の非符号ビットは、単一の「ライター」の存在の符号の下で与えられ、彼がリソースを所有するときに設定する必要があります。 実際、それを使用するには、定数WRITER_BIT
• 残りは30ビットの素整数として使用されます。 リソースを読み取るスレッドの数（「ライター」ビットが設定されていない場合）または読み取りを待機しているスレッド（「ライター」ビットが同時に設定されている場合）をそれぞれ記録します。

クラスコンストラクター

 CRwLock::CRwLock() : mWriterReaders(0) { }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

リソースを所有している誰かがいないことに対応する初期状態を確立するか、より簡単に言えば、すべてのビットを0にリセットするという、唯一のタスクを実行することが求められます。

読み取りロック

おそらくご想像のとおり、目標を達成するために、単一の整数変数でアトミック操作を使用します。

 void CRwLock::readLock() { if(::InterlockedExchangeAdd(&mWriterReaders, 1) >= WRITER_BIT) { while(::InterlockedCompareExchange(&mWriterReaders, 0, 0) >= WRITER_BIT) { Sleep(0); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

入力時に、すぐにリーダーに自分自身を追加し、同時に誰かが録音しているかどうかを確認します（書き込みストリームのビットが設定されているため、数値自体がこの値以上である場合）。 そうである場合、書き込み操作の終了と残りを待つ必要があります。 これを行うには、同じ「ライター」ビットがチェックされるスピンロックオプションを選択し、リセットされるとすぐに、読み取りを待機している全員がアクセスを取得します（この実装ではスレッドの読み取りが優先されますが、これについては後で詳しく説明します）。



ここでは、待機中のスレッドがアクティブにCPUリソースを消費している、いわゆるビジー待機の問題について説明します。 この場合、 Sleep（0）命令を追加することで妥協しました。これは、割り当てられたプロセスから残りの時間をスケジューラーに転送し、スケジューラーは優先度に応じて他のスレッドに発行できます。 言い換えれば、時間はアイドル状態で燃え尽きることはありませんが、有効に使用できます。 一方、待機ストリームからフラグの状態の変化までの反応の深刻度は鈍化しています。これは、スレッドのアイアンとスレッドによって実行される操作の私の構成の場合、テストプログラムの動作時間の約10％の増加をもたらしました。 ただし、システム全体が確実に自由なCPUを自由に使用できることを忘れないでください。



POSIXの場合、 Sleep（0）の代わりにsched_yieldを使用できます

書き込みロック

 void CRwLock::writeLock() { while(::InterlockedCompareExchange(&mWriterReaders, WRITER_BIT, 0) != 0) { Sleep(0); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

書き込みが必要なスレッドは、誰もがリソースを解放するまで（絶対ゼロ）待機する必要があり、その場合にのみリーダーに対して自身を確立します。 したがって、リーダーの優先順位-既存の記録ストリームでスタンバイ状態に切り替えた場合でも、同じブロックされた「ライター」よりも優先されることが保証されています。

ロック解除

 void CRwLock::readUnlock() { ::InterlockedExchangeAdd(&mWriterReaders, -1); } void CRwLock::writeUnlock() { ::InterlockedExchangeAdd(&mWriterReaders, -WRITER_BIT); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

読み取りの場合は単純なデクリメント、書き込みの場合はビットのリセット。

あとがきの代わりに

私の場合、クリティカルセクションを使用した場合と比べて、パフォーマンスの良い結果が得られました。クリティカルセクションは、ストリームの書き込みと読み取りの比率を変更しながら予測どおりに動作します。



私はあなたの批判とコメントに喜んでいるでしょう。