JPH0346043A - 実記憶割り当て方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔発明の利用分野〕 本発明は仮想記憶方式の計算機システムにおいて各仮想
ページに対する実記憶内の実ページの割り当て方法に係
わり、特に大容量の実記憶装置を有する計算機システム
に好適な実記憶割り当て方法に関する。

〔従来の技術〕

仮想ページに関する実ページの割り当てを管理する記憶
管理方法に関しては、特開昭５３−１１４３１８号、特
開昭５８−１７５８６号、特開昭６０−２０４０４８号
、特開昭６２−２７４３５１号記載の技術が知られてい
る。

まず、特開昭５３−１１４３１８号では記憶保のための
記憶キーの付与単位（実ページに相当）２”ＫＢ　（キ
ロバイト）の領域に対し仮想ページサイズが２”ＫＢで
ｍ≧ｎの範囲で可変であるような場合の高速アドレス変
換に関して論じられており、高速アドレス変換テーブル
エントリ長を拡張し２′″−０個のキーを格納可能な構
成にし、エントリ数を増やす事なくいずれの仮想ページ
サイズにおいても高速アドレス変換テーブル上に同数の
ページ数が登録可能としている。

この技術ではアドレス変換の効率に起因するシステムの
性能については考慮されているが、記憶保護のための記
憶キー設置単位による問題が考慮されておらず、キーの
付与が一番小さい単位毎に必要であり、実記憶容量の巨
大化に伴い記憶キー付与のためのキー記憶装置の容量が
巨大化し、しいては主記憶のアクセス性能が低下すると
言う問題がある。

すなわち、記憶キー付与数の低減が必要である。

また、特開昭５８−１７５８６号でも、仮想ページサイ
ズより実ページサイズが大きい場合の高速アドレス変換
テーブルの構造上の工夫に関して論じられているが前記
と同様の問題がある。

また、特開昭６０−２０４０４８号では、仮想記憶およ
び実記憶をあらかじめ複数の領域に分割し個々の領域で
は仮想ページサイズと実ページサイズが同一であるが、
異なる領域間ではこのページのサイズが異なっている。

実行するプログラムのメモリ利用特性に応じて各分割領
域上のページサイズとページ数をあらか′じめ決めてお
くことにより実記憶の有効活用とページの管理オーバヘ
ッドの削減を図っている。しかし、複数に分割された各
実記憶領域毎においては個々の領域の実ページと同一サ
イズの仮想ページのみ割り当て可能であり各実記憶領域
間の相互利用と言う点について考慮がされておらず、あ
るサイズの仮想ページに実記憶を割り当てようとしても
実記憶全体としては空き領域があるにもかかわらず仮想
ページと同サイズの実ページを持つ実記憶領域に空き領
域が無ければ割り当て不能となり、実記憶全体の効率的
な利用と言う面で問題がある。すなわち、異なるサイズ
の仮想ページと実ページの相互割り当てがなされていな
い。

また、特開昭６２−２７４３５１号では、実記憶上にセ
グメントサイズより大きな連続する空き領域が有ればセ
グメント単位に実記憶を割り当て、アドレス変換テーブ
ル上に記憶しておき、このような場合にはアドレス変換
の過程において実施される２つの変換単位、すなわちセ
グメント変換とページ変換の内、ページ変換を不要とす
ることによりアドレス変換の高速化、アドレス変換テー
ブルの容量削減を可能としている。

しかし、この技術はユーザプログラムからユーザの欲す
る任意のサイズで仮想記憶の確保、解放が成されると言
う点について考慮されておらず、たとえばセグメント単
位で実記憶を割り当てたとしても、ユーザプログラムか
らその内部を部分的に解放される′と仮想記憶、実記憶
上に虫食い状態の使用不可能領域が発生し利用効率が悪
い、また。

実記憶はセグメントより小さい単位の実ページに分割さ
れて各実ページは互いに独立して任意の仮想ページに割
り当てられるため連続した実記憶が空いてる確率は一般
的に非常に稀であると言う問題がある。

本発明の目的は異種サイズの仮想ページと実ページ間で
割り当てを可能とすることにより上記問題を解決する効
率的な記憶管理方法を提供することにある。

〔問題点を解決するための手段〕

上記目的達成のため本発明の記憶管理方式では、仮想ペ
ージサイズと記憶保護のためのキーの付与単位である実
ページサイズが異なる場合のページ割り当て方法として
、実ページサイズに対して仮想ページサイズが１　／　
ｎ倍（ｎは正整数）の場合割単位毎に仮想ページに割り
当てる。

また、実ページサイズに対して仮想ページサイズがｎ倍
（ｎは正整数）の場合には仮想ページサイズの整数倍の
アドレス有する実ページを先頭とする連続するｎヶの実
ページを捜し、−１この連続するｎヶを仮想ページ１ペ
ージに対応させることにより仮想ページサイズと異なる
ページサイズから構成される実記憶領域を仮想ページサ
イズ単位に割り当てる。また、実ページサイズに対して
仮想ページサイズが１　／　ｎ倍およびｎ倍のものが混
在する場合には、仮想ページと実ページのサイズの組み
合わせにより、前記の１　／　ｎ倍もしくはｎ倍の場合
のいづれかの方式でページ全開り当てる。

さらに、ページの使用頻度を調べる場合には、仮想ペー
ジサイズと実ページサイズの内大きい方のサイズを単位
としてページの使用頻度計」りを実施することにより前
記目的を達成する。

〔作用〕

（１）仮想ページサイズが実ページサイズより小さい場
合（１／　ｎ倍）、実ページ内部を１／ｎに分割し仮想
ページサイズ単位で割り当てることにより、仮想ページ
サイズに依存せずキー付与単位である実ページサイズを
大きくできる、したがって、実ページ数、キー記憶（第
１図の５）のエントリ（第１図の６）の数を少なくでき
、実記憶の増大にともなうキー記憶のエントリ数の巨大
化を抑止できる。

また、キー記憶エントリ数の巨大化抑止により、主記憶
のアクセス性能低下を抑えることができる。

さらに、この場合は、ページの使用頻度を調べる場合、
仮想ページサイズと実ページサイズの内大きい方のサイ
ズ、すなわち、実ページサイズを単位としてページの使
用頻度計測を実施することにより、計測ページ数を削減
でき、ページ計測に費やすオペレーティングシステムの
処理時間を短縮できる。

（２）仮想ページが実ページサイズのｎ倍の場合は、連
続するｎヶの実ページを仮想ページと同一のサイズを持
つ実ページ１ケと考え一つの仮想ページに割り当てる。

この場合は、仮想ページサイズを単位としてページの使
用頻度計測を実施することにより、計測ページ数を削減
でき、ページ計測に費やすオペレーティングシステムの
処理時間を短縮できる。

（３）仮想ページサイズが実ページサイズに対して１　
／　ｎ倍およびｎ倍のものが混在する場合には、仮想ペ
ージと実ページのサイズの組み合わせにより、上記の（
１）もしくは（２）を適応することにより異なるサイズ
の仮想／実ページ間の相互利用が可能となり効率のよい
実記憶の利用ができる。

〔実施例〕

以下、本発明の実施例を図面を参照して説明する。第１
の実施例では、第１図に示すように仮想記憶１１はサイ
ズ４ＫＢ　（キロバイト）の仮想ページ１２の群により
構成されている。実記憶１゜は実ページサイズの異なる
２つの領域２０．３０に分割されている。領域２ｏは４
ＫＢの実ページ２１の群より成り、以下この領域４ＫＢ
ページ領域と呼ぶ。領域３０は６４ＫＢの実ページ３１
の群より成り、以下この領域３０を６４ＫＢページ領域
と呼ぶ、以下に、詳述するように本実施例では６４ＫＢ
ページ領域３０を構成する各６４ＫＢページ３１を仮想
ページサイズに等しい４ＫＢの領域に分割し、各分割領
域を１つの仮想記憶に割り当てる所に特徴がある。

５は実記憶１０の各ページに対する記憶保護キーを保持
するためのキー記憶である。その各エントリ６には対応
する実ページに割り当てられた記憶保護キー（ＳＫ７）
　、そのページの参照の有無を示す参照ビット（Ｒ）８
．そのページが書き替えられたことを示すチェンビット
（ｃ）９を格納するエリエから戒る。キー記憶５の各エ
ントリ６は４ＫＢページ領域２０に対して従来と同様に
ページごと、すなわち、４ＫＢことに、６４ＫＢページ
領域３０に対しても同様にページごと、すなわち、６４
ＫＢごとに設置されている。すなわち、従来と同様に本
実施例でも実ページは記憶保護キ３０では実ページサイ
ズを４ＫＢから６４ＫＢに拡張されているので、４ＫＢ
ページ領域２０に比べ実記憶の単位容量当りのキー付与
数を１７１６に抑えキー記憶容量の増加を抑止している
。

第２図は、オペレーティングシステムに含まれるプログ
ラムおよび管理テーブルを示す。図において、２はその
うち実記憶割り当てプログラム、３はページ計測プログ
ラム、７はページアウトプログラムを示す。実記憶割り
当てプログラム２ではある仮想ページに対して、プログ
ラムから実記憶の割り当て要求があると仮想ページ単位
に実記憶の領域を割り当てる。この割り当てでは具体的
には実記憶より４ＫＢの空き領域を１つ選び出し割り当
てるべき仮想ページに対応するアドレス変換テーブルの
エントリ上に１選び出した実記憶領域のアドレスをセッ
トし仮想アドレスから実アドレスへの変換を可能とする
。すなわち、本発明でも従来と同様に仮想ページは仮ア
ドレスから実アドレスへのアドレス変換単位である。ペ
ージ計測プログラム３は実記憶上に割り当てられている
各仮想ページの使用頻度を計測するもので、実記憶の不
足状態に陥るとこの計測結果に従ってページアウトプロ
グラム７で使用頻度の低い仮想ページに割り当てられて
いる実記憶上の情報を順次、補助記憶にページアウトし
使用可能な実記憶を一定量確保する制御に用いられる６
図において、５０゜６０は実記憶の現在の割り当て状況
を管理するための実記憶管理テーブルである。４ＫＢ領
域理テーブル５０は仮想ページサイズと同じサイズの実
記憶領域、すなわち、４ＫＢ実ページの各々および各６
４ＫＢページの各分割領域に対応するエントリ５１を持
つ。各エントリには対応する実記憶内の４ＫＢ領域の割
り当て状況を示す情報を保持する。後に説明するように
この管理テーブル５０のエントリの内、仮想ページに未
だ割り当てられていない４ＫＢの実記憶領域に対応する
エントリのキュー（未割り当て４ＫＢ領域キユー７１０
（第４Ａ図））が形成される。７１はこのキューの先頭
エントリを示すポインタである。また、６４ＫＢ領域管
理テーブル６０は６４ＫＢページ領域３０内の６４ＫＢ
の実ページの各々に対応するエントリ６１を持つ。各エ
ントリは、対応する６４ＫＢページの割り当て状況を示
す情報を保持する。後に説明するようにこの管理テーブ
ル６０のエントリうち、仮想ページに未だ割り当てられ
ていない６４ＫＢの実記憶領域に対応するエントリのキ
ュー（未割り当て６４ＫＢ領域キユー７２０（第４Ｂ図
）が形成される。７２はこのキューの先頭エントリを示
すポインタである。また、１００はプログラム（ジョブ
）ごとに設けたジョブ管理テーブルである。この管理テ
ーブルには、後述するように、各ジョブが使用中の仮想
ページに割り当てられた４ＫＢ実ページに対応するテー
ブル５０内のエントリキュー（割り当て済み４ＫＢペー
ジキユー８１０（第５Ａ図））が形成される。８１はこ
のキューの先頭エントリを示すポインタである。また、
後述するように、各ジョブが使用中の仮想ページに割り
当てられた分割領域に対応するテーブル５０内のエント
リキュー（Ｉ’ｌｌり当て済み分割領域キュー８２０（
第５Ｂ図）が形威される。８２はこのキューの先頭エン
トリを示すポインタである。また、各ジョブについて各
ジョブが使用中の６４ＫＢ実ページの内、一部の分割領
域が未割り当てであるものに対するテーブル６０のエン
トリのキュー（部分未開り当て６４ＫＢページキユー９
１０（第５Ｃ図））が形成される。９１はこのキューの
先頭エントリを示すポインタである。また、各ジョブに
ついて、各ジョブが使用中の６４ＫＢ実ページの内、そ
の全ての分割領域が割り当て済であるものに対するテー
ブル６０のエントリキュー（全割り当て済６４ＫＢペー
ジキュー９２０（第５０図））が形成される。

９２はこのキューの先頭エントリを示すポインタである
。

第３Ａ図は４ＫＢ領域管理テーブル５０の１つのエント
リ５１内の情報を示す図である。このエントリ５１は実
記憶１０の各４ＫＢの領域毎に設けられている。フィー
ルド９１Ａには実記憶のエントリに対応する４ＫＢの領
域に割り当てられた仮想ページの仮想アドレスがセット
され、フィールド９２Ａにはその仮想ページを使用して
いるジョブの識別子が（ジョブＩＤ）がセットされる。

フィールド９３Ａには、実記憶の対応する４ＫＢ領域が
最近に使用されてから現在に至るまでの時間（未使用時
間）がセットされている。なお、６ＫＢの実ページ内を
分割した４ＫＢ領域に対応するエントリ５１にはセット
不要である。フィールド９４Ａ、９５Ａには、そのエン
トリがテーブル５０内の他のエントリとキューイングさ
れるときに使用されるもので、フィールド９４Ａには、
そのエントリの次につながるべきエントリのアドレス（
フォワードポインタ（ＦＷＰＩ））がセットされ、フィ
ールド９５Ａには、そのエントリの前つながっているエ
ントリのアドレス（バックワードポインタ（ＢＷＰＩ）
）がセットされる。

