JPH0318946A - 記憶管理装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は電子計算機システムに利用する。本発明は電子
計算機システムにおけるページテーブルによる記憶管理
に関する。

〔概要〕

本発明はページテーブルの空きエントリをサーチして記
憶管理を行う記憶管理装置において、ページテーブルの
エントリをグループにレベル分けし、レベルごとの空き
グループ情報を記憶し、要求ページ数の人力により空き
グループ情報を参照して各レベルのグループ中からサー
チ対象グループを選択し、要求ページを満たすページテ
ーブルの空きエントリをサーチし、ページテーブルの返
却要求時に対象となる各レベルのグループの空き情報を
更新することにより、 ページテーブルの空きエントリのサーチを空きエントリ
の分布による影響を受けることなく安定して行えるよう
にしたものである。

〔従来の技術〕

従来の電子計算機システムにおける記憶管理は、４０９
６バイトを１ペ一ジ単位、または４０９６ページを１セ
グメント単位として管理しているものがあり、論理空間
と物理空間とを対応づけるページテーブルは１エントリ
で１ペ一ジ分の論理空間と物理空間との対応づけを行い
、この対応づけが既に行われているかどうかの判定は、
ページテーブルの各エントリ内のフラグ（以下このフラ
グを「空きページフラグ」という）で管理されている。

また、ページテーブルはハードウェアの制約から連続空
間に置かれており、従って各エントリは連続して配置さ
れる。

論理空間と物理空間との対応づけを行う際には、ページ
テーブルの各エントリの空きページフラグを参照して論
理空間と物理空間との対応づけが行われていないエント
リ（以下このエントリを「空きエントリ」といい、空き
エントリ以外を［仕様中エントリコという）を見つけ出
す必要がある。

このサーチ方式には空きエントリの先頭からサーチする
ものがあり、ページテーブルに共通部をつくり空きエン
トリの先頭をポインタで管理している。

〔発明が解決しようとする問題点〕

従来のページテーブルの空きエントリのサーチは、連続
ページの要求（例えば、４ページ連続確保など）があっ
たとき、ページテーブルの各エントリを１エントリずつ
サーチしているために空きエントリのばらつきなどによ
ってサーチ時間が増加する問題がある。

例えば、第７図に示すようなページテーブルの空きエン
トリの分布があったとして、この状態で４ページの要求
が起こると、ページテーブル共通部の空きエントリの先
頭ポインタより、５エントリ目からサーチすることにな
る。■エントリのサーチに８ステツプかかるとすると４
ページの要求を満たすことのできる３００３エントリま
でサーチした場合、 （３００３−４”）　Ｘ　８　＝２３９９２ステップの
サーチが必要になる。

本発明はこのような問題を解決するもので、ページテー
ブルの空きエントリのサーチを空きエントリの分布によ
る影響を受けずに安定して行える装置を提供することを
目的とする。

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

本発明は、ページテーブルを備え、このページテーブル
の空きエントリをサーチして記憶管理を行う記憶管理装
置において、前記ページテーブルに、エントリをグルー
プに分けてさらにグループをレベル分けし、レベルごと
の各々の空きグループ情報を記憶する空きグループ情報
部を含み、要求ページ数の入力によりこの空きグループ
情報部を参照して各レベルのグループの中からサーチ対
象グループを選択し、要求ページ数を満たす前記ページ
テーブルの空きエントリをサーチする空きエントリサー
チ部と、前記ページテーブルのエントリの返却要求時に
対象となる各レベルのグループの空き情報を更新する空
きエントリ返却部とを備えたことを特徴とする。

〔作用〕

空きグループ情報部がページテーブルのエントリをグル
ープに分けてさらにグループをレベル分けし、レベルご
との各々の空きグループ情報を記憶し、空きエントリサ
ーチ部が要求ページ数の入力により空きグループ情報部
を参照して各レベルのグループの中からサーチ対象グル
ープを選択し、要求ページ数を満たすページテーブルの
空きエントリをサーチし、空きエントリ返却部がページ
テーブルのエントリの返却要求時に対象となる各レベル
のグループの空き情報を更新する。

これにより、ページテーブルの空きエントリのサーチを
空きエントリの分布による影響を受けることなく安定し
て実行することができる。

〔実施例〕

次に、本発明実施例を図面に基づいて説明する。

第１図は本発明実施例の構成を示すブロック図である。

