(57)【要約】【課題】  不要な猶予時間トークン処理を回避する新しいリード・コピー・アップデート猶予時間検出技術を提供する。【解決手段】  共有データ要素への既存の参照が除去されるまで共有データ要素の除去を据え置くことが必要なリード・コピー・アップデート・サブシステム又は他の処理環境において、アトミック命令なしに猶予時間を検出するための方法、システム、及びコンピュータ・プログラム製品である。猶予時間の検出は、データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立することを含む。トークンが処理エンティティ間を周回するたびに、猶予時間が経過する。各々の処理エンティティと関連付けられた分散インジケータが、いずれかの共有データ要素に関する除去処理を行う必要があるかどうかを示す。分散インジケータは、各々の処理エンティティがトークン処理を行う前に、各々の処理エンティティにおいて処理される。トークン処理は、分散インジケータによって保証されたときだけ行われる。このようにして、分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することができる。【選択図】  図９
2008518337.tif 000002
【特許請求の範囲】
【請求項１】
共有データ要素への既存の参照が除去されるまで前記共有データ要素の除去を据え置くための猶予時間を検出する方法であって、
前記共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立するステップと、
前記トークンが前記処理エンティティ間を周回したときに、前記猶予時間が経過したと判断するステップと、
前記処理エンティティによって共有される前記共有データ要素又は他のデータ要素に関する除去処理を行う必要があるかどうかを示す分散インジケータを、前記処理エンティティの各々と関連付けるステップと、
前記処理エンティティにおいてトークン処理を行う前に、前記処理エンティティの各々において前記分散インジケータを処理するステップと、
前記分散インジケータによって保証されたときだけ、前記処理エンティティにおいてトークン処理を行うステップと、
を含み、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能な方法。
【請求項２】
前記分散インジケータの各々は、前記処理エンティティの１つと関連付けられたキャッシュ・メモリにローカル変数として格納される、請求項１に記載の方法。
【請求項３】
前記分散インジケータは、前記処理エンティティによって共有されるデータ要素を除去するための保留要求を有する前記処理エンティティの数、又は、前記処理エンティティによって共有されるデータ要素を除去するための保留要求の数を表す、請求項１に記載の方法。
【請求項４】
前記分散インジケータは、前記処理エンティティによって共有されるデータ要素を除去するための保留要求を有する前記処理エンティティを特定するビットマップを表す、請求項１、請求項２、又は請求項３に記載の方法。
【請求項５】
前記処理エンティティのうちの１つにおける前記分散インジケータの１つに生じた変化が、前記処理エンティティのうちの他の処理エンティティに伝搬される、請求項１〜４のいずれか１つの請求項に記載の方法。
【請求項６】
前記処理エンティティのうちの第１の処理エンティティにおける前記分散インジケータの１つの値が、前記処理エンティティのうちの前記第１の処理エンティティにおけるデータ要素除去要求行為を反映させるため必要に応じて調整される、前記処理エンティティの隣接する第２の処理エンティティにおける前記分散インジケータのうちの第２の分散インジケータの値を反映する、請求項１〜５のいずれか１つの請求項に記載の方法。
【請求項７】
前記分散インジケータの前記処理は、前記トークンの循環を保証するために前記処理エンティティのうちの１つにおいてしきい数の保留データ要素除去要求が存在するかどうかを判断すること、又は、前記処理エンティティのうちの１つにおいていずれかの保留データ要素除去要求が存在するかどうかを判断することを含む、請求項１〜６のいずれか１つの請求項に記載の方法。
【請求項８】
リード・コピー・アップデート相互排他技術の一部として実装され、前記共有データ要素の除去は、前記処理エンティティにおいてコールバックを登録することによって実行され、前記分散インジケータは、リード・コピー・アップデート・サブシステムにおけるコールバック行為を反映する分散コールバック・インジケータである、請求項１〜７のいずれか１つの請求項に記載の方法。
【請求項９】
１つ又は複数のプロセッサ、メモリ、及び、前記１つ又は複数のプロセッサと前記メモリとの間の通信経路を有し、前記プロセッサのうちの１つによる共有データ要素の除去を、前記プロセッサのうちの他のプロセッサによって維持される前記共有データ要素への既存の参照が除去されるまで据え置くための猶予時間を検出するように適合されたデータ処理システムであって、
前記プロセッサ間で循環されるトークンと、
前記トークンを循環させ、前記プロセッサ間を周回する前記トークンにより前記猶予時間が経過したかどうかを判断するように適合された、前記プロセッサの各々と関連付けられたトークン・マニピュレータと、
前記プロセッサによって共有される前記共有データ要素又は他のデータ要素に関する除去処理を行う必要があるかどうかを示す、前記プロセッサの各々と関連付けられた分散インジケータと、
前記トークン・マニピュレータによるトークン処理の前に前記分散インジケータを処理するように適合された、前記プロセッサの各々と関連付けられた分散インジケータ処理機構と、
前記分散インジケータによって保証されたときだけ、前記トークン・マニピュレータが前記プロセッサにおいてトークン処理を行うことができるようにさらに適合された、前記分散インジケータ処理機構と、
を備え、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能なデータ処理システム。
【請求項１０】
共有データ要素への既存の参照が除去されるまで前記共有データ要素の除去を据え置くための猶予時間を検出するコンピュータ・プログラム製品であって、
１つ又は複数のデータ記憶媒体と、
前記共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立すること、
前記トークンが前記処理エンティティ間を周回したときに、前記猶予時間が経過したと判断すること、
前記処理エンティティによって共有される前記共有データ要素又は他のデータ要素に関する除去処理を行う必要があるかどうかを示す分散インジケータを、前記処理エンティティの各々と関連付けること、
前記処理エンティティにおいてトークン処理を行う前に、前記処理エンティティの各々において前記分散インジケータを処理すること、及び、
前記分散インジケータによって保証されたときだけ、前記処理エンティティにおいてトークン処理を行うこと、
によって動作するようにデータ処理プラットフォームをプログラムするための、前記データ記憶媒体に記録される手段と、
を含み、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能なコンピュータ・プログラム製品。
【請求項３０】
前記プログラム手段は、リード・コピー・アップデート・サブシステムのコンピュータ・プログラム製品の一部として実装され、前記共有データ要素の除去は、前記処理エンティティにおいてコールバックを登録することによって実行され、前記分散インジケータは、前記リード・コピー・アップデート・サブシステムにおけるコールバック行為を反映する分散コールバック・インジケータである、請求項２１に記載のコンピュータ・プログラム製品。
【請求項１１】
保留コールバックをいつ実行することができるかを判断するために、リード・コピー・アップデート・サブシステムにおいて猶予時間を検出する方法であって、
データ要素へのアクセスを共有するプロセッサの組の各々に静止状態カウンタを実装するステップと、
前記静止状態カウンタによって維持されるカウント値の不連続として猶予時間トークンを確立するステップと、
前記トークンが前記プロセッサの組の間を周回して前記プロセッサの１つに戻ったときに、前記プロセッサの前記１つにおいて前記猶予時間が経過したと判断するステップと、
前記コールバックを処理する必要があるかどうかを示す分散コールバック・インジケータを、前記プロセッサの各々と関連付けられたキャッシュ・メモリ内のローカル変数として関連付けるステップと、
前記プロセッサにおいてトークン処理を行う前に、前記プロセッサの各々において前記分散コールバック・インジケータを処理するステップと、
前記分散コールバック・インジケータによって保証されたときだけ、前記プロセッサにおいてトークン処理を行うステップと、
を含み、
前記分散コールバック・インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能な方法。
【請求項１２】
１つ又は複数のプロセッサ、メモリ、及び、前記１つ又は複数のプロセッサと前記メモリとの間の通信経路を有し、保留コールバックをいつ実行することができるかを判断するために猶予時間を検出するように適合されたリード・コピー・アップデート・サブシステムを含むデータ処理システムであって、
【請求項１３】
共有データ要素への既存の参照が除去されるまで前記共有データ要素の除去を据え置くための猶予時間を検出する方法であって、
前記共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立するステップと、
前記トークンが前記処理エンティティ間を周回したときに、前記猶予時間が経過したと判断するステップと、
前記処理エンティティによって共有されるデータ要素を除去するための保留要求を有する前記処理エンティティの数を表す分散インジケータを、前記処理エンティティの各々と関連付けるステップと、
前記処理エンティティにおいてトークン処理を行う前に、前記処理エンティティの各々において前記分散インジケータを処理するステップであって、前記処理は、前記処理エンティティの隣接する１つにおける前記分散インジケータの値に従って前記分散インジケータを修正することを含み、前記分散インジケータの修正は、（１）現在の猶予時間と関連付けられた除去要求が存在し、前の猶予時間と関連付けられた除去要求が存在しないかどうかに応じて行われ、この場合には前記分散インジケータを増加させ、（２）現在の猶予時間と関連付けられた除去要求が存在せず、前の猶予時間と関連付けられた除去要求が存在したかどうかに応じて行われ、この場合には前記分散インジケータを減少させ、又は、（３）現在の猶予時間と前の猶予時間の両方について除去要求が存在するかどうか、若しくは、現在の猶予時間と前の猶予時間の両方について除去要求が存在しないかどうかに応じて行われ、この場合には前記分散インジケータは同じままである、ステップと、
前記分散インジケータによって保証されたときだけ、前記処理エンティティにおいてトークン処理を行うステップと、
を含み、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能な方法。
【請求項１４】
共有データ要素への既存の参照が除去されるまで前記共有データ要素の除去を据え置くための猶予時間を検出する方法であって、
前記共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立するステップと、
前記トークンが前記処理エンティティ間を周回したときに、前記猶予時間が経過したと判断するステップと、
前記処理エンティティによって共有されるデータ要素を除去するための保留要求の総数を表す分散インジケータを、前記処理エンティティの各々と関連付けるステップと、
前記処理エンティティにおいてトークン処理を行う前に、前記処理エンティティの各々において前記分散インジケータを処理するステップであって、前記処理は、前記処理エンティティの隣接する１つにおける前記分散インジケータの値に従って前記分散インジケータを修正することを含み、前記値の修正は、現在の猶予時間の間に追加された除去要求の数と以前の猶予時間の間に処理された除去要求の数との間の差に応じて行われる、ステップと、
前記分散インジケータによって保証されたときだけ、前記処理エンティティにおいてトークン処理を行うステップと、
を含み、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能な方法。
【請求項１５】
共有データ要素への既存の参照が除去されるまで前記共有データ要素の除去を据え置くための猶予時間を検出する方法であって、
前記共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立するステップと、
前記トークンが前記処理エンティティ間を周回したときに、前記猶予時間が経過したと判断するステップと、
前記処理エンティティによって共有されるデータ要素を除去するための保留要求を有する前記処理エンティティのビットマップを表す分散インジケータを、前記処理エンティティの各々と関連付けるステップと、
前記処理エンティティにおいてトークン処理を行う前に、前記処理エンティティの各々において前記分散インジケータを処理するステップであって、前記処理は、前記処理エンティティの隣接する１つにおける前記分散インジケータの値に従って前記分散インジケータを修正することと、（１）現在の猶予時間と関連付けられた除去要求が存在するかどうかに応じて、評価している処理エンティティに対応するビットを１に設定するか、又は、（２）現在の猶予時間と関連付けられた除去要求が存在しないかどうかに応じて、評価している処理エンティティに対応するビットを０に設定することとを含む、ステップと、
前記分散インジケータによって保証されたときだけ、前記処理エンティティにおいてトークン処理を行うステップと、
を含み、
前記分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することが可能な方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各々の利用者に対するデータ保全性（integrity）及びデータ整合性（consistency）を保持しながら、同時データ利用者間でデータ・リソースが共有されるコンピュータ・システム及び方法に関する。より具体的には、本発明は、ロック・フリーのデータ読み取り動作がデータ更新動作と同時に実行される「リード・コピー・アップデート（read copy update）」として知られる相互排他機構の改善に関する。
【背景技術】
【０００２】
背景として、リード・コピー・アップデートは、同時にデータを更新（修正、削除、挿入など）できるようにしながら、ロック、共有メモリへの書き込み、メモリ・バリア、アトミック命令、又はコンピュータ的に高価な他の同期機構を使用しない読み取りのために、共有データにアクセスできるようにする相互排他技術である。この技術は、共有データ・セットにアクセスする読み取り動作（リーダ）の数が更新動作（アップデータ（updater））の数と比べて大きく、読み取り動作毎に（ロックなどの）他の相互排他技術を使用することに関するオーバーヘッド・コストが高くなる、マルチプロセッサ・コンピュータ環境に適している。例として、多くても数分に１回更新されるが、１秒当たり数千回も検索されるネットワーク・ルーティング・テーブルが、読み取り側のロック取得がかなり負担になるケースである。
【０００３】
リード・コピー・アップデート技術は、データ更新を２つのフェーズで実行する。第１の（初期更新）フェーズにおいては、実際のデータ更新は、更新されているデータの２つのビューを一時的に保持するように行われる。一方のビューは、データを現在参照している可能性のある動作に役立つように維持される古い（更新前）データ状態である。他方のビューは、更新後にデータにアクセスする動作に役立つようにするための利用可能な新しい（更新後）データ状態である。第２の（据え置き更新（deferred update））フェーズにおいては、古いデータ状態は、全ての実行動作がもはや更新前のデータへの参照を維持しないことが確実となる十分な長さの「猶予時間（grace period）」後に、削除される。
【０００４】
図１〜図４は、リード・コピー・アップデートを用いて、データ要素Ａ、Ｂ、及びＣのグループにおけるデータ要素Ｂを修正することを示す。データ要素Ａ、Ｂ、及びＣは、非巡回式（acyclic fashion）にトラバース（traverse）される単方向リンク・リスト（singly-linked list）として並べられ、各々の要素は、データの幾つかの項目を格納することに加えて、リスト内の次の要素へのポインタ（又は、最後の要素についてはＮＵＬＬポインタ）を含む。グローバル・ポインタ（図示せず）が、リストの最初のメンバであるデータ要素Ａをポイントすると仮定する。当業者であれば、Ｃ言語の「ｓｔｒｕｃｔ」変数によって定められるデータ構造を含むがこれに限定されるものではない、様々な従来のプログラミング構造体のいずれかを用いて、データ要素Ａ、Ｂ、及びＣを実装できることが分かるであろう。
【０００５】
図１〜図４のデータ要素のリストは、多数の同時リーダによって（ロックすることなく）トラバースされ、場合によっては、リスト内のデータ要素を削除し、挿入し、又は修正するアップデータによって更新されるものとする。図１においては、データ要素Ｂは、データ要素の下の垂直矢印によって示されるように、リーダｒ１によって参照されている。図２においては、アップデータｕ１が、データ要素Ｂを修正することによってリンク・リストを更新しようとしている。ｒ１がこのデータ要素を参照していることを考慮することなくこのデータ要素を単純に更新する（これは、ｒ１をクラッシュする可能性がある）代わりに、ｕ１は、Ｂを保持すると同時にその更新されたバージョン（図３においてデータ要素Ｂ´として示される）を生成し、それをリンク・リストに挿入する。これは、ｕ１が、スピンロックを取得し、新しいメモリをＢ´に割り当て、ＢのコンテンツをＢ´にコピーし、必要に応じてＢ´を修正し、Ｂ´をポイントするようにポインタをＡからＢ´に更新し、スピンロックを解除することによって行われる。したがって、リンク・リストをトラバースするリーダｒ２などの全ての後続の（更新後の）リーダは、Ｂ´に遭遇することによって更新動作の影響を認識することになる。一方、古いリーダｒ１は、Ｂの元のバージョンとそのＣへのポインタとが保持されているため、影響を受けないことになる。ここではｒ１が失効データ（stale data）を読み込んでいることになるが、データ要素が、コンピュータ・システムの外部にあるコンポーネントの状態（例えば、ネットワーク接続性）を追跡し、通信遅延のために古いデータを許容しなければならないときなど、これを許容せざるを得ない場合が多く存在する。
【０００６】
更新後のある時点において、ｒ１は、リンク・リストのトラバースを継続しており、その参照をＢから移動させている。さらに、他のリーダ・プロセスがＢにアクセスする権利が与えられない時間が存在する。図４に示されるように、ｕ１がＢを解放することができるのは、上述の猶予時間の満了を表すこの時点である。
【０００７】
図５〜図７は、リード・コピー・アップデートを用いて、データ要素Ａ、Ｂ、及びＣの単方向リンク・リストのうちのデータ要素Ｂを削除することを示す。図５に示されるように、リーダｒ１が、現時点でＢを参照していると仮定され、アップデータｕ１が、Ｂを削除しようとしている。図６に示されるように、アップデータｕ１は、ここではＡがＣをポイントするように、ポインタをＡからＣに更新する。このように、ｒ１は妨害されないが、後続のリーダｒ２は、削除の影響を認識する。図７に示されるように、ｒ１は、その後その参照をＢから移動させ、猶予時間の満了後にＢを解放することが可能になる。
【０００８】
リード・コピー・アップデート機構のコンテクストにおいては、猶予時間は、リード・コピー・アップデートによって保護されるデータ要素にアクセスできる実行中の全てのプロセスが、もはやデータ要素への参照を維持することも、データ要素のロックをアサートすることも、データ要素の状態について何らかの推測を行うこともできない「静止状態（quiescent state）」を経た時点を表す。従来、オペレーティング・システムのカーネル・コード・パスについて、コンテクスト（プロセス）スイッチ、アイドル・ループ、及びユーザ・モード実行の全てが、いずれかの所与のＣＰＵについての静止状態を表す（ここで挙げられていない他の動作も可能である）。
【０００９】
図８においては、４つの別個のＣＰＵで実行される４つのプロセス０、１、２、及び３が、（垂直の二重バーによって表される）静止状態を定期的に経ることが示されている。（垂直の点線線によって示される）猶予時間は、４つのプロセス全てが１つの静止状態を経た時間フレームを含む。４つのプロセス０、１、２、及び３が、図１〜図４又は図５〜図７のリンク・リストをトラバースするリーダ・プロセスである場合には、猶予時間前に古いデータ要素Ｂを参照するこれらのプロセスのいずれも、猶予時間後には古いデータ要素Ｂへの参照を維持することができない。これらのプロセスによって行われる猶予時間後の全ての検索が、アップデータによって挿入されるリンクを辿ることによってＢを迂回する。
【００１０】
発明の名称を「Apparatus And Method For Achieving ReducedOverhead Mutual-Exclusion And Maintaining Coherency In A Multiprocessor System UtilizingExecution History And Thread Monitoring」とする、同一出願人による特許文献１に記載されるコールバック処理の使用を含むがこれに限定されるものではない、猶予時間後の据え置きデータ更新を実行するのに用いることができる様々な方法が存在する。特許文献１の内容は、引用により本明細書に組み込まれる。
【００１１】
コールバック処理技術は、共有データ要素のアップデータが、更新されているデータの新しいビューを作成する初期（第１のフェーズ）データ更新動作を行い、次いで、更新されているデータの古いビューを除去する据え置き（第２のフェーズ）データ更新動作を行うためのコールバック機能を指定するものである。アップデータは、猶予時間の最後にコールバック機能（これ以降、「コールバック」と呼ぶ）を実行できるように、コールバックをリード・コピー・アップデート・サブシステムに登録する。リード・コピー・アップデート・サブシステムは、プロセッサ毎に保留コールバック（pending callback）を追跡し、各々のプロセッサの現在の猶予時間がいつ終了したかを検出するためにプロセッサ毎の静止状態の行為（activity）を監視する。各々の猶予時間が終了するときに、処理の準備が整った全ての予定コールバックが実行される。
【００１２】
リード・コピー・アップデートの実行を成功させるためには、猶予時間の長さを推定するための効率的な機構が必要である。１つの重要な実行のクラスは、猶予時間トークンを１つのプロセッサから次のプロセッサに渡して、そのトークンを所有するプロセッサについて猶予時間の最後に到達したことを示す。猶予時間トークンは、プロセッサ間で明示的に渡される識別値とすることができる。しかしながら、この技術を用いるときは、２つのメモリ書き込みアクセス、すなわち、１つはトークンをその現在のオーナーから除去することであり、もう１つはそのトークンを新しいオーナーに渡すことが必要である。猶予時間トークンを処理するより効率的な方法が、プロセッサ毎の静止状態カウンタと、それに関連するポーリング機構とを用いて、猶予時間トークンを黙示的に（implicitly）渡すことである。この技術によれば、プロセッサが静止状態を経るたびに、そのポーリング機構は、隣接するプロセッサのカウンタが現在のプロセッサの最後の猶予時間以降に変化したどうかを確認するために、隣接するプロセッサの静止状態カウンタを検査する。それが変化した場合には、現在のプロセッサは、最後にトークンを持ったとき以降に、新しい猶予時間が経過したと判断する。現在のプロセッサは、その保留コールバックを実行し、次いで、その静止状態カウンタを、隣接するプロセッサのカウンタより高い値に変更する。次いで、次のプロセッサは、このプロセッサの変更されたカウンタ値を確認し、その保留コールバックを処理し、自分自身のカウンタを増加させる。このシーケンスは継続し、猶予時間トークンは最終的に、ラウンドロビン方式でプロセッサの全てを通って進む。
【００１３】
猶予時間トークンがどのように実装されるかに関わらず、各々のプロセッサは、トークンを受け取ったときだけコールバックを処理する。猶予時間トークンが、現在の所有者であるプロセッサに到達する前に他の全てのプロセッサの間を移動しなければならない限り、現在のプロセッサは、常に、現在のプロセッサが最後にトークンを所有して以降に他のプロセッサが静止状態を経たことが保証され、したがって猶予時間が経過したことが確実となる。
【００１４】
トークン操作を用いる猶予時間検出は、プロセッサが静止状態を経るときにプロセッサ・サイクルを消費するため、リード・コピー・アップデート・サブシステムに保留コールバックが存在しない場合には、こうしたオーバーヘッドが発生することは望ましくない。そのため、効率的なトークンベースのリード・コピー・アップデート実装は、猶予時間トークンの処理の前にテストされる共有インジケータ（すなわち、グローバル変数）を用いて、リード・コピー・アップデート・サブシステムがアイドル状態であるかどうかを判断する。それがアイドル状態である場合には、猶予時間トークンを渡す必要がなく、関連する処理オーバーヘッドを回避することができる。共有インジケータは、典型的には、保留コールバック数のカウントである。コールバックが所与のプロセッサにおいて登録されるたびに、共有インジケータは、新しいコールバックを反映するように操作される。その後、そのコールバックが処理されるときに、共有インジケータは、リード・コピー・アップデート・サブシステムからのコールバックの除去を反映するように再度操作される。
【００１５】
【特許文献１】米国特許第５，７２７，２０９号
【非特許文献１】"Read Copy Update",Ottawa Linux Symposium(2002)
【発明の開示】
【発明が解決しようとする課題】
【００１６】
保留コールバックの存在についてテストするために共有インジケータを用いることについての欠点は、多数のプロセッサによるインジケータに関する動作を同期させるために、共有インジケータが操作されるたびにアトミック命令、ロック、又は、他の比較的高価な相互排他機構を呼び出さなければならないことである。さらに、各々のプロセッサによる、共有インジケータの従来のハードウェア・キャッシングは、通信キャッシュ・ミス及びキャッシュ・ライン・バウンシングをもたらす傾向がある。ビットマップ・インジケータの場合には、さらなる欠点は、多数のプロセッサが正常に適応できないことである。
【００１７】
本発明は、上述の問題を解決することに向けられている。特に、必要とされているのは、保留コールバック状態の共有インジケータに関するオーバーヘッドが発生することなく、不要な猶予時間トークン処理を回避する新しいリード・コピー・アップデート猶予時間検出技術である。
【課題を解決するための手段】
【００１８】
共有データ要素への既存の参照が除去されるまで該共有データ要素の除去を据え置くことが必要なリード・コピー・アップデート・サブシステム又は他の処理環境において、アトミック命令なしに猶予時間を検出するための方法、システム、及びコンピュータ・プログラム製品によって、上述の問題が解決され、当該技術分野が進歩する。猶予時間検出は、共有データ要素へのアクセスを共有する処理エンティティ間で循環されるトークンを確立することを含む。トークンが処理エンティティ間を周回するたびに、猶予時間が経過したと判断することができる。データ要素又は処理エンティティによって共有される他のデータ要素に関する除去処理を行う必要があるかどうか（例えば、本発明がコールバックベースのリード・コピー・アップデート・システムに実装される場合には、コールバック処理を保証する保留コールバックが存在するかどうか）を示す分散インジケータ（distributed indicator）が、処理エンティティの各々と関連付けられる。分散インジケータは、処理エンティティにおいてトークン処理が行われる前に、処理エンティティの各々において処理される。トークン処理は、分散インジケータによって保証されたときだけ、処理エンティティにおいて行われる。このようにして、分散インジケータがこうした処理を保証しないときは、不要なトークン処理を回避することができる。
【００１９】
本発明の例示的な実施形態においては、分散インジケータは、処理エンティティと関連付けられたキャッシュ・メモリにローカル変数として格納される（そして、一連の処理の間に、従来のキャッシュ・コヒーレンス機構を介して１つのキャッシュ・メモリから別のキャッシュ・メモリに複製される）。こうした実施形態においては、分散インジケータは、設計の初期設定に応じて、異なる種類の情報を表すことができる。例えば、分散インジケータは、代替的に、処理エンティティによって共有されるデータ要素の更新を行う保留要求を有する処理エンティティの数、更新の総数、又は、保留更新要求（pending update requests）を有する処理エンティティを特定するビットマップ、を表すことができる。
【００２０】
種々の処理エンティティによって分散インジケータに生じた変化の伝搬もまた、設計の初期設定に応じて異なる方法で行うことができる。例示的な実施形態においては、処理エンティティは、隣接する処理エンティティによって維持される分散インジケータを定期的に調べ、現在の処理エンティティにおけるデータ要素除去要求行為（data element removal request activity）（例えば、コールバック登録）の変化を反映させるため必要に応じてインジケータを調整する。データ要素除去要求行為の変化があったかどうかは、トークンの循環を保証するために、処理エンティティのうちの１つにおいてしきい数の保留データ要素除去要求が存在するかどうかなどといった種々の要因の判断を含むことができる。代替的に、こうした判断は、処理エンティティの１つにおいていずれかの保留データ要素除去要求が存在するかどうかに基づくものとすることができる。
【発明を実施するための最良の形態】
【００２１】
本発明の上述の及び他の特徴及び利点は、添付図面に示されるように、本発明の例示的な実施形態に関する以下のより具体的な説明から明らかとなるであろう。
【００２２】
ここで、同じ参照数字が幾つかの図面の全てにおいて同じの要素を表す図を参照すると、図９は、本発明を実装することができる例示的なコンピュータ環境を示す。具体的には、多数のプロセッサ４１、４２・・・４ｎが共通バス６によって共有メモリ８に接続される、対称型マルチプロセッサ（ＳＭＰ；symmetrical multiprocessor）コンピュータ・システム２が示される。各々のプロセッサ４１、４２・・・４ｎとそれぞれ関連付けられるのが、従来型のキャッシュ・メモリ１０１、１０２・・・１０ｎ及びキャッシュ・コントローラ１２１、１２２・・・１２ｎである。従来型のメモリ・コントローラ１４が、共有メモリ８と関連付けられる。コンピュータ・システム２は、ＳＭＰ環境において用いられるのに適した単一のマルチタスク・オペレーティング・システムの管理下にあると仮定する。
【００２３】
さらに、カーネル若しくはユーザ・モード・プロセス、スレッド、又は他の実行コンテクスト内で実行される更新動作が、共有メモリ８に格納される共有データ・セット１６の更新を定期的に行うと仮定する。参照数字１８１、１８２・・・１８ｎは、幾つかのプロセッサ４１、４２・・・４ｎ上で定期的に実行することができる個々のデータ更新動作（アップデータ）を示す。上の背景によって説明されたように、データ・アップデータ１８１、１８２・・・１８ｎによって行われる更新は、リンク・リストの要素を修正すること、新しい要素をリストに挿入すること、要素をリストから削除すること、及び他の多くのタイプの動作を含むことができる。こうした更新を容易にするために、幾つかのプロセッサ４１、４２・・・４ｎは、それらのオペレーティング・システム機能の一部としてそれぞれのリード・コピー・アップデート・インスタンス２０１、２０２・・・２０ｎを定期的に実行することなどによって、リード・コピー・アップデート（ＲＣＵ）サブシステム２０を実行するようにプログラムされる。図面には示されていないが、プロセッサ４１、４２・・・４ｎも共有データ・セット１６上で読み取り動作を実行することが分かるであろう。こうした読み取り動作は、典型的には、これがリード・コピー・アップデートの使用の基礎となる前提の１つである限り、更新よりはるかに頻繁に行われることになる。
【００２４】
図１０において示されるように、リード・コピー・アップデート・サブシステム・インスタンス２０１、２０２・・・２０ｎの各々は、コールバック登録コンポーネント２２を含む。コールバック登録コンポーネント２２は、アップデータ自体によって行われる初期（第１のフェーズ）更新後の据え置き（第２のフェーズ）データ要素更新についての要求を登録するためにアップデータ１８２・・・１８ｎによって呼び出すことができる、リード・コピー・アップデート・サブシステム２０へのＡＰＩ（アプリケーション・プログラミング・インタフェース）として機能する。当該技術分野において知られているように、これらの据え置き更新要求は、失効したデータ要素の除去を含み、リード・コピー・アップデート・サブシステム２０内でコールバックとして扱われることになる。リード・コピー・アップデート・サブシステム・インスタンス２０１、２０２・・・２０ｎの各々は、さらに、コールバック処理システム２６と共に、静止状態カウンタ操作及びポーリング機構２４（又は、トークンを渡すための他の機能）を含む。機能２４及び２６は、従来のように、カーネル・スケジューラの一部として実装できることに留意されたい。
【００２５】
プロセッサ４１、４２・・・４ｎと関連付けられたキャッシュ・メモリ１０１、１０２・・・１０ｎは、それぞれ、静止状態カウンタ２８１、２８２・・・２８ｎと、１つ又は複数のコールバック・キュー３０１、３０２・・・３０ｎを格納する。静止状態カウンタ２８１、２８２・・・２８ｎは、プロセッサ４１、４２・・・４ｎ間で猶予時間トークンを渡すために、カウンタ操作及びポーリング機構２４（トークン・マニピュレータ）によって管理される。他のいくつかの形式のトークン渡し（token passing）を用いる場合には、静止状態カウンタ２８１、２８２・・・２８ｎを必要としないことが分かるであろう。コールバック・キュー３０１、３０２・・・３０ｎには、新しいコールバックがコールバック登録コンポーネント２２によって登録されるときに、こうしたコールバックが追加される（又は、先頭に加えられる）。コールバック処理システム２６は、コールバック・キュー３０１、３０２・・・３０ｎ上で参照されるコールバックを実行し、次いでコールバックが処理されたときにそれらを除去する役割を果たす。
【００２６】
図１２及び図１３は、静止状態カウンタ２８１、２８２・・・２８ｎをどのように用いて、プロセッサが静止状態を経るときに例示的な４プロセッサ・システムにおけるプロセッサ間で猶予時間トークンを渡すことができるかを示す。図１２における各々の列は、所与の時点における全てのプロセッサの静止状態カウンタの例示的な値を示す。網掛けしたセルは、対応するプロセッサが猶予時間トークンのオーナーであることを示す。いずれの場合においても、オーナーは、カウンタが最小値を有し、かつ、隣接するプロセッサがトークンのオーナーのカウンタ値に対して不連続なカウンタ値を有する、プロセッサである。
【００２７】
図１２及び図１３によって表されるトークン渡し技術は、当該技術分野において知られており、したがって、これらの図は「従来技術」と表記されている。上の背景によって説明されたように、所与のプロセッサは、隣接するプロセッサ（例えば、プロセッサ数を法（％）として、プロセッサ番号が現在のプロセッサより１大きいプロセッサ）の１つによって維持される静止状態カウンタを参照することによって、猶予時間トークンを所有するかどうかを確認する。隣接するプロセッサの静止状態カウンタが、現在のプロセッサの最後の猶予時間以降に変化していない（すなわち、カウンタ値の不連続が存在しない）場合には、現在のプロセッサは、新しい猶予時間がまだ経過していないと判断し、通常の処理を再開する。隣接するプロセッサのカウンタが、現在のプロセッサの最後の猶予時間以降に変化した（すなわち、カウンタ値の不連続が存在する）場合には、現在のプロセッサは、新しい猶予時間が経過したと判断する。現在のプロセッサは、その保留コールバックを処理し、自分自身の静止状態カウンタを隣接するプロセッサのカウンタの値より１大きい値に増加させ、これにより、カウンタ値の不連続を自分自身に移動させる。例として、図１２の時間ｔ＝０においては、最小の静止状態カウンタ値（１）を有するプロセッサ３は、プロセッサ０における不連続のカウンタ値（４）を確認する。これは、プロセッサ３の最後の猶予時間以降にそのピア・プロセッサが経た静止状態が３（４−１）回存在したことを、プロセッサ３に対して示す。プロセッサ３は、このようにして、新しい猶予時間が経過し、かつ、現時点でプロセッサ３が猶予時間トークンを持っていると判断する。プロセッサ３は、コールバック処理を行い、その静止状態カウンタ値を４＋１＝５に設定する。時間ｔ＝１においては、静止状態カウンタ値２を有するプロセッサ２が、プロセッサ３における不連続のカウンタ値５を確認する。プロセッサ２は、猶予時間トークンを持っていると判断し、コールバック処理を行い、そのカウンタ値を５＋１＝６に設定する。このシーケンスを続けると、プロセッサ１は、時間ｔ＝２において猶予時間トークンを取得し、プロセッサ０は、時間ｔ＝３においてトークンを取得する。時間ｔ＝４において、トークンはプロセッサ３に戻り、このパターンが繰り返される。図１３においてさらに示されるように、プロセッサ３は、時間ｔ＝０、４、及び８においてトークン（Ｔ）を取得し、プロセッサ２は、時間ｔ＝１及び５においてトークンを取得し、プロセッサ１は、時間ｔ＝２及び６においてトークンを取得し、プロセッサ０は、時間ｔ＝３及び７においてトークンを取得することになる。
【００２８】
上の背景でも説明されたように、従来技術におけるリード・コピー・アップデート実装は、リード・コピー・アップデート・サブシステムにおいて処理を必要とする保留コールバックが存在するかどうかに関する共有インジケータとして機能するグローバル変数を操作することによって、不要なトークン処理を回避しようとするものである。例えば、Ｐ．ＭｃＫｅｎｎｅｙ他の非特許文献１において開示されるように、「ｒｃｕ−ｓｃｈｅｄ」として知られているリード・コピー・アップデートのＬｉｎｕｘ実装は、リード・コピー・アップデート・サブシステムにおける保留コールバック数のカウントを表す共有変数「ｒｃｕ＿ｐｅｎｄｉｎｇ」を用いる。関数呼び出し「ａｔｏｍｉｃ＿ｉｎｃ（＆ｒｃｕ＿ｐｅｎｄｉｎｇ）」によって、新しいコールバックが登録されたときにＬｉｎｕｘアトミック・インクリメント・プリミティブ「ａｔｏｍｉｃ＿ｉｎｃ」を呼び出してｒｃｕ＿ｐｅｎｄｉｎｇを増加させる。次いで、関数呼び出し「ａｔｏｍｉｃ＿ｄｅｃ（＆ｒｃｕ＿ｐｅｎｄｉｎｇ）」によって、コールバックが処理された後にＬｉｎｕｘアトミック・デクリメント・プリミティブ「ａｔｏｍｉｃ＿ｄｅｃ」を呼び出してｒｃｕ＿ｐｅｎｄｉｎｇを減少させる。「ｒｃｕ−ｓｃｈｅｄ」は、図１２及び図１３に示されるように、カウンタベースの猶予時間トークン渡しスキームを用いるリード・コピー・アップデート実装の一例であることも指摘されるべきである。
【００２９】
保留コールバックに関する共有インジケータを増加又は減少させるアトミック動作（又は、他の同時制御機構）の使用に関する欠点を回避するために、本発明は、代替的な手法を提案する。図１１において示されるように、分散コールバック・インジケータ３２を、プロセッサ４１、４２・・・４ｎの各々のキャッシュ・メモリ１０に維持し、リード・コピー・アップデート・サブシステム２０の変化を反映するローカル変数として操作することができる。各々の分散コールバック・インジケータ３２は、リード・コピー・アップデート・サブシステム２０の状態を表す。次いで、リード・コピー・アップデート・サブシステム・インスタンス２０１、２０２・・・２０ｎの各々の中の関連するコールバック・インジケータ処理機構３４（図１０においても示される）は、ローカルの分散コールバック・インジケータ３２を調べて、猶予時間トークン処理が必要であるかどうかを判断することができる。ローカルの分散コールバック・インジケータ３２が、リード・コピー・アップデート・サブシステムがアイドル状態であることを示す場合には、トークンを渡す必要はない。一方、ローカルの分散コールバック・インジケータ３２は、リード・コピー・アップデート・サブシステムにおいて保留コールバックが存在し、現在のプロセッサにおいて猶予時間トークン処理が必要であることを示すことができる。
【００３０】
リード・コピー・アップデート・サブシステム２０内において条件が変わるときに、分散コールバック・インジケータ３２を現在のままに保つために、図１２及び図１３の猶予時間トークン渡しスキームに若干類似する伝播技術を用いることができる。他の実装形態も可能である。この伝搬技術によれば、プロセッサ４１、４２・・・４ｎの各々が静止状態を経るときに、そのコールバック・インジケータ処理機構３４は、隣接するプロセッサの分散コールバック・インジケータ３２を調べ、現在のプロセッサの最後の猶予時間以降のローカル・コールバック履歴を考慮すると共に、隣接するプロセッサの値に応じて自分自身のローカル・コールバック・インジケータを調整する。
【００３１】
本発明の一実施形態においては、分散コールバック・インジケータ３２は、保留コールバックを有するプロセッサの数に関するプロセッサ毎のカウンタとして実装される。これらのプロセッサは、「コールバック・プロセッサ」と呼ぶことができ、分散コールバック・インジケータ３２は、コールバック・プロセッサ・カウンタと考えることができる。このカウンタを操作するために、プロセッサは、このプロセッサの最後の猶予時間以降にそのローカル・コールバック状態に何らかの変化が存在したかどうかを確認する。変化が生じなかった場合には、現在のプロセッサのカウンタは、隣接するプロセッサのカウンタと同じ値に設定される。プロセッサのコールバック履歴が、猶予時間トークンが最後にこのプロセッサを離れたときにはローカル・コールバックが登録されていなかったが、最後の猶予時間以降に必要な数の新しいローカル・コールバックが登録されたことを示す場合には、現在のプロセッサのカウンタは、隣接するプロセッサのカウンタの値より１大きい値に増加させられることになる。プロセッサのコールバック履歴が、猶予時間トークンが最後にこのプロセッサを離れたときにローカル・コールバックが登録されていたが、最後の猶予時間以降に必要な数の新しいローカル・コールバックが登録されなかったことを示す場合には、現在のプロセッサのカウンタは、隣接するプロセッサのカウンタの値より１小さい値になるように減少させられることになる。
【００３２】
本発明の第２の実施形態においては、保留コールバックの総数の表示を追跡するために、分散コールバック・インジケータ３２が実装される。この場合において、分散コールバック・インジケータ３２は、コールバック・カウンタと考えることができる。このカウンタを操作するために、プロセッサは、このプロセッサの最後の猶予時間以降に登録されたローカル・コールバックの数を、猶予時間トークンが最後にプロセッサを離れたときに登録されていたローカル・コールバックの数と比較する。現在のプロセッサのカウンタは、ローカル・コールバックの純増又は純減を反映するように調整した隣接するプロセッサのカウンタ値に設定される。
【００３３】
本発明の第３の実施形態においては、分散コールバック・インジケータ３２は、保留コールバックを有するプロセッサを特定するビットマップとして実装される。ビットマップを操作するために、プロセッサは、猶予時間トークンが最後にこのプロセッサを離れて以降に登録された必要な数のローカル・コールバックが存在するかどうかを判断する。存在する場合には、現在のプロセッサのビットマップは、隣接するプロセッサのビットマップに対応するように設定されるが、現在のプロセッサのビットは１に設定される。最後の猶予時間以降に、必要な数のローカル・コールバックが登録されなかった場合には、ビットマップにおける現在のプロセッサのビット値は、ゼロに設定される。この実装形態の１つの欠点は、プロセッサの数が多くなるのに従って大きなビットマップを処理することが必要になるため、多数のプロセッサを正常に扱えないことである。
【００３４】
図１４は、分散コールバック・インジケータ３２が保留コールバックを有するプロセッサ４１、４２・・・４ｎの数のカウントである上述の第１の実施形態に従って行うことができる処理ステップの例示的な手順を示す。図１４のプロセスは、分散コールバック・インジケータとして、「ｃｂｃｐｕｓ」（「ｃａｌｌｂａｃｋ  ｃｐｕｓ」の省略形）と呼ばれるプロセッサ毎のローカル変数を用いる。この変数は、処理を必要とするコールバックを有するプロセッサのカウントである。「ｌａｓｔｃｂｓ」（「ｌａｓｔ  ｃａｌｌｂａｃｋｓ」の省略形）と呼ばれるプロセッサ毎の別のローカル変数は、現在のプロセッサが、猶予時間トークンが最後にこのプロセッサを離れたときに登録されたコールバックを持つかどうかを示すフラグである。「ｎｕｍｃｂｓ」（「ｎｕｍｂｅｒ  ｏｆ  ｃａｌｌｂａｃｋｓ」の省略形）と呼ばれるプロセッサ毎の第３の変数は、最後の猶予時間以降に現在のプロセッサにおいて登録されたコールバックの数のカウントである。
【００３５】
図１４のステップ４０においては、ｎ番目のプロセッサのコールバック・インジケータ処理機構３４は、プロセッサｎ＋１のｃｂｃｐｕｓの値を取得する（所望の伝搬方向によってプロセッサｎ−１を用いることもできる）。ステップ４２においては、プロセッサｎは、猶予時間を開始するための基準を満たすいずれかの新しいコールバック（ｎｕｍｃｂｓ）が存在するかどうかを判断する。幾つかの場合においては、一つでもコールバックが存在すれば、この基準を満たすことになる。他の場合においては、猶予時間を開始するのに必要なコールバックの数を指定するコールバックしきい値と、コールバックしきい値に達しない場合であってもコールバック処理を起動する経過時間しきい値とを設定することによって、コールバックをバッチ処理することが望ましいことがある。ステップ４２において、処理を必要とする新しいコールバックが存在する場合には、ステップ４４において、現在のプロセッサのｃｂｃｐｕｓの値は、隣接するプロセッサのｃｂｃｐｕｓの値より１大きい値から現在のプロセッサのｌａｓｔｃｂｓを引いた値に設定される。次いで、ｌａｓｔｃｂｓの値は、現在のプロセッサ上のコールバックが猶予時間を開始するための基準を満たす場合に限り、ステップ４６において１に設定される。ステップ４２において、処理を必要とする新しいコールバックが存在しない場合には、ステップ４８において、現在のプロセッサのｃｂｃｐｕｓの値は、隣接するプロセッサのｃｂｃｐｕｓの値と等しい値から現在のプロセッサのｌａｓｔｃｂｓを引いた値に設定される。次いで、ｌａｓｔｃｂｓの値は、猶予時間を開始するための基準を満たす新しいコールバックが現在のプロセッサ上に存在しない場合に限り、ステップ５０において０に設定される。
【００３６】
各々のプロセッサが、静止状態を経ながら上述の処理を行うときに、新しいコールバックの登録又は古いコールバックの処理による変化が、分散コールバック・インジケータ（この例においては、ｃｂｃｐｕｓ）の各々によって迅速に反映されることになる。伝搬する分散コールバック・インジケータを各々のプロセッサにおいてテストすることによって、猶予時間トークンの循環を保証する十分なコールバックが存在しないときには潜在的に高価なトークン処理を回避することができる。図１５の表は、例示的な４つのプロセッサ・システムにおけるこうした処理を示す。図１５は、図１２を基にしたものであるが、プロセッサ０、１、２、及び３毎に、表の各々の要素の左側には猶予時間トークンを示し、表の各々の要素の右側には分散コールバック・インジケータ（この例においては、ｃｂｃｐｕｓ）を示す。この場合も、網掛けしたセルは、対応するプロセッサが猶予時間トークンのオーナーであることを示す。いずれの場合においても、オーナーは、静止状態カウンタが最小値を有し、かつ、隣接するプロセッサがトークンのオーナーのカウンタ値に対して不連続なカウンタ値を有する、プロセッサである。
【００３７】
図１５において、プロセッサ３は、プロセッサ０から猶予時間トークンを受け取る。しかしながら、プロセッサ３の分散コールバック・インジケータの値が０であるため、トークン処理は行われない。分散コールバック・インジケータ３２がコールバック・プロセッサのカウント（ｃｂｃｐｕｓ）である現在の例においては、０の値は、処理を保証する必要な数のコールバックを有するプロセッサが存在しないことを意味する。このようにして、プロセッサ３は、このプロセッサのグループについてのリード・コピー・アップデート・サブシステムはアイドル状態であると判断する。図１５の時間ｔ＝１においては、プロセッサ２は、新しいコールバック行為を有していると判断し、分散コールバック・インジケータの値を１に設定する。プロセッサ３は、（現在の例によれば、プロセッサ３は、コールバック・インジケータの動きについてプロセッサ０のみに注意を向けているため）影響を受けず、この場合も、猶予時間トークン処理を行わない。時間ｔ＝２において、プロセッサ２の分散コールバック・インジケータ値は、プロセッサ１に伝搬する。プロセッサ３は、影響を受けず、この場合も猶予時間トークン処理を行わない。時間ｔ＝３において、プロセッサ１の分散コールバック・インジケータ値は、プロセッサ０に伝搬する。プロセッサ３は、影響を受けず、この場合も猶予時間トークン処理を行わない。時間ｔ＝４において、プロセッサ０の分散コールバック・インジケータ値がプロセッサ３に伝搬したことによって、プロセッサ３は、猶予時間トークン処理を行い、トークンをプロセッサ２に渡す。時間ｔ＝５において、プロセッサ２は、猶予時間トークン処理を行い、トークンをプロセッサ１に渡す。時間ｔ＝６において、プロセッサ１は、猶予時間トークン処理を行い、トークンをプロセッサ０に渡す。さらに、プロセッサ２は、そのコールバックが処理され、その分散コールバック・インジケータが０に設定されていると判断したと思われる。時間ｔ＝７において、プロセッサ０は、猶予時間トークン処理を行い、トークンをプロセッサ３に渡す。さらに、プロセッサ２の分散コールバック・インジケータは、プロセッサ１に伝搬する。時間ｔ＝８において、プロセッサ３は、猶予時間トークン処理を行い、トークンをプロセッサ２に渡す。さらに、プロセッサ１の分散コールバック・インジケータは、プロセッサ０に伝搬する。図１４のシステムにおいて新しいコールバックが登録されていないと仮定すると、プロセッサ２の分散コールバック・インジケータが０であるため、ここで、猶予時間トークンは、プロセッサ２においてアイドル状態となる。
【００３８】
図１６は、上述の処理を要約するものである。図１６は、プロセッサ３が時間ｔ＝０、７においてトークン（Ｔ）を取得することを示す。次いで、トークンは、時間ｔ＝１、２、及び３の間、プロセッサ３においてアイドル状態となる。次いで、プロセッサ２は、時間ｔ＝４、８においてトークンを取得する。プロセッサ１は、時間ｔ＝５においてトークンを取得する。プロセッサ０は、時間ｔ＝６においてトークンを取得する。
【００３９】
ここで、図１７を参照すると、図１４の分散コールバック・インジケータ処理の代替形が示される。この代替的な手法によれば、（図１４のステップ４２に対応する）ステップ４２ａは、しきい値に達したかどうかを考慮することなく、ｎｕｍｃｂｓが非ゼロであるかどうかを調べる。（図１４のステップ４６に対応する）ステップ４６ａは、ｎｕｍｃｂｓが０より大きい場合に限り、ｌａｓｔｃｂｓを１に設定する。（図１４のステップ５０に対応する）ステップ５０ａは、ｎｕｍｃｂｓが０である場合に限り、ｌａｓｔｃｂｓを０に設定する。この代替的な手法の利点は、ごくわずかなコールバックを有するプロセッサが、それらのコールバック処理要求を別のプロセッサの猶予時間トークンの循環に「載せて運び（piggyback）」、トークンを移動させ続けることができることである。欠点は、付加的な猶予時間検出動作が生じる可能性があることである。
【００４０】
図１８は、分散コールバック・インジケータ３２が保留コールバックの数のカウントである上述の第２の実施形態に従って行うことができる処理ステップの例示的なシーケンスを示す。図１８のプロセスは、分散コールバック・インジケータとして、「ｃｂｓｐｅｎ」（「ｃａｌｌｂａｃｋｓ  ｐｅｎｄｉｎｇ」の省略形）と呼ばれるプロセッサ毎のローカル変数を用いる。「ｌａｓｔｃｂｓ」（「ｌａｓｔ  ｃａｌｌｂａｃｋｓ」の省略形）と呼ばれるプロセッサ毎の別のローカル変数は、猶予時間トークンが最後にこのプロセッサを離れたときに現在のプロセッサが登録したコールバックの数を示す値である。「ｎｕｍｃｂｓ」（「ｎｕｍｂｅｒ  ｏｆ  ｃａｌｌｂａｃｋｓ」の省略形）と呼ばれるプロセッサ毎の第３の変数は、最後の猶予時間以降に現在のプロセッサにおいて登録されたコールバックの数のカウントである。
【００４１】
図１８のステップ６０においては、ｎ番目のプロセッサのコールバック・インジケータ処理機構３４は、プロセッサｎ＋１のｃｂｓｐｅｎの値を取得する（所望の伝搬方向によってプロセッサｎ−１を用いることもできる）。ステップ６２においては、現在のプロセッサのｃｂｓｐｅｎの値は、隣接するプロセッサのｃｂｓｐｅｎの値に現在のプロセッサのｎｕｍｃｂｓの値を加えて、現在のプロセッサのｌａｓｔｃｂｓの値を引いた値に設定される。次いで、ｌａｓｔｃｂｓの値は、ステップ６４においてｎｕｍｃｂｓに設定される。
【００４２】
図１９は、分散コールバック・インジケータ３２がどのプロセッサが保留コールバックを有するかを示すビットマップである上述の第３の実施形態に従って行うことができる処理ステップの例示的な手順を示す。図１９のプロセスは、分散コールバック・インジケータとして、「ｃｂｃｐｕｍａｐ」（「ｃａｌｌｂａｃｋ  ｃｐｕ  ｍａｐ」の省略形）と呼ばれるプロセッサ毎のローカル・ビットマップ変数を用いる。「ｎｕｍｃｂｓ」（「ｎｕｍｂｅｒ  ｏｆ  ｃａｌｌｂａｃｋｓ」の省略形）と呼ばれるプロセッサ毎の別のローカル変数は、最後の猶予時間以降に現在のプロセッサにおいて登録されたコールバックの数のカウントである。
【００４３】
図１９のステップ８０においては、ｎ番目のプロセッサのコールバック・インジケータ処理機構３４は、プロセッサｎ＋１のｃｂｃｐｕｍａｐの値を取得する（所望の伝搬方向によってプロセッサｎ−１を用いることもできる）。ステップ８２においては、プロセッサｎは、（例えば、図１４に関して上述された）設定された何らかのしきい値を満足する、このプロセッサにおいて登録されたいずれかの新しいコールバック（ｎｕｍｃｂｓ）が存在するかどうかを判断する。ステップ８２において処理を必要とする新しいコールバックが存在する場合には、ステップ８４において、現在のプロセッサのｃｂｃｐｕｍａｐはプロセッサｎ＋１と等しい値に設定されるが、ｃｂｃｐｕｍａｐのｎ番目のビットは１に設定される。ステップ８２において処理を必要とする新しいコールバックが存在しない場合には、ステップ８６において、現在のプロセッサのｃｂｃｐｕｍａｐの値はプロセッサｎ＋１と等しい値に設定されるが、ｃｂｃｐｕｍａｐのｎ番目のビットは０に設定される。
【００４４】
以上の通り、アトミック命令を必要とせず、多数のプロセッサを正常に処理するために実装することができる、リード・コピー・アップデート猶予時間検出のための技術が開示された。上述の概念は、データ処理システム、マシン実装方法、及び、必要な機能を行うようにデータ処理システムを制御するのに用いるためにプログラム手段が１つ又は複数のデータ記憶媒体上に記録されたコンピュータ・プログラム製品のいずれかにおいて、様々に具体化できることが分かるであろう。こうしたプログラム手段を格納するための例示的なデータ記憶媒体が、図２０において参照数字１００によって示される。媒体１００は、従来から市販のソフトウェア販売に用いられているタイプの携帯型光記憶ディスクとして示される。こうした媒体は、本発明のプログラム手段を、単独で、又はリード・コピー・アップデート機能を組み込んだオペレーティング・システム若しくは他のソフトウェア製品と共に、格納することができる。プログラム手段は、（フロッピー・ディスク、フラッシュ・メモリ・スティックなどといった）携帯型磁気媒体上に、又はコンピュータ・プラットフォームに組み込まれたドライブ・システム（例えば、ディスク・ドライブ）と組み合わされた磁気媒体上に、格納することもできる。
【００４５】
本発明の種々の実施形態を説明したが、本発明に従って多くの変形及び代替的な実施形態を実装できることが明らかである。したがって、本発明は、特許請求の範囲及びその均等物の趣旨に合致する場合を除いて、どのような形であっても限定されるべきではないことが理解される。
【図面の簡単な説明】
【００４６】
【図１】従来のリード・コピー・アップデート機構によってデータ要素が置換されるデータ要素のリンク・リストを表す図である。
【図２】従来のリード・コピー・アップデート機構によってデータ要素が置換されるデータ要素のリンク・リストを表す図である。
【図３】従来のリード・コピー・アップデート機構によってデータ要素が置換されるデータ要素のリンク・リストを表す図である。
【図４】従来のリード・コピー・アップデート機構によってデータ要素が置換されるデータ要素のリンク・リストを表す図である。
【図５】従来のリード・コピー・アップデート機構によってデータ要素が削除されるデータ要素のリンク・リストを表す図である。
【図６】従来のリード・コピー・アップデート機構によってデータ要素が削除されるデータ要素のリンク・リストを表す図である。
【図７】従来のリード・コピー・アップデート機構によってデータ要素が削除されるデータ要素のリンク・リストを表す図である。
【図８】４つのプロセスが静止状態を経る猶予時間を示すフロー図である。
【図９】本発明を実装することができる１つの例示的な環境を表すマルチプロセッサ・コンピュータ・システムを示す機能ブロック図である。
【図１０】図９のマルチプロセッサ・コンピュータ・システムの各々のプロセッサによって実装されるリード・コピー・アップデート・サブシステムを示す機能ブロック図である。
【図１１】図９のマルチプロセッサ・コンピュータ・システムの各々のプロセッサと関連付けられるキャッシュ・メモリを示す機能ブロック図である。
【図１２】リード・コピー・アップデートを実装する仮想的な４プロセッサ・データ処理システムにおける例示的な静止状態カウンタの値を示す表である。
【図１３】リード・コピー・アップデート処理の際に、時間毎に猶予時間トークンを渡す場合の図１２の４つのプロセッサを示す機能ブロック図である。
【図１４】保留コールバックを有するプロセッサのカウントとして実装される分散コールバック・インジケータの操作を示すフロー図である。
【図１５】リード・コピー・アップデートを実装する仮想的な４プロセッサ・データ処理システムにおける、例示的な静止状態カウンタの値と分散コールバック・インジケータの値とを示す表である。
【図１６】リード・コピー・アップデート処理の際に、時間毎に猶予時間トークンを渡す場合の図１５の４つのプロセッサを示す機能ブロック図である。
【図１７】図１４のフロー図の修正形を表すフロー図である。
【図１８】保留コールバックのカウントとして実装される分散コールバック・インジケータの操作を示すフロー図である。
【図１９】保留コールバックを有するプロセッサを特定するビットマップとして実装される分散コールバック・インジケータの操作を示すフロー図である。
【図２０】本発明に係るリード・コピー・アップデート猶予時間検出機能を実装するためのコンピュータ・プログラム製品を格納するのに用いることができる記憶媒体を示す図である。
【図１】
2008518337.tif 000003
【図２】
2008518337.tif 000004
【図３】
2008518337.tif 000005
【図４】
2008518337.tif 000006
【図５】
2008518337.tif 000007
【図６】
2008518337.tif 000008
【図７】
2008518337.tif 000009
【図８】
2008518337.tif 000010
【図９】
2008518337.tif 000011
【図１０】
2008518337.tif 000012
【図１１】
2008518337.tif 000013
【図１２】
2008518337.tif 000014
【図１３】
2008518337.tif 000015
【図１４】
2008518337.tif 000016
【図１５】
2008518337.tif 000017
【図１６】
2008518337.tif 000018
【図１７】
2008518337.tif 000019
【図１８】
2008518337.tif 000020
【図１９】
2008518337.tif 000021
【図２０】
2008518337.tif 000022
【国際調査報告】
2008518337.tif 000023
2008518337.tif 000024