同時実行制御

情報技術とコンピュータサイエンス、特にコンピュータプログラミング、オペレーティングシステム、マルチプロセッサ、データベースの分野では 、同時実行制御により、同時実行操作の正しい結果が生成され、その結果が可能な限り迅速に得られることが保証されます。

コンピュータ システム (ソフトウェアとハ​​ードウェアの両方) は、モジュールまたはコンポーネントで構成されています。各コンポーネントは正しく動作するように、つまり、特定の一貫性ルールに従うか満たすように設計されています。同時に動作するコンポーネントがメッセージングによって、またはアクセスされたデータ (メモリまたはストレージ内) を共有することによって相互作用する場合、特定のコンポーネントの一貫性が別のコンポーネントによって侵害される可能性があります。同時実行制御の一般的な領域では、相互作用しながら同時に動作するコンポーネントの一貫性を維持し、システム全体の一貫性と正確性を維持するためのルール、方法、設計方法論、および理論が提供されます。システムに同時実行制御を導入するということは、通常、パフォーマンスがいくらか低下する操作制約を適用することを意味します。操作の一貫性と正確性は、パフォーマンスを妥当なレベル以下に低下させることなく、可能な限り効率的に達成する必要があります。同時実行制御では、より単純な順次アルゴリズムと比較して、同時実行アルゴリズムに大幅な追加の複雑さとオーバーヘッドが必要になる場合があります。

たとえば、同時実行制御に失敗すると、読み取り操作または書き込み操作が中断され、 データが破損する可能性があります。

コメント:

1. このセクションは、汎用データベース管理システム (DBMS) だけでなく、すべてのトランザクション システム、つまり、データベース トランザクション(アトミック トランザクション、たとえば、システム管理のトランザクション オブジェクトや、通常はプライベートな専用データベース システムを実装するスマートフォンのネットワーク) を使用するすべてのシステムに適用されます。
2. DBMS は、データベース トランザクションだけでなく、オペレーティング システム全般に共通する同時実行制御の問題にも対処する必要があります。これらの問題 (以下のオペレーティング システムにおける同時実行制御を参照) は、このセクションの範囲外です。

データベース管理システム(DBMS、例: Bernstein et al. 1987、Weikum and Vossen 2001)、その他のトランザクションオブジェクト、および関連する分散アプリケーション (例:グリッド コンピューティング、クラウド コンピューティング)における同時実行制御は、データベース トランザクションが、それぞれのデータベースのデータ整合性を侵害することなく同時に実行されることを保証します。したがって、同時実行制御は、時間が重なって実行される 2 つ以上のデータベース トランザクションが同じデータにアクセスする可能性のあるシステム (実質的にはあらゆる汎用データベース システム) の正確性にとって不可欠な要素です。その結果、1970 年代初頭にデータベース システムが登場して以来、関連する研究が大量に蓄積されてきました。データベース システムの確立された同時実行制御理論は、上記の参考文献で概説されています。直列化可能性理論は、同時実行制御の方法とメカニズムを効果的に設計および分析できるようにします。抽象データ型に対するアトミック トランザクションの同時実行制御の代替理論は、(Lynch et al. 1993) で紹介されていますが、以下では使用しません。この理論は、上記の古典的な理論よりも洗練され、複雑で、適用範囲が広く、データベースの文献ではあまり利用されていません。各理論には、長所と短所、重点と洞察があります。ある程度、それらは補完的であり、それらを統合すると役立つ場合があります。

正確性を保証するために、DBMS は通常、直列化可能な トランザクション スケジュールのみが生成されることを保証します。ただし、パフォーマンスを向上させるために直列化可能性が意図的に緩和されている場合は除きます。ただし、これはアプリケーションの正確性が損なわれない場合に限られます。失敗 (中止) したトランザクション (さまざまな理由で常に発生する可能性があります) の場合に正確性を維持するには、スケジュールに(中止からの)回復可能性プロパティも必要です。DBMS は、コミットされたトランザクションの効果が失われないこと、および中止(ロールバック) されたトランザクションの効果が関連データベースに残らないことも保証します。トランザクションの全体的な特性は、通常、以下のACIDルールによって要約されます。データベースが分散化されるか、分散環境で連携する必要が生じるようになったため ( 1990 年代初頭の連合データベースや現在のクラウド コンピューティングなど)、同時実行制御メカニズムの効果的な分散が特別な注目を集めています。

