JPS6336539B2

JPS6336539B2 -

Info

Publication number: JPS6336539B2
Application number: JP54129208A
Authority: JP
Inventors: Naoya Oono
Original assignee: Nippon Electric Co Ltd
Current assignee: NEC Corp
Priority date: 1979-10-05
Filing date: 1979-10-05
Publication date: 1988-07-20
Also published as: JPS5654683A

Description

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

マルチプログラミングで動作する情報処理シス
テムにおいては主記憶上の各プログラムに対し
て、いかに主記憶ページを割当てるかが問題とな
る。

このための方式としてあるプログラムで、一定
時間内に参照したページはそのプログラムのため
に確保しておく、いわゆるワーキングセツト方式
が知られている。

ワーキングセツト方式は、実際には、次のよう
に実現される。即ち、主記憶上の全ページについ
て、ページテーブルの参照ビツトを一定周期毎に
調べ、参照があれば、即ち参照ビツトが１なら
ば、これをリセツトするとともに対応するページ
の参照カウント置を０にし、参照されなかつた場
合には、カウント値をカウントアツプする。そし
て、参照カウント値が、ある値ｎよりも大きくな
つた場合には、即ちｎ周期の間参照されなかつた
場合には、そのページは不要ページとしてプログ
ラムからはずしシステムに戻され、空きページプ
ールに登録される。

プログラムの実行中にページフオルトが発生し
た場合には、空きページプールからページがとら
れ、これが、そのプログラムに与えられることに
なる。

この方式により、各プログラムに割当てられる
ページ数はその動きにより、必要に応じて、縮
小、拡大し、固定的にプログラムにページを与え
る場合に比べて、主記憶を有効に使うことが可能
である。

しかしながらこの方式においては、ある特定の
プログラムでたとえばフエイズの切挨わり等によ
り、アクセスするアドレス空間が急に切換わつた
場合には、ページフオルトが多発しこのプログラ
ムのワーキングセツトが拡大する。このために、
空きページプールから多くのページがこのプログ
ラムのために取られるために、他のプログラムで
発生したページフオルトに対して割当てるべき空
きページが不足するような事態が発生し、このた
めに、空きプールを回復するための処理が必要と
なりこれが処理速度の低下を招くという欠点があ
つた。そして、この空きプール不足の発生を少な
くするためには大きな空きプールを用意しておく
必要があり、これは主記憶の使用率を低下させる
要因となつていた。

本発明の目的は、従来のこれらの欠点を除こう
とするもので比較的少量の空きプールを用意して
おくだけで、主記憶上のページを効率的に使用で
きる情報処理装置を提供することにあり、また、
高い処理速度をもつ情報処理装置を提供すること
にある。

本発明は、各プログラムでワーキングセツトの
見直しを行つた時点で、次期の見直し周期におけ
るワーキングセツトの期待値を計算し、この期待
値に基づき、次の見直し周期までに各プログラム
が専有し得るページ数の最大値を設けておき、あ
るプログラムでページフオルトが発生する毎にそ
のプログララムで専用しているページ数が、この
最大値に達するまでは空きページプールからペー
ジをそのプログラムに割当てるが、それ以上ペー
ジフオルトが発生した場合にはそのプログラムの
ワーキングセツト枠の中で最も長い間使われなか
つたページを切り出し、ここに新たなページを割
当てるようにすることにより、特定のプログラム
におけるページフオルトの頻発により、空きペー
ジプールが不足する確率を低くしようとするもの
である。

従つて本発明によれば、従来の方式に比べて、
比較的小さい空きプールしか用意しなくても、空
きプールの不足の発生の確率を低くでき、主記憶
の有効利用、処理速度の向上が期待できることに
なる。

以下図により、本発明の一実施例を説明する。
本実施例においては、各プログラムに対応して、
ワーキングセツト管理が行われることとする。即
ち、ワーキングセツト枠がプログラム毎に設けら
れる。

