JPH11259313A - マルチスレッド計算環境内で関連付けられたデ―タ構造をロックするための方法、装置及びコンピュ―タプログラム製品 - Google Patents

マルチスレッド計算環境内で関連付けられたデ―タ構造をロックするための方法、装置及びコンピュ―タプログラム製品

Info

Publication number
JPH11259313A
JPH11259313A JP11014244A JP1424499A JPH11259313A JP H11259313 A JPH11259313 A JP H11259313A JP 11014244 A JP11014244 A JP 11014244A JP 1424499 A JP1424499 A JP 1424499A JP H11259313 A JPH11259313 A JP H11259313A
Authority
JP
Japan
Prior art keywords
group
lock
correlated
objects
computer
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.)
Pending
Application number
JP11014244A
Other languages
English (en)
Inventor
John L Furlani
ジョン・エル・ファラニ
Alexandra R Ohlson
アレキサンダー・アール・オールソン
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Sun Microsystems Inc
Original Assignee
Sun Microsystems Inc
Priority date (The priority date 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 date listed.)
Filing date
Publication date
Application filed by Sun Microsystems Inc filed Critical Sun Microsystems Inc
Publication of JPH11259313A publication Critical patent/JPH11259313A/ja
Pending legal-status Critical Current

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/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores

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)
  • Stored Programmes (AREA)
  • Debugging And Monitoring (AREA)

Abstract

