JPH1131081A - オブジェクトベースシステムにおけるスレッド同期を行う方法およびコンピュータシステム、並びに、そのためのコンピュータプログラム製品 - Google Patents

Abstract

(57)【要約】 【課題】 スレッドにオブジェクトをロックさせる、ま
た、アンロックさせる技術を開示する。 【解決手段】 本発明の一つの形態において、オブジェ
クトを第一のスレッドに関係づける方法では、まず、そ
のオブジェクトのオブジェクトヘッダフィールドの内容
を取得する。次に、オブジェクトヘッダフィールドから
得られた内容を、第一のスレッドに関連付けられたスタ
ック内の第一の位置に格納する。更に、オブジェクトヘ
ッダフィールドから得られた内容が格納されているスタ
ックを識別する参照インジケータを、オブジェクトヘッ
ダフィールドに格納する。本発明の一つの実施形態にお
いては、更に、オブジェクトヘッダフィールド内に参照
インジケータが格納されていることを示すように、オブ
ジェクトに関連付けられたステータスインジケータを更
新する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、オブジェクトに基
づくシステム（オブジェクトベースシステム）におい
て、オブジェクトをロックし、また、アンロックする技
術に関する。更に詳しくは、オブジェクトベースシステ
ムにおいて、複数の並列スレッドを同期させて効率よく
作動させるための技術に関する。

【０００２】

【従来の技術】オブジェクトは、一般に、演算の集合
と、それらの演算による結果を表す状態とを含んでい
る。オブジェクトは、ある程度の記憶能力を有するとい
う点で、実質的に記憶能力を持たない関数と区別され
る。例えば、あるオブジェクトに関連付けられている演
算によって得られた値は、その演算の引数ばかりでな
く、オブジェクトの状態にも依存する。すなわち、一つ
のオブジェクトから異なった結果が導かれる可能性があ
る。これに対して、関数によって得られた値は、通常、
その関数の引数にのみ依存する。すなわち、所定の引数
の集合に対して、一つの関数からは常に同一の結果が導
かれる。

【０００３】オブジェクトベースの環境において、スレ
ッドはサービスに対する要求を満たすためにしばしば用
いられる。スレッドは、記憶資源の「スケッチパッド」
と見なすことができ、本質的には、コンピュータプログ
ラム内部の一つの連続的な制御フローを意味する。一般
に、スレッドすなわち「制御の道筋（thread of contro
l ）」は、独立に実行することも可能であるような、一
連のＣＰＵインストラクションあるいはプログラミング
言語のステートメントである。当業者に周知のように、
所定のスレッドに関してあるメソッドを起動する（アク
ティブにする）場合、スレッドの実行スタック上に、そ
のメソッドの起動化（アクティベーション）が積み上げ
られる。逆に、そのメソッドが完了する場合、すなわ
ち、そのメソッドを停止する場合には、実行スタックか
らそのメソッドの起動化が取り出される。あるメソッド
の起動により他のメソッドが起動されることもあるの
で、実行スタックは、ＦＩＬＯ（最初に入れたものを最
後に取り出す）方式で作動する。

【０００４】スレッドは、通常、「協働型」か「並列
型」である。ある単一のスレッドが、完全な制御、例え
ば、プロセッサやプロセス等の演算リソースの制御を、
自発的に手放さない限り掌握している場合、スレッドは
協働型と考えられる。一方、並列型のスレッドは、自発
的に制御を手放すこともありえるが、主として他のスレ
ッドがそのスレッドに強制的に制御を手放させ得るよう
に構成されている。

【０００５】並列型のスレッドモデルにおいては、複数
のスレッドが互いに独立に実行可能である。協働型のス
レッドが協同するようにスケジューリングされるのに対
して、並列型スレッドの場合には、中断（プリエンプ
ト）を認めるようにスケジューリングされる。すなわ
ち、或る並列スレッドが実行している演算を、任意の時
点で、スケジューラー等の他の並列スレッドあるいはオ
ペレーティングシステムといった第三者に中断される可
能性もある。プログラムの実行中における重要なイベン
トが、スレッドの中断を引き起こすこともある。例え
ば、あるスレッドの優先度がプログラムに基づいて上昇
し、現在実行中のスレッドの優先度よりも高くなった場
合が、これにあたる。あるいは、所定の時間の経過等の
人工的に誘導されたイベントによりスレッドの中断が引
き起こされることもある。

【０００６】オブジェクトベースのプログラムの実行中
に、一つのスレッドが、複数のオブジェクトが関与して
いる演算の実行を試みる場合がある。一方、複数のスレ
ッドが、単一のオブジェクトに関する演算の実行を試み
る場合もある。ただし、通常は、一つのスレッドのみ
が、いずれの時点においても或る特定のオブジェクトに
関する複数の演算（すなわち同期演算）の一つを実行す
ることを許される。即ち、一時点では、一つのスレッド
のみが、或る所定のオブジェクト上で同期演算を実行す
ることを許される。同期メソッド等の同期演算はブロッ
ク構造を有しており、そのブロック構造においては、メ
ソッドを呼び出すスレッドは、まず、そのメソッドのオ
ブジェクトに同期することを要求され、また、そのメソ
ッドが戻るときには、そのオブジェクトとの同期を解除
するように要求される。スレッドをオブジェクトに同期
させる場合には、通常、メソッドの呼び出しの前に、同
期構造を用いたオブジェクトへのアクセスの制御を伴
う。

【０００７】或るオブジェクト上で定義されている同期
演算に加えて、そのオブジェクト上で定義されているい
くつかの非同期演算が存在することもある。この場合、
二つ以上のスレッドによって、或るオブジェクト上で、
非同期演算を同時に実行することができる。複数の非同
期演算を、或るオブジェクト上で一度に実行することも
できるし、また、一つあるいは複数の非同期演算を、一
つの同期演算として同時に実行するようにこともでき
る。

【０００８】並列スレッドは、制御を強制的に放棄させ
られる時を予測することが出来ないため、ロック、ミュ
ーテックス、セマフォ、モニタ等の同期構造を用いて、
共用リソース上でのスレッドの作動が不適当である期間
柱、共有リソースへのアクセスを制御することができ
る。例えば、二つ以上のスレッドがある特定の時間に同
一のオブジェクト上で処理を行うことがないように、オ
ブジェクトにはロックが備えられていることが多い。ロ
ックは、オブジェクトのロックを所有しているスレッド
のみがそのオブジェクト上でメソッドを実行可能なよう
に構成されている。図１を参照して、オブジェクトのロ
ックを獲得する処理について説明する。オブジェクトの
ロックを獲得する処理が開始されると、まずステップ１
０４で、スレッドが、作動対象となるオブジェクトを取
得する。一般に、スレッドの作動対象となるオブジェク
トは、関連するオブジェクトロックを有する。次に、ス
テップ１０６で、そのオブジェクトがロックされている
かどうかの判定を行う。即ち、そのオブジェクトに関連
付けられているオブジェクトロックが、他のスレッド、
例えば、現在そのオブジェクト上で作動しているスレッ
ド、に保有されているかどうかの判定がなされる。

【０００９】ステップ１０６でオブジェクトがロックさ
れていないと判定された場合には、ステップ１０８で、
そのスレッドがオブジェクトのロックを獲得する。一
方、オブジェクトがロックされていれば、処理はステッ
プ１１０に移り、スレッドは、オブジェクトがアンロッ
クされるまで待機する。オブジェクトがアンロックされ
れば、処理がステップ１１０からステップ１０８に移
り、そのスレッドによりオブジェクトがロックされる。

【００１０】前述したように、スレッドは、オブジェク
トのロックの獲得に成功すれば、そのオブジェクト上で
同期演算を実行することができる。一つのスレッドがオ
ブジェクトのロックを保持している間は、他のスレッド
は、そのオブジェクト上で他の同期演算の実行を試みる
ことはできるし、また、オブジェクト上で非同期演算を
実行することも可能である。スレッドの同期化は、スレ
ッドを相互に作用させて、オブジェクトがロック状態か
あるいはアンロック状態かというオブジェクトのステー
タスを調べ、オブジェクトのロックを保有しているスレ
ッドのみに、ロックされたオブジェクト上で同期演算を
実行することを認めるプロセスである。また、スレッド
の同期化は、スレッドに、オブジェクトのロックを獲得
したり解除したりすることを許容する。

【００１１】オブジェクトロックを所有するスレッドの
みがロックされたオブジェクト上で実行可能であるよう
にするためにスレッドを同期化する場合には、一般に、
同期構造が用いられる。図２は、オブジェクトベースシ
ステムにおいて、スレッドと、オブジェクトと、同期構
造とのインターフェースを示す説明図である。スレッド
２０２は、オブジェクト２０４上で同期演算を実行しよ
うとする。スレッド２０２がオブジェクト２０４上で同
期演算を実行するためには、まず、オブジェクト２０４
に関するオブジェクトロックを獲得する必要がある。

【００１２】スレッド２０２がオブジェクト２０４上で
同期演算を実行しようとする場合、オブジェクト２０４
に関連付けられている同期構造２０６が取得される。一
般に、オブジェクト２０４は、同期構造２０６ａのよう
に、オブジェクト２０４に同期アクセス可能に構成され
る同期構造と動的に関連付けられている。同期構造２０
６ａがオブジェクト２０４をリエントラント（再入可
能）にロック可能な場合、この同期構造２０６ａは、カ
ウンタ２０８を備える。カウンタ２０８は、オブジェク
ト２０４がスレッド２０２によってロックされた回数が
増えるごとにインクリメントされる（値を増やす）。同
期構造２０６ａは、また、オブジェクト２０４、もっと
一般的に言えば、モニタ２０６ａに関連付けられたオブ
ジェクトを識別するオブジェクトポインタ２１０を備え
る。同期構造２０６ａは、さらに、スレッド２０２、即
ち、同期構造２０６ａを現在ロックしているスレッド、
に関する識別子を備える。

【００１３】同期構造キャッシュは、通常、同期構造と
オブジェクトとの間を動的に関連付けるデータ構造とロ
ックの集合である。例えば、オブジェクト２０４は、同
期構造キャッシュを介して同期構造２０６ａに対応づけ
られている。同期構造２０６ａ、２０６ｂ、２０６ｃは
オブジェクトよりも大きなメモリ空間を必要とするかも
しれないが、同期構造２０６の大きさは、オブジェクト
と同等のものでかまわないので、多くの場合、同期構造
２０６は動的にオブジェクトと関連付けられる。同期構
造２０６ａをオブジェクト２０４と動的に関連付けるこ
とにより、例えば、オブジェクト２０４がロックされて
同期構造２０６ａが使用中である場合等の必要な場合を
除いて、オブジェクト２０４が比較的大容量のメモリと
関連付けられることを防止できる。

【００１４】同期構造２０６ａは、オブジェクト２０４
と本質的に関連付けられているわけではないので、スレ
ッド２０２がオブジェクト２０４上で同期演算の実行を
試みる場合、同期構造２０６ａを検索する必要がある。
より詳しく言えば、同期構造２０６ａのキャッシュ２１
２を検索することにより、同期構造２０６ａを見つけ
る。一般に、任意の或るオブジェクト２０４に関連付け
られている同期構造２０６は一つだけである。オブジェ
クト２０４に関連付けられている同期構造２０６が見つ
からない場合には、任意の適当な方法でモニタ２０６を
割り当てることができる。

【００１５】

【発明が解決しようとする課題】或るオブジェクトと共
に用いる適当なモニタを見つけるためには、同期構造の
ソフトウェアキャッシュあるいはハッシュテーブルを検
索する必要があるので、オブジェクトのステータス（状
態）を追跡するための同期構造としてモニタを用いる方
法は、多くの場合、比較的効率が悪い。このような検索
には時間がかかり、比較的大量のコンピュータシステム
リソースが必要となる。同期構造のキャッシュは、それ
自身で、相当な容量のコンピュータメモリを必要とす
る。更に、適当なモニタがない場合にはオブジェクトに
モニタを割り当てるメモリ管理が必要となり、これにも
コストがかかる。また、複数のスレッドが同期構造キャ
ッシュを共有するので、アクセスあるいは更新よりも前
に、同期構造キャッシュをロックする必要性がある。こ
れは、実行時間に余分な負荷をかける結果となり、更
に、同時に二つ以上のスレッドが同期構造キャッシュに
アクセスしようとした場合には、ロック操作の競合の原
因となる。

【００１６】同期構造がリエントラントなロック操作を
支援している場合には、或るスレッドがあるオブジェク
トを今までにロックした回数を追跡するために直接的な
カウンタが必要となる。コンピュータシステムリソース
の使用という観点からすると、直接的なカウンタの実現
と維持にはかなり費用がかかる。更に、自分をロックし
たスレッドの追跡を直接的に続けるためには、同期構造
を連続的に更新する必要がある。コンピュータシステム
リソースの消費という観点からすると、同期構造の連続
的な更新には、時間と費用がかかる。

【００１７】同期構造の使用は、複数のスレッドによる
同期演算の同時実行を防ぐためには有効であるが、上述
したように、システムリソースの消費という観点からは
非効率的で高くつく。更に、同期オブジェクトをロック
し、アンロックするためのスペースオーバーヘッドが高
い一方、ロックおよびアンロック操作の実行速度は低
い。このため、オブジェクトのロックおよびアンロック
を効率的に行う技術が必要とされている。特に、同期ス
レッドを用いるオブジェクトベースシステムにおいて、
オブジェクトのステータス（状態）を追跡する効率のよ
い技術が求められている。

【００１８】

【課題を解決するための手段およびその作用・効果】本
発明は、スレッドにオブジェクトをロックさせる、ま
た、アンロックさせる方法並びに装置を開示する。本発
明の一つの形態において、或るオブジェクトを第一のス
レッドに関連付ける方法では、まず、そのオブジェクト
のオブジェクトヘッダフィールドの内容を取得する。次
に、オブジェクトヘッダフィールドから得られた内容
を、第一のスレッドに関連付けられたスタック内部の第
一の位置に格納する。更に、オブジェクトヘッダフィー
ルドから得られた内容が格納されているスタックを識別
する参照インジケータを、オブジェクトヘッダフィール
ドに格納する。本発明の一つの実施形態においては、こ
の方法は、更に、オブジェクトヘッダフィールド内に参
照インジケータが格納されていることを示すように、オ
ブジェクトに関連付けられた状態インジケータを更新す
る。このような実施形態において、オブジェクトヘッダ
フィールドの内容がヘッダ値を含んでいてもよく、ま
た、オブジェクトが第一のスレッドにアクセス可能であ
ることを示すように状態インジケータを更新するように
してもよい。

