JPS6311704B2 - - Google Patents

Description

【発明の詳細な説明】 この発明は仮想記憶方式を採る電子計算機に係
り、その実記憶装置上からページを追出すための
論理を変更するページ追出方式に関する。

仮想記憶方式を採る電子計算機において、中央
処理装置がプログラムを実行するための高速な実
記憶装置は比較的小容量用意され、実際のプログ
ラムは大容量の外部記憶装置に格納されている。
従つて中央処理装置がプログラムを実行する時点
で実行対象となつたプログラムが既に実記憶装置
上に存在すれば、そのまま実行を継続できるが、
そのプログラムが実記憶装置上にないと、すなわ
ちプログラムの実行に必要な命令、またはある命
令の実行に必要なオペランドで指定されたデータ
がないとその部分を必要な時点で外部記憶装置か
ら実記憶装置へ呼込み、その後実行を再開させ
る。新らしく外部記憶装置からプログラムを呼込
むためには、通常は現在、実記憶装置上にある一
部を追出す必要がある。一般にプログラムの追出
しや呼込みは数Ｋバイト単位に行なわれ、この追
出しや呼込みの単位をページと呼ぶ（中央処理装
置の定める実記憶装置と外部記憶装置との間で読
出／書込できる単位をページと呼ぶこともある
が、本件では以下統一してプログラムの追出し、
呼込みの単位にページを使う）。また、中央処理
装置は実行に必要なプログラムの一部が実記憶装
置上にないとページフオルトと呼ばれる割出しが
発生し、このページフオルトを契機としてプログ
ラムの追出し、すなわちページアウトとプログラ
ムの呼込み、すなわちページインが行なわれる。
一般にページフオルトが発生すると実記憶装置と
外部記憶装置の間でプログラムが取り替えられる
ため、オペレーテイングシステムの処理時間が増
大する。そこでページイン／ページアウトを最小
回数とする目的でページイン／ページアウトに対
しLRU（Least Recantly Used）論理が利用され
ている。これは最近利用されたページが再び実行
対象となる場合が高いという仮定に基づいて、実
記憶装置上の最後に利用された時からの経過時間
が最も長いページの内容を追出す論理である。こ
のLRU論理を厳密に実施するためには、各ペー
ジに実行対象となつた時刻を記録し、実行の毎に
更新してゆき、追出す時最も古い時刻の記録され
たページ内容を追出せば良い。しかし実際にはタ
イマーを各ページに設けたり、時刻の管理をする
代りに実行対象となつた時に無条件にオンとする
１ビツトの参照表示と、さらにその実行対象がペ
ージ内書込の時であれば、その書込を表示する１
ビツトの書込表示により実現している。一定の契
機により例えばページフオルトの発生により、参
照表示と書込表示の付いているページはそれ等の
表示を消し、それ以前にそれ等の表示が消されて
いるページから優先的に追出す。この時、ページ
イン以後参照表示のみが付けられたページは同じ
内容が外部記憶装置上に存在するため単に新らし
いページをページインすることのみにより利用で
きるが、書込表示が過去に付いていたページは実
記憶装置上で更新されてしまつているので外部記
憶装置の内容をページアウトにより更新しなけれ
ばならない。このため同じ条件であれば参照表示
のみの付いていたページの追出しを優先する。以
上のページの状態別に各ページをキユーイングし
ておき、参照／書込の表示の消去とそれに伴う各
キユーの継ぎ変えとでLRU論理を近似している。

ところで、ページフオルトには実行対象となつ
た命令が実記憶装置上にない場合と実行対象とな
つた命令のオペランドで示されたデータが実記憶
装置上にない場合とがあるが、従来のLRU論理
ではこれらを区別をせず同一のページフオルトと
して扱つているため特にオペランドで示されたデ
ータの格納パターンに特徴のあるアプリケーシヨ
ンプログラムやユーザプログラムに対しては、ペ
ージの置換回数がかえつて増大する。

例えばフオートラン（FORTRAN）コンパイ
ラにより作成されたユーザプログラムによく見ら
れる例では数Ｋ〜数100Kのデータ領域を一方向
にサイクリツクに実行対象とすることを繰返え
す。

