ロックフリーのデータ構造。 1-開始

この記事が、ロックのないデータ構造に関する一連のメモの始まりを示していることを願っています。 ロックフリーデータ構造とは何か、それらを実装する方法、ロックフリーコンテナに適したSTL標準ライブラリのコンテナの概念、およびロックを使用する価値がある場合（あるとしても）について、私の経験、観察、考えをhabrasocietyと共有したいフリーのデータ構造。







ロックフリーデータ構造について話すことは、アトミック操作、特定のプログラミング言語で実装されたメモリモデル（もちろん、そのメモリモデルについて考えるほど言語が古くなっていない限り）、安全なメモリ解放、コンパイラ、彼らが使用する最適化、最新のプロセッサアーキテクチャ-これらのトピックはすべて、このサイクルである程度触れられます。 私は自分自身をそれらの絶対的な専門家とは考えていませんが、これらすべてのことについて話すことの自由を取ります。 その一方で、それらについての考えがなかったため、ロックフリーコンテナと安全なメモリ再生アルゴリズムのオープンソースC ++ライブラリであるlibcdsライブラリを作成および開発できませんでした。 CdsはConcurrent Data Structureの略で、接頭辞「lib」は奇妙なことに「ライブラリ」です。



図書館の歴史から始めましょう。 2006年に戻った。



その後、ビッグスリーのある電気通信事業者向けのソフトウェアを作成するかなり大きな会社で働きました。 ハードウェアプラットフォーム動物園用の非常に複雑なサーバーアプリケーションを開発しましたが、そもそもパフォーマンスの問題がありました（常にそうなるでしょう）。 特に、データ処理を並列化することで解決しました。 いつものように、並列化は共有データの出現をもたらし、そのデータへのアクセスは同期する必要がありました。 ある議論の中で、同僚が「ロックフリーキューについて何か聞いたことはありますか」と尋ねて歩き回りました。当時、私はそれについて何も知りませんでした。 しかし、Googleに尋ねたところ、ロックフリーキューの擬似コードが記載された記事がいくつか見つかりました。 それらを数回読んだ後、私は何も理解しませんでした。 より正確には、袖をまくり上げて「今すぐ！」と言った後、「私は何も理解していません」の状態になりました。常識で。 セグメンテーションフォールトと1か月戦った後、私の常識はあきらめました。 それから私は何も理解しませんでした。 私はこれが一般的にどのように機能するか理解できませんでした。ITが何らかの形で機能する場合でも、C ++でどのように実装できるかを理解していませんでした。 しかし、どういうわけかそれは機能するはずです。そうでなければ、賢い人はこれらの記事を書かないでしょうし、他の賢い人はそれらを参照しません（記事は科学的で、それぞれの終わりに、科学界ではいつものように、文学のリストが与えられました）。 これらのリンクをたどると、プロセッサアーキテクチャに関するソフトウェア開発者ガイドから、ロックフリーアルゴリズムを実装するための一般的なアプローチに関する記事のレビューに至るまで、1年の間に数十メガバイトの有用な情報を読みました。 途中で、このトピックで（もちろんC ++で）おもらしをして、特定のプリミティブを実装しました。 現時点（2006年から2007年）では、C ++ 11標準はまだ楽観的にC ++ 0xと呼ばれ、STLにはアトミックプリミティブはなく、インターフェイスの概要が示されただけで、コンパイラがアトミックプリミティブにいたずらをしたことがあります。特に重要な領域で機能しないコードを発行した。 2008年までに、libcdsライブラリのぼやけた輪郭が形になり始めました。 さまざまなプラットフォームでの最初のテストでは、勇気づけられる、時には驚くべき（「50倍高速になりました!!!」）結果が得られ、ロックフリーの世界に完全に飛び込みました。 2010年、私はSourceForgeにライブラリの最初の（0.5.0）バージョンを投稿しました。 現在、ライブラリの最新バージョンは1.4.0ですが、バージョン1.5.0で作業が進行中です。



