(57)【要約】      （修正有）【課題】同時の、ノンブロッキングの、ロックフリーのキューおよび方法、ならびにこれを実装するための装置およびコンピュータ・プログラムを提供する。【解決手段】キューが空になるのを防ぐのに必要なときにのみ、ダミー・ノードが同時の、ノンブロッキングの、ロックフリーのＦＩＦＯキューにエンキューされる。ダミー・ノードはデキュー動作中に、そしてデキュー動作中は単一のユーザー・ノードを含むときにのみエンキューされる。ユーザー・ノードはそのキューに直接にエンキューされ、任意のスレッドによりオンデマンドで直ちにデキューされることができる。好適には、エンキュー動作およびデキュー動作がロード・リンク／ストア・コンディショナル（ＬＬ／ＳＣ）同期プリミティブの使用を含む。これが特有の数、例えばあるキューに特有の数を使用する必要なしにＡＢＡ問題を解決する。【選択図】図３
2008123516.tif 000002
【特許請求の範囲】
【請求項１】
夫々が次のノードへの次のポインタを備える、少なくとも１個のユーザー・ノードと、
次のノードへの次のポインタを備えるダミー・ノードであって、該ダミー・ノードはデキュー動作中であって、かつロックフリー同時ＦＩＦＯキューが前記デキュー動作中に単一のユーザー・ノードを含むときにのみエンキューされる前記ダミー・ノードと、
ヘッド・ノードを識別するヘッド・ポインタと、
テール・ノードを識別するテール・ポインタと、
前記ダミー・ノードを識別するダミー・ポインタと
を含むロックフリー同時ＦＩＦＯキュー。
【請求項２】
前記ダミー・ノードが前記ロックフリー同時ＦＩＦＯキューに含まれず、かつ前記デキュー動作中に前記ダミー・ノードがエンキューされないように、前記ロックフリー同時ＦＩＦＯキューが前記デキュー動作中に２個以上のユーザー・ノードを含む、
請求項１に記載の、ロックフリー同時ＦＩＦＯキュー。
【請求項３】
（ａ）キューの終りにユーザー・ノードをエンキューするステップであって、前記キューが、次のノードへの次のポインタを備える少なくとも１個のダミー・ノードを前記エンキューするステップ（ａ）の前に含み、かつ前記ユーザー・ノードが、次のノードへの次のポインタを備える、前記エンキューするステップと、
（ｂ）前記エンキューするステップ（ａ）の後、前記キューから前記ダミー・ノードをデキューするステップと、
（ｃ）前記デキューするステップ（ｂ）の後、前記キューからヘッド・ノードを条件付きでデキューするステップと、
（ｄ）前記条件付でデキューするステップ（ｃ）中に、前記キューが唯一のユーザー・ノードを含むときにのみ前記キューの前記終りに他のダミー・ノードをエンキューするステップと
を含む、キューを実装する方法。
【請求項４】
前記エンキューするステップ（ａ）が、
前記ユーザー・ノードをポイントするようにテール・ノードの前記次のポインタをセットすることによって前記ユーザー・ノードを前記キューの終りにリンクするステップと、
前記ユーザー・ノードをポイントするように前記キューのテール・ポインタを更新するステップと
を含む、請求項３に記載の方法。
【請求項５】
前記更新するステップがエンキューするステップ（ａ）中は行われないが、その後のエンキュー動作中もしくはその後のデキュー動作中に行われる、請求項４に記載の方法。
【請求項６】
前記条件付でデキューするステップ（ｃ）が、ノードをデキューする際に成功裡に行われるなら、
前記条件付けでデキューするステップ（ｃ）でデキューされたノードの次のポインタをヌルにセットするステップと、
もし前記条件付でデキューするステップ（ｃ）でデキューされるノードがユーザー・ノードなら、前記デキューされたユーザー・ノードを戻すステップと、
もし前記条件付でデキューするステップ（ｃ）でデキューされるノードがダミー・ノードなら、前記条件付でデキューするステップ（ｃ）を再スタートするステップと
を更に含む、請求項３に記載の方法。
【請求項７】
前記エンキューするステップ（ａ）、前記デキューするステップ（ｂ）、前記条件付でデキューするステップ（ｃ）およびエンキューするステップ（ｄ）は夫々がロード・リンク／ストア・コンディショナルを使用することを含む、請求項３に記載の方法。
【請求項８】
前記エンキューするステップ（ａ）、前記デキューするステップ（ｂ）、前記条件付でデキューするステップ（ｃ）およびエンキューするステップ（ｄ）は夫々がストレージ・オーダリング・フェンスを使用することを含む、請求項７に記載の方法。
【請求項９】
少なくとも１個のプロセッサと、
前記少なくとも１個のプロセッサに結合されたメモリと、
前記少なくとも１個のプロセッサ上で稼動する少なくとも１個のスレッドによりエンキューおよびデキューされるロックフリー同時ＦＩＦＯキューであって、
夫々が次のノードへの次のポインタを備える、少なくとも１個のユーザー・ノードと、
次のノードへの次のポインタを備えるダミー・ノードであって、該ダミー・ノードはデキュー動作中であって、かつロックフリー同時ＦＩＦＯキューが前記デキュー動作中に単一のユーザー・ノードを含むときにのみエンキューされる前記ダミー・ノードと、
ヘッド・ノードを識別するヘッド・ポインタと、
テール・ノードを識別するテール・ポインタと、
前記ダミー・ノードを識別するダミー・ポインタと
を含む前記ロックフリー同時ＦＩＦＯキューと
を含む、キューを実装するための装置。
【請求項１０】
前記ダミー・ノードが前記ロックフリー同時ＦＩＦＯキューに含まれず、かつ前記デキュー動作中に前記ダミー・ノードがエンキューされないように、前記ロックフリー同時ＦＩＦＯキューが前記デキュー動作中に２個以上のユーザー・ノードを含む、
請求項９に記載の装置。
【請求項１１】
少なくとも１個のプロセッサを有するディジタル・コンピューティング装置においてキューを実装するためのコンピュータ・プログラムであって、
（ａ）キューの終りにユーザー・ノードをエンキューするステップであって、前記キューが、次のノードへの次のポインタを備える少なくとも１個のダミー・ノードを前記エンキューするステップ（ａ）の前に含み、かつ前記ユーザー・ノードが、次のノードへの次のポインタを備えるところの前記エンキューするステップと、
（ｂ）前記エンキューするステップ（ａ）の後、前記キューから前記ダミー・ノードをデキューするステップと、
（ｃ）前記デキューするステップ（ｂ）の後、前記キューからヘッド・ノードを条件付きでデキューするステップと、
（ｄ）前記条件付でデキューするステップ（ｃ）中に、前記キューが唯一のユーザー・ノードを含むときにのみ前記キューの前記終りに他のダミー・ノードをエンキューするステップと
を前記ディジタル・コンピューティング装置に実行させるコンピュータ・プログラム。
【請求項１２】
コンピュータ読み取り可能な、記録媒体を含む信号担持媒体上に与えられる複数個の実行可能な命令が、前記（ａ）、（ｂ）、（ｃ）および（ｄ）のステップを、前記少なくとも１個のプロセッサを有するディジタル・コンピューティング装置によって実行させる、請求項１１に記載のコンピュータ・プログラム。
【請求項１３】
コンピュータ読み取り可能な、伝送媒体を含む信号担持媒体上に与えられる複数個の実行可能な命令が、前記（ａ）、（ｂ）、（ｃ）および（ｄ）のステップを、前記少なくとも１個のプロセッサを有するディジタル・コンピューティング装置によって実行させる、請求項１１に記載のコンピュータ・プログラム。
【請求項１４】
前記エンキューするステップ（ａ）が、
前記ユーザー・ノードをポイントするようにテール・ノードの前記次のポインタをセットすることによって前記ユーザー・ノードを前記キューの終りにリンクするステップと、
前記ユーザー・ノードをポイントするように前記キューのテール・ポインタを更新するステップと
を含む、請求項１１に記載のコンピュータ・プログラム。
【請求項１５】
前記更新するステップがエンキューするステップ（ａ）中は行われないが、その後のエンキュー動作中もしくはその後のデキュー動作中に行われる、請求項１４に記載のコンピュータ・プログラム。
【請求項１６】
前記条件付でデキューするステップ（ｃ）が、ノードをデキューする際に成功裡に行われるなら、
前記条件付けでデキューするステップ（ｃ）でデキューされたノードの次のポインタをヌルにセットするステップと、
もし前記条件付でデキューするステップ（ｃ）でデキューされるノードがユーザー・ノードなら、前記デキューされたユーザー・ノードを戻すステップと、
もし前記条件付でデキューするステップ（ｃ）でデキューされるノードがダミー・ノードなら、前記条件付でデキューするステップ（ｃ）を再スタートするステップと
を更に含む、請求項１１に記載のコンピュータ・プログラム。
【請求項１７】
前記エンキューするステップ（ａ）、前記デキューするステップ（ｂ）、前記条件付でデキューするステップ（ｃ）およびエンキューするステップ（ｄ）は夫々がロード・リンク／ストア・コンディショナルを使用することを含む、請求項１１に記載のコンピュータ・プログラム。
【請求項１８】
前記エンキューするステップ（ａ）、前記デキューするステップ（ｂ）、前記条件付でデキューするステップ（ｃ）およびエンキューするステップ（ｄ）は夫々がストレージ・オーダリング・フェンスを使用することを含む、請求項１７に記載のコンピュータ・プログラム。  
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概略、デジタル・データ処理分野に関する。特にロード・リンク／ストア・コンディショナル（ＬＬ／ＳＣ）などのプロセッサ同期プリミティブ(primitives)を用いる、同時、ノンブロッキング、ロックフリーのＦＩＦＯキュー（先入れ先出し待ち行列）に関する。
【背景技術】
【０００２】
２０世紀後半には情報革命として知られる現象が始まった。情報革命がどんな一つのイベントや機械より範囲の広い歴史的な発展であるが、ディジタルの電子的なコンピュータよりも情報革命を代表するようになった単一の装置はない。コンピュータ・システムの発展は確かに革命であった。毎年、コンピュータ・システムは速くなるように成長し、より多くのデータを格納し、ユーザーにもっと多くのアプリケーションを提供する。
【０００３】
今日のコンピュータ・システムは典型的には少なくとも一つの中央処理装置（ＣＰＵ）と、情報を格納し、取り出し、転送するのに必要な通信バス、メモリなどサポート用のハードウエアを含む。それはまた入出力コントローラもしくはストレージ・コントローラおよびそれらに結合される装置など、外界と通信するのに必要なハードウエアを含む。その結合される装置は、キーボード、モニタ、テープ・ドライブ、ディスク・ドライブ、およびネットワークに結合される通信線などである。１個もしくは複数個のＣＰＵがそのシステムの心臓部である。それらはコンピュータ・プログラムを含む命令を実行し、その他のシステム・コンポーネントの動作を指示する。
【０００４】
コンピュータ・システムの全体の速度は並列化を増やすことにより典型的には改良され、特に複数個のＣＰＵ（プロセッサとも称する）を採用することによって改良される。集積回路チップ上にパッケージされる個別のプロセッサの控えめなコストは、マルチプロセッサ・システムを実用的なものにする。もっともそのようなマルチプロセッサはシステムにもっと多くの層の複雑さを加えることになる。
【０００５】
コンピュータのハードウエアの観点から、多くのシステムが基本的には同じ態様で動作する。プロセッサは、演算、論理比較、或る箇所から他の箇所へのデータの移動など、非常に簡単な動作を実行することができる。しかし各々の動作は非常に迅速に行われる。複数のレベルの洗練されたソフトウエアは膨大な数のこれらの簡単な動作を実行するようにコンピュータに命令し、コンピュータが複雑なタスクを実行することができるようにする。コンピュータ・システムの新規もしくは改良された性能としてユーザーに認められるものは、高速なハードウエアとともに増進した機能を有するソフトウエアを用い、非常に簡単な動作の同じセットを基本的に実行することによって可能にされる。
【０００６】
先入れ先出しキュー（ＦＩＦＯ待ち行列）は並列のアプリケーションおよびオペレーティング・システムでは広範に使用されている。データはアプリケーションおよびプロセス・スレッドによって頻繁にＦＩＦＯキューに出し入れされる。一般にＦＩＦＯキューはデータを含む異なるメモリ位置の命令されたリストを提供するデータ構造である。そのキューの異なるメモリ位置の各々は一般に「ノード」と呼ばれる。ノードを順序立てて維持するために、各ノードにそのキューの中の次のノードのメモリ位置を識別する（すなわちポイントする、あるいは指し示す）「次の」ポインタが与えられる。そのキューの第１のノードは「ヘッド（先頭）」ノードと呼ばれ、その最後のノードは「テール（末尾）」ノードと呼ばれる。テール・ノードがそのキューの最後のノードなので、テール・ノードの次のポインタは通常はヌル（空）である。そのキューはヘッド・ノードを識別する（即ちポイントする）ヘッド・ポインタとテール・ノードを識別する（即ちポイントする）テール・ポインタとを有する。
【０００７】
或るノードはキューの現在のテール・ノードの後にそれを挿入することによってエンキュー（待ち行列即ちキューに入れる、待ち行列化）され、その結果そのエンキューされたノードがそのキューの新しいテール・ノードになる。従って、或るノードをキューにエンキューするためには、どのノードが現在のテール・ノードであるかをスレッドが判定しなければならない。これを達成するためにスレッドは通常、キューのテール・ポインタを使用する。
【０００８】
或るノードはキューのヘッドでデキューされ（キュー即ち待ち行列から出され）、その結果現在のヘッド・ノードがデキューされ、その次のノードがそのキューの新しいヘッド・ノードになる。従って、キュー上の或るノードをデキューするためには、どのノードが現在のヘッド・ノードであるかをスレッドが判定しなければならない。これを達成するためにスレッドは通常、キューのヘッド・ポインタを使用させる。
【０００９】
前述の通り、アプリケーションおよびプロセスのスレッドがＦＩＦＯキュー上のデータをエンキューおよびデキューする。多数の異なるそのようなスレッドがキューの同時使用をすることができる。キューの同時使用はキューの完全性（インテグリティ、一貫性、整合性）を維持するのを困難にする。それでも、キューのインテグリティはそのキューが遭遇するかもしれない全ての可能な条件に亘って維持されなければならない。  
【００１０】
キューの完全性を維持するために同時アクセスを同期させなければならない。ＦＩＦＯキューを含む同時データ構造のためのアルゴリズムはブロッキングまたはノンブロッキングである。ブロッキング・アルゴリズムは、低速のもしくは遅延されたプロセス（もしくはスレッド）を許容し、これによって高速のプロセス（もしくはスレッド）が同時データ構造上の動作を完了させるのを独立に防止する。ノンブロッキング・アルゴリズムは、１個もしくはそれ以上のアクティブなプロセス（もしくはスレッド）が現在データ構造上の動作を完遂させようとするなら、幾つかの動作が或る限られた数のステップ中に完遂することを保証する。ノンブロッキング・アルゴリズムはブロッキング・アルゴリズムよりも一般には好ましい。何故ならば、ブロッキング・アルゴリズムはプロセッサ・スケジューリング・プリエンプション（先取り）、ページ・フォールト、キャッシュ・ミスといったイベントの発生によりプロセス（もしくはスレッド）が停止されもしくは遅延されるとき大きな性能低下を不都合にも経験することになるからである。
【００１１】
ロックフリー・アルゴリズムも、同時ＦＩＦＯキューを含む共有データ構造のために提案された。ロックフリー・アルゴリズムは、オペレーティング・システムの管理されたロックによって保護されるクリティカル・セクションに頼ることなく共有データ構造の同時更新を許容する。ロックフリー同期の最も一般的な利点の幾つかは、以下を含む。
・ロックベースのアルゴリズムより効果的であること
・マルチプロセッサ・マシーン上での改良されたスケーラビリティ
・インタラプト・ハンドラを含むほとんど全ての環境で使用可能であること
・ノンブロッキング・インプリメンテーションがプライオリティ逆転を自然に回避すること
・非生産的なスピン・ロックとは異なり、進展が生じるのを協働する技法が確保すること
【００１２】
従来からの比較およびスワップもしくは今日のロード・リンクされた／ストア・コンディショナル（例えば、パワーＰＣ  Ｉｄａｒｋ／ｓｔｄｃｘ）などの特別プロセッサ同期プリミティブが、ＦＩＦＯキューおよびＬＩＦＯキュー（後入れ先出し待ち行列）（ＬＩＦＯキューはＬＩＦＯスタックとも呼ぶ）の両方のための効果的なロックフリー・アルゴリズムを実装するのに使用されてきた。同時ＬＩＦＯキューは、実装するのに非常にシンプルであるが、効果的な同時ＦＩＦＯキューはもっとはるかに困難である。
【００１３】
従来の同時キューの効果的な状態は非特許文献１に記述されている。その刊行物にある問題点は以下の通りである。
・別個のリンク・ノードはそのキューにエンキューされたユーザー・ノードごとに割当てられる。このように、特別のリンク・ノードが必要とされるのでそのノードはそのキューに直接はエンキューされない。これはキューのパフォーマンスとともに、スレッドがそのキューを使用するかもしれない態様とを拘束する。この特別のリンク・ノードの割当てがオーバーヘッドを追加し、そしてメモリ割当ての問題による割り込みハンドラのためにこのアルゴリズムを実際的でないものにする。
・伝統的な比較およびスワップ・プリミティブは、クラシカルなＡＢＡ問題（以下で説明する）を防止し、追加のオーバーヘッドを加える。
【００１４】
一般に、この技術分野でよく知られている「ＡＢＡ問題」は、プロセスもしくはスレッドが、ＦＩＦＯキューなどの共有メモリ位置で値Ａを読み出し、新しい値を計算し、そしてこれはそれが続くべきではない場合でさえ続くかもしれないが、もし読み出しと比較およびスワップとの間で一つもしくはそれ以上の他のプロセスが値Ａを値Ｂに変更しそして再び値Ａに戻すならば、比較およびスワップ・プリミティブなどの動作を試みるときに、その「ＡＢＡ問題」が生じる。その日特許文献１は同時のノンブロッキング・キューを記述する。その中で、ＡＢＡ問題はキュー・ポインタに、例えばそのテール・ノードの次のポインタなどの特別の「カウント」フィールドを割当てることによってアドレスされる。従って、例えば任意のスレッドによってテール・ノードが修正されるごとにそのテール・ノードの次のポインタが増分される。もしテール・ノードがデキューされ、他のノード上で再エンキューされたなら、ＡＢＡ問題が普通は生じたであろう場合に、そのキュー上に新しいノードをエンキューしようとするスレッドは、次のポインタが以前と同じ値をなおも有するとしても、それがそのテール・ノードと信じるべきものの次のポインタ「カウント」フィールドを認識するであろう。従って、そのスレッドはそのエンキュー動作を完遂させず、これによってＡＢＡ問題が生じるのを防ぐであろうが、特別の「カウント」フィールドを提供するのに必要な追加のオーバーヘッドがかかる。
【００１５】
特許文献１は非特許文献１にある問題の幾つかを少なくとも部分的に解決するが、デキュー・タイミング窓を紹介する。その特許文献１の問題は以下を含む。
・ＡＢＡ問題に対する解決策は改良されるが、キュー特有の数が、そのノードを含むキューを個別に識別するのに必要とされる。
・そのキューのコード中のタイミング窓は、単一のユーザー・ノードのみがエンキューされるときに、空のキューを不正に検知する。すなわち、もしもダミー・ノードが第１のスレッドにより一時的にデキューされ単一のユーザー・ノードを残すなら、第２のスレッド上のデキューは空のキューを見ることになる。これは幾つかのアプリケーションを不適正に機能させ得る。
・特許文献１にその発明がノンブロッキング・アトミック比較およびスワップ（ＣＡＳ）命令を用いるＦＩＦＯキューに関係すると述べているが、その特許文献にはＣＡＳ命令が記述されておらず、そのフロー・ダイアグラムにも用いられていない。・幾つかの追加のストレージ・オーダリング・フェンスが特許文献１に開示されたアルゴリズムを一貫性の弱いプロセッサ（以下で説明する）上で稼動するのに必要となろう。
【００１６】
高速のプロセッサの開発が、一貫性の弱いプロセッサ・アーキテクチャの創作につながった。これは或る量のスペキュレーション（推測）ブランチ・スペキュレーションなど）を許容し、順序外れの（アウトオブオーダー）命令の実行を許容する。これらのタイプの実行を可能にするために、あるグループ中の命令相互間に依存性が存在しないときそのグループへの一連の命令をプロセッサが割当てる。あるグループ中の命令を並列にもしくは順序外れで（即ち前の命令より前に後の命令を実行するなど）実行することができる。しかし、データの依存性により、特にロードおよびストア命令の場合、命令シーケンスの中で、異なるグループ中の命令は正しい処理結果を得るためのプログラムの順序で実行しなければならない。従って、追加のオーダリング・フェンスは特許文献１に開示されるアルゴリズムのようなアルゴリズムを、一貫性の弱いプロセッサ上で実行することが必要になろう。しかし、特許文献１は一貫性の弱いプロセッサ上でそのアルゴリズムを動作可能にするのに必要な追加のストレージ・オーダリング・フェンスを苦労して作り上げてはいない。
【００１７】
ドロップオフ（降り）キューとして同時ＬＩＦＯキュー（スタック）を使用するのは普通ではないが、通常のイン・オーダー（順序正しい）タスク処理が行われ得る前にＬＩＦＯキューをＦＩＦＯキューに変換しれなければならない。例えば、特許文献２はそのようなアプローチを開示する。このアプローチは以下のような多くの欠点がある。
・ＬＩＦＯキューのＦＩＦＯキューへの変換がパフォーマンスに関して高価になり得る。
・単一のノードがデキューされ得る前に、ＬＩＦＯキュー中の全てのノードをＦＩＦＯオーダーに変換しなければならない。
・単一のタスクがＬＩＦＯからＦＩＦＯへの変換を実行しなければならない。マルチプロセッサ・システム上では、この変換がボトルネックとなり得る。
【特許文献１】米国特許第６，８８９，２６９号公報
【特許文献２】米国特許第５，６７１，４４６号公報
【非特許文献１】Michael ほか著のSymposium of Principles of DistributedComputing（分散コンピューティングの原理のシンポジューム、１９９６年の「Simple, Fast, and Practical Non-Blocking and Blocking ConcurrentAlgorithms（シンプルで、速い、プラクティカルなブロッキング同時アルゴリズム）」
【発明の開示】
【発明が解決しようとする課題】
【００１８】
従って、同時の、ノンブロッキングの、ロックフリーのＦＩＦＯキューを提供するための改良された機構の必要性が存在する。
【課題を解決するための手段】
【００１９】
本発明の好適な実施例によれば、キューが空になるのを防ぐのに必要なときにのみ、ダミー・ノードが同時の、ノンブロッキングの、ロックフリーのＦＩＦＯキューにエンキューされる。ダミー・ノードはデキュー動作中に、そしてデキュー動作中は単一のユーザー・ノードを含むときにのみエンキューされるだけである。これはキュー中にダミー・ノードを常に保持している従来の機構に対しオーバーヘッドを減じる。ユーザー・ノードはそのキューに直接にエンキューされ、任意のスレッドによりオンデマンドで直ちにデキューされることができる。好適には、エンキュー動作およびデキュー動作がロード・リンク／ストア・コンディショナル（ＬＬ／ＳＣ）同期プリミティブの使用を含む。これが特有の数、例えばあるキューに特有の数を使用する必要なしにＡＢＡ問題を解決し、比較およびスワップ（ＣＡＳ）同期プリミティブの使用を含む従来の機構とコントラストをなし、特有の数の使用を通じてＡＢＡ問題をアドレスする。更に、ストレージ・オーダリング・フェンスが、そのアルゴリズムが一貫性の弱いプロセッサ上で稼動するのを許容するように好適には挿入される。
【００２０】
本発明の前述その他の特徴および利点は、添付図面とともに説明するような、本発明の好適な実施例についての以下のもっと具体的な記述から明らかとなろう。
本発明の好適な実施例を添付の図面に沿って以下で説明するが、図面で同様な参照番号は同様な要素（エレメント）を指す。
【発明を実施するための最良の形態】
【００２１】
１．０  概要
本発明の好適な実施例によれば、同時の、ノンブロッキングの、ロックフリーのＦＩＦＯキューが標準のロード・リンクされた／ストア・コンディショナル（ＬＬ／ＳＣ）同期プリミティブを用いて実施される。比較およびスワップ（ＣＡＳ）同期プリミティブの代わりにロード・リンクされた／ストア・コンディショナル（ＬＬ／ＳＣ）同期プリミティブを用いると、或る種の特有の数、例えば或るキューに特有の数を必要とせずにＡＢＡ問題が解決され、もっと効率のよいカスタマイズされたコードを許容する。従って、本発明の好適な実施例は比較およびスワップ同期プリミティブを使用し特有の数を使用することを通じてＡＢＡ問題を解決することを含む従来の機構とコントラストをなす。またロード・リンクされた／ストア・コンディショナル（ＬＬ／ＳＣ）同期プリミティブを注意深く使用することによって、もっと効率の良いコードが発生され得る。
【００２２】
好適には、本発明の実施例によるアルゴリズムは、一貫性の弱いプロセッサ上で効率的なかつ正確な実行を可能にするように注意深く挿入されたストレージ・オーダリング・フェンス（例えば、ＰｏｗｅｒＰＣ同期命令）を使用する。
【００２３】
本発明の実施例によるアルゴリズムは協調的である。もしエンキューが遅れると、その後のエンキューもしくはデキュー動作がその現在のエンキューを完遂するように助ける。そのエンキューは２ステップ・プロセスである。
１．新しいノードをそのキューの終りにリンクせよ。
２．そのキューのテール・ポインタを新しいノードを指し示すために更新せよ。もし現在のエンキューが遅れるなら、例えば現在のエンキューが前述のリストされたステップ１およびステップ２の間に生じる高いプライオリティのタスクもしくはページ・フォールトによってプリエンプトされるなら、その後のエンキューもしくはデキュー動作は現在のエンキューのためのステップ２を完遂することができる。
【００２４】
エンキューおよびデキューの同時動作を許容するためにダミー・ノードを使用することは従来からよく知られた技法であるが、従来のアルゴリズムの現在の状態はそのキュー中の常時ダミー・ノードを保持する。本発明の好適な実施例によれば、キューにダミー・ノードがエンキューされるのは、キューが空になるのを防止するに必要なときだけである。即ち、ダミー・ノードがエンキューされるのは、デキュー動作中、およびそのキューがデキュー動作中単一のユーザー・ノードを含むときのみである。もし少なくとも２個のユーザー・ノードがエンキューされるなら、ダミー・ノードをエンキューする必要はない。これはキュー中にダミー・ノードを常時保持している特許文献１に開示されるような従来の機構に比べてオーバーヘッドを減じる。
【００２５】
この効果を示すために、本発明の好適な実施例（その詳細は「２．０  詳細な説明」に後述）によるアルゴリズムを用いた場合と特許文献１に開示されたアルゴリズムを用いた場合とで、１６個のユーザー・ノードが１０秒の期間の間に１６個のスレッドによりエンキューおよびデキューが反復される場合のテストが行われた。そのテストの結果を以下の表１に示す。
【表１】
2008123516.tif 000003
【００２６】
表１に示すように、特許文献１に記述されるアルゴリズムは１７回のエンキューごとに１回、ダミー・ノードをエンキューする。これに比べて、本発明の実施例によるアルゴリズムはテスト・ランの終りに１回、ダミー・ノードを再エンキューするだけである。また、本発明の好適な実施例によるアルゴリズムは特許文献１に開示されるアルゴリズムよりも１０秒の期間中５０％よりも多くのユーザー・ノードをエンキューすることができる。更に特許文献１に記述されるアルゴリズムは、前に説明したようにそのデキュー・タイミング・ウインドウの不備によりテスト・ランの終りにそのキュー中の１３個のユーザー・ノードを不都合にも残す。
【００２７】
一般にテストが示したのは、本発明の好適な実施例によるアルゴリズムが、プロデューサーのスレッド（エンキュー）およびカスタマー・スレッド（デキュー）がほぼ同じ割合で実行（ラン）するときダミー・ノードを稀にエンキューする。
【００２８】
本発明の好適な実施例によれば、ユーザー・ノードはキューに直接にエンキューされ、任意のスレッドによりオンデマンドで直ちにデキューされることが可能である。
【００２９】
本発明の好適な実施例によるアルゴリズムは、低レベルのカーネル割込みハンドラを含む、見かけ上全てのプログラミング環境で使用することができる。従って、本発明の好適な実施例は、非特許文献１などに開示されるような、特別のリンク・ノード・メモリ管理を必要とし、そのために利用が制限される従来の機構とコントラストをなす。その結果、そのような従来の機構は、例えばメモリ割当て制限を有する割込みハンドラには十分に適合しない。
【００３０】
２．０  詳細な説明
本発明の好適な実施例のコンピュータ・システムの実装例は特定のコンピュータ・システム１００、例えばＩＢＭｅＳｅｒｖｅｒ  ｉＳｅｒｉｅｓ（インターナショナル・ビジネス・マシーンズ・コーポレーションの登録商標）またはＳｙｓｔｅｍ  ｉ  コンピュータ・システムについて図１に沿って説明する。しかし、当業者には理解されるように、本発明のＦＩＦＯキュー、方法、装置およびコンピュータ・プログラムは、コンピュータ・システムが複雑なマルチ・ユーザー・コンピューティング装置、単一のユーザー・ワークステーション、ＰＣもしくは埋込み制御システムであるか否かに関係なく、任意のコンピュータ・システムに等しく適用できる。図１に示すように、コンピュータ・システム１００は、１個もしくはそれ以上のプロセッサ１０１Ａ、１０１Ｂ、１０１Ｃおよび１０１Ｄ、メイン・メモリ１０２、マス・ストレージ・インターフェース１０４、ディスプレイ・インターフェース１０６、ネットワーク・インターフェース１０８ならびにＩ／Ｏ装置インターフェース１０９を備える。これらのシステム・コンポーネントはシステム・バス１１０の使用を通じて相互接続される。
【００３１】
図１はコンピュータ・システム１００の代表的で主要なコンポーネントを高レベルで描くことを企図している。それは図１で個別のコンポーネントが図１で表されるよりももっと複雑であること、またそのようなコンポーネントのタイプおよび構成が変わり得ることお理解されたい。例えば、コンピュータ・システム１００が図示のものとは異なる数のプロセッサを備えていてもよい。
【００３２】
マス・ストレージ・インターフェース１０４がコンピュータ・システム１００にマスストレージ装置（例えば直接アクセス・ストレージ装置即ちＤＡＳＤ１１２）を接続するのに使用される。ＤＡＳＤ１１２の一つの特定の型は、読出し可能でかつ書込み可能なＣＤ  ＲＯＭドライブであって、ＣＤ  ＲＯＭ１１４にデータを読み書きしてもよい。
【００３３】
好適な実施例によるメイン・メモリ１０２はデータ１１６、オペレーティング・システム１１８およびエンキュー／デキュー機構１２０を備える。エンキュー／デキュー機構１２０は図１のオペレーティング・システム１１８とは別個に独立して示されているが、オペレーティング・システム１１８および／もしくはカーネル中に実装されているエンキュー／デキュー機構１２０に好適な実施例は明確に拡張できる。従来からよく知られているように、カーネルがオペレーティング・システム１１８中に集積されていて、オペレーティング・システム１１８および他のプログラムにカーネル・レベルのサービスを提供してもよい。例えば、エンキュー／デキュー機構１２０がカーネルに含まれるシステム・タスク・ディスパッチャおよび／もしくは割込みハンドラ中に実装されていてもよい。更に、エンキュー／デキュー機構１２０はアプリケーション・ソフトウエア、ユーティリティもしくは他の型のソフトウエアを単独でもしくは一緒に好適な実施例の範囲内に実装することもできる。例えば、本発明はデータベース、ネットワーキング、タスク・ディスパッチングおよびストレージ・マネージメントなど広範囲のアプリケーションに適用可能である。                  
【００３４】
コンピュータ・システム１００は、メイン・メモリ１０２およびＤＡＳＤ装置１１２など複数個の小さなストレージ・エンティティをアクセスする代わりに、単一の大きなストレージ・エンティティをあたかもアクセスしているようにコンピュータ・システム１００のプログラムが振舞うのを許容する、よく知られた仮想アドレス機構を使用する。従って、データ１１６、オペレーティング・システム１１８およびエンキュー／デキュー機構１２０がメイン・メモリ１０２中に存在することを示されているが、当業者はこれらのアイテムが全てメイン・メモリ１０２に同時に必ずしも完全に含まれていないことを認識している。「メモリ」と言う用語がコンピュータ・システム１００の仮想メモリ全体をおおよそ指すようにここでは使用されていることに留意されたい。
【００３５】
データ１１６は、コンピュータ・システム１００に於いて任意のプログラムへの入力もしくはそこへの出力として働く任意のデータを表す。オペレーティング・システム１１８は、ＯＳ／４００もしくはＩＢＭｉ５／ＯＳのようにこの業界で知られたマルチタスクのオペレーティング・システムである。しかし、当業者は本発明の趣旨および範囲がいずれか一つのオペレーティング・システムに限定されるのではないことを理解するであろう。  
【００３６】
本発明の好適な実施例によれば、以下で詳細に説明するように、エンキュー／デキュー機構１２０が、同時ノンブロッキング・ロックフリーＦＩＦＯキューを実装するための機能性を提供する。また本発明の好適な実施例によれば、エンキュー／デキュー機構１２０が、図７に示す「キュー（Ｑｕｅｕｅ）」クラスおよび「ノード（Ｎｏｄｅ）」構造のデータ・レイアウト、図８に示す「エンキュー（ｅｎｑｕｅｕｅ）」機能用のコード、図９に示す「エンキューステップ２（ｅｎｑｕｅｕｅＳｔｅｐ２）」機能用のコード、図１０に示す「デキュー（ｄｅｑｕｅｕｅ）」機能用のコード、および図１１に示す「エンキューダミー（ｅｎｑｕｅｕｅＤｕｍｍｙ）」機能用のコードを含む。エンキュー／デキュー機構１２０は、予めプログラムされていてもよいし、手でプログラムされてもよいし、また記録媒体（例えば、ＣＤ  ＲＯＭ１１４）から転送されても、インターネット（例えば、ネットワーク１２６）を介してダウンロードされてもよい。
【００３７】
プロセッサ１０１Ａ、１０１Ｂ、１０１Ｃおよび１０１Ｄ（これらの全体を「プロセッサ１０１」とここでは称する）は、１個以上のマイクロプロセッサおよび／もしくは集積回路から構成されることができる。プロセッサ１０１はメイン・メモリ１０２に格納されたプログラム命令を実行する。メイン・メモリ１０２はプロセッサ１０１がアクセスすることができるデータおよびプログラムを格納する。コンピュータ・システム１００が始動すると、プロセッサ１０１はオペレーティング・システム１１８を作り上げるプログラム命令を初期に実行する。オペレーティング・システム１１８はコンピュータ・システム１００のリソース（資源）を管理する高度なプログラムである。これらのリソースの幾つかは、プロセッサ１０１、メイン・メモリ１０２、マス・ストレージ・インターフェース１０４、ディスプレイ・インターフェース１０６、ネットワーク・インターフェース１０８、Ｉ／Ｏ装置インターフェース１０９およびシステム・バス１１０である。
【００３８】
コンピュータ・システム１００が４個のプロセッサおよび単一のシステム・バスを含むように示されているが、異なる数のプロセッサおよび／もしくは複数のバスを有するコンピュータ・システムを用いて本発明が実施されてもよいことを当業者には理解する。更に、好適な実施例で使用されるインターフェースは、プロセッサ１０１から、数値計算処理をオフロードするのに使用される別個の、完全にプログラムされたマイクロプロセッサを含む。しかし類似する機能を実行するのにＩ／Ｏアダプタを単に使用するコンピュータ・システムに本発明を等しく適用できることを当業者は理解するであろう。
【００３９】
ディスプレイ・インターフェース１０６はコンピュータ・システム１００に１個以上のディスプレイ１２２を直接接続するのに使用される。これらのディスプレイ１２２は、非インテリジェントな（即ち計算能力のない）ターミナルかまたは完全にプログラム可能なワークステーションであってもよいが、システム管理者およびユーザー（ここでは「オペレータ」ともいう）がコンピュータ・システム１００と通信するのを許容するのに使用される。しかし、ディスプレイ・インターフェース１０６が１個以上のディスプレイ１２２と通信するのをサポートするように設けられているが、コンピュータ・システム１００はディスプレイ１２２を必ずしも必要としない。ユーザーおよびプロセッサとの全ての必要な相互作用がネットワーク・インターフェース１０８を介して行われても良いからである。
【００４０】
ネットワーク・インターフェース１０８は他のコンピュータおよび／もしくはワークステーション１２４をコンピュータ・システム１００にネットワーク１２６を介して接続するのに使用される。本発明はコンピュータ・システム１００が他のコンピュータ・システムおよび／もしくはワークステーションにたとえどのように接続されようとも、今日のアナログおよび／もしくはディジタル技法を用いて、あるいは将来のある種のネットワーク機構を介してネットワーク接続１２６が行われるか否かに拘わらず等しく適用できる。更に多くの異なるネットワーク・プロトコルがネットワークを実装するのに使用できる。これらのプロトコルはコンピュータがネットワーク１２６を介して通信することができるようにする特別のコンピュータ・プログラムである。ＴＣＰ／ＩＰ（伝送制御プロトコル／インターネット・プロトコル）は適切なネットワーク・プロトコルの一例である。
【００４１】
Ｉ／Ｏ装置インターフェース１０９はいろいろな入出力装置のいずれかにインターフェースを提供する。
【００４２】
ここで、本発明の実施例が完全に機能的なコンピュータ・システムのコンテキストで記述されているが、当業者は本発明がいろいろな形式のプログラムとして配布されること、また本発明がその配布を実際に行うのに使用される信号担持媒体の特定の型に拘わらず等しく適用できることに留意することが重要である。適切な信号担持媒体の例は、フレキシブル・ディスクおよびＣＤ  ＲＯＭ（例えば、図１のＣＤ  ＲＯＭ１１４）のような記録可能型の媒体と、ディジタル・アナログ通信リンク（例えば、図１のネットワーク１２６）のような伝送型の媒体とを含む。
【００４３】
図２は本発明の好適な実施例によるＦＩＦＯキュー２００の初期状態のブロック図である。一般に、ＦＩＦＯキュー２００は図１に示すメイン・メモリ１０２のようなデータを含むメモリ中の位置である一連のノードを特定する格納されたリストを含む。ダミー・ノードは外部のスレッドには利用できない。他方、ユーザー・ノードは外部のプロセスもしくはアプリケーション・スレッドによってエンキューおよびデキューされることができる。
【００４４】
図２に示すその初期状態（即ち、それが構成された直後）では、ＦＩＦＯキュー２００を含む格納リストが以下のように特定される。ダミー・ノード２０２が次のポインタ２０４を有し、ヘッド・ポインタ２０６がダミー・ノード２０２をポイントし、テール・ポインタ２０８がダミー・ノード２０２をポイントし、そしてダミー・ポインタ２１０がダミー・ノード２０２をポイントする。このように、キューのヘッド、テールおよびダミーのポインタが全てダミー・ノード２０２をポイントする。本発明の好適な実施例によれば、ダミー・ノードはＦＩＦＯキュー２００が論理的に空にならないように維持するためにだけエンキューされる。ＦＩＦＯキュー２００はダミー・ノードだけがエンキューされるときに「論理的に空」である。このときダミー・ノード２０２の後に次のノードがないので、ダミー・ノードの次のポインタ２０４は好適には「ヌル（ＮＵＬＬ）」にセットされる。
【００４５】
図３は本発明の実施例によるエンキュー動作を示す。そこではユーザー・ノード３０２が図２に示すＦＩＦＯキュー２００の初期状態、即ち論理的に空のキューにエンキューされる。ユーザー・ノード３０２は次のポインタ３０４を備える。この時点でユーザー・ノード２０２の後には次のノードがないので、ユーザー・ノードの次のポインタ３０４は「ヌル」にセットされるのが好ましい。ダミー・ノード２０２は、例えＦＩＦＯキュー２００が論理的に空でなくても、自然にデキューされるまでＦＩＦＯキュー２００に留まる。本発明の好適な実施例によれば、図３に示すエンキュー動作は２回のステップで生じる。先ず、エンキュー動作は新しいノード、即ちユーザー・ノード３０２をＦＩＦＯキュー２００の終りにリンクする（ステップ３５１）。これはユーザー・ノード３０２をポイントするようにダミー・ノードの次のポインタ２０４をセットすることによって達成される。それから、新しいノード、即ちユーザー・ノード３０２をポイントするようにキューのテール・ポインタ２０８が更新される（ステップ３５２）。
【００４６】
図４、図５および図６は全体で本発明の好適な実施例によるデキュー動作を示すブロック図である。具体的には、図４ないし図６は全体で、どのようにダミー・ノードがデキューされ、それから最後のユーザー・ノードがデキューされるときに再エンキューされるかを説明する。図４では、ダミー・ノード２０２が、図３に示す状態にあるＦＩＦＯキュー２００からデキューされる。図５では、図４に示す状態にあるＦＩＦＯキュー２００にダミー・ノードが再エンキューされる。図６では、図５に示す状態にあるＦＩＦＯキュー２００からユーザー・ノード３０２がデキューされる。
【００４７】
本発明の好適な実施例によれば、図４ないし図６に示すシナリオが例外であることを理解されたい。これは定常状態でキューに少なくとも２個のユーザー・ノードがあると仮定するなら、ダミー・ノードが稀にしかエンキューされないからである。図４ないし図６に示すシナリオは例外ではあるが、本発明の好適な実施例に従ってどのようにダミー・ノードが使用されるかという視点から理解するためにこのシナリオは重要である。
【００４８】
図４では、ダミー・ノード２０２は、図３に示す状態のＦＩＦＯキュー２００からデキューされる。ダミー・ノード２０２がデキューされるのはそれがＦＩＦＯキュー２００における最初のノードだからである。ダミー・ノード２０２はこの時点でとっておく。本発明の好適な実施例によれば、ダミー・ノード２０２のデキュー動作は以下のように行われる。キューのヘッド・ポインタ２０６はユーザー・ノード３０２をポイントするようにセットされる（ステップ４５１）。更に、ダミー・ノードの次のポインタ２０４がヌルにセットされる（ステップ４５２）。
【００４９】
図５では、ダミー・ノードが図４に示す状態のＦＩＦＯキュー２００に再エンキューされる。再エンキューされたダミー・ノードはダミー・ノード４０２として図５に示す。ダミー・ノード４０２は好適にはとっておいたダミー・ノード２０２であるが、別のダミー・ノードでもよい。いずれにせよダミー・ノードは最後のユーザー・ノードがデキューされ得る前に再エンキューされなければならない。本発明の好適な実施例によれば、ダミー・ノード４０２の再エンキューは以下のように行われる。現在のテール・ノードの次のポインタ３０４はダミー・ノード４０２をポイントするようにセットされる（ステップ４５３）。このようにして、ダミー・ノード４０２がＦＩＦＯキュー２００の終りにリンクされる。それから、キューのテール・ポインタ２０８がダミー・ノード４０２をポイントするようにセットされる（ステップ４５４）。更に、この時点でダミー・ノード２０２の後に次のノードがないので、ダミー・ノードの次のポインタ４０４はヌルにセットされる。
【００５０】
図６では、ユーザー・ノード３０２が図５の状態のＦＩＦＯキュー２００からデキューされる。ユーザー・ノード３０２がデキューされると、ＦＩＦＯキュー２００にはダミー・ノード４０２だけが残る。本発明の好適な実施例によると、ユーザー・ノード３０２のデキューは以下のように行われる。キューのヘッド・ポインタ２０６がダミー・ノード４０２をポイントするようにセットされる（ステップ４５５）。また、ユーザー・ノードの次のポインタ３０４がヌルにセットされる（ステップ４５６）。
【００５１】
本発明の好適な実施例によれば、キューは、キューのヘッド・ポインタ、キューのテール・ポインタおよびノードの次のポインタという３個の関連しないポインタをアトミックに更新しなければならない。３個の全てのポインタは同時にはアトミックに更新できないので、これを解決困難な問題にしている。ロード・リンクされた／ストア・コンディショナルな同期プリミティブが１個のポインタをアトミックに更新し、ロード・リンクおよびストア・コンディショナル間の、関連しない共有メモリのテスト（ロード）を許容する。比較およびスワップ（ＣＡＳ）同期プリミティブが代替手段として利用できるであろうが、ＣＡＳ同期プリミティブに特有のＡＢＡ問題にアドレスする必要があり、その実施はかなり効果的でなくなる。
【００５２】
図７は本発明の好適な実施例による「ノード（Ｎｏｄｅ）」構造および「キュー（Ｑｕｅｕｅ）」クラスのデータ・レイアウトを説明するのに使用される例示的な擬似コードの図表である。ノード構造を行５０１で示す。「キュー」クラスは行５０２で示し、以下の機能を宣言する。エンキュー（ｅｎｑｕｅｕｅ）、「エンキューステップ２（ｅｎｑｕｅｕｅＳｔｅｐ２）」、デキューおよび「エンキューダミー（ｅｎｑｕｅｕｅＤｕｍｍｙ）」である。行５０３のところのエンキュー機能は新しいノードをエンキューするためのパブリックなインターフェースである。行５０５の「エンキューステップ２」機能はエンキュー動作の第２の半分を実行する（即ち「エンキューステップ２」機能がテール・ポインタを更新する）プライベートな機能である。行５０４のデキュー機能はノードをデキューするためのパブリックなインターフェースである。行５０６の「エンキューダミー」機能は必要であればダミー・ノードをエンキューする。
【００５３】
ノードがユーザー・ノードもしくはダミー・ノードのいずれかでもよい。ユーザー・ノードはユーザーによって割当てられ、ユーザー特有のデータを含む。１個のダミー・ノードがキューに対し割当てられ、ユーザーには見えない。
【００５４】
図７に示す「キュー」クラスおよび「ノード」構造のデータ・レイアウトが例示的なものであることが当業者は理解できよう。他の実施例も本発明の範囲内である。例えば、「キュー」クラスはユーザーの「ノード」構造のレイアウトを一般化するためのテンプレート・パラメータとして「ノード」を特定するテンプレート・クラスとして実施され得る。簡潔にするため、非テンプレート・クラスが示されている。
【００５５】
エンキュー動作は以下の２個のステップのプロセスである。
１．新しいノードをキューの終りにリンクする。
２．その新しいノードをポイントするようにキューのテール・ポインタを更新する。
第１のステップ、即ち新しいノードをキューの終りにリンクするというステップは、図７の「キュー」クラスにおける行５０３で指定したエンキュー機能に対応し、図８に関連して以下で詳細に説明する。第２のステップ、即ちその新しいノードをポイントするようにキューのテール・ポインタを更新するステップは、図７の「キュー」クラスにおける行５０５で宣言した「エンキューステップ２」機能に対応し、図９に関連して以下に詳細に説明する。一般に、エンキュー動作は少なくとも１個のノードがキュー中に常にエンキューされていると常に仮定する。
【００５６】
図８ないし図１１に図表化した例示の擬似コードが説明のためであり、本発明を制限する意図はないことを理解されたい。他の例が本発明の趣旨および範囲内であることは当業者が理解できよう。例えば、種々のステップが図８ないし図１１に好ましい順序で開示される。しかしその種々のステップが図示したのとは互いに異なるタイミングで生じたり、同時に生じたりしてもよいことは理解されたい。更に、当業者はそれらのステップの一つもしくは複数を省いてもよいことを理解できよう。
【００５７】
図８は、図７の「キュー」クラスにおける行５０３で宣言したエンキュー機能を説明するのに使用される例示の擬似コードの図表である。行６０１では、新しいノードがキューの終りに引き続きリンクされるまでループし続けるコードでもってエンキュー機能が開始する。行６０２では、キューのテール・ポインタのスナップショットが取られる。キューのテール・ポインタは常に「非ヌル（ｎｏｎ−ＮＵＬＬ）」とみなされる。何故ならば少なくとも１個のノードが常にエンキューされるからである。行６０３では、テール・ノードの次のポインタのスナップショットが取られ、そしてテール・ノードの次のポインタに何か格納するものがあるか検知するように予約がセットされる。行６０４では、テール・ノードの次のポインタはそれが（行６０５で）テストされる前に、現在であることを確実にするために、一貫性の弱いプロセッサにストレージ・オーダリング・フェンスが必要とされる。行６０５では、もしテール・ノードが変更されていなければ、現在のテール・ノードで以ってなおも作業しており、キューのテール・ポインタとテール・ノードの次のポインタが符合していることを意味する。もしテールが変更してしまったなら、エンキュー機能は行６０１で再スタートする。
【００５８】
行６０５．１では、現在のテール・ノードの次のポインタが「非ヌル」であれば、このことはエンキュー動作が部分的に終了し、そのテールが更新される必要があることを意味する。従って、「エンキューステップ２」（図９に関連して以下で詳細に説明する）が呼び出され、その部分的なエンキューを完了させるのを助ける。前のエンキューは次のエンキューが開始し得る前に完了していなければならない。従って、エンキュー機能は行６０１で再開する。
【００５９】
行６０５．２では、キューの終りに次のノードを条件付きでリンクしようとエンキュー機能が試みる。このストア・コンディショナル（格納条件）は、もし他のスレッドがノードを現在エンキューしているなら、フェール（失敗）してもよい。
【００６０】
行６０６では、エンキュー機能の最後のステップが「エンキューステップ２」（図９に関連して以下で説明する）を呼び出し、これによって新しいノードをポイントするようにキューのテール・ポインタを更新する。
【００６１】
図９は、図７の「キュー」クラスにおける行５０５で宣言された「エンキューステップ２」機能を説明するのに使用される例示の擬似コードの図表である。「エンキューステップ２」機能は、部分的なエンキューを完遂するのを助けるためにエンキューおよびデキューの両方の機能によって呼び出され得る。行７０１で、「エンキューステップ２」機能が、テールが更新されるまでループし続けるコードで以って開始する。これはマルチプル・スレッドによって同時に実行され得る協調作業である。だから、このスレッドがテールを更新できる前に他のスレッドがそれを更新することも可能であり、このスレッドが更新をする必要はない。行７０２では、キューのテール・ポインタのスナップショットがとられ、キューのテール・ポインタに何かストアするものがあるか検知するように予約がセットされる。行７０３では、テール・ノードの次のポインタが現在であることを確実にするために、一貫性の弱いプロセッサのためにストレージ・オーダリング・フェンスが必要とされる。行７０４では、テール・ノードの次のポインタのスナップショットが取られる。行７０５では、もしテール・ノードの次のポインタがヌルなら、ループから出る。何故ならばテールは他のスレッドによって既に更新されていりからである。行７０６では、「エンキューステップ２」機能がキューのテール・ポインタを次のノードまで条件付きでスイングしようと試みる。もし他のスレッドが現在実行している「エンキューステップ２」であれば、ストア・コンディショナル（格納条件）は合わないかもしれない。
【００６２】
デキュー動作はエンキュー動作よりも少し複雑であるかもしれない。デキューで考慮することは以下である。
・もしダミー・ノードがデキューされるなら、それをとっておき、次のノードをデキューしようとする。
・もしただ１個のユーザー・ノードがエンキューされるなら、ユーザー・ノードをデキューする前にダミー・ノードをエンキューする。キューは決して空にしてはならない。
・もしヘッド・ノードが部分的にエンキューされるなら、エンキューを完遂するのを助ける。現在のヘッド・ノードはそれが完全にエンキューされるまでデキューされることができない。
・もしキューが論理的に空なら、「ヌル」に戻る。前に述べた通り、ダミー・ノードだけがエンキューされるとき、キューは論理的に空である。
【００６３】
図１０は、図７の「キュー」クラスにおける行５０４で宣言されたデキュー機能を説明するのに使用される例示的な擬似コードである。行８０１では、デキュー機能は、ユーザー・ノードが成功裡にデキューされもしくは論理的に空のキューが検知されるまで、ループし続けるコードで以って開始される。行８０２では、キューのヘッド・ポインタのスナップショットが取られ、キューのヘッド・ポインタに何か格納するものがあるか検知するために予約がセットされる。行８０３では、ヘッド・ノードの次のポインタおよびキューのテール・ポインタが現在であることを確実にするために、一貫性の弱いプロセッサのためにストレージ・オーダリング・フェンスが必要とされる。行８０４では、ヘッド・ノードの次のポインタのスナップショットが取られる。行８０５では、もしキューのヘッドおよびテールのポインタが等しければ、キューの状態はノードがデキューされるのを許容しないであろう。ノードがデキューされるのを許容するためにキューの状態を変更するように３つの行為のうちの一つを行う。これらの３つの行為は、行８０５．１, ８０５．２ および８０５．３に夫々示される。
【００６４】
行８０５．１では、もしキューの中のノードがダミー・ノードなら、キューは論理的に空である。キューのヘッド・ポインタが変更されていないことを検証するためにストア・コンディショナルが行われる。もしヘッドが変更していなければ、デキュー機能はヌルに戻り、そのキューが空であることを示す。もしヘッドが変更していれば、デキュー機能が行８０１で再スタートする。
【００６５】
行８０５．２では、キューの中の唯一のノードがユーザー・ノードであれば、「エンキューダミー」機能（図１１に関連して以下で説明する）がダミー・ノードをエンキューするために呼び出される。ダミー・ノードがエンキューされた後、ユーザー・ノードがデキューできる。従って、一旦。ダミー・ノードがエンキューされると、デキュー機能が行８０１で再スタートする。
【００６６】
行８０５．３では、もし第２のノードが部分的にエンキューされるなら、「エンキューステップ２」機能（図９に関して既に説明した）が呼び出され、これによってキューのテール・ポインタを更新することによるエンキューの完遂を助ける。一旦、「エンキューステップ２」機能が完遂すると、行８０１でデキュー機能が再スタートする。
【００６７】
行８０６で、デキュー機能がヘッド・ノードを条件付でデキューしようとする。もし他のスレッドがそのノードを同時にデキューするなら、ストア・コンディショナル（格納条件）は合わないかも知れない。もしストア・コンディショナルが合うなら、以下のステップが行われる。
【００６８】
行８０６．１で、デキュー・ノードの次のポインタがヌルにセットされる。これはデキューされたノードが再度エンキューされる準備をする。
【００６９】
行８０６．２で、もしデキューされたノードがユーザー・ノードであったなら、ユーザー・ノードは呼び出し元に戻される。他方、行８０６．３で、もしデキューされたノードがダミー・ノードであったなら、そのダミー・ノードは取っておかれ、ユーザー・ノードをデキューするためにデキュー機能が行８０１で再スタートする。
【００７０】
図１１は図７の「キュー」クラスにおける行５０６で宣言された「エンキューダミー（ｅｎｑｕｅｕｅＤｕｍｍｙ）」機能を説明するのに使用される例示の擬似コードの図表である。キューが単一のユーザー・ノードを含むなら、「エンキューダミー」はダミー・ノードをエンキューするだけである。行９０１で、「エンキューダミー」機能は、ダミー・ノードが成功裡にエンキューされるか、またはダミー・ノードが最早エンキューされる必要がなくなるまでループし続けるコードで以って開始する。行９０２では、キューのテール・ポインタのスナップショットが取られる。行９０３では、テール・ノードの次のポインタが取られ、テール・ノードの次のポインタに何かストアされるものがあるか検知するように予約がセットされる。行９０４では、キューのヘッドおよびテールのポインタが現在か確認するために一貫性の弱いプロセッサのためのストレージ・オーダリング・フェンスが必要とされる。行９０５では、ダミー・ノードがまだ加えられる必要があることを「エンキューダミー」機能が検証する。第１に、テールが変更していないことを検証する（即ち、もしテールが変更していたらこのことは他のノードがエンキューされていることを意味するが、その場合、ダミー・ノードをエンキューする煩わしさがない）。第２に、キューのヘッドおよびテールのポインタが等しい（即ち、唯一つのノードがエンキューされる）ことを検証する。第３に、テール・ノードの次のポインタがヌルである（即ち、テール・ノードの次のポインタが非ヌルであり、このことは部分的エンキューが進行中であることを意味する）ことを検証する、第４に、ダミー・ノードが既にエンキューされてはいないことを検証する。
【００７１】
行９０５．１では、「エンキューダミー」機能がダミー・ノードを条件付きでエンキューしようとする。このストア・コンディショナルは、もし他のスレッドが一つのノードを同時にエンキューするなら、合わないかもしれない。もしダミー・ノードが成功裡にエンキューされるなら、「エンキューダミー」機能は完遂する。そうでなければ、「エンキューダミー」機能は行９０１で再スタートする。
【００７２】
行９０６で、もしダミー・ノードが最早エンキューされる必要がなければ、「エンキューダミー」機能は完遂する。即ち、行９０５で検証される４つの条件のうち一つが偽である。
【００７３】
当業者は本発明の範囲内に多くの変形が可能であることを認識する。例えば、このエンキュー／デキュー機構が図１のオペレーティング・システムとは別個に独立に示されているが、本発明はオペレーティング・システムおよび／もしくはカーネルの中で実施するよう拡張できる。更に、本発明はアプリケーション・ソフトウエア、ユーティリティもしくは他の型のソフトウエアにおいて単独にもしくは一緒に実施できよう。例えば、本発明はデータベース、ネットワーク、タスク・ディスパッチ、ストレージ管理など広範囲のアプリケーションに適用できる。このように、本発明がその好適な実施例について具体的に示されまた記述されてきたが、本発明の趣旨および範囲から逸れずにその形式および詳細についていろいろな変更をその中で行うことができることが当業者には理解されよう。
【図面の簡単な説明】
【００７４】
【図１】本発明の実施例に従う、同時の、ノンブロッキングの、ロックフリーのＦＩＦＯキューを提供するためのコンピュータ・システムのブロック図である。
【図２】本発明の実施例に従う、ＦＩＦＯキューの初期状態のブロック図である。
【図３】図２に示すＦＩＦＯキューの初期状態にユーザー・ノードがエンキューされるところの本発明の好適な実施例に従うエンキュー動作を説明するブロック図である。
【図４】本発明の好適な実施例によるデキュー動作を図５および図６とともに説明するブロック図であり、特に図３に示す状態のＦＩＦＯキューからダミー・ノードがデキューされた状態を示す図である。
【図５】本発明の好適な実施例によるデキュー動作を図４および図６とともに説明するブロック図であり、特に図４に示す状態のＦＩＦＯキューにダミー・ノードが再エンキューされた状態を示す図である。
【図６】本発明の好適な実施例によるデキュー動作を図４および図５とともに説明するブロック図であり、特に図５に示す状態のＦＩＦＯキューからユーザー・ノードがデキューされた状態を示す図である。
【図７】本発明の好適な実施例に従う、「キュー」クラスおよび「ノード」構造のデータ・レイアウトを説明するのに使用される例示的な擬似コードの図表である。
【図８】図７の「キュー」クラスで宣言された「エンキュー」機能を説明するのに使用される例示の擬似コードの図表である。
【図９】図７の「キュー」クラスで宣言された「エンキューステップ２」機能を説明するのに使用される実施例の擬似コードの図表である。
【図１０】図７の「キュー」クラスで宣言されたデキュー機能を説明するのに使用される例示の擬似コードの図表である。
【図１１】図７の「キュー」クラスで宣言された「エンキューダミー」機能を説明するのに使用される例示の擬似コードの図表である。
【符号の説明】
【００７５】
１００  コンピュータ・システム
１０１、１０１Ａないし１０１Ｄ  プロセッサもしくはＣＰＵ
１０２  メイン・メモリ
１０４  マス・ストレージ・インターフェース
１０６  ディスプレイ・インターフェース
１０８  ネットワーク・インターフェース
１０９  Ｉ／Ｏ装置インターフェース
１１０  システム・バス
１１２  直接アクセス・ストレージ装置（ＤＡＳＤ）
１１４  ＣＤ  ＲＯＭ
１１６  データ
１１８  オペレーティング・システム
１２０  エンキュー／デキュー機構
１２２  ディスプレイ
１２４  ワークステーション
１２６  ネットワーク
２００  ＦＩＦＯキュー
２０２  ダミー・ノード
２０４  次のポインタ
２０６  ヘッド・ポインタ
２０８  テール・ポインタ
２１０  ダミー・ポインタ
３０２  ユーザー・ノード
３０４  次のポインタ
４０２  ダミー・ノード
４０４  次のポインタ
【図１】
2008123516.tif 000004
【図２】
2008123516.tif 000005
【図３】
2008123516.tif 000006
【図４】
2008123516.tif 000007
【図５】
2008123516.tif 000008
【図６】
2008123516.tif 000009
【図７】
2008123516.tif 000010
【図８】
2008123516.tif 000011
【図９】
2008123516.tif 000012
【図１０】
2008123516.tif 000013
【図１１】
2008123516.tif 000014