JPH09305479A - 記憶装置の動的記憶領域管理装置 - Google Patents

Abstract

(57)【要約】 【課題】 動的記憶領域を複数のグループに分割して動
的記憶領域の確保及び解放ができ、動的記憶領域の検出
に要する時間の短縮を実現する動的記憶領域管理装置を
提供する。 【解決手段】 記憶領域を複数のグループに分割し該グ
ループごとの管理情報を格納する管理情報格納部３０
と、記憶領域中に所定の領域を確保する領域確保要求を
受け付け、管理情報格納部３０に格納された管理情報を
参照して記憶領域の所望のグループに所望の領域を確保
する領域確保処理部４１と、記憶領域中の所定の領域を
解放する領域開放要求を受け付け、管理情報格納部３０
に格納された管理情報を参照して記憶領域の所望のグル
ープに所属する該当領域を開放する領域解放処理部４２
とを備える。

Description

【発明の詳細な説明】

【０００１】

【発明が属する技術分野】本発明は、メモリや磁気ディ
スク装置等の記憶装置の記憶領域を管理する記憶領域管
理装置に関し、特に記憶領域の確保または解放の要求に
応じて適当な動的記憶領域を確保し、または解放する動
的記憶領域管理装置に関する。

【０００２】

【従来の技術】コンピュータシステムでは、メモリや磁
気ディスク装置等の記憶装置に対して中央処理装置（Ｃ
ＰＵ）や周辺装置の各種プロセスから記憶領域の確保要
求や解放要求が出された場合に、オペレーティングシス
テム等で制御された記憶領域管理装置により、当該要求
に応じた適当な動的記憶領域の確保や解放を行う。

【０００３】従来のオペレーティングシステムにより制
御された記憶領域管理装置は、管理対象である動的記憶
領域の全体を１つのグループとみなして、ソフトウエア
実行中に動的記憶領域の確保処理または解放処理を行な
っていた。

【０００４】従来のこの種の動的記憶領域管理技術とし
ては、例えば、特公平５−２７４２２１号公報に開示さ
れた技術がある。同公報には、動的割当領域を各種プロ
セスからの要求に応じて分割、割り当て、解放等の処理
を行い、また、動的割当領域を可変長のサイズのブロッ
ク（動的割当領域ブロック）に分割して管理する、動的
領域の管理方式について記載されている。

【０００５】また、従来の他の動的記憶領域管理技術と
して、特開平３−１３２８４０号公報に開示された技術
がある。同公報には、主メモリの各ブロック内の分割エ
リアにへッダを設け、そのへッダ内にメモリフリーリス
ト用のポインタ値または割り付け済みを示すメモリ割り
付け管理テーブルで主メモリのブロック内の分割エリア
を管理する、メモリアロケーション装置について記載さ
れている。

【０００６】

【発明が解決しようとする課題】しかし、上述した従来
の動的記憶領域管理装置は、動的記憶領域の確保や解放
を行なうための該当動的記憶領域の検出に時間がかかる
という欠点があった。その理由は、動的記憶領域の全体
を１つのグループとみなして管理を行なっていたからで
ある。

【０００７】本発明の目的は、上記従来の欠点を解決
し、動的記憶領域を複数のグループに分割して動的記憶
領域の確保及び解放ができる動的記憶領域管理装置を提
供することにある。

【０００８】本発明の他の目的は、動的記憶領域の確保
及び解放を行なうための該当動的記憶領域の検出に要す
る時間の短縮を実現する動的記憶領域管理装置を提供す
ることにある。

【０００９】

【課題を解決するための手段】上記の目的を達成するた
め、本発明の動的記憶領域管理装置は、記憶装置の記憶
領域を複数のグループに分割し該グループごとの管理情
報を格納する管理情報格納手段と、前記記憶装置の記憶
領域中に所定の領域を確保する領域確保要求を受け付
け、前記管理情報格納手段に格納された管理情報を参照
して前記記憶装置の記憶領域の適当なグループに所望の
領域を確保する領域確保処理手段と、前記記憶装置の記
憶領域中の所定の領域を解放する領域開放要求を受け付
け、前記管理情報格納手段に格納された管理情報を参照
して前記記憶装置の記憶領域の所望のグループに所属す
る該当領域を開放する領域解放処理手段とを備え、前記
領域確保手段は、前記領域確保要求に含まれる前記グル
ープの指定に応じて該グループから前記領域確保要求を
満足するサイズの領域の探索を開始し、前記領域解放手
段は、前記領域解放要求に含まれる前記グループの指定
に応じて該グループから前記領域開放要求にて指定され
た領域の探索を開始する構成としている。