従つて一度参照されたデータのページは再び最
も参照されにくいページとなつてしまい、従来の
LRU論理ではページ置換回数が逆に増大してし
まう欠点があつた。この発明は以上の欠点を克服
することを目的とし、この目的は、仮想記憶方式
を採る電子計算機において、論理変更回路を設
け、その論理変更回路に基づいてページを追出す
ための論理を変更するもので、特に命令が実記憶
上にないためのページフオルトかオペランドで示
されたデータが実記憶上にないためのページフオ
ルトかの区別と実行中のプログラムのデータが利
用されているパターンとに基づきページ追出しの
ための論理を変更することにより達成される。以
下この発明を図により詳しく説明する。

第１図は仮想記憶方式の概念図であり、１は実
記憶装置、２は外部記憶装置、３は実記憶装置と
外部記憶装置の対応表である。処理対象となつた
プログラムは対応表３の中に順に登録され、各プ
ログラムのページ部分が実記憶上に存在する時は
その対応部である実記憶アドレス欄３ａに実記憶
装置のアドレスが書かれている。また、一方、該
テーブルの外部記憶アドレス欄３ｂには各プログ
ラムのページが外部記憶装置２のどこに書かれて
いるかの外部記憶装置中のアドレスがすべて書込
まれている。実記憶装置の容量は比較的少ないた
め実行対象となつたページ部分だけが実記憶装置
上に存在する。ページイン、ページアウトにより
対応表３の中の実記憶装置のアドレスが書込まれ
たり消されたりし、処理対象のプログラムの実行
が終ると外部記憶装置中に存在する処理対象プロ
グラムが対応表３から消去される。

第２図はページイン／ページアウトされる各ペ
ージ状態説明図であり、第３図はこの発明に基く
ページ追出し方式の一実施例構成図である。

第２図における六角形の各点は実記憶装置の各
ページが登録されるキユーのターミナルを示して
いる。各ページはいずれかのキユーターミナルに
順番に継ながれており、各ページの内容のページ
アウトまたは参照表示／書込表示の消去によりり
キユーターミナルが変更される。参照表示と書込
表示は中央処理装置がページ内容を実行した時点
で無条件に付加される。

AVはページフオルト解決用のページのターミ
ナルであり、ページアウトされたページが順に
“最後”に継ながれてゆく。HDはページインさ
れたページが継ながれてゆくキユーターミナル、
AC１は書込みのなかつたページのターミナル
AVへの候補用ターミナル、AC２は書込のあつ
たページのターミナルAVへの候補用ターミナ
ル、AC３は参照のあつたページのターミナル、
AC４は書込のあつたページのターミナルである。

第３図においてOSはオペレーテイングシステ
ム、TSCHはジヨブ管理プログラムであり、PF
はページフオルト割出処理回路、QX１はターミ
ナルAVのページをターミナルHDまたはAC３に
継ぎ換える回路、QX２はターミナルAC１、タ
ーミナルAC２の先頭のページを取出し他のター
ミナルに継ぎ換える回路、TQXはターミナル
HD、ターミナルAC３、ターミナルAC４のすべ
てのページをそのまま、即ちキユーイングされた
まま他のターミナルに継ぎ換える回路、Piはペー
ジイン回路、Poはページアウト回路、LXは論理
変更回路である。

実記憶装置上にないページ、すなわちターミナ
ルHD、ターミナルAC１〜AC４に継ながれてい
ないページが実行の対象となるとページフオルト
が発生し、ページフオルト回路PFが検出する。
この信号に基づいて継ぎ換回路QX１がまずター
ミナルAV中にあるページで要求される内容を持
つページを探し出し、あればそのページをターミ
ナルHDに移す。これはページアウトされたペー
ジもその実ページ上に他のページがページインさ
れる直前までは以前に書込まれた内容が残つてい
るので、利用する手法である。ターミナルAV中
に要求ページがなければ、継ぎ変換回路QX１は
ターミナルAVの先頭の実ページに外部記憶装置
中の要求されたページをページイン回路Piにて呼
込むと共にそのページをターミナルHDあるいは
AC３に継ぎ変える。この時、論理変更回路LXは
オペレーテイングシステムOS中の実行対象プロ
グラムを管理しているジヨブ管理プログラム
TSCHの表示を見てページ追出しの論理変更の必
要の有無を検査する。論理変更の表示がなければ
継ぎ換回路QX１はページインされたページをタ
ーミナルAVからはずし、ターミナルHDの“最
後”に継ぐ。論理変更の表示がジヨブ管理プログ
ラムTSCHにある時は、さらにページフオルト割
出回路PF中の命令によるページフオルトかオペ
ランドによるページフオルトかの表示を見、命令
によるページフオルトであればターミナルHDの
“最後”に継ぎ、オペランドによるページフオル
トであればターミナルAC３の“最初”に継ぐ。
ここでターミナルAVのページ数は一定値以上、
常に用意しておく必要があり、ページインのため
の利用可能なページ数、すなわちターミナルAV
のページ数が減少すると継ぎ換回路QX２，TQX
により以下の様にターミナルAVの登録ページを
追加する。ターミナルAVの利用可能なページ数
が一定値以上であればページフオルト割出処理回
路PFに終了通知を発信する。

