JPH02201558A

JPH02201558A - 領域管理処理方式

Info

Publication number: JPH02201558A
Application number: JP2047889A
Authority: JP
Inventors: Masashi Washimi; 昌司鷲見
Original assignee: Fujitsu Ltd
Current assignee: Fujitsu Ltd
Priority date: 1989-01-30
Filing date: 1989-01-30
Publication date: 1990-08-09
Anticipated expiration: 2015-04-10
Also published as: JP3030030B2

Abstract

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

Description

【発明の詳細な説明】〔概要〕各エントリごとに管理対象Ｓｒ１域の位置情軸が登録さ
れる管理テーブルを使用して、記憶領域の管理を行う計
算機システムにおいて、管理テーブルの動的生成を行う
領域管理処理方式に関し。

管理対象領域のフラグメントが多発した場合にも、管理
テーブルのエントリ数の制約を受けずに。

効率よく領域を使用することができる手段を提供するこ
とを目的とし。

管理対象領域の変更の際に、既存の管理テーブルのエン
トリが不足した場合、新たに別の管理テーブルを動的に
生成し、既存の管理テーブルに新たな管理テーブルをリ
ンクして、その新たな管理テーブルから、管理対象領域
の登録に用いるエントリを獲得するように構成する。

〔産業上の利用分野〕

本発明は、各エントリごとに管理対象領域の位置情報が
登録される管理テーブルを使用して、記憶領域の管理を
行う計算機システムにおいて、管理テーブルの動的生成
を行う領域管理処理方式に関する。

計ＩＸ機システムにおいては、仮想空間や論理空間など
の記憶領域を３通常、何らかの管理テーブルを使用して
管理している。管理テーブルの構造。

大きさ、使用方法などは、システムの資源量にも関係し
て、システムおよび管理対象ごとにまちまちであり、制
約も異なってくる。

一般に、領域の獲得処理および解放処理が頻繁に繰り返
されると、領域のフラグメントが発生し管理テーブル自
体の領域区画数、すなわち管理テーブルのエントリ数の
制約によって、領域を効率よく使用できない場合が生じ
てくる。

そのため、領域のフラグメントの発生に対して管理テー
ブルの領域区画数の制約に影響されない領域管理処理方
式を実現し、領域を効率よく使用できるようにすること
が必要とされる。

〔従来の技術〕

第６図は従来技術の例を示す。

図中、１００はいわゆる論理空間の管理領域。

ＴＩは管理領域１００における未使用領域を管理するた
めの管理テーブルである。

管理テーブルＴ１は、未使用エントリ数を記憶する管理
情報部と、管理領域ｌＯＯにおける各未使用領域の先頭
アドレスとサイズとを記憶する複数のエントリと、管理
テーブルＴＩの終アをオールＯのコード（以下、Ｎ［Ｊ
ＬＬという）によって示す最終表示部とからなる。

従来技術では、管理テーブルＴＩは、あらかしめシステ
ム空間側の領域に１個または処理単位であるプロセス空
間側の領域ごとに１個用意され未使用領域などの管理対
象領域を登録することのできるエントリ数は、固定であ
った。なお、この例では、管理領域１００の未使用領域
を管理テブルＴ１によって管理しているが、未使用領域
ではなく、使用領域を管理する場合にも、同様な管理テ
ーブルの使用が行われることがある。

（発明が解決しようとする課題）従来の管理テーブルＴＩを使用した領域管理処理方式で
は、管理テーブルＴ１が１個だけ静的に用意されている
だけであるため、領域のフラグメントが発生し、領域が
小さく分割されてしまうと。

管理テーブルＴＩのエントリに不足が生じることがあり
、管理テーブルＴ１のエントリに未使用領域を登録でき
なくなることがある。そのため、領域を効率よ（使用す
ることができない場合が生じるという問題があった。

すなわち、第６図に示す例では、管理テーブルＴＩの１
０２エントリのうち、先頭と最終は管理情報部と最終表
示部として使用しているため、全部で１００個の未使用
領域を管理することができるだけであり、未使用領域の
個数がこれ以上増えると、管理テーブルＴｌによって管
理することはできなかった。

本発明は上記問題点の解決を図り、管理対象領域のフラ
グメントが多発した場合にも、管理テーブルのエントリ
数の制約を受けずに、効率よく領域を使用することがで
きる手段を提供することを目的としている。

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