(57)【要約】 【課題】排他的スレッド・アクセスを必要とするオブジ
ェクト・コレクション内のオブジェクトを利用するマル
チスレッド・コンピュータ・アプリケーションの性能を
改善する装置、方法、及びプログラム製品が開示されて
いる。 【解決手段】本発明は、オブジェクトコレクション内の
オブジェクト間の相互関係を監視して、排他的スレッド
アクセスのためこれらオブジェクトの最少の組をロック
する機構を提供する。これらのオブジェクトがロックさ
れるとき、独立もしくは無関係のオブジェクトはロック
されないままなので、別のスレッドがロックすることが
可能となる。最少の組のオブジェクトがロックされるの
で、そのオブジェクトコレクションにアクセスする他の
スレッドは、そのロックにより阻止される可能性が少な
い。こうして、これら他のスレッドはオブジェクトコレ
クション内のオブジェクトに同時にアクセスすることが
できる。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、マルチスレッド計
算環境におけるデータ構造のロック技術に関する。特
に、本発明は、マルチスレッド計算環境におけるデータ
構造の相関グループをロックする方法、装置及びコンピ
ュータプログラム製品である。
【０００２】
【従来の技術】データ構造は、コンピュータのメモリ内
で組織化された情報を保持する。これらのデータ構造の
各々は、他のデータ構造に対し独立にもできるし相互に
関連付けさせることもできる。データ構造へのアクセス
は、アクセスがシングルフロー実行（実行スレッド）を
有する計算環境において起こるときは、相関データ構造
内のデータがシングルスレッドの実行中、常に不変なの
で、簡単である。しかし、非同期演算（割り込み、コン
テクスト切り替え処理またはその他データ構造への競合
アクセスができる類似の演算）が起こったとき、別の演
算がそのデータ構造にアクセスしている間に非同期演算
がデータ構造を変更すると、データ構造の内容が不変で
なくなることがある。近年の計算システムは、コンピュ
ータ演算を並列化するため複数の実行のスレッドを用い
ることが多い。
【０００３】実行スレッド（スレッド）とは、プログラ
ムされた処理内での制御の順序である。在来のシングル
スレッドでプログラムされた処理は、実行中に単一の制
御順序に従う。マルチスレッドのプログラムされた処理
は、幾つかの処理順序を有し、幾つかの独立の行動をす
る能力がある。マルチスレッド計算環境の具体的な実装
について、Powell、Klieman、Barton、Shah、Steinおよ
びWeeksによりSunOS Multi-Thread Architectureの題名
で、USENIX、1991年冬号65頁に論じられている。Posix
(登録商標)スレッドについては、David R.Butenhof著Pr
ogramming with POSIX Thread、版権1997 Addison Wesl
ey Longman、Inc.,ISPN 0-201-63392-2、35-95頁に記述
されている。
【０００４】続いて開示される発明は、オブジェクト指
向プログラミング（ＯＯＰ）パラダイムのコンテクスト
に従って記述されている。ＯＯＰパラダイムはオブジェ
クトを用いる。オブジェクトは、オブジェクトのデータ
を、そのオブジェクトのデータに関して演算するための
ＯＯＰメソッドに関連付ける。通常、ＯＯＰオブジェク
トは、ヒープメモリ領域にインスタンス化され、ＯＯＰ
オブジェクト用にプログラムメソッドを参照するクラス
に基づく。インスタンス化されたＯＯＰオブジェクトは
ポインタを通じてアクセスされ、そのインスタンス化さ
れた特定のＯＯＰオブジェクトに固有であるデータをイ
ンスタンス変数に含む。概念的に、ＯＯＰオブジェクト
は、オブジェクト関連情報（オブジェクト内のインスタ
ンス変数の数など）、オブジェクトのインスタンス変数
を記憶するためのデータ構造、及びオブジェクト内のイ
ンスタンス変数にアクセスし、その値を扱うための呼び
出されたルーチン（ＯＯＰメソッド）のアドレスを保持
する。しかし、オブジェクトは、呼び出されたルーチン
及びオブジェクト関連情報を共有することが多いので、
この共有情報は、通常クラス内に抽出される。こうし
て、インスタンス化されたオブジェクトは単にそのイン
スタンス変数及びそのクラスへのポインタを含むだけで
ある。ＯＯＰの概念に関する詳しい情報は、Peter vand
er Linden著、Not Just Java、Sun Microsystems Press
/Prentice Hall PTR Corp., Upper Saddle River, NJ.
(1997), ISBN 0-13-864638, 136-149頁に見出される。
【０００５】データ構造はまた、ＯＯＰパラダイムにお
けるオブジェクトとしても取り扱うことができる。この
ようなデータ構造オブジェクトには、データ構造を構成
するインスタンス化されたデータ、このデータにアクセ
スするためプログラムメソッド及び可能性として他のデ
ータ構造オブジェクトへのリンクが含まれる。
【０００６】画像処理目的（及び他の多くの用途）に有
用なデータ構造は、画像及びこれらの画像に加えられる
演算を表わす修正された有向無周期グラフ（ＤＡＧ）で
ある。ＤＡＧエレメントはオブジェクトとして表わすこ
とができる。画像ライブラリが一個以上のソース画像に
対する一連の画像演算を捕らえたとき、そのライブラリ
によって、一個以上のＤＡＧを構築することができる。
出来上がったＤＡＧは、オブジェクトコレクションの中
に保持される。オブジェクトコレクションは、普通、独
立及び相関ＤＡＧオブジェクトの双方を保持する。独立
オブジェクトとは、他のオブジェクトに依存しないオブ
ジェクトである。相関オブジェクトは、その演算を実行
するため互いにアクセスする。独立オブジェクトは、そ
のスレッドに排他的アクセスを保証するためスレッドに
よってロックすることができる。しかし、一つの相関オ
ブジェクトをロックするには、第一のスレッドが処理し
ている間に第二のスレッドによりオブジェクト内の情報
が変更されないことを保証するため、各相関オブジェク
トもまたロックされなければならない。
【０００７】
【発明が解決しようとする課題】オブジェクトをロック
するための一つの先行技術の方法は、オブジェクトコレ
クションへのスレッドアクセスを順序付けるためミュー
テックス（mutex）を用いる。この手法での難点は、一
つのスレッドがオブジェクトコレクションの中の一つの
オブジェクトを処理している間は他のスレッドがこれを
出来ないことである。このように、スレッドが制御する
独立演算であって、オブジェクトコレクション中のオブ
ジェクトにアクセスする必要のある独立演算は、ロック
しているスレッドがそのオブジェクトコレクションを解
放するまで、アクセス出来ない。この手法は、オブジェ
クトコレクションを阻害要因にしてしまって、マルチス
レッド計算環境の利点を制限する。
【０００８】別の先行技術は、オブジェクトコレクショ
ン内で相互に関連しそうなオブジェクトの各グループへ
のアクセスを順序付けるよう（一般的に制御オブジェク
ト内で）ミューテックスを割り当てる。こうして、オブ
ジェクトコレクションは、それぞれがオブジェクトコレ
クションの独立グループへのアクセスを制御する多数の
制御オブジェクトを有することとなり、そして各グルー
プは相互依存しそうなオブジェクトを含む。この先行技
術に伴う難点は、相関していると思われるが実は相関し
ていないことが多いオブジェクトのグループへのアクセ
スを制御するため制御オブジェクトを用いていることで
ある。これは、制御オブジェクトが多すぎて必要オブジ
ェクト以上をロックすることを意味する。その結果、ス
レッドブロックが増加して性能が落ちる。
【０００９】オブジェクトコレクションの中のどのオブ
ジェクトが実際に相互に関連付けられているかを監視し
て、各制御オブジェクトを相関オブジェクトの最少グル
ープへのアクセスに限定するために使うのが有益であ
る。
【００１０】
【課題を解決するための手段】本発明は、スレッドが排
他的にアクセスしなければならない値を含む相関データ
構造のグループを用いるマルチスレッド・コンピュータ
・アプリケーションの性能を改善する。本発明はデータ
構造の間の相関関係を監視し、排他的スレッドアクセス
を必要とするデータ構造の最少の組をロックする機構を
提供する。本発明は、独立データ構造またはデータ構造
の非相関グループをロックしないで他のスレッドが利用
できるようにしたまま、グループから構成される相関デ
ータ構造をロックするのみである。グループは相関デー
タ構造の最少の組を含むので、そのグループがロックさ
れたとき他のスレッドがロックにより阻止される可能性
が小さい。こうして、他のスレッドが別のグループ内の
データ構造を同時に処理できる可能性が大きくなる。
【００１１】本発明の一つの側面は、非相関オブジェク
トをロックしたままにすることなくオブジェクトコレク
ション内の対象オブジェクトをロックするための、コン
ピュータ制御方法である。マルチスレッド計算環境にお
いてオブジェクトコレクションは一個以上のスレッドが
アクセスする。グループロックが、対象オブジェクトを
含めて相関オブジェクトの対応グループへのスレッドア
クセスを制御する。この方法は、グループロックが用い
る複数のグループロックリンケージへのスレッドアクセ
スを制御するため、参照ロックをオブジェクトコレクシ
ョンに関連付けするステップを含む。本方法はまた、相
関オブジェクトの対応グループ内における第一のオブジ
ェクトと第二のオブジェクトの間の関係の変化に応じて
複数のグループロックリンケージを修正するステップを
含む。もう一つのステップは、対象オブジェクトを含む
相関オブジェクトの対応グループをロックすることに関
する。すなわち、このステップは対象オブジェクト及び
その相関オブジェクトをロックする。
【００１２】本発明の別の側面は、非相関オブジェクト
をロックしたままにするすることなくオブジェクトコレ
クション内の対象オブジェクトをロックするための、中
央処理装置（ＣＰＵ）及び前記ＣＰＵに結合されたメモ
リを有する装置である。マルチスレッド計算環境におい
てオブジェクトコレクションには一個以上のスレッドが
アクセスする。グループロックが、対象オブジェクトを
含む相関オブジェクトの対応グループへのスレッドアク
セスを制御する。この装置は、グループロックによって
使用される複数のグループロックリンケージへのスレッ
ドアクセスを参照ロック機構が制御するよう、参照ロッ
クをオブジェクトコレクションに関連付けするよう構成
された参照ロック機構を含む。この装置はまた、相関オ
ブジェクトの対応グループを修正するよう構成されたグ
ループ修正機構を含む。この修正は、相関オブジェクト
の対応グループ内で第一のオブジェクトと第二のオブジ
ェクトの間の関係を変更することにより達成される。加
えてこの装置は、前記対象オブジェクトを含めて、相関
オブジェクトの対応グループをロックするよう構成され
たグループロック機構を含み、それにより前記対象オブ
ジェクト及びその相関オブジェクトをロックする。
【００１３】さらに別の本発明の側面は、非相関オブジ
ェクトをロックしたままにすることなくオブジェクトコ
レクション内の対象オブジェクトをコンピュータにロッ
クさせるための、コンピュータで使用可能な媒体上に実
装されたコンピュータプログラム製品である。マルチス
レッド計算環境においてオブジェクトコレクションには
一個以上のスレッドがアクセスする。グループロック
が、対象オブジェクトを含む相関オブジェクトの対応グ
ループへのスレッドアクセスを制御する。コンピュータ
上で実行した場合、このコンピュータに読み込めるコー
ドはコンピュータで、参照ロック機構、グループ修正機
構及びグループロック機構が動作するようにする。これ
らの機構の各々は前述の装置に関する相当機構と同じ機
能を有する。
【００１４】
【発明の実施の形態】前述及びその他の本発明の多くの
側面は、各種図面に図示された好適実施例の下記詳細説
明の読了後、疑いなく当事者に明らかになるであろう。
【００１５】[用語表]下記の「用語表」は本発明及びそ
の好適実施例の理解を助けるため用意した。条件変数
（Condition variable）−条件変数とは、条件付スレッ
ド同期機構である。条件変数は、条件が「偽」のとき、
スレッドが、ミューテックスを取得し、条件をテスト
し、ミューテックスを解放し及び保留になることを可能
とする。条件が「真」になったとき、スレッドは再開さ
れ、再度ミューテックスを取得する。このように、スレ
ッドは条件をテストし、これが満足されたときに、ミュ
ーテックスを取得して処理を継続する。 データ構造（Data Structure）−データ構造とは、変数
に関するメモリ中の記憶の秩序ある配置である。データ
構造は普通ＯＯＰオブジェクト内に含まれる。 ミューテックス（Mutex）−ミューテックス（相互排他
ロック）とは、スレッド同期プリミティブである。ミュ
ーテックスを呼び出そうとする最初のスレッドがミュー
テックスを取得する。それ以後のミューテッスクの呼び
出しは、呼び出したスレッドが阻止される結果を生じ
る。ミューテックスを取得したスレッドは次いでミュー
テックスを解放することができる。ミューテックスが解
放（ロック解除）されると阻止されたスレッドがミュー
テックス取得を争う。 オブジェクト（Object）−オブジェクト指向プログラミ
ング・パラダイムにおけるオブジェクトとは、プログラ
ムメソッドとデータ構造とが関連付けられたものであっ
てクラス及びクラスのオブジェクトを表わすインスタン
ス化された記憶により定義される。 オブジェクトコレクション（Object Collection）−オ
ブジェクトコレクションとは、（プログラムメソッド及
びデータ構造を含む）ＯＯＰオブジェクトの集合であ
る。好適実施例におけるオブジェクトコレクションに
は、画像処理用に用いられる有向無周期的グラフ（ＤＡ
Ｇ）が含まれる。 ポインタ（Pointer）−ポインタとは、データ構造また
はオブジェクトを参照するため用いられるデータ値であ
る。当業者は「ポインタ」には、無制限で、対象の情報
へのメモリアドレスまたはアドレス計算のため用いられ
る値、およびハンドルと類似構造を含む任意の機能的等
価物が含まれることを理解するであろう。 プログラムメソッド（Programmed method）−プログラ
ムメソッドとは、オブジェクトに関連したプログラムプ
ロシージャである。プログラムメソッドは、オブジェク
トに演算を実行させるため呼び出される。プロシージャ
プログラミング・パラダイムにおいては、プログラムメ
ソッドは、プログラムルーチンまたはファンクションと
同等である。 プロシージャ（Procedure）−プロシージャとは、望み
の結果を導き出す首尾一貫した一連のステップである。
これらのステップは、物理量の物理的取扱いを要求する
ものである。通常これらの量は記憶、転送、結合、比較
及び別途取扱いのできる電気的または磁気的信号の形を
取る。これらの信号は、ビット、値、要素、記号、文
字、術語、数字、または類似のものとして参照される。
当業者はこれら及び同様の術語のすべてが適切な物理量
と結びついておりこれらの量に適用される便利なラベル
に過ぎないことを理解するであろう。
【００１６】[概要]コンピュータが命令の実行に当たっ
て実施する操作は、加算または比較のような、人間の演
算者が行う知的演算に広く結びついた用語であらわされ
ることが多い。本発明においては、ここに記述する演算
のいずれにおいてもこのような人間の演算者の能力は必
要としない。演算はマシン演算である。本発明の演算を
実行するため有用なマシンには、プログラムされた汎用
デジタルコンピュータまたは類似の装置が含まれる。あ
らゆる場合に計算方法は、コンピュータ演算における演
算方法とは区別される。本発明は、電気的またはその他
の（例えば、機械的、化学的）物理信号を処理して別の
望みの物理的信号を発生する際にコンピュータに演算さ
せるためのメソッド・ステップに関する。
【００１７】本発明はまた、これらの演算を実行するた
めの装置にも関する。この装置は、所要目的のため特別
に構築されることもあり、コンピュータのメモリ内に記
憶されたコンピュータ・プログラムにより選択的に起動
もしくは再構築した汎用コンピュータを含むこともあ
る。ここに示したプロシージャは、特定のコンピュータ
またはその他の装置に本質的には関係しない。詳細に
は、各種の汎用マシンがここに述べた技術にしたがって
書いたプログラムを用いて使えるか、または必要なメソ
ッド・ステップを実行するのにもっと専門化した装置を
構築するのがさらに便利であると判明するかである。各
種のこれらマシンに必要な構造は以下の記述により明ら
かになるであろう。また、本発明はプログラムロジック
をコンピュータに実行させるプログラムにコード化して
コンピュータ読取り可能記憶媒体内に具体化できる。
【００１８】[演算環境]当業者は、本発明の以下の記述
はオブジェクト指向パラダイムに注目しているが、開示
された技術は他のプログラミング・パラダイムにも適用
できることを理解するであろう。
【００１９】好適実施例は、画像およびこれらの画像に
適用される演算を表わすのに修正された有向無周期グラ
フ（ＤＡＧ）を使用する。当業者は、ＤＡＧ以外のデー
タ構造も同様の結果を伴って使用できることを理解する
であろう。ＤＡＧは、ライブラリが一連の画像化演算を
捕らえたとき画像化ライブラリにより構築される。当業
者は、本発明が画像処理以外の分野においても実用でき
ること及び本発明が本発明の用途を示すため以下で用い
るもの以外のオブジェクト及びデータ構造にも応用でき
ることを理解するであろう。
【００２０】本発明はコンピュータを使用する。本発明
をサポートするために構成された、符号１００で示すよ
うな、コンピュータの幾つかの要素を図１に示す。ここ
には処理装置１０１が、中央処理装置（ＣＰＵ）１０
３、メモリ区画１０５及び入出力（Ｉ／Ｏ）区画１０７
を有しているのが示されている。Ｉ／Ｏ区画１０７は、
キーボード１０９、表示装置１０１、ディスク記憶装置
１１３およびＣＤ−ＲＯＭ駆動装置１１５に接続されて
いる。ＣＤ−ＲＯＭ駆動装置１１５は、一般的にプログ
ラム及びデータ１１９を含むＣＤ−ＲＯＭ媒体１１７を
読み込むことができる。ＣＤ−ＲＯＭ媒体１１７を伴う
ＣＤ−ＲＯＭ駆動装置１１５、及びディスク記憶装置１
１３はファイル記憶機構を構成する。当業者は、ＣＤ−
ＲＯＭ駆動装置１１５が、フロッピイディスク、磁気テ
ープ装置またはプログラム及びデータ１１９を収容でき
る着脱可能媒体を受け入れる類似の装置に置換できるこ
とを理解するであろう。このようなコンピュータ・シス
テムは本発明を具体化したアプリケーションを実行する
能力がある。
【００２１】図２は、符号２００によりあらわされる、
それぞれが相関オブジェクトを含む二つの独立グループ
を備えたグループ化されたオブジェクトコレクションを
示す。二つのグループは、別のスレッドにより並列に処
理することができる。この例においては、相関オブジェ
クトの第一のグループ２０１は、第一画像を表わすのに
用いられた「第一画像」オブジェクト２０３、第二画像
を表わすのに用いられた「第二画像」オブジェクト２０
５、「第一画像」オブジェクト２０３と「第二画像」オ
ブジェクト２０５の和を発生する画像演算を表わすのに
用いられた「加算演算」オブジェクト２０７を含む。こ
の加算画像は「第一結果画像」オブジェクト２０９であ
らわされる。当業者は、相関オブジェクトの第一のグル
ープ２０１の各オブジェクトが、「加算演算」オブジェ
クト２０７を通じて互いに関連していること及び「加算
演算」オブジェクト２０７が表わす演算を実行するスレ
ッドが、オブジェクト２０３、２０５、２０７、２０９
のグループ全体に排他的アクセスを有していなければな
らないことを理解するであろう。
【００２２】相関オブジェクトの第二のグループ２１１
は、相関オブジェクトの第一のグループ２０１とは独立
で、「第三画像」オブジェクト２１３及び、「ルックア
ップ・テーブル・データ」オブジェクト２１７にアクセ
スする「ＬＵＴ演算」オブジェクト２１５を含む。「Ｌ
ＵＴ演算」オブジェクト２１５は、「ルックアップ・テ
ーブル・データ」オブジェクト２１７を用いて「第三画
像」オブジェクト２１３に演算をおこない、「第二結果
画像」オブジェクト２１９を発生する。相関オブジェク
トの第一のグループ２０１と同様の方法で、相関オブジ
ェクトの第二のグループ２１１内の各オブジェクトは相
互に関連している。このように、「ＬＵＴ演算」オブジ
ェクト２１５であらわされる演算を実行するスレッドは
２１３、２１５、２１７、２１９のグループ全体に排他
的書き込みアクセスを有していなければならない。相関
オブジェクトの第一のグループ２０１及び相関オブジェ
クトの第二のグループ２１１の中のオブジェクトは、オ
ブジェクトコレクション２２１を作る。二つのグループ
は互いに独立、すなわち一つのグループのオブジェクト
は別のグループ内のオブジェクトに関して非相関オブジ
ェクトであるから、それらは別々のスレッドによりアク
セスできる。相関オブジェクトの第一のグループ２０１
は「第一グループロック」オブジェクト２２３によりロ
ックすることができる。相関オブジェクトの第二のグル
ープ２１１は「第二グループロック」オブジェクト２２
５によりロックすることができる。これらのグループロ
ックとオブジェクトコレクション２２１の中のオブジェ
クトを相互に関連させるリンクは「参照ロック」オブジ
ェクト２２７によりロックすることができる。各ロック
オブジェクトについては続いて記述する。
【００２３】ここで上記参照ロック及びグループロック
の用途をまとめておくのが有益である。これらのロック
は、非相関オブジェクトの中に含まれる。これらのロッ
クオブジェクトは、対象オブジェクトまたはグループ内
のオブジェクトとは相互に関連していない。ロックオブ
ジェクトはグループ内オブジェクトの間の相関関係の結
果ではあるが、それ自体はグループのメンバーではない
からである（ロックオブジェクトはオブジェクトコレク
ション内にある必要もない）。独立オブジェクトにアク
セスするには、スレッドはそのオブジェクトに関するロ
ックを取得する。相関オブジェクトにアクセスするに
は、スレッドは関係するグループロック（「第一グルー
プロック」オブジェクトなど）及びオブジェクトロック
を取得する。オブジェクト間及び／又はグループ間の関
係を変更するには、スレッドは「参照ロック」オブジェ
クト２２７を取得する。このように、「加算演算」オブ
ジェクト２０７が表わす演算を実行するには、スレッド
は先ず「第一グループロック」オブジェクト２２３を取
得しなければならない。
【００２４】図３は、相関オブジェクトをグループに関
連付けるための、符号２３０であらわされる、グループ
連結構造を示す。この例は、相関オブジェクトの第二の
グループ２１１を「第二グループロック」オブジェクト
２２５に関連付ける方法を示す。相関オブジェクトの第
二のグループ２１１の中の各オブジェクト２１３、２１
５、２１７、２１９には「グループロック・ポインタ」
オブジェクト２３１へのポインタが含まれる。こうして
「第三画像」オブジェクト２１３には、「グループロッ
ク・ポインタ」オブジェクト２３１を指す「第三画像」
リンク２３３が含まれる。同様の方法で、「ＬＵＴ演
算」オブジェクト２１５には「ＬＵＴ演算」リンク２３
５が含まれ、「ルックアップ・テーブル・データ」オブ
ジェクト２１７には「ルックアップ・テーブル・デー
タ」リンク２３７が含まれ、「第二結果画像」オブジェ
クト２１９には「第二結果画像」リンク２３９が含まれ
て、それぞれ「グループロック・ポインタ」オブジェク
ト２３１を指している。「グループロック・ポインタ」
オブジェクト２３１には、「第二グループロック」オブ
ジェクト２２５へのグループリンク２４１が含まれる。
当業者は、「グループロック・ポインタ」オブジェクト
２３１の中の値を（「第二グループロック」オブジェク
ト２２５及び逆グループリンク２４３への適切な変更と
ともに）変え、それによりグループリンク２４１を一つ
のグループロックから別のグループロックに変更するこ
とにより、前述のリンクは、各オブジェクト、２１３、
２１５、２１７、２１９に関するリンクを変更すること
なくグループ内の各オブジェクト、２１３、２１５、２
１７、２１９を異なるグループに結び付けるのを可能に
することを理解するであろう。
【００２５】相互依存オブジェクトの二つの独立グルー
プが、それ自体で相互依存になることが多い。この状況
では、グループ及びそのグループロックを併合しなけれ
ばならない。
【００２６】図４は、相関オブジェクトの第一のグルー
プ２０１を相関オブジェクトの第二のグループ２１１に
併合した結果の、符号２００であらわされた、オブジェ
クトコレクションを示す。「第一結果画像」オブジェク
ト２０９を「第二結果画像」オブジェクト２１９に乗算
して「第三結果画像」オブジェクト２５３を生じる「画
像乗算」オブジェクト２５１の挿入により、これら二つ
のグループは相互に関連付けられる。「画像乗算」オブ
ジェクト２５１が相関オブジェクトの第一のグループ２
０１を相関オブジェクトの第二のグループ２１１に相互
に関連付けられるため、二つのグループを一つのグルー
プに併合しなければならない。これは、続いて図９に関
して記述するように、相関オブジェクトの第二のグルー
プ２１１に関する「グループロック・ポインタ」オブジ
ェクト２３１の値を、「第一グループロック」オブジェ
クト２２３を指すよう変更することにより、達成され
る。当業者は、オブジェクトコレクションの中には普通
二グループ以上の相関オブジェクトがあることを理解す
るであろう。
【００２７】図５は、一つの実施例に用いられた、符号
３００であらわされる、ロッキング・データ構造を示
す。ロッキング・データ構造３００には、「参照ロッ
ク」オブジェクト３０１、「グループロック」オブジェ
クト３０３、「ロックオブジェクト」ポインタ３０５及
び「参照カウント」フィールド３０６を含む「グループ
ロック・ポインタ」オブジェクト３０４及びロック可能
オブジェクト３０７が含まれる。「参照ロック」オブジ
ェクト３０１は、続いて記述するグループロックリンケ
ージへの排他的アクセスを用意するために使用される。
オブジェクトコレクションは一個以上の関連「グループ
ロック」オブジェクト３０３を有してもよい。オブジェ
クトコレクション内の各グループに相関オブジェクトが
含まれており、これらは相関オブジェクトのいずれかに
アクセスする前にまとめてロックしなければならない。
こうして、オブジェクトコレクション内の各グループ
は、別々のスレッドにより独立にアクセスできる。「グ
ループロック・ポインタ」オブジェクト３０４には、
「グループロック」オブジェクト３０３への「ロックオ
ブジェクト」ポインタ３０５が含まれる。オブジェクト
コレクションの中の各相関オブジェクトには、「グルー
プロック・ポインタ」オブジェクト３０４が含まれ、こ
れがそのグループに関する「グループロック」オブジェ
クト３０３を指す。こうして、各オブジェクトを横切っ
てそのポインタを更新する代わりに、「ロックオブジェ
クト」ポインタ３０５の既存の値を新しい「グループロ
ック」オブジェクトへのポインタに置き換えることによ
り、グループ内の各相関オブジェクトを異なる「グルー
プロック」オブジェクト３０３に割り当てることができ
る。ロック可能オブジェクト３０７はオブジェクトコレ
クション内のオブジェクトである。一つの好適実施例に
おいては、「参照ロック」オブジェクト３０１、「グル
ープロック」オブジェクト３０３及び「グループロック
・ポインタ」オブジェクト３０４は、オブジェクトコレ
クション内に含まれていない。
【００２８】「参照ロック」オブジェクト３０１には、
「参照ロック」ミューテックス３０９及びスレッドアク
セス順序化のため良く知られた技術を用いる条件変数３
１１が含まれる。「参照ロック」オブジェクト３０１
は、グループロック・リンケージへの排他的アクセスを
得るために用いられる。「参照ロック」オブジェクト３
０１には、「最大ロックオブジェクトＩＤ」フィールド
３１３もまた含まれ、これにはロックオブジェクトを唯
一つ識別するために用いる単調に増加する値が含まれて
いる。「参照ロック」オブジェクト３０１には、「参照
ロック」オブジェクト３０１のための関数性を備えたプ
ログラムメソッドもまた含まれる。プログラムメソッド
には、「lockRefCreator」プログラムメソッド３１５、
「waitForLockObjUnlock」プログラムメソッド３１７、
および「signalUnlock」プログラムメソッド３１９が含
まれている。「lockRefCreator」プログラムメソッド３
１５は、オブジェクトコレクション内の独立オブジェク
トが別のオブジェクトと相関関係を持つようになったと
き、新しい「グループロック」オブジェクト３０３を作
る。「lockRefCreator」プログラムメソッド３１５はま
た、新たに出来た「グループロック」オブジェクト３０
３の中で「最大ロックオブジェクトID」フィールド３１
３の値を増分して記憶する。「waitForLockObjUnlock」
プログラムメソッド３１７は、スレッド化されたプロシ
ージャにより呼び出されて、オブジェクトコレクション
への排他的アクセスを要求し、最終的にはその要求スレ
ッドに「参照ロック」ミューテックス３０９及びオブジ
ェクトコレクション内のリンケージへの排他的アクセス
を受け取らせる。「signalUnlock」プログラムメソッド
３１９は、スレッドがもはやオブジェクトコレクション
内のリンケージへの排他的アクセスを必要としないこと
を示す「参照ロック」ミューテックス３０９の解放を合
図するため呼び出される。
【００２９】「グループロック」オブジェクト３０３に
は、相関オブジェクトのグループへのスレッドアクセス
順序化のため用いられるグループロック・ミューテック
ス３２１が含まれる。「グループロック」オブジェクト
３０３にアクセスするには、プログラムが先ず「参照ロ
ック」オブジェクト３０１を取得しなければならない。
「グループロック」オブジェクト３０３にはまた、「グ
ループロック」オブジェクト３０３が制御するオブジェ
クトコレクションの中のオブジェクト数を収容する「参
照数」フィールド３２３も含まれる。当業者は、「参照
数」フィールド３２３及び「参照カウント」フィールド
３０６はそれぞれ、「グループロック」オブジェクト３
０３及び「グループロック・ポインタ」オブジェクト３
０４が不要になった時期を判定するために用いられるこ
とを理解するであろう。「グループロック」オブジェク
ト３０３には、前述したような「lockRefCreator」プロ
グラムメソッド３１５が発生する単調増加される識別値
を収容する「グループロック識別」フィールド３２５も
また含まれる。「グループロック」オブジェクト３０３
にはまた、「参照ロック」オブジェクト３０１へのポイ
ンタを収容する「参照ロック・ポインタ」フィールド３
２７も含まれる。加えて、「グループロック」オブジェ
クト３０３には、「グループロック」オブジェクト３０
３を参照する各「グループロック・ポインタ」オブジェ
クト３０４へのポインタを作成するかまたはそれにリン
クする「参照ポインタ」記憶域３２８が含まれる。
【００３０】ロック可能オブジェクト３０７は、オブジ
ェクトコレクションの中のオブジェクトの一つである。
プログラムは、（無制限で）サービスを実行するかまた
はプログラムに情報を提供するためオブジェクトコレク
ション内に常駐するオブジェクトを使用する。ロック可
能オブジェクト３０７には、ロック可能オブジェクト３
０７をロックするため用いることのできるオブジェクト
ロックミューテックス３２９が含まれる。ロック可能オ
ブジェクト３０７にはまた、相関オブジェクトのグルー
プに属する「グループロック・ポインタ」オブジェクト
３０４へのポインタを収容する「グループ参照ポイン
タ」フィールド３３１も含まれる。ロック可能オブジェ
クト３０７にはまた、ロック可能オブジェクト３０７に
相互関連するオブジェクトへのポインタのための記憶を
作りまたはそれにリンクする「相関オブジェクトへのポ
インタ」記憶域３３３も含まれる。こうして、一つのグ
ループが、ロック可能オブジェクト３０７の第一及び第
二インスタンスの双方を含んでいるときは、それぞれが
それぞれの「相関オブジェクトへのポインタ」記憶域３
３３に記憶されたポインタを通じて他のオブジェクトへ
のポインタを参照する。ロック可能オブジェクト３０７
にはまた、「オブジェクトデータとプログラムメソッ
ド」記憶域３３５も含まれ、これは、オブジェクト指向
システムにおいて、オブジェクト・インスタンス変数及
びオブジェクトのプログラムメソッドへのアクセス手段
を含む。
【００３１】「参照ロック」オブジェクト３０１は、
「参照ロック」オブジェクト３０１を取得したスレッド
がこれらのグループロック・リンケージへの排他的アク
セスを有するよう、「グループロック」オブジェクト３
０３、「ロックオブジェクト」ポインタ３０５、及び
「グループ参照ポインタ」フィールド３３１を保護す
る。
【００３２】当業者は、ロッキング・データ構造３００
はオブジェクト指向方法で実装する必要はないこと及び
前述の関係と能力を実行するため在来のプロシージャ的
データ構成技術を用いることができることを理解するで
あろう。
【００３３】図６は、符号４００であらわされる、オブ
ジェクトロック処理を示し、オブジェクトコレクション
内の対象オブジェクトをロックするために用いられるス
テップを示す。処理４００は「スタート」端子４０１で
始まり、「参照ロックをロック」手順４０３に続く。
「参照ロックをロック」手順４０３は、「参照ロック」
オブジェクト３０１の中の「参照ロック」ミューテック
ス３０９をロックして、ロック可能オブジェクト３０７
のような対象オブジェクトへのアクセスに先立って、オ
ブジェクトコレクション（例えば、「グループロック」
オブジェクト３０３）の中のグループロック・リンケー
ジへの排他的スレッドアクセスを取得する。スレッドが
「参照ロック」ミューテックス３０９を取得すると、オ
ブジェクトコレクションの中のグループ及びオブジェク
トの相関関係は他のスレッドによるアクセスから保護さ
れる。これらの相関関係が他のスレッドから保護される
と、現行スレッドは相関関係を変更することができる。
次に処理４００は、対象オブジェクトのオブジェクトロ
ック・ミューテックス３２９を取得する「オブジェクト
をロック」手順４０５に続く。次いで「オブジェクト相
関」判定手順４０７が、アクセスしようとするロック可
能オブジェクト３０７（対象オブジェクト）が他のオブ
ジェクトに相関しているかそれとも他のオブジェクトと
は独立であるかを判定する。この判定はロック可能オブ
ジェクト３０７の中で「グループ参照ポインタ」フィー
ルド３３１を検査することにより行われる。「グループ
参照ポインタ」フィールド３３１の値が「オブジェクト
をロック」ポインタ３０５へのポインタを含んでいない
ときは、ロック可能オブジェクト３０７はオブジェクト
コレクションの中の他のオブジェクトとは独立である。
ロック可能オブジェクト３０７が独立でなければ、処理
４００は、グループロック・ミューテックス３２１を取
得する「グループをロック」手順４０９に続く。次いで
処理４００は、「参照ロックのロックを解除」手順４１
１に続く。「参照ロックのロックを解除」手順４１１は
また、「オブジェクト相関」判定手順４０７が対象オブ
ジェクトが独立であると判定したときは、直接実行され
る。「参照ロックのロックを解除」手順４１１は、「参
照ロック」ミューテックス３０９のロックを解除する。
次に処理４００は、対象オブジェクトに望みの演算を実
行する「オブジェクトに対する演算」手順４１３に続
く。演算が完了すると、処理４００は、「参照ロック」
ミューテックス３０９を再度ロックして他のスレッドが
オブジェクトコレクション内のグループロック・リンケ
ージを変更するのを防止する「参照ロックをロック」手
順４１５に続く。次に、「オブジェクト相関」判定手順
４１７が再度、対象オブジェクトが独立かまたは他のオ
ブジェクトと相関しているか否かを点検して判定する。
対象オブジェクトが相関しているときは、「グループを
ロック」手順４０９によりロックされたグループを「グ
ループのロックを解除」手順４１９が解放する。グルー
プのロックが解除されたとき、または対象オブジェクト
が独立であったときは、処理４００は、「オブジェクト
をロック」手順４０５により取得したオブジェクトロッ
ク・ミューテックスを解放する「オブジェクトのロック
を解除」手順４２１に続く。対象オブジェクトのロック
が解除されると、処理４００は、「参照ロックをロッ
ク」手順４１５によりロックされた「参照ロック」ミュ
ーテックス３０９のロックを解除する「参照ロックのロ
ックを解除」手順４２３に続く。処理４００は「エン
ド」端末４２５を通じて完了する。
【００３４】当業者は、「参照ロック」オブジェクト３
０１は、オブジェクトコレクション内でオブジェクトの
グループの間の関係を変更する他のスレッドに対する遅
延を最小にするため、極めて短時間だけロックされるこ
とを理解するであろう。
【００３５】図７は、符号５００であらわされる、挿入
とロック処理を図示する。これは対象オブジェクトが他
のオブジェクトに相互に関連しているかも知れない場合
に対象オブジェクトをオブジェクトコレクションに挿入
する。挿入とロック処理５００は「スタート」端末５０
１で始まり「参照ロックをロック」手順５０３に続く。
「参照ロックをロック」手順５０３は、「参照ロック」
オブジェクト３０１をロックする。「参照ロック」オブ
ジェクト３０１がロックされると、挿入とロック処理５
００は「対象オブジェクトはグループ内」判定手順５０
５において、対象オブジェクトが独立かまたはグループ
に割り当てられているかを判定する。判定は対象オブジ
ェクト内の「グループ参照ポインタ」フィールド３３１
を検査して行われる。「グループ参照ポインタ」フィー
ルド３３１がＮＵＬＬであるときは、対象オブジェクト
は独立である。そうでないときは、対象オブジェクトは
いずれかのグループに属する。対象オブジェクトが既に
グループに属しているとき挿入とロック処理５００は、
「グループをロック」手順５０７に続き、グループロッ
ク・ミューテックス３２１をロックすることにより対象
オブジェクトを含む「グループロック」オブジェクト３
０３をロックする。次に「参照ロックのロックを解除」
手順５１１が「参照ロック」オブジェクト３０１を解放
し、他のスレッドが他のグループ内のオブジェクトの間
のリンケージを取り扱うことができるようにする。挿入
とロック処理５００は「エンド」端末５１３を通じて完
了する。
【００３６】しかし、「対象オブジェクトはグループ
内」判定手順５０５が、対象オブジェクトがいずれかの
グループ内に含まれていないと判定したとき、挿入とロ
ック処理５００は「グループ参照ポインタを収集」手順
５１５に続く。「グループ参照ポインタを収集」手順５
１５は、グループ参照ポインタを対象オブジェクトに相
互に関連する各オブジェクトから収集する。次に「グル
ープ参照ポインタはすべてＮＵＬＬ」判定手順５１７が
相関オブジェクト内のグループ参照ポインタがすべてＮ
ＵＬＬか否かを判定する。すべてのグループ参照ポイン
タがＮＵＬＬであるときは、対象オブジェクトもいずれ
のその相関オブジェクトもグループには割り当てられて
いない。こうして、挿入とロック処理５００は、「新グ
ループ作成」手順５１９に進み、新しいグループを作
る。新しいグループが作成されると、挿入とロック処理
５００は「対象オブジェクトを新規または選択グループ
（割当てグループ）に割り当て」手順５２１に続く。
「対象オブジェクトを新規または選択グループ（割当て
グループ）に割り当て」手順５２１については後述す
る。
【００３７】しかし、「グループ参照ポインタはすべて
ＮＵＬＬ」判定手順５１７が非ＮＵＬＬグループを見出
したときは（相関オブジェクトの一つが既にグループの
一部であることを意味する）、挿入とロック処理５００
は「グループ選択」手順５２３に進む。「グループ選
択」手順５２３は、「グループ参照ポインタを収集」手
順５１５で集めたグループ参照ポインタから任意のグル
ープを選ぶ。挿入とロック処理５００は次いで、「対象
オブジェクトをグループに割り当て」手順５２１に続
く。「対象オブジェクトをグループに割り当て」手順５
２１は、「新グループ作成」手順５１９により作られた
新規グループか、もしくは「グループ選択」手順５２３
により選択されたグループのいずれかにグループを割り
当てる。このグループはここで「割当てグループ」と名
付けられる。次に、挿入とロック処理５００は、図８の
挿入とロック処理５００につながる「ＡＡへ」端末５２
７に続く。
【００３８】図８は、符号５６０であらわされる、挿入
とロック処理の続きを示す。これは図７の挿入とロック
処理の続きである。挿入とロック処理は「ＡＡ続き」端
末５６１で「ＡＡへ」端末５２７から続く。挿入とロッ
ク処理は、「相関オブジェクトを繰り返す」手順５６３
に続き、各相関オブジェクトから各グループ参照ポイン
タを繰り返す。各グループ参照ポインタを繰り返すと
き、挿入とロック処理は、グループ参照ポインタがＮＵ
ＬＬであるか否かを判定する「グループ参照ポインタは
ＮＵＬＬ」判定手順５６５に続く。グループ参照ポイン
タがＮＵＬＬであるときは、関連するオブジェクトはグ
ル−プに割り当てられていない。こうして、「割当てグ
ループにオブジェクトを割り当て」手順５６９が、関連
オブジェクトの「グループ参照ポインタ」フィールド３
３１が、対象オブジェクトに割り当てられたグループの
ための「グループロック・ポインタ」オブジェクト３０
４を指すよう、設定する。次いで、挿入とロック処理は
「相関オブジェクトを繰り返し」手順５６３に続き、他
のグループ参照ポインタを繰り返す。
【００３９】しかし、「グループ参照ポインタはＮＵＬ
Ｌ」判定手順５６５において、グループ参照ポインタが
ＮＵＬＬでないときは、挿入とロック処理は、「グルー
プは割当てグループ」判定手順５７１に続き、相関オブ
ジェクトに関連するグループは対象オブジェクトに割り
当てられたグループと同じグループであるか否かを判定
する。次に挿入とロック処理は「相関オブジェクトを繰
り返し」手順５６３に続き、他のグループ参照ポインタ
を繰り返す。
【００４０】しかし、グループ参照ポインタがＮＵＬＬ
でなく、かつ割当てグループと同一でないときは、挿入
とロック処理は、図９に従って後述する「割当てグルー
プと参照グループを併合」手順５７３に続き、二つのグ
ループを併合する。二つのグループが併合されると、
「繰り返しをリセット」手順５７４が、「相関オブジェ
クトを繰り返し」手順５６３を、新しく併合されたグル
ープからのすべてのグループ参照ポインタが繰り返され
るよう、リセットする。こうして、「割当てグループと
参照グループを併合」手順５７３が、再度呼び出されて
他のグループを今併合したグループに併合する。
【００４１】「相関オブジェクトを繰り返し」手順５６
３が完了すると、挿入とロック処理は、対象グループに
割り当てられたグループをロックする「割当てグループ
をロック」手順５７５に続く。グループがロックされる
と、「相関オブジェクトの参照を解放」手順５７７が、
再度非ＮＵＬＬグループポインタのリスト全体を繰り返
して各グループを解放する。該当するグループが解放さ
れると、「参照ロックのロックを解除」手順５８１が再
度「参照ロック」オブジェクト３０１のロックを解除す
る。次いで、挿入とロック処理は「エンド」端末５８３
で完了し対象オブジェクトを含むロックされ割り当てら
れたグループに戻る。
【００４２】図９は、相互に関連付けられるようになっ
た二つのグループを併合するための、符号６００であら
わされた、グループ併合処理を図示する。グループ併合
処理６００は、図８の「割当てグループと参照グループ
を併合」手順５７３により呼び出され、「スタート」端
末６０１で始まる。次いでグループ併合処理６００は、
「古いグループをロック」手順６０３に続き、「グルー
プロック識別」フィールド３２５内で低い識別値を有す
るグループをロックする。良く知られたロック手順につ
いては、続いて図１０及び図１１に沿って記述する。次
に、「ロック点検」判定手順６０５が、古いグループが
ロックされている間に他のスレッドにより関係リンケー
ジが変更されたか否かを判定する。関係リンケージが変
更されていれば、グループ併合処理６００は、「古いグ
ループのロックを解除」手順６０７に続き、古いグルー
プのロックを解除する。この場合グループ併合処理６０
０は「エンド」端末６０９を通じて完了する。当業者
は、「割当てグループと参照グループを併合」手順５７
３の後には常に「繰り返しをリセット」手順５７４が呼
び出されるので、「古いグループのロックを解除」手順
６０７を呼び出したロックの不定は続いて再試行される
ことを理解するであろう。
【００４３】しかし、「ロック点検」判定手順６０５に
よる判定で古いグループがロックされていて関係リンケ
ージが不変であるとき、グループ併合処理６００は、
「新しいグループをロック」手順６１１に続き、高い識
別値を持つグループ（新しいグループ）をロックする。
次に、「ロック点検」判定手順６１３が、新しいグルー
プがロックされている間に他のスレッドにより関係リン
ケージが変更されたか否かを判定する。関係リンケージ
が変更されていなければ、グループ併合処理６００は、
「新しいグループを古いグループに併合」手順６１５に
続き、新しいグループ（大きいグループロック識別値を
有するグループ）のグループ参照を古いグループのグル
ープロック識別値に設定する。次にグループ併合処理６
００は、新しいグループのロックを解除する「新しいグ
ループのロックを解除」手順６１７及び古いグループの
ロックを解除する「古いグループのロックを解除」手順
６１９に続く。グループ併合処理６００は次いで「エン
ド」端末６０９を通じて完了する。
【００４４】しかし、「ロック点検」判定手順６１３が
関係リンケージは変更されていると判定したとき、グル
ープ併合処理６００は、単に「新しいグループのロック
を解除」手順６１７、「古いグループのロックを解除」
手順６１９及び「エンド」端末６０９を通じて完了す
る。当業者は、「割当てグループと参照グループを併
合」手順５７３の後には常に「繰り返しをリセット」手
順５７４が呼び出されるので、「ロック点検」判定手順
６１３が判定したロックの不定は続いて再試行されるこ
とを理解するであろう。当業者は、デッドロック状態が
起こる可能性を排除するためグループロックを特定の順
序でロックすることが重要であることを理解するであろ
う。
【００４５】先行技術のロック処理を説明するのが有用
である。図１０は、グループのロックに用いられる符号
７００であらわされたグループロック処理を図示する。
グループロック処理７００は、「スタート」端末７０１
で始まり、「ロック試行」手順７０３に続き、グループ
ロック・ミューテックス３２１をロックしようと試み
る。グループロックミューテックス３２１が他のいずれ
かのスレッドによりロックされていなければ、「ロック
試行」手順７０３はグループロック・ミューテックス３
２１を取得する。しかし、「ロック試行」手順７０３
は、単にグループロックミューテックス３２１が既にロ
ックされているか否かを返すだけである。それに構わ
ず、「ロック取得」判定手順７０５が、「ロック試行」
手順７０３によりグループロック・ミューテックス３２
１がうまくロックされたか否かを判定する。グループロ
ック・ミューテックス３２１がうまくロックされていれ
ば、グループロック処理７００は、「エンド」端末７０
７を通じて完了する。グループロック・ミューテックス
３２１が取得されていないと、グループロック処理７０
０は、「条件変数上で待つ」手順７０９に続く。これは
「参照ロック」ミューテックス３０９のロックを解除し
て、グループロック・ミューテックス３２１のロックが
解除になったとの属性にしたがって、呼び出したスレッ
ドを休眠させる。属性が満足されると、「参照ロック」
ミューテックス３０９をロックして現行スレッドが継続
される。現行スレッドが継続されると、グループロック
処理７００は、「ロック試行」手順７０３に続いて、再
度グループロック・ミューテックス３２１をロックする
試みをする。
【００４６】オブジェクトのロックはグループのロック
と同様である。図１１は、オブジェクトのロックに用い
られる符号７５０で示されたオブジェクトロック処理を
図示する。オブジェクトロック処理７５０は、「スター
ト」端末７５１で始まり、「ロック試行」手順７５３に
続き、オブジェクトロック・ミューテックス３２９をロ
ックしようと試みる。オブジェクトロック・ミューテッ
クス３２９が他のいずれかのスレッドによりロックされ
ていなければ、「ロック試行」手順７５３はオブジェク
トロック・ミューテックス３２９を取得する。しかし、
「ロック試行」手順７５３は、単にオブジェクトロック
・ミューテックス３２９が既にロックされているか否か
を返すだけである。それに構わず、「ロック取得」判定
手順７５５が、「ロック試行」手順７５３によりオブジ
ェクトロック・ミューテックス３２９がうまくロックさ
れたか否かを判定する。オブジェクトロック・ミューテ
ックス３２９がうまくロックされているとオブジェクト
ロック処理７５０は、「エンド」端末７５７を通じて完
了する。オブジェクトロック・ミューテックス３２９が
取得されていないとき、オブジェクトロック処理７５０
は、「条件変数上で待つ」手順７５９に続く。これは
「参照ロック」ミューテックス３０９のロックを解除し
て、オブジェクトロック・ミューテックス３２９のロッ
クが解除になったとの属性にしたがって呼び出したスレ
ッドを休眠させる。属性が満足されると、「参照ロッ
ク」ミューテックス３０９をロックして現行スレッドが
継続される。現行スレッドが継続されると、オブジェク
トロック処理７５０は、「ロック試行」手順７５３に続
いて、再度オブジェクトロック・ミューテックス３２９
をロックする試みをする。
【００４７】当業者は、本発明は相互に関連するオブジ
ェクトまたはデータ構造の一個以上のグループを対象と
することを理解するであろう。マルチスレッド環境にお
いて、任意の与えられたインスタンスで単一スレッドの
みがグループにアクセスできる。こうして、本発明は、
大きさを最小にしたグループへのスレッドアクセスを順
序化して、相関データ構造のグループを処理するために
使うことのできるスレッドの数を最大にする。
【００４８】本発明を現在の好適実施例を用いて記述し
たが、当業者は各種の変更と代替が本発明の範囲を逸脱
することなく行われることを理解するであろう。したが
って、本発明の範囲はここに説明した特定の発明実施例
に限定されるものでなく、特許請求の範囲及びその等価
物によってのみ定義されなければならない。
【００４９】
【発明の効果】前述から、本発明は（無限定で）下記の
利点を有していることが認識されるであろう。 １）本発明は、他のスレッドによる中断なしにスレッド
がアクセスする相関オブジェクトのグループを最少にす
る。 ２）本発明は、相関オブジェクトのグループを最少にす
ることにより、非相関オブジェクトを不必要にロックし
ないので、スレッドを不必要に阻止しない。 ３）本発明は、オブジェクトのグループをオブジェクト
コレクションに併合するための効率的な機構である。
【図面の簡単な説明】
【図１】本発明を好適実施例により使用することのでき
るコンピュータシステムを示す。
【図２】好適実施例による二つのグループを持つオブジ
ェクトコレクションを示す。
【図３】好適実施例によるグループリンケージ構造を示
す。
【図４】好適実施例による併合グループを示す。
【図５】好適実施例によるロックされたデータ構造を示
す。
【図６】好適実施例によるオブジェクトへの排他的スレ
ッドアクセスを得るためのオブジェクトロック手順を示
す。
【図７】好適実施例による挿入とロック手順を示す。
【図８】好適実施例による挿入とロック手順を示す。
【図９】好適実施例によるグループ併合手順を示す。
【図１０】先行技術のグループロック手順を示す。
【図１１】先行技術のオブジェクトロック手順を示す。
───────────────────────────────────────────────────── フロントページの続き (72)発明者 アレキサンダー・アール・オールソン アメリカ合衆国 94301 カリフォルニア 州 パロアルト テニーソンアヴェニュー 666

