メモリ管理方法

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

【発明の名称】	メモリ管理方法
【発明者】	【氏名】平岩友理【氏名】清井雅広【氏名】秋葉千江子【氏名】長須賀弘文
【要約】	【課題】従来、ページリプレイスメントのための参照・更新情報を取得し実記憶の使用状況を反映するという処理を定期的にＣＰＵを占有して行う必要があった。従って実装する実記憶が大容量化した場合に、上記の使用状況反映処理に要する時間が長大化する課題があった。【解決手段】ページリプレイスメントのための参照・更新情報を取得し実記憶の使用状況を反映するという処理を行うか否かを空間単位でシステム稼働中に動的に変更できるようにする。

【特許請求の範囲】
【請求項１】主記憶装置と補助記憶装置を利用することで複数の仮想空間を展開し、当該主記憶装置以上の容量の仮想記憶を展開することが可能な計算機システムのメモリ管理方法において、当該計算機システム上に展開されている当該複数の仮想空間を、複数のグループのいずれかのグループに属するよう分類し、当該グループの中から１つ以上の仮想空間が属しているグループを１つ選択する処理を、予め定められた契機に基づき反復して動作させるステップと、上記主記憶装置上の利用されている領域を部分的に未使用状態にするときに、上記ステップにより選択されているグループに属している仮想空間が利用している当該主記憶装置上の領域の情報を、優先して上記補助記憶装置に出力するステップとを有することを特徴とするメモリ管理方法。
【請求項２】請求項１記載の計算機システムのメモリ管理方法において、当該主記憶装置上の領域を、一定のサイズ（ページ）単位で管理することを特徴とするメモリ管理方法。
【請求項３】主記憶装置と補助記憶装置を利用することで複数の仮想空間を展開し、当該主記憶装置以上の容量の仮想記憶を展開することが可能な計算機システムのメモリ管理方法において、当該計算機システム上に展開されている当該複数の仮想空間を、複数のグループのいずれかのグループに属するよう分類し、当該グループの中から１つ以上の仮想空間が属しているグループを１つ選択する処理を、予め定められた契機に基づき反復して動作させる第１のステップと、上記第１のステップで選択されたグループに属する仮想空間が利用している当該主記憶装置上の領域について未使用状態にする順序を決定する処理を、予め定められた契機に基づき反復して動作させる第２のステップと、上記主記憶装置上の利用されている領域を部分的に未使用状態にするときに、上記第１のステップにより選択されているグループに属している仮想空間が利用している当該主記憶装置上の領域の情報を、上記第２のステップにより決定した順序に基づき、優先して上記補助記憶装置に出力する第３のステップとを有することを特徴とするメモリ管理方法。
【請求項４】請求項３記載の計算機システムのメモリ管理方法において、当該主記憶装置上の領域を、一定のサイズ（ページ）単位で管理することを特徴とするメモリ管理方法。
【請求項５】請求項４記載の計算機システムのメモリ管理方法において、上記第１のステップは、当該複数の仮想空間から、予め定めた基準に基づき、少なくとも２つ以上で、多くとも当該複数の仮想空間の数より少ない数の仮想空間が属する第１のグループと、それ以外の仮想空間が属する第２のグループに分類する処理と、定期的に、予め定めた基準に基づき、上記第１のグループに属する仮想空間の中から、少なくとも１つ以上の仮想空間を残し、当該残された仮想空間以外の上記仮想空間を第１のグループから第２のグループに分類し、第２のグループから新たに少なくとも１つ以上の仮想空間を第１のグループに分類する処理と、定期的に、上記第１のグループを選択する処理から構成されることを特徴とするメモリ管理方法。
【請求項６】請求項５記載の計算機システムのメモリ管理方法において、上記第１のステップにおいて、上記第１のグループに仮想空間を残す基準を、当該グループに分類されてからの期間が短い順であることを特徴とするメモリ管理方法。
【請求項７】請求項４及び請求項６記載の計算機システムのメモリ管理方法において、上記主記憶装置上のページに対応するカウンタ領域を付加し、上記第２のステップは、上記第１のグループに属する仮想空間に割り当てられている上記主記憶装置上のページの参照及び更新の情報を取得し、参照又は更新があった場合は当該ページに対応するカウンタ領域をの値をクリアし、参照又は更新がなかった場合は当該ページに対応するカウンタ領域の値を増分させ、未使用状態にする順序を当該カウンタ領域の値が大きい順とする処理を、予め定められた契機に基づき反復して動作させることを特徴とするメモリ管理方法。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、仮想アドレスと実アドレスを対応させることで主記憶装置を使用する仮想記憶管理方式を採用した計算機システムにおけるメモリ管理方法に関する。特に、主記憶装置の空きが不足した場合に、既に割り当て済みのページを補助記憶装置に追い出し、空きページとして補給するページリプレイスメント方法に関する。
【０００２】
【従来の技術】仮想記憶方式では、主記憶装置と、主記憶装置に入り切らない情報を格納しておく補助記憶装置の間で、ページ単位の情報の交換を行う。主記憶装置から補助記憶装置に情報を移すことをページアウト、補助記憶装置から主記憶装置へ移すことをページインという。また、この２つを総称してページングという。
【０００３】通常、実装主記憶容量よりも仮想記憶の方が大きいため、システム稼働中にページングを行う必要が生じる。ある時点で必要なページを主記憶装置上に置くため、その時主記憶装置上にあるページ（実ページ）を選択し、ページアウトを行うことで空きページを作り、必要なページを割り当てるのである。これらのページの入れ替えによるメモリ管理方法はページリプレイスメントと呼ばれる。
【０００４】ページリプレイスメントを行う際に、空きページを作るためのページアウト対象ページを選択する論理に、例えばワーキングセット方式と呼ばれるものがある。これは実ページが参照・更新されたか否かの状態を一定時間毎に調査し、参照・更新状態でない時に対応する実ページ管理テーブルに設けられたカウンタを増分する処理を行い、その情報を元に実ページ管理テーブルを降順又は昇順に並び換える。そして、実際にページアウトを行う際に、実ページ管理テーブルの先頭又は最後尾に位置するページから、そのカウンタの値に基づきページアウトすることで、長い期間使用されていないページを対象として選出する方式である。なお、この種の仮想記憶方式及びページリプレイスメント方式については、例えば亀田寿夫著「オペレーティングシステムの基礎」（昭晃堂昭和６０年２月発行）の頁７０～８９や、前川守著「オペレーティングシステム」（岩波書店昭和６３年９月発行）の頁２５０～２７１に記述されている。
【０００５】また、特開平２－２４５９５１号公報に、主記憶領域を複数のグループに分けて、各々に対し順に参照・更新状態によるカウンタ操作処理を行うという技術が開示されている。
【０００６】
【発明が解決しようとする課題】従来技術において参照・更新状態を調査するには、その調査時点での使用状況を取得する必要があるため、ＣＰＵを占有して動作していた。従ってワーキングセット方式を主記憶装置上の全てのページを対象とした場合、その定期的にかかる参照・更新状態によるカウンタ操作処理のため、長時間ＣＰＵを占有してしまう問題があった。
【０００７】特に、大規模システムでは、高多重でジョブを実行するために、極めて大容量の主記憶を実装し、ジョブを実行したりジョブのデータを格納したりする仮想空間を多数配置できるようにしているため、上記問題点が顕著に現れてくる。
【０００８】特開平２－２４５９５１号公報で開示された技術は、主記憶容量の増加によるＣＰＵ占有時間の長大化を防止できるが、仮想空間の数が増加した場合に発生する上記問題点に対する解決策は開示されていない。
【０００９】
【課題を解決するための手段】上記課題を解決するために、本発明では実ページの参照・更新状態によるカウンタ操作処理を行うか否かをシステム稼働中に空間単位で切替えるメモリ管理方法を提供する。
【００１０】本発明での実ページの参照・更新の判断に用いるカウンタ管理や、実ページ管理テーブルのキュー操作等は、既に述べた公知技術と同様である。
【００１１】本発明のページリプレイスメント部は、ページリプレイスメント切替部と、ページリプレイスメント制御部と、ページリプレイスメント実行部から構成される。
【００１２】ページリプレイスメント切替部は、予め定めた基準に基づき、全ての空間を、参照・更新状態によるカウンタ操作処理行うグループと、同処理を行わないグループとに分類する。また、上記分類を行った後も、両グループの一部の空間の入れ替え処理を定期的に行う。
【００１３】ページリプレイスメント制御部は、定期的に、ページリプレイスメント切替部で参照・更新状態によるカウンタ操作処理を行うグループに分類された空間を選択し、同空間に割り当てられた実ページについて、参照・更新状態の情報を取得してカウンタを操作する。
【００１４】ページリプレイスメント実行部は、参照・更新状態によるカウンタ操作処理を行うグループに分類された空間に割り当てられた実ページを、それ以外の空間に割り当てられた実ページより優先してページアウトする。
【００１５】
【発明の実施の形態】本発明の実施形態を図を用いて詳細に説明する。
【００１６】まず第一の実施形態について図１～図８を用いて説明する。
【００１７】図１は、本実施形態の基本的な構成を表している。計算機１０１は、ＣＰＵ１０２、主記憶装置１０３、及び補助記憶装置１０５からなる。計算機１０１は、主記憶装置１０３上に配置しきれない情報を補助記憶装置１０５に書き出し、必要に応じて読み込みを行うページングを行う。このようにすることで、実装された主記憶装置１０３が有する容量以上の仮想記憶を計算機１０１に展開することが可能になる。
【００１８】主記憶装置１０３上のページは、ＣＰＵ１０２で実行される命令によって参照及び更新される。主記憶装置１０３上には、主記憶装置１０３の空きページ状況を格納した空きページ情報１０４、ページリプレイスメント処理に用いる情報を格納したリプレイスメント情報テーブル４００、本発明の主記憶管理を行うページリプレイスメント部８００、ユーザジョブが使用する仮想空間を管理するための仮想空間管理テーブル２００、実ページを管理するための実ページ管理テーブル３００がある。ページリプレイスメント部８００は、ページリプレイスメント切替部５００、ページリプレイスメント制御部６００、ページリプレイスメント実行部７００から構成される。仮想空間管理テーブル２００のチェインは並び換えられない。
【００１９】また、本システムでは、ＣＰＵ１０２によってページが参照及び更新されたという情報は、ハードウェアが情報を設定・保持し、ＣＰＵ１０２に参照及び更新情報取得用の命令を実行させることで取得できる。
【００２０】仮想空間管理テーブル２００の構成を図２に示す。切替情報２０１は、その空間が参照・更新状態によりカウンタを処理すべきか否かの情報を格納する領域である。本実施の形態では、ＯＮの場合に参照・更新状態によるカウンタ操作処理をする状態であり、ＯＦＦの場合は処理を行わない状態であるとして説明を行う。この切替情報２０１の内容を見ることで、その空間で参照・更新状態によるカウンタ操作処理を行っているか否かを見ることができる。ユーザは仮想空間管理テーブル２００を見てもよいし、稼動情報をモニタリングするツール等で表示させる手段をとってもよい。カウンタ処理回数２０２は、その仮想空間に対してページリプレイスメント制御部６００が参照・更新状態によるカウンタ操作処理を行った回数を格納するカウンタであり、初期値は０である。実ページ管理テーブルへのポインタ２０３は、その仮想空間に割り当てられている実ページを管理するための実ページ管理テーブル３００のキューの先頭へのポインタを格納している。但し、ポインタではなく、実ページ管理テーブルのアドレスを取得するための情報であってもよい。次空間テーブルへのポインタ２０４は、次の仮想空間管理テーブルへのポインタを格納している。前空間テーブルへのポインタ２０５は、前の仮想空間管理テーブルへのポインタを格納している。仮想空間管理テーブル２００が生成順等のキュー状にチェインされたとしても、そのキューの先頭と最後では、上記次空間テーブルへのポインタ２０４及び前空間テーブルへのポインタ２０５により、リング状に辿ることができる。
【００２１】実ページ管理テーブル３００の構成を図３に示す。カウンタ３０１は、参照・更新を管理するためのカウンタである。次テーブルへのポインタ３０２は、実ページ管理テーブル３００のキューでの、次のエントリへのポインタを格納している。但し、ポインタではなく、実ページ管理テーブルのアドレスを取得するための情報であってもよい。
【００２２】リプレイスメント情報テーブル４００の構成を図４に示す。処理空間数４０１は、参照・更新状態によるカウンタ操作処理を行ってページリプレイスメント実行部７００の第一の対象となるべき空間数を格納した領域である。リプレイスカウンタ値４０２は、ページリプレイスメント実行部７００で、実ページ管理テーブル３００のカウンタ３０１がいくつ以上のページをページアウト対象とするか選別するための閾値である。処理先頭空間テーブル４０３は、参照・更新状態によるカウンタ操作処理を行う空間の仮想空間管理テーブル２００へのポインタを格納する領域であり、システム立ち上げ時は空である。
【００２３】本実施形態におけるページリプレイスメント切替部５００の処理の流れを図５により説明する。本処理は定期的にタイマにより起動する。
【００２４】処理先頭空間テーブル４０３が空であるか否かを判定する（ステップ５０１）。
【００２５】上記判定が真であった場合は、以下の初期設定を行う。
【００２６】まず、処理先頭空間テーブル４０３に、ページアウト可能な実ページを有する空間の仮想空間管理テーブル２００の、先頭のエントリのアドレスを格納する（ステップ５０２）。
【００２７】次に処理先頭空間テーブル４０３から順に処理空間数４０１とリプレイスカウンタ値４０２を足した数から１減算した数の仮想空間管理テーブル２００の切替情報２０１にＯＮを設定する（ステップ５０３）。
【００２８】以上で初期設定時の処理を終了する。
【００２９】ステップ５０１における判定が偽であった場合は、以下の処理を行う。
【００３０】処理先頭空間テーブル４０３が指す仮想空間管理テーブル２００のカウンタ処理回数２０２がリプレイスカウンタ値４０２以上であるか否かを判定する（ステップ５０４）。
【００３１】上記判定が偽であった場合は、そのまま切替処理を終了する。
【００３２】上記判定が真であった場合は、以下の処理を行う。
【００３３】処理先頭空間テーブル４０３が指す仮想空間管理テーブル２００の切替情報２０１にＯＦＦを設定し、当該カウンタ処理回数２０２を０にクリアする。
【００３４】また、処理先頭空間テーブル４０３を、当該仮想空間管理テーブル２００の次のエントリを指すように設定する（ステップ５０５）。
【００３５】次に、ステップ５０５で更新した処理先頭空間テーブル４０３が指すエントリから、（処理空間数４０１＋リプレイスカウンタ値４０２－１）番目のエントリの切替情報２０１にＯＮを設定する（ステップ５０６）。
【００３６】以上で切替え処理は終了であり、引き続きリプレイスメント制御処理を行う。本実施形態におけるページリプレイスメント制御部６００の処理の流れを図６により説明する。リプレイスメント制御処理は、リプレイスメント切替処理から処理を引き継ぐ。
【００３７】ステップ６０４までの処理を、切替情報２０１がＯＮである仮想空間を対象として処理を行う（ステップ６０１）。
【００３８】当該空間の仮想空間管理テーブル２００の実ページ管理テーブルへのポインタ２０３にキューイングされている実ページ管理テーブル３００に対応する実ページの参照・更新状態を調べ、参照・更新されていた場合には、カウンタ３０１をクリアし、参照・更新されていなかった場合にはカウンタ３０１を増分する。当該空間の実ページについて処理が終った後に、このカウンタ３０１の値の大きい順に実ページ管理テーブル２００のキューを並び換える（ステップ６０２）。
【００３９】次に、ステップ６０２で処理を行った空間のカウンタ処理回数２０２を１つ増分する（ステップ６０３）。
【００４０】以上で１つの空間に対する処理を終了する（ステップ６０４）。
【００４１】本実施形態におけるページリプレイスメント実行部７００の処理の流れを図７により説明する。リプレイスメント実行処理は、タイマにより起動されるか、主記憶の空きが少なくなった場合に起動される。
【００４２】リプレイスメント対象空間を処理先頭空間テーブル４０３で指すエントリとする（ステップ７０１）。
【００４３】空きページ情報１０４から、必要なページアウト数を求める（ステップ７０２）。
【００４４】ページアウトする必要があるか否かを判定する（ステップ７０３）。
【００４５】上記判定が偽であった場合は、処理を終了する。
【００４６】上記判定が真であった場合は、以下の処理を行う。
【００４７】リプレイスメント対象空間のカウンタ処理回数２０２がリプレイスイカウンタ値４０２以上であるか否かを判定する（ステップ７０４）。
【００４８】上記判定が真であった場合は、以下の処理を行う。
【００４９】当該空間に割り当てられている実ページの実ページ管理テーブル３００のカウンタ３０１が、リプレイスカウンタ値４０２以上である実ページをページアウトする（ステップ７０５）。
【００５０】リプレイスメント対象空間を次のエントリにして、ステップ７０３へ戻る（ステップ７０６）。
【００５１】ステップ７０４の判定が偽であった場合は、以下の処理を行う。
【００５２】リプレイスメント対象空間を、処理先頭空間テーブル４０３の前のエントリとする（ステップ７０７）。
【００５３】当該空間に割り当てられている実ページの実ページ管理テーブル３００のカウンタ３０１が、リプレイスカウンタ値４０２以上である実ページをページアウトする（ステップ７０８）。
【００５４】リプレイスメント対象空間を前のエントリにする（ステップ７０９）。
【００５５】これ以上ページアウトする必要がないか、又は、リプレイスメント対象空間の切替情報２０１がＯＮであるかを判定する（ステップ７１０）。
【００５６】上記判定が何れかが真であった場合は、処理を終了する。
【００５７】上記判定が何れも偽であった場合は、ステップ７０８に戻る。
【００５８】本実施形態では、ステップ７０８において、処理対象である空間の切替情報２０１がＯＦＦであり、その時点より前の参照・更新状態によるカウンタ操作処理の結果をそのままリプレイスカウンタ値４０２と比較してページアウトするか否かの判定を行っているが、これをｔ回前に参照・更新状態によるカウンタ操作処理を行った空間であるならば（リプレイスカウンタ値４０２－ｔ）以上である実ページまでページアウトの対象と判定するなどの処理に変えてもよい。
【００５９】本実施形態におけるページリプレイスメント部８００における処理の概要を、図８により説明する。
【００６０】処理空間数４０１が３である。これは参照・更新状態によるカウンタ操作処理を行っていて、カウンタ３０１がリプレイスカウンタ値４０２以上でページアウト対象となり得る実ページを有する可能性のある空間を３個保持しながら動作することを示している。
【００６１】リプレイスカウンタ値４０２が２である。これは参照・更新状態によるカウンタ操作処理を行った結果、ページアウト対象としてカウンタ３０１が２以上の実ページをページアウト対象として選出することを示している。
【００６２】処理空間数４０１が３でありリプレイスカウンタ値４０２が２であることから、一回のページリプレイスメント制御部６００の起動で参照・更新状態によるカウンタ操作処理を行う空間数は４個である。これは図５におけるステップ５０３及びステップ５０６から求まる数値である。処理空間数４０１＋リプレイスカウンタ値４０２－１）から、１空間ずつずらしながら参照・更新状態によるカウンタ操作処理を行った場合でも、ある時点で処理空間数４０１に示した空間数からはページアウト可能であるために、一回のページリプレイス制御処理で参照・更新状態によるカウンタ操作処理を行う必要がある空間数が求まる。
【００６３】ｎ回目に参照・更新状態によるカウンタ操作処理を行ったのがＡからＤの４個の空間であったとすると、上記カウンタ操作処理により、各々の空間に割り当てられた実ページのカウンタ３０１が取り得る値の最大値は図示したようになる。空間Ａであれば０から４の値をとる。割り当てられた全てのページを参照・更新すると、カウンタ３０１がクリアされるため、必ず最大値の値を持つ実ページを有するわけではない。
【００６４】その後ページリプレイスメント切替部５００により参照・更新状態によるカウンタ操作処理を行う範囲がずれていく。
【００６５】ｎ＋２回目の参照・更新状態によるカウンタ操作処理を行った後に、ページリプレイスメント実行部によりページアウトを行う場合の、リプレイスメント対象となる空間の順序を■から■で示した。その時点での参照・更新状態によるカウンタ操作処理対象である空間Ｃから空間Ｆの内、リプレイスカウンタ値４０２を超えるカウンタ３０１の実ページを持つ可能性のある空間Ｃから空間Ｅをリプレイスメント対象とした後、更に必要な空きページを満たさなかった場合は、空間Ｃより前の空間を、参照・更新状態によるカウンタ操作処理の結果が確かな順に空間Ｂ、空間Ａと溯って対象としてページアウト処理を続ける。
【００６６】以上に述べたようにページリプレイスメント制御の切替を行い、ページリプレイスメントを実行することで、参照・更新状態によるカウンタ操作処理結果に基づく従来通りのワーキングセット方式のページリプレイスメントを行いつつ、大規模な主記憶装置全体に対して参照・更新状態によるカウンタ操作処理を行うことを避けることができる。また、対象となる空間を循環して変更していくことで、リプレイスカウンタ値４０２に示された回数以上に参照・更新状態によるカウンタ操作処理済みの空間を常に存在させておくことができ、いつページリプレイスメントを行う必要が生じた場合でも、ワーキングセット方式のページリプレイスメントが実行できる。更に、対象となる空間を循環して変更していくことで、ある時点より前に参照・更新状態によるカウンタ操作処理対象であった空間が何回前まで対象であったかを把握した上で、対象であった当時の参照・更新状態によるカウンタ操作処理結果を用いたページリプレイスメントができる。
【００６７】以上で本発明の第一の実施形態を説明したが、ページリプレイスメント切替部で、ｓ個（ｓは１以上の自然数）ずつ空間をずらす形態にしてもよい。
【００６８】ページリプレイスメント制御部の一回の動作で参照・更新状態によるカウンタ操作処理が行われる空間数は、（処理空間数４０１＋（リプレイスカウンタ値４０２－１）×ｓ）となる。この場合、ずらす個数ｓを格納する領域を設ける必要がある。
【００６９】次に、第二の実施形態を説明する。基本的には第一の実施形態と同様であるが、以下に相違点を述べる。
【００７０】前記実施形態においては、切替情報２０１の変更は、ページリプレイスメント切替部５００をタイマが起動する度に一空間ずつずらしていたが、これらを一定の時間が経過した場合に一括して切替え、ページリプレイスメント対象を、それ以前に参照・更新状態によるカウンタ操作処理を行っていた仮想空間群を単位としてずらす形態としてもよい。
【００７１】この場合の仮想空間情報テーブル２００を図９に示す。参照・更新状態によるカウンタ操作処理を行った順序情報を記述した切替順序情報２０６を追加してある。本実施形態では、この順序情報を０から始まり最大値の後０にラップアラウンドするカウンタとして説明するが、時刻情報としてもよい。
【００７２】また、本実施形態のリプレイスメント情報テーブル４００を図１０に示す。ページリプレイスメントによりページアウトを行う空間の先頭を指すリプレイスメント先頭空間テーブル４０４と、参照・更新状態によるカウンタ操作処理を行う時間を記述した経過時間閾値４０５を追加してある。
【００７３】次に、新たなページリプレイスメント切替部５００の処理の流れを図１１により説明する。本処理は定期的にタイマにより起動する。
【００７４】処理先頭空間テーブル４０３が空であるか否かを判定する（ステップ１１０１）。
【００７５】上記判定が真であった場合は、以下の初期設定を行う。
【００７６】まず、処理先頭空間テーブル４０３に、ページアウト可能な実ページを有する空間の仮想空間管理テーブル２００の、先頭のエントリのアドレスを格納する（ステップ１１０２）。
【００７７】次に処理先頭空間テーブル４０３から順に処理空間数４０１に記述された数の仮想空間管理テーブル２００の切替情報２０１にＯＮを設定する（ステップ１１０３）。
【００７８】ステップ１１０３で切替情報２０１をＯＮにした仮想空間管理テーブルの切替順序情報２０６に初期値である０を設定する（ステップ１１０４）。
【００７９】ステップ１１０１における判定が偽であった場合は、以下の処理を行う。
【００８０】リプレイスメント先頭空間テーブル４０４に、処理先頭空間テーブル４０３の内容を格納する（ステップ１１０５）その時点で切替情報２０１がＯＮである空間の切替情報２０１をＯＦＦにする（ステップ１１０６）。
【００８１】処理先頭空間テーブル４０３に、ステップ１１０７でＯＦＦにした空間の次の空間のテーブル２００のアドレスを格納する（ステップ１１０７）。
【００８２】処理先頭空間テーブル４０３が指す空間から、処理空間数４０１に記述された数の空間数の切替情報２０１をＯＮにし、各々の切替順序情報２０６に前回の切替順序情報に設定した値の次であることを示す値を設定する（ステップ１１０８）。前回の切替順序情報の値がａであれば、ａ＋１を設定する。前回の切替順序情報の値が切替順序情報２０６で表わせる最大値であれば、０を設定する。
【００８３】ステップ１１０１における判定が真であった場合も偽であった場合も、最後に経過時間閾値４０５に記述された時間後に次の切替処理を起動するためのタイマ設定を行い、処理を終了する（ステップ１１０９）。
【００８４】次に、ページリプレイスメント制御部６００の処理を説明する。処理の流れは図６を用いて説明した前記実施形態と同様であるが、ページリプレイスメント切替部とは別の契機でタイマ起動する。起動する契機は前記実施形態のページリプレイスメント切替部と同じである。
【００８５】次に、新たなページリプレイスメント実行部７００の処理の流れを図１２により説明する。リプレイスメント実行処理２は、タイマにより起動されるか、主記憶の空きが少なくなった場合に起動される。
【００８６】リプレイスメント対象空間をリプレイスメント先頭空間テーブル４０４で指すエントリとする（ステップ１２０１）。
【００８７】空きページ情報１０４から、必要なページアウト数を求める（ステップ１２０２）。
【００８８】ページアウトする必要がないか、又は、リプレイスメント対象空間が処理先頭空間テーブル４０３で指す空間に達したかを判定する（ステップ１２０３）。
【００８９】上記判定が何れかが真であった場合は、処理を終了する。
【００９０】上記判定が何れも偽であった場合は、以下の処理を行う。
【００９１】当該空間に割り当てられている実ページの実ページ管理テーブル３００のカウンタ３０１が、リプレイスカウンタ値４０２以上である実ページをページアウトする（ステップ１２０４）。
【００９２】当該エントリの切替順序情報２０６と、次のエントリの切替順序情報２０６が同じか否かを判定する（ステップ１２０５）。
【００９３】上記判定が真であった場合は、リプレイスメント対象空間を次のエントリにして、ステップ１２０３へ戻る（ステップ１２０６）。
【００９４】ステップ１２０５における判定が偽であった場合は、以下の処理を行う。
【００９５】当該エントリの切替順序情報２０６が示す値の直前にリプレイスメント制御処理の対象になったことを示す値を持った仮想空間管理テーブル２００を探し、複数あった場合はその先頭のエントリを、リプレイスメント先頭空間テーブル４０４に設定する（ステップ１２０７）。
【００９６】リプレイスメント対象空間をリプレイスメント先頭空間テーブル４０４で指すエントリとし、ステップ１２０３へ戻る（ステップ１２０８）。
【００９７】本実施形態におけるページリプレイスメント部８００における処理の概要を、図１３により説明する。
【００９８】処理空間数４０１が３である。これは参照・更新状態によるカウンタ操作処理を行う空間数と、カウンタ３０１がリプレイスカウンタ値４０２以上でページアウト対象となり得る実ページを有する可能性のある空間を３個として切替えることを示している。
【００９９】ある時間帯は、ｍ回目で示した参照・更新状態によるカウンタ操作処理の範囲と、リプレイスメント対象とする範囲でページリプレイスメントを行っているとする。
【０１００】その後ページリプレイスメント切替処理により、上記の対象をずらす。ｎ回目として示したように、前回まで上記カウンタ操作処理を行っていた範囲の空間が、優先的にリプレイスメント対象となり、前回まで上記カウンタ操作処理を行っていた範囲の次のエントリから処理空間数４０１に示された３個の空間が、新しい上記カウンタ操作処理の範囲となる。
【０１０１】ｎ回目から次のリプレイスメント切替処理が行われるまでに、ページリプレイスメント実行部によりページアウトを行う場合は、まず前回までリプレイスメント制御処理の対象であった■の範囲の空間のページを対象とし、その次に、更に前にリプレイスメント制御処理の対象であった■の範囲の空間のページを対象とする。このように、空間をいくつかのグループにわけ、そのグループ間でページリプレイスメントの対象として優先順位付けをする。
【０１０２】以上で本発明の実施形態を説明したが、ページリプレイスメント切替部で、新たに切替情報２０１をＯＮにする空間数を、その時のシステムの負荷に応じて変更する形態にしてもよい。ＣＰＵの負荷が低い期間に多くの空間に参照・更新状態によるカウンタ操作処理を行い、ＣＰＵの負荷が高くなった時に、参照・更新状態によるカウンタ操作処理を行う空間数を減らしてオーバーヘッドを抑えつつ、ＣＰＵの負荷が低い時期に算出したカウンタ３０１の情報を基にページアウト候補を選出する。
【０１０３】主記憶装置の他に拡張記憶装置を具備し、拡張記憶装置をページングに用いる計算機システムにおける、拡張記憶装置の空き領域管理に適用する形態もある。拡張記憶装置に空き領域を作成する場合に、拡張記憶装置を利用している空間の一部の空間に割り当てられている拡張記憶装置上の領域を、補助記憶装置への転送候補とする。
【０１０４】
【発明の効果】本発明により、ページアウトの対象となるページを選出するために、一定時間毎に割り当てられた実ページの参照・更新状態を調査する空間を、システム稼働中に動的に変更し、一部の空間のみ上記処理を行うことで、実記憶が大容量化し空間が多数存在した場合でも、定期的にＣＰＵを占有して行う上記処理に要する時間が長大化することを避けることができる。

【出願人】	【識別番号】０００００５１０８【氏名又は名称】株式会社日立製作所
【出願日】	平成１２年９月２６日（２０００．９．２６）
【代理人】	【識別番号】１０００７５０９６【弁理士】【氏名又は名称】作田康夫
【公開番号】	特開２００２－１０８７０６（Ｐ２００２－１０８７０６Ａ）
【公開日】	平成１４年４月１２日（２００２．４．１２）
【出願番号】	特願２０００－２９７０６９（Ｐ２０００－２９７０６９）