データベース トランザクション(またはアトミック トランザクション)の概念は、クラッシュがいつでも発生する可能性がある障害のある環境でのデータベース システムの十分な理解された動作と、クラッシュから十分な理解されたデータベース状態への回復の両方を可能にするために進化してきました。データベース トランザクションは作業単位であり、通常はデータベースに対するいくつかの操作 (データベース オブジェクトの読み取り、書き込み、ロックの取得など) をカプセル化します。これは、データベースだけでなく他のシステムでもサポートされている抽象化です。各トランザクションには、そのトランザクションに含まれるプログラム/コード実行に関して明確に定義された境界があります (トランザクションのプログラマが特別なトランザクション コマンドを使用して決定します)。すべてのデータベース トランザクションは、次のルールに従います (データベース システムでのサポートによります。つまり、データベース システムは、実行するトランザクションに対してこれらのルールを保証するように設計されています)。

• アトミック性-トランザクションが完了 (それぞれコミットまたは中止)すると、すべての操作の結果が残るか、まったく残らないかのどちらかになります (「すべてか無か」のセマンティクス)。言い換えると、コミットされたトランザクションは (データベースへの影響によって) 外部からは分割不可能 (アトミック) に見え、中止されたトランザクションはデータベースにまったく影響しません。すべての操作が完了するか、まったく実行されないかのどちらかです。
• 一貫性- すべてのトランザクションは、データベースを一貫性のある (正しい) 状態にしておく必要があります。つまり、データベースの所定の整合性ルール (データベースのオブジェクトに対する制約およびオブジェクト間の制約) を維持する必要があります。トランザクションは、データベースを 1 つの一貫性のある状態から別の一貫性のある状態に変換する必要があります (ただし、トランザクション自体が正しいこと、つまり、(アプリケーションの観点から) 意図したとおりに正しく実行され、DBMS によって事前定義された整合性ルールが強制されることを確認するのは、トランザクションのプログラマーの責任です)。したがって、データベースは通常、トランザクションによってのみ変更できるため、データベースのすべての状態は一貫しています。
• 分離- トランザクションは、実行の結果として互いに干渉することはできません。さらに、通常は (同時実行制御方法によって異なりますが) 不完全なトランザクションの影響は、別のトランザクションには見えません。分離を提供することが、同時実行制御の主な目的です。
• 耐久性- 成功した（コミットされた）トランザクションの効果は、クラッシュ後も持続する必要があります（通常は、トランザクションの効果とコミット イベントを不揮発性メモリに記録することによって）。

アトミック トランザクションの概念は、長年にわたって拡張され、実際にはワークフローの種類を実装し、アトミックではないビジネス トランザクションになりました。ただし、このような拡張トランザクションでも、通常はアトミック トランザクションがコンポーネントとして使用されます。

トランザクションがシリアルに、つまり時間的に重複することなく順番に実行される場合、トランザクションの同時実行性は存在しません。ただし、インターリーブ操作を伴う同時トランザクションが制御されていない方法で許可されると、次のような予期しない望ましくない結果が発生する可能性があります。

1. 更新の損失問題: 2 番目のトランザクションが、最初の同時トランザクションによって書き込まれた最初の値の上にデータ項目 (データ) の 2 番目の値を書き込みます。これにより、優先順位によって最初の値を読み取る必要がある同時実行中の他のトランザクションで最初の値が失われます。間違った値を読み取ったトランザクションは、誤った結果で終了します。
2. ダーティリード問題: トランザクションは、後で中止されたトランザクションによって書き込まれた値を読み取ります。この値は中止時にデータベースから消え、どのトランザクションによっても読み取られるべきではありません (「ダーティ リード」)。読み取りトランザクションは、誤った結果で終了します。
3. 不正確な要約の問題: 1 つのトランザクションが繰り返しデータ項目のすべてのインスタンスの値の要約を取得している間に、2 番目のトランザクションがそのデータ項目の一部のインスタンスを更新します。結果の要約は、2 つのトランザクション間の (通常、正確さのために必要となる) 優先順位 (一方が他方より先に実行される場合) の正しい結果を反映せず、更新のタイミングや、要約に特定の更新結果が含まれているかどうかに応じて、ランダムな結果になります。