第３Ｂ図は６４ＫＢ領域管理テーブル６０の工つのエン
トリ６１内の情報を示す図である。このエントリ６１は
実記憶１０の各６４ＫＢの実ページに対応して設けられ
る。フィールド９１Ｂ。

９２Ｂ、９３Ｂ、９４Ｂ、９５Ｂはそれぞれの第３Ａ図
のフィールド９１Ａ、９２Ａ、９３Ａ。

９４Ａ、９５Ａと同じ意味の情報がセットされる。

フィールド９６には、そのエントリに対応する６４ＫＢ
ページ内の１６個の分割領域の内、仮想ページに末割り
当ての分割領域数がセットされる。

フィールド９７には、対応する６４ＫＢ実ページ内の分
割領域が最初に使用された時に分割領域に割り当てた仮
想ページの持つ記憶保護キーがセットされる。この記憶
キーは後述するように６４ＫＢ実ページ内に割り当てる
１６個の仮想ページの記憶キーが矛盾しないで同一とな
るよう制御に使用する。フィールド９７．９８はそのエ
ントリに対応する６４ＫＢページ内の１６個の分割領域
に対する４ＫＢ領域管理テーブル５０内のエントリ５１
のキューを形成するときに使用される。

第４Ａ図は４ＫＢ未割当領域キュー７１０を示す。この
キューは実記憶１０の各４ＫＢ領域の内。

仮想ページが割りあてられていない領域に対するテーブ
ル５０のエントリ５１Ａの群をポインタにより連ねて構
成される。実記憶の４ＫＢの未割当領域に対する各エン
トリ５’ｌＡ内のフォワードポインタ（ＦＷＰＩ）は後
続の未割当の４ＫＢ領域に対応するエントリ５１Ａのア
ドレスがセットされ、そのエントリ５１．Ａ内のバック
ワードポインタ（ＢＷＰＩ）には、先行する未割当の４
　Ｋ　Ｂ　Ｍ域に対する他のエントリ５１Ａのアドレス
セットされている。さらに４ＫＢ未割当領域キューポイ
ンタ内にはこのエントリ列の内、先頭にあるエントリの
アドレスおよび末尾のエントリのアドレスをそれぞれフ
ォワードポインタ７１Ａ、バックワードポインタ７１Ｂ
としてセットされている。こうしてキュー７１０が形成
される。なお、このようなエントリ５１Ａがない場合に
はポインタ７１Ａ、７１ＢにはＯがセットされる。この
ことは他のキューについても同様である。

ポインタ７１につらなるエントリ５１Ａの列をたどるこ
とにより、未割当の４ＫＢ領域がいずれであるかを判定
できる。

第４Ｂ図は、６４ＫＢ未割当ページキュー７２０を示す
、このキューは、実記憶１０の６４ＫＢページの内、ど
の分割領域も仮想ページに割当てされていないものに対
する、テーブル６０のエントリ６１Ｂの列およびそれぞ
れの６４ＫＢページ内の１６個の分割領域に対するテー
ブル５０のエントリ５１Ｂの列からなる。すなわち未割
当の６４ＫＢページに対するテーブル６０のエントリ６
１Ｂのフォワードポイント（ＦＷＰ２）、バックワード
ポインタ（ＢＷＰ２）には、それにつづく、未割当の６
４ＫＢページに対するエントリ６１Ｂのアドレスおよび
それに先行する未割当の６４ＫＢページに対するエント
リ６１Ｂのアドレスがそれぞれセットされる。エントリ
５１Ｂの列の先頭のエントリおよび末尾のエントリのア
ドレスがそれぞれ、キューポインタ７２内に、フォワー
ドポインタ、バックワードポインタとしてセットされる
。こうしてキュー７２０が形成される。

さらに、未割当の６４ＫＢページに含まれる１６個分割
領域に対するテーブル５０のエントリ５１Ｂのフォワー
ドポインタ（ＦＷＰＩ）とバックワードポインタ（ＢＷ
ＰＩ）には、同じ６４ＫＢページ内の、後続の分割領域
に対する、テーブル５０のエントリ５１Ｂのアドレスお
よび同じ６４ＫＢページ内の先行する分割領域に対する
、テーブル５０のエントリ５１Ｂのアドレスがそれぞれ
セットされることにより、同じ６４ＫＢページに属する
エントリ５１Ｂの列が形成される。この６４ＫＢページ
に対する、テーブル６０内のエントリ６１Ｂ内の内部フ
ォワードポインタ（Ｆ）および内部バックワードポイン
タ（Ｌ）には、そのようなエントリ５１の列の先頭のエ
ントリ５１Ｂおよび末尾のエントリ５１Ｂのアドレスが
セットされている。

第５Ａ図はあるジョブに対する割当済４ＫＢページキユ
ー８１０に示す。キュー８１０はそのジョブに割当済み
の４ＫＢ実ページに対するテーブル５０のエントリ５１
Ｃの列とキューポインタ８１にて形成される。これらの
エントリの接続は未割当４ＫＢ領域キユー７１０（第４
Ａ図）の場合と同じである。

第５Ｂ図は、あるジョブに対する割当済分割領域キュー
８２０を示す。

このキュー８２０は、そのジョブに割当て済の介在領域
に対するテーブル５０のエントリ５１Ｄの列をキューポ
インタ８２とからなる。第５Ｃ図はあるジョブに対する
部分割り当て済み６４ＫＢページキユー９１０を示す。

このキューはそのジョブに一部の分割領域が割当て済み
であるが、他の一部の分割領域が未割当である６４にＢ
ページに対するテーブル６０のエントリ６１Ｅの列をそ
れぞれのページ内の未割当の分割領域に対するテーブル
５０のエントリ５１Ｅの列とキューポインタ９工とから
形成される。これらのエントリ６１Ｅ、５１Ｅの接続は
未割当６４ＫＢベージキユー８１０（第４Ｂ図）の場合
と同様である。

なお、ジョブ管理テーブル１００内の、６４ＫＢ部分使
用ページキューポインタ１０２には、これらのエントリ
６１の列の先頭のエントリおよび末尾のエントリのアド
レスがそれぞれフォワードポインタ１０２Ａ、バックワ
ードポインタ１０２Ｂとしてセットされる。このキュー
９１０からあるジョブが使用している６４ＫＢページの
内、未割当ての分割領域を容易に検出できる。

第５Ａ図〜第５Ｃ図に示したキュー８１０゜８２０．９
１０は他のジョブに対しても同様に設けられている。そ
れらは簡単化のために図示されていない。

第５Ｄ図は、あるジョブに対する全割り当て済み６４Ｋ
Ｂページ、９２０を示す。このキューは、そのジョブに
割り当てられている、６４ＫＢページのうち、その分割
領域が全て割り当て済みである（全てが使用済みである
）６４ＫＢページを対象に、それに対応するテーブル６
０のエントリ６１Ｆの列から形成される。このキュー９
２０は、後で述べるページ計測プログラム３により使用
される。また、このキュー９２０は、前記部分割り当て
済みキュー３１０とは異なり、全ての分割領域が使用済
みであるため、それら分割領域に対するテーブル５０の
エントリ列は接続されない。これら分割領域に対するエ
ントリは、前記の通り割り当て済み分割領域キュー８２
０に接続されている。

次に実記憶割り当てプログラム２の動作を説明する。

第６図はページ割り当てプログラム２の概略フローを示
す図である。

あるプログラム（ジョブ）の実行中に仮想記憶上のある
領域をアクセスしたとき、その仮想領域に対応する実記
憶領域が割り当てられていない場合に、ページフォルト
割り込みが発生し、これを契機に仮想領域に実記憶領域
を仮想ページ単位に割り当てるための実記憶割り当て要
求がおこり、実記憶割り当てプログラム２が起動される
。実記憶割り当てプログラム２が起動されると、まず実
記憶領域選定ステップ２００で割り当てるべき実記憶上
の領域を選定する。

本実施例では割り当てるべき実記憶が属する領域が４Ｋ
Ｂページ領域２０又は、６４ＫＥベージ領域３０のいず
れかにあらかじめ指定されている場合にはその指定領域
を選定し、その他の場合には、まず６４ＫＢページ領域
３０を選定する。後に説明するようにこの領域３０内の
未割り当ての４ＫＢ領域を捜し、これが見つからない場
合には４ＫＢページ領域２０内の実記憶を割り当てるよ
うになっている。実記憶領域選定ステップ２００により
６４ＫＢページ領域３０が選ばれると、要求元ジョブ割
り当て済み６４ＫＢページ内サーチ２１０を実施する。

この処理は６４ＫＢページ内を分割使用した場合に生じ
る６４ＫＢページ内の部分未刈り当て分割領域を利用す
るための工夫であり、要求元ジョブに概に部分的に割り
当て済みの６４ＫＢページ内の未割り当て分割領域を優
先してそのジョブに割り当てるい ジョブからの実記憶割り当ての要求がそのジョブから最
初に出された場合、そのジョブに対して部分的に未割り
当ての６４ＫＢページは存在しない。

従って、サーチ２１０は失敗するのでこのサーチ２１０
については後に説明する。サーチ２１０で部分的に未割
り当てのページが見つからなければ、次に未割り当て６
４ＫＢページサーチ２３０を実施し、未割り当て６４Ｋ
Ｂ内の一つの分割領域を割り当てる。すなわち、未割り
当て６４ＫＢページキユー７２０（第４Ｂ図）を用いて
、そのジョブに割り当てるべき未使用の６４ＫＢページ
を見つける。このために、まずステップ２３１でこのキ
ュー７２０のポインタ７２を取り出し、ステップ２３２
でポインタ値のゼロ判定を行いこのポインタに接続され
たエントリ６１Ｂの有無を調べる。

キューポインタ７２がゼロでなければ、ステップ２３３
にてそれに連なるキュー７２０の先頭のエントリ６１Ｂ
を取り出す。そのエントリ６１Ｂに連なる１６個の分割
領域に対するエントリ５１Ｂの列の先頭のエントリを選
択しそれに対応する分割領域を割り当て対象とする。次
に、ステップ２３４Ａで管理テーブルエントリおよびキ
ューの更新を行う。すなわち、エントリ６１Ｂの内部フ
ォワードポインタ（Ｆ）（第３Ｂ図）で示されるエント
リ６１Ｂに連なるエントリ５１Ｂを選択し、そのフィー
ルド９１Ａ、９２Ａ、（第３図Ａ）に割り当て対象とな
った仮想ページのアドレスと割り当て要求元のジョブの
ＩＤをセットし、選択したエントリ６１Ｂ内の割り当て
済み分割領域数９６を＋１しくその初期値はＯである）
、フィールド９２ＢにそのジョブのジョブＩＤをセット
する。

次に、キューの更新を以下のように行う。即ち、未割り
当て６４ＫＢページキユー７２０から（第４Ｂ図）上記
選択されたエントリ６１Ｂおよびこれに連なる１６個の
エントリ５１Ｂをはずし、このエントリ６１Ｂおよび上
記１６個のエントリ５１Ｂの中の、上記選択されたエン
トリ５１Ｂ以外の１５個（未割り当ての分割領域に対す
るテーブル５０のエントリ）をそのジョブに対して設け
られた部分割り当て済み６４ＫＢページキユー９１０（
第５Ｃ＠）に接続する。さらに、上記選択されたエント
リ５１Ｂをそのジョブに対して段別られた割り当て済み
分割領域キュー８２０（第５Ｂ図）に接続する。

次に、ステップ２３６Ａにて割り当て対象となった仮想
ページに指定されている記憶キー（ジョブから明示的に
指定されていない場合は、そのジョブのその時点のプロ
グラムキー値）をフィールド９７にセットし、割り当て
対象となった分割領域の含まれる６４ＫＢ実ページに対
応するキー記憶５（第工図）のエントリ６にフィールド
９７にセットした値と同じキー値をセットする。なお、
この６４ＫＢ実ページのアドレスは選択されたエントリ
６１Ｂがテーブル６０中の何番目のエントリであるか（
すなわち、それに対応して定まるこのエントリ６１Ｂの
テーブルインデイクスがそのまま実ページのページアド
レスをページ番号で示す）から決定することができる。

この６４ＫＢ実ページアドレスに基づいてハードウェア
命令を用いて上記記憶キーを書き込む。また、この記憶
キーの書き込みは未割り当て６４ＫＢページ内から分割
領域を最初に割り当てる場合のみ実施するのは前述の通
りである。

次に、ステップ２４０により、実記憶割り当てが要求さ
れた仮想ページに対応するアドレス変換テーブル内のエ
ントリに選択した分割領域の実アドレスのセットとこの
エントリのバリデーシコンを実施する。こうしてこの実
記憶領域が使用可能となる。こうして、未割り当ての６
４ＫＢページ内の最初の分割領域の割り当てが終了する
。

以上の処理における、サーチ２３０においてキューポイ
ンタ（７２）がゼロであれば未割り当ての６４ＫＢペー
ジは無しと判断し４ＫＢページの選択処理２６０にて実
記憶１０の４ＫＢ実ページ領域２０内の未割り当ての一
つの実ページを割り当てるべき実記憶領域として選択す
る。

