(57)【特許請求の範囲】
【請求項１】
１つ以上のオブジェクトを格納するメモリ内の個々の空きスペース領域を検出し合体させるためのマーク・アンド・スイ−プ法を用いたガ−ベッジ収集処理方法であって、
関心のあるシーケンスを求めて、生きている各オブジェクトの先頭にある第１セグメントに対応して１が設定され且つ生きていない各オブジェクトの各セグメント及び各オブジェクトの残りのセグメントに対応して０が設定されるマーク・ビット配列を検査するステップであって、前記関心のあるシーケンスがそれぞれ、しきい値数以上の連続している０のマーク・ビットを含んでいる、前記検査するステップと、
前記メモリのスイープ中に、前記マーク・ビット配列内のそれぞれの関心のあるシーケンスに対応する各メモリ領域の直前に格納されているオブジェクトの長さを検査し、この長さを当該関心のあるシーケンス内の連続している０の数と比較し、その差が充分に大きい場合には、当該各メモリ領域を割振り解除するステップとを含む、方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は一般に、データ処理システム内のメモリ管理に関し、より詳細には、データ処理システム内の空きスペース・メモリの割振り解除および合体（ｃｏａｌｅｓｃｅ）に関する。さらに詳細には本発明は、データ処理システム内のオブジェクト指向プログラム用のマーク・スイープ・ガーベッジ収集（ｍａｒｋ−ｓｗｅｅｐ  ｇａｒｂａｇｅ  ｃｏｌｌｅｃｔｉｏｎ）メモリ管理に関する。
【０００２】
【従来の技術】
「オブジェクト」は、コンピュータのプログラミングおよび操作の分野で考えるとき、定義されたプログラミング単位を指し、このプログラミング単位は通常、オブジェクト指向プログラムの多数の構成単位（ｂｕｉｌｄｉｎｇ  ｂｌｏｃｋ）の１つである。オブジェクトは、データおよびそのデータに対して実行することができる操作（メソッドと呼ばれる）から成る。標準の手続き型プログラミングに勝るオブジェクト指向プログラミングの利点の１つは、オブジェクトにより、プログラマが、新しいタイプのオブジェクトを追加するときに変更する必要のないモジュールを作成できるようになることである。米国カリフォルニア州パロ・アルトのＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社の商標であるＪａｖａＴＭは、オブジェクト指向プログラミング言語の一例である。
【０００３】
オブジェクトは文字通り、メモリの別々の領域を占め、重なり合うことが許されない。言い換えるとオブジェクトは、他のいかなるオブジェクトとも共用しない、メモリ内の定義された領域を有する。進行中の処理で現在利用されている「生きている（ｌｉｖｅ）」オブジェクトを含めて、様々な状態のオブジェクトがある。生きているオブジェクトには、プログラム内で占めることのできる寿命があり、そのオブジェクトに対する最後の参照が消滅するときにのみ死ぬ。「死んだ（ｄｅａｄ）」オブジェクト、または生きていないオブジェクトとは、その寿命が尽き、コンピュータ処理においてさらに利用されることのないオブジェクトである。「ヒープ」とは、そのサイズまたは存在が事前に決定できないデータを格納するときに、プログラムが利用するために確保されるメモリの部分を指す。
【０００４】
「ガーベッジ」とは、メモリ内に格納されているもう利用されないデータを指す。「ガーベッジ収集」とは、もはや使用されていないメモリを自動的に検出し、解放することである。オブジェクト指向プログラミングは通常、ヒープ内の利用されていないメモリを識別して解放するメモリ管理機能を含む。ガーベッジ収集機能を実行することにより、プログラマが明示的にメモリを割振り解除する（ｄｅ−ａｌｌｏｃａｔｅ）必要が無くなり、メモリ・フラグメンテーションが自動的に減少する。通常ガーベッジ収集手順は、予定に基づき指定してメモリを割振り、解除するのではなく、動的に記憶域を再利用し、提供する。
【０００５】
「マーク／スイープ」は、特定のタイプのガーベッジ収集手順であり、メモリを２回通過するうち１回目に、生きているオブジェクトが占める全てのメモリに、最初にマークをつけることによってスペースを再利用する。１回目の通過は、少なくとも１つの生きている（プログラム動作に必要な）アンカー・オブジェクトまたはルートから始まる。この手順は、１組のベース・ポインタから繰り返しポインタを追跡し、実際に使用されている記憶域内の、ポインタによって識別される各記憶域に対して、メモリ割振りテーブル内のマーク・ビット（ｍａｒｋ  ｂｉｔ）（オブジェクト上のビットが１に設定される）を設定するものである。このマーク機能の開始時に、メモリ割振りテーブルのすべてのマーク・ビットが０に設定される。生きているオブジェクトの先頭に対応する先頭マーク・ビットが１に設定され、生きているオブジェクト内の後続のバイト群に対応するマーク・ビットは０のままとなる。関連づけられたオブジェクトが生きているオブジェクトでない場合には、先頭マーク・ビットを含むマーク・ビットが０のままとなる。生きているオブジェクトにマークした後に、２回目の通過で、各オブジェクトを列挙することによって各オブジェクトを検査する（「スイーピング」）。あるオブジェクトに対して少なくとも１つの生きている参照が存在する限り、そのオブジェクトをガーベッジ収集することができず、そのオブジェクトを含む記憶域を割振り解除することができない。そうでない場合には、以前そのオブジェクトが占めていたメモリは割振り解除され、将来の割振りに利用可能になる。利用可能になった隣接した死んでいるオブジェクトは、より大きな空き領域に合体される。
【０００６】
図５、６を参照すると、マーク／スイープ方法の高レベルの流れ図が示してある。この収集処理は生きているオブジェクトを判定するためのものなので、マーク機能はステップ５００から始まり、ここからマーク／スイープ・ガーベッジ収集処理が開始し、生きていようがいまいが全てのマーク・ビットを０にリセットする。ステップ５０２に進み、「保留中」リスト（マークを付けられ、後で走査される生きているオブジェクトを含むリスト）を空にする。次いでステップ５０４に移り、マーク機能が各ルート・オブジェクト（生きていることが分かっているオブジェクト）にマーク・ビットを設定する。ステップ５０６に移り、各ルート・オブジェクトが保留中リストに加えられる。ステップ５０７に進み、保留中リストが空であるかどうか判定する。空である場合には、図６で述べるとおり、スイープ機能に進む。この保留中リストが空でない場合には、ステップ５０８へと進み、保留中リストから（生きている）オブジェクトを取り出す。
【０００７】
次にステップ５１０に進み、取り出されたオブジェクトが他のオブジェクトを参照しているかどうかを判定する。参照していない場合、ステップ５０７に戻る。そのオブジェクトが別のオブジェクトを参照していると判定される場合には、代わりにステップ５１０からステップ５１２に移り、参照されているオブジェクトが全てマークされているかどうか判定する。マークされている場合には、ステップ５０７に進み、このサイクルを繰り返す。そうでない場合には、代わりにステップ５１４に進み、参照されているマークされていないオブジェクトを全て保留中リストに追加する。次いでステップ５１６へと進み、参照されているマークされていないオブジェクト全てをマークする。次にステップは５０７に移って、保留中リストが空であるかどうかを調べる。このリストが空である場合には、マーク／スイープ・ガーベッジ収集処理のスイープ機能に進む。そのリストが空でない場合には、ステップ５０８に戻る。
【０００８】
次に図６を参照すると、マーク／スイープ・ガーベッジ収集処理のスイープ段階が示してある。ステップ５１８から始まり、第１のオブジェクトを見つける。次いでステップ５２０に進み、そのオブジェクトを検査する。次いでステップ５２２に移り、マーク・ビットをテストすることによって、そのオブジェクトが生きているかどうかを判定する。そのオブジェクトが生きていない場合には、ステップ５２４に進み、スイープ機能がオブジェクトを割振り解除してスペースを再利用する。ステップ５２６へと進み、割振り解除されたオブジェクトが任意の隣接した空きスペースと合体される。次にステップ５２８に移り、メモリ内のオブジェクトがすべてスイープされたかどうか判定する。ステップ５２２に戻って、そのオブジェクトが生きている場合には、スイープ機能はそのオブジェクトを無視し、ステップ５２８に移って、すべてのオブジェクトがスイープされたかどうかを判定する。すべてのオブジェクトがスイープされた場合には、ステップ５３２へと進み、マーク／スイープ・ガーベッジ収集手順が休止状態に戻る。そうでない場合は、代わりにステップ５３０に移り、スイープ機能は別のオブジェクトを探す。
【０００９】
スイープ・アルゴリズムがヒープ上の各オブジェクトを順次検査するので、「次の」オブジェクトの発見は非常に迅速でなければならない。多くのマーク／スイープ・アルゴリズムは長さフィールドを各オブジェクト上に置くことを選択するので、各オブジェクトはそのオブジェクトのサイズを記述する「長さ」フィールドから始まる。次のオブジェクト（実際には次のオブジェクトの長さフィールド）は、長さフィールド自体のアドレスに現在のオブジェクトの長さフィールドを加えることによって見つけられる。例えば、
0003560535.tif 000002
【００１０】
Ｌ１およびＬ２は、それぞれオブジェクトＡおよびＢのアドレスである。Ｌ１が与えられるとＡがどこにあるかが分かり、Ｌ１に「Ａの長さ」を加えてＬ２を得ることによって、Ｂが見つかる。しかしながら、長さフィールド（Ａの長さ、Ｂの長さ等）はヒープ内でスペースを占める。ほとんどのオブジェクトが得てして小さいので、かなりの量のヒープ・スペースがこの長さフィールドによって占められる。この長さフィールド情報を多数のオブジェクトで共用することができるなら、ヒープ内のメモリをプログラム使用のために保存できることになる。
【００１１】
マーク／スイープ・ガーベッジ収集方式は、システムがメモリを２回通過する間、このシステムに他の全ての動作を停止させる。この方式は、生きているオブジェクトを繰り返し処理し、プロセッサにかなりの負担をかける。ガーベッジ収集は繰り返し実行され、その主な利点は自動的に記憶域を再利用してメモリ設計エラーを減少させることにあるが、この処理はプロセッサ時間を費やし、進行中のアプリケーションを中断する。ガーベッジ収集は自動的であり、プログラマーの制御を超えているので、収集処理は、プログラム・アプリケーションが活動中の不都合な時に活動状態になる可能性がある。
【００１２】
「コピー」タイプのガーベッジ・コレクタは、生きているオブジェクトをすべてある区域から別の区域に動かす。新しい区域では、生きているオブジェクトは、隣接したスペースにコピーされ、そうすることよって、古い区域でそれらを分離していた空きスペース領域を除去する。生きているオブジェクトが動かされた元のスペースは、そのとき空であると見なされる。すべての空きスペースが単一集合として取り扱われ、死んでいるオブジェクトに注意は払われない。しかしながらコピー方式を実施するには、生きている個々のオブジェクトをすべてガーベッジ収集中に動かせることが必要である。コピー方式のガーベッジ・コレクタの欠点は、一時に使用可能メモリの半分しか使用されないので、ガーベッジ収集がより頻繁に発生することである。
【００１３】
したがって、オブジェクトを動かすことのできない状況を許容する方法および装置を提供することが望ましい。メモリ内の各オブジェクトを検査する必要をなくすことによって、システム・プロセッサに対する負担を減らすことも望ましい。進行中のプログラム・アプリケーションを中断する必要のある時間を減らす方法および装置を提供することがさらに望ましい。
【００１４】
【発明が解決しようとする課題】
したがって本発明の一目的は、データ処理システム内で、メモリ管理の改善された方法および装置を提供することである。
【００１５】
本発明の他の目的は、データ処理システム内で、空きスペース・メモリを割振り解除し合体させる改善された方法および装置を提供することである。
【００１６】
本発明の他の目的は、データ処理システム内で、オブジェクト指向プログラム用のマーク・スイープ・ガーベッジ収集メモリ管理のための改善された方法および装置を提供することである。
【００１７】
【課題を解決するための手段】
前述の目的は次に述べるように達成される。割振られていないメモリ・スペースを検出して再利用するとき、「関心のある（ｉｎｔｅｒｅｓｔｉｎｇ）」空きスペース領域（最小サイズより大きく、したがって回復する価値のあるそれらの領域）のしきい値サイズをガーベッジ収集中に使用する。マーク／スイープ・ガーベッジ収集に関しては、このしきい値はマーク・ビット配列内で連続する０のマーク・ビットの数に基づく。生きているオブジェクトの第１メモリ・セグメントを論理「１」、死んでいるオブジェクトの第１メモリ・セグメントを論理「０」、他のセグメントに対応する残りの配列要素を論理「０」でマークすることによって、割振られた各データ・オブジェクトが生きていることを示すマーク・ビット配列が、マーク／スイープ・ガーベッジ・コレクタのマーク段階によって生成される。しかしスイープ段階中には、メモリ内の各オブジェクトの代わりにこのマーク・ビット配列が処理される。しきい値サイズと一致するかまたはそれより大きく、割振り解除および合体の対象となる関心のある空きスペース領域は、連続する０の列（ｒｕｎ）またはシーケンス（ｓｅｑｕｅｎｃｅ）によって識別され、その列が、使用されていないメモリに対応することが検証される。これにより、ビット・シーケンスを並行に高速で検査し、オブジェクトを個々に検査する必要を無くし、生きているオブジェクトと混在する小さな空きスペース領域をスキップすることが可能となる。各オブジェクトが「生きている」ことを検査する必要を無くすことにより、マーク・ビットによって表されるオブジェクトのグループが、より迅速に処理することのできる集合として扱われる。
【００１８】
【発明の実施の形態】
図１を参照すると、本発明の好ましい実施形態を実施することのできる典型的なデータ処理システムが示してある。インターナショナル・ビジネス・マシンズ・コーポレーション（ＩＢＭ）から市販のＰＣマイクロプロセッサなどの中央処理装置（ＣＰＵ）１０２が設けられ、システム・バス１０１を介して他の様々なコンポーネントに相互接続される。オペレーティング・システム１２８は、ＣＰＵ１０２上で稼働し、制御を可能にし、図１の様々なコンポーネントの機能を調整するのに使用される。オペレーティング・システム１２８は、Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓから市販のＪａｖａＯＳＴＭオペレーティング・システムなど、市販されているオペレーティング・システムの１つでよい（ＪａｖａＯＳは米国カリフォルニア州パロ・アルトのＳｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社の商標）。オブジェクトを組み込んだプログラムであるアプリケーション１３０は、オペレーティング・システム１２８と共に稼働し、オペレーティング・システム１２８に出力呼出しを与え、オペレーティング・システム１２８が、アプリケーション１３０によって実行される様々な機能を実施する。
【００１９】
読取り専用メモリ（ＲＯＭ）１０４は、バス１０１を介してＣＰＵ１０２に接続され、基本的なコンピュータ機能を制御する基本入出力システム（ＢＩＯＳ）を含む。ランダム・アクセス・メモリ（ＲＡＭ）１０６、入出力アダプタ１０８、通信アダプタ１２２もシステム・バス１０１に相互接続される。オペレーティング・システム１２８およびアプリケーション１３０を含むソフトウェア・コンポーネントが、コンピュータ・システムの主記憶であるＲＡＭ１０６にロードされることに留意されたい。入出力アダプタ１０８は、ディスク記憶装置１１０と通信するＥＩＤＥ（拡張統合ドライブ電子回路）またはＰＣＩ（周辺コンポーネント・インタフェース）アダプタでもよい。通信アダプタ１２２は、バス１０１を外部ネットワークと相互接続し、データ処理システム１００がローカル・エリア・ネットワーク（ＬＡＮ）またはインターネットを含む広域ネットワーク（ＷＡＮ）を介して他のそのようなシステムと通信することを可能にする。入出力デバイスも、ユーザ・インタフェース・アダプタ１１２およびディスプレイ・アダプタ１２４によりデジタル−アナログ・コンバータ（図示せず）などの様々なコンポーネントを介してシステム・バス１０１に接続される。前述の入出力デバイスを使用することによって、ユーザーは、キーボード１１４、トラックボール１２０、マウス１１６によってシステムに情報を入力し、スピーカ１１８およびディスプレイ１２６によってシステムから出力情報を受け取ることができる。
【００２０】
次に図２を参照すると、本発明の好ましい実施形態によるマーク・ビット配列データ構造と、マーク・スイープ・ガーベッジ収集で用いられる関連メモリ・セグメントのブロック図が示してある。マーク・ビット配列２０２は、メモリ２０４の対応する部分内の各オブジェクトが生きていることを記述するビットの高密度の配列から成り、この配列は、マーク・スイープ・ガーベッジ収集のマーク段階中に設定されることも、設定されないこともある。配列２０２内のマーク・ビットがメモリ２０４内の対応するメモリ・セグメントに隣接しているように示されているが、実際には、マーク・ビットが対応するメモリ・セグメントに実際に隣接している可能性は高くない。
【００２１】
マーク段階中に、メモリ・ヒープの生きている各オブジェクトの先頭に対応して１ビットが設定される。他のすべての（生きていない）オブジェクトおよびオブジェクトの先頭に対応しないビットは、０のマーク・ビットを有する。マーク・ビット配列２０２内のマーク・ビットを列挙するリスト２０６は、本発明の説明を容易にするためにこの図に含めたが、本発明のデータ構造の一部を構成しない。
【００２２】
生きているデータを含むメモリ領域２０４は、この図で「データ」と識別され、一方生きているデータ・オブジェクトを含まない領域は、網掛によって示されている。図示したとおり、生きているオブジェクトの一部を形成する隣接する各データ領域に関連する第１ビットは、論理「１」でマークされる。一方配列２０２内の他のすべてのビットは論理「０」に設定される。
【００２３】
この例では、例えば配列２０２内のマーク・ビット１〜５、７、１０〜１１、１４〜１５、２０、２４、２６〜２９はすべて生きているオブジェクトに対応し、マーク・ビット６、８〜９、１２〜１３、１６〜１９、２１〜２３、２５、３０〜３２は生きているデータを含まないメモリ領域に対応する。配列２０２内のマーク・ビット１、２、４、７、１０、１４、２０、２４、２６は、生きているデータ・オブジェクトの第１メモリ・セグメントに対応するので、すべて論理「１」に設定される。
【００２４】
本発明では、本発明のマーク・スイープ・ガーベッジ収集方式の「ビットごとスイープ」機能によりメモリ領域を検査するかどうかを判定するしきい値が設定される。本発明は、「関心のある」空きスペース領域（最小サイズより大きい領域）がマーク・ビット配列２０２内で、かなりの連続する０のシーケンスをもたらすという事実を利用する。プロセッサは、バイトおよびワードの内容がすべて０であるかどうかを判定する効率的なテスト、すなわち一般に１プロセッサ・サイクルしかかからないテストを提供する。したがって、ビット・グループを合わせて高速に検査し、そのグループ内のすべてのビットが０であるかどうかを判定することが可能である。
【００２５】
この例ではしきい値が４ビットに設定され、この場合、４個未満の０のどのシーケンスも無視され、４個以上の０のどのシーケンスも検査される。したがって、ビット１〜１３（シーケンス２０８）は、その範囲内に少なくとも４個の０の列が識別されないので、迅速に除かれる。したがって本発明のスイープ段階は、シーケンス２１０までの全てのビットをスキップする。しかし、マーク・ビット１５〜１９（５つの０のビット）を含む、関心のある領域、シーケンス２１０は検出される。
【００２６】
生きているオブジェクト・シーケンスがマーク・ビット１４および１５に対応し、ここでビット位置１４は、生きているオブジェクトの配列２０２内の第１マーク・ビットであり、このオブジェクトは、マーク・ビット１４に関連するメモリ・セグメントに第１バイトを有し、マーク・ビット１５に関連するメモリ・セグメントまで延びる。しかしながら、マーク・ビット配列２０２の位置１４〜１９が１つの生きているオブジェクトに対応するかもしれないので、本発明のスイープ段階はマーク・ビット位置１４に対応するデータ・オブジェクトのサイズを検査する必要がある。このデータ・オブジェクトは、マーク・ビット位置１４および１５に対応する２つのメモリ・セグメントを占めると判定される。マーク・ビット位置１４〜１９に対応する残りのメモリ・セグメント、すなわち、マーク・ビット位置１６〜１９に対応するメモリ・セグメントは、生きているデータを含んでいないと判定される。
【００２７】
ビット位置１４、１５は生きているオブジェクトに対応するが、シーケンス２１０に対応するメモリ・セグメントを検査する動機は、配列２０２内で検出された連続する０のマーク・ビット数である（ビット位置１５〜１９の５つ）。「死んでいる」データを含むわずか４つの連続するメモリ・セグメントが見つかり、４つの連続する０のマーク・ビットというしきい値が満たされるので、これらのメモリ・セグメントを割振り解除し、ガーベッジ収集処理によって合体させることができる。
【００２８】
この例を続けると、４つの連続する０のビットというしきい値が満たされないので、本発明のスイープ段階はビット位置２１〜２５をスキップする。しかし、ビット位置２６〜３２のシーケンス２１２は、これらの位置のマーク・ビット配列２０２内に４つより多い連続する０があるので、検査される。スイープ段階がシーケンス２１２に対応するメモリ・セグメントを検査するとき、スイープ段階は、マーク・ビット２７〜２９に関連するメモリ・セグメントが、ビット位置２６に関連するメモリ・セグメントから始まる生きているオブジェクトを指すと判定する。したがって、空きスペースのしきい値サイズか満たされないので、ビット位置３０〜３２に対応するメモリ・セグメントを含む、検査されたメモリ・セグメントは全て無視される。しかし図３で論じ示すとおり、「充分大きい」空きスペースは、関心のあるシーケンスとともに、割振り解除するステップに含まれる可能性がある。
【００２９】
図２が示すとおり、マーク・ビット配列２０２は迅速に走査することができ、わずか２つの関心のあるシーケンスが検出され検査される。したがって本発明のスイープ段階は、ビット位置１５〜１９および２７〜３２に対応するメモリ・セグメントを検査するにすぎず、他の全てのメモリ・セグメントを無視する。これは、各データ・オブジェクトの検査よりかなり速く達成することができる。
【００３０】
ここに示すとおり、生きているオブジェクトのシーケンスは、関心のない空きスペース領域と混在する可能性があるが、迅速にスキップすることができる。（マーク・ビット配列２０２内に対応する０の列を有する）大きな空きスペースのシーケンスは、高速で処理することができる。残りの作業は、０のビットの関心のある各列の前にあるオブジェクトを検査することである。（多数バイト長の可能性のある）オブジェクト毎にわずか１ビットしか設定されないので、０の大きな列が大きなオブジェクトを表す可能性がある。しかし、ほとんどのオブジェクトが小さいので、場合によっては大きなオブジェクトを検査することが過大な処理時間をもたらさないように、しきい値を選択することができる。
【００３１】
上記の説明は、マーク・ビット配列２０２内のビットごとの検査に関するものである。しかし実際には、関心のある空きスペースを示す０のしきい値の列は４よりずっと大きい数に設定される可能性がある。関心のある領域を識別するしきい値として選択される連続する０の数は、メモリ・スイープのスピードと使用されていないメモリの再利用を均衡させるように選択することができる。したがって、マーク・ビット配列２０２内の連続する０のバイトあるいはワードを探すことによって、マーク・ビット配列を処理し、さらにスイープ段階のスピードを改善することができる。上述のプロセッサ命令をこの目的に用いることができる。
【００３２】
図３を参照すると、本発明の好ましい実施形態によるマーク・スイープ・ガーベッジ収集のスイープ段階中にマーク・ビット配列を検査する処理の高レベル流れ図を示す。処理はステップ３００で開始し、既に図５および図６に関して述べたマーク・スイープ・ガーベッジ収集のマーク機能が完了している。しかしこの処理のスイープ機能は、通常のマーク・スイープ・カーベージ・収集ルーチンのスイープ処理とは対照的に、図２に関して上述したスイープ処理である。
【００３３】
次にステップ３０２に移り、関心のあるシーケンス（関心のある領域とも呼ばれる）のしきい値が設定され（設計者によってあらかじめ選択されるか、またはシステム要件によって動的に判定される）、スイープ機能中に適用される。しきい値は、少なくとも最小サイズであり、このしきい値より小さい空きスペース領域は無視される。実際には、全ての空きスペースのほんの小さな部分だけがしきい値より小さい領域から成るようにしきい値を選択することが可能なので、ほとんど全ての空きスペースが発見される。個々の各オブジェクトを検査する必要を無くすことにより、本発明は、生きているオブジェクトのグループを、ずっと迅速に処理することのできる集合（０のマーク・ビットのしきい値を超える原因となるほどには大きくない、隣接した生きているオブジェクト）として扱うことによって、ほとんどの生きているオブジェトを無視する。
【００３４】
次にステップ３０４に進み、スイープ機能がビットの検査を活動化し開始する。ステップ３０６に進み、スイープ機能がしきい値を超える空きスペース領域を表すシーケンスを求めてマーク・ビット配列を走査する。すべての生きているオブジェクトは１でマークされ、死んでいるオブジェクトは０でマークされており、これらの値はそのマーク・ビット配列に格納されている。スイープ機能は、マーク・ビット配列を走査するが、プロセッサが、全て０のバイトおよびワード用の効果的なテストを提供するので、ビット・グループを合わせて高速で検査することが可能である。生きているオブジェクトの列は、おそらく関心のない空きスペース領域と混在しているが、スキップすることができる。空きスペースの大きな列（マーク・ビット配列の０に対応する）も、高速で走査することができる。
【００３５】
ステップ３０８に移り、関心のあるビット・シーケンス（すなわち、しきい値と一致するかそれより多い０の列）があるかどうか判定する。関心のあるシーケンスがない場合には、次いでステップ３１０に移り、スイープ機能が終了し、本発明のマーク・スイープ・ガーベッジ収集ルーチンが次の手順に備えてリセットする。関心のあるシーケンスがある場合には、ステップ３１２に移り、関心のあるシーケンスが充分大きいかどうか判定する。（すなわち、関心のあるシーケンスが４ビットであるのに対して、「充分大きい」は３ビットを含む。）そうでない場合には、ステップ３０６に移り、ステップ３０６および３０８を繰り返す。このシーケンスが充分大きい場合には、次いで、代わりにステップ３１４に移り、この０マーク・ビットによって表される残りの空きスペース領域を割り振り解除する。次いでステップ３０６に戻り、続行する。
【００３６】
関心のあるシーケンスおよび充分大きいシーケンスは、全て合体用と見なすことができる。充分大きいシーケンス（しきい値数より小さい特定数のビット）は、関心のあるシーケンスとして検出された場合には、合体させることができる。充分大きいシーケンスは常に、関心のあるシーケンス内に含まれる。充分大きいシーケンスを含めることによって、処理は、そうしない場合にスキップされる可能性のあるスペースを獲得することができる。処理が既に関心のあるシーケンスを検出し、検査し、このシーケンスがしきい値より小さい特定数のビットを有するので、このシーケンスは、しきい値の要件を満たさないが、充分大きく合体用に含まれる。
【００３７】
図４を参照すると、本発明の好ましい実施形態によるマーク・スイープ・ガーベッジ収集のスイープ段階中に、マーク・ビット配列を検査する処理の疑似コードが示してある。この疑似コードには、対応する処理の実行に関するコメントを（括弧内に太字で）付けてある。ここに示すとおり、処理は連続する０のバイトおよびワードを探す命令を利用する。
【００３８】
関心のあるシーケンスが充分長い場合には、シーケンス・ヒント（ｓｅｑｕｅｎｃｅ  ｈｉｎｔ）（迅速に検査することができ、関心のあるシーケンス内に必ず存在するビット・シーケンス、すなわち、８ビットの境界上にある８ビットの集合）を利用して、関心のあるシーケンスの発見を高速化することができる。そのシーケンスが充分長い場合には、このシーケンスは必ず、ある最低数の０のマーク・ビット（この例では、バイト境界上で一列に並ぶ全て０の８ビット）を含む。関心のあるシーケンスは、全てこの最低数を必要とするので、最低数の０のビットの集まり全体を探すことにより、関心のあるシーケンスを発見する処理を高速化することができる。
【００３９】
０のマーク・ビットのシーケンスを探索する間に、ワード全体のビットを処理する機械命令を利用することによって検索を最適化することが可能である。メモリ領域内の各ワード境界で、関連するマーク・ビット配列内の連続する０のワードを探す。識別された場合には次のワードが検査されるが、このワードの内容全てが０ではない場合には、このワードは、連続する０を求めてバイトごとに検査される。連続する０の各バイトが識別されると、次のバイトが検査される。内容全てが０ではないバイトが識別されると、識別された連続する０の列が検査され、それがしきい値を超えるかどうかが判定される。
【００４０】
識別された連続する０の列がしきい値を超える場合には、この列の先頭のオブジェクトの長さが検査され、この列のサイズと比較される。残りのスペースが充分大きい場合には、この空きスペースが割り振り解除され、メモリ・ヒープに戻される。しかし、そうでない場合には、この空きスペースは無視され、次のワードが検査される。
【００４１】
スイープ機能がヒープ境界を超えることを回避するために、「見張り」（ｓｅｎｔｉｎｅｌ）（ヒープ上の生きている最後のオブジェクトまたは空きスペースを終了させる０でないビットを含むワード）が設定される。処理は、第１ワード以降の各ワード境界に出会うと、見張りのパターンをチェックする。それが検出された場合には、メモリ・ヒープの最後である。そうでない場合には、全て０を求めて次のワードが最初に検査され、ワード全体の内容が全て０でない場合には、次いでバイトごとに検査される。
【００４２】
本発明を完全に機能的なデバイスの文脈の中で述べたが、本発明の機構および／またはその態様が、様々な形態の命令からなるコンピュータ使用可能媒体の形で配布できること、および本発明が、実際に配布するために使用する信号保持媒体の個々のタイプに関係なく等しく適用できることを、当業者なら理解できることに留意されたい。コンピュータ使用可能媒体の例には、読取り専用メモリ（ＲＯＭ）や消去可能電気的プログラム可能読取り専用メモリ（ＥＥＰＲＯＭ）などの不揮発性ハード・コード・タイプ媒体、フロッピー・ディスク、ハード・ディスク・ドライブおよびＣＤ−ＲＯＭなどの記録可能タイプ媒体、ならびにデジタル−アナログ通信リンクなどの伝送タイプ媒体が含まれる。
【００４３】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４４】
（１）個々の空きスペース領域を検出し合体させる方法であって、
関心のあるシーケンスを求めてマーク・ビット配列を検査するステップであって、前記関心のあるシーケンスがそれぞれ、第１論理状態を有するしきい値数の順次ビットを含むステップと、
メモリ・スイープ中に、関心のあるシーケンスの一部を形成しないマーク・ビット配列内のビットに対応するメモリ領域を無視するステップとを含む方法。
（２）前記メモリ・スイープ中に、前記マーク・ビット配列内のそれぞれの関心のあるシーケンスに対応する各メモリ領域を検査するステップをさらに含む、上記（１）に記載の方法。
（３）生きているオブジェクトを含まないメモリ領域を識別するのに応答して、前記メモリ領域を割振り解除するステップをさらに含む、上記（２）に記載の方法。
（４）メモリ・スイープの速度と、メモリ・スイープ中にあらゆる生きていないオブジェクトを発見することを均衡させるように、順次ビット数の前記しきい値を設定するステップをさらに含む、上記（１）に記載の方法。
（５）前記マーク・ビット配列内の各ワード境界で、１ワードの連続する０を求めて、ワード長分の隣接するビットを検査するステップをさらに含む、上記（１）に記載の方法。
（６）１ワードの連続する０を求めて、ワード長分の隣接するビットを検査する前記ステップが、
前記ワード長分の隣接するビットの内容全てが０ではない場合に、連続する０を求めて前記ワード長分の隣接するビットをバイトごとに検査するステップをさらに含む、上記（５）に記載の方法。
（７）個々の空きスペース領域を検出し合体させる方法であって、
マーク・ビット配列内で各シーケンス・ヒントを識別するステップであって、前記シーケンス・ヒントが、バイト境界上で終了する、しきい値数の連続する０ビットを有するビット・シーケンスであるステップと、
識別されたシーケンス・ヒントに対応する各メモリ領域を検査するステップと、
識別されたシーケンス・ヒットに対応するメモリ領域が生活オブジェクトを含まないと判定するのに応答して、前記メモリ領域を割振り解除するステップとを含む方法。
（８）前記シーケンス・ヒントをそれぞれ利用して前記マーク・ビット配列内のそれぞれの関心のあるシーケンスを識別するステップであって、関心のあるシーケンスが所定のサイズの連続する０のビットの列を含むステップをさらに含む、上記（７）に記載の方法。
（９）個々の空きスペース領域を検出し合体させる方法であって、
関心のあるシーケンスを求めてマーク・ビット配列を検査するステップであって、前記関心のあるシーケンスが、第１論理状態を有する第１しきい値数の順次ビットを含むステップと、
前記マーク・ビット配列内の関心のあるシーケンスに対応する各メモリ領域を検査するステップと、
前記第１しきい値未満で第２しきい値以上のマーク・ビットの列に対応する、いくつかの使用されていない隣接するメモリ・セグメントを含むメモリ領域を識別するのに応答して、識別されたメモリ領域を割振り解除するステップを含む方法。
（１０）個々の空きスペース領域を検出し合体させるシステムであって、
データ処理システム内のメモリと、
データ記憶用に割振ることのできる前記メモリ内の各メモリ・セグメントに対するマーク・ビットを含む、前記メモリの一部分内のマーク・ビット配列と、
前記データ処理システム内で動作するガーベッジ収集処理であって、
第１論理状態を有するしきい値数の順次ビットを含む関心のあるシーケンスを求めてマーク・ビット配列を検査し、
メモリ・スイープ中に、関心のあるシーケンスの一部を形成しないマーク・ビット配列内のビットに対応するメモリ領域を無視するガーベッジ収集処理とを含むシステム。
（１１）前記ガーベッジ収集処理が、前記メモリ・スイープ中に前記マークビット配列内の関心のあるシーケンスに対応する各メモリ領域を検査する、上記（１０）に記載のシステム。
（１２）前記ガーベッジ収集処理が、生きているオブジェクトを含まないメモリ領域を識別するのに応答して、前記メモリ領域を割振り解除する、上記（１１）に記載のシステム。
（１３）メモリ・スイープの速度と、メモリ・スイープ中にあらゆる生きていないオブジェクトを発見することを均衡させるように、順次ビット数の前記しきい値が選択される、上記（１０）に記載のシステム。
（１４）前記ガーベッジ収集処理が、前記メモリ・スイープ中に、前記マーク・ビット配列内の各ワード境界で１ワードの連続する０を求めてワード長分の隣接するビットを検査する、上記（１０）に記載のシステム。
（１５）前記ワード長分の隣接するビットの内容全てが０ではない場合に、前記カーベージ・収集処理が、連続する０を求めて前記ワード長分の隣接するビットをバイトごとに検査する、上記（１４）に記載のシステム。
（１６）コンピュータ使用可能媒体内の個々の空きスペース領域を検出し合体させるコンピュータ・プログラム製品であって、
関心のあるシーケンスを求めてマーク・ビット配列を検査する命令であって、前記関心のあるシーケンスがそれぞれ、第１論理状態を有するしきい値数の順次ビットを含む命令と、
メモリ・スイープ中に、関心のあるシーケンスの一部を形成しないマーク・ビット配列内のビットに対応するメモリ領域を無視する命令とを含むコンピュータ・プログラム製品。
（１７）前記メモリ・スイープ中に、前記マーク・ビット配列内のそれぞれの関心のあるシーケンスに対応する各メモリ領域を検査する命令をさらに含む、上記（１６）に記載のコンピュータ・プログラム製品。
（１８）生きているオブジェクトを含まないメモリ領域を識別するのに応答して、メモリ領域を割振り解除する命令をさらに含む、上記（１７）に記載のコンピュータ・プログラム製品。
（１９）メモリ・スイープの速度と、メモリ・スイープ中にあらゆる生きていないオブジェクトを発見することを均衡させるように、順次ビット数の前記しきい値を設定する命令をさらに含む、上記（１６）に記載のコンピュータ・プログラム製品。
（２０）前記マーク・ビット配列内の各ワード境界で、１ワードの連続する０を求めて、ワード長分の隣接するビットを検査する命令をさらに含む、上記（１６）に記載のコンピュータ・プログラム製品。
（２１）１ワードの連続する０を求めて、ワード長分の隣接するビットを検査する前記命令が、
前記ワード長分の隣接するビットの内容全てが０ではない場合に、連続する０を求めて前記ワード長分の隣接するビットをバイトごとに検査する命令をさらに含む、上記（２０）に記載のコンピュータ・プログラム製品。
【図面の簡単な説明】
【図１】本発明の好ましい実施形態がその中で実施されるデータ処理システムの図である。
【図２】本発明の好ましい実施形態によるマーク・スイープ・ガーベッジ収集で用いられる、関連するメモリ・セグメントを有するマーク・ビット配列データ構造のブロック図である。
【図３】本発明の好ましい実施形態によるマーク・スイープ・ガーベッジ収集のスイープ段階中に、マーク・ビット配列を検査する処理の高レベルの流れ図である。
【図４】本発明の好ましい実施形態によるマーク・スイープ・ガーベッジ収集のスイープ段階中に、マーク・ビット配列を検査する処理の疑似コードである。
【図５】メモリの空き領域を検出して合体させるガーベッジ収集の、周知のマーク・スイープ法の高レベル流れ図である。
【図６】メモリの空き領域を検出して合体させるガーベッジ収集の、周知のマーク・スイープ法の高レベル流れ図である。
【符号の説明】
１０２  ＣＰＵ
１０４  ＲＯＭ
１０６  ＲＡＭ
１０８  入出力アダプタ
１１２  ユーザ・インタフェース・アダプタ
１２２  通信アダプタ
１２４  ディスプレイ・アダプタ
１２８  オペレーティング・システム
１３０  アプリケーション
【図１】
0003560535.tif 000003
【図２】
0003560535.tif 000004
【図３】
0003560535.tif 000005
【図４】
0003560535.tif 000006
【図５】
0003560535.tif 000007
【図６】
0003560535.tif 000008