【００１９】本発明の別の形態において、第一のスレッ
ドを用いてオブジェクトのヘッダ値を取得するためのコ
ンピュータにより実現される方法では、まず、オブジェ
クトのヘッダフィールドの内容を、第一のスレッドに関
連付けられている実行スタックを識別するセンチネルと
置き換える。オブジェクトヘッダフィールドの内容がセ
ンチネルに置換されると、オブジェクトヘッダフィール
ドの内容がオブジェクトのヘッダ値を含むかどうかの判
断がなされる。ここで、オブジェクトヘッダフィールド
の内容がオブジェクトのヘッダ値を含んでいないと判定
されると、次に、オブジェクトが第二のスレッドにより
調査中であるかどうかの判断がなされる。本発明の一つ
の実施形態において、オブジェクトが第二のスレッドに
より調査中でないと判定された場合には、更に、第二の
スレッドに関連付けられたスタックに関連付けられてい
るリストに、第一のスレッドを加える。このリストは、
第一のスレッドがオブジェクトへのアクセス待機中であ
ることを示すように構成される。

【００２０】

【発明の実施の形態】マルチスレッド型のオブジェクト
ベースシステムにおいては、いずれの時点においても二
つ以上のスレッドが同一のオブジェクト上で動作するこ
とがないように、オブジェクトは、通常、同期構造を備
えている。一般に、同期構造は、或るオブジェクトに関
連付けられている同期構造をロックしたスレッドのみ
が、そのオブジェクト上で同期演算を実行できるように
構成されている。各オブジェクトは、それぞれ同期構造
と動的に関連付けられていてもよい。同期構造のキャッ
シュは、それに関連付けられているオブジェクトとは独
立に保持され、また、関連する同期構造に各々のオブジ
ェクトが対応づけられるように検索される。コンピュー
タシステムリソースの使用の観点からすると、適切な同
期構造を検索して、オブジェクトのステータスを反映す
るように同期構造を更新し続ける操作は、手間がかか
り、高くつく。

【００２１】本発明では、同期構造を用いることによっ
てオブジェクトのロック状態を直接的に記録する代わり
に、オブジェクト自身とオブジェクトをロックしている
スレッドのスタックのみを用いて、オブジェクトのロッ
ク状態を暗示的に記録する。オブジェクトがアンロック
された状態では、オブジェクトのヘッダフィールドは、
そのオブジェクトに関する情報を含むヘッダ値を有す
る。あるスレッドがオブジェクトをロックすると、その
スレッドが、そのスレッドに関連付けられている実行ス
タック内にヘッダ値を入れ、また、そのスレッドのスタ
ックを識別するオブジェクトヘッダフィールド内に参照
値を入れる。ここで、オブジェクトヘッダフィールド内
のロック状態インジケータを、オブジェクトがロックさ
れていることを示す状態に設定してもよい。このような
構成において、他のスレッドがオブジェクトのロックを
試みる場合に、ロック状態インジケータを用いてオブジ
ェクトのステータスを判断し、更に、参照値を用いてオ
ブジェクトのロックを現在保持しているスレッドを識別
することもできる。

【００２２】オブジェクトのオブジェクトヘッダフィー
ルド内においてオブジェクトのロック状態を暗示的に示
すことにより、直接的ではあるが費用のかかる同期構造
の使用を省略することができる。直接的な同期構造を省
略することにより、オブジェクトのロック状態の追跡に
要する演算オーバーヘッドを削減することができる。例
えば、ロッキング同期構造に関連付けられているメモリ
管理や、オブジェクトに関する同期構造の検索を伴う演
算を、基本的に省略可能にする。このように、オブジェ
クトのロック状態を暗示的に表示することにより、安価
で、かつ、効率よく、オブジェクトのロック状態を追跡
することができる。本発明は、ミューテックス・ロッ
ク、セマフォ等の様々な同期構造の使用を省略するため
に使用できることに注意すべきである。

【００２３】あるオブジェクトのロック状態が暗示的に
規定されている場合には、オブジェクトをロックしよう
とする度ごとに、スレッドは、通常、そのオブジェクト
に関するロック状態インジケータを調べる。そのスレッ
ドは、更に、オブジェクトのヘッダフィールドの内容を
調べて、そのオブジェクトを既にロックしている他のス
レッドや、あるいは、そのオブジェクトを調査中である
他のスレッドを識別する。次に、図３を参照して、本発
明の一実施例であるスレッドスタックとオブジェクトを
説明する。同期演算（この例では同期メソッド「ｆｏ
ｏ」３０４の呼び出し）が呼び出されるときには、スレ
ッドに付随する（すなわちローカルな）実行スタック３
０２が用いられる。当業者に周知のように、同期メソッ
ド「ｆｏｏ」３０４は、スタック３０２上で実行され
る。まず、スタックポインタ３０６が、スタック３０２
内部の現在のメモリアドレスあるいはメモリ位置、例え
ば、位置３０８を指し示す。

【００２４】メソッド「ｆｏｏ」３０４の呼び出しを行
いうるオブジェクト３１０には、ヘッダフィールド３１
２が含まれる。オブジェクト３１０がアンロックされて
いる場合には、即ち、スレッドによるロック可能な状態
では、オブジェクトヘッダフィールド３１２には、ヘッ
ダ値３１４とロック状態インジケータ３１６とが記憶さ
れている。ヘッダ値３１４には、通常、オブジェクト３
１０に関する情報が含まれている。例えば、ヘッダ値３
１４が、識別ハッシュ値とガーベジコレクション情報、
即ち、メモリ管理情報を備えるようにしてもよい。この
実施例において、ロック状態インジケータは、オブジェ
クト３１０がアンロック状態であるかどうかを示すタグ
・ビットである。図示されているように、ロック状態イ
ンジケータ３１６が値１である場合に、オブジェクト３
１０はアンロック状態である。

【００２５】メソッド「ｆｏｏ」３０４を呼び出す前
に、図４に示すように、ヘッダ値３１４をスタック３０
２上に格納する。一旦ヘッダ値３１４がスタック３０２
上に格納されると、オブジェクト３１０内部のロック状
態インジケータ３１６は、オブジェクト３１０がロック
されたことを示すように設定される。即ち、オブジェク
トヘッダフィールド３１２には、もはやヘッダ値３１４
が含まれていない。この実施例では、図３に示すよう
に、オブジェクト３１０がロックされて場合には、ロッ
ク状態インジケータ３１６は、値０であり、逆に、アン
ロックされている場合には、ロック状態インジケータ３
１６は、値１である。

【００２６】スタック３０２上にヘッダ値３１４が格納
されると、スタック３０２上のスタックヘッダ位置３２
２を表す進行ポインタ３２０が、オブジェクトヘッダフ
ィールド３１２に記録される。スタックヘッダ位置３２
２は、ヘッダ値３１４が格納されているスタック３０２
内部の位置を示す。スタックヘッダ位置３２２は、スタ
ック３０２上で現在使用されているメモリ位置を示すの
で、図示されるように、ヘッダ値３１４がスタック３０
２上に格納されると、スタックポインタ３０６がスタッ
クヘッダ位置３２２を指し示す。

【００２７】一般的にいって、メソッド「ｆｏｏ」３０
４によって、他のメソッドが呼び出される可能性があ
る。特に、メソッド「ｆｏｏ」３０４が、オブジェクト
３１０上で、（図示しない）他の同期メソッド「ｂａ
ｒ」を過渡的に呼び出す場合がある。メソッド「ｆｏ
ｏ」３０４がオブジェクト３１０上でメソッド「ｂａ
ｒ」を呼び出すと、オブジェクト３１０は、元々のメソ
ッド「ｆｏｏ」３０４と新しく呼び出されたメソッド
「ｂａｒ」の両方の呼び出しに必要とされる。ただし、
ヘッダ値３１４は、既にスタック３０２上に格納されて
いるため、スタック３０２上に格納されるためにヘッダ
値３１４が再入力されることはない。その代わりに、図
５に示すように、例えば、値０のインジケータ値３４０
がスタック３０２上に格納される。ここで、ヘッダ値３
１４がスタック３０２上に存在するので、インジケータ
値３４０は、スタック３０２を有するスレッドが、オブ
ジェクト３１０上で他の同期メソッドを呼び出したこと
を示すように構成される。

【００２８】上述したように、スレッドには、協働型と
並列型とがある。協働スレッドと並列スレッドとの相違
は、協働スレッドは一旦制御を獲得すると、自発的に手
放さない限り制御を掌握し続けるのに対して、並列スレ
ッドは制御を獲得しても、いつでもその制御を失う可能
性がある、という点にある。

【００２９】スレッドが或るオブジェクト上で同期演算
を実行するために、通常、スレッドは、そのオブジェク
トに関連付けられたロックを取得する。本実施例では、
オブジェクトのロックの取得は、オブジェクトのヘッダ
フィールドの値を得る処理を含む。或る協働スレッドが
オブジェクトをロックを取得した場合には、他のスレッ
ドから干渉を受けることなく、そのオブジェクトの使用
を完了するまで、前記協働スレッドがオブジェクトロッ
クを保持し続ける。以下に、図６を参照して、協働スレ
ッドがオブジェクトのロックを取得するステップを説明
し、更に、図１１および１２を参照して、並列スレッド
がオブジェクトのロックを取得するステップについて説
明する。

【００３０】まず、図６を参照して、本発明の一実施例
として、協働スレッドがオブジェクトのロックを獲得す
る処理を説明する。本実施例においては、上述したよう
に、オブジェクトロックの獲得は、オブジェクトのヘッ
ダフィールドの値を取得する処理を含む。処理が開始さ
れると、まず、ステップ４０２で、スレッドが、オブジ
ェクトのヘッダフィールドの内容を読み出す。次に、ス
テップ４０４で、オブジェクトのヘッダフィールドの内
容に基づいて、オブジェクトがロックされているかどう
かの判定が行われる。一般に、オブジェクトがロックさ
れている場合には、オブジェクトヘッダフィールドの内
容に、そのオブジェクトをロックしたスレッドを示す参
照値、即ち、進行ポインタが含まれる。一方、オブジェ
クトがアンロック状態のときには、オブジェクトヘッダ
フィールドの内容には、そのオブジェクトのヘッダ値が
含まれる。

【００３１】ステップ４０４でオブジェクトがロックさ
れていないと判定された場合には、処理は４０６に進
み、オブジェクトヘッダフィールドの内容が、そのスレ
ッドに関連付けられたスタック内に格納される。言いか
えると、オブジェクトヘッダフィールドから読み出され
たヘッダ値がスタック上に格納される。ヘッダ値をスタ
ック上に格納した後、処理は、ステップ４０８に進み、
オブジェクトヘッダフィールド内に進行ポインタを格納
する。ここで、進行ポインタは、ヘッダ値が格納された
スタック内の位置を示す参照値を有する（即ち、進行ポ
インタは、ヘッダ値が格納されたスタック上の位置を指
し示す）ということに注意すべきである。進行ポインタ
が格納されると、オブジェクトのロックを獲得する処理
が完了する。

【００３２】一方、ステップ４０４でオブジェクトがロ
ックされていると判定された場合には、処理はステップ
４１０に進み、スレッドがそのオブジェクトのロックを
既に保持しているかどうかを判定する。即ち、今行われ
ている同期演算がリエントラント（再入可能）かどうか
の判定をスレッドが行う。そのスレッドが現在オブジェ
クトのロックを保持していると判定された場合には、そ
のスレッドによってオブジェクト上で実行される次の同
期演算がオブジェクトにアクセス中であることを示して
いる。その結果、本実施例では、ステップ４１２におい
て、そのスレッドに関連付けられているスタック上にイ
ンジケータ値が格納され、そのスレッドが既にオブジェ
クトのロックを保持していること、更に、リエントラン
トな同期演算にオブジェクトが用いられていることが示
される。ここで、インジケータ値は、スレッドスタック
上の他の位置にオブジェクトのヘッダ値が格納されてい
ることを示す適当な値であればよい。例えば、インジケ
ータ値は値０であってもよい。インジケータ値がスタッ
ク内に格納された後は、オブジェクトロックが獲得され
たものと見なされる。

【００３３】同期演算が完了すると、オブジェクトロッ
クを保持しているスレッド（ここでは協働スレッド）
は、もはや、そのオブジェクトロックに関連付けられて
いるオブジェクトを必要としない。そこで、この協働ス
レッドは、オブジェクトをアンロックする。同期演算の
完了や非アクティブ化の際に、オブジェクトのヘッダ値
がスタック上に格納されている場合には、ヘッダ値をオ
ブジェクトヘッダフィールド内で進行ポインタ上に上書
きする。ヘッダ値をオブジェクトヘッダフィールドに戻
すことにより、オブジェクトがアンロックされる。即
ち、オブジェクトはロックされ得る状態となる。逆に、
ロックされたオブジェクトをアンロックしようとする際
に、リエントラントなロックの掌握を示すインジケータ
値がスレッドスタック上に格納されている場合には、当
業者に周知のように、スタックからそのインジケータ値
が取り出される。後者の場合、オブジェクトのヘッダ値
はスレッドスタック上に残っているので、ヘッダ値をオ
ブジェクトヘッダフィールドに戻すアンロッキング操作
が実行されるまで、そのスレッドは、オブジェクトのロ
ックを保持し続ける。

【００３４】協働型スレッドモデルでは、あるスレッド
が制御を掌握すると、他の協働スレッドに制御を自発的
に渡さない限り、そのスレッドが制御を保持し続けるこ
とが許容される。即ち、第一の協働スレッドが或るオブ
ジェクトのロックを取得する作業を開始すると、この第
一の協働スレッドがロックの入手を完了しない限り、他
の協働スレッドが制御を獲得したり、あるいは、他の協
働スレッドが実行されたりすることを認めない。あるい
は、他の協働スレッドが既にそのオブジェクトのロック
を保有している場合には、オブジェクトのロックが解除
されるのを待機ように第一の協働スレッドが準備するま
で、他の協働スレッドが制御を獲得したり、あるいは、
他の協働スレッドが実行されたりすることを認めない。

