JPS6034143B2

JPS6034143B2 - ワ−キングセット管理方式

Info

Publication number: JPS6034143B2
Application number: JP56055886A
Authority: JP
Inventors: 直哉大野
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1981-04-14
Filing date: 1981-04-14
Publication date: 1985-08-07
Also published as: JPS57169988A

Description

【発明の詳細な説明】本発明は、マルチプログラミングで動作する仮想記憶方
式の情報処理システムにおけるワーキングセットの管理
方式の改良に関するものである。

マルチプログラミングで動作する仮想記憶方式の情報処
理システムにおいては、主記憶上の各プログラムに対し
て、いかに主記憶ページを割当てるかが問題となる。各
プログラムに割当てるべき主記憶ページ数を決定するた
めの方式として、あるプログラムで、一定時間内（これ
は、ウィンドサイズと呼ばれる）に参照したページは、
そのプログラムのために確保しておく、といういわゆる
ワーキングセット方式が知られている。

（以下ＷＳ方式とよぶ）ＷＳ方式を正確に実現しようと
すると、主記憶上のページが参照されるたびに、その参
照された時刻を最後に参照された時刻として記録してお
くと、ともに、主記憶上のページで、前記ウィンドサイ
ズ以前の時刻が記録されているページを探しこれをワー
キングセットから外し、空きページとして登録するとい
う処理を行う必要があり、厳密なＷＳ管理は、管理オー
バヘッドの点で非現実的であり、実際には、次のように
して実現される。即ち、主記憶上の各ページに対するア
クセスの行われ方を管理するために、各ページに対応し
た使用ビットおよび使用カウンタが用意される。使用ビ
ットは、対応するページに対して、主記憶アクセスが行
われた時点でセットされる。一定のＷＳ見直し契機毎に
、ＷＳ見直し管理が起動され、主記憶上の全ページにつ
いて、前記使用ビットを調べ、これがオンの場合、即ち
、対応するページに対して参照があった場合には、使用
カウンタがリセツトされる。使用ビットがオフの場合に
は、即ち、対応するべ−ジに対してアクセスが行われな
かった場合には、使用カウント値がカウントアップされ
る。使用カウント値が、ある値ｎよりも大きくなった場
合には、即ちｎ周期の間参照されず、ウインドサイズか
ら外れた場合には、このページは、これまで接続されて
いたワーキングセット枠から外し、不要ページとして、
空きページプールに登録される。プログラムの実行中に
、べ−ジフオルトが発生した場合には、空きページプー
ルからページがとられ、これがプログラムに与えられる
ことになる。

即ちプログラムに対応するワーキングセット枠に接続さ
れる。この方式により、各プログラムに割当てられるペ
ージ数は、そのプログラムの動作状況により、必要に応
じて、縮小、拡大されるので固定的にプログラムにペー
ジを与える場合に比べて、主記憶を有効に使うことが可
能である。

一方、プログラムによっては、そのプログラムの作成時
点で、あるいは、過去のプログラムの実行時のデータに
より、その必要とするメモリ量が既知である場合がある
。

このような場合には、プログラムを実行する毎に、その
時点での必要メモリ量を計測するワーキングセット方式
を必ずしも必要とせず、逆に、ワーキングセット方式を
適用した場合には、この管理のためのオーバヘッドのた
めに、性能が低下する場合がある。従って、本発明の目
的は、ワーキングセット見直しが必要とされるワーキン
グセット枠についてのみ見直しを行うことにより、ワー
キングセット枠見直しのオーバヘッドを減少した、改良
されたワーキングセット管理方式を提供することにある
。

本発明は、ワーキングセット情報が既知のプログラムに
対しては、ワーキングセット枠の最大値および最小値と
して、等しい値を指定することにより、この等しい値が
指定されたワーキングセット枠に対しては、定期的なワ
ーキングセット見直しを行わないようにすることにより
、ワーキングセット見直しのオーバヘツドを減少させよ
うとするものである。

次に、本発明の一実施例を説明するが、これに先立ち従
来行われているワーキングセット管理方式の実施例の概
要を第１図により説明する。

ワーキングセット（以下ＷＳと略す）管理の実現のため
に次の各テーブルが用意される。ＷＳ枠制御ブロック１
（以下、ＷＳＣＢと略す）は、各ＷＳ管理の単位である
ＷＳ枠に属するページを管理するためのテーブルで、各
ＷＳ枠毎に、ここでは、各プログラムを単位として、Ｗ
Ｓが管理されるとしているので、各プログラム毎にヱン
トリｉをもち、ェントリｉにはそのＷＳ枠に属するペー
ジ数ＰＮｉ、そのＷＳ枠に許されるページ数の最大値Ｍ
Ｘｉ、最小値ＭＮｉ、そのＷＳ枠に属するページリスト
へのポィンタＰＴＲｉが用意される。