ほとんどの高性能トランザクション システムでは、パフォーマンス要件を満たすためにトランザクションを同時に実行する必要があります。したがって、同時実行制御がなければ、このようなシステムは正しい結果を提供することも、データベースを一貫して維持することもできません。

同時実行制御メカニズムの主なカテゴリは次のとおりです。

• 楽観的- トランザクションが (読み取り、書き込み) 操作をブロックせずに続行できるようにし ("... ルールが満たされていることを楽観的に考えます...")、各トランザクションのコミット時に、必要な整合性ルール (シリアル化可能性や回復可能性など) の違反のみをチェックします。トランザクションのコミット時に違反が検出されると、トランザクションは中止され、再開されます。このアプローチは、中止されるトランザクションが少ない場合に非常に効率的です。
• 悲観的- トランザクションの操作がルール違反 (シリアル化可能性や回復可能性など) を引き起こす可能性がある場合は、違反の可能性がなくなるまでその操作をブロックします。操作をブロックすると、通常、パフォーマンスの低下を伴います。
• 半楽観的- 違反の種類と検出速度に応じて悲観的または楽観的に応答します。

異なるカテゴリでは、トランザクション タイプの組み合わせ、並列処理の計算レベル、およびその他の要因に応じて、異なるパフォーマンス、つまり異なる平均トランザクション完了率 (スループット) が得られます。トレードオフに関する選択と知識が利用できる場合は、最高のパフォーマンスが得られるようにカテゴリと方法を選択する必要があります。

2 つ以上のトランザクション間の相互ブロック (それぞれが他のトランザクションをブロックする) により、関連するトランザクションが停止し、完了できないデッドロックが発生します。ほとんどの非楽観的メカニズム (ブロックを含む) はデッドロックになりがちですが、停止したトランザクションを意図的に中止し (これにより、デッドロック内の他のトランザクションが解放されます)、すぐに再起動して再実行することで、デッドロックは解決されます。デッドロックの可能性は通常は低いです。

ブロッキング、デッドロック、および中止はすべてパフォーマンスの低下につながるため、カテゴリ間でトレードオフが発生します。

並行処理制御には多くの方法があります。そのほとんどは、上記のいずれかの主要なカテゴリ内で実装できます。主な方法^[1]にはそれぞれ多くのバリエーションがあり、場合によっては重複したり組み合わせたりできるものは次のとおりです。

1. ロック (例: 2 フェーズ ロック- 2PL) -データに割り当てられたロックによってデータへのアクセスを制御します。別のトランザクションによってロックされたデータ項目 (データベース オブジェクト) へのトランザクションのアクセスは、ロックが解除されるまでブロックされる場合があります (ロックの種類とアクセス操作の種類によって異なります)。
2. シリアル化グラフ チェック(シリアル化可能性、競合、または優先順位グラフ チェックとも呼ばれます) -スケジュールのグラフ内のサイクルをチェックし、中止によってサイクルを中断します。
3. タイムスタンプ順序(TO) - トランザクションにタイムスタンプを割り当て、タイムスタンプ順序によってデータへのアクセスを制御またはチェックします。

上記の方法と組み合わせて使用​​されるその他の主要な同時実行制御タイプは次のとおりです。

• マルチバージョン同時実行制御(MVCC) - オブジェクトが書き込まれるたびにデータベース オブジェクトの新しいバージョンを生成し、スケジュール方法に応じてトランザクションによる各オブジェクトの複数の最新の関連バージョンの読み取り操作を許可することで、同時実行性とパフォーマンスを向上させます。
• インデックス同時実行制御-ユーザー データではなくインデックスへのアクセス操作を同期します。特殊な方法により、パフォーマンスが大幅に向上します。
• プライベート ワークスペース モデル(遅延更新) - 各トランザクションはアクセスされたデータ用のプライベート ワークスペースを維持し、変更されたデータはコミット時にのみトランザクションの外部で参照可能になります (例: Weikum および Vossen 2001)。このモデルは、多くの場合に利点がある異なる同時実行制御動作を提供します。