そして、ワーキングセツト枠の制御のために、
各枠に対して、ワーキングセツト枠制御ブロツク
（以下WSCBと略す）が用意される。各WSCB
は、次期ワーキングセツト見直し直後のワーキン
グセツトサイズの期待値を保持するフイールド
EWS_j現在その枠につながれているページ数、即
ち、現ワーキングセツトサイズを保持するフイー
ルドCWS、次期ワーキングセツト見直しまでに
許されるワーキングセツトの最大値MWS、その
枠に属するページのリストの最初、最後のページ
を示すポインタを保持するフイールドTP，LPを
もつ。

同様に、空きページプール枠の管理のために、
空きプール枠制御ブロツク（以下EPCBと略す）
が用意され、これは、現在この枠につながれてい
るページ数即ち、空きページ数を保持するフイー
ルドEPN、空きページのリストへのポインタフ
イールドTPをもつ。

また、主記憶上の実ページを管理するために、
実ページに対応したエントリをもつページマツプ
PMAPが用意される。ページマツプの各エント
リは、現在の使用カウント値を保持するフイール
ドUC、このページにつながるページへの両方向
のポインタをもつフイールドEP，BPおよび各ペ
ージが参照された事を示すＲビツト、書込みが行
われたことを示すＷビツトをもつ。

ワーキングセツト枠につながれたページは、
WSCBおよびページマツプ上のポインタにより、
使用カウントの小さい順に、即ち、新しくアクセ
スされた順に並べられ最大のものをトツプに、最
大のものをラストにしてリストとして管理されて
いる。

また、ある周期ｎ以上参照されなかつたページ
はワーキングセツトからはずされ、空きページ枠
に戻されるがこの値ｎが閾値として保持される。

なお、本実施例においては、前回のワーキング
セツトサイズの期待値EWSj′と、今回のワーキン
グセツトの見直しにおいて、枠に残されたページ
数の平均値が、次期ワーキングセツトサイズの期
待値、として使用され、かつ、このワーキングセ
ツトサイズの期待値に、定数を加えたものが、次
期のワーキングセツト見直しまでにその枠に許さ
れるワーキングセツトの最大値MWSjとして使用
されると想定している。

次に、本実施例における動作を図により説明す
る。

あるプログラムｊの実行中に、ページフオルト
が発生すると、まず、このプログラムにおける現
在のページ数CWSjと、最大ワーキングセツトサ
イズMWSjが流出され、比較される。CWSjが、
MWSjよりも小さい場合には、空きページプール
から１ページがはずされるが、プログラムｊのワ
ーキングセツト枠のトツプにつながれここに、必
要な内容が二次記憶からロードされる。

そしてこのつなぎかえに伴い、EPCBの空きペ
ージへのポイツタTP、空きページ数EPN、つな
ぎかえられたページｉに対応するページマツプエ
ントリのポインタFPi、ページフオルトを起した
プログラムのWSCBの現ワーキングセツトサイ
ズCWSj、ページのリストへのポインタTPj、つ
なぎかえまでその枠でトツプにいたページのポイ
ンタBPが更新される。

CWSjの値がMWSjに等しい場合即ち、既にそ
のワーキングセツトの最大値に達している場合に
は、空きページ枠からのつなぎかえを行わず、自
枠のラストにあつたページを主記憶から追出し、
ここに、必要な情報を二次記憶から転送する。

即ち、枠ｊのラストにあつたページｋを、この
枠のトツプにつなぎかえ、このページに内容の変
更があつたかどうかを調べる。内容の変更がない
場合には直ちに、あつた場合には、これを二次記
憶にページアウトした後、必要な情報を二次記憶
装置からページインする。

なお、このつなぎかえに伴い、WSCBjのTP、
LP、つなぎかえられたページｋに対応するEP、
つなぎかえの直前までリストのトツプにあつたペ
ージに対応すBPの更新が行われる。

第１図の例により、以上の動作を説明する。

たとえば、ある時点で、プログラムｊが実行さ
れていたときに、ページフオルトを発生したとす
る。この時点で、プログラムｊには、６ページが
つながれているとする（CWS＝６）。また、この
枠に属する６ページのつながれている順序は、ペ
ージ番号が７、１、10、14、13、２の順でありこ
れはトツプが７（TP＝７）、ラストが２（LP＝
２）、およびページマツプの対応するページの前
方向および後方向のポインタEP、BPにより接続
されている。また、これは、その枠に属する各ペ
ージの使用カウント（UC）が小さい順に並べら
れていることが示されている。