プール枠制御ブロック２（以下プールＣＢと略す）は、
どのＷＳ枠にも属さない、未使用ページを管理するため
のテーブルで、未使用ページ数ＰＰＮおよび未使用ペー
ジリストへのポィン夕ＰＰＴＲをもつ。メモリマップ３
は、主記憶上の実ページを管理するためのテーブルで、
各ページ毎にェントリをもつ。

各ェントリには、ポィン夕部と、使用状況情報部があり
、ポィンタ部により、実ページは、いずれかのＷＳ枠、
あるいはプール枠に属するページリストを構成している
。

使用状況情報としては、使用ビットＵＢおよび使用カウ
ントＵＣが用意される。

使用ビットＵＢは、ページへの参照があった時点で例え
ば“１”がセットされ使用カウントＵＣは、後に示すよ
うにＷＳ見直し‘こ際して更新される。

また、ＷＳから外すべき周期関値（ウィンドサイズ）を
保持する闇値レジスタ４が用意される。また前記闇値レ
ジスタ４の値と、使用カウントＵＣの値とを比較するた
めの比較回路が設けられる。一定時間毎に起動される、
ＷＳ見直しタイマ割込みにより、各ＷＳ枠について、次
の動作が行われる。即ち、ＷＳＣＢＩの第ｉェントリポ
ィンタＰＴＲｉおよびメモリマップ上のポインタＰＴＲ
ｊによりメモリマップ３を順次たどりながら、対応する
メモリマップのェントリを論出し参照ビットをチェック
し、これが“１”の場合、即ち、参照があった場合には
、参照ビットを“０”クＩＪアするとともに、使用カウ
ントを、クリアする。

参照ビットが“０”の場合には、使用カウントを、カウ
ントアップする。この更新の結果と、関値しジスタ４の
値ｎを比較回路５により比較し使用カウントの値がｎ‘
こなった場合にはこのページは、ワーキングセットから
外れたものとして、このＷＳ枠のページリストから外さ
れ、プール枠につながれる。

（但し、既にそのＷＳ枠のページ数がＭＮｉ以下の場合
には、プールへの返却は行われない。）このような操作
を行うことにより、ＷＳ見直しのｎ周期の間参照されな
かったページは、そのＷＳ枠から外され、プール枠に返
却されることになる。

（この動作のフロゥチャートを第４図に示す）ページフ
オルトに際しては、まずプール枠からページをとりあえ
ずこのページフオルトを発生したプログラムのＷＳ枠に
割当て、要求されたページのパッキングストアからの転
送を起動するとともに、このＷＳ枠のページ数のチェッ
クを行う。

割当ての結果、最大値ＭＸｉよりも大になった場合には
、そのＷＳ枠に、使用カウントがｎのページがあれば、
これをプール枠に返却する。ない場合には、このＷＳ枠
の各ページについて、順次使用ビットをチェック、クリ
アしながら使用カウントを更新し、この更新の結果、使
用カウントがｎのページが発生するまで、この処理を行
い、使用カウントがｎになったページをプールに返却す
る。割当ての結果、ＷＳ枠のページ数が最小値より大で
、最大値以下の場合には、このＷＳ枠に、使用カウント
がｎのページがあるかどうかをチェックし、ある場合に
は、これをＷＳ枠から外し、プール枠に返却する。使用
カウントがｎのページがない場合には、プールのページ
数に不足がある場合郎ち、現在のプールのページ数が、
不足閥値よりも小の場合にのみ、プールへの返却を行う
。ＷＳ枠のページ数ＰＮｉが最小値ＭＮｉ以下の場合に
は、プールへの返却は行わない。なお、プール枠からＷ
Ｓ枠へのページの割当ては、次のように行われる。

まず、プール枠制御ブロックのページ数ＰＰＮを１減少
させるとともにポィンタ部ＰＰＴＲの値すなわち、その
時のプールの先頭のページ番号をセーブするとともにＰ
ＰＴＲ（値ｊをもっとする）で指定されるメモリマップ
３のェントリｊのポィンタ部ＰＴＲｊの値すなわち、前
記先頭のページの次に接続されているページの番号をプ
ール枠制御ブロックのポイン夕をセットする。

すなわち、これを新たな先頭ページとする。

これによりプール枠からの取外しの処理が完了する。次
にメモリマップの先にセーブしたポインタに対応するェ
ントリｉのポィンタＰＴＲｊにページを接続すべきＷＳ
枠に対応するＷＳＣＢの第ｉェントリのポィンタＰＴＲ
ｉの値をセットする。

この後同ポィンタＰＴＲｊに先にセーブした値ｉをセッ
トするとともに、現ページ数ＰＮを１だけ増大させる。
これにより先にプール枠から取外されたページがＷＳ枠
に接続されたことになる。ＷＳ枠からのプール枠へのペ
ージの返却も同様に行われる。