第１図は本発明の構成例を示す。

第１図において、１０はＣＰＵおよびメモリなどからな
る処理装置、１１はデータ処理に使用する領域の獲得／
解放を要求する領域要求部、１２は記憶領域の管理を行
う領域管理部、１３は管理テーブルエントリ参照・更新
処理部、１４は管理テーブルのエントリポインタを更新
するエントリポインタ更新処理部、１５は管理テーブル
を動的に生成する管理テーブル生成処理部、１６は不要
となった管理テーブルを消去する管理テーブル消滅処理
部、１７は領域の切り出しが行われる記憶領域、ＴＩは
あらかじめ静的に確保される管理テーブル、Ｔ２は必要
なときに動的に確保される管理テーブル、Ａｌ−Ａ３は
記憶領域１７における管理対象領域を表す。

管理テーブルＴｌ、Ｔ２には、各エントリごとに管理対
象領域Ａ１．Ａ２．・・・の位置情報が登録されるよう
になっている。管理対象領域にフラグメントが発生して
いない最初の状態では、管理テ−フルＴＩのみが存在し
、管理テーブル１゛２は設けられない。

領域要求部１１からの領域の獲得および解放要求に対し
て、領域管理部１２は、記憶領域１７から切り出した領
域の割り当ておよび返却を行う。

このとき、管理テーブルエントリ参照・更新処理部１３
によって、管理テーブルＴ　１等の参照・更新を行う。

管理テーブルエントリ参照・更新処理部１３は、エント
リポインタ更新処理部１４．管理テーブル生成処理部１
５．管理テーブル消滅処理部１６を必要に応じて呼び出
し、・ゴ理テーブルＴＩ等への管理対象領域の登録およ
び登録抹消などの処理を行う。

管理対象領域の変更の際に、既存の管理チーフル、例え
ば管理テーブルＴ１のエントリが不足した場合、管理テ
ーブル生成処理部１５によって。

新たに別の管理テーブルＴ２を動的に生成し、既存の管
理テーブルＴ１に新たな管理テーブル゛ｒ２をリンクす
る。すなわち、管理テーブル１゛１における管理情報部
のリンクポインタに、新たに用意した管理テーブルＴ２
の先頭アドレスを設定する。

そして、その新たな管理テーブルＴ２がら、管理対象領
域の登録に用いるエントリを獲得するようにする。さら
に、領域のフラグメントが進み、管理テーブルＴ２のエ
ントリも不足する場合には。

同様に新しい管理テーブルを動的に生成して使用する。

エントリポインタ更新処理部１４は、必要とする１丁理
対象領域ＡＩ、Ａ２．　・・・を検索するときに管理テ
ーブルＴ１．”ｌ”２等におけるエントリのポインタを
更新する処理を行うものである。１つの管理テーブル内
では、■エントリずつポインタを進め２例えば管理テー
ブルＴ　Ｉの最終エントリから管理テーブルＴ２の先頭
エントリへ移る場合には、管理情報部のリンクポインタ
を使用することにより、エントリポインタの更新を行う
。

Ｒ理対象領域Ａ１．Ａ２．・・・のフラグメントが少な
くなり、動的に生成した管理テーブルＴ２などが不要と
なった場合には、管理テーブル消滅処理部１Ｇにより、
管理テーブルＴ２を消滅させ管理テーブルＴＩのリンク
ポインタをＮＵＬＬにする。

〔作用〕

本発明では、必要に応して管理テーブルが動的に生成さ
れ５　システム空間側の領域に数個あるいはプロセス空
間側の領域ごとに数個用意できる。

したがって、１つの管理テーブルのエントリ数が少ない
場合であっても、エントリ数の不足により管理できなく
なる領域が生じることはなく、フラグメントが多発して
も１領域を有効に使用できるようになる。　特に５管理
テーブルＴｌ、Ｔ２等に対する領域の検索のためのポイ
ンタを更新する処理を、エントリポインタ更新処理部１
４のように１部品化して用意するようにすれば１通常の
エントリへのアクセスでは、複数個の管理テーブルを意
識する必要がなく、処理の複雑化を避けることも可能で
ある。

〔実施例〕