【００３５】一方、並列型スレッドモデルの場合には、
或るオブジェクトのロックを取得する作業を開始してか
らでも、また、オブジェクトのロックを取得する作業を
完了する前の何時でも、現在制御を保持しているスレッ
ドから無理矢理に制御を取り上げることができる。この
場合には、演算処理を停止させないような機構、即ち、
演算処理の進行を止めないような機構が必要になる。オ
ブジェクトのロックを獲得する作業を開始した第一の並
列スレッドがロックを完全に掌握する前に中断される
と、途中になったロック処理のために、他の並列スレッ
ドによるオブジェクトのロック獲得が妨害されるため、
演算処理が停止される事態が起こりうる。第一の並列ス
レッドが中断された場合でも、第一の並列スレッドがオ
ブジェクトのロックを完了するまで処理の進行を保証す
る方法を、図１１および１２に従って後述する。

【００３６】図７は、本発明の一実施例として、先にロ
ックしたオブジェクトを、協働スレッドがアンロックす
る処理を示すプロセスフロー図である。処理が開始され
ると、まずステップ４２２で、アンロックされるべきオ
ブジェクトからオブジェクトヘッダフィールドの内容を
読み出す。ここで、オブジェクトをアンロックしようと
している同じ協働スレッドが、以前にそのオブジェクト
をロックしているものとする。オブジェクトヘッダフィ
ールドの内容が取得されると、次に、ステップ４２４
で、そのオブジェクトのロックがリエントラント（再入
可能）であるかどうかが判定される。即ち、オブジェク
トヘッダフィールドの内容が、そのオブジェクトをアン
ロックする作業に係わる今回の同期演算によってのみで
なく、オブジェクト上でそのスレッドにより実行された
前回の同期演算によってそのオブジェクトがロックされ
たことを示しているかどうかの判定を行う。

【００３７】ロックがリエントラントであると判定され
た場合には、ステップ４２６に処理が移り、リエントラ
ントな同期演算によりロックが使用されていることを示
すインジケータ値がスタックから取り出される。前述し
たように、このインジケータ値は、オブジェクトのヘッ
ダ値がスレッドスタック上の他の位置に格納されている
ことを示すのに適していればどのような値でもよい。現
在行われている同期演算に関してインジケータ値が取り
出されれば、オブジェクトをアンロックする処理は完了
したと見なされる。ただし、同じ協働スレッドによって
そのオブジェクト上で実行された前回の同期演算に関し
ては、同じ協働スレッドによるオブジェクトのロックは
保持されたままである。

【００３８】一方、ステップ４２４でロックがリエント
ラントではないと判定された場合には、処理がステップ
４３２に移り、ヘッダ値がスレッドスタックからオブジ
ェクトヘッダフィールドに戻される。ヘッダ値が戻され
れば、オブジェクトがアンロックされ、このオブジェク
トをアンロックする処理が終了する。

【００３９】並列スレッドは、通常、オブジェクトを
「調べる」ことが許容されており、より詳しく言うと、
オブジェクトがロック状態かアンロック状態かに係わら
ず、オブジェクトのヘッダフィールドの内容を調べるこ
とができる。並列スレッドに関連付けられているオブジ
ェクトの状態を追跡するために、オブジェクトのヘッダ
フィールドには、オブジェクトがロック状態か、アンロ
ック状態か、あるいは、オブジェクトの調査中であるか
を示す状態インジケータ（ステータスインジケータ）を
備えるようにしてもよい。このような状態インジケータ
を用いることによって、他のスレッドが現在オブジェク
トを調査中であるかどうかをスレッドが判定することが
可能になる。

【００４０】図８は、本発明の第二実施例として、並列
スレッドに関連付けられているスタックとオブジェクト
とを示す説明図である。オブジェクト５０２は、状態イ
ンジケータビット５０６とヘッダ値５０８とを備えるヘ
ッダフィールド５０４を有する。図示するように、ヘッ
ダフィールド５０４はヘッダ値５０８を含んでいるの
で、オブジェクト５０２はアンロック状態である。ヘッ
ダ値５０８には、通常、オブジェクト５０２に関する情
報が含まれる。例えば、これに限定されるものではない
が、ヘッダ値５０８は、識別ハッシュ値やガーベジコレ
クション情報等の情報を有する。状態インジケータビッ
ト５０６は、オブジェクト５０２がロック状態である
か、アンロック状態であるか、あるいは、ビジー（使用
中）であるかを示すように構成されている。本実施例で
は、第一の状態インジケータビット５０６ａが０で、第
二の状態インジケータビット５０６ｂが１である場合に
は、オブジェクト５０２がアンロック状態であることを
示す。

【００４１】同期演算（この例では同期メソッド「ｆｏ
ｏ」５１２）が呼び出されるときには、スレッドに付随
する（すなわちローカルな）実行スタック５１０が用い
られる。オブジェクト５０２が同期メソッド「ｆｏｏ」
５１２の実行に関与する場合に、同期メソッド「ｆｏ
ｏ」５１２は、オブジェクト５０２が他のスレッドによ
ってロックされていない場合であって、かつ、第一のス
レッドによってオブジェクト５０２がロックされた後で
のみ、オブジェクト５０２にアクセス可能になる。図９
は、スタック５１０に関連付けられているスレッドがオ
ブジェクト５０２のロックを完了した後のオブジェクト
５０２の状態を示す説明図である。このとき、ヘッダ値
５０８は、スタック５１０上に存在する。スタック５１
０上におけるヘッダ値５０８の位置を、特にスタックヘ
ッダ位置５２０と称する。

【００４２】ヘッダ値５０８がスタック５１０上に位置
する場合、進行ポインタ５２２がヘッダフィールド５０
４内に挿入され、ヘッダ値５０８の位置を示す。ヘッダ
フィールド５０４内に進行ポインタ５２２が存在してい
ることと、スタック５１０上にヘッダ値５０８が存在し
ていることとは、オブジェクト５０２がロックされてい
ることを示している。従って、状態インジケータビット
５０６は、オブジェクト５０２がロック状態であること
を示すように設定される。本実施例では、オブジェクト
５０２がロックされている場合、状態インジケータビッ
ト５０６ａも状態インジケータビット５０６ｂも０であ
る。

【００４３】スタック５１０に関連付けられたスタック
ポインタ５２４は、スタック５１０内の現在の位置、即
ち、メモリアドレスを識別するように構成される。換言
すれば、同期メソッド「ｆｏｏ」５１２の実行は、スタ
ック５１０内の異なったメモリアドレスへのアクセスを
含んでいる。スタックポインタ５２４は、メソッド「ｆ
ｏｏ」５１２の実行中に、現在使用されているメモリア
ドレスを追跡するために用いられる。図示するように、
スタックポインタ５２４は、スタックヘッダ位置５２０
を参照する。

【００４４】並列スレッドを含むシステムにおいては、
スレッドはオブジェクト５０２を、ほとんどいつでも
「調べる」ことができる。例えば、ヘッダ値５０８がス
タック５１０上にある間に、スレッドがオブジェクト５
０２を調べることもできる。また、ロック状態のオブジ
ェクト５０２を調べようとしているスレッドが、ヘッダ
フィールド５０４の内容を獲得することも可能である。
図１０は、スレッドがヘッダフィールド５０４の内容を
調査しているときの、図９のスタック５１０とオブジェ
クト５０２とを示す説明図である。スタックポインタ５
２４は、異なった位置に移動して、メソッド「ｆｏｏ」
５１２の処理が図９に対して進展していることを示して
いる。図示するように、ヘッダ値５０８がスタック５１
０上にまだ存在している間に、スレッド（これは、スタ
ック５１０に関連付けられているスレッドでもそうでな
いものでも構わない）が、一時的にヘッダフィールド５
０４の内容をセンチネル５３０に置き換える。センチネ
ル５３０は、通常、スレッドに関する識別子を符号化し
た値であり、進行ポインタおよびオブジェクトヘッダ値
と区別されるものでもよい。図９に示されるように、本
実施例においては、進行ポインタ５２２を調べることが
可能なように、センチネル５３０が進行ポインタ５２２
に置き換えられる。ただし、センチネル５５３０に置き
換えられるヘッダフィールド５０４の内容は、ヘッダ値
や他のセンチネルであってもよい。

【００４５】センチネル５３０は、オブジェクト５０２
を調査中のスレッドに関連付けられているスタック内に
おけるスタックポインタドレスを含む。図示される実施
例では、同期メソッド「ｆｏｏ」５１２がリエントラン
トである場合、即ち、同期メソッド「ｆｏｏ」５１２が
他の同期メソッド「ｂａｒ」を過渡的に起動する場合に
は、オブジェクト５０２は、スタック５１０に関連付け
られているスレッドにより再アクセス可能である。前述
したように、センチネル５３０は、位置５３２のアドレ
スを含むようにしてもよいし、あるいは、オブジェクト
５０２を用いる異なった同期メソッドの呼び出しに関連
付けられているスタック内の別の位置のアドレスを含む
ようにしてもよい。

【００４６】オブジェクト５０２のヘッダフィールド内
にセンチネル５３０が存在していることは、オブジェク
ト５０２が「ビジー」であることを示している。オブジ
ェクト５０２がビジーということは、スレッドがオブジ
ェクトを調査中であることを意味する。状態インジケー
タビット５０６は、オブジェクト５０２がビジーである
ことを示すように構成される。例えば、オブジェクト５
０２がビジーである場合、状態インジケータビット５０
６ａは１で、状態インジケータビット５０６ｂは０であ
る。また、センチネル５３０が状態インジケータビット
５０６を含むと考えることもできる。

【００４７】スレッドがオブジェクトのロックを獲得す
るためには（例えば、オブジェクトに関するヘッダ値を
獲得するためには）、通常、スレッドは、オブジェクト
ヘッダフィールドの内容を取得し、調査する。図１１お
よび図１２は、本発明の実施例として、並列スレッドを
用いてオブジェクトのロックを獲得する処理を示すプロ
セスフロー図である。処理が開始されると、まず、ステ
ップ６０２で、オブジェクトをロックしようとしている
スレッド、即ち、「現在のスレッド」に関してセンチネ
ルを作成する。上述したように、センチネルは、関連付
けられているスレッドを識別するように構成される。任
意の適当な方法でセンチネルを作成することができる
が、ビット演算を実行して、そのスレッドに関するスタ
ックポインタに状態インジケータを実質的に加えること
によりセンチネルを作成してもよい。本実施例では、こ
のような状態インジケータが、センチネルが挿入された
オブジェクトが「調査中である」ことを示すビジータグ
として機能する。前記したように、ビジータグは、２つ
のビット、例えば、「１０」、によって表されるように
してもよい。

【００４８】ステップ６０２でセンチネルを作成する
と、オブジェクトをロックしようとしているスレッドに
付随する（すなわちローカルな）特定の位置にセンチネ
ル値が挿入される。次に、ステップ６０４で、その特定
の位置の内容が、オブジェクト（即ち、ロックすべきオ
ブジェクト）のヘッダフィールドの内容と交換（スワッ
プ）される。特定の位置におけるセンチネル値をヘッダ
フィールドの内容と交換する場合に、この交換は、実質
的にアトミックに（すなわち割り込みをかけられない最
小の実行単位で）行われる。当業者に周知のように、特
定の位置の内容をヘッダフィールドの内容とアトミック
に交換するということは、特定の位置の内容とヘッダフ
ィールドの内容とをほとんど瞬間的に交換するというこ
とを意味しており、同様にオブジェクトの調査を試みて
いる任意の第二並列スレッドが、オブジェクトのヘッダ
フィールド内において部分的に交換された値を見いだす
可能性はない。即ち、第一のスレッドがオブジェクトを
調査しようとするのとほぼ同時に第二のスレッドがオブ
ジェクトの調査を試み、その結果、第二のスレッドのロ
ーカルな特定の位置の内容とオブジェクトのヘッダフィ
ールドの内容とを独立に交換する第二の交換作業を実行
することができる。交換が実質的にアトミックに行われ
るため、第二のスレッドによる交換後には、第二のスレ
ッドの特定の位置に、第一のスレッドによる交換前のオ
ブジェクトのヘッダフィールドの内容、あるいは、第一
のスレッドのセンチネル値が含まれることになる。

【００４９】次に、処理フローは、ステップ６０４から
ステップ６０６に移り、オブジェクトがアンロック状態
であるかどうかが判定される。ここで、オブジェクトの
ヘッダフィールド内の値の状態インジケータビット、即
ち、タグビットを用いて、オブジェクトがアンロック状
態であるかどうかを判定してもよい。例えば、図８を参
照して上述したように、状態インジケータビットの値が
「０１」である場合に、オブジェクトはアンロック状態
である。ステップ６０６でオブジェクトがアンロック状
態では無いと判定されたことは、オブジェクトはビジ
ー、即ち、他のスレッドによって調査中であるか、ある
いは、既にロック済みであることを示している。つま
り、オブジェクトがアンロック状態でなければ、オブジ
ェクトヘッダフィールドには、他のスレッドに関するセ
ンチネル値か、あるいは、オブジェクトをロックしたス
レッドを識別する進行ポインタか、が保持されている。
オブジェクトがアンロック状態でない場合には、ステッ
プ６１４で、オブジェクトがビジーであるかどうかが判
定される。

【００５０】本実施例において、ステップ６１４でオブ
ジェクトがビジーでないと判定された場合には、現在の
スレッドにより、そのオブジェクトが第二のスレッドに
よってロックされていると判定され、また、現在のスレ
ッドが交換により獲得したオブジェクトヘッダフィール
ドの内容は、調査対象のオブジェクトのロックを現在保
持している第二のスレッドの進行ポインタである。従っ
て、処理フローは、ステップ６１６に移り、図１３を参
照して後述するように、ヘッダ値が格納されたスレッド
スタックに関連付けられた待機リスト（ウェイタリス
ト）の列に現在のスレッドを加える。スレッドを待機リ
ストに加えた後、図１３を参照して後述するように、ス
テップ６１８で、待機リストが使用中であることを示す
ように、オブジェクトのヘッダ値のスタックヘッダ位置
におけるタグビットを設定する。一般に、ロックすべき
オブジェクトのヘッダ値を有する任意のスレッドの待機
リストの列に現在のスレッドを加えることができる。