ロックフリーデータ構造の一般的なレビューに進みます。 そのため、複雑なソフトウェアプロジェクト、特にサーバープロジェクトの設計と開発におけるプログラマの主なタスクは、ターゲットプラットフォームで利用可能なすべてのリソースを最も効果的に使用することです。 最新のコンピューターは、スマートフォンやタブレットでもマルチプロセッサ機器であるため、生産性を向上させる方法の1つはプログラムを並列化することです。 並列スレッド（スレッド）は、一部の共有データ（共有データ）を処理します。 したがって、私たちの主なタスクは、そのような共有データへの並列アクセスを整理することです。





前世紀の80年代には、いわゆる構造プログラミングが普及し、優れたプログラムを作成する方法として位置付けられました。 構造プログラミングの謝罪者は、パスカル言語の著者であるニコラス・ワースであり、ベストセラーの本「アルゴリズム+データ構造=プログラム」を執筆しました。 興味深いことに、この古い式は、オペレーティングシステムが提供するpthread、Win32 APIなどの最新のAPIの弱点を指しています：APIは、並列プログラム（このツールはスレッド、スレッド）を構築するためのツールを提供しますが、共有アクセスを提供する並列データ構造を構築するためのツールは提供しません。 代わりに、APIは、同期プリミティブの形式でデータアクセスを制限する手段を提供します。 ただし、同期は並列プログラムのボトルネックです。 基本的に、同期は並列処理の対極にあります。並列化アルゴリズム、シーケンシャルデータ構造を操作し、同期プリミティブ（クリティカルセクション、ミューテックス、条件変数（condvar））を提供します。 その結果、データ構造にアクセスするためにすべてのスレッドをキューに入れ、それにより並列処理を停止します。 同期プリミティブはOSカーネルのオブジェクトである場合があるため、そのようなオブジェクトへのアクセスは非常に高価になる可能性があります。コンテキストの切り替え、OSカーネルレベルへの移動、同期プリミティブで保護されたデータへのアクセスを待機するキューのサポートなどが必要になる場合があります。データ内の1つのポインターの値を変更するため、つまり、1つまたは2つのアセンブラー命令を実行します。 間接費は非常に高くなる可能性があります（実際にはあります）。 さらに、OSカーネルのオブジェクトは、数量が制限されたリソースであることを忘れないでください。



同期のもう1つの欠点は、スケーラビリティが低いことです。 スレッドの数が増えると、データへの同期アクセスがプログラムのボトルネックになります。 多くの場合、生産性の比例的な増加の代わりに、並列度の増加により、高負荷条件下でその劣化が生じます。



Wirthの公式「アルゴリズム+データ構造=プログラム」に基づいて、libcdの研究ではデータ構造のみに焦点を当てました。ライブラリには、並列ソートアルゴリズムや並列for-eachアルゴリズムはありません。 ライブラリには、競合するデータ構造（キュー、リスト、マップ、セットなど）と、ロックフリーデータをサポートするために必要なアルゴリズムのみが含まれています。まず、これらは安全なメモリ再生アルゴリズムです。 多くの場合、1つまたは別のデータ構造がいくつかの実装によって表されます。 これはもともと考えられていました：原則として、キューまたはマップを実装するいくつかの興味深いアルゴリズムがあり、一般的なケースではどちらが「良い」かわかりません：まず、「良い」または「悪い」という概念は相対的であり、特定のハードウェアに依存しますそして、特定のタスク、第二に、アルゴリズムを実装して他のアルゴリズムと比較するまで、それが良いかどうかわからないでしょう。 さて、アルゴリズムが実装およびデバッグされている場合、ライブラリでその場所をとってはいけません（そして、ユーザーに難しい選択を提供してください）？







アカデミック環境では、共有データへの同時アクセスを提供する競争力のあるデータ構造を実装する方法の研究により、いくつかの主要な領域が作成されました。

