JPS6367656A - デ−タ格納領域管理処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 記憶装置の記憶領域管理の処理効率を改善する管理処理
方式である。

種々の大きさの空き領域を、すべてチェインして管理す
るのでな（、一定長より大きい領域のみチェインして空
き領域探索の対象にし、使用中の必要領域が縮小した等
で空きになる領域が、前記の一定長以下のときは、空き
領域合計量のみを更新する。

この方式により、空き領域チェインの更新頻度の減少、
チェイン走査の高速化等ができる。

〔産業上の利用分野〕

本発明は、計算機システム等の記憶装置の記憶領域の管
理処理方式に関する。

データベースのデータを格納する記憶装置等では、新デ
ータの格納、格納データの更新によるデータ長の増減等
による空き領域の増減に対し、一般に何等かの領域管理
処理が必要である。

〔従来の技術〕

第２図は、計算機の一構成例を示すブロック図である。

処理装置１は主記憶装置２にロードされたプログラムを
実行して、例えば磁気ディスク記憶装置等で構成される
記憶装置３に格納された、データベースを管理する。

記憶装置３の記憶領域は、例えば一定の領域長（例えば
４０９６バイト）の、ページ等と呼ばれる記憶ブロック
に分割して管理される。

各ページ１０は、第３図（ａｌに例示するように、各デ
ータに対して、それぞれのデータ長に応じて割ａ、ｂ、
ｃ等と、未だ割り当てられていない空き領域（図で白抜
きの部分）α、β、Ｔ等、及び所定の制御情報領域から
なる。

各ページ１０は、初めは例えば制御情報領域部分を除く
全領域を１個の空き領域とし、例えば先頭から順次、格
納する各データに領域を分割して、隙間なく各データ領
域を割り当て、後部に連続した空き領域を残すようにす
ることができる。

しかしその後、格納したデータの更新によるデータ長の
増減、或いは削除等により、比較的小さく分割された空
き領域が散在するようになる。

そのため、第３図（ａｌにのように、制御情報領域内に
設ける制御域１１に、例えばページ内変位アドレスで示
すポインタを保持して、チェインの先頭になる１空き領
域の先頭をポイントする。

各空き領域の例えば先頭の部分には、その空き領域の領
域長を示すバイト数表示と、次の空き領域の先頭を指す
次領域ポインタとを保持し、ページ１０内のすべての空
き領域を接続したチェインを構成する。

チェインの末尾の領域は、例えばその次領域ポインタを
特定の値（例えばすべて１のビットからなる値）にして
識別できるようにする。

又、制御域１２にはすべての空き領域の領域長の合計を
、制御域１３には最大の空き領域の最大領域長を示すバ
イト数を保持する。

なお、割り当て済みのデータ領域については、制御情報
領域１４に保持する、各データ領域ごとのポインタとバ
イト数表示によって、それぞれの領域のアドレスと領域
長が示される。

データの更新等により記憶領域の所要領域長が増減した
場合、新たにデータを追加する場合、格納されているデ
ータを削除した場合等には、更新等の各処理を行ったプ
ログラムから発生される領域管理要求により、第４図に
処理の流れを示す領域管理処理が実行される。

第４図において、処理ステップ２０で要求が記憶領域を
取得する要求か、空き領域を返却する要求かにより処理
を分類する。

領域取得要求の場合には、処理ステップ２１において、
領域を探すべきページを選択する。この選択は、各ペー
ジ１０の制御域１３の最大領域長を、要求の５頁域長と
比較して、要求値を越える最大領域長の空き領域を持つ
１ページを決定する。なお、この要求が格納データの更
新によるデータ長増大による場合には、元のデータを格
納しているページを優先して選択するものとする。

所要条件を満たすページがある場合には、処理ステップ
２２で、前記のように制御域１１のポインタに始まる空
き領域のチェインをたどり、チェイン内の各空き領域の
領域長を要求領域長と比較することにより、要求の領域
長以上の大きさの空き領域の１つを選択する。

処理ステップ２３で、選択した空き領域をチェインから
外すように、チェインのポインタの更新処理をし、処理
ステップ２４で選択した空き領域のアドレス等を要求元
に通知して、該領域を使用可能にする。

以上により、チェインの状態が変わったので、処理ステ
ップ２５で、今割り当てた領域の領域長と制御域１３の
値を比較し、一致した場合は処理ステップ２６でチェイ
ンの全空き領域を走査して、最大の領域長を求め、その
値を制御域１３の最大値として設定する。

次に処理ステップ２７で、制御域１２の空き領域長の合
計値から、いま割り当てた領域の大きさを減じて合計値
を更新して処理を終わる。

もし、処理ステップ２１で適当なページが無い場合には
、処理ステップ２８で、各ページの制御域１２の合計値
を要求長と比較して、空き領域長の合計値が要求の大き
さを満たすページを探す。

所要のページがあれば処理ステップ２９において、公知
のいわゆるガーベジコレクション処理を実行して、その
ページの割り当て済みのデータ領域を例えば先頭の方へ
つめ、空き領域を後部にまとめるようにして、大きな空
き領域を作り、処理ステップ２４に進んで、空き領域を
要求元に渡す。

処理ステップ２８でも、所要の条件を満たすページが無
い場合には、既存ページの範囲では要求を満たすことが
できないので、本処理を終了して適当な異常処理を開始
する。

領域の返却要求の場合には、処理ステップ２０から処理
ステップ３０に進み、要求元から渡された領域に前記の
ような所定の空き領域情報を書込み、処理ステップ３１
において、その領域のページの空き領域チェインに接続
する。

チェインへの接続は、例えば制御域１１のポインタの値
を接続する空き領域内の次領域ポインタに設定し、制御
域１１には接続する領域のアドレスを設定することによ
り行われる。