【００５１】スタックヘッダ位置におけるタグビットを
設定した後、処理はステップ６２０に移り、ステップ６
０４でヘッダフィールドから入力された内容（即ち、第
二のスレッドの進行ポインタ）をアトミックにオブジェ
クトヘッダフィールドに戻す。この処理後、スレッド
は、処理を続行する通知の待機状態に入る。ステップ６
２２で処理を続行する通知を受け取ると、処理はステッ
プ６０２に戻り、新しいセンチネルを作成して、ロック
を獲得するように、上述の処理を繰り返す。

【００５２】ステップ６１４に戻り、オブジェクトがビ
ジーである場合を考える。オブジェクトがビジーの場合
には、他のスレッドによりオブジェクトの調査が行われ
ている。この場合、ビジーなオブジェクトは、ロック状
態ということも、あるいは、アンロック状態ということ
もありうる。しかし、他のスレッドがオブジェクトを調
査中であるため、現在のスレッド、即ち、オブジェクト
をロックしようとしているスレッドは、そのオブジェク
トがビジーであることが判定できるだけであり、そのオ
ブジェクトがロック状態であるかアンロック状態である
かを判定することはできない。ステップ６１４でオブジ
ェクトがビジーであると判定されると、ステップ６４０
で、オブジェクトのヘッダフィールドの内容が読み出さ
れる。ヘッダフィールドの内容を読み出した後、ステッ
プ６４２で、オブジェクトがビジーであるかどうかの判
定が行われる。

【００５３】ステップ６４２でオブジェクトがビジーで
あると判定された場合には、ステップ６４４で、現在の
スレッドがオブジェクトの調査の試みをアクティブに続
けるべきかどうかの判定がなされる。ビジーのオブジェ
クトは他のスレッドによって調査中であるが、この他の
スレッドは、最終的には、オブジェクトの調査を完了す
る。そして、そのオブジェクトがビジーでなくなった時
には、現在のスレッドがそのオブジェクトにアクセス可
能になる。

【００５４】ステップ６４４における、オブジェクトの
調査の試みをアクティブに続けるべきかどうかの判定
は、任意の数のファクタ（因子）に依存するようにする
ことができる。例えば、カリフォルニア州マウンテンビ
ュのサンマイクロシステムズ社によって開発されたＪａ
ｖａプログラミング言語（Ｊａｖａ（ジャバ）はサンマ
イクロシステムズ社の商標）によって書かれたプログラ
ムを実行するように構成されたＪａｖａ仮想マシン等
の、オブジェクトが関連付けられている仮想マシンを用
いて判定を行うこともできる。本発明を実現するのに適
した仮想マシンの一例を図２４を参照して後述する。オ
ブジェクトのロックを試みる試行の繰り返し回数Ｎとし
ては種々の値を取ることができ、関係システム上で利用
可能な記憶容量を含む因子に基づくようにしてもよい
が、これに限定されるものではない。例えば、一つしか
中央処理装置（ＣＰＵ）を持たないシステムにおいて
は、試行の繰り返しが全く行われないこともありえる。
これは、このようなシステム内では、どの時点において
も、たった一つのスレッドのみが処理を実行するからで
ある。一般に、システムに関連付けられているＣＰＵの
数が増えると、試行回数も増加するが、試行回数は任意
であることに注意すべきである。

【００５５】オブジェクトを調査する試みが更に必要で
あると判定された場合には、処理はステップ６４４から
ステップ６４０に移り、オブジェクトのオブジェクトヘ
ッダフィールドの値が読み出される。一版に、スレッド
が最終的に成功するまでオブジェクトを調査する試みを
続行する場合には、スレッドはスピンロックを実行して
いると言える。一方、ステップ６４４で、オブジェクト
を調査する試みがもはや必要ないと判定された場合に
は、処理はステップ６４６に進み、ステップ６４０でオ
ブジェクトヘッダフィールドから読み出された値から、
１つのスレッドが特定される。一般に、オブジェクトが
ビジーである場合、そのオブジェクトのオブジェクトヘ
ッダフィールドは、現在オブジェクトを調査中のスレッ
ドを識別するセンチネル値を含む。このため、オブジェ
クトヘッダフィールドから読み出された値であって、セ
ンチネルであると判定されたされた値から１つのスレッ
ドを特定する処理は、そのセンチネルによって識別され
るスレッドを捜し出す処理を含んでいる。

【００５６】オブジェクトヘッダフィールドから入力さ
れた値から１つのスレッドを特定した後、ステップ６４
８で、オブジェクトをロックしようとしているスレッド
が、識別されたスレッド（識別スレッド）に関連付けら
れたスレッドのロックを獲得する。ここでは、説明を明
確にするために、オブジェクトをロックしようとしてい
るスレッドを、ロッキングスレッドあるいは現在のスレ
ッドと称する。次のステップ６５０では、識別スレッド
の実行優先度がロッキングスレッドの優先度よりも低い
かどうかの判定を行う。一般に、低い実行優先度を持つ
スレッドは、それよりも高い実行優先度を有する実行可
能なスレッドが無くなるまで、処理を実行することが許
されない。識別スレッドの優先度がロッキングスレッド
の優先度以上であると判定された場合には、ステップ６
５２で、識別スレッドのスレッドロックを解除する。ス
レッドロックを解除した後、処理は、ステップ６０２に
戻り、新しいセンチネルを作成し、オブジェクトのロッ
クを獲得するための処理を繰り返す。

【００５７】一方、ステップ６５０で、識別スレッドの
優先度がロッキングスレッドの優先度よりも低いと判定
された場合には、処理がステップ６５４に移り、識別ス
レッドの優先度を上げる、即ち、高くする。本実施例に
おいては、識別スレッドの優先度を、ロッキングスレッ
ドの実行優先度まで上げる。識別スレッドの優先度を上
げるためには、任意の適当な方法を採用することができ
る。例えば、スレッドに関連付けられているオペレーテ
ィングシステムを呼び出して、スレッドの優先度を変更
するのに適したオペレーティングシステムのメソッドを
実行してもよい。オブジェクトヘッダフィールドによっ
て識別されたスレッドの優先度を上げることにより、図
１４ないし１８を参照して後述するように、スレッドの
処理実行の停止を避けることができる。スレッドの優先
度を上げることにより、コンピュータプログラムの実行
が進行することが保証される。即ち、スレッドの優先度
を上げることにより、本質的に、プログラムの実行に演
算サイクルが与えられると共に、与えられたサイクルの
うち少なくともいくつかが識別スレッドに対して利用可
能となり、その結果、ロッキングスレッドがロックしよ
うとしているオブジェクトの調査の完了に寄与すること
になる。通常は、識別スレッドがオブジェクトの調査を
完了するため、ロッキングスレッドは、オブジェクトを
調査する機会を最終的に保証されることになる。このよ
うにして、ロッキングスレッドは、次に、「有効な」作
業の実行を続けることができる。

【００５８】識別スレッドの優先度を上げた後、ステッ
プ６５６で、新たに優先度が高くなったスレッド（優先
度上昇スレッド）内部のブーストカウンタをインクリメ
ントする（カウンタの値を増やす）。ブーストカウンタ
はタイムスタンプ（時刻印）として有効に機能し、優先
度上昇スレッドが（より詳しくは、優先度上昇スレッド
の優先度が）最後に上げられた時を示す。続いて、処理
は、ステップ６５６からステップ６５８に移り、新たな
優先度上昇スレッドとブーストカウンタとが、ロッキン
グスレッドに関連付けられている優先度上昇スレッドの
列に加えられる。優先度上昇スレッドの列は、基本的
に、ロッキングスレッドによって今までに優先度を上げ
られたスレッドを追跡するためにそのロッキングスレッ
ドによって用いられるデータ構造である。例えば、優先
度上昇スレッドの列は、ロッキングスレッドによって今
までに優先度を上げられた実質的に全てのスレッドのリ
ストである。

【００５９】ロッキングスレッドに関連付けられている
優先度上昇スレッドの列が、新たな優先度上昇スレッド
とインクリメントされたブーストカウンタによって更新
されると、ステップ６６０で、ロッキングスレッドが、
優先度上昇スレッドのスレッドロックを放棄する。その
後、処理は、ステップ６０２に戻り、新たなセンチネル
値を作成して、オブジェクトのロックを取得する処理を
続ける。

【００６０】一方、ステップ６４２で、前にビジーだっ
たオブジェクトが今はビジーではないと最終的に判定さ
れた場合、これは、先にオブジェクトを調査していたい
かなるスレッドも、今はオブジェクトを調査していない
ことを意味している。このように、ステップ６４２で、
オブジェクトがビジーではないと判定されると、処理が
ステップ６０２に戻り、新しいセンチネルを作成し、オ
ブジェクトのロックを取得するための処理を繰り返す。

【００６１】最終的には、ロッキングスレッドがロック
しようとしているオブジェクトがアンロック状態である
と判定されることになる。即ち、ロッキングスレッド
は、最終的にはオブジェクトのロックを獲得することが
できる。ステップ６０６に戻り、ここで、オブジェクト
がアンロック状態であると判定されると、次に、処理は
ステップ６０８に進み、ロッキングスレッドに関連付け
られている全ての優先度上昇スレッドの優先度が引き下
げられる。言いかえると、ロッキングスレッドにより優
先度が引き上げられた可能性のある全てのスレッドの優
先度は、それらのスレッドに割り当てられた優先度に戻
される。この処理については、図２２を参照して、後述
する。ステップ６０８で、すべての優先度上昇スレッド
の優先度を引き下げた後、ステップ６１０で、オブジェ
クトヘッダフィールドの内容をロッキングスレッドのス
タック上に格納する。ステップ６０６でオブジェクトが
アンロック状態であると判定されているので、オブジェ
クトヘッダフィールドには、そのオブジェクトに関する
ヘッダ値が含まれている。このため、ステップ６１０で
は、必然的に、ヘッダ値がスタック上のスタックヘッダ
位置に保存される。ヘッダ値をスタック上に保存した
後、ステップ６１２で、スタックヘッダ位置を識別する
進行ポインタを、オブジェクトヘッダフィールド内に挿
入、即ち、保存する。これで、オブジェクトのロックを
獲得する処理が完了する。

【００６２】次に、図１３を参照して、本発明の一実施
例として、図１１のステップ６１８に関連して上述した
スタックヘッダ位置のタグビットに関して説明する。同
期演算が行われる場合、例えば、同期メソッド「ｆｏ
ｏ」７０２が実行される場合には、或るスレッドに関連
付けられているスタック７１０上で同期メソッド「ｆｏ
ｏ」７０２が実行される。オブジェクト７２０に関連付
けられたヘッダ値７１２がスタック７１０上に格納され
ると、オブジェクト７２０がロックされたと見なされ
る。図９を参照して先に説明したように、オブジェクト
７２０のロック状態を、状態インジケータビット７２２
を用いたオブジェクトヘッダフィールド７２４の内容と
進行ポインタ７２６の存在とによって表すようにしても
よい。

【００６３】ヘッダ値７１２は、スタック７１０に関連
付けられているスレッドによって、スタック７１０上の
スタックヘッダ位置７３０に保存される。第一のスレッ
ドがオブジェクト７２０のロックを保持している間に、
第二のスレッドがそのオブジェクト７２０上で同期演算
を実行しようとする場合、第二のスレッドは、オブジェ
クト７２０のロックが利用可能になるまで待機するよう
に要求される。この場合、第二のスレッドは、スタック
７１０上の待機リスト７３２に自分自身を登録して、オ
ブジェクト７２０のロックが利用可能になるまで待機す
る。一般に、ヘッダ値７１２がスタック７１０上に存在
するときに、即ち、第一のスレッドがオブジェクト７２
０のロックを保持しているときに、第二のスレッドがそ
のオブジェクト７２０上で同期演算を実行しようとする
場合には、第二のスレッドは、待機リスト７３２に自分
自身を登録する。スレッドが待機リスト７３２に登録さ
れると、オペレーティングシステム等からオブジェクト
７２０がフリーになったという通知を受け取るまでは、
そのスレッドは処理を実行しない。スタックヘッダ位置
７３０に存在するタグインジケータ７３４は、待機リス
ト７３２に登録されたスレッドが含まれていることを示
すように構成される。このため、オブジェクト７２０が
最終的にアンロックされると、待機リスト７３２に登録
されたスレッドがオブジェクト７２０をロックする処理
を続けてもよいという通知を促進するように、タグイン
ジケータ７３４を用いることができる。図示されている
例では、タグインジケータ７３４が、二つのタグビット
を備えている。

【００６４】並列スレッドモデルでは、複数の並列スレ
ッドが並行してオブジェクトの調査を行おうとした際、
多くの場合、それらの並列スレッドに割り当てられてい
る優先度に基づいて、特定のスレッドがオブジェクトを
調査する許可が与えられるか、および、いつ与えられる
かが決まる。一般に、高い実行優先度を持つスレッド
は、低い実行優先度を持つスレッドよりも、先に、オブ
ジェクトを調査する権利を獲得する。但し、低い優先度
のスレッドが最初にオブジェクトを調査する権利を獲得
して、その後、より高い優先度を持つスレッドが実行可
能（runnable）になったため、制御を放棄するように強
制される、即ち、制御を中断されるということもありえ
る。この場合、実際には、低い優先度を持つスレッド
が、より高い優先度を持つスレッドによるオブジェクト
の調査を妨害する。これは、より高い優先度を持つスレ
ッドがオブジェクトヘッダフィールドの内容をセンチネ
ル値と交換しようとした場合、オブジェクトヘッダフィ
ールド内に、低い優先度を持つスレッドのセンチネル値
が存在するためである。同時に、より高い優先度を持つ
スレッドが実行可能になり、低い優先度のスレッドに優
先して実行されるため、低い優先度を持つスレッドは、
実行不能になり、オブジェクトの調査を終了する。結果
として、オブジェクトを現在調査しているスレッドおよ
びオブジェクトの調査をこれからしようとしているスレ
ッドの何れもが進行不能になる。

