並行性制御

情報技術および計算機科学における並行性制御または同時実行制御とは、特にプログラミングとOSとマルチプロセッシングとデータベースにおいて、並行処理の結果が可能な限り素早くかつ正しく得られることを保証することである。

コンピュータシステムは、ソフトウェアもハードウェアも、モジュールまたはコンポーネントで構成される。各コンポーネントは何らかの一貫性規則に従って正しく動作するよう設計されている。コンポーネント間でメッセージをやり取りするかデータを共有して並行動作する際、あるコンポーネント間の一貫性が他のコンポーネントによって妨害されることがある。並行性制御の一般的な領域は、同時並行的に相互作用しながら動作するコンポーネント間の一貫性を保つための規則、技法、設計方法論、理論を提供し、結果としてシステム全体の一貫性と正確性を提供する。並行性制御をシステムに導入することは、一般に若干の性能低下を生じる操作上の制約を適用することを意味する。操作一貫性と正確性は、妥当な以上の性能低下を伴わずに可能な限り効率的に達成されるべきである。

1. データベースにおける並行性制御
------------------

ここでデータベースと称しているのは、汎用のデータベース管理システム  に限らず、トランザクションを行うあらゆるシステムである。DBMSはデータベースの並行性制御問題と同時にOS一般の並行性制御問題とも関わりが深い。

データベースについて、トランザクションがデータ完全性を失うことなく安全に実行されることを保証する手法である。並行性制御は特にデータベース管理システム  に適用され、トランザクションがACID原則に従って安全に実行されることを保証する。DBMSはシリアライズ可能  で復旧可能  なスケジュールだけを許すよう設計されなければならず、中断されたトランザクションを取り消す際にコミット済みのトランザクションの結果が失われないことを保証しなければならない。

データベース管理システム 、他のトランザクションオブジェクト、および関連する分散アプリケーションの並行性制御は、それぞれのデータベースのデータ完全性を損なうことなく同時並行にトランザクションを実行することを保証する。したがって並行性制御は、事実上あらゆる汎用データベースシステムにおいて、複数のトランザクションが時間的に重なりつつ同じデータにアクセスする際の正確性の基本要件である。その結果、1970年代初めにデータベースシステムが出現して以来ずっと関連した様々な研究成果が蓄積されていき、データベースシステムの並行性制御理論が確立している。直列化可能性理論は、並行性制御の技法と機構を効率的に設計し分析することを可能にする。抽象データ型に対するアトミックなトランザクションについての並行性制御理論もある。そちらの理論の方が洗練されていて複雑で適用範囲が広く、最近では上述の古典的理論よりもデータベースの教科書でよく採用されている。どちらの理論も一長一短であり、ある意味では相補的でもある。

正確性を確保するため、DBMSは「直列化可能な」トランザクションスケジュールのみを保証するのが普通だが、アプリケーションが正確性をあまり求めていない場合のみ直列化可能性を意図的に緩和して性能を向上させることもある。トランザクションが失敗した場合の正確性を確保するには、スケジュールが回復可能性という属性を持つ必要がある。DBMSはまた、「コミット」されたトランザクションの結果が失われないことを保証し、「中断」されたトランザクションの結果が関連するデータベースに残存しないことも保証する。トランザクション全体の特性は一般に後述するACID原則にまとめられる。データベースが分散されるか、分散環境で協調動作する必要がある場合、並行性制御機構の効果的分散に注目が集まる。

1.1. トランザクションとACID原則
--------------------

「データベース・トランザクション」の概念は、衝突がいつでも発生しうる不完全な環境でのデータベースシステムの動作をよく理解し、その上で衝突から回復できるよう発展してきた。データベース・トランザクションは仕事の単位であり、データベース上のいくつかの操作をカプセル化するのが一般的で、データベースや他のシステムでの抽象概念である。個々のトランザクションは、どのプログラム/コードの実行がそのトランザクションに含まれているかで境界が明確に定義され、プログラマが特別なトランザクションコマンドを使って決定する。データベースシステムは全てのトランザクションが以下の原則に従うことを要求する。

原子性  操作は全体が行われるか全く行われないかのいずれかである。換言すればトランザクションは外から見て不可分に行われる。 一貫性  全てのトランザクションはデータベースの一貫した状態を保つ。データベースについて事前に決定された完全性規則に従う。トランザクションは、データベースをある一貫した状態から別の一貫した状態へと遷移させる。データベースを変化させるのはトランザクションだけであり、データベースの状態は常に一貫している。途中で中断されたトランザクションはトランザクション開始前のデータベース状態を変更しない。 独立性  トランザクション同士が互いに影響を与えることはできない。さらに言えば、中断されたトランザクションの効果は他のトランザクションから見えない。独立性を提供することが並行性制御の主な目的である。 永続性  コンピュータシステムがクラッシュしても成功したトランザクションの結果は失われない。一般に不揮発性メモリにトランザクションの効果とそのコミットというイベントを記録しておく。アトミック・トランザクションの概念から、時間をかけてビジネストランザクション管理  へと発展したが、BTMは実際にはワークフローの実装でありアトミックではない。しかし、そのように発展したトランザクションもコンポーネントとしてアトミック・トランザクションを利用している。