この選択は、未割り当て４ＫＢベージキユー７１０（第
４Ａ図）に接続されたーっのエントリ５１Ａを選択する
ことにより行われる。次にステップ２３４Ｂにおいて、
この選択されたエントリ５１Ａ内に割り当て要求元のジ
ョブのＩＤおよび割り当て対象の仮想ページのアドレス
を書き込む。

さらに、このエントリ５１Ａを上記キュー７１０よりは
ずし、そのジョブに対して設けられた割り当て済４ＫＢ
ページキュー８１０（第５Ａ図）に接続する。その後、
ステップ２３６Ｂにおいて記憶キーのセットをステップ
２３６Ａと同様に行い。

ステップ２４０においてアドレス変換テーブルの書き換
えを先に述べたのと同じように行う。こうして４ＫＢ実
ページへの割り当てが終了する。その後、仮想ページに
対する新たな実記憶割り当て要求がなされる毎に同じよ
うに処理される。この際、先に詳細を省略した要求元ジ
ョブ割り当て済み６４ＫＢページサーチ２１０も実行さ
れる。以下、その詳細を述べる。

すなわち、ステップ２１１においてそのジョブに対する
部分未開り当て６４ＫＢベージキユー９１０（第５Ｃ図
）のキューポインタ９１を読み出し、ステップ２１２で
その値がゼロか否かを判断しポインタ９１の値がゼロで
あれば部分未開り当ての６４ＫＢページは無いと判断し
、前述の未割り当て６４ＫＢページサーチ２３０に移る
。

ポインタ９１がゼロでなければ、ステップ２１３でこの
キューポインタ９１に接続された先頭のエントリ６１Ｅ
を選択し、次にステップ２２０でその先頭のエントリ６
１Ｅの記憶キー９７（第３Ｂ図）と割り当て対象仮想ペ
ージの記憶キーとを比較し、一致すれば割り当て可能と
判断する。これが不一致であればステップ２２１でその
先頭エントリ６１Ｅ内のフォワードポインタＦＷＰ　２
（第５Ｃ図）を取り出しこれを新たなポインタとして、
ステップ２１２から２２１を後続のエントリ６１Ｅ内の
フォワードポインタＦＷＰ２がゼロとなるか、前記ステ
ップ２２０で記憶キーが一致するエントリ６１Ｅが見つ
かるまで繰り返す。このページキュー９１０にて示され
る６４ＫＢページはいずれも、今回のページ割り当て要
求元ジョブに一部の部分領域が割り当て済みである。今
回のページ割り当て対象仮想ページの記憶キーと一致す
る記憶キーを持つ６４Ｂ実ページがその部分割り当て済
みページキュー中に有れば、その部分割り当て済み６４
Ｂページ内の一つの分割領域を割り当てるべき実記憶領
域として選択する。このようにすれば６４ＫＢ実ページ
に対して１つのキー記憶エントリしか与えられない状態
においても、そのページを分割領域に分けてジョブに割
り当てても不都合が生じない。さて、上記のようにして
ステップ２２０において部分割り当て済み６４ＫＢペー
ジキユー９１０の−っのエントリ６１Ｅ内の記憶キーが
一致する場合には、ステップ２３４Ｃにてそのエントリ
およびキューの更新を行う。

すなわち、そのエントリ６１Ｅに接続されていた未使用
分割領域のエントリ５１Ｅを−っ選択し。

このエントリに対応する分割領域を割り当て領域とすべ
く、この選択されたエントリ５１ＨにそのジョブＩＤお
よび割り当て対処となった仮想ページのアドレスをセッ
トする。さらに、上記エントリ６１Ｅ内の割り当て済み
分割領域数９６を＋１する。

上記エントリ５１Ｅを上記キュー９１０からはずし、そ
のジョブに対して設けられている割り当て済み分割領域
キュー８２０に接続する。もし。

上記更新後の割り当て済み分割領域数が１６に等しいと
きは、割り当て対象となった分割領域を含む６４ＫＢ実
ページは未割り当ての分割領域がなくなったことになる
。したがって、この時には、この６４ＫＢ実ページに対
応する前記エントリ６１Ｅもキュー９１０からはずし、
全割り当て済みキュー９２０（第５Ｄ図）にエントリ６
１Ｆとして接続する。

こうして、ステップ２３４Ｃが終了するとその後ステッ
プ２４０が前と同様になされる。以上の処理を実ページ
割り当て要求がなされるたびに繰り返せばよい。こうし
て、仮想ページサイズは従来通りの４ＫＢのまま、実ペ
ージサイズのみを拡張した場合についても、キー記憶５
（第１図）上のエントリ６を６４ＫＢの実ページに対し
て１つしか設けずに、かつ実記憶に空きを生じないで実
記憶領域を仮想ページに割り当てることができる。

次にページ計測プログラム３（第２図）の動作を説明す
る。第７Ａ、７Ｂ図はページ計測プログラム３の概略フ
ローを示す図である。

点線で示したステップ３７０〜３８０は本ケースの実施
例では使用せず、後で述べる第２の実施例で用いる。

ページ計測プログラム３の動作説明の前にページ計測の
目的について少し述べておく、ページ計測とは、実記憶
不足時にページアウトすべきページを決定するために、
実行中の個々のジョブが一定のＣＰＵを使用するつど各
ジョブに割り当てられているページの使用頻度を前もっ
て調べておく処理である。したがって１本ページ計測プ
ログラム３はある時間インターバルで起動される。

本実施例におけるページ計測処理は、仮想ページとそれ
に割り当てられた実記憶が属する実ページサイズが異な
る場合、その仮想ページと実ページのサイズの大きい方
の領域毎にページ計測を行う所にある。

すなわち、６４ＫＢページがいくつかの仮想ページに割
り当てられている場合、その実ページの１６個の分割領
域のいずれかが使用された場合、その実ページが使用さ
れたものとしてページ計測を行う、すなわち、６４ＫＢ
ページ領域３０上に割り当てられている４ＫＢ仮想ペー
ジに対しては、割り当て済み分割領域キュー８２０（第
５Ｂ図）を使用せず、部分割り当て済み６〜４ＫＢペー
ジキユー９１０（第５ｃ図）、および全割り当て済み６
４　ＫＢ／＜−ジ’ｌｒユ　９２０（第５Ｄ図）を用い
てこれらキューに接続されているテーブル６ｏのエント
リ６１単位に、すなわち、６４に’Ｂ単位にページ計測
を実施する。

以下、詳細を説明する。第７Ａ図に示すように、ステッ
プ３１０でページ計測すべきジョブに対して設けられた
全割り当て済み６４ＫＢページキユー９２０（第５Ｄ図
〉の先頭ポインタ９２を変数ＱＵＥＵＥにセットし、ス
テップ３２０で内部サブルーチンＳＵＢ　１をコールす
る。

このキュー９２０は４ＫＢの仮想ページが割り当てられ
ている６４ＫＢ実ページに対するテーブル６０のエント
リを表すキューの一つで前述の６４ＫＢ実ページ内の全
分割領域が割り当て済みの６４ＫＢページを表す。サブ
ルーティン５ＵＢ１はコールされると、ステップ５１０
において、変数ＱＵＥＵＥの値がゼロか否かによりペー
ジ計測すべきエントリ６１Ｆがあるか否かを調べる。

次にエントリがある場合にはステップ４４０にょり変数
ＱＵＥＵＥで指されるエントリ６１Ｆに対応する６４Ｋ
Ｂ実ページの使用の有無を調べる。

これは、ハードウェア命令により第１図に示すキー記憶
エントリ６上の参照ビット（Ｒ７）を読み出すことによ
り行う。参照ビットＲ７は当該キー記憶エントリに対応
するページがアクセスされるとハードウェアによりセッ
トされ、前記ハードウェア命令により命令実行後リセッ
トされる。これらのビットがゼロであれば当該ページは
、前回のページ計測時点から今回のページ計測までの間
使用されなかったことが分かる。次に、当該ページが使
用されていれば、ステップ４５０において不参照期間数
９３Ａ（第３Ｂ図）をクリアしく不参照期間数９３Ａを
ゼロにする）、ステップ４６０で当該エントリ６１Ｆを
当該キュー（ＳＵＢＩがコールされたとき変数ＱＵＥＵ
Ｅにキューポインタをセットしたキュー、この場合はキ
ュー９２０（第５Ｄ図））の最終位置に移動する。この
エントリの移動は、不参照期間数９３Ａの大きい順にキ
ューを構成するためである。こうすることにより、後に
述べるページアウトプログラム７では、キューの先頭か
ら順次ページアウトすれば自動的に使用頻度の小さいも
のよりページアウトできる。

次に、当該ページが使用されていなければステップ４７
０において不参照期間数をカウントアツプする。このよ
うに、ページの使用頻度はページ計測インターバル毎に
そのページが使用されていない場合に不参照期間数をカ
ウントアツプし、使用されていた場合には不参照期間数
をゼロにするため、この不参照期間数が大きいほど使用
頻度が低いことを示す。

次にステップ４８０により変数ＱＵＥＵＥに現在処理し
ているエントリ６１Ｆ内のフォワードポインタ（ＦＷＰ
２）９４Ｂをセットし、新たなエントリ６１Ｆに対して
今まで述べてきたステップ５１０〜４８０の処理を変数
ＱＵＥＵＥの値がゼロすなわちキュー９２０に接続され
た全てのエントリ６１Ｆを処理し終わるまで繰り返す。

以上で、６４ＫＢページ領域３０上に割り当てられてい
る４ＫＢ仮想ページの内、全割り当て済み６４ＫＢペー
ジキユー９２０（第５Ｄ図）に接続されているものにつ
いて６４ＫＢ単位にページ計測を実施した。

次に、６４ＫＢページ領域３０上に割り当てられている
４ＫＢ仮想ページの内、もう一つの部分割り当て済み６
４ＫＢページキユー９１０（第５Ｃ図）に接続されてい
るものについて、６４ＫＢ単位にページ計測を実施する
ため、第７Ａ図に示すように、ステップ３３０で変数Ｑ
ＵＥＵＥこのキューの先頭エントリ６１Ｅを示すポイン
タ９１をセットしステップ３４０で内部サブルーチン５
ＵＢＩをコールする。サブルーチン５ＵＢＩは、前記キ
ュー９１０に接続されているエントリ６１Ｅを対象とし
て先はど説明したステップ５↓Ｏ〜４８０の処理を繰り
返すことにより当該キュー上に接続されるエントリ６１
Ｅに対するページ計測処理を６４ＫＢ単位に行う。以上
で６４ＫＢページ領域３０上に割り当てられている、当
該ジョブのページ計測が終了する。次に、４ＫＢページ
領域２０上に割り当てられている４ＫＢ仮想ページに対
してページ計測を実施する。この場合には、ページ計測
処理は４ＫＢ単位に実施する。４ＫＢページ領域２０上
に割り当てられている４ＫＢ仮想ページは全て、割り当
て済み４ＫＢページキユー８１０（第５Ａ図）に接続さ
れている。この場合も、前記同様にステップ３９０で変
数ＱＵＥＵＥにこのキューの先頭エントリ５１Ｃを示す
ポインタ８１をセットしステップ４００で内部サブルー
チン５ＵＢＩをコールする。サブルーチン５ＵＢ１は、
前記キュー８１０に接続されているエントリ５１Ｃを対
象として前記同様にステップ５１０〜４８０の処理を繰
り返すことにより当該キュー上に接続されるエントリ５
１Ｃに対するページ計測処理を４ＫＢ単位に行う６以上
の処理を実行中のジョブがＣＰＵをある一定時間使用す
るつと実施すればよい。こうして、仮想ページサイズは
従来通りの４ＫＢのままで、ページ計測処理はその仮想
ページに割り当てられた実記憶の実ページサイズ単位に
実施することができ、ページ計測数を低減することがで
きる。

次にページアウトプログラム７（第２図）の動作を説明
する。第１３Ａ、１３Ｂ図はページアウトプログラム７
の概略フローを示す図である。本実施例におけるページ
アウト処理は、仮想ページとそれに割り当てられた実記
憶が属する実ページサイズが異なる場合、その仮想ペー
ジと実ページのサイズの大きいほうのサイズ単位ページ
アウトを行う所にある。すなわち、６４ＫＢページ領域
３０内の同一６４ＫＢ実ページ上の１６個の分割領域に
割り当てられている仮想ページ群を一括してページアウ
ト処理する。こうすることにより１１０回線を低減する
ことができる。以下、第１３Ａ図、１３Ｂ図により、ペ
ージアウト処理の詳細を述べる。本ページアウトプログ
ラム７は実記憶の使用可能な領域が、ある一定量以下に
なると起動され、また、不参照期間数があらかじめ定め
られたｎ以上のページをＮ、Ｐ　Ａ　Ｇ　Ｅ個ページア
ウトするべく起動されるものとする。ページアウトプロ
グラム７は起動されると、まず、ステップ５００でペー
ジアウトしたページ数をカウントする変数、ＰＯＵＴを
Ｏにする。次に、ステップ５１０でページアウトすべき
ジョブに対して設けられた部分割り当て済み６４ＫＢペ
ージキユー９１０（第５Ｂ図）の先頭ポインタ９１を変
数ＲＰＮにセットし、ステップ５１１で６４ＫＢページ
領域３０上に割り当てられているページのキューである
ことを示すために変数ＥＸに１をセットし、ステップ５
１２で内部サブルーチンＯＵＴをコールする。サブルー
ティンＯＵＴはコールされると、ステップ６００におい
て、変数ＲＰＮの値がゼロか否かによりページアウトす
べきエントリ６１Ｅがあるか否かを調べ、エントリが無
ければ、何もせずリターンする。次にエントリがある場
合にはステップ６１０により当該エントリ６１Ｅの不参
照期間数がページアウトプログラム起動時に指示された
ｎ以上かを調べる。ｎ以下であれば、ページ計測プログ
ラム３で述べたように各エントリは不参照期間数が大き
い順に並んでいるため以降のエントリ６１Ｅもｎ以下で
あり、当該キューには今回のページアウト起動条件を満
たすページが無いためリターンする。