【００６５】図１４は、本発明の一実施例として、三つ
のスレッドを有するシステムにおいて、その三つのスレ
ッドが同じオブジェクトの調査を試みた場合の説明図で
ある。図示するように、第一のスレッド８０２の優先度
は「２」であり、これは、第一のスレッド８０２の実行
優先度がかなり低いことを意味する。第二のスレッド８
０４の実行優先度は「４」であり、これは、第一のスレ
ッド８０２に割り当てられた優先度よりも高い。第三の
スレッド８０６の実行優先度は７であり、これは、第一
のスレッド８０２および第二のスレッド８０４に割り当
てられた優先度のいずれよりも高い。

【００６６】優先度の割り当ては、より高い優先度を持
つスレッドが特定のオブジェクトを調査しようとした場
合に、自分より高い優先度を持つ全てのスレッドが実質
的にそのオブジェクトの調査を終了するまで、低い優先
度を持つスレッドはそのオブジェクトを調査することが
できないように行われる。例えば、第三のスレッド８０
６が実行されてオブジェクト８０８を調査しようとした
場合には、第三のスレッド８０６がオブジェクト８０８
の調査を完了するまで、より低い優先度のスレッド（例
えば第一のスレッド８０２）はそのオブジェクト８０８
を調査することができない。但し、第一のスレッド８０
２が第二のスレッド８０４および第三のスレッド８０６
よりも先に実行を開始している場合には、第一のスレッ
ドがオブジェクト８０８のオブジェクトヘッダフィール
ド８１２の内容をセンチネル値と交換して、さらに、そ
の交換の結果として、オブジェクト８０８からオブジェ
クトヘッダ値８１０を獲得しているということもありえ
る。図１５に示すように、オブジェクトヘッダフィール
ド８１２の内容には、ヘッダ値８１０が含まれている。

【００６７】オブジェクトヘッダフィールド８１２の内
容を第一のスレッド８０２が獲得すると、それと交換
に、第一センチネル８２０がオブジェクトヘッダフィー
ルド８１２に移る。第一センチネル８２０は、第一のス
レッド８０２を識別するための任意の適当な値であれば
よいが、例えば、第一センチネル８２０は、第一のスレ
ッド８０２に関連付けられたスタックポインタのアドレ
スである。第一センチネル８２０は交換によってオブジ
ェクトヘッダフィールド８１２に移り、このセンチネル
は、第一のスレッド８２０を、オブジェクト８０８を調
査しているスレッドとして（即ち、オブジェクト８０８
を「ビジー」にしているスレッドとして）識別する。な
お、「ビジー」状態は、状態インジケータビット８２２
で示される。

【００６８】第一のスレッド８０２がオブジェクトヘッ
ダフィールド８１２の内容を取得し、取得されたオブジ
ェクトヘッダフィールド８１２の内容にヘッダ値８１０
が含まれていると判定されると、第一のスレッド８０２
は、オブジェクトヘッダフィールド８１２内の第一セン
チネル８２０を、第一のスレッドを識別する進行ポイン
タで置き換えようとする。しかし、第一のスレッド８０
２がオブジェクトヘッダフィールド８１２内の第一セン
チネル８２０を進行ポインタで置き換える前に、より高
い優先度を持つスレッド（例えば、第二のスレッド８０
４）がオブジェクト８０８にアクセスすると、第一のス
レッド８０２は妨害されて、オブジェクト８０８の調査
を完了することができない。

【００６９】第二のスレッド８０４がオブジェクトヘッ
ダフィールド８１２の内容を取得すると、図１６に示す
ように、第二のスレッド８０４は、第一センチネル８２
０を得て、オブジェクトヘッダフィールド８１２内に第
二センチネル８３０を入力する。第二センチネル８３０
は、例えば、第二のスレッド８０４に関連付けられたス
タックポインタのアドレスである。第二のスレッド８０
４が獲得したオブジェクトヘッダフィールド８１２の内
容には、ヘッダ値８１０ではなく、第一センチネル８２
０が含まれているため、第二のスレッド８０４は、オブ
ジェクト８０８の調査の試みを成功するまで継続する。

【００７０】前述したように、第二のスレッド８０４の
優先度は第三のスレッド８０６の優先度よりも低い。こ
のため、第二のスレッド８０４がオブジェクト８０８の
調査を完了する前であって、かつ、オブジェクト８０８
の調査を試みた後に、第三のスレッド８０６がオブジェ
クトヘッダフィールド８１２の内容にアクセスすると、
オブジェクトヘッダフィールド８１２の内容がセンチネ
ル値で置き換えられているので、第三のスレッド８０６
は、図１７に示すように、第二センチネル８３０を取得
し、オブジェクトヘッダフィールド８１２内に第三セン
チネル８４０を入力する。第三センチネル８４０は、例
えば、第三のスレッド８０６に関連付けられたスタック
ポインタのアドレスである。第三のスレッド８０６が取
得したオブジェクトヘッダフィールド８１２の内容に
は、ヘッダ値８１０ではなく、第二センチネル８３０が
含まれているため、第三のスレッド８０６は、オブジェ
クト８０８を調査の試みを成功するまで継続する。

【００７１】第三のスレッド８０６の優先度は、第二の
スレッド８０４および第一のスレッド８０２の優先度よ
りも高いため、第三のスレッド８０６が実行中である限
り、第二のスレッド８０４も第一のスレッド８０２も処
理を続行してオブジェクト８０８にアクセスすることは
できない。しかし、第一のスレッド８０２が処理を完了
して、オブジェクトヘッダフィールド８１２にヘッダ値
８１０を最終的に戻すまで、第三のスレッド８０６は、
ヘッダ値８１０を得ることができない。この結果、「ス
ターベーション問題（飢餓問題）」が生じる。スターベ
ーション問題は、同じオブジェクトの調査を必要とする
より高い優先度を持つ他のスレッドが処理を開始して、
その結果、オブジェクトの調査を既に始めているスレッ
ドの調査完了を妨害をするため、オブジェクトの調査を
始めたスレッドがオブジェクトの調査を完了できないと
きに起こる。

【００７２】このスターベーション問題を解決する一つ
の手法として、実行スレッドの中で一番高い優先度を持
つスレッド、例えば第三のスレッド８０６が、他のスレ
ッドの優先度を一時的に引き上げる構成が考えられる。
この例では、第三のスレッド８０６がオブジェクト８０
８の調査を試みた結果として、第二のスレッド８０４の
センチネル値を受け取っている。オブジェクト８０８を
調査しようとした際に第三のスレッド８０６が第二のス
レッド８０４のセンチネル値を受け取ったということ
は、第三のスレッド８０６が処理を続行できるかどうか
は、第二のスレッド８０４の処理の進行に「依存してい
る」ということである。即ち、第二のスレッド８０４の
処理の進行が保証されれば、第三のスレッド８０６の処
理の進行も保証されることになる。第三のスレッド８０
６が現在実行中なので、第三のスレッド８０６と同一の
優先度を持つスレッドが一般に実行可能である。従っ
て、第二のスレッド８０４の優先度を第三のスレッド８
０６の優先度まで引き上げることにより、第二のスレッ
ド８０４の実行を可能にすれば、その結果、第三のスレ
ッド８０６もいずれは実行可能になる。

【００７３】オブジェクト８０８の調査を試みた際に第
三のスレッド８０６が受け取った第二のスレッド８０４
のセンチネル値には、第二のスレッド８０４の実行スタ
ック内へのポインタが含まれている。第三のスレッド８
０６は、このポインタを第二のスレッド８０４の実行ス
タック内で用いて第二のスレッド８０４を識別し、この
識別に基づいて、第三のスレッド８０６の優先度と同じ
になるように、第二のスレッド８０４の優先度を引き上
げる。第二のスレッド８０４の優先度を第三のスレッド
８０６の優先度まで引き上げることにより、第三のスレ
ッド８０６と実質的に同じ頻度で第二のスレッド８０４
を実行することが可能となる。

【００７４】同様に、第二のスレッドが実行され、オブ
ジェクト８０８の調査を試みた際に、第一のスレッド８
０２のセンチネル値を受け取ったことを第二のスレッド
自身で判別することができる。オブジェクト８０８を調
査しようとした際に第二のスレッド８０４が第一のスレ
ッド８０２のセンチネル値を受け取ったということは、
第二のスレッド８０４が処理を続行できるかどうかは、
第一のスレッド８０２の処理の進行に依存している、と
いうことである。オブジェクト８０８の調査を試みた際
に第二のスレッド８０４が受け取った第一のスレッド８
０２のセンチネル値には、第一のスレッド８０２の実行
スタック内へのポインタが含まれている。第二のスレッ
ド８０４は、このポインタを第一のスレッド８０２の実
行スタック内で用いることにより第一のスレッド８０２
を識別し、この識別に基づいて、第二のスレッド８０４
の優先度と同じになるように、第一のスレッド８０２の
優先度を引き上げる。第一のスレッド８０２の優先度を
第二のスレッド８０４の優先度まで引き上げることによ
り、第二のスレッド８０４と同じ頻度で第一のスレッド
８０２を実行することができる。当業者であれば理解で
きるように、実行中のスレッド（即ち、第三のスレッド
８０６）の優先度を第二のスレッド８０４に伝播させる
ことによって、第二のスレッド８０４を実行可能にする
ことができる。優先度の引き上げの結果、第二のスレッ
ド８０４が実行されると、更に、第二のスレッド８０４
の優先度が第一のスレッド８０２に伝播される。第三の
スレッド８０６の優先度が元々「７」であった場合、図
１８に示すように、第二のスレッド８０４と第一のスレ
ッド８０２の優先度も「７」に引き上げられる結果にな
る。優先度を「７」に引き上げられた結果、第一のスレ
ッド８０２は、第三のスレッド８０６および第二のスレ
ッド８０４と同じ頻度で実行可能になり、オブジェクト
８０８の調査を完了することができる。第一のスレッド
８０２がオブジェクト８０８の調査を完了すると、第二
のスレッド８０４および第三のスレッド８０６が、オブ
ジェクト８０８を調査する試みを再開することができ
る。

【００７５】オブジェクトのロックを保持しているスレ
ッドがオブジェクトをアンロックするためには、そのス
レッドは、そのオブジェクトを調査して、オブジェクト
の内容が、オブジェクトのアンロックが可能であること
を示しているかどうかを判定する。図１９は、本発明の
第三の実施例として、ロックされたオブジェクトをアン
ロックする方法を示すプロセスフロー図である。スレッ
ドがオブジェクトをアンロックしようとする場合、ま
ず、ステップ９０２で、そのスレッドに関連付けられた
スタック上のスタックヘッダ位置に存在する値を取得す
る。一般に、スタックヘッダ位置は、そのスタックに関
するスタックポインタによって識別される。

【００７６】ステップ９０２でスタックヘッダ位置の値
を取得した後、ステップ９０４では、スタックヘッダ位
置から取得された値が、オブジェクトからのヘッダ値が
スタックヘッダ位置に含まれていないことを示している
かどうかが判断される。本実施例では、スタックヘッダ
位置から取得された値（即ち、スタックヘッダ位置内に
保存されている値）が、ロックがリエントラント（再入
可能）に入力されたことを示すために用いられるインジ
ケータ値であるかどうかを判断することにより、この判
定を行う。スタックヘッダ位置に保存されている値がこ
のようなインジケータ値であると判断された場合には、
スレッドが他のスタック位置にオブジェクトのヘッダ値
をいまだに保持しているので、オブジェクトは完全にア
ンロックされていない可能性を示すことになる。スタッ
クヘッダ位置から取得された値がこのようなインジケー
タ値である場合には、オブジェクトをアンロックする処
理は完了したものと見なされる。ステップ９０４でスタ
ックヘッダ位置に格納された値がこのインジケータ値で
あると判定された場合には、当業者に周知のように、そ
のインジケータ値はスタックから取り出される。

【００７７】一方、ステップ９０４でスタックヘッダ位
置に格納された値がそのようなインジケータ値ではない
と判定された場合には、処理はステップ９０６に移り、
そのスレッドに関するセンチネル値を、アンロックすべ
きオブジェクトのヘッダと交換する。本実施例では、セ
ンチネル値は、オブジェクトヘッダフィールドの内容と
アトミックに交換（スワップ）される特定の位置に格納
される。ステップ９０６でセンチネル値をオブジェクト
ヘッダフィールドの内容と交換した後、ステップ９０８
では、オブジェクトヘッダフィールドから得られた値が
センチネルであるかどうかの判定がなされる。オブジェ
クトヘッダフィールドから得られた値がセンチネルであ
る場合、これは、アンロックするべきオブジェクトがビ
ジーである、即ち、他のスレッドによる「調査中」であ
ることを示す。このように、オブジェクトヘッダフィー
ルドから得られた値がセンチネルである場合には、処理
はステップ９０６に戻り、スレッドに関するセンチネル
値を再びオブジェクトヘッダフィールドの内容と交換す
る。

【００７８】一方、ステップ９０８において、オブジェ
クトヘッダフィールドから得られた値がセンチネルでは
ないと判定された場合には、ステップ９１０において、
スタックヘッダ位置から取得された値をオブジェクトの
オブジェクトヘッダフィールドに保存する。本実施例で
は、スタックヘッダ位置に格納されている値は、オブジ
ェクトのヘッダ値である。オブジェクトのオブジェクト
ヘッダフィールドにヘッダ値を格納することにより、オ
ブジェクトはアンロック状態に戻され、ほとんど全ての
スレッドが自由にオブジェクトのヘッダ値を獲得するこ
とができるようになる。従って、オブジェクトのオブジ
ェクトヘッダフィールドにヘッダ値が戻されると、オブ
ジェクトをアンロックする処理が完了したと見なされ
る。

