JPH09204357A - マルチスレッド環境を有する計算システム用の最大並行参照キャッシュ - Google Patents
マルチスレッド環境を有する計算システム用の最大並行参照キャッシュInfo
- Publication number
- JPH09204357A JPH09204357A JP8289018A JP28901896A JPH09204357A JP H09204357 A JPH09204357 A JP H09204357A JP 8289018 A JP8289018 A JP 8289018A JP 28901896 A JP28901896 A JP 28901896A JP H09204357 A JPH09204357 A JP H09204357A
- Authority
- JP
- Japan
- Prior art keywords
- entry
- cache
- key
- item
- entry number
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
- G06F12/02—Addressing or allocation; Relocation
- G06F12/08—Addressing or allocation; Relocation in hierarchically structured memory systems, e.g. virtual memory systems
- G06F12/0802—Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
- G06F12/0806—Multiuser, multiprocessor or multiprocessing cache systems
- G06F12/0842—Multiuser, multiprocessor or multiprocessing cache systems for multiprocessing or multitasking
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【課題】 マルチスレッド環境を有する処理システムの
共用キャッシュへの挿入動作または削除動作時に参照動
作を行えるようにする。 【解決手段】 マルチスレッド処理システムは、各スレ
ッドから共通にアクセスできるキャッシュを有する。こ
のキャッシュは、それぞれ、エントリ番号によって識別
される、項目を記憶する複数のエントリを有する。第１
のキーを含む項目の、キャッシュ中の位置は、この第１
のキーをロックレス参照エンジンに供給することによっ
て判定される。ロックレス参照エンジンは次いで、参照
出力、すなわち参照エントリ番号と、その項目がキャッ
シュに記憶されていないことを示すものとのどちらかを
提供する。参照エントリ番号は、第１のエントリ番号と
第２のエントリ番号のどちらかであり、この場合、第１
のエントリ番号は、その項目が記憶されている第１のエ
ントリを指し示し、第２のエントリ番号は、その項目が
記憶されていない第２のエントリを指す。
共用キャッシュへの挿入動作または削除動作時に参照動
作を行えるようにする。 【解決手段】 マルチスレッド処理システムは、各スレ
ッドから共通にアクセスできるキャッシュを有する。こ
のキャッシュは、それぞれ、エントリ番号によって識別
される、項目を記憶する複数のエントリを有する。第１
のキーを含む項目の、キャッシュ中の位置は、この第１
のキーをロックレス参照エンジンに供給することによっ
て判定される。ロックレス参照エンジンは次いで、参照
出力、すなわち参照エントリ番号と、その項目がキャッ
シュに記憶されていないことを示すものとのどちらかを
提供する。参照エントリ番号は、第１のエントリ番号と
第２のエントリ番号のどちらかであり、この場合、第１
のエントリ番号は、その項目が記憶されている第１のエ
ントリを指し示し、第２のエントリ番号は、その項目が
記憶されていない第２のエントリを指す。
Description
【０００１】
【発明の属する技術分野】本発明は、マルチスレッド環
境を有する処理システムにおける共用キャッシュに関
し、詳細には、キャッシュ挿入動作またはキャッシュ削
除動作時に参照動作を行えるようにする、マルチスレッ
ド環境で使用すべきキャッシュに関する。
境を有する処理システムにおける共用キャッシュに関
し、詳細には、キャッシュ挿入動作またはキャッシュ削
除動作時に参照動作を行えるようにする、マルチスレッ
ド環境で使用すべきキャッシュに関する。
【０００２】
【従来の技術】「キャッシュ」の語は、本開示全体にわ
たって使用されるときは、データの集合の部分集合を保
持するコンピュータ・メモリ中の領域である。ある情報
項目がキャッシュに記憶されている場合、キャッシュ中
のその項目の探索は成功し（「キャッシュ・ヒット」と
呼ばれる）、労力はほとんど必要とされない。しかし、
キャッシュ内にない情報項目の探索（「キャッシュ・ミ
ス」と呼ばれる）は通常、データの集合からその情報項
目を検索するためのコストと時間がかかる。キャッシュ
・ヒットの数を最大にするために、近い将来に参照され
る可能性が高いデータはキャッシュに記憶される。キャ
ッシュ・ヒットを最大にする２つの一般的な方法は、最
後に参照されたデータを記憶し、最も一般的に参照され
るデータを記憶することである。
たって使用されるときは、データの集合の部分集合を保
持するコンピュータ・メモリ中の領域である。ある情報
項目がキャッシュに記憶されている場合、キャッシュ中
のその項目の探索は成功し（「キャッシュ・ヒット」と
呼ばれる）、労力はほとんど必要とされない。しかし、
キャッシュ内にない情報項目の探索（「キャッシュ・ミ
ス」と呼ばれる）は通常、データの集合からその情報項
目を検索するためのコストと時間がかかる。キャッシュ
・ヒットの数を最大にするために、近い将来に参照され
る可能性が高いデータはキャッシュに記憶される。キャ
ッシュ・ヒットを最大にする２つの一般的な方法は、最
後に参照されたデータを記憶し、最も一般的に参照され
るデータを記憶することである。
【０００３】キャッシュは多くの場合、コンピュータ・
オペレーティング・システム（ＯＳ）の性能を向上させ
るために使用される。たとえば、Ｓｕｎ「ＳＯＬＡＲＩ
ＳTM」ＯＳ（ＳｕｎおよびＳｏｌａｒｉｓは、米国およ
びその他の国のサンマイクロシステムズ社（Ｓｕｎ Ｍ
ｉｃｒｏｓｙｓｔｅｍｓ．Ｉｎｃ）の商標または登録商
標である）は、ディレクトリ名参照キャッシュを使用し
て、最後にアクセスされたファイルの名前を記憶し、フ
ァイル属性キャッシュを使用して、最後にアクセスされ
たファイルの属性を記憶し、ディスク・バッファ・キャ
ッシュを使用して、最後にアクセスされたディスク・ブ
ロックを記憶する。
オペレーティング・システム（ＯＳ）の性能を向上させ
るために使用される。たとえば、Ｓｕｎ「ＳＯＬＡＲＩ
ＳTM」ＯＳ（ＳｕｎおよびＳｏｌａｒｉｓは、米国およ
びその他の国のサンマイクロシステムズ社（Ｓｕｎ Ｍ
ｉｃｒｏｓｙｓｔｅｍｓ．Ｉｎｃ）の商標または登録商
標である）は、ディレクトリ名参照キャッシュを使用し
て、最後にアクセスされたファイルの名前を記憶し、フ
ァイル属性キャッシュを使用して、最後にアクセスされ
たファイルの属性を記憶し、ディスク・バッファ・キャ
ッシュを使用して、最後にアクセスされたディスク・ブ
ロックを記憶する。
【０００４】並行して動作するいくつかの実行スレッド
（下記の本明細書全体にわたって、「スレッド」と呼
ぶ）によってキャッシュを共用することができる。この
ような並行動作のために、各スレッドは、マルチプロセ
ッサ環境におけるいくつかのプロセッサのうちの１つの
プロセッサに割り当てられる。別法として、論理並行性
は、オペレーティング・システムが単一のプロセッサ上
のみで「タイム・スライス」技法を使用することによっ
て達成することもできる。多くの場合、この２つの方法
が組み合わされ、それによってマルチプロセッサ・シス
テム中の各プロセッサがタイム・スライシングを使用す
ることができる。
（下記の本明細書全体にわたって、「スレッド」と呼
ぶ）によってキャッシュを共用することができる。この
ような並行動作のために、各スレッドは、マルチプロセ
ッサ環境におけるいくつかのプロセッサのうちの１つの
プロセッサに割り当てられる。別法として、論理並行性
は、オペレーティング・システムが単一のプロセッサ上
のみで「タイム・スライス」技法を使用することによっ
て達成することもできる。多くの場合、この２つの方法
が組み合わされ、それによってマルチプロセッサ・シス
テム中の各プロセッサがタイム・スライシングを使用す
ることができる。
【０００５】マルチスレッド環境を有するコンピュータ
処理システム（たとえば、複数の処理装置を有するシス
テム）では、従来型の技法は相互排他ロックを使用し
て、挿入動作、または削除動作、または参照動作を実行
するときには常に一度に１つのスレッドしかアクセスで
きないようにする。これは、キャッシュに記憶されてい
る情報がアトミックにアクセスまたは更新され、それに
より、更新動作中に発生する遷移不整合によって参照動
作が誤った結果を返すのを防止するためのものである。
相互排他ロックは、当技術分野において知られており、
本明細書では詳しく説明しない。ある種のロックは、ハ
ードウェアのサポートなしに完全にソフトウェアで実施
することができる。相互排他のための最も一般的な特殊
ハードウェア・サポートは、テスト・アンド・セット動
作である。しかし、この２つの解決策（すなわち、全ソ
フトウェア・ロックおよびハードウェア・サポート・ロ
ック）は、ビジー−待機ループを使用することは設計が
困難であり、この場合、待機方式を使用することができ
ないという欠点を有する。セマフォやモニタなどの特殊
言語機能を適用して、生産者−消費者問題やリーダー−
ライター問題など、相互排他を必要とする一般的な並行
プログラミング問題を解決することができる。詳細は、
Ａ．Ｂｕｒｎｓ＆Ｇ．Ｄａｖｉｓ著「Ｃｏｎｃｕｒｒｅ
ｎｔ Ｐｒｏｇｒａｍｍｉｎｇ」６４ないし６８ペー
ジ，１７５ないし１８４ページ，Ａｄｄｉｓｏｎ Ｗｅ
ｓｌｅｙ，１９９３年を参照されたい。この文献は引用
によって本明細書に組み込まれる。
処理システム（たとえば、複数の処理装置を有するシス
テム）では、従来型の技法は相互排他ロックを使用し
て、挿入動作、または削除動作、または参照動作を実行
するときには常に一度に１つのスレッドしかアクセスで
きないようにする。これは、キャッシュに記憶されてい
る情報がアトミックにアクセスまたは更新され、それに
より、更新動作中に発生する遷移不整合によって参照動
作が誤った結果を返すのを防止するためのものである。
相互排他ロックは、当技術分野において知られており、
本明細書では詳しく説明しない。ある種のロックは、ハ
ードウェアのサポートなしに完全にソフトウェアで実施
することができる。相互排他のための最も一般的な特殊
ハードウェア・サポートは、テスト・アンド・セット動
作である。しかし、この２つの解決策（すなわち、全ソ
フトウェア・ロックおよびハードウェア・サポート・ロ
ック）は、ビジー−待機ループを使用することは設計が
困難であり、この場合、待機方式を使用することができ
ないという欠点を有する。セマフォやモニタなどの特殊
言語機能を適用して、生産者−消費者問題やリーダー−
ライター問題など、相互排他を必要とする一般的な並行
プログラミング問題を解決することができる。詳細は、
Ａ．Ｂｕｒｎｓ＆Ｇ．Ｄａｖｉｓ著「Ｃｏｎｃｕｒｒｅ
ｎｔ Ｐｒｏｇｒａｍｍｉｎｇ」６４ないし６８ペー
ジ，１７５ないし１８４ページ，Ａｄｄｉｓｏｎ Ｗｅ
ｓｌｅｙ，１９９３年を参照されたい。この文献は引用
によって本明細書に組み込まれる。
【０００６】ソフトウェア・ロックを使用して、マルチ
スレッド環境を有するシステム中のキャッシュの整合性
を確保することは、そのシステムの性能に悪影響を及ぼ
し、より多くのスレッドが含まれるほど影響が大きくな
る。たとえば、マルチスレッド環境が複数の処理装置
（ＣＰＵ）を有する環境である場合、キャッシュのソフ
トウェア・ロックを得るために待機するアイドル・プロ
セスは、貴重なプロセッサ時間を使用しない。さらに、
複数のプロセスが単一のプロセッサ上のタイム・スライ
シングによってもたらされるシステムでも、待機中のス
レッドは、オペレーティング・システムによってスワッ
プまたはページアウトされる候補である。このようなス
レッドのページインおよびページアウト／スワップイン
およびスワップアウアトを行うためにオペレーティング
・システムに課される追加作業負荷によって、計算シス
テムのスケーリング可能性がさらに低減される。
スレッド環境を有するシステム中のキャッシュの整合性
を確保することは、そのシステムの性能に悪影響を及ぼ
し、より多くのスレッドが含まれるほど影響が大きくな
る。たとえば、マルチスレッド環境が複数の処理装置
（ＣＰＵ）を有する環境である場合、キャッシュのソフ
トウェア・ロックを得るために待機するアイドル・プロ
セスは、貴重なプロセッサ時間を使用しない。さらに、
複数のプロセスが単一のプロセッサ上のタイム・スライ
シングによってもたらされるシステムでも、待機中のス
レッドは、オペレーティング・システムによってスワッ
プまたはページアウトされる候補である。このようなス
レッドのページインおよびページアウト／スワップイン
およびスワップアウアトを行うためにオペレーティング
・システムに課される追加作業負荷によって、計算シス
テムのスケーリング可能性がさらに低減される。
【０００７】上記の議論は、一般にキャッシュに関係す
るものである。しかし、キャッシュは、下記の３つのパ
ラダイムのうちの１つに従って構成することができる。
るものである。しかし、キャッシュは、下記の３つのパ
ラダイムのうちの１つに従って構成することができる。
【０００８】１）「直接マップ」キャッシュとは、記憶
すべき各項目が、それを記憶できるキャッシュ位置を１
つしか有さないキャッシュである。このマッピングは、
各キャッシュ位置が場合によってはいくつかの異なる項
目を保持できるという点で一方向マッピングである。た
とえば、キャッシュエントリ１を文字「ａ」で始まるす
べての項目を記憶するものとして指定することができ
る。すでに項目「ａｂ」を有するキャッシュへ項目「ａ
ａ」の挿入を試みる場合、項目「ａｂ」は破棄せねばな
らない。
すべき各項目が、それを記憶できるキャッシュ位置を１
つしか有さないキャッシュである。このマッピングは、
各キャッシュ位置が場合によってはいくつかの異なる項
目を保持できるという点で一方向マッピングである。た
とえば、キャッシュエントリ１を文字「ａ」で始まるす
べての項目を記憶するものとして指定することができ
る。すでに項目「ａｂ」を有するキャッシュへ項目「ａ
ａ」の挿入を試みる場合、項目「ａｂ」は破棄せねばな
らない。
【０００９】２）「フリー・アソチエーティブ」キャッ
シュとは、記憶すべきデータ・項目を場合によっては任
意のキャッシュ位置に配置することができるキャッシュ
である。
シュとは、記憶すべきデータ・項目を場合によっては任
意のキャッシュ位置に配置することができるキャッシュ
である。
【００１０】３）「セット・アソシエーティブ」キャッ
シュとは、記憶すべきデータ・項目を場合によっては所
定の１組のキャッシュ位置のうちの１つに配置すること
ができるキャッシュである。
シュとは、記憶すべきデータ・項目を場合によっては所
定の１組のキャッシュ位置のうちの１つに配置すること
ができるキャッシュである。
【００１１】多くのアプリケーションでは、キャッシュ
を適切に機能させるために、キャッシュに記憶される各
情報項目が固有のものである必要がある。すなわち、項
目の複製をキャッシュに記憶することはできない。キャ
ッシュの整合性を確保する最も簡単な解決策は、キャッ
シュ全体に対して相互排他ロックを使用し、それによっ
て、キャッシュに対する挿入動作、または削除動作、ま
たは参照動作が１度に１つしかできないようにすること
である。
を適切に機能させるために、キャッシュに記憶される各
情報項目が固有のものである必要がある。すなわち、項
目の複製をキャッシュに記憶することはできない。キャ
ッシュの整合性を確保する最も簡単な解決策は、キャッ
シュ全体に対して相互排他ロックを使用し、それによっ
て、キャッシュに対する挿入動作、または削除動作、ま
たは参照動作が１度に１つしかできないようにすること
である。
【００１２】直接マップ・キャッシュおよびセット・ア
ソシエーティブ・キャッシュでは、多数の密粒相互排他
ロックを使用してキャッシュへのより並行性の高いアク
セスを可能にすることができる。したがって、キャッシ
ュ全体に１つの相互排他ロックしか使用しないのではな
く、キャッシュ中の各位置（直接マップ）または位置の
各集合（セット・アソシエーティブ）ごとに１つの相互
排他ロックがある。キャッシュへのアクセスがランダム
に行われる場合、複数の相互排他ロックを有すると、所
与のキャッシュ動作を適用するために必要な特定のロッ
クを得る際の競合の確率が低下するので、並行アクセス
が増加する。
ソシエーティブ・キャッシュでは、多数の密粒相互排他
ロックを使用してキャッシュへのより並行性の高いアク
セスを可能にすることができる。したがって、キャッシ
ュ全体に１つの相互排他ロックしか使用しないのではな
く、キャッシュ中の各位置（直接マップ）または位置の
各集合（セット・アソシエーティブ）ごとに１つの相互
排他ロックがある。キャッシュへのアクセスがランダム
に行われる場合、複数の相互排他ロックを有すると、所
与のキャッシュ動作を適用するために必要な特定のロッ
クを得る際の競合の確率が低下するので、並行アクセス
が増加する。
【００１３】
【発明が解決しようとする課題】通常、キャッシュ参照
は、挿入および削除よりもずっと頻繁に行われる。この
アクセス・パターンを利用するには、整合性を維持する
ために使用される相互排他ロックを読取り−書込みロッ
クで置き換えることができる。読取り−書込みロックで
は複数の並行キャッシュ参照が可能になる。というの
は、複数の並行キャッシュ参照によってキャッシュの内
容が修正されることはないからである。しかし、１つの
スレッドが挿入と削除のどちらかを実行している場合、
他のすべてのスレッドは、何らかの理由、すなわち、あ
る項目の別の挿入または削除、あるいは参照のためにキ
ャッシュ全体にアクセスすることは許可されない。した
がって、１つのスレッドの挿入または削除のために、他
の多数のスレッドがアイドル状態になる恐れがある。
は、挿入および削除よりもずっと頻繁に行われる。この
アクセス・パターンを利用するには、整合性を維持する
ために使用される相互排他ロックを読取り−書込みロッ
クで置き換えることができる。読取り−書込みロックで
は複数の並行キャッシュ参照が可能になる。というの
は、複数の並行キャッシュ参照によってキャッシュの内
容が修正されることはないからである。しかし、１つの
スレッドが挿入と削除のどちらかを実行している場合、
他のすべてのスレッドは、何らかの理由、すなわち、あ
る項目の別の挿入または削除、あるいは参照のためにキ
ャッシュ全体にアクセスすることは許可されない。した
がって、１つのスレッドの挿入または削除のために、他
の多数のスレッドがアイドル状態になる恐れがある。
【００１４】簡単に言えば、１つまたは複数のソフトウ
ェア・ロックを使用してマルチスレッド・システム中の
キャッシュの整合性を確保すると、キャッシュへの並行
アクセスが低減され、システムのスケーリング可能性に
悪影響が及ぼされる。
ェア・ロックを使用してマルチスレッド・システム中の
キャッシュの整合性を確保すると、キャッシュへの並行
アクセスが低減され、システムのスケーリング可能性に
悪影響が及ぼされる。
【００１５】
【課題を解決するための手段】マルチスレッド処理シス
テムは、各スレッドから共通にアクセスできるキャッシ
ュを有する。このキャッシュは、それぞれ、エントリ番
号によって識別される、項目を記憶する複数のエントリ
を有する。第１のキーを含むエントリの、キャッシュ中
の位置は、この第１のキーをロックレス参照エンジンに
供給することによって判定される。ロックレス参照エン
ジンは次いで、参照出力、すなわち参照エントリ番号を
提供する。参照エントリ番号は、第１のエントリ番号と
第２のエントリ番号のどちらかであり、この場合、第１
のエントリ番号は、その項目が記憶されている第１のエ
ントリを指し示し、第２のエントリ番号は、項目が記憶
されていない第２のエントリを指す。なお、参照エント
リ番号は、所望のエントリ番号での単なる「ヒント」を
提供するものとみなすことができる。次いで、参照エン
トリ番号が第１のエントリ番号であることが検証され
る。この検証には、少なくとも参照エントリ番号で指定
されたエントリへの排他的アクセスを許可する相互排他
ロックを得ることと、参照エントリ番号を使用して、参
照エントリ番号で指定されたエントリから記憶されてい
るキーを読み取ることと、第１のキーを、記憶されてい
るキーと比較することとが含まれる。２つのキーが合致
した場合、この項目が見つかったことになる。
テムは、各スレッドから共通にアクセスできるキャッシ
ュを有する。このキャッシュは、それぞれ、エントリ番
号によって識別される、項目を記憶する複数のエントリ
を有する。第１のキーを含むエントリの、キャッシュ中
の位置は、この第１のキーをロックレス参照エンジンに
供給することによって判定される。ロックレス参照エン
ジンは次いで、参照出力、すなわち参照エントリ番号を
提供する。参照エントリ番号は、第１のエントリ番号と
第２のエントリ番号のどちらかであり、この場合、第１
のエントリ番号は、その項目が記憶されている第１のエ
ントリを指し示し、第２のエントリ番号は、項目が記憶
されていない第２のエントリを指す。なお、参照エント
リ番号は、所望のエントリ番号での単なる「ヒント」を
提供するものとみなすことができる。次いで、参照エン
トリ番号が第１のエントリ番号であることが検証され
る。この検証には、少なくとも参照エントリ番号で指定
されたエントリへの排他的アクセスを許可する相互排他
ロックを得ることと、参照エントリ番号を使用して、参
照エントリ番号で指定されたエントリから記憶されてい
るキーを読み取ることと、第１のキーを、記憶されてい
るキーと比較することとが含まれる。２つのキーが合致
した場合、この項目が見つかったことになる。
【００１６】本発明の一実施態様では、相互排他ロック
は、参照エントリ番号で指定されたエントリのみへの排
他的アクセスを許可する。
は、参照エントリ番号で指定されたエントリのみへの排
他的アクセスを許可する。
【００１７】本発明の他の態様では、第１のキーが、記
憶されているキーに合致しない場合、相互排他ロックが
解除される。次いで、ロックレス参照エンジンが再びア
クセスされ、項目が探索される。
憶されているキーに合致しない場合、相互排他ロックが
解除される。次いで、ロックレス参照エンジンが再びア
クセスされ、項目が探索される。
【００１８】本発明の他の態様では、参照出力は参照エ
ントリ番号と、項目がキャッシュに記憶されていないこ
とを示すもののどちらかである。参照出力が、項目がキ
ャッシュに記憶されていないことを示すものである場
合、第２の検証が実行される。これは、キャッシュに対
する相互排他ロックを得てキャッシュへの挿入および削
除を拒否することと、ロックレス参照エンジンを使用し
て第２の参照出力を提供することとを含む。第２の参照
出力は、第１のエントリ番号と、項目がキャッシュに記
憶されていないことを示すもののどちらかであり、第２
の参照出力が第１のエントリ番号である場合、この項目
が見つかったことになる。
ントリ番号と、項目がキャッシュに記憶されていないこ
とを示すもののどちらかである。参照出力が、項目がキ
ャッシュに記憶されていないことを示すものである場
合、第２の検証が実行される。これは、キャッシュに対
する相互排他ロックを得てキャッシュへの挿入および削
除を拒否することと、ロックレス参照エンジンを使用し
て第２の参照出力を提供することとを含む。第２の参照
出力は、第１のエントリ番号と、項目がキャッシュに記
憶されていないことを示すもののどちらかであり、第２
の参照出力が第１のエントリ番号である場合、この項目
が見つかったことになる。
【００１９】本発明の他の態様では、第２の参照出力
が、項目がキャッシュに記憶されていないことを示すも
のである場合、第１のキーが新しいキャッシュエントリ
に記憶され、ロックレス参照エンジンに新しい要素が記
憶される。この場合、新しい要素は、第１のキーと、新
しいキャッシュエントリを識別する新しいエントリ番号
とを備える。
が、項目がキャッシュに記憶されていないことを示すも
のである場合、第１のキーが新しいキャッシュエントリ
に記憶され、ロックレス参照エンジンに新しい要素が記
憶される。この場合、新しい要素は、第１のキーと、新
しいキャッシュエントリを識別する新しいエントリ番号
とを備える。
【００２０】本発明の他の態様では、ロックレス参照エ
ンジンはロックレス参照ハッシュ・テーブルである。
ンジンはロックレス参照ハッシュ・テーブルである。
【００２１】本発明は、下記の詳細な説明を図面と共に
読むことによって理解されよう。図面では、同じ部分
は、同じ参照符号で識別されている。
読むことによって理解されよう。図面では、同じ部分
は、同じ参照符号で識別されている。
【００２２】
【発明の実施の形態】本発明の実施形態は、マルチスレ
ッド環境で使用できるフリー・アソシエーティブ・キャ
ッシュを提供する。本発明のキャッシュに対する挿入お
よび削除は、キャッシュ全域ロック（下記では「キャッ
シュ・ロック」と呼ぶ）によって順次化される。しか
し、すでにキャッシュに記憶されている項目を得る並行
参照動作がキャッシュ・ロックによって妨害されること
はない。したがって、本発明のキャッシュは、マルチス
レッド環境でのスループットをかなり向上させる。本発
明のこれらおよびその他の特性は、下記の詳細な説明か
ら明らかになろう。
ッド環境で使用できるフリー・アソシエーティブ・キャ
ッシュを提供する。本発明のキャッシュに対する挿入お
よび削除は、キャッシュ全域ロック（下記では「キャッ
シュ・ロック」と呼ぶ）によって順次化される。しか
し、すでにキャッシュに記憶されている項目を得る並行
参照動作がキャッシュ・ロックによって妨害されること
はない。したがって、本発明のキャッシュは、マルチス
レッド環境でのスループットをかなり向上させる。本発
明のこれらおよびその他の特性は、下記の詳細な説明か
ら明らかになろう。
【００２３】好ましい実施形態では、キャッシュは、複
数の「ＳＰＡＲＣTM」処理装置を有するＳｕｎワークス
テーションまたはサーバ、あるいはその両方上で実施さ
れる（ＳｕｎおよびＳＰＡＲＣは、米国およびその他の
国のサンマイクロシステムズ社の商標または登録商標で
ある）。次に図１を参照すると、本発明の技法を使用す
るための例示的なコンピュータ・システムが示されてい
る。このシステムは、それぞれ、ハードウェア・キャッ
シュ１２９（本明細書に記載した本発明のキャッシュと
混同しないよう留意されたい）を介して共通の二重ポー
ト・メモリ（ＤＰＭ）１０３に結合された、２つの同じ
プロセッサ１０１を含む。各プロセッサ１０１は、中央
演算処理装置（ＣＰＵ）１０５と、ランダム・アクセス
・メモリ（ＲＡＭ）１１５と、読取り専用メモリ（ＲＯ
Ｍ）１１７と、上記の各要素を接続する共通システム・
バス１１９とを備える。各プロセッサ１０１は、バス１
１９を介して共用入出力（Ｉ／Ｏ）制御装置１０９にも
接続される。入出力制御装置１０９によって、ディスク
１０７、入力装置１１１および１２３、出力装置１１３
および１２１にプロセッサを結合することができる。こ
れらの構成要素はそれぞれ、当技術分野で知られてお
り、本明細書でさらに詳しく説明する必要はない。
数の「ＳＰＡＲＣTM」処理装置を有するＳｕｎワークス
テーションまたはサーバ、あるいはその両方上で実施さ
れる（ＳｕｎおよびＳＰＡＲＣは、米国およびその他の
国のサンマイクロシステムズ社の商標または登録商標で
ある）。次に図１を参照すると、本発明の技法を使用す
るための例示的なコンピュータ・システムが示されてい
る。このシステムは、それぞれ、ハードウェア・キャッ
シュ１２９（本明細書に記載した本発明のキャッシュと
混同しないよう留意されたい）を介して共通の二重ポー
ト・メモリ（ＤＰＭ）１０３に結合された、２つの同じ
プロセッサ１０１を含む。各プロセッサ１０１は、中央
演算処理装置（ＣＰＵ）１０５と、ランダム・アクセス
・メモリ（ＲＡＭ）１１５と、読取り専用メモリ（ＲＯ
Ｍ）１１７と、上記の各要素を接続する共通システム・
バス１１９とを備える。各プロセッサ１０１は、バス１
１９を介して共用入出力（Ｉ／Ｏ）制御装置１０９にも
接続される。入出力制御装置１０９によって、ディスク
１０７、入力装置１１１および１２３、出力装置１１３
および１２１にプロセッサを結合することができる。こ
れらの構成要素はそれぞれ、当技術分野で知られてお
り、本明細書でさらに詳しく説明する必要はない。
【００２４】各プロセッサ１０１は、ＣＰＵ１０５によ
って実行できるいくつかのソフトウェアを含む。そのよ
うなソフトウェアの１つはオペレーティング・システム
であり、オペレーティング・システムは、ＲＯＭ１１７
から実行することも、あるいはＲＡＭ１１５から実行す
ることもできる。「ＳＯＬＡＲＩＳTM」は好ましいオペ
レーティング・システムである（ＳｕｎおよびＳｏｌａ
ｒｉｓは、米国およびその他の国のサンマイクロシステ
ムズ社の商標または登録商標である）。オペレーティン
グ・システムは、当技術分野で知られており、オペレー
ティング・システムの説明は本明細書の範囲を超えてい
る。代替実施形態では、システムは、単一のプロセッサ
１０１と、スレッドが並行して動作できるようにマルチ
タスキング機能を有するオペレーティング・システムと
を有することができる。この代替実施形態では、複数の
スレッドが、メモリに記憶されているキャッシュに共通
にかつ並行してアクセスすることができる。他の代替実
施形態では、システムに複数のプロセッサが設けられ、
各プロセッサは、マルチタスキング機能を有するオペレ
ーティング・システムを実行する。
って実行できるいくつかのソフトウェアを含む。そのよ
うなソフトウェアの１つはオペレーティング・システム
であり、オペレーティング・システムは、ＲＯＭ１１７
から実行することも、あるいはＲＡＭ１１５から実行す
ることもできる。「ＳＯＬＡＲＩＳTM」は好ましいオペ
レーティング・システムである（ＳｕｎおよびＳｏｌａ
ｒｉｓは、米国およびその他の国のサンマイクロシステ
ムズ社の商標または登録商標である）。オペレーティン
グ・システムは、当技術分野で知られており、オペレー
ティング・システムの説明は本明細書の範囲を超えてい
る。代替実施形態では、システムは、単一のプロセッサ
１０１と、スレッドが並行して動作できるようにマルチ
タスキング機能を有するオペレーティング・システムと
を有することができる。この代替実施形態では、複数の
スレッドが、メモリに記憶されているキャッシュに共通
にかつ並行してアクセスすることができる。他の代替実
施形態では、システムに複数のプロセッサが設けられ、
各プロセッサは、マルチタスキング機能を有するオペレ
ーティング・システムを実行する。
【００２５】図１に示した実施形態に戻ると分かるよう
に、各プロセッサ１０１は、ＲＡＭ１１５とＲＯＭ１１
７のどちらかに記憶されているプログラムを実行するこ
とによって互いに独立に動作する。この例では、各プロ
セッサ１０１は、ＤＰＭ１０３に記憶されているキャッ
シュ１２７へのプロセッサのアクセスを支配するキャッ
シュ制御プログラム１２５を含む。
に、各プロセッサ１０１は、ＲＡＭ１１５とＲＯＭ１１
７のどちらかに記憶されているプログラムを実行するこ
とによって互いに独立に動作する。この例では、各プロ
セッサ１０１は、ＤＰＭ１０３に記憶されているキャッ
シュ１２７へのプロセッサのアクセスを支配するキャッ
シュ制御プログラム１２５を含む。
【００２６】次に、本発明のキャッシュ１２７を図２に
関連して詳しく説明する。キャッシュに情報項目（下記
では「キャッシュ項目」と呼ぶ）を記憶するためにエン
トリ・テーブル２０１が提供される。キャッシュ項目
は、エントリ・テーブル２０１のＮ個の位置またはエン
トリ（下記では、「エントリ」と呼ぶ）のうちの任意の
位置に記憶することができる。エントリ・テーブル２０
１中の各エントリは、固有にエントリ番号に関連付けら
れ、エントリ番号はエントリ・テーブル２０１中のエン
トリへのポインタとして使用される。各エントリは、キ
ー２０３、データ値２０５、エントリ・ロック２０７、
最後のアクセス時間２０９、リファレンス・カウント２
１１の各情報を記憶するフィールドを有する。キー２０
３と値２０５は共に、キャッシュ・ユーザが記憶または
検索し、あるいはその両方を行いたい情報項目を構成す
る。値２０５は、キャッシュ・ユーザが定義する任意の
タイプの構造（たとえば、即値データ・オペランドや他
のメモリ位置を指すポインタ）でよい。好ましい実施形
態では、キャッシュ・ユーザは、メモリ位置を指すポイ
ンタが、「ビジー」とマーク付けされたキャッシュ・エ
ントリ中にキー２０３または値２０５として記憶されて
いる場合、その位置は割り振り解除されないという制限
に従わなければならない。この理由は、他のスレッド
が、キャッシュからそのポインタを得ており、メモリが
割り振り解除されたことを知らずにそのポインタを使用
する可能性があるからである。このようなオカレンスの
後の結果は、予想できないものである。
関連して詳しく説明する。キャッシュに情報項目（下記
では「キャッシュ項目」と呼ぶ）を記憶するためにエン
トリ・テーブル２０１が提供される。キャッシュ項目
は、エントリ・テーブル２０１のＮ個の位置またはエン
トリ（下記では、「エントリ」と呼ぶ）のうちの任意の
位置に記憶することができる。エントリ・テーブル２０
１中の各エントリは、固有にエントリ番号に関連付けら
れ、エントリ番号はエントリ・テーブル２０１中のエン
トリへのポインタとして使用される。各エントリは、キ
ー２０３、データ値２０５、エントリ・ロック２０７、
最後のアクセス時間２０９、リファレンス・カウント２
１１の各情報を記憶するフィールドを有する。キー２０
３と値２０５は共に、キャッシュ・ユーザが記憶または
検索し、あるいはその両方を行いたい情報項目を構成す
る。値２０５は、キャッシュ・ユーザが定義する任意の
タイプの構造（たとえば、即値データ・オペランドや他
のメモリ位置を指すポインタ）でよい。好ましい実施形
態では、キャッシュ・ユーザは、メモリ位置を指すポイ
ンタが、「ビジー」とマーク付けされたキャッシュ・エ
ントリ中にキー２０３または値２０５として記憶されて
いる場合、その位置は割り振り解除されないという制限
に従わなければならない。この理由は、他のスレッド
が、キャッシュからそのポインタを得ており、メモリが
割り振り解除されたことを知らずにそのポインタを使用
する可能性があるからである。このようなオカレンスの
後の結果は、予想できないものである。
【００２７】エントリ・ロック２０７、最後のアクセス
時間２０９、リファレンス・カウント２１１は、ハウス
キーピング項目であり、キャッシュ制御プログラム１２
５によって使用される。簡単に言えば、エントリ・ロッ
ク２０７によって、ロック保持者は、関連するキャッシ
ュ・エントリ（そのエントリのみ）が他のスレッドによ
って変更または削除されるのを防止することができる。
時間２０９、リファレンス・カウント２１１は、ハウス
キーピング項目であり、キャッシュ制御プログラム１２
５によって使用される。簡単に言えば、エントリ・ロッ
ク２０７によって、ロック保持者は、関連するキャッシ
ュ・エントリ（そのエントリのみ）が他のスレッドによ
って変更または削除されるのを防止することができる。
【００２８】最後のアクセス時間２０９は、キャッシュ
・クロック１３から得られ、好ましくは、キャッシュ・
エントリがアクセスされたときには常に単調に増加す
る。キャッシュ・エントリがアクセスされる（すなわ
ち、エントリ・テーブル２０１に挿入され、あるいはエ
ントリ・テーブルから削除される）たびに、その最後の
アクセス時間２０９はキャッシュ・クロック２１３の現
在の値に設定される。キャッシュ項目を含まないキャッ
シュ・エントリの最後のアクセス時間２０９は零に等し
くなる。下記で詳しく説明するように、この情報は、い
くつかのキャッシュ・エントリのうち、最後に使用され
たのはどれかを判定するためにキャッシュ置換ルーチン
によって使用することができる（キャッシュ・エントリ
を使用した時間が新しいほど、最後のアクセス時間の値
は大きくなる）。
・クロック１３から得られ、好ましくは、キャッシュ・
エントリがアクセスされたときには常に単調に増加す
る。キャッシュ・エントリがアクセスされる（すなわ
ち、エントリ・テーブル２０１に挿入され、あるいはエ
ントリ・テーブルから削除される）たびに、その最後の
アクセス時間２０９はキャッシュ・クロック２１３の現
在の値に設定される。キャッシュ項目を含まないキャッ
シュ・エントリの最後のアクセス時間２０９は零に等し
くなる。下記で詳しく説明するように、この情報は、い
くつかのキャッシュ・エントリのうち、最後に使用され
たのはどれかを判定するためにキャッシュ置換ルーチン
によって使用することができる（キャッシュ・エントリ
を使用した時間が新しいほど、最後のアクセス時間の値
は大きくなる）。
【００２９】リファレンス・カウント２１１とは、零に
初期設定され、次いでスレッドによって、関連するキャ
ッシュ項目が得られるたびに増分される数である。スレ
ッドは、もはやそのキャッシュ項目を使用しないと決定
した場合、リファレンス・カウント２１１を減分させる
責任を負う。リファレンス・カウントが零よりも大きな
場合は、そのキャッシュ項目が使用中であることを示す
ので、そのキャッシュ項目が再使用されることがないよ
うにしたいスレッドは、単に、そのキャッシュ項目を得
た後にリファレンス・カウント２１１に対して何もしな
ければよい。
初期設定され、次いでスレッドによって、関連するキャ
ッシュ項目が得られるたびに増分される数である。スレ
ッドは、もはやそのキャッシュ項目を使用しないと決定
した場合、リファレンス・カウント２１１を減分させる
責任を負う。リファレンス・カウントが零よりも大きな
場合は、そのキャッシュ項目が使用中であることを示す
ので、そのキャッシュ項目が再使用されることがないよ
うにしたいスレッドは、単に、そのキャッシュ項目を得
た後にリファレンス・カウント２１１に対して何もしな
ければよい。
【００３０】さらに、キャッシュ１２７には、キャッシ
ュ項目の挿入および削除を順次化し、そのような動作を
１度に１つしか実行できないようにするキャッシュ・ロ
ック２１５が関連付けられる。キャッシュ参照は、キャ
ッシュ削除動作またはキャッシュ挿入動作が実行されて
いる間に行うことができる。この特性を本明細書では
「ロックレス参照」と呼ぶ。参照動作は、参照が挿入中
のエントリ番号と同じエントリ番号に対するものでない
かぎり、並行挿入によって遅延することはない。参照動
作は、並行削除動作によってときどき遅延する可能性の
方が高い。このようにときどき遅延する理由は下記で明
らかになろう。
ュ項目の挿入および削除を順次化し、そのような動作を
１度に１つしか実行できないようにするキャッシュ・ロ
ック２１５が関連付けられる。キャッシュ参照は、キャ
ッシュ削除動作またはキャッシュ挿入動作が実行されて
いる間に行うことができる。この特性を本明細書では
「ロックレス参照」と呼ぶ。参照動作は、参照が挿入中
のエントリ番号と同じエントリ番号に対するものでない
かぎり、並行挿入によって遅延することはない。参照動
作は、並行削除動作によってときどき遅延する可能性の
方が高い。このようにときどき遅延する理由は下記で明
らかになろう。
【００３１】前述のように、キャッシュ１２７は、完全
にアソシエーティブであり、そのため、キャッシュ項目
をキャッシュ・エントリに記憶することができる。本発
明によれば、エントリ・テーブル２０１中のキャッシュ
項目の探索を促進するのを助けるためにロックレス参照
エンジンが提供される。ロックレス参照エンジンは、テ
ーブル２１７と参照エンジン制御プログラム（図示せ
ず）の２つの部分を備える。参照エンジンのテーブル２
１７は、好ましくはキャッシュ１２７に含まれる。対応
する参照エンジン制御プログラムは好ましくはキャッシ
ュ制御プログラム１２５に組み込まれる。
にアソシエーティブであり、そのため、キャッシュ項目
をキャッシュ・エントリに記憶することができる。本発
明によれば、エントリ・テーブル２０１中のキャッシュ
項目の探索を促進するのを助けるためにロックレス参照
エンジンが提供される。ロックレス参照エンジンは、テ
ーブル２１７と参照エンジン制御プログラム（図示せ
ず）の２つの部分を備える。参照エンジンのテーブル２
１７は、好ましくはキャッシュ１２７に含まれる。対応
する参照エンジン制御プログラムは好ましくはキャッシ
ュ制御プログラム１２５に組み込まれる。
【００３２】参照エンジンの目的は、入力キー２１９を
受け取り、エントリ・テーブル２０１中のエントリを指
すエントリ番号２２１を入力キーから生成することであ
る。したがって、参照エンジン自体が、前述の参照機能
だけでなく、それぞれ、キャッシュ挿入動作およびキャ
ッシュ削除動作に対応する、挿入動作および削除動作も
サポートすべきである。すなわち、使用可能なキャッシ
ュ・エントリにキャッシュ項目を挿入するとき、そのキ
ャッシュ項目に関連付けられたキー２０３、およびエン
トリ・テーブル２０１中のその項目のエントリ番号は、
この関連を将来使用するために記録できるように入力２
１９および２２３として参照エンジン・テーブル２１７
に与えられる。同様に、キャッシュ１２７が、そのエン
トリ・テーブル２０１からの対応するキャッシュ項目の
削除を許可している場合に参照エンジン自体も、キーお
よびそれに関連付けられたエントリ番号の参照機構から
の削除をサポートすべきである。
受け取り、エントリ・テーブル２０１中のエントリを指
すエントリ番号２２１を入力キーから生成することであ
る。したがって、参照エンジン自体が、前述の参照機能
だけでなく、それぞれ、キャッシュ挿入動作およびキャ
ッシュ削除動作に対応する、挿入動作および削除動作も
サポートすべきである。すなわち、使用可能なキャッシ
ュ・エントリにキャッシュ項目を挿入するとき、そのキ
ャッシュ項目に関連付けられたキー２０３、およびエン
トリ・テーブル２０１中のその項目のエントリ番号は、
この関連を将来使用するために記録できるように入力２
１９および２２３として参照エンジン・テーブル２１７
に与えられる。同様に、キャッシュ１２７が、そのエン
トリ・テーブル２０１からの対応するキャッシュ項目の
削除を許可している場合に参照エンジン自体も、キーお
よびそれに関連付けられたエントリ番号の参照機構から
の削除をサポートすべきである。
【００３３】キャッシュ１２７の効率を最大にするため
に、参照エンジンは、それ自体のソフトウェア・ロック
を有すのではなく、キャッシュ全体によって使用できる
ように提供されるロックに依存すべきである。したがっ
て、参照エンジンは、それ自体の挿入動作および削除動
作は順次化されるが、参照動作は任意の時間に行うこと
ができる条件の下で動作することが予想される。マルチ
スレッド環境ではしたがって、参照動作によって常に正
確な結果がもたらされるわけではないことが予想でき
る。たとえば、参照エンジンは、実際には所望の要素
（「要素」は、キーと、それに関連付けられたエントリ
番号とからなる）が同時に他のスレッドによって書き込
まれているときに誤って、「要素が見つからない」とい
う結果を返すことがある。参照エンジンは誤って、削除
されたばかりの要素のエントリ番号２２１を返すことも
ある。さらに、参照エンジンは、要素が同時に他のスレ
ッドによって修正されている場合にその要素の誤ったエ
ントリ番号２２１を返すことがある。
に、参照エンジンは、それ自体のソフトウェア・ロック
を有すのではなく、キャッシュ全体によって使用できる
ように提供されるロックに依存すべきである。したがっ
て、参照エンジンは、それ自体の挿入動作および削除動
作は順次化されるが、参照動作は任意の時間に行うこと
ができる条件の下で動作することが予想される。マルチ
スレッド環境ではしたがって、参照動作によって常に正
確な結果がもたらされるわけではないことが予想でき
る。たとえば、参照エンジンは、実際には所望の要素
（「要素」は、キーと、それに関連付けられたエントリ
番号とからなる）が同時に他のスレッドによって書き込
まれているときに誤って、「要素が見つからない」とい
う結果を返すことがある。参照エンジンは誤って、削除
されたばかりの要素のエントリ番号２２１を返すことも
ある。さらに、参照エンジンは、要素が同時に他のスレ
ッドによって修正されている場合にその要素の誤ったエ
ントリ番号２２１を返すことがある。
【００３４】本発明によれば、参照エンジンによって提
供されるこれらの「ヒント」（保証された正確な答えに
対するものとして）は、システム中のどのスレッドもあ
る時点での有効な要素の一部として挿入したことがない
エントリ番号２２１を返す参照動作がなくなることが参
照エンジンによって保証されるかぎり、受け入れること
ができる。言い換えれば、参照エンジンは、初期設定さ
れていない値をエントリ番号２２１として返すことを許
可されてはならい。この要件の理由は、エントリ値が、
キャッシュのエントリ・テーブル２０１にアドレスする
ためのポインタとして使用されることである。したがっ
て、ランダム値ではシステムの障害が生じる恐れがあ
る。ワースト・ケースで、エントリ番号２２１が単に、
エントリ・テーブル２０１中の誤ってはいるが実際のエ
ントリを指すことを保証することによって、前述のシス
テム障害を回避することができる。
供されるこれらの「ヒント」（保証された正確な答えに
対するものとして）は、システム中のどのスレッドもあ
る時点での有効な要素の一部として挿入したことがない
エントリ番号２２１を返す参照動作がなくなることが参
照エンジンによって保証されるかぎり、受け入れること
ができる。言い換えれば、参照エンジンは、初期設定さ
れていない値をエントリ番号２２１として返すことを許
可されてはならい。この要件の理由は、エントリ値が、
キャッシュのエントリ・テーブル２０１にアドレスする
ためのポインタとして使用されることである。したがっ
て、ランダム値ではシステムの障害が生じる恐れがあ
る。ワースト・ケースで、エントリ番号２２１が単に、
エントリ・テーブル２０１中の誤ってはいるが実際のエ
ントリを指すことを保証することによって、前述のシス
テム障害を回避することができる。
【００３５】好ましい実施形態によれば、参照エンジン
はロックレス参照ハッシュ・テーブルであり、挿入動作
および削除動作のみの順次化しか必要とせず、並行参照
動作を許可し、以前にシステム中のどのスレッドからも
ハッシュ・テーブルに書き込まれたことがない値が返さ
れることがなくなることが保証される。そのようなハッ
シュ・テーブルは、本発明と同じ出願人に譲渡され引用
によって全体的に本明細書に組み込まれた米国特許出力
第 号（整理番号０２６４１４−００１）に詳しく記
載されている。
はロックレス参照ハッシュ・テーブルであり、挿入動作
および削除動作のみの順次化しか必要とせず、並行参照
動作を許可し、以前にシステム中のどのスレッドからも
ハッシュ・テーブルに書き込まれたことがない値が返さ
れることがなくなることが保証される。そのようなハッ
シュ・テーブルは、本発明と同じ出願人に譲渡され引用
によって全体的に本明細書に組み込まれた米国特許出力
第 号（整理番号０２６４１４−００１）に詳しく記
載されている。
【００３６】次に、ロックレス参照ハッシュ・テーブル
をキャッシュ１２７用の参照エンジンとして使用するこ
とを図３に示す。この例では、キャッシュ・エントリ・
テーブル３０１はディレクトリ名参照キャッシュであ
り、この場合、各キー２０３はファイル名であり、値２
０５はファイル番号である。そのようなキャッシュの目
的は、最後のアクセスされたファイルの名前および対応
するファイル番号を記憶することである。図のように、
キーが「ｓｙｓ」であるキャッシュ項目がキャッシュ・
エントリ０に記憶され、キーが「ｆｉｌｅ１」であるキ
ャッシュ項目がキャッシュ・エントリ１０１に記憶さ
れ、キーが「ｍｙｆｉｌｅ」であるキャッシュ項目がキ
ャッシュ・エントリ１０２に記憶され、キーが「ｍｙｄ
ｉｒ」であるキャッシュ項目がキャッシュ・エントリＮ
に記憶される。
をキャッシュ１２７用の参照エンジンとして使用するこ
とを図３に示す。この例では、キャッシュ・エントリ・
テーブル３０１はディレクトリ名参照キャッシュであ
り、この場合、各キー２０３はファイル名であり、値２
０５はファイル番号である。そのようなキャッシュの目
的は、最後のアクセスされたファイルの名前および対応
するファイル番号を記憶することである。図のように、
キーが「ｓｙｓ」であるキャッシュ項目がキャッシュ・
エントリ０に記憶され、キーが「ｆｉｌｅ１」であるキ
ャッシュ項目がキャッシュ・エントリ１０１に記憶さ
れ、キーが「ｍｙｆｉｌｅ」であるキャッシュ項目がキ
ャッシュ・エントリ１０２に記憶され、キーが「ｍｙｄ
ｉｒ」であるキャッシュ項目がキャッシュ・エントリＮ
に記憶される。
【００３７】任意のキャッシュ項目のエントリ番号を見
つけられるように、それに関連付けられたキーが入力と
して与えられる場合、ロックレス参照ハッシュ・テーブ
ル３０３はキーとエントリ番号の対を記憶している。所
与の対では、エントリ番号は、キーおよびそれに関連付
けられた値が記憶されているキャッシュ中のエントリを
指す。各キー／エントリ番号対が配置されたロックレス
参照ハッシュ・テーブル中の位置は、キーに作用してハ
ッシュ・テーブルの初期インデックスを生成するハッシ
ュ関数と、初期インデックスが、すでに占有されている
位置を指す場合に、使用可能なエントリを見つける競合
方法によって判定される。したがって、この例では、キ
ー「ｓｙｓ」のハッシュ値はＮ−１であり、したがって
対「（ｓｙｓ，０）」はロックレス参照ハッシュ・テー
ブル３０３中の位置Ｎ−１に記憶される。矢印３０５で
示したように、「０」は、キャッシュ・エントリ０にキ
ャッシュ項目が記憶されていることを示す。
つけられるように、それに関連付けられたキーが入力と
して与えられる場合、ロックレス参照ハッシュ・テーブ
ル３０３はキーとエントリ番号の対を記憶している。所
与の対では、エントリ番号は、キーおよびそれに関連付
けられた値が記憶されているキャッシュ中のエントリを
指す。各キー／エントリ番号対が配置されたロックレス
参照ハッシュ・テーブル中の位置は、キーに作用してハ
ッシュ・テーブルの初期インデックスを生成するハッシ
ュ関数と、初期インデックスが、すでに占有されている
位置を指す場合に、使用可能なエントリを見つける競合
方法によって判定される。したがって、この例では、キ
ー「ｓｙｓ」のハッシュ値はＮ−１であり、したがって
対「（ｓｙｓ，０）」はロックレス参照ハッシュ・テー
ブル３０３中の位置Ｎ−１に記憶される。矢印３０５で
示したように、「０」は、キャッシュ・エントリ０にキ
ャッシュ項目が記憶されていることを示す。
【００３８】上記の例では、エントリ・テーブル２０１
中のキー用に予約されたメモリ領域内にキーを記憶する
ことができると仮定した。しかし、実際には、ファイル
名の長さは大幅に異なることがあり、非常に長くなるこ
とがある（すなわち、最大２５５バイト）。各キャッシ
ュ・エントリごとに、ファイル名の最大サイズに等しい
キー・フィールドを予約するのは無駄である。この状況
に対するより良い解決策は、キー２０３自体をメモリ領
域を指すポインタにすることである。その場合、ポイン
タは、個別の各ファイル名ごとの必要に応じて動的に割
り振ることができる。しかし、他のスレッドがあるキー
を見ないことが確実でないかぎり、ユーザがそのキー用
の記憶域を割り振り解除しないようにする方法を使用し
なければならない。
中のキー用に予約されたメモリ領域内にキーを記憶する
ことができると仮定した。しかし、実際には、ファイル
名の長さは大幅に異なることがあり、非常に長くなるこ
とがある（すなわち、最大２５５バイト）。各キャッシ
ュ・エントリごとに、ファイル名の最大サイズに等しい
キー・フィールドを予約するのは無駄である。この状況
に対するより良い解決策は、キー２０３自体をメモリ領
域を指すポインタにすることである。その場合、ポイン
タは、個別の各ファイル名ごとの必要に応じて動的に割
り振ることができる。しかし、他のスレッドがあるキー
を見ないことが確実でないかぎり、ユーザがそのキー用
の記憶域を割り振り解除しないようにする方法を使用し
なければならない。
【００３９】好ましい実施形態では、２つのキャッシュ
項目が同じキーを有することはできない。この理由は、
キー２０３を入力キー値と突き合わせることによってキ
ャッシュ項目が見つけられることである。２つのキャッ
シュ項目が同じキー２０３を有することができる場合、
それらのうちの一方しか見つからない。たとえば、前述
のように、参照エンジンがロックレス参照ハッシュ・テ
ーブルである場合、ハッシュ・テーブル参照動作は常
に、キーが合致した第１の要素に出会った後に探索プロ
ーブ・シーケンスを停止する。
項目が同じキーを有することはできない。この理由は、
キー２０３を入力キー値と突き合わせることによってキ
ャッシュ項目が見つけられることである。２つのキャッ
シュ項目が同じキー２０３を有することができる場合、
それらのうちの一方しか見つからない。たとえば、前述
のように、参照エンジンがロックレス参照ハッシュ・テ
ーブルである場合、ハッシュ・テーブル参照動作は常
に、キーが合致した第１の要素に出会った後に探索プロ
ーブ・シーケンスを停止する。
【００４０】常に正確な答えではなく前述の「ヒント」
を返すことに依存できる参照エンジンを使用するには、
本発明による下記の方法を使用する。参照エンジン・テ
ーブル２１７中の項目の参照が失敗した（すなわち、合
致するキーを有する要素が見つからず、したがって、明
らかに「キャッシュ・ミス」が発生していることをテー
ブルが示す）場合、相互排他キャッシュ・ロック２１５
を得てその項目に対する第２の参照を実行し、その項目
が実際にキャッシュ中にないことを検証しなければなら
ない。キャッシュ・ロック２１５を得ることによって、
他のスレッドがキャッシュ・エントリを削除し、あるい
はキャッシュ・エントリに項目を挿入することが防止さ
れることを想起されたい。スレッドが参照エンジンを更
新するときにはいつでも、最初にキャッシュ・ロック２
１５を得るので、参照エンジンの挿入および削除も防止
され、それによって、参照エンジン・テーブル２１７は
確実に、この検証動作に対する正確な出力を生成する。
探索中の要素が実際に参照エンジン・テーブル２１７に
あることが判明した場合、新たに得たエントリ番号２２
１を使用して所望のキャッシュ項目を見つけることがで
きる。探索中の要素が参照エンジン・テーブル２１７に
あることが判明するかどうかにはかかわらず、他のスレ
ッドをさらに遅延させることがないように、この検証動
作の後にキャッシュ・ロック２１５は放棄される。
を返すことに依存できる参照エンジンを使用するには、
本発明による下記の方法を使用する。参照エンジン・テ
ーブル２１７中の項目の参照が失敗した（すなわち、合
致するキーを有する要素が見つからず、したがって、明
らかに「キャッシュ・ミス」が発生していることをテー
ブルが示す）場合、相互排他キャッシュ・ロック２１５
を得てその項目に対する第２の参照を実行し、その項目
が実際にキャッシュ中にないことを検証しなければなら
ない。キャッシュ・ロック２１５を得ることによって、
他のスレッドがキャッシュ・エントリを削除し、あるい
はキャッシュ・エントリに項目を挿入することが防止さ
れることを想起されたい。スレッドが参照エンジンを更
新するときにはいつでも、最初にキャッシュ・ロック２
１５を得るので、参照エンジンの挿入および削除も防止
され、それによって、参照エンジン・テーブル２１７は
確実に、この検証動作に対する正確な出力を生成する。
探索中の要素が実際に参照エンジン・テーブル２１７に
あることが判明した場合、新たに得たエントリ番号２２
１を使用して所望のキャッシュ項目を見つけることがで
きる。探索中の要素が参照エンジン・テーブル２１７に
あることが判明するかどうかにはかかわらず、他のスレ
ッドをさらに遅延させることがないように、この検証動
作の後にキャッシュ・ロック２１５は放棄される。
【００４１】同様に、参照エンジン・テーブル２１７中
の項目の参照が成功した（すなわち、キー／エントリ番
号が見つかり、したがって明らかに「キャッシュ・ヒッ
トが発生していることが報告された）場合、指し示され
たキャッシュ項目のＩＤを検証する必要がある。本発明
の一態様によれば、キャッシュ全体を探すのではなく、
指し示されたキャッシュ項目のエントリ・ロック２０７
のみが得られる。このため、指し示されたキャッシュ・
エントリに配置されたキー２０３は削除されず、あるい
はその他の方法で変更されることもない。エントリ・ロ
ック２０７を得た後、入力キー２１９をキー２０３と比
較して、探索中のキャッシュ項目が実際に見つかったこ
とを検証することができる。
の項目の参照が成功した（すなわち、キー／エントリ番
号が見つかり、したがって明らかに「キャッシュ・ヒッ
トが発生していることが報告された）場合、指し示され
たキャッシュ項目のＩＤを検証する必要がある。本発明
の一態様によれば、キャッシュ全体を探すのではなく、
指し示されたキャッシュ項目のエントリ・ロック２０７
のみが得られる。このため、指し示されたキャッシュ・
エントリに配置されたキー２０３は削除されず、あるい
はその他の方法で変更されることもない。エントリ・ロ
ック２０７を得た後、入力キー２１９をキー２０３と比
較して、探索中のキャッシュ項目が実際に見つかったこ
とを検証することができる。
【００４２】次に、本発明の他の態様について説明す
る。「キャッシュ・ミス」が発生すると多くの場合、こ
の報告を受け取ったスレッドは、メイン・メモリやディ
スク記憶装置など他の情報源から探索中の情報を得る余
分の処置をとる。スレッドは、情報を得た後、この情報
を次回により迅速に検索できるようにキャッシュに記憶
する処置をとる。キャッシュに項目を記憶するには、相
互排他キャッシュ・ロック２１５を得る必要があるの
で、本発明は好ましくは、キャッシュ参照機能が、キャ
ッシュ・ミスが実際に発生したと判定した後、キー２０
３のみを使用可能なエントリに書き込み、このエントリ
を「ビジー」とマーク付けし、キー２０３をロックレス
参照エンジン２１７に挿入することによってキャッシュ
・エントリを予約する機能を含む。このエントリ用のエ
ントリ・ロック２０７も得られ、次いで、このエントリ
を指すポインタが、「新しいキャッシュ項目」を示すリ
ターン・コードと共に呼び出し側スレッドに返される。
ユーザ・スレッドは次いで、代替情報源から情報を得
て、次いで、キャッシュ・ロック２１５を得るのを待つ
必要なしにキャッシュ・エントリにこの情報を記憶する
ことができる。別法として、ユーザ・スレッドは、探索
中の情報を代替情報源から得なくてもよい。その場合、
ユーザ・スレッドは、新たに作成したキャッシュ・エン
トリをエントリ・テーブル２０１から削除すべきであ
る。キャッシュ・エントリの削除については下記で詳し
く説明する。
る。「キャッシュ・ミス」が発生すると多くの場合、こ
の報告を受け取ったスレッドは、メイン・メモリやディ
スク記憶装置など他の情報源から探索中の情報を得る余
分の処置をとる。スレッドは、情報を得た後、この情報
を次回により迅速に検索できるようにキャッシュに記憶
する処置をとる。キャッシュに項目を記憶するには、相
互排他キャッシュ・ロック２１５を得る必要があるの
で、本発明は好ましくは、キャッシュ参照機能が、キャ
ッシュ・ミスが実際に発生したと判定した後、キー２０
３のみを使用可能なエントリに書き込み、このエントリ
を「ビジー」とマーク付けし、キー２０３をロックレス
参照エンジン２１７に挿入することによってキャッシュ
・エントリを予約する機能を含む。このエントリ用のエ
ントリ・ロック２０７も得られ、次いで、このエントリ
を指すポインタが、「新しいキャッシュ項目」を示すリ
ターン・コードと共に呼び出し側スレッドに返される。
ユーザ・スレッドは次いで、代替情報源から情報を得
て、次いで、キャッシュ・ロック２１５を得るのを待つ
必要なしにキャッシュ・エントリにこの情報を記憶する
ことができる。別法として、ユーザ・スレッドは、探索
中の情報を代替情報源から得なくてもよい。その場合、
ユーザ・スレッドは、新たに作成したキャッシュ・エン
トリをエントリ・テーブル２０１から削除すべきであ
る。キャッシュ・エントリの削除については下記で詳し
く説明する。
【００４３】本発明の他の態様は、キャッシュ置換方式
に関する。そのような方式では、キャッシュが満杯であ
る場合にキャッシュからどのキャッシュ項目を削除すべ
きかを決定する条件が指定される。好ましい実施形態で
は、スレッドによって使用されていないキャッシュ項目
のみが置換の候補である。リファレンス・カウント２１
１は、ある項目が現在、使用されているか、それとも使
用されていないかを示すために使用される。リファレン
ス・カウント２１１が零である場合、その項目は使用さ
れておらず、非零リファレンス・カウント２１１は、そ
のキャッシュ項目が使用中であることを意味する。
に関する。そのような方式では、キャッシュが満杯であ
る場合にキャッシュからどのキャッシュ項目を削除すべ
きかを決定する条件が指定される。好ましい実施形態で
は、スレッドによって使用されていないキャッシュ項目
のみが置換の候補である。リファレンス・カウント２１
１は、ある項目が現在、使用されているか、それとも使
用されていないかを示すために使用される。リファレン
ス・カウント２１１が零である場合、その項目は使用さ
れておらず、非零リファレンス・カウント２１１は、そ
のキャッシュ項目が使用中であることを意味する。
【００４４】キャッシュ置換方式は、ＬＲＵ方式の修正
バージョンである。基本的に、キャッシュ・エントリ・
テーブル２０１全体が論理的に、数組の１６個のキャッ
シュ・エントリに分割される。各組は、使用可能なキャ
ッシュ・エントリが必要なときはいつでもラウンドロビ
ン方式でポーリングされる。キャッシュ項目は、リファ
レンス・カウント２１１が零に設定されることによっ
て、使用されていないことが示された場合に置換の候補
となる。１組の１６個のキャッシュ・エントリのうちの
複数が現在使用されていない場合、最後のアクセス時間
２０９の値によって、最後に使用されたことが示された
キャッシュ・エントリが、置換すべきものとして選択さ
れる。ある組のあらゆるキャッシュ項目が使用されてい
る場合は、現在の組はスキップされ、次の組が調べられ
る。これは、受け入れられる置換候補が選択されるまで
継続する。使用可能な他のキャッシュ・エントリが必要
であるとき、次の１組の１６個のキャッシュ項目に同じ
方式を適用することによって次の候補が選択される。修
正ＬＲＵキャッシュ置換方式によって、普通なら、従来
型のＬＲＵ技法によってキャッシュ項目を順序付けする
のに必要とされる、キャッシュに対するある種のロック
を得ることが不要になる。ロックを保持せずにＬＲＵ順
序を決定することにより、修正ＬＲＵ方式によって選択
されたエントリを、その選択時とロック時との間に他の
スレッドによって使用することが可能になる（ただし、
こうする可能性は低い）。しかし、好ましい実施形態で
は、絶対的なＬＲＵ順序付けは必要とされない。ＬＲＵ
順序に近ければ十分である。
バージョンである。基本的に、キャッシュ・エントリ・
テーブル２０１全体が論理的に、数組の１６個のキャッ
シュ・エントリに分割される。各組は、使用可能なキャ
ッシュ・エントリが必要なときはいつでもラウンドロビ
ン方式でポーリングされる。キャッシュ項目は、リファ
レンス・カウント２１１が零に設定されることによっ
て、使用されていないことが示された場合に置換の候補
となる。１組の１６個のキャッシュ・エントリのうちの
複数が現在使用されていない場合、最後のアクセス時間
２０９の値によって、最後に使用されたことが示された
キャッシュ・エントリが、置換すべきものとして選択さ
れる。ある組のあらゆるキャッシュ項目が使用されてい
る場合は、現在の組はスキップされ、次の組が調べられ
る。これは、受け入れられる置換候補が選択されるまで
継続する。使用可能な他のキャッシュ・エントリが必要
であるとき、次の１組の１６個のキャッシュ項目に同じ
方式を適用することによって次の候補が選択される。修
正ＬＲＵキャッシュ置換方式によって、普通なら、従来
型のＬＲＵ技法によってキャッシュ項目を順序付けする
のに必要とされる、キャッシュに対するある種のロック
を得ることが不要になる。ロックを保持せずにＬＲＵ順
序を決定することにより、修正ＬＲＵ方式によって選択
されたエントリを、その選択時とロック時との間に他の
スレッドによって使用することが可能になる（ただし、
こうする可能性は低い）。しかし、好ましい実施形態で
は、絶対的なＬＲＵ順序付けは必要とされない。ＬＲＵ
順序に近ければ十分である。
【００４５】本発明の他の態様では、キャッシュ１２７
は、挿入または削除の結果としてキャッシュ・エントリ
をキャッシュから破棄するときはいつでもそのエントリ
の内容を他の記憶媒体に直接書き込み直すコールバック
機能を含む。コールバック・ルーチンによって実行され
る特定のステップは、アプリケーションに特有のもので
ある。名前キャッシュの場合、コールバック機能は何も
行わない。バッファ・キャッシュの場合、再使用される
バッファの内容をディスクに書き込んでおかなければ、
バッファを再使用することはできない。挿入または削除
を実行しているスレッドは、コールバック情報２２５か
らコールバック・ルーチンのアドレスを得る。コールバ
ック・ルーチンのアドレスは、キャッシュ・エントリ・
テーブル２０１を作成したスレッド（下記では「作成者
スレッド」と呼ぶ）によってコールバック情報２２５内
に置かれる。このため、作成者スレッドは、キャッシュ
・エントリが置き換えられるときに常にとるべき処置を
指定することができる。
は、挿入または削除の結果としてキャッシュ・エントリ
をキャッシュから破棄するときはいつでもそのエントリ
の内容を他の記憶媒体に直接書き込み直すコールバック
機能を含む。コールバック・ルーチンによって実行され
る特定のステップは、アプリケーションに特有のもので
ある。名前キャッシュの場合、コールバック機能は何も
行わない。バッファ・キャッシュの場合、再使用される
バッファの内容をディスクに書き込んでおかなければ、
バッファを再使用することはできない。挿入または削除
を実行しているスレッドは、コールバック情報２２５か
らコールバック・ルーチンのアドレスを得る。コールバ
ック・ルーチンのアドレスは、キャッシュ・エントリ・
テーブル２０１を作成したスレッド（下記では「作成者
スレッド」と呼ぶ）によってコールバック情報２２５内
に置かれる。このため、作成者スレッドは、キャッシュ
・エントリが置き換えられるときに常にとるべき処置を
指定することができる。
【００４６】次に、キャッシュ制御装置（たとえば、キ
ャッシュ制御プログラム１２５を実行するＣＰＵ１０
５）の一実施形態を図４ないし１１に関して説明する。
下記の説明は様々な値に言及しているが、これは単に都
合上のものであり、下記のプロセスが実際には、例示的
なコンピュータ・システムの動作を制御する制御信号を
生成する手段の一実施形態を説明するものであることを
理解されたい。当業者なら、下記の例が本発明の一実施
形態を例示するものに過ぎず、例示的な実施形態を修正
することができ、しかも本開示に記載したすべての要件
が満たされることが認識されよう。
ャッシュ制御プログラム１２５を実行するＣＰＵ１０
５）の一実施形態を図４ないし１１に関して説明する。
下記の説明は様々な値に言及しているが、これは単に都
合上のものであり、下記のプロセスが実際には、例示的
なコンピュータ・システムの動作を制御する制御信号を
生成する手段の一実施形態を説明するものであることを
理解されたい。当業者なら、下記の例が本発明の一実施
形態を例示するものに過ぎず、例示的な実施形態を修正
することができ、しかも本開示に記載したすべての要件
が満たされることが認識されよう。
【００４７】キャッシュへのアクセスは、Ｇｅｔ＿Ｃａ
ｃｈｅ＿ＥｎｔｒｙおよびＤｅｌｅｔｅ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙの２つのルーチンにより、ユーザ・スレッド
によって行われる。
ｃｈｅ＿ＥｎｔｒｙおよびＤｅｌｅｔｅ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙの２つのルーチンにより、ユーザ・スレッド
によって行われる。
【００４８】まず、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチンでは、このルーチンのユーザがこのルーチンにキ
ーを供給する。これに応答して、Ｇｅｔ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙルーチンは、合致するキーを有するキャッシ
ュ項目を含むエントリ・テーブル２０１中のキャッシュ
・エントリを見つけロックする。次いで、キャッシュ・
エントリのリファレンス・カウント２１１が１だけ増分
される。次いで、エントリ・テーブル２０１中のこのエ
ントリを指すポインタがユーザに供給される。そのよう
なキャッシュ項目がまだキャッシュ１２７に記憶されて
いない場合、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
は、新たに得たキャッシュ・エントリにキー２０３を追
加し、キャッシュ・エントリを「ビジー」としてセット
し、それをロックし（キャッシュ全体ではなく、そのエ
ントリのみである）、ロックしたエントリを指すポイン
タを返す。これによって、他のスレッドが、同じ名前を
有する他のエントリをエントリ・テーブル２０１に追加
するのが防止され、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙを
呼び出したスレッドは、他の情報源から関連する情報を
得て、次いでこの情報を値２０５として記憶することが
できる。別法として、ユーザは、他のスレッドがこの情
報を挿入する機会を有するように、新たに作成されたキ
ャッシュ・エントリを削除する以外何も行わなくてもよ
い。
ーチンでは、このルーチンのユーザがこのルーチンにキ
ーを供給する。これに応答して、Ｇｅｔ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙルーチンは、合致するキーを有するキャッシ
ュ項目を含むエントリ・テーブル２０１中のキャッシュ
・エントリを見つけロックする。次いで、キャッシュ・
エントリのリファレンス・カウント２１１が１だけ増分
される。次いで、エントリ・テーブル２０１中のこのエ
ントリを指すポインタがユーザに供給される。そのよう
なキャッシュ項目がまだキャッシュ１２７に記憶されて
いない場合、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
は、新たに得たキャッシュ・エントリにキー２０３を追
加し、キャッシュ・エントリを「ビジー」としてセット
し、それをロックし（キャッシュ全体ではなく、そのエ
ントリのみである）、ロックしたエントリを指すポイン
タを返す。これによって、他のスレッドが、同じ名前を
有する他のエントリをエントリ・テーブル２０１に追加
するのが防止され、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙを
呼び出したスレッドは、他の情報源から関連する情報を
得て、次いでこの情報を値２０５として記憶することが
できる。別法として、ユーザは、他のスレッドがこの情
報を挿入する機会を有するように、新たに作成されたキ
ャッシュ・エントリを削除する以外何も行わなくてもよ
い。
【００４９】次に、図４を参照すると、Ｇｅｔ＿Ｃａｃ
ｈｅ＿Ｅｎｔｒｙルーチン４００のフローチャートが示
されている。このルーチンの概要は下記のとおりであ
る。エントリ・テーブル２０１において要求されたエン
トリを見つけることが試みられる（ステップ４０１での
「Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ」のサブルーチン
呼出し）。このエントリが見つかった場合（ステップ４
０３でキャッシュ・ヒット＝「ｙｅｓ」）、キャッシュ
・クロック２１３が増分され（ステップ４０７）、この
項目の最後のアクセス時間２０９がキャッシュ・クロッ
ク２１３の値に等しい値に設定される（ステップ４０
９）。最後に、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチ
ン４００を呼び出したスレッドに、このキャッシュ・エ
ントリを指すポインタが返される（ステップ４１１）。
ｈｅ＿Ｅｎｔｒｙルーチン４００のフローチャートが示
されている。このルーチンの概要は下記のとおりであ
る。エントリ・テーブル２０１において要求されたエン
トリを見つけることが試みられる（ステップ４０１での
「Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ」のサブルーチン
呼出し）。このエントリが見つかった場合（ステップ４
０３でキャッシュ・ヒット＝「ｙｅｓ」）、キャッシュ
・クロック２１３が増分され（ステップ４０７）、この
項目の最後のアクセス時間２０９がキャッシュ・クロッ
ク２１３の値に等しい値に設定される（ステップ４０
９）。最後に、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチ
ン４００を呼び出したスレッドに、このキャッシュ・エ
ントリを指すポインタが返される（ステップ４１１）。
【００５０】あるいは、要求されたエントリを見つける
最初の試みが失敗した場合（ステップ４０３で、キャッ
シュ・ヒット＝「ｎｏ」）は、新たに得られたキャッシ
ュ・エントリにキーを挿入し、このエントリをビジーと
してマーク付けし、このエントリに対するロックを得る
ことが試みられる（ステップ４０５での「Ｉｎｓｅｒｔ
＿Ｃａｃｈｅ＿Ｉｔｅｍ」のサブルーチン呼出し）。前
の文で「試み」の語を使用した理由は、Ｆｉｎｄ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン（ステップ４０１）が、要
求された項目が見つからないことを報告した後に、その
項目がキャッシュ１２７に挿入された可能性があるから
である。こうなると、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔ
ｅｍルーチン４０５は新しい項目を挿入せず、その代わ
りに、合致するキーを有する前に挿入されたエントリを
指すポインタを得る。この項目はロックされ、ビジーと
してマーク付けされる。
最初の試みが失敗した場合（ステップ４０３で、キャッ
シュ・ヒット＝「ｎｏ」）は、新たに得られたキャッシ
ュ・エントリにキーを挿入し、このエントリをビジーと
してマーク付けし、このエントリに対するロックを得る
ことが試みられる（ステップ４０５での「Ｉｎｓｅｒｔ
＿Ｃａｃｈｅ＿Ｉｔｅｍ」のサブルーチン呼出し）。前
の文で「試み」の語を使用した理由は、Ｆｉｎｄ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン（ステップ４０１）が、要
求された項目が見つからないことを報告した後に、その
項目がキャッシュ１２７に挿入された可能性があるから
である。こうなると、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔ
ｅｍルーチン４０５は新しい項目を挿入せず、その代わ
りに、合致するキーを有する前に挿入されたエントリを
指すポインタを得る。この項目はロックされ、ビジーと
してマーク付けされる。
【００５１】次に、図５を参照すると、Ｆｉｎｄ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン４０１のフローチャートが
示されている。このルーチンは、ユーザのキーに関連付
けられたエントリ番号を得るためにロックレス参照ハッ
シュ・テーブルにアクセスすることによって開始する。
要素が見つからなかったことを示すものをハッシュ・テ
ーブルが返した場合（ステップ５０３で、キャッシュ・
ヒット＝「ｎｏ」）、Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン４０１が、「ｎｏｔ ｆｏｕｎｄ」を示すリ
ターン・コードと共にＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ
ルーチン４００に戻る。
ｃｈｅ＿Ｅｎｔｒｙルーチン４０１のフローチャートが
示されている。このルーチンは、ユーザのキーに関連付
けられたエントリ番号を得るためにロックレス参照ハッ
シュ・テーブルにアクセスすることによって開始する。
要素が見つからなかったことを示すものをハッシュ・テ
ーブルが返した場合（ステップ５０３で、キャッシュ・
ヒット＝「ｎｏ」）、Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン４０１が、「ｎｏｔ ｆｏｕｎｄ」を示すリ
ターン・コードと共にＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ
ルーチン４００に戻る。
【００５２】あるいは、ハッシュ・テーブルが実際にエ
ントリ番号を返した場合（ステップ５０３で、キャッシ
ュ・ヒット＝「ｙｅｓ」）は、下記のステップを実行し
てこの「ヒント」が正確であることを確認しなければな
らない。まず、このエントリ（すなわち、エントリ番号
によって指し示されたエントリ）に対するエントリ・ロ
ック２０７が得られる。この場合、他のスレッドがこの
エントリ・ロックを解除するのを待つ必要があることに
留意されたい。
ントリ番号を返した場合（ステップ５０３で、キャッシ
ュ・ヒット＝「ｙｅｓ」）は、下記のステップを実行し
てこの「ヒント」が正確であることを確認しなければな
らない。まず、このエントリ（すなわち、エントリ番号
によって指し示されたエントリ）に対するエントリ・ロ
ック２０７が得られる。この場合、他のスレッドがこの
エントリ・ロックを解除するのを待つ必要があることに
留意されたい。
【００５３】エントリ・ロック２０７が得られていると
き、Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４０１
では、そのエントリに現在記憶されているキー２０３は
変更されない。したがって、このルーチンは続いて、こ
のキー２０３を読み取り、要求された項目のキーと比較
し、それらが合致することを検証することができる（ス
テップ５０９）。合致が見つかった場合（ステップ５１
１で、名前が合致したか＝「ｙｅｓ」）、このエントリ
のリファレンス・カウント２１１が増分され、このエン
トリが「ビジー」としてマーク付けされ（ステップ５１
３）、このキャッシュ・エントリを指すポインタがＧｅ
ｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４００に返される
（ステップ５１７）。このキャッシュ・エントリに対す
るエントリ・ロック２０７が保持されることに留意され
たい。
き、Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４０１
では、そのエントリに現在記憶されているキー２０３は
変更されない。したがって、このルーチンは続いて、こ
のキー２０３を読み取り、要求された項目のキーと比較
し、それらが合致することを検証することができる（ス
テップ５０９）。合致が見つかった場合（ステップ５１
１で、名前が合致したか＝「ｙｅｓ」）、このエントリ
のリファレンス・カウント２１１が増分され、このエン
トリが「ビジー」としてマーク付けされ（ステップ５１
３）、このキャッシュ・エントリを指すポインタがＧｅ
ｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４００に返される
（ステップ５１７）。このキャッシュ・エントリに対す
るエントリ・ロック２０７が保持されることに留意され
たい。
【００５４】あるいは、このエントリに記憶されている
キー２０３が、要求された項目のキーに合致しない場合
（ステップ５１１で、キーが合致したか＝「ｎｏ」）
は、ロックレス参照ハッシュ・テーブルから返された
「ヒント」は誤っている可能性が高い。しかし、ロック
レス参照ハッシュ・テーブルでは、参照動作を実行する
うえでロックが得られない場合でも、すでに記憶されて
いるエントリ番号しか返されないので、Ｆｉｎｄ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン４０１が、エントリ・テー
ブル２０１の範囲外のメモリ位置にアクセスする恐れが
ないことに留意されたい。見つかったエントリのキー２
０３が、要求された項目のキーに合致しないと判定され
た後、このエントリに対するエントリ・ロック２０７が
解除され（ステップ５１５）、プロセスは、ステップ５
０１から繰り返される。
キー２０３が、要求された項目のキーに合致しない場合
（ステップ５１１で、キーが合致したか＝「ｎｏ」）
は、ロックレス参照ハッシュ・テーブルから返された
「ヒント」は誤っている可能性が高い。しかし、ロック
レス参照ハッシュ・テーブルでは、参照動作を実行する
うえでロックが得られない場合でも、すでに記憶されて
いるエントリ番号しか返されないので、Ｆｉｎｄ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン４０１が、エントリ・テー
ブル２０１の範囲外のメモリ位置にアクセスする恐れが
ないことに留意されたい。見つかったエントリのキー２
０３が、要求された項目のキーに合致しないと判定され
た後、このエントリに対するエントリ・ロック２０７が
解除され（ステップ５１５）、プロセスは、ステップ５
０１から繰り返される。
【００５５】次に、図６を参照すると、Ｉｎｓｅｒｔ＿
Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５が示されている。
このルーチンは、Ｇｅｔ＿Ｎｅｘｔ＿Ａｖａｉｌａｂｌ
ｅ＿Ｅｎｔｒｙと呼ばれるサブルーチンを呼び出すこと
によって開始し（ステップ６０１）、前述の修正ＬＲＵ
方式によって使用可能なキャッシュ・エントリ（「キャ
ッシュ・エントリＮ」と呼ぶ）を見つけ、そのエントリ
を指すポインタを返す。キャッシュ・エントリＮに対す
るエントリ・ロック２０７は得られており、その基準カ
ウンタ２１１が「ビジー」を示すように増分される。
Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５が示されている。
このルーチンは、Ｇｅｔ＿Ｎｅｘｔ＿Ａｖａｉｌａｂｌ
ｅ＿Ｅｎｔｒｙと呼ばれるサブルーチンを呼び出すこと
によって開始し（ステップ６０１）、前述の修正ＬＲＵ
方式によって使用可能なキャッシュ・エントリ（「キャ
ッシュ・エントリＮ」と呼ぶ）を見つけ、そのエントリ
を指すポインタを返す。キャッシュ・エントリＮに対す
るエントリ・ロック２０７は得られており、その基準カ
ウンタ２１１が「ビジー」を示すように増分される。
【００５６】次に、キャッシュ・ロック２１５が得ら
れ、他のキャッシュ挿入動作やキャッシュ削除動作が拒
否される（ステップ６０３）。キャッシュ・ロック２１
５が得られた後、Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔ
ｒｙと呼ばれるサブルーチンが呼び出される（ステップ
６０５）。Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン６０５の入力パラメータは、キャッシュ・エント
リＮを指すポインタである。Ｒｅｃｌａｉｍ＿Ｃａｃｈ
ｅ＿Ｅｎｔｒｙルーチン６０５は、キャッシュ・エント
リＮの古いキーのコピーをロックレス参照ハッシュ・テ
ーブルから削除し、次いで、キャッシュ・エントリＮの
最後のアクセス時間２０９を（それが空きキャッシュ・
エントリであることを示す）零に等しい値に設定する。
れ、他のキャッシュ挿入動作やキャッシュ削除動作が拒
否される（ステップ６０３）。キャッシュ・ロック２１
５が得られた後、Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔ
ｒｙと呼ばれるサブルーチンが呼び出される（ステップ
６０５）。Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン６０５の入力パラメータは、キャッシュ・エント
リＮを指すポインタである。Ｒｅｃｌａｉｍ＿Ｃａｃｈ
ｅ＿Ｅｎｔｒｙルーチン６０５は、キャッシュ・エント
リＮの古いキーのコピーをロックレス参照ハッシュ・テ
ーブルから削除し、次いで、キャッシュ・エントリＮの
最後のアクセス時間２０９を（それが空きキャッシュ・
エントリであることを示す）零に等しい値に設定する。
【００５７】これらの動作が完了すると、Ｉｎｓｅｒｔ
＿Ｃａｃｈｅ＿Ｅｎｔｒｙと呼ばれるサブルーチンを呼
び出すことによって、キャッシュ・エントリ・テーブル
２０１に記憶すべき項目のキーがロックレス参照ハッシ
ュ・テーブル２１７に挿入される（ステップ６０７）。
このサブルーチンは、合致するキーがまだロックレス参
照ハッシュ・テーブル内に含まれていないことを確認す
る検査を含む。したがって、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ
＿Ｅｎｔｒｙ６０７がＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔ
ｅｍ４０５に戻ると、リターン・コードが検査され（ス
テップ６０９）、キャッシュ・エントリＮのキーがロッ
クレス参照ハッシュ・テーブル２１７の新しい要素とし
て首尾良く挿入されたかどうかが調べられる。挿入が成
功した場合、他の挿入動作または削除動作を実行できる
ようにキャッシュ・ロック２１５が解除される（ステッ
プ６１１）。これに続いて、新たに作成されたキャッシ
ュ・エントリ（すなわち、キャッシュ・エントリＮ）が
Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４００に返さ
れる（ステップ６１３）。キャッシュ・エントリＮはま
だロックされ「ビジー」としてマーク付けされている。
さらに、このサブルーチンからのリターン・コードは、
これが新しいキャッシュ・エントリを指すポインタであ
ることをＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４０
０に知らせる。呼出し側スレッドは、この情報を使用し
て、関連する値２０５を他の情報源から得てこのキャッ
シュ・エントリに書き込む必要があるかどうかを判定す
る。
＿Ｃａｃｈｅ＿Ｅｎｔｒｙと呼ばれるサブルーチンを呼
び出すことによって、キャッシュ・エントリ・テーブル
２０１に記憶すべき項目のキーがロックレス参照ハッシ
ュ・テーブル２１７に挿入される（ステップ６０７）。
このサブルーチンは、合致するキーがまだロックレス参
照ハッシュ・テーブル内に含まれていないことを確認す
る検査を含む。したがって、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ
＿Ｅｎｔｒｙ６０７がＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔ
ｅｍ４０５に戻ると、リターン・コードが検査され（ス
テップ６０９）、キャッシュ・エントリＮのキーがロッ
クレス参照ハッシュ・テーブル２１７の新しい要素とし
て首尾良く挿入されたかどうかが調べられる。挿入が成
功した場合、他の挿入動作または削除動作を実行できる
ようにキャッシュ・ロック２１５が解除される（ステッ
プ６１１）。これに続いて、新たに作成されたキャッシ
ュ・エントリ（すなわち、キャッシュ・エントリＮ）が
Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４００に返さ
れる（ステップ６１３）。キャッシュ・エントリＮはま
だロックされ「ビジー」としてマーク付けされている。
さらに、このサブルーチンからのリターン・コードは、
これが新しいキャッシュ・エントリを指すポインタであ
ることをＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン４０
０に知らせる。呼出し側スレッドは、この情報を使用し
て、関連する値２０５を他の情報源から得てこのキャッ
シュ・エントリに書き込む必要があるかどうかを判定す
る。
【００５８】キャッシュ・エントリＮのキーと同じキー
を有する他のキャッシュ・エントリ（キャッシュ・エン
トリＦと呼ぶ）のキーがすでにロックレス参照ハッシュ
・テーブル２１７に記憶されていることをロックレス参
照ハッシュ・テーブル２１７が報告した場合（ステップ
６０９で、挿入は成功したか＝「ｎｏ」）、他の挿入動
作または削除動作を実行することができるようにキャッ
シュ・ロック２１５が解除される（ステップ６１５）。
この点で、他のスレッドがキャッシュ１２７中の項目を
変更し削除する可能性があり、したがって、キャッシュ
・エントリＦを指すポインタはもはや、そのキー２０３
がキャッシュ・エントリ・テーブル２０１に記憶すべき
項目のキーに合致している項目を確実に示しているわけ
ではない（すなわち、ロックレス参照ハッシュ・テーブ
ルから得たポインタは現在、「ヒント」になってい
る）。この「ヒント」が誤りであるかどうかを判定する
ために、キャッシュ・エントリに対するエントリ・ロッ
ク２０７が得られ（ステップ６１７）、要求された項目
のキーがキャッシュ・エントリＦのキーと比較される
（ステップ６１９）。キーが合致する場合（ステップ６
２１で、キーが合致したか＝「ｙｅｓ」）、ロックレス
参照ハッシュ・テーブル２１７によって報告された「ヒ
ント」は正確であり、要求された項目は実際に、すでに
キャッシュ・エントリ・テーブル２０１に記憶されてい
る。したがって、キャッシュ・エントリＦのリファレン
ス・カウント２１１が増分され、この項目が「ビジー」
であることが示され（ステップ６２３）、前に得たキャ
ッシュ・エントリＮのエントリ・ロック２０７が解除さ
れ、キャッシュ・エントリＮがこの時点では使用されな
いためにキャッシュ・エントリＮのリファレンス・カウ
ント２１１が減分される（ステップ６２５）。その代わ
り、キャッシュ・エントリＦを指すポインタが、これが
すでに存在しているキャッシュ・エントリであることの
報告と共に、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
４００に返される。この情報は、値２０５を他の情報源
から得てキャッシュ・エントリに記憶する必要があるか
否かを決定するので、呼出し側スレッドが知る情報とし
て重要である。
を有する他のキャッシュ・エントリ（キャッシュ・エン
トリＦと呼ぶ）のキーがすでにロックレス参照ハッシュ
・テーブル２１７に記憶されていることをロックレス参
照ハッシュ・テーブル２１７が報告した場合（ステップ
６０９で、挿入は成功したか＝「ｎｏ」）、他の挿入動
作または削除動作を実行することができるようにキャッ
シュ・ロック２１５が解除される（ステップ６１５）。
この点で、他のスレッドがキャッシュ１２７中の項目を
変更し削除する可能性があり、したがって、キャッシュ
・エントリＦを指すポインタはもはや、そのキー２０３
がキャッシュ・エントリ・テーブル２０１に記憶すべき
項目のキーに合致している項目を確実に示しているわけ
ではない（すなわち、ロックレス参照ハッシュ・テーブ
ルから得たポインタは現在、「ヒント」になってい
る）。この「ヒント」が誤りであるかどうかを判定する
ために、キャッシュ・エントリに対するエントリ・ロッ
ク２０７が得られ（ステップ６１７）、要求された項目
のキーがキャッシュ・エントリＦのキーと比較される
（ステップ６１９）。キーが合致する場合（ステップ６
２１で、キーが合致したか＝「ｙｅｓ」）、ロックレス
参照ハッシュ・テーブル２１７によって報告された「ヒ
ント」は正確であり、要求された項目は実際に、すでに
キャッシュ・エントリ・テーブル２０１に記憶されてい
る。したがって、キャッシュ・エントリＦのリファレン
ス・カウント２１１が増分され、この項目が「ビジー」
であることが示され（ステップ６２３）、前に得たキャ
ッシュ・エントリＮのエントリ・ロック２０７が解除さ
れ、キャッシュ・エントリＮがこの時点では使用されな
いためにキャッシュ・エントリＮのリファレンス・カウ
ント２１１が減分される（ステップ６２５）。その代わ
り、キャッシュ・エントリＦを指すポインタが、これが
すでに存在しているキャッシュ・エントリであることの
報告と共に、Ｇｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
４００に返される。この情報は、値２０５を他の情報源
から得てキャッシュ・エントリに記憶する必要があるか
否かを決定するので、呼出し側スレッドが知る情報とし
て重要である。
【００５９】あるいは、要求された項目のキーとキャッ
シュ・エントリＦのキーとの比較によって、キーが合致
しないと判定された場合（ステップ６２１で、キーが合
致したか＝「ｎｏ」）、ロックレス参照ハッシュ・テー
ブル２１７によって報告された「ヒント」は不正確であ
り、キャッシュ・エントリＦに対するエントリ・ロック
２０７が解除される。次いで、プロセスがステップ６０
３から繰り返され、キャッシュ・エントリＮをロックレ
ス参照ハッシュ・テーブル２１７に首尾良く挿入できる
かどうかが再び判定される。最後に、ループはステップ
６１３とステップ６２７のどちらかで終了する。
シュ・エントリＦのキーとの比較によって、キーが合致
しないと判定された場合（ステップ６２１で、キーが合
致したか＝「ｎｏ」）、ロックレス参照ハッシュ・テー
ブル２１７によって報告された「ヒント」は不正確であ
り、キャッシュ・エントリＦに対するエントリ・ロック
２０７が解除される。次いで、プロセスがステップ６０
３から繰り返され、キャッシュ・エントリＮをロックレ
ス参照ハッシュ・テーブル２１７に首尾良く挿入できる
かどうかが再び判定される。最後に、ループはステップ
６１３とステップ６２７のどちらかで終了する。
【００６０】次に、Ｇｅｔ＿Ｎｅｘｔ＿Ａｖａｉｌａｂ
ｌｅ＿Ｅｎｔｒｙルーチン６０１を図７に関連して詳し
く説明する。このルーチンは、Ｆｉｎｄ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙ＿ＬＲＵのサブルーチン呼出しを行うことに
よって開始する（ステップ７０１）。このサブルーチン
は、ビジーではないとみなされ、したがってＩｎｓｅｒ
ｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５によって挿入
すべき新しいキャッシュ項目として使用できるキャッシ
ュ・エントリ（キャッシュ・エントリＮと呼ぶ）を指す
ポインタを返す。しかし、この判定を下すためにロック
は使用されないので、キャッシュ・エントリＮの状況が
「非ビジー」であることは確実ではない。したがって、
この状況を検証しなければならない。まず、キャッシュ
・エントリＮに対するエントリ・ロック２０７を得るこ
とが試みられる（ステップ７０３）。この試みが成功す
るのは、キャッシュ・エントリＮがまだロックされてい
ない場合だけである。
ｌｅ＿Ｅｎｔｒｙルーチン６０１を図７に関連して詳し
く説明する。このルーチンは、Ｆｉｎｄ＿Ｃａｃｈｅ＿
Ｅｎｔｒｙ＿ＬＲＵのサブルーチン呼出しを行うことに
よって開始する（ステップ７０１）。このサブルーチン
は、ビジーではないとみなされ、したがってＩｎｓｅｒ
ｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５によって挿入
すべき新しいキャッシュ項目として使用できるキャッシ
ュ・エントリ（キャッシュ・エントリＮと呼ぶ）を指す
ポインタを返す。しかし、この判定を下すためにロック
は使用されないので、キャッシュ・エントリＮの状況が
「非ビジー」であることは確実ではない。したがって、
この状況を検証しなければならない。まず、キャッシュ
・エントリＮに対するエントリ・ロック２０７を得るこ
とが試みられる（ステップ７０３）。この試みが成功す
るのは、キャッシュ・エントリＮがまだロックされてい
ない場合だけである。
【００６１】キャッシュ・エントリＮをロックする試み
が成功しなかった場合（ステップ７０５で、ロックが成
功したか＝「ｎｏ」）、キャッシュ・エントリＮを使用
することはできず、他のキャッシュ・エントリを見つけ
るべきである。これは通常、すでにロックされているエ
ントリに対するロックを得るのを待つよりも、ロックさ
れていないキャッシュ・エントリを見つける方が速いか
らである。他のキャッシュ・エントリを見つけるには、
ステップ７０１からループを再開する。
が成功しなかった場合（ステップ７０５で、ロックが成
功したか＝「ｎｏ」）、キャッシュ・エントリＮを使用
することはできず、他のキャッシュ・エントリを見つけ
るべきである。これは通常、すでにロックされているエ
ントリに対するロックを得るのを待つよりも、ロックさ
れていないキャッシュ・エントリを見つける方が速いか
らである。他のキャッシュ・エントリを見つけるには、
ステップ７０１からループを再開する。
【００６２】しかし、キャッシュ・エントリＮをロック
する試みが成功した場合（ステップ７０５で、ロックが
成功したか＝「ｙｅｓ」）、キャッシュ・エントリＮの
リファレンス・カウント２１１が試験され、キャッシュ
・エントリＮがビジーであるかどうかが調べられる。こ
れを行うのは、前のスレッドがキャッシュ・エントリＮ
を「得て」、それに続いてリファレンス・カウント２１
１を減分せずにエントリ・ロック２０７を解除した可能
性があるからである。これは、キャッシュ・エントリＮ
を他のスレッドによって削除することも、あるいは再使
用することもできないようにするために行われる。
する試みが成功した場合（ステップ７０５で、ロックが
成功したか＝「ｙｅｓ」）、キャッシュ・エントリＮの
リファレンス・カウント２１１が試験され、キャッシュ
・エントリＮがビジーであるかどうかが調べられる。こ
れを行うのは、前のスレッドがキャッシュ・エントリＮ
を「得て」、それに続いてリファレンス・カウント２１
１を減分せずにエントリ・ロック２０７を解除した可能
性があるからである。これは、キャッシュ・エントリＮ
を他のスレッドによって削除することも、あるいは再使
用することもできないようにするために行われる。
【００６３】リファレンス・カウント２１１が零に等し
くない場合（ステップ７０７で、キャッシュ・エントリ
Ｎはビジーか＝「ｙｅｓ」）、キャッシュ・エントリＮ
を使用することはできず、他のキャッシュ・エントリを
見つけなければならない。これは、キャッシュ・エント
リＮに対するエントリ・ロック２０７を解除し、次いで
ステップ７０１からループを再開することによって行わ
れる。
くない場合（ステップ７０７で、キャッシュ・エントリ
Ｎはビジーか＝「ｙｅｓ」）、キャッシュ・エントリＮ
を使用することはできず、他のキャッシュ・エントリを
見つけなければならない。これは、キャッシュ・エント
リＮに対するエントリ・ロック２０７を解除し、次いで
ステップ７０１からループを再開することによって行わ
れる。
【００６４】しかし、リファレンス・カウント２１１が
零に等しい場合（ステップ７０７で、キャッシュ・エン
トリＮはビジーであるか＝「ｎｏ」）、キャッシュ・エ
ントリＮは、使用されていないキャッシュ・エントリと
して使用することができる。したがって、キャッシュ・
エントリＮのリファレンス・カウント２１１が（このエ
ントリが「ビジー」であることを示すために）増分され
る（ステップ７１１）。最後のアクセス時間２０９が零
よりも大きいことによって、キャッシュ・エントリＮが
キャッシュ項目を含むことが示されている場合（ステッ
プ７１３で、キャッシュ・エントリＮはキャッシュ項目
を含むか＝「ｙｅｓ」）、すでにキャッシュ・エントリ
Ｎに記憶されている項目が「フラッシュ」され、すなわ
ち、エントリ・テーブル２０１からキャッシュ項目の内
容が削除される前にキャッシュ項目の内容のクリーンナ
ップまたはメイン位置への書き直し、あるいはその両方
を実行するために、コールバック情報２２５によって指
定されたコールバック・ルーチンが呼び出される（ステ
ップ７１５）。あるいは、キャッシュ・エントリＮが使
用されたことがない場合（ステップ７１３で、キャッシ
ュ・エントリＮはキャッシュ項目を含むか＝「ｎｏ」）
は、コールバック関数は呼び出されない。
零に等しい場合（ステップ７０７で、キャッシュ・エン
トリＮはビジーであるか＝「ｎｏ」）、キャッシュ・エ
ントリＮは、使用されていないキャッシュ・エントリと
して使用することができる。したがって、キャッシュ・
エントリＮのリファレンス・カウント２１１が（このエ
ントリが「ビジー」であることを示すために）増分され
る（ステップ７１１）。最後のアクセス時間２０９が零
よりも大きいことによって、キャッシュ・エントリＮが
キャッシュ項目を含むことが示されている場合（ステッ
プ７１３で、キャッシュ・エントリＮはキャッシュ項目
を含むか＝「ｙｅｓ」）、すでにキャッシュ・エントリ
Ｎに記憶されている項目が「フラッシュ」され、すなわ
ち、エントリ・テーブル２０１からキャッシュ項目の内
容が削除される前にキャッシュ項目の内容のクリーンナ
ップまたはメイン位置への書き直し、あるいはその両方
を実行するために、コールバック情報２２５によって指
定されたコールバック・ルーチンが呼び出される（ステ
ップ７１５）。あるいは、キャッシュ・エントリＮが使
用されたことがない場合（ステップ７１３で、キャッシ
ュ・エントリＮはキャッシュ項目を含むか＝「ｎｏ」）
は、コールバック関数は呼び出されない。
【００６５】最後に、キャッシュ・エントリＮを指すポ
インタがＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン
に返される（ステップ７１７）。この時点で、キャッシ
ュ・エントリＮがロックされ「ビジー」とマーク付けさ
れることに留意されたい。
インタがＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン
に返される（ステップ７１７）。この時点で、キャッシ
ュ・エントリＮがロックされ「ビジー」とマーク付けさ
れることに留意されたい。
【００６６】次に、Ｆｉｎｄ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ
＿ＬＲＵルーチン７０１を図８に関連して説明する。こ
のルーチンは、キャッシュ・エントリ・テーブル２０１
が論理的に分割された数組の１６個のキャッシュ・エン
トリのうちの１組を選択することによって開始する（ス
テップ８０１）。選択は好ましくは、ラウンド・ロビン
方式で行われる。
＿ＬＲＵルーチン７０１を図８に関連して説明する。こ
のルーチンは、キャッシュ・エントリ・テーブル２０１
が論理的に分割された数組の１６個のキャッシュ・エン
トリのうちの１組を選択することによって開始する（ス
テップ８０１）。選択は好ましくは、ラウンド・ロビン
方式で行われる。
【００６７】次に、１６個のキャッシュ・エントリのそ
れぞれの最後のアクセス時間が分析され、それによっ
て、キャッシュ・エントリのリストを、最初に使用され
たものから最後に使用されたものへ昇順に作成すること
ができる（ステップ８０３）。次いで、零よりも大きな
リファレンス・カウントを有するキャッシュ・エントリ
がリストから削除され（ステップ８０５）、非ビジーで
あるとみなされるキャッシュ・エントリのみが残る。キ
ャッシュ項目を変更するのを妨げるためのロックが得ら
れないので、このようなキャッシュ・エントリの実際の
状況を保証することはできない。リストが空である場合
（ステップ８０７からの「ｙｅｓ」経路）、この組のキ
ャッシュ・エントリは使用されない。キャッシュ・エン
トリを見つけるための別の試みは、ステップ８０１から
ループを繰り返すことによって行われる。
れぞれの最後のアクセス時間が分析され、それによっ
て、キャッシュ・エントリのリストを、最初に使用され
たものから最後に使用されたものへ昇順に作成すること
ができる（ステップ８０３）。次いで、零よりも大きな
リファレンス・カウントを有するキャッシュ・エントリ
がリストから削除され（ステップ８０５）、非ビジーで
あるとみなされるキャッシュ・エントリのみが残る。キ
ャッシュ項目を変更するのを妨げるためのロックが得ら
れないので、このようなキャッシュ・エントリの実際の
状況を保証することはできない。リストが空である場合
（ステップ８０７からの「ｙｅｓ」経路）、この組のキ
ャッシュ・エントリは使用されない。キャッシュ・エン
トリを見つけるための別の試みは、ステップ８０１から
ループを繰り返すことによって行われる。
【００６８】しかし、リストが空ではない場合（ステッ
プ８０７からの「ｎｏ」経路）、リスト中の第１のキャ
ッシュ・エントリを指すポインタがＧｅｔ＿Ｎｅｘｔ＿
Ａｖａｉｌａｂｌｅ＿Ｅｎｔｒｙルーチン６０１に返さ
れる（ステップ８０９）。これが、非ビジーであるとみ
なされるキャッシュ・エントリのうちで最初に使用され
たエントリである。
プ８０７からの「ｎｏ」経路）、リスト中の第１のキャ
ッシュ・エントリを指すポインタがＧｅｔ＿Ｎｅｘｔ＿
Ａｖａｉｌａｂｌｅ＿Ｅｎｔｒｙルーチン６０１に返さ
れる（ステップ８０９）。これが、非ビジーであるとみ
なされるキャッシュ・エントリのうちで最初に使用され
たエントリである。
【００６９】代替実施形態では、単にその組のキャッシ
ュ・エントリを走査し、それまでに出会ったうちで最も
小さな非ビジー・エントリを追跡することによって、前
述のようにリストを実際に構築することが回避される。
ュ・エントリを走査し、それまでに出会ったうちで最も
小さな非ビジー・エントリを追跡することによって、前
述のようにリストを実際に構築することが回避される。
【００７０】次に、Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎ
ｔｒｙルーチン６０５を図９に関連して詳しく説明す
る。Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
６０５の呼び出し側はキャッシュ・ロック２１５を得る
ことに責任を負い、そのため、実行すべき様々なキャッ
シュ・エントリおよびハッシュ・テーブル・エントリは
確実に正確な結果をもたらす。
ｔｒｙルーチン６０５を図９に関連して詳しく説明す
る。Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン
６０５の呼び出し側はキャッシュ・ロック２１５を得る
ことに責任を負い、そのため、実行すべき様々なキャッ
シュ・エントリおよびハッシュ・テーブル・エントリは
確実に正確な結果をもたらす。
【００７１】Ｒｅｃｌａｉｍ＿Ｃａｃｈｅ＿Ｅｎｔｒｙ
ルーチン６０５への入力は、キャッシュ・エントリを指
すポインタである。このルーチンは、最後のアクセス時
間２０９が零に設定されることによって、キャッシュ・
エントリがすでに空であることが示されているかどうか
を判定することによって開始する。キャッシュ・エント
リがすでに空である場合（ステップ９０１からの「ｙｅ
ｓ」経路）、他には何も実行する必要がなく、ルーチン
は単にＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４
０５に戻る。前述のように、関連するキャッシュ項目が
スレッドによって得られるたびにリファレンス・カウン
トが増分される。キャッシュ・クロック２１３のカウン
ト値が最大クロック値から零に「ラップアラウンド」す
るときに誤って基準時間２０９を零に設定することを回
避するために、この値はただちに値「１」に設定され
る。次いで、キャッシュ・ロック２１５が得られ、非零
の最後のアクセス時間２０９を有するすべてのキャッシ
ュ・エントリの最後のアクセス時間２０９が「１」にリ
セットされる。これは、修正ＬＲＵキャッシュ置換方式
を一時的に妨害するものであるが、キャッシュ・エント
リの最後のアクセス時間２０９間の比較を容易にする利
点を有する。
ルーチン６０５への入力は、キャッシュ・エントリを指
すポインタである。このルーチンは、最後のアクセス時
間２０９が零に設定されることによって、キャッシュ・
エントリがすでに空であることが示されているかどうか
を判定することによって開始する。キャッシュ・エント
リがすでに空である場合（ステップ９０１からの「ｙｅ
ｓ」経路）、他には何も実行する必要がなく、ルーチン
は単にＩｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４
０５に戻る。前述のように、関連するキャッシュ項目が
スレッドによって得られるたびにリファレンス・カウン
トが増分される。キャッシュ・クロック２１３のカウン
ト値が最大クロック値から零に「ラップアラウンド」す
るときに誤って基準時間２０９を零に設定することを回
避するために、この値はただちに値「１」に設定され
る。次いで、キャッシュ・ロック２１５が得られ、非零
の最後のアクセス時間２０９を有するすべてのキャッシ
ュ・エントリの最後のアクセス時間２０９が「１」にリ
セットされる。これは、修正ＬＲＵキャッシュ置換方式
を一時的に妨害するものであるが、キャッシュ・エント
リの最後のアクセス時間２０９間の比較を容易にする利
点を有する。
【００７２】キャッシュ・エントリがまだ空ではない場
合（ステップ９０１の」ｎｏ」経路）、キャッシュ項目
のキー２０３が得られ（ステップ９０３）、ロックレス
参照ハッシュ・テーブル削除動作への入力として使用さ
れる（ステップ９０５）。この目的は、ロックレス参照
ハッシュ・テーブル２１７からその要素を削除すること
である。
合（ステップ９０１の」ｎｏ」経路）、キャッシュ項目
のキー２０３が得られ（ステップ９０３）、ロックレス
参照ハッシュ・テーブル削除動作への入力として使用さ
れる（ステップ９０５）。この目的は、ロックレス参照
ハッシュ・テーブル２１７からその要素を削除すること
である。
【００７３】次に、キャッシュ・エントリの最後のアク
セス時間２０９が、このキャッシュ・エントリが空であ
ることのインディケータとして零に設定される（ステッ
プ９０７）。このルーチンは次いで、単にＩｎｓｅｒｔ
＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５に戻ることによ
って終了する（ステップ９０９）。
セス時間２０９が、このキャッシュ・エントリが空であ
ることのインディケータとして零に設定される（ステッ
プ９０７）。このルーチンは次いで、単にＩｎｓｅｒｔ
＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４０５に戻ることによ
って終了する（ステップ９０９）。
【００７４】次に、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｅｎｔ
ｒｙルーチン６０７を図１０に関連して詳しく説明す
る。呼出し側ルーチン（Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉ
ｔｅｍ４０５）はすでにキャッシュ・ロック２１５を得
ており、そのため、ロックレス参照ハッシュ・テーブル
２１７へのアクセスが、単なる「ヒント」ではなく正確
な結果を返すことに留意されたい。Ｉｎｓｅｒｔ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン６０７は、ロックレス参照
ハッシュ・テーブル２１７に対する参照動作を実行し、
新しいキャッシュ項目のキー２０３のコピーがすでにハ
ッシュ・テーブル中にあり、それによって、挿入すべき
キャッシュ項目がすでにキャッシュ・エントリ・テーブ
ル２０１に記憶されていることが示されているかどうか
を判定することによって開始する（ステップ１００
１）。キー２０３のコピーが見つかったと報告された場
合（ステップ１００３でキャッシュ・ヒットか＝「ｙｅ
ｓ」）は、同じキーを有するキャッシュ項目をキャッシ
ュ・エントリ・テーブル２０１に挿入することはできな
い。したがって、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン６０７は、動作が成功しなかったことを示す
リターン・コードと共に呼出し側ルーチンに戻る（ステ
ップ１００５）。
ｒｙルーチン６０７を図１０に関連して詳しく説明す
る。呼出し側ルーチン（Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｉ
ｔｅｍ４０５）はすでにキャッシュ・ロック２１５を得
ており、そのため、ロックレス参照ハッシュ・テーブル
２１７へのアクセスが、単なる「ヒント」ではなく正確
な結果を返すことに留意されたい。Ｉｎｓｅｒｔ＿Ｃａ
ｃｈｅ＿Ｅｎｔｒｙルーチン６０７は、ロックレス参照
ハッシュ・テーブル２１７に対する参照動作を実行し、
新しいキャッシュ項目のキー２０３のコピーがすでにハ
ッシュ・テーブル中にあり、それによって、挿入すべき
キャッシュ項目がすでにキャッシュ・エントリ・テーブ
ル２０１に記憶されていることが示されているかどうか
を判定することによって開始する（ステップ１００
１）。キー２０３のコピーが見つかったと報告された場
合（ステップ１００３でキャッシュ・ヒットか＝「ｙｅ
ｓ」）は、同じキーを有するキャッシュ項目をキャッシ
ュ・エントリ・テーブル２０１に挿入することはできな
い。したがって、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン６０７は、動作が成功しなかったことを示す
リターン・コードと共に呼出し側ルーチンに戻る（ステ
ップ１００５）。
【００７５】しかし、キー２０３のコピーがロックレス
参照ハッシュ・テーブル２１７では見つからなかったと
報告された場合（ステップ１００３でキャッシュ・ヒッ
トか＝「ｎｏ」）、キー２１９をハッシュ・テーブル中
のキーとして使用し、新しいキャッシュ・エントリ（キ
ャッシュ・エントリＮ）を指すポインタを、記憶すべき
関連する値として使用して、ロックレス参照ハッシュ・
テーブル２１７への挿入が実行される（ステップ１００
７）。次いで、入力キー２１９がキャッシュ・エントリ
Ｎのキー２０３にコピーされる（ステップ１００９）。
この動作が完了すると、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｅ
ｎｔｒｙルーチン６０７は、動作が成功したことを示す
リターン・コードと共に呼び出し側ルーチンに戻る（ス
テップ１０１１）。
参照ハッシュ・テーブル２１７では見つからなかったと
報告された場合（ステップ１００３でキャッシュ・ヒッ
トか＝「ｎｏ」）、キー２１９をハッシュ・テーブル中
のキーとして使用し、新しいキャッシュ・エントリ（キ
ャッシュ・エントリＮ）を指すポインタを、記憶すべき
関連する値として使用して、ロックレス参照ハッシュ・
テーブル２１７への挿入が実行される（ステップ１００
７）。次いで、入力キー２１９がキャッシュ・エントリ
Ｎのキー２０３にコピーされる（ステップ１００９）。
この動作が完了すると、Ｉｎｓｅｒｔ＿Ｃａｃｈｅ＿Ｅ
ｎｔｒｙルーチン６０７は、動作が成功したことを示す
リターン・コードと共に呼び出し側ルーチンに戻る（ス
テップ１０１１）。
【００７６】この議論では次に、図１１のフローチャー
トに関連してＤｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン１１００に焦点を当てる。このルーチンの開始時
には、呼出し側はすでにＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン４００を呼び出しており、削除すべきキャッ
シュ項目に対するエントリ・ロック２０７を得ている。
まず、呼出し側が、削除すべきキャッシュ・エントリに
対するエントリ・ロック２０７を得ているか（ステップ
１１０１で、キャッシュ・エントリがロックされている
か＝「ｎｏ」）どうかを調べる試験が実行される。この
キャッシュ・エントリがロックされていない場合、Ｄｅ
ｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１００を
実行することはできず、このルーチンは、この失敗を示
すリターン・コードと共に呼出し側に戻る（ステップ１
１０３）。
トに関連してＤｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン１１００に焦点を当てる。このルーチンの開始時
には、呼出し側はすでにＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒ
ｙルーチン４００を呼び出しており、削除すべきキャッ
シュ項目に対するエントリ・ロック２０７を得ている。
まず、呼出し側が、削除すべきキャッシュ・エントリに
対するエントリ・ロック２０７を得ているか（ステップ
１１０１で、キャッシュ・エントリがロックされている
か＝「ｎｏ」）どうかを調べる試験が実行される。この
キャッシュ・エントリがロックされていない場合、Ｄｅ
ｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１００を
実行することはできず、このルーチンは、この失敗を示
すリターン・コードと共に呼出し側に戻る（ステップ１
１０３）。
【００７７】あるいは、ユーザが、削除すべきキャッシ
ュ・エントリに対するエントリ・ロック２０７を得てい
る場合（ステップ１１０１で、キャッシュ・エントリが
ロックされているか＝「ｙｅｓ」）、次のステップは、
このキャッシュ・エントリのリファレンス・カウント２
１１が１に等しく、このキャッシュ・エントリを「ビジ
ー」としてマーク付けしているスレッドが１つだけであ
ることが示されているかどうかを調べる試験を行う（ス
テップ１１０５）ことである。定義上、リファレンス・
カウント２１１は、削除動作を実行したいスレッドによ
って増分されているので、リファレンス・カウント２１
１が１に等しいことから、削除を実行したいスレッドは
このキャッシュ・エントリの唯一のユーザであると推定
することができる。したがって、他のスレッドもこのキ
ャッシュ項目を「ビジー」としてマーク付けしている場
合（ステップ１１０５で、キャッシュ・エントリリファ
レンス・カウントは１に等しいか＝「ｎｏ」）、Ｄｅｌ
ｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１００を実
行することはできず、このルーチンは、この失敗を示す
リターン・コードと共に呼出し側に戻る（ステップ１１
０７）。
ュ・エントリに対するエントリ・ロック２０７を得てい
る場合（ステップ１１０１で、キャッシュ・エントリが
ロックされているか＝「ｙｅｓ」）、次のステップは、
このキャッシュ・エントリのリファレンス・カウント２
１１が１に等しく、このキャッシュ・エントリを「ビジ
ー」としてマーク付けしているスレッドが１つだけであ
ることが示されているかどうかを調べる試験を行う（ス
テップ１１０５）ことである。定義上、リファレンス・
カウント２１１は、削除動作を実行したいスレッドによ
って増分されているので、リファレンス・カウント２１
１が１に等しいことから、削除を実行したいスレッドは
このキャッシュ・エントリの唯一のユーザであると推定
することができる。したがって、他のスレッドもこのキ
ャッシュ項目を「ビジー」としてマーク付けしている場
合（ステップ１１０５で、キャッシュ・エントリリファ
レンス・カウントは１に等しいか＝「ｎｏ」）、Ｄｅｌ
ｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１００を実
行することはできず、このルーチンは、この失敗を示す
リターン・コードと共に呼出し側に戻る（ステップ１１
０７）。
【００７８】しかし、このキャッシュ・エントリを削除
したいスレッドがこのキャッシュ・エントリの唯一のユ
ーザである場合（ステップ１１０５で、キャッシュ・エ
ントリリファレンス・カウントは１に等しいか＝「ｙｅ
ｓ」）、削除を首尾良く実行することができる。これは
好ましくは、このキャッシュ・エントリに含まれるキャ
ッシュ項目（すなわち、キー２０３および値２０５）を
得て（ステップ１１０９）、コールバック情報２２５で
指定されたコールバック関数を呼び出し、削除中のキャ
ッシュ項目をフラッシュさせる（すなわち、キャッシュ
項目の内容がエントリ・テーブル２０１から削除される
前にそのキャッシュ項目の内容のクリーンナップまたは
メイン位置への書き直し、あるいはその両方を行う）こ
とによって行われる。
したいスレッドがこのキャッシュ・エントリの唯一のユ
ーザである場合（ステップ１１０５で、キャッシュ・エ
ントリリファレンス・カウントは１に等しいか＝「ｙｅ
ｓ」）、削除を首尾良く実行することができる。これは
好ましくは、このキャッシュ・エントリに含まれるキャ
ッシュ項目（すなわち、キー２０３および値２０５）を
得て（ステップ１１０９）、コールバック情報２２５で
指定されたコールバック関数を呼び出し、削除中のキャ
ッシュ項目をフラッシュさせる（すなわち、キャッシュ
項目の内容がエントリ・テーブル２０１から削除される
前にそのキャッシュ項目の内容のクリーンナップまたは
メイン位置への書き直し、あるいはその両方を行う）こ
とによって行われる。
【００７９】次に、キャッシュ・ロック２１５が得られ
（ステップ１１１３）、ロックレス参照ハッシュ・テー
ブルに対して削除動作が実行され、削除すべきキャッシ
ュ要素のキーによって指定された要素が削除される（ス
テップ１１１５）。
（ステップ１１１３）、ロックレス参照ハッシュ・テー
ブルに対して削除動作が実行され、削除すべきキャッシ
ュ要素のキーによって指定された要素が削除される（ス
テップ１１１５）。
【００８０】次いで、キャッシュ・ロック２１５が解除
され（ステップ１１１７）、このキャッシュ・エントリ
の最後のアクセス時間２０９およびリファレンス・カウ
ント２１１が零に設定され、このキャッシュ・エントリ
が使用可能なキャッシュ・エントリとして選択できるも
のであることが示される（ステップ１１１９）。最後
に、Ｄｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１
１００が、首尾良く完了したことを示すリターン・コー
ドと共にユーザに戻る（ステップ１１２１）。
され（ステップ１１１７）、このキャッシュ・エントリ
の最後のアクセス時間２０９およびリファレンス・カウ
ント２１１が零に設定され、このキャッシュ・エントリ
が使用可能なキャッシュ・エントリとして選択できるも
のであることが示される（ステップ１１１９）。最後
に、Ｄｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１
１００が、首尾良く完了したことを示すリターン・コー
ドと共にユーザに戻る（ステップ１１２１）。
【００８１】本発明のキャッシュ１２７の使用法は簡単
である。キャッシュ項目がすでにキャッシュ・エントリ
・テーブル２０１に記憶されているかどうかをスレッド
が知ることはできないので、参照関数と挿入関数は共に
前述のＧｅｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４００に
よってアクセスされる。このルーチンは常に、「ビジ
ー」とマーク付けされたロックされたキャッシュ・エン
トリを指すポインタを返す。キャッシュ・エントリが新
しいものであり、すなわち、キャッシュ・エントリが新
しく、現在このキー２０３に関して記憶されている値２
０５がないことを意味するかどうかをユーザに知らせる
リターン・コードも提供される。
である。キャッシュ項目がすでにキャッシュ・エントリ
・テーブル２０１に記憶されているかどうかをスレッド
が知ることはできないので、参照関数と挿入関数は共に
前述のＧｅｔ＿Ｃａｃｈｅ＿Ｉｔｅｍルーチン４００に
よってアクセスされる。このルーチンは常に、「ビジ
ー」とマーク付けされたロックされたキャッシュ・エン
トリを指すポインタを返す。キャッシュ・エントリが新
しいものであり、すなわち、キャッシュ・エントリが新
しく、現在このキー２０３に関して記憶されている値２
０５がないことを意味するかどうかをユーザに知らせる
リターン・コードも提供される。
【００８２】新しいキャッシュ・エントリを指すポイン
タが返されている場合、ユーザ・スレッドは、代替情報
源から関連する情報を得る処置をとることができる。こ
のような動作は、アプリケーションに特有のものであ
り、その詳しい説明は本開示の範囲を超えている。
タが返されている場合、ユーザ・スレッドは、代替情報
源から関連する情報を得る処置をとることができる。こ
のような動作は、アプリケーションに特有のものであ
り、その詳しい説明は本開示の範囲を超えている。
【００８３】ユーザ・スレッドは、キーに関連付けられ
た情報を得る場合、キャッシュ・エントリに対するエン
トリ・ロック２０７を保持しているので、この情報を直
接このキャッシュ・エントリに記憶することができる。
キャッシュ１２７のすべてのユーザは、特定のキャッシ
ュ・エントリに対するエントリ・ロックが得られていな
いかぎり、キャッシュ・エントリ・テーブル２０１への
書込みは禁止されるという規則に従うべきである。
た情報を得る場合、キャッシュ・エントリに対するエン
トリ・ロック２０７を保持しているので、この情報を直
接このキャッシュ・エントリに記憶することができる。
キャッシュ１２７のすべてのユーザは、特定のキャッシ
ュ・エントリに対するエントリ・ロックが得られていな
いかぎり、キャッシュ・エントリ・テーブル２０１への
書込みは禁止されるという規則に従うべきである。
【００８４】ユーザ・スレッドは、もはやキャッシュ・
エントリ・テーブル２０１に項目を記憶したくないとき
には、エントリ・ロック２０７を解除する。ユーザ・ス
レッドは、情報がキャッシュに残るかどうかも、あるい
は他のキャッシュ項目用の空間を設けるためにスワップ
アウトされかどうかも気にしない場合、エントリ・ロッ
ク２０７を解除する直前にリファレンス・カウント２１
１の減分も行う。しかし、ユーザ・スレッドは、このキ
ー２０３を有するキャッシュ項目をキャッシュ・エント
リ・テーブル２０１に残したい場合、リファレンス・カ
ウント２１１を減分しておくことなしにエントリ・ロッ
ク２０７を解除する。これは、キャッシュ置換関数が常
に、このキャッシュ・エントリを「ビジー」とみなし、
置換すべきものとして選択することがないことを意味す
る。ユーザ・スレッドは、このキー２０３を有するキャ
ッシュ項目をキャッシュ・エントリ・テーブル２０１に
残すことができるが、それによって他のスレッドがこの
キャッシュ項目の値２０５を修正しないことが保証され
るわけではないことにも留意されたい。
エントリ・テーブル２０１に項目を記憶したくないとき
には、エントリ・ロック２０７を解除する。ユーザ・ス
レッドは、情報がキャッシュに残るかどうかも、あるい
は他のキャッシュ項目用の空間を設けるためにスワップ
アウトされかどうかも気にしない場合、エントリ・ロッ
ク２０７を解除する直前にリファレンス・カウント２１
１の減分も行う。しかし、ユーザ・スレッドは、このキ
ー２０３を有するキャッシュ項目をキャッシュ・エント
リ・テーブル２０１に残したい場合、リファレンス・カ
ウント２１１を減分しておくことなしにエントリ・ロッ
ク２０７を解除する。これは、キャッシュ置換関数が常
に、このキャッシュ・エントリを「ビジー」とみなし、
置換すべきものとして選択することがないことを意味す
る。ユーザ・スレッドは、このキー２０３を有するキャ
ッシュ項目をキャッシュ・エントリ・テーブル２０１に
残すことができるが、それによって他のスレッドがこの
キャッシュ項目の値２０５を修正しないことが保証され
るわけではないことにも留意されたい。
【００８５】ユーザ・スレッドは、キャッシュ項目を削
除したいとき、まずＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン４００を介してキャッシュ・エントリを得ること
によってこれを行う。次いで、ユーザ・スレッドは単に
Ｄｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１０
０を呼び出す。ユーザ・スレッドがこの特定のエントリ
の唯一のユーザである場合、「成功」を示すリターン・
コードが返されるはずである。
除したいとき、まずＧｅｔ＿Ｃａｃｈｅ＿Ｅｎｔｒｙル
ーチン４００を介してキャッシュ・エントリを得ること
によってこれを行う。次いで、ユーザ・スレッドは単に
Ｄｅｌｅｔｅ＿Ｃａｃｈｅ＿Ｅｎｔｒｙルーチン１１０
０を呼び出す。ユーザ・スレッドがこの特定のエントリ
の唯一のユーザである場合、「成功」を示すリターン・
コードが返されるはずである。
【００８６】好ましい実施形態は、キャッシュ全域動作
とキャッシュ・エントリ動作に分割されるいくつかのル
ーチンを提供する。これらのルーチンは、前述のすべて
のルーチンを含み、好ましくは、複数のＣＰＵを有する
Ｓｕｎ ＳＰＡＲＣマシン上でＣ＋＋プログラミング言
語によって実施される。当業者なら、下記の説明からこ
れらのルーチンを容易に作成できよう。
とキャッシュ・エントリ動作に分割されるいくつかのル
ーチンを提供する。これらのルーチンは、前述のすべて
のルーチンを含み、好ましくは、複数のＣＰＵを有する
Ｓｕｎ ＳＰＡＲＣマシン上でＣ＋＋プログラミング言
語によって実施される。当業者なら、下記の説明からこ
れらのルーチンを容易に作成できよう。
【００８７】キャッシュ全域動作 − ｃｒｅａｔｅ＿ｃａｃｈｅ：このルーチンはキ
ャッシュ１２７を作成する。この入力パラメータは下記
のとおりである。 − ｎｕｍｂｅｒ＿ｏｆ＿ｃａｃｈｅ＿ｅｎｔｒｉ
ｅｓ − ｓｉｚｅ＿ｏｆ＿ｅａｃｈ＿ｃａｃｈｅ＿ｉｔ
ｅｍ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｅｑｕａｌ＿ｆｕｎｃ
ｔｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｈａｓｈ＿ｆｕｎｃｔ
ｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｇｅｔ＿ｋｅｙ＿ｆｕ
ｎｃｔｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｗｒｉｔｅ＿ｂａｃｋ
＿ｆｕｎｃｔｉｏｎ
ャッシュ１２７を作成する。この入力パラメータは下記
のとおりである。 − ｎｕｍｂｅｒ＿ｏｆ＿ｃａｃｈｅ＿ｅｎｔｒｉ
ｅｓ − ｓｉｚｅ＿ｏｆ＿ｅａｃｈ＿ｃａｃｈｅ＿ｉｔ
ｅｍ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｅｑｕａｌ＿ｆｕｎｃ
ｔｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｈａｓｈ＿ｆｕｎｃｔ
ｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｇｅｔ＿ｋｅｙ＿ｆｕ
ｎｃｔｉｏｎ − ｐｏｉｎｔｅｒ＿ｔｏ＿ｗｒｉｔｅ＿ｂａｃｋ
＿ｆｕｎｃｔｉｏｎ
【００８８】ｃｒｅａｔｅ＿ｃａｃｈｅルーチンの入力
パラメータを下記に説明する。 − ｎｕｍｂｅｒ＿ｏｆ＿ｃａｃｈｅ＿ｅｎｔｒｉ
ｅｓ：キャッシュ中のエントリの数を定義する。 − ｓｉｚｅ＿ｏｆ＿ｅａｃｈ＿ｉｔｅｍ：キャッ
シュ中の各項目ごとに割り振るべきメモリのサイズを定
義する。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｅｑｕａｌ＿ｆｕｎｃ
ｔｉｏｎ：ｅｑｕａｌ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔ
ｅｒ＿ｔｏ＿ｋｅｙｌ，ｐｏｉｎｔｅｒ＿ｔｏ＿ｋｅｙ
２）、すなわちｋｅｙ１がｋｅｙ２に等しい場合に
「真」の値を返す関数を指す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｈａｓｈ＿ｆｕｎｃｔ
ｉｏｎ：ｈａｓｈ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔｅｒ
＿ｔｏ＿ｋｅｙ）、すなわち入力キーにハッシュ関数を
適用し結果を返す関数を指す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｇｅｔ＿ｆｕｎｃｔｉ
ｏｎ：ｇｅｔ＿ｋｅｙ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔ
ｅｒ＿ｔｏ＿ｃａｃｈｅ＿ｅｎｔｒｙ）、すなわちキャ
ッシュ項目に属するキーを指すポインタを返す関数を指
す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｗｒｉｔｅ＿ｂａｃｋ
＿ｆｕｎｃｔｉｏｎ：ｗｒｉｔｅ＿ｂａｃｋ＿ｆｕｎｃ
ｔｉｏｎ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｌｏｃｋｅｄ＿ｃａ
ｃｈｅ＿ｅｎｔｒｙ）、すなわち上記で詳しく説明した
ようにキャッシュ項目をフラッシュさせる関数を指す。
これは、特定のアプリケーションに必要な書き直し動作
またはクリーンナップ動作を実行するために必要であ
る。
パラメータを下記に説明する。 − ｎｕｍｂｅｒ＿ｏｆ＿ｃａｃｈｅ＿ｅｎｔｒｉ
ｅｓ：キャッシュ中のエントリの数を定義する。 − ｓｉｚｅ＿ｏｆ＿ｅａｃｈ＿ｉｔｅｍ：キャッ
シュ中の各項目ごとに割り振るべきメモリのサイズを定
義する。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｅｑｕａｌ＿ｆｕｎｃ
ｔｉｏｎ：ｅｑｕａｌ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔ
ｅｒ＿ｔｏ＿ｋｅｙｌ，ｐｏｉｎｔｅｒ＿ｔｏ＿ｋｅｙ
２）、すなわちｋｅｙ１がｋｅｙ２に等しい場合に
「真」の値を返す関数を指す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｈａｓｈ＿ｆｕｎｃｔ
ｉｏｎ：ｈａｓｈ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔｅｒ
＿ｔｏ＿ｋｅｙ）、すなわち入力キーにハッシュ関数を
適用し結果を返す関数を指す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｇｅｔ＿ｆｕｎｃｔｉ
ｏｎ：ｇｅｔ＿ｋｅｙ＿ｆｕｎｃｔｉｏｎ（ｐｏｉｎｔ
ｅｒ＿ｔｏ＿ｃａｃｈｅ＿ｅｎｔｒｙ）、すなわちキャ
ッシュ項目に属するキーを指すポインタを返す関数を指
す。 − ｐｏｉｎｔｅｒ＿ｔｏ＿ｗｒｉｔｅ＿ｂａｃｋ
＿ｆｕｎｃｔｉｏｎ：ｗｒｉｔｅ＿ｂａｃｋ＿ｆｕｎｃ
ｔｉｏｎ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｌｏｃｋｅｄ＿ｃａ
ｃｈｅ＿ｅｎｔｒｙ）、すなわち上記で詳しく説明した
ようにキャッシュ項目をフラッシュさせる関数を指す。
これは、特定のアプリケーションに必要な書き直し動作
またはクリーンナップ動作を実行するために必要であ
る。
【００８９】− ｇｅｔ＿ｃａｃｈｅ＿ｅｎｔｒｙ（ｃ
ａｃｈｅ＿ｉｄ ｋｅｙ，ｂｏｏｌ＆ｎｅｗ＿ｃａｃｈ
ｅ＿ｅｎｔｒｙ）：あるキャッシュ項目のキーを指すポ
インタが与えられた場合、このルーチンは、合致する同
じキーを有するキャッシュ項目を含むキャッシュ・エン
トリを指すポインタを返す。ブール値ｎｅｗ＿ｃａｃｈ
ｅ＿ｅｎｔｒｙは、キャッシュ項目が新しい項目である
か、それとも既存の項目であるかを示す。 − ｄｅｌｅｔｅ＿ｃａｃｈｅ＿ｅｎｔｒｙ（ｃａｃｈ
ｅ＿ｅｎｔｒｙ＊ｃｐ）：このルーチンは、キャッシュ
・エントリ（ポインタ）に含まれるキャッシュ項目をキ
ャッシュから削除する。このルーチンを呼び出す前に、
キャッシュ・エントリを専用に使用できるようにまずロ
ックしておかなければならない。
ａｃｈｅ＿ｉｄ ｋｅｙ，ｂｏｏｌ＆ｎｅｗ＿ｃａｃｈ
ｅ＿ｅｎｔｒｙ）：あるキャッシュ項目のキーを指すポ
インタが与えられた場合、このルーチンは、合致する同
じキーを有するキャッシュ項目を含むキャッシュ・エン
トリを指すポインタを返す。ブール値ｎｅｗ＿ｃａｃｈ
ｅ＿ｅｎｔｒｙは、キャッシュ項目が新しい項目である
か、それとも既存の項目であるかを示す。 − ｄｅｌｅｔｅ＿ｃａｃｈｅ＿ｅｎｔｒｙ（ｃａｃｈ
ｅ＿ｅｎｔｒｙ＊ｃｐ）：このルーチンは、キャッシュ
・エントリ（ポインタ）に含まれるキャッシュ項目をキ
ャッシュから削除する。このルーチンを呼び出す前に、
キャッシュ・エントリを専用に使用できるようにまずロ
ックしておかなければならない。
【００９０】キャッシュ・エントリ動作： − ｍｕｔｅｘ＿ｌｏｃｋ（ｐｏｉｎｔｅｒ＿ｔｏ＿
ｃａｃｈｅ＿ｅｎｔｒｙ）：この関数は、指示されたｃ
ａｃｈｅ＿ｅｎｔｒｙに対するエントリ・ロック２０７
を得るものである。エントリ・ロック２０７は相互排他
ロックである。 − ｍｕｔｅｘ＿ｕｎｌｏｃｋ（ｐｏｉｎｔｅｒ＿ｔ
ｏ＿ｃａｃｈｅ＿ｅｎｔｒｙ）：この関数は、指示され
たｃａｃｈｅ＿ｅｎｔｒｙに対するエントリ・ロック２
０７を解除するものである。 − ｈｏｌｄ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｃａｃｈｅ＿
ｅｎｔｒｙ）：この関数は、指示されたキャッシュ・エ
ントリのリファレンス・カウント２１１を増分するもの
である。リファレンス・カウント２１１を増分すると、
キャッシュ・エントリは「ビジー」としてマーク付けさ
れる。ｇｅｔ＿ｃａｃｈｅ＿ｅｎｔｒｙルーチンも、そ
れが返すキャッシュ・エントリのリファレンス・カウン
ト２１１を増分するが、スレッドはエントリを解除し
（すなわち、リファレンス・カウント２１１を減分
し）、次いでこれを変更してエントリに再び「ビジー」
とマーク付けすることが可能である。ホールド関数はこ
のために提供される。ホールド関数を呼び出す前に、指
示されたキャッシュ・エントリに対するエントリ・ロッ
ク２０７を得ておかなければならない。 − ｒｅｌｅａｓｅ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｃａｃ
ｈｅ＿ｅｎｔｒｙ）：この関数は、キャッシュ・エント
リのリファレンス・カウント２１１を減分する。リリー
ス関数を呼び出す前に、指示されたキャッシュ・エント
リに対するエントリ・ロック２０７を得ておかなければ
ならない。 − ｇｅｔ＿ｋｅｙ（）：この関数は、キャッシュ・
キー２０３を指すポインタを返す。 − ｇｅｔ＿ｖａｌｕｅ（）：この関数は、値２０５
を指すポインタを返す。
ｃａｃｈｅ＿ｅｎｔｒｙ）：この関数は、指示されたｃ
ａｃｈｅ＿ｅｎｔｒｙに対するエントリ・ロック２０７
を得るものである。エントリ・ロック２０７は相互排他
ロックである。 − ｍｕｔｅｘ＿ｕｎｌｏｃｋ（ｐｏｉｎｔｅｒ＿ｔ
ｏ＿ｃａｃｈｅ＿ｅｎｔｒｙ）：この関数は、指示され
たｃａｃｈｅ＿ｅｎｔｒｙに対するエントリ・ロック２
０７を解除するものである。 − ｈｏｌｄ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｃａｃｈｅ＿
ｅｎｔｒｙ）：この関数は、指示されたキャッシュ・エ
ントリのリファレンス・カウント２１１を増分するもの
である。リファレンス・カウント２１１を増分すると、
キャッシュ・エントリは「ビジー」としてマーク付けさ
れる。ｇｅｔ＿ｃａｃｈｅ＿ｅｎｔｒｙルーチンも、そ
れが返すキャッシュ・エントリのリファレンス・カウン
ト２１１を増分するが、スレッドはエントリを解除し
（すなわち、リファレンス・カウント２１１を減分
し）、次いでこれを変更してエントリに再び「ビジー」
とマーク付けすることが可能である。ホールド関数はこ
のために提供される。ホールド関数を呼び出す前に、指
示されたキャッシュ・エントリに対するエントリ・ロッ
ク２０７を得ておかなければならない。 − ｒｅｌｅａｓｅ（ｐｏｉｎｔｅｒ＿ｔｏ＿ｃａｃ
ｈｅ＿ｅｎｔｒｙ）：この関数は、キャッシュ・エント
リのリファレンス・カウント２１１を減分する。リリー
ス関数を呼び出す前に、指示されたキャッシュ・エント
リに対するエントリ・ロック２０７を得ておかなければ
ならない。 − ｇｅｔ＿ｋｅｙ（）：この関数は、キャッシュ・
キー２０３を指すポインタを返す。 − ｇｅｔ＿ｖａｌｕｅ（）：この関数は、値２０５
を指すポインタを返す。
【００９１】本発明を特定の実施形態に関連して説明し
た。しかし、当業者には、前述の好ましい実施形態の態
様以外の特定の態様で本発明を具体化できることが容易
に明らかになろう。これは、本発明の趣旨から逸脱せず
に行うことができる。好ましい実施形態は例示的なもの
に過ぎず、制限的なものとみなすべきものではない。本
発明の範囲は、上記の説明ではなく添付の特許請求の範
囲によって与えられ、特許請求の範囲内のすべての変形
および等価物は、本発明に包含されるものである。
た。しかし、当業者には、前述の好ましい実施形態の態
様以外の特定の態様で本発明を具体化できることが容易
に明らかになろう。これは、本発明の趣旨から逸脱せず
に行うことができる。好ましい実施形態は例示的なもの
に過ぎず、制限的なものとみなすべきものではない。本
発明の範囲は、上記の説明ではなく添付の特許請求の範
囲によって与えられ、特許請求の範囲内のすべての変形
および等価物は、本発明に包含されるものである。
【図１】 本発明と共に使用すべき例示的なマルチスレ
ッド・システムのブロック図である。
ッド・システムのブロック図である。
【図２】 本発明の実施形態によるキャッシュのブロッ
ク図である。
ク図である。
【図３】 本発明の一態様によるキャッシュ項目とハッ
シュ・テーブル項目との間の関係を示す図である。
シュ・テーブル項目との間の関係を示す図である。
【図４】 本発明の一実施形態によるｇｅｔ＿ｃａｃｈ
ｅ＿ｅｎｔｒｙルーチンのフローチャートである。
ｅ＿ｅｎｔｒｙルーチンのフローチャートである。
【図５】 本発明の一実施形態によるｆｉｎｄ＿ｃａｃ
ｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
ｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
【図６】 本発明の一実施形態によるｉｎｓｅｒｔ＿ｃ
ａｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートであ
る。
ａｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートであ
る。
【図７】 本発明の一態様によるｇｅｔ＿ｎｅｘｔ＿ａ
ｖａｉｌａｂｌｅ＿ｅｎｔｒｙルーチンのフローチャー
トである。
ｖａｉｌａｂｌｅ＿ｅｎｔｒｙルーチンのフローチャー
トである。
【図８】 本発明の一態様によるｆｉｎｄ＿ｃａｃｈｅ
＿ｅｎｔｒｙ＿ｌｅａｓｔ＿ｒｅｃｅｎｔｌｙ＿ｕｓｅ
ｄルーチンのフローチャートである。
＿ｅｎｔｒｙ＿ｌｅａｓｔ＿ｒｅｃｅｎｔｌｙ＿ｕｓｅ
ｄルーチンのフローチャートである。
【図９】 本発明の一態様によるｒｅｃｌａｉｍ＿ｃａ
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
【図１０】 本発明の一態様によるｉｎｓｅｒｔ＿ｃａ
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
【図１１】 本発明の一態様によるｄｅｌｅｔｅ＿ｃａ
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
ｃｈｅ＿ｅｎｔｒｙルーチンのフローチャートである。
１０１ プロセッサ １０３ 共通二重ポート・メモリ（ＤＰＭ） １０５ 中央演算処理装置（ＣＰＵ） １０７ ディスク １０９ 入出力（Ｉ／Ｏ）制御装置 １１１ 入力装置 １１３ 出力装置 １１５ ランダム・アクセス・メモリ（ＲＡＭ） １１７ 読取り専用メモリ（ＲＯＭ） １１９ 共通システム・バス １２１ 出力装置 １２３ 入力装置 １２５ キャッシュ制御プログラム １２７ キャッシュ １２９ ハードウェア・キャッシュ ２０１ エントリ・テーブル ２０３ キー ２０５ データ値 ２０７ エントリ・ロック ２０９ 最後のアクセス時間 ２１１ リファレンス・カウント ２１３ キャッシュ・クロック ２１５ キャッシュ・ロック ２１７ テーブル ２１９ 入力キー ２２１ エントリ番号 ２２３ 入力 ３０１ キャッシュ・エントリ・テーブル ３０３ ロックレス参照ハッシュ・テーブル
フロントページの続き (72)発明者 セロン・ディ・トック アメリカ合衆国 94086 カリフォルニア 州・サニーベール・アヤラ ドライブ・ナ ンバー 100・1260
Claims (11)
- 【請求項１】 キャッシュが、項目を記憶する複数のエ
ントリを有し、各エントリが、エントリ番号によって識
別され、項目が第１のキーを含みときに、各スレッドか
ら共通にアクセスできるキャッシュを有するマルチスレ
ッド処理システムでキャッシュ中の項目を見つける方法
であって、 ａ）ロックレス参照エンジンに第１のキーを供給するス
テップと、 ｂ）ロックレス参照エンジンを使用して、参照出力、す
なわち参照エントリ番号を与えるステップと、 ｃ）項目が、参照エントリ番号に関連付けられたエント
リに記憶されているかどうかを判定するステップとを含
み、その判定ステップが、 少なくとも、参照エントリ番号で指定されたエントリ
に、専用アクセスを許可する相互排他ロックを得るステ
ップと、 参照エントリ番号を使用して、参照エントリ番号で指定
されたエントリから記憶されているキーを読み取るステ
ップと、 第１のキーを記憶されているキーと比較するステップと
を含み、第１のキーが、記憶されているキーに合致する
場合、項目が参照エントリ番号に関連付けられたエント
リに記憶されることを特徴とする方法。 - 【請求項２】 キャッシュが、項目を記憶する複数のエ
ントリを有し、各エントリが、エントリ番号によって識
別され、項目が第１のキーを含みときに、各スレッドか
ら共通にアクセスできるキャッシュを有するマルチスレ
ッド処理システムでキャッシュ中の項目を見つける方法
であって、 ａ）ロックレス参照エンジンに第１のキーを供給するス
テップと、 ｂ）参照エントリ番号が第１のエントリ番号と第２のエ
ントリ番号のどちらかであり、第１のエントリ番号は項
目が記憶されている第１のエントリを指し示し、第２の
エントリ番号は項目が記憶されていない第２のエントリ
を指すようになっているときに、ロックレス参照エンジ
ンを使用して、参照出力、すなわち参照エントリ番号を
与えるステップと、 ｃ）参照エントリ番号が第１のエントリ番号であること
を検証するステップとを含み、その検証ステップが、 少なくとも、参照エントリ番号で指定されたエントリ
に、専用アクセスを許可する相互排他ロックを得るステ
ップと、 参照エントリ番号を使用して、参照エントリ番号で指定
されたエントリから記憶されているキーを読み取るステ
ップと、 第１のキーを記憶されているキーと比較するステップ
と、 第１のキーが記憶されているキーに合致する場合にの
み、参照エントリ番号を第１のエントリ番号として供給
するステップとを含むことを特徴とする方法。 - 【請求項３】 さらに、 第１のキーが、記憶されているキーに合致しない場合
に、相互排他ロックを解除し、ステップａ）ないしｃ）
を繰り返すステップを含むことを特徴とする請求項２に
記載の方法。 - 【請求項４】 キャッシュが、項目を記憶する複数のエ
ントリを有し、各エントリが、エントリ番号によって識
別され、項目が第１のキーを含みときに、各スレッドか
ら共通にアクセスできるキャッシュを有するマルチスレ
ッド処理システムでキャッシュ中の項目を見つける装置
であって、 ａ）ロックレス参照エンジンに第１のキーを供給する手
段と、 ｂ）参照エントリ番号が、第１のエントリ番号と第２の
エントリ番号のどちらかであり、第１のエントリ番号
が、項目が記憶されている第１のエントリを指し示し、
第２のエントリ番号が、項目が記憶されていない第２の
エントリを指すようになっているときに、ロックレス参
照エンジンを使用して、参照出力、すなわち参照エント
リ番号を与える手段と、 ｃ）参照エントリ番号が第１のエントリ番号であること
を検証する手段とを含み、その検証手段が、 少なくとも、参照エントリ番号で指定されたエントリ
に、専用アクセスを許可する相互排他ロックを得る手段
と、 参照エントリ番号を使用して、参照エントリ番号で指定
されたエントリから記憶されているキーを読み取る手段
と、 第１のキーを記憶されているキーと比較する手段と、 第１のキーが記憶されているキーに合致する場合にの
み、参照エントリ番号を第１のエントリ番号として供給
する手段とを含むことを特徴とする装置。 - 【請求項５】 さらに、 第１のキーが、記憶されているキーに合致しないことに
応答して、相互排他ロックを解除し、手段ａ）ないし
ｃ）を再び作動させる手段を備えることを特徴とする請
求項４に記載の装置。 - 【請求項６】 キャッシュが、項目を記憶する複数のエ
ントリを有し、各エントリが、エントリ番号によって識
別され、項目が第１のキーを含むときに、各スレッドか
ら共通にアクセスできるキャッシュを有するマルチスレ
ッド処理システムで使用すべき製品であって、 キャッシュ中の項目を見つけさせるように構成されたコ
ンピュータ読取り可能プログラム・コードを有するコン
ピュータ使用可能媒体を備え、製品中の前記コンピュー
タ読取り可能プログラム・コードが、 マルチスレッド処理システム中のコンピュータに、ロッ
クレス参照エンジンに第１のキーを供給させるように構
成されたコンピュータ読取り可能なプログラム・コード
と、 コンピュータに、ロックレス参照エンジンを使用して、
参照出力、すなわち参照エントリ番号を提供させるよう
に構成されたコンピュータ読取り可能プログラム・コー
ドと、 コンピュータに、項目が、参照エントリ番号に関連付け
られたエントリに記憶されているかどうかを判定させる
ように構成されたコンピュータ読取り可能プログラム・
コードとを備え、コンピュータに判定を下させるように
構成されたコンピュータ読取り可能プログラム・コード
が、 コンピュータに、少なくとも、参照エントリ番号で指定
されたエントリに、専用アクセスを許可する相互排他ロ
ックを得させるように構成されたコンピュータ読取り可
能プログラム・コードと、 コンピュータに、参照エントリ番号を使用して、参照エ
ントリ番号で指定されたエントリから記憶されているキ
ーを読み取らせるように構成されたコンピュータ読取り
可能コードと、 コンピュータに、第１のキーを、記憶されているキーと
比較させるように構成されたコンピュータ読取り可能プ
ログラム・コードとを備え、第１のキーが、記憶されて
いるキーに合致する場合、項目が、参照エントリ番号に
関連付けられたエントリに記憶されることを特徴とする
製品。 - 【請求項７】 キャッシュが、項目を記憶する複数のエ
ントリを有し、各エントリが、エントリ番号によって識
別され、項目が第１のキーを含むときに、各スレッドか
ら共通にアクセスできるキャッシュを有するマルチスレ
ッド処理システムで使用すべき製品であって、 キャッシュ中の項目を見つけさせるように構成されたコ
ンピュータ読取り可能プログラム・コードを有するコン
ピュータ使用可能媒体を備え、製品中の前記コンピュー
タ読取り可能プログラム・コードが、 ａ）マルチスレッド処理システム中のコンピュータに、
ロックレス参照エンジンに第１のキーを供給させるよう
に構成されたコンピュータ読取り可能なプログラム・コ
ードと、 ｂ）コンピュータに、ロックレス参照エンジンを使用し
て、参照出力、すなわち参照エントリ番号を提供させる
ように構成され、参照エントリ番号が、第１のエントリ
番号と第２のエントリ番号のどちらかであり、第１のエ
ントリ番号が、項目が記憶されている第１のエントリを
指し示し、第２のエントリ番号が、項目が記憶されてい
ない第２のエントリを指す、コンピュータ読取り可能プ
ログラム・コードと、 ｃ）コンピュータに、参照エントリ番号が第１のエント
リ番号であることを検証させるように構成されたコンピ
ュータ読取り可能プログラム・コードとを備え、コンピ
ュータに検証を行わせるように構成されたコンピュータ
読取り可能プログラム・コードが、 コンピュータに、少なくとも、参照エントリ番号で指定
されたエントリに、専用アクセスを許可する相互排他ロ
ックを得させるように構成されたコンピュータ読取り可
能プログラム・コードと、 コンピュータに、参照エントリ番号を使用して、参照エ
ントリ番号で指定されたエントリから記憶されているキ
ーを読み取らせるように構成されたコンピュータ読取り
可能プログラム・コードと、 コンピュータに、第１のキーを、記憶されているキーと
比較させるように構成されたコンピュータ読取り可能プ
ログラム・コードと、 コンピュータに、第１のキーが、記憶されているキーに
合致する場合にのみ、参照エントリ番号を第１のエント
リ番号として供給させるように構成されたコンピュータ
読取り可能プログラム・コードとを備えることを特徴と
する製品。 - 【請求項８】 さらに、 コンピュータに、第１のキーが、記憶されているキーに
合致しないことに応答して、相互排他ロックを解除し、
コンピュータ読取り可能プログラム・コードａ）ないし
ｃ）を再び呼び出させるように構成されたコンピュータ
読取り可能プログラム・コードを備えることを特徴とす
る請求項７に記載の製品。 - 【請求項９】 各スレッドから共通にアクセスすること
ができ、項目を記憶する複数のエントリを有するキャッ
シュを有するマルチスレッド処理システムでの新しい項
目を記憶する新しいキャッシュ・エントリを得る方法で
あって、 ａ）複数のエントリを論理的に数組のエントリに分割す
るステップと、 ｂ）数組のエントリのうちの１組を選択するステップ
と、 ｃ）選択された１組のエントリに関して、どのエントリ
がビジーでないかを判定するステップと、 ｄ）選択された１組のエントリのうちの少なくとも１つ
のエントリがビジーでない場合に、１組のエントリのう
ちの非ビジー・エントリのうちで最初に使用されたエン
トリを新しいキャッシュ・エントリとして選択するステ
ップと、 ｅ）選択された１組のエントリのどのエントリもビジー
でない場合に、数組のエントリのうちの他の１組を選択
しステップｃ）ないしｅ）を繰り返すステップとを含む
ことを特徴とする方法。 - 【請求項１０】 各スレッドから共通にアクセスするこ
とができ、項目を記憶する複数のエントリを有するキャ
ッシュを有するマルチスレッド処理システムでの新しい
項目を記憶する新しいキャッシュ・エントリを得る装置
であって、 ａ）複数のエントリを論理的に数組のエントリに分割す
る手段と、 ｂ）数組のエントリのうちの１組を選択する手段と、 ｃ）選択された１組のエントリに関して、どのエントリ
がビジーでないかを判定する手段と、 ｄ）選択された１組のエントリのうちの少なくとも１つ
のエントリがビジーでないことに応答して、１組のエン
トリのうちの非ビジー・エントリのうちで最初に使用さ
れたエントリを新しいキャッシュ・エントリとして選択
する手段と、 ｅ）選択された１組のエントリのどのエントリもビジー
でないことに応答して、数組のエントリのうちの他の１
組を選択し、手段ｃ）ないしｅ）を再び起動する手段と
を備えることを特徴とする装置。 - 【請求項１１】 各スレッドから共通にアクセスするこ
とができ、項目を記憶する複数のエントリを有するキャ
ッシュを備えたマルチスレッド処理システムで使用すべ
き製品であって、 新しい項目を記憶する新しいキャッシュ・エントリを得
させるように構成されたコンピュータ読取り可能プログ
ラム・コードを有するコンピュータ使用可能媒体を有
し、製品中のコンピュータ読取り可能プログラム・コー
ドが、 ａ）マルチスレッド処理システム中のコンピュータに、
複数のエントリを論理的に数組のエントリに分割させる
ように構成されたコンピュータ読取り可能プログラム・
コードと、 ｂ）コンピュータに、数組のエントリのうちの１組を選
択させるように構成されたコンピュータ読取り可能プロ
グラム・コードと、 ｃ）コンピュータに、選択された１組のエントリに関し
て、どのエントリがビジーでないかを判定させるように
構成されたコンピュータ読取り可能プログラム・コード
と、 ｄ）コンピュータに、選択された１組のエントリのうち
の少なくとも１つのエントリがビジーでないことに応答
して、１組のエントリのうちの非ビジー・エントリのう
ちで最初に使用されたエントリを新しいキャッシュ・エ
ントリとして選択させるように構成されたコンピュータ
読取り可能プログラム・コードと、 ｅ）コンピュータに、選択された１組のエントリのどの
エントリもビジーでないことに応答して、数組のエント
リのうちの他の１組を選択し、コンピュータ読取り可能
プログラム・コードｃ）ないしｅ）を再び起動させるよ
うに構成されたコンピュータ読取り可能プログラム・コ
ードとを備えることを特徴とする製品。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/543105 | 1995-10-13 | ||
| US08/543,105 US5701432A (en) | 1995-10-13 | 1995-10-13 | Multi-threaded processing system having a cache that is commonly accessible to each thread |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH09204357A true JPH09204357A (ja) | 1997-08-05 |
Family
ID=24166597
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP8289018A Pending JPH09204357A (ja) | 1995-10-13 | 1996-10-14 | マルチスレッド環境を有する計算システム用の最大並行参照キャッシュ |
Country Status (7)
| Country | Link |
|---|---|
| US (2) | US5701432A (ja) |
| EP (1) | EP0768608B1 (ja) |
| JP (1) | JPH09204357A (ja) |
| KR (1) | KR970022764A (ja) |
| CN (1) | CN1087451C (ja) |
| DE (1) | DE69625768T2 (ja) |
| TW (1) | TW324081B (ja) |
Families Citing this family (121)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5819298A (en) * | 1996-06-24 | 1998-10-06 | Sun Microsystems, Inc. | File allocation tables with holes |
| US5832525A (en) * | 1996-06-24 | 1998-11-03 | Sun Microsystems, Inc. | Disk fragmentation reduction using file allocation tables |
| US5937187A (en) * | 1996-07-01 | 1999-08-10 | Sun Microsystems, Inc. | Method and apparatus for execution and preemption control of computer process entities |
| US5974438A (en) * | 1996-12-31 | 1999-10-26 | Compaq Computer Corporation | Scoreboard for cached multi-thread processes |
| US6014667A (en) * | 1997-10-01 | 2000-01-11 | Novell, Inc. | System and method for caching identification and location information in a computer network |
| US6216218B1 (en) | 1997-11-03 | 2001-04-10 | Donald L. Sollars | Processor having a datapath and control logic constituted with basis execution blocks |
| US6067601A (en) * | 1997-11-03 | 2000-05-23 | Brecis Communications | Cache memory based instruction execution |
| US6161166A (en) * | 1997-11-10 | 2000-12-12 | International Business Machines Corporation | Instruction cache for multithreaded processor |
| US5995998A (en) * | 1998-01-23 | 1999-11-30 | Sun Microsystems, Inc. | Method, apparatus and computer program product for locking interrelated data structures in a multi-threaded computing environment |
| US6289358B1 (en) | 1998-04-15 | 2001-09-11 | Inktomi Corporation | Delivering alternate versions of objects from an object cache |
| US6128623A (en) * | 1998-04-15 | 2000-10-03 | Inktomi Corporation | High performance object cache |
| US6205519B1 (en) | 1998-05-27 | 2001-03-20 | Hewlett Packard Company | Cache management for a multi-threaded processor |
| US6490654B2 (en) * | 1998-07-31 | 2002-12-03 | Hewlett-Packard Company | Method and apparatus for replacing cache lines in a cache memory |
| US6594701B1 (en) | 1998-08-04 | 2003-07-15 | Microsoft Corporation | Credit-based methods and systems for controlling data flow between a sender and a receiver with reduced copying of data |
| US6321276B1 (en) | 1998-08-04 | 2001-11-20 | Microsoft Corporation | Recoverable methods and systems for processing input/output requests including virtual memory addresses |
| US6360220B1 (en) * | 1998-08-04 | 2002-03-19 | Microsoft Corporation | Lock-free methods and systems for accessing and storing information in an indexed computer data structure having modifiable entries |
| US6269425B1 (en) * | 1998-08-20 | 2001-07-31 | International Business Machines Corporation | Accessing data from a multiple entry fully associative cache buffer in a multithread data processing system |
| US6189007B1 (en) | 1998-08-28 | 2001-02-13 | International Business Machines Corporation | Method and apparatus for conducting a high performance locking facility in a loosely coupled environment |
| US6253274B1 (en) * | 1998-08-28 | 2001-06-26 | International Business Machines Corporation | Apparatus for a high performance locking facility |
| US6185650B1 (en) | 1998-08-28 | 2001-02-06 | International Business Machines Corporation | High performance locking facility |
| US6349363B2 (en) * | 1998-12-08 | 2002-02-19 | Intel Corporation | Multi-section cache with different attributes for each section |
| US7529907B2 (en) | 1998-12-16 | 2009-05-05 | Mips Technologies, Inc. | Method and apparatus for improved computer load and store operations |
| US7020879B1 (en) * | 1998-12-16 | 2006-03-28 | Mips Technologies, Inc. | Interrupt and exception handling for multi-streaming digital processors |
| US7237093B1 (en) | 1998-12-16 | 2007-06-26 | Mips Technologies, Inc. | Instruction fetching system in a multithreaded processor utilizing cache miss predictions to fetch instructions from multiple hardware streams |
| US7257814B1 (en) * | 1998-12-16 | 2007-08-14 | Mips Technologies, Inc. | Method and apparatus for implementing atomicity of memory operations in dynamic multi-streaming processors |
| US6389449B1 (en) * | 1998-12-16 | 2002-05-14 | Clearwater Networks, Inc. | Interstream control and communications for multi-streaming digital processors |
| US7035997B1 (en) | 1998-12-16 | 2006-04-25 | Mips Technologies, Inc. | Methods and apparatus for improving fetching and dispatch of instructions in multithreaded processors |
| US6460122B1 (en) * | 1999-03-31 | 2002-10-01 | International Business Machine Corporation | System, apparatus and method for multi-level cache in a multi-processor/multi-controller environment |
| US6535905B1 (en) | 1999-04-29 | 2003-03-18 | Intel Corporation | Method and apparatus for thread switching within a multithreaded processor |
| US6507862B1 (en) * | 1999-05-11 | 2003-01-14 | Sun Microsystems, Inc. | Switching method in a multi-threaded processor |
| US6938147B1 (en) * | 1999-05-11 | 2005-08-30 | Sun Microsystems, Inc. | Processor with multiple-thread, vertically-threaded pipeline |
| US6542921B1 (en) | 1999-07-08 | 2003-04-01 | Intel Corporation | Method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor |
| AU7728300A (en) * | 1999-11-22 | 2001-06-04 | Ericsson Inc. | Buffer memories, methods and systems for buffering having seperate buffer memories for each of a plurality of tasks |
| US6889319B1 (en) | 1999-12-09 | 2005-05-03 | Intel Corporation | Method and apparatus for entering and exiting multiple threads within a multithreaded processor |
| US6496925B1 (en) | 1999-12-09 | 2002-12-17 | Intel Corporation | Method and apparatus for processing an event occurrence within a multithreaded processor |
| US7188344B1 (en) | 1999-12-21 | 2007-03-06 | Unisys Corporation | Architecture for a read/write thread lock |
| US7590644B2 (en) * | 1999-12-21 | 2009-09-15 | International Business Machine Corporation | Method and apparatus of streaming data transformation using code generator and translator |
| US7051329B1 (en) | 1999-12-28 | 2006-05-23 | Intel Corporation | Method and apparatus for managing resources in a multithreaded processor |
| US7856633B1 (en) * | 2000-03-24 | 2010-12-21 | Intel Corporation | LRU cache replacement for a partitioned set associative cache |
| US6622168B1 (en) * | 2000-04-10 | 2003-09-16 | Chutney Technologies, Inc. | Dynamic page generation acceleration using component-level caching |
| US7111156B1 (en) * | 2000-04-21 | 2006-09-19 | Ati Technologies, Inc. | Method and apparatus for multi-thread accumulation buffering in a computation engine |
| DE60143896D1 (de) | 2000-07-14 | 2011-03-03 | Mips Tech Inc | Anweisungsabruf und -absendung in einem multi-thread-system |
| US7185196B1 (en) * | 2000-09-15 | 2007-02-27 | Atheros Communications, Inc. | Key caching system |
| US6785714B1 (en) * | 2000-09-28 | 2004-08-31 | Microsoft Corporation | System and method for employing slot level locking of a cache |
| SE0004736D0 (sv) * | 2000-12-20 | 2000-12-20 | Ericsson Telefon Ab L M | Mapping system and method |
| JP3990115B2 (ja) * | 2001-03-12 | 2007-10-10 | 株式会社東芝 | サーバ側プロキシ装置及びプログラム |
| US6732238B1 (en) * | 2001-06-08 | 2004-05-04 | Tensilica, Inc. | Set-associative cache memory having variable time decay rewriting algorithm |
| US6976155B2 (en) * | 2001-06-12 | 2005-12-13 | Intel Corporation | Method and apparatus for communicating between processing entities in a multi-processor |
| GB0116497D0 (en) * | 2001-07-06 | 2001-08-29 | Koninkl Philips Electronics Nv | Receiver apparatus and method |
| US6944717B2 (en) * | 2001-07-27 | 2005-09-13 | Fujitsu Limited | Cache buffer control apparatus and method using counters to determine status of cache buffer memory cells for writing and reading data therefrom |
| US8024735B2 (en) | 2002-06-14 | 2011-09-20 | Intel Corporation | Method and apparatus for ensuring fairness and forward progress when executing multiple threads of execution |
| JP3900025B2 (ja) * | 2002-06-24 | 2007-04-04 | 日本電気株式会社 | 共有キャッシュメモリのヒット判定制御方法及び共有キャッシュメモリのヒット判定制御方式 |
| US6915296B2 (en) * | 2002-10-29 | 2005-07-05 | Agere Systems Inc. | Incremental reorganization for hash tables |
| US7831974B2 (en) * | 2002-11-12 | 2010-11-09 | Intel Corporation | Method and apparatus for serialized mutual exclusion |
| US7415540B2 (en) * | 2002-12-31 | 2008-08-19 | Intel Corporation | Scheduling processing threads |
| US7418577B2 (en) | 2003-02-13 | 2008-08-26 | Sun Microsystems, Inc. | Fail instruction to support transactional program execution |
| US7089374B2 (en) * | 2003-02-13 | 2006-08-08 | Sun Microsystems, Inc. | Selectively unmarking load-marked cache lines during transactional program execution |
| US7269693B2 (en) | 2003-02-13 | 2007-09-11 | Sun Microsystems, Inc. | Selectively monitoring stores to support transactional program execution |
| US7269694B2 (en) | 2003-02-13 | 2007-09-11 | Sun Microsystems, Inc. | Selectively monitoring loads to support transactional program execution |
| US7269717B2 (en) | 2003-02-13 | 2007-09-11 | Sun Microsystems, Inc. | Method for reducing lock manipulation overhead during access to critical code sections |
| US7398355B1 (en) | 2003-02-13 | 2008-07-08 | Sun Microsystems, Inc. | Avoiding locks by transactionally executing critical sections |
| US6938130B2 (en) * | 2003-02-13 | 2005-08-30 | Sun Microsystems Inc. | Method and apparatus for delaying interfering accesses from other threads during transactional program execution |
| US7152170B2 (en) | 2003-02-20 | 2006-12-19 | Samsung Electronics Co., Ltd. | Simultaneous multi-threading processor circuits and computer program products configured to operate at different performance levels based on a number of operating threads and methods of operating |
| GB2410584B (en) * | 2003-02-20 | 2006-02-01 | Samsung Electronics Co Ltd | Simultaneous multi-threading processor circuits and computer program products configured to operate at different performance levels |
| US20040190506A1 (en) * | 2003-03-24 | 2004-09-30 | International Business Machines Corp. | Method and apparatus for performing complex pattern matching in a data stream within a computer network |
| US20040199727A1 (en) * | 2003-04-02 | 2004-10-07 | Narad Charles E. | Cache allocation |
| US7225299B1 (en) | 2003-07-16 | 2007-05-29 | Transmeta Corporation | Supporting speculative modification in a data cache |
| US20050120195A1 (en) * | 2003-11-13 | 2005-06-02 | Alok Kumar | Allocating memory |
| US7536377B1 (en) | 2003-12-18 | 2009-05-19 | Xilinx, Inc. | Component naming |
| US7703098B1 (en) | 2004-07-20 | 2010-04-20 | Sun Microsystems, Inc. | Technique to allow a first transaction to wait on condition that affects its working set |
| US8074030B1 (en) | 2004-07-20 | 2011-12-06 | Oracle America, Inc. | Using transactional memory with early release to implement non-blocking dynamic-sized data structure |
| US7809888B1 (en) * | 2004-09-29 | 2010-10-05 | Emc Corporation | Content-aware caching techniques |
| US7376798B1 (en) * | 2005-04-07 | 2008-05-20 | Transmeta Corporation | Memory management methods and systems that support cache consistency |
| KR100850712B1 (ko) * | 2005-06-20 | 2008-08-06 | 삼성전자주식회사 | 화상 형성 장치의 전사 전압 제어 방법 및 장치 |
| US7966292B1 (en) | 2005-06-30 | 2011-06-21 | Emc Corporation | Index processing |
| US8161005B1 (en) | 2005-06-30 | 2012-04-17 | Emc Corporation | Efficient index processing |
| US8156079B1 (en) | 2005-06-30 | 2012-04-10 | Emc Corporation | System and method for index processing |
| US20070022250A1 (en) * | 2005-07-19 | 2007-01-25 | International Business Machines Corporation | System and method of responding to a cache read error with a temporary cache directory column delete |
| WO2007031696A1 (en) * | 2005-09-13 | 2007-03-22 | Arm Limited | Cache miss detection in a data processing apparatus |
| EP1938207A1 (en) * | 2005-09-27 | 2008-07-02 | Teamon Systems, Inc. | System for transforming application data using xslt extensions to render templates from cache and related methods |
| CA2621348C (en) * | 2005-09-27 | 2010-07-06 | Teamon Systems, Inc. | System for obtaining image using xslt extension and related method |
| US7752211B1 (en) | 2005-09-30 | 2010-07-06 | Emc Corporation | Adaptive index processing |
| US7698325B1 (en) * | 2005-09-30 | 2010-04-13 | Emc Corporation | Index processing for legacy systems |
| US7627609B1 (en) | 2005-09-30 | 2009-12-01 | Emc Corporation | Index processing using transformed values |
| US7886068B1 (en) * | 2005-10-27 | 2011-02-08 | Network Appliance, Inc. | Management of streaming media playlists |
| US8185724B2 (en) * | 2006-03-03 | 2012-05-22 | Arm Limited | Monitoring values of signals within an integrated circuit |
| WO2007101969A1 (en) * | 2006-03-06 | 2007-09-13 | Arm Limited | Accessing a cache in a data processing apparatus |
| US7930695B2 (en) * | 2006-04-06 | 2011-04-19 | Oracle America, Inc. | Method and apparatus for synchronizing threads on a processor that supports transactional memory |
| US7685368B1 (en) * | 2006-06-28 | 2010-03-23 | Emc Corporation | Methods and apparatus for removing data from a cache |
| US7668851B2 (en) * | 2006-11-29 | 2010-02-23 | International Business Machines Corporation | Lockless hash table lookups while performing key update on hash table element |
| US20080183963A1 (en) * | 2007-01-31 | 2008-07-31 | International Business Machines Corporation | System, Method, And Service For Providing A Generic RAID Engine And Optimizer |
| US8095750B2 (en) * | 2007-05-14 | 2012-01-10 | International Business Machines Corporation | Transactional memory system with fast processing of common conflicts |
| US8688920B2 (en) | 2007-05-14 | 2014-04-01 | International Business Machines Corporation | Computing system with guest code support of transactional memory |
| US8095741B2 (en) * | 2007-05-14 | 2012-01-10 | International Business Machines Corporation | Transactional memory computing system with support for chained transactions |
| US9009452B2 (en) | 2007-05-14 | 2015-04-14 | International Business Machines Corporation | Computing system with transactional memory using millicode assists |
| US8117403B2 (en) * | 2007-05-14 | 2012-02-14 | International Business Machines Corporation | Transactional memory system which employs thread assists using address history tables |
| US8321637B2 (en) * | 2007-05-14 | 2012-11-27 | International Business Machines Corporation | Computing system with optimized support for transactional memory |
| US8200917B2 (en) * | 2007-09-26 | 2012-06-12 | Qualcomm Incorporated | Multi-media processor cache with cache line locking and unlocking |
| US8032706B2 (en) * | 2008-08-05 | 2011-10-04 | Intel Corporation | Method and apparatus for detecting a data access violation |
| US9727508B2 (en) | 2009-04-27 | 2017-08-08 | Intel Corporation | Address learning and aging for network bridging in a network processor |
| US8321385B2 (en) * | 2010-03-12 | 2012-11-27 | Lsi Corporation | Hash processing in a network communications processor architecture |
| US8515965B2 (en) | 2010-05-18 | 2013-08-20 | Lsi Corporation | Concurrent linked-list traversal for real-time hash processing in multi-core, multi-thread network processors |
| US9152564B2 (en) | 2010-05-18 | 2015-10-06 | Intel Corporation | Early cache eviction in a multi-flow network processor architecture |
| US8949838B2 (en) | 2009-04-27 | 2015-02-03 | Lsi Corporation | Multi-threaded processing with hardware accelerators |
| US9461930B2 (en) | 2009-04-27 | 2016-10-04 | Intel Corporation | Modifying data streams without reordering in a multi-thread, multi-flow network processor |
| US8910168B2 (en) | 2009-04-27 | 2014-12-09 | Lsi Corporation | Task backpressure and deletion in a multi-flow network processor architecture |
| US8873550B2 (en) | 2010-05-18 | 2014-10-28 | Lsi Corporation | Task queuing in a multi-flow network processor architecture |
| US8949578B2 (en) | 2009-04-27 | 2015-02-03 | Lsi Corporation | Sharing of internal pipeline resources of a network processor with external devices |
| US8949582B2 (en) | 2009-04-27 | 2015-02-03 | Lsi Corporation | Changing a flow identifier of a packet in a multi-thread, multi-flow network processor |
| US8874878B2 (en) | 2010-05-18 | 2014-10-28 | Lsi Corporation | Thread synchronization in a multi-thread, multi-flow network communications processor architecture |
| US8566524B2 (en) | 2009-08-31 | 2013-10-22 | International Business Machines Corporation | Transactional memory system with efficient cache support |
| US9075720B2 (en) | 2010-10-04 | 2015-07-07 | International Business Machines Corporation | Locking a cache line for write operations on a bus |
| US9104678B1 (en) | 2011-12-31 | 2015-08-11 | Richard Michael Nemes | Methods and apparatus for information storage and retrieval using a caching technique with probe-limited open-address hashing |
| US9268596B2 (en) | 2012-02-02 | 2016-02-23 | Intel Corparation | Instruction and logic to test transactional execution status |
| US8938428B1 (en) | 2012-04-16 | 2015-01-20 | Emc Corporation | Systems and methods for efficiently locating object names in a large index of records containing object names |
| WO2014014452A1 (en) * | 2012-07-18 | 2014-01-23 | Empire Technology Development Llc | Virtual cache directory in multi-processor architectures |
| US9081672B1 (en) | 2013-05-30 | 2015-07-14 | Richard Michael Nemes | Methods and apparatus for information storage and retrieval using a caching technique with external-chain hashing and dynamic resource-dependent data shedding |
| US9830275B2 (en) | 2015-05-18 | 2017-11-28 | Imagination Technologies Limited | Translation lookaside buffer |
| US11593167B2 (en) * | 2019-05-09 | 2023-02-28 | International Business Machines Corporation | Thread embedded cache management |
| US11030109B2 (en) * | 2019-06-06 | 2021-06-08 | Samsung Electronics Co., Ltd. | Mechanisms for a contention free lookup in a cache with concurrent insertions and deletions |
| US11151050B2 (en) * | 2020-01-03 | 2021-10-19 | Samsung Electronics Co., Ltd. | Efficient cache eviction and insertions for sustained steady state performance |
Family Cites Families (12)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US4513367A (en) * | 1981-03-23 | 1985-04-23 | International Business Machines Corporation | Cache locking controls in a multiprocessor |
| US4736293A (en) * | 1984-04-11 | 1988-04-05 | American Telephone And Telegraph Company, At&T Bell Laboratories | Interleaved set-associative memory |
| US4926323A (en) * | 1988-03-03 | 1990-05-15 | Advanced Micro Devices, Inc. | Streamlined instruction processor |
| NL8901626A (nl) * | 1989-06-27 | 1991-01-16 | Thomassen & Drijver | Inrichting voor het uitstoten van verkeerd geoerienteerde deksels uit een continue stroom. |
| US5491806A (en) * | 1990-06-26 | 1996-02-13 | Lsi Logic Corporation | Optimized translation lookaside buffer slice having stored mask bits |
| US5325504A (en) * | 1991-08-30 | 1994-06-28 | Compaq Computer Corporation | Method and apparatus for incorporating cache line replacement and cache write policy information into tag directories in a cache system |
| US5353425A (en) * | 1992-04-29 | 1994-10-04 | Sun Microsystems, Inc. | Methods and apparatus for implementing a pseudo-LRU cache memory replacement scheme with a locking feature |
| WO1994003856A1 (en) * | 1992-08-07 | 1994-02-17 | Massachusetts Institute Of Technology | Column-associative cache |
| GB2276961B (en) * | 1993-03-30 | 1997-03-26 | Int Computers Ltd | Set-associative memory |
| US5535365A (en) * | 1993-10-22 | 1996-07-09 | Cray Research, Inc. | Method and apparatus for locking shared memory locations in multiprocessing systems |
| US5727212A (en) * | 1995-04-12 | 1998-03-10 | International Business Machines Corporation | Object oriented device driver system for procedural device drivers |
| US6281893B1 (en) * | 1996-04-04 | 2001-08-28 | Sun Microsystems, Inc. | Method and apparatus for providing an object oriented approach to a device independent graphics control system |
-
1995
- 1995-10-13 US US08/543,105 patent/US5701432A/en not_active Expired - Lifetime
-
1996
- 1996-10-10 DE DE69625768T patent/DE69625768T2/de not_active Expired - Fee Related
- 1996-10-10 EP EP96307364A patent/EP0768608B1/en not_active Expired - Lifetime
- 1996-10-12 CN CN96121911A patent/CN1087451C/zh not_active Expired - Fee Related
- 1996-10-12 KR KR1019960045540A patent/KR970022764A/ko not_active Withdrawn
- 1996-10-14 JP JP8289018A patent/JPH09204357A/ja active Pending
- 1996-11-06 TW TW085113583A patent/TW324081B/zh active
- 1996-12-23 US US08/773,258 patent/US5909695A/en not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0768608A2 (en) | 1997-04-16 |
| DE69625768D1 (de) | 2003-02-20 |
| EP0768608B1 (en) | 2003-01-15 |
| TW324081B (en) | 1998-01-01 |
| EP0768608A3 (en) | 1998-08-12 |
| CN1087451C (zh) | 2002-07-10 |
| CN1155121A (zh) | 1997-07-23 |
| US5909695A (en) | 1999-06-01 |
| DE69625768T2 (de) | 2003-09-18 |
| US5701432A (en) | 1997-12-23 |
| KR970022764A (ko) | 1997-05-30 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH09204357A (ja) | マルチスレッド環境を有する計算システム用の最大並行参照キャッシュ | |
| US5265245A (en) | High concurrency in use manager | |
| US6115802A (en) | Efficient hash table for use in multi-threaded environments | |
| CN109407979B (zh) | 多线程持久性b+树数据结构设计与实现方法 | |
| US5414840A (en) | Method and system for decreasing recovery time for failed atomic transactions by keeping copies of altered control structures in main memory | |
| JP4176857B2 (ja) | リファレンスされたオブジェクトを管理するための３状態リファレンスの使用 | |
| US7587566B2 (en) | Realtime memory management via locking realtime threads and related data structures | |
| US5410697A (en) | Concurrency management using version identification of shared data as a supplement to use of locks | |
| US6898650B1 (en) | Queueing method supporting multiple client accesses simultaneously | |
| US6625591B1 (en) | Very efficient in-memory representation of large file system directories | |
| US6804766B1 (en) | Method for managing pages of a designated memory object according to selected memory management policies | |
| US8250047B2 (en) | Hybrid multi-threaded access to data structures using hazard pointers for reads and locks for updates | |
| US5134696A (en) | Virtual lookaside facility | |
| US7065763B1 (en) | Method of reducing contention of a highly contended lock protecting multiple data items | |
| JP2008262585A (ja) | データベース・オブジェクト処理命令を挿入するためにデータベース・アクセス方法を自動的に変更するシステム及び方法 | |
| SG175109A1 (en) | Performing concurrent rehashing of a hash table for multithreaded applications | |
| US7493464B2 (en) | Sparse matrix | |
| US5247647A (en) | Detection of deletion of stored data by concurrently executing processes in a multiprocessing data processing system | |
| US7007146B2 (en) | System and method for relocating pages pinned in a buffer pool of a database system | |
| US20150134900A1 (en) | Cache efficiency in a shared disk database cluster | |
| Singh et al. | Efficient hardware primitives for immediate memory reclamation in optimistic data structures | |
| US10417209B1 (en) | Concurrent index using copy on write | |
| EP0394173A2 (en) | High concurrency manager of open files | |
| Klaftenegger et al. | On the scalability of the Erlang term storage | |
| Malek | An implementation and experimental comparison of dynamic ordered sets |