ブラウザよりも高速アクセス！
16 関係: ABA問題、並列計算、ミューテックス、リード・コピー・アップデート、ロック (情報工学)、トレードオフ、プリミティブ、データ構造、デッドロック、アルゴリズム、コンペア・アンド・スワップ、スレッド (コンピュータ)、セマフォ、優先順位の逆転、Java、排他制御。
ABA問題
ABA問題（英: ABA problem）とは、マルチスレッドプログラミングにおいて同期化の過程で発生する問題であり、ある記憶域を二回読み出し、二回の読み出しが同じ値であることを「変更がない」とみなすことにしたとき、二回の読み出しの間に別のスレッドが値を変更し、他の作業を行った後また元の値に戻すと、最初のスレッドが誤って「変更がなかった」とみなしてしまうというものである。 ABA 問題は、複数のスレッドや(or プロセス)が共有されたメモリにアクセスする場合に生じる。下記のイベントの流れは、ABA 問題を発生させる。.
新しい！!: Lock-freeとWait-freeアルゴリズムとABA問題 · 続きを見る »
並列計算
並列計算（へいれつけいさん、parallel computing）は、コンピュータにおいて複数のプロセッサで1つのタスクを動作させること。並列コンピューティングや並列処理とも呼ばれる。問題を解く過程はより小さなタスクに分割できることが多い、という事実を利用して処理効率の向上を図る手法である。また、このために設計されたコンピュータを並列コンピュータという。ディープ・ブルーなどが有名。 関連する概念に並行計算（へいこうけいさん）があるが、並行計算は一つのタスクの計算を並列化することにとどまらず、複数の相互作用しうるタスクをスレッドなどをもちいて複数の計算資源にスケジューリングするといった、より汎用性の高い処理をさす。 特に、並列計算専用に設計されたコンピュータを用いずに、複数のパーソナルコンピュータやサーバ、スーパーコンピュータを接続することで並列計算を実現するものをコンピュータ・クラスターと呼ぶ。このクラスターをインターネットなどの広域ネットワーク上に分散させるものも、広義には並列計算に属すが、分散コンピューティングあるいはグリッド・コンピューティングと呼び、並列計算とは区別することが多い。.
新しい！!: Lock-freeとWait-freeアルゴリズムと並列計算 · 続きを見る »
ミューテックス
ミューテックス (Mutex) とは、コンピュータプログラミングにおける技術用語。クリティカルセクションでアトミック性を確保するための排他制御や同期機構の一種である。Mutexという語はMUTual EXclusion (相互排他、排他制御) の省略形である。ここでは、狭義の排他制御について述べる。.
新しい！!: Lock-freeとWait-freeアルゴリズムとミューテックス · 続きを見る »
リード・コピー・アップデート
リード・コピー・アップデート（read-copy-update、RCUと略記）とは、オペレーティングシステムにおいて一種の排他制御RCU は一般的な意味での排他制御の実装ではない。通常の排他制御機構が時間的に排他するのに対して、RCUではデータを更新中もデータの古いバージョンへの参照を同時に行えるようにすることで、空間的な排他を行う。を実装する同期機構であり、の代替手段として使われることがある。参照において待ち状態が生じず、極めてオーバーヘッドが低い。しかしRCUにおけるデータ更新は、既存の参照者のために古い版のデータ構造を保持しつつ行うため、時間と空間（メモリ）をより多く必要とする。古い版のデータ構造は、既存の参照者が全てアクセスを完了した後で回収される。.
新しい！!: Lock-freeとWait-freeアルゴリズムとリード・コピー・アップデート · 続きを見る »
ロック (情報工学)
情報工学におけるロック (lock) とは、計算機システム内に複数の動作主体（プロセス，スレッド等）のある環境で、データやデバイスなどのリソースへのアクセス制限を課す同期機構。ロックは並行性制御ポリシーを実施する手法のひとつである。アクセス制限を課す動作を「ロックする」，「ロックを取得する」などと表現する．また対義語として，制限を解除することをunlock（アンロック，ロック解放，ロック解除）と言う．.
新しい！!: Lock-freeとWait-freeアルゴリズムとロック (情報工学) · 続きを見る »
トレードオフ
トレードオフ（）とは、一方を追求すれば他方を犠牲にせざるを得ないという状態・関係のことである。トレードオフのある状況では具体的な選択肢の長所と短所をすべて考慮したうえで決定を行うことが求められる。.
新しい！!: Lock-freeとWait-freeアルゴリズムとトレードオフ · 続きを見る »
プリミティブ
プリミティブ プリミティブ (primitive): 原始的、素朴な、幼稚な、などといった意味。.
新しい！!: Lock-freeとWait-freeアルゴリズムとプリミティブ · 続きを見る »
データ構造
データ構造（データこうぞう、data structure）は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。 ソフトウェア開発において、データ構造についてどのような設計を行うかは、プログラム（アルゴリズム）の効率に大きく影響する。そのため、さまざまなデータ構造が考え出されている。 多くのプログラムの設計において、データ構造の選択は主要な問題である。これは大規模システムの構築において、実装の困難さや質、最終的なパフォーマンスはベストのデータ構造を選択したかどうかに大きく依存してきたという経験の結果である。多くの場合、データ構造が決まれば、利用するアルゴリズムは比較的自明に決まる。しかし場合によっては、順番が逆になる。つまり、与えられた仕事をこなす最適なアルゴリズムを使うために、そのアルゴリズムが前提としている特定のデータ構造が選択される。いずれにしても適切なデータ構造の選択は極めて重要である。 この洞察は、多くの定式化された設計手法やプログラミング言語において、データ構造がアルゴリズムよりもキーとなる構成要素となっていることに現れている。大半の言語は異なるアプリケーションにおいてデータ構造を安全に再利用できるよう、実装の詳細をインターフェイスの背後に隠蔽するような、モジュール化のしくみを備えている。C++やJavaといったオブジェクト指向プログラミング言語はクラスをこの目的に用いている。 データ構造は専門的なプログラミングにとって非常に重要なので、C++におけるSTLや、Java API、および.NET Frameworkのようなプログラミング言語の標準ライブラリや環境において多くのデータ構造がサポートされている。 データ構造が実装を表すのかインターフェースを表すのかについてはいくらか議論がある。どのように見えるかは相対的な問題なのかもしれない。データ構造は2つの関数の間にあるインターフェイスとして見ることもできるし、データ型に基づいて構成されたストレージにアクセスする方法を実装したものとして見ることもできる。.
新しい！!: Lock-freeとWait-freeアルゴリズムとデータ構造 · 続きを見る »
デッドロック
デッドロック (英: deadlock) とは、特に計算機科学において、2つ以上のスレッドあるいはプロセスなどの処理単位が互いの処理終了を待ち、結果としてどの処理も先に進めなくなってしまうことを言う。 また、合弁契約書などにおいてパートナーと利害関係がぶつかるような問題が生じた場合の解決方法を定めた条項を「デッドロック条項（Deadlock Clause）」と言う。 英語ではもともと行き詰まりの意味である。.
新しい！!: Lock-freeとWait-freeアルゴリズムとデッドロック · 続きを見る »
アルゴリズム
フローチャートはアルゴリズムの視覚的表現としてよく使われる。これはランプがつかない時のフローチャート。 アルゴリズム（algorithm ）とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。算法と訳されることもある。 「問題」はその「解」を持っているが、アルゴリズムは正しくその解を得るための具体的手順および根拠を与える。さらに多くの場合において効率性が重要となる。 コンピュータにアルゴリズムをソフトウェア的に実装するものがコンピュータプログラムである。人間より速く大量に計算ができるのがコンピュータの強みであるが、その計算が正しく効率的であるためには、正しく効率的なアルゴリズムに基づいたものでなければならない。.
新しい！!: Lock-freeとWait-freeアルゴリズムとアルゴリズム · 続きを見る »
コンペア・アンド・スワップ
ンペア・アンド・スワップ（Compare-and-Swap、CAS）とは、アトミックに、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納するCPUの特別な命令の一種である。この操作の結果、置換が行われたかどうかを示す必要があり、単純な真理値を返すか、そのメモリ位置から読み込んだ内容（書き込んだ内容ではない）を返す。 CAS命令はマルチプロセッサシステムでセマフォなどを実装するのに使われる。 また、マルチプロセッサシステムでLock-freeとWait-freeアルゴリズムを実装するのにも使われる。Maurice Herlihy(1993年)はこれが単なるリード、ライトやテスト・アンド・セットでは実装できないことを示した。 CAS命令を利用したアルゴリズムは、一般にあるキーとなるメモリ位置を読み取り、その古い値を記憶しておく。その古い値に基づいて、新しい値を計算する。その後、CAS命令でそのメモリ位置に新しい値を格納するが、そのときにCAS命令の比較によって計算に用いた古い値が置換時にもそのまま入っていることを確認する。CAS命令が比較に失敗した場合、最初から処理をやり直す。メモリ位置を再度読み取って、値を計算し、CAS命令を再実行するのである。 このようなアルゴリズムは False Positive（偽陽性）という問題（あるいは ABA問題）に対処しなければならない。古い値を読み取った後、CAS命令を実行するまでの間に、そのメモリ位置の内容が複数回書き換えられて偶然もとの古い値と同じビットパターンになっている可能性がある。CAS命令だけではこの事実を検出できない。その値はパターンは同じでも全く異なった意味かもしれない。 CAS命令はシングルプロセッサのシステムには不要である。その場合、単に割り込みを不可にすることでアトミック性が達成される。しかし、マルチプロセッサシステムでは同時に全てのプロセッサで割り込みを不可とすることは困難だし、不十分でもある。他のプロセッサでも同じメモリ位置にアクセスしようとしているかもしれない。CAS命令はそのようなプロセッサ間の衝突を防ぎ、アトミックにメモリ位置をチェックして変更することを可能にする。.
新しい！!: Lock-freeとWait-freeアルゴリズムとコンペア・アンド・スワップ · 続きを見る »
スレッド (コンピュータ)
レッド（thread）とは、CPU利用の単位。プロセスに比べて、プログラムを実行するときのコンテキスト情報が最小で済むので切り替えが速くなる。スレッドは、thread of execution（実行の脈絡）という言葉を省略したものである。 プログラミングの観点からみると、アプリケーションの処理の「実行の脈絡」は1つでないことが多い。これをシングルスレッドで実現しようとするとシグナルやタイマーを駆使してコーディングすることになる。また、複数のプロセスに分割してプロセス間通信で協調動作させるという方法もある。しかし、いずれの場合もそれらの機能を使うための余分な、本来のアルゴリズムと関係ないコーディングが必要となる。スレッドを使用したプログラミングは本来のアルゴリズムに集中しやすくなり、プログラムの構造が改善されるという効果がある。.
新しい！!: Lock-freeとWait-freeアルゴリズムとスレッド (コンピュータ) · 続きを見る »
セマフォ
マフォ（semaphore）とは、計算機科学において、並列プログラミング環境での複数の実行単位（主にプロセス）が共有する資源にアクセスするのを制御する際の、単純だが便利な抽象化を提供する変数または抽象データ型である。 ある資源が何個使用可能かを示す記録と考えればわかりやすく、それにその資源を使用する際や解放する際にその記録を「安全に」（すなわち競合状態となることなく）書き換え、必要に応じて資源が使用可能になるまで待つ操作が結びついている。セマフォは競合状態を防ぐ便利なツールであるが、セマフォを使うことでプログラムにおける競合状態がなくなると保証するものではない。任意個の資源を扱うセマフォをカウンティングセマフォ、値が0と1に制限されている（ロック/アンロック、使用可能/使用不可の意味がある）セマフォをバイナリセマフォと呼ぶ。後者はミューテックスと同等の機能を持つ。 セマフォの概念はオランダ人計算機科学者エドガー・ダイクストラが考案した。今ではさまざまなオペレーティングシステムで採用されている。 「semaphore」の本来の語義は「視覚による通信・信号」全般を指し、腕木通信や、それから派生した鉄道の腕木信号（や自動車の方向指示器）、手旗信号などが含まれる。日本語でのセマフォは、本用途（コンピュータ、プログラミング関連）に限られる。 語源の腕木式信号機.
新しい！!: Lock-freeとWait-freeアルゴリズムとセマフォ · 続きを見る »
優先順位の逆転
優先順位の逆転（ゆうせんじゅんいのぎゃくてん、Priority Inversion）とは、スケジューリングにおいて優先順位の高いタスクが必要としているリソースを優先順位の低いタスクが占有しているときに発生する状態である。低い優先順位のタスクがそのリソースを解放するまで高い優先順位のタスクが実行をブロックされるため、実質的に二つのタスクの優先順位が逆転する。他の中程度の優先順位のタスクがその途中で動作するなら、そのタスクは高優先順位のタスクと低優先順位のタスクの両方に優先して動作していることになる。 運が良ければ、優先順位の逆転があっても被害をまぬがれるかもしれない。優先順位の高いタスクの遅延により致命的な何かが起きる前に、運良く、低優先順位のタスクがリソースを解放して、それで間に合うかもしれないからである。しかし一方、優先順位の逆転が深刻な問題の原因となる状況も多々ある。もし高優先順位のタスクがリソーススタベーションの原因となっているのにブロックされているなら、システム全体の誤動作を引き起こすかもしれないし、事前に定義された矯正手段（例えば、ウォッチドッグタイマによるシステム全体のリセット）の引き金となる可能性もある。火星探査船「マーズ・パスファインダー」で発生した問題は、リアルタイムシステムでの優先順位の逆転が引き起こした典型的な例である（#外部リンク参照）。 優先順位の逆転はシステムの見た目の性能も低下させる。低優先順位のタスクは迅速に処理しなくてもよいから低優先順位に設定されている（例えばそれはバッチ処理かもしれないし、他の非対話型処理かもしれない）。同様に、高優先順位のタスクは時間的制限が問題となるから高優先順位に設定される。対話的にユーザーにデータを提供している場合もあるし、何らかのリアルタイムな応答を保証した処理をしているかもしれない。優先順位の逆転は低優先順位のタスクが高優先順位のタスクをブロックしてしまうので、システムの応答性能の低下を招き、保証された応答性能の違反となる可能性もある。 この問題は1970年代から知られているが、この状況を予測する確実な方法はない。様々な解決策は存在している。最も一般的な解決策は次のようなものである。.
新しい！!: Lock-freeとWait-freeアルゴリズムと優先順位の逆転 · 続きを見る »
Java
Java（ジャバ）は、狭義ではプログラミング言語Javaを指す。広義では言語仕様以外にも、仕様が与えられているJavaクラスライブラリやJava仮想マシン、さらにはJDKやJREなどの公式のものをはじめとする、場合によってはサードパーティのものなどを含め曖昧にJavaプラットフォームと総称されるようなものなどのエコシステムなどを指すこともある。構文についてはJavaの文法の記事を参照。.
新しい！!: Lock-freeとWait-freeアルゴリズムとJava · 続きを見る »
排他制御
排他制御せずに ''i'' と ''i+1'' という2つのノードを同時に連結リストから外す操作を行うと、結果として ''i+1'' のノードが外れないという状態になりうる。 排他制御（はいたせいぎょ）とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（mutual exclusion）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。 換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが Solution of a problem in concurrent programming control（並行プログラミング制御における問題の解法）と題した論文で扱ったのが最初であるTaubenfeld.
新しい！!: Lock-freeとWait-freeアルゴリズムと排他制御 · 続きを見る »
