Loading article…
情報技術やコンピュータ科学、特にコンピュータプログラミング、オペレーティングシステム、マルチプロセッサ、データベースの分野では、並行処理の制御によって、並行処理の結果が正しいものになるようにすると同時に、その結果をできるだけ迅速に取得することが保証されます。
コンピュータシステムは、ソフトウェアとハードウェアの両方において、モジュールまたはコンポーネントで構成されています。各コンポーネントは、正しく動作するように、つまり、特定の整合性ルールに従うか、満たすように設計されています。並行して動作するコンポーネントが、メッセージングやアクセスされたデータ（メモリまたはストレージ内）の共有によって相互作用する場合、あるコンポーネントの整合性が別のコンポーネントによって侵害される可能性があります。並行制御の一般的な分野は、相互作用しながら並行して動作するコンポーネントの整合性を維持し、ひいてはシステム全体の整合性と正確性を確保するためのルール、方法、設計手法、および理論を提供します。システムに並行制御を導入するということは、通常、パフォーマンスの低下につながる動作制約を適用することを意味します。動作の整合性と正確性は、パフォーマンスを妥当なレベル以下に低下させることなく、可能な限り効率的に達成する必要があります。並行制御は、より単純な逐次アルゴリズムと比較して、並行アルゴリズムにかなりの複雑さとオーバーヘッドを追加する必要が生じる場合があります。
例えば、並行性制御の不具合は、読み取りまたは書き込み操作の中断によるデータ破損を引き起こす可能性があります。
コメント:
データベース管理システム（DBMS、例：Bernstein et al. 1987、Weikum and Vossen 2001）、その他のトランザクションオブジェクト、および関連する分散アプリケーション（例：グリッドコンピューティング、クラウドコンピューティング）における並行性制御は、データベーストランザクションがそれぞれのデータベースのデータ整合性を損なうことなく並行して実行されることを保証します。したがって、並行性制御は、時間的に重複して実行される 2 つ以上のデータベーストランザクションが同じデータにアクセスできるシステム（事実上あらゆる汎用データベースシステム）の正当性にとって不可欠な要素です。その結果、1970 年代初頭にデータベースシステムが登場して以来、関連する膨大な研究が蓄積されてきました。データベースシステム向けの確立された並行性制御理論は、上記の参考文献に概説されている直列化可能性理論であり、これにより並行性制御の方法とメカニズムを効果的に設計および分析することができます。抽象データ型に対するアトミックトランザクションの並行性制御に関する別の理論は、 （ Lynch et al. 1993 ）で提示されていますが、以下では使用しません。この理論は、より洗練され、複雑で、適用範囲も広く、上記の古典的な理論に比べてデータベース関連の文献ではあまり活用されていません。それぞれの理論には長所と短所、重点と洞察があります。ある程度は互いに補完し合う関係にあり、両者を融合させることは有益かもしれません。
正確性を確保するため、DBMS は通常、シリアライズ可能なトランザクション スケジュールのみが生成されることを保証します。ただし、パフォーマンスを向上させるために意図的にシリアライズ可能性を緩和する場合、アプリケーションの正確性が損なわれない場合に限ります。トランザクションが失敗した場合 (中止された場合) (多くの理由で常に発生する可能性があります) の正確性を維持するために、スケジュールには(中止からの)回復可能性プロパティも必要です。DBMS はまた、コミットされたトランザクションの効果が失われず、中止された(ロールバックされた) トランザクションの効果が関連するデータベースに残らないことを保証します。トランザクションの全体的な特性は、通常、以下のACIDルールで要約されます。データベースが分散化され、分散環境で連携する必要が生じたため (たとえば、 1990 年代初頭のフェデレーテッド データベースや現在のクラウド コンピューティング)、並行性制御メカニズムの効果的な分散が特に注目されています。
データベーストランザクション（またはアトミックトランザクション）の概念は、クラッシュがいつでも発生する可能性のある障害のある環境において、十分に理解されたデータベースシステムの動作を可能にし、クラッシュから十分に理解されたデータベース状態への復旧を可能にするために発展してきました。データベーストランザクションは作業単位であり、通常はデータベースに対する複数の操作（データベースオブジェクトの読み取り、書き込み、ロックの取得など）をカプセル化します。これはデータベースだけでなく、他のシステムでもサポートされている抽象化です。各トランザクションには、そのトランザクションに含まれるプログラム/コードの実行に関して明確に定義された境界があります（トランザクションのプログラマが特別なトランザクションコマンドを使用して決定します）。すべてのデータベーストランザクションは、次のルールに従います（データベースシステムでのサポートにより、つまり、データベースシステムは、実行するトランザクションに対してこれらのルールを保証するように設計されています）。
アトミックトランザクションの概念は、長年にわたり拡張され、ワークフローの一種を実装するビジネストランザクションへと発展しました。これらはアトミックではありません。しかし、こうした拡張されたトランザクションも、通常は構成要素としてアトミックトランザクションを利用します。
トランザクションが直列に、つまり時間的に重複することなく順次実行される場合、トランザクションの同時実行性は存在しません。しかし、インターリーブ操作を伴う同時トランザクションが制御されない方法で許可されると、次のような予期しない望ましくない結果が発生する可能性があります。
高性能トランザクションシステムの多くは、性能要件を満たすためにトランザクションを並行して実行する必要があります。したがって、並行性制御がなければ、このようなシステムは正しい結果を提供することも、データベースの一貫性を維持することもできません。
並行性制御メカニズムの主なカテゴリは以下のとおりです。
カテゴリによってパフォーマンス、つまり平均トランザクション完了率（スループット）は異なり、これはトランザクションの種類構成、並列処理レベル、その他の要因によって異なります。トレードオフに関する選択肢と知識があれば、最高のパフォーマンスが得られるようにカテゴリと方法を選択すべきです。
2つ以上のトランザクション間で相互にブロックし合う（互いにブロックし合う）とデッドロックが発生し、関係するトランザクションが停止して完了できなくなります。ほとんどの非楽観的メカニズム（ブロッキング機能を持つもの）はデッドロックが発生しやすく、停止したトランザクションを意図的に中止（これによりデッドロック内の他のトランザクションが解放される）し、直ちに再開して再実行することで解決されます。デッドロックが発生する可能性は通常低いです。
ブロッキング、デッドロック、およびアボートはすべてパフォーマンスの低下につながるため、これらのカテゴリ間にはトレードオフが存在する。
並行性制御には多くの手法が存在する。それらのほとんどは、上記のいずれかの主要カテゴリに実装できる。主な手法[ 1 ]はそれぞれ多くのバリエーションがあり、場合によっては重複したり組み合わせたりできる。
上記の方法と併用されるその他の主要な並行性制御タイプには、以下のようなものがあります。
1970年代の初期の頃からデータベースシステムで最も一般的なメカニズムタイプは、 2相ロック（2PL）の特殊なケース（バリアント）である、強力厳密2相ロック（ SS2PL、厳密スケジューリングまたは厳密2PLとも呼ばれる）です。これは悲観的です。その長い名前（歴史的な理由による）にもかかわらず、SS2PLメカニズムの考え方は単純です。「トランザクションが終了した後にのみ、トランザクションによって適用されたすべてのロックを解放する」。SS2PL（または厳密性）は、このメカニズムによって生成できるすべてのスケジュールの集合の名前でもあります。つまり、これらのSS2PL（または厳密性）スケジュールは、SS2PL（または厳密性）プロパティを持っています。
並行性制御メカニズムは、まず正しく動作する必要があります。つまり、トランザクションが並行して実行されている間、各トランザクションの整合性ルール（並行性に関連するもの。アプリケーション固有の整合性ルールはここでは対象外）を維持し、トランザクションシステム全体の整合性を確保する必要があります。この正確性は、可能な限り高いパフォーマンスで実現する必要があります。さらに、トランザクションがプロセス、コンピュータ、およびコンピュータネットワークに分散されている間も、効率的に動作する必要性がますます高まっています。並行性制御に影響を与える可能性のあるその他の要素としては、リカバリとレプリケーションが挙げられます。
正確性を確保するため、ほとんどの並行性制御メカニズムの共通の主要目標は、直列化可能性プロパティを持つスケジュールを生成することです。直列化可能性がないと、例えば口座からお金が消えたり、どこからともなくお金が生成されたりするなど、望ましくない現象が発生する可能性があります。スケジュールの直列化可能性とは、同じトランザクションを持つシリアルスケジュール（つまり、トランザクションが時間的に重複することなく順次実行され、互いに完全に分離されているスケジュール：2つのトランザクションが同じデータに同時にアクセスすることは不可能）と（結果として得られるデータベース値において）等価であることを意味します。直列化可能性は、データベーストランザクション間の最高レベルの分離であり、並行トランザクションの主要な正確性基準であると考えられています。場合によっては、パフォーマンス向上（例えば、広く普及しているスナップショット分離メカニズム）や、高度に分散されたシステムにおける可用性要件を満たすため（結果整合性を参照）、妥協された、緩和された形式の直列化可能性が許可されますが、アプリケーションの正確性が緩和によって損なわれない場合に限ります（例えば、お金のトランザクションでは緩和は許可されません。緩和によってお金が消えたり、どこからともなく現れたりする可能性があるためです）。
実装されている並行性制御メカニズムのほぼすべては、競合直列化可能性を提供することで直列化可能性を実現しています。競合直列化可能性は、直列化可能性の広範な特殊ケースであり（つまり、ほとんどの直列化可能なスケジュールをカバーし、可能にし、遅延を引き起こす重大な追加制約を課しません）、効率的に実装できます。
並行性制御は通常、トランザクションの中止（さまざまな理由で常に発生する可能性がある）の場合に正確性を維持するために、スケジュールの回復可能性プロパティも保証します。回復可能性（中止からの回復）とは、スケジュール内のコミットされたトランザクションが、中止されたトランザクションによって書き込まれたデータを読み取っていないことを意味します。 このようなデータは（中止時に）データベースから消え、誤ったデータベース状態の一部となります。 このようなデータを読み取ると、ACID の一貫性ルールに違反します。 シリアライザビリティとは異なり、回復可能性は、いかなる場合でも妥協したり緩和したりすることはできません。緩和すると、中止時にデータベースの整合性がすぐに侵害されるためです。 上記の主要なメソッドは、シリアライザビリティ メカニズムを提供します。 それらのいずれも、一般的な形式では自動的に回復可能性を提供するものではなく、回復可能性をサポートするには特別な考慮事項とメカニズムの強化が必要です。 回復可能性の一般的な特殊ケースは厳密性であり、障害からの効率的なデータベースの回復を可能にします（ただし、楽観的な実装は除外されます）。
コンピューティング技術の急速な発展に伴い、低遅延ネットワークやバス上でのローカルコンピューティングと分散コンピューティングの区別は曖昧になりつつあります。そのため、コンピュータクラスタやマルチコアプロセッサなど、分散環境においてローカル技術を効果的に活用することが一般的になっています。しかし、ローカル技術には限界があり、スケーリングのためにマルチプロセッサ（またはマルチコア）がサポートするマルチプロセス（またはスレッド）を使用します。トランザクション自体が複数のプロセスにまたがる必要がある場合、これはしばしばトランザクションを分散トランザクションに変えてしまいます。このような場合、ほとんどのローカル並行性制御技術はスケーリング性能が劣ります。
すべてのシステムは障害が発生する可能性があり、障害からの復旧は必須です。並行性制御メカニズムによって決定される生成スケジュールの特性は、復旧の有効性と効率性に影響を与える可能性があります。例えば、（上記の「復旧可能性」のセクションで述べた）厳密性特性は、効率的な復旧のためにしばしば望ましい特性です。
高可用性を実現するため、データベースオブジェクトはしばしば複製されます。同じデータベースオブジェクトのレプリカの更新は同期を保つ必要があります。これは、同時実行制御の方法に影響を与える可能性があります（例：Gray et al. 1996 [ 2 ]）。
マルチタスクオペレーティングシステム、特にリアルタイムオペレーティングシステムは、オペレーティングシステムが動作するハードウェアの制限により、実際には一度に 1 つまたは少数のタスクしか実行されていないにもかかわらず、その上で実行されているすべてのタスクが同時に実行されているという錯覚を維持する必要があります。このようなマルチタスクは、すべてのタスクが互いに独立している場合は比較的簡単です。しかし、複数のタスクが同じリソースを使用しようとしたり、タスクが情報を共有しようとしたりすると、混乱や矛盾が生じる可能性があります。並行コンピューティングのタスクは、この問題を解決することです。いくつかの解決策は、データベースで使用されるロックと同様の「ロック」を使用しますが、デッドロックなどの独自の問題を引き起こすリスクがあります。その他の解決策としては、ノンブロッキングアルゴリズムと読み取りコピー更新があります。