JP3701890B2 - 圧縮メモリ・システムの再利用スペース予約 - Google Patents
圧縮メモリ・システムの再利用スペース予約 Download PDFInfo
- Publication number
- JP3701890B2 JP3701890B2 JP2001254088A JP2001254088A JP3701890B2 JP 3701890 B2 JP3701890 B2 JP 3701890B2 JP 2001254088 A JP2001254088 A JP 2001254088A JP 2001254088 A JP2001254088 A JP 2001254088A JP 3701890 B2 JP3701890 B2 JP 3701890B2
- Authority
- JP
- Japan
- Prior art keywords
- page
- data structure
- memory
- space
- deleted
- 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.)
- Expired - Fee Related
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F12/00—Accessing, addressing or allocating within memory systems or architectures
-
- 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/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
- G06F12/023—Free address space management
-
- 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/12—Replacement control
-
- 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
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F2212/00—Indexing scheme relating to accessing, addressing or allocation within memory systems or architectures
- G06F2212/40—Specific encoding of data in memory or cache
- G06F2212/401—Compressed data
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)
- Memory System (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
- Record Information Processing For Printing (AREA)
Description
【０００１】
【発明の属する技術分野】
本発明は、一般にはコンピュータのオペレーティング・システムに関し、特に圧縮メイン・メモリを組み込んだシステムで予約する必要のある物理フリー・スペースを少なくするシステム及び方法に関する。
【０００２】
【従来の技術】
図１は、圧縮メモリ管理機能を採用したコンピュータ・システム１００の一例である。コンピュータ・システム１００は、例えば１つ以上のプロセッサ１０２、オペレーティング・システム１２５、キャッシュ１０４、圧縮コントローラ１０６、圧縮メイン・メモリ１０８、及び１つ以上の入出力（Ｉ／Ｏ）デバイス１１０を含む。以下、それぞれについて説明する。
【０００３】
周知の通り、プロセッサ１０２はコンピュータ・システム１００の制御センターである。プロセッサ１０２は少なくとも１つのオペレーティング・システム（ＯＳ）１２５を実行する。ＯＳはプログラムの実行とデータの処理を制御する。ＯＳには、ＩＢＭから商標ＡＩＸとして販売されているようなＯＳや、マイクロソフト社からWindows（Ｒ）として販売されているＯＳ等がある。後述するように、オペレーティング・システム１２５は、コンピュータ・システム１００の１つのコンポーネントであり、本発明の機能を組み込んで使用することができる。
【０００４】
プロセッサ１０２と圧縮コントローラ１０６（後述）にはキャッシュ・メモリ１０４が接続される。キャッシュ・メモリ１０４は、Ｉ／Ｏデバイス１１０や圧縮メイン・メモリ１０８から圧縮コントローラ１０６により取得されたデータのための短期、高速、高容量のコンピュータ・メモリである。
【０００５】
キャッシュ１０４と圧縮メモリ１０８には圧縮コントローラ１０６が接続される。コントローラ１０６は、後述する通り、例えばＩ／Ｏデバイス１１０とキャッシュ１０４間の情報の転送や圧縮メイン・メモリ１０８とキャッシュ１０４間の情報転送を管理する。圧縮コントローラの機能は、データの圧縮／圧縮解除、得られた圧縮ラインの固定サイズ・ブロックへの保存を含む。これは好適には、オペレーティング・システムから見て実ページ・アドレスからメモリ１０８の固定サイズ・ブロックのアドレスへのマッピングを含む。
【０００６】
圧縮コントローラ１０６に接続された圧縮メイン・メモリ１０８は、例えばキャッシュ・ライン単位で圧縮されたデータを格納する。実施例では各ページが４つのキャッシュ・ラインを含む。キャッシュ・ラインは、キャッシュ１０４に挿入されたとき圧縮解除され、キャッシュ１０４からキャストアウトされたとき圧縮される。Ｉ／Ｏデバイス１１０からのページもメイン・メモリ１０８に挿入されたとき（キャッシュ・ライン単位で）圧縮される。簡素化のため１つのキャッシュしか示していないが、実際のシステムにはキャッシュの階層を加えてもよい。
【０００７】
周知の通り、メモリのページに関する情報は、メイン・メモリまたはキャッシュの１つ以上のページ・テーブルに保存することができ、ＯＳ１２５により用いられる。ページ・テーブルの１例（１４０）を図２に示す。ページ・テーブル１４０は複数のページ・テーブル・エントリ１４２を含み、各エントリは、例えば所与のページの仮想アドレス１４４、そのページの仮想アドレスに対応した実アドレス１４６、及びページの管理情報１４８のセットを含む。管理情報１４８は、例えばページが参照されたかどうかを示す使用ビット・フィールドと、許可アクセス・タイプを示す読取り／書込みアクセス・フィールドまたは読取り専用アクセス・フィールドである。
【０００８】
ページの実アドレスは、キャッシュ・ライン毎に、メイン・メモリ１０８からページが要求されたとき物理アドレスのセット（ストレージ・ブロックの識別子等）にマップされる。これは、実施例では、図３に示すテーブル１５０及び１６０を使用して実行される。これらのテーブルは圧縮コントローラ１０６に保存することができる。テーブル１５０は、例えばページの実ページ・アドレスと呼ばれるアドレスであるPage（ｉ）、及びページのライン毎のメモリ・ブロック・リストを含む。例えばページは、サイズが４Ｋバイトのときは４つのキャッシュ・ラインを含む。各キャッシュ・ラインのサイズは１Ｋバイトである。
【０００９】
圧縮キャッシュ・ラインは、例えば２５６バイトの固定サイズ・ブロックに保存される。テーブル１６０は、例えばPage（ｉ）の特定のラインを構成する圧縮ブロックを含む。例えばPage（ｉ）のライン１は、それぞれ２５６バイトの３つの圧縮ブロックを含む。この例では各ページが最大４つのキャッシュ・ラインを含み、各キャッシュ・ラインは最大４つの圧縮メモリ・ブロックを含むので、各ページは最大１６のメモリ・ブロックを占めることができる。
【００１０】
再び図１に示したシステムを参照する。圧縮コントローラ１０６は、１つ以上の割込みレジスタ１２０とフリー・スペース・リスト１１２を含むことができる。フリー・スペース・リスト１１２の実施形態として、当業者には周知のリンク・リストが考えられる。圧縮コントローラ１０６は次のような様々な機能を実行する。
ａ）キャッシュ１０４からキャストアウトされたラインを圧縮し、結果をフリー・スペース・リスト１１２から引き出されたいくつかの固定サイズ・ブロックに保存する。
ｂ）キャッシュ・フェッチでラインを圧縮解除する。
ｃ）メモリからのラインの削除、変更されたラインの圧縮（によりスペースを少なくする）等の操作により空いたブロックをフリー・スペース・リスト１１２に追加する。
ｄ）ブロック数のカウントＦをフリー・スペース・リスト１１２に維持する。このカウントは好適には要求時にＯＳ１２５から使用できる。
ｅ）サイズＦの割込みレジスタ（１２０）として実装されるしきい値セットを維持する。しきい値を超える結果になるＦの変更により、プロセッサ割込みが生じる。好適には、各しきい値をソフトウェアにより動的に設定することができ、少なくとも測定量に関係するしきい値はコントローラ１０６の割込みレジスタ１２０に保存される。
【００１１】
図１には他に、フリー・スペース・リスト１１２に適切な数のブロックを維持するフリー・スペース・マネージャ１３０が示してある。ブロックが少なすぎるとシステムが異常終了するか、アプリケーションの実行が保留されてページアウトも保留される。ブロックが多すぎるとストレージが無駄になり、ページ・フォールトが過剰に発生する。フリー・スペース・マネージャ１３０はまた、割込みレジスタ１２０を、割込みが生成される１つ以上のしきい値（Ｔ０．．．ＴＮ）で設定する。定期的に測定される値とは異なる実際の測定値に関係するしきい値は、１つ以上の割込みレジスタ１２０に保存される。しきい値設定ポリシと制御プロセスの例については、米国特許出願第 （ＹＯ９９７３３８）号、COMPRESSION STORE FREE-SPACE MANAGEMENTを参照されたい。図１には、オペレーティング・システムにより要求されたときすぐ使用できるページ・フレームを表すページを持つ再利用リスト１３４も示してある。再利用リストの全ページの有効コピーがディスク上に存在するためにこれが可能である。
【００１２】
ページアウトを実行する際にはスペースを追加する必要があるが、これは、十分な量の物理フリー・スペースを維持することで解決することができる。ただし、これは物理ストレージをかなり無駄にすることにもなる。必要なページアウトは、最悪の場合の拡張も考慮する必要のあるページ・テーブル等の大きいオブジェクトの走査を伴うことがあるからである。これは、使用されているが使用可能な状態にあるメモリとみなされる。
【００１３】
例えば、図１に示すように、共有キャッシュ・メモリを実装したコンピュータ・システム１００に関して、コントローラ１０６は、コンピュータのオペレーティング・システムから使用できるフリー・スペースの量を表す値を持つカウント"Ｆ"を維持するように構成される。一般にＦは、スペース量がＦ*と指定されるページアウトを実行するに十分でなければならない。Ｆがしきい値Ｔ１より小さくなると（Ｔ１＞＝Ｆ*）、メモリ・コントローラはプロセッサに割込みを発行する。この割込みにより通常の処理が停止し、第２しきい値Ｔ２より上で使用できるフリー・スペースを増やすため十分なページ数を削除するか、またはディスクにページアウトすることによってフリー・スペースの回復が開始される。一般にＴ１により表される予約域はかなり大きく、かなりの量の未使用スペースがあり、従って無駄になっているスペースがあることを示す。
【００１４】
ディスクへのページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することが強く望まれる。
【００１５】
割込みハンドラにより削除できるが、システムにより参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１６】
ディスクへのページアウトを実行し、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしに、ページアウトを実行できるようにするため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１７】
【発明が解決しようとする課題】
本発明の目的は、予約スペースが足りないときにページアウトを実行できるように予約しておく必要のある物理スペースを少なくすることである。
【００１８】
本発明の他の目的は、圧縮メモリ・システムにおいて、圧縮／圧縮解除の過負荷から高速に回復する、つまりスペースを高速にクリアし、ページを回復する機構を提供することである。
【００１９】
本発明の他の目的は、圧縮メモリ・システムにおいて、割込みハンドラにより削除でき、システムによって参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウト操作を実行するのに必要な予約スペースを少なくするシステム及び方法を提供することである。
【００２０】
本発明の他の目的は、圧縮メモリ・システムにおいて、ページアウト操作を実行するのに必要な予約スペースを少なくし、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしにページアウトを実行できるようにするシステム及び方法を提供することである。
【００２１】
【課題を解決するための手段】
本発明に従い、圧縮された形で維持され、ページとして編成された内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理するシステム及び方法が提供される。システムは、圧縮された内容のメモリ・ストレージ・デバイスとの間の入出力操作の実行を管理する制御装置を含む。出力操作は、フリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含む。制御装置は、後続のページアウト操作が実行できるように、しきい値量を超えるまで回復するためすぐ使用できるフリー・ストレージ・スペースを維持する。後続のページアウト操作のため物理メモリからすぐクリアできるページの場所を含む新規のデータ構造体が提供される。制御装置は、データ構造体にアクセスし、このリストで削除可能と判定された１つ以上のページを便宜上削除することによってフラッシュ操作を実行する。このデータ構造体とフラッシュ操作により、フリー・ストレージ・スペースを回復するためのしきい値量を大幅に縮小することができる。
【００２２】
新規データ構造体が、すぐクリアできるページのリストを含む特別なソフトウェア構造体であることは好都合であり、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。
【００２３】
新規データ構造体の構造は、更新目的の通常のアクセス（スペース不足の問題がないとき）では、オペレーティング・システムをロックする必要があるが、（スペース不足の問題があるとき）ページのリストを走査することができ、最初にロックを取得することなく物理ストレージからページを消去することができる構造である。もう１つの要件は、割込み処理中に、またはサービス・プロセッサを介して、仮想メモリ・リスト管理とは独立して構造自体にアクセスできることである。
【００２４】
更に、新規データ構造体の構造は、通常動作へ復帰できるだけのストレージを表すのに十分なページのリストを保持することが保証された状態に保たれる構造である。従って、メモリが不足している場合にリストからページが消去されるとき、通常動作を再開する前のオペレーティング・システムの目的は、次の回復のため十分なページをこのリストに追加することである。
【００２５】
【発明の実施の形態】
本発明に従い、特別なソフトウェア構造体（ここでは"出力リスト"と称する）が提供され、図１のオペレーティング・システム１２５によって維持される。構造体は、すぐクリアできるページのリストを含むので、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。出力リスト構造の要件は、仮想メモリ・リスト管理から独立して、割込み処理中に、またはサービス・プロセッサを介して構造それ自体にアクセスできることである。
【００２６】
好適には、出力リスト構造自体が小さいメモリ・スペースを占め、よって大きい予約スペースの必要なしに走査し処理することができる。すなわち、出力リスト構造を与えることで、次の要件で前記のしきい値Ｔ１が大幅に縮小される。
【数１】
Ｔ１＜Ｆ*−Ｆ０＋Ｆ１
【００２７】
ここでＦ０は、出力リスト上のページにより保持されるスペース、Ｆ１は、出力リストの走査と処理のため予約する必要のあるスペース、Ｆ*は、ページアウトの実行を可能にするため必要な所定メモリ・スペースである。
【００２８】
図４は、好適には仮想アドレスが連続したＮ個のページのセットを持つハッシュ・テーブル１８０を含む出力リスト構造（１８０）の概念を示す。図４に示すように、出力リスト１８０上のページは、ハッシュ・テーブルのエントリ１８５として表され、各エントリ１８５は位置を含む。通常のハッシュ・リストに見られるように、所与のページのエントリは、そのアドレスのハッシュによりハッシュ・テーブルのエントリ・ポイントを取得することによって見つけることができる。衝突の場合（異なるページがこの位置に入力された場合）、Ｒを法とする昇順アドレスの順序で所望のページ（またはページのスペース）が見つかるまでアイテムが調べられる。Ｒはリスト上の位置の数である。出力リストにページが存在することは、オペレーティング・システムのページ・テーブルにあるそのエントリで示される。
【００２９】
図５は、フラッシュ操作でページの存在を示す"存在"ビット・フラグを格納するフィールド１９０（後述）、現在のページを示すページＩＤフィールド１９５、及びページが占める物理スペースＳ（ｉ）、つまり出力リスト・スペースを示すフィールド１９９を含むハッシュ・テーブル１８０のエントリ１８５を示す。
【００３０】
図６乃至図８に関して詳述するが、好適には、出力リスト上で行える操作が３つある。１）出力リスト上でのページの通常の追加と削除のＮＯＲＭＡＬ。出力リストにページが入力されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースに追加される。逆に、出力リストからページが削除されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースから引かれる。２）割込みハンドラによる出力リストからのページの削除であるＦＬＵＳＨ、及び３）通常の操作が再開される前に、ページ・テーブルが更新され、ＦＬＵＳＨ操作により行われたページの削除が反映されるＳＷＥＥＰである。図４に戻る。システムの通常動作時、ハッシュ・テーブル１８０での位置を示すポインタＰが維持される。例えばポインタ・エントリＰ１は、フラッシュ操作で消去された最も新しいページ１８１を示す。ポインタＰ２として示される第２ポインタ・エントリは、最後に消去されたページ１８４を示す。
【００３１】
ＮＯＲＭＡＬ動作ではハッシュ・テーブル１８０にアイテムを追加し、またはそこからアイテムを削除することができる。例えばテーブルのページ１８５を参照し、よってワーキング・セットに移すことができる。ページ"Ｖｉ"が削除されると、量Ｆ０は、Ｓ（ｉ）により示される占有物理スペースの量だけ少なくされる。Ｆ０が少なすぎる、つまりしきい値Ｔ１を下回る場合、リストにページが追加され、Ｆ０がＦ０＞Ｔ１になるまで調整される。
【００３２】
出力リストのデータ構造体は、（スペース不足が問題ではないときの）更新を目的にした通常のアクセスでは、オペレーティング・システムのロックを取得する必要がある。すなわち、２つ以上のＯＳスレッドが出力リストを同時に変更しようとするときの不一致を避けるため、通常のスレッド１つだけがアクティブになることを許可され、ページの入力または削除毎にロックが取得される。これは、ハッシュ・テーブルにロックを保持することをこのスレッドに要求することによって制御される。ただし、好適な実施例では、（スペース不足が問題になっているとき）ページのリストを走査し、ＦＬＵＳＨ操作で、最初にロックを取得することなしに物理ストレージからページを消去することができる。すなわち、入力が完了する前にフラッシュ操作によりスレッドに割込みをかけることができる。好適には、この不一致を避けるため、ページを"Ｖｉ"に入力する操作または"Ｖｉ"に入力されたページを削除する操作について、図６と合わせて説明する。"Ｖｉ"は、一番後に追加されたかまたは削除され、Ｓ（ｉ）物理スペースを占めるページのＩＤを表す。
【００３３】
図６は、ＮＯＲＭＡＬ出力リスト操作２００のフローチャートである。図６で、ハッシュ・テーブルにページを入力するかまたはそこから削除するため、ハッシュ・テーブルに対するロックを取得する第１ステップ２０２が必要である。次にステップ２０５で、このページが移行中であることを示すページＩＤ"Ｖ"がPageInTransシステム変数に割当てられる。この変数は、フラッシュ操作割込みの呼び出しにより追加／削除操作に割込みが入った場合にこのページが削除されるのを防ぐため与えられる。ページ２０８で、参照されたページを追加するか削除するかが確認される。ページが追加される場合、ステップ２１２に示すように、"存在ビット"の状態が確認される。存在ビットが設定されていない場合、ステップ２１５でハッシュ・テーブル・エントリが追加される。更にステップ２１６で、出力リストのページにより保持されたスペース、つまりＦ０の量を調整するため、比較交換操作により、ページが占める物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２１２で、ビットがすでに存在することが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。この時点で、ハッシュ・テーブルはロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加するかまたは削除する操作が繰り返される。
【００３４】
図６のステップ２０８に戻る。参照されたページが削除される場合、ステップ２２２に示されるように、"存在ビット"の状態が確認される。存在ビットが設定されている場合、ハッシュ・テーブル・エントリが削除される（ステップ２２５）。プロセスはステップ２１６に進み、出力リストのページにより保持されたスペースの量、つまりＦ０を調整するため、比較交換操作により削除されたページが占めていた物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２２２で、ビットがもう存在しないことが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。ここでハッシュ・テーブルのロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加する操作または削除する操作が繰り返されることを理解されたい。
【００３５】
比較交換は、図６のステップ２１６に示すようなアトミック・オペレーションであることを理解されたい。前述の通り、比較が否定的なら（フラッシュがあった場合）、プロセスは繰り返される。
【００３６】
図７は、割込み時に発生するシステムＦＬＵＳＨ操作３００の詳細を示すフローチャートである。基本的には、通常動作時に割込みが受信されてフラッシュ操作が開始された場合、ｉ＝１、２、．．．のとき、位置（Ｐ１＋ｉ） ｍｏｄ Ｒにあるページは、Ｖを除いて消去され、それらの存在ビットがステップ１５７で０に設定される。また詳しく後述するが、量Ｆ０が調整される。これはＦ０が量"デルタ"だけ小さくなるまで続けられる。デルタは、オペレーティング・システム（ＯＳ）を再起動するため十分と判断されるフリー・スペースの量である。最後に消去されるページは位置Ｐ２である。
【００３７】
図７の最初のステップ３０３に示すように、次のエントリが選択され、ステップ３０６で、PageIDがPageInTrans（遷移中のページ）に等しくないか確認される。PageIDがPageInTrans変数に等しくない場合、ステップ３０８でハッシュ・エントリの"存在ビット"が使用できないものとして指示され、ステップ３１０でページが０にされる。次にステップ３１３で、出力リストのページにより保持されたスペース量、つまりＦ０を調整するため、比較交換操作が実行され、ページが占めた物理スペース量Ｓ（ｉ）だけＦ０が調整される。ステップ３１５に進み、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいか確認される。ステップ３１５で、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいことが確認された場合、プロセスは終了し、スイープ操作に進む。ステップ３１５で、フラッシュされたスペースが必要なＦ*量に等しくないかまたはより大きくないことが確認された場合、プロセスはステップ３０３に戻り、フラッシュ操作のためハッシュ・テーブルから次のエントリが選択される。ステップ３１５の条件が真になるまでプロセス・ステップ３０３乃至３１５が繰り返される。
【００３８】
好適な実施例では、オペレーティング・システムが"ページ・フレーム・データベース"を維持する。このデータベースはメモリに保持されたページの状態を記述する。本発明に従って出力リストに保持されたページに対応するビットが、ページ・フレーム・データベースに設定される。これが参照される場合、一般には、ここで述べる操作により出力リストからこれを削除するのが望ましい。次に、出力リストのページにより保持されたスペース量がしきい値より少なくなった場合、このリストにページが追加される。図８は、ＦＬＵＳＨ操作の後、通常動作の再開前に発生するＳＷＥＥＰ操作４００を示す。この手順では、ページ・テーブルが更新され、ＦＬＵＳＨの結果としてのページの削除が反映される。特にＯＳはハッシュ・テーブルに対するロックを取得し、ポインタＰ１及びＰ２によりポイントされたページ位置間の全エントリをスイープし、存在ビットが０に設定されたエントリを消去し、そのページ・テーブルを調整するため、十分なエントリをテーブルに追加してスペース予約要件を満足する。これが完了すると、通常のシステム動作が再開される。具体的には、図８のステップ４０３に示すように、最初のステップはハッシュ・テーブルに対するロックを取得し、ポインタＰを最初のページＰ１、つまりフラッシュ操作時に消去された最も新しいページに等しく設定することである。次にステップ４０５で次のエントリが選択され、ステップ４０８で存在ビットが設定されているか確認される。選択されたページの存在ビットが設定されていない場合、つまり０に等しい場合、プロセスはステップ４１２に進み、ハッシュ・エントリとページ・フレーム・データベースのエントリが削除される。次にステップ４１５でページ・テーブル・エントリとフラッシュ・テーブルが無効にされる。ステップ４０８に戻り、存在ビットが設定されている場合、つまりフラッシュ操作が指示されている場合、プロセスはステップ４１８に進み、ポインタ値Ｐが増分され、ＰがＰ２、つまりＦＬＵＳＨ操作で最後に消去されたページより大きいか確認される。値Ｐが値Ｐ２よりまだ大きくない場合、プロセスはステップ４０５にループバックし、ハッシュ・テーブルの次のエントリが選択され、ステップ４０８乃至４１８が繰り返される。プロセス・ステップ４０５乃至４１８は、図８のステップ４１８で、ポインタＰがＰ２より大きいことが確認されるまで繰り返される。この条件が成立すると、プロセスはステップ４２０に進み、ハッシュ・テーブルのロックが解除され、再び新しいポインタ値ＰがＰ１に等しく設定される。
【００３９】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４０】
（１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理するシステムであって、該圧縮メモリの内容は、該メモリ・ストレージ・デバイスのページとして編成され、前記メモリ・ストレージ・デバイスとの間の圧縮内容の入出力操作のパフォーマンスを管理し、該出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含み、後続のページアウト操作を実行できるように、回復にすぐ使用できるフリー・ストレージ・スペース量をしきい値量を上回る値に維持する、制御装置と、
後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体とを含み、前記制御装置はフラッシュ操作を実行するため、該データ構造体にアクセスし、該データ構造体リストで識別された１つ以上のページを便宜上削除し、
よって、前記データ構造体により可能になった前記便宜上の削除を可能にすることによって、フリー・ストレージ・スペースを回復する前記しきい値量が少なくなる、システム。
（２）通常、ページアウト操作では、プロセッサ・デバイスにより発行された仮想メモリ・アドレスをフリー・スペースを回復するため削除される前記物理メモリのページ位置にマップするページ・テーブルをオペレーティング・システム・スレッドにより走査する必要があり、前記システムは、前記フラッシュ操作のため該ページ・テーブル走査を必要としない、前記（１）記載のシステム。
（３）前記システムは、回復のためのフリー・スペースの不足を確認する機構を含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、該機構が割込みを生成し、オペレーティング・システムから前記データへのアクセスを可能にし、プロセッサ・デバイスにより実行されるコマンド実行操作の一時的保留を開始する、前記（１）記載のシステム。
（４）前記データ構造体はテーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占められる関連物理スペースとを含み、前記データ構造体は前記リストの全てのアイテムにより占められる総物理スペースを維持する、
前記（３）記載のシステム。
（５）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたは前記物理メモリ・ストレージに追加する前記ページの可用性を示すビットを含み、前記制御装置は、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定する、前記（４）記載のシステム。
（６）前記制御装置は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するデバイスを含み、該調整は、前記データ構造体にテーブル・エントリを追加するかまたはそこから削除するための前記データ構造体へのアクセスを含み、
入力された各ページ用に占有された物理スペースが前記総物理スペースに追加され、削除された各ページ用に占有された物理スペースが前記総物理スペースから削除される、前記（４）記載のシステム。
（７）１つのオペレーティング・システム・スレッドがシステムの通常動作で前記データ構造体にアクセスできるようにするロック機構を含み、前記割込み処理機構が前記データ構造体への該オペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にする、前記（６）記載のシステム。
（８）前記データ構造体に入力された新しいページを遷移中のページとして識別する機構を含み、前記制御装置が、該新しいページを便宜上削除しないように、遷移中の新しいページが識別されていないか確認する、前記（７）記載のシステム。
（９）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持し、便宜上の削除操作時に消去された最後のページへの位置への第２ポインタを維持するトラッキング・ポインタ機構を含む、前記（６）記載のシステム。
（１０）前記フラッシュ操作の後、前記データ構造体リストのエントリを削除するスイープ機構を含み、削除される前記エントリは、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを含む、前記（９）記載のシステム。
（１１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理する方法であって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法は、
ａ）オペレーティング・システムによるページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、
を含む、方法。
（１２）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることの確認に応答して、
割込みを生成してオペレーティング・システムから前記データへのアクセスを可能にするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、前記（１１）記載の方法。
（１３）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全アイテムにより占有される総物理スペースを維持するステップを含む、
前記（１２）記載の方法。
（１４）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
前記（１３）記載の方法。
（１５）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有された物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、前記（１４）記載の方法。
（１６）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして、前記フラッシュ操作を可能にするステップを含む、前記（１５）記載の方法。
（１７）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、前記（１６）記載の方法。
（１８）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、
便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、
を含む、前記（１５）記載の方法。
（１９）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（１８）記載の方法。
（２０）圧縮された形で維持される内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理する方法のステップを実行するため、機械で実行可能な命令のプログラムを明確に具体化した機械可読プログラム・ストレージ・デバイスであって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法のステップは、
ａ）オペレーティング・システムによるメモリのページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、
を含む、機械可読プログラム・ストレージ・デバイス。
（２１）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、
割込みを生成してオペレーティング・システムから前記データにアクセスできるようにするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、前記（２０）記載の機械可読プログラム・ストレージ・デバイス。
（２２）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全てのアイテムにより占有される総物理スペースを維持するステップを含む、
前記（２１）記載の機械可読プログラム・ストレージ・デバイス。
（２３）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
前記（２２）記載の機械可読プログラム・ストレージ・デバイス。
（２４）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有される物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、前記（２３）記載の機械可読プログラム・ストレージ・デバイス。
（２５）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にするステップを含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２６）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、前記（２５）記載の機械可読プログラム・ストレージ・デバイス。
（２７）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、
便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、
を含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２８）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（２７）記載の機械可読プログラム・ストレージ・デバイス。
【図面の簡単な説明】
【図１】本発明の原理に従ってメモリ管理機能を組み込み使用するコンピュータ環境１００の例を示す図である。
【図２】ページ・テーブル構造の例を示す図である。
【図３】圧縮メイン・メモリのページの物理アドレスの編成例を示す図である。
【図４】物理スペースを回復するためのページのリストを含む出力リスト・テーブル２００を示す図である。
【図５】本発明に従った出力リスト・テーブル・エントリ２５０の内容を示す図である。
【図６】本発明の原理に従ったＮＯＲＭＡＬ出力リスト操作２００に関するシステム手法を示す図である。
【図７】本発明の原理に従ったＦＬＵＳＨ出力リスト操作３００に関するシステム手法を示す図である。
【図８】本発明の原理に従ったＳＷＥＥＰ出力リスト操作４００に関するシステム手法を示す図である。
【符号の説明】
１００ コンピュータ・システム
１０２ プロセッサ
１０４ キャッシュ
１０６ 圧縮コントローラ
１０８ 圧縮メイン・メモリ
１１０ 入出力（Ｉ／Ｏ）デバイス
１１２ フリー・スペース・リスト
１２０ 割込みレジスタ
１２５ オペレーティング・システム（ＯＳ）
１３０ フリー・スペース・マネージャ
１３４ 再利用リスト
１４０ ページ・テーブル
１４２ ページ・テーブル・エントリ
１４４ 仮想アドレス
１４６ 実アドレス
１４８ ページの管理情報
１５０、１６０ テーブル
１８０ ハッシュ・テーブル（出力リスト）
１８１、１８４、２０８ ページ
１８５ エントリ（ページ）
１９０ ビット・フィールド
１９５ ページＩＤフィールド
１９９ 出力リスト・スペース・フィールド
２００ ＮＯＲＭＡＬ出力リスト操作
３００ ＦＬＵＳＨ出力リスト操作
４００ ＳＷＥＥＰ出力リスト操作
【発明の属する技術分野】
本発明は、一般にはコンピュータのオペレーティング・システムに関し、特に圧縮メイン・メモリを組み込んだシステムで予約する必要のある物理フリー・スペースを少なくするシステム及び方法に関する。
【０００２】
【従来の技術】
図１は、圧縮メモリ管理機能を採用したコンピュータ・システム１００の一例である。コンピュータ・システム１００は、例えば１つ以上のプロセッサ１０２、オペレーティング・システム１２５、キャッシュ１０４、圧縮コントローラ１０６、圧縮メイン・メモリ１０８、及び１つ以上の入出力（Ｉ／Ｏ）デバイス１１０を含む。以下、それぞれについて説明する。
【０００３】
周知の通り、プロセッサ１０２はコンピュータ・システム１００の制御センターである。プロセッサ１０２は少なくとも１つのオペレーティング・システム（ＯＳ）１２５を実行する。ＯＳはプログラムの実行とデータの処理を制御する。ＯＳには、ＩＢＭから商標ＡＩＸとして販売されているようなＯＳや、マイクロソフト社からWindows（Ｒ）として販売されているＯＳ等がある。後述するように、オペレーティング・システム１２５は、コンピュータ・システム１００の１つのコンポーネントであり、本発明の機能を組み込んで使用することができる。
【０００４】
プロセッサ１０２と圧縮コントローラ１０６（後述）にはキャッシュ・メモリ１０４が接続される。キャッシュ・メモリ１０４は、Ｉ／Ｏデバイス１１０や圧縮メイン・メモリ１０８から圧縮コントローラ１０６により取得されたデータのための短期、高速、高容量のコンピュータ・メモリである。
【０００５】
キャッシュ１０４と圧縮メモリ１０８には圧縮コントローラ１０６が接続される。コントローラ１０６は、後述する通り、例えばＩ／Ｏデバイス１１０とキャッシュ１０４間の情報の転送や圧縮メイン・メモリ１０８とキャッシュ１０４間の情報転送を管理する。圧縮コントローラの機能は、データの圧縮／圧縮解除、得られた圧縮ラインの固定サイズ・ブロックへの保存を含む。これは好適には、オペレーティング・システムから見て実ページ・アドレスからメモリ１０８の固定サイズ・ブロックのアドレスへのマッピングを含む。
【０００６】
圧縮コントローラ１０６に接続された圧縮メイン・メモリ１０８は、例えばキャッシュ・ライン単位で圧縮されたデータを格納する。実施例では各ページが４つのキャッシュ・ラインを含む。キャッシュ・ラインは、キャッシュ１０４に挿入されたとき圧縮解除され、キャッシュ１０４からキャストアウトされたとき圧縮される。Ｉ／Ｏデバイス１１０からのページもメイン・メモリ１０８に挿入されたとき（キャッシュ・ライン単位で）圧縮される。簡素化のため１つのキャッシュしか示していないが、実際のシステムにはキャッシュの階層を加えてもよい。
【０００７】
周知の通り、メモリのページに関する情報は、メイン・メモリまたはキャッシュの１つ以上のページ・テーブルに保存することができ、ＯＳ１２５により用いられる。ページ・テーブルの１例（１４０）を図２に示す。ページ・テーブル１４０は複数のページ・テーブル・エントリ１４２を含み、各エントリは、例えば所与のページの仮想アドレス１４４、そのページの仮想アドレスに対応した実アドレス１４６、及びページの管理情報１４８のセットを含む。管理情報１４８は、例えばページが参照されたかどうかを示す使用ビット・フィールドと、許可アクセス・タイプを示す読取り／書込みアクセス・フィールドまたは読取り専用アクセス・フィールドである。
【０００８】
ページの実アドレスは、キャッシュ・ライン毎に、メイン・メモリ１０８からページが要求されたとき物理アドレスのセット（ストレージ・ブロックの識別子等）にマップされる。これは、実施例では、図３に示すテーブル１５０及び１６０を使用して実行される。これらのテーブルは圧縮コントローラ１０６に保存することができる。テーブル１５０は、例えばページの実ページ・アドレスと呼ばれるアドレスであるPage（ｉ）、及びページのライン毎のメモリ・ブロック・リストを含む。例えばページは、サイズが４Ｋバイトのときは４つのキャッシュ・ラインを含む。各キャッシュ・ラインのサイズは１Ｋバイトである。
【０００９】
圧縮キャッシュ・ラインは、例えば２５６バイトの固定サイズ・ブロックに保存される。テーブル１６０は、例えばPage（ｉ）の特定のラインを構成する圧縮ブロックを含む。例えばPage（ｉ）のライン１は、それぞれ２５６バイトの３つの圧縮ブロックを含む。この例では各ページが最大４つのキャッシュ・ラインを含み、各キャッシュ・ラインは最大４つの圧縮メモリ・ブロックを含むので、各ページは最大１６のメモリ・ブロックを占めることができる。
【００１０】
再び図１に示したシステムを参照する。圧縮コントローラ１０６は、１つ以上の割込みレジスタ１２０とフリー・スペース・リスト１１２を含むことができる。フリー・スペース・リスト１１２の実施形態として、当業者には周知のリンク・リストが考えられる。圧縮コントローラ１０６は次のような様々な機能を実行する。
ａ）キャッシュ１０４からキャストアウトされたラインを圧縮し、結果をフリー・スペース・リスト１１２から引き出されたいくつかの固定サイズ・ブロックに保存する。
ｂ）キャッシュ・フェッチでラインを圧縮解除する。
ｃ）メモリからのラインの削除、変更されたラインの圧縮（によりスペースを少なくする）等の操作により空いたブロックをフリー・スペース・リスト１１２に追加する。
ｄ）ブロック数のカウントＦをフリー・スペース・リスト１１２に維持する。このカウントは好適には要求時にＯＳ１２５から使用できる。
ｅ）サイズＦの割込みレジスタ（１２０）として実装されるしきい値セットを維持する。しきい値を超える結果になるＦの変更により、プロセッサ割込みが生じる。好適には、各しきい値をソフトウェアにより動的に設定することができ、少なくとも測定量に関係するしきい値はコントローラ１０６の割込みレジスタ１２０に保存される。
【００１１】
図１には他に、フリー・スペース・リスト１１２に適切な数のブロックを維持するフリー・スペース・マネージャ１３０が示してある。ブロックが少なすぎるとシステムが異常終了するか、アプリケーションの実行が保留されてページアウトも保留される。ブロックが多すぎるとストレージが無駄になり、ページ・フォールトが過剰に発生する。フリー・スペース・マネージャ１３０はまた、割込みレジスタ１２０を、割込みが生成される１つ以上のしきい値（Ｔ０．．．ＴＮ）で設定する。定期的に測定される値とは異なる実際の測定値に関係するしきい値は、１つ以上の割込みレジスタ１２０に保存される。しきい値設定ポリシと制御プロセスの例については、米国特許出願第 （ＹＯ９９７３３８）号、COMPRESSION STORE FREE-SPACE MANAGEMENTを参照されたい。図１には、オペレーティング・システムにより要求されたときすぐ使用できるページ・フレームを表すページを持つ再利用リスト１３４も示してある。再利用リストの全ページの有効コピーがディスク上に存在するためにこれが可能である。
【００１２】
ページアウトを実行する際にはスペースを追加する必要があるが、これは、十分な量の物理フリー・スペースを維持することで解決することができる。ただし、これは物理ストレージをかなり無駄にすることにもなる。必要なページアウトは、最悪の場合の拡張も考慮する必要のあるページ・テーブル等の大きいオブジェクトの走査を伴うことがあるからである。これは、使用されているが使用可能な状態にあるメモリとみなされる。
【００１３】
例えば、図１に示すように、共有キャッシュ・メモリを実装したコンピュータ・システム１００に関して、コントローラ１０６は、コンピュータのオペレーティング・システムから使用できるフリー・スペースの量を表す値を持つカウント"Ｆ"を維持するように構成される。一般にＦは、スペース量がＦ*と指定されるページアウトを実行するに十分でなければならない。Ｆがしきい値Ｔ１より小さくなると（Ｔ１＞＝Ｆ*）、メモリ・コントローラはプロセッサに割込みを発行する。この割込みにより通常の処理が停止し、第２しきい値Ｔ２より上で使用できるフリー・スペースを増やすため十分なページ数を削除するか、またはディスクにページアウトすることによってフリー・スペースの回復が開始される。一般にＴ１により表される予約域はかなり大きく、かなりの量の未使用スペースがあり、従って無駄になっているスペースがあることを示す。
【００１４】
ディスクへのページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することが強く望まれる。
【００１５】
割込みハンドラにより削除できるが、システムにより参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウトを実行するため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１６】
ディスクへのページアウトを実行し、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしに、ページアウトを実行できるようにするため必要な予約スペースを少なくするシステム及び方法を提供することも強く望まれる。
【００１７】
【発明が解決しようとする課題】
本発明の目的は、予約スペースが足りないときにページアウトを実行できるように予約しておく必要のある物理スペースを少なくすることである。
【００１８】
本発明の他の目的は、圧縮メモリ・システムにおいて、圧縮／圧縮解除の過負荷から高速に回復する、つまりスペースを高速にクリアし、ページを回復する機構を提供することである。
【００１９】
本発明の他の目的は、圧縮メモリ・システムにおいて、割込みハンドラにより削除でき、システムによって参照し使用することもできるページ・セットに予約域の多くを維持することによって、ページアウト操作を実行するのに必要な予約スペースを少なくするシステム及び方法を提供することである。
【００２０】
本発明の他の目的は、圧縮メモリ・システムにおいて、ページアウト操作を実行するのに必要な予約スペースを少なくし、ページ・テーブルの一般走査やページングＩ／Ｏの必要なしにページアウトを実行できるようにするシステム及び方法を提供することである。
【００２１】
【課題を解決するための手段】
本発明に従い、圧縮された形で維持され、ページとして編成された内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理するシステム及び方法が提供される。システムは、圧縮された内容のメモリ・ストレージ・デバイスとの間の入出力操作の実行を管理する制御装置を含む。出力操作は、フリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含む。制御装置は、後続のページアウト操作が実行できるように、しきい値量を超えるまで回復するためすぐ使用できるフリー・ストレージ・スペースを維持する。後続のページアウト操作のため物理メモリからすぐクリアできるページの場所を含む新規のデータ構造体が提供される。制御装置は、データ構造体にアクセスし、このリストで削除可能と判定された１つ以上のページを便宜上削除することによってフラッシュ操作を実行する。このデータ構造体とフラッシュ操作により、フリー・ストレージ・スペースを回復するためのしきい値量を大幅に縮小することができる。
【００２２】
新規データ構造体が、すぐクリアできるページのリストを含む特別なソフトウェア構造体であることは好都合であり、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。
【００２３】
新規データ構造体の構造は、更新目的の通常のアクセス（スペース不足の問題がないとき）では、オペレーティング・システムをロックする必要があるが、（スペース不足の問題があるとき）ページのリストを走査することができ、最初にロックを取得することなく物理ストレージからページを消去することができる構造である。もう１つの要件は、割込み処理中に、またはサービス・プロセッサを介して、仮想メモリ・リスト管理とは独立して構造自体にアクセスできることである。
【００２４】
更に、新規データ構造体の構造は、通常動作へ復帰できるだけのストレージを表すのに十分なページのリストを保持することが保証された状態に保たれる構造である。従って、メモリが不足している場合にリストからページが消去されるとき、通常動作を再開する前のオペレーティング・システムの目的は、次の回復のため十分なページをこのリストに追加することである。
【００２５】
【発明の実施の形態】
本発明に従い、特別なソフトウェア構造体（ここでは"出力リスト"と称する）が提供され、図１のオペレーティング・システム１２５によって維持される。構造体は、すぐクリアできるページのリストを含むので、ページ・テーブルの一般走査やページングＩ／Ｏが不要になる。出力リスト構造の要件は、仮想メモリ・リスト管理から独立して、割込み処理中に、またはサービス・プロセッサを介して構造それ自体にアクセスできることである。
【００２６】
好適には、出力リスト構造自体が小さいメモリ・スペースを占め、よって大きい予約スペースの必要なしに走査し処理することができる。すなわち、出力リスト構造を与えることで、次の要件で前記のしきい値Ｔ１が大幅に縮小される。
【数１】
Ｔ１＜Ｆ*−Ｆ０＋Ｆ１
【００２７】
ここでＦ０は、出力リスト上のページにより保持されるスペース、Ｆ１は、出力リストの走査と処理のため予約する必要のあるスペース、Ｆ*は、ページアウトの実行を可能にするため必要な所定メモリ・スペースである。
【００２８】
図４は、好適には仮想アドレスが連続したＮ個のページのセットを持つハッシュ・テーブル１８０を含む出力リスト構造（１８０）の概念を示す。図４に示すように、出力リスト１８０上のページは、ハッシュ・テーブルのエントリ１８５として表され、各エントリ１８５は位置を含む。通常のハッシュ・リストに見られるように、所与のページのエントリは、そのアドレスのハッシュによりハッシュ・テーブルのエントリ・ポイントを取得することによって見つけることができる。衝突の場合（異なるページがこの位置に入力された場合）、Ｒを法とする昇順アドレスの順序で所望のページ（またはページのスペース）が見つかるまでアイテムが調べられる。Ｒはリスト上の位置の数である。出力リストにページが存在することは、オペレーティング・システムのページ・テーブルにあるそのエントリで示される。
【００２９】
図５は、フラッシュ操作でページの存在を示す"存在"ビット・フラグを格納するフィールド１９０（後述）、現在のページを示すページＩＤフィールド１９５、及びページが占める物理スペースＳ（ｉ）、つまり出力リスト・スペースを示すフィールド１９９を含むハッシュ・テーブル１８０のエントリ１８５を示す。
【００３０】
図６乃至図８に関して詳述するが、好適には、出力リスト上で行える操作が３つある。１）出力リスト上でのページの通常の追加と削除のＮＯＲＭＡＬ。出力リストにページが入力されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースに追加される。逆に、出力リストからページが削除されると、それが占める物理スペースの量が、リストのアイテムにより占められる総物理スペースから引かれる。２）割込みハンドラによる出力リストからのページの削除であるＦＬＵＳＨ、及び３）通常の操作が再開される前に、ページ・テーブルが更新され、ＦＬＵＳＨ操作により行われたページの削除が反映されるＳＷＥＥＰである。図４に戻る。システムの通常動作時、ハッシュ・テーブル１８０での位置を示すポインタＰが維持される。例えばポインタ・エントリＰ１は、フラッシュ操作で消去された最も新しいページ１８１を示す。ポインタＰ２として示される第２ポインタ・エントリは、最後に消去されたページ１８４を示す。
【００３１】
ＮＯＲＭＡＬ動作ではハッシュ・テーブル１８０にアイテムを追加し、またはそこからアイテムを削除することができる。例えばテーブルのページ１８５を参照し、よってワーキング・セットに移すことができる。ページ"Ｖｉ"が削除されると、量Ｆ０は、Ｓ（ｉ）により示される占有物理スペースの量だけ少なくされる。Ｆ０が少なすぎる、つまりしきい値Ｔ１を下回る場合、リストにページが追加され、Ｆ０がＦ０＞Ｔ１になるまで調整される。
【００３２】
出力リストのデータ構造体は、（スペース不足が問題ではないときの）更新を目的にした通常のアクセスでは、オペレーティング・システムのロックを取得する必要がある。すなわち、２つ以上のＯＳスレッドが出力リストを同時に変更しようとするときの不一致を避けるため、通常のスレッド１つだけがアクティブになることを許可され、ページの入力または削除毎にロックが取得される。これは、ハッシュ・テーブルにロックを保持することをこのスレッドに要求することによって制御される。ただし、好適な実施例では、（スペース不足が問題になっているとき）ページのリストを走査し、ＦＬＵＳＨ操作で、最初にロックを取得することなしに物理ストレージからページを消去することができる。すなわち、入力が完了する前にフラッシュ操作によりスレッドに割込みをかけることができる。好適には、この不一致を避けるため、ページを"Ｖｉ"に入力する操作または"Ｖｉ"に入力されたページを削除する操作について、図６と合わせて説明する。"Ｖｉ"は、一番後に追加されたかまたは削除され、Ｓ（ｉ）物理スペースを占めるページのＩＤを表す。
【００３３】
図６は、ＮＯＲＭＡＬ出力リスト操作２００のフローチャートである。図６で、ハッシュ・テーブルにページを入力するかまたはそこから削除するため、ハッシュ・テーブルに対するロックを取得する第１ステップ２０２が必要である。次にステップ２０５で、このページが移行中であることを示すページＩＤ"Ｖ"がPageInTransシステム変数に割当てられる。この変数は、フラッシュ操作割込みの呼び出しにより追加／削除操作に割込みが入った場合にこのページが削除されるのを防ぐため与えられる。ページ２０８で、参照されたページを追加するか削除するかが確認される。ページが追加される場合、ステップ２１２に示すように、"存在ビット"の状態が確認される。存在ビットが設定されていない場合、ステップ２１５でハッシュ・テーブル・エントリが追加される。更にステップ２１６で、出力リストのページにより保持されたスペース、つまりＦ０の量を調整するため、比較交換操作により、ページが占める物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２１２で、ビットがすでに存在することが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。この時点で、ハッシュ・テーブルはロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加するかまたは削除する操作が繰り返される。
【００３４】
図６のステップ２０８に戻る。参照されたページが削除される場合、ステップ２２２に示されるように、"存在ビット"の状態が確認される。存在ビットが設定されている場合、ハッシュ・テーブル・エントリが削除される（ステップ２２５）。プロセスはステップ２１６に進み、出力リストのページにより保持されたスペースの量、つまりＦ０を調整するため、比較交換操作により削除されたページが占めていた物理スペース量Ｓ（ｉ）だけＦ０が増やされる。ステップ２２２で、ビットがもう存在しないことが確認された場合、プロセスはステップ２１９に進み、PageInTrans変数がリセットされ、操作は終了する。ここでハッシュ・テーブルのロックが解除される（ステップ２２０）。比較が否定的な場合（フラッシュがあったことを示す場合）、ステップ２０８以下でページ・エントリを追加する操作または削除する操作が繰り返されることを理解されたい。
【００３５】
比較交換は、図６のステップ２１６に示すようなアトミック・オペレーションであることを理解されたい。前述の通り、比較が否定的なら（フラッシュがあった場合）、プロセスは繰り返される。
【００３６】
図７は、割込み時に発生するシステムＦＬＵＳＨ操作３００の詳細を示すフローチャートである。基本的には、通常動作時に割込みが受信されてフラッシュ操作が開始された場合、ｉ＝１、２、．．．のとき、位置（Ｐ１＋ｉ） ｍｏｄ Ｒにあるページは、Ｖを除いて消去され、それらの存在ビットがステップ１５７で０に設定される。また詳しく後述するが、量Ｆ０が調整される。これはＦ０が量"デルタ"だけ小さくなるまで続けられる。デルタは、オペレーティング・システム（ＯＳ）を再起動するため十分と判断されるフリー・スペースの量である。最後に消去されるページは位置Ｐ２である。
【００３７】
図７の最初のステップ３０３に示すように、次のエントリが選択され、ステップ３０６で、PageIDがPageInTrans（遷移中のページ）に等しくないか確認される。PageIDがPageInTrans変数に等しくない場合、ステップ３０８でハッシュ・エントリの"存在ビット"が使用できないものとして指示され、ステップ３１０でページが０にされる。次にステップ３１３で、出力リストのページにより保持されたスペース量、つまりＦ０を調整するため、比較交換操作が実行され、ページが占めた物理スペース量Ｓ（ｉ）だけＦ０が調整される。ステップ３１５に進み、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいか確認される。ステップ３１５で、フラッシュされたスペースがＦ*ページアウトの実行に必要なメモリ・スペース量に等しいかまたはより大きいことが確認された場合、プロセスは終了し、スイープ操作に進む。ステップ３１５で、フラッシュされたスペースが必要なＦ*量に等しくないかまたはより大きくないことが確認された場合、プロセスはステップ３０３に戻り、フラッシュ操作のためハッシュ・テーブルから次のエントリが選択される。ステップ３１５の条件が真になるまでプロセス・ステップ３０３乃至３１５が繰り返される。
【００３８】
好適な実施例では、オペレーティング・システムが"ページ・フレーム・データベース"を維持する。このデータベースはメモリに保持されたページの状態を記述する。本発明に従って出力リストに保持されたページに対応するビットが、ページ・フレーム・データベースに設定される。これが参照される場合、一般には、ここで述べる操作により出力リストからこれを削除するのが望ましい。次に、出力リストのページにより保持されたスペース量がしきい値より少なくなった場合、このリストにページが追加される。図８は、ＦＬＵＳＨ操作の後、通常動作の再開前に発生するＳＷＥＥＰ操作４００を示す。この手順では、ページ・テーブルが更新され、ＦＬＵＳＨの結果としてのページの削除が反映される。特にＯＳはハッシュ・テーブルに対するロックを取得し、ポインタＰ１及びＰ２によりポイントされたページ位置間の全エントリをスイープし、存在ビットが０に設定されたエントリを消去し、そのページ・テーブルを調整するため、十分なエントリをテーブルに追加してスペース予約要件を満足する。これが完了すると、通常のシステム動作が再開される。具体的には、図８のステップ４０３に示すように、最初のステップはハッシュ・テーブルに対するロックを取得し、ポインタＰを最初のページＰ１、つまりフラッシュ操作時に消去された最も新しいページに等しく設定することである。次にステップ４０５で次のエントリが選択され、ステップ４０８で存在ビットが設定されているか確認される。選択されたページの存在ビットが設定されていない場合、つまり０に等しい場合、プロセスはステップ４１２に進み、ハッシュ・エントリとページ・フレーム・データベースのエントリが削除される。次にステップ４１５でページ・テーブル・エントリとフラッシュ・テーブルが無効にされる。ステップ４０８に戻り、存在ビットが設定されている場合、つまりフラッシュ操作が指示されている場合、プロセスはステップ４１８に進み、ポインタ値Ｐが増分され、ＰがＰ２、つまりＦＬＵＳＨ操作で最後に消去されたページより大きいか確認される。値Ｐが値Ｐ２よりまだ大きくない場合、プロセスはステップ４０５にループバックし、ハッシュ・テーブルの次のエントリが選択され、ステップ４０８乃至４１８が繰り返される。プロセス・ステップ４０５乃至４１８は、図８のステップ４１８で、ポインタＰがＰ２より大きいことが確認されるまで繰り返される。この条件が成立すると、プロセスはステップ４２０に進み、ハッシュ・テーブルのロックが解除され、再び新しいポインタ値ＰがＰ１に等しく設定される。
【００３９】
まとめとして、本発明の構成に関して以下の事項を開示する。
【００４０】
（１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理するシステムであって、該圧縮メモリの内容は、該メモリ・ストレージ・デバイスのページとして編成され、前記メモリ・ストレージ・デバイスとの間の圧縮内容の入出力操作のパフォーマンスを管理し、該出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含み、後続のページアウト操作を実行できるように、回復にすぐ使用できるフリー・ストレージ・スペース量をしきい値量を上回る値に維持する、制御装置と、
後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体とを含み、前記制御装置はフラッシュ操作を実行するため、該データ構造体にアクセスし、該データ構造体リストで識別された１つ以上のページを便宜上削除し、
よって、前記データ構造体により可能になった前記便宜上の削除を可能にすることによって、フリー・ストレージ・スペースを回復する前記しきい値量が少なくなる、システム。
（２）通常、ページアウト操作では、プロセッサ・デバイスにより発行された仮想メモリ・アドレスをフリー・スペースを回復するため削除される前記物理メモリのページ位置にマップするページ・テーブルをオペレーティング・システム・スレッドにより走査する必要があり、前記システムは、前記フラッシュ操作のため該ページ・テーブル走査を必要としない、前記（１）記載のシステム。
（３）前記システムは、回復のためのフリー・スペースの不足を確認する機構を含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、該機構が割込みを生成し、オペレーティング・システムから前記データへのアクセスを可能にし、プロセッサ・デバイスにより実行されるコマンド実行操作の一時的保留を開始する、前記（１）記載のシステム。
（４）前記データ構造体はテーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占められる関連物理スペースとを含み、前記データ構造体は前記リストの全てのアイテムにより占められる総物理スペースを維持する、
前記（３）記載のシステム。
（５）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたは前記物理メモリ・ストレージに追加する前記ページの可用性を示すビットを含み、前記制御装置は、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定する、前記（４）記載のシステム。
（６）前記制御装置は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するデバイスを含み、該調整は、前記データ構造体にテーブル・エントリを追加するかまたはそこから削除するための前記データ構造体へのアクセスを含み、
入力された各ページ用に占有された物理スペースが前記総物理スペースに追加され、削除された各ページ用に占有された物理スペースが前記総物理スペースから削除される、前記（４）記載のシステム。
（７）１つのオペレーティング・システム・スレッドがシステムの通常動作で前記データ構造体にアクセスできるようにするロック機構を含み、前記割込み処理機構が前記データ構造体への該オペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にする、前記（６）記載のシステム。
（８）前記データ構造体に入力された新しいページを遷移中のページとして識別する機構を含み、前記制御装置が、該新しいページを便宜上削除しないように、遷移中の新しいページが識別されていないか確認する、前記（７）記載のシステム。
（９）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持し、便宜上の削除操作時に消去された最後のページへの位置への第２ポインタを維持するトラッキング・ポインタ機構を含む、前記（６）記載のシステム。
（１０）前記フラッシュ操作の後、前記データ構造体リストのエントリを削除するスイープ機構を含み、削除される前記エントリは、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを含む、前記（９）記載のシステム。
（１１）圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理する方法であって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法は、
ａ）オペレーティング・システムによるページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、
を含む、方法。
（１２）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることの確認に応答して、
割込みを生成してオペレーティング・システムから前記データへのアクセスを可能にするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、前記（１１）記載の方法。
（１３）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全アイテムにより占有される総物理スペースを維持するステップを含む、
前記（１２）記載の方法。
（１４）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
前記（１３）記載の方法。
（１５）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有された物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、前記（１４）記載の方法。
（１６）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして、前記フラッシュ操作を可能にするステップを含む、前記（１５）記載の方法。
（１７）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、前記（１６）記載の方法。
（１８）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、
便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、
を含む、前記（１５）記載の方法。
（１９）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（１８）記載の方法。
（２０）圧縮された形で維持される内容を保存するフリー・スペースを持つ物理メモリを含むメモリ・ストレージ・デバイスを管理する方法のステップを実行するため、機械で実行可能な命令のプログラムを明確に具体化した機械可読プログラム・ストレージ・デバイスであって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法のステップは、
ａ）オペレーティング・システムによるメモリのページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐクリアできるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記リストで識別された１つ以上のページを便宜上削除することによってフラッシュ操作を実行するステップと、
を含む、機械可読プログラム・ストレージ・デバイス。
（２１）ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、
割込みを生成してオペレーティング・システムから前記データにアクセスできるようにするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、前記（２０）記載の機械可読プログラム・ストレージ・デバイス。
（２２）前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全てのアイテムにより占有される総物理スペースを維持するステップを含む、
前記（２１）記載の機械可読プログラム・ストレージ・デバイス。
（２３）前記データ構造体は更に、前記物理メモリ・ストレージから回復するかまたはそこに追加する前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
前記（２２）記載の機械可読プログラム・ストレージ・デバイス。
（２４）前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有される物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、前記（２３）記載の機械可読プログラム・ストレージ・デバイス。
（２５）システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にするステップを含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２６）前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、前記（２５）記載の機械可読プログラム・ストレージ・デバイス。
（２７）フラッシュ操作時に消去された最も新しいページの位置への第１ポインタを維持するステップと、
便宜上の削除操作時に消去された最後のページの位置への第２ポインタを維持するステップと、
を含む、前記（２４）記載の機械可読プログラム・ストレージ・デバイス。
（２８）前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、前記（２７）記載の機械可読プログラム・ストレージ・デバイス。
【図面の簡単な説明】
【図１】本発明の原理に従ってメモリ管理機能を組み込み使用するコンピュータ環境１００の例を示す図である。
【図２】ページ・テーブル構造の例を示す図である。
【図３】圧縮メイン・メモリのページの物理アドレスの編成例を示す図である。
【図４】物理スペースを回復するためのページのリストを含む出力リスト・テーブル２００を示す図である。
【図５】本発明に従った出力リスト・テーブル・エントリ２５０の内容を示す図である。
【図６】本発明の原理に従ったＮＯＲＭＡＬ出力リスト操作２００に関するシステム手法を示す図である。
【図７】本発明の原理に従ったＦＬＵＳＨ出力リスト操作３００に関するシステム手法を示す図である。
【図８】本発明の原理に従ったＳＷＥＥＰ出力リスト操作４００に関するシステム手法を示す図である。
【符号の説明】
１００ コンピュータ・システム
１０２ プロセッサ
１０４ キャッシュ
１０６ 圧縮コントローラ
１０８ 圧縮メイン・メモリ
１１０ 入出力（Ｉ／Ｏ）デバイス
１１２ フリー・スペース・リスト
１２０ 割込みレジスタ
１２５ オペレーティング・システム（ＯＳ）
１３０ フリー・スペース・マネージャ
１３４ 再利用リスト
１４０ ページ・テーブル
１４２ ページ・テーブル・エントリ
１４４ 仮想アドレス
１４６ 実アドレス
１４８ ページの管理情報
１５０、１６０ テーブル
１８０ ハッシュ・テーブル（出力リスト）
１８１、１８４、２０８ ページ
１８５ エントリ（ページ）
１９０ ビット・フィールド
１９５ ページＩＤフィールド
１９９ 出力リスト・スペース・フィールド
２００ ＮＯＲＭＡＬ出力リスト操作
３００ ＦＬＵＳＨ出力リスト操作
４００ ＳＷＥＥＰ出力リスト操作
Claims (27)
- 圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリを含むメモリ・ストレージ・デバイスを管理するシステムであって、該圧縮メモリの内容は、該メモリ・ストレージ・デバイスにページとして編成され、
前記メモリ・ストレージ・デバイスとの間の圧縮内容の入出力操作のパフォーマンスを管理し、該出力操作はフリー・メモリ・ストレージ・スペースを回復するメモリ・ページアウト操作を含み、後続のページアウト操作を実行できるように、回復にすぐ使用できるフリー・ストレージ・スペース量をしきい値量を上回る値に維持する、制御装置と、
後続のページアウト操作のため前記物理メモリからすぐ削除できるページの位置を含むデータ構造体とを含み、前記制御装置はページを削除するフラッシュ操作を実行するため、該データ構造体にアクセスし、該データ構造体で識別された１つ以上のページを便宜上削除し、
よって、前記データ構造体により可能になった前記便宜上の削除を実行することによって、フリー・ストレージ・スペースを回復する前記しきい値量が少なくなり、
前記ページアウト操作では、プロセッサ・デバイスにより発行された仮想メモリ・アドレスをフリー・スペースを回復するため削除される前記物理メモリのページ位置にマップするページ・テーブルをオペレーティング・システム・スレッドにより走査する必要があり、前記フラッシュ操作では該ページ・テーブル走査を必要としないことを特徴とする、システム。 - 前記システムは、回復のためのフリー・スペースの不足を確認する機構を含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、該機構が割込みを生成し、オペレーティング・システムから前記データへのアクセスを可能にし、プロセッサ・デバイスにより実行されるコマンド実行操作の一時的保留を開始する、請求項１記載のシステム。
- 前記データ構造体はテーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占められる関連物理スペースとを含み、前記データ構造体は前記リストの全てのアイテムにより占められる総物理スペースを維持する、
請求項２記載のシステム。 - 前記データ構造体は更に、前記物理メモリにフリーなスペースを回復または追加するためのページの可用性を示すビットを含み、前記制御装置は、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定する、請求項３記載のシステム。
- 前記制御装置は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するデバイスを含み、該調整は、前記データ構造体にテーブル・エントリを追加するかまたはそこから削除するための前記データ構造体へのアクセスを含み、
入力された各ページ用に占有された物理スペースが前記総物理スペースに追加され、削除された各ページ用に占有された物理スペースが前記総物理スペースから削除される、請求項４記載のシステム。 - １つのオペレーティング・システム・スレッドがシステムの通常動作で前記データ構造体にアクセスできるようにするロック機構を含み、前記割込み処理機構が前記データ構造体への該オペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にする、請求項５記載のシステム。
- 前記データ構造体に入力された新しいページを遷移中のページとして識別する機構を含み、前記制御装置が、該新しいページを便宜上削除しないように、遷移中の新しいページが識別されていないか確認する、請求項６記載のシステム。
- フラッシュ操作時に削除された最初のページの位置への第１ポインタ、最後のページへの位置への第２ポインタをそれぞれ維持するトラッキング・ポインタ機構を含む、請求項５記載のシステム。
- 前記フラッシュ操作の後、前記データ構造体リストのエントリを削除するスイープ機構を含み、削除される前記エントリは、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを含む、請求項８記載のシステム。
- 圧縮された形で維持される内容を保存するフリー・スペースのある物理メモリと仮想メモリ管理手段を含むメモリ・ストレージ・デバイスを管理する方法であって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法は、
ａ）オペレーティング・システムによるページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐ削除できるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記データ構造体で識別された１つ以上のページを便宜上削除することによってページを削除するフラッシュ操作を実行するステップとを含み、
前記便宜上削除とは、前記仮想メモリ手段が管理するページ・テーブルへ該当ページが削除されたことの反映を行わない削除であることを特徴とする、方法。 - ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることの確認に応答して、
割込みを生成してオペレーティング・システムから前記データへのアクセスを可能にするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、請求項１０記載の方法。 - 前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全アイテムにより占有される総物理スペースを維持するステップを含む、
請求項１１記載の方法。 - 前記データ構造体は更に、前記物理メモリにフリーなスペースを回復または追加するための前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
請求項１２記載の方法。 - 前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有された物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、請求項１３記載の方法。 - システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして、前記フラッシュ操作を可能にするステップを含む、請求項１４記載の方法。
- 前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、請求項１５記載の方法。 - 前記メモリ・ストレージ・デバイスは、フラッシュ操作時に削除された最初のページの位置への第１ポインタ、最後のページの位置への第２ポインタをそれぞれ維持するトラッキング・ポインタ機構を含むことを特徴とする
請求項１４記載の方法。 - 前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、請求項１７記載の方法。
- 圧縮された形で維持される内容を保存するフリー・スペースを持つ物理メモリと仮想メモリ管理手段を含むメモリ・ストレージ・デバイスを管理する方法のステップを実行するため、機械で実行可能な命令のプログラムを格納した機械可読プログラム・ストレージ・デバイスであって、該圧縮メモリ内容は、該メモリ・ストレージ・デバイスにページとして編成され、該方法のステップは、
ａ）オペレーティング・システムによるメモリのページアウト操作を可能にするしきい値量を超える量まで回復するためすぐ使用できるフリー・メモリ・ストレージ・スペースを維持するステップと、
ｂ）後続のページアウト操作のため前記物理メモリからすぐ削除できるページの位置を含むデータ構造体にアクセスするステップと、
ｃ）前記データ構造体で識別された１つ以上のページを便宜上削除することによってページを削除するフラッシュ操作を実行するステップとを含み、
前記便宜上削除とは、前記仮想メモリ手段が管理するページ・テーブルへ該当ページが削除されたことの反映を行わない削除であることを特徴とする、機械可読プログラム・ストレージ・デバイス。 - ステップｂ）の前に、ページアウト操作のためフリー・メモリ回復スペースの不足を確認するステップを含み、ページアウトのためフリー・ストレージ・スペースをすぐ回復する必要のあることが確認されたことに応答して、
割込みを生成してオペレーティング・システムから前記データにアクセスできるようにするステップと、
プロセッサ・デバイスにより実行されるコード実行操作の一時的保留を開始するステップと、
を含む、請求項１９記載の機械可読プログラム・ストレージ・デバイス。 - 前記データ構造体は、テーブル・エントリ・リストを持つハッシュ・テーブルを含み、該テーブル・エントリはそれぞれ、
前記物理メモリの前記ページを見つけるページ識別子と、
前記ページにより占有された関連物理スペースとを含み、前記維持ステップａ）は、前記リストの全てのアイテムにより占有される総物理スペースを維持するステップを含む、
請求項２０記載の機械可読プログラム・ストレージ・デバイス。 - 前記データ構造体は更に、前記物理メモリにフリーなスペースを回復または追加するための前記ページの可用性を示すビットを含み、前記維持ステップａ）は更に、前記フラッシュ操作のとき便宜上削除されるページに関連付けられたビットを設定するステップを含む、
請求項２１記載の機械可読プログラム・ストレージ・デバイス。 - 前記維持ステップａ）は更に、システムの通常動作時に後続のページアウト操作を考慮して前記総物理スペースを調整するステップを含み、該調整は、
i）前記データ構造体にアクセスしてテーブル・エントリを前記データ構造体に追加するかまたはそこから削除するステップと、
ii）入力された各ページについて占有される物理スペースを前記総物理スペースに追加するか、または、削除された各ページにより占有された物理スペースを前記総物理スペースから削除するステップと、
を含む、請求項２２記載の機械可読プログラム・ストレージ・デバイス。 - システムの通常動作で１つのオペレーティング・システム・スレッドから前記データ構造体にアクセスできるようにするロック機構を与え、該ロック機構が前記データ構造体へのオペレーティング・システム・スレッドのアクセスを無効にして前記フラッシュ操作を可能にするステップを含む、請求項２３記載の機械可読プログラム・ストレージ・デバイス。
- 前記データ構造体に入力された新しいページを遷移中のページとして識別するステップと、
前記フラッシュ操作時に遷移中のページとして識別された前記ページの便宜上の削除を防ぐステップと、
を含む、請求項２４記載の機械可読プログラム・ストレージ・デバイス。 - 前記メモリ・ストレージ・デバイスは、フラッシュ操作時に削除された最初のページの位置への第１ポインタ、最後のページの位置への第２ポインタをそれぞれ維持するトラッキング・ポインタ機構を含むことを特徴とする
請求項２３記載の機械可読プログラム・ストレージ・デバイス。 - 前記フラッシュ操作の後、前記第１ポインタと第２ポインタの位置の間にあり、前記可用性ビットが設定されたエントリを削除するステップを含む、請求項２６記載の機械可読プログラム・ストレージ・デバイス。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US09/648681 | 2000-08-25 | ||
| US09/648,681 US6842832B1 (en) | 2000-08-25 | 2000-08-25 | Reclaim space reserve for a compressed memory system |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JP2002132582A JP2002132582A (ja) | 2002-05-10 |
| JP3701890B2 true JP3701890B2 (ja) | 2005-10-05 |
Family
ID=24601778
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2001254088A Expired - Fee Related JP3701890B2 (ja) | 2000-08-25 | 2001-08-24 | 圧縮メモリ・システムの再利用スペース予約 |
Country Status (6)
| Country | Link |
|---|---|
| US (1) | US6842832B1 (ja) |
| JP (1) | JP3701890B2 (ja) |
| KR (1) | KR100443320B1 (ja) |
| IE (1) | IE20010731A1 (ja) |
| IL (1) | IL142020A (ja) |
| TW (1) | TW509842B (ja) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7565509B2 (en) * | 2002-04-17 | 2009-07-21 | Microsoft Corporation | Using limits on address translation to control access to an addressable entity |
| US6986006B2 (en) * | 2002-04-17 | 2006-01-10 | Microsoft Corporation | Page granular curtained memory via mapping control |
| US7039769B2 (en) | 2002-05-30 | 2006-05-02 | International Business Machines Corporation | Direct addressed shared compressed memory system |
| US20050246461A1 (en) * | 2004-04-29 | 2005-11-03 | International Business Machines Corporation | Scheduling threads in a multi-processor computer |
| US7383399B2 (en) * | 2004-06-30 | 2008-06-03 | Intel Corporation | Method and apparatus for memory compression |
| EP1703404A1 (fr) * | 2005-03-16 | 2006-09-20 | Amadeus s.a.s | Méthode et système pour maintenir la cohérence d'une mémoire cache utilisée par de multiples processus indépendants |
| KR100735552B1 (ko) * | 2005-09-23 | 2007-07-04 | 삼성전자주식회사 | 코드 메모리 상의 프로그램의 코드 크기를 줄이는 방법 |
| KR100786505B1 (ko) * | 2006-03-02 | 2007-12-17 | 엘지전자 주식회사 | 휴대용 단말기의 파일 관리 방법 |
| US20080307188A1 (en) * | 2007-06-06 | 2008-12-11 | International Business Machines Corporation | Management of Guest OS Memory Compression In Virtualized Systems |
| US8260927B2 (en) * | 2009-01-22 | 2012-09-04 | International Business Machines Corporation | Management of a reserve forever device |
| KR101574747B1 (ko) * | 2009-05-07 | 2015-12-07 | 삼성전자주식회사 | 플래시 메모리 저장 장치 및 그것을 포함한 컴퓨팅 시스템 |
| US8868575B2 (en) * | 2010-01-13 | 2014-10-21 | International Business Machines Corporation | Method and system for transformation of logical data objects for storage |
| KR101956031B1 (ko) * | 2012-10-15 | 2019-03-11 | 삼성전자 주식회사 | 데이터 압축 장치 및 방법, 데이터 압축 장치를 포함하는 메모리 시스템 |
| US9760478B2 (en) | 2014-12-02 | 2017-09-12 | Macronix International Co., Ltd. | Read leveling method and memory device using the same |
| US9690488B2 (en) * | 2015-10-19 | 2017-06-27 | Intel Corporation | Data compression using accelerator with multiple search engines |
| US12321620B2 (en) * | 2021-08-06 | 2025-06-03 | Micron Technology, Inc. | Techniques for memory zone size adjustment |
| CN113900826B (zh) * | 2021-11-25 | 2024-04-12 | 企查查科技股份有限公司 | 数据处理方法、装置、计算机设备、存储介质和程序产品 |
Family Cites Families (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1995018996A2 (en) * | 1993-12-30 | 1995-07-13 | Connectix Corporation | Lossless data compression system and method |
| US5696927A (en) * | 1995-12-21 | 1997-12-09 | Advanced Micro Devices, Inc. | Memory paging system and method including compressed page mapping hierarchy |
| US6279092B1 (en) * | 1999-01-06 | 2001-08-21 | International Business Machines Corporation | Kernel identification for space management in compressed memory systems |
-
2000
- 2000-08-25 US US09/648,681 patent/US6842832B1/en not_active Expired - Fee Related
-
2001
- 2001-03-14 IL IL142020A patent/IL142020A/en not_active IP Right Cessation
- 2001-07-06 TW TW090116682A patent/TW509842B/zh not_active IP Right Cessation
- 2001-08-01 IE IE20010731A patent/IE20010731A1/en not_active IP Right Cessation
- 2001-08-17 KR KR10-2001-0049453A patent/KR100443320B1/ko not_active Expired - Fee Related
- 2001-08-24 JP JP2001254088A patent/JP3701890B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JP2002132582A (ja) | 2002-05-10 |
| KR100443320B1 (ko) | 2004-08-09 |
| IL142020A0 (en) | 2002-03-10 |
| IE20010731A1 (en) | 2002-04-17 |
| IL142020A (en) | 2006-04-10 |
| US6842832B1 (en) | 2005-01-11 |
| KR20020016513A (ko) | 2002-03-04 |
| TW509842B (en) | 2002-11-11 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3701890B2 (ja) | 圧縮メモリ・システムの再利用スペース予約 | |
| US6216199B1 (en) | Hardware mechanism for managing cache structures in a data storage system | |
| JP4718683B2 (ja) | コンピュータ内のアプリケーションプログラム間でフォーカスが変更されたときに物理メモリの状態を復元する方法およびシステム | |
| EP2478442B1 (en) | Caching data between a database server and a storage system | |
| US5794256A (en) | Pointer swizzling facility using three-state references to manage access to referenced objects | |
| US11256434B2 (en) | Data de-duplication | |
| US20020166022A1 (en) | Access control method, access control apparatus, and computer-readable memory storing access control program | |
| US9081692B2 (en) | Information processing apparatus and method thereof | |
| US20090164715A1 (en) | Protecting Against Stale Page Overlays | |
| JPH08129457A (ja) | 外部記憶ストラクチャを拡大、縮小、及び再配分するための方法及び装置 | |
| JPH01303527A (ja) | 共有資源の管理方法 | |
| CA2426619A1 (en) | Defensive heap memory management | |
| US12223178B2 (en) | Information processing apparatus | |
| US20070130441A1 (en) | Address translation table synchronization | |
| US6889296B2 (en) | Memory management method for preventing an operating system from writing into user memory space | |
| JPH11259285A (ja) | オペレーティングシステムのモジュール入れ替え方法及びモジュールの入れ替えを作う処理装置 | |
| US6782444B1 (en) | Digital data storage subsystem including directory for efficiently providing formatting information for stored records | |
| US8898413B2 (en) | Point-in-time copying of virtual storage | |
| JPH06332625A (ja) | ファイルのデータ多重化方法及びデータ処理システム | |
| US7159139B2 (en) | Digital data storage subsystem including directory for efficiently providing formatting information for stopped records and utilization of a check value for verifying that a record is from a particular storage location | |
| US5900009A (en) | System and method for accessing records in a cache slot which are associated with a current owner storage element or at least one previous owner storage element | |
| US8892838B2 (en) | Point-in-time copying of virtual storage and point-in-time dumping | |
| JPH05210584A (ja) | 改善されたぺージングを有するディジタルデータプロセッサ | |
| US7139879B2 (en) | System and method of improving fault-based multi-page pre-fetches | |
| US6804754B1 (en) | Space management in compressed main memory |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20050127 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050209 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050422 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20050614 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050620 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050705 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050714 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080722 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090722 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100722 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110722 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110722 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120722 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130722 Year of fee payment: 8 |
|
| LAPS | Cancellation because of no payment of annual fees |