【００１０】また、他の態様では、前記領域確保処理手
段は、前記領域確保要求により指定されたグループに前
記領域確保要求を満足するサイズの領域が存在しない場
合に、他のグループに対して前記領域確保要求を満足す
るサイズの領域の探索を行い、該当領域を検出した場合
に、該検出した領域を確保する。

【００１１】さらに他の態様では、前記領域確保処理手
段は、前記領域確保要求を満足するサイズの領域を確保
した場合に、該領域の所属するグループを特定する情報
を前記領域確保要求の発行元に通知する。

【００１２】また、他の好ましい態様では、前記領域解
放処理手段は、前記領域開放要求により指定されたグル
ープに前記領域開放要求にて指定された領域が存在しな
い場合に、他のグループに対して前記領域開放要求を満
足するサイズの領域の探索を行い、該当領域を検出した
場合に、該検出した領域を開放する。

【００１３】

【発明の実施の形態】以下、本発明の実施例について図
面を参照して詳細に説明する。

【００１４】図１は、本発明の１実施例による動的記憶
領域管理装置の構成を示すブロック図である。

【００１５】図示のように、本実施例の動的記憶領域管
理装置２０はプログラム制御されたＣＰＵとＲＡＭ等の
メモリとで実現され、動的記憶領域１０を備える記憶装
置に接続されており、動的記憶領域１０の管理情報を格
納する管理情報格納部３０と、記憶装置に対して動的記
憶領域１０の確保処理及び解放処理を実行する領域処理
部４０とを備える。なお、図には本実施例の特徴的な構
成のみを記載し、他の構成については記載を省略してあ
る。

【００１６】動的記憶領域１０は、ＲＡＭ等のメモリで
実現される主記憶装置（仮想アドレス空間を含む）上の
記憶領域である。当該動的記憶領域１０は、複数のグル
ープ１１、１２、・・・に分割されており、各グループ
１１、１２、・・・は、複数の管理単位領域に分割され
ている。図示の例では、Ａグループ１１に３つの管理単
位領域Ａ１、Ａ２、Ａ３を備え、Ｂグループ１２に３つ
の管理単位領域Ｂ１、Ｂ２、Ｂ３を備える。

【００１７】各管理単位領域は、当該管理単位領域を管
理するための管理情報部と記憶領域の確保や解放に用い
る領域とを備える。管理情報部には、少なくとも当該領
域の最も大きい空きサイズに関する情報と次に位置する
管理単位領域のアドレスとを格納してある。図３に、図
１の動的領域１０のＡグループ１１の管理単位領域Ａ１
の構成例を示す。図示のように、Ａグループ１１の管理
単位領域Ａ１は、当該管理単位領域Ａ１の最大空きサイ
ズ情報及び次の管理単位領域である管理単位領域Ａ２の
アドレスを格納した管理情報部Ａ１１と、記憶領域とし
て用いる領域Ａ１２とを備える。

【００１８】管理情報格納部３０は、動的記憶領域１０
に形成されるグループ１１、１２、・・・ごとに当該グ
ループに関するグループ情報３１、３２、・・・を格納
してある。格納する情報には、少なくとも、当該グルー
プの最も大きい空きサイズに関する情報と、当該グルー
プの次に位置するグループ情報のアドレスと、当該グル
ープの先頭アドレスとを含む。図２に、図１の動的記憶
領域１０のＡグループ１１に関するグループ情報の構成
例を示す。図示のように、Ａグループ１１のグループ情
報３１は、Ａグループ１１内の最大空きサイズ情報３１
１、次のグループであるＢグループのアドレス３１２、
Ａグループの先頭アドレス３１３が含まれている。

【００１９】領域処理部４０は、動的記憶領域１０に記
憶領域の確保を行う領域確保処理部４１と、動的記憶領
域１０の所定の記憶領域の解放を行う領域解放処理部４
２とを備える。領域確保処理部４１、領域解放処理部４
２は、それぞれＣＰＵや外部の処理装置であって動的記
憶領域１０へのアクセスを行う領域確保要求元５０、領
域解放要求元６０からの要求に応じて処理を実行する。
また、領域処理部４０は、例えばオペレーティングシス
テムの一部として設けられる。