本発明実施例は、ページテーブル１０の空きエントリを
サーチして記憶管理を行う記憶管理装置１００のページ
テーブル１０に、エントリをグループに分けてさらにグ
ループをレベル分けし、レベルごとの各々の空きグルー
プ情報を記憶する空きグループ情報部１を含み、要求ペ
ージ数の人力によりこの空きグループ情報部１を参照し
て各レベルのグループの中からサーチ対象グループを選
択し、要求ページ数を満たすページテーブル１０の空き
エントリをサーチする空きエン）　ＩＪサーチ部２と、
ページテーブル１０のエントリの返却要求時に対象とな
る各レベルのグループの空き情報を更新する空きエント
リ返却部３とを備える。

次に、このように構成された本発明実施例の動作につい
て説明する。

空きグループ情報部ｌはページテーブル１０の各エント
リを数エン）　ＩＪずつのグループに分けて空きエン）
　ＩＪの情報を記憶する。本実施例では第２図に示すよ
うにページテーブルｌＯの１６エントリをレベル１グル
ープの１単位とする。また、１６個のレベル１グループ
をレベル２グループの１単位とする。

このように１ページテーブル内に４０９６エントリが存
在する場合、レベル１グループには２５６個のグループ
、レベル２グループには１６個のグループが存在する。

また、本実施例では第３図に示すようにレベルｌ空きフ
ラグ３１とレベル２空きフラグ３２とをページテーブル
１０のエントリ内に持つ。レベル１空きフラグ３１はペ
ージテーブル１０の先頭エントリから１６エントリごと
のエントリ内に設定される。レベル２空きフラグ３２は
ページテーブルＩＯの先頭エントリから２５６　エント
リごとのエントリ内に設定される。

空きページフラグ３３は従来方式によりページテーブル
の各エン）　ＩＪ内に設定されている。本実施例では１
ビツトで構成され、 ′０”　Ｂのとき二使相中エントリ “１“　Ｂのとき：空きエントリ とする。このビットの更新については従来の記憶管理で
の扱いと同様とする（従来技術参照）。

レベル１空きフラグ３１はページテーブル１０の１６エ
ントリ内の状態を２ビツトで表現し、下記のようにレベ
ル１空きフラグ３１を定義する。

００”　Ｂのとき：ページテーブルの１６エントリはす
べて空きエントリである ０１　Ｂのとき：ページテーブル１０の１６エントリ内
に空きエントリと使用中エントリがある’１１’Ｂのと
き：ページテーブルＩＯの１６エントリ内に空きエント
リが一つもない レベル２空きフラグ３２は１６個のレベルｌグループの
状態を２ビツトで表現し、下記のようにレベル２空きフ
ラグ３２を定義する。

“００゛　Ｂのとき１１６個のレベル１グループはすべ
て空き状態である。つまり１６個のレベル１空きフラグ
３１がすべて“００′　Ｂである’Ｏ１’Ｂのとき１１
６個のレベル１グループは空き状態と使用中状態がある
。つまり１６個のレベル１空きフラグ３１がすべて“０
０′　Ｂではなく、かつ１６個のレベルＩ空きフラグ３
１がすべて’１１’Ｂではない °１１°　Ｂのとき１１６個のレベル１グループは空き
状態のものが１つもない、つまり１６個のレベル１空き
フラグ３１がすべて“１１’Ｂである次に、空きエント
リサーチ部２について説明する。空きエントリ取得要求
が記憶管理袋＠１００内で発生すると、空きエントリサ
ーチ部２に制御を移行する。人力情報として要求ページ
数（＝空きエントリ数）を人力する。また要求ページは
論理空間で連続であるものを対象とする。

第４図に空きエントリサーチ部２の処理の流れを示す。

空きエントリサーチ部２では空きカウンタを０クリアし
くステップ４１）、その後レベル２グループのサーチを
行う（ステップ４２）。レベル２グループのサーチでは
レベル２空きフラグ３２を順に参照する（ページテーブ
ル１０の先頭から２５６エントリごとに参照する）。判
定ステップ４３により処理を振り分ける。

レベル２空きフラグ３２が０１’Ｂのとき、レベル１グ
ループサーチを行う（ステップ４６）。要求ページ≦空
きカウンタが成立するとくステップ４７）、要求ページ
数の確保ができたことになるのでフラグの更新（ステッ
プ４９）を行う。フラグの更新（ステップ４９）では確
保対象となったレベルｌ空きフラグ３ルベル２空きフラ
グ３２をそれぞれ上述したレベル１空きフラグ３１の定
義、レベル２空きフラグ３２の定義に従って更新する。

また、要求ページ数の確保が可能なページテーブル１０
の先頭エントリアドレスを出力情報として要求元に制御
を移行する。