1970 年代の初期の頃から、データベース システムで最も一般的なメカニズム タイプは、2 フェーズ ロック(2PL)の特殊なケース (バリアント) である、強力で厳格な 2 フェーズ ロック(SS2PL、 Rigorous schedulingまたはRigorous 2PLとも呼ばれる) です。これは悲観的です。長い名前にもかかわらず (歴史的な理由により)、SS2PLメカニズムの考え方は単純です。「トランザクションによって適用されたすべてのロックは、トランザクションが終了した後にのみ解放します。」SS2PL (または Rigorousness) は、このメカニズムによって生成できるすべてのスケジュールのセットの名前でもあります。つまり、これらの SS2PL (または Rigorous) スケジュールには、SS2PL (または Rigorousness) プロパティがあります。

同時実行制御メカニズムは、まず正しく動作する必要があります。つまり、トランザクションが同時に実行されている間に各トランザクションの整合性ルール (同時実行に関連するもの。アプリケーション固有の整合性ルールはここでは対象外) を維持し、トランザクション システム全体の整合性を維持する必要があります。正確性は、可能な限り優れたパフォーマンスで達成する必要があります。さらに、トランザクションがプロセス、コンピューター、およびコンピューター ネットワークに分散されている間に効率的に動作する必要性が高まっています。同時実行制御に影響を与える可能性のあるその他の主題には、リカバリとレプリケーションがあります。

正確性に関して、ほとんどの並行性制御メカニズムの共通の主要な目標は、直列化可能性プロパティを持つスケジュールを生成することです。直列化可能性がないと、望ましくない現象が発生する可能性があります。たとえば、口座からお金が消えたり、どこからともなくお金が生成されたりすることがあります。スケジュールの直列化可能性とは、同じトランザクションを持ついくつかの直列スケジュールと (結果のデータベース値において) 同等であることを意味します(つまり、トランザクションは時間的に重複することなく連続しており、したがって互いに完全に分離されています。つまり、2 つのトランザクションが同じデータに同時にアクセスすることはできません)。直列化可能性は、データベース トランザクションの中で最も高いレベルの分離と考えられており、並行トランザクションの主要な正確性基準です。場合によっては、パフォーマンスを向上させるため (一般的なスナップショット分離メカニズムなど)、または高度に分散されたシステムでの可用性要件を満たすために (結果整合性を参照)、妥協した緩い形式の直列化可能性が許可されますが、これはアプリケーションの正確性が緩和によって侵害されない場合に限ります (たとえば、緩和によってお金が消えたり、どこからともなく現れたりする可能性があるため、お金のトランザクションでは緩和は許可されません)。

実装されているほぼすべての並行性制御メカニズムは、効率的に実装できる直列化可能性の広範な特殊なケース (つまり、ほとんどの直列化可能なスケジュールをカバーし、それを可能にし、遅延を引き起こす大きな追加の制約を課さない) である Conflict 直列化可能性 を提供することで直列化可能性を実現します。

直列化可能性の回復可能性を参照

同時実行制御では通常、スケジュールの回復可能性プロパティも確保され、トランザクションが中止された場合 (さまざまな理由で常に発生する可能性があります) に正確性が維持されます。回復可能性(中止から) とは、スケジュール内のコミットされたトランザクションが、中止されたトランザクションによって書き込まれたデータを読み取っていないことを意味します。 このようなデータは (中止時に) データベースから消え、不正なデータベース状態の一部になります。 このようなデータを読み取ると、ACID の一貫性ルールに違反します。 直列化可能性とは異なり、回復可能性は妥協したり、緩和したりすることはできません。緩和すると、中止時にすぐにデータベースの整合性が侵害されるためです。 上記の主要な方法では、直列化メカニズムが提供されます。 いずれも、一般的な形式では回復可能性を自動的に提供するものではなく、回復可能性をサポートするには特別な考慮とメカニズムの拡張が必要です。 回復可能性のよく使用される特別なケースは厳密性で、これにより、障害からの効率的なデータベース回復が可能になります (ただし、楽観的な実装は除外されます)。