【００２０】領域確保処理部４１は、領域確保要求元５
０からの要求を受け付け、確保しようとする記憶領域の
サイズと当該領域を確保するために指定されたグループ
に関する情報を取得し、当該情報に応じて動的記憶領域
１０の該当するグループに要求サイズを確保する。図４
のフローチャートを参照して、領域確保処理部４１の動
作について説明する。

【００２１】領域確保要求元５０から確保しようとする
記憶領域のサイズと当該記憶領域を確保するグループと
を指定する領域確保要求があると、領域処理部４０の領
域確保処理部４１は、当該確保要求で指定されたグルー
プ番号（Ａ〜Ｘのいずれか）に対応するグループ情報部
の管理情報格納部３０におけるアドレスを取得する（ス
テップ４０１）。そして、要求するグループ内に領域を
確保可能かどうかを調べるため、グループ情報部３１、
３２、・・・の該当グループの最大空きサイズ情報と要
求されている領域サイズとを比較する（ステップ４０
２）。要求されているグループへ当該領域を確保可能な
場合は、当該グループ内の先頭アドレスを当該グループ
情報部から取得する（ステップ４０３）。

【００２２】要求されているグループへ当該領域を確保
不可能な場合は、当該領域を別のグループに確保するた
め次のグループの情報部アドレスを取得する（ステップ
４０４）。このときすべてのグループのサーチが終了し
ていなければ当該グループへ当該領域を確保可能かを調
べる（ステップ４０５、ステップ４０２）。この処理
は、確保要求されている領域を確保可能なグループが見
つかるまで繰り返される。ただし、全グループのサーチ
が終了しても要求サイズを確保可能な空き領域が見つか
らない場合は、領域確保要求元５０へ当該領域を確保で
きないことを通知する（ステップ４０６）。

【００２３】上記ステップ４０２からステップ４０６ま
での処理により要求されている領域を確保可能なグルー
プが確定し、ステップ４０３の処理によりグループ内の
先頭のアドレスを取得した後、当該グループのどの管理
単位領域に当該記憶領域の確保が可能かを順番にサーチ
する。

【００２４】まず、管理単位領域内の管理情報部を参照
し、当該管理単位領域の最大空きサイズと確保要求され
ている領域サイズとを比較し、確保可能であれば、当該
管理単位領域の空き領域に確保要求されているサイズ分
の動的記憶領域を確保する（ステップ４０７、４０
８）。そして、当該管理単位領域の管理情報の最大空き
サイズ情報を更新し（ステップ４０９）、さらに動的領
域管理装置２０の管理情報格納部３０に格納されている
当該グループのグループ内最大空きサイズ情報を更新す
る（ステップ４１０）。この後、領域確保処理部４１
は、領域確保要求元５０へ確保した動的記憶領域の先頭
アドレスと、確保先のグループの番号を通知する（ステ
ップ４１１）。

【００２５】これに対し、当該管理単位領域に要求され
ている領域の確保が不可能であれば、次の管理単位領域
のアドレスを取得する（ステップ４０７、４１２）。こ
のとき、当該グループ内の全ての領域をサーチ終了して
いなければ、当該管理単位領域内に要求されている記憶
領域の確保が可能か調べる（ステップ４１３、ステップ
４０７）。この処理は要求されている記憶領域の確保が
可能な管理単位領域が見つかるまで繰り返される。当該
グループ内の全領域のサーチが終了しても要求サイズを
確保可能な空き領域がない場合、ステップ４０２におけ
る判断と矛盾するため、処理結果が異常であると認識
し、領域確保要求元５０へ異常終了を通知する（ステッ
プ４１４）。

【００２６】領域解放処理部４２は、領域解放要求元６
０からの要求を受け付け、解放し空き領域とする記憶領
域に関する情報を取得し、当該情報に応じて動的記憶領
域１０の該当する領域を検出し、解放して空き領域とす
る。図５のフローチャートを参照して、領域解放処理部
４２の動作について説明する。

【００２７】領域解放要求元からアドレスとグループと
を指定する領域解放要求があると、領域処理部４０の領
域解放処理部４２は、当該確保要求で指定されたグルー
プ番号（Ａ〜Ｘのいずれか）に対応するグループ情報部
の管理情報格納部３０におけるアドレスを取得する（ス
テップ５０１）。そして、当該グループ情報部を参照し
て当該グループ内の先頭のアドレスを取得し（ステップ
５０２）、取得したアドレスが解放要求されている動的
記憶領域のアドレスに該当するか調べる（ステップ５０
３）。アドレスが該当する場合は、当該動的記憶領域の
解放を行なう（ステップ５０４）。