また、空きページ枠はこの時点で５ページをも
ち、そのページのトツプはページ番号12、次に
15、０、４、５の順にページマツプのポインタ
EPによりリストを構成している。この様子が第
１図ａに示されている。

ページフオルトの発生について、ワーキングセ
ツトの最大値をMWS＝８とした場合についてみ
るとCWSj＜MWSjであるので空きページ枠か
ら、そのトツプにあるページ(12)が枠ｊのトツプに
つなぎかえられここにページ転送が行われる。第
１図ｂに示すようにこれに伴い空きページ枠のペ
ージ数ENPは５から４に、リストのトツプは以
前のページ番号12の次に、つながつていたページ
番号15となる（TP＝15）。また、枠ｊのTPには
12が、ページ数CWSは６から７にカウントアツ
プされる。また、これに伴いページマツプのポイ
ンタも更新される。また枠ｊには新たにつなげら
れたページ12のUC、Ｗビツトは０に、Ｒビツト
は１にセツトされる。これに対して、MWSj＝６
と設定されていた場合においては、ページフオル
トの発生により、CWSj＝MWSj＝６であり、従
つてこの場合には、ページ枠からのページのつな
ぎかえは行われず、第１図ｃに示すように枠ｊの
ラストにあるページ２がトツプにつなぎかえられ
る。ページ２はPMAPのページ２に対応するＷ
ビツトが１であり、書込みが行われているので、
まず、このページの内容を二次記憶装置に転送
し、Ｗビツトをリセツトした後要求された情報
を、二次記憶からページ転送し、Ｒビツトを１に
セツトするまたUCも０にリセツトする。なお、
これに伴いWSCBjのトツプは２に（TP＝２）、
ラストはページ２の前にあつた13になる（LP＝
13）また、ページマツプPMAPのポインタも第
１図ｃのように変更される。

なお、これらの処理を第２図のフロウチヤート
に示す。また、第１図のページマツプPMAPに
おいてページ３、６、８、９、11は枠ｊにも空き
ページ枠にも属していないページである。

なお、フロウチヤートにおけるｉ、ｌ、ｈ、ｋ
は、数値を一時的に保持する一時的な変数であ
る。

なお、ワーキングセツトの見直しは一定時間毎
に起動され、次の処理が行われる。即ち、主記憶
上にあるプログラムに属する全ページについて、
そのページに参照があつた場合即ち参照ビツトＲ
が１の場合にはこれをリセツトするとともに対応
する使用カウンタUCを０にするとともに、この
ページをそのページの属するワーキングセツトの
トツプにつなぎかえる。

ページに参照がなかつた場合には、対応する使
用カウンタUCをカウントアツプし、この値が閾
値ｎを越えている場合には、即ちＴ周期の間使用
されなかつたページは、空きページ枠に戻す。
（即ち、CWSをカウントダウンするとともに、こ
のページの空きページ枠へのつなぎかえのための
ポインタの更新、EPNのカウントアツプを行
う。）閾値ｎを越えていない場合には何も行わな
い。

また、各ワーキングセツトの枠について、次期
のワーキングセツト見直しまでに許されるワーキ
ングセツトの最大値MWSを次のようにして計算
し、新MWSとしてセツトする。

即ち、今回の見直しにより、枠ｊに残つている
ページ数を数えこの数と、枠ｊの前回の期待値即
ちEWSjフイールドの値を加算し、1/2倍するこ
とにより平均をとり、これを新EWSjとして、
EWSjのフイルドに格納するとともに、これに、
システムで管理されている定数Ｎを加え、これを
次期ワーキングセツト見直しまでのその枠におい
て許されるワーキングセツトサイズの最大値とし
て枠制御ブロツクWSCBjのMWSjのフイールド
に格納する。