次に処理ステップ３２で、返却された領域の領域長と制
御域１３に保持する最大値とを比較し、返却領域の方が
大きい場合には、処理ステップ３３で返却領域領域長を
制御域１３に設定して最大値を更新する。

又、処理ステップ３４で、返却領域の領域長によって、
制御域１２に保持する空き領域長合計値を増加して処理
を終わる。

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

前記説明のように領域管理処理では、領域取得及び返却
要求の場合に、毎回空き領域のチェインの更新処理が伴
い、又領域取得のために空き領域を走査する場合には、
そのページの全空き領域をつないだ比較的長いチェイン
をたどらなければならないので、領域管理のオーバヘッ
ドが比較的大きくなり、改善が望まれていた。

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

第１図は、本発明の構成を示す処理の流れ図である。

図において、４０は領域返却処理手段、４１は領域取得
処理手段を構成する処理を示す。

〔作　用〕

従来のように領域管理の処理要求があり、それが領域返
却処理であると、処理ステップ２０から領域返却処理手
段４０が起動される。

領域返却処理手段４０は返却された領域が一定の領域長
より大きいとき、その領域を空き領域のチェインに接続
し、それ以下の大きさの領域の場合には、単に制御域１
２の空き領域長合計値に返却領域長を加えるのみで処理
を終わる。

要求が領域取得の場合に、領域取得手段４１は従来と同
様の処理で、但し前記のようにして構成される一定の領
域長より大きな空き領域のみのチェインから空き領域を
選択する。

以上の方式により、領域返却処理でチェインを処理する
場合が減少し、又領域取得処理で走査するチェインの長
さが短縮されるので、領域管理の処理時間を減少するこ
とができる。

〔実施例〕

第１図において、処理ステップ２ｏで要求が記憶領域を
取得する要求が、空き領域を返却する要求かにより処理
を分類する。

領域の返却要求の場合には、処理ステップ２ｏがら領域
返却処理手段４０の処理ステップ４２に進み、要求元か
ら渡された領域に、前記と同様に空き領域情報を書込む
。

次に処理ステップ４３において、返却領域の領域長が、
このシステムで規定されている一定の領域長より大きい
か比較判定する。

一定の領域長には、例えばこのデータベース等を構成す
るデータの平均長をとり、システムの制御定数として領
域管理プログラム内に指定しておくものとする。

返却領域が一定長より大きい場合には、処理ステップ４
４で返却領域を空き領域のチェインに接続する。チェイ
ンへの接続処理は、従来と同様でよく、例えば制御域１
１のポインタでポイントされる、チェインの先頭に返却
領域を挿入する。

その後処理ステップ４５．４６により、従来と同様にし
て、必要な場合に制御域１３の保持する最大領域長の値
を更新し、処理ステップ４７で制御域１２の空き領域長
合計値を増加して処理を終わる。

処理ステップ４３で返却領域の大きさが一定長以下であ
った場合には、以上のチェインへの接続処理を行わず、
直ちに処理ステップ４７に進んで、制御域１２の更新の
み行って処理を終わる。

このようにして構成されるチェインの一例を、第３図（
′ｂ）に示す。

第３図（′ｂ）は、前記に説明した第３図（ａ）と同じ
空き領域状態のページの例であるが、本発明により、比
較的小さな空き領域α及びγはチェインされず、空き領
域β及びδのみがチェインを構成する。なお、制御域１
２の空き領域の合計値及び制御域１３の最大領域長の値
は、（ａ）と（ｂｌで同一の値が保持される。

領域取得要求の場合の、領域取得処理手段４１による処
理は、処理ステップ２１〜２７によって、従来と同様の
処理が実行される。

しかし、処理ステップ２２において走査されるチェイン
が、前記のように一定長より大きな空き領域のみを選択
して構成されるチェインであるので、走査するチェイン
が比較的短く、要求領域長を越える領域に到達し易いの
で、短時間で処理することができるようになる。

〔発明の効果〕

以上の説明から明らかなように、本発明によれば、計算
機システムのデータベース等のデータを格納する領域の
管理において、データ格納領域の取得及び返却における
管理処理のオーバヘッド時間が削減されるので、システ
ムの処理効率を改善するという著しい工業的効果がある
。

【図面の簡単な説明】

第１図は本発明の構成を示す処理の流れ図、第２図は計
算機システムの一構成例ブロック図、第３図はページの
状態を説明する図、 第４図は従来の処理の流れ図 である。 図において、 １は処理装置、　　　　２は主記憶装置、３は記憶装置
、　　　　１０はページ、１１．１２．１３は制御域、
　１４は制御情報、２０〜３４．４２〜４７は処理ステ
ップ、４０は領域返却処理手段、４１は領域取得処理手
段本発明の１成を示す処理の流れ図 第１図 計算機システムの一構成例ブロフク図 第２図 ページの状態を説明する図 従来の処理の流れ図 第４図

Claims (1)

1. 【特許請求の範囲】 記憶装置の所定の記憶ブロックにデータを格納するため
   の空き領域の管理において、 該記憶ブロック内の、すべての空き領域の領域長の合計
   値を計算して保持する手段（４０）と、該記憶ブロック
   内の、所定の領域長を越える該空き領域を連結してチェ
   インを構成する手段（４０）とを設け、 所要長のデータを格納する場合には、該チェインを構成
   する領域の中から、該所要長以上の領域長を有する領域
   を選択し（４１）、 該所定の領域長以下の空き領域が発生した場合には、前
   記合計値の更新のみを行う（４０）ように構成されてい
   ることを特徴とするデータ格納領域管理処理方式。