JPH02226347A - 並列性制御方法 - Google Patents
並列性制御方法Info
- Publication number
- JPH02226347A JPH02226347A JP1338896A JP33889689A JPH02226347A JP H02226347 A JPH02226347 A JP H02226347A JP 1338896 A JP1338896 A JP 1338896A JP 33889689 A JP33889689 A JP 33889689A JP H02226347 A JPH02226347 A JP H02226347A
- Authority
- JP
- Japan
- Prior art keywords
- transaction
- transactions
- depth
- tree
- lock
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/466—Transaction processing
Landscapes
- Engineering & Computer Science (AREA)
- Software Systems (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。
め要約のデータは記録されません。
Description
【発明の詳細な説明】
Ａ、産業上の利用分野
本発明は、一般に、マルチ・ユーザー・データ処理環境
における並列性の制御に、より具体的には、待機木の深
さを所定の深さに制限し、且つコンフリクトの解決にお
いてトランザクションにより行なわれた経過を考慮に入
れる新規な並列性制御（ＣＣ）方法に関するものである
。良好な実施例において、待機木の深さは１に制限され
る。
における並列性の制御に、より具体的には、待機木の深
さを所定の深さに制限し、且つコンフリクトの解決にお
いてトランザクションにより行なわれた経過を考慮に入
れる新規な並列性制御（ＣＣ）方法に関するものである
。良好な実施例において、待機木の深さは１に制限され
る。
Ｂ、従来技術
マルチ・ユーザー・データ処理環境においては、２Å以
上のユーザーがデータベース中のレコードのフィールド
をそのフィールドの初期の値に基すいて更新しようと試
みる時の問題を避けるために、ある種の並列性の制御が
必要である。並列性制御の１つのアプローチは、ロッキ
ングとして知られている。他のアプローチは、タイム・
スタンプ法又は楽天的な並列性制御として知られている
。これら２つのなかでは、広く使われているという点で
、ロッキングがより重要である。
上のユーザーがデータベース中のレコードのフィールド
をそのフィールドの初期の値に基すいて更新しようと試
みる時の問題を避けるために、ある種の並列性の制御が
必要である。並列性制御の１つのアプローチは、ロッキ
ングとして知られている。他のアプローチは、タイム・
スタンプ法又は楽天的な並列性制御として知られている
。これら２つのなかでは、広く使われているという点で
、ロッキングがより重要である。
トランザクションは、ロック・マネジャと呼ばれるシス
テム構ｆ２要素に要求を出す事によってレコードに対す
るロックを取得できる。もしトランザクションがあるオ
ブジェクト例えばデータベース・レコードに対する排他
的なロックを保持していると、他のトランザクションは
最初のトランザクションがそのロックを解放するまでは
、そのオブジェクトに対していかなる型のロックも獲得
する事ができない。レコードを更新しようとするトラン
ザクションは、最初に、それに対するロックを取得しな
ければならない。もしロックが取得できなければ、その
トランザクションはブロックされ、待機状態に入る。そ
のレコードが利用可能になり、ロックが認められた時に
、そのトランザクションは再始動される。このロッキン
グ・プロトコルは更新の問題を解決するが、２つの他の
問題を導入する。１つは、デッドロックの問題であり、
この場合、２つ以上のトランザクションが同時ｔこ待機
状態に入り、各々が、それが進行するために必要なロッ
クを他のトランザクションが解放するのを待機する。高
性能のアプリケーションにおいて（典型的には、かなり
の数のトランザクションが並行して処理されている場合
に）出会う可能性のある他の問題は、たとえデッドロッ
クが存在しない場合であっても、これらのトランザクシ
ョンの多く又は殆どのものが所定の時間待機する可能性
が生じる事である。並列性のレベル（同時に進行しよう
とするトランザクションの数）が増大する事は、与えら
れた時間に（待機したりデッドロックに入ったりするこ
となく）有用な仕事をする数を実質的に減少させる。
テム構ｆ２要素に要求を出す事によってレコードに対す
るロックを取得できる。もしトランザクションがあるオ
ブジェクト例えばデータベース・レコードに対する排他
的なロックを保持していると、他のトランザクションは
最初のトランザクションがそのロックを解放するまでは
、そのオブジェクトに対していかなる型のロックも獲得
する事ができない。レコードを更新しようとするトラン
ザクションは、最初に、それに対するロックを取得しな
ければならない。もしロックが取得できなければ、その
トランザクションはブロックされ、待機状態に入る。そ
のレコードが利用可能になり、ロックが認められた時に
、そのトランザクションは再始動される。このロッキン
グ・プロトコルは更新の問題を解決するが、２つの他の
問題を導入する。１つは、デッドロックの問題であり、
この場合、２つ以上のトランザクションが同時ｔこ待機
状態に入り、各々が、それが進行するために必要なロッ
クを他のトランザクションが解放するのを待機する。高
性能のアプリケーションにおいて（典型的には、かなり
の数のトランザクションが並行して処理されている場合
に）出会う可能性のある他の問題は、たとえデッドロッ
クが存在しない場合であっても、これらのトランザクシ
ョンの多く又は殆どのものが所定の時間待機する可能性
が生じる事である。並列性のレベル（同時に進行しよう
とするトランザクションの数）が増大する事は、与えら
れた時間に（待機したりデッドロックに入ったりするこ
となく）有用な仕事をする数を実質的に減少させる。
デッドロックの問題は、広範に研究されている。
一般に、ロック・マネジャは、デッドロックの発生を検
出し、それを解決する事ができなければならない。デッ
ドロックの解決は、ロックされたトランザクションの１
つを選択し、それをロール・バックする事より成る。こ
の処理は、トランザクションの終了と、それが行なった
更新の取消と、関連の資源が他のトランザクションに割
当てられるようにそのロックを解放する事を含む。
出し、それを解決する事ができなければならない。デッ
ドロックの解決は、ロックされたトランザクションの１
つを選択し、それをロール・バックする事より成る。こ
の処理は、トランザクションの終了と、それが行なった
更新の取消と、関連の資源が他のトランザクションに割
当てられるようにそのロックを解放する事を含む。
データベースのトランザクションにおける並列性に関連
する一般的な問題は、Ｇ、Ｊ、 Ｄａｔｅ著’ＡｎＩｎ
ｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａｂａｓｅ Ｓｙ
ｓｔｅｍ」第２巻、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐ
ｕｂｌｉｓｈｉｎｇ Ｃｏｍｐａｎｙ （１９８３）の
第３章により詳細に考察されている。種々の並列性の問
題及びプロトコル特にロッキング型の並列性制御につい
てのより以上の情報は、この教科書を参照されたい。
する一般的な問題は、Ｇ、Ｊ、 Ｄａｔｅ著’ＡｎＩｎ
ｔｒｏｄｕｃｔｉｏｎ ｔｏ Ｄａｔａｂａｓｅ Ｓｙ
ｓｔｅｍ」第２巻、Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐ
ｕｂｌｉｓｈｉｎｇ Ｃｏｍｐａｎｙ （１９８３）の
第３章により詳細に考察されている。種々の並列性の問
題及びプロトコル特にロッキング型の並列性制御につい
てのより以上の情報は、この教科書を参照されたい。
実行待優先順位（ｒｕｎｎｉｎｇ ｐｒｉｏｒｉｔｙ）
（ＲＰ ）方式％式％ Ｐｒｏｃｅｓｓｉｎｇ ”に記載されている。この方法
は、標準的なロッキングに較べると、性能が改善されて
いる。というのは、これは、ブロックされた（即ちロッ
クを待機している）どのトランザクションも他のブロッ
クされたトランザクションによってホールドされないよ
うにする事によって、「本質的なブロッキング」を近似
しているからである。
（ＲＰ ）方式％式％ Ｐｒｏｃｅｓｓｉｎｇ ”に記載されている。この方法
は、標準的なロッキングに較べると、性能が改善されて
いる。というのは、これは、ブロックされた（即ちロッ
クを待機している）どのトランザクションも他のブロッ
クされたトランザクションによってホールドされないよ
うにする事によって、「本質的なブロッキング」を近似
しているからである。
ＲＰ法に伴う問題は、楽天的な並列性制御を含む他の方
法と同様に、２乗効果（ｑｕａｄｒａｔｉｃｅｆｆｅｃ
ｔ：多数のデータ項目をアクセスする「長い」トランザ
クションはロック競合により「２乗」式に悪影響を受け
る現象）である。より具体的には、トランザクションが
より多くのロックを保持すればするほど、それはロック
・コンフリクトを起こしやすくなり、システムにおいて
トランザクションにより消費される時間は保持されるロ
ックの数に対して線形的に増加し、トランザクションは
よりロック・コンフリクトを受けやすくなり且つ再始動
し易くなる。
法と同様に、２乗効果（ｑｕａｄｒａｔｉｃｅｆｆｅｃ
ｔ：多数のデータ項目をアクセスする「長い」トランザ
クションはロック競合により「２乗」式に悪影響を受け
る現象）である。より具体的には、トランザクションが
より多くのロックを保持すればするほど、それはロック
・コンフリクトを起こしやすくなり、システムにおいて
トランザクションにより消費される時間は保持されるロ
ックの数に対して線形的に増加し、トランザクションは
よりロック・コンフリクトを受けやすくなり且つ再始動
し易くなる。
Ｃ０発明が解決しようとする課題
従って、本発明の目的は、不必要なロック・コンフリク
トを減少させる新規な並列性制御方法を提供する事であ
る。
トを減少させる新規な並列性制御方法を提供する事であ
る。
本発明の他の目的は、ＲＰ法におけるように待機木の深
さを適当に制限し、さらにコンフリクトの解決において
トランザクションにより行なわれた経過を考慮に入れる
並列性制御方法を提供する事である。
さを適当に制限し、さらにコンフリクトの解決において
トランザクションにより行なわれた経過を考慮に入れる
並列性制御方法を提供する事である。
０１課題を解決するための手段
本発明によれば、即座にトランザクションを再始動（ｒ
ｅｓｔａｒｔ）する代りに、トランザクションの再始動
は、コンフリクトが生じた時点におけるすべてのコンフ
リクトを生じているトランザクションが完了するか又は
再始動するまで遅延される。
ｅｓｔａｒｔ）する代りに、トランザクションの再始動
は、コンフリクトが生じた時点におけるすべてのコンフ
リクトを生じているトランザクションが完了するか又は
再始動するまで遅延される。
本発明の待機深さ制限（ＷＤＬ）並列性制御は、待機木
の深さをＲＰ法のように°１に制限しながら（従ってブ
ロックされたトランザクションは他のトランザクション
をブロックできない）、下記の付加的な利点を有する。
の深さをＲＰ法のように°１に制限しながら（従ってブ
ロックされたトランザクションは他のトランザクション
をブロックできない）、下記の付加的な利点を有する。
第１に、それは、アクセスされるデータ項目の数及びト
ランザクションにより取得されるロックの数を考慮に入
れる事による非比例的に長い応答時間を長いトランザク
ションが有するという問題を軽減する事である。第２に
、再始動したトランザクションは、そのロックを解放す
るが、その再始動は、コンフリクトを起こしているトラ
ンザクションが完了するか又はそれらが再始動するまで
、遅延される。その結果、ＣＰＵ処理の浪費が減少する
。というのは、そのような再始動したトランザクション
はその元のトランザクションによりコンフリクトを生じ
再び再始動する可能性があるからである。第３に、（活
動状態のトランザクションと）ロック・コンフリクトを
生じ且つブロックされなければならない活動状態のトラ
ンザクションは、もしそれが他のトランザクションをブ
ロックしているならば、それ自身再始動が考慮されると
いう点で。ＲＰ法と較べると、ＷＤＬ法は対称的である
。これは、トランザクションが、他のブロックされたト
ランザクションによりブロックされない事を保証する。
ランザクションにより取得されるロックの数を考慮に入
れる事による非比例的に長い応答時間を長いトランザク
ションが有するという問題を軽減する事である。第２に
、再始動したトランザクションは、そのロックを解放す
るが、その再始動は、コンフリクトを起こしているトラ
ンザクションが完了するか又はそれらが再始動するまで
、遅延される。その結果、ＣＰＵ処理の浪費が減少する
。というのは、そのような再始動したトランザクション
はその元のトランザクションによりコンフリクトを生じ
再び再始動する可能性があるからである。第３に、（活
動状態のトランザクションと）ロック・コンフリクトを
生じ且つブロックされなければならない活動状態のトラ
ンザクションは、もしそれが他のトランザクションをブ
ロックしているならば、それ自身再始動が考慮されると
いう点で。ＲＰ法と較べると、ＷＤＬ法は対称的である
。これは、トランザクションが、他のブロックされたト
ランザクションによりブロックされない事を保証する。
Ｅ、実施例
図面、特に第３図を参照して、ＷＤＬ法がどのように動
作するかの例を最初に説明する。最初に、トランザクシ
ョンＢが、ロック要求を出しているトランザクションで
あり、この要求はトランザクションＡとコンフリクトを
生じるものと仮定する。
作するかの例を最初に説明する。最初に、トランザクシ
ョンＢが、ロック要求を出しているトランザクションで
あり、この要求はトランザクションＡとコンフリクトを
生じるものと仮定する。
ＷＤＬ法は、この場合、待機木の中のトランザクション
の性質に基すいてトランザクションＡ又はトランザクシ
ョンＢのいずれかを再始動する事により待機木の深さを
１にまで減少させる。これは単なる概説であり、完全に
一般的な説明は後述する。
の性質に基すいてトランザクションＡ又はトランザクシ
ョンＢのいずれかを再始動する事により待機木の深さを
１にまで減少させる。これは単なる概説であり、完全に
一般的な説明は後述する。
シミュレーション結果は、ＷＤＬ法が一般的にＲＰ法を
上回る性能を示す事を示しているが、またＷＤＬ法は以
前に考察したＣＣ法よりも優秀な性能を有している。
上回る性能を示す事を示しているが、またＷＤＬ法は以
前に考察したＣＣ法よりも優秀な性能を有している。
実数値関数りにより表されるトランザクション特有の情
報を用いてすべての待機木の深さを所定の正の整数値ｄ
に制限する方法の類について説明する。ただし、任意の
時点におけるシステム中の各トランザクションＴに関し
てＬ（Ｔ）は、トランザクションの現在の「長さ」のあ
る尺度を与える。
報を用いてすべての待機木の深さを所定の正の整数値ｄ
に制限する方法の類について説明する。ただし、任意の
時点におけるシステム中の各トランザクションＴに関し
てＬ（Ｔ）は、トランザクションの現在の「長さ」のあ
る尺度を与える。
この長さ関数を実現する方法は後程詳細に説明する。こ
の説明のために、ＴＪが根であり、（ＴＩ）ｔがノード
である待機木をＶＪとする。２以上の（Ｔ。
の説明のために、ＴＪが根であり、（ＴＩ）ｔがノード
である待機木をＶＪとする。２以上の（Ｔ。
）４が実際には同一のトランザクションであるという事
が生じ得る。この状況は、コンフリクトが対になって取
扱われるので、起きる可能性がある。
が生じ得る。この状況は、コンフリクトが対になって取
扱われるので、起きる可能性がある。
その結果はデッドロックの可能性である。従って、もし
１よりも大きな深さの木が許されるならば、デッドロッ
クの場合が考慮されなければならない。
１よりも大きな深さの木が許されるならば、デッドロッ
クの場合が考慮されなければならない。
しかしながら、ＷＤＬ（ｄ）でｄ＝１の場合、デッドロ
ックは自動的に消去される。というのは、デッドロック
は少なくとも２つの長さの待機連鎖を意味するからであ
る。ここでＷＤＬ（ｄ）として言及される並列性制御方
法の類は次の通りである。
ックは自動的に消去される。というのは、デッドロック
は少なくとも２つの長さの待機連鎖を意味するからであ
る。ここでＷＤＬ（ｄ）として言及される並列性制御方
法の類は次の通りである。
待機木Ｖ、に関連するロック・コンフリクトが与えられ
ているとすると、並列性制御方法は、それが［ＶＪ、（
Ｌ（ＴＩ））Ｊｌの関数として（Ｔ 、）Ｊのある部分
集合を再始動させ、従って深さがｄ以下に減少されるか
又は保たれるならば、それはＷＤＬ（ｄ）のメンバーで
ある。但し、ＶＪはトランザクションＴｊを根とする待
機木でありそのノードは１組のトランザクション（’ｒ
、）Ｊである。Ｌは実数値関数であり、Ｌ（ＴＩ）は
トランザクションＴｊの現在の長さの測度である。（Ｌ
（Ｔｊ））Ｊは待機木■。
ているとすると、並列性制御方法は、それが［ＶＪ、（
Ｌ（ＴＩ））Ｊｌの関数として（Ｔ 、）Ｊのある部分
集合を再始動させ、従って深さがｄ以下に減少されるか
又は保たれるならば、それはＷＤＬ（ｄ）のメンバーで
ある。但し、ＶＪはトランザクションＴｊを根とする待
機木でありそのノードは１組のトランザクション（’ｒ
、）Ｊである。Ｌは実数値関数であり、Ｌ（ＴＩ）は
トランザクションＴｊの現在の長さの測度である。（Ｌ
（Ｔｊ））Ｊは待機木■。
中のトランザクションＴｊ現在の長さの集合である。
これまでの説明は完全な一般性を与えている。
本発明の良好な実施例では、ＷＤＬ（１）の方法が説明
される。即ち、すべての待機木が１の深さに制限される
ような並列性制御方法である。畏さ関数りを実現するい
くつかの方法は次の通りである。
される。即ち、すべての待機木が１の深さに制限される
ような並列性制御方法である。畏さ関数りを実現するい
くつかの方法は次の通りである。
（１）Ｌ（Ｔ）はトランザクションＴによって現在保持
されているロックの数である。（２）Ｌ（Ｔ）は現在の
ものを含めてトランザクションＴのなんラカの起動（ｉ
ｎｃａｒｎａｔ １ｏｎ）により保持されたロックの数
の最大値である。（３）Ｌ（Ｔ）は現在のものまでのＴ
の各起動により保持されたロックの数の和である。長さ
関数を他の形で実現する事も可能である。
されているロックの数である。（２）Ｌ（Ｔ）は現在の
ものを含めてトランザクションＴのなんラカの起動（ｉ
ｎｃａｒｎａｔ １ｏｎ）により保持されたロックの数
の最大値である。（３）Ｌ（Ｔ）は現在のものまでのＴ
の各起動により保持されたロックの数の和である。長さ
関数を他の形で実現する事も可能である。
第２Ａ図を参照して、２つの活動状態のトランザクショ
ンＴ°及びＴが存在し、ｍ個及びｎ個のトランザクショ
ンが、初期状態として図面に示すようにそれぞれを待機
している（ｍ又はｎはゼロであり得る）と仮定する。Ｗ
ＤＬ（１）の下では、１よりも大きな深さの待機木は存
在しないので、Ｔｊ′又はＴ Ｊ ’のいずれかを待機
するトランザクションは存在しない。従って、これは２
つの活動状態のトランザクションに関する一般的な場合
を表している。ＴはＴ又はＴｊの１つとコンフリクトを
生じるロック要求を行なうものと仮定する。深さ２又は
３の待機木が生じ得る一時的な状態が第２Ｂ、第２０及
び第２Ｄ図に示されている。第２０及び第２Ｄ図に示し
た場合に関して、これらの場合が生じるために、ｎはゼ
ロよりも大きくなければならない。本発明の良好な実施
例に関して、その方法が第１図の流れ図に説明されてい
る。そのプロセスは機能ブロック１ｏから始まり、活動
状態のトランザクションＴ°が他のトランザクションと
コンフリクトを生しるロックを要求する。
ンＴ°及びＴが存在し、ｍ個及びｎ個のトランザクショ
ンが、初期状態として図面に示すようにそれぞれを待機
している（ｍ又はｎはゼロであり得る）と仮定する。Ｗ
ＤＬ（１）の下では、１よりも大きな深さの待機木は存
在しないので、Ｔｊ′又はＴ Ｊ ’のいずれかを待機
するトランザクションは存在しない。従って、これは２
つの活動状態のトランザクションに関する一般的な場合
を表している。ＴはＴ又はＴｊの１つとコンフリクトを
生じるロック要求を行なうものと仮定する。深さ２又は
３の待機木が生じ得る一時的な状態が第２Ｂ、第２０及
び第２Ｄ図に示されている。第２０及び第２Ｄ図に示し
た場合に関して、これらの場合が生じるために、ｎはゼ
ロよりも大きくなければならない。本発明の良好な実施
例に関して、その方法が第１図の流れ図に説明されてい
る。そのプロセスは機能ブロック１ｏから始まり、活動
状態のトランザクションＴ°が他のトランザクションと
コンフリクトを生しるロックを要求する。
第２Ｂ図では場合■を説明する。他のトランザクション
が活動状態にあるか否かを見るために判定ブロック１２
で最初にテストが行なわれる。トランザクションＴは場
合■では活動状態なので、このテストの結果は肯定的で
ある。次に、判定ブロック１４で、トランザクションＴ
°を待機しているトランザクションが存在するが否かを
判定するテストが行なわれる。もしｍ＝ｏであれば、待
機木は深さが１であり、トランザクションＴ゛は機能ブ
ロック１６に示すように待機を行なう。さもなければ、
ｍ＞Ｏであり、待機木は深さが２である。深さを１に減
少させるために、判定ブロック２０で判定されるように
、Ｌ（Ｔ’）≧Ｌ（Ｔ）であす且つ各ｉ毎にＬ （Ｔ
’）≧Ｌ （Ｔ 、 ’）であるのでなければ、機能ブ
ロック１８でトランザクションＴ゛が再始動される。ま
た、判定結果が肯定的であれば、トランザクションＴ°
に優先権が与えられ、機能ブロック２２に示すようにト
ランザクションＴが代りに再始動される。
が活動状態にあるか否かを見るために判定ブロック１２
で最初にテストが行なわれる。トランザクションＴは場
合■では活動状態なので、このテストの結果は肯定的で
ある。次に、判定ブロック１４で、トランザクションＴ
°を待機しているトランザクションが存在するが否かを
判定するテストが行なわれる。もしｍ＝ｏであれば、待
機木は深さが１であり、トランザクションＴ゛は機能ブ
ロック１６に示すように待機を行なう。さもなければ、
ｍ＞Ｏであり、待機木は深さが２である。深さを１に減
少させるために、判定ブロック２０で判定されるように
、Ｌ（Ｔ’）≧Ｌ（Ｔ）であす且つ各ｉ毎にＬ （Ｔ
’）≧Ｌ （Ｔ 、 ’）であるのでなければ、機能ブ
ロック１８でトランザクションＴ゛が再始動される。ま
た、判定結果が肯定的であれば、トランザクションＴ°
に優先権が与えられ、機能ブロック２２に示すようにト
ランザクションＴが代りに再始動される。
第２Ｃ図の場合ＩＩを説明する。この場合、判定ブロッ
ク１２のテストが否定的であり、そして判定ブロック２
４で、待機中のなんらがのトランザクションがトランザ
クションＴ°を待機しているか否かを判定するテストが
行なわれる。場合ＩＩにおいては、このテストの結果は
否定的である、即ちｍ＝ｏであり、待機木は深さが２で
ある。深さを１に減少させるために、判定ブロック２６
のテストで判定されるように、Ｌ（Ｔ□）≧Ｌ（Ｔ）且
つＬ（Ｔｊ）≧Ｌ（Ｔ’）でなければ、機能ブロック２
９でトランザクションＴ１が再始動される。また逆の場
合には、トランザクションＴ１に優先権が与えられ、機
能ブロック２２に示すようにトランザクションＴが代り
に再始動される。
ク１２のテストが否定的であり、そして判定ブロック２
４で、待機中のなんらがのトランザクションがトランザ
クションＴ°を待機しているか否かを判定するテストが
行なわれる。場合ＩＩにおいては、このテストの結果は
否定的である、即ちｍ＝ｏであり、待機木は深さが２で
ある。深さを１に減少させるために、判定ブロック２６
のテストで判定されるように、Ｌ（Ｔ□）≧Ｌ（Ｔ）且
つＬ（Ｔｊ）≧Ｌ（Ｔ’）でなければ、機能ブロック２
９でトランザクションＴ１が再始動される。また逆の場
合には、トランザクションＴ１に優先権が与えられ、機
能ブロック２２に示すようにトランザクションＴが代り
に再始動される。
第２Ｄ図には、場合ＩＩＩが説明されている。この場合
、判定ブロック２４のテストが肯定的である。
、判定ブロック２４のテストが肯定的である。
即ち、第１の又は要求を行なっているトランザクション
を待機している他のトランザクションが存在する。従っ
て、待機木は深さが３である。その深さを１に減少させ
るために、判定ブロック２８で判定されるように、Ｌ（
Ｔ’）≧Ｌ（Ｔ１）且つ各ｉ毎にＬ （Ｔ ’）≧Ｌ（
ＴＩ’）でなければ、機能ブロック１８でトランザクシ
ョンＴ°が再始動され、また逆の場合には、トランザク
ションＴ′に優先権が与えられ、代りにブロック２９で
トランザクションＴ□が再始動される。
を待機している他のトランザクションが存在する。従っ
て、待機木は深さが３である。その深さを１に減少させ
るために、判定ブロック２８で判定されるように、Ｌ（
Ｔ’）≧Ｌ（Ｔ１）且つ各ｉ毎にＬ （Ｔ ’）≧Ｌ（
ＴＩ’）でなければ、機能ブロック１８でトランザクシ
ョンＴ°が再始動され、また逆の場合には、トランザク
ションＴ′に優先権が与えられ、代りにブロック２９で
トランザクションＴ□が再始動される。
Ｆ０発明の効果
従って、本発明を用いれば、不必要なロック・コンフリ
クトが減少する新規な並列性制御方法が提供される。
クトが減少する新規な並列性制御方法が提供される。
第１図は、第２Ａ〜第２Ｄ図に示した場合に関するコン
フリクト解決プロセスを説明する流れ図、第２Ａ〜２Ｄ
図は、本発明の良好な実施例に従う並列性制御方法がど
のように働くかを説明するための、コンフリクトを生じ
たトランザクション初期状態と３つの場合を示す図、 第３図は、コンフリクトを生じたトランザクションを示
す図である。 ■ 初期状態 第２Ａ図 第２Ｂ図 ■ 場合几 場合■ ■ 第３図
フリクト解決プロセスを説明する流れ図、第２Ａ〜２Ｄ
図は、本発明の良好な実施例に従う並列性制御方法がど
のように働くかを説明するための、コンフリクトを生じ
たトランザクション初期状態と３つの場合を示す図、 第３図は、コンフリクトを生じたトランザクションを示
す図である。 ■ 初期状態 第２Ａ図 第２Ｂ図 ■ 場合几 場合■ ■ 第３図
Claims (2)
- （１）マルチユーザー・データ処理システムにおいて待
機木の深さを所定の数ｄに制限する並列性制御方法であ
って、 トランザクションＴ＿ｊを根としトランザクションの集
合｛Ｔ＿ｉ｝＿ｊをノードとする待機木をＶ＿ｊとし、
任意の時点におけるシステム中の各トランザクションＴ
に関してトランザクションの現在の長さの尺度を与える
実数値関数をＬ（Ｔ）とし、 トランザクションＴ＿ｊによるロックの要求毎に、待機
木Ｖ＿ｊを調べて、その深さがｄを越えるか否かを判定
し、 ［Ｖ＿ｊ｛Ｌ（Ｔ＿ｉ）｝＿ｊ］の関数として｛Ｔ＿ｉ
｝＿ｊのある部分集合を再始動するステップを含む 並列性制御方法。 - （２）関数Ｌ（Ｔ）が、トランザクションＴにより現在
保持されているロックの数、又はトランザクションＴの
いずれかの起動により保持されたロックの最大数、又は
トランザクションＴの各起動時に保持されたロックの数
の和を与えるような特許請求の範囲第１項に記載の並列
性制御方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US29433489A | 1989-01-05 | 1989-01-05 | |
| US294334 | 1989-01-05 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH02226347A true JPH02226347A (ja) | 1990-09-07 |
| JPH0687227B2 JPH0687227B2 (ja) | 1994-11-02 |
Family
ID=23132964
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP1338896A Expired - Lifetime JPH0687227B2 (ja) | 1989-01-05 | 1989-12-28 | 並列性制御方法 |
Country Status (3)
| Country | Link |
|---|---|
| EP (1) | EP0377133B1 (ja) |
| JP (1) | JPH0687227B2 (ja) |
| DE (1) | DE68924409T2 (ja) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06103132A (ja) * | 1991-02-25 | 1994-04-15 | Internatl Business Mach Corp <Ibm> | 並行制御方法 |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6113352A (ja) * | 1984-06-28 | 1986-01-21 | Fujitsu Ltd | 共用フアイルの排他制御方法 |
-
1989
- 1989-12-07 EP EP19890122612 patent/EP0377133B1/en not_active Expired - Lifetime
- 1989-12-07 DE DE1989624409 patent/DE68924409T2/de not_active Expired - Fee Related
- 1989-12-28 JP JP1338896A patent/JPH0687227B2/ja not_active Expired - Lifetime
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPS6113352A (ja) * | 1984-06-28 | 1986-01-21 | Fujitsu Ltd | 共用フアイルの排他制御方法 |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH06103132A (ja) * | 1991-02-25 | 1994-04-15 | Internatl Business Mach Corp <Ibm> | 並行制御方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| JPH0687227B2 (ja) | 1994-11-02 |
| DE68924409T2 (de) | 1996-05-02 |
| DE68924409D1 (de) | 1995-11-02 |
| EP0377133B1 (en) | 1995-09-27 |
| EP0377133A2 (en) | 1990-07-11 |
| EP0377133A3 (en) | 1992-12-23 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5193188A (en) | Centralized and distributed wait depth limited concurrency control methods and apparatus | |
| AU2016244128B2 (en) | Processing database transactions in a distributed computing system | |
| Badrinath et al. | Semantics-based concurrency control: Beyond commutativity | |
| US5745747A (en) | Method and system of lock request management in a data processing system having multiple processes per transaction | |
| US7146366B2 (en) | Distributed concurrency control using serialization ordering | |
| CA2027934C (en) | Accelerated deadlock detection in congested data transactions | |
| CN109800062B (zh) | 一种分布式数据库事务处理系统 | |
| Lam et al. | On using real-time static locking protocols for distributed real-time databases | |
| JPH02226347A (ja) | 並列性制御方法 | |
| CN117348977A (zh) | 一种数据库中事务并发控制的方法、装置、设备及介质 | |
| Buckley et al. | Obtaining Progressive Protocols for a Simple Multiversion Database Model. | |
| Pang et al. | On using similarity for resolving conflicts at commit in mixed distributed real-time databases | |
| US12608362B2 (en) | Method and system for lock after qualification for update queries | |
| Ragunathan et al. | Improving the performance of Read-only Transactions through Speculation | |
| KR100253627B1 (ko) | 데이타 저장시스템에서 철회중인 트랜잭션이 교착상태 희생자로 선택되지 않도록 하는 트랜잭션 제어 방법 | |
| Wang et al. | Comprehensive framework of RDMA-enabled concurrency control protocols | |
| Hassanein et al. | Performance modeling of nested transactions in database systems | |
| QIN et al. | Distributed real-time transaction commit processing | |
| Geetha et al. | Deadlock elimination of AND model requests in distributed systems | |
| EP1831798A1 (en) | Augmented database resource management | |
| Kuo | Concurrency control system for a relational DBMS using two-phase locks | |
| Atwater | Performance of two-phase locking algorithm under hot-spots environments | |
| Ahir | Proficient Method towards Concurrency Control in Distributed Database | |
| Huang | Experimental Evaluation of Real-Time Optimistic |