【００２８】取得しているアドレスが解放要求のアドレ
スに該当しない場合、当該取得アドレスにて特定される
管理単位領域の管理情報部を参照し、次の管理単位領域
のアドレスを取得する（ステップ５０５）。そして、こ
の処理により当該グループ内の全ての管理単位領域をサ
ーチ終了していなければ、当該管理単位領域のアドレス
が解放要求のアドレスに該当するか調べる（ステップ５
０６、ステップ５０３）。一方、当該グループの全ての
管理単位領域をサーチ終了した場合は、次のグループの
グループ情報部の管理情報格納部３０におけるアドレス
を取得する（ステップ５０７）。そして、当該グループ
情報部を参照して当該グループ内の先頭のアドレスを取
得し（ステップ５０８、５０２）、取得したアドレスが
解放要求されている動的記憶領域のアドレスに該当する
か調べる（ステップ５０３）。この処理は全てのグルー
プのサーチが終了するまで行われる。全てのグループの
サーチが終了しても解放要求のアドレスに該当する動的
記憶領域１０のアドレスを見つけだすことができなかっ
た場合は、領域解放要求元６０に対して異常終了を通知
する（ステップ５０８、５０９）。

【００２９】上記ステップ５０３からステップ５０９ま
での処理により解放要求のアドレスを有する管理単位領
域を検出した場合、ステップ５０４の処理により当該動
的記憶領域を解放した後、当該管理単位領域の管理情報
の最大空きサイズ情報を更新し（ステップ５１０）、さ
らに動的領域管理装置２０の管理情報格納部３０に格納
されている当該グループのグループ内最大空きサイズ情
報を更新する（ステップ５１１）。この後、領域解放処
理部４２は、領域解放要求元６０へ確保した動的記憶領
域の先頭アドレスと、確保先のグループの番号を通知す
る（ステップ５１２）。

【００３０】図６は、動的領域管理装置２０により分割
管理される動的記憶領域１０と動的管理装置２０の管理
情報格納部３０との関係を具体的な設定例を提示して示
す図である。

【００３１】本設定例では、動的記憶領域１０に設けら
れるグループの個数をあらかじめ２個と決めておく。し
たがって、オペレーティングシステムを立ち上げる際、
メモリマップの初期設定の時点で、動的記憶領域１０を
２つのグループに均等に分割して割り当てる。また、そ
れぞれのグループは、１単位６４ＫＢの管理単位領域の
集合として構成するように初期化を行なう。動的記憶領
域１０は、システムの大きさによって６４ＫＢ単位でサ
イズを設定するため、各グループに割り当てる領域サイ
ズは可変となる。例えば、動的記憶領域１０のサイズを
６４ＫＢ＊８とした場合、２つのグループに均等に、６
４ＫＢの管理単位領域を４個ずつ割り当てることとな
る。

【００３２】以上のように複数のグループに分割した動
的記憶領域１０を管理し、動的記憶領域１０へのアクセ
スを制御するため、動的記憶領域管理装置２０は、管理
情報格納部３０に上記２つのグループのグループ情報部
を設定する。そして、動的記憶領域１０の初期化と同様
に、オペレーティングシステムの立ち上げの際、メモリ
マップの初期設定時に、グループの個数分のグループ情
報部の初期化を行なう。ここでは、グループの個数が２
個なので、第１グループ、第２グループとしてグループ
情報部を設定する。第１、第２グループともに情報部内
のグループの最大空きサイズ情報には最大値ＦＦＦＦを
設定しておく。第１グループのグループ情報部における
次グループ情報部のアドレスには第２グループの情報部
のアドレスを設定しておく。そして第２グループのグル
ープ情報部における次グループ情報部アドレスには第１
グループの情報部アドレスを設定しておく。つまり、所
定のグループからループ的に全てのグループを順次サー
チできるように次グループ情報アドレスを設定する。

【００３３】次に、各管理単位領域の管理情報部の設定
について説明する。