継ぎ換回路QX２はターミナルAC１を見てタ
ーミナルAC１に実ページがあればその先頭の実
ページを１つ取出し、参照表示がなければターミ
ナルAVの最後に継ぎ、参照表示があればターミ
ナルAC３の最後に継ぎ、書込表示があればAC４
の最後後に継ぐ。但し、付いていた参照表示と書
込表示は継ぎ換回路QX２が継ぎ換える場合はす
べて継ぎ換えるとき消去してしまう。

継ぎ換回路QX２は、ターミナルAC１を見て
ターミナルAC１に実ページがあれば、ターミナ
ルAC１の先頭の実ページをターミナルAVの
“最後”に継ぐ、なければターミナルAC２を見て
ターミナルAC２に実ページがあればその先頭の
実ページを１つ取り出し参照表示があればターミ
ナルAC４の最後に継ぎ、参照表示がなければペ
ージアウト回路Poにてその内容を外部記憶装置
に更新し、ページアウトした実ページをターミナ
ルAVの最後に継ぐ。継ぎ換回路QX１はターミ
ナルAC１にもターミナルAC２にも実ページがな
いと継ぎ換回路TQXに実ページのターミナル変
更を発信する。継ぎ換回路TQXはターミナルAC
３の実ページをそのまますべてターミナルAC１
に、ターミナルAC４の実ページをそのまますべ
てターミナルAC２に、更にターミナルHDの実
ページをそのまますべてターミナルAC３に継ぎ
換え、継ぎ換回路QX２に実ページ群の継ぎ換え
終了を発信する。

継ぎ換回路QX２は再びターミナルAC１また
はターミナルAC２よりターミナルAVに上記補
給処理を繰返し、ターミナルAVに一定数以上の
実ページが継がれるまで、必要な都度継ぎ換回路
TQXを利用する。

継ぎ換回路QX２はターミナルAVの実ページ
数が所定の値に達するとその時点で継ぎ換えを終
了しページフオルト割出処理回路PFに終了通知
を発信する。継ぎ換回路QX１，QX２からペー
ジ処理の終了通知がページフオルト処理回路PF
に発信されるとページフオルト処理回路がオペレ
ーテイングシステムOSにページ処理の終了通知
を発信する。

また、上記中のページイン回路Piとページアウ
ト回路Poは第１図に示した対応表３への実ペー
ジの登録と消去とを実ページのページイン、ペー
ジアウトに対応して更新している。

以上の説明で継ぎ換回路QX１がページインさ
れた実ページを論理変更回路LXの指定によりタ
ーミナルAC３の“最初”に継ぐことにより、タ
ーミナルAVに追出される確率が高く、最近に利
用された実ページがターミナルAVに最も早く継
ぎ換えられる。これはMRU（Most Recantly
Used）論理を近似しているものである。

一方、継ぎ換回路Ｑ１がページインされた実ペ
ージを論理変更回路LXの指定がなければターミ
ナルHDの“最後”に継ぐことによりターミナル
AVに追出される確率が低く、最後に利用された
時からの経過時間の最も長い実ページがターミナ
ルAVに継ぎ換えられる。これはLRU論理を近似
しているものである。