第２図は本発明の実施例、第３図は本発明の実施例に係
るエンＩ−ＩＪ参照・更新処理の例、第４図は本発明の
実施例に係る管理テーブル生成処理の例、第５図は本発
明の実施例に係るエントリポインタ更新処理の例を示す
。

第２図は、管理領域１００における未使用領域を、管理
対象領域として、管理テーブルＴｌ、Ｔ２によって管理
する例を示している。

管理テーブル”］”ｉＴ２は、それぞれ１個の管理情報
部と、１００個の未使用領域を登録することのできるエ
ントリと、１個の最終表示部とからなる。管理情報部は
、未使用エントリ数の記憶域と１次の管理テーブルの先
頭アドレスを記憶するリンクポインタの領域とを持つ。

最終管理テーブルのリンクポインタの値は、ＮＵＬＬで
ある。

静的にあらかじめ用意されるのは、管理テーブルＴＩだ
けであるが、管理領域１００における未使用領域の個数
が１００個を超える場合には、新たに、管理テーブルＴ
２が動的に生成され、管理テーブルＴ１にリンクされる
。

第２図に示す例では、未使用領域が１０２個あるので、
管理テーブルＴＩに１００個の未使用領域、管理テーブ
ルＴ２に２個の未使用領域が登録されている。

ここでは、未使用領域を管理対象としているが。

使用領域を管理する場合にも、同様な管理テーブルの構
成により、エントリ数に制約されることなく、管理する
ことができる。

領域の獲得要求により１未使用領域から指定された大き
さの領域を切り出す場合９例えば第１図に示す管理テー
ブルエントリ参照・更新処理部１３は、第３図に示すよ
うな処理を行う。以下の説明における■〜０は、第３図
に示す処理■〜０に対応する。

■　まず、管理テーブルを検索するためのエントリのア
ドレスを、最初の未使用領域のエントリアドレスとする
。

■　未使用領域のサイズと、要求された割り当てサイズ
との比較により、領域の割り当てが可能であるかどうか
を判定する。割り当て可能である場合、処理■へ移る。

なお、この割り当て可否の判定では、領域の使用目的に
より、ページ境界を意識して９切り出す領域がページ境
界をまたがらないことを条件としてもよい。

■　領域の割り当てが不可である場合、エントリポイン
タ更新処理により、検索するエントリのアドレスを１工
ントリ分だけ先に進める。

■　次のエントリにおけるサイズの値がＮ（ＪＬＬであ
るかどうかを判定する。ＮＵＬＬであれば。

領域を割り当てることができる未使用領域は存在しない
ので１割り当て不可を呼び出し元に通知し、処理を終了
する。ＮＵＬＬでなければ処理■へ制御を戻し、同様に
処理を繰り返す。

■　領域の割り当てが可能である場合、現エントリの内
容、すなわち領域切り出し後の未使用領域のアドレスと
サイズとを更新する。

■　そのエントリの削除が必要であるかどうかを判定す
る。残った未使用領域のサイズが０である場合、エント
リの削除が必要である。エントリの削除が必要でない場
合、呼び出し元へ割り当て領域のアドレスを通知し、制
御を戻す。

■〜■　エントリの削除が必要な場合、エントリポイン
タ更新処理により、処理対象とするエントリのアドレス
を１工ントリ分だけ先に進める。

そして、直後のエントリの内容を現エントリに設定する
。これをエントリのサイズ（ｓｉｚｅ）情報が０になる
まで繰り返す。

■　管理テーブルの管理悄ｔ１１部における未使用エン
トり数に１を加算する。

■　管理テーブルの削除が必要かどうかを判定する。管
理テーブルの削除を行うのは、その管理テーブルがすべ
て未使用エントリとなり、かつそれが先頭の管理テーブ
ルではない場合である。

＠〜０　管理テーブルの削除が必要な場合、管理テーブ
ル消滅処理を実行する。すなわち、管理テーブルの領域
を解放し、前の管理テーブルのリンクポインタにＮＵＬ
Ｌを設定する。その後。

呼び出し元へ制御を戻し、処理を終了する。