Claims (18)

    【特許請求の範囲】
  1. 【請求項１】 オブジェクトコレクション内の対象オブ
    ジェクトを、非相関オブジェクトをロックしたままにす
    ることなく、ロックするためのコンピュータ制御方法で
    あって、前記オブジェクトコレクションがマルチスレッ
    ド計算環境内の一個以上のスレッドによりアクセスさ
    れ、グループロックが前記対象オブジェクトを含む相関
    オブジェクトの対応グループへのスレッドアクセスを制
    御するものにおいて、前記方法が、（Ａ）前記グループ
    ロックが用いる複数のグループロック・リンケージへの
    スレッドアクセスを制御するため、参照ロックを前記オ
    ブジェクトコレクションに関連付けるステップと、
    （Ｂ）前記相関オブジェクトの対応グループ内における
    第一のオブジェクトと第二のオブジェクトとの間の関係
    の変化に応じて、前記複数のグループロック・リンケー
    ジを修正するステップと、（Ｃ）前記対象オブジェクト
    を含む前記相関オブジェクトの対応グループをロックし
    て、前記対象オブジェクトとその相関オブジェクトとを
    ロックするステップと、の各ステップを含むコンピュー
    タ制御方法。
  2. 【請求項２】 前記ステップ（Ｃ）が、（Ｃ１）前記参
    照ロックをロックするステップと、（Ｃ２）次いで、前
    記相関オブジェクトの対応グループに関連付けられた前
    記グループロックをロックするステップと、（Ｃ３）次
    いで、前記参照ロックのロックを解除するステップと、
    を含む請求項１に記載のコンピュータ制御方法。
  3. 【請求項３】 前記相関オブジェクトの対応グループ
    が、第一のグループロックに関連付けられた相関オブジ
    ェクトの第一のグループであり、前記第二のオブジェク
    トが第二のグループロックに関連付けられた相関オブジ
    ェクトの第二のグループに所属しており、ステップ
    （Ｂ）がさらに、（Ｂ１）前記参照ロックをロックする
    ステップと、（Ｂ２）次いで、前記相関オブジェクトの
    第一のグループと前記相関オブジェクトの第二のグルー
    プとを、単一グループロックに関連付けられた相関オブ
    ジェクトの併合グループに併合するステップと、（Ｂ
    ３）次いで、前記参照ロックのロックを解除するステッ
    プと、を含む請求項１に記載のコンピュータ制御方法。
  4. 【請求項４】 前記第二のオブジェクトが独立であっ
    て、ステップ（Ｂ）がさらに、（Ｂ１）前記参照ロック
    をロックするステップと、（Ｂ２）次いで、前記第二の
    オブジェクトを前記相関オブジェクトの対応グループに
    割り当てるステップと、（Ｂ３）次いで、前記参照ロッ
    クのロックを解除するステップと、を含む請求項１に記
    載のコンピュータ制御方法。
  5. 【請求項５】 前記対象オブジェクトが、前記相関オブ
    ジェクトの対応グループと前記グループロックの一つと
    を関連付ける有向無周期的グラフ（ＤＡＧ）オブジェク
    トである請求項１に記載のコンピュータ制御方法。
  6. 【請求項６】 前記ＤＡＧオブジェクトが画像処理演算
    を記述する請求項１に記載のコンピュータ制御方法。
  7. 【請求項７】 中央処理装置（ＣＰＵ）と前記ＣＰＵに
    結合されたメモリとを有する、オブジェクトコレクショ
    ン内の対象オブジェクトを、非相関オブジェクトをロッ
    クしたままにすることなくロックするための装置であっ
    て、前記オブジェクトコレクションがマルチスレッド計
    算環境内の一個以上のスレッドによりアクセスされ、グ
    ループロックが前記対象オブジェクトを含む相関オブジ
    ェクトの対応グループへのスレッドアクセスを制御する
    ものにおいて、前記装置が、 前記グループロックが用いる複数のグループロック・リ
    ンケージへのスレッドアクセスを制御するため、参照ロ
    ックを前記オブジェクトコレクションに関連付けるよう
    構成された参照ロック機構と、 前記相関オブジェクトの対応グループ内の第一のオブジ
    ェクトと第二のオブジェクトとの間の関係を変更するこ
    とによって、前記相関オブジェクトの対応グループを修
    正するよう構成されたグループ修正機構と、 前記対象オブジェクトを含む前記相関オブジェクトの対
    応グループをロックして、前記対象オブジェクトとその
    相関オブジェクトとをロックするよう構成されたグルー
    プロック機構と、を含む装置。
  8. 【請求項８】 前記グループロック機構が、 前記参照ロックをロックするよう構成された参照ロック
    ロック機構と、 前記参照ロックが前記参照ロックロック機構によりロッ
    クされた後、前記相関オブジェクトの対応グループに関
    連付けられた前記グループロックをロックするよう構成
    された対応グループロック機構と、 前記グループロックが前記対応グループロック機構によ
    りロックされた後、前記参照ロックのロックを解除する
    よう構成された参照ロックロック解除機構と、を含む請
    求項７に記載の装置。
  9. 【請求項９】 前記相関オブジェクトの対応グループ
    が、第一のグループロックに関連付けられた相関オブジ
    ェクトの第一のグループであり、前記第二のオブジェク
    トが第二のグループロックに関連付けられた相関オブジ
    ェクトの第二のグループに所属しており、前記グループ
    修正機構がさらに、 前記参照ロックがロックされている間に、相互関連され
    た前記相関オブジェクトの第一のグループと前記相関オ
    ブジェクトの第二のグループとを、単一グループロック
    に関連付けられた相関オブジェクトの併合グループに併
    合するよう構成されたグループ併合機構を含む請求項７
    に記載の装置。
  10. 【請求項１０】 前記第二のオブジェクトが独立であっ
    て、前記グループ修正機構がさらに、前記参照ロックが
    ロックされている間に、前記第二のオブジェクトを前記
    相関オブジェクトの対応グループに割り当てるよう構成
    されたグループ割当機構を含む請求項７に記載の装置。
  11. 【請求項１１】 前記対象オブジェクトが、前記相関オ
    ブジェクトの対応グループと前記グループロックの一つ
    とを関連付ける有向無周期的グラフ（ＤＡＧ）オブジェ
    クトである請求項７に記載の装置。
  12. 【請求項１２】 前記ＤＡＧオブジェクトが画像処理演
    算を記述する請求項７に記載の装置。
  13. 【請求項１３】 オブジェクトコレクション内の対象オ
    ブジェクトを、非相関オブジェクトをロックしたままに
    することなく、コンピュータにロックさせるためのコン
    ピュータ読み取り可能コードを実装するコンピュータ利
    用可能記憶媒体であって、前記オブジェクトコレクショ
    ンがマルチスレッド計算環境内の一個以上のスレッドに
    よりアクセスされ、グループロックが前記対象オブジェ
    クトを含む相関オブジェクトの対応グループへのスレッ
    ドアクセスを制御するものにおいて、前記コンピュータ
    読み取り可能コードが、 前記グループロックが用いる複数のグループロック・リ
    ンケージへのスレッドアクセスを制御するため、参照ロ
    ックを前記オブジェクトコレクションに関連付けるよう
    構成された参照ロック機構が、前記コンピュータによっ
    て動作されるよう構成されたコンピュータ読み取り可能
    プログラムコードと、 前記相関オブジェクトの対応グループ内の第一のオブジ
    ェクトと第二のオブジェクトとの間の関係を変更するこ
    とによって、前記相関オブジェクトの対応グループを修
    正するよう構成されたグループ修正機構が、前記コンピ
    ュータによって動作されるよう構成されたコンピュータ
    読み取り可能プログラムコードと、 前記対象オブジェクトを含む前記相関オブジェクトの対
    応グループをロックして、前記対象オブジェクトとその
    相関オブジェクトとをロックするよう構成されたグルー
    プロック機構が、前記コンピュータによって動作される
    よう構成されたコンピュータ読み取り可能プログラムコ
    ードと、を含むコンピュータプログラム製品。
  14. 【請求項１４】 前記グループロック機構が、 前記参照ロックをロックするよう構成された参照ロック
    ロック機構が、前記コンピュータによって動作されるよ
    う構成されたコンピュータ読み取り可能プログラムコー
    ドと、 前記参照ロックが参照ロックロック機構によりロックさ
    れた後、前記相関オブジェクトの対応グループに関連付
    けられた前記グループロックをロックするよう構成され
    た対応グループロック機構が、前記コンピュータによっ
    て動作されるよう構成されたコンピュータ読み取り可能
    プログラムコードと、 前記グループロックが前記対応グループロック機構によ
    りロックされた後、前記参照ロックのロックを解除する
    よう構成された参照ロックロック解除機構が、前記コン
    ピュータによって動作されるよう構成されたコンピュー
    タ読み取り可能プログラムコードと、を含む請求項１３
    に記載のコンピュータプログラム製品。
  15. 【請求項１５】 前記相関オブジェクトの対応グループ
    が、第一のグループロックに関連付けられた相関オブジ
    ェクトの第一のグループであり、前記第二のオブジェク
    トが第二のグループロックに関連付けられた相関オブジ
    ェクトの第二のグループに所属しており、前記グループ
    修正機構がさらに、 前記参照ロックがロックされている間に、相互関連され
    た前記相関オブジェクトの第一のグループと前記相関オ
    ブジェクトの第二のグループとを、単一グループロック
    に関連付けられた相関オブジェクトの併合グループに併
    合するよう構成されたグループ併合機構が、前記コンピ
    ュータによって動作されるよう構成されたコンピュータ
    読み取り可能プログラムコード、を含む請求項１３に記
    載のコンピュータプログラム製品。
  16. 【請求項１６】 前記第二のオブジェクトが独立であっ
    て、前記グループ修正機構がさらに、前記参照ロックが
    ロックされている間に、前記第二のオブジェクトを前記
    相関オブジェクトの対応グループに割り当てるよう構成
    されたグループ割当機構が、前記コンピュータによって
    動作されるよう構成されたコンピュータ読み取り可能プ
    ログラムコードを含む請求項１３に記載のコンピュータ
    プログラム製品。
  17. 【請求項１７】 前記対象オブジェクトが、前記相関オ
    ブジェクトの対応グループと前記グループロックの一つ
    とを関連付ける有向無周期的グラフ（ＤＡＧ）オブジェ
    クトである請求項１３に記載のコンピュータプログラム
    製品。
  18. 【請求項１８】 前記ＤＡＧオブジェクトが画像処理演
    算を記述する請求項１３に記載のコンピュータプログラ
    ム製品。