コンピューティングの急速な技術発展により、低レイテンシのネットワークまたはバスを介したローカル コンピューティングと分散コンピューティングの違いはあいまいになっています。そのため、コンピュータ クラスターやマルチコア プロセッサなどの分散環境では、ローカル テクニックを非常に効果的に利用することが一般的です。ただし、ローカル テクニックには制限があり、拡張するにはマルチプロセッサ (またはマルチコア) でサポートされるマルチプロセス (またはスレッド) を使用します。これにより、トランザクション自体がマルチプロセスにまたがる必要がある場合、トランザクションが分散トランザクションになることがよくあります。このような場合、ほとんどのローカル同時実行制御テクニックは拡張性が低くなります。

すべてのシステムは障害に陥りやすく、障害からの回復処理は必須です。同時実行制御メカニズムによって決定される生成されたスケジュールのプロパティは、回復の有効性と効率性に影響を与える可能性があります。たとえば、厳密性プロパティ (上記の回復可能性のセクションで説明) は、効率的な回復のために望ましいことがよくあります。

高可用性を実現するために、データベースオブジェクトは複製されることが多い。同じデータベースオブジェクトのレプリカの更新は同期を保つ必要がある。これは同時実行制御が行われる方法に影響を与える可能性がある（例えば、Gray et al. 1996 ^[2]）。

マルチタスクオペレーティング システム、特にリアルタイム オペレーティング システムでは、オペレーティング システムが実行されているハードウェアの制限により、実際には 1 つまたは少数のタスクしか実行されていないにもかかわらず、その上で実行されているすべてのタスクが同時に実行されているという錯覚を維持する必要があります。このようなマルチタスクは、すべてのタスクが互いに独立している場合、かなり単純です。ただし、複数のタスクが同じリソースを使用しようとしたり、タスクが情報を共有しようとしたりすると、混乱や矛盾が生じる可能性があります。並行コンピューティングのタスクは、その問題を解決することです。一部のソリューションでは、データベースで使用されるロックに似た「ロック」を使用しますが、デッドロックなどの独自の問題を引き起こすリスクがあります。その他のソリューションには、非ブロッキング アルゴリズムと読み取りコピー更新があります。

• 線形化可能性 – 並行プログラミングにおけるいくつかの操作の特性
• ロック（コンピュータサイエンス）  – リソースへのアクセス制限を強制する同期メカニズム
• 相互排他 – コンピューティングにおいて、一度に 1 つのスレッドだけがデータにアクセスできるように制限すること
• 検索エンジンのインデックス作成 – データ管理の方法
• セマフォ（プログラミング）  – 並行システムで使用される変数
• ソフトウェア トランザクション メモリ – ソフトウェアにおける並行処理制御メカニズム
• トランザクション同期拡張 – ハードウェア トランザクション メモリ サポートを追加する x86 命令セット アーキテクチャの拡張
• データベーストランザクションスケジュール
• 隔離（コンピュータサイエンス）
• 分散同時実行制御

• Andrew S. Tanenbaum、Albert S Woodhull (2006):オペレーティングシステムの設計と実装、第 3 版、Prentice Hall、ISBN  0-13-142938-8
• Silberschatz, Avi; Galvin, Peter; Gagne, Greg (2008)。『オペレーティングシステムの概念』、第 8 版。John Wiley & Sons。ISBN 978-0-470-12872-5。
• Philip A. Bernstein、Vassos Hadzilacos、Nathan Goodman (1987): データベース システムにおける同時実行制御と回復 (無料 PDF ダウンロード)、Addison Wesley Publishing Company、1987、ISBN 0-201-10715-5 
• Gerhard Weikum、Gottfried Vossen (2001): Transactional Information Systems、Elsevier、ISBN 1-55860-508-8 
• ナンシー・リンチ、マイケル・メリット、ウィリアム・ウェイル、アラン・フェケテ (1993): Atomic Transactions in Concurrent and Distributed Systems 、Morgan Kaufmann (Elsevier)、1993 年 8 月、ISBN 978-1-55860-104-8、ISBN 1-55860-104-X  
• Yoav Raz (1992): 「コミットメント順序の原則、またはアトミック コミットメントを使用した複数の自律リソース マネージャーの異機種環境におけるシリアル化可能性の保証」(PDF)、第 18 回国際超大規模データベース会議 (VLDB) の議事録、pp. 292-312、バンクーバー、カナダ、1992 年 8 月。(また、DEC-TR 841、Digital Equipment Corporation、1990 年 11 月)