JPH0687227B2 - 並列性制御方法 - Google Patents
並列性制御方法Info
- Publication number
- JPH0687227B2 JPH0687227B2 JP1338896A JP33889689A JPH0687227B2 JP H0687227 B2 JPH0687227 B2 JP H0687227B2 JP 1338896 A JP1338896 A JP 1338896A JP 33889689 A JP33889689 A JP 33889689A JP H0687227 B2 JPH0687227 B2 JP H0687227B2
- Authority
- JP
- Japan
- Prior art keywords
- transaction
- transactions
- depth
- waiting
- wait
- 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.)
- Expired - Lifetime
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)
Description
【発明の詳細な説明】 A.産業上の利用分野 本発明は、一般に、マルチ・ユーザー・データ処理環境
における並列性の制御に、より具体的には、待機木の深
さを所定の深さに制限し、且つコンフリクトの解決にお
いてトランザクションにより行なわれた経過を考慮に入
れる新規な並列性制御（CC）方法に関するものである。
良好な実施例において、待機木の深さは１に制限され
る。
における並列性の制御に、より具体的には、待機木の深
さを所定の深さに制限し、且つコンフリクトの解決にお
いてトランザクションにより行なわれた経過を考慮に入
れる新規な並列性制御（CC）方法に関するものである。
良好な実施例において、待機木の深さは１に制限され
る。
B.従来技術 マルチ・ユーザー・データ処理環境においては、２人以
上のユーザーがデータベース中のレコードのフィールド
をそのフィールドの初期の値に基ずいて更新しようと試
みる時の問題を避けるために、ある種の並行性の制御が
必要である。並行性制御の１つのアプローチは、ロッキ
ングとして知られている。他のアプローチは、タイム・
スタンプ法又は楽天的な並列性制御として知られてい
る。これら２つのなかでは、広く使われているという点
で、ロッキングがより重要である。
上のユーザーがデータベース中のレコードのフィールド
をそのフィールドの初期の値に基ずいて更新しようと試
みる時の問題を避けるために、ある種の並行性の制御が
必要である。並行性制御の１つのアプローチは、ロッキ
ングとして知られている。他のアプローチは、タイム・
スタンプ法又は楽天的な並列性制御として知られてい
る。これら２つのなかでは、広く使われているという点
で、ロッキングがより重要である。
トランザクションは、ロック・マネジャと呼ばれるシス
テム構成要素に要求を出す事によってレコードに対する
ロックを取得できる。もしトランザクションがあるオブ
ジェクト例えばデータベース・レコードに対する排他的
なロックを保持していると、他のトランザクションは最
初のトランザクションがそのロックを解放するまでは、
そのオブジェクトに対していかなる型のロックも獲得す
る事ができない。レコードを更新しようとするトランザ
クションは、最初に、それに対するロックを取得しなけ
ればならない。もしロックが取得できなければ、そのト
ランザクションはブロックされ、待機状態に入る、その
レコードが利用可能になり、ロックが認められた時に、
そのトランザクションは再始動される。このロッキング
・プロトコルは更新の問題を解決するが、２つの他の問
題を導入する。１つは、デッドロックの問題であり、こ
の場合、２つ以上のトランザクションが同時に待機状態
に入り、各々が、それが進行するために必要なロックを
他のトランザクションが解放するのを待機する。高性能
のアプリケーションにおいて（典型的には、かなりの数
のトランザクションが並行して処理されている場合に）
出会う可能性のある他の問題は、たとえデッドロックが
存在しない場合であっても、これらのトランザクション
の多く又は殆どのものが所定の時間待機する可能性が生
じる事である。並行性のレベル（同時に進行しようとす
るトランザクションの数）が増大する事は、与えられた
時間に（待機したりデッドロックに入ったりすることな
く）有用な仕事をする数を実質的に減少させる。
テム構成要素に要求を出す事によってレコードに対する
ロックを取得できる。もしトランザクションがあるオブ
ジェクト例えばデータベース・レコードに対する排他的
なロックを保持していると、他のトランザクションは最
初のトランザクションがそのロックを解放するまでは、
そのオブジェクトに対していかなる型のロックも獲得す
る事ができない。レコードを更新しようとするトランザ
クションは、最初に、それに対するロックを取得しなけ
ればならない。もしロックが取得できなければ、そのト
ランザクションはブロックされ、待機状態に入る、その
レコードが利用可能になり、ロックが認められた時に、
そのトランザクションは再始動される。このロッキング
・プロトコルは更新の問題を解決するが、２つの他の問
題を導入する。１つは、デッドロックの問題であり、こ
の場合、２つ以上のトランザクションが同時に待機状態
に入り、各々が、それが進行するために必要なロックを
他のトランザクションが解放するのを待機する。高性能
のアプリケーションにおいて（典型的には、かなりの数
のトランザクションが並行して処理されている場合に）
出会う可能性のある他の問題は、たとえデッドロックが
存在しない場合であっても、これらのトランザクション
の多く又は殆どのものが所定の時間待機する可能性が生
じる事である。並行性のレベル（同時に進行しようとす
るトランザクションの数）が増大する事は、与えられた
時間に（待機したりデッドロックに入ったりすることな
く）有用な仕事をする数を実質的に減少させる。
デッドロックの問題は、広範に研究されている。一般
に、ロック・マネジャは、デッドロックの発生を検出
し、それを解決する事ができなければならない。デッド
ロックの解決は、ロックされたトランザクションの１つ
を選択し、それをロール・バックする事より成る。この
処理は、トランザクションの終了と、それが行なった更
新の取消と、関連の資源が他のトランザクションに割当
てられるようにそのロックを解放する事を含む。
に、ロック・マネジャは、デッドロックの発生を検出
し、それを解決する事ができなければならない。デッド
ロックの解決は、ロックされたトランザクションの１つ
を選択し、それをロール・バックする事より成る。この
処理は、トランザクションの終了と、それが行なった更
新の取消と、関連の資源が他のトランザクションに割当
てられるようにそのロックを解放する事を含む。
データベースのトランザクションにおける並列性に関連
する一般的な問題は、C.J. Date著「An Introduction t
o Database System」第２巻、Addison-Wesley Publishi
ng Company（1983）の第３章により詳細に考察されてい
る。種々の並列性の問題及びプロトコル特にロッキング
型の並列性制御についてのより以上の情報は、この教科
書を参照されたい。
する一般的な問題は、C.J. Date著「An Introduction t
o Database System」第２巻、Addison-Wesley Publishi
ng Company（1983）の第３章により詳細に考察されてい
る。種々の並列性の問題及びプロトコル特にロッキング
型の並列性制御についてのより以上の情報は、この教科
書を参照されたい。
実行時優先順位（running priority）（RP）方式の並列
性制御（CC）は、P.A.Franaszek and J.T.Robinson, AC
M Transactions on Database Syatems, 10, March 198
5, pp. 1 to 28の論文“Limitations of Concurrency i
n Transaction Processing"に記載されている。この方
法は、標準的なロッキングに較べると、性能が改善され
ている。というのは、これは、ブロックされた（即ちロ
ックを待機している）どのトランザクションも他のブロ
ックされたトランザクションによってホールドされない
ようにする事によって、「本質的なブロッキング」を近
似しているからである。
性制御（CC）は、P.A.Franaszek and J.T.Robinson, AC
M Transactions on Database Syatems, 10, March 198
5, pp. 1 to 28の論文“Limitations of Concurrency i
n Transaction Processing"に記載されている。この方
法は、標準的なロッキングに較べると、性能が改善され
ている。というのは、これは、ブロックされた（即ちロ
ックを待機している）どのトランザクションも他のブロ
ックされたトランザクションによってホールドされない
ようにする事によって、「本質的なブロッキング」を近
似しているからである。
RP法に伴う問題は、楽天的な並列性制御を含む他の方法
と同様に、２乗効果（quadraticeffect;多数のデータ項
目をアクセスする「長い」トランザクションはロック競
合により「２乗」式に悪影響を受ける現象）である。よ
り具体的には、トランザクションがより多くのロックを
保持すればするほど、それはロック・コンフリクトを起
こしやすくなり、システムにおいてトランザクションに
より消費される時間は保持されるロックの数に対して線
形的に増加し、トランザクションはよりロック・コンフ
リクトを受けやすくなり且つ再始動し易くなる。
と同様に、２乗効果（quadraticeffect;多数のデータ項
目をアクセスする「長い」トランザクションはロック競
合により「２乗」式に悪影響を受ける現象）である。よ
り具体的には、トランザクションがより多くのロックを
保持すればするほど、それはロック・コンフリクトを起
こしやすくなり、システムにおいてトランザクションに
より消費される時間は保持されるロックの数に対して線
形的に増加し、トランザクションはよりロック・コンフ
リクトを受けやすくなり且つ再始動し易くなる。
C.発明が解決しようとする課題 従って、本発明の目的は、不必要なロック・コンフリク
トを減少させる新規な並列性制御方法を提供する事であ
る。
トを減少させる新規な並列性制御方法を提供する事であ
る。
本発明の他の目的は、RP法におけるように待機木の深さ
を適当に制限し、さらにコンフリクトの解決においてト
ランザクションにより行なわれた経過を考慮に入れる並
列性制御方法を提供する事である。
を適当に制限し、さらにコンフリクトの解決においてト
ランザクションにより行なわれた経過を考慮に入れる並
列性制御方法を提供する事である。
D.課題を解決するための手段 本発明によれば、即座にトランザクションを再始動（re
start）する代りに、トランザクションの再始動は、コ
ンフリクトが生じた時点におけるすべてのコンフリクト
を生じているトランザクションが完了するか又は再始動
するまで遅延される。本発明の待機深さ制限（WDL）並
列性制御は、待機木の深さをRP法のように１に制限しな
がら（従ってブロックされたトランザクションは他のト
ランザクションをブロックできない）、下記の付加的な
利点を有する。第１に、それは、アクセスされるデータ
項目の数及びトランザクションにより取得されるロック
の数を考慮に入れる事による非比例的に長い応答時間を
長いトランザクションが有するという問題を軽減する事
である。第２に、再始動したトランザクションは、その
ロックを解放するが、その再始動は、コンフリクトを起
こしているトランザクションが完了するか又はそれらが
再始動するまで、遅延される。その結果、CPU処理の浪
費が減少する。というのは、そのような再始動したトラ
ンザクションはその元のトランザクションによりコンフ
リクトを生じ再び再始動する可能性があるからである。
第３に、（活動状態のトランザクションと）ロック・コ
ンフリクトを生じ且つブロックされなければならない活
動状態のトランザクションは、もしそれが他のトランザ
クションをブロックしているならば、それ自身再始動が
考慮されるという点で。RP法と較べると、WDL法は対称
的である。これは、トランザクションが、他のブロック
されたトランザクションによりブロックされない事を保
証する。
start）する代りに、トランザクションの再始動は、コ
ンフリクトが生じた時点におけるすべてのコンフリクト
を生じているトランザクションが完了するか又は再始動
するまで遅延される。本発明の待機深さ制限（WDL）並
列性制御は、待機木の深さをRP法のように１に制限しな
がら（従ってブロックされたトランザクションは他のト
ランザクションをブロックできない）、下記の付加的な
利点を有する。第１に、それは、アクセスされるデータ
項目の数及びトランザクションにより取得されるロック
の数を考慮に入れる事による非比例的に長い応答時間を
長いトランザクションが有するという問題を軽減する事
である。第２に、再始動したトランザクションは、その
ロックを解放するが、その再始動は、コンフリクトを起
こしているトランザクションが完了するか又はそれらが
再始動するまで、遅延される。その結果、CPU処理の浪
費が減少する。というのは、そのような再始動したトラ
ンザクションはその元のトランザクションによりコンフ
リクトを生じ再び再始動する可能性があるからである。
第３に、（活動状態のトランザクションと）ロック・コ
ンフリクトを生じ且つブロックされなければならない活
動状態のトランザクションは、もしそれが他のトランザ
クションをブロックしているならば、それ自身再始動が
考慮されるという点で。RP法と較べると、WDL法は対称
的である。これは、トランザクションが、他のブロック
されたトランザクションによりブロックされない事を保
証する。
E.実施例 図面、特に第３図を参照して、WDL法がどのように動作
するかの例を最初に説明する。最初に、トランザクショ
ンＢが、ロック要求を出しているトランザクションであ
り、この要求はトランザクションＡとコンフリクトを生
じるものと仮定する。WDL法は、この場合、待機木の中
のトランザクションの性質に基ずいてトランザクション
Ａ又はトランザクションＢのいずれかを再始動する事に
より待機木の深さを１にまで減少させる。これは単なる
概説であり、完全に一般的な説明は後述する。
するかの例を最初に説明する。最初に、トランザクショ
ンＢが、ロック要求を出しているトランザクションであ
り、この要求はトランザクションＡとコンフリクトを生
じるものと仮定する。WDL法は、この場合、待機木の中
のトランザクションの性質に基ずいてトランザクション
Ａ又はトランザクションＢのいずれかを再始動する事に
より待機木の深さを１にまで減少させる。これは単なる
概説であり、完全に一般的な説明は後述する。
シミュレーション結果は、WDL法が一般的にRP法を上回
る性能を示す事を示しているが、またWDL法は以前に考
察したCC法よりも優秀な性能を有している。
る性能を示す事を示しているが、またWDL法は以前に考
察したCC法よりも優秀な性能を有している。
実数値関数Ｌにより表されるトランザクション特有の情
報を用いてすべての待機木の深さを所定の正の整数値ｄ
に制限する方法の類について説明する。ただし、任意の
時点におけるシステム中の各トランザクションＴに関し
てＬ（Ｔ）は、トランザクションの現在の「長さ」のあ
る尺度を与える。この長さ関数を実現する方法は後程詳
細に説明する。この説明のために、Tjが根であり、｛T
i｝ｊがノードである待機木をVjとする。２以上の｛T
i｝ｊが実際には同一のトランザクションであるという
事が生じ得る。この状況は、コンフリクトが対になって
取扱われるので、起きる可能性がある。その結果はデッ
ドロックの可能性である。従って、もし１よりも大きな
深さの木が許されるならば、デッドロックの場合が考慮
されなければならない。しかしながら、WDL（ｄ）でｄ
＝１の場合、デッドロックは自動的に消去される。とい
うのは、デッドロックは少なくとも２つの長さの待機連
鎖を意味するからである。ここでWDL（ｄ）として言及
される並列正制御方法の類は次の通りである。
報を用いてすべての待機木の深さを所定の正の整数値ｄ
に制限する方法の類について説明する。ただし、任意の
時点におけるシステム中の各トランザクションＴに関し
てＬ（Ｔ）は、トランザクションの現在の「長さ」のあ
る尺度を与える。この長さ関数を実現する方法は後程詳
細に説明する。この説明のために、Tjが根であり、｛T
i｝ｊがノードである待機木をVjとする。２以上の｛T
i｝ｊが実際には同一のトランザクションであるという
事が生じ得る。この状況は、コンフリクトが対になって
取扱われるので、起きる可能性がある。その結果はデッ
ドロックの可能性である。従って、もし１よりも大きな
深さの木が許されるならば、デッドロックの場合が考慮
されなければならない。しかしながら、WDL（ｄ）でｄ
＝１の場合、デッドロックは自動的に消去される。とい
うのは、デッドロックは少なくとも２つの長さの待機連
鎖を意味するからである。ここでWDL（ｄ）として言及
される並列正制御方法の類は次の通りである。
待機木Vjに関連するロック・コンフリクトが与えられて
いるとすると、並列性制御方法は、それが［Vj,｛Ｌ（T
i）｝ｊ］の関数として｛Ti｝ｊのある部分集合を再始
動させ、従って深さがｄ以下に減少されるか又は保たれ
るならば、それはWDL（ｄ）のメンバーである。但し、V
jはトランザクションTjを根とする待機木でありそのノ
ードは１組のトランザクション｛Ti｝ｊである。Ｌは実
数値関数であり、Ｌ（Ti）はトランザクションTiの現在
の長さの測度である。｛Ｌ（Ti）｝ｊは待機木Vj中のト
ランザクションTi現在の長さの集合である。
いるとすると、並列性制御方法は、それが［Vj,｛Ｌ（T
i）｝ｊ］の関数として｛Ti｝ｊのある部分集合を再始
動させ、従って深さがｄ以下に減少されるか又は保たれ
るならば、それはWDL（ｄ）のメンバーである。但し、V
jはトランザクションTjを根とする待機木でありそのノ
ードは１組のトランザクション｛Ti｝ｊである。Ｌは実
数値関数であり、Ｌ（Ti）はトランザクションTiの現在
の長さの測度である。｛Ｌ（Ti）｝ｊは待機木Vj中のト
ランザクションTi現在の長さの集合である。
これまでの説明は完全な一般性を与えている。本発明の
良好な実施例では、WDL（１）の方法が説明される。即
ち、すべての待機木が１の深さに制限されるような並列
性制御方法である。長さ関数Ｌを実現するいくつかの方
法は次の通りである。（１）Ｌ（Ｔ）はトランザクショ
ンＴによって現在保持されているロックの数である。
（２）Ｌ（Ｔ）は現在のものを含めてトランザクション
Ｔのなんらかの起動（incarnation）により保持された
ロックの数の最大値である。（３）Ｌ（Ｔ）は現在のも
のまでのＴの各起動により保持されたロックの数の和で
ある。長さ関数を他の形で実現する事も可能である。
良好な実施例では、WDL（１）の方法が説明される。即
ち、すべての待機木が１の深さに制限されるような並列
性制御方法である。長さ関数Ｌを実現するいくつかの方
法は次の通りである。（１）Ｌ（Ｔ）はトランザクショ
ンＴによって現在保持されているロックの数である。
（２）Ｌ（Ｔ）は現在のものを含めてトランザクション
Ｔのなんらかの起動（incarnation）により保持された
ロックの数の最大値である。（３）Ｌ（Ｔ）は現在のも
のまでのＴの各起動により保持されたロックの数の和で
ある。長さ関数を他の形で実現する事も可能である。
第2A図を参照して、２つの活動状態のトランザクション
Ｔ′及びＴが存在し、ｍ個及びｎ個のトランザクション
が、初期状態として図面に示すようにそれぞれを待機し
ている（ｍ又はｎはゼロであり得る）と仮定する。WDL
（１）の下では、１よりも大きな深さの待機木は存在し
ないので、Ti′又はTj′のいずれかを待機するトランザ
クションは存在しない。従って、これは２つの活動状態
のトランザクションに関する一般的な場合を表してい
る。Ｔ′はＴ又はTjの１つとコンフリクトを生じるロッ
ク要求を行なうものと仮定する。深さ２又は３の待機木
が生じ得る一時的な状態が第2B、第2C及び第2D図に示さ
れている。第2C及び第2D図に示した場合に関して、これ
らの場合が生じるために、ｎはゼロよりも大きくなけれ
ばならない。本発明の良好な実施例に関して、その方法
が第１図の流れ図に説明されている。そのプロセスは機
能ブロック10から始まり、活動状態のトランザクション
Ｔ′が他のトランザクションとコンフリクトを生じるロ
ックを要求する。第2B図では場合Ｉを説明する。他のト
ランザクションが活動状態にあるか否かを見るために判
定ブロック12で最初にテストが行なわれる。トランザク
ションＴは場合Ｉでは活動状態なので、このテストの結
果は肯定的である。次に、判定ブロック14で、トランザ
クションＴ′を待機しているトランザクションが存在す
るか否かを判定するテストが行なわれる。もしｍ＝０で
あれば、待機木は深さが１であり、トランザクション
Ｔ′は機能ブロック16に示すように待機を行なう。さも
なければ、ｍ＞０であり、待機木は深さが２である。深
さを１に減少させるために、判定ブロック20で判定され
るように、Ｌ（Ｔ′）≧Ｌ（Ｔ）であり且つ各ｉ毎にＬ
（Ｔ′）≧Ｌ（Ti′）であるのでなければ、機能ブロッ
ク18でトランザクションＴ′が再始動される。また、判
定結果が肯定的であれば、トランザクションＴ′に優先
権が与えられ、機能ブロック22に示すようにトランザク
ションＴが代りに再始動される。
Ｔ′及びＴが存在し、ｍ個及びｎ個のトランザクション
が、初期状態として図面に示すようにそれぞれを待機し
ている（ｍ又はｎはゼロであり得る）と仮定する。WDL
（１）の下では、１よりも大きな深さの待機木は存在し
ないので、Ti′又はTj′のいずれかを待機するトランザ
クションは存在しない。従って、これは２つの活動状態
のトランザクションに関する一般的な場合を表してい
る。Ｔ′はＴ又はTjの１つとコンフリクトを生じるロッ
ク要求を行なうものと仮定する。深さ２又は３の待機木
が生じ得る一時的な状態が第2B、第2C及び第2D図に示さ
れている。第2C及び第2D図に示した場合に関して、これ
らの場合が生じるために、ｎはゼロよりも大きくなけれ
ばならない。本発明の良好な実施例に関して、その方法
が第１図の流れ図に説明されている。そのプロセスは機
能ブロック10から始まり、活動状態のトランザクション
Ｔ′が他のトランザクションとコンフリクトを生じるロ
ックを要求する。第2B図では場合Ｉを説明する。他のト
ランザクションが活動状態にあるか否かを見るために判
定ブロック12で最初にテストが行なわれる。トランザク
ションＴは場合Ｉでは活動状態なので、このテストの結
果は肯定的である。次に、判定ブロック14で、トランザ
クションＴ′を待機しているトランザクションが存在す
るか否かを判定するテストが行なわれる。もしｍ＝０で
あれば、待機木は深さが１であり、トランザクション
Ｔ′は機能ブロック16に示すように待機を行なう。さも
なければ、ｍ＞０であり、待機木は深さが２である。深
さを１に減少させるために、判定ブロック20で判定され
るように、Ｌ（Ｔ′）≧Ｌ（Ｔ）であり且つ各ｉ毎にＬ
（Ｔ′）≧Ｌ（Ti′）であるのでなければ、機能ブロッ
ク18でトランザクションＴ′が再始動される。また、判
定結果が肯定的であれば、トランザクションＴ′に優先
権が与えられ、機能ブロック22に示すようにトランザク
ションＴが代りに再始動される。
第2C図の場合IIを説明する。この場合、判定ブロック12
のテストが否定的であり、そして判定ブロック24で、待
機中のなんらかのトランザクションがトランザクション
Ｔ′を待機しているか否かを判定するテストが行なわれ
る。場合IIにおいては、このテストの結果は否定的であ
る。即ちｍ＝０であり、待機木は深さが２である。深さ
を１に減少させるために、判定ブロック26のテストで判
定されるように、Ｌ（T1）≧Ｌ（Ｔ）且つＬ（T1）≧Ｌ
（Ｔ′）でなければ、機能ブロック29でトランザクショ
ンT1が再始動される。また逆の場合には、トランザクシ
ョンT1に優先権が与えられ、機能ブロック22に示すよう
にトランザクションＴが代りに再始動される。
のテストが否定的であり、そして判定ブロック24で、待
機中のなんらかのトランザクションがトランザクション
Ｔ′を待機しているか否かを判定するテストが行なわれ
る。場合IIにおいては、このテストの結果は否定的であ
る。即ちｍ＝０であり、待機木は深さが２である。深さ
を１に減少させるために、判定ブロック26のテストで判
定されるように、Ｌ（T1）≧Ｌ（Ｔ）且つＬ（T1）≧Ｌ
（Ｔ′）でなければ、機能ブロック29でトランザクショ
ンT1が再始動される。また逆の場合には、トランザクシ
ョンT1に優先権が与えられ、機能ブロック22に示すよう
にトランザクションＴが代りに再始動される。
第2D図には、場合IIIが説明されている。この場合、判
定ブロック24のテストが肯定的である。即ち、第１の又
は要求を行なっているトランザクションを待機している
他のトランザクションが存在する。従って、待機木は深
さが３である。その深さを１に減少させるために、判定
ブロック28で判定されるように、Ｌ（Ｔ′）≧Ｌ（T1）
且つ各ｉ毎にＬ（Ｔ′）≧Ｌ（Ti′）でなければ、機能
ブロック18でトランザクションＴ′が再始動され、また
逆の場合には、トランザクションＴ′に優先権が与えら
れ、代りにブロック29でトランザクションT1が再始動さ
れる。
定ブロック24のテストが肯定的である。即ち、第１の又
は要求を行なっているトランザクションを待機している
他のトランザクションが存在する。従って、待機木は深
さが３である。その深さを１に減少させるために、判定
ブロック28で判定されるように、Ｌ（Ｔ′）≧Ｌ（T1）
且つ各ｉ毎にＬ（Ｔ′）≧Ｌ（Ti′）でなければ、機能
ブロック18でトランザクションＴ′が再始動され、また
逆の場合には、トランザクションＴ′に優先権が与えら
れ、代りにブロック29でトランザクションT1が再始動さ
れる。
F.発明の効果 従って、本発明を用いれば、不必要なロック・コンフリ
クトが減少する新規な並列性制御方法が提供される。
クトが減少する新規な並列性制御方法が提供される。
第１図は、第2A〜第2D図に示した場合に関するコンフリ
クト解決プロセスを説明する流れ図、 第2A〜2D図は、本発明の良好な実施例に従う並列性制御
方法がどのように働くかを説明するための、コンフリク
トを生じたトランザクション初期状態と３つの場合を示
す図、 第３図は、コンフリクトを生じたトランザクションを示
す図である。
クト解決プロセスを説明する流れ図、 第2A〜2D図は、本発明の良好な実施例に従う並列性制御
方法がどのように働くかを説明するための、コンフリク
トを生じたトランザクション初期状態と３つの場合を示
す図、 第３図は、コンフリクトを生じたトランザクションを示
す図である。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 アレキサンダー・トマージン アメリカ合衆国ニユーヨーク州プレゼント ヴイレ、ミドウブロック・ロード17番地 (56)参考文献 特開 昭61−13352（ＪＰ，Ａ)
Claims (2)
- 【請求項１】複数の並列的に走るトランザクションによ
る、データベースに対するアクセスを管理するためのロ
ック・テーブルを含むトランザクション・マネジャを有
するマルチ・ユーザー・データ処理システムにおける、
待機深さ制限並列性制御方法であって、 （ａ）上記システムによって処理されつつあるトランザ
クションの待機深さをグラフ的に記述するものであっ
て、任意の瞬間に上記システムにおける各トランザクシ
ョン毎に、実数値関数がトランザクションの現在の長さ
の速度を与えるような、待機深さデータ構造を維持し、
その際、上記データ処理システムは、集中システムであ
って、上記トランザクション・マネジャによって許可さ
れるロックは、共有または排他的のどちらかであり、上
記データ構造は、上記データベースの部分上の排他的ロ
ックの開放のために他のトランザクション上で待機する
トランザクションの階層を記述する有向グラフであり、
上記実数値関数は、１つのトランザクションによって保
持されているロックの数である段階と、 （ｂ）トランザクションによるロックを求める各々の要
求毎に、待機深さが予定の値を超えるかどうかを決定す
るべく上記待機深さデータ構造をテストする段階と、 （ｃ）上記実数値関数を使用して、上記待機深さの予定
の値の超過をもたらすトランザクション間の衝突を生じ
た場合に、トランザクションのどの部分集合を再始動さ
せるかを決定する段階と、 （ｄ）待機深さが減少され、または上記予定の値を超え
ないように維持されるように、上記決定されたトランザ
クションの部分集合を再始動させる段階とを有する、 並列性制御方法。 - 【請求項２】複数の並列的に走るトランザクションによ
る、データベースに対するアクセスを管理するためのロ
ック・テーブルを含むトランザクション・マネジャを有
するマルチ・ユーザー・データ処理システムにおける、
待機深さ制限並列性制御方法であって、 （ａ）上記システムによって処理されつつあるトランザ
クションの待機深さをグラフ的に記述するものであっ
て、任意の瞬間に上記システムにおける各トランザクシ
ョン毎に、実数値関数がトランザクションの現在の長さ
の測度を与えるような、待機深さデータ構造を維持し、
その際、上記データ処理システム上で走る少なくとも２
つのアクティブなトランザクションＴ′及びＴが存在
し、トランザクションＴ′上ではｍ個のトランザクショ
ンが待機し、トランザクションＴ上ではｎ個のトランザ
クションが待機し、ｍはゼロよりも大きく、トランザク
ションＴ′はトランザクションＴと衝突するロック要求
を行うものであり、上記実数値関数をＬとすると、Ｌ
（Ｔ）は、トランザクションＴの長さの測度である段階
と、 （ｂ）トランザクションによるロックを求める各々の要
求毎に、待機深さが予定の値を超えるかどうかを決定す
るべく上記待機深さデータ構造をテストする段階と、 （ｃ）上記実数値関数を使用して、上記待機深さの予定
の値の超過をもたらすトランザクション間の衝突を生じ
た場合に、トランザクションのどの部分集合を再始動さ
せるかを決定する段階と、 （ｄ）Ｌ（Ｔ′）≧Ｌ（Ｔ）かどうかを決定し、もしそ
うなら、上記Ｔ′を待機する上記トランザクションをT
i′（ｉ＝１〜ｍ）とすると、各々のｉにつき、もしＬ
（Ｔ′）≧Ｌ（Ti′）ならば、トランザクションＴ′に
優先権を与えてトランザクションＴを再始動させ、そう
でないなら、トランザクションＴ′を再始動させること
によって、上記待機深さを減少させるかまたは、上記予
定の値を超えないように維持されるように、上記トラン
ザクションの部分集合を再始動させる段階を有する、 並列性制御方法。
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 JPH02226347A (ja) | 1990-09-07 |
| JPH0687227B2 true 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) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5193188A (en) * | 1989-01-05 | 1993-03-09 | International Business Machines Corporation | Centralized and distributed wait depth limited concurrency control methods and apparatus |
Family Cites Families (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
Also Published As
| Publication number | Publication date |
|---|---|
| DE68924409T2 (de) | 1996-05-02 |
| DE68924409D1 (de) | 1995-11-02 |
| EP0377133B1 (en) | 1995-09-27 |
| JPH02226347A (ja) | 1990-09-07 |
| 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 | |
| Huang et al. | Experimental Evaluation of Real-Time Optimistic Concurrency Control Schemes. | |
| AU2016244128B2 (en) | Processing database transactions in a distributed computing system | |
| US5940827A (en) | Methods and apparatus for managing a database in a distributed operating environment | |
| Huang et al. | On Using Priority Inheritance In Real-Time Databases. | |
| JP2705717B2 (ja) | ロック装置及び方法、ロック要求の細分性を判別するための装置及び方法 | |
| US5745747A (en) | Method and system of lock request management in a data processing system having multiple processes per transaction | |
| US6772153B1 (en) | Method and apparatus to provide concurrency control over objects without atomic operations on non-shared objects | |
| Krivokapić et al. | Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis | |
| Shanker et al. | SWIFT—A new real time commit protocol | |
| Pandey et al. | On using priority inheritance-based distributed static two-phase locking protocol | |
| Lam et al. | Resolving executing–committing conflicts in distributed real-time database systems | |
| Lam et al. | On using real-time static locking protocols for distributed real-time databases | |
| Hung et al. | Locking protocols for concurrency control in real-time database systems | |
| JPH0687227B2 (ja) | 並列性制御方法 | |
| Al-Jumah et al. | Implementation and modeling of two-phase locking concurrency control—a performance study | |
| CN117348977A (zh) | 一种数据库中事务并发控制的方法、装置、设备及介质 | |
| Pang et al. | On using similarity for resolving conflicts at commit in mixed distributed real-time databases | |
| US20090064141A1 (en) | Efficient utilization of transactions in computing tasks | |
| Lam et al. | Transaction scheduling in distributed real-time systems | |
| Warner et al. | The impact of multilevel security on database buffer management | |
| Son et al. | Scheduling and Concurrency Control for Real-Time Database Systems | |
| KR100253627B1 (ko) | 데이타 저장시스템에서 철회중인 트랜잭션이 교착상태 희생자로 선택되지 않도록 하는 트랜잭션 제어 방법 | |
| Mittal et al. | Dynamic versus static locking in real-time parallel database systems | |
| Huang | Experimental Evaluation of Real-Time Optimistic |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20070823 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 6 Free format text: PAYMENT UNTIL: 20080823 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 6 Free format text: PAYMENT UNTIL: 20080823 |
|
| FPAY | Renewal fee payment (prs date is renewal date of database) |
Year of fee payment: 7 Free format text: PAYMENT UNTIL: 20090823 |
|
| LAPS | Cancellation because of no payment of annual fees |