第１図ｃの状態でワーキングセツトの見直しを
行つた場合を例として示す。なおここでは、枠ｊ
と、空きページ枠だけを対象としている。また、
ここでは定数ｎ＝２としている。またワーキング
セツトサイズMWSを定めるための定数Ｎ＝３と
する。また、前回の枠ｊのワーキングセツトサイ
ズの期待値EWSは３で、これがEWSjのフイール
ドに格納されているとする。

まず、ページ２は参照されているので（Ｒビツ
ト＝１）UCは０に、またリストのトツプにおか
れページ７はＲ＝０なのでUCは０から１にカウ
ントアツプされ、リスト上の順序はそのまま、ペ
ージ１はＲ＝１なのでUCは０、リストのトツプ
におかれ、次にページ10はＲ＝０なのでUCは１
から２にカウントアツプされる、ページ14はＲ＝
０なのでUCは２から３になりｎ＝２よりも大と
なつたので、これは枠ｊのリストからはずし、こ
の場合にはＷビツトが０なのでそのまま空きプー
ル枠のトツプにつなげる。これにより、枠ｊの
CWSは、６から５にカウントダウンされ、空き
プールサイズEPNは５から６にカウントアツプ
されるページ13は、Ｒ＝１なのでUCは２から０
にリセツトされ、リストのトツプにつながれる。
次に、枠ｊの今回の見直しによるページ数CWS
は５で、前回の期待値３との平均が計算され、こ
の値、即ち４が新たな期待値としてEWSのフイ
ールドに格納され、さらに、これにＮ＝３を加え
た値７が、次期のワーキングセツトサイズの最大
値として、MWSのフイールドに格納される。ワ
ーキングセツトの見直しが完了した時点で、枠ｊ
には、13、１、２、７、10の順で５個のページが
つながれ、空きページ枠には新たにページ14が加
えられている。それを第１図ｄに示す。なおメモ
リマツプにおける一は何の値でも関係ないことを
示す。以上、本発明の一実施例について説明した
ように、本発明の主旨は特定のワーキングセツト
枠におけるページフオルトの頻発により、空きプ
ール枠から無制限にページが割当てられるのを防
ぐために、特定のワーキングセツト枠が次のワー
キングセツトの見直しの周期までに許されるワー
キングセツトの最大値を設け、これ以上は割当て
られないようにすることにより、主記憶の有効利
用処理速度の向上を計ることにより、この主旨に
背かないかぎりいくつかの変形が可能であること
は明らかであろう。

たとえば、本実施例においては、ワーキングセ
ツト枠は、プログラム毎に用意するとしている
が、複数のプログラムに対して、１個のワーキン
グセツト枠を設けることも可能である。

また、本実施例においては、第２図のフロウチ
ヤートの右側に示すようにあるWS枠で最大値Ｎ
以上のページフオルトが発生した場合には、その
WS枠からまずページを切出し、必要ならばペー
ジアウトを行つた後、ページ転送を行うとしてい
るが、そのかわりに次のようにすることも可能で
ある。

即ち、まず空きページからページを割当て、こ
のページに対して二次記憶からのページの転送起
動する。この後でこれがこのWS枠に対する最大
値Ｎ以上のページフオルトであるかどうかを調
べ、そうであつた場合には、そのWS枠からリス
トの最後のページを取出し、このページのＷビツ
トを調べ、これが０ならばただちに、これが１な
らば、二次記憶に対して追出しを行つた後（ペー
ジアウト）、空きページ枠に戻すようにすること
も可能である。これにより、自WS枠内での切出
しに際して、切出すべきページに書込みがあつた
場合においても、この追出しに先立つて空きペー
ジ枠のページへのページインが行えるので、ペー
ジフオルト処理を短縮することができる。

なお、本実施例においては、ページマツプは専
用のメモリ上におかれ、ページへの参照があるた
びにページマツプ上の参照ビツトＲが１にセツト
されまた、書込みがあるたびにＷビツトに１がセ
ツトされるとしているが、ワーキングセツト見直
しにおける参照ビツトのリセツト時に、アドレス
変換テーブル上の参照ビツトを同時にリセツトし
ておき、アドレス変換テーブルで参照ビツトの０
から１への書換えがあつたときにのみ、ページマ
ツプ上の参照ビツトを１にセツトするように構成
することも可能である。また、参照ビツトをメモ
リマツプ上に設けずに、ページテーブル上に設け
ることも可能である。