【００７９】ステップ９０６においてセンチネル値をオ
ブジェクトヘッダフィールドの内容と交換し、ステップ
９０８において交換されたオブジェクトヘッダフィール
ドの内容がセンチネルであるかどうかを判定する繰り返
し処理は、スピンロックであるということもできる。こ
れは、オブジェクトヘッダフィールドから得られた値が
センチネルでなくなるまで、ステップ９０６とステップ
９０８との間で処理を繰り返すことにより、プロセスフ
ローが「スピン」し続けるためである。スピンロック
は、アンロックの対象となっているオブジェクトを用い
るメソッドを実行するプロセスを止めてしまう可能性が
ある。例えば、スピンロックを実行中のスレッドがオブ
ジェクトヘッダフィールドの内容とセンチネル値とを交
換している間は、ロックを解除するための準備として他
のスレッドがオブジェクトヘッダフィールド内にそのセ
ンチネル値を格納することができない。この結果、オブ
ジェクトのロックを解除することができず、更に、スピ
ンロックを実行中のスレッドも処理を進行させることが
できなくなる。

【００８０】このような処理の進行停止を避けるため
に、例えば、オブジェクトのロック解除が妨げられた場
合に、スレッドの優先度を一時的に高くするようにして
もよい。スレッドの優先度を高くする処理により、上述
したように、低い優先度のスレッドを現在実行中のスレ
ッドの優先度まで引き上げることができる。スレッドの
優先度を引き上げることにより、元々優先度の低かった
スレッドが処理を続行可能になり、オブジェクトの調査
を完了して、そのオブジェクトのオブジェクトヘッダフ
ィールドからそのスレッドのセンチネル値を取り出すこ
とができるようになる。

【００８１】次に、図２０および図２１を参照して、本
発明の第四実施例として、優先度を高める手法により、
ロックされたオブジェクトをアンロックする別の方法を
説明する。オブジェクトをアンロックするためには、通
常は、オブジェクトに関するヘッダ値がオブジェクトの
オブジェクトヘッダフィールドに戻される。スレッドが
オブジェクトをアンロックしようとする場合、まず、ス
テップ９４２で、スタックポインタによって識別される
スタックヘッダ位置に格納されている値を取得する。こ
こで、スタックポインタは、オブジェクトをアンロック
しようとしているスレッド（即ち、「現在のスレッ
ド」）に関連付けられているスタックを指し示している
ことに注意すべきである。本実施例では、現在のスレッ
ドは並列スレッドである。

【００８２】ステップ９４２でスタックヘッダ位置に格
納されている値を取得した後、ステップ９４４では、オ
ブジェクトからのヘッダ値がスタックヘッダ位置に含ま
れていないことを、スタックヘッダ位置から取得された
値が示すかどうかの判定を行う。本実施例では、スタッ
クヘッダ位置から取得された値（即ち、スタックヘッダ
位置に保存されている値）が、ロックがリエントラント
（再入可能）に入力されたことを示すために用いられる
インジケータ値であるかどうかを判断することにより、
この判定を行う。スタックヘッダ位置に保存されている
値がこのようなインジケータ値であると判断された場
合、そのスレッドが他のスタック位置にオブジェクトの
ヘッダ値をいまだに保持しているので、オブジェクトが
完全にアンロックされていない可能性を示すことにな
る。スタックヘッダ位置から取得された値がそのような
インジケータ値である場合には、オブジェクトをアンロ
ックする処理は完了したものと見なされる。ステップ９
４４でスタックヘッダ位置に格納された値がそのインジ
ケータ値であると判定された場合には、当業者に周知の
ように、そのインジケータ値はスタックから取り出され
る。

【００８３】スタックヘッダ位置から得られた値がその
ようなインジケータ値でない場合には、処理がステップ
９４６に移り、そのスレッドに関連付けられているセン
チネル値を、アンロックすべきオブジェクトのオブジェ
クトヘッダフィールドの内容と交換（スワップ）する。
上述したように、センチネル値とオブジェクトヘッダフ
ィールドの内容とを交換する交換処理は、アトミック処
理、または、実質的にアトミックに行われる処理であ
る。次に、ステップ９４６からステップ９４８に進み、
オブジェクトがビジーであるかどうかの判定を行う。オ
ブジェクトがビジーであるという表示は任意の適当な形
態で行えるが、例えば、図１０に関連して説明したよう
に、オブジェクトのヘッダフィールドの内容に含まれる
タグビットを使用して、オブジェクトがビジーであるこ
と、例えば、他のスレッドが現在オブジェクトを調査中
であることを示すようにしてもよい。

【００８４】ステップ９４８でオブジェクトがビジーで
はないと判定された場合には、ステップ９５０におい
て、スタックヘッダ位置の値をオブジェクトのオブジェ
クトヘッダフィールドに格納する。オブジェクトがビジ
ーでない場合、これは、例えば、交換前にオブジェクト
ヘッダフィールドに存在した値が、現在のスレッド（即
ち、アンロックしようとしているスレッド）のスタック
を参照する進行ポインタであったことを示す。スタック
ヘッダ位置の値がオブジェクトのヘッダフィールドに格
納されると、オブジェクトをアンロックする処理が完了
する。

【００８５】時々は、例えば他のスレッドがオブジェク
トの状態を決めるためにオブジェクトを調査中である場
合などに、オブジェクトがビジーになる。ステップ９４
８でオブジェクトがビジーであると判定された場合、こ
れは、他のスレッドがオブジェクトを調査中であること
（即ち、オブジェクトがロック状態であるかアンロック
状態であるかを他のスレッドが判定中であること）を示
している。オブジェクトがビジーであれば、処理はステ
ップ９５１に移り、オブジェクトのヘッダフィールドを
読み込む。オブジェクトのヘッダフィールドの内容を読
み込んだ後、ステップ９５２で、オブジェクトがまだビ
ジーであるかどうかを判定する。ここで、オブジェクト
がビジーでないと判断されると、処理はステップ９４６
に戻り、スレッドに関連付けられているセンチネル値
を、再び、アンロックすべきオブジェクトのヘッダフィ
ールドの内容と交換する。

【００８６】一方、ステップ９５２でオブジェクトがビ
ジーであると判定されると、処理はステップ９５４に進
み、オブジェクトを調査する試みをアクティブに続ける
べきかどうかの判定がなされる。図１２に関して説明し
たように、この試行の繰り返し回数Ｎは種々の値に設定
可能であり、関係システム上で利用可能な記憶容量を含
む因子（ファクタ）に基づくようにしてもよいが、これ
に限定されるものではない。

【００８７】オブジェクトを調査する試みが更に必要で
あると判定された場合には、処理はステップ９５４から
ステップ９５１に移り、オブジェクトのヘッダフィール
ドの内容が読み出される。ステップ９５１、９５２、９
５４の間のループは一種のスピンロックであると考える
ことができる。これは、オブジェクトがビジーでなくな
るか、あるいは、試行の繰り返し回数Ｎが或る値を超え
るまで、このループを繰り返すからである。

【００８８】一方、ステップ９５４で、オブジェクトを
調査する試みはもはや必要ないと判定された場合には、
処理はステップ９５６に進み、オブジェクトヘッダフィ
ールドから入力された値からスレッドが特定される。一
般に、オブジェクトがビジーである場合、そのオブジェ
クトのオブジェクトヘッダフィールドは、現在オブジェ
クトを調査中のスレッドを識別するセンチネル値を含
む。このため、オブジェクトヘッダフィールドから入力
された値（センチネルであると判定されたもの）からス
レッドを識別する処理は、センチネルによって識別され
るスレッドを捜し出す処理を含んでいる。

【００８９】オブジェクトヘッダフィールドから取得さ
れた値からスレッドが特定されると、ステップ９５８に
おいて、オブジェクトをアンロックしようとしているス
レッドが、識別されたスレッド（「識別スレッド」と呼
ぶ）に関連付けられたスレッドロックを獲得する。ここ
では、説明を明確にするために、オブジェクトをアンロ
ックしようとしているスレッドを、アンロッキングスレ
ッドと称する。次のステップ９６０では、識別スレッド
の優先度がアンロッキングスレッドの優先度よりも低い
かどうかの判定を行う。識別スレッドの有する優先度が
アンロッキングスレッドの優先度以上であると判定され
た場合には、ステップ９６２で、識別スレッドのスレッ
ドロックが解除される。スレッドロックを解除した後、
処理は、ステップ９４６に戻り、スレッドに関するセン
チネル値を、再び、アンロックすべきオブジェクトのヘ
ッダフィールドの内容と交換する。

【００９０】一方、ステップ９６０で、識別スレッドの
優先度がアンロッキングスレッドの優先度よりも低いと
判定された場合には、処理がステップ９６４に移り、識
別スレッドの優先度を一時的に上げる、即ち、高くす
る。本実施例においては、識別スレッドの優先度が、ア
ンロッキングスレッドの優先度まで高められる。識別ス
レッドの優先度を上げるためには任意の適当な方法を採
用可能であるが、例えば、スレッドに関連付けられてい
るオペレーティングシステムを呼び出して、スレッドの
優先度を変更するのに適したオペレーティングシステム
のメソッドを実行することができる。

【００９１】識別スレッドの優先度を上げた後、ステッ
プ９６６で、新たに優先度が高くなったスレッド（「優
先度上昇スレッド」と呼ぶ）内部のブーストカウンタを
インクリメントする。ブーストカウンタ（即ち、タイム
スタンプ）は、優先度上昇スレッドが、より詳しくは、
優先度上昇スレッドの優先度が、最後に上げられた時を
示す。ブーストカウンタをインクリメントすることによ
り、ブーストカウンタが更新される。続いて、処理フロ
ーは、ステップ９６６からステップ９６８に移り、新た
な優先度上昇スレッドとブーストカウンタとが、アンロ
ッキングスレッドに関連付けられている優先度上昇スレ
ッドの列に加えられる。優先度上昇スレッドの列は、ア
ンロッキングスレッドによって今までに優先度を上げら
れたスレッドを追跡するために、そのアンロッキングス
レッドによって用いられるデータ構造であると考えるこ
ともできる。例えば、優先度上昇スレッドの列は、アン
ロッキングスレッドによって今までに優先度を上げられ
た実質的に全てのスレッドのリストである。

【００９２】アンロッキングスレッドに関連付けられて
いる優先度上昇スレッドの列が、新たな優先度上昇スレ
ッドとそれに対応するブーストカウンタとによって更新
されると、ステップ９７０において、そのアンロッキン
グスレッドによって、優先度上昇スレッドのスレッドロ
ックが解除される。その後、処理フローは、ステップ９
４６に戻り、スレッドに関連付けられているセンチネル
値を、再び、アンロックすべきオブジェクトのヘッダフ
ィールドの内容と交換する。

【００９３】前述したように、優先度を引き上げられた
スレッド、即ち、優先度上昇スレッドの優先度は、それ
に割り当てられている優先度まで引き下げられる、即
ち、戻される。この場合、優先度上昇スレッド自身で優
先度を引き下げてもよいが、優先度上昇スレッドの優先
度を引き上げたスレッドを用いて、優先度上昇スレッド
の優先度を引き下げるようにすることもできる。以下
に、図２２を参照して、本発明の一実施例として、優先
度上昇スレッドの優先度を引き上げたスレッドを用い
て、優先度上昇スレッドの優先度を引き下げる処理を説
明する。即ち、図１１のステップ６０８で行われる処理
の一例を説明する。

【００９４】この処理では、少なくとも部分的に優先度
の引き上げに関与した特定のスレッドがオペレーティン
グシステムを呼び出して、優先度上昇スレッドの優先度
を引き下げる。まず、ステップ９８０では、或るスレッ
ドが、自分が先に他のスレッドの優先度を引き上げたか
どうかを判定する。即ち、或るスレッドが、優先度を引
き上げた可能性のある他のスレッドの優先度の引き下げ
に自分が関与していたかどうかを判定する。優先度を引
き下げるべきスレッドが存在するかどうかの判定には、
任意の適当な方法を用いることができるが、例えば、優
先度上昇スレッドの優先度を引き下げるスレッド（即
ち、「優先度引き下げスレッド」あるいは「現在のスレ
ッド」）に関連付けられている優先度上昇スレッド列を
検索するようにしてもよい。ステップ９８０において、
優先度を引き下げるべき優先度上昇スレッドが存在しな
いと判定された場合には、優先度上昇スレッドの優先度
を引き下げる処理を終了する。

【００９５】一方、ステップ９８０で、優先度を引き下
げる必要性があると考えられる優先度上昇スレッドが存
在すると判定された場合には、ステップ９８２で、優先
度を引き下げられるべきスレッドに関する情報が取得さ
れる。例えば、その優先度引き下げスレッドに関連付け
られている優先度上昇スレッド列から、次の優先度上昇
スレッドとそれに対応するブーストカウンタとを取得す
る。優先度上昇スレッド列から取り出されたブーストカ
ウンタは、通常、優先度引き下げスレッドが、入力され
た優先度上昇スレッドの優先度を引き上げた時を示すよ
うに構成されている。

【００９６】次に、ステップ９８４では、取得された優
先度上昇スレッドに関連付けられたスレッドロックを獲
得する。取得された優先度上昇スレッドに関連付けられ
ているスレッドロックを獲得することにより、取得され
た優先度上昇スレッドの優先度が他のスレッドによって
変更されることが一時的に防止される。次のステップ９
８４では、取得された優先度上昇スレッドからブースト
カウンタが読み出される。取得された優先度上昇スレッ
ドから読み出されたブーストカウンタは、通常、取得さ
れた優先度上昇スレッドの優先度が最後に引き上げられ
た時を示すように構成されており、このため、ブースト
カウンタはタイムスタンプであると考えることができ
る。スレッドに割り当てられてた優先度が、引き上げら
れた優先度以上である場合には、スレッドのブーストカ
ウンタがインクリメントされる。

【００９７】取得された優先度上昇スレッドからブース
トカウンタを読み出した後、ステップ９８８において、
このブーストカウンタを優先度上昇スレッド列から得ら
れたブーストカウンタと比較する。このような比較を行
うことによって、取得された優先度上昇スレッドの優先
度引き上げを最後に行ったのが、優先度引き下げスレッ
ドであるか、あるいは別のスレッドであるかが判定され
る。ステップ９９０では、取得された優先度引き上げス
レッドから読み出されたブーストカウンタが、優先度上
昇スレッド列から得られたブーストカウンタと等しいか
どうかの判定がなされる。言いかえると、優先度引き下
げスレッドが、取得された優先度上昇スレッドの優先度
を最後に引き上げたスレッドとして記録されているかど
うかが判定される。

