4

このトピックについて少しだけ読んだだけですが、唯一の利点は競合の問題を回避することですが、ロックフリーのコードは非常に小さく基本的なものであるため、デッドロックの問題には重要な影響を与えません (fifos、 lifos、hash) で、デッドロックの問題が発生しなかったことを確認しました。

パフォーマンスがすべてです。これでよろしいですか？

4

7 に答える 7

9

ロックフリー プログラミングは (私の知る限り) 常にパフォーマンスに関するものですが、それ以外の場合は、ほとんどの場合、ロックを使用する方がはるかに簡単であり、したがって好ましいと言えます。

ただし、ロックのないプログラミングでは、デッドロックとライブロックを交換することになる可能性があることに注意してください。これは、診断するように設計されたツールがないため、診断がはるかに困難です (ただし、間違っている可能性があります)。

必要な場合にのみ、ロックフリーの道をたどってください。つまり、ロックの競合が激しく、パフォーマンスが低下しているシナリオがあります。（壊れていない場合は、修正しないでください）。

于 2009-09-06T11:48:19.773 に答える
9

いくつかの問題。

まもなく、64、128、および 256 コアのデスクトップ システムに直面することになります。このドメインでの並列処理は、現在の 2、4、8 コアの経験とは異なります。このような小さなシステムで正常に実行されるアルゴリズムは、高度な並列システムでは競合のために遅くなります。

その意味で、スケーラビリティの解決に大きく貢献するロックフリーは重要です。

また、Windows カーネルなど、ロックフリーが非常に便利な非常に特殊な領域もいくつかあります。ここでは、あらゆる種類のスリープ (待機など) が禁止されている実行モードがあり、データ構造に関して明らかに非常に制限されています。 、ただし、ロックフリーが優れたソリューションを提供する場合。

また、ロックフリーのデータ構造には多くの場合、障害モードがありません。もちろん、ロックベースのデータ構造がロックの取得に失敗する可能性がある場合、それらが実際に失敗することはありません。失敗を心配する必要がないため、コードが簡素化されます。

ロックフリーのデータ構造のライブラリを作成しました。これは間もなくリリースされます。開発者が十分に証明された API を手に入れることができれば、それをそのまま使用できると思います。ロックフリーかどうかは問題ではありません。基礎となる実装の複雑さについて心配する必要はありません。それが行く方法です。

于 2009-09-09T08:31:46.990 に答える
1

これはパフォーマンスに関するものですが、マルチスレッドの負荷を処理する機能に関するものでもあります。

  • ロックはコードの一部への排他的アクセスを許可します: スレッドがロックを持っている間、他のスレッドはスピン (ロックを取得しようとしてループ) またはブロックされ、ロックが解放されるまでスリープします (スピンが長すぎる場合に通常発生します)。 ;

  • アトミック操作は、割り込み不可能な組み込み CPU 命令を使用して、リソース (通常はワード サイズの変数またはポインター) への排他的アクセスを許可します。

ロックが他のスレッドの実行をブロックするため、プログラムの速度が低下します。アトミック操作は連続して (次々に) 実行されるため、ブロッキング*はありません。

(*)同じリソースにアクセスしようとする同時 CPUの数がボトルネックを作成しない限り - ただし、これを問題と見なすのに十分な CPU コアがまだありません。

私は、作業中のサーバーの待機なし (待機状態のないロックなし) の Key-Value ストアを作成する問題に取り組んできました。

Tokyo Cabinet のようなライブラリ (単純な配列である TC-FIXED でさえも) は、データベースの整合性を維持するためにロックに依存しています。

「書き込みスレッドがデータベースを操作している間、他の読み取りスレッドと書き込みスレッドはブロックされます」（東京内閣のドキュメント）

並行性のないテスト (1 スレッド テスト) の結果:

SQLite   time: 56.4 ms (a B-tree)
TC       time: 10.7 ms (a hash table)
TC-FIXED time:  1.3 ms (an array)
G-WAN KV time:  0.4 ms (something new which works, but I am not sure a name is needed)