ｎ以上であれば、次にステップ６２０でページアウトし
て良いページかどうかを調べる。これは、そのページの
ページアウトが禁止されている（ページ固定されている
）とか、既に前回のページアウト処理でページアウト中
であると言った従来からのチエツクで、仮想記憶方式の
計算機において通常酸されているチエツクである。ペー
ジアウト不可であれば、キューに接続された次のページ
を処理するため、ステップ６８０で変数ＰＲＮに当該エ
ントリ６１Ｈのフォワードポインタ９４Ｂをセットしス
テップ６００からの処理を繰り返す。

ステップ６２０でページアウト可能なページが見つかれ
ば、次にステップ６３０で変数ＥＸの値を調べる。この
場合はＥＸに１がセットされており６４ＫＢ単位の処理
であると判断し、ステップ６４０に進む。ステップ６４
０では当該エントリ６１Ｅ上に含まれる１６個の分割領
域を全てページアウトしく但し当該エントリ６１Ｅの対
応するキー記憶上のチェンジビットＣ（第８図５）がｏ
ｆｆの場合はページアウトは行わない）、各分割領域に
割り当てられていた仮想ページに対応するアドレス変換
テーブルのエントリを無効とする。

次に、ステップ６５０で前記各分割領域に対応するエン
トリ５１Ｅを部分割り当て済み６４ＫＢページキユー９
１０から全てはずし、当該エントリ６１Ｅ上のキューポ
インタ９８．９９　（第３Ｂ図）テ管理される６４ＫＢ
ペ一ジ内部のキューへ接続し、割り当て済み分割領域数
９６（第３Ｂ図）をＯにセットし、さらに、エントリ６
１Ｅを未割り当て６４ＫＢページキユー７２０（第４Ｂ
図）に接続する。次に、ステップ６６０でページアウト
数を示す変数ＰＯＵＴを工６増し、ステップ６７０でＰ
ＯＵＴがページアウトすべき個数に達したか否かをチエ
ツクするため変数ＮＰＡＧＥと比較する。ページアウト
数がＮＰＡＧＥ未満であれば、つぎにステップ６８０で
変数ＲＰＮに当該エントリ６１Ｅのフォワードポインタ
９４Ｂをセットしステップ６００からの処理を繰り返す
。以上の処理をステップ６００で当該キューの全エント
リ６１Ｅを処理し終わるか、ステップ６１０で起動時の
条件以上の不参照期間数を持つエントリ６１Ｅが現れる
まで、もしくは、ステップ６７０で所定のページ数（Ｎ
ＰＡＧＥ）をページアウトするまで繰り返す。以上で、
６４ＫＢページ領域３０上に割り当てられている４ＫＢ
仮想ページの内、部分割り当て済み６４ＫＢページキユ
ー９１０（第５Ｃ図）に接続されているものについて６
４ＫＢ単位にページアウトを実施しサブルーチンＯＵＴ
がリターンする。次に、第１３Ａ図のステップ５２０で
所定のページ数（ＮＰＡＧＥ）をページアウト出来た′
かどうかを調べ、所定数に達していなければ１次に、６
４ＫＢページ領域３０上に割り当てられている４ＫＢ仮
想ページの内、もう１つの全割り当て済み６４ＫＢペー
ジキユー９２０（第５Ｄ図）に接続されているものにつ
いて、６４ＫＢ単位にページアウトを実施する。これは
、第１３Ａ図に示すように、ステップ５３０で変数ＲＰ
Ｎこのキューの先頭エントリ６１Ｆを示すポインタ９２
をセットしステップ５３１で６４ＫＢページ領域３０上
に割り当てられているページのキューであることを示す
ために変数ＥＸに１をセットしステップ５３２で内部サ
ブルーチンＯＵＴをコールする。

サブルーティンＯＵＴはコールされると今度は。

キュー９２０上のエントリ６１Ｆに対して前記と同様に
先はどまで説明したステップ６００〜６８０の処理を繰
り返すごとにより当該キュー９２０上に接続されるエン
トリ６１Ｆに対するページアウト処理を６４ＫＢ単位に
行う。但し、ステップ６５０でキューの更新する際、エ
ントリ６１Ｆをキュー９２０から外す処理が追加される
ことが異なる。以上で６４ＫＢページ領域３０上に割り
当てられている、当該キューのページアウトが終了しサ
ブルーチンＯＵＴはリターンする。

次に、再度第１３Ａ図のステップ５４０で所定のページ
数（ＮＰＡＧＥ）をページアウト出来たかどうかを調べ
、所定数に達していなければ、次に、４ＫＢページ領域
２０上に割り当てられている４ＫＢ仮想ページに対して
ページアウトを実施する。

この場合には、ページアウト処理は４ＫＢ単位に実施す
る。４ＫＢページ領域２０上に割り当てられている４Ｋ
Ｂ仮想ページは全て１割り当て済み４ＫＢページキユー
８１０（第５Ａ図）に接続されている。この場合も、前
記同様にステップ５５０で変数ＲＰＮにこのキューの先
頭エントリ５１Ｇを示すポインタ８１をセットしステッ
プ５５１で、４ＫＢページ領域２０上のキューであるこ
とを示すためＥＸにＯんセットし、ステップ５５２で内
部サブルーチンＯＵＴをコールする。

サブルーチンＯＵＴは、前記キュー８１０に接続されて
いるエントリ５１Ｃを対象として前記同様にステップ６
００〜６３０のまでの処理を行うと、次にステップ６３
０で変数ＥＸの値を調べる。この場合はＥＸにＯがセッ
トされており４ＫＢ単位の処理であると判断し、ステッ
プ６４０Ａに進む。

ステップ６４０Ａでは当該エントリ５１Ｃに対応するペ
ージをページアウトしく但し当該エントリ５１Ｃの対応
するキー記憶上のチェンジビットＣ（第８図５）がｏｆ
ｆの場合はページアウトは行わない）、当該領域に割り
当てられていた仮想ページに対応するアドレス変換テー
ブルのエントリを無効とする０次に、ステップ６５０Ａ
で前記各エントリ５１Ｃを割り当て済み４ＫＢページキ
ユー８１０からはずし、当該エントリ５１Ｃを未割り当
て４ＫＢベージキユー７１０　（第４Ａ図）に接続する
。次に、ステップ６６０Ａでページアウト数を示す変数
ＰＯＵＴを１増し、ステップ６７０でＰＯＵＴがページ
アウトすべき個数に達したか否かをチエツクするため変
数ＮＰＡＧＥと比較する。ページアウト数がＮＰＡＧＥ
未満であれば、つぎにステップ６８０で変数ＲＰＮに当
該エントリ５１Ｃのフォワードポインタ９４Ａ（第３Ａ
図）をセットしステップ６００からの処理を繰り返す。

以上に処理をステップ６００で当該キューの全エントリ
５１Ｃを処理し終わるか、ステップ６１０で起動時の条
件以下の不参照期間数を持つエントリ５１Ｃが現れるま
で、もしくは、ステップ６７０で所定のページ数（ＮＰ
ＡＧＥ）をページアウ以上で、４ＫＢページ領域２０上
に割り当てられている割り当て済み４ＫＢページキユー
８１０（第５Ａ図）に接続されているものについて４Ｋ
Ｂ単位にページアウトを実施しサブルーチンＯＵＴがリ
ターンし、処理を終える。以上の様にして十分な未使用
実記憶量が確保出来るまで、ページアウトプログラム７
起動時の条件の１つであるページアウトすべき不参照期
間数を順次小さくして繰り返しページアウトプログラム
７を起動すれば良い。こうして、仮想ページサイズは従
来通りの４ＫＢのままで、ページアウト処理はその仮想
ページに割り当てられた実記憶の実ページサイズ単位に
実施することができ、ページアウトに関するＸ７０回数
を低減できる。

以上で本発明の第１の実施例の説明を終える。

次に、本発明の第２の実施例について述べる。

なお、第２の実施例 の説明に当り第１実施例と同じ構成、用途のものは第１
実施例と同じ番号を付加し、その詳細図も同一の図を用
いる。

第２の実施例では、第８図に示すように仮想記憶１１Ａ
は仮想アドレス ２ＧＢ　（ギガバイト）を境としてサイズ４ＫＢ（キロ
バイト）の仮想ペ ージ′１２の群により構成されている４ＫＢページ領域
１１０とサイズ６４ＫＢ　（キロバイト）の仮想ベージ
１３の群により構成されている６４ＫＢページ領域１２
０から成る。

実記憶１０Ａは第１の実施例と同様に実ページサイズの
異なる２つの領域、すなわち、ページサイズ４　Ｋ　Ｂ
　Ｍ域と６４ＫＢ領域に分割されている。

さらに、本実施例では各ページサイズの領域内がさらに
各々２分割されており１合計４つの領域２０．２０Ａ、
３０，３０Ａに分割されている。

領域２０は４ＫＢの実ページ２１の群より成り、以下こ
の領域を４ＫＢページ専用領域と呼ぶ。

領域２ＯＡは４ＫＢの実ページ２ＬＡの群より成り、以
下この領域を４ＫＢページ共用領域と呼ぶ、なお、この
両者をまとめて４ＫＢページ領域と呼ぶ。

領域３０は６４ＫＢの実ページ３１の群より戊り、以下
この領域３０を６４ＫＢページ共用領域と呼ぶ。

領域３０Ａは６４ＫＢの実ページ３１Ａの群より成り、
以下この領域３０Ａを６４ＫＢページ専用領域と呼ぶ。

なお、この両者をまとめて６４ＫＢページ領域と呼ぶ。

すなわち１本実施例では第１の実施例に領域２０Ａと領
域３０Ａが起加されている所が異なる。領域２０は第１
実施例で詳述したように本実施例においても４ＫＢ仮想
ページのみを割り当て可能な領域である。領域３０も第
１実施例と同様に６４ＫＢページ領域３０構成する各６
４ＫＢページ３１を４ＫＢの領域に分割し、各分割領域
　１つの４ＫＢ仮想ページに割り当てることも出来るし
、各６４ＫＢページ３１＆１つの６４ＫＢ仮想ページに
割り当てることも出来る所が特徴の一つである。また、
領域２ＯＡは領域を構成する各４ＫＢページ２１Ａを１
つの４ＫＢ仮想ページに割り当てることも出来るし、１
６個の連続する４ＫＢページ２１Ａをまとめて１つの６
４ＫＢ仮想ページに割り当てることも出来る所が特徴の
一つである。

また、領域３０Ａは６４ＫＢ仮想ページのみが割り当て
可能な領域である。

５は実記憶１０Ａの各ページに対する記憶保護キーを保
持するためのキー記憶である。その各くエントリ６には
対応する実ページに割り当てられた記憶保護キー（ＳＫ
７）、そのページの参照の有無を示す参照ビット（Ｒ）
８、そのページが書き替えられたことを示すチェンビッ
ト（ｃ）９を格納するエリアから成る。キー記憶５の各
エントリ６は４ＫＢページ領域２０．２ＯＡ対しては従
来と同様にページごと、すなわち、４ＫＢごとに、６４
ＫＢページ領域３０．３０Ａに対しても同様にページご
と、すなわち、６４ＫＢごとに設置されている。すなわ
ち、従来と同様に本実施例でも実ページは記憶保護キー
の付与単位となっている。

６４ＫＢページ領域３０．３ＯＡでは実ページサイズを
４ＫＢから６４ＫＢに拡張されているので、第１必実施
例と同様に４ＫＢページ領域２０゜２ＯＡに比べ実記憶
の単位容量当りのキー付与数を１／工６に抑えキー記憶
容量の増加を抑止している。

第９図は、オペレーティングシステムに含まれるプログ
ラムおよび管理テーブルを示す０図において、２Ａはそ
のうちの実記憶割り当てプログラム、３はページ計測プ
ログラム、７Ａはページアウトプログラムを示す、実記
憶割り当てプログラム２Ａではある仮想ページに対して
、プログラムから実記憶の割り当て要求があると仮想ペ
ージ単位に実記憶の領域を割り当てる。この割り当てで
は具体的には実記憶より仮想ページサイズに一致する空
き領域を１つ選び出し割り当てるべき仮想ページに対応
するアドレス変換テーブルのエントリ上に、選び出した
実記憶領域のアドレスをセットし仮想アドレスから実ア
ドレスへの変換を可能とする。すなわち１本発明でも従
来と同様に仮想ページは仮想アドレスから実アドレスへ
のアドレス変換単位である。ページ計測プログラム３は
実記憶上に割り当てられている各仮想ページの使用頻度
を計測するもので、実記憶の不足状態に陥るとこの計測
結果に従ってページアウトプログラム７Ａで使用頻度の
低い仮想ページに割り当てられている実記憶上の情報を
順次、補助記憶にページアウトし使用可能な実記憶を一
定量確保する制御に用いられる。図において、５０．６
０は実記憶の現在の割り当て状況を管理するための実記
憶管理テーブルである。４ＫＢ領域管理テーブル５゜は
仮想ページサイズと同じサイズの実記憶領域、すなわち
、４ＫＢ実ページの各々（２１，２１Ａ群）および各６
４ＫＢページの各分割領域（３１群）に対応するエント
リ５１を持つ。各エントリには対応する実記憶内の４Ｋ
Ｂ領域の割り当て状況を示す情報を保持する。後に説明
するようにこの管理テーブル５０のエントリの内、仮想
ページに未だ割り当てられていない４ＫＢの実記憶領域
に対応するエントリのキュー（未割り当て４ＫＢ領域キ
ユー７１０（第４Ａ図））が形成される。