また、本実施例においては、各ワーキングセツ
トの枠に対してワーキングセツトサイズの期待値
から最大値を求める方法として、期待値に、枠に
よらず一定値Ｎを加えるとしたが、各ワーキング
セツトの枠毎にたとえば、ワーキングセツトサイ
ズの期待値に応じて異なる値を与えるようにして
もよい。また、一定値Ｎを加えるとした場合に
は、MWSによりEWSを計算できるので、ワーキ
ングセツト枠制御ブロツクのEWSのフイールド
を省略してもよい。また、次期ワーキングセツト
の期待値として、今回のワーキングセツト見直し
直後のページ数と、前回の期待値との平均値を用
いているが、必ずしもこのようにする必要はな
く、前回の期待値と今回の値との比を変えること
も可能であり、また、今回のワーキングセツト見
直し直前のページ数も考慮して、次期期待値
EWSを求めることも可能である。たとえば、2/1
（見直し直前のページ数＋見直し直後のページ数）
と前回の期待値との平均を次期期待値としてもよ
い。

第３図は本実施例の構成の概要を示すブロツク
図である。本実施例においては、各ワーキングセ
ツト枠におけるページリスト現ワーキングセツト
サイズ、発生ページフオルト回数を管理するワー
キングセツト枠管理ブロツク１、主記憶上の各ペ
ージにおける書込み、参照、使用カウント等の使
用状況、ワーキングセツト枠、あるいは空きペー
ジ枠上につながれている順序等を管理するメモリ
マツプ２、空きページを管理する空きページ管理
ブロツク３、および、関連する制御回路４が用意
される。

制御回路４はページフオルトの発生に伴う、ペ
ージのプールからワーキングセツト枠へのつなぎ
かえ、ワーキングセツトの見直しに伴う、メモリ
マツプ上の参照ビツトのチエツク、使用カウント
の更新、ワーキングセツト枠から空きページ枠へ
のつなぎかえ、あるいは、ページへの参照、書込
に伴うＲビツト、Ｗビツトの更新等の前述の動作
を制御するが、本発明の詳細な説明な構成、ある
いは、制御回路の詳細な動作は本発明の主旨とは
直接関係がないので詳細な説明は省略してあるが
従来知られている技術で容易に実現可能であるこ
とは明らかであろう。

【図面の簡単な説明】

第１図ａ〜ｄは、本発明の一実施例における動
作を示すもので、第１図ａは、ページフオルトの
発生直前の主記憶上のページの状態を示すもので
ある。第１図ｂは、ページフオルト回数が規定最
大値を超えなかつた場合、第１図ｃは最大値をこ
えた場合におけるページフオルト後の状態を示
す。なお、第１図ｄは、ワーキングセツト見直し
後の状態を示す。第２図は、本発明における動作
を示すフロウチヤート、第３図は本発明の一実施
例の構成を示すブロツク図である。１はワーキングセツト枠管理ブロツク、２はペ
ージマツプ、３は空きプール制御ブロツク、４は
関連する制御回路を示す。

Claims

【特許請求の範囲】

１マルチプログラムで動作する情報処理装置に
おいて、ワーキングセツトを管理する単位である
ワーキングセツト枠（WS枠）は、次のワーキン
グセツト見直しまでの間にそのワーキングセツト
が保有することができるベージ数の最大値を保持
する手段をもち、ワーキングセツト見直しに際
し、各WS枠に対して次の見直し周期におけるワ
ーキングセツトへの期待値とともに前記ページ数
の最大値を求め、これを前記保持する手段に格納
するとともに、ページフオルト発生に際しては当
該ページフオルトを発生したWS枠に属するペー
ジ数が前記最大値を越えていない場合には、空き
ページプールからページを切出してこのWS枠に
付与し、前記最大値に達している場合には、その
WS枠からページを切出すことを特徴とするワー
キングセツト管理方式。