• ロックフリーのデータ構造。
• きめ細かいアルゴリズム。
• トランザクションメモリ

libcdsには、トランザクションメモリベースの実装はありません。 トランザクションメモリは、主に未来に焦点を当てた研究の広大な領域です。 トランザクションメモリに基づくアルゴリズムは、大まかに言って、メモリがアトミックトランザクションをサポートしていることを意味し、アトミックトランザクションはアトミックに受け入れ（コミット）または拒否（ロールバック）できます。 明らかに、そのようなメモリはハードウェアで実装する必要があります。 研究者自身によると、既存のソフトウェア実装には十分なパフォーマンスがありません。 正義のために、Haswell Intelプロセッサは既に命令システムでトランザクションサポートを持っていることに注意する価値があります。そのため、トランザクションメモリの原理に基づいたアルゴリズムの全盛期はもうすぐです。



粒度の細かいアルゴリズムは高度な同期方法であり、通常はOCが提供する同期プリミティブの使用ではなく、スピンロックなどの「軽い」アトミックプリミティブの使用に基づいて構築されます。 このようなプリミティブに基づいて、データ構造のノード（ノード）またはページ（ページ、バケット）のレベルで同期が実行され、この構造での操作のアルゴリズムに組み込まれている並列読み取りまたは並列記録を可能にするデータ構造が構築されます。 多くの場合、きめの細かいコンテナは、比較的軽い負荷でロックフリーコンテナのパフォーマンスに匹敵するパフォーマンスを示します。 libcdsライブラリは、そのようなデータ構造を軽視しません。



ロックフリーのデータ構造外部アクセス同期を必要としないデータ構造を呼び出します。 これは、非公式の純粋に技術的な定義であり、コンテナの内部構造とその操作を反映しています。 ここでは「外部」という言葉が意図的に強調されています。ロックフリーデータ構造のプロセッサからの特別なサポートを使用しないと、構築することはほとんど不可能であることを理解する必要があります。 ただし、ロックフリーコンテナーでのこの種のサポートは、コンテナーのシーケンシャルメソッドへのアクセスを同期するのではなく、コンテナーのメソッド内で配線されたアトミック変更メカニズム、またはコンテナーのコンポーネント（ノード、バケット、ページ）のレベルでの内部同期によって提供されます。



ロックフリーオブジェクトの正式な定義は[Her91]です。他の作業の結果に関係なく、 あるスレッドが有限数のステップでオブジェクトの操作を完了することを保証する場合、共有オブジェクトはロックフリーオブジェクト（非ブロッキング、非ブロッキングオブジェクト）と呼ばれますスレッド（これらの他のスレッドがクラッシュした場合でも）。 待機なしオブジェクトのより厳密な概念は、 各スレッドが有限数のステップでオブジェクトの操作を完了する場合、オブジェクトは待機なしであると言います。 ロックフリー状態は、少なくとも1つのスレッドの昇格を保証し、強力な待機フリー状態は、すべてのスレッドの正常な実行を保証します。 競合するデータ構造の理論には、線形化可能性[Her90]の概念もあります。これは、ロックフリーアルゴリズムの正確性の形式的証明で重要な役割を果たします。 大まかに言って、アルゴリズムの結果がアルゴリズムの最後に表示される場合、アルゴリズムは線形化可能です。 たとえば、リストへの挿入の結果は、挿入関数の最後に表示されます。 ばかげているように思えますが、リストに挿入するアルゴリズムを考え出すことができ、線形化はできません。 たとえば、すべての種類のバッファリングはこのプロパティの違反につながる可能性があります。挿入する代わりに、新しい要素をバッファに入れ、別のスレッドにコマンドを「バッファから要素をリストに挿入」し、要素の挿入を待たないことができます。 または、十分な数の要素がバッファに蓄積されたときにのみ挿入します。 次に、リスト内の挿入関数の最後で、要素がリスト内にあることを保証できません。 保証できるのは、現在または後でリストに要素が確実に挿入されることです （未来形！）。