７１はこのキューの先頭エントリを示すポインタである
。

また、６４ＫＢ領域管理テーブル６０は４ＫＢページ領
域２０Ａの連続する４ＫＢ実ページ２１Ａを１６ａ毎に
まとめた６４ＫＢ単位に対応するエントリ６１、および
、６４ＫＢページ領域３ｏ内の６４ＫＢの実ページ３１
の各々に対応するエントリ６１を持つ。各エントリは、
対応する実記憶領域の割り当て状況を６４ＫＢ単位に示
す情報を保持する。

後に説明するようにこの管理テーブル６０のエントリの
内、仮想ページに未だ割り当てられていない６４ＫＢ単
位の実記憶領域に対応するエントリのキュー（未割り当
て４ＫＢ共用キユー１７２０（第１０Ａ図）９部分割り
当て済み４ＫＢ共用キユー１７３０　（第１０Ｂ図）、
未割り当て６４ＫＢ領域キユー７２０（第４Ｂ図））が
形成される。

１７２．１７３．７２はこれらキューの先頭エントリを
示すポインタである。

また、６４ＫＢ領域管理テーブル４０は６４ＫＢページ
領域３０Ａ内の６４ＫＢの実ページ３１Ａの各々に対応
するエントリ４１を持つ、各エントリ゛は、対応する実
記憶領域の割り当て状況を６４ＫＢ単位に示す情報を保
持する。

後に説明するようにこの管理テーブル４０のエントリう
ち、仮想ページに未だ割り当てられていない６４ＫＢ単
位の実記憶領域に対応するエントリのキュー（未割り当
て６４ＫＢ専用キユー１７５０（第１０Ｃ図））が形成
される。

１７５はこのキューの先頭エントリを示すポインタであ
る。

また、１００Ａはプログラム（ジョブ）ごとに設けたジ
ョブ管理テーブルである。この管理テーブルには、機能
するように、各ジョブが使用中の仮想ページに割り当て
られた４ＫＢ実ページに対応するテーブル５０内のエン
トリキュー（割り当て済み４ＫＢページキユー８１０（
第５Ａ図））が形成される。

８１はこのキューの先頭エントリを示すポインタである
。

また、後述するように、各ジョブが使用中の仮想ページ
に割り当てられた分割領域に対応するテ−プル５０内の
エントリキュー（割り当て済み分割領域キュー８２０（
第５Ｂ図））が形成される９８２はこのキューの先頭エ
ントリを示すポインタである。また、各ジョブについて
各ジョブが４ＫＢの仮想ページ割り当てに使用中の６４
ＫＢ実ページの内、一部の分割領域が未割り当てである
ものに対するテーブル６０のエントリのキュー（部分未
開り当て６４ＫＢページキユー９１０（第５Ｃ図））が
形成される。９■はこのキューの先頭エントリを示すポ
インタである。また、各ジョブについて各ジョブが４Ｋ
Ｂの仮想ページ割り当てに使用中の６４ＫＢ実ページの
内、全部の分割領域が割り当て済みであるものに対する
テーブル６０のエントリのキュー（全割り当て済み６４
ＫＢページキユー９２０（第５Ｄ図））が形成される。

９２はこのキューの先頭エントリを示すポインタである
。

また、各ジョブが使用中の６４ＫＢ仮想ページが割り当
てられている６４ＫＢ実ページ３１Ａに対するテーブル
４０のエントリ４１のキュー（割り当て済み６４ＫＢペ
ージキユー１７６０　（第１１図〉）が形成される。１
７６はこのキューの先頭エントリを示すポインタである
。

第３Ａ図、第３Ｂ図に各管理テーブルエントリ５１、エ
ントリ６１の構造を示すが、第１実施例ですでに説明し
たため詳細説明は省略する。

また、６４ＫＢ専用領域管理テーブル４０の１つのエン
トリ４１の内の情報は第３Ａ図のエントリ５１と全く同
じである。

尚、第３Ｂ図は８４ＫＢ領域管理テーブル６０の１つの
エントリ６１内の情報を示す図であるが、６４ＫＢ仮想
ページが割り当てられる場合には第１実施例とはセット
するフィールドが異なる。すなわち、フィールド９７．
９８．９９は使用しない。

次に、第１実施例に対して追加された各キューについて
述べる。

第１０Ａ図は未割り当て４ＫＢ共用キユーを示す、この
キューは第１実施例のキュー７２０（第ページ領域２Ｏ
Ａ内の領域を６４ＫＢ単位で管理する。仮想ページが割
り当てられていない連続する１６個の４ＫＢ実ペ一ジ２
１Ａ群毎に設けられたテーブル６０のエントリ６１Ｇの
列および前記４ＫＢ実ペ一ジ２１Ａ群の各々に対するエ
ントリ５１Ｇの列とキューポインタ１７２とから形成さ
れる。各エントリのキューのされ方は前記キュー７２０
と同様であり省略する。

第１０Ｂ図は部分割り当て済み４ＫＢページ共用キユー
１７３０を示す。このキューは第１実施例のキュー９１
０（第４Ｃ図）と同形式であるが。

第１実施例とは異なりジョブ別に作成されずシステム全
体で唯一１個のキューを形成する。

このキューは実記憶１０Ａの４ＫＢページ領域２ＯＡ内
の領域を連続する１６個の４ＫＢ実ペ一ジ２１Ａ群毎の
６４ＫＢ領域の内、前記連続する１６個の４ＫＢ実ペ一
ジ２１Ａ群のいづれかが４ＫＢ仮想ページに割り当てら
れているテーブル６０のエントリ６１Ｈの列および前記
４ＫＢ実ぺ一キューポインタ１７３とから形成される。

各エントリのキューのされ方は前記キュー９１０と同様
であり省略する。なお、このキューがシステム全体で唯
一１個のキューを形成するのは、前記キュー９１０とは
異なりこのエントリ６１Ｈ内はもともと１６個の４ＫＢ
実ペ一ジ２１Ａ群により構成されるため、キー記憶がエ
ントリ５１Ｈ対応に存在し、各々のエントリ５１Ｈに対
応する４ＫＢ実ページは異なる記憶キーの仮想ページや
ジョブに割り当て可能である為である。第１０Ｃ図は未
割り当て６４ＫＢページ専用キユーを示す。このキュー
は６４ＫＢページ専用領域３０Ａ上の仮想ページが割り
当てられていないテーブル４０のエントリ４１の列とキ
ューポインタ１７５とから形成される。キューのされ方
は第１実施例のキュー７１０と同様であり省略する。第
１１Ａ図は割り当て済み６４ＫＢページキユーを示す。

このキューはジョブ別に設けられたキューで、実ページ
サイズを問わずそのジョブの６４ＫＢ仮想ページに割り
当てられている管理テーブル４０のエントリ４１（領域
３０Ａ上）の列および管理テーブル６０のエントリ６１
Ｊ（領域２ＯＡ上）、６１１（領域３０上）の列とキュ
ーポインタ１７６とから形成される。

次に実記憶割り当てプログラム２Ａの動作を説明する。

第１２Ａ、１２Ｂ図はページ割り当てプログラム２Ａの
概略フローを示す図である。あるプログラム（ジョブ）
の実行中に仮想記憶上のある領域をアクセスしたとき、
その仮想領域に対応する実記憶領域が割り当てられてい
ない場合に、ページフォールト割り込みが発生し、これ
を契機に仮想領域に実記憶領域を仮想ページ単位に割り
当てるための実記憶割り当て要求がおこり、実記憶割り
当てプログラム２Ａが起動されるのは第１実施例と同様
である。

実記憶割り当てプログラム２Ａが起動されると、まずス
テップ２０００でページフォールト割り込みが発生した
仮想アドレスを調べる。仮想アドレに示す６４ＫＢ仮想
ページの割り当てを実施する。

仮想アドレスが２ＧＢ以下であれば４ＫＢ仮想ページの
割り当てを実施する。４ＫＢ仮想ページの割り当ての場
合には、まず、ステップ２１０で第１実施例で述べた要
求元ジョブ割り当て済み６４ＫＢページ内サーチ処理を
実施する。この処理の詳細は前述の通りであり省略する
が、この処理は６４ＫＢページ内を分割使用した場合に
生じる６４ＫＢページ内の部分末剤り当て分割領域を利
用するための工夫であり、要求元ジョブに既に部分的に
割り当て済みの６４ＫＢページ内の未割り当て分割領域
を優先してそのジョブに割り当てる。

ジョブに最初にページを割り当てる場合はそのジョブに
対して部分的に未割り当ての６４ＫＢページは存在しな
い。従って、サーチ２１０は失敗するのでこのサーチ２
１０については後に説明する。

ステップ２０１０でサーチ２１０において部分的に未割
り当てのページが見つからなかったことを判断すると、
次に、部分割り当て済み４ＫＢ共用するが、この場合も
同様に最初はキューが存在しないためステップ２１００
は失敗するのでこの処理についても後に説明する０次に
未割り当て４ＫＢ共用キユー１７２０　（第１０Ａ図）
から未使用ページをサーチするためステップ２２００で
そのキューポインタ１７２がゼロであるか否かを調ベゼ
ロでなければ、ステップ２２１０でこのキュー１７２０
の先頭に接続されるエントリ６１Ｇを選択する。さらに
、このエントリ６１Ｇに連なる１６個の４ＫＢペ一ジ２
１Ａ群に対するエントリ５１Ｇの列の先頭のエントリを
選択しそれに対応する４ＫＢページ２１Ａを割り当て対
象とする。

次に、ステップ２２２０で管理テーブルエントリおよび
キューの更新を行う。すなわち、エントリ６１Ｇの内部
ポインタＦ（第３Ｂ図）で示されるエントリ６１Ｇに連
なる先頭のエントリ５１Ｇを選択し、そのフィールド９
１Ａ、９２Ａ、（第３図Ａ）に割り当て対象となった仮
想ページのアドレスと割り当て要求元のジョブのＩＤを
セットし、減数９６を＋１しくその初期値は０である）
する。

次に、キューの更新を以下のように行う。即ち。

未割り当て４ＫＢページ共用キユー１７２ｏがら（第１
０Ａ図）上記選択されたエントリ６１Ｇおよびこれに連
なる１６個のエントリ５１Ｂをはずし、このエントリ６
１Ｇおよび上記１６個のエントリ５１Ｇの中の、上記選
択されたエントリ５１Ｇ以外の１５個（未割り当ての４
ＫＢペ一ジ２１Ａ群に対するテーブル５０のエントリ）
を部分割り当て済み４ＫＢページ共用キユー１７３０　
（第１０Ｂ図）に接続する。さらに、上記選択されたエ
ントリ５１Ｇをそのジョブに対して設けられた割り当て
済み４ＫＢページキユー８１ｏ（第５Ａ図〉に接続する
。

さらに割り当て対象となった仮想ページに指定されてい
る記憶キー（ジョブから明示的に指定されていない場合
は、そのジョブのその時点のプログラムキー値）を割り
当て対象となったエントリ５１Ｇに対応するキー記憶５
（第１図）のエントリ６のＳＫ７にセットする。なお、
この４ＫＢ実べ−ジのアドレスは、選択されたエントリ
５１Ｇが管理テーブル５ｏ中の何番目のエントリである
か。

すなわち、エントリ５１Ｇのテーブルインデックスによ
り決定することができる。この４ＫＢ実ページアドレス
に基づいてハードウェア命令を用いて記憶キーセットす
る。

次に、ステップ２６００により、実記憶割り当てが要求
された仮想ページに対応するアドレス変換テーブル内の
エントリに選択した分割領域の実アドレスのセットとこ
のエントリのバリデーションを実施する。こうして；の
実記憶領域が使用可能となる。こうして、未割り当て４
ＫＢページ共用キユー１７２０内の最初の割り当てが終
了する。

以上の処理における、ステップ２２００でキューポイン
タ（１７２）がゼロであれば領域２０Ａ上には未割り当
てページは無して判断し、次に未割り当て６４ＫＢペー
ジキユー７２０（第４Ｂ図）から未割り当て６４ＫＢペ
ージのサーチを実施し、未割り当て６４ＫＢ内の一つの
分割領域を割り当−７２０（第４Ｂ図）を用いて、その
ジョブに割り当てるべき未使用の６４ＫＢページを見つ
ける。

このために、まずステップ２３００でこのキュー７２０
のポインタ７２の値のゼロ判定を行いこのポインタに接
続されたエントリ６１Ｂの有無調べる。

キューポインタ７２がゼロでなければ、ステップ２３１
０にてそれに連なるキュー７２０の先頭のエントリ６１
Ｂ＆選択する。そのエントリ６よりに連なる１６個の分
割領域に対するエントリ５１Ｂの列の先頭のエントリを
選択しそれに対応する分割領域を割り当て対象とする。

次に、ステップ２３２０で管理テーブルエントリおよび
キューの更新を行う。すなわち、エントリ６１Ｂの内部
ポインタＦ（第３Ｂ図）で示されるエントリ６１Ｂに連
なるエントリ５１Ｂを選択し、前記と同様にそのフィー
ルド９ＬＡ、９２Ａ。

