並行性制御

情報技術および計算機科学における並行性制御（へいこうせいせいぎょ、）または同時実行制御（どうじじっこうせいぎょ）とは、特にプログラミングとOSとマルチプロセッシングとデータベースにおいて、並行処理の結果が可能な限り素早くかつ正しく得られることを保証することである。
コンピュータシステムは、ソフトウェアもハードウェアも、モジュールまたはコンポーネントで構成される。各コンポーネントは何らかの一貫性規則に従って正しく動作するよう設計されている。コンポーネント間でメッセージをやり取りするか（記憶装置内で）データを共有して並行動作する際、あるコンポーネント間の一貫性が他のコンポーネントによって妨害されることがある。並行性制御の一般的な領域は、同時並行的に相互作用しながら動作するコンポーネント間の一貫性を保つための規則、技法、設計方法論、理論を提供し、結果としてシステム全体の一貫性と正確性を提供する。並行性制御をシステムに導入することは、一般に若干の性能低下を生じる操作上の制約を適用することを意味する。操作一貫性と正確性は、妥当な以上の性能低下を伴わずに可能な限り効率的に達成されるべきである。
データベースにおける並行性制御.
ここでデータベースと称しているのは、汎用のデータベース管理システム (DBMS) に限らず、トランザクションを行うあらゆるシステムである。DBMSはデータベースの並行性制御問題と同時にOS一般の並行性制御問題とも関わりが深い。
データベースについて、トランザクションがデータ完全性を失うことなく安全に実行されることを保証する手法である。並行性制御は特にデータベース管理システム (DBMS) に適用され、トランザクションがACID原則（後述）に従って安全に実行されることを保証する。DBMSはシリアライズ可能 (Serializable) で復旧可能 (Recoverable) なスケジュールだけを許すよう設計されなければならず、中断されたトランザクションを取り消す際にコミット済みのトランザクションの結果が失われないことを保証しなければならない。
データベース管理システム (DBMS)、他のトランザクションオブジェクト、および関連する分散アプリケーション（例えば、グリッド・コンピューティングやクラウドコンピューティング）の並行性制御は、それぞれのデータベースのデータ完全性を損なうことなく同時並行にトランザクションを実行することを保証する。したがって並行性制御は、事実上あらゆる汎用データベースシステムにおいて、複数のトランザクションが時間的に重なりつつ同じデータにアクセスする際の正確性の基本要件である。その結果、1970年代初めにデータベースシステムが出現して以来ずっと関連した様々な研究成果が蓄積されていき、データベースシステムの並行性制御理論が確立している。直列化可能性理論は、並行性制御の技法と機構を効率的に設計し分析することを可能にする。抽象データ型に対するアトミックなトランザクションについての並行性制御理論もある。そちらの理論の方が洗練されていて複雑で適用範囲が広く、最近では上述の古典的理論よりもデータベースの教科書でよく採用されている。どちらの理論も一長一短であり、ある意味では相補的でもある。
正確性を確保するため、DBMSは「直列化可能な」トランザクションスケジュールのみを保証するのが普通だが、アプリケーションが正確性をあまり求めていない場合のみ直列化可能性を意図的に緩和して性能を向上させることもある。トランザクションが失敗した場合の正確性を確保するには、スケジュールが回復可能性という属性を持つ必要がある。DBMSはまた、「コミット」されたトランザクションの結果が失われないことを保証し、「中断」（ロールバック）されたトランザクションの結果が関連するデータベースに残存しないことも保証する。トランザクション全体の特性は一般に後述するACID原則にまとめられる。データベースが分散されるか、分散環境で協調動作する必要がある場合（例えば、1990年代初めの連合データベースや21世紀のクラウドコンピューティング）、並行性制御機構の効果的分散に注目が集まる。
トランザクションとACID原則.
「データベース・トランザクション」（または「アトミック・トランザクション」）の概念は、衝突がいつでも発生しうる不完全な環境でのデータベースシステムの動作をよく理解し、その上で衝突から回復できるよう発展してきた。データベース・トランザクションは仕事の単位であり、データベース上のいくつかの操作（データベースオブジェクトの読み取り、書き込み、ロック取得など）をカプセル化するのが一般的で、データベースや他のシステムでの抽象概念である。個々のトランザクションは、どのプログラム/コードの実行がそのトランザクションに含まれているかで境界が明確に定義され、プログラマが特別なトランザクションコマンドを使って決定する。データベースシステムは全てのトランザクションが以下の原則に従うことを要求する。
アトミック・トランザクションの概念から、時間をかけて (BTM) へと発展したが、BTMは実際にはワークフローの実装でありアトミックではない。しかし、そのように発展したトランザクションもコンポーネントとしてアトミック・トランザクションを利用している。
並行性制御機構.
分類.
並行性制御機構は以下のように大別される。
カテゴリが異なれば、性能も異なる。トランザクションの完了レート（スループット）は、トランザクションの種類の比率、計算の並列性レベルなどに左右される。トレードオフに関する知識が入手でき、選択が可能なら、最も性能が高くなる方式を選択すべきである。
2つ以上のトランザクションが互いにブロックしあう状況からデッドロックが生じ、関連するトランザクション群は処理を続行できなくなり、完了不可能となる。楽観的でない機構の多くはデッドロックを発生させる可能性があり、ストールしているトランザクションを意図的に中断させ、即座に再試行させることで問題を解決するしかない。一般にデッドロックはそう頻繁に発生するものではない。
ブロック、デッドロック、中断はいずれも性能を低下させるので、どのような並行性制御を選択するかはトレードオフの問題である。
技法.
並行性制御には多数の技法が存在する。その多くは上述の分類のどれであっても実装可能である。主な技法にはそれぞれ多数の派生があり、複数の技法を組み合わせたものもある。
上掲の技法に加えて以下のような並行性制御技法も使われている。
データベースシステムでの最も一般的な機構は1970年代以降「強く厳密な（厳格な）ツーフェーズロック」(SS2PL, Rigorous 2PL) であり、ツーフェーズロック (2PL) と コミットメント順序付け (CO) の特殊ケース（派生）である。悲観的機構に分類される。歴史的経緯から長い名前がついているが、機構は単純で「トランザクションが終わった後のみ、そのトランザクションが確保した全ロックを解放する」というものである。SS2PLはこの機構によって生成される全スケジュールも指し、SS2PLスケジュールはSS2PL属性を持つ。
目標.
並行性制御は、個々のトランザクションが完全性規則に従うようにし、結果的にシステム全体が完全性を保つようにする。正確性を保つと同時に可能な限り性能を向上させることが目標である。プロセス群、コンピュータ群、コンピュータネットワーク群においてトランザクションが分散されることが多くなるにつれ、並行性制御の必要性は増大している。並行性制御は、データ復旧とレプリケーションにも影響を受ける。
分散正確性.
ITの急激な進歩によってコンピュータネットワークの性能が向上し、ローカルな処理と分散処理の違いは曖昧になりつつある。そのためローカルな技法を極めて効率的に分散環境（例えば、コンピュータ・クラスターやマルチコアプロセッサ）に適用するのが一般的となっている。しかし、ローカルな技法には限界があり、分散のスケールが拡大すると対応できない。
OSにおける並行性制御.
マルチタスクOS、特にリアルタイムOSは、動作中の全タスクが同時に動作しているかのように見せる必要があるが、ハードウェアの制限があるため実際にある時点で同時に動作しているタスクはごく少数である。マルチタスクは全タスクが互いに完全に独立しているなら単純である。しかし複数のタスクが同一資源を使用しようとした場合や、タスク間で情報を共有しようとした場合、混乱と矛盾をもたらすことがある。並行計算はこの問題を解決するためにある。データベースと同様にロックを使用する解法もあるが、その場合デッドロックなどの問題を引き起こす危険性も生じる。他にはブロックしないアルゴリズムもある。