これらの概念は、研究プロジェクトで広く使用されています。 私の記事は研究論文のふりをしていないので、「哲学的」な意味でロックフリーという用語を使用して、従来の同期パターンを使用せずに、または外部同期なしで構築された競合コンテナのクラスを指します。









ロックフリーアルゴリズムの特徴は何ですか？ おそらくあなたの目を引く最初のことは、その複雑さです。 単一リンクリストに実装されている通常のキューが何であるか想像できますか？ 非常に簡単なコード：



あなたは書くことができ、さらに短くすることができます。 そして、ここに、古典的なMichael＆Scottロックフリーキューアルゴリズムのエンキュー/デキューメソッド（プッシュ/ポップシノニム）があります（[Mic96]のように、コードはcds::intrusive::MSQueue



クラスのcds::intrusive::MSQueue



ライブラリから最小限の省略で取得されました）：





アルゴリズムは複雑です。 同じ一重リンクリストですが、通常のキューとロックフリーキューの単純な視覚的比較でさえ、すでに何かを言っています。 ロックフリーキューには次のように表示されます。

• 無限ループ-うまくいくまで操作を完了しようとします。 これは、アトミック操作compare_exchange
  
  
  
  を使用する典型的なパターンです。
• ロックフリーアルゴリズムでメモリ（ポインター）を使用して安全に作業する方法の1つを使用したローカル変数（ guards
  
  
  
  ）の保護。この場合は、ハザードポインター法です。
• アトミックプリミティブの適用C ++ 11- load, compare_exchange
  
  
  
  、メモリバリアmemory_order_xxx
  
  
  
  ;
• あるスレッドが別のスレッドを機能させるのに役立つ場合、ロックフリーアルゴリズムでは非常に一般的なトリックです。
• オプションのバックオフ戦略（ bkoff
  
  
  
  functor）の適用。ただし、多くのスレッドが同時にキューにアクセスする場合、場合によっては高負荷下でプロセッサを大幅にアンロードできます。

これらはすべて非常に広範囲にわたるため、個別の議論が必要なため、ここでは説明しません。 陰謀を続けましょう。 今後の記事でこれらのトピックをカバーしたいと考えています。



次の記事では、すべてのロックフリーデータ構造の基礎となる基本概念である原子性と原子プリミティブについて説明します。





そして最後に-有用な書籍（記事ではありません）。私の観点からは、競合プログラミングの問題を最も完全に扱っています。

現在までに、私は2つの良い作品を知っています。



1. Nir ​​Shavit、Maurice Herlihy 、マルチプロセッサプログラミングの芸術 。 私の知る限り、ロシア語への翻訳はありません。 世界で非常に有名なロックフリー作家の本は、それらを構築するための多くの並列アルゴリズムと方法を説明しています。 すべての例はJavaで記述されているため、作成者はメモリの解放、C ++メモリモデル（Javaではメモリモデルの方が厳密です）、およびJavaの言語自体に埋め込まれているその他のことについて心配する必要はありませんでした.C ++では、これらすべてを自分で記述する必要があります。 それにもかかわらず、本は非常に便利です。



2. Anthony Williams C ++ Concurrency in Action （ ロシア語の翻訳があります ）。 世界的に有名なC ++の著者の本は、C ++でのマルチスレッドプログラミングに特化しており、新しいC ++ 11標準と、並列アルゴリズムを実装するための標準によって提供される新しい機能について説明しています。 読むことを強くお勧めします。



参照：



[Her90] M. Herlihy、JM Wing Linearizability ：A Concentness Condition for Concurrent Objects 、ACM Transactions on Programming Languages and Systems、1990



[Her91] M. Herlihy 高度に同時データオブジェクトを実装するための方法論 、1991



[Mic96] M.マイケル、M。スコットシンプル、高速、および実用的な非ブロッキングおよびブロッキングコンカレントキューアルゴリズム