判定ステップ４３でレベル２空きフラグ３２が°１１′
　Ｂのときはカウンタを０にしくステップ４４）、ステ
ップ４２に処理を移し、“００′　Ｂのときは空きカウ
ンタに６４を加算しくステップ４５）、ステップ４７に
処理を移す。

また、ステップ４７で要求ページ≦空きカウンタでない
ときは１６回繰り返したか否かが判定され（ステップ４
８）、繰り返していれば終了し、繰り返していなければ
ステップ４２に処理を移す。

次に、第４図に示すレベル１グループサーチ処理（ステ
ップ４６）を第５図を用いて説明する。レベルｌグルー
プサーチ（ステップ４６）では、レベルｌグループの先
頭から順に（該当するページテーブル１０のエントリか
ら１６エントリごとに参照する）　レベル１空きフラグ
３１を参照する（ステップ５１）。判定ステップ５２に
より処理を振り分ける。

例えば、レベル２空きフラグ３２が“０１′　Ｂのとき
、ページテーブルサーチを行う（ステップ５５）サーチ
後要求ページ≦空きカウンタであるか否か判定され（ス
テップ５６）、そうであれ（ス終了し、そうでなければ
１６回繰り返したか否かが判定され（ステップ５７）、
繰り返していなければステップ５１に処理を移し、繰り
返しでなければ終了する。

また°１１゛　Ｂのときは空きカウンタを０としくステ
ップ５３）、ステップ５１に処理を戻し、　“００′Ｂ
のときは空きカウンタに４加算され（ステップ５４）、
ステップ５６に処理を移す。

次に、ページテーブルサーチ（ステップ５５）を第６図
を用いて説明する。ページテーブルサーチ（ステップ５
５）では、レベル１グループに属するページテーブルの
エントリの先頭から順に空きページフラグ３３を参照す
る（ステップ６１）。判定ステップ６２により処理を振
り分ける。　“１”　Ｂであれば空きカウンタを１加算
しくステップ６４）、要求ページ≦空きカウンタである
か否か判定され（ステップ６５）、そうであれば終了し
、そうでなければ１６回繰り返したか否かが判定され（
ステップ６６）、繰り返されていれば終了し、繰り返さ
れていなければステップ６１に処理を戻す。またステッ
プ６２で“０’　　Ｂのときは空きカウンタを０としく
ステップ６３）、ステップ６１に処理を戻す。

次に、空きエントリ返却部３の説明を行う。空きエント
リ返却要求が発生すると、空きエントリ返却部３に制御
移行する。空きエントリ返却部３では人力情報としての
返却ページのページテーブル１０の先頭エントリアドレ
スと返却ページ数とから、レベル１空きフラグ３１とレ
ベル２空きフラグ３２とをそれぞれレベル１空きフラグ
３１の定義、レベル２空きフラグ３２の定義に従って更
新する。

例えば、第７図に示すようなページテーブルの場合、グ
ループ化により使用中エントリを１エントリずつサーチ
することはなくなるのでサーチに要するステップ数を大
幅に削減することができる。

〔発明の効果〕

以上説明したように本発明によれば、ページテーブルの
空きエントリのサーチを空きエントリの分布による影響
を受けずに安定して行える効果がある。

【図面の簡単な説明】

第１図は本発明実施例の全体構成を示すブロック図。 第２図は本発明実施例レベル化グループの詳細を示す図
。 第３図は本発明実施例の空きグループ情報部を示す図。 第４図は本発明実施例の空きエン）　ＩＪサーチ部の処
理の流れを示すフローチャート。 第５図は本発明実施例のレベル１グループサーチのフロ
ーチャート。 第６図は本発明のページテーブルサーチの流れを示すフ
ローチャート。 第７図はページテーブルの空きエントリ分布の例を示す
図。 １・・・空きグループ情報部、２・・・空きエントリサ
ーチ部、３・・・空きエントリ返却部、１０・・・ペー
ジテーブル、１００・・・記憶管理装置。

Claims (1)

1. 【特許請求の範囲】 １、ページテーブルを備え、このページテーブルの空き
   エントリをサーチして記憶管理を行う記憶管理装置にお
   いて、 前記ページテーブルに、 エントリをグループに分けてさらにグループをレベル分
   けし、レベルごとの各々の空きグループ情報を記憶する
   空きグループ情報部を含み、要求ページ数の入力により
   この空きグループ情報部を参照して各レベルのグループ
   の中からサーチ対象グループを選択し、要求ページ数を
   満たす前記ページテーブルの空きエントリをサーチする
   空きエントリサーチ部と、 前記ページテーブルのエントリの返却要求時に対象とな
   る各レベルのグループの空き情報を更新する空きエント
   リ返却部と を備えたことを特徴とする記憶管理装置。