(57)【特許請求の範囲】
【請求項１】
マーク付けされていないデータのオブジェクトのゴミ集めの準備のために、連続したメモリ内における識別ポインタにより連結されたデータのオブジェクトから形成されるデータ構造を調べるマーク付け方法であって、該マーク付け方法が、
ａ）選択されたルートの１つのオブジェクトに関して、該１つのオブジェクトが持つポインタを調べて該１つのオブジェクトに連結された他のオブジェクトを検出するステップと、
ｂ）上記ステップにより新たに検出された他のオブジェクトに対する参照子を固定された大きさのスタック又は待ち行列である付加記憶手段に入力するステップと、
ｃ）ポインタを調べて、前記ステップｂ）により識別された他のオブジェクトに連結された更に他のオブジェクトを検出するステップと、
を有し、前記ステップｂ）及びｃ）は前記スタック又は待ち行列である付加記憶手段の容量が一杯になるまで繰り返され、次いで、これらステップにおいて識別されたオブジェクトがマーク付けされ、次いで、既にマーク付けされたオブジェクトに連結された別のオブジェクトを捜すために前記連続したメモリが走査されるようなマーク付け方法において、
前記連続したメモリが複数の別個のページに分割され、前記ステップｂ）及びｃ）が前記ルートの１つのオブジェクトと同一のページ内のオブジェクトに限定され、当該ページ外の何れの連結されたオブジェクトに関しても前記ステップｂ）において該ページに関する識別子が記憶されることを特徴とするマーク付け方法。
【請求項２】
請求項１に記載のマーク付け方法において、前記スタック又は待ち行列である付加記憶手段は、１つのページ内に含まれることができる最大数のオブジェクトがあった場合でも各参照子を収容する大きさがあることを特徴とするマーク付け方法。
【請求項３】
請求項１又は請求項２に記載のマーク付け方法において、前記ステップａ）、ｂ）及びｃ）は各ページに対して順番に実行され、前記ステップｂ）及びｃ）は、前記連続したメモリ内にマーク付けされていない連結されたオブジェクトが残存しなくなるまで繰り返されることを特徴とするマーク付け方法。
【請求項４】
請求項３に記載のマーク付け方法において、前記連続したメモリ内にマーク付けされていない連結されたオブジェクトが残存しなくなると、全ての残存するマーク付けされていないオブジェクトを削除することを特徴とするマーク付け方法。
【請求項５】
ランダムアクセスメモリに結合されたデータプロセッサを有するデータ処理装置であって、前記ランダムメモリは該ランダムメモリの連続した領域内に識別ポインタによりデータ構造内で連続された複数のデータオブジェクトを含み、該データ処理装置は固定した大きさのスタック又は待ち行列である第１付加記憶手段を更に有し、前記プロセッサは前記記憶された複数のデータオブジェクトに対して、
ａ）選択されたルートの１つのオブジェクトに関して、該１つのオブジェクトが持つポインタを調べて前記１つのオブジェクトに連結された他のオブジェクトを検出する演算と、
ｂ）上記演算により新たに検出された各他のオブジェクトに対する参照子を、前記スタック又は待ち行列である第１付加記憶手段に入力する演算と、
ｃ）ポインタを調べて、前記第１付加記憶手段において識別された他のオブジェクトに連結された更に他のオブジェクトを検出する演算と、
を実行するよう構成され、前記プロセッサは前記演算ｂ）及びｃ）を前記スタック又は待ち行列である第１付加記憶手段が一杯になるまで繰り返し、これら演算において識別されたオブジェクトにマーク付けをし、前記ランダムアクセスメモリの連続した領域を走査して既にマーク付けされたオブジェクトに連結された全ての別のオブジェクトを捜すようなデータ処理装置において、
前記連続したメモリが複数の別個のページに分割され、前記演算ｂ）及びｃ）が前記ルートの１つのオブジェクトと同一のページ内のオブジェクトに限定され、当該ページ外の何れの連結されたオブジェクトに関しても該ページに関する識別子が第２付加記憶手段に記憶され、既にマーク付けされたオブジェクトに連結された全ての別のオブジェクトを捜す前記走査が前記第２付加記憶手段内で識別されるページのみに関して実行されることを特徴とするデータ処理装置。
【請求項６】
請求項５に記載のデータ処理装置において、各ページに関して当該ページの捜し出されたマーク付けされるべき最初及び最後のオブジェクトの開始ロケーションを示す２つのポインタフィールドを含む第３付加記憶手段を有し、既にマーク付けされたオブジェクトに連結された全ての他のオブジェクトを捜す前記走査が前記第２付加記憶手段内で識別される各ページ内の上記の２つのポインタフィールドでカバーされた領域のみに関して実行されることを特徴とするデータ処理装置。
【請求項７】
請求項６に記載のデータ処理装置において、各ページの内容が線形に連結され、前記第３付加記憶手段は捜し出された最初及び最後のデータオブジェクトの各開始点に対する一対のポインタを保持することを特徴とするデータ処理装置。
【請求項８】
請求項７に記載のデータ処理装置において、前記プロセッサは、処理されているページ以外のページにおけるオブジェクトを識別した際に、該新たに捜し出されたオブジェクトの開始ロケーションを当該ページの開始及び終了ポインタと比較し、これらポインタを適切に更新するように構成されていることを特徴とするデータ処理装置。
【発明の詳細な説明】
技術分野
本発明は、相互に接続された記憶されたデータオブジェクトを扱うマーク付け方法及びデータ処理装置に係り、専らではないが特には、データ処理装置の実際の又は仮想のメモリスペース内でリアルタイムで実行するメモリ圧縮及びゴミ集め処理におけるオブジェクト構造を介しての参照の追跡に関する。
背景技術
ゴミ集め（garbage collection）は、プログラムにより最後に使用された後のシステムメモリスペースの自動化された再生利用である。多数のゴミ集め技術の例が、ジョン・ワイリ・アンド・サンにより１９９６年に発行された（ISBN 0-471-94148-4）Ｒ・ジョーンズ他による“ゴミ集め：自動式動的メモリ管理”の第１〜１８頁、及び１９９２年９月のフランス、サンマロにおけるメモリ管理に関する１９９２年国際ワークショップの論文集にＰ・Ｒ・ウィルソンにより掲載された“単プロセッサのゴミ集め技術”で議論されている。メモリの割り付け及び回復がプログラマ又はコンパイラにより扱われるようにして、多くのコンピュータプログラムの記憶要件は単純であり予測可能であるが、特定のデータ構造の寿命を実行時前に決定することが最早可能ではなく、従って当該プログラムが実行される際に当該記憶部を自動的に再生利用することが必須であるような、もっと複雑な実行パターンを持つ機能言語へ進む傾向がある。
上述したウィルソン文献に述べられているように、多くのゴミ集め再生使用技術の共通の特徴は、別個の記憶されたデータオブジェクトが持つポインタを参照することにより形成されるデータ構造を、増分的に調べることである。該技術は、先ず、データオブジェクトを連結するポインタを介して経路又は複数の経路を追跡することにより、他の記憶されたオブジェクトにより又は外部ロケーションから依然として到達され得る全ての記憶されたオブジェクトにマーク付けする過程を含む。この過程には、メモリを掃除又は圧縮する過程、即ち当該メモリに記憶された全てのオブジェクトを調べて、そのスペースを再生使用することができるようなマークの付されていないオブジェクトを決定する過程が後続する。
多くの場合、ゴミ集めは、単一の全域的ヒープ（即ち、データ構造又はオブジェクトが特定の順序によらず記憶される単一のメモリ領域）上で、特定のスペースが特定のオブジェクトを保持するのに充分な程大きいか否かに関してのみ動作する全システム的タスクである。全ての追跡型ゴミ集めシステムは、斯かるヒープ内のデータ構造を調べる機構を含んでいる。マークスタック又は待ち行列が、調査を継続中のオブジェクトに対する参照を記憶するために使用される。しかしながら、最悪の状況においては、マーク付けデータ構造の大きさが上記ヒープの大きさと同等となってしまう可能性がある。ゴミ集め手段の目的はメモリを再生使用することにあるから、マーク付け処理が小さな静的量よりも多くのメモリを必要とすることは許容することができない。上述したウィルソン文献は、割り付けられた各オブジェクト内のフィールドをマーク付けリスト内の次のものへのポインタ専用にすることを含む多数の従来の解決策を示している。この解決策は、全てのオブジェクトがマーク付けリスト上にあるような最悪の状況を見越すことにより静的なオーバーヘッドを保証するが、結果としてメモリを浪費する。他の技術は、一定のサイズのマーク付け構造を割り付け、斯かるマーク付け構造を満杯になるまで使用するが、その後、該マーク付けリストは新たな項目を該リスト上に戻すことなく処理される。この場合、上記のオーバーフローした項目を見付けるために、メモリは走査されねばならない。この妥協的解決策は最悪の場合の性能が劣る。何故なら、メモリの大きな領域が、オーバーフローしたデータを捜すために繰り返し走査されねばならないからである。第３の技術はポインタの逆転を使用し、ポインタを現ノードからマーク付けツリーを遡るように記憶する。余分なスペースは必要とされないが、アルゴリズムが実行されている間はヒープオブジェクトが不使用状態であるので、該アルゴリズムは増分的に使用することはできない。上記３つの技術のうち、第２のものが好ましい。何故なら、第２のものは第１のもののようにはメモリを浪費せず、第３のものとは異なり、完全なゴミ集め処理が実施される長い期間の間、プログラムの実行が停止される必要がないからである。
発明の開示
したがって、本発明の目的は、増分的ゴミ集め処理の一部として使用するのに適した追跡／マーク付け技術の効率の改善、及び斯かる技術を使用すると共に一定且つ有限の大きさのマーク付け構造が使用されるようなデータ処理装置の効率を改善することにある。
本発明によれば、マーク付けされていないデータオブジェクトのゴミ集めの準備のために、連続したメモリ内における識別ポインタにより連結されたデータオブジェクトから形成されるデータ構造を調べるマーク付け方法であって、該マーク付け方法が、
ａ）選択されたルートの１つのオブジェクトに関して、該１つのオブジェクトが持つポインタを調べて前記１つのオブジェクトに連結された他のオブジェクトを検出するステップと、
ｂ）上記ステップにより新たに検出された他のオブジェクトに対する参照子を固定された大きさのスタック又は待ち行列である付加記憶手段に入力するステップと、
ｃ）ポインタを調べて、前記ステップｂ）により識別された他のオブジェクトに連結された更に他のオブジェクトを検出するステップと、
を有し、前記ステップｂ）及びｃ）は前記スタック又は待ち行列である付加記憶手段が一杯になるまで繰り返され、次いで、これらステップにおいて識別されたオブジェクトがマーク付けされ、次いで、既にマーク付けされたオブジェクトに連結された別のオブジェクトを捜すために前記連続したメモリが走査されるようなマーク付け方法において、
前記連続したメモリが複数の別個のページに分割され、前記ステップｂ）及びｃ）が前記ルートの１つのオブジェクトと同一のページ内のオブジェクトに限定され、当該ページ外の何れの連結されたオブジェクトに関しても前記ステップｂ）において該ページに関する識別子が代わりに記憶されることを特徴とするようなマーク付け方法が提供される。
最初に処理される領域をページに制限し、次いで“オーバーフロー”オブジェクトが発生するページを記録することにより、効率が改善されると共に後の走査の量が減少される。上記スタック又は待ち行列である付加記憶手段は、好ましくは、１つのページ内に含まれることができる最大数のオブジェクトに関する各参照子を収容する大きさのものとし、１つのページ内の全オブジェクトが考慮された場合に、該スタック又は待ち行列である付加記憶手段が一杯になると見なされるようにする。また、動作時に、上記ステップａ）、ｂ）及びｃ）が各ページに対して順番に適切に実行され、ステップｂ）及びｃ）の続いての繰り返しが、前記連続したメモリ内にマーク付けされていない連結されたオブジェクトが残存しなくなるまで前記ページを介してサイクル内で繰り返されるようにする。この時点で、残存するマーク付けされていない何れのオブジェクトも削除することが可能なゴミであると見なされる。
また、本発明によれば、ランダムアクセスメモリに結合されたデータプロセッサを有するデータ処理装置であって、前記ランダムメモリは該ランダムメモリの連続した領域内に識別ポインタによりデータ構造内で連続された複数のデータオブジェクトを含み、該データ処理装置は固定した大きさのスタック又は待ち行列である第１付加記憶手段を更に有し、前記プロセッサは前記記憶された複数のデータオブジェクトに対して、
ａ）選択されたルートの１つのオブジェクトに関して、該１つのオブジェクトが持つポインタを調べて前記１つのオブジェクトに連結された他のオブジェクトを検出する演算と、
ｂ）上記演算により新たに検出された各他のオブジェクトに対する参照子を、
前記スタック又は待ち行列である第１付加記憶手段に入力する演算と、
ｃ）ポインタを調べて、前記第１付加記憶手段において識別された他のオブジェクトに連結された更に他のオブジェクトを検出する演算と、
を実行するよう構成され、前記プロセッサは前記演算ｂ）及びｃ）を前記スタック又は待ち行列である第１付加記憶手段が一杯になるまで繰り返し、これら演算において識別されたオブジェクトにマーク付けをし、前記ランダムアクセスメモリの連続した領域を走査して既にマーク付けされたオブジェクトに連結された全ての別のオブジェクトを捜すようなデータ処理装置において、
前記連続したメモリが複数の別個のページに分割され、前記演算ｂ）及びｃ）が前記ルートの１つのオブジェクトと同一のページ内のオブジェクトに限定され、当該ページ外の何れの連結されたオブジェクトに関しても該ページに関する識別子が第２付加記憶手段に記憶され、既にマーク付けされたオブジェクトに連結された全ての別のオブジェクトを捜す前記走査が前記第２付加記憶手段内で識別されるページのみに関して実行されることを特徴とするようなデータ処理装置が提供される。上記第１及び第２付加記憶手段は分離された別個のデータ処理装置として設けることができ、又はこれら記憶手段は上述した連続した走査される区域とは別個ではあるが、上記と同一のランダムアクセスメモリ内に保持されるスタック若しくは待ち行列を有してもよい。
各ページに関して当該ページの捜し出されたマーク付けされるべき最初及び最後のオブジェクトの開始ロケーションを示す２つのポインタフィールドを含む第３付加記憶手段を設けてもよく、既にマーク付けされたオブジェクトに連結された全ての他のオブジェクトを捜す前記走査が、前記第２付加記憶手段内で識別される各ページ内の上記の２つのポインタフィールドでカバーされた領域のみに関して実行されるようにする。各ページの内容が線形に連結される場合は、前記第３付加記憶手段は捜し出された最初及び最後のデータオブジェクトの各開始点に対する一対のポインタを適切に保持するようにし、前記走査が２つのアドレスの間の領域においてのみ実行されるようにする。このような構成においては、前記プロセッサは、処理されているページ以外のページにおけるオブジェクトを識別した際に、該新たに捜し出されたオブジェクトの開始ロケーションを当該ページの開始及び終了ポインタと比較し、これらポインタを適切に更新するように構成されるようにする。
【図面の簡単な説明】
以下、本発明を添付図面を参照して例示的にのみ説明するが、添付図面において、
第１図は、本発明を実施化するのに適したデータ処理システムのブロック図、
第２図ないし第４図は、部分的に連結された一群のデータオブジェクトを、３色マーク付け法を用いて追跡が進むにつれて示し、
第５図は、追跡の間に使用される付加的な参照記憶部を伴う複数のデータオブジェクトを含む連続したヒープメモリを表し、
第６図は、本発明を実施化する追跡／マーク付け処理を示すフローチャート、
第７図は、第６図におけるオブジェクトのマーク付けステップを詳細に示すフローチャート、
第８図は、第６図におけるオブジェクトの処理ステップを詳細に示すフローチャートである。
発明を実施するための最良の形態
第１図は、パーソナルコンピュータのようなデータ処理システムを示し、このシステムは例えば該システムを仮想環境を定義するデータ用のブラウザとして構成させることができるような多数のソフトウェアユーティリティ用のホストとして作用する。該システムは、アドレス及びデータバス１２を介してランダムアクセスメモリ（ＲＡＭ）１４及び読み出し専用メモリ（ＲＯＭ）１６に結合された中央処理ユニット（ＣＰＵ）１０を有している。これらのメモリは、１個又は数個の集積回路装置を有してなることができると共に、システムハードディスク及びＣＤ−ＲＯＭのような付加的な（着脱可能な）メモリ装置から読み取る手段により増加することができる。本発明は、特に、ＣＰＵ１０の制御下でのＲＡＭ１４のワーキング領域用のメモリ管理に実施化されており、このための制御プログラムは最初ＲＯＭ１６内に保持されると共に電源投入時にオペレーティングシステムと共にロードされる。
ＣＰＵ１０にはバス１２を介して第１及び第２のユーザ入力装置１８及び２０も結合されており、これら装置は好適にはキーボード、並びにマウス又はトラックボールのようなカーソル制御及び選択装置を有することができる。該システムからのオーディオ出力は、オーディオ処理段２４により駆動される１以上のスピーカ２２によりなされる。該システムからのビデオ出力は、ＣＰＵ１０の制御の下で表示駆動段２８により駆動されるディスプレイスクリーン２６上に提示される。該システムに対する更なるデータ源は、例えばインターネットを介してのように、遠隔サイトへのオンラインリンクを介するもので、該リンク側に対し当該システムはバス１２に結合されたネットワークインターフェース３０を備えている。
第２図ないし第４図は、３色マーク付け法（以下の例では、この用語が使用される）を用いた増分的ゴミ集めにおける追跡の基本原理を概念的に示している。増分的な収集の特別な特徴は、処理が連続的に実施されるのではなく、実行に対する長い中断をまねくのを防止するために、プログラム実行の期間により分散された離散的なステップで実施される点にある。３色法は、マーク付け処理を、ポインタによりリンクされたメモリオブジェクトにより形成された“ネットワーク”を介して広がるにつれて説明するのに便利なマーク付け方法である。このマーク付け方法においては、走査処理により到達され且つ通過されたオブジェクト（即ち、該走査が全てのリンクされた子孫オブジェクトに到達している）は、黒に色付けされ、該走査により到達されているが実際の又は可能性のある子孫オブジェクトは到達されていないようなオブジェクトはグレイに色付けされ、他の全てのオブジェクトは白に色付けされる。
第２図ないし第４図のオブジェクトの部分的にリンクされた集合において、第２図は、オブジェクト３５から開始して外方／下方に向かって広がる追跡処理の最初の増分的段階の後の状態を示し、オブジェクト３５は黒でマーク付けされ、該オブジェクトがポインタを有する３つのオブジェクト３６、３８及び３９はグレイでマーク付けされている。第３図は、更なる増分的段階の後の状態を示し、オブジェクト３６、３８及び３９の子孫オブジェクト４０、４１、４２、４４及び４５が到達され、これに応じてグレイにマーク付けされている。オブジェクト３６、３８及び３９は、それらの全ての子孫オブジェクトが到達されているので、この段階では黒でマーク付けされている。第４図は、残存するリンクされたオブジェクトが存在しないと判断された最終段階を示し、オブジェクト４０、４１、４２、４４及び４５は黒でマーク付けされる。これにより、マーク付けフェーズは終了し、ポインタが存在しない２つの“到達することのできない”オブジェクトが存在することが分かる。これらのオブジェクトは依然として白でマーク付けされており、ゴミであり、したがって削除することができることを示している。
３色マーク付け法は、上記ウィルソン文献に斯かる処理の増分的特性を扱うための技術を含み詳細に議論されており、そこでは、データ構造の配置は走査の間に変更することができ、プログラム実行の分散された区画が配置されたポインタの配列をずらす。一つの特筆すべき点は、第２図ないし第４図におけるオブジェクトの階層的な配置は純粋に図示説明の目的のためのものであり、実際には、これらオブジェクトは利用可能なメモリ全体に連結ポインタの配置のみにより決まる階層構造で分散される。
第５図は、第１図のシステムからの多数の別個のメモリ領域、及び特に種々のプログラムスレッドにより使用される多数のデータオブジェクト５２を保持するヒープメモリ５０を概念的に表している。以下の例は、ジャバ（▲Ｒ▼サン マイクロシステムズ インク）の仮想マシンにおけるメモリ管理技術に従っており、用語はそれに応じて解釈されるべきである。しかしながら、本発明はジャバに準拠したシステムに限定されるものではなく、純粋に仮想的なメモリ管理に限定されるものでもないことが理解されるであろう。図示の配置においては、ゴミ集めが、プログラムによる最後の又は唯一の参照の後にデータオブジェクトが削除されるようになされるのは上記ヒープメモリ５０である。
該ヒープ５０はメモリの１つの連続した領域であると見なされる。該領域は論理的に一定の大きさのページＰ．０ないしＰ．５に分割され、データオブジェクト５２は複数ページにわたることができる。即ち、ページの境界はマーク付け処理以外では意味を有さない。該ヒープ５０と共に、多数の別個の記憶されたデータ構造が使用される。物理的には、これらは別個の主体を有するか、又は当該ヒープを含むメモリ内のゴミ集めの目的で走査される領域以外の個別の領域であってもよい。これら構造の第１のものは、１ページに入る最大数のオブジェクト５２を保持するのに充分な程大きなスタック５４の形態の固定した大きさのマーク記憶部である。該マークスタックは１度に１ページ内のオブジェクトを処理するために使用される。第２の構造は、当該ヒープの各ページに対する参照を含むのに充分な程大きな固定した大きさのページリスト５６である。該リストは各ページに対する参照を含む巡回式バッファの形態である。当業者であれば、上記マーク記憶部及びページリストは、各々、スタック（図におけるマーク記憶部のように）又は待ち行列（図におけるページリストのように）の何れかとして構成することができることが理解されるであろう。
第３の記憶されるデータ構造は、全ページへのエントリを備える固定した大きさのテーブル５８である。各エントリは２つのポインタフィールド、START及びENDを有している。これらフィールドは、当該ページ内でマーク付けされるべき最初及び最後のオブジェクトの開始ロケーションを示すように設定される。ヘッドポインタが当該ページ内のアドレスを示す場合には、該ページ内にオブジェクトが‘存在’する。他のページにオーバーフローするオブジェクトは、これらのポインタによっては参照されない。
以下、第６、７及び８図を参照して追跡及びマーク付け処理を説明するが、該処理は前述したように増分的方法に適していることを示す３色マーク付け法を仮定している。他のマーク状態機構は該アルゴリズムとは互換性がない。
メイン処理が第６図に示され、該メイン処理は６００で開始して、最初の処理は６０１においてオブジェクトのルートの組から最初の項目を選択することである。このルートの組は、スタック、全域的オブジェクト及び、通常は、当該ヒープの外側から参照することができる全ての記憶されたデータ主体を有している。選択に続いて、マークサブルーチンが６０２において実行される。該サブルーチンの個々のステップは第７図を参照して説明する。マーク付けに続いて、６０３において、上記ルートの組内に何らかの残存する項目があるかに関しての検査がなされる。該ルートの組内には処理されるべき残存項目がない場合は、処理は６０４へと続き、さもなければ、該処理は６０５（当該ルートの組からの次の項目の選択）を介して項目マーク付けサブルーチン６０２の開始に戻る。６０４においては、前記ページリスト（第５図の５６）が空であるかに関しての更なる検査がなされ、もしそうなら、当該処理は６０６において終了する。
６０４の検査がページリストは空でないことを示す場合は、６０７において上記リストから次のページが取り出され（POP）、６０８において該ページ内の最初の項目が選択される。６０９においては、該項目が既にグレイにマーク付けされている（即ち、該項目は到達されたが、ヒープ走査によっては未だ充分には考慮されていない）かについての検査がなされる。この項目がグレイである場合は、該項目は６１０において処理されるが、該処理の詳細は第８図を参照して後述する。検査６０９の結果が否定的である（即ち、当該項目がグレイでない）場合は、６１１において該項目が特定のページの最後のものであるかについての更なる検査がなされ、そうでない場合は、６１２において当該ページからの次の項目が選択され、当該処理は６０９における当該項目がグレイであるかについての検査に戻る。６１１の上記検査が、当該ページからの全ての項目が考慮されたことを示す場合は、（６１３における）次の検査が当該マークスタック（第５図の５４）内に何らかの残存項目が存在するかを判定し、もしそうなら、これら残存項目の最初のものが６１４において取り出され、続いて６１３に戻る前に６１５において（ここでも、第８図の処理ルーチンを用いて）処理される。該マークスタックが空である場合は、当該処理は６０６において終了する。
上記ステップ６０２のマーク付け処理は、第７図に詳細に示され、７０１において当該項目をグレイに設定することにより開始する。７０２においては、目下考慮中の項目が当該ヒープメモリ内の何のページにあるかについての判定がなされる。ステップ７０３により当該項目が目下考慮中の現ページ内にあると判定された場合は、該項目は当該ページ内での後での処理のために７０４においてマークスタックに格納（Push）され、続いて当該マーク処理は７０５において終了する。
７０３の検査が、目下考慮中の項目が現ページ外にあることを示す場合は、該項目が実際に存在するページに関しページテーブルは更新又は作成さえされる必要がある。ステップ７０６において、新たに識別されたページに関する開始ポインタが無に設定されているかについての検査がなされる。もしそうなら、当該ページに関しては記録された既存のオブジェクトはないと仮定される。結果として、ステップ７０７において該新たに識別されたページがページリスト（第５図の５６）に追加されて、該ページが“生の”オブジェクトを含んでいることを示すようにし、これに続いてステップ７０８において該ページに関する開始及び終了ポインタがステップ７０８及び７０９において目下考慮中の項目の開始点に各々設定され、これに続いて当該処理は７０５において終了する。当該ページテーブルの開始ポインタが無の値を有していない場合（７０６）は、該ページに関して記録された少なくとも１つのオブジェクトが既に存在することを意味する。このような状況においては、新たな項目を考慮するために、通常は開始ポインタ又は終了ポインタの何れかを適合させる必要があるであろう。ステップ７１０においては、上記新たな項目の開始点が上記開始ポインタにより特定される既存のロケーションよりも当該ページの始点に近いかについての検査がなされ、もしそうなら、ステップ７１１において該開始ポインタが更新される。ステップ７１２においては、上記新たに考慮されている項目の開始点が上記ページ終了ポインタにより特定されるロケーションよりも当該ページの終点に近いかについての検査がなされ、もしそうなら、ステップ７１３において該終了ポインタが更新されると共に当該処理が終了される。
第６図における項目処理段階６１０及び６１５が、第８図に詳細に示されている。８００における開始から始めて、８０１において、目下考慮中の項目がポインタを有する最初の項目が選択される。８０２において、この最初に選択された項目が白である（即ち、以前にマーク付けがされていない）かについての検査がなされ、その場合にはステップ８０３において当該項目はマーク付けされる。ステップ８０４においては、目下考慮中の項目により参照される何らかの他の項目が存在するかについての検査がなされ、もしそうなら、これら項目のうちの次のものがステップ８０５において選択され、当該処理はステップ８０２における該項目が白であるか否かの検査に戻る。ステップ８０４により、目下考慮中の項目により参照される全項目が扱われたと判断されると、該目下考慮中の項目は、当該ルーチンが８０７において終了する前に、ステップ８０６において黒に設定される。
第６図の処理が一旦完了すると、全てのオブジェクトは白状態又は黒状態となる。白のオブジェクトは削除することができる。
この処理は、全てのマーク演算が代わりに上記ページテーブルにデータを追加することにより、ローカルなマークスタック無しで（僅かに修正された形態で）実施化することができる。しかしながら、参照に関する相応の局所性のレベルが与えられた場合は、マークスタックの使用が好ましい。何故なら、マークスタックの使用は、処理されているページがページリスト上で置き換えられねばならない回数を劇的に減少させるからである。
当該アルゴリズムの性能は多くの要因に依存し、それら要因の第１のものはページの大きさである。ページテーブルの背後にある理由付けは、オブジェクトの検索スペースを狭小化することにある。最悪の状況は、当該ページ内の最初と最後の項目はグレイであるが中間のオブジェクトがそうでない場合である。ページの大きさは、上記最悪の状況が許容できるように、選定されるべきである。小さなページは、短い走査フェーズをページテーブルに関する大きな静的オーバーヘッドに対して取り引きすることになる。
第２の要因は参照の局所性である。オブジェクトは、しばしば、メモリ内で互いに近接する他のオブジェクトを参照する。このような発生が実際にどの程度普通であるかは、採用される割り付けシステム及びメモリ圧縮処理のようなデータを移動させる他の処理に依存する。上記マークスタックは、ページテーブルに対する不必要な処理を防止すべく、ページ内参照を記憶するために使用される。各ページの大きさは既知であるから、各ページ処理フェーズの間に上記マークスタックに対して処理することができる項目の数は既知となる。参照の局所性の程度が高い程、当該ページリストに載せられるページの数は少なく、外側のループの繰り返しの数も少ない。ページの大きさは、典型的なデータ構造の大きな部分が１つのページ内に完全に納まり、従ってページ間ポインタが論理的に別個のデータ項目の間で発生し易いように、選定されるべきである。
主にソフトウェアのブラウザの構成に関して規定したが、当業者であれば、上述した多くの機能的特徴がハードウェアの形でも同様に実施化することができることが分かるであろう。
本開示を読むことにより、当業者にとっては、他の変形例が明らかとなるであろう。斯かる変形例は、画像処理及び／又はデータネットワークアクセス装置並びにそれらの部品の設計、製造及び使用において既知であり、且つ、上述した特徴の代わりに又はそれらに追加して使用することができるような他の特徴を含むことができる。本出願においては請求項は特定の特徴の組み合わせに対して記載されているが、本出願の開示の範囲は、何れかの請求項において現在記載されている発明と同一の発明に関するものであるか否かに拘わらず、且つ、本発明が解決するものと同一の課題の何れか又は全てを解決するか否かに拘わらず、本明細書で明示的に又は暗示的に開示された如何なる新規な特徴若しくはこれら特徴の新規な組み合わせ又はそれらの如何なる一般化をも含むものと理解されるべきである。出願人は、斯かる特徴及び斯かる特徴の組み合わせに関して、本出願又は本出願から派生する全ての他の出願の審査の間に、新たな請求項を記載することがあることを注記する。
【図１】
0004248025.tif 000002
【図２】
0004248025.tif 000003
【図３】
0004248025.tif 000004
【図４】
0004248025.tif 000005
【図５】
0004248025.tif 000006
【図６】
0004248025.tif 000007
【図７】
0004248025.tif 000008
【図８】
0004248025.tif 000009