（第３＠Ａ）に割り当て対象となった仮想ページのアド
レスと割り当て要求元のジョブのＩＤをセみ分割領域数
９６を＋１しくその初期値はＯである）、フィールド９
２ＢにそのジョブのジョブＩＤをセットする。

次に、キューの更新を以下のように行う。即ち、未割り
当て６４ＫＢページキユー７２０から（第４Ｂ図）上記
選択されたエントリ６１Ｂおよびこれに連なる１６個の
エントリ５１Ｂをはずし、このエントリ６１Ｂおよび上
記１６個のエントリ５１Ｂの中の、上記選択されたエン
トリ５１Ｂ以外の１５個（未割り当ての分割領域に対す
るテーブル５０のエントリ）をそのジョブに対して設け
られた部分割り当て済み６４ＫＢページキユー９１０（
第５Ｃ図）に接続する。さらに、上記選択されたエント
リ５１Ｂをそのジョブに対して設けられた割り当て済み
分割領域キュー８２０（第５Ｂ図）に接続する。さらに
、割り当て対象となった仮想ページに指定されている記
憶キー（ジョブから明示的に指定されていない場合は、
そのジョブのその時点のプログラムキー値）をフィール
ド９７にセットし、割り当て対象となった分割領域の含
まれる６４’ＫＢ実ページに対応するキー記憶５（第１
図）のエントリ６にフィールド９７にセットした値と同
じキー値をセットする。なお、この６４ＫＢ実ページの
アドレスは選択されたエントリ６１Ｂがテーブル６０中
の何番目のエントリであるか（すなわち、それに対応し
て定まることエントリ６１Ｂのテーブルインデイクス）
から決定することができる。この６４ＫＢ実ページのア
ドレスに基づいて八−ドウエア命令を用いて上記記憶キ
ーをキー記憶５の対応するエントリ６のフィールドＳＫ
７　（第８図）に書き込む。また。

この記憶キーの書き込みは未割り当で６４ＫＢページ内
から分割領域を最初に割り当てる場合のみ実施する。次
に、前記同様にステップ２６００により、実記憶割り当
てが要求された仮想ページに対応するアドレス変換テー
ブル内のエントリに選択した分割領域の実アドレスのセ
ットとこのエントリのバリデーションを実施する。こう
してこの実記憶領域が使用可能となる。こうして、未割
り当て６４ＫＢページキユー９１０からの最初の分別領
域の割り当てが終了する。

上記の処理における、ステップ２３００においてキュー
ポインタ（７２）がゼロであればキュー９１０にはエン
トリが存在しないと判断し未割り当て４ＫＢページキユ
ー７１０からの割り当てを試みる。この処理は実記憶１
０Ａの４ＫＢ実ページ専用領域２０内の未割り当ての一
つの実ページを割り当てるべき実記憶領域として選択す
る。この選択は、未割り当て４ＫＢページキユー７１０
（第４Ａ図）に接続されたエントリが有るかどうかをス
テップ２４００で調べ、有ればステップ２４１０でキュ
ー７１０の先頭につながるエントリ５１Ａを選択するこ
とにより行われる。次にステップ２４２０において、こ
の選択されたエントリ５１Ａ内に割り当て要求もとのジ
ョブのＩＤおよび割り当て対象の仮想ページのアドレス
を書き込む。さらに、このエントリ５１Ａを上記キュー
７１０よりはずし、そのジョブに対して設けられた割り
当てず見４ＫＢページキュー８１０（第５Ａ図）に接続
する。さらに、前記エントリ５１Ｇの場合と同様に記憶
キーのセットを行い、ステップ２６００においてアドレ
ス変換テーブルの書き替えを先に述べたのと同じように
行う。こうして４ＫＢ実ページへの割り当てが終了する
。その後、４ＫＢ仮想ページに対する新たな実記憶割り
当て要求がなされる毎に同じように処理される。この際
、先に詳細を省略した要求元ジョブ割り当て済み６４Ｋ
Ｂページサーチ２１０も実行される。以下、この処理に
ついて述べる。

ステップ２１０の処理は既に第１実施例で詳述したので
省略するが、ステップ２１０が完了すると、ステップ２
０１０でこのジョブに設けられた部分割り当て済み６４
ＫＢページキユー９１０内に割り当て可能な部分未開り
当ての６４ＫＢページが有ったか無かったかを判断し、
有ればステップ８３４Ｃにてそのエントリおよびキュー
の更新を行う、すなわち、そのエントリ６１Ｅに接続さ
れてた未使用分割領域のエントリ５１Ｅを一つ選択し、
このエントリに対応する分割領域を割り当て領域とすべ
く、この選択されたエントリ５１ＥにそのジョブのＩＤ
および割り当て対処となった仮想ページのアドレスをセ
ットする。

さらに、上記エントリ６１Ｅ内の割り当て済み分割領域
数を＋１する。

上記エントリ５１Ｅを上記キュー９１０からはずし、そ
のジョブに対して設けられている割り当て済み分割領域
キュー８２０に接続する。もし、上記更新後の割り当て
済み分割領域数が１６に等しいときは、割り当て対象と
なった分割領域を含む６４ＫＢ実ページは未割り当ての
分割領域がなくなったことになる。したがって、この時
には、この６４ＫＢ実ページに対応する前記エントリ６
１Ｅもキュー９１０からはずし、全割り当て済みキュー
９２０（第５Ｄ図）にエントリ６１Ｆとして接続する。

こうして、ステップ２３４Ｃがするとその後ステップ２
６００が前と同様になされる。上記のステップ２０１０
で割り当て可能な部分未開り当ての６４ＫＢページが無
かったか場合には、次に前記の説明で後回しにしたもう
一つの処理、すなわち、部分割り当て済み４ＫＢページ
共用キユー１７３０　（第１０Ｂ図）がらの割り当てを
行う、この処理はステップ２１００でこのキューのポイ
ンタ１７３がゼロでない場合に実施され、ステップ２１
１０でキュー１７３０の先頭のエントリ６１Ｈを取り出
す。そのエントリ６１Ｈに連なる４ＫＢペ一ジ２１Ａ群
に対するエントリ５１Ｈの列の先頭のエントリを選択し
これを割り当て対象とする。

次に、ステップ２１２０で管理テーブルエントリおよび
キューの更新を行う。すなわち、エントリ６１Ｈの内部
ポインタＦ（第３Ｂ図）で示されるエントリ６１Ｈに連
なるエントリ５１Ｈを選択し、そのフィールド９１Ａ、
９２Ａ、（第３図Ａ）に割り当て対象とな漬た仮想ペー
ジのアドレスと割り当て要求元のジョブのＩＤをセット
し、′ａ択したエントリ６１Ｂ内の割り当て済み分割領
域数９６を＋１しくその初期値はＯである）する。さら
に前記エントリ５１Ｇの場合と同様に記憶キーをセット
する。次に、上記エントリ５１Ｈを上記キュー１７３０
よりはずし、そのジョブに対して設けられた部分割り当
て済み４ＫＢページキユー８１０（第５Ａ図）に接続す
る。もし、上記更新後の割り当て済み分割領域数が１６
に等しい時は、上記エントリ６１Ｈ内の全ての領域が使
用されたことを表す。したがって、この場合には前記エ
ントリ６１．Ｈもキュー１７３０からはずす。こうして
、ステップ２１２０が終了するとその後のステップ２６
００が前と同様になされる。

また、上記のいずれの処理においても割り当て可能な領
域が無い場合には後で述べるページアウトプログラム７
Ａ（第１４Ａ、第１４Ｂ図）が動作し、実記憶に使用可
能なページを一定量確保できるまでステップ２５００で
当該割り当て要求元ジョブを停止させて実記憶の空きを
待たせる。この場合は、ページアウトプログラム７Ａに
対していずれのサイズの仮想ページを割り当てるための
領域が不足しているかを通知する１以上の処理を実ペー
ジ割り当て要求がなされるたびに繰り返せばよい。

発生アドレスが２ＧＢ以上の場合、即ち、６４ＫＢ仮想
ページの割り当て処理について第１２Ｂ図を用いて説明
する。６４ＫＢ仮想ページの割り当て処理では、まず、
未割り当て６４ＫＢページ専用キユー１７５０　（第１
０Ｃ図）から未使用ページをサーチするためステップ３
０００でそのキューポインタ１７５がゼロであるか否か
を調ベゼロでなければ、ステップ３０１０でこのキュー
１７５０の先頭に接続されるエントリ４１選択し、これ
を割り当て対象とする。次に、ステップ３０２０でテー
ブルエントリおよびキューの更新を行う。

すなわち、そのエントリ４１フイールド９１Ａ。

９２Ａ、（第３図Ａ）に割り当て対象となった仮想ペー
ジのアドレスと割り当て要求元のジョブのＩＤをセット
する。次に、キューの更新を以下のように行う、即ち、
未割り当て６４ＫＢページ専用キユー１７５０から（第
１０Ｃ図）上記選択されたエントリ４１をはずし、その
ジョブに対して設けられた割り当て済み６４ＫＢ　（仮
想）ページテップ３５００により、実記憶割り当てが要
求された仮想ページに対応するアドレス変換テーブル内
のエントリに選択したエントリ４１に対する実アドレス
のセットとこのアドレス変換テーブルエントリのバリデ
ーションを実施する。

こうしてこの実記憶領域が使用可能とする。こうして、
未割り当て６４ＫＢページ専用キユー１７５０内のから
の割り当てが終了する。

以上の処理における。ステップ３０００でキューポイン
タ（１７５）がゼロであれば領域３０Ａ上には未割り当
てページは無しと判断し１次に未割り当て６４ＫＢペー
ジキユー７２０（第４Ｂ図）から未割り当て６４ＫＢペ
ージのサーチを実施し。

未割り当て６４ＫＢの一つを割り当てる。すなわち、未
割り当て６４ＫＢページキユー７２０（第４Ｂ図）を用
いて、そのジョブに割り当てるべき未使用の６４ＫＢペ
ージを見つける。このために、まずステップ３１００で
このキュー７２０のポインタ７２の値のゼロ判定を行い
このポインタに接続されたエントリ６１Ｂの有無調べる
。

キューポインタ７２がゼロでなければ、ステップ３１１
０にてそれに連なるキュー７２０の先頭のエントリ６１
Ｂを選択し、それに対応する領域を割り当て対象とする
。次に、ステップ３１２゜で管理テーブルエントリおよ
びキューの更新を行う。すなわち、エントリ６１Ｂのフ
ィールド９１Ｂ、９２Ｂ、（第３図Ｂ）に割り当て対象
となった仮想ページのアドレスと割り当て要求元のジョ
ブのＩＤをセットし、選択したエントリ６１Ｂ内の割り
当て済み分割領域数９６を＋１６（その初期値はＯであ
る）する。

次に、キューの更新を以下のように行う。即ち。

未割り当て６４ＫＢページキユー７２０から（第４Ｂ図
）上記選択されたエントリ６１Ｂをはずし、そのジョブ
に対して設けられた割り当て済み６４ＫＢページキユー
１７６０　（第１１図）に接続する。次ぎに、前記同様
にステップ３５００により、実記憶割り当てが要求され
た仮想ページに対応するアドレス変換テーブル内のエン
トリに選択した領域の実アドレスをセットしアドレス変
換テープルエントリのバリデーションを実施する。こう
してこの実記憶領域が使用可能となる。

上記の処理における、ステップ３１００においてキュー
ポインタ（７２）がゼロであればキュー９１０にはエン
トリが存在しないと判断し未割り当て４ＫＢページ共用
キユー１７２０　（第１０Ａ図）からの割り当てを試み
る。この処理は実記憶１０Ａの４ＫＢ実ページ共用領域
２ＯＡ内の連続する１６個の４ＫＢペ一ジ２１Ａ群より
なる未割り当ての６４ＫＢ領域を割り当てるべき実記憶
領域として選択する。この選択は、未割り当て４ＫＢペ
ージ共用キユー１７２０に接続されたエントリが有るか
どうかをステップ３２００で調べ、有ればステップ３２
１０でキュー１７２０の先頭につながるエントリ６１Ｇ
を取り出すことにより行われる。次に、ステップ３２２
０で管理テーブルエントリおよびキューの更新を行う。

すなわち、エントリ６１Ｇのフィールド９１Ｂ、９２Ｂ
。

（第３図Ｂ）に割り当て対象となった仮想ページのアド
レスと割り当て要求元のジョブのＩＤをセットし、選択
したエントリ６１Ｂ内の割り当て済み分割領域数９６を
＋１６（その初期値は０である）する。

次に、キューの更新を前記同様に行う。即ち。

未割り当て４ＫＢページ共用キユー１７２０から（第１
０Ａ図）上記選択されたエントリ６１Ｇをはずし、その
ジョブに対して設けられた割り当て済み６４ＫＢページ
キユー１７６０　（第１１図）に接続する。次に、前記
同様にステップ２３５００においてアドレス変換テーブ
ルの書き替えを先に述べたのと同じように行う、こうし
て６４ＫＢ仮想ページに対する実記憶領域の割り当てが
終了する。その後、６４ＫＢ仮想ページに対する新たな
実記憶割り当て要求がなされる毎に同じように処理され
る。

また、上記のいずれの処理においても割り当て可能な領
域が無い場合には前記同様に未使用ページを一定確保で
きるまでステップ２５００で当該割り当て要求元ジョブ
を停止させて実記憶の空きをこの場合は、ページアウト
プログラム７Ａに対して６４ＫＢのサイズの仮想ページ
を割り当てるための領域が不足していることを通知する
。以上の処理を６４ＫＢ仮想ページに対する実ページ割
り当て要求がなされるたびに繰り返せばよい。