同時実行性 (複数のスレッドが同じ DB で書き込みと読み取りを行う) では、G-WAN KV だけが同じテストに耐えました。これは、(他のものとは対照的に) ブロックされることがないためです。

そうです、この KV ストアを使用すると、開発者はスレッド化の問題を気にする必要がないため、使いやすくなります。ただし、このように機能させることは簡単ではありませんでした。

于 2011-05-12T19:17:32.390 に答える
1

プリエンプティブ スレッドの場合、ロックを保持している間に中断されたスレッドは、それ以外の場合は進行中のスレッドをブロックできます。Herlihy の定義によれば、他のスレッドは常に前進できるため、ロックフリーにはそのような問題はありません。

非プリエンプティブ スレッドの場合、Herlihy の定義ではスピン ロック ベースのソリューションでさえロックフリーであるため、それほど重要ではありません。

于 2009-09-07T10:52:55.983 に答える
1

また、スケーラビリティについてもです。最近では、パフォーマンスを向上させるために、取り組んでいる問題を並列化して、複数のコアにまたがってスケールできるようにする必要があります。

これを行う従来の方法は、並列アクセスを必要とするデータ構造をロックすることですが、真に並列に実行できるスレッドが増えるほど、ボトルネックが大きくなります。

そうそう、それはパフォーマンスについてです...

于 2009-09-06T11:46:09.710 に答える
0

どんなアルゴリズムでも待機なしで記述できることを数学的に証明した記事を見たと思います（つまり、基本的に、各スレッドが常に目標に向かって進んでいることを保証できます）。これは、あらゆる大規模アプリケーションに適用できることを意味し（結局のところ、プログラムは非常に多くのパラメーターを持つ単なるアルゴリズムです）、待機がないため、デッド/ライブロックが発生しないことが保証されます（発生しない限り）。本当に自由に待つことを妨げるバグがあります）、それはプログラムのその側を単純化します。一方、数学的な証明は、コード自体を実際に実装することとはかけ離れています（AFAIK、PCで実行できる完全にロックされていないリンクリストすらありません。ほとんどの部分をカバーしているものを見てきましたが、それらは通常、いくつかの一般的な機能を処理できません。

ちなみに、確率の法則やその他のさまざまな要因により、ロックフリーアルゴリズムが実際には待機なしと見なされることを示す別の証拠も見つかりました。

于 2009-10-15T12:23:48.090 に答える
0

  1. スケーラビリティは、効率的なマルチ/マニアコア プログラミングにおいて非常に重要な問題です。最大の制限要因は、実際にはシリアルで実行する必要があるコード セクションです (アムダールの法則を参照)。ただし、ロックの競合も非常に問題です。

  2. ロックフリー アルゴリズムは、従来のロックが持つスケーラビリティの問題に対処します。したがって、ロックフリーは主にパフォーマンスのためであり、デッドロックの可能性を減らすものではないと言えます。

  3. ただし、現在の x86 アーキテクチャでは、一般的なロックフリー アルゴリズムを作成することは不可能です。これは、現在の x86 では任意のサイズのデータ​​をアトミックに交換できないためです (また、Sun の ROCK を除く他のアーキテクチャにも当てはまります)。そのため、現在のロックフリーのデータ構造は非常に限定されており、特定の用途に特化しています。

  4. 現在のロックフリーのデータ構造は、10 年以内に使用されなくなると思います。ハードウェア支援の一般的なロックフリー メカニズム (そう、トランザクション メモリ、TM) が 10 年以内に実装されることを強く期待しています。ロックの問題を完全に解決することはできませんが、何らかの TM を実装すると、多くの問題 (優先順位の逆転やデッドロックを含む) が解消されます。ただし、TM をハードウェアに実装することは依然として非常に困難であり、x86 ではまだドラフトが提案されているだけです。

まだ長すぎる: 2 つの文の要約。

ロックフリーのデータ構造は、ロックベースのマルチスレッドプログラミングの万能薬ではありません (TM でさえそうではありません。スケーラビリティが真剣に必要で、ロックの競合に問題がある場合は、ロックフリーのデータ構造を検討してください。

于 2009-11-09T17:52:57.053 に答える