【００９８】ステップ９９０において、二つのブースト
カウンタが等しいと判定された場合には、処理がステッ
プ９９２に移り、取得された優先度上昇スレッドの優先
度が、そのスレッドに割り当てられている優先度まで引
き下げられる。優先度上昇スレッドの優先度を引き下げ
る処理は、一般には、そのスレッドに関連付けられてい
るブーストカウンタをデクリメントする（あるいは更新
する）処理を含んでいる。ここで、割り当てられている
優先度は、必ずしも、取得された優先度上昇スレッドの
優先度が優先度引き下げスレッドによって引き上げられ
た時点でその優先度上昇スレッドが有していた優先度で
ある必要はないことに注意すべきである。取得された優
先度上昇スレッドに関連付けられているオペレーティン
グシステムは、いつでも、そのスレッドに新しい優先度
を割り当てることができる。例えば、元々の優先度が
「２」である第一のスレッドが、第二のスレッドにより
優先度「６」まで引き上げられ、その後、オペレーティ
ングシステムによって優先度「４」が割り当てられたと
仮定する。このような場合、第二のスレッドが第一のス
レッドの優先度を引き下げる際には、第一のスレッドの
優先度は「４」まで下がる。ステップ９９２において、
取得された優先度上昇スレッドの優先度を引き下げた
後、処理フローはステップ９８０に戻り、優先度引き下
げスレッドが、優先度を引き下げる必要性があると考え
られる他のスレッドの優先度を以前に引き上げたかどう
かの判定が行われる。

【００９９】一方、ステップ９９０で二つのブーストカ
ウンタが等しくないと判定された場合、これは、別のス
レッドが、優先度引き下げスレッドよりも後に、取得さ
れた優先度上昇スレッドの優先度を引き上げたことを意
味している。このような場合には、取得された優先度上
昇スレッドの優先度は優先度引き下げスレッドによって
引き下げられず、処理フローはステップ９８０に戻り、
その優先度引き下げスレッドが以前に他のスレッドの優
先度を引き上げたかどうかの判定が行われる。

【０１００】図２３は、本実施例を実現するのに適し
た、典型的な汎用コンピュータシステムを示す。このコ
ンピュータシステム１０３０は、任意の数のプロセッサ
１０３２（中央処理装置、ＣＰＵとも称される）を備え
る。プロセッサ１０３２は、主記憶装置１０３４（例え
ば、リードオンリーメモリ、ＲＯＭ）および主記憶装置
１０３６（例えば、ランダムアクセスメモリ、ＲＡＭ）
を含む記憶装置に接続されている。

【０１０１】当業者には理解できるように、コンピュー
タシステム１０３０を、より明確には、ＣＰＵ１０３２
を、仮想マシンをサポートするように構成してもよい。
コンピュータシステム１０３０にサポートされる仮想マ
シンの一例を、図２４を参照して後述する。周知のよう
に、ＲＯＭは、単方向処理として、データおよび命令を
ＣＰＵ１０３２に転送する役割を果たす。これに対し
て、ＲＡＭは、双方向へのデータおよび命令の転送に用
いられる。ＣＰＵ１０３２は、任意の数のプロセッサを
備え、また、主記憶装置１０３４、１０３６は、何れ
も、任意の適当なコンピュータ読み取り可能な媒体（記
録媒体）を備える。大容量記憶装置等の補助記憶装置１
０３８も双方向的にＣＰＵ１０３２に接続され、データ
記憶容量を追加する。大容量記憶装置１０３８は、コン
ピュータコード、データ等を含むプログラムを記憶する
ために用いられるコンピュータ読み取り可能な媒体であ
る。典型的には、大容量記憶装置１０３８は、主記憶装
置１０３４、１０３６よりも処理速度の遅いハードディ
スクあるいはテープ等の記憶媒体である。あるいは、大
容量記憶装置１０３８は、磁気テープリーダ、紙テープ
リーダ等の、他の周知の装置の形態を取っていてもよ
い。必要に応じて、大容量記憶装置１０３８の内部に保
持される情報を、仮想記憶として、ＲＯＭ１０３６の一
部に標準的な方法で組み込むようにしてもよい。ＣＤ−
ＲＯＭ等の特殊な主記憶装置１０３４も、単方向処理と
して、ＣＰＵ１０３２にデータを送ることができる。

【０１０２】ＣＰＵ１０３２は、更に、一つ以上の入出
力装置１０４０に接続されている。入力装置１０４０と
しては、ビデオモニタ、トラックボール、マウス、キー
ボード、マイク、タッチセンサーディスプレイ、トラン
スデューサカードリーダ、磁気あるいは紙テープリー
ダ、タブレット、スタイラスペン、音声あるいは手書き
認識装置、あるいは他のコンピュータ等のその他の周知
の入力装置等を含んでいてもよいが、これらに限定され
るものではない。また、ＣＰＵ１０３２を、ネットワー
ク接続を利用して、インターネット、イントラネット等
のコンピュータネットワークあるいは通信ネットワーク
１０１２に接続することもできる。このようなネットワ
ーク接続を利用することにより、ＣＰＵ１０３２がネッ
トワークから情報を入力したり、また、上記のようなメ
ソッドを実行する過程でネットワークに情報を出力する
ことも可能である。ＣＰＵ１０３２を用いて実行される
一連の命令に代表されるような情報を、例えば、搬送波
に乗せられたコンピュータデータ信号の形態で、ネット
ワークから入力したりネットワークに出力したりでき
る。上述した装置等は、コンピュータのハードウェアお
よびソフトウェアの分野では周知のものである。

【０１０３】前述したように、コンピュータシステム１
０３０上で仮想マシンを実行することができる。図２４
は、図２３のコンピュータシステム１０３０にサポート
される、本発明の実現に適した仮想マシンを示す説明図
である。Ｊａｖａプログラミング言語によって書かれた
コンピュータプログラム等のコンピュータプログラムを
実行するときには、コンパイル時環境１１０５内でソー
スコード１１１０をコンパイラ１１２０に入力する。コ
ンパイラ１１２０は、ソースコード１１１０をバイトコ
ード１１３０に翻訳する。一般に、ソフトウェア開発者
によってソースコード１１１０が作成された時点で、ソ
ースコード１１１０がバイトコード１１３０に翻訳され
る。

【０１０４】バイトコード１１３０は、再生され、ダウ
ンロードされ、図２３のネットワーク１０１２等のネッ
トワークを介して分配され、あるいは、図２３の主記憶
装置１０３４等の記憶装置に保存される。本実施例で
は、バイトコード１１３０は、プラットホームには依存
しない。即ち、バイトコード１１３０は、適当な仮想マ
シン１１４０上で実行を行うほとんどどのようなコンピ
ュータシステム上でも実行可能である。

【０１０５】バイトコード１１３０は、仮想マシン１１
４０を備えるランタイム環境（実行時環境）１１３５に
供給される。ランタイム環境１１３５は、通常、図２３
のＣＰＵ１０３２等の一つあるいは複数のプロセッサを
利用することにより実行される。仮想マシン１１４０
は、コンパイラ１１４２と、インタプリタ１１４４と、
ランタイムシステム１１４６とを備える。バイトコード
１１３０は、コンパイラ１１４２に供給されてもよく、
あるいは、インタプリタ１１４４に供給されてもよい。

【０１０６】バイトコード１１３０がコンパイラ１１４
２に供給される場合には、バイトコード１１３０に含ま
れるメソッドが機械語命令に翻訳される。例えば、コン
パイラ１１４２は、メソッドが実行されるときが来るま
でバイトコード１１３０に含まれるメソッドの翻訳を遅
らせるジャスト・イン・タイムコンパイラである。バイ
トコード１１３０がインタプリタ１１４４に供給される
場合には、バイトコード１１３０は、一時に一バイトコ
ードずつインタプリタ１１４４に読み込まれる。各バイ
トコードがインタプリタ１１４４に読み込まれるのに伴
い、インタプリタ１１４４は、各バイトコードによって
規定される演算を実行する。即ち、当業者には理解でき
るように、インタプリタ１１４４は、バイトコード１１
３０を「解釈」する。一般に、インタプリタ１１４４
は、ほぼ連続的にバイトコード１１３０を処理して、バ
イトコード１１３０に関連付けられた演算を実行する。

【０１０７】あるメソッドが他のメソッドによって起動
される場合、あるいは、ランタイム環境１１３５から起
動される場合、そのメソッドがインタプリタで解釈され
るときには、ランタイムシステム１１４６は、インタプ
リタ１１４４によって直接実行可能な一連のバイトコー
ド１１３０の形態で、ランタイム環境１１３５からその
メソッドを取得するようにしてもよい。一方、起動され
たメソッドがコンパイルを完了していないコンパイルメ
ソッドである場合、ランタイムシステム１１４６は、一
連のバイトコード１１３０の形態でランタイム環境１１
３５からメソッドを取得し、コンパイラ１１４２を起動
する。コンパイラ１１４２は、バイトコード１１３０を
機械語命令に変換し、結果として出力される機械語命令
はＣＰＵ１０３２によって直接実行される。仮想マシン
１１４０が終了すると、機械語命令は捨てられる。

【０１０８】以上、本発明の実施例を説明したが、本発
明は、発明の要旨の範囲内で、これ以外の種々の形態で
実施可能である。例えば、オブジェクトのロックおよび
オブジェクトのアンロックに係わるステップを並べ変え
ることもできるし、また、本発明の要旨の範囲内でステ
ップを省略したり追加したりすることも可能である。

【０１０９】上記の実施例では、優先度上昇スレッドの
優先度を引き下げる処理は、優先度上昇スレッドの優先
度を引き上げたスレッドによって開始されているが、優
先度上昇スレッドがそれ自身で優先度を引き下げるよう
にしてもよい。換言すれば、優先度上昇スレッドが、割
り当てられた優先度まで自分自身の優先度を引き下げる
処理を少なくとも開始するように構成することもでき
る。あるいは、いくつかの優先度上昇スレッドの優先度
は、それらに関連付けられた優先度引き上げスレッドに
よって引き下げ、他の優先度上昇スレッドの優先度は自
分自身で引き下げるような構成も可能である。

【０１１０】本発明に従ってオブジェクトをロックした
りアンロックしたりするメソッドは、Ｊａｖａベースの
環境で実現されることが特に望ましいが、これらのメソ
ッドを任意の適当なオブジェクトベース環境に適用する
こともできる。特に、これらのメソッドは、プラットホ
ームに依存しないオブジェクトベース環境で好適に用い
られる。また、これらのメソッドを、分散オブジェクト
指向システムで実現することも可能である。

【０１１１】上述の実施例では、状態インジケータを、
オブジェクトがロック状態か、アンロック状態か、ある
いはビジーかを識別するビットとして説明した。状態イ
ンジケータに係わるビット数は、実施例では一ビットあ
るいは二ビットであったが、状態インジケータに係わる
ビット数を様々に変えることができる。更に、オブジェ
クトの状態を状態インジケータ以外の機構を用いて識別
するようにしてもよい。例えば、オブジェクトの状態を
識別するリストを示すポインタを、オブジェクトが備え
るようにしてもよい。

【０１１２】上述の実施例では、関連する仮想マシンを
備えるコンピュータシステムに本発明を適用したが、任
意の適当なオブジェクト指向コンピュータシステム上で
本発明を実現するようにしてもよい。特に、本発明に従
ってオブジェクトをロックしたりアンロックしたりする
メソッドを、本発明の要旨の範囲内で、任意のマルチス
レッド型オブジェクト指向システムで実現することが可
能である。上述の実施例は、本発明を説明するためのも
のであり、何ら限定するものではない。また、本発明
は、それらの詳細に限定されるものではなく、本発明の
クレームの範囲内で様々に変形可能である。

【図面の簡単な説明】

【図１】オブジェクトのロックを取得する処理を示すプ
ロセスフロー図。

【図２】スレッドと、呼び出されたオブジェクトと、同
期構造の集合体との間の関係を示す説明図。

【図３】本発明の一実施例として、協働スレッドスタッ
クとオブジェクトとを示す説明図。

【図４】本発明の一実施例として、オブジェクトのヘッ
ダ値をスタック上に入力した後の、図３の協働スレッド
スタックとオブジェクトとを示す説明図。

【図５】本発明の一実施例として、スレッドスタックに
関連付けられているスレッドによってオブジェクトを再
入力した後の、図４の協働スレッドスタックとオブジェ
クトとを示す説明図。

【図６】本発明の一実施例として、協働スレッドを用い
てオブジェクトのロックを取得する処理を示すプロセス
フロー図。

【図７】本発明の一実施例として、協働スレッドを用い
て一旦ロックしたオブジェクトをアンロックする処理を
示すプロセスフロー図。

【図８】本発明の一実施例として、並列スレッドに関連
付けられているスタックとオブジェクトとを示す説明
図。

【図９】本発明の一実施例として、ヘッダ値をスタック
上に入力した後の、図８のオブジェクトとスタックとを
示す説明図。

【図１０】本発明の一実施例として、オブジェクトヘッ
ダフィールド内にセンチネルを入力した後の、図９のオ
ブジェクトとスタックとを示す説明図。

【図１１】本発明の一実施例として、オブジェクトのロ
ックを獲得する処理を示すプロセスフロー図。

【図１２】本発明の一実施例として、オブジェクトのロ
ックを獲得する処理を示すプロセスフロー図。

【図１３】本発明の一実施例として、オブジェクトと待
機リストを含むスタックとを示す説明図。

【図１４】本発明の一実施例として、オブジェクトとの
インターフェースとして構成される、異なった優先度を
有するスレッドの集合を示す説明図。

【図１５】本発明の一実施例として、低い優先度のスレ
ッドがオブジェクトのヘッダ値を獲得した後の、図１４
のスレッド集合を示す説明図。

【図１６】本発明の一実施例として、中間の優先度のス
レッドがオブジェクトヘッダフィールドの内容とセンチ
ネルとを交換した後の図１５のスレッド集合を示す説明
図。