以上の説明では論理変更回路LXは実行対象プ
ログラムの性格表示とオペランドによるページフ
オルトを条件としてLRU論理とMRU論理との変
更を行つたが、本発明の意図はこれに限られるも
のではなく、一つの実行対象プログラムが連続し
てページフオルトを頻発した場合等を条件として
ページを追出すための論理を変更することも可能
である。

以上説明した様にこの発明は仮想記憶方式を採
る電子計算機において、論理変更回路を設け、そ
の論理変更回路の判定するページフオルトの種
類、実行対象プログラムの性格等に基づいてペー
ジを追出すための論理を変更することによりペー
ジフオルトの多発を減少させることができた。特
にオペランドで示すデータへの読出／書込が一方
向にサイクリツクに実行される多数のアプリケー
シヨンプログラムやユーザプログラムにおいてこ
の効果が大きい。

【図面の簡単な説明】

第１図は仮想記憶方式の概念図であり、１は実
記憶装置、２は外部記憶装置、３は実記憶装置と
外部記憶装置の対応表である。 第２図は実記憶装置の各ページの状態説明図で
あり、AV，HD，AC１，AC２，AC３，AC４
はターミナルを示す。 第３図は本発明に基づくページ追出し方式の一
実設例構成図であり、PFはページフオルト割出
処理回路、QX１，QX２，TQXはページ継ぎ換
回路、Piはページイン回路、Poはページアウト
回路、LXは論理変更回路である。

Claims (1)

1. 【特許請求の範囲】 １ 必要最少限のプログラムを外部記憶装置から
   実記憶装置上に読出し、所定の処理を実行させ、
   プログラムの実行に必要な部分が実記憶装置上に
   ないこと示すページフオルト発生の場合に上記実
   記憶装置上の所定のページを追い出してプログラ
   ムの実行を継続させる仮想記憶方式にけるページ
   追い出し制御装置において、 複数のターミナルのいずれか１つのターミナル
   に実記憶装置上の各ページを使用状況に応じて登
   録するとともに、 ページフオルト解決用ターミナルAVに登録さ
   れているページの数が所定個数以下になつた場合
   には、書込みのなかつたページ故にページフオル
   ト解決用ターミナルAVへの候補ページのキユー
   のターミナルAC１に登録されているページをチ
   エツクし、参照表示がなければページフオルト解
   決用ターミナルAVの最後の登録ページに当該ペ
   ージを繋ぎ換え、参照表示があればページ参照の
   あつたページのキユーのターミナルAC３の最後
   の登録ページに当該ページを繋ぎ換え、書込表示
   があれば書込みのあつたページでページフオルト
   解決用ターミナルAVへの候補でないページのキ
   ユーのターミナルAC４の最後の登録ページに当
   該ページを繋ぎ換え、一方当該ターミナルAC１
   に実ページがない場合にはターミナルAC２をチ
   エツクし、参照表示付ページであれば上記ターミ
   ナルAC４に繋ぎ、参照表示がないページであれ
   ば、そのページの内容を外部記憶装置へ格納して
   該ページアウトした実ページを上記ターミナル
   AVの最後の登録ページに繋ぎ換える個別繋ぎ換
   え回路QX２、 ページインされた直後のページが登録されてい
   るホールドページターミナルHDから上記ページ
   参照のあつたページのキユーのターミナルAC３
   へと、ページ参照のアルゴリズムページのキユー
   のターミナルAC３からページフオルト解決用タ
   ーミナルAVへの候補ページのキユーのターミナ
   ルAC１へと、及び、書込みのあつたページでペ
   ージフオルト解決用ターミナルAVへの候補でな
   いページのキユーのターミナルAC４から書込み
   のあつたページでページフオルト解決用ターミナ
   ルAVへの候補ページのキユーのターミナルAC
   ２へと、当該ターミナルに接続されているページ
   のキユーをまとめて繋ぎ換える一括繋ぎ換え回路
   TQXとを備え、 命令によるページフオルト発生時には上記ペー
   ジフオルト解決用ターミナルAVのページをペー
   ジインされたページのキユーのターミナルHDの
   最後に繋ぎ、オペランドによるページフオルト発
   生時には上記ページフオルト解決用ターミナル
   AVのページを上記参照のあつたページのキユー
   のターミナルAC３の登録ページの最初に繋ぐよ
   う制御したことを特徴とするページの追い出し制
   御装置。