(57)【要約】【課題】プリエンプタブルなデータ参照者に影響する共用データの更新動作の後に猶予期間検出を最適化するための技術を提供する。【解決手段】データ処理システムが、ユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかという決定がなされる。もし、データ処理システムがユニプロセッサ・システムであれば、第１の猶予期間検出技術を使用して、猶予期間検出処理が実行される。一方、データ処理システムがマルチプロセッサ・システムであれば、第２の猶予期間検出技術を使用して、猶予期間検出処理が実行される。猶予期間検出処理は、プリエンプションの対象である参照者が静止状態を通過し且つ共用データの更新前のビューへの参照を維持することができない、猶予期間の終わりを決定する。【選択図】  図１３
2010033554.tif 000002
【特許請求の範囲】
【請求項１】
プリエンプタブルなデータ参照者を有するデータ処理システムにおいて、当該データ参照者に影響する共用データの更新動作の後に猶予期間検出を最適化するための方法であって、
前記データ処理システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかを決定するステップと、
前記データ処理システムがユニプロセッサ・システムである場合は、第１の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記データ処理システムがマルチプロセッサ・システムである場合は、第２の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記猶予期間検出処理が、プリエンプションの対象である参照者が静止状態を通過し且つ前記共用データの更新前のビューへの参照を維持することができない、猶予期間の終わりを決定するステップとを含む、方法。
【請求項２】
前記第１の猶予期間検出技術が、マルチプロセッサ調整処理を含まず、前記第２の猶予期間検出技術が、前記マルチプロセッサ調整処理を含む、請求項２記載の方法。
【請求項３】
前記マルチプロセッサ調整処理が、メモリ・バリアを実行すること及び新しい猶予期間の確認を待機することの一方又は両方を含む、請求項２記載の方法。
【請求項４】
前記第１の猶予期間検出技術又は前記第２の猶予期間検出技術の何れかを実行するために前記猶予期間検出処理が静的にコンパイルされるように、前記決定するステップがコンパイル時に実行される、請求項１記載の方法。
【請求項５】
前記第１の猶予期間検出技術又は前記第２の猶予期間検出技術の何れかを実行するために前記猶予期間検出処理が動的に条件付けられるように、前記決定するステップが実行時に実行される、請求項１記載の方法。
【請求項６】
前記決定するステップが、コンパイル時、ブート時又は実行時に提供されるシステム構成情報に基づく、請求項１記載の方法。
【請求項７】
データ処理システムであって、
１つ以上のプロセッサと、
前記１つ以上のプロセッサに結合されたメモリとを備え、
前記メモリ内に格納された少なくとも１つのプログラムの命令が、プリエンプタブルなデータ参照者に影響する共用データの更新動作の後に猶予期間検出を最適化するために、前記１つ以上のプロセッサに
前記データ処理システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかを決定するステップと、
前記データ処理システムがユニプロセッサ・システムである場合は、第１の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記データ処理システムがマルチプロセッサ・システムである場合は、第２の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記猶予期間検出処理が、プリエンプションの対象である参照者が静止状態を通過し且つ前記共用データの更新前のビューへの参照を維持することができない、猶予期間の終わりを決定するステップとを実行させる、システム。
【請求項８】
プリエンプタブルなデータ参照者に影響する共用データの更新動作の後に猶予期間検出を最適化するためのコンピュータ・プログラムであって、
データ処理システムに
前記データ処理システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかを決定するステップと、
前記データ処理システムがユニプロセッサ・システムである場合は、第１の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記データ処理システムがマルチプロセッサ・システムである場合は、第２の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記猶予期間検出処理が、プリエンプションの対象である参照者が静止状態を通過し且つ前記共用データの更新前のビューへの参照を維持することができない、猶予期間の終わりを決定するステップとを実行させる、コンピュータ・プログラム。
【請求項９】
プリエンプタブルな参照者を有するデータ処理システムにおいて、共用データの更新動作の後に猶予期間検出を最適化するための方法であって、
共用データ上で第１段階のデータの更新動作を実行するとともに、当該更新動作中に前記共用データを同時に参照中の参照者のために前記共用データの更新前のビューを一時的に保存するステップと、
前記データ処理システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかを動的に決定するステップと、
前記データ処理システムがユニプロセッサ・システムである場合は、第１の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記データ処理システムがマルチプロセッサ・システムである場合は、第２の猶予期間検出技術を使用して、猶予期間検出処理を実行するステップと、
前記猶予期間検出処理が、プリエンプションの対象である参照者が静止状態を通過し且つ前記共用データの前記更新前のビューへの参照を維持することができない、猶予期間の終わりを決定するステップと、
前記猶予期間の後に第２段階の更新動作を実行するステップとを含む、方法。
【請求項１０】
前記決定するステップが、コンパイル時、ブート時又は実行時に提供されるシステム構成情報に基づく、請求項９記載の方法。
【請求項１１】
請求項１乃至請求項６または請求項９若しくは請求項１０の何れか１項に記載の方法の各ステップをコンピュータに実行させるためのコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ資源が複数の消費者間で同時に共用される際に、各消費者に関するデータの完全性及び一貫性を維持するようにしたコンピュータ・システム及び方法に係り、さらに詳細に説明すれば、ユニプロセッサ・コンピュータ環境において、「読み取り・コピー・更新」（read-copy-update：以下「ＲＣＵ」と略記）として知られている相互排他機構を実装することに係る。
【背景技術】
【０００２】
ＲＣＵ技術とは、ロック、共用メモリへの書き込み、メモリ・バリア、アトミック命令又は計算コストが高い他の同期機構を使用することなく、読み取りのために共用データにアクセスすることを可能にするとともに、当該データを同時に更新（修正、削除、挿入）することを可能にする相互排他技術である。ＲＣＵ技術を使用するのに特に適したマルチプロセッサ・コンピュータ環境とは、共用データセットにアクセスする読み取り動作（参照者）の数が更新動作（更新者）の数より大きく、しかも各読み取り動作のために他の相互排他技術（例えば、ロック）を使用するオーバーヘッド・コストが高い、というものである。例えば、読み取り側のロック獲得が著しい負担となるケースは、数分おきに１回だけ更新されるが、毎秒数千回も検索されるようなネットワーク経路指定テーブルである。
【０００３】
ＲＣＵ技術は、データ更新を２つの段階で実装する。第１（初期更新）段階では、実際のデータ更新は、更新中データの２つのビューを一時的に保存するという態様で実行される。１つのビューは、当該データを参照中の読み取り動作のために維持される、古い（更新前の）データ状態である。他のビューは、当該更新の後に当該データにアクセスする動作のために使用可能な、新しい（更新後の）データ状態である。第２（遅延型更新）段階では、古いデータ状態は、「猶予期間」の後に除去される。この「猶予期間」は、実行中の全ての動作がもはや更新前のデータへの参照を維持しないであろうということを保証するように十分に長くなっている。第２段階の更新動作は、典型的には、古いデータ要素を解放することを含む。特定のＲＣＵ実装では、第２段階の更新動作は、第１段階の更新に従った動作状態を変更するような他の操作を含むことがある。
【０００４】
図１〜図４は、１グループのデータ要素Ａ〜Ｃのうちデータ要素Ｂを修正する場合の、ＲＣＵ機構の使用例を示す。データ要素Ａ〜Ｃは、循環的に探索される単方向連結リスト内に配列され、その各要素は、データの或るアイテムを格納することに加えて、当該リスト内の次の要素へのポインタ（最後の要素の場合はヌル・ポインタ）を保持する。グローバル・ポインタ（図示せず）が、当該リストの第１のメンバである、データ要素Ａを指すものと仮定する。当業者には明らかなように、データ要素Ａ〜Ｃは、Ｃ言語の「struct」変数によって定義されるデータ構造を含む、種々の伝統的プログラミング構文のうち任意のものを使用して実装される。
【０００５】
ここで、図１〜図４の単方向連結リストが、複数の参照者によって（ロックなしで）同時に探索され、そして当該リスト内のデータ要素を削除、挿入又は修正する更新者によって時々更新されるものと仮定する。図１では、データ要素Ｂの下部にある矢印によって示すように、参照者ｒ１がデータ要素Ｂを参照中である。図２では、更新者ｕ１は、データ要素Ｂを修正することにより、連結リストを更新することを望んでいる。参照者ｒ１がデータ要素Ｂを参照中であるという事実を考慮することなくデータ要素Ｂを単に更新する代わりに（そのようにすると、参照者ｒ１を破壊することがある）、更新者ｕ１は、データ要素Ｂを保存し、他方、その更新バージョン（図３のデータ要素Ｂ’）を生成し且つ当該更新バージョンを連結リスト内に挿入する。具体的には、更新者ｕ１は、適切なロックを獲得し、データ要素Ｂ’用の新しいメモリを割り振り、データ要素Ｂの内容をデータ要素Ｂ’にコピーし、必要に応じてデータ要素Ｂ’を修正し、データ要素Ｂ’を指すようにＡからＢへのポインタを更新し、ロックを解除する。連結リストを探索する後続（更新後）の全ての参照者（例えば、参照者ｒ２）は、データ要素Ｂ’に遭遇することにより、更新動作の結果を見出すであろう。他方、古い参照者ｒ１は、データ要素Ｂの原バージョン及びデータ要素Ｃへのそのポインタが保存されるという理由で、影響を受けないであろう。参照者ｒ１は、古いデータを現に読み取り中であるが、これを許容することができる多くのケースが存在する。１例を挙げると、データ要素がコンピュータ・システムの外部にあるコンポーネントの状態（例えば、ネットワーク接続性）を追跡するときは、通信遅延のために古いデータを許容しなければならない。
【０００６】
前記更新後の或る時間に、参照者ｒ１は、連結リストの探索を継続し、そしてデータ要素Ｂのその参照から移動しているであろう。さらに、他の如何なる参照者プロセスも、データ要素Ｂにアクセスする資格を有さない時点が存在するであろう。前述の猶予期間の満了を表すこの時点では、更新者ｕ１は、図４に示すように、データ要素Ｂを解放することができる。
【０００７】
図５〜図７は、単方向連結リスト内のデータ要素Ａ〜Ｃのうちデータ要素Ｂを削除する場合の、ＲＣＵ機構の使用例を示す。図５に示すように、参照者ｒ１がデータ要素Ｂを現に参照中であり、そして更新者ｕ１がデータ要素Ｂを削除することを望んでいるものと仮定する。図６に示すように、更新者ｕ１は、データ要素Ａがデータ要素Ｃを指すようにＡからＢへのポインタを更新する。このように、参照者ｒ１は、妨害されないが、後続の参照者ｒ２は、削除の結果を見出す。図７に示すように、参照者ｒ１は、その後にデータ要素Ｂのその参照から移動し、その結果、猶予期間の満了後にデータ要素Ｂを解放することを許容するであろう。
【０００８】
ＲＣＵ機構の文脈では、猶予期間は、ＲＣＵ機構によって保護されたデータ要素にアクセスする全ての実行中プロセスが、「静止状態」を通過した時点を表す。この場合、これらの実行中プロセスは、もはや当該データ要素への参照を維持したり、当該データ要素上のロックを表明したり、或いはデータ要素の状態に関する如何なる仮定も行うことができない。規約により、オペレーティング・システムのカーネル・コード・パス、コンテキスト（プロセス）スイッチ、アイドル・ループ及びユーザ・モードの実行については、その全ては、所与のＣＰＵのための静止状態を表す（他の同様の動作は省略）。
【０００９】
図８では、４つの別個のＣＰＵ上で実行中のプロセス０〜３は、（２重の垂直バーによって表された）静止状態を定期的に通過するように示されている。猶予期間は、プロセス０〜３の全てがそれぞれ１つの静止状態を通過する、時間フレームを包含する。もし、プロセス０〜３が、図１〜図４又は図５〜図７の単方向連結リストを探索する参照者プロセスであれば、猶予期間の前に古いデータ要素Ｂを参照していたどのプロセスも、猶予期間の後は、当該古いデータ要素Ｂへの参照を維持することができないであろう。これらのプロセスによって行われる猶予期間後の全ての探索は、更新者によって挿入されたリンクを辿って、データ要素Ｂをバイパスするであろう。
【００１０】
猶予期間後に遅延型データ更新を実装するために使用される種々の方法が存在する。その１つは、遅延型更新要求を（例えば、コールバック・リスト上の）コールバックとして累積し、猶予期間の終わりに、バッチ・コールバック処理を実行するというものである。これは、非同期的な猶予期間処理を表す。更新者は、第１段階の更新を実行し、コールバック要求を発行した後、それらのコールバックが猶予期間の終わりに最終的に処理されるであろうということを知った上で動作を再開することができる。一般的に使用される他の技術は、更新者に第１段階の更新を実行させ、猶予期間が完了するまで阻止（待機）させた後、遅延型更新を実行することを再開させるというものである。これは、同期的な猶予期間処理を表す。
【００１１】
ＲＣＵ機構は、リナックス（登録商標）カーネルを含む、種々のオペレーティング・システム・カーネル環境内で長年にわたって稼働してきた。非プリエンプタブル・カーネルでは、猶予期間検出処理は、自然な静止状態（例えば、コンテキスト・スイッチ、ユーザ・モード又はアイドル・ループ）を監視するか、又はかかる状態を（例えば、コンテキスト・スイッチの強制を通して）生じさせることにより、これを実行することができる。プリエンプタブル・カーネルでは、実行中のＲＣＵ参照者は、優位順位の高いタスクによってプリエンプトされ得る。かかるプリエンプションは、当該参照者がＲＣＵ機構によって保護されたデータ要素を参照中のカーネル・モードのクリティカル・セクション内にある間さえ、行われることがある。参照者のプリエンプションは、コンテキスト・スイッチを表すが、それは、猶予期間検出のために有効に使用できないことがある。そのため、プリエンプタブルな環境用に設計されたＲＣＵバージョン（以下「非プリエンプタブルなＲＣＵ」と称する）は、自然な静止状態に依存しない。その代わりに、各参照者は、当該参照者がＲＣＵクリティカル・セクションに入るか又はそこから出るときに、ＲＣＵクリティカル・セクション処理のための登録又は登録抹消を行うことにより、それ自体の静止状態を定義する。
【００１２】
猶予期間が満了すると決定されるのは、当該猶予期間の開始後に登録した全ての参照者がその後に登録抹消を行った場合である。幾つかのプリエンプタブルなＲＣＵ実装については、この猶予期間検出作業は、ＲＣＵ参照者を実行中の種々のプロセッサ間の調整（coordination）を必要とする。参照者は、更新者が新しい猶予期間を開始する時点を知る必要があり、更新者は、古い猶予期間の終わりを宣言する前に、参照者がそれぞれのＲＣＵクリティカル・セクションから出たことを確信する必要がある。メモリ・アクセスを順序外で実行することを可能にするＣＰＵ及び／又はコンパイラによる最適化に起因して、或るタイプのプリエンプタブルなＲＣＵ猶予期間検出のために必要とされる調整作業が、重要となることがある。
【００１３】
一般に、プリエンプタブルなＲＣＵは、マルチプロセッサ環境内で使用されるが、ユニプロセッサ環境内でもこれを使用することができる。例えば、多数の小さな組み込み式リアルタイム・システムは、依然としてユニプロセッサ・システムである。かかるシステムは、しばしばＲＣＵから恩恵を受けることがあり、従って他の相互排他機構の代替手段としてプリエンプタブルなＲＣＵを使用することができる。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかし、プリエンプタブルなＲＣＵの幾つかの実装によって使用される既存の猶予期間検出方法は、ユニプロセッサ環境については最適でないことがある。
【課題を解決するための手段】
【００１５】
プリエンプタブルなデータ参照者に影響する共用データの更新動作の後の猶予期間検出を最適化するための方法、システム及びコンピュータ・プログラムが提供される。データ処理システムが、ユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかという決定がなされる。もし、前記データ処理システムがユニプロセッサ・システムであれば、第１の猶予期間検出技術を使用して、猶予期間検出処理が実行される。もし、前記データ処理システムがマルチプロセッサ・システムであれば、第２の猶予期間検出技術を使用して、猶予期間検出処理が実行される。前記猶予期間検出処理は、猶予期間の終わりを決定する。その場合、プリエンプションの対象である参照者は、静止状態を通過しており、共用データの更新前のビューへの参照を維持することができない。
【発明の効果】
【００１６】
本発明は、プリエンプタブルなＲＣＵの幾つかの実装によって使用される既存の猶予期間検出方法を、ユニプロセッサ環境について最適化することができるという効果を奏する。
【図面の簡単な説明】
【００１７】
【図１】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を修正するための一連の動作を例示する図である。
【図２】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を修正するための一連の動作を例示する図である。
【図３】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を修正するための一連の動作を例示する図である。
【図４】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を修正するための一連の動作を例示する図である。
【図５】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を削除するための一連の動作を例示する図である。
【図６】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を削除するための一連の動作を例示する図である。
【図７】従来のＲＣＵ機構に従った、単方向連結リスト内の１グループのデータ要素のうち一のデータ要素を削除するための一連の動作を例示する図である。
【図８】従来技術に従った、猶予期間の間に４つのプロセスが静止状態を通過する態様を例示する図である。
【図９】ユニプロセッサ動作用のプリエンプタブルなＲＣＵ猶予期間検出を最適化するために使用することができる環境を表す、コンピュータ・システムを示すブロック図である。
【図１０】図９のコンピュータ・システム内で実装される、ＲＣＵサブシステムを示すブロック図である。
【図１１】マルチプロセッサ動作用のプリエンプタブルなＲＣＵ猶予期間検出を最適化するために使用することができる代替環境を表す、他のコンピュータ・システムを示すブロック図である。
【図１２】ユニプロセッサ動作用のプリエンプタブルなＲＣＵ猶予期間検出を最適化するために使用することができる、システム構成変数を示すブロック図である。
【図１３】本発明に従った、プリエンプタブルなＲＣＵの猶予期間検出処理を最適化する、第１の例を示すフローチャートである。
【図１４】本発明に従った、プリエンプタブルなＲＣＵの猶予期間検出処理を最適化する、第２の例を示すフローチャートである。
【図１５】スリープ可能なＲＣＵ実装内で実行される、従来技術の猶予期間検出処理を示すフローチャートである。
【図１６】スリープ可能なＲＣＵ実装内で実行される、ユニプロセッサ動作用の最適化された猶予期間検出を示すフローチャートである。
【図１７】スリープ可能なＲＣＵ実装内で実行される、ユニプロセッサ動作用の最適化された猶予期間検出をサポートする、修正された synchronize_shed() 関数を示すフローチャートである。
【図１８】リアルタイムＲＣＵ実装内で使用される、従来技術の状態マシンを示すフローチャートである。
【図１９】図１８の状態マシンの第１の状態で実装される、従来技術の関数を示すフローチャートである。
【図２０】図１８の状態マシンの第２の状態で実装される、従来技術の関数を示すフローチャートである。
【図２１】図１８の状態マシンの第３の状態で実装される、従来技術の関数を示すフローチャートである。
【図２２】図１８の状態マシンの第４の状態で実装される、従来技術の関数を示すフローチャートである。
【図２３】図１８の状態マシンの他のビューを示すフローチャートである。
【図２４】リアルタイムＲＣＵ実装内で実行可能なユニプロセッサ動作用の最適化された猶予期間検出を有する、図１８の状態マシンの修正を示すフローチャートである。
【図２５】リアルタイムＲＣＵ実装内で実行可能なユニプロセッサ動作用の最適化された猶予期間検出を有する、図１８の状態マシンの修正を示すフローチャートである。
【図２６】ユニプロセッサ動作用に最適化されたＲＣＵ猶予期間検出を実装するためのコンピュータ・プログラムを提供するために使用することができる、コンピュータ可読媒体を示す図である。
【発明を実施するための形態】
【００１８】
図９は、その内部で本発明が実装される、コンピュータ環境を例示する。具体的には、ユニプロセッサ・コンピュータ・システム２が図示され、そこではプロセッサ４がシステム・バス６を介してメモリ８に接続される。通常のキャッシュ・メモリ１０及びキャッシュ・コントローラ１２が、プロセッサ４に関連する。通常のメモリ・コントローラ１４が、メモリ８に関連する。
【００１９】
図９では、カーネル・レベル又はユーザ・レベルのプロセス若しくはスレッド（又は他の実行コンテキスト）内で実行される更新動作が、メモリ８内に格納された１セットの共用データ１６上で定期的に更新を実行することを仮定している。参照番号１８１〜１８ｎは、プロセッサ４上で定期的に実行される、個別的なデータ更新動作（更新者）を示す。前述の背景技術の項で説明したように、データ更新者１８１〜１８ｎによって実行される更新は、連結リストの要素を修正し、当該リストに新しい要素を挿入し、当該リストから要素を削除することに加えて、（リスト又は他のデータ構造が関係する）他の多くのタイプの動作を含むことができる。かかる更新を促進するために、プロセッサ４は、そのカーネル・レベル又はユーザ・レベル機能の一部としてＲＣＵサブシステム２０を実装するようにプログラムされる。また、プロセッサ４は、共用データ１６上で、カーネル・レベル又はユーザ・レベルの読み取り動作（参照者）２１１〜２１ｎを定期的に実行する。かかる読み取り動作は、典型的には、更新よりも遙かに多く実行されるであろう。これがＲＣＵの使用の基礎となる前提のうちの１つである。もし、システム２がリアルタイム動作をサポートすれば、更新者１８１〜１８ｎ及び参照者２１１〜２１ｎは、プリエンプタブルであると仮定される。そのため、幾つかの参照者２１１〜２１ｎが共用データ要素１６への同時的な参照を維持している間に、更新者１８１〜１８ｎが（例えば、プリエンプションを行っているリアルタイム・プロセス又はスレッドのコンテキストにおいて、又は割り込みコンテキストから）同じデータ項目を更新することが可能であろう。
【００２０】
ＲＣＵサブシステム２０は、図９の環境内で、種々のプリエンプタブルなＲＣＵ実装のうち任意のものを使用して実装される。これらのプリエンプタブルなＲＣＵ実装は、リナックス（登録商標）カーネルの最近のバージョン又はリナックス（登録商標）カーネルの最近のバージョンに対するパッチ・セットで見出される、リアルタイムＲＣＵ、スリープ可能なＲＣＵ（ＳＲＣＵ）及びクイックＳＲＣＵ（ＱＲＣＵ）実装を含む。これらのプリエンプタブルなＲＣＵ実装の各変形は、猶予期間検出処理を実装するために、前述の背景技術の項で説明したように、参照者の登録及び登録抹消を使用する。参照者登録、参照者登録抹消及び猶予期間検出機能は、ＲＣＵサブシステム２０内のＲＣＵプリミティブによってサポートされる。これらのプリミティブは、図１０の参照番号２２、２４及び２６によってそれぞれ例示される。
【００２１】
また、前述の背景技術の項で説明したように、幾つかのプリエンプタブルなＲＣＵ実装、特に直前の段落で言及したものは、マルチプロセッサ・システムにおいて調整された猶予期間検出処理を必要とする。この調整作業は、他のプロセッサが特定の猶予期間検出アクションを取るまで、各プロセッサが相当な時間にわたって待機することを必要とすることがある。本発明者は、ユニプロセッサ・システム内では猶予期間検出の調整が常に必要とされるものではないことを認識し、ユニプロセッサ環境内でかかる処理を回避するための解決策を開発した。具体的には、本発明に従った当該解決策は、システム内にあるプロセッサの数を、猶予期間検出処理の条件とする。もし、２つ以上のプロセッサがアクティブであれば、前述の猶予期間検出の調整が実行される。一方、１つのプロセッサだけがアクティブであれば、プロセッサ間の猶予期間検出の調整を実行する必要はない。図９のシステム２は、この条件が適用される１つの環境を表す。他の例は、１つのプロセッサだけがアクティブなマルチプロセッサ環境（例えば、ホット・プラグ可能なＣＰＵを有するシステム）になるであろう。この例は、図１１のホット・プラグ可能なマルチプロセッサ・システム２Ａによって例示される。このシステムには、関連するキャッシュ・メモリ１０１〜１０ｎ及びキャッシュ・コントローラ１２１〜１２ｎを有する、複数のプロセッサ４１〜４ｎが存在する。ＲＣＵサブシステム２０は、ＲＣＵサブシステムのインスタンス２０１〜２０ｎとして、プロセッサ４１〜４ｎ上に分散される。システム２Ａは、プロセッサ４１〜４ｎのうち１つを除く全てが非アクティブである（実質的にユニプロセッサ・システムになる）状態に置くことができるので、本発明に従った、条件付きの猶予期間検出の解決策を使用することができる。
【００２２】
ユニプロセッサ環境用の猶予期間検出処理は、これを種々の方法で条件付けることができる。１つの技術は、マルチプロセッサ対ユニプロセッサ・コンパイラ・プリプロセッサ指令に基づき、ＲＣＵサブシステムを条件付きでコンパイルすることにより、猶予期間検出条件をコンパイル時に静的にセットするものであろう。リナックス（登録商標）では、この条件は、CONFIG_SMPカーネル構成（Kconfig）オプションに基づくことがある。プリプロセッサ指令の擬似コードは、次のように実装される。
#ifdef CONFIG_SMP
#definegp_detection()smp_gp_detection()
#else gp_detection() up_gp_detection()
#endif 
【００２３】
この場合、smp_gp_detection() 関数は、マルチプロセッサ環境内のプロセッサ調整を有する猶予期間検出を実行し、一方、up_gp_detection() 関数は、ユニプロセッサ環境内のプロセッサ調整のない猶予期間検出を実行する。gp_detection() 関数は、コンパイル時における適切な環境のためにセットされるであろう。
【００２４】
猶予期間検出処理を条件付けるための他の技術は、実行時に、猶予期間条件を動的にセットするものであろう。こうするためには、コンパイル時に提供されるシステム構成情報を、ブート時又は実行時に調べるようにすればよい。例えば、ユニプロセッサ又はマルチプロセッサ構成の何れかを指示するように、コンパイル時に、図１２のシステム構成変数３０を定義することができる。プリプロセッサ指令を使用する擬似コードは、次のように実装される。
Static const int config_smp =
#ifdef CONFIG_SMP
1;
#else 
0;
#endif
【００２５】
これから明らかなように、config_smp 構成変数３０は、マルチプロセッサ・コードコンパイルについては１として定義され、ユニプロセッサ・コンパイルについてはゼロとして定義されるであろう。実行時には、config_smp 変数をテストすることにより、適切なシステム構成に従って猶予期間検出を条件付けることができる。
【００２６】
猶予期間検出処理を動的に条件付けるための他の技術は、ブート時に渡されるカーネルのブート・パラメータに従って、猶予期間検出を選択するものであろう。カーネルの初期化コードは、ユニプロセッサ及びマルチプロセッサの猶予期間検出処理のうちどちらをＲＣＵサブシステム２０が使用すべきかを指示するブート・パラメータに従って、構成変数３０（例えば、前述のconfig_smp ）をセットすることができる。直前の段落で挙げた例のように、ＲＣＵサブシステム２０は、構成変数３０を検査して、ユニプロセッサ・モード及びマルチプロセッサ・モードの猶予期間検出のうちどちらを使用すべきかを動的に決定するように、プログラムされるであろう。
【００２７】
猶予期間検出処理を動的に条件付けるための他の技術は、アクティブなプロセッサの現在の数に従って、構成変数３０をセットするものであろう。図１１のシステム２Ａのようなホット・プラグ可能な環境では、オンライン・プロセッサの数は、カーネルから容易に決定することができる。例えば、ＲＣＵサブシステム２０がリナックス（登録商標）カーネル内で実装されるならば、ＲＣＵサブシステム２０は、既存の「num_online_cpus()」関数を呼び出すことにより、当該システムがユニプロセッサ又はマルチプロセッサ・システムの何れとして現に動作しているかを動的に決定することができる。ＲＣＵサブシステム２０がユーザ空間内で実装される場合は、他の技術を使用することができる。一旦プロセッサの数が決定されると、環境（ユニプロセッサ又はマルチプロセッサ）を指定するように、構成変数３０（例えば、前述のconfig_smp ）をセットすることができる。代替的に、この場合は構成変数３０が実際に必要とされていないから、ＲＣＵサブシステム２０は、プロセッサの数の直接的な評価によって（例えば、num_online_cpus() 関数によって戻された結果を使用して）その猶予期間検出をセットすることができる。
【００２８】
図１３は、コンパイル時に猶予期間検出を静的に条件付けた後、実行時に適切なタイプの猶予期間検出を自動的に実装するための、ＲＣＵサブシステム２０によって実行される処理を例示する。コンパイル時には、ブロック４０、４２Ａ及び４２Ｂの初期処理が実行される。実行時には、ブロック４４〜５０の後続処理が実行される。ブロック４０では、コンパイラは、プリプロセッサ指令を介して、ユニプロセッサ又はマルチプロセッサ環境の何れかについてコンパイルするように命令される。もし、ユニプロセッサ・コンパイルが指令されるならば、ブロック４２Ａが実装され、猶予期間検出は、マルチプロセッサ調整機能性を含まないようにコンパイルされる。一方、マルチプロセッサ・コンパイルが指令されるならば、ブロック４２Ｂが実装され、猶予期間検出は、必要とされるマルチプロセッサ調整機能性を含むようにコンパイルされる。実行時中のブロック４４では、更新者１８１〜１８ｎは、図９及び図１１の共用データセット１６への更新を実行する。ＲＣＵの原理に従って、この更新は、当該更新動作中に共用データを現に参照中の参照者のために、共用データの更新前のビューを一時的に保存する、という態様で実行される（第１段階の更新）。ブロック４６では、更新者は、ＲＣＵサブシステム２０の猶予期間検出コンポーネント２６を呼び出す。ブロック４８では、猶予期間検出コンポーネント２６は、ブロック４２Ａ又は４２Ｂでコンパイルされた方法に基づいて（すなわち、当該システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかに従って）、マルチプロセッサ調整を含むか又はこれを含まない猶予期間検出を実装する。ブロック５０では、第２段階の更新動作が実行される（例えば、古いデータ要素が解放される）。もし、この猶予期間検出が同期的であれば、第１段階の更新を実行した更新者１８１〜１８ｎが、ブロック５０の第２段階の更新動作を実行する。一方、この猶予期間検出が非同期的であれば、ＲＣＵサブシステム２０が、ブロック５０を実装するであろう。
【００２９】
図１４は、実行時に猶予期間検出処理を動的に条件付けるための、ＲＣＵサブシステム２０によって実行される処理を例示する。ブロック６０では、更新者１８１〜１８ｎは、図９及び図１１の共用データセット１６への更新を実行する。ＲＣＵの原理に従って、この更新は、当該更新動作中に共用データを現に参照中の参照者のために、共用データの更新前のビューを一時的に保存する、という態様で実行される（第１段階の更新）。ブロック６２では、更新者は、ＲＣＵサブシステム２０の猶予期間検出コンポーネント２６を呼び出す。ブロック６４では、猶予期間検出コンポーネント２６は、ホスト・データ処理システムがユニプロセッサ・システム又はマルチプロセッサ・システムの何れであるかを動的に決定する。前述のように、使用される３つの可能な技術は、コンパイル時、ブート時又は実行時に提供されるシステム構成情報（例えば、図１２の構成変数３０）を検査するものを含む。もし、当該データ処理システムがユニプロセッサ・システムであれば、ＲＣＵサブシステム２０は、マルチプロセッサ調整を含まない第１の猶予期間検出技術を使用して、ブロック６６Ａの猶予期間検出処理を実行する。一方、当該データ処理システムがマルチプロセッサ・システムであれば、ＲＣＵサブシステム２０は、マルチプロセッサ調整を含む第２の猶予期間検出技術を使用して、ブロック６６Ｂの猶予期間検出処理を実行する。何れの場合も、猶予期間検出処理は、参照者が共用データの更新前のビューへの参照を維持することができない、猶予期間の終わりを決定する。ブロック６８では、第２段階の更新動作が実行される（例えば、古いデータ要素が解放される）。もし、この猶予期間検出が同期的であれば、第１段階の更新を実行した更新者１８１〜１８ｎが、ブロック６８の第２段階の更新動作を実行する。一方、この猶予期間検出が非同期的であれば、ＲＣＵサブシステム２０が、ブロック６８を実装するであろう。
【００３０】
以下、既存のプリエンプタブルなＲＣＵ実装を修正することにより、図１３及び図１４の処理を実装する方法を例示するために、特定の実装例を説明する。これらの例は、それぞれリナックス（登録商標）カーネルの現行バージョン内で実装されるような、ＳＲＣＵ及びリアルタイムＲＣＵに基づく。しかし、他のカーネル・レベルのプリエンプタブルなＲＣＵバージョン及びユーザ・レベルのプリエンプタブルなＲＣＵも、本明細書に開示した猶予期間検出の最適化技術を実装するための開始点として役立つであろう。
【００３１】
＜例１−ＳＲＣＵ＞
スリープ可能なＲＣＵは、ＲＣＵ参照者がＲＣＵクリティカル・セクション内でスリープするか又は遅れることを可能にする、プリエンプタブルなＲＣＵ実装である。参照者が長い期間にわたって阻止されることがあるという理由で、非同期的な猶予期間検出は、許容されない。更新者は、同期的な猶予期間検出を実行することが必要とされる。誤った参照者がシステム全体の猶予期間検出を遅らせる可能性を最小化するために、参照者は、サブシステムによってグループ化される。各サブシステムは、ＲＣＵクリティカル・セクションの登録及び登録抹消のために当該サブシステム内の参照者によって使用され且つ猶予期間検出のために更新者によって使用される、「srcu_struct」タイプのデータ構造を割り当てられる。各ＳＲＣＵデータ構造は、（１）経過した猶予期間のカウント、（２）プロセッサ対応のカウンタ・ペアへのポインタ及び（３）mutex ロックを保持する。プロセッサ対応の各カウンタ・ペアは、現在の猶予期間中に開始した読み取り動作をカウントするためのアクティブ・カウンタと、最後の猶予期間中に開始した読み取り動作をカウントするための非アクティブ・カウンタとを含む。経過した猶予期間カウンタの下位ビットは、現在の猶予期間にアクティブに関連する、プロセッサ対応のカウンタをインデックスするために使用される。
【００３２】
ＳＲＣＵ実装では、図１０の参照者登録コンポーネント２２は、srcu_read_lock() プリミティブを使用して実装することができる。このプリミティブは、適用可能なＳＲＣＵデータ構造にアクセスし且つ現在の猶予期間及び参照者のプロセッサに関連するプロセッサ対応のカウンタをインクリメントすることにより、ＲＣＵクリティカル・セクション処理のための参照者を登録する。ＳＲＣＵ実装内の参照者登録抹消コンポーネント２４は、srcu_read_unlock() プリミティブを使用して実装することができる。このプリミティブは、srcu_read_lock() によって以前にインクリメントされたプロセッサ対応のカウンタをデクリメントすることにより、ＲＣＵクリティカル・セクションの処理の後に、参照者を登録抹消する。
【００３３】
ＳＲＣＵ実装内の猶予期間検出コンポーネント２６は、synchronize_scru() プリミティブを使用して実装することができる。このプリミティブは、所与のＳＲＣＵデータ構造内の経過した猶予期間カウントをインクリメントすることにより、プロセッサ対応のカウンタの役割を交換し（カウンタの「フリッピング」と呼ばれる）、その後、参照者がＲＣＵクリティカル・セクションの処理を完了するのに応じて、以前の猶予期間に関連するカウンタがゼロに達するまで待機する。その後、第２段階のＲＣＵ更新動作を、安全に実行することができる。マルチプロセッサ環境では、１つのプロセッサ上で実行されるＳＲＣＵ猶予期間検出処理は、他のプロセッサとの注意深い調整を必要とする。synchronize_scru() プリミティブでは、この調整処理は、synchronize_sched() として知られている調整関数に対し幾つかの呼び出しを行うことにより扱われる。これが、ＲＣＵの非プリエンプタブル・バージョン内で使用される、猶予期間検出プリミティブであることに留意されたい。このプリミティブは、各プロセッサ上で猶予期間をスケジュールすることにより、各プロセッサにコンテキスト・スイッチを通過させる。前述のように、このタイプの自然なコンテキスト・スイッチは、非プリエンプタブルなＲＣＵ内では静止状態と見なされる。これは、プリエンプタブルなＲＣＵ内で静止状態を実装するための適切な方法ではない。しかし、ＳＲＣＵは、静止状態を強制するためにsynchronize_sched() プリミティブを使用しない。むしろ、このプリミティブが使用されるのは、これが各プロセッサ上でメモリ・バリアを実装するという副次的な効果を有するためである。このメモリ・バリアの副次的な効果は、ＳＲＣＵについて必要とされる、必須のマルチプロセッサ調整を提供する。synchronize_scru() プリミティブは、synchronize_sched() への幾つかの呼び出しを行うことにより、猶予期間検出動作の種々の段階でメモリ・バリアを実装する。これは、更新側が参照者の状態を知らずに進行しないように、参照者が更新側でなされる状態変更を知ることを保証する。
【００３４】
図１５は、synchronize_scru() プリミティブの従来の動作を例示する。更新者は、synchronize_scru() を呼び出すことにより、所与のサブシステムに関連するＳＲＣＵデータ構造を指定して、当該サブシステム内の猶予期間検出を開始する。ブロック７０で、synchronize_scru() は、ＳＲＣＵデータ構造を読み取って、現在の猶予期間カウントを決定する。ブロック７２で、synchronize_scru() は、ＳＲＣＵデータ構造のロックを獲得する。ブロック７４で、synchronize_scru() は、同じＳＲＣＵデータ構造上で他のプロセッサが既に猶予期間検出を実行中であることを決定する場合、当該ＳＲＣＵデータ構造のロックを解除する。また、synchronize_scru() は、戻る前に、他のプロセッサが猶予期間の検出を完了することを待機する。さもなければ、ブロック７６で、synchronize_scru() は、synchronize_sched() を呼び出す。各プロセッサ上で実行される結果的なメモリ・バリアは、さらなる猶予期間検出処理が実行される前に、synchronize_scru() を呼び出した更新者によって行われた第１段階の更新を、これらのプロセッサが見出すであろうということを保証する。このことは、synchronize_read_lock() への対応する呼び出しに先行するように、他の或るプロセッサが、そのＲＣＵ読み取り側クリティカル・セクション内のアクセスを再配列することを禁止し、その結果、かかる参照が実際に保護されるであろうということを保証する。ブロック７８で、synchronize_scru() は、現在のプロセッサ対応カウンタ・インデックスを獲得し、猶予期間カウントをインクリメントする（カウンタのフリッピングに帰着する）。ブロック８０で、synchronize_scru() は、再びsynchronize_sched() を呼び出す。各プロセッサ上で実行される結果的なメモリ・バリアは、参照者がそれらのＲＣＵクリティカル・セクションに入る前に、古いカウンタを使用する全てのscru_read_lock() の呼び出しが完了しているであろうということを保証する。当該クリティカル・セクションは、依然として実行中であろうが、保護されるであろう。というのは、scru_read_lock() プリミティブそれ自体は、実行を終了しているからである。ブロック８２で、synchronize_scru() は、最後の猶予期間に関連するプロセッサ対応のカウンタ（ブロック７８で獲得したインデックスに対応するもの）がゼロにデクリメントされるまで待機する。ブロック８４で、synchronize_scru() は、再びsynchronize_sched() を呼び出す。各プロセッサ上で実行される結果的なメモリ・バリアは、ブロック８２と同時に実行されていた全てのscru_read_unlock() プリミティブがこの時点までに完了していることを保証する。一層重要なことは、メモリ・バリアは、対応するＲＣＵ読み取り側クリティカル・セクションが完了し且つＲＣＵで保護されたデータ・アイテムへの対応する参照が終了することを強制するということである。ブロック８６で、synchronize_scru() は、ＳＲＣＵデータ構造のロックを解除することにより、猶予期間検出処理を完了させる。
【００３５】
本明細書に開示した猶予期間最適化技術に従って、synchronize_scru() プリミティブは、synchronize_sched() の呼び出しを修正することにより、ユニプロセッサ動作用に最適化することができる。もし、かかる最適化がコンパイル時に実行されるならば、synchronize_scru() は、synchronize_sched() の代わりに、新しい関数smp_synchronize_sched() を呼び出すように修正することができる。この関数の使用例は、図１５に対応する図１６に示されている。但し、図１５のブロック７６、８０及び８４におけるsynchronize_sched() は、図１６のブロック７６Ａ、８０Ａ及び８４Ａにおける新しいsmp_synchronize_sched() 関数で置き換えられている。次に、以下のコンパイラ・プリプロセッサ指令を使用して、synchronize_sched() を条件付きで定義することができる。
#ifdefCONFIG_SMP
#define smp_synchronize_sched() synchronize_sched()
#else
#define smp_synchronize_sched() barrier()
#endif
【００３６】
もし、マルチプロセッサ・システムが存在すれば、smp_synchronize_sched()は、オリジナルのsynchronize_sched() プリミティブに変換されるであろう。さもなければ、smp_synchronize_sched()は、「barrier()」という名前のプリミティブに変換される。このプリミティブは、コンパイラがsynchronize_srcu() 内のsmp_synchronize_sched()を横切ってメモリ参照を再配列することを禁止するが、マルチプロセッサ調整に使用されるメモリ・バリアをsynchronize_sched() 内で実装しない。
【００３７】
もし、実行時にユニプロセッサの最適化を実行することが望まれるならば、マルチプロセッサ環境内でsynchronize_sched() を条件付きで呼び出し、そしてユニプロセッサ環境内でbarrier() を呼び出すように、synchronize_srcu() を修正することができる。その場合、synchronize_sched() は、synchronize_srcu() 内で、図１７に示す処理を実行するラッパ関数（例えば、synchronize_sched_wrapper()）と置き換えることができる。ブロック９０で、synchronize_sched_wrapper() は、それがユニプロセッサ環境又はマルチプロセッサ環境の何れにあるかを決定する。再び、これを行うことができる３つの可能な方法は、コンパイル時、ブート時又は実行時に提供される、システム構成情報（例えば、図１２の構成変数３０）を検査するというものである。もし、ユニプロセッサ環境が検出されるならば、ブロック９２で、barrier() への呼び出しが行われる。一方、マルチプロセッサ環境が検出されるならば、ブロック９４で、synchronize_sched() への呼び出しが行われる。
【００３８】
＜例２−リアルタイムＲＣＵ＞
リアルタイムＲＣＵは、参照者がプリエンプトされる場合でさえ、ＲＣＵ参照者を時期尚早の猶予期間処理から保護する、プリエンプタブルなＲＣＵバージョンである。参照者は、現在の猶予期間番号を使用してインデックスされる、プロセッサ対応のカウンタ・ペアを使用して追跡される。ＳＲＣＵのように、プロセッサ対応のカウンタのうちの１つは、現在の猶予期間中にＲＣＵクリティカル・セクションを開始した参照者によってインクリメント／デクリメントされる。プロセッサ対応の他のカウンタは、最後の猶予期間中にＲＣＵクリティカル・セクションを開始した参照者によって使用される。一旦新しい猶予期間が開始されると、以前の猶予期間に関連するカウンタはデクリメントされるだけであり、従って参照者がクリティカル・セクションを完了すると、最終的にゼロまでカウント・ダウンするであろう。リアルタイムＲＣＵ実装では、図１０の参照者登録コンポーネント２２は、rcu_read_lock() プリミティブを使用して実装することができる。このプリミティブは、現在の猶予期間に関連するプロセッサ対応のカウンタをインクリメントすることにより、ＲＣＵクリティカル・セクションの参照者を登録する。リアルタイムＲＣＵ実装内の参照者登録抹消コンポーネント２４は、rcu_read_unlock() プリミティブを使用して実装することができる。このプリミティブは、rcu_read_lock() によって以前にインクリメントされたプロセッサ対応のカウンタをデクリメントするか、又は参照者がプリエンプトされ且つ異なるプロセッサ上で復元されたならば、当該参照者の猶予期間に対応する新しいプロセッサ上のプロセッサ対応のカウンタをデクリメントすることにより、ＲＣＵクリティカル・セクション処理の後に当該参照者を登録抹消する。
【００３９】
リアルタイムＲＣＵ実装内の猶予期間検出コンポーネント２６は、rcu_try_flip() プリミティブによって実装することができる。このプリミティブによって実装される猶予期間検出アルゴリズムは、複数のプロセッサ上の猶予期間処理を調整するために、状態マシンを使用する。図１８は、状態マシン１００及びその猶予期間検出状態１０２〜１０８を示す。rcu_try_flip() によって実装される猶予期間検出アルゴリズムは、各スケジューリング・クロック割り込みで各プロセッサ上で呼び出される。状態ごとに、rcu_try_flip() は、（状態１０２〜１０８の名前によって表される）別個の関数を呼び出す。もし、この関数がゼロを戻すならば、状態マシンは、同じ状態に留まる。一方、この関数が１を戻すならば、状態マシンは前進する。所与の猶予期間を完了するためには、幾つかのサイクルが必要とされる。
【００４０】
状態１０２は、アイドル状態であり、その状態では如何なる猶予期間検出も進行中ではない。この状態では、rcu_try_flip() は、rcu_try_flip_idle() という関数を呼び出す。図１９は、この関数の処理を示す。ブロック１１０で、この関数は、１つ以上の更新者が第１段階のＲＣＵ更新動作を実行しているために新しい猶予期間が必要とされるか否かを決定する。そうでなければ、ブロック１１２で、この関数はゼロの値を戻し、そしてrcu_try_flip() 状態マシンは、アイドル状態に留まる。一方、新しい猶予期間が必要とされるならば、ブロック１１４で、当該期間が開始される。ブロック１１６では、他のプロセッサが新しい猶予期間を見るように、メモリ・バリア命令が実行される。ブロック１１８で、各プロセッサは、新しい猶予期間を確認するように要求される。ブロック１２０で、この関数は１の値を戻し、そしてrcu_try_flip() 状態マシンは、次の状態１０４に前進する。
【００４１】
状態１０４は、各プロセッサが状態１０２で要求された確認を実行することを待機する、wait_for_ACK 状態である。この状態では、rcu_try_flip() は、rcu_try_flip_waitack() として知られている関数を呼び出す。図２０は、この関数の処理を示す。ブロック１２２で、この関数は、全てのプロセッサから新しい猶予期間の確認が受け取られたか否かを決定する。そうでなければ、ブロック１２４で、この関数はゼロの値を戻し、そしてrcu_try_flip() 状態マシンは、wait_for_ACK 状態に留まる。一方、全ての確認が受け取られたならば、カウンタのモニタリングが行われる前に全ての確認が受け取られることを保証するために、ブロック１２６で、メモリ・バリア命令が実行される。次に、ブロック１２８で、この関数は１の値を戻し、そしてrcu_try_flip() 状態マシンは、次の状態１０６に前進する。
【００４２】
状態１０６は、以前の猶予期間に関連する全てのカウンタがゼロに達するのを待機する、wait_for_zero 状態である。この状態では、rcu_try_flip() は、rcu_try_flip_waitzero() として知られている関数を呼び出す。図２１は、この関数の処理を示す。ブロック１３０で、この関数は、以前の猶予期間に関連するプロセッサ対応の全てのカウンタの和がゼロであるか否かを決定する。そうでなければ、ブロック１３２で、この関数はゼロの値を戻し、そしてrcu_try_flip() 状態マシンは、wait_for_zero状態に留まる。一方、当該カウンタの和がゼロであれば、これらのカウンタの全てが実際にゼロとなる前に後続の処理に進まないことを保証するために、ブロック１３４で、メモリ・バリア命令が実行される。次に、ブロック１３６で、この関数は、全てのプロセッサがメモリ・バリアを実装することを要求する。これは、第２段階のＲＣＵ更新動作が実行される前に、参照者によって全てのＲＣＵクリティカル・セクション処理が完了されているであろうということを保証する。次に、ブロック１３８で、この関数は１の値を戻し、そしてrcu_try_flip() 状態マシンは、次の状態１０８に前進する。
【００４３】
状態１０８は、全てのプロセッサがメモリ・バリアを実装するのを待機する、wait_for_mb 状態である。この状態では、rcu_try_flip() は、rcu_try_flip_waitmb() として知られている関数を呼び出す。図２２は、この関数の処理を示す。ブロック１４０で、この関数は、全てのプロセッサがメモリ・バリアを実装したか否かを決定する。そうでなければ、ブロック１４２で、この関数はゼロの値を戻し、そしてrcu_try_flip() 状態マシンは、wait_for_mb 状態に留まる。一方、全てのメモリ・バリアが実装されたならば、メモリ・バリアの検査が任意の後続猶予期間の前進に先行することを保証するために、ブロック１４４で、メモリ・バリア命令が実行される。次に、ブロック１４６で、この関数は１の値を戻し、そしてrcu_try_flip() 状態マシンは、次のアイドル状態１０２に前進する。状態マシン１００を通しての追加サイクルの後、第２段階のＲＣＵ更新動作を実行する（例えば、以前の猶予期間に関連する古いデータを解放する）ことができる。
【００４４】
図２３は、rcu_try_flip() によって実行される、状態マシンの処理を示す。ブロック１５０で、rcu_try_flip() は、rcu_try_flip_idle() 関数（図１９）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１５２で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１５４で、rcu_try_flip() は、wait_for_ACK 状態１０４に前進する。
【００４５】
ブロック１５６で、rcu_try_flip() は、rcu_try_flip_waitack() 関数（図２０）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１５８で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１６０で、rcu_try_flip() は、wait_for_zero状態１０６に前進する。
【００４６】
ブロック１６２で、rcu_try_flip() は、rcu_try_flip_waitzero() 関数（図２１）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１６４で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１６６で、rcu_try_flip() は、wait_for_mb 状態１０８に前進する。
【００４７】
ブロック１６８で、rcu_try_flip() は、rcu_try_flip_waitmb() 関数（図２２）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１７０で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１７２で、rcu_try_flip() は、アイドル状態１０２に前進する。再び、この時点で、第２段階のＲＣＵ更新動作を実行することができる。
【００４８】
本明細書に開示した猶予期間最適化技術に従って、リアルタイムＲＣＵのrcu_try_flip() プリミティブは、図１８の状態１０４及び１０８を除去することにより、ユニプロセッサ動作用に最適化することができる。もし、この最適化がコンパイル時に実行されるのであれば、rcu_try_flip() 状態マシン・プリミティブは、ユニプロセッサのために状態１０４及び１０８をバイパスするようにコンパイルすることができる。代替的に、状態１０４及び１０８に関連するrcu_try_flip_waitack() 及びrcu_try_flip_waitmb() 関数は、他の任意の処理を実行することなく、（状態マシンを前進させるために）単に１の値を戻すように、ユニプロセッサ動作用にコンパイルすることができる。
【００４９】
もし、ユニプロセッサの最適化を実行時に実行することが望まれるのであれば、rcu_try_flip() 状態マシンは、マルチプロセッサ環境では条件付きで状態１０４及び１０８に入り、ユニプロセッサ環境ではそれらの状態をバイパスするように修正することができる。代替的に、状態１０４及び１０８に関連するrcu_try_flip_waitack() 及びrcu_try_flip_waitmb() 関数は、条件付きで他の任意の処理を実行することなく、（状態マシンを前進させるために）１の値を戻すように修正することができる。再び、これを行うことができる３つの可能な方法は、コンパイル時、ブート時又は実行時に提供される、システム構成情報（例えば、図１２のシステム構成変数３０）を検査するというものである。
【００５０】
図２４及び図２５は、ユニプロセッサ又はマルチプロセッサ・システムの何れが得られるかに従って、実行時に猶予期間検出処理が動的に条件付けられる、rcu_try_flip() 状態マシンの修正されたバージョンを例示する。先ず、図２４を参照して説明する。ブロック１８０で、rcu_try_flip() は、try_flip_idle() 関数（図１９）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１８２で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１８４で、rcu_try_flip() は、マルチプロセッサ環境が存在するか否かを検査する。そうであれば、ブロック１８６で、状態マシンは、wait_for_ACK 状態１０４に前進する。
【００５１】
ブロック１８８で、rcu_try_flip() は、rcu_try_flip_waitack() 関数（図２０）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１９０で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１９２で、rcu_try_flip() は、wait_for_zero状態１０６に前進する。また、ブロック１８４で、ユニプロセッサ環境が存在することを決定する場合にも、状態マシンは、wait_for_zero 状態１０６に前進する。その場合、wait_for_ACK 状態１０４は、不要であり除去することができる。
【００５２】
次に、図２５を参照して説明する。ブロック１９４で、rcu_try_flip() は、rcu_try_flip_waitzero() 関数（図２１）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック１９６で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック１９８で、rcu_try_flip() は、マルチプロセッサ環境が存在するか否かを検査する。そうであれば、ブロック２００で、状態マシンは、wait_for_mb 状態１０８に前進する。
【００５３】
ブロック２０２で、rcu_try_flip() は、rcu_try_flip_mb() 関数（図２２）を呼び出し、その戻り値を検査する。この戻り値がゼロであれば、ブロック２０４で、rcu_try_flip() は、新しい状態に前進することなくブレークする。一方、この戻り値が１であれば、ブロック２０６で、rcu_try_flip() は、アイドル状態１０２に前進する。また、ブロック１９８で、ユニプロセッサ環境が存在することを決定する場合にも、状態マシンは、アイドル状態１０２に前進する。その場合、wait_for_mb 状態１０８は、不要であり除去することができる。
【００５４】
従って、ユニプロセッサ・システム用の猶予期間検出最適化技術が開示された。当業者には明らかなように、前述の概念は、データ処理システム、コンピュータ実装方法及びコンピュータ・プログラムのうち任意のもので種々に具体化され、そしてそのプログラミング手段は、必要とされる諸機能を実行するようにデータ処理システムを制御する際に使用するための１つ以上のコンピュータ可読媒体によって提供される。図２６は、かかるプログラミング手段を提供するために使用することができる、コンピュータ可読媒体３００を例示する。この媒体３００は、市販ソフトウェアの販売に一般に使用される、読み取り専用のＣＤ−ＲＯＭ、読み書き可能なＣＤ−Ｒ／Ｗ及びＤＶＤのような、可搬型の光ストレージ・ディスクとして示されている。かかる媒体は、本発明のプログラミング手段を単独で格納するか、又はオペレーティング・システムのような必要とされる機能を組み込んだ他のソフトウェア製品と共に格納することができる。また、このプログラミング手段は、可搬型の磁気媒体（例えば、フレキシブル・ディスク、フラッシュ・メモリ・スティック等）、ドライブ・システム（例えば、ディスク・ドライブ）と組み合わされた磁気媒体、或いはランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、又は他の半導体若しくは固体メモリのようなデータ処理プラットフォームに統合された媒体によって提供することができる。広義には、この媒体は、データ処理システム、コンピュータ、他の命令実行システム又は装置によって、又はこれらに関連して使用するためのプログラミング手段を保持し、格納し、通信し、伝播し又は移送することができる、電子、磁気、光学、電磁気、赤外線、半導体システム若しくは装置、伝送媒体若しくは信号、又は他のエンティティのうち任意のものとすることができる。
【００５５】
以上、本発明の種々の実施形態を説明したが、本発明に従って多数の変形及び代替的な実施形態を実装されることは明らかである。従って、本発明は、請求項の記載事項及びそれらの均等物の精神に従う場合を除き、限定されるべきものではない。
【符号の説明】
【００５６】
Ａ〜Ｃ・・・・・・データ要素
Ｂ’・・・・・・・データ要素Ｂの更新バージョン
ｒ１、ｒ２・・・・読み取り動作（参照者）
ｕ１・・・・・・・更新動作（更新者）
２・・・・・・・・ユニプロセッサ・コンピュータ・システム
２Ａ・・・・・・・対称型マルチプロセッサ（ＳＭＰ）コンピュータ・システム
４１〜４ｎ・・・・・プロセッサ
６・・・・・・・・共通システム・バス
８・・・・・・・・共用メモリ
１０１〜１０ｎ・・・キャッシュ・メモリ
１２１〜１２ｎ・・・キャッシュ・コントローラ
１４・・・・・・・メモリ・コントローラ
１６・・・・・・・共用データセット
１８１〜１８ｎ・・・更新動作（更新者）
２０１〜２０ｎ・・・ＲＣＵインスタンス（ＲＣＵサブシステム）
２１１〜２１ｎ・・・読み取り動作（参照者）
２２・・・・・・・・参照者登録コンポーネント
２４・・・・・・・・参照者登録抹消コンポーネント
２６・・・・・・・・猶予期間検出コンポーネント
３０・・・・・・・・システム構成変数
３００・・・・・・コンピュータ可読媒体
【図１】
2010033554.tif 000003
【図２】
2010033554.tif 000004
【図３】
2010033554.tif 000005
【図４】
2010033554.tif 000006
【図５】
2010033554.tif 000007
【図６】
2010033554.tif 000008
【図７】
2010033554.tif 000009
【図８】
2010033554.tif 000010
【図９】
2010033554.tif 000011
【図１０】
2010033554.tif 000012
【図１１】
2010033554.tif 000013
【図１２】
2010033554.tif 000014
【図１３】
2010033554.tif 000015
【図１４】
2010033554.tif 000016
【図１５】
2010033554.tif 000017
【図１６】
2010033554.tif 000018
【図１７】
2010033554.tif 000019
【図１８】
2010033554.tif 000020
【図１９】
2010033554.tif 000021
【図２０】
2010033554.tif 000022
【図２１】
2010033554.tif 000023
【図２２】
2010033554.tif 000024
【図２３】
2010033554.tif 000025
【図２４】
2010033554.tif 000026
【図２５】
2010033554.tif 000027
【図２６】
2010033554.tif 000028