(57)【特許請求の範囲】
【請求項１】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを有することを特徴とするページングシステム。
【請求項２】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とするページングシステム。
【請求項３】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とするページングシステム。
【請求項４】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストへページアウトする手順を含むことを特徴とするページング方法。
【請求項５】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順を含むことを特徴とするページング方法。
【請求項６】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とするページングプログラム。
【請求項７】
ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下でなければ、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下であれば、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とするページングプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ページングシステム、ページング方法、および、ページングプログラムに関し、特に、スタンバイリストを階層化したページングシステム、ページング方法、および、ページングプログラムに関する。
【０００２】
【従来の技術】
従来のページング方式で実装されたメモリ管理機構はオペレーティングシステム（ＯＳ）によって実装に差異があるが、たとえば、マイクロソフト社のＷｉｎｄｏｗｓ（登録商標）での実装は、書籍「アーキテクチャ徹底解説  Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ（登録商標）  ２０００  上  マイクロソフト公式解説書  Ｄａｖｉｄ  Ａ．Ｓｏｌｏｍｏｎ，Ｍａｒｋ  Ｅ．Ｒｕｓｓｉｎｏｖｉｃｈ著／多摩ソフトウエア有限会社訳  ＩＳＢＮ４−８９１００−１９１−７  日経ＢＰソフトプレス発行  ２００１年４月２日」の第７章にまとめて記載されている（特に７．５節以降）。
【０００３】
また、「特開平６−２３６３２０号公報」記載の発明は、仮想記憶方式のコンピュータシステムにおいて、起動要求毎の時間間隔が長く、かつ、応答性能が重視されるプログラムを主記憶装置からページアウトする際に、そのプログラムの処理特性に応じてワーキングセット保証量とワーキングセット保証時間を更新することによりページアウト量を調整するようにしたメモリ管理方法」である。
【０００４】
【発明が解決しようとする課題】
上述した従来の技術（書籍記載）の問題点は、ページフォールトの際に人間が意識するほどの時間がかかる場合があるということである。
【０００５】
その理由は、ページを単純にＬＲＵで判断してハードウェアページフォールトを行うからである。ソフトウェアページフォールトに比してハードウェアページフォールトはディスクＩ／Ｏを伴うため、処理完了に時間がかかるが、この結果、一時的にページの利用が多発するような場合にアクセス頻度が高いページでもハードウェアページフォールトしてしまう確率が高くなるためである。
【０００６】
また、「特開平６−２３６３２０号公報」記載の発明の問題点は、スタンバイリストが存在しないので、ハードウェアページアウトの発生確率が高いという問題がある。
【０００７】
本発明の目的は、スタンバイリストを階層化することにより、低速なＩ／Ｏ処理を伴うディスクへのハードウェアページアウト回数を利用頻度の高いものについて改善することである。
【０００８】
【課題を解決するための手段】
本発明の第１のページングシステムは、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを有することを特徴とする。
【０００９】
本発明の第２のページングシステムは、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とする。
【００１０】
本発明の第３のページングシステムは、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とする。
【００１１】
本発明の第４のページングシステムは、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とする。
【００１２】
本発明の第５のページングシステムは、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルと、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする処理を行うオペレーティングシステムとを有することを特徴とする。
【００１３】
本発明の第１のページング方法は、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストへページアウトする手順を含むことを特徴とする。
【００１４】
本発明の第２のページング方法は、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順を含むことを特徴とする。
【００１５】
本発明の第３のページング方法は、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストへページアウトする手順を含むことを特徴とする。
【００１６】
本発明の第４のページング方法は、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順を含むことを特徴とする。
【００１７】
本発明の第１のページングプログラムは、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とする。
【００１８】
本発明の第２のページングプログラムは、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が事前に設定した閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とする。
【００１９】
本発明の第３のページングプログラムは、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とする。
【００２０】
本発明の第４のページングプログラムは、ページごとのページ切り替え回数、｛ページ切り替え回数×前回の平均アクセス間隔＋（システム時刻−閾値）｝／（ページ切り替え回数＋１）に従う平均アクセス間隔を含む主記憶上のページディレクトリと、ページを格納する主記憶装置上のワーキングセットと、前記ワーキングセットからページアウトするページ、前記ワーキングセットにページインするページを格納する主記憶上の第１スタンバイリストと、前記ワーキングセット、前記第１スタンバイリストからページアウトするページ、前記ワーキングセット、前記ワーキングセットにページインするページを格納する第２スタンバイリストと、前記第２スタンバイリストからページアウトされるページ、前記ワーキングセットにページインされるページを格納する外部記憶装置上のページファイルとを利用し、前記ワーキングセットからページアウトされるページの平均アクセス間隔が前記閾値以下であれば、前記第２スタンバイリストに空きがあれば、前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記ワーキングセットからのページを前記第２スタンバイリストへページアウトし、前記閾値以下でなければ、前記第１スタンバイリストに空きがあれば、前記第１スタンバイリストへページアウトし、前記第１スタンバイリストに空きがなければ、前記第２スタンバイリストに空きがあれば、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、空きがなければ、前記第２スタンバイリストからページを前記ページファイルへページアウトし、その後、前記第１スタンバイリストからのページを前記第２スタンバイリストへページアウトし、その後、前記ワーキングセットからのページを前記第１スタンバイリストへページアウトする手順をコンピュータに実行させることを特徴とする。
【００２１】
【発明の実施の形態】
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。
【００２２】
本発明の第１の実施の形態が適用される装置（たとえば、コンピュータ）は、時刻情報を取得する機能と、ページング方式をメモリ管理機構とするオペレーティングシステム（以降、ＯＳと記す）とが動作しているものとする。また、時刻情報は、システムで次の要件を満たすものとする。
［時刻情報の要件］
・たとえば、Ｗｉｎｄｏｗｓ（登録商標）のアプリケーションインタフェース（ＡＰＩ）のように、コマンドにより取得できる。
【００２３】
・システムにおいて、一意（構造体でもかまわない）で計算と比較が可能なデータである。
【００２４】
・データの分解能はカンタム値（プロセッサへのディスパッチの最小時間）である。
【００２５】
・前記分解能単位で計時機能（時刻とともに恒常的に変化する）がある。
【００２６】
通常、時計機能は、タイマやクロックのようにプロセッサとは独立しているのでプロセッサに問題があっても計時は可能である。データとしては現在の時刻をカンタム値の分解能で表現したもの、またはシステムが起動してからのカンタム値の分解能で測定可能な経過時間が該当する。
【００２７】
図１は、本発明の第１の実施の形態を示すブロック図である。
【００２８】
図１を参照すると、本発明の第１の実施の形態は、ＯＳにより動作するコンピュータのメモリ領域に設けられるワーキングセット１１０と、ワーキングセット１１０に対応する第１スタンバイリスト１４０と、第２スタンバイリスト１５０と、システム時刻データ（Ｓ）１６０と、閾値データ（Ｔ）１７０と、ページテーブル１８０と、ページディレクトリ１９０と、ハードディスク等の外部記憶装置に設けられるページファイル１３０と、セット・リスト管理データ３００とから構成される。
【００２９】
ワーキングセット１１０には、プロセスにより使用される命令語、データ等を含むページが格納される。
【００３０】
ワーキングセット１１０、第１スタンバイリスト１４０、第２スタンバイリスト１５０、および、ページファイル１３０は、ページを配置する構成である。また、システム時刻データ（Ｓ）１６０は、記時刻情報の要件を満たすデータであり、閾値データ（Ｔ）１７０は、システム時刻データ（Ｓ）１６０と比較・計算可能なデータである（いずれもシステムで単一である必要がある）。ここで、システム時刻データ（Ｓ）１６０は、起動からの総時間でもよければ、現在の時刻でもよい。
【００３１】
図２は、ページを管理するページテーブル１８０、ページディレクトリ１９０の構成を示す説明図である。
【００３２】
図２を参照すると、ページテーブル１８０は、複数のページテーブルエントリ（ＰＴＥ）を含み、ページディレクトリ１９０は、複数のページディレクトリエントリを含んで構成される。
【００３３】
また、ページディレクトリエントリは、ページ固有の平均アクセス間隔（Ａ）２００、最終更新時間（Ｌ）２１０、および、ページ切り替え回数（ｎ）２２０を格納する。
【００３４】
次に、ページディレクトリ１９０、ページテーブル１８０について図面を参照して説明する。
【００３５】
図６は、ページディレクトリ１９０のページディレクトリエントリの内容を示す説明図である。
【００３６】
図７は、ページテーブル１８０のページテーブルエントリの内容を示す説明図である。
【００３７】
図２に示すように、ページディレクトリ１９０は、ページテーブル１８０のページテーブルエントリの位置を表すページディレクトリエントリ（ＰＤＥ）の配列である。
【００３８】
図６を参照すると、たとえば、ページディレクトリエントリ（ＰＤＥ）は、ページテーブルエントリ（ＰＴＥ）の位置を示す情報、および、ページの状態を示す情報（Ａ、Ｌ、ｎ）を含む。
【００３９】
図７を参照すると、ページテーブル１８０のページテーブルエントリ（ＰＴＥ）は、たとえば、ページ番号、その他の情報を含む。
【００４０】
プロセスが作成されると、各プロセスに対応したページディレクトリ１９０と、ページテーブル１８０とが一つずつ作成される。作成されたページディレクトリ１９０のページディレクトリエントリ（ＰＤＥ）は、プロセス固有のページテーブルエントリ（ＰＴＥ）、もしくは、システム共有のページテーブルエントリ（ＰＴＥ）の位置の情報を持っている。このシステム共有のページテーブル１８０は、あらかじめ存在し、各プロセスから共有可能である。
【００４１】
次に、本発明の第１の実施の形態の動作について図面を参照して説明する。
【００４２】
以下の動作は、すべて、ＯＳにより実施される。
【００４３】
プロセスが作成（プログラムが起動）されると、ページディレクトリ１９０が作成される（個々のページディレクトリエントリがページやページテーブル１８０のテーブルエントリに１対１対応しているのに対し、ページディレクトリ１９０全体は、プロセスに１対１対応している）。ページディレクトリ１９０のページディレクトリエントリ、ページテーブル１８０のページテーブルエントリは、ページが作成されると追加される。ページは、作成時は、ワーキングセット１１０に割り当てられる。
【００４４】
ページディレクトリエントリのページ固有の平均アクセス間隔（Ａ）２００、最終更新時間（Ｌ）２１０、および、ページ切り替え回数（ｎ）２２０は、初期状態では次の値をとる（作成された直後のページはワーキングセット１１０に含まれることを前提にしているため）。
【００４５】
Ａ＝０                    （１ａ）。
【００４６】
Ｌ＝０                    （１ｂ）。
【００４７】
ｎ＝０                    （１ｃ）。
【００４８】
次に、ページフォールト時の動作のうち、ページアウトの動作について説明する。ページアウトとは、ワーキングセット１１０から第１スタンバイリスト１４０への移動、第１スタンバイリスト１４０から第２スタンバイリスト１５０への移動、および、第２スタンバイリスト１５０からページファイル１３０への移動を意味する。
【００４９】
図３は、本発明の第１の実施の形態のページアウトの動作を示すフローチャートである。
【００５０】
図３を参照すると、ページアウトが必要になった場合に、まず、ＯＳが、ワーキングセット１１０からページアウトすべきページをＬＲＵ等のアルゴリズムにより決定する（図３ステップＳ１）。次に、ページアウトすべきと決定されたページの平均アクセス間隔（Ａ）２００とシステムの閾値データ（Ｔ）１７０とを比較して（図３ステップＳ２）、次の式を評価し、正しければ（図３ステップＳ２／Ｙｅｓ）、第１スタンバイリスト１４０への移動を開始し、正しくなければ（図３ステップＳ２／Ｎｏ）、第２スタンバイリスト１５０への移動を行う処理に進む。
【００５１】
Ａ≦Ｔ                      （２）。
【００５２】
第１スタンバイリスト１４０への移動の場合、まず、移動したいページが移動可能であるかどうか、すなわち、第１スタンバイリスト１４０に空きが存在するかどうかを調べる（図３ステップＳ３）。第１スタンバイリスト１４０に空きが存在する場合は（図３ステップＳ３／Ｙｅｓ）、ワーキングセット１１０からのページを第１スタンバイリスト１４０に移動する（図３ステップＳ５）。
【００５３】
第１スタンバイリスト１４０に空きがない場合は（図３ステップＳ３／Ｎｏ）、まず、空きを作ってから移動処理を行う。空き領域を作るために第１スタンバイリスト１４０の内部からＬＲＵ等で第２スタンバイリスト１５０にページアウトされるページを決定する（図３ステップＳ４）。
【００５４】
次に、第１スタンバイリスト１４０から第２スタンバイリスト１５０にページの移動が可能であるかどうか、すなわち、第２スタンバイリスト１５０に空きが存在するかどうかを調べる（図３ステップＳ６）。第２スタンバイリスト１５０に空きが存在する場合には（図３ステップＳ６／Ｙｅｓ）、第１スタンバイリスト１４０からのページを第２スタンバイリスト１５０に移動する（図３ステップＳ９）。
【００５５】
第２スタンバイリスト１５０に空きが存在しない場合には（図３ステップＳ６／Ｎｏ）、空き領域を作るために第２スタンバイリスト１５０の内部からＬＲＵ等でページファイル１３０にページアウトされるページを決定し（図３ステップＳ７）、決定されたページをページファイル１３０に移動する（図３ステップＳ８）。次に、再度、ステップＳ６に戻り、第２スタンバイリスト１５０に空きが存在するので（図３ステップＳ６／Ｙｅｓ）、第１スタンバイリスト１４０からのページを第２スタンバイリスト１５０に移動する（図３ステップＳ９）。
【００５６】
次に、ステップＳ３に戻り、第１スタンバイリスト１４０に空きが存在するので（図３ステップＳ３／Ｙｅｓ）、ワーキングセット１１０からのページを第１スタンバイリスト１４０に移動する（図３ステップＳ５）。
【００５７】
また、Ａ≦Ｔでなかった場合（図３ステップＳ２／Ｎｏ）、第２スタンバイリスト１５０に空きが存在するかどうかを調べる（図３ステップＳ６’）。第２スタンバイリスト１５０に空きが存在する場合には（図３ステップＳ６’／Ｙｅｓ）、ワーキングセット１１０からのページを第２スタンバイリスト１５０に移動する（図３ステップＳ９’）。
【００５８】
第２スタンバイリスト１５０に空きが存在しない場合には（図３ステップＳ６’／Ｎｏ）、空き領域を作るために第２スタンバイリスト１５０の内部からＬＲＵ等でページファイル１３０にページアウトされるページを決定し（図３ステップＳ７’）、決定されたページをページファイル１３０に移動する（図３ステップＳ８’）。次に、再度、ステップＳ１０に戻り、第２スタンバイリスト１５０に空きが存在するので（図３ステップＳ１０／Ｙｅｓ）、ワーキングセット１１０からのページを第２スタンバイリスト１５０に移動する（図３ステップＳ９’）。
【００５９】
以上において、ワーキングセット１１０、第１スタンバイリスト１４０、第２スタンバイリスト１５０にどのページが格納されているかどうか、空きがあるかどうかは、セット・リスト管理データ３００により管理される。たとえば、セット・リスト管理データ３００は、ワーキングセット１１０、第１スタンバイリスト１４０、第２スタンバイリスト１５０対応に、それらに格納されているページ番号（ページを識別するために一意につけられた番号）を保持する。ＯＳは、このセット・リスト管理データ３００を参照することにより空きがあるかどうかを判断できる。また、上述したように、ＬＲＵを適用することにより、リプレースの管理もできる。
【００６０】
次に、ページフォールトの発生の有無にかかわらず新しいページを作成する際、ワーキングセット１１０内で発生するページの切り替えについて説明する。
【００６１】
図４は、ページ切り替えにおける統計情報の更新の動作を示すフローチャートである。
【００６２】
ＯＳが、プロセッサにディスパッチされたタスクが使用するページに切り替える（コンテキスト・スイッチの一つ）。
【００６３】
図４を参照すると、ＯＳは、統計情報の初期化処理を実施する。すなわち、現在ディスパッチされているタスクが使用しているページ（切り替え前のページ）について、ページディレクトリ１９０の対応するページディレクトリエントリの最終更新時間（Ｌ）２１０にシステム時刻データ（Ｓ）１６０の値を格納する（図４ステップＳ１０、）。以降、矢印（←）は、代入を表す。Ｓは、各々図１で示されるシステム時刻データ（Ｓ）１６０である。
【００６４】
Ｌ←Ｓ                                  （３）。
【００６５】
次に、コンテキスト・スイッチされたページ（切り替え後のページ）に対し平均アクセス間隔（Ａ）２００とページ切り替え回数（ｎ）２２０とを計算し、ページディレクトリ１９０の対応するページディレクトリエントリに格納する（図４ステップＳ１１）。計算は、次の（４ａ）、（４ｂ）式でこの順に行われる。Ｔは、各々図１で示される閾値データ（Ｔ）１７０である。
【００６６】
Ａ←｛ｎ×Ａ＋（Ｓ−Ｔ）｝／（ｎ＋１）  （４ａ）。
【００６７】
ｎ←ｎ＋１                              （４ｂ）。
【００６８】
ここで、初めて切り替わる場合には、Ａ＝０、ｎ＝１であるから、Ａ＝（Ｓ−Ｔ）／２、ｎ＝２となる。
【００６９】
以上の処理後に、ページの切り替えが発生し、ワーキングセット１１０に空きが無い場合に、ページフォールトが発生し、ページアウト・ページインの処理が行われる。ワーキングセット１１０に空きがあるかどうか調べ（図４ステップＳ１２）、空きがあれば（図４ステップＳ１２／Ｙｅｓ）、後述するページインの処理を実施する。空きがなければ（図４ステップＳ１２／Ｎｏ）、図３に示すページアウトの処理をステップＳ１から実施し、その後、ステップＳ１２に戻り、ワーキングセット１１０に空きがあるので（図４ステップＳ１２／Ｙｅｓ）、後述するページインの処理に進む。
【００７０】
次に、ページインの動作について図面を参照して説明する。
【００７１】
図５は、本発明の第１の実施の形態のページインの動作を示すフローチャートである。
【００７２】
ページインは、新規にページが作成される場合、あるいは、ページアウトされたページをワーキングセット１１０に移動する場合に発生するもので、ページフォールトのきっかけとなる動作である。既存ページのワーキングセット１１０への移動の場合、第１スタンバイリスト１４０、第２スタンバイリスト１５０、ページファイル１３０の順にワーキングセット１１０へ移動するページが存在するかどうかを検索する。
【００７３】
図５を参照すると、まず、第１スタンバイリスト１４０を検索する（図５ステップＳ１３）。ページインすべきページが第１スタンバイリスト１４０に検出されれば（図５ステップＳ１３／Ｙｅｓ）、検出されたページをワーキングセット１１０に移動する（図５ステップＳ１４）。ページインすべきページが第１スタンバイリスト１４０に検出されなければ（図５ステップＳ１３／Ｎｏ）、第２スタンバイリスト１５０を検索する（図５ステップＳ１５）。
【００７４】
ページインすべきページが、第２スタンバイリスト１５０に検出されれば（図５ステップＳ１５／Ｙｅｓ）、検出されたページをワーキングセット１１０に移動する（図５ステップＳ１６）。ページインすべきページが、第２スタンバイリスト１５０に検出されなければ（図５ステップＳ１５／Ｎｏ）、ページファイル１３０を検索し、ページファイル１３０から、ページインすべきページをワーキングセット１１０に移動する（図５ステップＳ１７）。ここで、ページファイル１３０にも検出されないということは原理的にはありえない。
【００７５】
以上では、平均アクセス間隔（Ａ）２００、最終更新時間（Ｌ）２１０、ページ切り替え回数（ｎ）２２０をＰＤＥに保持したが、ページディレクトリ１９０のエントリＰＤＥとページテーブル１８０のエントリＰＴＥとは一対一対応しているので、ページテーブル１８０のＰＴＥに保持させることも可能である。
【００７６】
次に、ハードウェアページフォールト回数が減ることについて説明する。
【００７７】
従来の技術について以下のように設定する（１つだけ存在するスタンバイリストを第０スタンバイリストとする）。
【００７８】
ｖｉ：ワーキングセット１１０に滞留する、または、から移動する確率（ｉの意味；０：ワーキングセット１１０に滞留、１：第０スタンバイリストに移動）。
【００７９】
ａｉ：第０スタンバイリストに滞留する、または、から移動する確率（ｉの意味；０：第０スタンバイリストに滞留、１：ワーキングセット１１０に移動、２：ページファイル１３０にページアウト）。
【００８０】
Σｖｉ＝１（０≦ｉ≦１）                （５ａ）。
【００８１】
Σａｉ＝１（０≦ｉ≦２）                （５ｂ）。
【００８２】
次に、本発明の第１の実施の形態において、以下の設定とする。
【００８３】
ｗｉ：ワーキングセット１１０に滞留する、または、から移動する確率（ｉの意味；０：ワーキングセット１１０に滞留、１：第１スタンバイリスト１４０に移動、２：第２スタンバイリスト１５０に移動）。
【００８４】
ｂｉ：第１スタンバイリスト１４０に滞留する、または、から移動する確率（ｉの意味；０：第１スタンバイリスト１４０に滞留、１：ワーキングセット１１０に移動、２：第２スタンバイリスト１５０に移動）。
【００８５】
ｃｉ：第２スタンバイリスト１５０に滞留する、または、から移動する確率（ｉの意味；０：第２スタンバイリスト１５０に滞留、１：ワーキングセット１１０に移動、２：ページファイル１３０にページアウト）。
【００８６】
Σｗｉ＝１（０≦ｉ≦２）                （６ａ）。
【００８７】
Σｂｉ＝１（０≦ｉ≦２）                （６ｂ）。
【００８８】
Σｃｉ＝１（０≦ｉ≦２）                （６ｃ）。
【００８９】
以下の式が成立する。
【００９０】
ｖ０＝ｗ０                              （７ａ）。
【００９１】
ｖ１×ａ０＝（ｗ１×ｂ２＋ｗ２）×ｃ０  （７ｂ）。
【００９２】
ｖ１×ａ１＝ｗ１×ｂ１＋ｗ２×ｃ１      （７ｃ）。
【００９３】
ｖ１×ａ２＝（ｗ１×ｂ２＋ｗ２）×ｃ２  （７ｄ）。
【００９４】
１−ａ０＝（１−ｂ０）×（１−ｃ０）    （７ｅ）。
【００９５】
ここで、（７ａ）、（７ｂ）、（７ｃ）、（７ｄ）、（７ｅ）式は、従来の技術と、本発明の第１の実施の形態とで、ページが、それぞれ、ワーキングセット１１０に存在する確率、第０スタンバイリストに存在する確率（第１スタンバイリスト１４０＋第２スタンバイリスト１５０に存在する確率）、ページファイル１３０に存在する確率は、等しいことから導出される。ただし、第０スタンバイリストに存在する確率は、第１スタンバイリスト１４０に存在する確率と第２スタンバイリスト１５０に存在する確率との合計とする。
【００９６】
（７ｂ）、（７ｄ）式から、次式を得る。
【００９７】
ａ２／ｃ２＝ａ０／ｃ０                  （８）。
【００９８】
（７ｅ）式を展開すると、次式を得る。
【００９９】
ａ０−ｂ０−ｃ０＋ｂ０×ｃ０＝０        （９）。
【０１００】
結果として、次の式を得る。
【０１０１】
ａ０／ｃ０＞１                      （１０ａ）。
【０１０２】
ａ２／ｃ２＞１                      （１０ｂ）。
【０１０３】
（１０ｂ）式より、従来の技術よりも、ハードウェアページフォールトの発生回数が低くなっていることがわかる。
【０１０４】
次に、本発明の第２の実施の形態について図を参照して説明する。
【０１０５】
本発明の第２の実施の形態は、本発明の第１の実施の形態の動作のステップ（図３、図４、図５）の手順を含む方法である。
【０１０６】
次に、本発明の第３の実施の形態について図を参照して説明する。
【０１０７】
本発明の第３の実施の形態は、本発明の第２の実施の形態の動作のステップ（図３、図４、図５）の手順をコンピュータに実行させるプログラムである。
【０１０８】
【発明の効果】
本発明の効果は、低速なＩ／Ｏ処理を伴うディスクへのハードウェアページアウト回数を利用頻度の高いものについて改善できることである。
【０１０９】
その理由は、第１スタンバイリスト−第２スタンバイリスト間のページの移動がＬＲＵ等で選択されたページについて発生することにより、アクセス間隔の短いページについては、ハードウェアページフォールトする確率が相対的に減るからである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態を示すブロック図である。
【図２】ページテーブル、ページディレクトリの構成を示す説明図である。
【図３】本発明の第１の実施の形態のページアウトの動作を示すフローチャートである。
【図４】ページ切り替えにおける統計情報の更新の動作を示すフローチャートである。
【図５】本発明の第１の実施の形態のページインの動作を示すフローチャートである。
【図６】ページディレクトリのページディレクトリエントリの内容を示す説明図である。
【図７】ページテーブルのページテーブルエントリの内容を示す説明図である。
【符号の説明】
１１０    ワーキングセット
１３０    ページファイル
１４０    第１スタンバイリスト
１５０    第２スタンバイリスト
１６０    システム時刻データ（Ｓ）
１７０    閾値データ（Ｔ）
１８０    ページテーブル
１９０    ページディレクトリ
２００    平均アクセス間隔（Ａ）
２１０    最終更新時間（Ｌ）
２２０    ページ切り替え回数（ｎ）
３００    セット・リスト管理データ
【図１】
0003901002.tif 000002
【図２】
0003901002.tif 000003
【図３】
0003901002.tif 000004
【図４】
0003901002.tif 000005
【図５】
0003901002.tif 000006
【図６】
0003901002.tif 000007
【図７】
0003901002.tif 000008