以上、領域の獲得要求に対する管理テーブルの扱いにつ
いての処理の例を説明したが、領域の解放要求に対する
処理も、同様にエントリポインタを更新しつつ処理を行
う。領域の返却により、未使用領域の数が増えた場合に
は、エントリへの追加登録が行われ、特に、管理テーブ
ルのエントリが不足した場合には、前述したように、管
理テーブルの動的生成が行われる。

この管理テーブル生成処理は９例えば第４図に示す処理
■〜■のように行われる。

■　先頭の管理テーブルのアドレ・スを得る。

■〜■　リンクポインタがＮＵＬＩ、になるまで。

管理テーブルのリンクポインタをたどり、最終の管理テ
ーブルを探す。

■　最終の管理テーブルにおける未使用エントリ数がＯ
であるかどうかを判定する。０でない場合、管理テーブ
ルの生成は必要ないので、呼び出し元へ制御を戻す。

■〜■　未使用エントリ数が０のときは、新しい管理テ
ーブルを追加するため、管理テーブルを設ける領域を、
システム空間側の領域であれば。

システム空間の領域から、プロセス空間側の領域であれ
ばプロセス空間の領域から獲得する。

その獲得した領域を用いて、管理テーブルの初期化を行
う。この初期化では、管理テーブルをオール０にクリア
した後、未使用エントリ数を最大エントリ数に設定する
。そして、その管理テーブルのアドレスを、現管理テー
ブルのリンクポインタに設定し、管理テーブルをリンク
する。その後５呼び出し元へ制御を戻す。

第１図に示すエントリポインタ更新処理部１４によるエ
ントリポインタ更新処理は、第５図に示す処理■〜■の
ように行われる。

■　現管理テーブルアドレスを退避する。

■　リンクポインタがＮ　Ｕ　Ｌ　Ｌであるかどうかを
判定する。ＮＵＬＬである場合、処理■へ移る。

■　次に、直後のエントリのサイズ（ｓｉｚｅ）［４￥
ＪｉｉがＮＵＬＬであるかどうかを判定する。ＮｔＪＬ
Ｌでない場合、処理■へ移る。

■〜■　現管理テーブルアドレスを退避し、現管理テー
ブルアドレスを、リンクポインタの示すイ直にする。そ
して、現エントリポインタとして。

次の管理テーブルのエントリアドレスを設定し呼び出し
元へ制ｉ’ｔｌｌを戻す。

■　管理テーブルを切り替える必要がない場合。

現エントリポインタを、エントリサイズ分だけ先に進め
るように更新し、呼び出し元へ制御を戻す。

以上の処理によって、先頭の管理テーブルから。

順にエントリを検索する場合に、エントリポインタ更新
処理部１４の外部では、管理テーブルの切り替わりを意
識する必要がなくなる。

〔発明の効果〕

以上説明したように１本発明によれば５管理テブルが必
要に応じて動的に生成されるので、領域のフラグメント
が発生しても、管理テーブルの使用可能なエントリ数の
制約による影古を回避することができ、領域を効享よ（
使用することができるようになる。

【図面の簡単な説明】

第１図は本発明の構成例。第２図は本発明の実施例。第３図は本発明の実施例に係るエントリ参照・更新処理
の例第４図は本発明の実施例に係る管理テーブル生成処理の
例。第５図は本発明の実施例に係るエントリポインタ更新処
理の例。第６図は従来技ｊ・ＦｊＯ例を示す。図中、１０は処理装置、１１は領域要求部、１２は領域
管理部、１３は管理テーブルエントリ参照・更新処理部
、１４はエントリポインタ更新処理部、１５は管理テー
ブル生成処理部、１６は管理テーブル消滅処理部、１７
は記憶領域、ＴＩＴ２は管理テーブル、Ａｌ−Ａ３は管
理対象領域を表す。

Claims

【特許請求の範囲】各エントリごとに管理対象領域の位置情報が登録される
管理テーブルを使用して、記憶領域（１７）の管理を行
う計算機システムにおける領域管理処理方式において、管理対象領域の変更の際に、既存の管理テーブル（Ｔ１
）のエントリが不足した場合、新たに別の管理テーブル
（Ｔ２）を動的に生成し、既存の管理テーブル（Ｔ１）
に新たな管理テーブル（Ｔ２）をリンクして、その新た
な管理テーブル（Ｔ２）から、管理対象領域の登録に用
いるエントリを獲得するようにしたことを特徴とする領
域管理処理方式。