【００３４】まず、領域内の最大空きサイズ情報とし
て、それぞれ６４ＫＢから当該管理情報部のサイズを引
いた分の大きさを初期的に設定する。次に、グループ内
の各領域のサーチを行なう場合に使用するポインタを設
定する。例えば、第１グループにおける領域１の次領域
アドレスには同じ第１グループの次に位置する領域２の
アドレスを設定する。第１グループの最後尾の管理単位
領域である領域４の次領域アドレスにはＮＵＬＬを設定
する。

【００３５】以上好ましい実施例をあげて本発明を説明
したが、本発明は必ずしも上記実施例に限定されるもの
ではない。

【００３６】

【発明の効果】以上説明したように、本発明の動的記憶
領域管理装置は、第１の効果として、動的記憶領域を複
数のグループに分割して管理し、記憶領域の確保及び解
放を行なうため、記憶領域の確保及び解放を行う場合、
動的記憶領域全体を対象とせず、サイズの小さいグルー
プを特定して目的の記憶領域をサーチできるため、サー
チに要する時間を短縮できるという効果がある。

【００３７】第２の効果として、記憶領域を確保した際
に当該記憶領域を確保したグループを特定する情報を取
得するため、記憶領域の解放を要求する場合に解放しよ
うとする領域を含むグループを指定することができ、記
憶領域の解放を行う際のサーチに要する時間の一層の短
縮化を図れるという効果がある。

【図面の簡単な説明】

【図１】 本発明の１実施例による動的記憶領域管理装
置の構成を示すブロック図である。

【図２】 本実施例の管理情報格納部に格納されたグル
ープ情報部の構成を示す概略図である。

【図３】 本実施例にて管理する動的記憶領域のグルー
プを構成する管理単位領域の構成を示す概略図である。

【図４】 本実施例の領域確保処理部による動作を示す
フローチャートである。

【図５】 本実施例の領域解放処理部による動作を示す
フローチャートである。

【図６】 本実施例の管理情報格納部と動的記憶領域と
の関係を示す概略図である。

【符号の説明】

１０ 動的記憶領域 １１、１２ グループ ２０ 動的記憶領域管理装置 ３０ 管理情報格納部 ３１、３２ グループ情報部 ４０ 領域処理部 ４１ 領域確保処理部 ４２ 領域解放処理部

Claims (4)

【特許請求の範囲】
1. 【請求項１】 記憶装置の記憶領域を複数のグループに
   分割し該グループごとの管理情報を格納する管理情報格
   納手段と、 前記記憶装置の記憶領域中に所定の領域を確保する領域
   確保要求を受け付け、前記管理情報格納手段に格納され
   た管理情報を参照して前記記憶装置の記憶領域の適当な
   グループに所望の領域を確保する領域確保処理手段と、 前記記憶装置の記憶領域中の所定の領域を解放する領域
   開放要求を受け付け、前記管理情報格納手段に格納され
   た管理情報を参照して前記記憶装置の記憶領域の所望の
   グループに所属する該当領域を開放する領域解放処理手
   段とを備え、 前記領域確保手段は、前記領域確保要求に含まれる前記
   グループの指定に応じて該グループから前記領域確保要
   求を満足するサイズの領域の探索を開始し、 前記領域解放手段は、前記領域解放要求に含まれる前記
   グループの指定に応じて該グループから前記領域開放要
   求にて指定された領域の探索を開始することを特徴とす
   る記憶装置の動的記憶領域管理装置。
2. 【請求項２】 前記領域確保処理手段は、 前記領域確保要求により指定されたグループに前記領域
   確保要求を満足するサイズの領域が存在しない場合に、
   他のグループに対して前記領域確保要求を満足するサイ
   ズの領域の探索を行い、 該当領域を検出した場合に、該検出した領域を確保する
   ことを特徴とする請求項１に記載の記憶装置の動的記憶
   領域管理装置。
3. 【請求項３】 前記領域確保処理手段は、前記領域確保
   要求を満足するサイズの領域を確保した場合に、該領域
   の所属するグループを特定する情報を前記領域確保要求
   の発行元に通知することを特徴とする請求項１または請
   求項２に記載の記憶装置の動的記憶領域管理装置。
4. 【請求項４】 前記領域解放処理手段は、前記領域開放
   要求により指定されたグループに前記領域開放要求にて
   指定された領域が存在しない場合に、他のグループに対
   して前記領域開放要求を満足するサイズの領域の探索を
   行い、 該当領域を検出した場合に、該検出した領域を開放する
   ことを特徴とする請求項１または請求項２に記載の記憶
   装置の動的記憶領域管理装置。