JP11014244A 1998-01-23 1999-01-22 マルチスレッド計算環境内で関連付けられたデ―タ構造をロックするための方法、装置及びコンピュ―タプログラム製品 Pending JPH11259313A (ja)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US09/012,683 US5995998A (en) 1998-01-23 1998-01-23 Method, apparatus and computer program product for locking interrelated data structures in a multi-threaded computing environment
US09/012683 1998-01-23

Publications (1)

Publication Number Publication Date
JPH11259313A true JPH11259313A (ja) 1999-09-24

Family

ID=21756193

Family Applications (1)

Application Number Title Priority Date Filing Date
JP11014244A Pending JPH11259313A (ja) 1998-01-23 1999-01-22 マルチスレッド計算環境内で関連付けられたデ―タ構造をロックするための方法、装置及びコンピュ―タプログラム製品

Country Status (4)

Country Link
US (2) US5995998A (ja)
EP (1) EP0932101B1 (ja)
JP (1) JPH11259313A (ja)
DE (1) DE69926820T2 (ja)

Families Citing this family (44)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6289410B1 (en) * 1996-07-18 2001-09-11 Electronic Data Systems Corporation Method and system for maintaining consistency of shared objects based upon instance variable locking
CA2222389A1 (en) * 1997-11-27 1999-05-27 Ibm Canada Limited-Ibm Canada Limitee A mechanism for managing the locking and unlocking of objects in java
US5995998A (en) * 1998-01-23 1999-11-30 Sun Microsystems, Inc. Method, apparatus and computer program product for locking interrelated data structures in a multi-threaded computing environment
US6366946B1 (en) * 1998-12-16 2002-04-02 Microsoft Corporation Critical code processing management
US6898617B2 (en) * 1999-11-18 2005-05-24 International Business Machines Corporation Method, system and program products for managing thread pools of a computing environment to avoid deadlock situations by dynamically altering eligible thread pools
US6742032B1 (en) * 1999-12-17 2004-05-25 Xerox Corporation Method for monitoring and encouraging community activity in a networked environment
US7487152B1 (en) * 2000-05-31 2009-02-03 International Business Machines Corporation Method for efficiently locking resources of a global data repository
US7086053B2 (en) * 2000-06-12 2006-08-01 Sun Microsystems, Inc. Method and apparatus for enabling threads to reach a consistent state without explicit thread suspension
US20030131201A1 (en) * 2000-12-29 2003-07-10 Manoj Khare Mechanism for efficiently supporting the full MESI (modified, exclusive, shared, invalid) protocol in a cache coherent multi-node shared memory system
EP1354411A1 (en) * 2001-01-11 2003-10-22 Koninklijke Philips Electronics N.V. Data compression method with identifier of regressive string reference
US6748470B2 (en) * 2001-11-13 2004-06-08 Microsoft Corporation Method and system for locking multiple resources in a distributed environment
US7028300B2 (en) * 2001-11-13 2006-04-11 Microsoft Corporation Method and system for managing resources in a distributed environment that has an associated object
US7406519B2 (en) 2001-11-13 2008-07-29 Microsoft Corporation Method and system for locking resources in a distributed environment
US20030105871A1 (en) * 2001-11-13 2003-06-05 Microsoft Corporation, Method and system for modifying lock properties in a distributed environment
JP4139613B2 (ja) * 2002-03-18 2008-08-27 株式会社日立製作所 データ処理方法
US7293130B2 (en) 2002-05-29 2007-11-06 Intel Corporation Method and system for a multi-level memory
US7457933B2 (en) * 2002-09-09 2008-11-25 Sap Ag Methods and systems for archiving data
AU2003264264A1 (en) * 2002-09-09 2004-04-30 Sap Aktiengesellschaft Electronic data structure for controlling access to data objects using locks
US20060149696A1 (en) * 2002-09-09 2006-07-06 Thorsten Pferdekaemper Method and systems for controlling access to a data object by means of locks
US7693881B2 (en) * 2002-09-09 2010-04-06 Sap Ag Methods and systems for moving data using locks
US7653667B2 (en) * 2002-09-09 2010-01-26 Sap Ag Methods and systems for data moving using locks
US7756813B2 (en) * 2002-09-09 2010-07-13 Sap Ag Electronic data structure for controlling access to data objects using locks
US7594053B2 (en) * 2003-12-12 2009-09-22 Alcatel-Lucent Usa Inc. Adaptive object level locking
US7539678B2 (en) * 2004-01-30 2009-05-26 Microsoft Corporation Systems and methods for controlling access to an object
US7331010B2 (en) 2004-10-29 2008-02-12 International Business Machines Corporation System, method and storage medium for providing fault detection and correction in a memory subsystem
CN100337204C (zh) * 2004-11-05 2007-09-12 华为技术有限公司 软件在线升级的方法
US7765547B2 (en) 2004-11-24 2010-07-27 Maxim Integrated Products, Inc. Hardware multithreading systems with state registers having thread profiling data
US8802113B2 (en) * 2005-10-27 2014-08-12 University Of Notre Dame Extracellular matrix cancer vaccine adjuvant
US7685392B2 (en) 2005-11-28 2010-03-23 International Business Machines Corporation Providing indeterminate read data latency in a memory system
US8176022B1 (en) * 2006-08-26 2012-05-08 Radames Garcia Locking protocol using dynamic locks and dynamic shared memory
US7870459B2 (en) * 2006-10-23 2011-01-11 International Business Machines Corporation High density high reliability memory module with power gating and a fault tolerant address and command bus
US8914565B2 (en) * 2007-06-08 2014-12-16 Sap Ag Locking or loading an object node
US20100082624A1 (en) * 2008-09-30 2010-04-01 Apple Inc. System and method for categorizing digital media according to calendar events
US20100122253A1 (en) * 2008-11-09 2010-05-13 Mccart Perry Benjamin System, method and computer program product for programming a concurrent software application
US8875107B2 (en) 2009-03-24 2014-10-28 International Business Machines Corporation Component lock tracing by associating component type parameters with particular lock instances
US8595692B2 (en) * 2010-03-22 2013-11-26 International Business Machines Corporation Identifying lock granularization opportunities
JP5843514B2 (ja) * 2011-06-22 2016-01-13 キヤノン株式会社 情報処理装置および制御方法およびプログラム
US8756613B2 (en) * 2011-09-23 2014-06-17 International Business Machines Corporation Scalable, parallel processing of messages while enforcing custom sequencing criteria
US8966491B2 (en) * 2012-04-27 2015-02-24 Oracle International Corporation System and method for implementing NUMA-aware reader-writer locks
US9665403B2 (en) * 2013-03-15 2017-05-30 Miosoft Corporation Executing algorithms in parallel
US9613112B2 (en) 2013-03-15 2017-04-04 Miosoft Corporation Structuring data
US9996402B2 (en) 2014-04-07 2018-06-12 Oracle International Corporation System and method for implementing scalable adaptive reader-writer locks
US10108931B2 (en) * 2014-09-26 2018-10-23 Oracle International Corporation Lock-based updating of a document
US10901807B2 (en) 2019-01-02 2021-01-26 International Business Machines Corporation Computer system with concurrency for multithreaded applications

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5319780A (en) * 1987-10-19 1994-06-07 International Business Machines Corporation System that implicitly locks a subtree or explicitly locks a node based upon whether or not an explicit lock request is issued
JPH0784851A (ja) * 1993-09-13 1995-03-31 Toshiba Corp 共有データ管理方法
GB2301204A (en) * 1995-05-23 1996-11-27 Ibm Collaborative data processing
US5852731A (en) * 1995-06-05 1998-12-22 International Business Machines Corporation Computer program product for synchronizing static variable initialization and reference under a multi-threaded computer environment
US5771382A (en) * 1995-06-05 1998-06-23 International Business Machines Corporation System and method for synchronizing static variable initialization and reference under a multi-threaded computer environment
US5822588A (en) * 1995-06-09 1998-10-13 Sun Microsystem, Inc. System and method for checking the use of synchronization locks in a multi-threaded target program
US5701432A (en) * 1995-10-13 1997-12-23 Sun Microsystems, Inc. Multi-threaded processing system having a cache that is commonly accessible to each thread
US5995998A (en) * 1998-01-23 1999-11-30 Sun Microsystems, Inc. Method, apparatus and computer program product for locking interrelated data structures in a multi-threaded computing environment