次に本発明の一実施例について説明する。

なお、本実施例においては、ＷＳ枠はプログラム即ち、
タスク対応に用意され、各プログラム毎にジョブ制御文
により、そのプログラムに与えるべきＷＳの最小値およ
び最大値を指定できるものとする。

プログラムの開始に際しては、このプログラムにタスク
制御ブロックｉが与えられた時点で、ＷＳＣＢｉも割当
てられ、ＷＳＣＢｉの有効ビットをオンにするとともに
ジョブ制御文で指定されたＷＳ最小値、最大値が、各々
、ＭＮｉ，ＭＡＸｉにセットされる。

以後、プログラムのロードページ・フオルト時のページ
のロード等は、タスク制御ブロックで指定されたＷＳ枠
に対して行われることになる。本実施例においては、Ｗ
Ｓ見直しを制御するために、図示してないが、ＷＳ枠選
択制御部およびＷＳ見直し制御部が設けられる。

ＷＳ枠選択制御部は、一定時間毎に起動され、ＷＳ見直
しを行うべきＷＳ枠を選択し、ＷＳ見直し制御部は、Ｗ
Ｓ枠選択制御部で選択されたＷＳ枠に対するＷＳ見直し
処理を行う。

第２図は本発明を具体化した一実施例の構成を示すブロ
ック図である。

本実施例においては、第１図に示した実現例に加えてＷ
ＳＣＢＩのＷＳの最小値ＭＮ、および最大値ＭＸを比較
するための一致検出回路７が設けられる。

次に、本実施例の動作を説明する。

一定時間毎に起動されるＷＳ見直しに際しては、ＷＳ枠
選択制御部は現在使用中の、即ち、有効ビットＶｉがオ
ンのＷＳ枠を順次選択し、選択されたＷＳ枠ｉに対応す
るＷＳＣＢｉの最小値ＭＮｉおよび最大値ＭＫｉを議出
し、この値を一致検出回路７により比較する。

一致検出回路が一致を検出した場合、即ち、両者の値が
等しい場合には、対応するＷＳ枠は、ＷＳ見直しの対象
とはせず、次のＷＳ枠について選択の処理を続ける。両
者の値が等しくない場合にはこのＷＳ枠に対してＷＳ見
直しを起動する。全ＷＳＣＢ（Ｎ個とする）について以
上の処理を行う。この動作のフロゥチャートを第３図に
示す。起動されたＷＳ見直し制御部は、実現例における
と同様の処理を行う。この動作のフロウチャート第４図
に示す。以上、本発明の一実施例の説明を行ったが、本
発明の主旨は、ワーキングセット見直しの各契機におい
て、ＷＳ枠に許されるメモリ量の最大値と最小値が等し
いＷＳ枠に対しては、ＷＳ見直しを行わないようにする
ことにより、ＷＳ見直しのオーバヘツドを減少できるよ
うにしたことにあり、プログラムとＷＳ枠の対応のさせ
方、使用カウントの指定のしかた、具体的なべージの使
用状況の管理方法等については、いくつかの実現方法が
考え得るであろう。また、本実施例で示したＷＳ枠選択
制御部、ＷＳ見直し制御部の詳細の実現方法、ＷＳ枠と
プール枠とのページのつなぎかえの詳細等については本
発明の主旨とは直接の関係がないので、説明の繁雑さを
避けるため述べなかったが、これらは通常の従来知られ
ている方法により、実現可能であることは明らかであろ
う。

【図面の簡単な説明】

第１図は、従来のＷＳ管理方式の一美現例を示すブロッ
ク図、第２図は、本発明を具体化した一実施例の構成を
示すブロック図、第３図は★本発明の一実施例における
見直しＷＳ枠選択制御部の処理のフロウチャートを示す
。第４図は本発明の一実施例におけるＷＳ見直し制御部の
処理のフロウチヤートを示す。１は、ＷＳ枠制御ブロッ
ク、２は、プール枠制御ブロック、３は、メモリマップ
、４は、閥値しジスタ、５は、比較回路、６は、カウン
トアップ回路、７は、比較回路である。姿ー図多２図髪３図髪４図

Claims

【特許請求の範囲】

１マルチプログラムで動作する仮想記憶方式の情報処
理システムにおいて、ワーキングセツトを管理する単位
である１個以上のワーキングセツト枠制御ブロツクをも
ち、前記各ワーキングセツト枠制御ブロツクは、そのワ
ーキングセツト枠に与えるべきページ数の最小値および
最大値を指定するフイールドを備え、一定時間毎に行わ
れるワーキングセツト見直しに際しては、前記各ワーキ
ングセツト枠制御ブロツクの最小ページ数と、最大ペー
ジ数が等しいワーキングセツト枠については、見直しを
行わないようにしたことを特徴とするワーキングセツト
管理方式。