1.2. 並行性制御機構
------------

1.2.1. 分類
---------

並行性制御機構は以下のように大別される。

楽観的 操作が実際に行われるまでトランザクションの同期を遅延させる。衝突は起きないだろうと想定しているが、実際に操作するまでわからない。コミットによってACID原則を破る状態になるなら、トランザクションを中断させる。中断されたトランザクションは即座に再試行され、オーバーヘッドを生じる。中断されるトランザクションが少なければ、楽観的並行性制御はよい戦略である。 悲観的 最初からトランザクションが並行して実行されるもの見なして同期を行う。ブロックが発生する可能性はより高く想定され、予期されている。そのため、若干の性能低下が見込まれる。 準楽観的 楽観的と悲観的の中間であり、状況によって当初から同期する場合と遅延させる場合を使い分ける。カテゴリが異なれば、性能も異なる。トランザクションの完了レートは、トランザクションの種類の比率、計算の並列性レベルなどに左右される。トレードオフに関する知識が入手でき、選択が可能なら、最も性能が高くなる方式を選択すべきである。

2つ以上のトランザクションが互いにブロックしあう状況からデッドロックが生じ、関連するトランザクション群は処理を続行できなくなり、完了不可能となる。楽観的でない機構の多くはデッドロックを発生させる可能性があり、ストールしているトランザクションを意図的に中断させ、即座に再試行させることで問題を解決するしかない。一般にデッドロックはそう頻繁に発生するものではない。

ブロック、デッドロック、中断はいずれも性能を低下させるので、どのような並行性制御を選択するかはトレードオフの問題である。

1.2.2. 技法
---------

並行性制御には多数の技法が存在する。その多くは上述の分類のどれであっても実装可能である。主な技法にはそれぞれ多数の派生があり、複数の技法を組み合わせたものもある。

ロック データに割り当てられたロックでそのデータへのアクセスを制御する。トランザクションはデータにアクセスする際にロックを獲得し、そのロックが解放されるまで他のトランザクションはブロックされる可能性がある。 相反グラフ検査 スケジュールの有向グラフに閉路がないか調べ、あればトランザクションを中断することで閉路を断つ。 時刻印順序付け  時刻印をトランザクションに割り当て、時刻印の順序でデータへのアクセスを制御またはチェックする。 コミットメント順序付け  トランザクションをコミット事象の順序で制御またはチェックする。上掲の技法に加えて以下のような並行性制御技法も使われている。

多版型並行性制御  データベースオブジェクトが更新される度に新たな版を生成することで並行性と性能の向上を図る。トランザクションのリード操作はスケジュール技法に従って、適切な版に対して行う。 索引並行性制御 ユーザーデータではなく索引へのアクセス操作を同期させる。性能向上策のひとつ。 個別作業空間モデル 個々のトランザクションがデータアクセスのための個別の作業空間を持ち、更新したデータはトランザクションがコミットしたときのみ外界から見えるようになる。このモデルは従来とは異なる並行性制御を提供し、多くの利点がある。データベースシステムでの最も一般的な機構は1970年代以降「強く厳密なツーフェーズロック」 であり、ツーフェーズロック  と コミットメント順序付け  の特殊ケースである。悲観的機構に分類される。歴史的経緯から長い名前がついているが、機構は単純で「トランザクションが終わった後のみ、そのトランザクションが確保した全ロックを解放する」というものである。SS2PLはこの機構によって生成される全スケジュールも指し、SS2PLスケジュールはSS2PL属性を持つ。

1.3. 目標
-------

並行性制御は、個々のトランザクションが完全性規則に従うようにし、結果的にシステム全体が完全性を保つようにする。正確性を保つと同時に可能な限り性能を向上させることが目標である。プロセス群、コンピュータ群、コンピュータネットワーク群においてトランザクションが分散されることが多くなるにつれ、並行性制御の必要性は増大している。並行性制御は、データ復旧Data recovery}}とレプリケーションにも影響を受ける。

1.3.1. 正確性
----------

直列化可能性 正確性を維持するため、並行性制御機構の多くは直列化可能性を備えたスケジュールを生成する。直列化可能性は独立性の最も高いレベルである。直列化可能性は、性能向上のためや高度に分散されたシステムでの可用性向上のために緩和されることもあるが、それはその用途での正確さが緩和によって影響を受けない場合のみである。 回復可能性  回復可能性とは、中断されたトランザクションが生じた場合に正確さを維持するスケジュールの属性である。回復可能性がある場合、中断されたトランザクションが更新したデータをコミットされたトランザクションが読み込んでいるということが発生しない。

1.3.2. 分散正確性
------------

ITの急激な進歩によってコンピュータネットワークの性能が向上し、ローカルな処理と分散処理の違いは曖昧になりつつある。そのためローカルな技法を極めて効率的に分散環境に適用するのが一般的となっている。しかし、ローカルな技法には限界があり、分散のスケールが拡大すると対応できない。