Also Published As

Publication number Publication date
EP0932101A2 (en) 1999-07-28
DE69926820T2 (de) 2006-06-29
US5995998A (en) 1999-11-30
US6594683B1 (en) 2003-07-15
EP0932101A3 (en) 2001-11-21
DE69926820D1 (de) 2005-09-29
EP0932101B1 (en) 2005-08-24

Similar Documents

Publication Publication Date Title
JPH11259313A (ja) マルチスレッド計算環境内で関連付けられたデ―タ構造をロックするための方法、装置及びコンピュ―タプログラム製品
Jones Concurrent operations on priority queues
EP0881576B1 (en) Method and apparatus for generational garbage collection in a shared heap memory by means of multiple processor units
US6247025B1 (en) Locking and unlocking mechanism for controlling concurrent access to objects
US7451146B2 (en) Almost non-blocking linked stack implementation
EP0874318B1 (en) A method and apparatus for locating object pointers used within exact garbage collection
US6529982B2 (en) Locking of computer resources
US5404521A (en) Opportunistic task threading in a shared-memory, multi-processor computer system
WO2003060705A2 (en) Lock-free implementation of dynamic-sized shared data structure
JP2500079B2 (ja) プログラムの最適化方法及びコンパイラ・システム
JPH113269A (ja) スタックの内容をサブスタックに分離することによる正確なガーベイジ・コレクションを補助するシステムと方法
WO2000033195A1 (en) Elimination of traps and atomicity in thread synchronization
US7451438B2 (en) Method, system and product for identifying and executing locked read regions and locked write regions in programming languages that offer synchronization without explicit means to distinguish between such regions
JPH07191865A (ja) オペレーティング・システムにおけるインタブロックの分析方法
EP0955584B1 (en) Fast synchronization for programs written in the java programming language
EP0784264B1 (en) A computer-implemented process for determining a minimum code set for an executable application in a data processing system
US6951018B2 (en) Method and apparatus for efficiently tracking monitors
Luchangco et al. On the uncontended complexity of consensus
Michael et al. Relative performance of preemption-safe locking and non-blocking synchronization on multiprogrammed shared memory multiprocessors
US6490609B1 (en) Method, apparatus and computer program product for invoking a thread-unaware routine that uses an operation-dependent temporary data structure
US6055529A (en) Method, apparatus and computer program product for extracting known patterns from a data structure in a single pass
Laneve A lightweight deadlock analysis for programs with threads and reentrant locks
US20040128672A1 (en) Generic program adapting general algorithm as iteration
Herman et al. Space-optimal wait-free queues
Scherer et al. BMP-RAP: Branching Multithreaded Pipeline for Real-time Applications with Pooled Resources