【図１７】本発明の一実施例として、高い優先度のスレ
ッドがオブジェクトヘッダフィールドの内容とセンチネ
ルとを交換した後の図１６のスレッド集合を示す説明
図。

【図１８】本発明の一実施例として、高い優先度のスレ
ッドが中間の優先度のスレッドおよび低い優先度のスレ
ッドに優先度を譲り渡した後の図１７のスレッド集合を
示す説明図。

【図１９】本発明の一実施例として、ロックされたオブ
ジェクトをアンロックする方法を示すプロセスフロー
図。

【図２０】本発明の一実施例として、ロックされたオブ
ジェクトをアンロックする別の方法を示すプロセスフロ
ー図。

【図２１】本発明の一実施例として、ロックされたオブ
ジェクトをアンロックする別の方法を示すプロセスフロ
ー図。

【図２２】本発明の一実施例として、スレッドを用いて
一旦優先度を引き上げられたスレッドの優先度を引き下
げる処理、即ち、図１１のステップ６０８の処理を示す
プロセスフロー図。

【図２３】本発明の実現に適した汎用コンピュータシス
テムを示す説明図。

【図２４】本発明の実現に適した仮想マシンを示す説明
図。

【符号の説明】

１０１２…通信ネットワーク １０３０…コンピュータシステム １０３２…ＣＰＵ（プロセッサ） １０３４…主記憶装置（ＲＡＭ） １０３６…主記憶装置（ＲＯＭ） １０３８…補助記憶装置（大容量記憶装置） １０４０…入出力装置 １１０５…コンパイル時環境 １１１０…ソースコード １１２０…コンパイラ １１３０…バイトコード １１３５…ランタイム環境 １１４０…仮想マシン １１４２…コンパイラ １１４４…インタプリタ １１４６…ランタイムシステム

───────────────────────────────────────────────────── フロントページの続き (71)出願人 591064003 901 ＳＡＮ ＡＮＴＯＮＩＯ ＲＯＡＤ ＰＡＬＯ ＡＬＴＯ，ＣＡ 94303，Ｕ. Ｓ．Ａ. (72)発明者 ティモシー・ジー．・リンドホルム アメリカ合衆国 カリフォルニア州94301 パロ・アルト，ミドルフィールド・ロー ド，623

Claims (25)

【特許請求の範囲】
1. 【請求項１】 第一のスレッドを用いてオブジェクトの
   ヘッダ値を獲得するための、コンピュータにより実現さ
   れる方法であって、 前記オブジェクトはオブジェクトヘッダを含み、前記第
   一のスレッドは、関連する実行スタックおよび第一スレ
   ッド実行優先度を有し、 前記方法は、 ａ）オブジェクトヘッダの内容を、前記スタックを識別
   するセンチネルで置き換える工程と、 ｂ）前記内容が前記オブジェクトのヘッダ値を含むかど
   うかを判定する工程と、 ｃ）前記内容が前記オブジェクトのヘッダ値を含まない
   と判定された場合、前記オブジェクトが第二のスレッド
   による調査中か否かを判定する工程と、を備える、コン
   ピュータにより実現される方法。
2. 【請求項２】 請求項１記載のコンピュータにより実現
   される方法であって、 前記オブジェクトが前記第二のスレッドによる調査中で
   はないと判定された場合には、更に、 前記スタックに関連付けられているリストに前記第一の
   スレッドを加えて、前記第一のスレッドが前記オブジェ
   クトへのアクセスの待機状態にあることを示すように前
   記リストを構成する工程と、 前記内容を前記オブジェクトヘッダに戻す工程と、を備
   える、コンピュータにより実現される方法。
3. 【請求項３】 請求項１または２記載のコンピュータに
   より実現される方法であって、更に、 前記第一のスレッドが前記オブジェクトにアクセスする
   ことの通知を受け取る工程と、 前記工程ａ）ないしｃ）を繰り返す工程と、 を備える、コンピュータにより実現される方法。
4. 【請求項４】 請求項１ないし３のいずれかに記載のコ
   ンピュータにより実現される方法であって、 前記オブジェクトが前記第二のスレッドによる調査中で
   あると判定された場合には、更に、 前記内容から前記第二のスレッドを識別する工程と、 前記第二のスレッドに関する第二スレッド実行優先度
   が、前記第一スレッド実行優先度よりも低いか否かを判
   定する工程と、を備える、コンピュータにより実現され
   る方法。
5. 【請求項５】 請求項４記載のコンピュータにより実現
   される方法であって、 前記第二スレッド実行優先度が前記第一スレッド実行優
   先度よりも低いと判定された場合には、更に、 前記第二スレッド実行優先度を前記第一スレッド実行優
   先度まで引き上げる工程と、 前記第二スレッド実行優先度が引き上げられたことを示
   すように、前記第二のスレッドに関するカウンタをイン
   クリメントする工程と、 前記第二のスレッドおよび前記カウンタを、前記第一の
   スレッドに関連付けられている優先度上昇スレッド列に
   加える工程と、 前記工程ａ）ないしｃ）を繰り返す工程と、を備える、
   コンピュータにより実現される方法。
6. 【請求項６】 請求項１ないし５のいずれかに記載のコ
   ンピュータにより実現される方法であって、 前記内容が前記ヘッダ値を含むと判定された場合には、
   更に、 前記内容を前記スタックの特定の位置に格納する工程
   と、 前記オブジェクトヘッダに、前記特定の位置を識別する
   ように構成されたポインタを格納する工程と、を備え
   る、コンピュータにより実現される方法。
7. 【請求項７】 請求項６記載のコンピュータにより実現
   される方法であって、更に、 前記第一スレッド実行優先度まで引き上げられていた前
   記第二のスレッドの第二スレッド実行優先度を引き下げ
   る工程、を備える、コンピュータにより実現される方
   法。
8. 【請求項８】 オブジェクトを第一のスレッドに関連付
   けるための、コンピュータにより実現される方法であっ
   て、 前記オブジェクトはオブジェクトヘッダフィールドを含
   み、前記第一のスレッドは、関連するスタックを有し、 前記方法は、 前記オブジェクトヘッダフィールドの内容を取得する工
   程と、 前記スタック内の第一の位置に前記オブジェクトヘッダ
   フィールドの内容を格納する工程と、 前記オブジェクトヘッダフィールドに、前記スタックを
   識別するように構成された参照インジケータを格納する
   工程と、を備える、コンピュータにより実現される方
   法。
9. 【請求項９】 請求項８記載のコンピュータにより実現
   される方法であって、更に、 前記オブジェクトヘッダフィールド内に前記参照インジ
   ケータが格納されていることを示すように、前記オブジ
   ェクトに関連付けられている状態インジケータを更新す
   る工程を備え、ここで、前記オブジェクトヘッダフィー
   ルドの前記内容はヘッダ値を含み、 前記状態インジケータを更新する工程は、前記オブジェ
   クトが前記第一のスレッドによりアクセス可能であるこ
   とを示すように前記状態インジケータを更新する工程を
   備える、コンピュータにより実現される方法。
10. 【請求項１０】 請求項８または９記載のコンピュータ
    により実現される方法であって、 前記参照インジケータは、前記スタック内の前記第一の
    位置を識別するように構成された進行ポインタである、
    コンピュータにより実現される方法。
11. 【請求項１１】 請求項８ないし１０のいずれかに記載
    のコンピュータにより実現される方法であって、 前記オブジェクトヘッダフィールドの前記内容の格納と
    前記参照インジケータの格納がほぼ同時に行われる、コ
    ンピュータにより実現される方法。
12. 【請求項１２】 複数のスレッドを含むメモリを備える
    コンピュータシステムであって、 前記複数のスレッドの各々が関連スタックを備え、 前記コンピュータシステムは、 前記メモリに接続されたプロセッサと、 オブジェクトヘッダフィールドを含むオブジェクトと、 前記複数のスレッドから選択された第一のスレッドに関
    連付けられている第一のスタック内の第一の位置に、前
    記オブジェクトヘッダフィールドの内容を格納するよう
    に構成された第一の機構と、 前記第一のスタックを識別するように構成された参照イ
    ンジケータを、前記オブジェクトヘッダフィールド内に
    格納するように構成された第二の機構と、を備えるコン
    ピュータシステム。
13. 【請求項１３】 請求項１２記載のコンピュータシステ
    ムであって、更に、 前記参照インジケータが前記オブジェクトヘッダフィー
    ルドに格納されていることを示すように、前記オブジェ
    クトに関連付けられている状態インジケータを更新する
    ように構成された更新部、を備えるコンピュータシステ
    ム。
14. 【請求項１４】 複数のスレッドを含むメモリを備える
    コンピュータシステムであって、 前記複数のスレッドの各々が関連スタックを備え、 前記コンピュータシステムは、 前記メモリに接続されたプロセッサと、 オブジェクトヘッダを含むオブジェクトと、を備え、 前記オブジェクトヘッダは、前記オブジェクトに関する
    情報を含むヘッダ値を含むように構成され、 前記複数のスレッドから選択された第一のスレッドが、
    前記ヘッダ値を取得するとともに、前記第一のスレッド
    に関連付けられているスタックを識別するように構成さ
    れた第一参照インジケータを前記オブジェクトヘッダ内
    に格納するように構成され、 前記複数のスレッドから選択された第二のスレッドが、
    前記オブジェクトヘッダから前記第一参照インジケータ
    を取得するとともに、前記第一参照インジケータを使用
    して、前記第二のスレッドが前記オブジェクトを利用可
    能でないことを判定するように構成されている、コンピ
    ュータシステム。
15. 【請求項１５】 請求項１４記載のコンピュータシステ
    ムであって、 前記オブジェクトは、前記第一参照インジケータが前記
    オブジェクトヘッダに格納されていることを示すように
    構成された状態インジケータを含む、コンピュータシス
    テム。
16. 【請求項１６】 請求項１５記載のコンピュータシステ
    ムであって、 前記第一のスレッドに関連付けられているスタックは、
    第一の位置に前記ヘッダ値を格納するように構成されて
    おり、 前記第一参照インジケータは、前記第一の位置を識別す
    るように構成されている、コンピュータシステム。
17. 【請求項１７】 請求項１５記載のコンピュータシステ
    ムであって、 前記第二のスレッドは、前記第二のスレッドに関連付け
    られているスタックを識別するように構成された第二参
    照インジケータを前記オブジェクトヘッダ内に格納する
    ように構成されており、 前記複数のスレッドから選択された第三のスレッドが、
    前記オブジェクトヘッダから前記第二参照インジケータ
    を取得するとともに、前記第三のスレッドに関連付けら
    れているスタックを識別するように構成された第三参照
    インジケータを前記オブジェクトヘッダ内に格納するよ
    うに構成されている、コンピュータシステム。
18. 【請求項１８】 第一のスレッドにオブジェクトを関連
    付けるためのコンピュータプログラム製品であって、 前記オブジェクトはオブジェクトヘッダを備え、前記第
    一のスレッドはコンピュータシステムに関連するメモリ
    に割り当てられた関連スタックを有し、 前記コンピュータプログラム製品は、 前記オブジェクトヘッダの内容を取得するコンピュータ
    コードと、 前記オブジェクトヘッダの前記内容を前記スタック内の
    第一の位置に格納するコンピュータコードと、 前記スタックを識別するように構成された参照インジケ
    ータを前記オブジェクトヘッダ内に格納するコンピュー
    タコードと、 前記オブジェクトヘッダの前記内容がヘッダ値を含まな
    いか否かを判定するコンピュータコードと、 前記オブジェクトヘッダの前記内容が前記ヘッダ値を含
    まない場合には、前記オブジェクトが第二のスレッドに
    より調査中であるか否かを判定するコンピュータコード
    と、 前記コンピュータコードを格納するコンピュータ読み取
    り可能な媒体と、を備える、コンピュータプログラム製
    品。
19. 【請求項１９】 請求項１８記載のコンピュータプログ
    ラム製品であって、 前記コンピュータ読み取り可能な媒体は、搬送波に乗せ
    られたデータ信号である、コンピュータプログラム製
    品。
20. 【請求項２０】 請求項１８または１９記載のコンピュ
    ータプログラム製品であって、更に、 前記参照インジケータが前記オブジェクトヘッダ内に格
    納されていることを示すように、前記オブジェクトに関
    連付けられている状態インジケータを更新するコンピュ
    ータコードを備える、コンピュータプログラム製品。
21. 【請求項２１】 オブジェクトベースのプログラムの制
    御下で動作するコンピュータにおいて、ヘッダを有する
    オブジェクト上での処理を制御する方法であって、 メモリ領域の一部が前記オブジェクトヘッダに関連付け
    られているようなメモリ領域内に、前記オブジェクトを
    確立する工程と、 第一のスレッドを用いて、前記オブジェクトヘッダに関
    連付けられている前記メモリ領域内に所定のパターンを
    格納することにより、前記オブジェクトをロックする工
    程と、 第二のスレッドを用いて、前記オブジェクトへのアクセ
    スを試みる工程と、 前記オブジェクトヘッダに関連付けられている前記メモ
    リ領域内における前記所定のパターンの存在に応じて、
    前記第二のスレッドによる前記オブジェクトへのアクセ
    スを少なくとも一時的に中断する工程と、を備える方
    法。
22. 【請求項２２】 請求項２１記載の方法であって、更
    に、前記オブジェクトヘッダを第二のメモリ位置に移動
    させる工程を備える、方法。
23. 【請求項２３】 請求項２１または２２記載の方法であ
    って、更に、 前記第一のスレッドに関連付けられているスタックに前
    記オブジェクトヘッダを移動させる工程を備える、方
    法。
24. 【請求項２４】 請求項２１ないし２３のいずれかに記
    載の方法であって、更に、前記オブジェクトヘッダを、
    前記第一のスレッドに関連付けられているスタック内の
    アドレスと交換する工程を備える、方法。
25. 【請求項２５】 請求項２１ないし２４のいずれかに記
    載の方法であって、 前記所定のパターンは、前記所定のパターンがオブジェ
    クトヘッダのパターンでは無いものとして一義的に識別
    するための少なくとも一つのビットを備える、方法。