分散直列可能性とコミットメント順序付け データベースシステムを分散化したり、分散環境で協調動作する場合、トランザクションも分散化される。分散トランザクションは複数プロセスにまたがるトランザクションであり、さらにコンピュータ間や地理的に離れたサイト間をまたぐこともある。これを処理するには効率的な分散並行性制御機構を必要とする。分散システムのスケジュールで直列化可能性を効率的に達成するには、ローカルな運用を意図して設計された機構では不可能な工夫を必要とする。これは主に、ネットワークやコンピュータによるレイテンシによって並行性制御情報の分散が高くつくことによる。唯一広く知られている分散技法はコミットメント順序付け  であり、特許取得後の1991年に公表された。これは、トランザクションのコミットイベントを時系列に順序付けする技法である。COでは並行性制御情報を分散する必要がなく、信頼性/性能/スケーラビリティの観点で効率的な汎用技法となっており、異なる並行性制御機構を採用したシステムから成るヘテロジニアスな環境でも使用可能である。COはコミットイベントの順序を決定するだけで、具体的な機構には関与しない。1991年に公表されるまで、そのような技法は存在しないと言われていたし、発表後も誤解する専門家が多く見られた。COの重要な副作用として、分散デッドロック状態の自動的な解消がある。コミットメント順序付けの結果生成されるスケジュールの属性もCOと呼ばれる。 先述したSS2PLはCOの派生と見ることもでき、効率的に分散またはグローバルな直列化可能性を達成することができる。COと同様に分散デッドロックを自動的に解消でき、同時に正確性と直列化可能性を備えている。このような好ましい特徴を持ち、よく知られたロック実装機構であることから、SS2PLは広く採用されている。SS2PLは1980年に登場して以来広く採用され、デファクトスタンダードとなっている。ただしSS2PLはブロックする性質のある悲観的機構であるため、制限がもっと緩いCOを使って性能向上を図る場合もある。 分散衝突状態の直列化可能性は、効率的かつ汎用的に対処するのが難しい。「分散CO」では、各ローカルコンポーネントが何らかのCOを持ち、全体を2相コミット 
による投票戦略で制御する。各ローカルコンポーネントがSS2PLであれば、分散COの特殊ケースである「分散SS2PL」となる。これはCOが知られていない1980年代から使われていた。 参照とコミットの順序付けについてはCOの公表以前から研究されており、COのスケジュール属性は "dynamic atomicity" と呼ばれていた。COのアルゴリズムの正確な記述は1992年に公表された。最近ではCOは4つの主要な並行性制御技法の1つとされており、他の技法の相互運用を可能にするものとされている。 分散回復可能性 分散回復可能性はコミットメント順序付けとよく似た直接的な方法で効率的に達成できる。各データベースはローカルに適用し、2相コミット  の戦略を採用する。 分散正確性と分散コミットメント順序付けを含む分散SS2PLは自動的に投票戦略を採用し、全てのローカルな並行性制御機構としてSS2PLを採用すれば、全体で分散SS2PLが実現する。

1.3.3. 他の観点
-----------

復旧 どんなシステムも障害はつきもので、障害発生時の復旧Data recovery}}は必須である。並行性制御機構が生成するスケジュールの特性が復旧の容易さや効率に影響を与える可能性がある。例えば、厳格性は効率的復旧のために望ましい属性である。 レプリケーション 高可用データベースではオブジェクトは複製されることが多い。複製は必要なら同期して更新されなければならない。このために並行性制御が影響を受けることがある。

2. OSにおける並行性制御
--------------

マルチタスクOS、特にリアルタイムOSは、動作中の全タスクが同時に動作しているかのように見せる必要があるが、ハードウェアの制限があるため実際にある時点で同時に動作しているタスクはごく少数である。マルチタスクは全タスクが互いに完全に独立しているなら単純である。しかし複数のタスクが同一資源を使用しようとした場合や、タスク間で情報を共有しようとした場合、混乱と矛盾をもたらすことがある。並行計算はこの問題を解決するためにある。データベースと同様にロックを使用する解法もあるが、その場合デッドロックなどの問題を引き起こす危険性も生じる。他にはブロックしないアルゴリズムもある。

3. 参考文献
-------

first=Yoav , also DEC-TR 841, Digital Equipment Corporation, November 1990
Andrew S. Tanenbaum, Albert S Woodhull : //Operating Systems Design and Implementation, 3rd Edition//, Prentice Hall, ISBN 0-13-142938-8
ミック .「[2]」DEVELOPER STAGE. gihyo.jp

4. 脚注
-----

5. 関連項目
-------

データベース
関係データベース
スケジュール 
トランザクション分離レベル
分散並行性制御
グローバル並行性制御
OS
不可分操作
排他制御
セマフォ
ロック 
ソフトウェアトランザクショナルメモリ
競合状態
スケジューリング
同期 

6. 外部リンク
--------

[3]
[4]