トップ :: G 物理学 :: G06 計算;計数




【発明の名称】 圧縮メモリ・システムの再利用スペース予約
【発明者】 【氏名】ピーター・エイ・フラナゼック

【氏名】ダン・イー・ポフ
【要約】 【課題】圧縮された形で維持されページとして編成された内容を保存するフリー・スペースを持つ物理メモリ管理システムを提供する。

【解決手段】メモリ・ストレージ・デバイスとの間の圧縮された内容の入出力操作のパフォーマンスを管理する制御装置を含む。出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含む。制御装置はページアウト操作が実行できるように、しきい値量を超える量まで回復するためすぐ使用できるフリー・ストレージ・スペースを維持する。ページアウト操作のため物理メモリからすぐクリアできるページの位置を含む新規のデータ構造体が提供される。制御装置はフラッシュ操作を実行するためデータ構造体にアクセスし、リストで削除可能として識別された１つ以上のページを便宜上削除する。このデータ構造体とフラッシュ操作により、フリー・ストレージ・スペースを回復するしきい値量を大幅に縮小する。
【特許請求の範囲】
【請求項１】圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理するシステムであって、該圧縮メモリの内容は、該メモリ・ストレージ・デバイスのページとして編成され、前記メモリ・ストレージ・デバイスとの間の圧縮内容の入出力操作のパフォーマンスを管理し、該出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含み、後続のページアウト操作を実行できるように、回復にすぐ使用できるフリー・ストレージ・スペース量をしきい値量を上回る値に維持する、制御装置と、後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体とを含み、前記制御装置はフラッシュ操作を実行するため、該データ構造体にアクセスし、リストで識別された１つ以上のページを便宜上削除し、よって、前記データ構造体により可能になった前記便宜上の削除を可能にすることによって、フリー・ストレージ・スペースを回復する前記しきい値量が少なくなる、システム。
【請求項２】通常、ページアウト操作では、プロセッサ・デバイスにより発行された仮想メモリ・アドレスをフリー・スペースを回復するため削除される前記物理メモリのページ位置にマップするページ・テーブルをオペレーティング・システム・スレッドにより走査する必要があり、前記システムは、前記フラッシュ操作のため該ページ・テーブル走査を必要としない、請求項１記載のシステム。
【請求項３】前記システムは、回復のためのフリー・スペースの不足を確認する機構を含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、該機構が割込みを生成し、オペレーティング・システムから前記データへのアクセスを可能にし、プロセッサ・デバイスにより実行されるコマンド実行操作の一時的保留を開始する、請求項１記載のシステム。
【請求項４】前記データ構造体はテーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占められる関連物理スペースとを含み、前記データ構造体は前記リストの全てのアイテムにより占められる総物理スペースを維持する、請求項３記載のシステム。
【請求項５】前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたは前記物理メモリ・ストレージに追加する前記ページの可用性を示すビットを含み、前記制御装置は、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定する、請求項４記載のシステム。
【請求項６】前記制御装置は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するデバイスを含み、該調整は、前記データ構造体にテーブル・エントリを追加するかまたはそこから削除するための前記データ構造体へのアクセスを含み、入力された各ページ用に占有された物理スペースが前記総物理スペースに追加され、削除された各ページ用に占有された物理スペースが前記総物理スペースから削除される、請求項４記載のシステム。
【請求項７】１つのオペレーティング・システム・スレッドがシステムの通常動作で前記データ構造体にアクセスできるようにするロック機構を含み、前記割込み処理機構が前記データ構造体への該オペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にする、請求項６記載のシステム。
【請求項８】前記データ構造体に入力された新しいページを遷移中のページとして識別する機構を含み、前記制御装置が、該新しいページを便宜上削除しないように、遷移中の新しいページが識別されていないか確認する、請求項７記載のシステム。
【請求項９】フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持し、便宜上の削除操作時に消去された最後のページへの位置への第２ポインタを維持するトラッキング・ポインタ機構を含む、請求項６記載のシステム。
【請求項１０】前記フラッシュ操作の後、前記データ構造体リストのエントリを削除するスイープ機構を含み、削除される前記エントリは、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを含む、請求項９記載のシステム。
【請求項１１】圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理する方法であって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法は、ａ）オペレーティング・システムによるページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、を含む、方法。
【請求項１２】ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることの確認に応答して、割込みを生成してオペレーティング・システムから前記データへのアクセスを可能にするステップと、プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、を含む、請求項１１記載の方法。
【請求項１３】前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全アイテムにより占有される総物理スペースを維持するステップを含む、請求項１２記載の方法。
【請求項１４】前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、請求項１３記載の方法。
【請求項１５】前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、ii）入力された各ページについて占有された物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、を含む、請求項１４記載の方法。
【請求項１６】システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして、前記フラッシュ操作を可能にするステップを含む、請求項１５記載の方法。
【請求項１７】前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、を含む、請求項１６記載の方法。
【請求項１８】フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、を含む、請求項１５記載の方法。
【請求項１９】前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、請求項１８記載の方法。
【請求項２０】圧縮された形で維持される内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理する方法のステップを実行するため、機械で実行可能な命令のプログラムを明確に具体化した機械可読プログラム・ストレージ・デバイスであって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法のステップは、ａ）オペレーティング・システムによるメモリのページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、を含む、機械可読プログラム・ストレージ・デバイス。
【請求項２１】ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、割込みを生成してオペレーティング・システムから前記データにアクセスできるようにするステップと、プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、を含む、請求項２０記載の機械可読プログラム・ストレージ・デバイス。
【請求項２２】前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全てのアイテムにより占有される総物理スペースを維持するステップを含む、請求項２１記載の機械可読プログラム・ストレージ・デバイス。
【請求項２３】前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、請求項２２記載の機械可読プログラム・ストレージ・デバイス。
【請求項２４】前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、ii）入力された各ページについて占有される物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、を含む、請求項２３記載の機械可読プログラム・ストレージ・デバイス。
【請求項２５】システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にするステップを含む、請求項２４記載の機械可読プログラム・ストレージ・デバイス。
【請求項２６】前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、を含む、請求項２５記載の機械可読プログラム・ストレージ・デバイス。
【請求項２７】フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、を含む、請求項２４記載の機械可読プログラム・ストレージ・デバイス。
【請求項２８】前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、請求項２７記載の機械可読プログラム・ストレージ・デバイス。
【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、一般にはコンピュータのオペレーティング・システムに関し、特に圧縮メイン・メモリを組み込んだシステムで予約する必要のある物理フリー・スペースを少なくするシステム及び方法に関する。
【０００２】
【従来の技術】図１は、圧縮メモリ管理機能を採用したコンピュータ・システム１００の一例である。コンピュータ・システム１００は、例えば１つ以上のプロセッサ１０２、オペレーティング・システム１２５、キャッシュ１０４、圧縮コントローラ１０６、圧縮メイン・メモリ１０８、及び１つ以上の入出力（Ｉ／Ｏ）デバイス１１０を含む。以下、それぞれについて説明する。
【０００３】周知の通り、プロセッサ１０２はコンピュータ・システム１００の制御センターである。プロセッサ１０２は少なくとも１つのオペレーティング・システム（ＯＳ）１２５を実行する。ＯＳはプログラムの実行とデータの処理を制御する。ＯＳには、ＩＢＭから商標ＡＩＸとして販売されているようなＯＳや、マイクロソフト社からWindows（Ｒ）として販売されているＯＳ等がある。後述するように、オペレーティング・システム１２５は、コンピュータ・システム１００の１つのコンポーネントであり、本発明の機能を組み込んで使用することができる。
【０００４】プロセッサ１０２と圧縮コントローラ１０６（後述）にはキャッシュ・メモリ１０４が接続される。キャッシュ・メモリ１０４は、Ｉ／Ｏデバイス１１０や圧縮メイン・メモリ１０８から圧縮コントローラ１０６により取得されたデータのための短期、高速、高容量のコンピュータ・メモリである。
【０００５】キャッシュ１０４と圧縮メモリ１０８には圧縮コントローラ１０６が接続される。コントローラ１０６は、後述する通り、例えばＩ／Ｏデバイス１１０とキャッシュ１０４間の情報の転送や圧縮メイン・メモリ１０８とキャッシュ１０４間の情報転送を管理する。圧縮コントローラの機能は、データの圧縮／圧縮解除、得られた圧縮ラインの固定サイズ・ブロックへの保存を含む。これは好適には、オペレーティング・システムから見て実ページ・アドレスからメモリ１０８の固定サイズ・ブロックのアドレスへのマッピングを含む。
【０００６】圧縮コントローラ１０６に接続された圧縮メイン・メモリ１０８は、例えばキャッシュ・ライン単位で圧縮されたデータを格納する。実施例では各ページが４つのキャッシュ・ラインを含む。キャッシュ・ラインは、キャッシュ１０４に挿入されたとき圧縮解除され、キャッシュ１０４からキャストアウトされたとき圧縮される。Ｉ／Ｏデバイス１１０からのページもメイン・メモリ１０８に挿入されたとき（キャッシュ・ライン単位で）圧縮される。簡素化のため１つのキャッシュしか示していないが、実際のシステムにはキャッシュの階層を加えてもよい。
【０００７】周知の通り、メモリのページに関する情報は、メイン・メモリまたはキャッシュの１つ以上のページ・テーブルに保存することができ、ＯＳ１２５により用いられる。ページ・テーブルの１例（１４０）を図２に示す。ページ・テーブル１４０は複数のページ・テーブル・エントリ１４２を含み、各エントリは、例えば所与のページの仮想アドレス１４４、そのページの仮想アドレスに対応した実アドレス１４６、及びページの管理情報１４８のセットを含む。管理情報１４８は、例えばページが参照されたかどうかを示す使用ビット・フィールドと、許可アクセス・タイプを示す読取り／書込みアクセス・フィールドまたは読取り専用アクセス・フィールドである。
【０００８】ページの実アドレスは、キャッシュ・ライン毎に、メイン・メモリ１０８からページが要求されたとき物理アドレスのセット（ストレージ・ブロックの識別子等）にマップされる。これは、実施例では、図３に示すテーブル１５０及び１６０を使用して実行される。これらのテーブルは圧縮コントローラ１０６に保存することができる。テーブル１５０は、例えばページの実ページ・アドレスと呼ばれるアドレスであるPage（ｉ）、及びページのライン毎のメモリ・ブロック・リストを含む。例えばページは、サイズが４Ｋバイトのときは４つのキャッシュ・ラインを含む。各キャッシュ・ラインのサイズは１Ｋバイトである。
【０００９】圧縮キャッシュ・ラインは、例えば２５６バイトの固定サイズ・ブロックに保存される。テーブル１６０は、例えばPage（ｉ）の特定のラインを構成する圧縮ブロックを含む。例えばPage（ｉ）のライン１は、それぞれ２５６バイトの３つの圧縮ブロックを含む。この例では各ページが最大４つのキャッシュ・ラインを含み、各キャッシュ・ラインは最大４つの圧縮メモリ・ブロックを含むので、各ページは最大１６のメモリ・ブロックを占めることができる。
【００１０】再び図１に示したシステムを参照する。圧縮コントローラ１０６は、１つ以上の割込みレジスタ１２０とフリー・スペース・リスト１１２を含むことができる。フリー・スペース・リスト１１２の実施形態として、当業者には周知のリンク・リストが考えられる。圧縮コントローラ１０６は次のような様々な機能を実行する。
ａ）キャッシュ１０４からキャストアウトされたラインを圧縮し、結果をフリー・スペース・リスト１１２から引き出されたいくつかの固定サイズ・ブロックに保存する。
ｂ）キャッシュ・フェッチでラインを圧縮解除する。
ｃ）メモリからのラインの削除、変更されたラインの圧縮（によりスペースを少なくする）等の操作により空いたブロックをフリー・スペース・リスト１１２に追加する。
ｄ）ブロック数のカウントＦをフリー・スペース・リスト１１２に維持する。このカウントは好適には要求時にＯＳ１２５から使用できる。
ｅ）サイズＦの割込みレジスタ（１２０）として実装されるしきい値セットを維持する。しきい値を超える結果になるＦの変更により、プロセッサ割込みが生じる。好適には、各しきい値をソフトウェアにより動的に設定することができ、少なくとも測定量に関係するしきい値はコントローラ１０６の割込みレジスタ１２０に保存される。
【００１１】図１には他に、フリー・スペース・リスト１１２に適切な数のブロックを維持するフリー・スペース・マネージャ１３０が示してある。ブロックが少なすぎるとシステムが異常終了するか、アプリケーションの実行が保留されてページアウトも保留される。ブロックが多すぎるとストレージが無駄になり、ページ・フォールトが過剰に発生する。フリー・スペース・マネージャ１３０はまた、割込みレジスタ１２０を、割込みが生成される１つ以上のしきい値（Ｔ０．．．ＴＮ）で設定する。定期的に測定される値とは異なる実際の測定値に関係するしきい値は、１つ以上の割込みレジスタ１２０に保存される。しきい値設定ポリシと制御プロセスの例については、米国特許出願第 （ＹＯ９９７３３８）号、COMPRESSION STORE FREE-SPACE MANAGEMENTを参照されたい。図１には、オペレーティング・システムにより要求されたときすぐ使用できるページ・フレームを表すページを持つ再利用リスト１３４も示してある。再利用リストの全ページの有効コピーがディスク上に存在するためにこれが可能である。
【００１２】ページアウトを実行する際にはスペースを追加する必要があるが、これは、十分な量の物理フリー・スペースを維持することで解決することができる。ただし、これは物理ストレージをかなり無駄にすることにもなる。必要なページアウトは、最悪の場合の拡張も考慮する必要のあるページ・テーブル等の大きいオブジェクトの走査を伴うことがあるからである。これは、使用されているが使用可能な状態にあるメモリとみなされる。
【００１３】例えば、図１に示すように、共有キャッシュ・メモリを実装したコンピュータ・システム１００に関して、コントローラ１０６は、コンピュータのオペレーティング・システムから使用できるフリー・スペースの量を表す値を持つカウント"Ｆ"を維持するように構成される。一般にＦは、スペース量がＦ*と指定されるページアウトを実行するに十分でなければならない。Ｆがしきい値Ｔ１より小さくなると（Ｔ１＞＝Ｆ*）、メモリ・コントローラはプロセッサに割込みを発行する。この割込みにより通常の処理が停止し、第２しきい値Ｔ２より上で使用できるフリー・スペースを増やすため十分なページ数を削除するか、またはディスクにページアウトすることによってフリー・スペースの回復が開始される。一般にＴ１により表される予約域はかなり大きく、かなりの量の未使用スペースがあり、従って無駄になっているスペースがあることを示す。
【００１４】ディスクへのページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することが強く望まれる。
【００１５】割込みハンドラにより削除できるが、システムにより参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１６】ディスクへのページアウトを実行し、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしに、ページアウトを実行できるようにするため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１７】
【発明が解決しようとする課題】本発明の目的は、予約スペースが足りないときにページアウトを実行できるように予約しておく必要のある物理スペースを少なくすることである。
【００１８】本発明の他の目的は、圧縮メモリ・システムにおいて、圧縮／圧縮解除の過負荷から高速に回復する、つまりスペースを高速にクリアし、ページを回復する機構を提供することである。
【００１９】本発明の他の目的は、圧縮メモリ・システムにおいて、割込みハンドラにより削除でき、システムによって参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウト操作を実行するのに必要な予約スペースを少なくするシステム及び方法を提供することである。
【００２０】本発明の他の目的は、圧縮メモリ・システムにおいて、ページアウト操作を実行するのに必要な予約スペースを少なくし、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしにページアウトを実行できるようにするシステム及び方法を提供することである。
【００２１】
【課題を解決するための手段】本発明に従い、圧縮された形で維持され、ページとして編成された内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理するシステム及び方法が提供される。システムは、圧縮された内容のメモリ・ストレージ・デバイスとの間の入出力操作の実行を管理する制御装置を含む。出力操作は、フリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含む。制御装置は、後続のページアウト操作が実行できるように、しきい値量を超えるまで回復するためすぐ使用できるフリー・ストレージ・スペースを維持する。後続のページアウト操作のため物理メモリからすぐクリアできるページの場所を含む新規のデータ構造体が提供される。制御装置は、データ構造体にアクセスし、このリストで削除可能と判定された１つ以上のページを便宜上削除することによってフラッシュ操作を実行する。このデータ構造体とフラッシュ操作により、フリー・ストレージ・スペースを回復するためのしきい値量を大幅に縮小することができる。
【００２２】新規データ構造体が、すぐクリアできるページのリストを含む特別なソフトウェア構造体であることは好都合であり、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。
【００２３】新規データ構造体の構造は、更新目的の通常のアクセス（スペース不足の問題がないとき）では、オペレーティング・システムをロックする必要があるが、（スペース不足の問題があるとき）ページのリストを走査することができ、最初にロックを取得することなく物理ストレージからページを消去することができる構造である。もう１つの要件は、割込み処理中に、またはサービス・プロセッサを介して、仮想メモリ・リスト管理とは独立して構造自体にアクセスできることである。
【００２４】更に、新規データ構造体の構造は、通常動作へ復帰できるだけのストレージを表すのに十分なページのリストを保持することが保証された状態に保たれる構造である。従って、メモリが不足している場合にリストからページが消去されるとき、通常動作を再開する前のオペレーティング・システムの目的は、次の回復のため十分なページをこのリストに追加することである。
【００２５】
【発明の実施の形態】本発明に従い、特別なソフトウェア構造体（ここでは"出力リスト"と称する）が提供され、図１のオペレーティング・システム１２５によって維持される。構造体は、すぐクリアできるページのリストを含むので、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。出力リスト構造の要件は、仮想メモリ・リスト管理から独立して、割込み処理中に、またはサービス・プロセッサを介して構造それ自体にアクセスできることである。
【００２６】好適には、出力リスト構造自体が小さいメモリ・スペースを占め、よって大きい予約スペースの必要なしに走査し処理することができる。すなわち、出力リスト構造を与えることで、次の要件で前記のしきい値Ｔ１が大幅に縮小される。
【数１】Ｔ１＜Ｆ*−Ｆ０＋Ｆ１【００２７】ここでＦ０は、出力リスト上のページにより保持されるスペース、Ｆ１は、出力リストの走査と処理のため予約する必要のあるスペース、Ｆ*は、ページアウトの実行を可能にするため必要な所定メモリ・スペースである。
【００２８】図４は、好適には仮想アドレスが連続したＮ個のページのセットを持つハッシュ・テーブル１８０を含む出力リスト構造（１８０）の概念を示す。図４に示すように、出力リスト１８０上のページは、ハッシュ・テーブルのエントリ１８５として表され、各エントリ１８５は位置を含む。通常のハッシュ・リストに見られるように、所与のページのエントリは、そのアドレスのハッシュによりハッシュ・テーブルのエントリ・ポイントを取得することによって見つけることができる。衝突の場合（異なるページがこの位置に入力された場合）、Ｒを法とする昇順アドレスの順序で所望のページ（またはページのスペース）が見つかるまでアイテムが調べられる。Ｒはリスト上の位置の数である。出力リストにページが存在することは、オペレーティング・システムのページ・テーブルにあるそのエントリで示される。
【００２９】図５は、フラッシュ操作でページの存在を示す"存在"ビット・フラグを格納するフィールド１９０（後述）、現在のページを示すページＩＤフィールド１９５、及びページが占める物理スペースＳ（ｉ）、つまり出力リスト・スペースを示すフィールド１９９を含むハッシュ・テーブル１８０のエントリ１８５を示す。
【００３０】図６乃至図８に関して詳述するが、好適には、出力リスト上で行える操作が３つある。１）出力リスト上でのページの通常の追加と削除のＮＯＲＭＡＬ。出力リストにページが入力されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースに追加される。逆に、出力リストからページが削除されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースから引かれる。２）割込みハンドラによる出力リストからのページの削除であるＦＬＵＳＨ、及び３）通常の操作が再開される前に、ページ・テーブルが更新され、ＦＬＵＳＨ操作により行われたページの削除が反映されるＳＷＥＥＰである。図４に戻る。システムの通常動作時、ハッシュ・テーブル１８０での位置を示すポインタＰが維持される。例えばポインタ・エントリＰ１は、フラッシュ操作で消去された最も新しいページ１８１を示す。ポインタＰ２として示される第２ポインタ・エントリは、最後に消去されたページ１８４を示す。
【００３１】ＮＯＲＭＡＬ動作ではハッシュ・テーブル１８０にアイテムを追加し、またはそこからアイテムを削除することができる。例えばテーブルのページ１８５を参照し、よってワーキング・セットに移すことができる。ページ"Ｖｉ"が削除されると、量Ｆ０は、Ｓ（ｉ）により示される占有物理スペースの量だけ少なくされる。Ｆ０が少なすぎる、つまりしきい値Ｔ１を下回る場合、リストにページが追加され、Ｆ０がＦ０＞Ｔ１になるまで調整される。
【００３２】出力リストのデータ構造体は、（スペース不足が問題ではないときの）更新を目的にした通常のアクセスでは、オペレーティング・システムのロックを取得する必要がある。すなわち、２つ以上のＯＳスレッドが出力リストを同時に変更しようとするときの不一致を避けるため、通常のスレッド１つだけがアクティブになることを許可され、ページの入力または削除毎にロックが取得される。これは、ハッシュ・テーブルにロックを保持することをこのスレッドに要求することによって制御される。ただし、好適な実施例では、（スペース不足が問題になっているとき）ページのリストを走査し、ＦＬＵＳＨ操作で、最初にロックを取得することなしに物理ストレージからページを消去することができる。すなわち、入力が完了する前にフラッシュ操作によりスレッドに割込みをかけることができる。好適には、この不一致を避けるため、ページを"Ｖｉ"に入力する操作または"Ｖｉ"に入力されたページを削除する操作について、図６と合わせて説明する。"Ｖｉ"は、一番後に追加されたかまたは削除され、Ｓ（ｉ）物理スペースを占めるページのＩＤを表す。
【００３３】図６は、ＮＯＲＭＡＬ出力リスト操作２００のフローチャートである。図６で、ハッシュ・テーブルにページを入力するかまたはそこから削除するため、ハッシュ・テーブルに対するロックを取得する第１ステップ２０２が必要である。次にステップ２０５で、このページが移行中であることを示すページＩＤ"Ｖ"がPageInTransシステム変数に割当てられる。この変数は、フラッシュ操作割込みの呼び出しにより追加／削除操作に割込みが入った場合にこのページが削除されるのを防ぐため与えられる。ページ２０８で、参照されたページを追加するか削除するかが確認される。ページが追加される場合、ステップ２１２に示すように、"存在ビット"の状態が確認される。存在ビットが設定されていない場合、ステップ２１５でハッシュ・テーブル・エントリが追加される。更にステップ２１６で、出力リストのページにより保持されたスペース、つまりＦ０の量を調整するため、比較交換操作により、ページが占める物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２１２で、ビットがすでに存在することが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。この時点で、ハッシュ・テーブルはロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加するかまたは削除する操作が繰り返される。
【００３４】図６のステップ２０８に戻る。参照されたページが削除される場合、ステップ２２２に示されるように、"存在ビット"の状態が確認される。存在ビットが設定されている場合、ハッシュ・テーブル・エントリが削除される（ステップ２２５）。プロセスはステップ２１６に進み、出力リストのページにより保持されたスペースの量、つまりＦ０を調整するため、比較交換操作により削除されたページが占めていた物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２２２で、ビットがもう存在しないことが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。ここでハッシュ・テーブルのロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加する操作または削除する操作が繰り返されることを理解されたい。
【００３５】比較交換は、図６のステップ２１６に示すようなアトミック・オペレーションであることを理解されたい。前述の通り、比較が否定的なら（フラッシュがあった場合）、プロセスは繰り返される。
【００３６】図７は、割込み時に発生するシステムＦＬＵＳＨ操作３００の詳細を示すフローチャートである。基本的には、通常動作時に割込みが受信されてフラッシュ操作が開始された場合、ｉ＝１、２、．．．のとき、位置（Ｐ１＋ｉ） ｍｏｄＲにあるページは、Ｖを除いて消去され、それらの存在ビットがステップ１５７で０に設定される。また詳しく後述するが、量Ｆ０が調整される。これはＦ０が量"デルタ"だけ小さくなるまで続けられる。デルタは、オペレーティング・システム（ＯＳ）を再起動するため十分と判断されるフリー・スペースの量である。最後に消去されるページは位置Ｐ２である。
【００３７】図７の最初のステップ３０３に示すように、次のエントリが選択され、ステップ３０６で、PageIDがPageInTrans（遷移中のページ）に等しくないか確認される。PageIDがPageInTrans変数に等しくない場合、ステップ３０８でハッシュ・エントリの"存在ビット"が使用できないものとして指示され、ステップ３１０でページが０にされる。次にステップ３１３で、出力リストのページにより保持されたスペース量、つまりＦ０を調整するため、比較交換操作が実行され、ページが占めた物理スペース量Ｓ（ｉ）だけＦ０が調整される。ステップ３１５に進み、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいか確認される。ステップ３１５で、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいことが確認された場合、プロセスは終了し、スイープ操作に進む。ステップ３１５で、フラッシュされたスペースが必要なＦ*量に等しくないかまたはより大きくないことが確認された場合、プロセスはステップ３０３に戻り、フラッシュ操作のためハッシュ・テーブルから次のエントリが選択される。ステップ３１５の条件が真になるまでプロセス・ステップ３０３乃至３１５が繰り返される。
【００３８】好適な実施例では、オペレーティング・システムが"ページ・フレーム・データベース"を維持する。このデータベースはメモリに保持されたページの状態を記述する。本発明に従って出力リストに保持されたページに対応するビットが、ページ・フレーム・データベースに設定される。これが参照される場合、一般には、ここで述べる操作により出力リストからこれを削除するのが望ましい。次に、出力リストのページにより保持されたスペース量がしきい値より少なくなった場合、このリストにページが追加される。図８は、ＦＬＵＳＨ操作の後、通常動作の再開前に発生するＳＷＥＥＰ操作４００を示す。この手順では、ページ・テーブルが更新され、ＦＬＵＳＨの結果としてのページの削除が反映される。特にＯＳはハッシュ・テーブルに対するロックを取得し、ポインタＰ１及びＰ２によりポイントされたページ位置間の全エントリをスイープし、存在ビットが０に設定されたエントリを消去し、そのページ・テーブルを調整するため、十分なエントリをテーブルに追加してスペース予約要件を満足する。これが完了すると、通常のシステム動作が再開される。具体的には、図８のステップ４０３に示すように、最初のステップはハッシュ・テーブルに対するロックを取得し、ポインタＰを最初のページＰ１、つまりフラッシュ操作時に消去された最も新しいページに等しく設定することである。次にステップ４０５で次のエントリが選択され、ステップ４０８で存在ビットが設定されているか確認される。選択されたページの存在ビットが設定されていない場合、つまり０に等しい場合、プロセスはステップ４１２に進み、ハッシュ・エントリとページ・フレーム・データベースのエントリが削除される。次にステップ４１５でページ・テーブル・エントリとフラッシュ・テーブルが無効にされる。ステップ４０８に戻り、存在ビットが設定されている場合、つまりフラッシュ操作が指示されている場合、プロセスはステップ４１８に進み、ポインタ値Ｐが増分され、ＰがＰ２、つまりＦＬＵＳＨ操作で最後に消去されたページより大きいか確認される。値Ｐが値Ｐ２よりまだ大きくない場合、プロセスはステップ４０５にループバックし、ハッシュ・テーブルの次のエントリが選択され、ステップ４０８乃至４１８が繰り返される。プロセス・ステップ４０５乃至４１８は、図８のステップ４１８で、ポインタＰがＰ２より大きいことが確認されるまで繰り返される。この条件が成立すると、プロセスはステップ４２０に進み、ハッシュ・テーブルのロックが解除され、再び新しいポインタ値ＰがＰ１に等しく設定される。
【００３９】まとめとして、本発明の構成に関して以下の事項を開示する。
【００４０】（１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理するシステムであって、該圧縮メモリの内容は、該メモリ・ストレージ・デバイスのページとして編成され、前記メモリ・ストレージ・デバイスとの間の圧縮内容の入出力操作のパフォーマンスを管理し、該出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含み、後続のページアウト操作を実行できるように、回復にすぐ使用できるフリー・ストレージ・スペース量をしきい値量を上回る値に維持する、制御装置と、後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体とを含み、前記制御装置はフラッシュ操作を実行するため、該データ構造体にアクセスし、該データ構造体リストで識別された１つ以上のページを便宜上削除し、よって、前記データ構造体により可能になった前記便宜上の削除を可能にすることによって、フリー・ストレージ・スペースを回復する前記しきい値量が少なくなる、システム。
（２）通常、ページアウト操作では、プロセッサ・デバイスにより発行された仮想メモリ・アドレスをフリー・スペースを回復するため削除される前記物理メモリのページ位置にマップするページ・テーブルをオペレーティング・システム・スレッドにより走査する必要があり、前記システムは、前記フラッシュ操作のため該ページ・テーブル走査を必要としない、前記（１）記載のシステム。
（３）前記システムは、回復のためのフリー・スペースの不足を確認する機構を含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、該機構が割込みを生成し、オペレーティング・システムから前記データへのアクセスを可能にし、プロセッサ・デバイスにより実行されるコマンド実行操作の一時的保留を開始する、前記（１）記載のシステム。
（４）前記データ構造体はテーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占められる関連物理スペースとを含み、前記データ構造体は前記リストの全てのアイテムにより占められる総物理スペースを維持する、前記（３）記載のシステム。
（５）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたは前記物理メモリ・ストレージに追加する前記ページの可用性を示すビットを含み、前記制御装置は、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定する、前記（４）記載のシステム。
（６）前記制御装置は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するデバイスを含み、該調整は、前記データ構造体にテーブル・エントリを追加するかまたはそこから削除するための前記データ構造体へのアクセスを含み、入力された各ページ用に占有された物理スペースが前記総物理スペースに追加され、削除された各ページ用に占有された物理スペースが前記総物理スペースから削除される、前記（４）記載のシステム。
（７）１つのオペレーティング・システム・スレッドがシステムの通常動作で前記データ構造体にアクセスできるようにするロック機構を含み、前記割込み処理機構が前記データ構造体への該オペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にする、前記（６）記載のシステム。
（８）前記データ構造体に入力された新しいページを遷移中のページとして識別する機構を含み、前記制御装置が、該新しいページを便宜上削除しないように、遷移中の新しいページが識別されていないか確認する、前記（７）記載のシステム。
（９）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持し、便宜上の削除操作時に消去された最後のページへの位置への第２ポインタを維持するトラッキング・ポインタ機構を含む、前記（６）記載のシステム。
（１０）前記フラッシュ操作の後、前記データ構造体リストのエントリを削除するスイープ機構を含み、削除される前記エントリは、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを含む、前記（９）記載のシステム。
（１１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理する方法であって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法は、ａ）オペレーティング・システムによるページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、を含む、方法。
（１２）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることの確認に応答して、割込みを生成してオペレーティング・システムから前記データへのアクセスを可能にするステップと、プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、を含む、前記（１１）記載の方法。
（１３）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全アイテムにより占有される総物理スペースを維持するステップを含む、前記（１２）記載の方法。
（１４）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、前記（１３）記載の方法。
（１５）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、ii）入力された各ページについて占有された物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、を含む、前記（１４）記載の方法。
（１６）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして、前記フラッシュ操作を可能にするステップを含む、前記（１５）記載の方法。
（１７）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、を含む、前記（１６）記載の方法。
（１８）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、を含む、前記（１５）記載の方法。
（１９）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（１８）記載の方法。
（２０）圧縮された形で維持される内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理する方法のステップを実行するため、機械で実行可能な命令のプログラムを明確に具体化した機械可読プログラム・ストレージ・デバイスであって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法のステップは、ａ）オペレーティング・システムによるメモリのページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、を含む、機械可読プログラム・ストレージ・デバイス。
（２１）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、割込みを生成してオペレーティング・システムから前記データにアクセスできるようにするステップと、プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、を含む、前記（２０）記載の機械可読プログラム・ストレージ・デバイス。
（２２）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、前記物理メモリの前記ページを見つけるページ識別子と、前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全てのアイテムにより占有される総物理スペースを維持するステップを含む、前記（２１）記載の機械可読プログラム・ストレージ・デバイス。
（２３）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、前記（２２）記載の機械可読プログラム・ストレージ・デバイス。
（２４）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、ii）入力された各ページについて占有される物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、を含む、前記（２３）記載の機械可読プログラム・ストレージ・デバイス。
（２５）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にするステップを含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２６）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、を含む、前記（２５）記載の機械可読プログラム・ストレージ・デバイス。
（２７）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、を含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２８）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（２７）記載の機械可読プログラム・ストレージ・デバイス。
【出願人】 【識別番号】３９０００９５３１
【氏名又は名称】インターナショナル・ビジネス・マシーンズ・コーポレーション
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＳＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【出願日】 平成１３年８月２４日（２００１．８．２４）
【代理人】 【識別番号】１０００８６２４３
【弁理士】
【氏名又は名称】坂口 博 （外２名）
【公開番号】 特開２００２−１３２５８２（Ｐ２００２−１３２５８２Ａ）
【公開日】 平成１４年５月１０日（２００２．５．１０）
【出願番号】 特願２００１−２５４０８８（Ｐ２００１−２５４０８８）