| 翻訳と辞書 |
| Lock-freeとWait-freeアルゴリズム ： ウィキペディア日本語版 |
Lock-freeとWait-freeアルゴリズム
Lock-freeとWait-freeアルゴリズムとは、共有データにロックをかけて保護するアルゴリズムとは違い、複数のスレッドが同時並行的に、ある対象データを壊すことなしに読み書きすることを可能にするアルゴリズムである。Lock-free とはスレッドがロックしないことを意味しており、全てのステップにおいてシステムが必ず進行する。通常ロックを所有するスレッドは、コンテキストスイッチが発生した時点で、全体の進行を阻止することがあるので、Lock-free ではミューテックスやセマフォといった、排他制御のためのプリミティブが使われていないということになる。Wait-free とは、他のスレッドの動作に関係なく、スレッドがいかなる操作も有限のステップで操作を完了させられることを指す。Wait-free なアルゴリズムは Lock-free である。
== 意義 ==
マルチスレッドプログラミングに置いて古典的な手法は、共有リソースにアクセスするときはロックをかけることである。ミューテックスやセマフォといった排他制御はソースコードのある領域( クリティカルセクション)を同時に実行しないようにし、それゆえ、共有メモリの構造を破壊しないようにする。もし、他のスレッドが事前に獲得したロックをあるスレッドが獲得しようとするときは、ロックが解放されるまでスレッドの動作は停止する。
スレッドが停止することは多くの理由で望ましくない。まず、スレッドがブロックされている間は、何も出来ない。そして、スレッドが優先順位の高い処理やリアルタイム処理を行っているならば、そのスレッドを停止することは望ましくない。また、複数のリソースにロックをかけることは、デッドロック、ライブロック、優先順位の逆転を起こすことがある。さらに、ロックを使うには、並列処理の機会を減らす粒度の荒い( = クリティカルセクションが長い )ロックを選択するか、バグを生みやすく注意して設計しないといけない粒度の細かいロックを選択するかというトレードオフ問題を生む。
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Lock-freeとWait-freeアルゴリズム」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|