こうして、仮想ページサイズと実ページサイズが同一の
場合は元よりサイズの異なった仮想領域と実記線領域間
の相互割り当てができる。

次にページ計測プログラム３（第９図）の動作を説明す
る。第７Ａ、７Ｂ図はページ計測プログラム３の概略フ
ローを示す図である。第１実施例では点線で示したステ
ップ３７０．３８０は使用しなかったが本実施例では、
これらを含め全てを使用する。以下、ページ計測プログ
ラム３の第２の実施例における動作を説明する。

本実施例においてもページ計測処理は、仮想ページとそ
れに割り当てられた実記憶が属する実ページサイズが異
なる場合、その仮想ページと実ページのサイズの大きい
ほうの領域毎にページ計測以下、詳細説明を行う。ステ
ップ３１０〜３４０、およびステップ３９０，４００は
既に第１実施例で詳細を述べたのでこれらについては簡
単化のため詳しくは述べない。まず、ページ計測プログ
ラム３は、ページ計測すべきジョブに対して設けられた
全割り当て済み６４ＫＢページキユー９２０（第５Ｂ図
）の先頭ポインタ９２を変数ＱＵＥＵＥにセットし、ス
テップ３２０で内部サブルーチン５ＵＢＩをコールする
。

このキュー９２０は４ＫＢの仮想ページが割り当てられ
ている６４ＫＢ実ページ領域３０に対するテーブル６０
のエントリを表すキューの一つで前述の６４ＫＥ実ペー
ジ内の全分割領域が各々１６個の仮想ページに割り当て
済みである６４ＫＢページを示し、上記の処理ではこれ
らのページに対するページ計測を６４ＫＢ単位に行った
ことになる。

次に、６４ＫＢページ領域３０上に割り当てられている
４ＫＢ仮想ページの内、もう一つの部分０図）に接続さ
れているものについて、ステップ３３０，３４０で同様
に６４ＫＢ単位にページ計測を実施する。次に、本実施
例で初めて現れる６４ＫＢ仮想ページに割り当てられて
いる領域のページ計測を実施する。６４ＫＢ仮想ページ
に割り当てられている実記憶領域は第１２Ｂ図の６４Ｋ
Ｂ写ページの割り当てで述べた様に実記憶上の領域の種
類によらず全てが第１１図に示すキュー１７６０に接続
されている。したがって、第７Ａ図に示すように、この
キュー１７６０のキューポインタ１７６をステップ３７
０において変数ＱＵＥＵＥにセットし、ステップ３８０
で内部サブルーチン５ＵＢＩをコールすれば全ての６４
ＫＢ仮想ページに割り当てられている領域のページ計測
が行える。すなわち、サブルーティン５ＵＢｉはコール
されると、ステップ５１０において、変数ＱＵＥＵＥの
値がゼロか否かによりページ計測すべきエントリ４１．
エントリ６１１．エントリ６１Ｊのいづれかがあるか否
かを調べる０次にエントリがある場合にはステップ４４
０により変数ＱＵＥＵＥで指されるエントリ４１Ａ、エ
ントリ６１１、エントリ６１Ｊのいづれかに対応する６
４ＫＢ実領域の使用の有無を調べる。これは、第１の実
施例と同様にハードウェア命令により第１図に示すキー
記憶エントリ６上の参照ビットＲ７を読み出すことによ
り行う。

これらのビットがゼロであれば当該ページは、前回のペ
ージ計測時点から今回のページ計測までの間使用されな
かったことが分かる。次に、当該ページが使用されてい
れば、ステップ４５０において不参照期間数９３Ａ（第
３Ａ図または第３Ｂ＠）をクリアし、ステップ４６０で
当該エントリ（エントリ４１Ａ、エントリ６１１．エン
トリ６１Ｊのいずれか）を当該キュー１７６０の最終位
置に移動する。このエントリの移動は、不参照期間数９
３Ａの大きい順にキューを構成するためである。

次に、当該ページが使用されていなければステップ４７
０において不参照期間数をカウンタアップする。

ンターバル毎にそのページが使用されていない場合に不
参照期間数をカウントアツプし、使用されていた場合に
は不参照期間数をゼロにするため、この不参照期間数が
大きいほど使用頻度が低いことを示す。

次にステップ４８０により変数ＱＵＥＵＥに現在処理し
ているエントリ内のフォワードポインタ（ＦＷＰ２）Ｑ
ＵＥＵＥにセットし、新たなエントリに対して今まで述
べてきたステップ５１０〜４８０の処理を変数ＱＵＥＵ
Ｅの値がゼロすなわち、キュー１７６０に接続された全
てのエントリを処理し終わるまで繰り返す。以上で、６
４ＫＢ仮想ページに割り当てられている全ての実施例に
対して６４ＫＢ単位にページ計測を実施した。最後に、
４ＫＢページ領域２０、および２０Ａ上に割り当てられ
ている４ＫＢ仮想ページに対してページ計測を実施する
。この場合には、ページ計測処理は４ＫＢ単位に実施す
る。４ＫＢページ領域２０、および２０Ａ上に割り当て
られている４ＫＢ仮想ページは全て、割り当て済み４Ｋ
Ｂページキユー８１０（第５Ａ図）に接続されている。

この場合も、前記同様にステップ３９０で変数ＱＵＥＵ
Ｅにこのキューの先頭エントリ５１Ｃを示すポインタ８
１をセットしステップ４００で内部サブルーチン５ＵＢ
Ｉをコールする。サブルーチン５ＵＢＩは、前記キュー
８１０に接続されているエントリ５１Ｃを対象として前
記同様にステップ５１０〜４８０の処理を繰り返すこと
により当該キュー上に接続されるエントリ５１Ｃに対す
るページ計測処理を４ＫＢ単位に行う。以上の処理を実
行中のジョブがＣＰＵがある一定時間使用するつど実施
すればよい。こうして、第２実施例においてもページ計
測処理はその仮想ページサイズとその仮想ページに割り
当てられている実記憶の実ページサイズの大きいほうの
サイズでできページ計測数を低減することができる。

次にページアウトプログラム？Ａ（第９図）の動作を説
明する。

第１４図はページアウトプログラム７Ａ概略フローを示
す図である。本実施例におけるページアウド処理も第１
実施例と同様に、仮想ページとそれに割り当てられた実
記憶が属する実ページサイズが異なる場合、その仮想ペ
ージと実ページサイズの大きいほうのサイズ単位にペー
ジアウトを行う所にある。以下、図にしたがって動作を
説明する。

第１実施例と同様に１本ページアウトプログラム７Ａは
実記憶の使用可能な領域が、ある一定量以下になると起
動され、また、不参照期間数がｎに以上のページをＮＰ
ＡＧＥ個ページアウトするべく起動されるものとする。

ページアウトプログラム７Ａが起動されると、まず、ス
テップ４００でページアウトしたページ数をカウントす
る変数ＰＯＵＴをＯにする。次に、ステップ４１００で
いずれのサイズの仮想ページ割り当て用の領域を処理す
るのかを判断する。これは、ページアウトプログラム７
Ａが起動されるときに起動者により指定される。仮想４
ＫＢ用の処理であれば、第１実施例で述べたページアウ
トプログラム７（第１３Ａ図、１３Ｂ図）を実行し処理
する。この詳細は説明済みである。ステップ４１００で
仮想６４ＫＢ用の処理であると判断すると、次にステッ
プ４３００でページアウトすべきジョブに対して設けら
れた割り当て済み６４ＫＢページキユー１７６０（第１
１図）の先頭ポインタ１７６を変数ＲＰＮにセットし、
ページアウトすべきキュー１７６０の先頭エントリ（エ
ントリ４１Ａ、エントリ６１１、エントリ６１Ｊのいづ
れか）をセットする。その後ステップ４４００において
、変数ＲＰＮの値がゼロか否かによりページアウトすべ
きエントリあるか否かを調べ、エントリが無ければ。

何もせずリターンする。次にエントリがある場合には、
次にステップ４４１０でページアウトして良いページか
どうかを調べる。これは、そのページのページアウトが
禁止されている（ページ固定されている）とか、既に前
回のページアウト処理でページアウト中であると言った
従来からのチエツクで、仮想記憶方式の計算機において
通常酸されているチエツクである。ページアウト不可で
あれば、キューに接続された次のページを処理するため
、ステップ４７６０において変数ＲＰＮに当該エントリ
（エントリ４１Ａ、エントリ６１１゜エントリ６１Ｊの
いづれか）のフォワードポインタをセットとステップ４
４００からの処理を繰り返す、上記のステップ４４１０
でページアウト可能であれば、ステップ４５００にて、
当該エントリの不参照期間数がページアウトプログラム
起動時に指示されたｎ以上かを調べる。ｎ以下であれば
、ページ計測プログラム３Ａで述べたように各エントリ
は不参照期間数が大きい順に並んでいるため以降のエン
トリ６１Ｅもｎ以下であり、当該キューには今回のペー
ジアウト起動条件を満たすページが無いためリターンす
る。

ｎ以下であれば、次に、ステップ４６００で当該エント
リに対応する６４ＫＢの実記憶領域をページアウトしく
但し当該エントリの対応するキー記憶上のチェンジビッ
トＣ（第８図５）がｏｆｆの場合はページアウトは行わ
ない）仮想ページに対応するアドレス変換テーブルのエ
ントリを無効とする１次にステップ４７００にて当該エ
ントリ（エントリ４１Ａ、エントリ６１工、エントリ６
１Ｊのいずれか）がいずれの実記憶領域に属するかを調
べる。これは、第８図述べた実記憶１０Ａの４つの領域
（領域２０．領域２０Ａ、領域３０、領域３０Ａ）の各
々の大きさがシステムの初期化（ＩＰＬ）時に定まる様
に戊っており、各領域の先頭および末尾の実アドレスが
あらかじめ分かっている。このアドレスと当該エントリ
のポインタである変数ＲＰＮとを比較することにより当
該エントリが属する領域が分かる。当該エントリが領域
３０Ａに属している場合には、ステップ４７１０が実行
されキュー１７６０　（第１１図）よりエントリ４１Ａ
をはずし、未割り当て６４ＫＢページ専用キユー１７５
０　（第１０Ｃ図）へ接続する０次にステップ４７４０
でページアウト数を示す変数ＰＯＵＴを１増し、ステッ
プ４７５０でＰＯＵＴがページアウトすべき個数に達し
たか否かをチエツクするため変数ＮＰＡＧＥと比較する
。ページアウト数がＮＰＡＧＥ未満であれば、つぎにス
テップ４７４６で変数ＲＰＮに当該エントリ４１Ａのフ
ォワードポインタをセットしステップ４４００からの処
理を繰り返す。

また、前記ステップ４７００で領域３０に属する場合に
はステップ４７２０が実行されキュー１７６０よりエン
トリ６１１をはずし、さらに、当該エントリ６１１上の
割り当て済み分割領域数９６（第３Ｂ図）をＯにセット
し、さらに、エントリ６１１を未割り当て６４ＫＢペー
ジキユー７２０（第４Ｂ図）に接続する。次に、前記同
様にステップ４７４０でページアウト数を示す変数ＰＯ
１ＪＴをｌ増し、ステップ４７５０でＰＯＵＴがページ
アウトす°べき個数に達したか否かをチエツクするため
変数ＮＰＡＧＥと比較し、ページアウト数がＮ　Ｐ　Ａ
　Ｇ　Ｅ未満であれば、つぎのステップ４７４６で変数
ＲＰＮに当該エントリ６１１のフォワードポインタをセ
ットしステップ４４００からの処理を繰り返す。

また、前記ステップ４７００で領域２０Ａに属する場合
にはステップ４７３０が実行されキュー１７６０よりエ
ントリ６１Ｊをはずし、さらに、当該エントリ６１Ｊ上
の割り当て済み分割領域数９６（第３Ｂ図）をＯにセッ
トし、さらに、エントリ６１Ｊを未割り当て４ＫＢペー
ジ共用キユー１７２０（第１０Ａ図）に接続する。次に
、前記同様にステップ４７４０でページアウト数を示す
変数ＰＯＵＴを１増し、ステップ４７５０でＰＯＵＴが
ページアウトすべき個数に達したか否かをチエツクする
ため変数ＮＰＡＧＥと比較し、ページアウト数がＮＰＡ
ＧＥ未満であれば、つぎにステップ４７４６で変数ＲＰ
Ｎに当該エントリ６１Ｊのフォワードポインタをセット
しステップ４４０ｏからの処理を繰り返す。以上に処理
をステップ４４００で当該キューの全エントリを処理し
終わるか、ステップ４５００で起動時の条件以下の不導
前期間数を持つエントリが現れるまで、もしくは、ステ
ップ４７５０で所定のページ数（ＮＰＡＧＥ）をページ
アウトするまで繰り返す。

以上で、６４ＫＢ仮想ページに割り当てられている実記
憶領域を６４ＫＢ単位にページアウトを実施し処理を終
了する。以上の処理で十分な認使用実記憶領域が得られ
なかった場合には、ページアウトプログラム７Ａ起動時
の１つの条件であるページアウトすべき不参照期間数を
順次小さくして繰り返しページアウトプログラム７Ａを
起動すれば良い。こうして、仮想ページサイズ、および
実ページサイズが各々２種存在する本第２実施例におい
てのページアウト処理を仮想ページサイズとその仮想ペ
ージに割り当てられた実記憶の実ページサイズの内大き
いほうのサイズで実施することができる。

本実施例によれば仮想ページサイズと実ページサイズが
必ずしも一致しなくてもよく、自由度の高い実記憶り拡
張が可能となり、実ページサイズを６４ＫＢに拡張する
ことにより従来の４ＫＢに比べてオペレーティングシス
テムで管理する実ページ数が１７１６となり管理オーバ
ヘッドの削減ができる。

〔発明の効果〕

本発明によれば、実記憶／仮想記憶上の異なるサイズに
より構成された各領域間で相互にページの割り当てが可
能となるため、主記憶の効率的な管理が可能となる。ま
た、ページ計測処理を仮想ページサイズ／実ページサイ
ズの内大きい方の単位で実施するため計測数が城すオー
バヘッドの大幅削減が図れる。

【図面の簡単な説明】

第１図は本発明の第１の実施例の仮想記憶と実記憶の構
成図、第２図は本発明の第１実施例における構成回位と
実記憶の対応図、第３Ａ、３Ｂ。 を唸、４Ａ、４Ｂ、５Ａ〜５Ｄ図は本発明の第１実施例
における各種実記憶管理テーブルの説明図、第６図（よ
第１実施例におけるページ割り当てプログラムの処理フ
ロー図、第７Ａ、７Ｂ図は本発明の第１実施例、第２実
施例におけるページ計測プログラムの処理フロー図、第
８図は本発明の第２の実施例の仮想記憶と実記憶の構成
図、第９図は本発明の第２実施例における構成回位と実
記憶の対応図、第１０Ａ−１０Ｃ，１１図は第２実施例
における、各種実記憶管理テーブルの説明図、第１２Ａ
、１２Ｂ図は第２実施例におけるページ割リ当てプログ
ラムの処理フロー図、第１３．１３Ｂ図は本発明の第１
実施例におけるぺ・ウドプログラムの処理フロー図、第
１４図（実施例におけるページアウトプログラムの３０
−図。 符号の説明 ２・・・ページ割り当てプログラム、３，３４−ジ計測
プログラム、１０．ＩＯＡ・・・実記１１１・・・仮想
記憶、２０・・・４ＫＢ実ページ領大３０・・・６４Ｋ
Ｂ実ページ領域、５０・・・第１４１−プル（４ＫＢ単
位）、６０・・・第２管理チー（６４ＫＢ単位）、２１
・・・４ＫＢ実ページ、３１・・・６４ＫＢ実ページ、
５１・・・４ＫＢ単（１管理テーブルのエントリ、６１
・・・６４ＫＩの第２管理テーブルのエントリ、７．７
Ａ・シアウドプログラム。

Claims (1)

1. 【特許請求の範囲】 １、それぞれに対応して記憶保護のための記憶キーが記
   憶されるべき複数の実ページを含む実記憶を、仮想記憶
   の複数の仮想ページに割り当てる方法において、（ａ）
   第１のサイズの複数の仮想ページおよび該第１のサイズ
   のｎ（ｎは正整数）倍の第２のサイズの複１の実ページ
   をそれぞれ仮想記憶および実記憶に準備し、（ｂ）各実
   ページを分割して得られる該第１のサイズを有する複数
   の分割領域をそれぞれ異なる仮想ページに割り当てるこ
   とを特徴とする実記憶割り当て方法。 ２、（ｃ）該複数の実ページの一つに含まれる分割領域
   がすべて未割り当てのときに、その一つの分割領域をあ
   るプログラムが使用する仮想ページに割り当てる場合、
   該仮想ページにその時与えられている記憶キーでもって
   その実ページをアクセスするのを許可する値を有する記
   憶キーを該一つの実ページに対する記憶キーとして記憶
   するステップをさらに有する第１項の実記憶割り当て方
   法。 ３、該ステップにおいて、少くとも一つの分割領域が仮
   想ページに割り当て済みで少くとも一つの他の分割領域
   が仮想ページに割り当てられていない部分未分り当ての
   実ページであって、実記憶を割り当てるべき仮想ページ
   を使用するプログラムにその時与えられたアクセスキー
   でもってその実ページをへアクセスするのを許可する値
   を、該ページに対応して記憶された記憶キーが有する実
   ページを捜し、該一つの実ページ中の該他の分割領域を
   該実記憶を割り当てるべき仮想ページに割り当てる第２
   項の実記憶割り当て方法。 ４、該一つの割り当て済みの分割領域が該プログラムが
   使用する仮想ページのいずれかに割り当てられた分割領
   域である第３項の実記憶割り当て方法。 ５、該実ページを捜しえないとき、いずれの仮想ページ
   に対しても未割り当ての分割領域のみからなる他の実ペ
   ージを捜し、それらの分割領域の一つを該実記憶を割り
   当たるべき仮想ページに割り当てる第３項の実記憶割り
   当て方法。 ６、いずれかの仮想ページに割り当て済みの分割領域を
   有する複数の実ページの各々について、それに含まれる
   分割領域のいずれかがプログラムにより参照されたか否
   かに依存してそれぞれの実ページがプログラムにより参
   照されたか否かを計測するステップをさらに有する第１
   項の実記憶割り当て方法。 ７、それぞれの実ページに含まれる複数の分割領域を一
   緒にページアウトするステップをさらに有する第１項の
   実記憶割り当て方法。 ８、該第１のサイズと同じサイズの複数の実ページをさ
   らに該実記憶にあらかじめ準備し、該第２のサイズを有
   する複数の実ページの一つにある一つの分割領域と該第
   １のサイズを有する複数の実ページ内、指定によりかわ
   る一方を選択して、新たに実記憶を割り当てるべき仮想
   ページに該一方を割り当てる第１項の実記憶割り当て方
   法。 ９、該第１のサイズを有する複数の実ページをさらに該
   実記憶にあらかじめ準備し、該ステップ（ｂ）において
   、（ｂ１）該第１のサイズを有する複数の実ページの中
   に実記憶の割り当てを要求する仮想ページに対して割り
   当て可能な少くとも一つの分割領域があるかをあらかじ
   め定めた割当て条件により判別し、（ｂ２）該一つの分
   割領域がある場合には、その分割領域を該仮想ページに
   割り当て、（ｂ３）該一つの分割領域がない場合には該
   第１のサイズを有する該複数の実ページの一つを該仮想
   ページに割り当てる第１項の実記憶割り当て方法。 １０、それぞれに対応して記憶保護のための記憶キーが
   記憶されるべき複数の実ページを有する実記憶内の領域
   を仮想記憶の複数の仮想ページに割り当てる方法におい
   て、（ａ）第１のサイズの複数の仮想ページおよび該第
   １のサイズの１／ｎ（ｎは正整数）の第２のサイズを有
   する複数の実ページをそれぞれ仮想記憶および実記憶に
   あらかじめ準備し、（ｂ）該複数の実ページを連続する
   ｎ個のページからなる複数の実ページ群の各々を該仮想
   ページの異なるものに割り当てる実記憶割り当て方法。 １１、該一つの仮想ページを使用するプログラムにその
   時与えられた仮想ページの記憶キーでもつてそのｎ個の
   実ページの群の各々の実ページをアクセスするのを許可
   する値の記憶キーを該ｎ個の実ページの各々に対応して
   記憶するステップをさらに有する第１１項の実記憶割り
   当て方法。 １２、各実ページ群について、そこに含まれる実ページ
   のいずれかがプログラムにより参照されたかに依存して
   、それぞれの実ページ群が参照されたか否かを計測する
   ステップをさらに有する第１１項の実記憶割り当て方法
   。 １３、それぞれの実ページ群に含まれる実ページを一緒
   にページアウトするステップをさらに有する第１２項の
   実記憶割り当て方法。 １４、該ステップ（ａ）において、該第２のサイズを有
   する複数の仮想ページをさらに該仮想記憶にあらかじめ
   準備し、該ステップ（ｂ）において実記憶を割り当てる
   べき第１の仮想ページが該第１のサイズを有する場合、
   該複数の実ページ群の内、仮想ページへの割り当てに用
   いられていないｎ個のページのみからなる第１の群内の
   実ページを該第１の仮想ページに割り当て、実記憶を割
   り当てるべき第２の仮想ページが該第２のサイズを有す
   る場合、該複数の実ページ群の第２の群に属し、ｎ個の
   実ページの内、仮想ページの割り当てに用いられていな
   い一つの実ページに割り当てる第１０項の実記憶管理方
   法。 １５、該第１の仮想ページに実ページを割り当てた時に
   、そのときに与えられていたアクセスキーに実記憶への
   アクセスを許可する値の記憶キーを、該第１の実ページ
   群に含まれるｎ個の実ページの各々に対応して記憶し、
   該第２の仮想ページに実ページを割り当てた時に、与え
   られていたアクセスキーに対して実記憶へのアクセスを
   許可する値の記憶キーを、該第２の実ページ群内のｎ個
   の実ページの内、該一つの実ページに対応して記憶する
   ステップをさらに有する第１４項の実記憶割り当て方法
   。 １６、該複数の実ページ群の内、該第１のサイズを有す
   る仮想ページへ割り当てられた複数の第１種実ページ群
   の各群について、その実ページ群がプログラムが参照さ
   れたか否かを、その実ページ群内のいずれかの実ページ
   が参照されたか否かに依存して計測し、該複数の実ペー
   ジの内、該第２のサイズを有する仮想ページに割り当て
   られた少くとも一つの実ページを有する第２種の実ペー
   ジ群にいずれかに属する実ページの各々について、それ
   ぞれの実ページがプログラムにより参照されたか否かを
   計測するステップをさらに有する第１４項の実記憶管理
   方法。 １７、該第１種の実ページ群の各々に含まれるｎ個の実
   ページを一緒にページアウトし、該第２種の実ページ群
   の各々に含まれるｎ個の実ページのそれぞれを他の実ペ
   ージとは別にページアウトするステップをさらに有する
   第１５項の実記憶管理方法。 １８、（ｄ）該第２のサイズを有する複数の第３種の実
   ページを該実記憶にさらに設け、（ｅ）実記憶を割り当
   てるべき第２種の仮想ページに対して、該第３種の実ペ
   ージの内、仮想ページに割り当てられていない一つを捜
   し、（ｆ）該一つの第３種の実ページが検出されたとき
   には、該実記憶を割り当てるべき第２種の仮想ページに
   該検出された一つの第３種の実ページを割り当て、（ｇ
   ）該一つの第３種の実ページが検出されなかったときに
   該ステップ（ｃ）を実行する。 １９、該ステップ（ｃ）は、（ｃ１）仮想ページに未だ
   割り当てられていない第２種の実ページが少くとも一つ
   あるかを判別し、（ｃ２）該一つの第２種の実ページが
   あれば、それを実記憶割り当て対象の該仮想ページに割
   り当て、（ｃ３）該一つの第２種の実ページがなければ
   、該連続するｎ個の第１種の実ページを割り当てるステ
   ップからなる第１６項の実記憶割り当て方法。 ２０、それぞれに対応して記憶保護のための記憶キーが
   記憶されるべき複数の実ページを有する記憶を仮想記憶
   の複数の仮想ページに割り当てる実記憶割り当て方法に
   おいて、（ａ）第１のサイズの複数の第１種の仮想ペー
   ジと該第１のサイズのｎ倍（ｎは正整数）を有する第２
   のサイズの複数の第２種の仮想ページとをあらかじめ仮
   想記憶に準備し、（ｂ）該第１のサイズを有する複数の
   第１種の実記憶と該第２のサイズを有する複数の第２種
   の実ページとを実記憶にあらかじめ準備し、（ｃ）実記
   憶を割り当てるべき第１種の仮想ページに対して、該第
   １種の実ページの一つ又は該第２種の実ページの一つを
   分割して得られるｎ個の分割領域の一つを割り当て、（
   ｄ）実記憶を割り当てるべき第２種の仮想ページに対し
   て、該第２種の実ページの一つ又は連続するｎ個の、仮
   想ページにまだ割り当てられていない第１種の実ページ
   を割り当てる実記憶割り当て方法。 ２１、ステップ（ｂ）において該第１のサイズを有する
   第３種の複数の実ページおよび該第２のサイズを有する
   第４種の複数の実ページをあらかじめ該実記憶に準備し
   、ステップ（ｃ）において、（ｃ１）実記憶を割り当て
   るべき第１種の仮想ページに対して割り当て可能な少く
   とも一つの第３種の実ページがあるかをあらかじめ定め
   た第１の条件により判別し、（ｃ２）該一つの第３種の
   実ページがある場合、それら該第１種の仮想ページに割
   り当て、（ｃ３）該一つの第３種の実ページがない場合
   、該第１種の仮想ページに割り当て可能な少くとも一つ
   の第１種の実ページがあるかをあらかじめ定めた第２の
   条件により判別し、（ｃ４）該一つの第１種の実ページ
   がある場合、それを該第１種の仮想ページに割り当て、
   ステップ（ｄ）において、（ｄ１）実記憶を割り当てる
   べき第２種の仮想ページに対して割り当て可能な少くと
   も一つの第４種の実ページがあるかをあらかじめ定めた
   第３の条件により判別し、（ｄ２）該一つの第４種の実
   ページがある場合は、それを該第２種の仮想ページに割
   り当て、（ｄ３）該一つの第４種の実ページがない場合
   は、該第２種の仮想ページに割当て可能な少くとも一つ
   の第２種の実ページがあるかをあらかじめ定めた第４の
   条件により判別し、（ｄ４）該一つの第２種の実ページ
   があるときには、それを該第２種の仮想ページに割り当
   てる第２０項の実記憶割り当て方法。